Comments 11
Есть небольшая терминологическая путаница с NVRAM:
кто-то понимает эту аббревиатуру буквально: Non-Volatile Random Access Memory, и реализует для него API как у памяти, т.е. "прочитай мне столько байт по вот этому адресу", "запиши мне вот эти байты по вот этому адресу" и т.п. Так, к примеру, работает контролер eMMC и хороших SD-карт (некоторые из которых давно уже научились делать все нужные танцы вокруг сырого флеша, чтобы его до дыр не затирала запись по одному и тому же виртуальному адресу).
другие понимают ее как "хранилище ключ-значение поверх энергонезависимой памяти", и тогда API получается примерно таким: "прочитай мне переменную с вот этим ключом", "запиши мне вот эти байты в переменную с вот этим ключом", и т.п. Так работает UEFI NVRAM, Apple NVRAM, и прочие подобные на ПК и мобильной технике.
Важны оба, эта статья описывает первый, и она хорошая (до отличной не хватает ссылки на исходный код под пермиссивной лицензией, чтобы читатель не переписывал уже существующее нормальное решение, а взял готовое).
Весьма странный интерфейс. По идее модулям которые используют этот драйвер не нужно знать о его внутренней структуре с его узлами и всем остальным, нужен просто адрес и данные, само собой с длиной, раз уж на си пишем.
Хорошо бы определиться с терминологией, что такое страница, сектор, блок:
Обычно в этих микрухах страница это 256 байт, как раз адресуемость по младшему байту адресного слова.
Сектор это уже минимальная область которая стирается, обычно 4 килобайта
Следовательно вопрос, что в вашем алгоритме называется страницей?
Кстати, сложность доступа к нужному элементу будет не O(Log2(n)), так как в дереве могут находиться лишние узлы и оно несбалансировано. В итоге в лучшем случае это O(Log2(n)) в худшем - О(n) или ещё хуже, скорее это будет где-то между ними.
интересно, что если записывать нули - то можно адреса уменьшать на степени двойки даже после записи (т.е. это будет не совсем однократная запись)
да, но зачем? Правило буравчика данной NVRAM это не менять каркас.
это позволяет не удлинять цепочку. В текущем варианте любая запись - это новый блок, а так можно немного ускорить чтение.
PS: или добавить дополнительные адреса для лево-право (т.е. чтобы был массив, не по 1 штуке) для тех мест, которые активно пишут.
Дело в том что после удаленного блока может быть куча валидных блоков.
заголовки блоков у вас же одинаковой длины?
значит их можно хранить в отдельном пространстве (отдельной странице), друг на друга они могут ссылаться по индексам (адрес = индекс*размер), а для данных иметь отдельный указатель.
PS: понятно что это размен скорости на память, вы сделали так как написали в статье - вы огромный молодец, а я всего лишь теоретик-советчик, не принимайте мой трындёж близко к сердцу :)
Я так понял CRC16 используется для решения изменились ли данные и не перезаписывать одно и то же? Но для CRC может быть слишком много коллизий когда разные наборы байт будут давать одно и то же число. Для этого придумали ХЕШ-функции, которые созданы для минимизации коллизий. Наиболее известная - MD5. Её бы для этого использовать...
Для CRC16 несложно подсчитать вероятность коллизии - 1/65535 тоесть примерно на 100К записей будет как минимум одно ложное срабатывание и какие-то данные будут потеряны(не записаны). А пользователь некоего устройства будет в задумчивости почему конкретная конфигурация настроек не сохраняется, и воспроизвести проблему на другом аналогичном устройстве не удасться, т.к. там будет уже другая такая "удачная" конфигурация, которая кроме прочего зависит от истории использования и очень трудно локализуется.
Спасибо за дополнение @Alexeyslav. Попробую исправить.
NVRAM Поверх off-chip SPI-NOR Flash