Buffer circular en Flash

Question

Necesito almacenar elementos de longitud variable en una cola circular en un chip flash. Cada artículo tendrá su encapsulamiento para que pueda descubrir qué tan grande es y dónde comienza el próximo artículo. Cuando hay suficientes elementos en el búfer, se ajustará al principio.

¿Cuál es una buena manera de almacenar una cola circular en un chip flash?

Hay una posibilidad de decenas de miles de artículos que me gustaría guardar. Por lo tanto, comenzar desde el principio y leer hasta el final del búfer no es ideal, ya que llevará tiempo buscar hasta el final.

Además, como es circular, necesito poder distinguir el primer elemento del último.

El último problema es que se almacena en flash, por lo que borrar cada bloque consume mucho tiempo y solo se puede hacer un número determinado de veces para cada bloque.

Answer 1

En primer lugar, la gestión de bloques:

Ponga una pequeña cabecera al comienzo de cada bloque. Lo principal que necesita para realizar un seguimiento de los "más antiguos" y "más nuevos" es un número de bloque, que simplemente incrementa el módulo k. k debe ser mayor que su número total de bloques. Idealmente, haga que k sea menor que su valor MAX (por ejemplo, 0xFFFF) para que pueda ver fácilmente qué es un bloque borrado.

En el arranque, el código lee las cabeceras de cada bloque a su vez, y localiza la primera y última bloques en la secuencia que es n _{i + 1} = (n _i + 1) módulo k. Tenga cuidado de no confundirse con los bloques borrados (el número de bloque es, por ejemplo, 0xFFFF) o los datos que de alguna manera están dañados (por ejemplo, borrado incompleto).

Dentro de cada bloque

Cada bloque comienza inicialmente vacío (cada byte es 0xFF). Cada registro se escribe simplemente uno después del otro. Si tiene registros de tamaño fijo, puede acceder a él con un índice simple. Si tiene registros de tamaño variable, entonces para leerlos debe escanear desde el inicio del bloque, estilo de lista vinculada.

Si desea tener registros de tamaño variable, pero evite el escaneo lineal, entonces podría tener un encabezado bien definido en cada registro. P.ej. use 0 como delimitador de registro y COBS -encode (o COBS/R -encode) cada registro. O use un byte de su elección como delimitador, y 'escape' ese byte si ocurre en cada registro (similar al PPP protocol).

En la puesta en marcha, una vez que conoce su último bloque, puede hacer un escaneo lineal para el último registro. O si tiene registros de tamaño fijo o delimitadores de registros, podría hacer una búsqueda binaria.

Borrar programación

Para algunos chips de memoria flash, borrando un bloque puede tomar mucho tiempo - por ejemplo. 5 segundos. Considere programar un borrado como una tarea en segundo plano un poco "adelantado". P.ej. cuando el bloque actual está x% lleno, entonces comience a borrar el siguiente bloque.

registro de numeración

es posible que desee los registros de número. La forma en que lo hice en el pasado es poner, en el encabezado de cada bloque, el número de registro del primer registro. Luego, el software debe mantener el recuento de los números de cada registro dentro del bloque.

suma de comprobación o CRC

Si desea detectar datos corruptos (por ejemplo incompleta escribe o borra debido a la falta de energía inesperada), a continuación, se puede añadir una suma de comprobación o CRC para cada registro, y quizás al bloque encabezamiento. Tenga en cuenta que el encabezado del bloque CRC solo cubriría el encabezado en sí, no los registros, ya que no podría volver a escribirse cuando se escribe cada nuevo registro.

Answer 2

Creo que lo entiendo ahora. Parece que su mayor problema será, habiendo llenado el espacio disponible para grabar, ¿qué pasará después? Los nuevos datos deberían sobrescribir los datos más antiguos, que es lo que usted entiende por un buffer circular. Pero dado que los datos no son de longitud fija, puede sobrescribir más de un registro.

Supongo que la cantidad de variabilidad en la longitud es lo suficientemente alta para que acolchar todo a una longitud fija no sea una opción.

Su segmento de escritura debe hacer un seguimiento de la dirección que representa el inicio del siguiente registro para escribir. Si conoce el tamaño de un bloque para escribir antes de tiempo, puede decir si va a terminar al final del búfer lógico y volver a comenzar en '0'. No dividiría un disco con algunos al final y otros al principio.

Un registro separado puede rastrear el comienzo; este es el dato más antiguo que aún no ha sido sobrescrito. Si fue a leer los datos, aquí es donde comenzaría.

El escritor de datos verificaría, dada la dirección de inicio de escritura y la longitud de los datos que está a punto de confirmar, si se topa con el registro de lectura, que examinaría el primer bloque y vería la longitud, y avanzaría al siguiente registro, hasta que haya espacio suficiente para escribir cualesquiera que sean los datos. Habrá una brecha de datos basura que se encuentra entre el final de los datos escritos y el inicio de los datos más antiguos, probablemente. Pero de esta manera, puede escribir una o dos direcciones como sobrecarga y no reorganizar bloques.

Al menos, eso es probablemente lo que haría. HTH

Answer 3

veo tres opciones:

option1: es rellenar todo lo que fuera al mismo tamaño, esto es simple, almacenar un puntero a la cabeza y la cola de la memoria intermedia para que sepa dónde escribir y dónde empiece a leer, use el tamaño de cada objeto para obtener un desplazamiento al siguiente, esto significa que debe atravesar el búfer como lo haría con una lista vinculada, también es lento si necesita el artículo 5000.

opción2: es almacene solo punteros a los datos reales en el búfer circular, de esa manera, cuando gira, no tiene que lidiar con el tamaño incorrecto. si almacena los datos reales en un búfer circular y no los rellena, podría encontrarse con situaciones en las que se sobreponen varios elementos con 1 nuevo objeto de datos, supongo que esto no está bien.

almacenar los datos reales en cualquier otro lugar en flash, la mayoría de flash tendrá algún tipo de nivelación de desgaste incorporado, si es así no tiene que preocuparse por sobrescribir la misma ubicación varias veces, el IC averiguará dónde almacenar realmente en un chip, solo escribe en el siguiente espacio libre disponible.

esto significa que debe elegir un tamaño máximo para el búfer circular, la forma de hacerlo depende de la variabilidad de los datos. Si el tamaño de los datos simplemente cambia mucho, digamos solo unos pocos bytes, entonces simplemente debe rellenarlo y usar la opción 1. Si el tamaño cambia salvajemente e impredeciblemente, elija el tamaño más grande que podría ser y descubra cuántos objetos de ese tamaño cabría en tu flash, úsala como el número máximo de entradas en el búfer. Esto significa que pierdes un montón de espacio.

opción 3: si el objeto realmente puede ser de cualquier tamaño, su punto en el que solo debe usar un sistema de archivos, nombre los archivos en orden y devuélvalo cuando esté lleno teniendo en cuenta si su nueva entrada es grande puede tener que eliminar múltiples entradas antiguas para que quepan. Esto es realmente solo una extensión de la opción 2 ya que la opción 2 es en muchos sentidos un sistema de archivos simple.

Answer 4

Mantenga un bloque separado que contiene un puntero al comienzo del primer registro y al final del último registro. También puede conservar más información, como el número total de registros, etc.

Hasta que se quede sin espacio, agregar registros es tan simple como escribirlos al final del búfer y actualizar el puntero de cola.

Como necesita recuperar espacio, elimine suficientes registros para que pueda ajustarse a su registro actual. Actualice el puntero de la cabeza mientras elimina los registros.

Deberá realizar un seguimiento de cuánto espacio adicional se ha liberado. Si mantiene un puntero al final del último registro, la próxima vez que necesite agregar un registro, puede compararlo con el puntero al primer registro para determinar si necesita eliminar más registros.

Además, si esto es NAND, usted o el controlador de flash necesitarán desbloquear y nivelar el desgaste, pero todo debe estar en una capa más baja que la asignación de espacio para el búfer circular.

Answer 5

La "circular" en un flash se puede hacer en función del tamaño del bloque, lo que significa que debe declarar la cantidad de bloques del flash que asigna para este búfer.

El tamaño real del búfer será en cada momento particular entre n-1 (n es el número de bloques) y n.

Cada bloque debe comenzar con un encabezado que contenga el número secuencial o la marca de tiempo que podría usarse para determinar qué bloque es más antiguo que el otro.

Cada artículo encapsulado con un encabezado y un pie de página. el encabezado predeterminado contiene lo que quieras, pero según este encabezado debes saber el tamaño del artículo. El pie de página predeterminado es 0xFFFFFFFF. Este valor indica una terminación nula.

En su RAM debe guardar un puntero al bloque más antiguo y el último bloque y puntero al elemento más antiguo y último. Al encender, revisa todos los bloques, encuentra los bloques relevantes y carga estos miembros.

Cuando desee almacenar un nuevo artículo, verifique si el último bloque contiene espacio suficiente para este artículo. Si lo hace, guarda el artículo al final del artículo anterior y cambia el pie de página anterior para que apunte a este elemento. Si no contiene suficiente espacio, debe borrar el bloque más antiguo. Antes de borrar este bloque, cambie los miembros del bloque más antiguos (RAM) para que apunten al siguiente bloque y el elemento más antiguo para que apunte al primer elemento de este bloque. Luego puede guardar el nuevo elemento en este bloque y cambiar el pie de página del último elemento para señalar este elemento.

Sé que la explicación puede sonar complicada, pero el proceso es muy simple y si lo escribe correctamente puede hacer que incluso la alimentación eléctrica falle (siempre tenga en cuenta el orden de las escrituras).

atención

de pago que la circularidad de la memoria intermedia no se guarda en el flash, pero el flash sólo contiene unos bloques con elementos que se pueden decidir de acuerdo a los bloques encabezados y artículos cabeceras de lo que es el orden de estos elementos