Buffer circolare in Flash

Question

ho bisogno di memorizzare oggetti di varia lunghezza in una coda circolare in un chip flash. Ogni oggetto avrà il suo incapsulamento in modo da poter capire quanto è grande e dove l'elemento successivo inizia. Quando ci sono elementi sufficienti nel buffer, si avvolgere all'inizio.

Che cosa è un buon modo per memorizzare una coda circolare in un chip flash?

C'è la possibilità di decine di migliaia di oggetti vorrei memorizzare. Così a partire dall'inizio e la lettura alla fine del buffer non è l'ideale, perché ci vorrà tempo per cercare fino alla fine.

Inoltre, perché è circolare, ho bisogno di essere in grado di distinguere il primo elemento dall'ultimo.

L'ultimo problema è che questo è memorizzato in Flash, quindi cancellando ogni blocco è sia in termini di tempo e può essere fatto solo un determinato numero di volte per ogni blocco.

Answer 1

In primo luogo, la gestione dei blocchi:

Mettere un colpo di testa più piccola all'inizio di ogni blocco. La cosa principale è necessario tenere traccia del "vecchio" e "più nuova" è un numero di blocco, che incrementa semplicemente modulo k . k deve essere maggiore il numero totale di blocchi. Idealmente, fare k meno che il vostro valore MAX (ad esempio 0xFFFF) in modo da poter facilmente dire che cosa è un blocco cancellato.

Al di start-up, il codice legge le intestazioni di ciascun blocco a turno, e individua il primo e l'ultimo blocco della sequenza che è n _{i + 1} = (n _i + 1) MODULO k. Fare attenzione a non confondersi con blocchi cancellati (numero di blocco è per esempio 0xFFFF) o dati che sono in qualche modo danneggiato (ad esempio cancellazione incompleta).

All'interno di ogni blocco

Ogni blocco inizia inizialmente vuoto (ogni byte è 0xFF). Ogni record è semplicemente scritto una dopo l'altra. Se si dispone di record di dimensione fissa, quindi è possibile accedervi con un indice semplice. Se si dispone di record di dimensione variabile, quindi di leggere che è necessario eseguire la scansione dall'inizio del blocco, stile lista concatenata.

Se si desidera avere record di dimensioni variabili, ma evitare la scansione lineare, allora si potrebbe avere un colpo di testa ben definito su ogni record. Per esempio. utilizzare 0 come delimitatore record e COBS -encode (o / R -encode ) ogni record. Oppure utilizzare un byte di vostra scelta come delimitatore, e 'fuga' che Byte se si verifica in ogni record (simile al PPP protocollo ).

Al di start-up, una volta che conosci il tuo ultimo blocco, si può fare una scansione lineare per l'ultimo record. O record o delimitatori di record di dimensione fissa se si è, si potrebbe fare una ricerca binaria.

Cancella la programmazione

Per alcuni chip di memoria flash, la cancellazione di un blocco può richiedere molto tempo - per esempio. 5 secondi. Prendere in considerazione la pianificazione di una cancellazione come attività in background un po ' "prima del tempo". Per esempio. quando il blocco attuale è x% pieno, quindi avviare la cancellazione del blocco successivo.

Record di numerazione

Si consiglia di record numerici. Il modo in cui ho fatto in passato è quello di mettere, nell'intestazione di ogni blocco, il numero record del primo record. Poi il software deve tenere il conto del numero di ciascun record all'interno del blocco.

Checksum o CRC

Se si desidera rilevare i dati danneggiati (per esempio scrive incomplete o cancella a causa di mancanza di corrente inaspettato), allora si può aggiungere un checksum o CRC per ogni record, e forse per l'intestazione del blocco. Si noti l'intestazione del blocco CRC sarebbe solo coprire l'intestazione stessa, non i record, dal momento che potrebbe non essere riscritta quando ogni nuovo record viene scritto.

Answer 2

Tenere un blocco separato che contiene un puntatore all'inizio del primo record e la fine dell'ultimo record. È inoltre possibile mantenere ulteriori informazioni come il numero totale di record, ecc.

Fino a che inizialmente esaurisce lo spazio, l'aggiunta di record è così semplice come scriverli alla fine del buffer e l'aggiornamento del puntatore coda.

Per quanto è necessario recuperare spazio, eliminare abbastanza dischi in modo da poter adattare il vostro record corrente. Aggiornare il puntatore di testa, come si eliminano i record.

Avrete bisogno di tenere traccia di quanto spazio in più è stato liberato. Se si mantiene un puntatore alla fine dell'ultimo record, la prossima volta che è necessario aggiungere un record, è possibile confrontare che con il puntatore al primo record per determinare se è necessario eliminare tutti i più record.

Inoltre, se questo è NAND, voi o il regolatore istantaneo sarà necessario fare deblock e all'usura livellamento, ma che dovrebbe essere tutti ad un livello inferiore rispetto allocare spazio per il buffer circolare.

Answer 3

Credo di aver capito adesso. Sembra che il problema più grande sarà, dopo aver riempito lo spazio disponibile per la registrazione, cosa succede dopo? I nuovi dati dovrebbero sovrascrivere i dati più vecchi, che è credo cosa si intende per un buffer circolare. Ma dal momento che i dati non è fisso lunghezza si può sovrascrivere più di un record.

Sto assumendo che la quantità di variabilità nella lunghezza è abbastanza alto che imbottitura tutto fuori ad una lunghezza fissa non è un'opzione.

Il segmento di scrittura ha bisogno di tenere traccia dell'indirizzo che rappresenta l'inizio del prossimo disco di scrivere. Se si conosce la dimensione di un blocco per scrivere prima del tempo, si può dire se si sta andando a finire alla fine del buffer logica e ricominciare a '0'. Non vorrei dividere un record con un po 'alla fine e un po' all'inizio.

Un registro separato in grado di monitorare l'inizio; Questi sono i dati più antico che non è ancora stato sovrascritto. Se si è andato a leggere i dati questo è dove si dovrebbe cominciare.

Lo scrittore di dati allora avrebbe controllato, dato l'indirizzo di scrittura-start e la lunghezza dei dati proprio sul punto di commettere, se deve urtare il registro di lettura, che esaminerà il primo blocco e vedere la lunghezza, e passare a quello successivo registrare, fino a quando non v'è spazio sufficiente per scrivere quello dei dati è. Ci sarà uno spazio di dati spazzatura che vive tra la fine dei dati scritti e l'inizio dei dati più vecchi, probabilmente. Ma in questo modo, si può solo essere iscritto un indirizzo o due come in testa, e non riorganizzare i blocchi.

Almeno, questo è probabilmente quello che vorrei fare. HTH

Answer 4

Vedo tre opzioni:

opzione1: è quello di pad tutto fuori alla stessa dimensione, questo è semplice, memorizzare un puntatore alla testa e la coda del buffer in modo da sapere dove scrivere e dove iniziare la lettura, utilizzare la dimensione di ogni oggetto da ottenere un offset per il prossimo, questo significa che è necessario trasversale buffer come se fosse una lista collegata, alias la sua lenta se avete bisogno di voce 5000.

opzione2: è quello di memorizzare solo i puntatori ai dati reali nel buffer circolare, in questo modo quando si anello intorno non si ha a che fare con la dimensione mis-matchs. se si memorizzano i dati reali in un buffer circolare e non fai pad fuori si potrebbe incorrere in una situazione in cui il vostro corso witting oggetti multipli con 1 nuovo oggetto di dati, suppongo questo non va bene.

memorizzare i dati effettivi altrove in flash, più flash avere una sorta di livellamento usura integrato, se così non è necessario preoccuparsi di sovrascrivere stessa posizione più volte, l'IC sarà capire dove realmente conservarlo on chip, basta scrivere a al successivo spazio libero disponibile.

questo significa che è necessario scegliere una dimensione massima per il buffer circolare come si esegue questa operazione dipende dalla variabilità dei dati. Se la dimensione dei dati basta cambiare molto, dire che solo da pochi byte, allora si dovrebbe solo pad fuori e l'opzione 1. uso Se le modifiche di dimensione selvaggiamente e imprevedibile, scegliere la dimensione più grande che potrebbe essere e capire come molti oggetti di quelle dimensioni si adatterebbe nella vostra flash, utilizzarlo come il numero massimo di voci nel buffer. Questo significa che si rifiuti di un sacco di spazio.

opzione 3: se l'oggetto può davvero essere di qualsiasi dimensione, la tua nel punto in cui si deve solo usare un file system, il nome del file in ordine e ciclo indietro quando il vostro tenendo pieno a mente se la nuova voce è grande si può deve eliminare più voci vecchie per adattarsi in. Questo è in realtà solo una proroga dell'opzione 2 come opzione2 è per molti versi un file di sistema semplice.

Answer 5

Il "circolare" in un lampo può essere fatto in base alla dimensione del blocco, il che significa che è necessario dichiarare quanto i blocchi del flash si alloca per questo buffer.

La dimensione effettiva del buffer sarà in ogni particolare momento tra n-1 (n è il numero di blocchi) e n.

Ogni blocco deve iniziare con un'intestazione contenente numero sequenziale o timestamp che potrebbe essere utilizzato per determinare quale blocco è più vecchia rispetto agli altri.

Ogni prodotto incapsulato con un'intestazione e un piè di pagina. l'intestazione predefinito contiene tutto quello che vuoi, ma secondo questa intestazione è necessario conoscere la dimensione della voce. Il piè di pagina di default è 0xFFFFFFFF. Questo valore indica una terminazione nullo.

Nella vostra RAM è necessario salvare un puntatore al blocco più antica e la più recente blocco e puntatore sulla voce più antica e più recente voce. All'accensione si va oltre tutti i blocchi trovare i blocchi rilevanti e caricare questo membri.

Quando si desidera memorizzare un nuovo elemento, si controlla se l'ultimo blocco contiene abbastanza spazio per questo articolo. Se lo fa si salva la voce alla fine della voce precedente e la variazione del piè di pagina precedente di puntare a questa voce. Se non contiene abbastanza spazio necessario per cancellare il blocco più antico. Prima di cancellare questo blocco Cambiare i membri del blocco più vecchi (RAM) per puntare sul prossimo blocco e l'elemento più antico per puntare sul primo punto in questo blocco. Quindi è possibile salvare la nuova voce in questo blocco e cambiare il piè di pagina l'ultimo nato a punto di questo oggetto.

So che la spiegazione può sembrare complicato, ma il processo è molto semplice e se si scrive corretto si può rendere ancora più potere fail safe (sempre tenere a mente che si l'ordine delle operazioni di scrittura).

Fare attenzione che la circolarità del buffer non viene salvato nella flash, ma il flash contiene solo blocchi con elementi che è possibile decidere in base ai blocchi di intestazioni e le intestazioni articoli qual è l'ordine di questi elementi