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.
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.
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!
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.
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).
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
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
>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.
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.
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?
> 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.
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
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.
>>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
Ü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
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...
n Bisschen Bugfixing und noch ein paar Sachen aus der ToDo Liste habe ich noch bearbeitet. Neue Doku ist in Mache ;)
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%20File%20System (Nein, das ist keine klickibunti augenkrebs-grün-hintergrund homepage ;))
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.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.