Круговой буфер во вспышке

Question

Мне нужно хранить элементы различной длины в круговой очереди во флэш-чипе.Каждый элемент будет иметь свою инкапсуляцию, чтобы я мог определить, насколько он велик и где начинается следующий элемент.Когда в буфере будет достаточно элементов, он будет перенесен в начало.

Каков хороший способ сохранить циклическую очередь во флэш-чипе?

Существует вероятность того, что я хотел бы сохранить десятки тысяч предметов.Таким образом, начинать с начала и читать до конца буфера не идеально, потому что для поиска до конца потребуется время.

Кроме того, поскольку он круглый, мне нужно уметь отличать первый элемент от последнего.

Последняя проблема заключается в том, что это хранится во флэш-памяти, поэтому удаление каждого блока занимает много времени и может быть выполнено только определенное количество раз для каждого блока.

Answer 1

Во-первых, управление блоками:

Поместите заголовок меньшего размера в начале каждого блока.Главное, что вам нужно для отслеживания "самого старого" и "самого нового", - это номер блока, который просто увеличивается по модулю k. k должно быть больше вашего общего количества блоков.В идеале, сделайте k меньше вашего МАКСИМАЛЬНОГО значения (например0xFFFF) таким образом, вы можете легко определить, что такое удаленный блок.

При запуске ваш код по очереди считывает заголовки каждого блока и находит первый и последний блоки в последовательности, равной n_i+1 = (n_i + 1) ПО МОДУЛЮ k.Следите за тем, чтобы не запутаться в удаленных блоках (номер блока равен, например,0xFFFF) или данные, которые каким-либо образом повреждены (напримернеполное стирание).

Внутри каждого блока

Каждый блок изначально начинается пустым (каждый байт равен 0xFF).Каждая запись просто записывается одна за другой.Если у вас есть записи фиксированного размера, то вы можете получить к ним доступ с помощью простого индекса.Если у вас есть записи переменного размера, то для их чтения вам нужно сканировать с начала блока в стиле связанного списка.

Если вы хотите иметь записи переменного размера, но избегать линейного сканирования, то у вас мог бы быть четко определенный заголовок для каждой записи.Например.используйте 0 в качестве разделителя записи, и ПОЧАТКИ-кодировать (или ПОЧАТКИ/R-кодировать) каждую запись.Или используйте байт по вашему выбору в качестве разделителя и "экранируйте" этот байт, если он встречается в каждой записи (аналогично Протокол PPP).

При запуске, как только вы узнаете свой последний блок, вы можете выполнить линейное сканирование для поиска последней записи.Или, если у вас есть записи фиксированного размера или разделители записей, вы могли бы выполнить двоичный поиск.

Стереть планирование

Для некоторых микросхем флэш-памяти удаление блока может занять значительное время - например5 секунд.Подумайте о том, чтобы запланировать стирание в качестве фоновой задачи немного "загодя".Например.когда текущий блок заполнится на x%, начните стирать следующий блок.

Нумерация записей

Возможно, вы захотите пронумеровать записи.Способ, которым я делал это в прошлом, заключается в том, чтобы помещать в заголовок каждого блока номер первой записи.Затем программное обеспечение должно вести подсчет номеров каждой записи внутри блока.

Контрольная сумма или CRC

Если вы хотите обнаружить поврежденные данные (напримернезавершенная запись или удаление из-за неожиданного сбоя питания), затем вы можете добавить контрольную сумму или CRC к каждой записи и, возможно, к заголовку блока.Обратите внимание, что CRC заголовка блока будет охватывать только сам заголовок, а не записи, поскольку он не может быть перезаписан при записи каждой новой записи.

Answer 2

Сохраните отдельный блок, содержащий указатель на начало первой записи и конец последней записи.Вы также можете сохранить дополнительную информацию, такую как общее количество записей и т.д.

Пока у вас изначально не закончится свободное место, добавлять записи так же просто, как записывать их в конец буфера и обновлять конечный указатель.

Поскольку вам необходимо освободить место, удалите достаточное количество записей, чтобы вы могли разместить свою текущую запись.Обновляйте указатель заголовка по мере удаления записей.

Вам нужно будет отслеживать, сколько дополнительного места было освобождено.Если вы сохраните указатель на конец последней записи, то в следующий раз, когда вам нужно будет добавить запись, вы можете сравнить ее с указателем на первую запись, чтобы определить, нужно ли удалять еще какие-либо записи.

Кроме того, если это NAND, вам или контроллеру флэш-памяти потребуется выполнить деблокировку и выравнивание износа, но все это должно быть на более низком уровне, чем выделение места для циклического буфера.

Answer 3

Думаю, теперь я все понял.Похоже, ваша самая большая проблема будет заключаться в том, что после заполнения доступного места для записи, что происходит дальше?Новые данные должны перезаписать самые старые данные, что, я полагаю, вы подразумеваете под циклическим буфером.Но поскольку данные не имеют фиксированной длины, вы можете перезаписать более одной записи.

Я предполагаю, что степень вариабельности длины достаточно высока, что заполнение всего до фиксированной длины не является вариантом.

Ваш сегмент записи должен отслеживать адрес, который представляет начало следующей записи для записи.Если вы заранее знаете размер блока для записи, вы можете определить, попадете ли вы в конец логического буфера и начнете все сначала с '0'.Я бы не стал делить пластинку на несколько частей в конце и несколько в начале.

Отдельный регистр может отслеживать начало;это самые старые данные, которые еще не были перезаписаны.Если бы вы отправились зачитывать данные, вы бы начали именно с этого.

Затем устройство записи данных проверит, учитывая адрес начала записи и длину данных, которые оно собирается зафиксировать, следует ли ему активировать регистр чтения, который проверит первый блок и увидит длину, и перейдет к следующей записи, пока не останется достаточно места для записи любых данных.Вероятно, между окончанием записанных данных и началом самых старых данных возникнет пробел в ненужных данных.Но таким образом, вы можете просто записать один или два адреса в качестве служебных данных, а не переставлять блоки.

По крайней мере, это, вероятно, то, что я бы сделал.HTH

Answer 4

Я вижу три варианта:

вариант 1:заключается в том, чтобы заполнить все до одинакового размера, это просто, сохраните указатель на начало и конец буфера, чтобы вы знали, куда записывать и с чего начинать чтение, используйте размер каждого объекта, чтобы получить смещение к следующему, это означает, что вам нужно перемещать буфер так, как вы бы делали со связанным списком, он же медленный, если вам нужен элемент 5000.

вариант 2:заключается в том, чтобы хранить только указатели на реальные данные в циклическом буфере, таким образом, при выполнении цикла вам не придется иметь дело с несоответствиями размеров.если вы храните реальные данные в циклическом буфере и не заполняете их, вы можете столкнуться с ситуациями, когда вы заменяете несколько элементов 1 новым объектом данных, я предполагаю, что это не нормально.

храните фактические данные в другом месте флэш-памяти, в большинстве флэш-памяти будет встроено какое-то выравнивание износа, если это так, вам не нужно беспокоиться о перезаписи одного и того же местоположения несколько раз, микросхема сама определит, где на самом деле хранить их на чипе, просто запишите в следующее доступное свободное место.

это означает, что вам нужно выбрать максимальный размер циклического буфера, то, как вы это сделаете, зависит от изменчивости данных.Если размер данных просто сильно изменился, скажем, всего на несколько байт, то вам следует просто заполнить их и использовать вариант 1.Если размер меняется сильно и непредсказуемо, выберите максимально возможный размер и подсчитайте, сколько объектов такого размера поместилось бы в вашем flash, используйте это как максимальное количество записей в буфере.Это означает, что вы тратите впустую кучу места.

вариант 3:если объект действительно может быть любого размера, то в тот момент, когда вам следует просто использовать файловую систему, назовите файлы по порядку и вернитесь к полному, имея в виду, что если ваша новая запись большая, вам, возможно, придется удалить несколько старых записей, чтобы она поместилась.На самом деле это просто расширение варианта 2, поскольку option2 во многих отношениях является простой файловой системой.

Answer 5

"Цикличность" во флэш-памяти может быть выполнена на основе размера блока, что означает, что вы должны указать, сколько блоков флэш-памяти вы выделяете для этого буфера.

Фактический размер буфера будет находиться в каждый конкретный момент времени между n-1 (n - количество блоков) и n.

Каждый блок должен начинаться с заголовка, содержащего порядковый номер или временную метку, которые могут быть использованы для определения, какой блок старше другого.

Каждый элемент инкапсулирован в верхний и нижний колонтитулы.заголовок по умолчанию содержит все, что вы хотите, но в соответствии с этим заголовком вы должны знать размер элемента.Нижний колонтитул по умолчанию равен 0xFFFFFFFF.Это значение указывает на нулевое завершение.

В вашей оперативной памяти вы должны сохранить указатель на самый старый блок и последний блок, а также указатель на самый старый элемент и последний элемент.При включении питания вы просматриваете все блоки, находите соответствующие блоки и загружаете эти элементы.

Когда вы хотите сохранить новый элемент, вы проверяете, достаточно ли места для этого элемента в последнем блоке.Если это так, вы сохраняете элемент в конце предыдущего элемента и изменяете предыдущий нижний колонтитул, чтобы он указывал на этот элемент.Если в нем недостаточно места, вам нужно стереть самый старый блок.Перед удалением этого блока измените самые старые элементы блока (RAM), чтобы они указывали на следующий блок, а самый старый элемент - на первый элемент в этом блоке.Затем вы можете сохранить новый элемент в этом блоке и изменить нижний колонтитул последнего элемента, чтобы указать этот элемент.

Я знаю, что объяснение может показаться сложным, но процесс очень прост, и если вы напишете его правильно, вы можете сделать его даже безаварийным (всегда помните о порядке записи).

Обратите внимание, что округлость буфера не сохраняется во флэш-памяти, но флэш-память содержит только блоки с элементами, порядок расположения которых вы можете определить в соответствии с заголовками блоков и заголовками элементов