Циклический буфер переменной длины

asket76 · 28.10.2010, 20:34

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

MasterMushi · 28.10.2010, 21:40

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

Минус метода - придется искать патерны циклом или делать неравномерные указатели (в отдельный блок пишем мини массив маркеров указателей откуда надо начинать искать. Эти же указатели также перемещаем по кругу как и основные данные).
Плюс метода - гарантировано точно определение актуального маркера плюс все сбои будут известны.

Alex9797 · 28.10.2010, 22:07

Сообщение от MasterMushi

Программа смотрит последовательно на структуру и ищет там число соответствующее паттерну

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

MasterMushi · 29.10.2010, 15:00

Alex9797, Поэтому и организуем структуру а не одномерный поток данных.
К примеру данные сгруппированы по блокам, как фактически и ведется запись в NAND. Тогда последние 4 байта блока - контрольный паттерн. с забитым внутрь битом четности или контрольной суммой.
Если будет сбой в блоке - собьется сам паттерн, если будет сбой данных - то свалится бит четности или контрольная сумма, смотря что применяли.

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

asket76 · 30.10.2010, 12:19

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

MasterMushi · 30.10.2010, 12:56

asket76, =)))) А нам и не принципиально куда писать. начало, конец, один блок, два блока или пол блока главное знать четко - есть сообщение и есть паттерн и они ВСЕГДА находятся в строгом порядке где-то на флеше.
Паттерн мы переписываем вот для чего
К примеру
Нам пришло сообщение
"Мама мыла раму"
На флеш мы пишем
"Мама мыла раму", *0101010101010101010101010101010
где * - это бит четности сообщения

Приходит второе собщение.
"А роза упала на лапу Азора"
мы пишем на флеху в предыдущую запись паттерн "не актуально"
*1010101010101010101010101010101 чтобы получилось
"Мама мыла раму", *1010101010101010101010101010101
Тоесть инвертируем "актуально"

А в новый блок пишем сообщение и паттерн-маркер актуальности
"А роза упала на лапу Азора", *0101010101010101010101010101010

И вот проходим N-ое количество циклов перезаписи и однажды когда мы
смотрим куда бы записать сообщение находим там паттерн который не соответствует шаблону:
01110101010101110101011101011101
Сразу понятно что гдето чтото не стерлось или потерялось.
Тогда мы это блок просто пропускаем.

Важное условие - паттерны проверяем ДО записи в блок сообщения. А лучше не просто проверяем чтением но и делаем пробную запись. Это сократит количество перезаписей вдвое, зато нивелирует вероятность сбоя. А так как мы пишем по циклу, то общее время службы будет столетия!!! Что в принципе делает даже тройную проверку несущественной причиной проблем. А так как срок службы любого оборудования ограничено 25-50 годами, то можно флеху гонять проверками до полного психологического комфорта.

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

Как проверять патерны быстро на истинность?
Простой операцией исключающее или
pattern1 XOR pattern2
что на 32х разрядных процессорах делается в один прием. И результат работы должен быть 0х7FFFFFFF или 0хFFFFFFFF в зависимости от установленного бита четности
Если значение паттерна будет отличаться - блок сбойный

asket76 · 31.10.2010, 14:43

Сообщение от MasterMushi

мы пишем на флеху в предыдущую запись паттерн "не актуально"
*1010101010101010101010101010101 чтобы получилось
"Мама мыла раму", *1010101010101010101010101010101
Тоесть инвертируем "актуально"

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

picavr · 31.10.2010, 14:57

Сообщение от asket76

Но ведь надо перезаписывать дважды маркер, что ни есть хорошо.. Может я неправильно понял?

Типа да, патерн переписывается в 2 раза чаще чем само сообщение, следовательно он уменьшает в 2 раза количество перезаписей.
А теперь умножте (количество перезаписей/2) для используемой EEPROM на количество умещающихся в обьём EEPROM сообщений и получите количество возможных перезаписей сообщений.
1 000 000 колич перезаписей
100 сообщений
имеем 1 000 000/2*100= 50 000 000.

RY723 · 31.10.2010, 15:02

Сообщение от picavr

100 сообщений
имеем 1 000 000/2*100= 50 000 000.

Это не совсем точно - наряд два раза в одно место не попадает. Так что ресурс по записи будет больше.

asket76 · 31.10.2010, 15:44

Сообщение от RY723

Это не совсем точно - наряд два раза в одно место не попадает. Так что ресурс по записи будет больше.

В смысле два раза не попадет? Если сообщение имеет длину меньше чем размер блока во флеш-памяти, то фактически маркер будет писаться всегда в начале КАЖДОГО блока, вроде я так понял.