Мне дали задание для микроконтроллера (не важен какой, главное, алгоритм) написать циклический буфер переменной длины, равномерно распределенный по всей памяти (NAND Flash или EEPROM), чтоб исключить перезапись в одну и ту же область памяти из за их ограничения числа записи-стирания. Там будут храниться сообщения передаваемые куда-то, новые сообщения по мере переполнения буфера затирают старые, при включения питания микроконтроллера нужно восстановить указатели на начало и конец рулона. Приходит мысль об использовании маркера и ID ячейки, больше ничего придумать не смог.. Нужен совет.. Код только на СИ, допускается использование библиотечных функции тип printf, безо всякого malloc или alloc. Спасибо. 

Не до конца понял что надо, но вроде бу тут уместно использование связанных списков.
Извиняюсь, если ерунду сказал. Не до конца понял что требуется...

Если есть EEPROM с большим ресурсом, то смещения начала и конца буфера можно хранить в специально отведенных для этого ячейках EEPROM'а. (Лучше в 2х копиях с контрольной суммой, что бы можно было отловить случаю выключения питания при их записи).
Если EEPROM'а нет, то можно признаки начала и конца буфера писать прямо в самом буфере в виде специальных байтов (1 спец. в начале, 2й - в конце). Что бы эти байты не встречались внутри буфера нужно их экранировать 3м специальным байтом (писать в виде 2х байтовой ESC последовательности).
При старте контролера сканировать FLASH и искать маркеры.

Кстати, сделать совсем независимым от типа применяемого FLASH не получится - у каждого FLASH есть свои требования по размерам записываемого и стираемого блока

  Добавить признак того что ячейка была удалена (всего 1 бит). Также важно чтобы число ячеек в одном стираемом блоке было целым. Сначала делает бинарный поиск начала, затем конца циклического буфера. Еще такой момент, нужно знать при стирании чего записывается в ячейки нули или единицы. Если нули то признак стирания бит 1, если единицы, то 0.

Поменять 1 бит в NAND FLASH может не получиться (только стерев весь блок).
И вообще задача СИЛЬНО зависит от геометрии и способа записи FLASH'а. Например, если FLASH может записываться только блоками, имеет смысл сделать в начале каждого блока монотонно увеличивающийся счетчик (битов так на 32). Этого должно хватить на полное восстановление всех указателей (записи и чтения)

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

Добавлено через 4 минуты и 34 секунды

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

Я на эту тему думал, а что если МК не успел записать указатели начала и конца в момент выключения питания, в EEPROM долго пишется как горячие эстонские пааарни, это отпадает.   


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

Добавлено через 14 минут и 42 секунды
Есть предложение, прокомментируйте плиз..
Начало сообщения - маркер, пусть будет 0xAA55, конец - тоже маркер 0xBB66, внутри Id который позволит нам выявить где начало и конец, то есть например текущее сообщение имеет ID=3, а следующее ID = 4, пропускаем, затем идет ID=7, значит сообщение ID=4 - конец рулона, а с ID=7 начало рулона.. Когда происходит затирание новыми старых сообщений, мы ищем следующий маркер и делаем его хвостом. И еще один момент, эта область памяти используется для перепрошивки, поэтому там может оказаться мусор. Неужели нет готовых решений? 

Это сообщение отредактировал(а) daemonaz - 28.10.2010, 12:21

  На счет готовых лучше спрашивать тут http://forum.vingrad.ru/forum/tech-control...rogramming.html .

Мне дали задание для микроконтроллера (не важен какой, главное, алгоритм) написать циклический буфер переменной длины, равномерно распределенный по всей памяти (NAND Flash или EEPROM), чтоб исключить перезапись в одну и ту же область памяти из за их ограничения циклов записи-стирания. Там будут храниться сообщения передаваемые куда-то, новые сообщения по мере переполнения буфера затирают старые, при включения питания микроконтроллера нужно восстановить указатели на начало и конец рулона. Приходит мысль об использовании маркера и ID ячейки, больше ничего придумать не смог.. Нужен совет и рекомендации.. Код только на СИ, допускается использование библиотечных функции тип printf, безо всякого malloc или alloc. Если есть готовые решения, буду благодарен.. Спасибо.  

Можно конечно, но у NAND FLASH есть еще одна особенность - ее рекомендуют записывать последовательно, т.е. не перезаписывая один и тот же блок по 2 раза подряд. Иначе ее ресурс упадет   


Ну он же не каждый байт будет двумя делать


В таком случае эти последовательности внутри буфера так же придется ESC'апить. Т.е. ровно то, что я предлагал (только я предлагал маркеры одно байтовые)

  Может имелось ввиду 2 раза со стиранием? Без стирания не должно быть проблем.

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


Это сообщение отредактировал(а) daemonaz - 28.10.2010, 17:14

Там не может быть мусора, который совпадет с маркерными байтами, т.к. таких байтов в теле предыдущих записей быть не может (они esc'апятся), а FLASH при стирании никогда не заполняется мусором.

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

И вообще, у вас FLASH блочная, или она умеет писаться побайтно? (в последнее верится с трудом)
Если первое, то вам надо ориентироваться именно на блочную структуру записи (см мое 2е сообщение назад)

Добавлено @ 17:51
Могут быть. У разных производителей свои заскоки   


Это сообщение отредактировал(а) xvr - 28.10.2010, 17:54

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

есть разметка в EEPROM

LOG_BUF_START 0x100
LOG_BUF_SIZE   256
LOG_BUF_END   LOG_BUF_START+LOG_BUF_SIZE

вот мой сектор, что хочу что и делаю с ним.. 

Будет не геморой, а полное переписывание всего с нуля. 
Свою область стереть нельзя?   
Один раз это сделать можно, но потом, когда начнется запись лога, это уже не будет мусор. Так что надо либо явно прописывать метку конца и перезаписывать ее с каждой новой записью (что отрицательно скажется на ресурсе флэша), либо все же протереть свое место (один раз). Надеятся на то, что каких то многобайтовых последовательностей в старом образе прошивки не найдется нельзя - это не даст 100% гарантию, все может найтись   

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

Это сообщение отредактировал(а) daemonaz - 28.10.2010, 21:21

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

Элементарно. В начале лога располагается специальный многобайтовый маркер, который в принципе не может встретится в этом месте в образе прошивки для МК. Обычно такой маркер можно выбрать, т.к. в начале прошивки МК обычно лежат какие то фиксированные данные,  типа векторов прерывания или чего то похожего. И у этих данных вполне регулярная структура.
Если модуль логирования не находит этого маркера, он стирает всю область и пишет маркер (собственно сам маркер после этого не меняется)

Это подразумевает 2х кратное переписывание каждой ячейки EEPROM с маркером. Не очень хорошо.

Кроме того, проблема с неинициализированным после перепрошивки буфером не решается - в нем вообще никаких маркеров не будет

  Я у себя использовал такой 0xAAAAAAAA  . Бинарно это выглядит как заборчик 101010101010101... . Специально такого не будет что 32 бита заборчика и глазами если что легко увидеть в дампе.

Осталось самая малость - найти p_beg, p_end; при включении МК, причем в EEPROM их записывать нельзя   

...
Почему нельзя?

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

Потому что у него NAND FLASH (будет), который необходимо записывать/перезаписывать последовательно (для достижения заявленного ресурса перезаписей). Сохранить указатели в EEPROM я ему посоветовал еще в 3м сообщении (если есть EEPROM с достаточным ресурсом перезаписей)

да и еще нужно писать сообщения переменной длины, не забывайте!  

Вообщем-то я понял так, в начале лога пишется длинный маркер, по которому мы определяем, была ли перепрошивка или нет, если такой маркер присуствует, то ишем указатели, иначе стираем всю область памяти, и cтолбим этот же маркер. Далее хотим мы записать новое сообщение, по предложению уважаемого xvr, вводим  ESC-последовательность, чтобы выделить начало и конец сообщения, у каждого сообщения будет свой ID, по ID будем определять где head и где tail. При включении МК ишется разница между ID,   если она больше 1, то сообщение с малым ID - head, а с большим ID - tail. теперь заполнили всю область LOG, нужно записать новое сообщение, вот здесь как быть? Либо весь блок Flash отдать под одно сообщение, что слишком жирно, или каждый раз нужно переписывать этот блок, либо стереть этот блок и начинаем писать заново? Мой моск разваливается..   

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

Mazzi абсолютно прав - маркеров нужно 2 (что бы корректно определить целые записи). ID должен быть достаточного размера, что бы полностью заполненный FLASH при минимальной длине каждой записи не вызвал переполнение ID (причем нужен как минимум 2х кратный запас).
Записи пишутся во FLASH по кольцу (как в исходнике от Mazzi), при переполнении новые записи начинают затирать старые.
При старте ищутся первая и последняя целая запись (должны присутствовать оба маркера), и извлекаются их ID. Затем ID сравниваются на больше-меньше (с учетом возможного переполнения, т.е. если старшие биты у них разные, то произошло переполнение и ID с нулевым старшим битом считается больше, чем ID с единичным старшим битом). 
Собственно все - запись с большим ID будет головой (писать надо сразу после нее), запись стартует со следующего ID. 
Запись с меньшим ID становится указателем чтения.

это конечно не по теме, не хочу открывать новую ветку.. Вопрос, как вычислить кратность некоторому числу без деления с остатками?
например, если 16 делится на 8, используется 16%8=0, не делится 15%8!=0, как это сделать без деления?
второе,  как вычислить наибольшее ближайшее данному числу кратное некому числу без цикла? Например, у нас число 13, он не делится на 8, доводим его 16. 
Я делаю так..

 

Есть ли быстрый и эффективный способ?

Если это 'некоторое число' - степень двойки, то элементарно: (x&(N-1))==0 - число x кратно N

x - число, N - выравнивание (должно быть степень двойки)

В общем случае (если N НЕ степень двойки)
или

xvr, огромное спасибо!