{"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\/da\/blog\/administrirovanie\/moya-realizatsiya-koltsevogo-bufera-v-nor-flash","title":{"rendered":"Min implementering af en ringbuffer i NOR flash","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"<h1 id=\"predystoriya\">Background<\/h1>\n<p><\/p>\n<p>Der er salgsautomater udviklet internt. Inden i en Raspberry Pi og lidt ekstra udstyr p\u00e5 et separat kort. Tilsluttet er m\u00f8ntindkast, sedelmater, bankterminal... Det hele styres af et skr\u00e6ddersyet program. Al driftshistorik skrives til en log p\u00e5 et flash-drev (MicroSD), som derefter overf\u00f8res via internettet (med en USB-modem) til en server, hvor det gemmes i en database. Oplysninger om salget uploades til 1C, og der er ogs\u00e5 et simpelt web-interface til overv\u00e5gning osv. <\/p>\n<p><\/p>\n<p>S\u00e5 loggen er absolut n\u00f8dvendig \u2014 til registrering (herunder indt\u00e6gter, salg osv.), overv\u00e5gning (forskellige fejl og andre uforudsete omst\u00e6ndigheder); det kan siges at v\u00e6re al den information, vi har om denne automat. <\/p>\n<p><\/p>\n<h1 id=\"problema\">Problemet<\/h1>\n<p><\/p>\n<p>USB-drev viser sig at v\u00e6re meget ustabile enheder. De g\u00e5r med j\u00e6vne mellemrum i stykker. Dette f\u00f8rer til b\u00e5de stilstand i automaterne og (hvis loggen af en eller anden grund ikke kunne overf\u00f8res online) til tab af data.<\/p>\n<p><\/p>\n<p><em>Dette er ikke det f\u00f8rste fors\u00f8g med USB-drev; tidligere var der et andet projekt med mere end hundrede enheder, hvor loggen blev gemt p\u00e5 USB-drev, der var ogs\u00e5 problemer med p\u00e5lidelighed, og nogle gange var antallet af defekte enheder om m\u00e5neden i titaller. Vi har pr\u00f8vet forskellige USB-drev, herunder m\u00e6rkevarer med SLC hukommelse, og nogle modeller er mere p\u00e5lidelige end andre, men at skifte USB-drev l\u00f8ste ikke problemet fundamentalt.<\/em><\/p>\n<p><noindex><a rel=\"nofollow\" name=\"habracut\"><\/a><\/noindex> <\/p>\n<p><strong>Opm\u00e6rksomhed!<\/strong> Longread! Hvis du ikke er interesseret i 'hvorfor', men kun i 'hvordan', kan du g\u00e5 videre. <noindex><a rel=\"nofollow\" href=\"#format\">slutningen<\/a><\/noindex> af artiklen.<\/p>\n<p><\/p>\n<h1 id=\"reshenie\">L\u00f8sning<\/h1>\n<p><\/p>\n<p>Det f\u00f8rste, der kommer til at t\u00e6nke p\u00e5, er at opgive MicroSD, s\u00e6tte en SSD i stedet, og starte derfra. Teoretisk set er det muligvis, men ret dyrt, og ikke s\u00e5 p\u00e5lideligt (en USB-SATA adapter tilf\u00f8jes; statistikker for billige SSD'er ser heller ikke s\u00e5 gode ud).<\/p>\n<p><\/p>\n<p>USB HDD ser heller ikke ud til at v\u00e6re en s\u00e6rlig attraktiv l\u00f8sning.<\/p>\n<p><\/p>\n<p>Derfor kom vi frem til denne l\u00f8sning: beholde opstart fra MicroSD, men bruge dem i read-only tilstand, og gemme driftloggen (og anden unik information for det p\u00e5g\u00e6ldende udstyr \u2014 serienummer, sensor kalibreringer, osv.) et andet sted. <\/p>\n<p><\/p>\n<p>Emnet read-only filsystemer til Raspberry Pi er allerede blevet grundigt unders\u00f8gt, jeg vil ikke dv\u00e6le ved detaljerne i implementeringen i denne artikel <em>(men hvis der er interesse \u2014 s\u00e5 m\u00e5 jeg m\u00e5ske skrive en mini-artikel om dette emne)<\/em>. Det eneste, jeg gerne vil n\u00e6vne, er, at b\u00e5de ud fra personlige erfaringer og anmeldelser fra dem, der allerede har implementeret det, er der en vund i p\u00e5lideligheden. Ja, det er umuligt helt at undg\u00e5 fejl, men det er ret realistisk at reducere deres hyppighed betydeligt. Desuden bliver kortene ensartede, hvilket m\u00e6rkbart letter udskiftningen for servicepersonalet.<\/p>\n<p><\/p>\n<h2 id=\"apparatnaya-chast\">Hardware<\/h2>\n<p><\/p>\n<p>Der var ingen s\u00e6rlige tvivl om valget af hukommelsestype \u2014 NOR Flash.<br \/>\nArgumenter: <\/p>\n<p><\/p>\n<ul>\n<li>enkelt tilslutning (oftest SPI-bussen, som vi allerede har erfaring med, s\u00e5 der forventes ikke 'hardware'-problemer);<\/li>\n<li>lidt sjov pris;<\/li>\n<li>standard driftsprotokol (implementeringen findes allerede i Linux-kernen, hvis \u00f8nskes kan man tage en tredjepartsl\u00f8sning, som ogs\u00e5 findes, eller endda skrive sin egen, da alt er ganske enkelt);<\/li>\n<li>p\u00e5lidelighed og levetid:<br \/>\nfra et typisk datablad: data opbevares i 20 \u00e5r, 100.000 sletninger for hver blok;<br \/>\nfra eksterne kilder: ekstremt lav BER, det postuleres, at der ikke er behov for fejlkorrigeringskoder <em>(i nogle arbejder overvejes ECC for NOR, men normalt henviser de dog til MLC NOR, der findes ogs\u00e5 s\u00e5danne);<\/em>.<\/li>\n<\/ul>\n<p><\/p>\n<p>Lad os overveje kravene til volumen og ressource.<\/p>\n<p><\/p>\n<p>Vi \u00f8nsker, at data skal bevares sikkert i flere dage. Det er n\u00f8dvendigt for at sikre, at salgsstatistikken ikke g\u00e5r tabt i tilf\u00e6lde af kommunikationsproblemer. Lad os sigte efter 5 dage, i denne periode <em>(selv med hensyn til weekender og helligdage)<\/em> kan problemet l\u00f8ses.<\/p>\n<p><\/p>\n<p>Hos os indsamles omkring 100 kb log pr. dag (3-4 tusinde poster), men gradvist stiger det tal \u2014 detaljeringen \u00f8ges, og nye h\u00e6ndelser tilf\u00f8jes. Derudover er der nogle gange spikes (for eksempel begynder en sensor at spamme med falske positive). Lad os regne med 10.000 poster med 100 bytes \u2014 en megabyte om dagen.<\/p>\n<p><\/p>\n<p>Det giver i alt 5 Mb rene (godt komprimerbare) data. Dertil kommer <em>(grov vurdering)<\/em> 1 Mb overhead data.<\/p>\n<p><\/p>\n<p>Det vil sige, vi har brug for en chip p\u00e5 8 Mb, hvis vi ikke bruger kompression, eller 4 Mb, hvis vi bruger det. Helt realistiske tal for denne type hukommelse.<\/p>\n<p><\/p>\n<p>Hvad ang\u00e5r levetiden: hvis vi planl\u00e6gger, at hukommelsen bliver skrevet helt over, ikke oftere end hver 5. dag, s\u00e5 f\u00e5r vi mindre end tusind omskrivninger i l\u00f8bet af 10 \u00e5rs drift.<br \/>\nJeg minder om, at producenten lover hundrede tusinde.<\/p>\n<p>\n<b class=\"spoiler_title\">Lidt om NOR vs NAND<\/b><\/p>\n<p>I dag er NAND-hukommelse selvf\u00f8lgelig langt mere popul\u00e6r, men til dette projekt ville jeg ikke v\u00e6lge den; NAND kr\u00e6ver i mods\u00e6tning til NOR altid brug af fejlkorrektion, defekte bloktabeller osv., og benene p\u00e5 NAND-chips er som regel ogs\u00e5 mange flere.<\/p>\n<p><\/p>\n<p>Ulemper ved NOR kan n\u00e6vnes:<\/p>\n<p><\/p>\n<ul>\n<li>lille kapacitet (og dermed h\u00f8j pris pr. megabyte);<\/li>\n<li>lav udvekslingshastighed (meget p\u00e5 grund af brugen af sekventiel gr\u00e6nseflade, normalt SPI eller I2C);<\/li>\n<li>langsom sletning (afh\u00e6ngig af blokst\u00f8rrelsen tager det fra br\u00f8kdele af et sekund til flere sekunder).<\/li>\n<\/ul>\n<p><\/p>\n<p>Der ser ikke ud til at v\u00e6re noget kritisk for os, s\u00e5 lad os forts\u00e6tte.<\/p>\n<p><\/p>\n<p>Hvis detaljer er interessante, blev chippen valgt <noindex><a rel=\"nofollow\" href=\"https:\/\/www.adestotech.com\/wp-content\/uploads\/doc3686.pdf\">at25df321a<\/a><\/noindex> <em>(det er dog ikke v\u00e6sentligt, der er masser af analoger p\u00e5 markedet, som er kompatible med pinout og kommando-system; selv hvis vi beslutter os for at s\u00e6tte en chip fra en anden producent og\/eller af en anden st\u00f8rrelse, vil alt fungere uden \u00e6ndringer i koden)<\/em>.<\/p>\n<p><\/p>\n<p>Jeg bruger den indbyggede driver i Linux-kernen, p\u00e5 Raspberry Pi er det ret enkelt takket v\u00e6re underst\u00f8ttelsen af device tree overlay \u2014 man skal blot l\u00e6gge den kompilerede overlay i \/boot\/overlays og \u00e6ndre lidt i \/boot\/config.txt.<\/p>\n<p>\n<b class=\"spoiler_title\">Eksempel p\u00e5 dts-fil<\/b><\/p>\n<p>\u00c6rligt talt er jeg ikke sikker p\u00e5, at det er skrevet fejlfrit, men det fungerer.<\/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\">Og endnu en linje i config.txt<\/b><\/p>\n<pre><code class=\"plaintext\">dtoverlay=at25:spimaxfrequency=50000000<\/code><\/pre>\n<p><\/p>\n<p>Jeg vil lade beskrivelsen af, hvordan chippen forbindes til Raspberry Pi, ligge. P\u00e5 den ene side er jeg ikke specialist i elektronik, p\u00e5 den anden side er det ret enkelt selv for mig: chippen har kun 8 ben, hvoraf vi har brug for jord, str\u00f8m, SPI (CS, SI, SO, SCK); niveauerne svarer til dem p\u00e5 Raspberry Pi, ingen yderligere kredsl\u00f8b er n\u00f8dvendigt \u2014 man skal blot forbinde de n\u00e6vnte 6 ben.<\/p>\n<p><\/p>\n<h2 id=\"postanovka-zadachi\">Problemformulering<\/h2>\n<p><\/p>\n<p>Som s\u00e6dvanligt foreg\u00e5r opstilling af opgaven i flere iterationer, og jeg synes, det er tid til endnu en. S\u00e5 lad os stoppe op, samle det, der allerede er skrevet, og afklare de tilbageholdte detaljer.<\/p>\n<p><\/p>\n<p>S\u00e5 vi har besluttet, at loggen vil blive gemt i SPI NOR Flash.<\/p>\n<p>\n<b class=\"spoiler_title\">Hvad er NOR Flash for dem, der ikke ved det?<\/b><\/p>\n<p>Det er en ikke-flygtig hukommelse, hvor man kan udf\u00f8re tre operationer:<\/p>\n<p><\/p>\n<ol>\n<li>L\u00e6sning:<br \/>\nDen mest almindelige l\u00e6sning: vi sender adressen og l\u00e6ser s\u00e5 mange bytes som vi har brug for;<\/li>\n<li>Skrivning:<br \/>\nI NOR flash ser man ud som almindelig, men den har en s\u00e6rlig egenskab: man kan kun \u00e6ndre 1 til 0, men ikke omvendt. For eksempel, hvis der l\u00e5 0x55 i hukommelsescellen, s\u00e5 vil der efter skrivning af 0x0f st\u00e5 0x05 der. <em>(se tabellen lidt l\u00e6ngere nede)<\/em>;<\/li>\n<li>Slet:<br \/>\nSelvf\u00f8lgelig skal vi kunne udf\u00f8re den omvendte operation - \u00e6ndre 0 til 1; det er netop derfor, operationen slet eksisterer. I mods\u00e6tning til de to f\u00f8rste opererer den ikke med bytes, men med blokke (den mindste sletteblok i den valgte mikrochip er 4kb). Sletningen tilintetg\u00f8r hele blokken, og det er den eneste m\u00e5de at \u00e6ndre 0 til 1. Derfor skal man ofte justere datastrukturer til gr\u00e6nsen for sletteblok.<br \/>\nSkriv til NOR Flash:<\/li>\n<\/ol>\n<p><\/p>\n<p>Bin\u00e6re data<\/p>\n<p><strong>Var<\/strong><br \/>\n<code>01010101<\/code><\/p>\n<p><strong>Skrevet<\/strong><br \/>\n<code>00001111<\/code><\/p>\n<p><strong>Er blevet<\/strong><br \/>\n<code>00000101<\/code><\/p>\n<p><\/p>\n<p>Selv journalen repr\u00e6senterer en sekvens af poster af variabel l\u00e6ngde. Den typiske l\u00e6ngde for en post er cirka 30 bytes (selv om der nogle gange optr\u00e6der poster, der er flere kilobytes lange). <em>I dette tilf\u00e6lde arbejder vi med dem som et s\u00e6t bytes, men hvis det er interessant, bruges der CBOR indenfor posterne.<\/em><\/p>\n<p><\/p>\n<p>Udover loggen skal vi gemme nogle 'konfigurations'-oplysninger, b\u00e5de dem der opdateres, og dem der ikke g\u00f8r: en form for enhed ID, sensor kalibreringer, flag 'enhed midlertidigt deaktiveret', osv.<br \/>\nDisse oplysninger best\u00e5r af et s\u00e6t key-value poster, der ogs\u00e5 gemmes i CBOR. Vi har ikke meget af denne information (maksimalt et par kilobytes), og den opdateres ikke ofte.<br \/>\nFremover kalder vi det kontekst.<\/p>\n<p><\/p>\n<p>Hvis man husker, hvordan denne artikel begyndte, s\u00e5 er det meget vigtigt at sikre p\u00e5lidelig datalagring og om muligt uafbrudt drift, selv i tilf\u00e6lde af hardwarefejl\/dataskader.<\/p>\n<p><\/p>\n<p>Hvilke kilder til problemer kan man overveje?<\/p>\n<p><\/p>\n<ul>\n<li>Str\u00f8mafbrydelse under write\/erase operationer. Dette h\u00f8rer til 'mod svaghed er der ingen r\u00e5d'.<br \/>\nOplysninger fra <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\">diskussionen<\/a><\/noindex> p\u00e5 stackexchange: ved str\u00f8mafbrydelse under arbejde med flash sp\u00f8rgsm\u00e5lene om b\u00e5de erase (s\u00e6tte til 1), og write (s\u00e6tte til 0) f\u00f8rer til undefined behavior: data kan blive skrevet, skrevet delvist (lad os sige, at vi sendte 10 byte\/80 bits, men kun 45 bits blev skrevet), det er ogs\u00e5 muligt, at nogle bits kan v\u00e6re i en 'midlertidig' tilstand (l\u00e6se kan returnere b\u00e5de 0 og 1);<\/li>\n<li>Fejl i selve flash-hukommelsen.<br \/>\nBER er meget lav, men kan ikke v\u00e6re lig med nul;<\/li>\n<li>Fejl over bussen<br \/>\nData transmitted via SPI is not protected in any way, and single-bit errors or synchronization errors can easily occur\u2014loss or insertion of bits (which leads to significant data corruption);<\/li>\n<li>Other errors\/failures<br \/>\nFejl i koden, 'g\u00e6lder' Raspberry, indblanding fra rumv\u00e6sener\u2026<\/li>\n<\/ul>\n<p><\/p>\n<p>I formulated the requirements that, in my opinion, are necessary for ensuring reliability:<\/p>\n<p><\/p>\n<ul>\n<li>records must be written to flash memory immediately; deferred writing is not considered; - if an error occurs, it must be detected and handled as early as possible; - the system should restore operation after errors whenever possible.<br \/>\n<em>(et eksempel fra livet 'hvordan det ikke b\u00f8r v\u00e6re', som jeg tror, alle har m\u00f8dt: efter en katastrofal genstart blev filsystemet '\u00f8delagt' og operativsystemet starter ikke)<\/em><\/li>\n<\/ul>\n<p><\/p>\n<h2 id=\"idei-podhody-razmyshleniya\">Ideas, approaches, reflections<\/h2>\n<p><\/p>\n<p>When I started thinking about this task, a bunch of ideas flashed through my mind, for example:<\/p>\n<p><\/p>\n<ul>\n<li>using data compression;<\/li>\n<li>using clever data structures, for example, storing the headers of records separately from the records themselves, so that in case of an error in any record, the others can still be read without issues;<\/li>\n<li>using bit fields to control the completeness of the record during power loss;<\/li>\n<li>storing checksums for everything;<\/li>\n<li>using some kind of error-resistant coding.<\/li>\n<\/ul>\n<p><\/p>\n<p>Some of these ideas were used, while others were decided to be discarded. Let's go through them in order.<\/p>\n<p><\/p>\n<h3 id=\"szhatie-dannyh\">Data compression<\/h3>\n<p><\/p>\n<p>De begivenheder, vi registrerer i loggen, er temmelig ensartede og gentagne ('kastede en 5 kr. m\u00f8nt', 'trykkede p\u00e5 knappen for at f\u00e5 tilbageveksling', osv.). Derfor skal komprimering vise sig at v\u00e6re ret effektiv.<\/p>\n<p><\/p>\n<p>The overhead for compression is negligible (our processor is powerful enough, even the first Pi had a core with a frequency of 700 MHz, and the current models have several cores with frequencies over one gigahertz), the speed of communication with storage is low (a few megabytes per second), and the size of the records is small. Overall, if compression does affect performance, it will only be positively. <em>(not critical at all, just stating the fact)<\/em>. Plus, we don't have a real embedded system, but a regular Linux \u2014 so the implementation shouldn't require much effort (just link the library and use a few functions from it).<\/p>\n<p><\/p>\n<p>The log was taken from a working device (1.7MB, 70 thousand entries) and initially checked for compressibility using gzip, lz4, lzop, bzip2, xz, zstd available on the computer.<\/p>\n<p><\/p>\n<ul>\n<li>gzip, xz, zstd showed similar results (40KB).<br \/>\nIt was surprising that the trendy xz performed on par with gzip or zstd here;<\/li>\n<li>lzip with default settings gave slightly worse results;<\/li>\n<li>lz4 and lzop showed not very good results (150KB);<\/li>\n<li>bzip2 surprisingly yielded good results (18KB).<\/li>\n<\/ul>\n<p><\/p>\n<p>So, the data compresses very well.<br \/>\nTherefore, (if we don't find fatal flaws) compression will happen! Simply because more data can fit on the same flash drive.<\/p>\n<p><\/p>\n<p>Let's consider the disadvantages.<\/p>\n<p><\/p>\n<p>The first issue: we already agreed that each entry must be immediately written to the flash. Usually, compressors accumulate data from the input stream until they decide it's time to write to the output. We need to immediately get a compressed block of data and save it in non-volatile memory.<\/p>\n<p><\/p>\n<p>I see three paths:<\/p>\n<p><\/p>\n<ol>\n<li>Compress each entry using dictionary compression instead of the algorithms discussed above.<br \/>\nEn helt fungerende mulighed, men jeg kan ikke lide den. For at sikre et nogenlunde anst\u00e6ndigt kompressionsniveau skal ordbogen v\u00e6re 'tilpasset' specifikke data, enhver \u00e6ndring vil f\u00f8re til, at kompressionsniveauet falder katastrofalt. Ja, problemet kan l\u00f8ses ved at oprette en ny version af ordbogen, men det er en hovedpine \u2014 vi skal opbevare alle versioner af ordbogen; i hver post skal vi angive, hvilken version af ordbogen den er blevet komprimeret med\u2026<\/li>\n<li>At komprimere hver post med 'klassiske' algoritmer, men uafh\u00e6ngigt af andre.<br \/>\nThe compression algorithms being considered are not designed to work with entries of this size (dozens of bytes), the compression ratio will clearly be less than 1 (i.e., an increase in data volume instead of compression);<\/li>\n<li>Perform a FLUSH after each entry.<br \/>\nMany compression libraries support FLUSH. This is a command (or parameter to the compression procedure), upon receiving which the compressor generates a compressed stream so that it can restore <strong>alle<\/strong> the uncompressed data that has already been received. Such an analogy <code>synk<\/code> i filsystemer eller <code>commit<\/code> i sql.<br \/>\nVigtigt er, at efterf\u00f8lgende komprimeringsoperationer vil kunne bruge den akkumulerede ordbog, og komprimeringsgraden vil ikke lide s\u00e5 meget som i den tidligere version.<\/li>\n<\/ol>\n<p><\/p>\n<p>Det er \u00e5benlyst, at jeg har valgt den tredje mulighed, lad os se n\u00e6rmere p\u00e5 den.<\/p>\n<p><\/p>\n<p>Fundet <noindex><a rel=\"nofollow\" href=\"https:\/\/www.bolet.org\/~pornin\/deflate-flush.html\">fremragende artikel<\/a><\/noindex> om FLUSH i zlib.<\/p>\n<p><\/p>\n<p>Jeg lavede et testfors\u00f8g inspireret af en artikel, tog 70.000 poster fra en rigtig enhed med en sidest\u00f8rrelse p\u00e5 60Kb <em>(til sidest\u00f8rrelsen vender vi tilbage senere)<\/em> opn\u00e5ede:<\/p>\n<p><\/p>\n<p>Kildedata<br \/>\nGzip kompression -9 (uden FLUSH)<br \/>\nzlib med Z_PARTIAL_FLUSH<br \/>\nzlib med Z_SYNC_FLUSH<\/p>\n<p><strong>St\u00f8rrelse, Kb<\/strong><br \/>\n1692<br \/>\n40<br \/>\n352<br \/>\n604<\/p>\n<p><\/p>\n<p>Ved f\u00f8rste \u00f8jekast virker omkostningen ved FLUSH overdreven, men i virkeligheden har vi ikke meget valg - enten komprimere slet ikke, eller komprimere (og meget effektivt) med FLUSH. Man skal huske, at vi har 70.000 poster, overfl\u00f8digheden introduceret af Z_PARTIAL_FLUSH er kun 4-5 bytes pr. post. Og komprimeringsgraden viste sig at v\u00e6re n\u00e6sten 5:1, hvilket er mere end et fremragende resultat.<\/p>\n<p>\n<b class=\"spoiler_title\">Det kan virke overraskende, men faktisk er Z_SYNC_FLUSH \u2014 en mere effektiv m\u00e5de at g\u00f8re FLUSH p\u00e5<\/b><\/p>\n<p>I tilf\u00e6lde af brug af Z_SYNC_FLUSH vil de sidste 4 bytes af hver post altid v\u00e6re 0x00, 0x00, 0xff, 0xff. Og hvis vi kender dem - kan vi undlade at gemme dem, s\u00e5ledes at den endelige st\u00f8rrelse bliver kun 324Kb.<\/p>\n<p><\/p>\n<p>I artiklen, jeg refererer til, er der en forklaring:<\/p>\n<p><\/p>\n<blockquote><p>En ny type 0 blok med tomt indhold tilf\u00f8jes.<\/p>\n<p>En type 0 blok med tomt indhold best\u00e5r af:<\/p>\n<ul>\n<li>den tre-bit blokoverskrift;<\/li>\n<li>0 til 7 bits lig med nul for at opn\u00e5 bytejustering;<\/li>\n<li>den fire-byte sekvens 00 00 FF FF.<\/li>\n<\/ul>\n<p>\n<\/p><\/blockquote>\n<p>Som det er let at se, g\u00e5r der i den sidste blok f\u00f8r disse 4 bytes fra 3 til 10 nul-bits. Men praksis har vist, at der faktisk er mindst 10 nul-bits.<\/p>\n<p><\/p>\n<p>Det viser sig, at s\u00e5 korte datablokke normalt (eller altid?) kodes ved hj\u00e6lp af en blok type 1 (fast blok), som n\u00f8dvendigvis slutter med 7 nul-bits, s\u00e5 vi f\u00e5r 10-17 garanteret nul-bits (og de \u00f8vrige vil v\u00e6re nul med en sandsynlighed p\u00e5 omkring 50%).<\/p>\n<p><\/p>\n<p>S\u00e5 p\u00e5 testdata i 100% af tilf\u00e6ldene g\u00e5r der en nul-byte f\u00f8r 0x00, 0x00, 0xff, 0xff, og i mere end en tredjedel af tilf\u00e6ldene - to nul-bytes. <em>(m\u00e5ske skyldes det, at jeg bruger bin\u00e6r CBOR, og n\u00e5r jeg bruger tekstbaseret JSON ville jeg oftere m\u00f8de blokke type 2 - dynamisk blok, og derfor ville der v\u00e6re blokke uden ekstra nul-bytes f\u00f8r 0x00, 0x00, 0xff, 0xff)<\/em>.<\/p>\n<p><\/p>\n<p>I alt kan man p\u00e5 de eksisterende testdata komprimere til mindre end 250Kb med komprimerede data.<\/p>\n<p><\/p>\n<p>Man kan spare lidt mere ved at jonglere med bits: lige nu ignorerer vi tilstedev\u00e6relsen af flere nul-bits i slutningen af blokken, flere bits i starten af blokken \u00e6ndrer sig heller ikke...<br \/>\nMen her tog jeg en afg\u00f8rende beslutning om at stoppe, ellers kan jeg med dette tempo ende med at udvikle min egen arkiveringssoftware.<\/p>\n<p><\/p>\n<p>I alt fik jeg fra mine testdata 3-4 byte pr. skrivning, og komprimeringsforholdet endte med at v\u00e6re mere end 6:1. \u00c6rligt talt, jeg havde ikke forventet et s\u00e5 godt resultat; efter min mening er alt, hvad der er bedre end 2:1, allerede et resultat, der retf\u00e6rdigg\u00f8r brugen af komprimering.<\/p>\n<p><\/p>\n<p>Alt er perfekt, men zlib (deflate) er trods alt en gammel, velkendt og lidt gammeldags komprimeringsalgoritme. Bare det faktum, at de seneste 32KB af den ukomprimerede datastream bruges som ordbog, virker i dag m\u00e6rkeligt (dvs. hvis en datablok ligner noget fra indstr\u00f8mningen for 40KB siden, s\u00e5 vil den begynde at blive arkiveret forfra og ikke referere til tidligere indgange). I moderne komprimeringsv\u00e6rkt\u00f8jer m\u00e5les ordbogs st\u00f8rrelsen ofte i megabyte i stedet for kilobyte.<\/p>\n<p><\/p>\n<p>S\u00e5 lad os forts\u00e6tte med vores mini-unders\u00f8gelse af komprimeringsprogrammer.<\/p>\n<p><\/p>\n<p>Den n\u00e6ste, der blev testet, var bzip2 (jeg minder om, at uden FLUSH viste den en fantastisk grad af komprimering, n\u00e6sten 100:1). Desv\u00e6rre, med FLUSH viste den sig at v\u00e6re meget d\u00e5rlig, st\u00f8rrelsen p\u00e5 de komprimerede data endte med at v\u00e6re st\u00f8rre end de ukomprimerede.<\/p>\n<p>\n<b class=\"spoiler_title\">Mine formodninger om \u00e5rsagerne til fiaskoen<\/b><\/p>\n<p>Libbz2 tilbyder kun \u00e9n mulighed for flush, som tilsyneladende rydder ordbogen (analogt med Z_FULL_FLUSH i zlib); man kan ikke tale om effektiv komprimering efter dette.<\/p>\n<p><\/p>\n<p>Og den sidste, der blev testet, var zstd. Afh\u00e6ngigt af parametrene komprimerer den enten p\u00e5 niveau med gzip, men meget hurtigere, eller bedre end gzip.<\/p>\n<p><\/p>\n<p>Desv\u00e6rre har det ikke vist sig at v\u00e6re 's\u00e5 godt' med FLUSH: st\u00f8rrelsen p\u00e5 de komprimerede data var omkring 700 Kb.<\/p>\n<p><\/p>\n<p>Jeg <noindex><a rel=\"nofollow\" href=\"https:\/\/github.com\/facebook\/zstd\/issues\/900\">stillede et sp\u00f8rgsm\u00e5l<\/a><\/noindex> p\u00e5 projektets github-side, fik svaret, at man skal regne med op til 10 byte serviceoplysninger pr. blok af komprimerede data, hvilket er t\u00e6t p\u00e5 de opn\u00e5ede resultater; man kan ikke indhente deflate.<\/p>\n<p><\/p>\n<p>P\u00e5 dette besluttede jeg at stoppe eksperimenterne med komprimeringsprogrammer (jeg minder om, at xz, lzip, lzo og lz4 ikke viste sig at v\u00e6re effektive allerede i testfasen uden FLUSH, og jeg \u00f8nskede ikke at overveje mere eksotiske komprimeringsalgoritmer).<\/p>\n<p><\/p>\n<p>Lad os vende tilbage til problemerne med arkivering.<\/p>\n<p><\/p>\n<p>Det n\u00e6ste (som man siger i r\u00e6kkef\u00f8lge, ikke i betydning) problem er, at de komprimerede data repr\u00e6senterer et enkelt stream, hvor der konstant henvises til tidligere sektioner. Dermed, n\u00e5r en del af de komprimerede data skades, mister vi ikke kun de usammenh\u00e6ngende data, der er knyttet til den del, men ogs\u00e5 alle efterf\u00f8lgende.<\/p>\n<p><\/p>\n<p>Der er tilgange til at l\u00f8se dette problem:<\/p>\n<p><\/p>\n<ol>\n<li>At forhindre problemet i at opst\u00e5 \u2013 ved at tilf\u00f8je redundans til de komprimerede data, som muligg\u00f8r identifikation og rettelse af fejl; dette vil vi tale om senere;<\/li>\n<li>At minimere konsekvenserne, hvis problemet opst\u00e5r.<br \/>\nVi har tidligere n\u00e6vnt, at vi kan komprimere hver datablok uafh\u00e6ngigt, hvilket vil tage problemet ud af ligningen (beskadigelse af data i en blok vil kun resultere i tab af data i den blok). Men dette er et yderpunkt, hvor datakompression vil v\u00e6re ineffektiv. Den modsatte yderpunkt: at bruge de 4 MB af vores chip som et enkelt arkiv, hvilket vil give os fremragende kompression, men katastrofale konsekvenser i tilf\u00e6lde af dataskader.<br \/>\n<em>Ja, en kompromis kr\u00e6ves set fra et p\u00e5lidelighedssynspunkt. Men man m\u00e5 huske, at vi udvikler et dataopbevaringsformat til energifri hukommelse med ekstremt lav BER og en erkl\u00e6ret opbevaringsperiode p\u00e5 20 \u00e5r.<\/em><\/li>\n<\/ol>\n<p><\/p>\n<p>Under eksperimenter fandt jeg, at mere eller mindre m\u00e6rkbare tab i kompressionsniveauet begynder med komprimerede datablokke, der er mindre end 10 KB.<br \/>\nDet blev tidligere n\u00e6vnt, at den anvendte hukommelse har en sideorienteret organisation, jeg ser ingen grunde til, at man ikke skulle bruge '\u00e9n side \u2014 \u00e9n blok med komprimerede data'.<\/p>\n<p><\/p>\n<p>Det vil sige, at den mindste fornuftige sides st\u00f8rrelse er 16 KB (med lidt margen til administrationsinformation). Men en s\u00e5 lille sides st\u00f8rrelse l\u00e6gger betydelige begr\u00e6nsninger p\u00e5 den maksimale st\u00f8rrelsen af en post.<\/p>\n<p><\/p>\n<p>Selvom jeg endnu ikke forventer poster st\u00f8rre end et par kilobyte komprimeret, har jeg besluttet at bruge sider p\u00e5 st\u00f8rrelse med 32 KB (det giver 128 sider pr. chip).<\/p>\n<p><\/p>\n<p><strong>Resume:<\/strong><\/p>\n<p><\/p>\n<ul>\n<li>Data opbevares komprimeret med zlib (deflate);<\/li>\n<li>For hver post indstiller vi Z_SYNC_FLUSH;<\/li>\n<li>For hver komprimeret post besk\u00e6rer vi de afsluttende bytes <em>(for eksempel 0x00, 0x00, 0xff, 0xff)<\/em>; i headeren angiver vi, hvor mange bytes vi har besk\u00e5ret;<\/li>\n<li>Data opbevares i blokke af 32KB; inden for blokken er der en sammenh\u00e6ngende str\u00f8m af komprimerede data; komprimeringen genoptages fra starten af hver blok.<\/li>\n<\/ul>\n<p><\/p>\n<p>Og f\u00f8r vi afslutter komprimeringen, vil jeg gerne p\u00e5pege, at vi kun f\u00e5r et par byte komprimerede data pr. post, s\u00e5 det er ekstremt vigtigt ikke at opsvulme metadata, da hver byte t\u00e6ller.<\/p>\n<p><\/p>\n<h3 id=\"hranenie-zagolovkov-dannyh\">Opbevaring af dataoverskrifter<\/h3>\n<p><\/p>\n<p>Da vi har variable l\u00e6ngdeoptegnelser, skal vi finde en m\u00e5de at bestemme placeringen\/gr\u00e6nserne for optegnelserne.<\/p>\n<p><\/p>\n<p>Jeg kender tre tilgange:<\/p>\n<p><\/p>\n<ol>\n<li>Alle optegnelser opbevares i en kontinuerlig str\u00f8m, f\u00f8rst kommer optegnelsens header, der indeholder l\u00e6ngden, og derefter selve optegnelsen.<br \/>\nI denne variant kan b\u00e5de overskrifter og data have variabel l\u00e6ngde.<br \/>\nI realiteten f\u00e5r vi en enkelt linked list, der benyttes ofte;<\/li>\n<li>Overskrifterne og selve optegnelserne opbevares i separate str\u00f8mme.<br \/>\nVed at bruge faste l\u00e6ngdeoverskrifter sikrer vi, at beskadigelse af en header ikke p\u00e5virker de andre.<br \/>\nDenne tilgang anvendes eksempelvis i mange filsystemer;<\/li>\n<li>Optegnelserne opbevares i en kontinuerlig str\u00f8m, hvor gr\u00e6nsen for en optegnelse bestemmes af en bestemt mark\u00f8r (tegn\/tegnsekvens, der er forbudt inden for datablokke). Hvis en mark\u00f8r findes inden for en optegnelse, erstatter vi den med en bestemt sekvens (escaper den).<br \/>\nDenne tilgang anvendes eksempelvis i PPP-protokollen.<\/li>\n<\/ol>\n<p><\/p>\n<p>Jeg vil illustrere det.<\/p>\n<p><\/p>\n<p>Variant 1:<br \/>\n<img decoding=\"async\" alt=\"Min implementering af en ringbuffer i NOR flash\" src=\"\/wp-content\/uploads\/2019\/12\/e5a9676ca21eaca07e64ddf9fcd9f2eb.jpg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nHer er det meget enkelt: ved at kende l\u00e6ngden af optegnelsen kan vi beregne adressen til den n\u00e6ste header. P\u00e5 den m\u00e5de bev\u00e6ger vi os gennem overskrifterne, indtil vi m\u00f8der et omr\u00e5de fyldt med 0xff (frit omr\u00e5de) eller enden p\u00e5 blokken.<\/p>\n<p><\/p>\n<p>Variant 2:<br \/>\n<img decoding=\"async\" alt=\"Min implementering af en ringbuffer i NOR flash\" src=\"\/wp-content\/uploads\/2019\/12\/4fed4860fb659ab6042be9aeeb5c041a.jpg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nP\u00e5 grund af den variable l\u00e6ngde p\u00e5 posterne kan vi ikke p\u00e5 forh\u00e5nd sige, hvor mange poster (og dermed ogs\u00e5 overskrifter) vi f\u00e5r brug for p\u00e5 siden. Man kan sprede overskrifterne og dataene over forskellige sider, men jeg foretr\u00e6kker en anden tilgang: b\u00e5de overskrifterne og dataene placeres p\u00e5 \u00e9n side, men overskrifterne (af fast st\u00f8rrelse) kommer fra begyndelsen af siden, mens dataene (af variable l\u00e6ngde) kommer fra slutningen. S\u00e5 snart de 'm\u00f8des' (pladsen er ikke tilstr\u00e6kkelig til en ny post) betragter vi denne side som fyldt.<\/p>\n<p><\/p>\n<p>Variant 3:<br \/>\n<img decoding=\"async\" alt=\"Min implementering af en ringbuffer i NOR flash\" src=\"\/wp-content\/uploads\/2019\/12\/dfb64009aa7781fcb8a47423ff4160c6.jpg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nHer er der ikke behov for at gemme l\u00e6ngden eller anden information om dataplacering i headeren, det er tilstr\u00e6kkeligt med mark\u00f8rer, der angiver gr\u00e6nserne for posterne. Men dataene skal behandles ved skrivning\/l\u00e6sning.<br \/>\nSom mark\u00f8r ville jeg bruge 0xff (som siden er fyldt med efter sletning), s\u00e5 den frie plads vil helt klart ikke blive opfattet som data.<\/p>\n<p><\/p>\n<p>Sammenligningstabel:<\/p>\n<p><\/p>\n<p>Mulighed 1<br \/>\nMulighed 2<br \/>\nMulighed 3<\/p>\n<p><strong>Fejltolerance<\/strong><br \/>\n\u2014<br \/>\n+<br \/>\n+<\/p>\n<p><strong>Kompakthed<\/strong><br \/>\n+<br \/>\n\u2014<br \/>\n+<\/p>\n<p><strong>Implementeringskompleksitet<\/strong><br \/>\n*<br \/>\n**<br \/>\n**<\/p>\n<p><\/p>\n<p>Mulighed 1 har en fatal ulempe: hvis en af headerne beskadiges, vil hele den efterf\u00f8lgende k\u00e6de blive \u00f8delagt. De andre muligheder tillader at genoprette dele af dataene, selv ved omfattende skader.<br \/>\nMen det er v\u00e6rd at huske, at vi har besluttet at gemme data i komprimeret form, og da vi alligevel mister alle data p\u00e5 siden efter den '\u00f8delagte' post, tager vi ikke minusset i tabellen med i betragtning.<\/p>\n<p><\/p>\n<p>Kompakthed:<\/p>\n<p><\/p>\n<ul>\n<li>I den f\u00f8rste mulighed skal vi kun gemme l\u00e6ngden i headeren; hvis vi bruger variabel l\u00e6ngde, kan vi i de fleste tilf\u00e6lde klare os med \u00e9t byte;<\/li>\n<li>I den anden mulighed skal vi gemme startadressen og l\u00e6ngden; posten skal have en konstant st\u00f8rrelse, jeg vurderer det til 4 bytes pr. post (to bytes til offset og to bytes til l\u00e6ngde);<\/li>\n<li>Den tredje mulighed kr\u00e6ver kun \u00e9t tegn for at angive begyndelsen af posten, plus selve posten vil p\u00e5 grund af escaping vokse med 1-2%. Generelt er der omtrent paritet med den f\u00f8rste mulighed.<\/li>\n<\/ul>\n<p><\/p>\n<p>Oprindeligt betragtede jeg den anden mulighed som den prim\u00e6re (og skrev endda en implementering). Jeg droppede den kun, da jeg endeligt besluttede at bruge komprimering.<\/p>\n<p><\/p>\n<p><em>Muligvis vil jeg en dag bruge en s\u00e5dan l\u00f8sning. For eksempel hvis jeg skal h\u00e5ndtere lagring af data for et rumskib, der sejler mellem Jorden og Mars - der er helt andre krav til p\u00e5lidelighed, kosmisk str\u00e5ling, ...<\/em><\/p>\n<p><\/p>\n<p>Hvad ang\u00e5r den tredje mulighed: jeg gav den to stjerner for implementeringskompleksitet bare fordi jeg ikke kan lide at besk\u00e6ftige mig med escaping, \u00e6ndring af l\u00e6ngde undervejs osv. Ja, det er m\u00e5ske forudindtaget, men det er mig, der skal skrive koden - hvorfor tvinge mig selv til at lave noget, jeg ikke kan lide.<\/p>\n<p><\/p>\n<p><strong>Resume:<\/strong> Vi v\u00e6lger en lagermetode i form af k\u00e6der af 'overskrift med l\u00e6ngde - variable l\u00e6ngde data' p\u00e5 grund af effektivitet og enkel implementering.<\/p>\n<p><\/p>\n<h3 id=\"ispolzovanie-bitovyh-poley-dlya-kontrolya-uspeshnosti-operaciy-zapisi\">Brug af bitfelter til at kontrollere succesraten for skriveoperationer<\/h3>\n<p><\/p>\n<p>Jeg kan ikke huske, hvor jeg s\u00e5 id\u00e9en, men det ser omtrent s\u00e5dan ud:<br \/>\nFor hver opslag afs\u00e6tter vi nogle bits til lagring af flag.<br \/>\n<em>Som vi tidligere har n\u00e6vnt, efter erase er alle bits fyldt med 1, og vi kan \u00e6ndre 1 til 0, men ikke omvendt.<\/em> S\u00e5 for 'flag ikke sat' bruger vi 1, for 'flag sat' bruger vi 0.<\/p>\n<p><\/p>\n<p>S\u00e5dan kan placeringen af en variabel l\u00e6ngde post i flash se ud:<\/p>\n<p><\/p>\n<ol>\n<li>Vi s\u00e6tter flaget \"skrivning af l\u00e6ngde er startet\";<\/li>\n<li>Vi skriver l\u00e6ngden;<\/li>\n<li>Vi s\u00e6tter flaget \"skrivning af data er startet\";<\/li>\n<li>Vi skriver data;<\/li>\n<li>Vi s\u00e6tter flaget \"skrivning er afsluttet\".<\/li>\n<\/ol>\n<p><\/p>\n<p>Derudover har vi et flag \"der opstod en fejl\", i alt 4 bitflag.<\/p>\n<p><\/p>\n<p>I dette tilf\u00e6lde har vi to stabile tilstande \"1111\" - skrivningen er ikke startet, og \"1000\" - skrivningen er lykkedes; ved en uventet afbrydelse af skriveprocessen f\u00e5r vi mellemtilstande, som vi senere kan opdage og h\u00e5ndtere.<\/p>\n<p><\/p>\n<p>Tilgangen er interessant, men den beskytter kun mod pludselig str\u00f8mafbrydelse og lignende fejl, hvilket selvf\u00f8lgelig er vigtigt, men det er langt fra den eneste (og endda ikke den prim\u00e6re) \u00e5rsag til mulige fejl.<\/p>\n<p><\/p>\n<p><strong>Resume:<\/strong> Lad os forts\u00e6tte med at lede efter en god l\u00f8sning.<\/p>\n<p><\/p>\n<h3 id=\"kontrolnye-summy\">Kontrolsummer<\/h3>\n<p><\/p>\n<p>Kontrolsummer giver os ogs\u00e5 mulighed for at v\u00e6re sikre (med tilstr\u00e6kkelig sandsynlighed) for, at vi l\u00e6ser akkurat det, der skulle v\u00e6re skrevet. Og i mods\u00e6tning til de bitfelter, vi har gennemg\u00e5et ovenfor, fungerer de altid.<\/p>\n<p><\/p>\n<p>Hvis vi overvejer listen over potentielle kilder til problemer, som vi n\u00e6vnte ovenfor, kan kontrolsummen identificere fejl uanset deres oprindelse <em>(med undtagelse af m\u00e5ske ondskabsfulde rumv\u00e6sener - de kan ogs\u00e5 forfalske kontrolsummen)<\/em>.<\/p>\n<p><\/p>\n<p>S\u00e5 hvis vores m\u00e5l er at kontrollere, at dataene er intakte, er kontrolsummer en fremragende id\u00e9.<\/p>\n<p><\/p>\n<p>Valget af algoritme til beregning af kontrolsummen gav ikke anledning til sp\u00f8rgsm\u00e5l - CRC. P\u00e5 den ene side g\u00f8r de matematiske egenskaber det muligt at fange 100% af fejl af visse typer, og p\u00e5 den anden side viser denne algoritme normalt en sandsynlighed for kollisioner, der ikke er meget st\u00f8rre end den teoretiske gr\u00e6nse p\u00e5 tilf\u00e6ldige data. <img decoding=\"async\" alt=\"Min implementering af en ringbuffer i NOR flash\" src=\"\/wp-content\/uploads\/2019\/12\/bf9cca3564db7d9d03d3ce49642d3a71.jpg\" style=\"display:block;margin: 0 auto;\" \/>Selvom det ikke er den hurtigste algoritme, og ikke altid den mest optimale med hensyn til antallet af kollisioner, har den en meget vigtig egenskab: i de tests, jeg har m\u00f8dt, har der ikke v\u00e6ret nogen m\u00f8nstre, hvor den \u00e5benlyst svigtede. Stabilitet er den vigtigste kvalitet i dette tilf\u00e6lde.<\/p>\n<p><\/p>\n<p>Eksempel p\u00e5 en omfattende unders\u00f8gelse: <noindex><a rel=\"nofollow\" href=\"http:\/\/amsoftware.narod.ru\/algo.html\">del 1<\/a><\/noindex>, <noindex><a rel=\"nofollow\" href=\"http:\/\/amsoftware.narod.ru\/algo2.html\">del 2<\/a><\/noindex> <em>(links til narod.ru, undskyld)<\/em>.<\/p>\n<p><\/p>\n<p>Men opgaven med at v\u00e6lge en kontrolsum er ikke afsluttet, CRC er en hel familie af checksums. Vi skal beslutte l\u00e6ngden, og derefter v\u00e6lge polynomiet.<\/p>\n<p><\/p>\n<p>Valget af l\u00e6ngden p\u00e5 checksummen er ikke et s\u00e5 enkelt sp\u00f8rgsm\u00e5l, som det kan synes ved f\u00f8rste \u00f8jekast.<\/p>\n<p><\/p>\n<p>Jeg vil illustrere:<br \/>\nLad os antage, at sandsynligheden for fejl i hver byte <img decoding=\"async\" alt=\"Min implementering af en ringbuffer i NOR flash\" src=\"\/wp-content\/uploads\/2019\/12\/89a9be2edf2a43cc9115eba37fa02fc8.jpg\" style=\"display:block;margin: 0 auto;\" \/> og den ideelle kontrolsum, lad os beregne det gennemsnitlige antal fejl pr. million poster:<\/p>\n<p><\/p>\n<p>Data, byte<br \/>\nKontrolsum, byte<br \/>\nUopdagede fejl<br \/>\nFalske positive fejl<br \/>\nI alt forkerte aktiveringer<\/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>Det virker simpelt \u2014 v\u00e6lg l\u00e6ngden p\u00e5 checksummen afh\u00e6ngigt af l\u00e6ngden af de beskyttede data med mindst mulige falske aktiveringer \u2014 og det er klaret.<\/p>\n<p><\/p>\n<p>Men med korte checksums opst\u00e5r der et problem: selvom de godt opdager enkelte bitfejl, kan de med en ret h\u00f8j sandsynlighed acceptere helt tilf\u00e6ldige data som gyldige. Der har allerede v\u00e6ret en artikel p\u00e5 Habr, der beskrev <noindex><a rel=\"nofollow\" href=\"https:\/\/habr.com\/ru\/post\/428746\/\">problemet i det virkelige liv<\/a><\/noindex>.<\/p>\n<p><\/p>\n<p>Derfor, for at g\u00f8re tilf\u00e6ldige matches af checksummen praktisk talt umulige, skal man bruge checksums med l\u00e6ngde p\u00e5 32 bit eller mere <em>(til l\u00e6ngder over 64 bit bruger man normalt kryptografiske hash-funktioner)<\/em>.<\/p>\n<p><\/p>\n<p>P\u00e5 trods af at jeg tidligere har skrevet, at man skal spare plads med alle midler, vil vi alligevel bruge en 32-bit kontrolsum (16 bit er for lidt, kollisionssandsynligheden er over 0,01%; og 24 bit, som man siger, er hverken her eller der).<\/p>\n<p><\/p>\n<p>Her kan der opst\u00e5 et indvending: har vi ikke sparet hver byte ved kompression for senere at give 4 byte v\u00e6k? Var det ikke bedre ikke at komprimere og ikke tilf\u00f8je en kontrolsum? Selvf\u00f8lgelig ikke, mangel p\u00e5 kompression <em>betyder ikke<\/em>, at integritetskontrol ikke er n\u00f8dvendig.<\/p>\n<p><\/p>\n<p>Vi vil ikke opfinde cyklen p\u00e5 valget af polynomiet, men tage den popul\u00e6re CRC-32C.<br \/>\nDenne kode opdager 6 bitfejl i pakker op til 22 byte (sandsynligvis den mest almindelige situation for os), 4 bitfejl i pakker op til 655 byte (ogs\u00e5 en hyppig situation for os), 2 eller et hvilket som helst ulige antal bitfejl i pakker af enhver rimelig l\u00e6ngde.<\/p>\n<p>\n<b class=\"spoiler_title\">Hvis nogen er interesseret i detaljerne<\/b><\/p>\n<p><noindex><a rel=\"nofollow\" href=\"https:\/\/en.wikipedia.org\/wiki\/Cyclic_redundancy_check\">Wikipediainfo<\/a><\/noindex> om CRC.<\/p>\n<p><\/p>\n<p><noindex><a rel=\"nofollow\" href=\"https:\/\/users.ece.cmu.edu\/~koopman\/crc\/c32\/0x8f6e37a0_len.txt\">Parametre for crc-32c koden<\/a><\/noindex> og f\u00e5 en fungerende kommando. <noindex><a rel=\"nofollow\" href=\"http:\/\/users.ece.cmu.edu\/~koopman\/crc\/notes.html\">Kaufmans websted<\/a><\/noindex> \u2014 sandsynligvis den f\u00f8rende ekspert i verden inden for CRC.<\/p>\n<p><\/p>\n<p>I <noindex><a rel=\"nofollow\" href=\"http:\/\/users.ece.cmu.edu\/~koopman\/networks\/dsn02\/dsn02_koopman.pdf\">i hans artikel<\/a><\/noindex> er <noindex><a rel=\"nofollow\" href=\"https:\/\/users.ece.cmu.edu\/~koopman\/crc\/c32\/0xfa567d89_len.txt\">endnu en interessant kode<\/a><\/noindex>, som giver lidt bedre parametre for de pakker, der er relevante for os, men jeg fandt ikke forskellen v\u00e6sentlig og f\u00f8ler mig kompetent nok til at v\u00e6lge en brugerdefineret kode frem for den standard og godt unders\u00f8gte.<\/p>\n<p><\/p>\n<p>Derudover, da vi har komprimerede data, opst\u00e5r sp\u00f8rgsmaalet: skal vi beregne summen af kontrolekserne for de komprimerede eller ukomprimerede data?<\/p>\n<p><\/p>\n<p>Argumenter 'for' beregning af kontrolsum for ukomprimerede data:<\/p>\n<p><\/p>\n<ul>\n<li>vi skal i sidste ende kontrollere, at dataene er bevaret \u2014 her kontrollerer vi det direkte (samtidig vil eventuelle fejl i implementationen af komprimering\/afkomprimering, fejl for\u00e5rsaget af beskadiget hukommelse osv. ogs\u00e5 blive kontrolleret);<\/li>\n<li>deflate-algoritmen i zlib har en tilstr\u00e6kkelig moden implementering og <em>b\u00f8r ikke<\/em> Faldende ved 'sk\u00e6ve' inputdata, desuden er den ofte i stand til selv at opdage fejl i inputstr\u00f8mmen, hvilket reducerer den samlede sandsynlighed for uopdagede fejl (jeg har udf\u00f8rt en test med inversion af en enkelt bit i en kort post, zlib opdagede fejlen i ca. en tredjedel af tilf\u00e6ldene).<\/li>\n<\/ul>\n<p><\/p>\n<p>Argumenter 'imod' beregning af kontrolsum for ukomprimerede data:<\/p>\n<p><\/p>\n<ul>\n<li>CRC er 'skabt' netop til f\u00e5 bitfejl, som er typiske for flashhukommelse (en bitfejl i en komprimeret str\u00f8m kan f\u00f8re til en massiv \u00e6ndring af outputstr\u00f8mmen, som vi teoretisk set kan 'fange' en kollision p\u00e5);<\/li>\n<li>jeg kan ikke lide tanken om at overf\u00f8re potentielt beskadigede data til dekompressoren, <noindex><a rel=\"nofollow\" href=\"https:\/\/www.cvedetails.com\/vulnerability-list\/vendor_id-72\/product_id-1820\/GNU-Zlib.html\">hvem ved<\/a><\/noindex>, hvordan den vil reagere.<\/li>\n<\/ul>\n<p><\/p>\n<p>I dette projekt besluttede jeg at afvige fra den almindelige praksis med at gemme summen af kontrolekserne for de ukomprimerede data.<\/p>\n<p><\/p>\n<p><strong>Resume:<\/strong> vi bruger CRC-32C, og vi beregner summen af kontrolekserne baseret p\u00e5 dataene i den form, de er gemt i flash (efter komprimering).<\/p>\n<p><\/p>\n<h3 id=\"izbytochnost\">Overfl\u00f8dighed<\/h3>\n<p><\/p>\n<p>Brugen af redundante kodninger udelukker selvf\u00f8lgelig ikke datatab, men det kan v\u00e6sentligt (ofte med mange r\u00e6kkefordele) reducere sandsynligheden for uopretteligt datatab.<\/p>\n<p><\/p>\n<p>Vi kan anvende forskellige former for redundans for at korrigere fejl.<br \/>\nHamming-koder kan rette enlige bitfejl, Reed-Solomon-koder kan h\u00e5ndtere tegnfejl, mens flere kopier af data sammen med kontrolsummer eller kodning som RAID-6 kan hj\u00e6lpe med at genskabe data selv ved massefejl.<br \/>\nOprindeligt var jeg indstillet p\u00e5 at bruge meget fejltolerant kodning, men jeg inds\u00e5, at man f\u00f8rst skal have en forst\u00e5else af, hvilke fejl man \u00f8nsker at beskytte sig imod, f\u00f8r man v\u00e6lger kodningen.<\/p>\n<p><\/p>\n<p>Vi har tidligere talt om, at fejl skal opdages s\u00e5 hurtigt som muligt. Hvorn\u00e5r kan vi st\u00f8de p\u00e5 fejl?<\/p>\n<p><\/p>\n<ol>\n<li>Ufuldst\u00e6ndig post (af forskellige grunde blev str\u00f8mmen afbrudt under skrivningen, Raspberry hang, ...)<br \/>\nDesv\u00e6rre er der kun mulighed for at ignorere ugyldige registreringer og betragte data som tabt i tilf\u00e6lde af en s\u00e5dan fejl;<\/li>\n<li>Skrivefejl (af forskellige grunde blev der skrevet noget andet til flash-hukommelsen end det, der skulle skrives)<br \/>\nS\u00e5danne fejl kan vi straks opdage, hvis vi laver en kontrolafl\u00e6sning umiddelbart efter skrivning;<\/li>\n<li>Forvr\u00e6ngning af data i hukommelsen under opbevaring;<\/li>\n<li>L\u00e6sefejl<br \/>\nFor at rette det er det tilstr\u00e6kkeligt at gentage afl\u00e6sningen flere gange, hvis kontrolsummen ikke stemmer overens.<\/li>\n<\/ol>\n<p><\/p>\n<p>Det vil sige, at kun fejl af den tredje type (spontan datakorruption under opbevaring) ikke kan rettes uden fejltolerant kodning. Man m\u00e5 antage, at s\u00e5danne fejl er yderst usandsynlige.<\/p>\n<p><\/p>\n<p><strong>Resume:<\/strong> Det blev besluttet at opgive redundante kodninger, men hvis driften viser, at denne beslutning er fejlagtig, vil man overveje sp\u00f8rgsm\u00e5let igen (med allerede opsamlede statistikker om svigt, som vil muligg\u00f8re valg af den mest optimale kodning).<\/p>\n<p><\/p>\n<h3 id=\"prochee\">Andet<\/h3>\n<p><\/p>\n<p>Naturligvis tillader artikelens format ikke at begrunde hver bit i formatet <em>(og jeg er ogs\u00e5 blevet tr\u00e6t)<\/em>, derfor vil jeg kort skitsere nogle punkter, der ikke er blevet ber\u00f8rt tidligere.<\/p>\n<p><\/p>\n<ul>\n<li>Det blev besluttet at g\u00f8re alle sider 'ligev\u00e6rdige'<br \/>\nDet vil sige, at der ikke vil v\u00e6re nogle specielle sider med metadata, separate str\u00f8mme osv., men i stedet en enkelt str\u00f8m, der skriver alle sider sekventielt.<br \/>\nDette sikrer en j\u00e6vn slid p\u00e5 siderne, frav\u00e6ret af et enkelt fejlpunkts og passer bare til mig;<\/li>\n<li>Der skal n\u00f8dvendigvis tages h\u00f8jde for versionering af formatet.<br \/>\nEt format uden versionsnummer i overskriften er ondsindet!<br \/>\nDet er tilstr\u00e6kkeligt at tilf\u00f8je et felt med et eller andet Magic Number (signatur) i sidens overskrift, som vil angive den anvendte version af formatet. <em>(Jeg tror ikke, at der i praksis vil v\u00e6re mere end ti af dem.)<\/em>;<\/li>\n<li>Brug en variabel l\u00e6ngdeoverskrift til posterne (hvilket der er rigtig mange af), og pr\u00f8v for de fleste tilf\u00e6lde at g\u00f8re den \u00e9n byte lang.<\/li>\n<li>Til kodning af l\u00e6ngden p\u00e5 overskriften og l\u00e6ngden af den besk\u00e5rne del af den komprimerede post skal der anvendes variable l\u00e6ngdekoder.<\/li>\n<\/ul>\n<p><\/p>\n<p>Det hjalp meget <noindex><a rel=\"nofollow\" href=\"https:\/\/planetcalc.com\/2481\/\">online generator<\/a><\/noindex> af Huffman-koder. Jeg kunne bogstaveligt talt finde de n\u00f8dvendige variable l\u00e6ngdekoder p\u00e5 f\u00e5 minutter.<\/p>\n<p><\/p>\n<h1 id=\"anchorformatanchoropisanie-formata-hraneniya-dannyh\"><noindex><a rel=\"nofollow\" name=\"format\"><\/a><\/noindex>Beskrivelse af dataopbevaringsformatet.<\/h1>\n<p><\/p>\n<h2 id=\"byte-order\">Byteordens<\/h2>\n<p><\/p>\n<p>Felter, der overstiger \u00e9n bytes st\u00f8rrelse, gemmes i big-endian-format (netv\u00e6rks byteordens), det vil sige 0x1234 skrives som 0x12, 0x34.<\/p>\n<p><\/p>\n<h2 id=\"delenie-na-stranicy\">Opdeling i sider<\/h2>\n<p><\/p>\n<p>Hele flashhukommelsen er opdelt i sider af ens st\u00f8rrelse.<\/p>\n<p><\/p>\n<p>Standardst\u00f8rrelsen p\u00e5 en side er 32 KB, men ikke mere end 1\/4 af den samlede st\u00f8rrelse p\u00e5 hukommelseschippen (for en chip p\u00e5 4 MB bliver det 128 sider).<\/p>\n<p><\/p>\n<p>Hver side gemmer data uafh\u00e6ngigt af andre (det vil sige data fra \u00e9n side henviser ikke til data fra en anden side).<\/p>\n<p><\/p>\n<p>Alle sider er nummereret i naturlig r\u00e6kkef\u00f8lge (i stigende adresseorden), begyndende med nummer 0 (den null\u00e6ssige side begynder ved adresse 0, den f\u00f8rste ved 32 KB, den anden ved 64 KB osv.).<\/p>\n<p><\/p>\n<p>Hukommelseschipsen bruges som en cirkul\u00e6r buffer, hvilket betyder, at optagelserne f\u00f8rst gemmes p\u00e5 side nummer 0, derefter p\u00e5 nummer 1, &#8230;, n\u00e5r vi fylder den sidste side, starter vi forfra, og optagelsen forts\u00e6tter fra nul-siden.<\/p>\n<p><\/p>\n<h2 id=\"vnutri-stranicy\">Inde i siden<\/h2>\n<p><\/p>\n<p><img decoding=\"async\" alt=\"Min implementering af en ringbuffer i NOR flash\" src=\"\/wp-content\/uploads\/2019\/12\/39b45f83dc46bb2fd7081ed2a0b638c9.jpg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nI starten af siden gemmes en 4-byte overskrift, derefter en kontrolsum for overskriften (CRC-32C), og derefter gemmes posterne i formatet &#171;overskrift, data, kontrolsum&#187;.<\/p>\n<p><\/p>\n<p>Sideoverskriften (i diagrammet er den smaragdgr\u00f8n) best\u00e5r af:<\/p>\n<p><\/p>\n<ul>\n<li>et to-byte Magic Number felt (det er ogs\u00e5 - en indikator for formatversionen)<br \/>\nfor den nuv\u00e6rende version af formatet betragtes det som <code>0xed00 \u2295 side nummer<\/code>;<\/li>\n<li>en to-byte t\u00e6ller &#171;Versionsnummer for siden&#187; (antal cykler for omskrivning af hukommelsen).<\/li>\n<\/ul>\n<p><\/p>\n<p>Poster p\u00e5 siden gemmes i komprimeret form (deflate-algoritmen anvendes). Alle poster p\u00e5 \u00e9n side komprimeres i \u00e9n str\u00f8m (en f\u00e6lles ordbog bruges), og komprimeringen starter p\u00e5 ny p\u00e5 hver ny side. Det betyder, at alle tidligere poster fra denne side kr\u00e6ves for at dekomprimere enhver post (og kun fra denne).<\/p>\n<p><\/p>\n<p>Hver post komprimeres med flaget Z_SYNC_FLUSH, hvilket betyder, at der i slutningen af den komprimerede str\u00f8m er 4 bytes 0x00, 0x00, 0xff, 0xff, som eventuelt kan v\u00e6re forudg\u00e5et af en eller to null-bits.<br \/>\nDenne sekvens (4, 5 eller 6 bytes lang) kasseres, n\u00e5r der skrives til flashhukommelsen.<\/p>\n<p><\/p>\n<p>Headeren for posten best\u00e5r af 1, 2 eller 3 bytes, som indeholder:<\/p>\n<p><\/p>\n<ul>\n<li>et bit (T), der betyder posttypen: 0 \u2014 kontekst, 1 \u2014 log;<\/li>\n<li>et felt af variabel l\u00e6ngde (S) fra 1 til 7 bit, der angiver l\u00e6ngden af overskriften og &#171;halen&#187;, der skal tilf\u00f8jes til posten for dekomprimering;<\/li>\n<li>l\u00e6ngden af posten (L).<\/li>\n<\/ul>\n<p><\/p>\n<p>V\u00e6rdi tabel S:<\/p>\n<p><\/p>\n<p>Angreb op til 1,2<br \/>\nHeaderens l\u00e6ngde, bytes<br \/>\nKasseres ved skrivning, 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>Fors\u00f8gte at illustrere, ved ikke, hvor klart det er:<br \/>\n<img decoding=\"async\" alt=\"Min implementering af en ringbuffer i NOR flash\" src=\"\/wp-content\/uploads\/2019\/12\/8c9b739eec5af4429395c32b4ba4044a.jpg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nGul markerer feltet T, hvid markerer feltet S, gr\u00f8n markerer L (l\u00e6ngden af de komprimerede data i bytes), bl\u00e5 markerer de komprimerede data, r\u00f8d markerer de afsluttende bytes af de komprimerede data, som ikke skrives til flashhukommelsen.<\/p>\n<p><\/p>\n<p>S\u00e5ledes kan vi gemme headeren for de mest almindelige l\u00e6ngder (op til 63+5 bytes i komprimeret form) med \u00e9n byte.<\/p>\n<p><\/p>\n<p>Efter hver post opbevares en CRC-32C kontrolsum, hvor det initiale v\u00e6rdien (init) bruges som den inverterede v\u00e6rdi af den forrige kontrolsum.<\/p>\n<p><\/p>\n<p><em>CRC har egenskaben &#171;vedholdenhed&#187;, hendes formel fungerer (plus-minus invertering af bits i processen): <img decoding=\"async\" alt=\"Min implementering af en ringbuffer i NOR flash\" src=\"\/wp-content\/uploads\/2019\/12\/b194d6a3d18ae2f4ae5d4054a93c0ea3.jpg\" style=\"display:block;margin: 0 auto;\" \/>.<br \/>\nDet vil sige, at vi faktiske beregner CRC for alle tidligere bytes af headerne og dataene p\u00e5 denne side.<\/em><\/p>\n<p><\/p>\n<p>Lige efter kontrolsummen ligger headeren for den n\u00e6ste post.<\/p>\n<p><\/p>\n<p>Headeren er konstrueret s\u00e5dan, at den f\u00f8rste byte altid er forskellig fra 0x00 og 0xff (hvis vi m\u00f8der 0xff i stedet for den f\u00f8rste byte af headeren, betyder det, at det er et ubenyttet omr\u00e5de; 0x00 indikerer en fejl).<\/p>\n<p><\/p>\n<h2 id=\"primernye-algoritmy\">Eksempler p\u00e5 algoritmer<\/h2>\n<p><\/p>\n<h3 id=\"chtenie-iz-flesh-pamyati\">L\u00e6sning fra flashhukommelsen<\/h3>\n<p><\/p>\n<p>Enhver l\u00e6sning sker med kontrolsum verificering.<br \/>\nHvis kontrolsummen ikke stemmer overens, gentages l\u00e6sningen flere gange i h\u00e5bet om at l\u00e6se de korrekte data.<\/p>\n<p><\/p>\n<p><em>(det giver mening, Linux cacher ikke l\u00e6sning fra NOR Flash, bekr\u00e6ftet)<\/em><\/p>\n<p><\/p>\n<h3 id=\"zapis-v-flesh-pamyat\">Skrivning til flashhukommelse<\/h3>\n<p><\/p>\n<p>Vi skriver data.<br \/>\nVi l\u00e6ser dem.<\/p>\n<p><\/p>\n<p>Hvis de l\u00e6ste data ikke matcher de skrevne, fylder vi omr\u00e5det med nuller og signalerer en fejl.<\/p>\n<p><\/p>\n<h3 id=\"podgotovka-novoy-mikroshemy-k-rabote\">Forberedelse af den nye chip til brug<\/h3>\n<p><\/p>\n<p>Til initialisering skrives en header med version 1 til den f\u00f8rste (mere pr\u00e6cist, nulte) side.<br \/>\nDerefter skrives den indledende kontekst (indeholder UUID for enheden og standardindstillinger) til denne side. <\/p>\n<p><\/p>\n<p>Alt er klar, flashhukommelsen er klar til brug.<\/p>\n<p><\/p>\n<h3 id=\"zagruzka-avtomata\">Indl\u00e6sning af enheden<\/h3>\n<p><\/p>\n<p>Under indl\u00e6sning l\u00e6ses de f\u00f8rste 8 bytes af hver side (header + CRC), sider med ukendt Magic Number eller ukorrekt CRC ignoreres.<br \/>\nFra &#171;korrekte&#187; sider v\u00e6lges de sider med den h\u00f8jeste version, fra disse tages den side med det h\u00f8jeste nummer.<br \/>\nDen f\u00f8rste post l\u00e6ses, CRC-korrekthed tjekkes, samt tilstedev\u00e6relsen af &#171;kontext&#187; flaget. Hvis alt er i orden, betragtes denne side som aktuel. Hvis ikke, ruller vi tilbage til den foreg\u00e5ende, indtil vi finder en &#171;levende&#187; side.<br \/>\nfra den fundne side l\u00e6ser vi alle poster, og dem med &#171;kontext&#187; flaget anvendes.<br \/>\nVi gemmer zlib-ordbog (den vil v\u00e6re n\u00f8dvendig for genopskrivning til denne side).<\/p>\n<p><\/p>\n<p>Alt er godt, indl\u00e6sningen er afsluttet, konteksten er genskabt, nu kan vi arbejde.<\/p>\n<p><\/p>\n<h3 id=\"dobavlenie-zapisi-v-zhurnal\">Tilf\u00f8jelse af en post til loggen<\/h3>\n<p><\/p>\n<p>Vi komprimerer posten med den korrekte ordbog, angiver Z_SYNC_FLUSH. Vi ser, om den komprimerede post kan placeres p\u00e5 den nuv\u00e6rende side.<br \/>\nHvis den ikke kan placeres (eller der var CRC-fejl p\u00e5 siden) - starter vi en ny side (se nedenfor).<br \/>\nVi skriver posten og CRC. Hvis der opstod en fejl - starter vi en ny side.<\/p>\n<p><\/p>\n<h3 id=\"novaya-stranica\">Ny side<\/h3>\n<p><\/p>\n<p>Vi v\u00e6lger en ledig side med det laveste nummer (vi betragter en side som ledig, hvis der er en forkert kontrolsum i headeren eller en version mindre end den aktuelle). Hvis der ikke er s\u00e5danne sider, v\u00e6lger vi en side med det laveste nummer med en version, der er lig med den aktuelle.<br \/>\nVi s\u00e6tter den valgte side til at blive slettet. Vi sammenligner indholdet med 0xff. Hvis der er noget galt, tager vi den n\u00e6ste ledige side osv.<br \/>\nTil den slettede side skriver vi headeren, som den f\u00f8rste post, den aktuelle tilstand af konteksten, den n\u00e6ste - ikke skrevne post fra loggen (hvis der er en).<\/p>\n<p><\/p>\n<h1 id=\"primenimost-formata\">Anvendelighed af formatet<\/h1>\n<p><\/p>\n<p>Efter min mening er dette en god format til opbevaring af enhver n\u00e6vnev\u00e6rdig komprimerbar informationsstr\u00f8m (enkelt tekst, JSON, MessagePack, CBOR, muligvis protobuf) i NOR Flash.<\/p>\n<p><\/p>\n<p>Selvf\u00f8lgelig er formatet &#171;tilpasset&#187; til SLC NOR Flash.<\/p>\n<p><\/p>\n<p>Det skal ikke bruges med medier med h\u00f8j BER, som NAND eller MLC NOR. <em>(er s\u00e5dan hukommelse overhovedet til salg? Jeg har kun set omtale af det i artikler om fejlkorrektioner.)<\/em>.<\/p>\n<p><\/p>\n<p>Endda b\u00f8r det ikke bruges med enheder, der har deres egen FTL: USB flash, SD, MicroSD osv. <em>(for s\u00e5dan hukommelse lavede jeg et format med en side st\u00f8rrelse p\u00e5 512 byte, en signatur i starten af hver side og unikke poster id'er \u2014 nogle gange kunne jeg, med simpelt sekventiel l\u00e6sning, genoprette alle data fra en &#171;fejll\u00e6st&#187; USB-stik)<\/em>.<\/p>\n<p><\/p>\n<p>Afh\u00e6ngigt af opgaverne kan formatet bruges u\u00e6ndret p\u00e5 flash-drev fra 128 Kbit (16 Kb) til 1 Gbit (128 Mb). Hvis \u00f8nskes, kan det ogs\u00e5 bruges p\u00e5 chips med st\u00f8rre kapacitet, men det skal nok tilpasses sidest\u00f8rrelsen. <em>(Men her opst\u00e5r sp\u00f8rgsm\u00e5let om \u00f8konomisk rentabilitet, prisen p\u00e5 h\u00f8jkapacitets NOR Flash er ikke tilfredsstillende.)<\/em>.<\/p>\n<p><\/p>\n<p>Hvis nogen har fundet formatet interessant og \u00f8nsker at bruge det i et \u00e5bent projekt \u2014 skriv, s\u00e5 vil jeg pr\u00f8ve at finde tid til at forbedre koden og uploade den til GitHub.<\/p>\n<p><\/p>\n<h1 id=\"zaklyuchenie\">Konklusion<\/h1>\n<p><\/p>\n<p>Som vi kan se, viste formatet sig at v\u00e6re enkelt. <em>og endda kedeligt.<\/em>.<\/p>\n<p><\/p>\n<p>I artiklen er det sv\u00e6rt at skildre evolutionen af min mening, men tro mig: i starten ville jeg skabe noget avanceret, n\u00e6sten ubrydeligt, i stand til at overleve selv efter en atomexplosion i n\u00e6rheden. Men fornuften (forh\u00e5bentlig) sejrede, og prioriteterne skiftede gradvist mod enkelhed og kompakthed.<\/p>\n<p><\/p>\n<p>Kan det v\u00e6re, at jeg tog fejl? Ja, selvf\u00f8lgelig. Det kan meget vel vise sig, for eksempel, at vi har k\u00f8bt en batch af defekte chips. Eller af en eller anden grund, at udstyret ikke vil leve op til forventningerne om p\u00e5lidelighed.<\/p>\n<p><\/p>\n<p>Har jeg en plan for dette tilf\u00e6lde? Jeg tror, at efter at have l\u00e6st artiklen, vil du ikke tvivle p\u00e5, at der er en plan. Og ikke bare \u00e9n.<\/p>\n<p><\/p>\n<p>Hvis vi skal v\u00e6re lidt mere alvorlige, er formatet udviklet b\u00e5de som en arbejdsversion og som en &#171;pr\u00f8ve&#187;.<\/p>\n<p><\/p>\n<p>I \u00f8jeblikket fungerer alt fint p\u00e5 bordet, l\u00f8sningen vil snart blive implementeret. <em>(cirka)<\/em> p\u00e5 hundrede enheder, lad os se, hvad der sker i &#171;kamp&#187; drift (heldigvis h\u00e5ber jeg, at formatet kan registrere fejl p\u00e5lideligt; s\u00e5 vi kan samle fuld statistik). Efter et par m\u00e5neder vil der kunne drages konklusioner. <em>(og hvis uheldet er ude \u2014 s\u00e5 f\u00f8r det)<\/em>.<\/p>\n<p><\/p>\n<p>Hvis der opdages alvorlige problemer efter brug, og der er behov for forbedringer, vil jeg bestemt skrive om det.<\/p>\n<p><\/p>\n<h1 id=\"literatura\">Litteratur<\/h1>\n<p><\/p>\n<p>Jeg \u00f8nskede ikke at lave en lang, kedelig liste over de anvendte v\u00e6rker, alle har jo Google.<\/p>\n<p><\/p>\n<p>Her besluttede jeg at efterlade en liste over fund, som jeg syntes var s\u00e6rligt interessante, men efterh\u00e5nden blev de direkte indarbejdet i teksten, og der er kun \u00e9n post tilbage p\u00e5 listen:<\/p>\n<p><\/p>\n<ol>\n<li>Utility <noindex><a rel=\"nofollow\" href=\"https:\/\/github.com\/madler\/infgen\/\">infgen<\/a><\/noindex> fra forfatteren zlib. Den kan vise indholdet af deflate\/zlib\/gzip-arkiver p\u00e5 en forst\u00e5elig m\u00e5de. Hvis du skal forst\u00e5 den indre struktur af deflate-formatet (eller gzip) \u2014 kan jeg st\u00e6rkt anbefale det.<\/li>\n<\/ol>\n<p>Kilde: <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.3 - 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\/da\/blog\/administrirovanie\/moya-realizatsiya-koltsevogo-bufera-v-nor-flash\" \/>\n\t\t<meta name=\"generator\" content=\"All in One SEO (AIOSEO) 5.0.3\" \/>\n\t\t<meta property=\"og:locale\" content=\"da_DK\" \/>\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\/da\/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\udd47Min implementering af ringbufferen i NOR flash | ProHoster","description":"Baggrund Der er salgsautomater af egen udvikling. Inde i dem er der en Raspberry Pi og lidt ekstra udstyr p\u00e5 et separat printkort.","canonical_url":"https:\/\/prohoster.info\/da\/blog\/administrirovanie\/moya-realizatsiya-koltsevogo-bufera-v-nor-flash","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"da_DK","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\/da\/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\/da\/wp-json\/wp\/v2\/posts\/53751","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/comments?post=53751"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/posts\/53751\/revisions"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/media?parent=53751"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/categories?post=53751"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/tags?post=53751"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}