PandoraSuechtig
Member
- Joined
- Oct 7, 2008
- Messages
- 456
Da uns Thrake den "Weihnachtsupdate vonCraigx" Thread zugemacht hat, da das Thema dort wirklich OT war, werden wir (ich, wejp, grond) uns brav im eigenen Thread zum Thema (Wie schon von Mae vorgeschlagen) weiter unterhalten 
Für die meisten Pandora-Fans dürfte das Thema belanglos sein. Aber vielleicht hat der eine oder andere sogar Erfahrung damit und kann uns die Diskussion mit einigen Einsichten vereinfachen.
Die Diskussion fing damit an :
http://forum.gp2x.de/viewtopic.php?f=23&t=6424&start=73
Ab da sind wir in die Tiefen von Wear Leveling Algorithmen (WLA) in flashes abgetaucht...
Wir konnten vor allem eine Frage nicht klären: Sind die WLA in Flashes Filesystem sensitiv?? also funktionieren sie z.B. nur FAT effektiv?? Da jeder Hersteller seinen WLA als Betriebsgeheimnis hütet und jeder wohl seinen eigenen hat, wäre hier ein Insider sehr hilfreich? Wer hilft uns Inkognito weiter?
EDIT BY Thrake:
Unabhängig davon ob wir von einem Controller reden, der die freien Blöcke im FS beachtet oder seine eigenen freien Blöcke managed, in beiden Fällen wird nach einmal 2^(n+m) Bytes Schreiben die Fragmentierung anfangen. Denn die Liste der freien Blöcke wird jeweils um den letzten freigegebenen Block ergänzt und die Freigaben können zufällig erfolgen, also wird die Liste ab dem ersten Eintrag nach 2^(n+m) Bytes Schreibzugriffen ungeordnet sein. Es geht mir nicht darum, dass wenn das Medium fast voll ist, die Knappheit der freien Blöcke das Problem wäre (Falls wir von freien Blöcken im FS reden), sondern, dass die Liste der freien Blöcke nur ganz am Anfang garantiert nach der physikalischen Adresse der Blöcke sortiert ist.
Tut mir leid Gond, ich will echt nicht böse sein, aber ich zweifle an deinem Vorschlag.
Soviel ich schon im Vorfeld sinniert habe über mögliche WL Algorithmen, die das Flash möglichst wenig abnutzen, habe ich immer eine Sache vermieden, da ich keine gute Antwort drauf weiss: Wie wird ein "möglichst wenig" benutzter Block ermittelt? Da das Führen einer Datenstruktur für ein schnelles oder optimales (der am wenigsten Benutzte Block) Auffinden immer in einem oder mehreren Blocks landen würde, die dann besonders belastet werden, denke ich, dass hier "suboptimal" ad hoc, wenn einer benötigt wird, sequentiell nach einem "ausreichend gutem" Kandidaten gesucht wird. Falls die Ersetzung eines Blocks wie weiter oben vorgeschlagen nur etwa jeden 1024. Schreibzugriff auf denselben ausgetauscht würde, könnte in einem Bereich z.B. ein Offset (und Statistiken??) gespeichert werden welches der letzte gefundene Block war und bei der nächsten sequentiellen Suche wird ab dem folgenden fortgefahren.
Mit der suboptimalen Lösung wären trotzdem sehr viele Schreibzugriffe möglich, bevor ein Abnutzungsproblem auftaucht. Nehmen wir an, wegen der Verteilung der Schreibzugriffe würde jeder 20. auf denselben Block fallen (das wär schon eine sehr schlechte Verteilung), dann wäre nach ca. 20000 Schreibzugriffen auf das Medium ein Ersetzen nötig. Nur dann würde eine kleine Performancebusse wegen der Suche nach einem freien Block und dem Ersetzen anfallen und die Blöcke mit den Statistiken würden 20000x10000 = 200Mio Schreibzugriffe auf das Medium aushalten.
Jetzt fallen mir noch einige Optimierungen ein:
Für die meisten Pandora-Fans dürfte das Thema belanglos sein. Aber vielleicht hat der eine oder andere sogar Erfahrung damit und kann uns die Diskussion mit einigen Einsichten vereinfachen.
Die Diskussion fing damit an :
http://forum.gp2x.de/viewtopic.php?f=23&t=6424&start=73
Ab da sind wir in die Tiefen von Wear Leveling Algorithmen (WLA) in flashes abgetaucht...
Wir konnten vor allem eine Frage nicht klären: Sind die WLA in Flashes Filesystem sensitiv?? also funktionieren sie z.B. nur FAT effektiv?? Da jeder Hersteller seinen WLA als Betriebsgeheimnis hütet und jeder wohl seinen eigenen hat, wäre hier ein Insider sehr hilfreich? Wer hilft uns Inkognito weiter?
EDIT BY Thrake:
Nein, das eine ist eine Tabelle von Adresspaaren, das andere eine Liste von einzelnen Adressen (die Zuordnung erfolgt durch die Position in der Liste). Das erste lässt viel Interpretationsspielraum und erwähnt Adress"paare". Eine Lookuptable mit Adressen hätte ich noch als equivalent verstanden.grond said:Das ist identisch mit dem, was ich meinte: die physikalische Adresse ist Funktion der logischen Adresse, die Abbildung ist eineindeutig und bijektiv, d.h., Adresspaare werden gebildet.PandoraSuechtig said:Falsch. Eine einfache sequentielle Liste der physischen Adressen (die (logische Adresse/Blockgrösse[=2^n]) entspricht dem Index in dieser Tabelle) wär die banalste Lösung.grond said:Um eine physikalische Adresse auf einen anderen Block zu mappen, muss es eine Tabelle geben, die Adresspaare beinhaltet, die einander zugeordnet sind.
Dann wars nur ein Schreibfehler.grond said:Das meinte ich. s/Block/Byte.PandoraSuechtig said:Blödsinn. Die Adresse des Blocks besteht aus den x, die y addressieren ein bestimmtes Byte im Block.grond said:grond hat geschrieben:
Die tatsächliche Adresse eines Blocks setzt sich dann so zusammen: %xxxxxxxxxxyyyyyyyy. "x" bedeutet dabei ein Bit, das aus der Zuordnungstabelle gelesen wird, y ein Bit aus der unveränderten Eingangsadresse.
History hat denselben Haken wie deine Idee der "FreeList": Irgendwo auf dem Flash muss sie gespeichert werden, und wenn sie bei jedem Schreibzugriff angepasst werden muss (angeblich der Fall durch doppelte Schreibzugriffe), hat sie nach 10000 Schreibzugriffen auf das Medium selber schon 10000 Schreibzugriffe erfahren und wird als erstes ausfallen... Dafür hatte ich schon vorher die Idee aufgeführt, dass man WriteCounts pro Flashblock führt (Jeweils als Teil des Blocks) und nur nach je z.B. 1024 Schreibzugriffen auf dieselbe Zelle ein Austausch (und somit eine Anpassung des Blockmappings) erfolgt (worst case: nach 10 Mio Schreibzugriffen [je 1024 gebündelt auf denselben Block] auf das Medium hätte das Mapping 10000 Zugriffe erfahren).grond said:Meine Ausführungen beruhen auf der Annahme, dass der Controller wissen kann, ob ein Block im FS belegt ist oder nicht. Ich weiß nicht, ob das so ist. Wenn es nicht so ist, müssten grundsätzlich Daten zwischen Quelle und Ziel ausgetauscht werden, wodurch die Anzahl der Schreibzugriffe erst einmal in der Gesamtbilanz verdoppelt würde. Dann bliebe höchstens, besonders aktive Blocks festzustellen und nach einer bestimmten Anzahl Schreibzugriffe mit einem anderen Block zu tauschen. Dazu würde wohl eine Art "history" am einfachsten sein.PandoraSuechtig said:Zögert nur die Fragmentierung hinaus bis einmal 2^(n+m) Bytes (Fassungsvermögen des Mediums) auf das Medium geschrieben wurden. Also eine ziemlich mickrige Verzögerung...grond said:Dazu reicht es, den Adresseintrag für den gerade freigewordenen Block so zu verändern, dass er ganz ans Ende der Blockliste rutscht. Damit wird der Zeitabstand bis zu einem erneuten Beschreiben automatisch maximiert.
Unabhängig davon ob wir von einem Controller reden, der die freien Blöcke im FS beachtet oder seine eigenen freien Blöcke managed, in beiden Fällen wird nach einmal 2^(n+m) Bytes Schreiben die Fragmentierung anfangen. Denn die Liste der freien Blöcke wird jeweils um den letzten freigegebenen Block ergänzt und die Freigaben können zufällig erfolgen, also wird die Liste ab dem ersten Eintrag nach 2^(n+m) Bytes Schreibzugriffen ungeordnet sein. Es geht mir nicht darum, dass wenn das Medium fast voll ist, die Knappheit der freien Blöcke das Problem wäre (Falls wir von freien Blöcken im FS reden), sondern, dass die Liste der freien Blöcke nur ganz am Anfang garantiert nach der physikalischen Adresse der Blöcke sortiert ist.
Hmmm. Ich sehe eine rollende Liste und einen Offsetzeiger, ist das alles um was es geht? Anstatt die Liste ständig zu shiften mit einem Offsetzeiger zu arbeiten? Wenn dies nur die Liste der freien Blöcke sein soll, funktioniert das nicht, denn sie kann sich in der Länge ändern. Wenn es die Liste aller Blöcke ist, dann ginge es darum bei jedem Schreibvorgang den nächsten "zum Ersetzen zu verwendenden" Block sofort ermitteln zu können? Dies würde ein Ersetzen bei jedem Schreibzugriff erfordern? Dann wird das Flash jedesmal mit 2 Schreibzugriffen belastet und diese Liste + Basiszeiger (Offset) muss mit jedem Schreibzugriff upgedatet werden? Wie oben schon beschrieben wären nach 10'000 Schreibzugriffen auf das Medium zumindest der Block der den Offset speichert schon am Belastungslimit. Die Idee mit der rollenden Liste (soweit ich das richtig verstehe) hätte natürlich den Vorzug der optimalen gleichmässigen Abnutzung aller Blöcke in der Liste, aber in der Praxis klappt das nicht weil der Block, der den Offset enthält jedes mal upgedatet werden würde. Dazu kommt der doppelte Schreibzugriff.grond said:Anfangszustand: {1, 2, 3}, Basiszeiger = 0PandoraSuechtig said:Nun wirds mir unverständlich, genau genommen ergibt es für mich keinen Sinn. Basiszeiger von allen Adressen abziehen, zugleich soll eine Veränderung dieses Basiszeiger aber keine Anpassung aller Einträge zur Folge haben???grond said:Basiszeiger reichen, dessen Wert man von allen Adressen abzieht und der bei jeder Operation erhöht wird, so dass er immer auf den ersten freien Eintrag zeigt), man würde sich aber das Dekrementieren aller Einträge in der Zuordnungstabelle sparen, wenn ein Block auf den letzten Platz der freien Blöcke rutscht.
erste Verschiebung (erster physikalischer Block wird freigegeben): {4, 2, 3}, Basiszeiger = 1 (der erste physikalische Block rutscht logisch aufgrund der Erhöhung um Anzahl(Blöcke) = 3 nach hinten)
zweite Verschiebung (zweiter physikalischer Block wird freigegeben): {4, 5, 3}, Basiszeiger = 2
Will ich nun in den logischen Block 1 schreiben, muss ich alle Einträge minus den Basiszeiger rechnen und die Resultate mit der gewünschten logischen Adresse vergleichen. Da wir hier über Hardware reden, wäre das nahezu beliebig parallelisierbar. Allerdings für eine Blockgröße von 512 Bytes nicht praktisch realisierbar. Da müsste man schon mit größeren Blöcken arbeiten.
Tut mir leid Gond, ich will echt nicht böse sein, aber ich zweifle an deinem Vorschlag.
Soviel ich schon im Vorfeld sinniert habe über mögliche WL Algorithmen, die das Flash möglichst wenig abnutzen, habe ich immer eine Sache vermieden, da ich keine gute Antwort drauf weiss: Wie wird ein "möglichst wenig" benutzter Block ermittelt? Da das Führen einer Datenstruktur für ein schnelles oder optimales (der am wenigsten Benutzte Block) Auffinden immer in einem oder mehreren Blocks landen würde, die dann besonders belastet werden, denke ich, dass hier "suboptimal" ad hoc, wenn einer benötigt wird, sequentiell nach einem "ausreichend gutem" Kandidaten gesucht wird. Falls die Ersetzung eines Blocks wie weiter oben vorgeschlagen nur etwa jeden 1024. Schreibzugriff auf denselben ausgetauscht würde, könnte in einem Bereich z.B. ein Offset (und Statistiken??) gespeichert werden welches der letzte gefundene Block war und bei der nächsten sequentiellen Suche wird ab dem folgenden fortgefahren.
Mit der suboptimalen Lösung wären trotzdem sehr viele Schreibzugriffe möglich, bevor ein Abnutzungsproblem auftaucht. Nehmen wir an, wegen der Verteilung der Schreibzugriffe würde jeder 20. auf denselben Block fallen (das wär schon eine sehr schlechte Verteilung), dann wäre nach ca. 20000 Schreibzugriffen auf das Medium ein Ersetzen nötig. Nur dann würde eine kleine Performancebusse wegen der Suche nach einem freien Block und dem Ersetzen anfallen und die Blöcke mit den Statistiken würden 20000x10000 = 200Mio Schreibzugriffe auf das Medium aushalten.
Jetzt fallen mir noch einige Optimierungen ein:
- Einige wenige Byte (Adressen) kann der Controller sicher in einem kleinen (flüchtigen) Puffer (Register?) halten: Wenn er bei jedem Lesevorgang den WriteCount des Blocks beachtet, kann er sich so bei jedem Lesen eine winzige Liste mit den am wenigsten beschriebenen Blöcken merken (je Eintrag: WC+Adresse). Dies ist generell, welchen WL-Algorithmus wir auch immer annehmen, von Nutzen.
- Wenn beim Schreiben ein Block ersetzt werden soll, kann der auch in einen "TODO" Buffer. Sobald der IO pausiert, kann der Controller sich dann daran machen den/die TODOs im Buffer abzuarbeiten, also die Blöcke zu ersetzen. Wenn beim Schreiben mehr Blöcke anfallen, als dieser Puffer Platz hat, könnte ausnahmsweise (und nur dann) gleich während dem Schreiben die Ersetzung vollzogen werden oder der "am wenigsten brennende Fall" aus dem Puffer fallen? Das sollte den Geschwindigkeitseinbruch beim Schreiben minimieren.
- Genauso kann auch die sequentielle Suche nach guten Kandidaten für Ersatzblöcke in der IO losen Zeit erfolgen.