Прибор должен сохранять лог измеряемых данных в DataFlash 32Мбит в худшем случае каждые 3 секунды по одной или несколько строк из 16 байт. Работа прибора непрерывная с непредсказуемыми перерывами (может вкл./выкл. в любое время с любой частотой). Батарейного питания на плате нет. Срок жизни прибора лет 10 (может и больше ).
Где лучше хранить указатель на конец данных и как это все получше организовать?

Посколько DataFlash не позволяет писать меньше страницы в 512 байт, то планирую кешировать данные в буфере. При кешировании указатель будет в ОЗУ. При сохранении страницы во флеш и при вкл/выкл прибора действия могут быть разными. Придумал два варианта:

1. Сохранять указатель в одной ячейке EEPROM AVR только при выкл. прибора, а при вкл. грузить его в ОЗУ и с ним работать.
+ простота алгоритма
- проблема в случае сбоя записи при выкл.: нужно искать конец данных в 32Мбит DataFlash

2. Сохранять указатель в циклическом буфере ячеек EEPROM не только при выкл. прибора, но и при записи страницы во флеш.
Циклический буфер указателей нужен из-за малого ресурса перезаписи у EEPROM.
- сложности с организацией циклического буфера указателей
+ всегда можно будет найти предыдущий указатель и конец данных.

Какие есть еще варианты и соображения?

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

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

Давно использую в приборе для архива 45DB021. Тоже все начиналось с кеша в буфере DBшки (по выключению питания сливал его во флеш, пока еще от емкостей жил). Указатель не хранил, а просто при заполнении буфера стирал следующую страницу и писал текущую. При старте искал страницу из 0xFF, потом не из 0xFF и считал ее за начало. Благо командой сравнения буфера и собственно флеша сделать это можно быстро.
Но вот незадача - начали поступать рекламации на некоторые приборы, что выключаешь питание, включаешь - нет событий последних (не сливало кеш). Решил вопрос следующим образом. Страница очищается, а затем каждый раз в буфере создается нужная запись (на нужном месте), а остальное заполняется 0xFF и затем делается запись без стирания. Запись происходит из 1 в 0, т.е. новые данные флеш=старые данные and данные в буфере. В результате ресурс ячеек тот-же, что и с кешированием, а запись происходит непосредственно. Теперь нареканий нет
Правда, идея с такой разделенной записью непосредственно в даташите не описана. Я сначала поставил эксперимент, а потом, напуганый коллегами (типа, нет в даташите, не будет работать ) отыскал в каком-то апноте Atmel'а такой алгоритм. Только нифига не помню в каком. Но точно был.

Это я прикинул. Почти крайний случай - запись страницы раз в минуту.
Год = 365*24*60=525600 минут. За 10 лет = 5.5 млн.записей / 10^5 (ресурс EEPROM)= 55 раз
Буфер из 64 указателей выдерживает такую нагрузку.
Только вот сразу проблемы с алгоритмом:
- Как менять ячейку (по какому алгоритму)
- Как запоминать её (указатель на указатель ) Просто тупо искать среди них самый последний (по величине)??


Объемы флешки у вас не те. В 2Мбитах можно и каждый раз искать, у меня 32М.
А запись в предварительно очищенную страницу нынче штатный режим, я так и собираюсь делать, поскольку время Стирание/Запись 17-40 мс, а просто Запись 3-6 мс.

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

со связанным списком сложно получится - нужно будет по границе страницы начало записи делать (не допускать, чтобы середина записи попадала на границу страницы) - а это потерянный объем... Второй момент - если уже пошло кольцо, а последняя запись последняя на странице - нужно будет обязательно обнулять указатель на голову первой записи предыдущей страницы.
В общем, когда делал такое, наиболее простым показалось присваивать каждой записи номер. Диапазон должен быть больше чем максимальное количество записей в объеме флешки, тогда гарантированно можно найти начало и конец, даже если запись последней страницы не удалась

Скорость поиска в 32Мбит всего лишь в 4 раза дольше чем в 2Мбит флешке...
Тока при производстве нужно стирать всю флешку...

У меня строки по 16 байт, кратно размеру страницы, проблем тут не вижу.
Реализация кольцевого буфера тоже не вызывает вопросов, такое делал, ничего сложного - два указателя, один догоняет другого
Вопрос не в этом, а в том, где и как сохранять эти указатели при вкл/выкл прибора и нужно ли их вообще сохранять - может быть проще каждый раз искать границы данных "роясь" во флешке.


Я понимаю, что можно искать, например, методом "деления отрезка пополам" и кол-во шагов при этом будет не очень большим. НО: это все же ВНЕШНЯЯ SPI флешка, доступ к ней довольно длительный

Можно поставить рядышком NVRAM (с RTC) и хранить в нем адрес.
проблема отпадет сама собой.

Если же RTC использовать не нужно/дорого, и хранить адрес в eeprom, то что мешает записывать не только указатель, но и порядковый номер записи, по которому потом и находить последнюю запись.

Полагаться на мусор во флеш я бы не стал.

А сколько времени Вы готовы потратить на поиск? Я ж говорю, надо искать коммандой "Main Memory Page to Buffer Compare", это у меня 200мкс. Щас под рукой pdf'а на 32хмегабитную нет, но если данные такие же, то поиск займет 8192 страниц*200мкс=1.6секунды. Если это много, тогда конечно хранить указатели.



Если будете организовывать кольцевой буфер, то не выстрелит. Потому как дырка может быть в любом месте.

вы знаете, что такое связанный список? в каждой записи хранится указатель на предыдущую и указатель на последующую запись. У головы списка указатель на предыдущую равен 0, у хвоста - указатель на следующую равен 0. Таким образом перебором всех записей можно найти первую и последнюю. НО! для реализации лога во флешке такой вариант не надежен - если самые старые записи начали затираться новыми, при сохранении последней записи нужно модифицировать следующую (которая станет головой списка). Если вы при этом рубанется питание, а голова находится в следующем секторе и вы не успели его модифицировать, гарантированное начало списка вы скорей всего не найдете.
Поэтому лучше каждой записи присваивать порядковый номер, на единицу больший предыдущей. Диапазон должен быть больше максимального количества записей, чтобы не было двойного переполнения.
В этом случае всегда можно найти начало и конец списка при любых конфликтах. Естественно, если требуется удалять записи в середине списка такой метод не прокатит. Опять же, сложно будет организовать чтение произвольной записи, но для лога этого обычно не нужно.
Хранить указатели на начало и конец где-то в другом месте не разумно. А поиск действительно делается в течении ~1-2 секунд при включении устройства. У меня еще каждая запись имеет CRC, поэтому чуть дольше. И не стоит закладываться на фиксированный размер записи, сделайте универсальное решение.

32Mb состоит из 4096 секторов, следовательно для поиска свободного сектора требуется чтение и анализ 12 секторов ( 2^12=4096), это заимет меньще 0,2 с.

NVRAM (с RTC) ставить нет смысла для одной функции.
А чем принципиально отличается сохранение указателя от сохранения порядкового номера записи?


Глобально я еще взаимодействие всех функц.блоков модуля при старте не прорабатывал, так что насчет времени поиска ничего сказать не могу. Секунда, наверное, будет не критична. Но непонятно, а как вы предлагаете искать при помощи "Main Memory Page to Buffer Compare"? С чем сравнивать?

Методом "деления отрезка пополам" для кольцевого FIFO, конечно, не годится . Это я для случая фиксированного начала записи говорил.


Для моего случая связанные списки не нужны. У меня линейная структура записей (FIFO). Никакого перемешивания быть не может.

з.ы. нужно прикинуть алгоритм и время поиска. Если уложусь в ~1 сек, то это будет проще чем EEPROM (???)

Расскажите, как использовать бинарный поиск, если организован кольцевой буфер и дырка (т.е. начало и конец) где-то в середине?




У вас конец буфера маркируется пустым сектором из одних 0xFF. Т.е. реальная емкость буфера колеблется от (N-2)/sizeof(Record) до (N-1)/sizeof(Record) - как минимум, один сектор всегда пустой. Сравнивать конечно с буфером, заполненым 0xFF

Я ж вам написал: если старые записи затираются новыми, то если использовать связанный список, нужно модифицировать следующую запись, указывать что она первая. Если эта запись находится в другом секторе, но нужно сначала сохранить текущий, а потом считать-изменить-сохранить другой. Есть вероятность что может пропасть питание между сохранением текущего и модификацией следующего сектора. Это все, финиш, начала и конца вы не найдете.
Вариант с пустым сектором как маркером конца мне тоже не нравится - потому что придется записи сохранять по границе сектора (ну а запись может быть чуть больше половины сектора - какой овехед получается) и опять же никто не гарантирует что не пропадет питание...
С индексом записи (который в каждой записи и хранится) таких проблем не будет. Когда бы не пропало питание вы всегда сможете найти начало и конец, даже если текущий буфер сектора будет потерян.
А алгоритм поиска прост - перебираете все записи, вычисляете CRC, контролируете индексы. Это же сделать надо один раз при включении питания, дальше указатели храняться в ОЗУ

Тем что можно писать в произвольные сектора.

Вы видимо не совсем поняли идею. Запись организовывается примерно так



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

А что будет, если ErasePage из-за пропадания питания не выполнится и следующая страница не пустая?
ИМХО предложение AlexB более надежное. Кроме того, не нужно деление.

Если вдруг из-за понижения питания не сработает ErasePage, то дальше дело не пойдет, процессор просто упадет в сброс от BOD'а. Тут конечно, надо процедуру PageErase делать правильную, с тестом, стаботало или нет. И, например, повторять, пока не очистится. Вообщем, такой алгоритм получается вполне транзакционный (если не учитывать то, что самые старые записи могут быть выброшены до записи новой, но это не беда, если это архив событий).


Если все числа будут кратны 2, то деление и остаток будут преобразованы компилятором в сдвиги и and. Так что тут не волнуйтесь.

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

Вопрос в придумывании наиболее простого и быстрого алгоритма.


Вашу мысль все равно не понял


+1
Вот до этого я уже сам додумался, этот алгоритм мне нравится больше всего.

------------
to All: А другие мысли есть?
В EEPROM никто эти указатели не сохраняет?

В другом приборе сохраняет указатели в EEPROM. Результат: при меньшем количестве произведенных приборов (ну раз в 10 ориентировочно) замечания чаще.

При каждой записи во флеш увеличивать некий счетчик, записывать в кольцевой буфер внутренней eeprom младший байт этого счетчика (sequence записи), адрес флеш и crc8.
После рестарта - вычитать кольцевой буфер в ОЗУ, пробежаться по всем элементам, найти i-й элемент для которого справедливо условие
sequence[i] == sequence[i - 1] + 1;
sequence[i] != sequence[i + 1] - 1;
вытащить из этого элемента адрес флеш. Инициализировать счетчик числом "i + 1".

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

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

А я в свое время хранил адрес следующей записи(или как вы его называете - указатель) в ЕЕПРОМ, но записывал его туда не после каждой записи, а только при выключении питания, которое контролировал встроенным компаратором, и пока разряжались конденсаторы все успевал сделать и даже хранилось все это в одной ячейке ЕЕПРОМ(это был мой первый проект на незнакомом до этого AVR так что не пинайте сильно). Кстати данные во флешке я тоже модифицировал в буфере AT45 а буфер в страницу записывал по заполнению буфера или по сигналу того же компаратора при выключении питания. При включении прибора читал указатель в ОЗУ и работал с ним далее до выключения.

Вот и у меня так было (только без указателя в EEPROM). В 2001 году. Потом переделал.

Где-то был описан простой способ "размазывания" данных по EEPROM (для сохранения ее ресурса):

Предположим, нужно "размазать" 1 байт данных, имея массив из 100 байт в EEPROM. Для этого в программе организуем счетчик от 0 до 99, который инкрементируется при каждой записи. В ячейку EEPROM по адресу этого счетчика пишем такое значение, чтобы XOR всех 100 ячеек было равно запоминаемому числу. В итоге максимальное количество записей возрастает в 100 раз.

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

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

to defunct: все понял, спасибо. Наконец-то до меня дошло, что вы говорите об алгоритме сохранения указателя в EEPROM

to DenisN: интересный алгоритм


Все-таки склоняюсь к методу, предложенному Rst7. С EEPROM сложновато получается.