Во встраиваемых устройствах существуют два основных вида долговременной памяти: EEPROM (Electrically Erasable Programmable Read-only Memory) и flash (NAND/NOR).

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

Для программиста взаимодействовать со flash памятью неудобно. Появляется необходимость в создании библиотеки, которая будет осуществлять:

• поиск данных по ключу за минимально возможное время
• поддержку целостности данных при сбоях во время записи
• использование минимума оперативной памяти для хранения вспомогательных структур
• циркуляцию использования страниц (wear-leveling)
• абстрагирование от конкретной задачи, ОС и устройства

Для осуществления первого требования необходимо решить как ссылаться на данные. Два простых способа:
ссылка по имени, ссылка по названию. Первый вариант, по типу файловых систем, приведет к излишним накладным расходам, необходимо будет ограничивать длину названия (как это делается в FAT), и скорее всего будет для многих встраиваемых систем ограничением на пути к использованию. Поэтому я выбрала решение на основе ссылки по идентификатору. В случае 16-битного значения, существует 65536 различных идентификаторов. Для многих задач такого количества достаточно, учитывая значительные ограничения по ресурсам во встраиваемых системах.

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

Для удовлетворения условия целостности, после данных следует 16 битная контрольная сумма, вычисляемая по алгоритму longitudinal parity check от идентификатора, длины и данных.

Приходим к следующему формату хранения данных:

 
|  ID (16 бит) | LENGTH (16 бит) | DATA (LENGTH байт) | CHECKSUM (16 бит)  | 

Равномерное использование flash страниц (wear leveling) является ключевым алгоритмом для многих производителей устройств хранения на основе flash памяти. Алгоритмы известны в общих чертах, хотя готовых реализаций я не нашла. Я выбрала самый простой вариант: использование алгоритма round robin. Помимо страничного закольцовывания, нужно хранить и поддерживать дополнительную информацию. Ввиду этого каждая страница имеет заголовок, состоящий, как минимум, из статуса страницы. Для целей реализации хватило трех типов статусов: VALID, EMPTY, RECEIVING.

Страницы типа VALID являются страницами, на которых располагаются данные и/или на которые можно записать
необходимую информацию в соответствии с вышеприведенным форматом данных. Для VALID страниц после статуса хранится их порядковый номер. Страницы типа EMPTY не содержат данных и могут быть аллоцированы. Страницы типа RECEIVING — страницы, которые находятся в состоянии перехода из статуса EMPTY в VALID.

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

Во время инициализации VIrtEEPROM производится присваивание переменным необходимых значений, а также восстановление системы после сбоя, проверка валидности хранимых значений. Все RECEIVING страницы стираются и переводятся в статус ERASE. Заполняется массив, задающий правильный логический порядок страниц, а также массив валидных и занятых страниц.

На страницах типа VALID могут быть обнаружены несколько валидных элементов, имеющих одни и те же идентификаторы. В этом случае рассматривается самое последнее вхождение как наиболее новое.

Выше были перечислены требования и основные нюансы реализации. Далее обсудим API взаимодействия с VirtEEPROM.

В самом начале необходимо создать в единственном экземпляре текущий статус виртуального EEPROM'a, что осуществляется вызовом функции veeprom_create_status(), которое возвращает указатель на структуру типа veeprom_status.

Далее нужно сообщить адрес начала отображаемой flash памяти c помощью функции
veeprom_vstatus_init(veeprom_status *vstatus, uint16_t *addr), где vstatus — ранее созданный указатель на структуру veeprom_status, addrs — указатель, на область памяти начала flash памяти.

После этого необходимо вызывать veeprom_init(veeprom_status *s), которая возвращает 0 (OK), в случае, если не произошло ошибок в процессе инициализации.

Для поиска поиска данных по идентификатору используется функция veeprom_read(uint16_t id, veeprom_status *vstatus), которой в качестве параметров необходимо передать проинициализированный указатель на структуру vtstatus. Функция возвращает либо NULL в случае, если данные не найдены, либо указатель на структуру vdata*, которая в поле p содержит указатель, где записаны данные в вышеописанным формате.

Для записи необходимо указать идентификатор через параметр id, передать указатель на данные через data, передать размер данных в параметре length, так же передать указатель на veeprom_status в функцию veeprom_write(uint16_t id, uint8_t *data, int length, veeprom_status *vstatus). В случае успешной записи, функция возвращает 0. Если данные с переданным идентификатором уже были записаны, то значение обновится новой информацией.

Для удаления используется функция veeprom_delete(uint16_t id, veeprom_status *vstatus), которой передаётся удаляемый идентификатор и указатель на veeprom_status. В случае успеха функция возвращает 0.

Код виртуального EEPROM (VirtEEPROM) находится на стадии концепта. Уже сейчас есть готовая и рабочая реализация, основанная на флеш эмуляторе. Для более детального рассмотрения исходников можно их скачать и запустить:

$ git clone https://github.com/ninaevseenko/virteeprom.git
$ cd virteeprom/verification/ 
$ make 
$ ./examine 

Помимо этого, у кого есть STM32F3-Discovery, то можно прошить и посмотреть код VirtEEPROM в действии. Все необходимое находится в virteeprom/verification/stm32f3discovery/. После запуска на UART1 печатаются различные отладочные сообщения, и в котором запускается shell со следующим набором команд:

• initflash — инициализирует необходимые структуры для работы с virteeprom
• wipeflash — стирает все, кроме кода и данных программы
• writeflash — записывает 100 однобайтовых значений
• readflash — считывает 100 однобайтовых значений

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



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