Мне дали задание для микроконтроллера (не важен какой, главное, алгоритм) написать циклический буфер переменной длины, равномерно распределенный по всей памяти (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% гарантию, все может найтись