Newsgroup: it.hobby.elettronica.digitale
Titolo: Filesystem minimalista

Come in molti progetti embedded ho l'esigenza di salvare su piccole 
memorie non volatili dei dati di configurazione che vengono letti 
all'avvio per ripristinare gli ultimi salvati.
Il driver per gestire la memoria è formata da due semplici funzioni:
   int load(const unsigned int addr, const void *ptr, size_t size);
   int save(const unsigned int addr, const void *ptr, size_t size);
Normalmente voi come vi orientate per gestire questi dati? Per esempio 
su una piccola EEPROM seriale da 8KB?
L'idea di una serie di #define in un file memmap.h non mi piace per niente:
--- memmap.h ---
#define DATA_ADDR_1 0x0000
#define DATA_ADDR_2 0x0004
#define DATA_ADDR_3 0x000A
...
----------------
Infatti questo vuol dire calcolare l'indirizzo dei dati a partire dalla 
dimensione del precedente. Cambiare uno dei dati diventa complicato.
Recentemente sono passato a un approccio di questo tipo:
--- memmap.h ---
typedef struct {
   Data1 data1;
   Data2 data2;
   ...
} EEPROM;
#define SIZEOF(s,m) ((size_t) sizeof(((s *)0)->m))
#define LOAD(m,dst)
   load(offsetof(EEPROM, m), dst, SIZEOF(EEPROM, m));
-----------------
Ho parecchi vantaggi.
Gli indirizzi in EEPROM sono calcolati automaticamente mediante 
l'operatore offsetof(). Anche la dimensione dei vari dati è calcolata 
automaticamente mediante l'operatore derivato SIZEOF().
La cosa che non mi piace, anche se poca cosa, è dover esportare i 
simboli Data1, Data2, ecc (quindi definirli in un file .h da includere 
nel memap.h) che potrebbero rimanere tranquillamente a livello di modulo .c.
Il mio cervello si stava anche masturbando su eventuali file system 
minimali a cui accedere con una semplice libreria. Magari un file system 
la cui immagine iniziale (con i parametri di default) è possibile creare 
su computer. L'implementazione embedded potrebbe non prevedere la 
creazione/cancellazione dei file (che rimarrebbero sempre gli stessi 
sempre) e neanche la possibilità di aumentare/diminuire la dimensione 
degli stessi.
Come al solito, ditemi che sto esagerando...

 Come al solito, ditemi che sto esagerando...
Io ti dico la mia, poi aspetta il parere di quelli bravi :)
Dipende in primo luogo se questi dati sono statici (es. parametri di 
configurazione) oppure dinamici (cioè possono variare, magari anche a 
run-time).
Secondo, se parliamo di una EEPROM da 8 kB è un conto, se iniziamo a 
usare una SD da 2 GB è un altro.
Nei primi due casi (dati statici e memoria piccola) non vale la pena 
complicarsi la vita, basta organizzare bene i dati in qualche struct e 
assegnare l'indirizzo anche come hai fatto tu, cioè calcolando al volo 
la dimensione. Così se metti mano alla struct non cambi di una virgola 
il codice. Prevedi sempre un checksum nei dati così da ripristinare 
quelli di default (e segnalarlo!) in caso di corruzione/modifica della 
struttura.
Se la tipologia dei dati memorizzati può variare continuamente allora si 
può pensare a qualche cosa più evoluta, ma lascerei il file-system - 
anche non minimale es. FAT/FAT32 - a memorie più capienti.
Marco

   int load(const unsigned int addr, const void *ptr, size_t size);
Appunto estemporaneo: prt non può essere const, altrimenti il 
compilatore ti darà warning...

Prima di tutto premetto che i filesystem per embedded sono la mia 
passione, quindi potrei essere logorroico :-)
Devo dire che in linea generale sono abbastanza d'accordo con Marco 
per quanto riguarda i dispositivi piccoli.
Il sistema che stai usando è più o meno quello che ho usato anche io 
per diverso tempo, con ottimi risultati.
Io uso/usavo una sola macro, definita così (sarebbe la offsetof ma 
funziona anche con espressioni non costanti):
#define e2addr(type, field) ((e2addr_t)&(((type *)0)->field))
In questo modo, se hai una struttura in eeprom così:
typedef struct
{
     int array[128];
     ...
} EepromLayout;
poi puoi farci cose ganze tipo:
int buf[128];
for (int i = 0; i < 128; ++i)
{
     load(e2addr(EepromLayout, array[i]), &buf[i], sizeof(int));
     ...
}
Per il sizeof() poi usavo semplicemente l'operatore sizeof(), perché 
hai dovuto definirti la macro?
In ogni caso, una cosa del genere va bene se non hai altre esigenze.
Infatti i limiti di questo approccio vengono fuori quando poi si 
comincia a volere qualcosa di più; tipicamente, in ordine sparso, mi 
veniva chiesto di:
- Assicurarmi che il dato in memoria non fosse corrotto (memoria 
nuova/spegnimento improvviso).
- Che anche in caso di corruzione (spegnimento proprio mentre il micro 
stava scrivendo), ci fossero sempre dei dati buoni, tipicamente quelli 
precedenti.
- Che anche se l'utente avesse scritto 1000 volte al secondo le 
impostazioni, la memoria non si friggesse (wear levelling).
Se hai queste esigenze, alla fine avere un filesystem minimale, anche 
per una memoria da 8k, secondo me conviene.
Date queste premesse alla fine ne ho scritto uno mio, il BattFS, che 
ha come obbiettivi:
- Integrità assoluta dei dati (e non solo dei metadati)
- Wear levelling
- Struttura semplice: solo file e niente directory
- Transazionalità: fino al termine di una operazione i dati non sono 
"validi" su disco, quindi se spento in modo non pulito rimangono 
sempre disponibili i dati vecchi.
E' una cosa su cui "gioco" da diverso tempo, è quasi completo e manca 
solo dell'ultima feature (la transazionalità). Questo non perché sia 
lunga o complessa da implementare, solo perché non ho trovato il 
tempo/l'ispirazione :-)
In ogni caso per fare avere tutte queste features è però richiesta un 
po' RAM, proporzionale alla grandezza del "disco".
Quando mi riprende la vena creativa avevo anche in mente di 
implementare un'altra idea: un filesystem con le features di cui sopra 
ma adatto al salvataggio di sole strutture dati, senza file, e quindi 
più semplice e minimale ma anche più sprecone in termini di spazio si 
dico occupato: un qualcosa di vagamente simile a quello che hai 
immaginato tu.
La mia idea era quella di avere una API per cui all'inizio dici al 
filesystem quanta memoria del disco può usare. Per i dati di payload 
potrai usarne solo metà di quella specificata, l'altra metà verrà 
usata dal fs per fare una copia (simil-raid1 :-))
I dati salvati sulle metà sono protetti da CRC e ad ogni scrittura il 
fs scrive alternativamente su una o su l'altra metà in modo avere 
sempre dati validi anche dopo spegnimenti improvvisi.
Il tutto poi può scalare: da dividere il disco in 2 si può salire fino 
a N, in modo da aumentare la vita della memoria di N volte, occupando 
però N volte lo spazio dei dati veri.
Un fs del genere non sarebbe troppo difficile da implementare e non 
richiederebbe grandi risorse (poche decine di byte di RAM, qualche kB 
di flash).
Mi dai una mano :-P?
-- 
  _|/ Francesco Sacchi - Develer S.r.l., R&D dept.
   |\ 
http://www.develer.com/
 - 
http://www.bertos.org

 Mi dai una mano :-P?
Non penso di essere in grado, eventualmente devo capire meglio la
filosofia di questo fs.

 per impostare un dato da salvare con una frequenza molto alta.
Domanda idiota: non basta in questo caso riscrivere solo i dati che sono 
stati modificati?
Inoltre, personalmente inserisco sempre un ritardo dopo la 
memorizzazione dei parametri. Per cui se anche l'utente mi invia 100 
volte al secondo il comando di salvataggio, io scrivo 1 volta al secondo 
(numeri a caso).
Marco

 (numeri a caso).
Però questo crea dei ritardi non voluti quando magari c'è una
scrittura
voluta di più dati in poco tempo.

Reinvio perché mi ha dato errore e non lo vedo nel NG. Spero non appaia 
due volte agli altri.
Il 07/12/2010 10:46, pozz ha scritto:
 > Però questo crea dei ritardi non voluti quando magari c'è una
 > scrittura
 > voluta di più dati in poco tempo.
Giusto. Altro caso reale: alla ricezione dei dati aggiorno la struttura 
in RAM. Dopo x secondi in cui non ricevo più nuovi dati allora scrivo 
sulla EEPROM. Ti piace di più? :)
Marco

 filosofia di questo fs.
Tutto questo è pensato per salvare poche centinaia/kB di byte in magari 
una EEPROM da qualche decina di kB.
I punti di forza sono quelli indicati nel post precedente, a patto di 
avere spazio su disco e non preoccuparsi troppo delle prestazioni.
Se invece devi salvare parecchi dati e anche lo spazio su disco occupato 
e le prestazioni sono importanti, allora BattFS è migliore, ma di contro 
perde in spazio occupato su RAM.
Purtroppo una soluzione che fornisce tutto non esiste (o almeno io non 
sono in grado di trovarla :-)), come sempre si tratta di compromessi.
--
Francesco


Rimane sempre il problema che se uno dà il comando di salvataggio e poi 
spegne l'apparato, di fatto ha perso le impostazioni inviate.
Bisogna trovare un trade-off.
Alla fine sono giunto alla conclusione che il sistema migliore è doppio:
- cache svuotata ogni X, con X il massimo possibile per l'applicazione
- wear levelling se X deve essere breve.
--
Francesco

 avere spazio su disco e non preoccuparsi troppo delle prestazioni.
Non mi convince il fatto di dover scrivere ogni volta, anche per minime 
modifiche, tutta la partizione. Ma penso di aver capito male il tuo 
meccanismo...

 Sbaglio qualcosa nel mio ragionamento?
Decisamente ho cannato alla grande. Quel (1/100)^N è la probabilità di 
scrivere sempre lo stesso blocco dopo N scritture, considerando uniforme 
la probabilità di scrittura dei blocchi.
Sarebbe curioso calcolare il valore medio delle scritture per avere 
almeno un blocco difettoso (quindi scritto per N volte).
Ma intuitivamente non riesco a capire come scrivere ogni volta 100 
blocchi anzichè 1, seppure con due partizioni, possa far aumentare il 
tempo di vita della memoria.

 Sbaglio qualcosa nel mio ragionamento?
Sě, mi sa che non ci siamo capiti.
Ogni volta, riscrivo solo il numero minimo di blocchi necessario.
Ho fatto l'esempio con 2 che č il caso piů semplice da capire, ma 
questo va  bilanciato con la lunghezza dei dati da salvare e lo spazio 
su disco disponibile. Supponi di voler salvare 10 bytes in un disco da 
1000 bytes. Il mio sistema, invece di salvare questi 10 bytes sempre 
nello stesso posto, usa 100 blocchi da 10 bytes ciascuno, a rotazione, 
riscrivendone uno dopo l'altro. Se la vita di un blocco č N scritture, 
con questo sistema il primo blocco fallirŕ dopo 100 * N scritture. E 
questo č 100 volte meglio che salvare sempre nello stesso posto.
Il BattFS, usa tutto il disco e riscrive solo il numero minimo di 
blocchi necessario usando il sistema di cui sopra. Ha perň l'overhead 
di doversi tenere in RAM la mappa dei blocchi.
Nel caso di memorie non a blocchi come le EEPROM, il filesystem 
semplificato che proponevo, ha una granularitŕ scelta come la 
grandezza della tua struttura da salvare. Questo semplifica moltissimo 
l'accesso al disco e non richiede praticamente strutture in RAM.
Rispetto a non usare nulla e salvare sempre nello stesso posto ottieni:
- Assoluta integritŕ dei dati
- Transazionalitŕ: in ogni caso esiste sempre almeno un dato vecchio 
valido
- Incremento della vita della memoria di sizeof(disco)/sizeof(struttura)
Di contro perderesti solo un po' di spazio in flash per le funzioni di 
accesso al disco. Non mi sembra affatto male.
Purtroppo č un trade-off: non puoi ottenere la granularitŕ del singolo 
byte su una EEPROM senza sprecare una quantitŕ di memoria RAM maggiore 
della dimensione della EEPROM stessa. A dire la veritŕ un'alternativa 
ci sarebbe: non tenere una mappa dei blocchi e cercare tutte le volte 
l'informazione che ti serve nel disco. Ma questo influirebbe troppo 
sulle prestazioni: avrebbe senso leggersi magari 32K quando cerchi un 
dato da un byte?


 doversi tenere in RAM la mappa dei blocchi.
Ok, ma quando parli di 10 byte intendi *tutti* i dati della tua
applicazione, oppure solo una parte (solo Config1 degli esempi sopra)?
Facciamo un esempio più realistico di un'applicazione: 10 strutture
dati (Config1... Config10) da 10 byte l'una. Quindi 100 byte in una
memoria da 1000 byte. Posso fare 10 partizioni per aumentare il tempo
di vita della memoria di 10 volte.
Cosa faresti quando vuoi aggiornare solo Config1? Salvi tutti i 100
byte su un'altra partizione, oppure solo Config1 su un'altra
partizione.
Se salvi tutti i 100 byte, stai scrivendo *molti* più byte di quelli
che scriveresti aggiornando solo Config1 sempre sulla stessa
partizione.
Sei sicuro di allungare il tempo di vita della memoria?
Se salvi solo i 10 byte di Config1 su un'altra partizione, devi
prevedere che ogni struttura dati si possa trovare in una partizione
diversa. Quindi ogni struttura dati avrà una sua CRC con un suo
contatore.

 (o estensione), ecc.
Ok, tieni presente però che un FS del genere potrebbe friggerti la 
eeprom in poche ore se le scritture sono frequenti. Infatti, ogni volta 
che tocchi un file, devi scrivere, nell'ordine: il cluster, il checksum 
e eventualmente la tabella, che sono in locazioni fisse.
Questi sì che ammazza la vista dalle memoria ;-)
Inoltre avresti problemi di perdita di dati in caso di spegnimento a 
caldo (però magari questa feature non ti interessa).
In genere invece, i FS per dispositivi con un numero limitato di 
scritture sono tutti log-based, ovvero non si servono di tabelle o altro 
ma obsoletano l'informazione vecchia semplicemente scrivendone una nuova 
versione.
La tabella la tengono solo in RAM e al mount devono scandire tutto il disco.

Capisco il tuo ragionamento, ma come sempre si tratta di trovare un 
trade-off. Perché se no, a questo punto ti chiedo: se devo cambiare solo 
1 byte dentro Config1, perché devo scrivere tutta la struttura?
Il FS minimale a cui stavo pensando, per avere i requisiti di semplicità 
e basso impatto RAM, deve necessariamente salvare tutto, tutte le volte.
Questo però non vieta di avere N filesystem, uno per struttura Config, 
che salvano i dati in partizioni diverse della memoria.
In questo modo ottieni tutti i vantaggi dati dal FS con in più la 
possibilità di tenere separate le configurazioni come volevi tu.
Che ne dici?
-- 
Francesco

 Che ne dici?
Chiamarlo FS, seppure minimale, č esagerato. Si tratta di avere lo 
stesso layout nelle N partizioni. All'avvio, per ogni struttura Config, 
si cerca quella pių recente tra le N partizioni e si usa quella.
In RAM ci sarā in effetti una tabella con la corrispondenza della 
partizione corrente associata ad ogni Config.
In soldoni, ogni struttura dati dovrā essere "decorata" con una checksum 
ed un contatore.
Qualcosa di questo tipo:
--- EepromLayout.h ---
typedef struct {
   struct Config1Data {
     Config1 cfg1; int checksum; int counter;
   } cfg1data;
   struct Config2Data {
     Config2 cfg2; int checksum; int counter;
   } cfg2data;
   ...
} EepromLayout;
---
La funzione di caricamento di una struttura dati sarā del tipo:
---
int
load_cfg1 (void)
{
   int i, imax, cntmax;
   struct Config1Data cfg1data;
   struct Config1 cfg1;
   cntmax = -1;
   for (i = 0; i < NUM_PARTITIONS; i++) {
     load(offsetof(EepromLayout, Config1Data);
     if (cfg1data.counter > cntmax) {
       cntmax = cfg1data.counter;
       imax = i;
       memcpy(&cfg1, &cfg1data, sizeof(cfg1));
     }
   }
}
---
Purtroppo, perō, questa funzione deve essere diversa per ogni Config.
Ma in questo FS minimale di cui parli, non c'č spazio per gestire 
automaticamente l'ingrossamento delle strutture Config, che č il mio 
cruccio principale, ancora maggiore del tempo di vita della memoria?

 partizione corrente associata ad ogni Config.
No, non č necessaria la tabella in RAM.
Al mount, dici al FS quale partizione usare (da cui deriva la 
lunghezza del disco) e quanti bytes vuoi salvarci. A questo punto 
viene scandito il disco e trovata l'ultima informazione valida (se 
esistente). Da questo momento in poi i salvataggi procedono in modo 
incrementale in round robin, usando blocchi della lunghezza 
specificata all'inizio + lunghezza metadati (crc + num versione).

No aspetta, il FS si chiama cosė proprio perché si occuperebbe lui di 
gestire queste cose. Non devi modificare le tue strutture, i metadati 
vengono aggiunti dal FS in modo trasparente. Il FS sarebbe un modulo a 
parte generico che poi verrebbe usato dalle funzioni di caricamento 
configurazione. E per quanto riguarda l'ingrossamento, ogni modulo puō 
gestire in autonomia l'upgrade di versione in modo indipendente dagli 
altri, come stai facendo adesso. Certo, l'aumento di dimensione non č 
la prerogativa con cui questo FS č progettato e l'aggiornamento č un 
po' macchinoso, d'altra parte io questo non lo consideravo una prioritā.
Se invece vuoi qualcosa in cui ci siano dei veri file che possono 
essere creati, cancellati, allungati e troncati, allora ti serve 
BattFS, che č sempre minimale, ma non minimale quanto l'approccio 
precedente. Richiede qualche kB di flash e 2 bytes di RAM per ogni 
blocco su disco. Se supponiamo di avere un EEPROM 24256 da 32KBytes, 
con blocchi da 128 bytes, occuperebbe 512 bytes di RAM.
Ho anche un'altra alternativa. Se la tua preoccupazione principale č 
la dinamicitā, forse nemmeno i file sono la soluzione migliore.
In questi giorni dovrei progettare (dico dovrei perché non ho mai 
tempo) un sistema per memorizzare coppie di chiave-valore, proprio per 
un sistema di configurazione che deve essere altamente dinamico.
Invece di salvare le strutture intere, ho la necessitā di salvare dati 
specifici, di vario tipo (int, float, data, stringa, etc...). Ad ogni 
dato dai un ID e lo butti nel "filesystem" (forse sarebbe pių corretto 
chiamarlo "dizionario" o "mappa"). In questo modo le modifiche sono 
molto facili e la granularitā č a livello di singolo dato. Quando vuoi 
aggiungere un dato basta... farlo e non si rompe nulla di quello che 
c'č giā. L'aggiornamento da una versione vecchia a quella nuova puoi 
farlo leggendo semplicemente la chiave con il numero di versione e 
cambiando/aggiungendo specificatamente solo quello che serve. Devo 
ancora pensare se e come gestire i problemi di integritā e di wear 
levelling della memoria.


 levelling della memoria.
Non ci crederai, ma è quello a cui ho pensato anche io. Alla fine
stavo pensando addirittura ad un file INI che avrebbe l'enorme
vantaggio
di poter essere facilmente creato e visionato su un computer.
Però l'utilizzo di caratteri ASCII sia per i nomi delle chiavi che per
i valori farebbe aumentare di molto sia lo spazio nella memoria che
l'elaborazione.
In effetti sarebbe meglio un file INI di tipo binario dove associ ad
ogni
chiave (individuata tramite un ID numerico) un valore (una sequenza di
byte grezza).

 byte grezza).
Beh, se ti interessa, ti tengo aggiornato, и un lavoro che devo fare il 
prima possibile.
Ciao!
-- 
Francesco

 prima possibile.
Certo che sono interessato... :-)

 Certo che sono interessato... :-)
Ok, alla prossima allora :-)
