Algoritmo de registro circular ligero (tipo sistema de archivos) para el almacenamiento basado en flash

Question

Actualmente estoy trabajando en un proyecto que implica el registro rápido y continuo de una métrica bastante específica de la aplicación durante un largo periodo de tiempo. Para ello he acabado utilizando un NXP M0 y un chip flash SPI de 32MiB. El registro es continuo y tiene que durar muchos años en el campo (más de 10), y es revisado periódicamente por un humano para detectar tendencias. Eventualmente el buffer se llena y empieza a sobrescribir datos antiguos, lo cual está perfectamente bien. Se me ocurrió un algoritmo sencillo para recorrer todo el dispositivo flash y encontrar el cabezal actual después de un encendido (el dispositivo se apaga con bastante frecuencia fuera de mi control) para que el registro pueda continuar donde lo dejó. Puedo hacer fuerza bruta a través de este paseo y hacerlo con ~4s como el peor de los casos.

Esto me hizo pensar, ¿hay algún sistema de archivos estructurados de registro que se adapte a los dispositivos flash y a los microcontroladores? JFFS y todos los demás conocidos Logs estructurados Imagino que sería un poco pesado para un simple microcontrolador (depende de la aplicación, claro). Para ser más específico, me gustaría saber de algún algoritmo que esté diseñado para ser específicamente un registro circular con un tiempo de búsqueda de cabeza rápido y/o alguno que esté diseñado para un sistema de archivos "tradicional" en un dispositivo flash que pueda ser ejecutado en un microcontrolador. Tradicional en este sentido es algo como JFFS donde hay una estructura de datos que representa una colección de archivos mutables de acceso aleatorio en un espacio de nombres jerárquico.

Answer 1

estructura de datos de la cuerda

Me fascina la estructura de datos de la cuerda . Tengo un proyecto de hobby en el que intento adaptarlo a un microcontrolador con sólo unos pocos bytes de RAM enganchado a una enorme memoria Flash, para poder insertar y borrar y editar arbitrariamente texto de longitud variable en enormes archivos de texto. Archivos de texto demasiado grandes para que quepan en la RAM. Borrar la última mitad del archivo y reescribirlo en flash, desplazado un byte, cada vez que inserto o borro un carácter en medio de un archivo de texto de varios megabytes, sería demasiado lento, pero la estructura de datos de la cuerda puede hacer esto mucho más rápido. Dado que la estructura de datos de la cuerda puede representar tales archivos de longitud variable de acceso aleatorio mutable como piezas de longitud fija inmutable, parece ser un buen partido para la memoria flash - todas las ediciones se escriben en una forma de registro circular. Por desgracia, aún no se han resuelto todos los errores en mi código. :-(

registros cronológicos de longitud fija

Conseguí que funcionara un sistema de registro circular similar, para un producto que ayudé a desarrollar.

Simplemente escribí registros de longitud fija uno tras otro, llenando el flash como una matriz circular.

(Con una memoria flash completamente vacía, empecé a escribir registros unos 3 bloques antes del final de la matriz, para poder probar la envoltura circular después de almacenar sólo unos pocos registros de datos, en lugar de empezar en el registro cero y esperar a que se escribieran los datos de un mes antes de descubrir que había un error en mi código de envoltura).

Me aseguré de que siempre hubiera al menos 2 "bloques borrados" listos para ser escritos. Después de escribir un registro, si sólo había 2 "bloques borrados" tras él que estuvieran vacíos, borraba incondicionalmente el bloque de datos más antiguo, el tercer bloque de datos más antiguo tras los 2 "bloques borrados". (Cerca del final de la memoria flash, "después" significa "envolver al principio de la memoria flash). (Tal vez un solo bloque borrado hubiera sido adecuado -- no recuerdo por qué pensé que necesitaba al menos 2 y a veces 3).

Olvidé exactamente cuántos registros puse en cada "bloque de borrado", pero me aseguré de no tener nunca un registro a caballo entre dos bloques de borrado: los dos primeros bytes de cada bloque de borrado de la flash eran el valor "borrado" 0xFFFF, o los dos primeros bytes de una suma de comprobación Fletcher-16 (que nunca es 0xFFFF) en la cabecera de cada registro.

Eso hizo que fuera rápido escanear la siguiente vez que se encendiera y encontrar la cabeza del registro circular -- sólo tuve que mirar los dos primeros bytes de cada bloque de borrado para distinguir entre bloques "borrados" y "de datos". (Me preocupaba un poco que un "fallo de alimentación en mitad del borrado de un bloque" provocara el borrado de los dos primeros bytes a 0xFFFF pero dejara los bytes no borrados en mitad del bloque, así que escribí código para que el microcontrolador comprobara esto y reiniciara el proceso de "borrado de un bloque").

Por favor, díganme si encuentran otras estructuras de datos o sistemas de archivos aptos para flash.

Answer 2

Han pasado bastantes años, pero quería hacer un seguimiento de esto por si alguien se pasaba por aquí. Parece que hay algunos proyectos en estos días, que se mantienen activamente (a partir de enero de 2020) que son sistemas de archivos destinados a los microcontroladores dirigidos a la flash NOR SPI.

Tenga en cuenta que no he probado estos en cualquier capacidad, pero hacen exactamente lo que la pregunta original estaba buscando: "...estructura de datos que representa una colección de archivos mutables de acceso aleatorio..."

https://github.com/ARMmbed/littlefs - Creado por ARM, con licencia BSD

https://github.com/joembedded/JesFs - Realmente no parece tener licencia, pero fue diseñado muy específicamente para la flash SPI NOR.