Мне дали задание написать для МК (микроконтроллера) циклический буфер для log-сообщений переменной длины (туда входят как двоичная так и текстовая информация), которые будут записываться последовательно во внешнюю память EEPROM или в худшем случае FLASH-память, и при этом после включения питания МК должен восстановить указатели на сообщения, но ту же область памяти можно использовать как для промежуточного хранения прошивки, а после перепрошивки МК должен правильно распознать, что там лежит мусор и переинициализировать указатели. Как это лучше сделать? Есть варианты: 1. использовать ячейки постоянной длины типа массива ссобщений фиксированной длины, невыгодно, так как длина сообщений может варьироваться в больших пределах, да и неэкономно на флешке маленького объема. 2. использование маркера тоже не понятно, как различить где начало и конец, а где наехало новое сообщение. Вообщем то, нужно чтоб на одну и ту же область памяти не записывалось много раз, а равномерно распределялось по всей области памяти. Нужен совет, или ссылочку на какое-нибудь готовое решение. Спасибо.

 На ум приходит только что-то типа связанного списка. Т.е. каждое сообщение имеет структуру: 1. длина. 2. идентификационный номер (ID).3. само сообщение. 

Прошивки должны записываться также как и обычное сообщение. Если в сообщении имеется время то ID не нужен, если же нет, то нужен и максимальный ID должен быть как минимум на 1 больше чем максимально возможное количество сообщений, хранящихся в памяти при их минимальной длине. Иначе с поиском будут проблемы.

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

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

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

PS. Кажется, лучше в качестве маркера использовать двухбайтовое значение. Допустим 0x00 0x55

Насчет маркера то, что вы предлагаете, это что-то вроде SLIP-протокола для модема, там как раз используется метод замены одного ключевого символа(то ли стопового, то ли стартового, я не помню) двумя, я уже рассматривал этот вариант, невыгодно с точки зрения экономии памяти. А вот идентификационный номер (ID) тоже неоднозначно, допустим, однобайтовый текущий номер 0xFF, а следующий будет 0, какой последний пакет, а какой первый? Тем более допускается, что при заполнении буфера новые сообщения записываются поверх самых старых, то есть могут наехать на старые, оставив ему маркер. Время используется в формате NTP, как счетчик, при этом вероятность совпадения маркера с меткой времени должна быть ближе к нулю. Должны ведь готовые решения, неужели их нет?

Я то думал вы оперируете сотнями мегабайт - гигабайтами , там-то пару байт не жалко.



Прежде всего я бы ID 0xff запретил, т.е. максимальный номер допустим 0xfe. Если Вы в дальнейшем на Flash перейдете 0xff будет в пустых ячейках. 

Теперь о главном. Я не зря сказал, что максимальный номер ID должен хотя бы на 1 быть больше возможных сообщений. Дальше буду использовать слово ячейки, и оперировть ячейками одинаковой длины. Тоже самое справедливо и для переменной длины. Только прежде чем записывать следующую запись поверх предыдущих, нужно, скорее всего, (сами это додумаете) удалять предыдущие ячейки по границам сообщений. Допустим память имеет 254 ячейки (0x00-0xfd). Тогда можем использовать 1байт с максимальным номером 255 (0xfe). В этом случае при первом заполнении доходим до 0xfd и в нулевую ячейку ляжет запись с ID 0xfe вместо предыдущей 0x00. На место записи с ID 0x01 ложится запись с ID 0x00. Допустим начинаем поиск. Смотрим в нулевую ячейку. ID 0xfe. Рассчитываем следующий ID - 0x00. Находим следующую запись. В ней ID 0x00. Находим следующую. В ней ID 0x02, а должен быть на 1 больше предыдущего - 0x01. Следовательно эта запись с ID 02 - начало рулона, а запись с 00 - конец, т.е. последняя. 



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

barabek, спасибо!