Post on 28-Jan-2021
transcript
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
Flash-DateisystemeVortrag im Rahmen des Seminars
”Ausgewählte Themen in
Hardwareentwurf und Optik“
Jakob Haufe
ZITI - Institut für Technische InformatikUniversität Heidelberg
18. Dezember 2009
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
FlashNORNANDVergleichFlash Translation Layer
Flash-DateisystemeAllgemeinesJFFSYAFFSLogFSUBIUBIFS
Fazit
Quellen
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
NORNANDVergleichFlash Translation Layer
Grundprinzip
Word LineControl Gate
SourceLine
N N
Float Gate
Bit Line
P
I Tunneleffekt(Quantenmechanik)
I Elektronen im FGbeeinflussen VTH
I Kapazitätserhöhung durchunterschiedliche Ladung(MLC)
I”Abnutzung“ durch
hängenbleibende Elektronenim FG
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
NORNANDVergleichFlash Translation Layer
NOR: Aufbau
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
NORNANDVergleichFlash Translation Layer
NOR: Eigenschaften
I Schreiben byte- oder wortweise
I Löschen pro Block
I Keine Defekte ab Werk
I Lesen wie (EEP)ROM
I eXecute-in-Place möglich
I Nur bis 1Gbit verfügbar (2009)
I Zugriffszeit ca. 80ns
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
NORNANDVergleichFlash Translation Layer
NAND: Aufbau
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
NORNANDVergleichFlash Translation Layer
NAND: Eigenschaften
I Kompakter als NOR ( 25 der Fläche lt. Toshiba)
I Zugriff kommandobasiert
I Aufteilung in Blöcke (256 KB), Seiten (4096B) und evtl.Unterseiten
I Pro Seite außerdem”Spare Area“ für OOB-Daten
I Schreiben pro (Unter-)Seite, Löschen pro Block
I Defekte Blöcke ab Werk (markiert)
I Zugriffszeit: 25µs (wahlfrei), 25ns (sequentiell)
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
NORNANDVergleichFlash Translation Layer
NOR vs. NAND: Toshiba vergleicht
Toshiba NAND vs. NOR Flash Memory Technology Overview Page 2
Fig. 1 Comparison of NOR and NAND Flash
File Storage Use
Code Execution
Read Speed
Write Speed
Capacity
NORNAND
Cost-per-bit
Active Power (*)
Standby Power
High
Low
Hard
Easy
Easy
High
Low
High
High
Low
HighLow
Low
(*) : Dependant on how memory is used.NOR is typically slow on writes and consumes more power than NAND.NOR is typically fast on reads, which consume less power.
The History of Flash Memory As a recognized pioneer in flash technology, Toshiba was a principal innovator of both NOR-type and NAND-type Flash technology in the 1980’s. These new memories were developed to address the need for a non-volatile memory that is easily reprogrammable within a system. Some kind of non-volatile memory is necessary for computing systems so that the system does not erase all data every time it is powered down, or following a power failure. Both NOR and NAND Flash systems are electrically erasable solutions, and can write and erase data many times, but do not lose stored data when the power is turned off. NAND and NOR Flash Memory Architecture In the internal circuit configuration of NOR Flash, the individual memory cells are connected in parallel, which enables the device to achieve random access. This configuration enables the short read times required for the random access of microprocessor instructions. NOR Flash is ideal for lower-density, high-speed read applications, which are mostly read only, often referred to as code-storage applications. NAND Flash was developed as an alternative optimized for high-density data storage, giving up random access capability in a tradeoff to achieve a smaller cell size, which translates to a smaller chip size and lower cost-per-bit. This was achieved by creating an array of eight memory transistors connected in a series. Utilizing the NAND Flash architecture’s high storage density and smaller cell size, NAND Flash systems enable faster write and erase by programming blocks of data. NAND Flash is ideal for low-cost, high-density, high-speed program/erase applications, often referred to as data-storage applications.
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
NORNANDVergleichFlash Translation Layer
Flash Translation Layer
I Emuliert Blockdevice auf Flash-Speicher
I Bemüht sich um Wear-Levelling
I Findet sich in Speicherkarten (SD, CF, etc.), USB-Sticks,SSDs
I Nahezu unmöglich herauszufinden, welche Blöcke frei sind
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
AllgemeinesJFFSYAFFSLogFSUBIUBIFS
Flash-Dateisysteme
I Motivation
I Allgemeines
I JFFS und JFFS2
I LogFS
I YAFFS
I UBI und UBIFS
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
AllgemeinesJFFSYAFFSLogFSUBIUBIFS
Motivation
I Wear-Levelling
I Beachtung von Seiten- und Blockgrenzen
I Konsistenz nach Stromausfall
I In-place Updates nicht sinnvoll umsetzbar
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
AllgemeinesJFFSYAFFSLogFSUBIUBIFS
Log Structured File System - Konzept
I Medium als Ringpuffer
I Aufräumen wenn voll → Garbage CollectorI Erste Implementation 1992, John Ousterhout und Mendel
Rosenblum für Sprite OS (Berkeley)
I Vorteilhafte für schreiblastige Anwendungen
I Konzept heutzutage wahrscheinlich in den meisten SSDsverwendet
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
AllgemeinesJFFSYAFFSLogFSUBIUBIFS
Log Structured File System - Arbeitsprinzip
Benutzer schreibt Datei A
I 10 ”X”nach Offset 0
I 5 ”Z”nach Offset 10
I 5 ”Y”nach Offset 5
Medium
I A:0:10:XXXXXXXXXX
I A:10:5:ZZZZZ
I A:5:5:YYYYY
Datei A:
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
AllgemeinesJFFSYAFFSLogFSUBIUBIFS
Log Structured File System - Arbeitsprinzip
Benutzer schreibt Datei A
I 10 ”X”nach Offset 0
I 5 ”Z”nach Offset 10
I 5 ”Y”nach Offset 5
Medium
I A:0:10:XXXXXXXXXX
I A:10:5:ZZZZZ
I A:5:5:YYYYY
Datei A:
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
AllgemeinesJFFSYAFFSLogFSUBIUBIFS
Log Structured File System - Arbeitsprinzip
Benutzer schreibt Datei A
I 10 ”X”nach Offset 0
I 5 ”Z”nach Offset 10
I 5 ”Y”nach Offset 5
Medium
I A:0:10:XXXXXXXXXX
I A:10:5:ZZZZZ
I A:5:5:YYYYY
Datei A: XXXXXXXXXX
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
AllgemeinesJFFSYAFFSLogFSUBIUBIFS
Log Structured File System - Arbeitsprinzip
Benutzer schreibt Datei A
I 10 ”X”nach Offset 0
I 5 ”Z”nach Offset 10
I 5 ”Y”nach Offset 5
Medium
I A:0:10:XXXXXXXXXX
I A:10:5:ZZZZZ
I A:5:5:YYYYY
Datei A: XXXXXXXXXX
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
AllgemeinesJFFSYAFFSLogFSUBIUBIFS
Log Structured File System - Arbeitsprinzip
Benutzer schreibt Datei A
I 10 ”X”nach Offset 0
I 5 ”Z”nach Offset 10
I 5 ”Y”nach Offset 5
Medium
I A:0:10:XXXXXXXXXX
I A:10:5:ZZZZZ
I A:5:5:YYYYY
Datei A: XXXXXXXXXXZZZZZ
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
AllgemeinesJFFSYAFFSLogFSUBIUBIFS
Log Structured File System - Arbeitsprinzip
Benutzer schreibt Datei A
I 10 ”X”nach Offset 0
I 5 ”Z”nach Offset 10
I 5 ”Y”nach Offset 5
Medium
I A:0:10:XXXXXXXXXX
I A:10:5:ZZZZZ
I A:5:5:YYYYY
Datei A: XXXXXXXXXXZZZZZ
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
AllgemeinesJFFSYAFFSLogFSUBIUBIFS
Log Structured File System - Arbeitsprinzip
Benutzer schreibt Datei A
I 10 ”X”nach Offset 0
I 5 ”Z”nach Offset 10
I 5 ”Y”nach Offset 5
Medium
I A:0:10:XXXXXXXXXX
I A:10:5:ZZZZZ
I A:5:5:YYYYY
Datei A: XXXXXYYYYYZZZZZ
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
AllgemeinesJFFSYAFFSLogFSUBIUBIFS
Log Structured File System - Arbeitsprinzip
Benutzer schreibt Datei A
I 10 ”X”nach Offset 0
I 5 ”Z”nach Offset 10
I 5 ”Y”nach Offset 5
Medium
I A:0:10:XXXXXXXXXX
I A:10:5:ZZZZZ
I A:5:5:YYYYY
Datei A: XXXXXYYYYYZZZZZ
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
AllgemeinesJFFSYAFFSLogFSUBIUBIFS
Garbage Collector
I Löscht leere Blöcke
I Fasst teilgefüllte Blöcke zusammen
I Wird (spätestens) aufgerufen wenn Medium fast(!) voll
I Strategie hat starken Einfluß auf Performance
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
AllgemeinesJFFSYAFFSLogFSUBIUBIFS
Journalling Flash File System
I Entwickelt von Axis
I 1999 für Linux 2.0 unter der GPL freigegeben
I Log structured file system
I”Perfektes“ Wear-Levelling
I Keine Kompression, keine Hardlinks
I Komplettes Einlesen beim Mounten
I Hoher RAM-Bedarf
I Ursprüngliche Implementation unvollständig
Quelle: http://sourceware.org/jffs2/jffs2.pdf
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
AllgemeinesJFFSYAFFSLogFSUBIUBIFS
JFFS2 (1)
I Weiterentwicklung durch RedHat
I Anstoß war der Wunsch nach Kompression
I Berücksichtigt Blockgrenzen
I Verschiedene”node types“
I Abwärtskompatibel (compatibility bitmask)
I RAM-Bedarf verbessert, aber noch hoch
I Unklar, ob GC frei von Deadlocks
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
AllgemeinesJFFSYAFFSLogFSUBIUBIFS
JFFS2 (2)
I Kein striktes LFS mehr
I GC arbeitet pseudozufällig, daher unpassend für MLC-Flashs
I Mehrere Listen, darunter: clean list, dirty list, free list, u.a.
I EBS - Erase Block Summary: Verkürzt Mount-Zeit(RWCOMPAT DELETE)
I Sinnvoll bis ca. 64MB
I 13k SLOC
Quelle: http://www.linux-mtd.infradead.org/faq/ubi.htmlQuelle: http://www.linux-mtd.infradead.org/doc/jffs2.htmlQuelle: http://sourceware.org/jffs2/jffs2-slides-transformed.pdf
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
AllgemeinesJFFSYAFFSLogFSUBIUBIFS
Ziele von JFFS3
I RAM-Verbrauch veringern und unabhängig von Flash-Größe
I Index auf den Flash verlagern
I Write-back cache
I Extended attributes
I ACLs
I Nebenläufigkeit: Lesen während GC, Zugriff während journalcommit
I Ersetzt durch UBI und UBIFS
Quelle: :pserver:anoncvs@cvs.infradead.org:/home/cvs
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
AllgemeinesJFFSYAFFSLogFSUBIUBIFS
Ziele von JFFS3
I RAM-Verbrauch veringern und unabhängig von Flash-Größe
I Index auf den Flash verlagern
I Write-back cache
I Extended attributes
I ACLs
I Nebenläufigkeit: Lesen während GC, Zugriff während journalcommit
I Ersetzt durch UBI und UBIFS
Quelle: :pserver:anoncvs@cvs.infradead.org:/home/cvs
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
AllgemeinesJFFSYAFFSLogFSUBIUBIFS
Yet Another Flash File System
I Entworfen für NAND
I Kritik an JFFS2: RAM-Bedarf, Mount-Zeiten
I Verwendet im T-Mobile G1 (Android)
I Verfügbar für Linux, eCOS, WinCE, pSOS (RTOS von WindRiver u.a.)
I 8k SLOC
Quelle: http://www.yaffs.net/yaffs-talk-slide-1-title
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
AllgemeinesJFFSYAFFSLogFSUBIUBIFS
YAFFS im Vergleich zu JFFS2
I Deutlich geringerer RAM-Bedarf, daher auch für große Flashs(max. 8 GB) sinnvoll
I Bei Flashs ≤ 64 MB ist JFFS2 sinnvollerI GC einfacher und schneller, daher bessere
Schreib-Performance
I Keine Kompression
I Nicht sinnvoll auf NOR-Flash
Quelle: http://www.yaffs.net/comparison-yaffs-vs-jffs
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
AllgemeinesJFFSYAFFSLogFSUBIUBIFS
LogFS
I Entwickelt insbesondere für große Flashs
I Will Probleme von JFFS2 und YAFFS lösen
I Benutzt Baumstrukturen ähnlich zu ext2
I Vollständig seit November 2008 (Testsuite)
I Jedoch:”LogFS is not ready yet.“ (FAQ)
I Noch nicht als Root-FS verwendbar (Bugliste)
I GC fehlerhaft wenn FS voll (Bugliste)
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
AllgemeinesJFFSYAFFSLogFSUBIUBIFS
Wandering trees
A
B C
D E
F G
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
AllgemeinesJFFSYAFFSLogFSUBIUBIFS
Wandering trees
A
B C
D E
F G
G’⇒ E’
F G’
⇒ C’
D E’
F G’
⇒ A’
B C’
D E’
F G’
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
AllgemeinesJFFSYAFFSLogFSUBIUBIFS
UBI SUNT DATA? - Unsorted Block Images
I Abstraktion über MTD (PEBs ↔ LEBs)I Trennung von Flash-Management und Dateisystem
I Wear-Levelling
I Bad-Block-Handling
I sozusagen LVM für MTD
I UBI ist kein FTL
I 7.5k SLOC
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
AllgemeinesJFFSYAFFSLogFSUBIUBIFS
Unterschiede zu”rohem“ MTD
I Wear-Levelling über ganzen Flash
I UBI-Volumes statt MTD-Partitionen
I Kann auch in einer MTD-Partition benutzt werden(Bootloader)
I gluebi emuliert MTD auf UBI (ermöglicht z.B. JFFS2 aufUBI)
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
AllgemeinesJFFSYAFFSLogFSUBIUBIFS
Logische und Physikalische Eraseblocks
Adrian Hunter, Artem Bityutskiy (Битюцкий Артём) 18
UBI operation exampleUBI operation example
UBI volume
1. Write data to LEB0a) Map LEB0 to PEB1
MTD device
2. Write data to LEB1, LEB4
PEB0 PEB1 PEB2 PEB3 PEB4 PEB5 PEB6
LEB0 LEB1 LEB2 LEB3 LEB4 LEB5
3. Erase LEB1a) Un-map LEB1 ...b) Erase PEB4 in background
4. Write data to LEB1
b) Write the data
return
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
AllgemeinesJFFSYAFFSLogFSUBIUBIFS
Eraseblocks
I Erste (Unter-)Seiteenthält Erase Counter
I Zweite (Unter-)Seiteenthält VolumeHeader
I Alle Header werdenbei Initialisierungeingelesen (schnellerals JFFS2)
struct ubi ec hdr {ubi32 t magic; // "UBI#"
uint8 t version;
uint8 t padding1[3];
ubi64 t ec;
ubi32 t vid hdr offset;
ubi32 t data offset;
uint8 t padding2[36];
ubi32 t hdr crc;
} attribute ((packed));
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
AllgemeinesJFFSYAFFSLogFSUBIUBIFS
UBI Volumes
I Volume-IDs 0-65535
I reserviert:65280-65535
I derzeit nur 0-127 fürBenutzer
struct ubi vid hdr
ubi32 t magic; // "UBI!"
uint8 t version;
uint8 t vol type;
uint8 t copy flag;
uint8 t compat;
ubi32 t vol id;
ubi32 t lnum;
ubi32 t leb ver;
ubi32 t data size;
ubi32 t used ebs;
ubi32 t data pad;
ubi32 t data crc;
uint8 t padding1[12];
uint8 t ivol data[UBI VID HDR IVOL DATA SIZE];
ubi32 t hdr crc;
attribute ((packed));
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
AllgemeinesJFFSYAFFSLogFSUBIUBIFS
Layout Volume
I ID 65280 (reserviert),immer LEB 0
I Name ”ubi-layout”
I Enthält Informationenüber alle Volumes aufdiesem UBI-Device
I Bei VerlustRekonstruktion durchDevice-Scan möglich
struct ubi vol tbl record {ubi32 t reserved pebs;
ubi32 t alignment;
ubi32 t data pad;
uint8 t vol type;
uint8 t padding1;
ubi16 t name len;
uint8 t name[UBI VOL NAME MAX + 1];
uint8 t padding2[24];
ubi32 t crc;
} attribute ((packed));
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
AllgemeinesJFFSYAFFSLogFSUBIUBIFS
Wear Levelling
I Überprüfung bei jedem Löschvorgang
I Wenn EC(gelöschter Block) = min(EC) + 4096, dann wirdauf einen Block mit min(EC) verschoben
I Sortierte Liste freier Blöck im RAM
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
AllgemeinesJFFSYAFFSLogFSUBIUBIFS
UBIFS
I Write-back support
I Kompression mit zlib (klein) oder lzo (schnell)
I Index (B+-Baum) auf dem Flash
I Nutzdaten in den Blättern
I Nur das Journal muß beim Mounten gelesen werden
I 21k SLOC
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
Fazit
I JFFS2 ist das ext2 des Flash
I YAFFS2 ist schlank
I LogFS ist noch nicht fertig
I UBI(FS) hat interessante Konzepte, jedoch viel Code
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
Vielen Dank für Ihre Aufmerksamkeit!
Jakob Haufe Flash-Dateisysteme
ÜberblickFlash
Flash-DateisystemeFazit
Quellen
Sonstige Quellen
I http://en.wikipedia.org/wiki/Flash memory
I http://en.wikipedia.org/wiki/JFFS
I http://en.wikipedia.org/wiki/YAFFS
I http://developer.axis.com/old/software/jffs/
I http://lwn.net/Articles/234441/
I http://www.linux-mtd.infradead.org/doc/general.html
I http://www.linux-mtd.infradead.org/faq/general.html
I http://www.logfs.net/
I
http://www.kemt.fei.tuke.sk/predmety/VlozeneSystemyAutomobilov/ materialy/Prednasky/2/NANDvsNOR.pdf
Jakob Haufe Flash-Dateisysteme
ÜberblickFlashNORNANDVergleichFlash Translation Layer
Flash-DateisystemeAllgemeinesJFFSYAFFSLogFSUBIUBIFS
FazitQuellen