Flash-Dateisysteme - Vortrag im Rahmen des Seminars …ra.ziti.uni-heidelberg.de/pages/student_work/seminar/hws... · 2017. 9. 8. · UBI UBIFS Ziele von JFFS3 I RAM-Verbrauch veringern

ÜberblickFlash

Flash-DateisystemeFazit

Quellen

Flash-DateisystemeVortrag im Rahmen des Seminars

”Ausgewählte Themen in

Hardwareentwurf und Optik“

Jakob Haufe

ZITI - Institut für Technische InformatikUniversität Heidelberg

18. Dezember 2009

Jakob Haufe Flash-Dateisysteme

ÜberblickFlash


Quellen

FlashNORNANDVergleichFlash Translation Layer

Flash-DateisystemeAllgemeinesJFFSYAFFSLogFSUBIUBIFS

Fazit

Quellen


ÜberblickFlash


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 Kapazitätserhöhung durchunterschiedliche Ladung(MLC)

I”Abnutzung“ durch

hängenbleibende Elektronenim FG


ÜberblickFlash


Quellen


NOR: Aufbau


ÜberblickFlash


Quellen


NOR: Eigenschaften

I Schreiben byte- oder wortweise

I Löschen pro Block

I Keine Defekte ab Werk

I Lesen wie (EEP)ROM

I eXecute-in-Place möglich

I Nur bis 1Gbit verfügbar (2009)

I Zugriffszeit ca. 80ns


ÜberblickFlash


Quellen


NAND: Aufbau


ÜberblickFlash


Quellen


NAND: Eigenschaften

I Kompakter als NOR ( 25 der Fläche lt. Toshiba)

I Zugriff kommandobasiert

I Aufteilung in Blöcke (256 KB), Seiten (4096B) und evtl.Unterseiten

I Pro Seite außerdem”Spare Area“ für OOB-Daten

I Schreiben pro (Unter-)Seite, Löschen pro Block

I Defekte Blöcke ab Werk (markiert)

I Zugriffszeit: 25µs (wahlfrei), 25ns (sequentiell)


ÜberblickFlash


Quellen


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.


ÜberblickFlash


Quellen


Flash Translation Layer

I Emuliert Blockdevice auf Flash-Speicher

I Bemüht sich um Wear-Levelling

I Findet sich in Speicherkarten (SD, CF, etc.), USB-Sticks,SSDs

I Nahezu unmöglich herauszufinden, welche Blöcke frei sind


ÜberblickFlash


Quellen

AllgemeinesJFFSYAFFSLogFSUBIUBIFS

Flash-Dateisysteme

I Motivation

I Allgemeines

I JFFS und JFFS2

I LogFS

I YAFFS

I UBI und UBIFS


ÜberblickFlash


Quellen


Motivation

I Wear-Levelling

I Beachtung von Seiten- und Blockgrenzen

I Konsistenz nach Stromausfall

I In-place Updates nicht sinnvoll umsetzbar


ÜberblickFlash


Quellen


Log Structured File System - Konzept

I Medium als Ringpuffer

I Aufräumen wenn voll → Garbage CollectorI Erste Implementation 1992, John Ousterhout und Mendel

Rosenblum für Sprite OS (Berkeley)

I Vorteilhafte für schreiblastige Anwendungen

I Konzept heutzutage wahrscheinlich in den meisten SSDsverwendet


ÜberblickFlash


Quellen


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:


ÜberblickFlash


Quellen







Medium

I A:0:10:XXXXXXXXXX

I A:10:5:ZZZZZ

I A:5:5:YYYYY

Datei A: XXXXXXXXXX


ÜberblickFlash


Quellen







Medium

I A:0:10:XXXXXXXXXX

I A:10:5:ZZZZZ

I A:5:5:YYYYY

Datei A: XXXXXXXXXXZZZZZ


ÜberblickFlash


Quellen







Medium

I A:0:10:XXXXXXXXXX

I A:10:5:ZZZZZ

I A:5:5:YYYYY

Datei A: XXXXXYYYYYZZZZZ


ÜberblickFlash


Quellen


Garbage Collector

I Löscht leere Blöcke

I Fasst teilgefüllte Blöcke zusammen

I Wird (spätestens) aufgerufen wenn Medium fast(!) voll

I Strategie hat starken Einfluß auf Performance


ÜberblickFlash


Quellen


Journalling Flash File System

I Entwickelt von Axis

I 1999 fü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 Ursprüngliche Implementation unvollständig

Quelle: http://sourceware.org/jffs2/jffs2.pdf


ÜberblickFlash


Quellen


JFFS2 (1)

I Weiterentwicklung durch RedHat

I Anstoß war der Wunsch nach Kompression

I Berücksichtigt Blockgrenzen

I Verschiedene”node types“

I Abwärtskompatibel (compatibility bitmask)

I RAM-Bedarf verbessert, aber noch hoch

I Unklar, ob GC frei von Deadlocks


ÜberblickFlash


Quellen


JFFS2 (2)

I Kein striktes LFS mehr

I GC arbeitet pseudozufällig, daher unpassend für MLC-Flashs

I Mehrere Listen, darunter: clean list, dirty list, free list, u.a.

I EBS - Erase Block Summary: Verkü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


ÜberblickFlash


Quellen


Ziele von JFFS3

I RAM-Verbrauch veringern und unabhängig von Flash-Größe

I Index auf den Flash verlagern

I Write-back cache

I Extended attributes

I ACLs

I Nebenläufigkeit: Lesen während GC, Zugriff während journalcommit

I Ersetzt durch UBI und UBIFS

Quelle: :pserver:[email protected]:/home/cvs


ÜberblickFlash


Quellen


Yet Another Flash File System

I Entworfen für NAND

I Kritik an JFFS2: RAM-Bedarf, Mount-Zeiten

I Verwendet im T-Mobile G1 (Android)

I Verfügbar für Linux, eCOS, WinCE, pSOS (RTOS von WindRiver u.a.)

I 8k SLOC

Quelle: http://www.yaffs.net/yaffs-talk-slide-1-title


ÜberblickFlash


Quellen


YAFFS im Vergleich zu JFFS2

I Deutlich geringerer RAM-Bedarf, daher auch fü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


ÜberblickFlash


Quellen


LogFS

I Entwickelt insbesondere für große Flashs

I Will Probleme von JFFS2 und YAFFS lösen

I Benutzt Baumstrukturen ähnlich zu ext2

I Vollstä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)


ÜberblickFlash


Quellen


Wandering trees

A

B C

D E

F G


ÜberblickFlash


Quellen


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’


ÜberblickFlash


Quellen


UBI SUNT DATA? - Unsorted Block Images

I Abstraktion über MTD (PEBs ↔ LEBs)I Trennung von Flash-Management und Dateisystem

I Wear-Levelling

I Bad-Block-Handling

I sozusagen LVM für MTD

I UBI ist kein FTL

I 7.5k SLOC


ÜberblickFlash


Quellen


Unterschiede zu”rohem“ MTD

I Wear-Levelling ü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 (ermöglicht z.B. JFFS2 aufUBI)


ÜberblickFlash


Quellen


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


ÜberblickFlash


Quellen


Eraseblocks

I Erste (Unter-)Seiteenthält Erase Counter

I Zweite (Unter-)Seiteenthä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;


ubi32 t hdr crc;

} attribute ((packed));


ÜberblickFlash


Quellen


UBI Volumes

I Volume-IDs 0-65535

I reserviert:65280-65535

I derzeit nur 0-127 fü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 ivol data[UBI VID HDR IVOL DATA SIZE];

ubi32 t hdr crc;

attribute ((packed));


ÜberblickFlash


Quellen


Layout Volume

I ID 65280 (reserviert),immer LEB 0

I Name ”ubi-layout”

I Enthält Informationenüber alle Volumes aufdiesem UBI-Device

I Bei VerlustRekonstruktion durchDevice-Scan mö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];


ubi32 t crc;

} attribute ((packed));


ÜberblickFlash


Quellen


Wear Levelling

I Überprüfung bei jedem Löschvorgang

I Wenn EC(gelöschter Block) = min(EC) + 4096, dann wirdauf einen Block mit min(EC) verschoben

I Sortierte Liste freier Blöck im RAM


ÜberblickFlash


Quellen


UBIFS

I Write-back support

I Kompression mit zlib (klein) oder lzo (schnell)

I Index (B+-Baum) auf dem Flash

I Nutzdaten in den Blättern

I Nur das Journal muß beim Mounten gelesen werden

I 21k SLOC


ÜberblickFlash


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


ÜberblickFlash


Quellen

Vielen Dank für Ihre Aufmerksamkeit!


ÜberblickFlash


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


ÜberblickFlashNORNANDVergleichFlash Translation Layer

Flash-DateisystemeAllgemeinesJFFSYAFFSLogFSUBIUBIFS

FazitQuellen

Documents

Flash-Dateisysteme - Vortrag im Rahmen des Seminars …ra.ziti.uni-heidelberg.de/pages/student_work/seminar/hws... · 2017. 9. 8. · UBI UBIFS Ziele von JFFS3 I RAM-Verbrauch veringern