Настал первый случай за 12 лет, когда в программировании микроконтроллеров понадобились бинарные деревья поиска.

В этом тексте поговорим о том как можно построить эффективную программную реализацию энергонезависимой Key-Value Map(ки) над дешевой SPI NOR Flash для микроконтроллерных проектов. Суть проста. Нужна NVRAM.

Требуется абстрактная структура данных. Ключ-значение. В качестве ключа 32-битное целое число. В качестве данных - бинарный массив произвольной длинны.

У меня уже был текст про простую, компактную, наивную, медленную O(n) on-chip NOR Flash NVRAM https://habr.com/ru/articles/706972/, которая в общем-то отлично работает, когда в распоряжение 16kByte...128kByte. Теперь же потребовалось создать полноценную быструю O(Log2(n)) NVRAM для off-chip NOR Flash(ей) c размерами 4....16 MByte.

Требования к отличной NVRAM

1. Принцип работы NVRAM. Даешь виртуальный 32bit адрес, данные, размер данных, записываешь данные. Отключаешь питание. Включаешь питание. Даешь виртуальный адрес, получаешь данные и их размер.

2. Должны остаться предыдущие данные с ключом ADDR, если питание пропадет в момент записывания очередного блока.

3. Можно хранить данные разного размера. Например 512 байт и более в одной записи.

4. Данные должны сохраняться при пропадании питания.

5. Узел должен быстро вставляться

6. Узел должен быстро находиться

7. Узел должен быстро удаляться

8. Не должно быть пустых мест в памяти. Записи следуют одна за другой, впритык. Без какого бы то ни было выравнивания.

9. Данные должны быть оснащены CRC16. Это позволит выявить такие события как пропадание питания в момент записи узла, да и просто отличить кадр от случайных чиселок.

10. Данные должны храниться в зашифрованном виде. Это позволит защитить данные, если кто-то решит обклеить микросхему оранжевой каптоновой лентой и сдуть термо феном микросхему SPI-NOR Flash(а) для последующего считывания dump(а) другим микроконтроллером и разбора типов данных внутри.

11. Данные могут сжиматься. То есть подвергаться компрессии. Это позволит загрузить в NOR-Flash больше байт payload(а).

Особенности работы с SPI NOR flash

В качестве физического число хранилища будет выступать обыкновенные дешевые микросхемы SPI NOR Flash. Например MX25R6435F

В NOR Flash когда прописывается NOR Flash, то биты меняются по следующему закону.

То есть записью считается обнуление бита. Отдельный обнуленный бит взвести обратно в единицу нельзя. Надо стирать всю страницу. А это порядка 4kByte.

На самом деле задача разработки NVRAM сложнее чем кажется. Потребуются десятки итераций отладки и диагностики. Тут надо эффективные методы отладки софтвера.

Для отладки чисто программной составляющей надо сначала накропать имитатор SPI-Nor Flash на PC. В качестве SPI-Flash просто определить массив RAM памяти процесса. Всю логику работы надо отладить на NetTop(е) а потом с уверенностью собрать этот код на Tagret платформе. Плюс эта DeskTop утилита пригодится вам если вы захотите скомпилировать образ готовой файловой системы в виде hex массива, а затем прошить её во flash вместе с прошивкой.

Также подобного рода задачи как разработка NVRAM отлично покрываются модульными тестами. Тут идеально ложится методология TDD. Поэтому сразу подготовим как можно больше тестов. Эти же тесты будут выполнять роль документации и скреп при рефакторинге и помогут понять, когда настало время остановиться в разработке кода NVRAM.

Основная идея реализации NVRAM на SPI NOR Flash

Для начала определимся с терминологией.

Какой API мы хотим получить? Наверное что-то простое как это:

#ifndef NVRAM_DRIVER_H
#define NVRAM_DRIVER_H

#include <stdbool.h>
#include <stdint.h>

#include "sw_nvram_types.h"

bool nvram_write(NvRamItem_t* Node, uint32_t address,const uint8_t* const data, uint32_t size);
bool nvram_read(NvRamItem_t* Node, uint32_t address, uint8_t * const data, uint32_t* const size);
bool nvram_delete(NvRamItem_t* Node, uint32_t address);

bool nvram_init(NvRamItem_t* Node);

#endif /*NVRAM_DRIVER_H*/

Теперь определимся со структурой кадра, которую мы будем хранить в энергонезависимой памяти.

Под увеличением эту таблицу можно посмотреть тут.

В заголовке всё только самое нужное: преамбула (параметризуемая), адрес, данные, контрольная сумма, тип данных, временная отметка, состояние переменной, указатели на листья. Всего 36 байт на заголовок.

Хорошо. С заголовком плюс/минус определились. Но как хранить сами фреймы то?

Новые узлы всегда записываются в конец страницы NOR Flash памяти. Впритирку, впритык к последнему прописанному кадру. Никакого выравнивая чтобы не потерять впустую драгоценнейшие байты.

Теперь важный момент. Основная идея NVRAM заключается в том, чтобы использовать для связи узлов бинарное дерево поиска (BST). Бинарное дерево поиска, помимо всего прочего, в данном случае хорошо и тем, что указатели на правый и левый узлы в каждом узле прописываются только один раз. Это отлично ложиться на физические ограничения SPI-NOR Flash(а). В качестве ключа будет выступать всё тот же 32битный адрес данных. Мы же делаем NVRAM. А RAM работает по принципу: "даешь адрес, получаешь данные".

Вставка данных в NVRAM

Перед вставной надо проверить, есть ли уже такие данные в NOR Flash(е). В этом деле нам поможет контрольная сумма CRC16 в каждом Frame(е). Нет смысла вставлять то же самое. Это противоречит требованию заботы об износе памяти. Называется такая технология lazy write (ленивая запись).

Это нужно для равномерного износа микросхем NOR Flash. Вставка данных в NVRAM сводится к вставке в бинарное дерево. Перед вставкой надо проверить что в дереве есть уже такой адрес. Он может быть с данными другого размера и другой контрольной суммой. Если да, то его надо отметить как устаревший. После чего только и вставить в дерево новый лист и отметить вставленный frame как новый. На рисунке это зелёный цвет.

Вот пример организации узлов

вот пример вставки пары кадров UART-CLI командой nvrw

Поиск узла в NVRAM

Поиск узла сводится к поиску внутри бинарного дерева поиска. В качестве ключа выступает 32-битный адрес переменной в NVRAM. Время поиска ограничено максимальной высотой бинарного дерева. Также можно запросто обойти все узлы по возрастанию или по убыванию. В дереве происходит быстрый поиск. В лучшем случае O(Log2(N)), когда дерево сбалансировано в худшем O(N) когда дерево вырождается в связанный список.

Удаление узла из NVRAM

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

NVRAM на основе бинарного дерева поиска (BST) хороша тем, что хранит не только данные, но и историю работы с данными. Когда создавали, что удаляли. Всё это останется в краткосрочной перспективе до момента переполнения и переключения страниц.

Кто же стирает NOR Flash?

Вся память которая есть в распоряжении драйвера NVRAM будет поделена на 2 равные NVRAM страницы: aктивная и пассивная. Активная страница это та в которую и будут записываться переменные. Пассивная страница это то временное хранилище которое понадобится при перестроении дерева, чтобы очистить устаревшие и удаленные заголовки.

Как драйвер NVRAM узнает какая страница активна?

В самом начале страниц NVRAM будет одно двойное слово (qword).

При подаче питания драйвер NVRAM в функции nvram_init() проверит эти числа и поймет с какой страницей предстоит работать сегодня. С первой или со второй. Вот LookUp таблица принятия решения в функции nvram_init()

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

При этом при пере копировании страницы NVRAM надо обходить бинарное дерево в порядке level order. Таким образом в противоположной странице сформируется дерево той же высоты по отношению к активным узлам как и в изначальной странице. Это очень важно. Так как если при перебросе кадров обходить изначальное дерево в порядке in order, то в новой странице сформируется не дерево, а длиннющий связанный список и это замедлит время всех операций.

В идеале надо вообще придумать алгоритм потокового формирования сбалансированного дерева в новой странице при переключении страниц, при условии что нельзя переписывать указатели листьев, но это тема очень трудная, потянет на магистерское исследование какого-нибудь европейского ВУЗ(овца).

Получается, что операция стирания страницы это достаточно редкая операция, которая происходит только при заполнении половины всего NOR-Flash. Этим и достигается защита памяти от износа.

При этом количество переключений страниц можно также хранить тут же в NVRAM в переменной с определенным зарезервированным виртуальным адресом и предсказывать тот чудный день, когда NOR Flash откажет. Например, если наступит 80k переключений, то можно выдать предупреждение в UART консоль.

Программные зависимости

NVRAM не может работать в вакууме. NVRAM это надстройка над драйвером какого-либо NOR-Flash(а). Будь-то on или off chip. Также нужен компонент расчета контрольных сумм, функции которые возвращают время (UTC или Up-Time), и классический код для обслуживания бинарного дерева поиска.

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

Вывод

Вот так, исключительно благодаря софтверу, из практически одноразовой дешевой памяти ценой 20 RUR/MByte получили многоразовую дорогую память ценой 2000 RUR/MByte (в 100 раз дороже)! Волшебство!

Теперь, когда есть NVRAM можно спокойно запустить на SPI-Flash FatFs и создавать привычные всем текстовые и бинарные файлики прямо внутри микросхемы.

Для работы с NVRAM надо ориентироваться в следующих акронимах

Links

Сайт для визуализации построения абстрактных структур данных
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

Простая NVRAM для on-chip NOR Flash https://habr.com/ru/articles/706972/

Сайт отрисовки графов https://dreampuf.github.io/GraphvizOnline

Структура узла для NVRAM https://docs.google.com/spreadsheets/d/1UmJThfkCRQpiLWmO9J47Z5gdim99YF0lR8Lr8KIgXAY/edit#gid=0

https://habr.com/ru/articles/730232/

https://habr.com/ru/articles/479044/

https://habr.com/ru/articles/584156/

https://habr.com/ru/articles/731604/

https://www.youtube.com/watch?v=0U6eT9vTitc

Контрольные вопросы:

1. Какие бывают обходы бинарных деревьев?

2. Какова алгоритмическая сложность поиска узла в бинарном дереве поиска?

3. Какова алгоритмическая сложность вставки узла в бинарное дереве поиска?

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

5. На страница "A" произвольное бинарное дерево поиска. Как нарисовать эквивалентное сбалансированное бинарное дерево поиска на странице "B"? Ограничения: Дерево на странице B надо нарисовать с первой попытки, за одни раз. Дерево на странице "A" нельзя менять. RAM памяти в 300 раз меньше, чем размер дерева на странице "A".