www.mikrocontroller.net

Forum: Projekte & Code Custom made file system: "uFS"


Autor: Simon K. (simon) Benutzerseite
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Huhu,

Ich hab mich mal ein Weilchen hingehockt und mir gewissermaßen ein 
eigenes Dateisystem designed. Es ist - um gottes Willen - nicht 
vergleichbar mit FAT oder NTFS, aber ich habe sehr viel Wert darauf 
gelegt (und werde es bei zukünftigen Änderungen tun), dass es schnell 
auf 8 Bit Mikroprozessoren (zB 8 Bit AVR) läuft. Einige Sachen habe ich 
bewusst nicht implementiert (zB Journaling oder verschiedene 
Partitionen) und einige Sachen sind noch nicht ganz eingebaut oder 
könnten verbuggt sein.

Naja, wie auch immer. Ich habe schonmal eine ram-emulated Version 
angehangen, an der ich immer entwicklte. Man kann sich das ganze also 
schonmal zu gemüte führen. Ich habe bewusst alles in Englisch 
dokumentiert, auch wenn sich vielleicht teilweise Formulierungen zum 
totschießen anhören könnten, sollte man immer wissen, was ich mit der 
Aussage aussagen wollte ;). Ich habe mir sogar die Mühe gemacht, alles 
in einem PDF zu dokumentieren, um es leicht nachvollziehen zu können.

Ihr könnt ja mal reinschauen. Ich werde es aufjedenfall für mein AVR-NAS 
verwenden :-).

Viel Spaß schonmal. Kritik und Bugreport ausdrücklich erwünscht.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ist zwar schon etwas spär, aber vielleicht kann ich
dich noch überreden:

Du benutzt wie FAT eine Bitmap um anzuzeigen, wo die nächste
freie Page ist. Hätte ich so nicht gemacht. Denn damit brauchst
du immer noch Speicher im µC um diese Page zu lesen um zu
entscheiden wo Daten als nächstes geschrieben werden können.
Mal ganz abgesehen von dem ganzen Bit-Gefummel.

Ich würde Pages in 2 Kategorien unterteilen: Benutzte und
unbenutzte.
Wenn Daten geschrieben wurden, dann sind ja die Pages
untereinander verknüpft. In jeder Page steht, wo die
nächste Page, die zu diesem File gehört zu finden ist.

Nun: Dasselbe kann ich auch mit dem nicht benutzten Pages
machen. Auch die werden auf die gleiche Art und Weise
miteinander verknüpft werden: In jeder freien Page
steht, welches die nächste freie Page ist. Der Anfang
der Kette steht in der Header Page. Brauche ich also
eine freie Page, so brauche ich nur im Page Header
nachschauen, wo sich die befindet. Von der Page hole
ich mie die Verkettungsinformation und schreibe die
in den Page Header. Somit ist die zuvor eingetragene
Page aus der Kette ausgehängt und kann für ein File
benutzt werden. Genau umgekehrt beim Löschen eines Files:
In die frei werdende Page schreibe ich die Verkettungsinformation
aus dem Header und die freiwerdende Page wird im Header
eingetragen.

Auf die Art brauch ich keine Bitmap um die Pages zu verwalten.
Das ganze Medium enthält praktisch immer mindestens 1 'File':
Das File, das die unbenutzten Pages aufsammelt.

Ansonsten: Sieht gut aus.

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Karl Heinz,

Die Idee ist verdammt genial. Das erspart mir sogar das Suchen nach 
einem freien Bit und spart zudem auch noch Speicherplatz. Somit passt 
das vorallem sehr gut in mein 8Bit-Mikrocontroller-Prinzip.

Das schreib ich mir auf die ToDo Liste, vielen Dank :-)))

PS:
>Ansonsten: Sieht gut aus.
Dankesehr!

Autor: Thomas (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sag mal, unter Linux müsste es doch sogar möglich sein einen Treiber zu 
schreiben sodass dort auch dein µFS gelesen werden kann oder?

In den Devicefiles /dev/xxx stehen ja soweit die reinen Rohdaten drin, 
unter Windows hat man so einfach ja keine Zugriffsmöglichkeiten.

Autor: Tobias Schneider (tobias)
Datum:

Bewertung
0 lesenswert
nicht lesenswert

Autor: ---- (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Schön gemacht und gut gelungen.
Und vor allem nicht vorher lang und breit posaunt, sondern gleich mit 
einem vorzeigbaren(!) (Zwischen)ergebnis hier aufgetreten! Weiter so.

----, (QuadDash).

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Thomas wrote:
> Sag mal, unter Linux müsste es doch sogar möglich sein einen Treiber zu
> schreiben sodass dort auch dein µFS gelesen werden kann oder?
>
> In den Devicefiles /dev/xxx stehen ja soweit die reinen Rohdaten drin,
> unter Windows hat man so einfach ja keine Zugriffsmöglichkeiten.

Leider kann ich dir da keine Antwort drauf geben, aber WENN es möglich 
wäre, dann hättest du 101% meines Interesses ;)

Für Windows will ich das garnicht erst versuchen. Hau' mir bloß ab damit 
:-)

@Quaddash: Vielen Dank :-)

PS: Die ToDo Liste ist noch um ein paar Einträge gewachsen. Immer her 
mit der Kritik :D

Autor: Hans Wilhelm (hans-)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
am pinguin sollte das sogar ziemlich einfach hinhaun ein "neues" 
betriebssystem einzubaun ... schau dir mal da 
an:http://fuse.sourceforge.net/

gibt da noch so ein projekt weis aber nicht mehr genau wie das hieß...

prinzipiell fehlt mir selbst auch soein nettes, kleines filesystem.. 
aber ich würd deins dezent umkrempeln auf verkettete listen.. das ist 
einfach schneller...

ggf könnte das ganze sogar so ausschaun: du hast  ja deine files eh 
schon als listen organisiert... mach doch einfach beim formatieren eine 
nette Free-File.. die enthält alle pages des datenträgers.. wenn du dann 
in eine file schreibst nimmst du der free-file einfach eine page weg 
wenn du mehr speicher brauchst...

damit müsstest nur noch ein file-attribute für die free-file einführen 
und könntest damit wunderbar arbeiten... theoretisch könntest du sogar 
nach einer free-file suchen lassen wenn dir der platz in der aktuellen 
ausgeht.. dann brauchst bei den zu löschenden files einfach nur das 
free-flag setzen...

damit wär sogar ein recovery möglich wenn noch nix überschrieben wurde..

mal schaun ob ich in den nächsten ferien mal zeit hab... ich bin nämlich 
schon am überlegen ob ich nicht einen lua-interpreten für so kleine 
plattformen bastle und da wär so ein filesystem recht nett :)

73

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>prinzipiell fehlt mir selbst auch soein nettes, kleines filesystem..
>aber ich würd deins dezent umkrempeln auf verkettete listen.. das ist
>einfach schneller...

Wie meinst du das? Das basiert doch schon auf einer verketteten Liste. 
Oder meinst du Karl Heinz's Idee?
Das werd ich demnächst auch mal einbauen, wenn mich wieder Langeweile 
überkommt. ;)

>ggf könnte das ganze sogar so ausschaun: du hast  ja deine files eh
>schon als listen organisiert... mach doch einfach beim formatieren eine
>nette Free-File.. die enthält alle pages des datenträgers.. wenn du dann
>in eine file schreibst nimmst du der free-file einfach eine page weg
>wenn du mehr speicher brauchst...

>damit müsstest nur noch ein file-attribute für die free-file einführen
>und könntest damit wunderbar arbeiten... theoretisch könntest du sogar
>nach einer free-file suchen lassen wenn dir der platz in der aktuellen
>ausgeht.. dann brauchst bei den zu löschenden files einfach nur das
>free-flag setzen...

Verstehe ich dich jetzt falsch oder meinst du das so, wie Karl Heinz? 
Wofür das Free-Flag?

Vielen Dank schonmal für deine Antwort. Das mit dem LUA Interpreter 
klingt interessant und das FUSE schau ich mir doch glatt mal an.

Autor: Oliver Döring (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nicht schlecht!

Mich beschäftigt zur Zeit etwas ähnliches - Dateien, von denen sich 
manche ständig ändern, effizient in einem Atmel Data Flash 
unterzubringen. FAT kann man total vergessen, weil dann die Page, in der 
die FAT untergebracht ist, nach kürzester Zeit verschlissen ist.

Der Vorschlag von Karl-Heinz Buchegger würde schon mal einen Großteil 
der Zugriffe über das Flash verteilen und damit die Gesamtlebensdauer 
erhöhen.

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Oliver,

Um mal zum Thema der Lebensdauer zu kommen:
Prinzipiell magst du recht haben, aber das hängt auch von der 
Implementierung ab.

Nehmen wir mal an, meine page-allocate funktion fängt bei jeder 
page-allokation an, erstmal den disk-header zu lesen, die adresse der 
ersten freien pages zu ermitteln, die pointer dann "umzuhängen" und dann 
wieder die disk-header page zu schreiben. Wenn das tatsächlich so 
implementiert werden würde, würde bei jeder page-allokation der 
disk-header geschrieben.
Resultat: Nach 100000 Page-allokationen (also sagen wir nach dem 
kopieren einer datei, die 100000*512 = ~5MB groß ist) ist die 
disk-header page hinüber. Das ist nicht nur blöd, sondern auch blöd! *g 
;)

Mir fällt zur Zeit nur ein Ansatz ein, dies anders zu gestalten:
Beim hochfahren des Mikrocontrollers holt sich der Mikrocontroller aus 
dem disk-header die Adresse der ersten freien Page in eine statische 
Variable. Wird eine Page allokiert, dann geht meine page-allocation 
Funktion zuerst zu der Page, dessen Adresse in der statischen Variable 
gespeichert ist, hold den pNextpage pointer und diverse andere 
Informationen und nimmt diese Page aus der Liste. Dabei wird natürlich 
an die Adresse, die in der statischen Variable ist, geschrieben. Jetzt 
sagen wir aber einfach, dass wir die statische Variable nach diesem 
Vorgang auf die Adresse der nächsten freien Page setzen (Die haben wir 
ja vorhin unter anderem mit aus der SD Karte herausgelesen). Beim 
nächsten Allokationsvorgang wird also die nächste Page in der Liste 
verändert.
Das gleiche machen wir dann noch beim freigeben von Pages: Wir hängen 
die Page nach der Page ein, die mit der statischen Variable adressiert 
ist und erneuern diese Variable auf die nächste freie Page.
Resultat: Möglichst gleichmäßige Abnutzung utner der Vorraussetzung, 
dass der Mikrocontroller relativ lange an ist und sich die statische 
Variable möglichst lange im Speicher halten kann.
(Man könnte die Variable dann vielleicht noch beim Herunterfahren auf 
die Disk zurückschreiben, aber das ist jetzt erstmal nebensächlich)

Naja, macht das ganze System schon etwas komplizierter und (worauf ich 
eigentlich auch Wert lege) für "Newbies" noch unverständlicher udn 
verwirrender auf den ersten Blick.

Hat hier vielleicht jemand eine andere Idee?

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Um mal zum Thema der Lebensdauer zu kommen:

Das gleiche Problem hast du doch auch mit den Bitmap Pages.

Das Problem ist doch, dass es mindestens 1 Page geben muss,
die an einer konstanten, immer gleichen Speicherstelle liegen
muss, weil sie der Einstiegspunkt zur restlichen Organisation
ist. Um die kommst du nicht rum, und die wird auch am häufigsten
benutzt und wahrscheinlich als erstes 'abgenutzt'.

Ich sehe da eigentlich nur 1 Möglichkeit da etwas
aufzuräumen: Für Lesezugriffe im SRAM einen Cache einrichten,
klar.
Für Schreibzugriffe müsste man das eigentliche Schreiben
etwas verzögern. Keine Ahnung, vielleicht 1 oder 2 Sekunden.
Trifft in dieser Zeitspanne ein weiterer Schreibversuch ein,
dann hast du damit einen effektiven Schreibzugriff auf das
Medium eingespart und die Wartezeit beginnt wieder von vorne.
Problem an der Sache sind natürlich die ungeduldigen User:
Wer nicht warten kann, bis auch der letzte Schreibzugriff
abgeschlossen ist und die Karte vorzeitig abzieht, bringt
alles in Unordnung.

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Auch diese "Probleme" lassen sich lösen. Die Idee ist es ja alle Pages 
wie ein Ringbuffer untereinander zu verlinken. Bei freien Pages hat man 
genügend Platz um noch mehr Daten zu speichern, zb. einen Zähler. Statt 
nun diesen Buffer immer vom Anfang zu verwenden wird man ihn einfach wie 
ein Ringbuffer verwenden. D.h. würde man eine Datei mit 256 Pages 
anlegen, so hätte man zwei verlinkte Ring"buffer". Gibt man diese Datei 
nun wiederholt frei und alloziert sie neu so würde man ja immer die 
gleichen 256 Pages benutzen. Nun könnte man aber auch immer reihherum 
die freien Pages benutzen. Beim ersten mal also Pages 0 bis 255, beim 
Zweiten Mal Pages 256 bis 511 usw. Man benötigt dann nur einen Zähler 
der quasi die Reihenfolge/Priorität ihrer Benutzung speichert.

Bei der ersten Initialisierung der SD Karte muß man nun sequientiell 
alle Pages druchgehen um die Startpage für die nächsten Allokationen zu 
ermitteln. Das wäre dann ein ein wenig länger dauernder Prozess, würde 
aber die Verwendung einer FAT-Header-Page vermeiden. Zur Laufzeit 
speichert man diesen Index dann im SRAM und inkremetiert ihn 
entsprechend den Allokationen. Zurückschreiben auf die SD Karte muß man 
diesen aber nicht, da ja die Linkstruktur innerhalb der Pages immer 
konsistent bleibt.

Man könnte auch einfach mit einem sich nicht wiederholendem 
Zufallsgenerator arbeiten und damit die Startpage ermitteln. Im Mittel 
müssten dann alle Pages gleichermaßen belastet werden.

Gruß Hagen

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ja, genau die Ringbuffer beschreibung passt auf das, was ich erklären 
wollte. Man verknüpft die freien Pages als Ring und hat einen immer 
wieder inkrementierenden statischen pointer auf die page, die als 
nächstes allokiert wird, bzw wo die nächste gelöschte page eingefügt 
wird. Ist so ein Vorgang abgeschlossen, wird der Pointer so 
inkrementiert, dass bei der nächsten Allokation die nächste Page im 
Bunde verändert wird.

Aber zurückschreiben würde ich diesen Pointer beim "Herunterfahren" 
schon. Um bei einem Start die letzte Ringposition wiederherzustellen.

Ich werde das mal an meinem ramdrive Modell ausprobieren...

so long.

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>>Aber zurückschreiben würde ich diesen Pointer beim "Herunterfahren"
>>schon. Um bei einem Start die letzte Ringposition wiederherzustellen.

Aber dann musst du diesen wieder in eine fest definierte Page 
zurückschreiben und hast dann wieder eine stärker belastete Page die 
schneller verschleißt. Diesen Zeiger in den EEPROM zu speichern würde 
bedeuten das er inkonsistent zu den Daten auf der SD Karte werden 
könnte, weil zb. mehrere Geräte die gleiche Karte nutzen könnten. 
Desweiteren entstehen Inkonsistenzen wenn man diesen Pointer im SRAM 
buffert und der Controller nicht korrekt "herunter"gefahren wird.

Deshalb die Idee eine Page mit einem Zähler zu versehen. Die Page mit 
dem geringsten Zähler ist unser Startlink im Ringbuffer. Beim Powerup 
kann man nun die SD Karte durchsuchen nach dieser Page. Man muß dies 
aber nicht sequientiell machen sondern kann auf Grund der Linkstruktur 
mit besseren Suchverfahren arbeiten, Binäre Suche zb. Bei einer 512Mb 
SD-Karte haben wir 1024*1024 Pages das macht im Worstcase exakt 20 Pages 
die man laden und untersuchen muss um die Startpage zu finden. Das ist 
doch nicht schlecht. Zumal die SD-MMC Karten ein "truncated" Lesen der 
Pages zulassen. Wenn man also nur die ersten 8 Bytes für die Links 
benutzt so muss man bei dieser Suche auch nur diese 8 Bytes laden, statt 
512. Das wären 8*20 Bytes, das ist in par Millisekunden erledigt. Man 
müsste also 2 Suchen durchführen, erstens um die Page mit dem kleinsten 
Zähler zu finden und noch eine um die Page mit dem höchsten Zähler zu 
finden. Die Page mit dem kleinsten Zähler ist diejenige die man als 
nächstes verwendet, die Page mit dem höchsten Zähler enthält den Zähler 
-1 den man bei der nächsten freizugebenden Page benutzen muß. Man kommt 
dann komplett ohne FAT oder dergleichen aus. Allerdings besteht ja die 
Aufgabe einer FAT nun nicht nur darin die Pages zu einer Datei zu 
verwalten sondern eben auch die Dateinamen/Attribute/Datum/Zeit etc. Das 
wäre mit obiger Linkstruktur ja noch nicht berücksichtigt. Aber auch das 
könnte man machen indem man in der ersten Page zur Datei diese Daten 
speichert. Zusätzlich verlinkt man nun diese "Datei-Header-Pages" 
untereinander und hat so eine verlinkte Liste der Dateien. Je nach 
Dateioperation sind bestimmte Datenoperationen nun effizient und andere 
wiederum ineffiztienter als bei einer FAT. Das Auffinden/Öffnen einer 
Datei ist zb. langsammer als bei einer FAT. Diese Operation ist aber auf 
einer SD-Karte benutzt in einer MCU diejenige Operation die am 
seltensten vorkommen sollte.

Die zeitkritischen Momente (Spannungsversorgung/Reset etc) beschränken 
sich dann nur auf die Zeitspanne wenn man die SD Karte schreibt. 
Ansonsten sind die Daten konsistent.

Gruß Hagen

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Übrigens könnte man diese "Datei-Header-Pages" beim Anlegen einer neuen 
Datei so verlinken das man diese Pages immer per Dateinamen sortiert 
verlinkt. Das ist bei doppelt verlinkten Datenstrukturen eine einfache 
Operation die dann 3 Pages verändern würde. Vorteil ist es nun das man 
wiederum per binärer Suche sehr schnell eine Datei auffinden kann.

Allerdings, je mehr man verlinkt desto höher wird die Wahrscheinlichkeit 
das diese Verlinkungen fehlerhaft werden können und damit die gesamte 
Struktur zerstören könnten. Das sollte man von vornherein 
berücksichtigen. Zb. eben je nach Operation Links als erstes oder 
letztes schreiben, oder Prüfcodes vorsehen.

Gruß Hagen

Autor: Simon K. (simon) Benutzerseite
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
So, ich habe mich mal hingesetzt und das mit den Bitmap-pages verworfen.

Herausgekommen ist dabei das, was im Anhang ist.

Es wird eine pLastPage Variable gehalten, die die Adresse des Vorgängers 
der "letzten Aktion" beinhaltet.
Das hat zur Folge, dass bei zum Beispiel bei fünf aufeinanderfolgenden 
Allokationen immer jeweils eine Page übersprungen wird, die ebenfalls 
hätte allokiert werden könnte. Am Ende der single-linked-list 
angekommen, fängt die Allokationsfunktion wieder von vorne an.
Das hat den Sinn, dass die jeweils nächste allokierte Page eine Page 
ist, dessen letzter Schreibzugriff am längsten her sein sollte. (Soweit 
ich mich jetzt nicht vertue).

Was mich noch ein bisschen stört:
Es sind mehrere Page-reads und Page-writes nötig pro Allokation -> :-/

Ihr könnt euch das ja mal anschauen und ggf. Bugs reporten.

EDIT: Ups, die Dokumentation ist natürlich jetzt obsolet...

Autor: Simon K. (simon) Benutzerseite
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
n Bisschen Bugfixing und noch ein paar Sachen aus der ToDo Liste habe 
ich noch bearbeitet.

Neue Doku ist in Mache ;)

Autor: Simon K. (simon) Benutzerseite
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Siehe ToDo.txt :-)

PS: Ich werde neue Versionen der einfachheithalber einfach mal auf 
meiner HP uppen:

http://klinkerstein.m-faq.de/index.php?dir=/Micro%...

(Nein, das ist keine klickibunti augenkrebs-grün-hintergrund homepage 
;))

Autor: Simon K. (simon) Benutzerseite
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Ein paar Bugfixes. Läuft auch jetzt auf dem AVR (Bisher läuft mein 
Webserver mit dem uFS sehr sehr gut.)

Zum kopieren von Dateien gibt es jetzt "ufs_SD", dass Dateien von der 
Festplatte über die API von Windows über einen Kartenleser auf eine SD 
Karte schreiben kann.

PS: Die AVR Version adde ich später.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.