{"id":53751,"date":"2019-12-09T00:00:00","date_gmt":"2019-12-08T21:00:00","guid":{"rendered":"https:\/\/prohoster.info\/blog\/blog_prohoster\/moya-realizatsiya-koltsevogo-bufera-v-nor-flash"},"modified":"2020-02-18T14:01:41","modified_gmt":"2020-02-18T11:01:41","slug":"moya-realizatsiya-koltsevogo-bufera-v-nor-flash","status":"publish","type":"post","link":"https:\/\/prohoster.info\/es\/blog\/administrirovanie\/moya-realizatsiya-koltsevogo-bufera-v-nor-flash","title":{"rendered":"Mi implementaci\u00f3n de un b\u00fafer circular en memoria NOR flash","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"<h1 id=\"predystoriya\">Antecedentes<\/h1>\n<p><\/p>\n<p>Existen m\u00e1quinas expendedoras de desarrollo propio. En su interior hay una Raspberry Pi y un poco de cableado en una placa separada. Est\u00e1n conectados un aceptador de monedas, un aceptador de billetes, un terminal bancario\u2026 Todo es controlado por un programa hecho a medida. Toda la historia de trabajo se registra en un archivo en una memoria USB (MicroSD), que luego se transmite a trav\u00e9s de Internet (con un m\u00f3dem USB) a un servidor, donde se almacena en una base de datos. La informaci\u00f3n sobre las ventas se carga en 1C, tambi\u00e9n hay una interfaz web sencilla para monitoreo, etc. <\/p>\n<p><\/p>\n<p>Es decir, el registro es vital \u2014 para la contabilidad (ah\u00ed est\u00e1n los ingresos, las ventas, etc.), el monitoreo (cualquier fallo y otros imprevistos); esto es, se puede decir, toda la informaci\u00f3n que tenemos sobre esta m\u00e1quina. <\/p>\n<p><\/p>\n<h1 id=\"problema\">Problema<\/h1>\n<p><\/p>\n<p>Las memorias USB se muestran como dispositivos muy poco fiables. Fallan con una frecuencia notable. Esto conduce a paradas en las m\u00e1quinas y, si por alguna raz\u00f3n el registro no pudo ser transmitido en l\u00ednea, a p\u00e9rdidas de datos.<\/p>\n<p><\/p>\n<p><em>Esta no es la primera experiencia con memorias USB; antes hubo otro proyecto con m\u00e1s de un centenar de dispositivos, donde el registro se almacenaba en memorias USB, y ah\u00ed tambi\u00e9n hubo problemas de fiabilidad, a veces el n\u00famero de fallos al mes se contaba por decenas. Se probaron diferentes memorias, incluidas algunas de marcas conocidas con memoria SLC: algunas modelos son m\u00e1s fiables que otros, pero la sustituci\u00f3n de las memorias no resolvi\u00f3 el problema de manera dr\u00e1stica.<\/em><\/p>\n<p><noindex><a rel=\"nofollow\" name=\"habracut\"><\/a><\/noindex> <\/p>\n<p><strong>\u00a1Atenci\u00f3n!<\/strong> \u00a1Informe detallado! Si no te interesa el 'por qu\u00e9', sino solo el 'c\u00f3mo', puedes ir directamente. <noindex><a rel=\"nofollow\" href=\"#format\">al final<\/a><\/noindex> art\u00edculo.<\/p>\n<p><\/p>\n<h1 id=\"reshenie\">Soluci\u00f3n<\/h1>\n<p><\/p>\n<p>Lo primero que se me ocurre: renunciar a MicroSD, poner, por ejemplo, un SSD y arrancar desde \u00e9l. Te\u00f3ricamente es posible, probablemente, pero relativamente caro y no tan fiable (se a\u00f1ade un adaptador USB-SATA; la estad\u00edstica de fallos de los SSD econ\u00f3micos tampoco es muy alentadora).<\/p>\n<p><\/p>\n<p>Un disco duro USB tampoco parece ser una soluci\u00f3n muy atractiva.<\/p>\n<p><\/p>\n<p>As\u00ed que llegamos a la siguiente opci\u00f3n: mantener el arranque desde MicroSD, pero utilizarlas en modo de solo lectura, y almacenar el registro de trabajo (y otra informaci\u00f3n exclusiva para cada dispositivo, como el n\u00famero de serie, las calibraciones de los sensores, etc.) en otro lugar. <\/p>\n<p><\/p>\n<p>El tema del sistema de archivos en modo solo lectura para Raspberry Pi ya ha sido explorado a fondo, no me detendr\u00e9 en los detalles de implementaci\u00f3n en este art\u00edculo. <em>(pero si hay inter\u00e9s, quiz\u00e1s escriba un mini-art\u00edculo sobre este tema)<\/em>. Hay un punto que merece ser mencionado: tanto por experiencia personal como por los testimonios de quienes ya han implementado la mejora en fiabilidad, es evidente. S\u00ed, es imposible eliminar por completo las aver\u00edas, pero reducir su frecuencia es absolutamente viable. Adem\u00e1s, las tarjetas se estandarizan, lo que simplifica notablemente el reemplazo para el personal de mantenimiento.<\/p>\n<p><\/p>\n<h2 id=\"apparatnaya-chast\">Parte de hardware<\/h2>\n<p><\/p>\n<p>No hubo dudas especiales sobre la elecci\u00f3n del tipo de memoria: NOR Flash.<br \/>\nArgumentos: <\/p>\n<p><\/p>\n<ul>\n<li>conexi\u00f3n simple (generalmente un bus SPI, del cual ya tenemos experiencia, por lo que no se anticipan problemas 'de hardware');<\/li>\n<li>precio rid\u00edculo;<\/li>\n<li>protocolo de operaci\u00f3n est\u00e1ndar (la implementaci\u00f3n ya est\u00e1 en el n\u00facleo de Linux, si se desea, se puede usar uno externo que tambi\u00e9n est\u00e1 disponible, o incluso escribir el propio, ya que todo es simple);<\/li>\n<li>fiabilidad y recurso:<br \/>\ndel t\u00edpico datasheet: los datos se almacenan durante 20 a\u00f1os, 100,000 ciclos de borrado por cada bloque;<br \/>\nde fuentes externas: una tasa de error extremadamente baja, se postula que no hay necesidad de c\u00f3digos de correcci\u00f3n de errores <em>(en algunos trabajos se considera ECC para NOR, pero generalmente se refieren a MLC NOR, eso tambi\u00e9n ocurre)<\/em>.<\/li>\n<\/ul>\n<p><\/p>\n<p>Vamos a estimar los requerimientos de volumen y recurso.<\/p>\n<p><\/p>\n<p>Quiero garantizar que los datos se mantengan durante varios d\u00edas. Esto es necesario para que, en caso de alg\u00fan problema con la conexi\u00f3n, no se pierda el historial de ventas. Vamos a orientarnos a 5 d\u00edas, en este per\u00edodo <em>(incluso considerando fines de semana y festivos)<\/em> se puede resolver el problema.<\/p>\n<p><\/p>\n<p>Actualmente acumulamos alrededor de 100kb de registros en un d\u00eda (3-4 mil entradas), sin embargo, esta cifra va en aumento: se incrementa la detallizaci\u00f3n, se a\u00f1aden nuevos eventos. Adem\u00e1s, a veces hay picos (alg\u00fan sensor comienza a enviar alertas falsas, por ejemplo). Calcularemos sobre 10,000 entradas de 100 bytes \u2014 un megabyte al d\u00eda.<\/p>\n<p><\/p>\n<p>En total, se obtienen 5Mb de datos limpios (bien comprimibles). A ellos se suman <em>(estimaci\u00f3n grosera)<\/em> 1Mb de datos de servicio.<\/p>\n<p><\/p>\n<p>Es decir, necesitamos un chip de 8Mb si no utilizamos compresi\u00f3n, o de 4Mb si la usamos. Cifras totalmente realistas para este tipo de memoria.<\/p>\n<p><\/p>\n<p>En cuanto al recurso: si planeamos que la memoria se sobrescriba completamente no m\u00e1s de una vez cada 5 d\u00edas, durante 10 a\u00f1os de vida \u00fatil obtendremos menos de mil ciclos de regrabaci\u00f3n.<br \/>\nRecuerden, el fabricante promete cien mil.<\/p>\n<p>\n<b class=\"spoiler_title\">Un poco sobre NOR vs NAND<\/b><\/p>\n<p>Hoy en d\u00eda, por supuesto, la memoria NAND es mucho m\u00e1s popular, pero para este proyecto no la utilizar\u00eda: NAND, a diferencia de NOR, siempre requiere el uso de c\u00f3digos de correcci\u00f3n de errores, tablas de bloques defectuosos, etc., y adem\u00e1s, las patas de los chips NAND suelen ser bastante m\u00e1s numerosas.<\/p>\n<p><\/p>\n<p>Como desventajas de NOR se pueden mencionar:<\/p>\n<p><\/p>\n<ul>\n<li>bajo volumen (y, por ende, alto precio por megabyte);<\/li>\n<li>baja velocidad de intercambio (en gran parte debido a que se utiliza una interfaz secuencial, generalmente SPI o I2C);<\/li>\n<li>borrado lento (dependiendo del tama\u00f1o del bloque, puede tomar desde fracciones de segundo hasta varios segundos).<\/li>\n<\/ul>\n<p><\/p>\n<p>Parece que no hay nada cr\u00edtico para nosotros, as\u00ed que continuemos.<\/p>\n<p><\/p>\n<p>Si te interesan los detalles, se eligi\u00f3 el chip <noindex><a rel=\"nofollow\" href=\"https:\/\/www.adestotech.com\/wp-content\/uploads\/doc3686.pdf\">at25df321a<\/a><\/noindex> <em>(aunque esto es irrelevante, hay un mont\u00f3n de an\u00e1logos en el mercado que son compatibles en cuanto a la disposici\u00f3n de pines y el sistema de comandos; incluso si quisi\u00e9ramos instalar un chip de otro fabricante y\/o de otro volumen, funcionar\u00e1 sin necesidad de modificar el c\u00f3digo)<\/em>.<\/p>\n<p><\/p>\n<p>Estoy utilizando el controlador incorporado en el n\u00facleo de Linux, en Raspberry gracias al soporte de overlay de device tree es muy sencillo: solo hay que colocar el overlay compilado en \/boot\/overlays y modificar un poco \/boot\/config.txt.<\/p>\n<p>\n<b class=\"spoiler_title\">Ejemplo de archivo dts<\/b><\/p>\n<p>Honestamente, no estoy seguro de que est\u00e9 escrito sin errores, pero funciona.<\/p>\n<p><\/p>\n<pre><code class=\"plaintext\">\/*\n * Device tree overlay for at25 at spi0.1\n *\/\n\n\/dts-v1\/;\n\/plugin\/;\n\n\/ {\n    compatible = \"brcm,bcm2835\", \"brcm,bcm2836\", \"brcm,bcm2708\", \"brcm,bcm2709\"; \n\n    \/* disable spi-dev for spi0.1 *\/\n    fragment@0 {\n        target = &lt;&amp;spi0&gt;;\n        __overlay__ {\n            status = \"okay\";\n            spidev@1{\n                status = \"disabled\";\n            };\n        };\n    };\n\n    \/* the spi config of the at25 *\/\n    fragment@1 {\n        target = &lt;&amp;spi0&gt;;\n        __overlay__ {\n            #address-cells = &lt;1&gt;;\n            #size-cells = &lt;0&gt;;\n            flash: m25p80@1 {\n                    compatible = \"atmel,at25df321a\";\n                    reg = &lt;1&gt;;\n                    spi-max-frequency = &lt;50000000&gt;;\n\n                    \/* default to false:\n                    m25p,fast-read ;\n                    *\/\n            };\n        };\n    };\n\n    __overrides__ {\n        spimaxfrequency = &lt;&amp;flash&gt;,\"spi-max-frequency:0\";\n        fastread = &lt;&amp;flash&gt;,\"m25p,fast-read?\";\n    };\n};<\/code><\/pre>\n<p>\n<b class=\"spoiler_title\">Y otra l\u00ednea en config.txt<\/b><\/p>\n<pre><code class=\"plaintext\">dtoverlay=at25:spimaxfrequency=50000000<\/code><\/pre>\n<p><\/p>\n<p>Omitir\u00e9 la descripci\u00f3n de c\u00f3mo conectar el chip a Raspberry Pi. Por un lado, no soy un especialista en electr\u00f3nica, y por otro, aqu\u00ed todo es bastante sencillo incluso para m\u00ed: el chip tiene solo 8 pines, de los cuales necesitamos tierra, alimentaci\u00f3n, SPI (CS, SI, SO, SCK); los niveles coinciden con los de Raspberry Pi, no se necesita ninguna conexi\u00f3n adicional: simplemente conectamos los 6 pines mencionados.<\/p>\n<p><\/p>\n<h2 id=\"postanovka-zadachi\">Planteamiento del problema<\/h2>\n<p><\/p>\n<p>Como suele ser, el planteamiento del problema pasa por varias iteraciones, creo que ya es hora de una nueva. As\u00ed que deteng\u00e1monos, reunamos todo lo que ya se ha escrito y aclaremos los detalles que quedan en la sombra.<\/p>\n<p><\/p>\n<p>As\u00ed que hemos decidido que el registro se almacenar\u00e1 en SPI NOR Flash.<\/p>\n<p>\n<b class=\"spoiler_title\">Qu\u00e9 es NOR Flash para quienes no lo saben<\/b><\/p>\n<p>Es una memoria no vol\u00e1til que permite realizar tres operaciones:<\/p>\n<p><\/p>\n<ol>\n<li>Lectura:<br \/>\nLa lectura m\u00e1s com\u00fan: enviamos la direcci\u00f3n y leemos tantos bytes como necesitemos;<\/li>\n<li>Grabaci\u00f3n:<br \/>\nLa escritura en memoria NOR flash se ve como una normal, pero tiene una peculiaridad: solo se puede cambiar un 1 por un 0, pero no al rev\u00e9s. Por ejemplo, si en nuestra celda de memoria ten\u00edamos 0x55, despu\u00e9s de escribirle 0x0f ya se almacenar\u00e1 como 0x05. <em>(ver tabla un poco m\u00e1s abajo)<\/em>;<\/li>\n<li>Borrar:<br \/>\nPor supuesto, tambi\u00e9n necesitamos poder realizar la operaci\u00f3n inversa: cambiar un 0 por un 1, y para eso existe la operaci\u00f3n de borrado. A diferencia de las dos anteriores, opera no con bytes, sino con bloques (el tama\u00f1o m\u00ednimo del bloque de borrado en el chip seleccionado es de 4 KB). Borrar destruye todo el bloque en su totalidad y es la \u00fanica manera de cambiar un 0 por un 1. Por lo tanto, al trabajar con memoria flash, a menudo se deben alinear las estructuras de datos al borde del bloque de borrado.<br \/>\nEscritura en NOR Flash:<\/li>\n<\/ol>\n<p><\/p>\n<p>Datos binarios<\/p>\n<p><strong>Era<\/strong><br \/>\n<code>01010101<\/code><\/p>\n<p><strong>Escribimos<\/strong><br \/>\n<code>00001111<\/code><\/p>\n<p><strong>Se volvi\u00f3<\/strong><br \/>\n<code>00000101<\/code><\/p>\n<p><\/p>\n<p>El registro en s\u00ed representa una secuencia de entradas de longitud variable. La longitud t\u00edpica de una entrada es de aproximadamente 30 bytes (aunque a veces hay entradas de varios kilobytes). <em>En este caso, trabajamos con ellos simplemente como un conjunto de bytes, pero, si es interesante, dentro de las entradas se utiliza CBOR.<\/em><\/p>\n<p><\/p>\n<p>Adem\u00e1s del registro, necesitamos almacenar cierta informaci\u00f3n 'de configuraci\u00f3n', tanto actualizable como no: un ID del dispositivo, las calibraciones de los sensores, un indicador de 'dispositivo desconectado temporalmente', etc.<br \/>\nEsta informaci\u00f3n consiste en un conjunto de registros clave-valor, que tambi\u00e9n se almacenan en CBOR. No tenemos mucha de esta informaci\u00f3n (m\u00e1ximo unos pocos kilobytes) y no se actualiza con frecuencia.<br \/>\nA partir de ahora la llamaremos contexto.<\/p>\n<p><\/p>\n<p>Si recordamos de d\u00f3nde comenz\u00f3 este art\u00edculo, es muy importante garantizar la fiabilidad del almacenamiento de datos y, de ser posible, la continuidad del trabajo incluso en caso de fallos de hardware \/ corrupci\u00f3n de datos.<\/p>\n<p><\/p>\n<p>\u00bfQu\u00e9 fuentes de problemas se pueden considerar?<\/p>\n<p><\/p>\n<ul>\n<li>Desconexi\u00f3n de la alimentaci\u00f3n en el momento de las operaciones de escritura\/borrado. Esto es del tipo 'no hay t\u00e1ctica contra la fuerza bruta'.<br \/>\nInformaci\u00f3n de <noindex><a rel=\"nofollow\" href=\"https:\/\/electronics.stackexchange.com\/questions\/225956\/what-would-happen-in-case-of-power-outage-during-nor-flash-erase-or-programming\">las discusiones<\/a><\/noindex> en stackexchange: al desconectar la alimentaci\u00f3n durante el trabajo con flash, tanto la operaci\u00f3n de borrado (estableciendo en 1) como la de escritura (estableciendo en 0) conducen a un comportamiento indefinido: los datos pueden escribirse, escribirse parcialmente (digamos, se transmitieron 10 bytes\/80 bits, y solo se lograron escribir 45 bits), no se puede descartar que partes de los bits queden en un estado 'intermedio' (la lectura puede devolver tanto 0 como 1);<\/li>\n<li>Errores de la propia memoria flash.<br \/>\nAunque la BER es muy baja, no puede ser igual a cero;<\/li>\n<li>Errores en el bus<br \/>\nLos datos transmitidos a trav\u00e9s de SPI no est\u00e1n protegidos de ninguna manera; pueden ocurrir tanto errores de bit aislados como errores de sincronizaci\u00f3n \u2014 p\u00e9rdida o inserci\u00f3n de bits (lo que lleva a distorsiones masivas de datos);<\/li>\n<li>Otros errores\/fallos<br \/>\nErrores en el c\u00f3digo, 'fallos' en la Raspberry, intervenci\u00f3n de extraterrestres...<\/li>\n<\/ul>\n<p><\/p>\n<p>He formulado los requisitos, cuyo cumplimiento considero necesario para garantizar la fiabilidad:<\/p>\n<p><\/p>\n<ul>\n<li>las grabaciones deben ir directamente a la memoria flash, no se considera la escritura diferida; - si ocurre un error, debe detectarse y manejarse lo antes posible; - el sistema debe restaurar su funcionamiento tras los errores siempre que sea posible.<br \/>\n<em>(ejemplo de la vida real 'de c\u00f3mo no debe ser', con el que creo que todos se han encontrado: despu\u00e9s de un reinicio forzado, el sistema de archivos se 'rompi\u00f3' y el sistema operativo no arranca)<\/em><\/li>\n<\/ul>\n<p><\/p>\n<h2 id=\"idei-podhody-razmyshleniya\">Ideas, enfoques, reflexiones<\/h2>\n<p><\/p>\n<p>Cuando empec\u00e9 a pensar en esta tarea, me pasaron por la cabeza muchas ideas, por ejemplo:<\/p>\n<p><\/p>\n<ul>\n<li>utilizar compresi\u00f3n de datos;<\/li>\n<li>usar estructuras de datos ingeniosas, por ejemplo, almacenar los encabezados de los registros por separado de los propios registros, para que en caso de error en alguno de ellos se puedan leer sin problemas los dem\u00e1s;<\/li>\n<li>usar campos de bits para controlar la finalizaci\u00f3n del registro al cortar la alimentaci\u00f3n;<\/li>\n<li>almacenar sumas de verificaci\u00f3n para todo y para todos;<\/li>\n<li>usar alguna variante de codificaci\u00f3n de correcci\u00f3n de errores.<\/li>\n<\/ul>\n<p><\/p>\n<p>Parte de estas ideas se utiliz\u00f3, y se decidi\u00f3 desechar otras. Vamos por partes.<\/p>\n<p><\/p>\n<h3 id=\"szhatie-dannyh\">Compresi\u00f3n de datos<\/h3>\n<p><\/p>\n<p>Los eventos que registramos en el registro son bastante homog\u00e9neos y repetitivos ('lanz\u00f3 una moneda de 5 rublos', 'presion\u00f3 el bot\u00f3n de cambio',...). Por lo tanto, la compresi\u00f3n deber\u00eda resultar bastante eficaz.<\/p>\n<p><\/p>\n<p>Los gastos generales de compresi\u00f3n son insignificantes (tenemos un procesador bastante potente, incluso en el primer Pi hab\u00eda un n\u00facleo con una frecuencia de 700MHz, en los modelos actuales hay varios n\u00facleos con frecuencia superior a un gigahercio), la velocidad de intercambio con el almacenamiento no es alta (varios megabytes por segundo), el tama\u00f1o de los registros es peque\u00f1o. En general, si la compresi\u00f3n afecta el rendimiento, solo ser\u00e1 de manera positiva <em>(absolutamente no cr\u00edtico, solo lo constato)<\/em>. Adem\u00e1s, no tenemos un embedded real, sino un Linux normal, por lo que la implementaci\u00f3n no deber\u00eda requerir mucho esfuerzo (basta con enlazar la biblioteca y usar algunas funciones de ella).<\/p>\n<p><\/p>\n<p>Se tom\u00f3 una parte del registro de un dispositivo en funcionamiento (1.7 Mb, 70 mil registros) y se verific\u00f3 inicialmente su compresibilidad utilizando gzip, lz4, lzop, bzip2, xz, zstd que ten\u00edamos en la computadora.<\/p>\n<p><\/p>\n<ul>\n<li>gzip, xz, zstd mostraron resultados similares (40 Kb).<br \/>\nMe sorprendi\u00f3 que el famoso xz se comportara aqu\u00ed al nivel de gzip o zstd;<\/li>\n<li>lzip con la configuraci\u00f3n predeterminada dio un resultado ligeramente peor;<\/li>\n<li>lz4 y lzop mostraron un resultado no muy bueno (150 Kb);<\/li>\n<li>bzip2 mostr\u00f3 un resultado sorprendentemente bueno (18 Kb).<\/li>\n<\/ul>\n<p><\/p>\n<p>As\u00ed que los datos se comprimen muy bien.<br \/>\nAs\u00ed que (si no encontramos defectos fatales) \u00a1habr\u00e1 compresi\u00f3n! Simplemente porque se podr\u00e1 almacenar m\u00e1s datos en la misma memoria flash.<\/p>\n<p><\/p>\n<p>Pensemos en las desventajas.<\/p>\n<p><\/p>\n<p>El primer problema: ya hemos acordado que cada registro debe ir inmediatamente a la memoria flash. Normalmente, un compresor acumula datos del flujo de entrada hasta que decide que es hora de escribir en la salida. Pero nosotros necesitamos obtener inmediatamente un bloque de datos comprimidos y guardarlo en memoria no vol\u00e1til.<\/p>\n<p><\/p>\n<p>Veo tres caminos:<\/p>\n<p><\/p>\n<ol>\n<li>Comprimir cada registro usando compresi\u00f3n de diccionario en lugar de los algoritmos mencionados anteriormente.<br \/>\nEs una opci\u00f3n funcional, pero no me gusta. Para garantizar un nivel de compresi\u00f3n m\u00e1s o menos aceptable, el diccionario deber\u00eda estar 'ajustado' a los datos espec\u00edficos; cualquier cambio har\u00e1 que el nivel de compresi\u00f3n caiga de manera catastr\u00f3fica. S\u00ed, el problema se resuelve creando una nueva versi\u00f3n del diccionario, pero eso es un dolor de cabeza: tendremos que almacenar todas las versiones del diccionario; en cada registro necesitaremos indicar con qu\u00e9 versi\u00f3n del diccionario fue comprimido...<\/li>\n<li>Comprimir cada registro con algoritmos 'cl\u00e1sicos', pero independientemente de los dem\u00e1s.<br \/>\nLos algoritmos de compresi\u00f3n considerados no est\u00e1n dise\u00f1ados para trabajar con registros de este tama\u00f1o (decenas de bytes), el coeficiente de compresi\u00f3n ser\u00e1 claramente inferior a 1 (es decir, el volumen de datos aumentar\u00e1 en lugar de comprimirse);<\/li>\n<li>Hacer un FLUSH despu\u00e9s de cada registro.<br \/>\nEn muchas bibliotecas de compresi\u00f3n hay soporte para FLUSH. Este es un comando (o un par\u00e1metro para el procedimiento de compresi\u00f3n), que al recibirlo, el compresor forma un flujo comprimido de tal manera que con base en \u00e9l se pueden reconstruir <strong>cargas de trabajo dejar\u00e1n de funcionar!<\/strong> los datos no comprimidos que ya se han recibido. Tal an\u00e1logo <code>sync<\/code> en sistemas de archivos o <code>commit<\/code> en sql.<br \/>\nEs importante que las operaciones de compresi\u00f3n posteriores pueden usar el diccionario acumulado y el grado de compresi\u00f3n no se ver\u00e1 tan afectado como en la opci\u00f3n anterior.<\/li>\n<\/ol>\n<p><\/p>\n<p>Creo que es obvio que eleg\u00ed la tercera opci\u00f3n, as\u00ed que nos detendremos en ella m\u00e1s en detalle.<\/p>\n<p><\/p>\n<p>Encontrado <noindex><a rel=\"nofollow\" href=\"https:\/\/www.bolet.org\/~pornin\/deflate-flush.html\">un excelente art\u00edculo<\/a><\/noindex> sobre FLUSH en zlib.<\/p>\n<p><\/p>\n<p>Hice una prueba basada en un art\u00edculo, tom\u00e9 70 mil registros de un registro de un dispositivo real, con un tama\u00f1o de p\u00e1gina de 60Kb <em>(volvemos al tama\u00f1o de la p\u00e1gina m\u00e1s tarde)<\/em> recib\u00ed:<\/p>\n<p><\/p>\n<p>Datos de entrada<br \/>\nCompresi\u00f3n gzip -9 (sin FLUSH)<br \/>\nzlib con Z_PARTIAL_FLUSH<br \/>\nzlib con Z_SYNC_FLUSH<\/p>\n<p><strong>Tama\u00f1o, Kb<\/strong><br \/>\n1692<br \/>\n40<br \/>\n352<br \/>\n604<\/p>\n<p><\/p>\n<p>A primera vista, el costo de FLUSH parece excesivo, sin embargo, en realidad tenemos una selecci\u00f3n limitada: o no comprimir en absoluto, o comprimir (y de manera bastante efectiva) con FLUSH. No olvidemos que tenemos 70 mil registros, la redundancia introducida por Z_PARTIAL_FLUSH es solo de 4-5 bytes por registro. Y el coeficiente de compresi\u00f3n result\u00f3 ser casi 5:1, lo cual es m\u00e1s que un excelente resultado.<\/p>\n<p>\n<b class=\"spoiler_title\">Puede parecer sorprendente, pero en realidad Z_SYNC_FLUSH es una forma m\u00e1s eficaz de realizar FLUSH.<\/b><\/p>\n<p>En el caso de usar Z_SYNC_FLUSH, los 4 \u00faltimos bytes de cada registro siempre ser\u00e1n 0x00, 0x00, 0xff, 0xff. Y si los conocemos, podemos no almacenarlos, por lo que el tama\u00f1o final resulta ser solo 324Kb.<\/p>\n<p><\/p>\n<p>En el art\u00edculo al que me refiero, hay una explicaci\u00f3n:<\/p>\n<p><\/p>\n<blockquote><p>Se a\u00f1ade un nuevo bloque de tipo 0 con contenidos vac\u00edos.<\/p>\n<p>Un bloque de tipo 0 con contenidos vac\u00edos consiste en:<\/p>\n<ul>\n<li>el encabezado de bloque de tres bits;<\/li>\n<li>0 a 7 bits iguales a cero, para lograr la alineaci\u00f3n de bytes;<\/li>\n<li>la secuencia de cuatro bytes 00 00 FF FF.<\/li>\n<\/ul>\n<p>\n<\/p><\/blockquote>\n<p>Como es f\u00e1cil de notar, en el \u00faltimo bloque antes de estos 4 bytes hay entre 3 y 10 bits nulos. Sin embargo, la pr\u00e1ctica ha mostrado que los bits nulos son en realidad un m\u00ednimo de 10.<\/p>\n<p><\/p>\n<p>Resulta que bloques de datos tan cortos suelen (\u00bfsiempre?) codificarse utilizando un bloque de tipo 1 (bloque fijo), que necesariamente termina con 7 bits nulos, por lo que obtenemos entre 10 y 17 bits nulos garantizados (y los dem\u00e1s ser\u00e1n nulos con una probabilidad de alrededor del 50%).<\/p>\n<p><\/p>\n<p>As\u00ed que, en los datos de prueba, en el 100% de los casos, antes de 0x00, 0x00, 0xff, 0xff hay un byte nulo, y en m\u00e1s de un tercio de los casos hay dos bytes nulos. <em>(posiblemente, se deba a que estoy usando CBOR binario, y al usar JSON de texto, se encontrar\u00edan m\u00e1s bloques de tipo 2 \u2014 bloques din\u00e1micos, por lo tanto habr\u00eda bloques sin bytes nulos adicionales antes de 0x00, 0x00, 0xff, 0xff)<\/em>.<\/p>\n<p><\/p>\n<p>En total, en los datos de prueba existentes se puede comprimirse en menos de 250Kb de datos comprimidos.<\/p>\n<p><\/p>\n<p>Se puede ahorrar un poco m\u00e1s al practicar el malabarismo de bits: ahora estamos ignorando la presencia de varios ceros al final del bloque, varios bits al principio del bloque tambi\u00e9n permanecen sin cambios...<br \/>\nPero aqu\u00ed tom\u00e9 la decisi\u00f3n de detenerme, de lo contrario, a este ritmo podr\u00eda llegar a desarrollar mi propio compresor.<\/p>\n<p><\/p>\n<p>En total, de mis datos de prueba obtuve entre 3 y 4 bytes por escritura, la tasa de compresi\u00f3n result\u00f3 ser de m\u00e1s de 6:1. Honestamente, no esperaba tal resultado; en mi opini\u00f3n, todo lo que sea mejor que 2:1 ya justifica el uso de compresi\u00f3n.<\/p>\n<p><\/p>\n<p>Todo est\u00e1 genial, pero zlib (deflate) sigue siendo un algoritmo de compresi\u00f3n un tanto arcaico y un poco anticuado. Solo el hecho de que se utilicen los \u00faltimos 32 KB del flujo de datos sin comprimir como diccionario se ve extra\u00f1o hoy en d\u00eda (es decir, si alg\u00fan bloque de datos es muy parecido a lo que estuvo en el flujo de entrada hace 40 KB, empezar\u00e1 a ser comprimido de nuevo, en lugar de hacer referencia a la entrada pasada). En los compresores modernos de moda, el tama\u00f1o del diccionario suele medirse en megabytes, no en kilobytes.<\/p>\n<p><\/p>\n<p>As\u00ed que continuamos nuestra mini-investigaci\u00f3n sobre compresores.<\/p>\n<p><\/p>\n<p>El siguiente fue bzip2 (recuerden, sin FLUSH mostr\u00f3 un grado de compresi\u00f3n fant\u00e1stico, casi 100:1). Lamentablemente, con FLUSH se comport\u00f3 muy mal, el tama\u00f1o de los datos comprimidos result\u00f3 ser mayor que el de los datos sin comprimir.<\/p>\n<p>\n<b class=\"spoiler_title\">Mis suposiciones sobre las razones del fracaso<\/b><\/p>\n<p>Libbz2 ofrece solo una opci\u00f3n de flush, que parece limpiar el diccionario (an\u00e1logo a Z_FULL_FLUSH en zlib), no se puede hablar de una compresi\u00f3n efectiva despu\u00e9s de esto.<\/p>\n<p><\/p>\n<p>Y el \u00faltimo que prob\u00e9 fue zstd. Dependiendo de los par\u00e1metros, comprime ya sea al nivel de gzip, pero mucho m\u00e1s r\u00e1pido, o mejor que gzip.<\/p>\n<p><\/p>\n<p>Lamentablemente, con FLUSH tambi\u00e9n se mostr\u00f3 'no muy' efectivo: el tama\u00f1o de los datos comprimidos fue de alrededor de 700 Kb.<\/p>\n<p><\/p>\n<p>Yo <noindex><a rel=\"nofollow\" href=\"https:\/\/github.com\/facebook\/zstd\/issues\/900\">hice una pregunta<\/a><\/noindex> en la p\u00e1gina del proyecto en github, recib\u00ed la respuesta de que se debe considerar hasta 10 bytes de datos de servicio por cada bloque de datos comprimidos, lo que se acerca a los resultados obtenidos; no se lograr\u00e1 superar a deflate.<\/p>\n<p><\/p>\n<p>En este punto decid\u00ed detenerme en los experimentos con compresores (recuerden, xz, lzip, lzo, lz4 tampoco mostraron buenos resultados en las pruebas sin FLUSH, y no consider\u00e9 algoritmos de compresi\u00f3n m\u00e1s ex\u00f3ticos).<\/p>\n<p><\/p>\n<p>Volvemos a los problemas de la archivaci\u00f3n.<\/p>\n<p><\/p>\n<p>El segundo problema (como se dice, en orden y no por importancia) es que los datos comprimidos se presentan en un \u00fanico flujo, en el que constantemente hay referencias a secciones anteriores. As\u00ed, al da\u00f1ar una parte de los datos comprimidos, no solo perdemos el bloque de datos descomprimidos asociado, sino tambi\u00e9n todos los siguientes.<\/p>\n<p><\/p>\n<p>Hay enfoques para resolver este problema:<\/p>\n<p><\/p>\n<ol>\n<li>Prevenir la aparici\u00f3n del problema: a\u00f1adir redundancia a los datos comprimidos que permita identificar y corregir errores; de esto hablaremos m\u00e1s adelante;<\/li>\n<li>Minimizar las consecuencias en caso de que ocurra un problema<br \/>\nYa hemos mencionado antes que se pueden comprimir cada bloque de datos de manera independiente, lo que har\u00e1 que el problema se resuelva por s\u00ed mismo (la corrupci\u00f3n de datos de un bloque conducir\u00e1 a la p\u00e9rdida de datos solo de ese bloque). Sin embargo, este es un caso extremo, en el que la compresi\u00f3n de datos ser\u00e1 ineficaz. El extremo opuesto: usar los 4MB de nuestro chip como un \u00fanico archivo comprimido, lo que nos dar\u00e1 una excelente compresi\u00f3n, pero consecuencias catastr\u00f3ficas en caso de corrupci\u00f3n de datos.<br \/>\n<em>S\u00ed, se necesita un compromiso en t\u00e9rminos de fiabilidad. Pero hay que recordar que estamos desarrollando un formato de almacenamiento de datos para memoria no vol\u00e1til con un BER extremadamente bajo y un tiempo de retenci\u00f3n de datos declarado de 20 a\u00f1os.<\/em><\/li>\n<\/ol>\n<p><\/p>\n<p>En el transcurso de los experimentos, descubr\u00ed que las p\u00e9rdidas de nivel de compresi\u00f3n m\u00e1s o menos notables comienzan en bloques de datos comprimidos de menos de 10KB.<br \/>\nSe mencion\u00f3 anteriormente que la memoria utilizada tiene una organizaci\u00f3n paginada, no veo razones por las cuales no deber\u00edamos usar la correspondencia 'una p\u00e1gina - un bloque de datos comprimidos'.<\/p>\n<p><\/p>\n<p>Es decir, el tama\u00f1o m\u00ednimo razonable de una p\u00e1gina es de 16KB (con un margen para la informaci\u00f3n de servicio). Sin embargo, un tama\u00f1o de p\u00e1gina tan peque\u00f1o impone limitaciones significativas al tama\u00f1o m\u00e1ximo de los registros.<\/p>\n<p><\/p>\n<p>Aunque por ahora no prevengo registros de m\u00e1s de unos kilobytes en formato comprimido, decid\u00ed usar p\u00e1ginas de 32KB (en total, eso significa 128 p\u00e1ginas por chip).<\/p>\n<p><\/p>\n<p><strong>Resumen:<\/strong><\/p>\n<p><\/p>\n<ul>\n<li>Los datos los almacenamos comprimidos usando zlib (deflate);<\/li>\n<li>Para cada registro, establecemos Z_SYNC_FLUSH;<\/li>\n<li>A cada registro comprimido le recortamos los bytes finales <em>(por ejemplo, 0x00, 0x00, 0xff, 0xff)<\/em>; en el encabezado indicamos cu\u00e1ntos bytes hemos recortado;<\/li>\n<li>Los datos se almacenan en p\u00e1ginas de 32 KB; dentro de la p\u00e1gina hay un flujo continuo de datos comprimidos; en cada p\u00e1gina comenzamos la compresi\u00f3n desde cero.<\/li>\n<\/ul>\n<p><\/p>\n<p>Y, antes de terminar con la compresi\u00f3n, me gustar\u00eda se\u00f1alar que obtenemos solo unos pocos bytes de informaci\u00f3n comprimida por registro, por lo que es crucial no inflar la informaci\u00f3n de control; cada byte cuenta aqu\u00ed.<\/p>\n<p><\/p>\n<h3 id=\"hranenie-zagolovkov-dannyh\">Almacenamiento de encabezados de datos<\/h3>\n<p><\/p>\n<p>Dado que tenemos registros de longitud variable, necesitamos alguna forma de determinar la ubicaci\u00f3n\/l\u00edmites de los registros.<\/p>\n<p><\/p>\n<p>Conozco tres enfoques:<\/p>\n<p><\/p>\n<ol>\n<li>Todos los registros se almacenan en un flujo continuo, primero va el encabezado del registro, que contiene la longitud, y luego el propio registro.<br \/>\nEn esta variante, tanto los encabezados como los datos pueden tener longitud variable.<br \/>\nDe hecho, tenemos una lista enlazada que se utiliza con frecuencia;<\/li>\n<li>Los encabezados y los registros se almacenan en flujos separados.<br \/>\nAl usar encabezados de longitud fija, logramos que la corrupci\u00f3n de un encabezado no afecte a los dem\u00e1s.<br \/>\nEste enfoque se utiliza, por ejemplo, en muchos sistemas de archivos;<\/li>\n<li>Los registros se almacenan en un flujo continuo, el l\u00edmite del registro se determina por un marcador (s\u00edmbolo\/secuencia de s\u00edmbolos que est\u00e1n prohibidos dentro de los bloques de datos). Si dentro de un registro encontramos un marcador, lo sustituimos por una cierta secuencia (lo escapamos).<br \/>\nEste enfoque se utiliza, por ejemplo, en el protocolo PPP.<\/li>\n<\/ol>\n<p><\/p>\n<p>Lo ilustrar\u00e9.<\/p>\n<p><\/p>\n<p>Opci\u00f3n 1:<br \/>\n<img decoding=\"async\" alt=\"Mi implementaci\u00f3n de un b\u00fafer circular en memoria NOR flash\" src=\"\/wp-content\/uploads\/2019\/12\/e5a9676ca21eaca07e64ddf9fcd9f2eb.jpg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nAqu\u00ed todo es muy sencillo: sabiendo la longitud del registro, podemos calcular la direcci\u00f3n del siguiente encabezado. As\u00ed nos movemos a trav\u00e9s de los encabezados hasta que encontramos un \u00e1rea llena de 0xff (\u00e1rea libre) o el final de la p\u00e1gina.<\/p>\n<p><\/p>\n<p>Opci\u00f3n 2:<br \/>\n<img decoding=\"async\" alt=\"Mi implementaci\u00f3n de un b\u00fafer circular en memoria NOR flash\" src=\"\/wp-content\/uploads\/2019\/12\/4fed4860fb659ab6042be9aeeb5c041a.jpg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nDebido a la longitud variable de los registros, no podemos decir de antemano cu\u00e1ntos registros (y, por lo tanto, encabezados) necesitaremos por p\u00e1gina. Se pueden dividir los encabezados y los datos en diferentes p\u00e1ginas, pero prefiero otro enfoque: colocamos tanto los encabezados (de tama\u00f1o fijo) como los datos (de longitud variable) en la misma p\u00e1gina, sin embargo, los encabezados comienzan al principio de la p\u00e1gina y los datos desde el final. Una vez que se 'encuentran' (no hay suficiente espacio libre para un nuevo registro), consideramos que esta p\u00e1gina est\u00e1 llena.<\/p>\n<p><\/p>\n<p>Opci\u00f3n 3:<br \/>\n<img decoding=\"async\" alt=\"Mi implementaci\u00f3n de un b\u00fafer circular en memoria NOR flash\" src=\"\/wp-content\/uploads\/2019\/12\/dfb64009aa7781fcb8a47423ff4160c6.jpg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nNo es necesario almacenar la longitud u otra informaci\u00f3n sobre la ubicaci\u00f3n de los datos en el encabezado; es suficiente con los marcadores que indican los l\u00edmites de los registros. Sin embargo, los datos deben ser procesados durante la escritura\/lectura.<br \/>\nComo marcador, usar\u00eda 0xff (que llena la p\u00e1gina despu\u00e9s de borrar), de esa manera el \u00e1rea libre no se interpretar\u00e1 como datos.<\/p>\n<p><\/p>\n<p>Tabla comparativa:<\/p>\n<p><\/p>\n<p>Opci\u00f3n 1<br \/>\nOpci\u00f3n 2<br \/>\nOpci\u00f3n 3<\/p>\n<p><strong>Resistencia a errores<\/strong><br \/>\n\u2014<br \/>\n+<br \/>\n+<\/p>\n<p><strong>Compactaci\u00f3n<\/strong><br \/>\n+<br \/>\n\u2014<br \/>\n+<\/p>\n<p><strong>Complejidad de implementaci\u00f3n<\/strong><br \/>\n*<br \/>\n**<br \/>\n**<\/p>\n<p><\/p>\n<p>La opci\u00f3n 1 tiene una desventaja fatal: si se da\u00f1a alguno de los encabezados, se destruye toda la cadena subsiguiente. Las otras opciones permiten recuperar parte de los datos incluso en caso de da\u00f1os masivos.<br \/>\nPero aqu\u00ed es pertinente recordar que decidimos almacenar los datos en formato comprimido, de todos modos, perdemos todos los datos en la p\u00e1gina despu\u00e9s de un registro 'da\u00f1ado', por lo que, aunque en la tabla haya un menos, no lo tomamos en cuenta.<\/p>\n<p><\/p>\n<p>Compactaci\u00f3n:<\/p>\n<p><\/p>\n<ul>\n<li>En la primera opci\u00f3n solo necesitamos almacenar la longitud en el encabezado; si usamos variables de longitud variable, en la mayor\u00eda de los casos podemos arreglarnos con un solo byte;<\/li>\n<li>En la segunda opci\u00f3n necesitamos almacenar la direcci\u00f3n inicial y la longitud; la escritura debe ser de tama\u00f1o fijo, lo estimo en 4 bytes por entrada (dos bytes para el desplazamiento y dos bytes para la longitud);<\/li>\n<li>A la tercera opci\u00f3n le basta con un solo car\u00e1cter para indicar el inicio de la entrada, m\u00e1s la propia entrada aumentar\u00e1 debido a la escapaci\u00f3n en un 1-2%. En general, hay una paridad aproximada con la primera opci\u00f3n.<\/li>\n<\/ul>\n<p><\/p>\n<p>Inicialmente consider\u00e9 la segunda opci\u00f3n como la principal (e incluso escrib\u00ed una implementaci\u00f3n). Solo renunci\u00e9 a ella cuando decid\u00ed definitivamente usar compresi\u00f3n.<\/p>\n<p><\/p>\n<p><em>Quiz\u00e1s en alg\u00fan momento utilice una variante como esta. Por ejemplo, si tuviera que almacenar datos para una nave que navega entre la Tierra y Marte, ser\u00edan requisitos completamente diferentes en t\u00e9rminos de fiabilidad, radiaci\u00f3n espacial, \u2026<\/em><\/p>\n<p><\/p>\n<p>En cuanto a la tercera opci\u00f3n: le di dos estrellas por la dificultad de implementaci\u00f3n simplemente porque no me gusta lidiar con la escapaci\u00f3n, el cambio de longitud en el proceso, etc. S\u00ed, puede que sea prejuicioso, pero ser\u00e9 yo quien deba escribir el c\u00f3digo \u2014 \u00bfpor qu\u00e9 obligarme a hacer algo que no me gusta?<\/p>\n<p><\/p>\n<p><strong>Resumen:<\/strong> Elegimos la opci\u00f3n de almacenamiento en forma de cadenas 'encabezado con longitud \u2014 datos de longitud variable' por su eficacia y simplicidad de implementaci\u00f3n.<\/p>\n<p><\/p>\n<h3 id=\"ispolzovanie-bitovyh-poley-dlya-kontrolya-uspeshnosti-operaciy-zapisi\">Uso de campos de bits para controlar el \u00e9xito de las operaciones de escritura<\/h3>\n<p><\/p>\n<p>Ya no recuerdo d\u00f3nde vi la idea, pero se ve m\u00e1s o menos as\u00ed:<br \/>\nPara cada registro, se asignan varios bits para almacenar indicadores.<br \/>\n<em>Como mencionamos anteriormente, despu\u00e9s de borrar, todos los bits est\u00e1n llenos de 1, y podemos cambiar 1 a 0, pero no al rev\u00e9s.<\/em> As\u00ed que para 'bandera no establecida' usamos 1, para 'bandera establecida' \u2014 0.<\/p>\n<p><\/p>\n<p>As\u00ed es como puede verse la colocaci\u00f3n de un registro de longitud variable en Flash:<\/p>\n<p><\/p>\n<ol>\n<li>Establecemos el indicador 'la escritura de longitud ha comenzado';<\/li>\n<li>Escribimos la longitud;<\/li>\n<li>Establecemos el indicador 'la escritura de datos ha comenzado';<\/li>\n<li>Escribimos los datos;<\/li>\n<li>Establecemos el indicador 'la escritura ha terminado'.<\/li>\n<\/ol>\n<p><\/p>\n<p>Adem\u00e1s de esto, tendremos un indicador 'ha ocurrido un error', es decir, 4 indicadores de bits.<\/p>\n<p><\/p>\n<p>En este caso, tenemos dos estados estables '1111' \u2014 la escritura no ha comenzado y '1000' \u2014 la escritura ha sido exitosa; en caso de una interrupci\u00f3n inesperada del proceso de escritura, obtendremos estados intermedios que luego podremos detectar y manejar.<\/p>\n<p><\/p>\n<p>El enfoque es interesante, pero solo protege contra un corte repentino de energ\u00eda y fallos similares, lo cual es importante, sin embargo, no es la \u00fanica (y ni siquiera la principal) causa de posibles fallos.<\/p>\n<p><\/p>\n<p><strong>Resumen:<\/strong> Sigamos adelante en busca de una buena soluci\u00f3n.<\/p>\n<p><\/p>\n<h3 id=\"kontrolnye-summy\">Sumas de verificaci\u00f3n<\/h3>\n<p><\/p>\n<p>Las sumas de verificaci\u00f3n tambi\u00e9n permiten asegurarnos (con suficiente probabilidad) de que estamos leyendo exactamente lo que se deber\u00eda haber grabado. Y, a diferencia de los campos de bits considerados anteriormente, siempre funcionan.<\/p>\n<p><\/p>\n<p>Si consideramos la lista de posibles fuentes de problemas que mencionamos anteriormente, la suma de verificaci\u00f3n puede detectar el error independientemente de su origen <em>(salvo, quiz\u00e1s, por alien\u00edgenas malintencionados \u2014 ellos pueden falsificar la suma de verificaci\u00f3n tambi\u00e9n)<\/em>.<\/p>\n<p><\/p>\n<p>As\u00ed que, si nuestro objetivo es verificar que los datos son \u00edntegros, las sumas de verificaci\u00f3n son una excelente idea.<\/p>\n<p><\/p>\n<p>La elecci\u00f3n del algoritmo para calcular la suma de verificaci\u00f3n no gener\u00f3 dudas: CRC. Por un lado, las propiedades matem\u00e1ticas permiten capturar errores de ciertos tipos al 100%, y por otro lado, en datos aleatorios, este algoritmo suele mostrar una probabilidad de colisiones no mucho mayor que el l\u00edmite te\u00f3rico. <img decoding=\"async\" alt=\"Mi implementaci\u00f3n de un b\u00fafer circular en memoria NOR flash\" src=\"\/wp-content\/uploads\/2019\/12\/bf9cca3564db7d9d03d3ce49642d3a71.jpg\" style=\"display:block;margin: 0 auto;\" \/>. Aunque no sea el algoritmo m\u00e1s r\u00e1pido, ni siempre el que minimiza el n\u00famero de colisiones, tiene una cualidad muy importante: en las pruebas que he encontrado, no he visto patrones donde claramente falle. La estabilidad es la principal cualidad en este caso.<\/p>\n<p><\/p>\n<p>Ejemplo de un estudio voluminoso: <noindex><a rel=\"nofollow\" href=\"http:\/\/amsoftware.narod.ru\/algo.html\">parte 1<\/a><\/noindex>, <noindex><a rel=\"nofollow\" href=\"http:\/\/amsoftware.narod.ru\/algo2.html\">parte 2<\/a><\/noindex> <em>(enlaces a narod.ru, disculpen)<\/em>.<\/p>\n<p><\/p>\n<p>Sin embargo, el problema de elegir el valor de control no est\u00e1 completo; CRC es toda una familia de valores de control. Hay que decidir la longitud y luego elegir el polinomio.<\/p>\n<p><\/p>\n<p>La elecci\u00f3n de la longitud del valor de control no es una cuesti\u00f3n tan sencilla como parece a primera vista.<\/p>\n<p><\/p>\n<p>Ilustro:<br \/>\nSupongamos que tenemos una probabilidad de error en cada byte <img decoding=\"async\" alt=\"Mi implementaci\u00f3n de un b\u00fafer circular en memoria NOR flash\" src=\"\/wp-content\/uploads\/2019\/12\/89a9be2edf2a43cc9115eba37fa02fc8.jpg\" style=\"display:block;margin: 0 auto;\" \/> y un valor de control ideal, calculemos el n\u00famero promedio de errores en un mill\u00f3n de registros:<\/p>\n<p><\/p>\n<p>Datos, byte<br \/>\nValor de control, byte<br \/>\nErrores no detectados<br \/>\nFalsos positivos<br \/>\nTotal de activaciones incorrectas<\/p>\n<p>1<br \/>\n0<br \/>\n1000<br \/>\n0<br \/>\n1000<\/p>\n<p>1<br \/>\n1<br \/>\n4<br \/>\n999<br \/>\n1003<\/p>\n<p>1<br \/>\n2<br \/>\n\u22480<br \/>\n1997<br \/>\n1997<\/p>\n<p>1<br \/>\n4<br \/>\n\u22480<br \/>\n3990<br \/>\n3990<\/p>\n<p>10<br \/>\n0<br \/>\n9955<br \/>\n0<br \/>\n9955<\/p>\n<p>10<br \/>\n1<br \/>\n39<br \/>\n990<br \/>\n1029<\/p>\n<p>10<br \/>\n2<br \/>\n\u22480<br \/>\n1979<br \/>\n1979<\/p>\n<p>10<br \/>\n4<br \/>\n\u22480<br \/>\n3954<br \/>\n3954<\/p>\n<p>1000<br \/>\n0<br \/>\n632305<br \/>\n0<br \/>\n632305<\/p>\n<p>1000<br \/>\n1<br \/>\n2470<br \/>\n368<br \/>\n2838<\/p>\n<p>1000<br \/>\n2<br \/>\n10<br \/>\n735<br \/>\n745<\/p>\n<p>1000<br \/>\n4<br \/>\n\u22480<br \/>\n1469<br \/>\n1469<\/p>\n<p><\/p>\n<p>Aparentemente, todo es simple: elige la longitud del valor de control seg\u00fan la longitud de los datos protegidos, con un m\u00ednimo de activaciones incorrectas, y el asunto est\u00e1 resuelto.<\/p>\n<p><\/p>\n<p>Sin embargo, con valores de control cortos surge un problema: aunque detectan bien errores de bits individuales, pueden aceptar, con una probabilidad bastante alta, datos completamente aleatorios como correctos. Ya hubo un art\u00edculo en Habr que describ\u00eda <noindex><a rel=\"nofollow\" href=\"https:\/\/habr.com\/ru\/post\/428746\/\">el problema en la vida real.<\/a><\/noindex>.<\/p>\n<p><\/p>\n<p>Por lo tanto, para hacer pr\u00e1cticamente imposible la coincidencia aleatoria del valor de control, se deben usar valores de control de 32 bits o m\u00e1s. <em>(para longitudes superiores a 64 bits, generalmente se utilizan funciones hash criptogr\u00e1ficas)<\/em>.<\/p>\n<p><\/p>\n<p>A pesar de que antes mencion\u00e9 que se debe ahorrar espacio por todos los medios, a\u00fan as\u00ed utilizaremos un valor de control de 32 bits (16 bits son demasiado pocos, la probabilidad de colisi\u00f3n es superior al 0.01%; y 24 bits, como se dice, no son ni aqu\u00ed ni all\u00ed).<\/p>\n<p><\/p>\n<p>Aqu\u00ed puede surgir una objeci\u00f3n: \u00bfpara qu\u00e9 hemos ahorrado cada byte al elegir la compresi\u00f3n, para ahora dar 4 bytes a la vez? \u00bfNo ser\u00eda mejor no comprimir y no a\u00f1adir el valor de control? Por supuesto que no, la falta de compresi\u00f3n <em>no significa<\/em>, que la verificaci\u00f3n de la integridad no sea necesaria.<\/p>\n<p><\/p>\n<p>No vamos a inventar la rueda en cuanto a la elecci\u00f3n del polinomio, y tomaremos el popular CRC-32C.<br \/>\nEste c\u00f3digo detecta 6 errores de bits en paquetes de hasta 22 bytes (quiz\u00e1s el caso m\u00e1s com\u00fan para nosotros), 4 errores de bits en paquetes de hasta 655 bytes (tambi\u00e9n un caso frecuente para nosotros), 2 o cualquier n\u00famero impar de errores de bits en paquetes de cualquier longitud razonable.<\/p>\n<p>\n<b class=\"spoiler_title\">Si a alguien le interesan los detalles<\/b><\/p>\n<p><noindex><a rel=\"nofollow\" href=\"https:\/\/en.wikipedia.org\/wiki\/Cyclic_redundancy_check\">Art\u00edculo de Wikipedia<\/a><\/noindex> sobre CRC.<\/p>\n<p><\/p>\n<p><noindex><a rel=\"nofollow\" href=\"https:\/\/users.ece.cmu.edu\/~koopman\/crc\/c32\/0x8f6e37a0_len.txt\">Par\u00e1metros del c\u00f3digo crc-32c<\/a><\/noindex> en <noindex><a rel=\"nofollow\" href=\"http:\/\/users.ece.cmu.edu\/~koopman\/crc\/notes.html\">del sitio de Kupman<\/a><\/noindex> \u2014 quiz\u00e1s el principal especialista en CRC en el planeta.<\/p>\n<p><\/p>\n<p>En <noindex><a rel=\"nofollow\" href=\"http:\/\/users.ece.cmu.edu\/~koopman\/networks\/dsn02\/dsn02_koopman.pdf\">en su art\u00edculo<\/a><\/noindex> hay <noindex><a rel=\"nofollow\" href=\"https:\/\/users.ece.cmu.edu\/~koopman\/crc\/c32\/0xfa567d89_len.txt\">otro c\u00f3digo interesante<\/a><\/noindex>, que proporciona par\u00e1metros ligeramente mejores para las longitudes de paquetes relevantes para nosotros, pero no consider\u00e9 que la diferencia fuera significativa, y me siento lo suficientemente competente para elegir un c\u00f3digo personalizado en vez del est\u00e1ndar y bien investigado.<\/p>\n<p><\/p>\n<p>Adem\u00e1s, dado que nuestros datos est\u00e1n comprimidos, surge la pregunta: \u00bfdeber\u00edamos calcular la suma de verificaci\u00f3n sobre los datos comprimidos o no comprimidos?<\/p>\n<p><\/p>\n<p>Argumentos 'a favor' del c\u00e1lculo de la suma de comprobaci\u00f3n de datos no comprimidos:<\/p>\n<p><\/p>\n<ul>\n<li>al final, necesitamos verificar la integridad del almacenamiento de datos \u2014 as\u00ed que lo estamos verificando directamente (adem\u00e1s, se verificar\u00e1n posibles errores en la implementaci\u00f3n de compresi\u00f3n\/descompresi\u00f3n, da\u00f1os causados por memoria defectuosa, etc.);<\/li>\n<li>el algoritmo deflate en zlib tiene una implementaci\u00f3n bastante madura y <em>no deber\u00eda<\/em> caer ante datos de entrada 'corruptos', adem\u00e1s, a menudo puede detectar errores en el flujo de entrada por s\u00ed mismo, reduciendo la probabilidad general de no detecci\u00f3n de errores (realic\u00e9 una prueba invirtiendo un solo bit en un registro corto, zlib detect\u00f3 el error en aproximadamente un tercio de los casos).<\/li>\n<\/ul>\n<p><\/p>\n<p>Argumentos 'en contra' del c\u00e1lculo de la suma de comprobaci\u00f3n de datos no comprimidos:<\/p>\n<p><\/p>\n<ul>\n<li>CRC est\u00e1 'afinado' precisamente para errores de bit poco frecuentes, que son caracter\u00edsticos de la memoria flash (un error de bit en un flujo comprimido puede resultar en un cambio masivo en el flujo de salida, en el que, te\u00f3ricamente, podemos 'captar' una colisi\u00f3n);<\/li>\n<li>no me gusta mucho la idea de pasar datos potencialmente corruptos al descompresor, <noindex><a rel=\"nofollow\" href=\"https:\/\/www.cvedetails.com\/vulnerability-list\/vendor_id-72\/product_id-1820\/GNU-Zlib.html\">qui\u00e9n sabe<\/a><\/noindex>, c\u00f3mo reaccionar\u00e1.<\/li>\n<\/ul>\n<p><\/p>\n<p>En este proyecto decid\u00ed alejarme de la pr\u00e1ctica com\u00fan de almacenar la suma de verificaci\u00f3n de los datos no comprimidos.<\/p>\n<p><\/p>\n<p><strong>Resumen:<\/strong> utilizamos CRC-32C, la suma de verificaci\u00f3n se calcula a partir de los datos en la forma en que se almacenan en la flash (despu\u00e9s de la compresi\u00f3n).<\/p>\n<p><\/p>\n<h3 id=\"izbytochnost\">Redundancia<\/h3>\n<p><\/p>\n<p>El uso de codificaci\u00f3n redundante no elimina, por supuesto, la posibilidad de p\u00e9rdida de datos, sin embargo, puede reducir significativamente (a menudo en varios \u00f3rdenes de magnitud) la probabilidad de una p\u00e9rdida de datos irrecuperable.<\/p>\n<p><\/p>\n<p>Podemos utilizar diferentes tipos de redundancia para corregir errores.<br \/>\nLos c\u00f3digos de Hamming pueden corregir errores de un solo bit, los c\u00f3digos de Reed-Solomon son simb\u00f3licos, varias copias de datos junto con sumas de comprobaci\u00f3n o codificaci\u00f3n como RAID-6 pueden ayudar a recuperar datos incluso en caso de da\u00f1os masivos.<br \/>\nInicialmente estaba predispuesto a un uso amplio de la codificaci\u00f3n resistente a fallos, pero luego comprend\u00ed que primero necesitamos tener una idea clara de qu\u00e9 errores queremos proteger y luego elegir la codificaci\u00f3n.<\/p>\n<p><\/p>\n<p>Hemos mencionado antes que los errores deben detectarse lo antes posible. \u00bfEn qu\u00e9 momentos podemos encontrarnos con errores?<\/p>\n<p><\/p>\n<ol>\n<li>Registro incompleto (por alguna raz\u00f3n, durante el registro se interrumpi\u00f3 la alimentaci\u00f3n, Raspberry se colg\u00f3, \u2026)<br \/>\nLamentablemente, en caso de tal error, solo queda ignorar las grabaciones no v\u00e1lidas y considerar los datos perdidos;<\/li>\n<li>Errores de escritura (por alguna raz\u00f3n, se grab\u00f3 en la memoria flash algo diferente a lo que se estaba escribiendo)<br \/>\nPodemos detectar tales errores de inmediato si realizamos una lectura de comprobaci\u00f3n justo despu\u00e9s de la escritura;<\/li>\n<li>Distorsi\u00f3n de datos en la memoria durante el almacenamiento;<\/li>\n<li>Errores de lectura<br \/>\nPara corregir, basta con repetir la lectura varias veces en caso de discrepancia en la suma de comprobaci\u00f3n.<\/li>\n<\/ol>\n<p><\/p>\n<p>Es decir, solo los errores de tipo tres (degradaci\u00f3n espont\u00e1nea de los datos durante el almacenamiento) no pueden ser corregidos sin codificaci\u00f3n resistente a fallos. Se piensa que tales errores son extremadamente poco probables.<\/p>\n<p><\/p>\n<p><strong>Resumen:<\/strong> Se decidi\u00f3 renunciar a la codificaci\u00f3n redundante, pero si la operaci\u00f3n demuestra que esta decisi\u00f3n es err\u00f3nea, se volver\u00e1 a considerar la cuesti\u00f3n (con estad\u00edstica acumulada sobre fallos que permitir\u00e1 elegir el tipo \u00f3ptimo de codificaci\u00f3n).<\/p>\n<p><\/p>\n<h3 id=\"prochee\">Otros<\/h3>\n<p><\/p>\n<p>Por supuesto, el formato del art\u00edculo no permite justificar cada bit en el formato <em>(y ya me he quedado sin fuerzas)<\/em>, por lo que pasar\u00e9 brevemente por algunos aspectos que no se han mencionado anteriormente.<\/p>\n<p><\/p>\n<ul>\n<li>Se decidi\u00f3 hacer todas las p\u00e1ginas 'iguales'<br \/>\nEs decir, no habr\u00e1 p\u00e1ginas especiales con metadatos, flujos separados, etc., en su lugar, habr\u00e1 un flujo \u00fanico que reescribir\u00e1 todas las p\u00e1ginas por turno.<br \/>\nEsto asegura un desgaste uniforme de las p\u00e1ginas, la ausencia de un \u00fanico punto de fallo, y simplemente gusta;<\/li>\n<li>Es fundamental prever la versi\u00f3n del formato.<br \/>\n\u00a1Un formato sin n\u00famero de versi\u00f3n en el encabezado es un desastre!<br \/>\nBasta con a\u00f1adir al encabezado de la p\u00e1gina un campo con un n\u00famero m\u00e1gico (firma) que indique la versi\u00f3n del formato utilizado. <em>(no creo que en la pr\u00e1ctica haya incluso diez).<\/em>;<\/li>\n<li>Utilizar para las entradas (que son muchas) un encabezado de longitud variable, tratando en la mayor\u00eda de los casos de hacer su longitud de 1 byte;<\/li>\n<li>Para codificar la longitud del encabezado y la longitud de la parte truncada de la entrada comprimida, utilizar c\u00f3digos binarios de longitud variable.<\/li>\n<\/ul>\n<p><\/p>\n<p>Ayud\u00f3 mucho <noindex><a rel=\"nofollow\" href=\"https:\/\/planetcalc.com\/2481\/\">el generador en l\u00ednea<\/a><\/noindex> de c\u00f3digos Huffman. En cuesti\u00f3n de minutos, fue posible encontrar los c\u00f3digos de longitud variable necesarios.<\/p>\n<p><\/p>\n<h1 id=\"anchorformatanchoropisanie-formata-hraneniya-dannyh\"><noindex><a rel=\"nofollow\" name=\"format\"><\/a><\/noindex>Descripci\u00f3n del formato de almacenamiento de datos<\/h1>\n<p><\/p>\n<h2 id=\"byte-order\">Orden de bytes<\/h2>\n<p><\/p>\n<p>Los campos de tama\u00f1o superior a un byte se almacenan en formato big-endian (orden de bytes de red), es decir, 0x1234 se almacena como 0x12, 0x34.<\/p>\n<p><\/p>\n<h2 id=\"delenie-na-stranicy\">Divisi\u00f3n en p\u00e1ginas<\/h2>\n<p><\/p>\n<p>Toda la memoria flash est\u00e1 dividida en p\u00e1ginas de tama\u00f1o igual.<\/p>\n<p><\/p>\n<p>El tama\u00f1o de la p\u00e1gina por defecto es de 32 KB, pero no m\u00e1s de 1\/4 del tama\u00f1o total del chip de memoria (para un chip de 4 MB, eso equivale a 128 p\u00e1ginas).<\/p>\n<p><\/p>\n<p>Cada p\u00e1gina almacena datos de manera independiente de las dem\u00e1s (es decir, los datos de una p\u00e1gina no hacen referencia a los datos de otra p\u00e1gina).<\/p>\n<p><\/p>\n<p>Todas las p\u00e1ginas est\u00e1n numeradas en orden natural (en orden creciente de direcciones), comenzando desde el n\u00famero 0 (la p\u00e1gina cero comienza en la direcci\u00f3n 0, la primera en 32 KB, la segunda en 64 KB, etc.).<\/p>\n<p><\/p>\n<p>El chip de memoria se utiliza como un b\u00fafer circular (ring buffer), es decir, primero se escribe en la p\u00e1gina n\u00famero 0, luego en la n\u00famero 1, &#8230;, cuando llenamos la \u00faltima p\u00e1gina, comienza un nuevo ciclo y la escritura contin\u00faa desde la p\u00e1gina cero.<\/p>\n<p><\/p>\n<h2 id=\"vnutri-stranicy\">Dentro de la p\u00e1gina<\/h2>\n<p><\/p>\n<p><img decoding=\"async\" alt=\"Mi implementaci\u00f3n de un b\u00fafer circular en memoria NOR flash\" src=\"\/wp-content\/uploads\/2019\/12\/39b45f83dc46bb2fd7081ed2a0b638c9.jpg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nAl principio de la p\u00e1gina se almacena un encabezado de 4 bytes, luego un checksum del encabezado (CRC-32C), y a continuaci\u00f3n se almacenan registros en el formato &#171;encabezado, datos, checksum&#187;.<\/p>\n<p><\/p>\n<p>El encabezado de la p\u00e1gina (en el esquema de color verde sucio) consiste en:<\/p>\n<p><\/p>\n<ul>\n<li>un campo de dos bytes de n\u00famero m\u00e1gico (tambi\u00e9n es el indicador de la versi\u00f3n del formato)<br \/>\npara la versi\u00f3n actual del formato se considera como <code>0xed00 \u2295 n\u00famero de p\u00e1gina<\/code>;<\/li>\n<li>un contador de dos bytes &#171;Versi\u00f3n de la p\u00e1gina&#187; (n\u00famero del ciclo de sobrescritura de la memoria).<\/li>\n<\/ul>\n<p><\/p>\n<p>Las entradas en la p\u00e1gina se almacenan en formato comprimido (se utiliza el algoritmo deflate). Todas las entradas en una sola p\u00e1gina se comprimen en un solo flujo (se utiliza un diccionario com\u00fan), en cada nueva p\u00e1gina la compresi\u00f3n comienza de nuevo. Es decir, para descomprimir cualquier entrada se requieren todas las entradas anteriores de esa p\u00e1gina (y solo de esa).<\/p>\n<p><\/p>\n<p>Cada entrada se comprimir\u00e1 con la bandera Z_SYNC_FLUSH, al final del flujo comprimido hay 4 bytes 0x00, 0x00, 0xff, 0xff, precedidos, posiblemente, por uno o dos bytes cero.<br \/>\nEsta secuencia (de longitud 4, 5 o 6 bytes) se descarta al escribir en la memoria flash.<\/p>\n<p><\/p>\n<p>El encabezado de la entrada consiste en 1, 2 o 3 bytes, que contienen:<\/p>\n<p><\/p>\n<ul>\n<li>un bit (T) que indica el tipo de entrada: 0 \u2014 contexto, 1 \u2014 registro;<\/li>\n<li>un campo de longitud variable (S) de 1 a 7 bits, que determina la longitud del encabezado y el &#171;tail&#187; que se debe agregar al registro para la descompresi\u00f3n;<\/li>\n<li>la longitud de la entrada (L).<\/li>\n<\/ul>\n<p><\/p>\n<p>Tabla de valores S:<\/p>\n<p><\/p>\n<p>S<br \/>\nLongitud del encabezado, bytes<br \/>\nSe descarta al escribir, bytes<\/p>\n<p><code>0<\/code><br \/>\n1<br \/>\n5 (<code>00 00 00 ff ff<\/code>)<\/p>\n<p><code>10<\/code><br \/>\n1<br \/>\n6 (<code>00 00 00 00 ff ff<\/code>)<\/p>\n<p><code>110<\/code><br \/>\n2<br \/>\n4 (<code>00 00 ff ff<\/code>)<\/p>\n<p><code>1110<\/code><br \/>\n2<br \/>\n5 (<code>00 00 00 ff ff<\/code>)<\/p>\n<p><code>11110<\/code><br \/>\n2<br \/>\n6 (<code>00 00 00 00 ff ff<\/code>)<\/p>\n<p><code>1111100<\/code><br \/>\n3<br \/>\n4 (<code>00 00 ff ff<\/code>)<\/p>\n<p><code>1111101<\/code><br \/>\n3<br \/>\n5 (<code>00 00 00 ff ff<\/code>)<\/p>\n<p><code>1111110<\/code><br \/>\n3<br \/>\n6 (<code>00 00 00 00 ff ff<\/code>)<\/p>\n<p><\/p>\n<p>He tratado de ilustrar, no s\u00e9 cu\u00e1n claro ha quedado:<br \/>\n<img decoding=\"async\" alt=\"Mi implementaci\u00f3n de un b\u00fafer circular en memoria NOR flash\" src=\"\/wp-content\/uploads\/2019\/12\/8c9b739eec5af4429395c32b4ba4044a.jpg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nEn amarillo aqu\u00ed se indica el campo T, en blanco el campo S, en verde L (longitud de los datos comprimidos en bytes), en azul los datos comprimidos, en rojo los bytes finales de los datos comprimidos que no se escriben en la memoria flash.<\/p>\n<p><\/p>\n<p>As\u00ed, los encabezados de las entradas de longitud m\u00e1s com\u00fan (hasta 63+5 bytes en formato comprimido) podremos escribir con un solo byte.<\/p>\n<p><\/p>\n<p>Despu\u00e9s de cada entrada se almacena una suma de verificaci\u00f3n CRC-32C, cuya valor inicial (init) es el valor invertido de la suma de verificaci\u00f3n anterior.<\/p>\n<p><\/p>\n<p><em>El CRC tiene la propiedad de &#171;continuidad&#187;, funciona (m\u00e1s o menos invirtiendo bits en el proceso) con esta f\u00f3rmula: <img decoding=\"async\" alt=\"Mi implementaci\u00f3n de un b\u00fafer circular en memoria NOR flash\" src=\"\/wp-content\/uploads\/2019\/12\/b194d6a3d18ae2f4ae5d4054a93c0ea3.jpg\" style=\"display:block;margin: 0 auto;\" \/>.<br \/>\nEs decir, en realidad calculamos el CRC de todos los bytes anteriores de encabezados y datos en esta p\u00e1gina.<\/em><\/p>\n<p><\/p>\n<p>Inmediatamente despu\u00e9s de la suma de verificaci\u00f3n est\u00e1 el encabezado de la siguiente entrada.<\/p>\n<p><\/p>\n<p>El encabezado est\u00e1 dise\u00f1ado de tal manera que su primer byte siempre sea diferente de 0x00 y 0xff (si en lugar del primer byte del encabezado encontramos 0xff, eso significa que es un \u00e1rea a\u00fan no utilizada; 0x00 se\u00f1ala un error).<\/p>\n<p><\/p>\n<h2 id=\"primernye-algoritmy\">Algoritmos aproximados<\/h2>\n<p><\/p>\n<h3 id=\"chtenie-iz-flesh-pamyati\">Lectura de la memoria flash<\/h3>\n<p><\/p>\n<p>Cualquier lectura se realiza con verificaci\u00f3n de suma de verificaci\u00f3n.<br \/>\nSi la suma de comprobaci\u00f3n no coincide, la lectura se repite varias veces con la esperanza de leer los datos correctos.<\/p>\n<p><\/p>\n<p><em>(tiene sentido, Linux no almacena en cach\u00e9 la lectura de NOR Flash, probado)<\/em><\/p>\n<p><\/p>\n<h3 id=\"zapis-v-flesh-pamyat\">Escritura en la memoria flash<\/h3>\n<p><\/p>\n<p>Escribiendo datos.<br \/>\nLey\u00e9ndolos.<\/p>\n<p><\/p>\n<p>Si los datos le\u00eddos no coinciden con los escritos, rellenamos el \u00e1rea con ceros y se\u00f1alizamos un error.<\/p>\n<p><\/p>\n<h3 id=\"podgotovka-novoy-mikroshemy-k-rabote\">Preparaci\u00f3n de un nuevo chip para su funcionamiento<\/h3>\n<p><\/p>\n<p>Para la inicializaci\u00f3n, se escribe un encabezado con la versi\u00f3n 1 en la primera (m\u00e1s precisamente, la cero) p\u00e1gina.<br \/>\nDespu\u00e9s de eso, se escribe el contexto inicial en esta p\u00e1gina (contiene el UUID del dispositivo y configuraciones predeterminadas). <\/p>\n<p><\/p>\n<p>Todo listo, la memoria flash est\u00e1 lista para trabajar.<\/p>\n<p><\/p>\n<h3 id=\"zagruzka-avtomata\">Carga del dispositivo<\/h3>\n<p><\/p>\n<p>Al cargar, se leen los primeros 8 bytes de cada p\u00e1gina (encabezado + CRC), se ignoran las p\u00e1ginas con un Magic Number desconocido o un CRC incorrecto.<br \/>\nDe las p\u00e1ginas &#171;correctas&#187; se eligen las que tienen la versi\u00f3n m\u00e1xima, de ellas se toma la p\u00e1gina con el n\u00famero m\u00e1s alto.<br \/>\nSe lee el primer registro, se verifica la correcci\u00f3n del CRC y la presencia de la bandera &#171;contexto&#187;. Si todo est\u00e1 bien, esta p\u00e1gina se considera actual. Si no, retrocedemos a la anterior hasta encontrar una p\u00e1gina &#171;viva&#187;.<br \/>\nEn la p\u00e1gina encontrada leemos todos los registros, aquellos con la bandera &#171;contexto&#187; se aplican.<br \/>\nGuardamos el diccionario zlib (ser\u00e1 necesario para la reescritura en esta p\u00e1gina).<\/p>\n<p><\/p>\n<p>Listo, la carga ha finalizado, el contexto se ha restaurado, se puede trabajar.<\/p>\n<p><\/p>\n<h3 id=\"dobavlenie-zapisi-v-zhurnal\">A\u00f1adiendo una entrada al registro<\/h3>\n<p><\/p>\n<p>Comprimimos la entrada con el diccionario correcto, indicando Z_SYNC_FLUSH. Verificamos si la entrada comprimida cabe en la p\u00e1gina actual.<br \/>\nSi no cabe (o hubo errores de CRC en la p\u00e1gina), comenzamos una nueva p\u00e1gina (ver m\u00e1s abajo).<br \/>\nEscribimos la entrada y el CRC. Si ocurre un error, comenzamos una nueva p\u00e1gina.<\/p>\n<p><\/p>\n<h3 id=\"novaya-stranica\">Nueva p\u00e1gina<\/h3>\n<p><\/p>\n<p>Seleccionamos una p\u00e1gina libre con el n\u00famero m\u00ednimo (consideramos libre aquella que tiene una suma de comprobaci\u00f3n incorrecta en el encabezado o con una versi\u00f3n inferior a la actual). Si no hay tales p\u00e1ginas, seleccionamos la p\u00e1gina con el n\u00famero m\u00ednimo de aquellas que tienen la versi\u00f3n igual a la actual.<br \/>\nHacemos que la p\u00e1gina seleccionada sea borrada. Comparar el contenido con 0xff. Si algo no est\u00e1 bien, tomamos la siguiente p\u00e1gina libre, etc.<br \/>\nEn la p\u00e1gina borrada escribimos el encabezado, como primera entrada el estado actual del contexto, y como siguiente, la entrada no escrita del registro (si hay una).<\/p>\n<p><\/p>\n<h1 id=\"primenimost-formata\">Aplicabilidad del formato<\/h1>\n<p><\/p>\n<p>En mi opini\u00f3n, se ha logrado un formato decente para almacenar cualquier flujo de informaci\u00f3n m\u00e1s o menos comprimible (texto simple, JSON, MessagePack, CBOR, posiblemente protobuf) en NOR Flash.<\/p>\n<p><\/p>\n<p>Por supuesto, el formato est\u00e1 &#171;optimizado&#187; para SLC NOR Flash.<\/p>\n<p><\/p>\n<p>No se debe usar con medios que tengan un alto BER, como NAND o MLC NOR. <em>(\u00bfhay memoria como esa a la venta? Solo he visto menciones en trabajos sobre c\u00f3digos de correcci\u00f3n).<\/em>.<\/p>\n<p><\/p>\n<p>Adem\u00e1s, no se debe utilizar con dispositivos que tengan su propio FTL: USB flash, SD, MicroSD, etc. <em>(para este tipo de memoria hice un formato con un tama\u00f1o de p\u00e1gina de 512 bytes, una firma al inicio de cada p\u00e1gina y n\u00fameros \u00fanicos de registros; a veces, de una flash &#171;fallida&#187; logr\u00e9 restaurar todos los datos con una simple lectura secuencial)<\/em>.<\/p>\n<p><\/p>\n<p>Dependiendo de las tareas, el formato se puede utilizar sin cambios en memorias flash de 128Kbit (16Kb) a 1Gbit (128Mb). Si se desea, se puede usar en chips de mayor volumen, solo que probablemente ser\u00e1 necesario ajustar el tama\u00f1o de la p\u00e1gina. <em>(Pero aqu\u00ed surge la cuesti\u00f3n de la viabilidad econ\u00f3mica, el precio de NOR Flash de gran capacidad no es alentador).<\/em>.<\/p>\n<p><\/p>\n<p>Si alguien encuentra el formato interesante y quiere usarlo en un proyecto abierto, escr\u00edbeme, intentar\u00e9 encontrar tiempo, ajustar el c\u00f3digo y publicarlo en github.<\/p>\n<p><\/p>\n<h1 id=\"zaklyuchenie\">Conclusi\u00f3n<\/h1>\n<p><\/p>\n<p>Como podemos ver, al final el formato result\u00f3 ser simple. <em>e incluso aburrido.<\/em>.<\/p>\n<p><\/p>\n<p>En el art\u00edculo es dif\u00edcil reflejar la evoluci\u00f3n de mi punto de vista, pero cr\u00e9anme: al principio quer\u00eda crear algo complejo, indestructible, capaz de sobrevivir incluso tras una explosi\u00f3n nuclear cercana. Sin embargo, la raz\u00f3n (espero) ha prevalecido y poco a poco las prioridades se han desplazado hacia la simplicidad y la compactaci\u00f3n.<\/p>\n<p><\/p>\n<p>\u00bfPuede ser que me haya equivocado? S\u00ed, claro. Podr\u00eda suceder, por ejemplo, que hayamos comprado un lote de chips de mala calidad. O, por alguna otra raz\u00f3n, el equipo no cumpla con las expectativas de fiabilidad.<\/p>\n<p><\/p>\n<p>\u00bfTengo un plan para este caso? Creo que tras leer el art\u00edculo no duden de que tengo un plan. E incluso m\u00e1s de uno.<\/p>\n<p><\/p>\n<p>Si queremos ser un poco m\u00e1s serios, el formato se desarroll\u00f3 simult\u00e1neamente como una opci\u00f3n de trabajo y como un &#171;intento&#187;.<\/p>\n<p><\/p>\n<p>En este momento, todo funciona bien en la mesa, literalmente en unos d\u00edas la soluci\u00f3n ser\u00e1 desplegada. <em>(aproximadamente)<\/em> en un centenar de dispositivos, veremos qu\u00e9 sucede en la &#171;explotaci\u00f3n real&#187; (afortunadamente, espero que el formato permita detectar fallos de manera confiable; as\u00ed que se podr\u00e1 recopilar estad\u00edsticas completas). En unos meses se podr\u00e1n sacar conclusiones. <em>(y si no tengo suerte, tal vez antes)<\/em>.<\/p>\n<p><\/p>\n<p>Si al final del uso se detectan problemas graves y se requieren mejoras, definitivamente escribir\u00e9 sobre ello.<\/p>\n<p><\/p>\n<h1 id=\"literatura\">Literatura<\/h1>\n<p><\/p>\n<p>No quer\u00eda hacer una larga y aburrida lista de trabajos utilizados; al fin y al cabo, todos tienen Google.<\/p>\n<p><\/p>\n<p>Aqu\u00ed decid\u00ed dejar una lista de hallazgos que me parecieron especialmente interesantes, sin embargo, con el tiempo se trasladaron directamente al texto del art\u00edculo, quedando solo un \u00edtem en la lista:<\/p>\n<p><\/p>\n<ol>\n<li>Utilidad <noindex><a rel=\"nofollow\" href=\"https:\/\/github.com\/madler\/infgen\/\">infgen<\/a><\/noindex> del autor zlib. Muestra de forma comprensible el contenido de archivos deflate\/zlib\/gzip. Si necesitas entender el formato deflate (o gzip), lo recomiendo encarecidamente.<\/li>\n<\/ol>\n<p>Fuente: <a content=\"nofollow\" rel=\"nofollow\" href=\"https:\/\/habr.com\/ru\/post\/479044\/\">habr.com<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"<p>\u041f\u0440\u0435\u0434\u044b\u0441\u0442\u043e\u0440\u0438\u044f \u0415\u0441\u0442\u044c \u0442\u043e\u0440\u0433\u043e\u0432\u044b\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u044b \u0441\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0439 \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u043a\u0438. \u0412\u043d\u0443\u0442\u0440\u0438 Raspberry Pi \u0438 \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u043e\u0431\u0432\u044f\u0437\u043a\u0438 \u043d\u0430 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e\u0439 \u043f\u043b\u0430\u0442\u0435. \u041f\u043e\u0434\u043a\u043b\u044e\u0447\u0435\u043d\u044b \u043c\u043e\u043d\u0435\u0442\u043e\u043f\u0440\u0438\u0451\u043c\u043d\u0438\u043a, \u043a\u0443\u043f\u044e\u0440\u043e\u043f\u0440\u0438\u0451\u043c\u043d\u0438\u043a, \u0431\u0430\u043d\u043a\u043e\u0432\u0441\u043a\u0438\u0439 \u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b\u2026 \u0423\u043f\u0440\u0430\u0432\u043b\u044f\u0435\u0442 \u0432\u0441\u0435\u043c \u0441\u0430\u043c\u043e\u043f\u0438\u0441\u043d\u0430\u044f \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0430. \u0412\u0441\u044f \u0438\u0441\u0442\u043e\u0440\u0438\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u043f\u0438\u0448\u0435\u0442\u0441\u044f \u0432 \u0436\u0443\u0440\u043d\u0430\u043b \u043d\u0430 \u0444\u043b\u0435\u0448\u043a\u0435 (MicroSD), \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043f\u043e\u0442\u043e\u043c \u043f\u0435\u0440\u0435\u0434\u0430\u0451\u0442\u0441\u044f \u0447\u0435\u0440\u0435\u0437 \u0438\u043d\u0442\u0435\u0440\u043d\u0435\u0442 (\u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e USB-\u043c\u043e\u0434\u0435\u043c\u0430) \u043d\u0430 \u0441\u0435\u0440\u0432\u0435\u0440, \u0442\u0430\u043c \u0441\u043a\u043b\u0430\u0434\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0432 \u0411\u0414. \u0418\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044f \u043e \u043f\u0440\u043e\u0434\u0430\u0436\u0430\u0445 \u0437\u0430\u0433\u0440\u0443\u0436\u0430\u0435\u0442\u0441\u044f \u0432 1\u0441, \u0442\u0430\u043a\u0436\u0435 \u0435\u0441\u0442\u044c [&hellip;]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[688],"tags":[],"class_list":["post-53751","post","type-post","status-publish","format-standard","hentry","category-administrirovanie"],"aioseo_notices":[],"aioseo_head":"\n\t\t<!-- All in One SEO 5.0.2 - aioseo.com -->\n\t<meta name=\"description\" content=\"\u041f\u0440\u0435\u0434\u044b\u0441\u0442\u043e\u0440\u0438\u044f \u0415\u0441\u0442\u044c \u0442\u043e\u0440\u0433\u043e\u0432\u044b\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u044b \u0441\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0439 \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u043a\u0438. \u0412\u043d\u0443\u0442\u0440\u0438 Raspberry Pi \u0438 \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u043e\u0431\u0432\u044f\u0437\u043a\u0438 \u043d\u0430 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e\u0439 \u043f\u043b\u0430\u0442\u0435.\" \/>\n\t<meta name=\"robots\" content=\"max-image-preview:large\" \/>\n\t<meta name=\"author\" content=\"Yuri Gagarin\"\/>\n\t<link rel=\"canonical\" href=\"https:\/\/prohoster.info\/es\/blog\/administrirovanie\/moya-realizatsiya-koltsevogo-bufera-v-nor-flash\" \/>\n\t<meta name=\"generator\" content=\"All in One SEO (AIOSEO) 5.0.2\" \/>\n\t\t<meta property=\"og:locale\" content=\"es_ES\" \/>\n\t\t<meta property=\"og:site_name\" content=\"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b\" \/>\n\t\t<meta property=\"og:type\" content=\"article\" \/>\n\t\t<meta property=\"og:title\" content=\"\ud83e\udd47\u041c\u043e\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043a\u043e\u043b\u044c\u0446\u0435\u0432\u043e\u0433\u043e \u0431\u0443\u0444\u0435\u0440\u0430 \u0432 NOR flash | ProHoster\" \/>\n\t\t<meta property=\"og:description\" content=\"\u041f\u0440\u0435\u0434\u044b\u0441\u0442\u043e\u0440\u0438\u044f \u0415\u0441\u0442\u044c \u0442\u043e\u0440\u0433\u043e\u0432\u044b\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u044b \u0441\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0439 \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u043a\u0438. \u0412\u043d\u0443\u0442\u0440\u0438 Raspberry Pi \u0438 \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u043e\u0431\u0432\u044f\u0437\u043a\u0438 \u043d\u0430 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e\u0439 \u043f\u043b\u0430\u0442\u0435.\" \/>\n\t\t<meta property=\"og:url\" content=\"https:\/\/prohoster.info\/es\/blog\/administrirovanie\/moya-realizatsiya-koltsevogo-bufera-v-nor-flash\" \/>\n\t\t<meta property=\"og:image\" content=\"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg\" \/>\n\t\t<meta property=\"og:image:secure_url\" content=\"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg\" \/>\n\t\t<meta property=\"og:image:width\" content=\"350\" \/>\n\t\t<meta property=\"og:image:height\" content=\"350\" \/>\n\t\t<meta property=\"article:published_time\" content=\"2019-12-08T21:00:00+00:00\" \/>\n\t\t<meta property=\"article:modified_time\" content=\"2020-02-18T11:01:41+00:00\" \/>\n\t\t<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/prohoster\" \/>\n\t\t<meta property=\"article:author\" content=\"https:\/\/www.facebook.com\/prohoster\" \/>\n\t\t<!-- All in One SEO -->\n\n","aioseo_head_json":{"title":"\ud83e\udd47Mi implementaci\u00f3n de un b\u00fafer circular en NOR flash | ProHoster","description":"Antecedentes Hay m\u00e1quinas expendedoras de desarrollo propio. Dentro hay un Raspberry Pi y un poco de cableado en una placa separada.","canonical_url":"https:\/\/prohoster.info\/es\/blog\/administrirovanie\/moya-realizatsiya-koltsevogo-bufera-v-nor-flash","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"es_ES","og:site_name":"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b","og:type":"article","og:title":"\ud83e\udd47\u041c\u043e\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043a\u043e\u043b\u044c\u0446\u0435\u0432\u043e\u0433\u043e \u0431\u0443\u0444\u0435\u0440\u0430 \u0432 NOR flash | ProHoster","og:description":"\u041f\u0440\u0435\u0434\u044b\u0441\u0442\u043e\u0440\u0438\u044f \u0415\u0441\u0442\u044c \u0442\u043e\u0440\u0433\u043e\u0432\u044b\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u044b \u0441\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0439 \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u043a\u0438. \u0412\u043d\u0443\u0442\u0440\u0438 Raspberry Pi \u0438 \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u043e\u0431\u0432\u044f\u0437\u043a\u0438 \u043d\u0430 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e\u0439 \u043f\u043b\u0430\u0442\u0435.","og:url":"https:\/\/prohoster.info\/es\/blog\/administrirovanie\/moya-realizatsiya-koltsevogo-bufera-v-nor-flash","og:image":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:secure_url":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:width":350,"og:image:height":350,"article:published_time":"2019-12-08T21:00:00+00:00","article:modified_time":"2020-02-18T11:01:41+00:00","article:publisher":"https:\/\/www.facebook.com\/prohoster","article:author":"https:\/\/www.facebook.com\/prohoster"},"aioseo_meta_data":{"post_id":"53751","title":null,"description":null,"keywords":null,"keyphrases":null,"primary_term":null,"canonical_url":null,"og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":null,"og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"","isEnabled":true},"graphs":[]},"schema_type":null,"schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":null,"robots_max_videopreview":null,"robots_max_imagepreview":"large","priority":null,"frequency":null,"local_seo":null,"seo_analyzer_scan_date":"2026-01-24 08:36:23","breadcrumb_settings":null,"limit_modified_date":false,"reviewed_by":null,"ai":null,"created":"2021-02-28 20:18:30","updated":"2026-01-24 08:36:23","focus_keyword":null,"additional_keywords":null,"truseo_locale":null},"gt_translate_keys":[{"key":"link","format":"url"}],"_links":{"self":[{"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/posts\/53751","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/comments?post=53751"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/posts\/53751\/revisions"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/media?parent=53751"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/categories?post=53751"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/tags?post=53751"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}