JFFS2
Z Wikipedii
Journalling Flash File System version 2 lub JFFS2 (nie mylić z systemem plików JFS) jest systemem plików o strukturze loga używanym w urządzeniach z pamięcią Flash. Jest następnikiem systemu plików JFFS. JFFS2 został włączony do jądra systemu Linux od wydania 2.4.10. JFFS2 jest również dostępny w programach rozruchowych eCos, RTOS oraz RedBoot.
Spis treści |
[edytuj] Charakterystyka
JFFS2 posiada następujące cechy:
- Wsparcie dla urządzeń NAND flash. Wymagało znacznej ilości pracy ze względu na fakt, że urządzenia NAND posiadają szeregowy interfejs weścia-wyjścia, a to uniemożliwia zastosowanie mapowania pamięci w celu jej odczytu.
- Linki "twarde". Ich istnienie w JFFS nie było możliwe ze względu na ograniczenia formatu, w jakich zapisywano "węzły" (w JFFS nie ma rozróżnienia między węzłem reprezentującym katalog a inodem).
- Kompresję. Dostępne są trzy algorytmy: zlib, rubin oraz rtime.
- Większą wydajność. W JFFS dysk traktowany jest jako log cykliczny, co powoduje wiele niepotrzebnych operacji wejścia-wyjścia. Dzięki algorytmowi odśmiecania w JFFS2 stają się one w większości niepotrzebne.
[edytuj] Projekt
[edytuj] Typy węzłów
Podobnie jak w przypadku systemu plików JFFS, zmiany w plikach oraz katalogach są "logowane" w pamięci flash w postaci "węzłów", przy czym w JFFS2 wyróżnia się ich trzy rodzaje:
- JFFS2_NODETYPE_INODE - reprezentuje i-węzeł; pełni rolę podobną do struct jffs_raw_inode w JFFS v1. Zawiera:
- pole version
- (opcjonalnie) dane, które mogą być skompresowane; rozmiar danych nie może być większy niż jedna strona (rozmiar strony właściwy dla docelowej platformy sprzętowej; podobnie kolejność bajtów)
I-węzeł jest usuwany, jeśli ostatni wpis w katalogu odnoszący się do i-węzła został odlinkowany (usunięty) oraz gdy zamknięte zostały wszystkie deskryptory odnoszące się do i-węzła.
- JFFS2_NODETYPE_DIRENT - reprezentuje wpis w katalogu, inaczej: dowiązanie do i-węzła. Zawiera:
- pole vesion
- numer i-węzła katalogu, w którym znajduje się dowiązanie
- nazwa dowiązania
- numer i-węzła, do którego odnosi się dowiązanie
Usunięcie dowiązania (wpisu w katalogu) polega na zapisaniu węzła typu JFFS2_NODETYPE_DIRENT z tą samą nazwą, co usuwane dowiązanie, lecz z numerem i-węzła, do którego odnosi się dowiązanie, równym zero (i, oczywiście, zwiększonym polem version.
- JFFS2_NODETYPE_CLEANMAKER - węzeł tego typu służy do oznaczenia prawidłowo wyczyszczonego bloku. Gdy operacja czyszczenia bloku zakończy się pomyślnie, do bloku zapisywany jest jeden węzeł tego typu.
Tutaj również, tak jak w JFFS, węzły rozpoczynają swój cykl życia jako "ważne", po czym, gdy w innym miejscu powstanie nowsza ich wersja, zostają "unieważnione".
[edytuj] Bloki
W przeciwieństwie do JFFS, w JFFS2 nie ma koncepcji cyklicznego loga. W jego miejsce pojawiły się bloki, jednostki tych samych rozmiarów, co usuwalny segment w pamięciach flash. Bloki są pojedynczo wypełniane i-węzlami, od dołu ku górze. Bloki są ze sobą powiązane w kilku listach:
- dirty_list: lista bloków, z których każdy posiada co najmniej jeden węzeł do odśmiecenia (unieważniony)
- clean_list: lista bloków, których wszystkie węzły są ważne
- free_list: w nowo utworzonym (czystym) systemie plików składa się z bloków posiadających tylko jeden węzeł-znacznik, który mówi, że zawierający go blok został poprawnie wyczyszczony
[edytuj] Garbage collection
W tle działa garbage collector, który, wykorzystując powyższe listy bloków, przekształca bloki "brudne" w bloki "wolne". Robi to poprzez skopiowanie "ważnych" węzłów znajdujących się w "brudnych" blokach do nowych bloków, pomijając przy tym węzły "unieważnione". Następnie oznacza "brudne" bloki w specjalny sposób tak, aby oznaczały bloki "wolne", a następnie usuwa je (oznaczanie jest stosowane w celu uniknięcia problemów w przypadku, gdy podczas operacji usuwania zniknie zasilanie).
[edytuj] Wybór bloku do odśmiecenia
Garbage collector wyznacza blok do odśmiecenia na podstawie licznika jiffies: : jeśli jiffies % 100 (dzielenie modulo 100) da w wyniku wartość niezerową, odśmiecany jest blok z listy dirty_list; gdy wynikiem jest zero, odśmiecany jest blok z listy clean_list. Jest to ważna optymalizacja: bloki z ważnymi węzłami nie są, jak w przypadku jffs, odśmiecane równie często, jak bloki, w których są zdezaktualizowane węzły, a jedynie w jednym przypadku na sto; ograniczona jest więc liczba niepotrzebnych operacji przepisywania danych z miejsca na miejsce na nośniku, a jednocześnie, dzięki występującemu od czasu do czasu wyborowi bloku z listy clean_list, zapewnione jest równoważenie zużycia nośnika.
[edytuj] Działanie
Węzły zapisywane są po kolei do bieżącego bloku; gdy ten zostanie zapełniony, brany jest nowy blok z listy free_list. Gdy na liście free_list zaczyna brakować bloków, włączany jest garbage collector, którego zadaniem jest przeniesienie ważnych węzłów ze starszego bloku do nowszego, co umożliwi wyczyszczenie starszego bloku i odzyskanie w ten sposób bloku do ponownego użycia. Węzły nie są przechowywane w pamięci przez cały czas; choć przy montowaniu budowana jest pełna mapa i-węzłów, to podczas działania modyfikowane są jedynie pewne struktury w pamięci (ograniczonych rozmiarów).
[edytuj] Struktura jffs2_inode_cache
Dla każdego i-węzła na nośniku w pamięci przechowywana jest struktura struct jffs2_inode_cache, która przechowuje:
- numer i-węzła
- liczbę dowiązań do i-węzła
- wskaźnik do początku listy zawierającej fizyczne węzły dotyczące i-węzła
Struktury te są przechowywane w tablicy haszującej o bardzo prostej funkcji haszującej (numer i-węzła dzielony modulo długość tablicy), dzięki czemu zapewniony jest równomierny rozkład tych struktur w tablicy .
[edytuj] Struktura jffs2_raw_node_ref
Dla każdego węzła przechowywana jest w pamięci struktura jffs2_raw_node_ref, która przechowuje:
- wskaźnik do struktury jffs2_raw_node_ref reprezentującej następny węzeł w fizycznym bloku (next_phys)
- wskaźnik do struktury jffs2_raw_node_ref reprezentującej następny węzeł odnoszący się do tego samego i-węzła (next_in_ino)
- przesunięcie węzła (flash_offset, dwa ostatnie bity są używane jako flagi: flaga, czy węzeł jest unieważniony i flaga nieużywana)
- całkowitą długość węzła (totlen)
[edytuj] Wykorzystanie struktur
Garbage collector musi na podstawie struktury jffs2_raw_node_ref odnaleźć i-węzeł, którego ta struktura dotyczy. Jest to możliwe dzięki temu, że na końcu listy wskaźników wskazujących na struktury jffs2_raw_node_ref reprezentujące kolejne węzły odnoszące się do tego samego węzła, nie umieszczono wartości NULL wprost, tylko wskaźnik do struktury jffs2_inode_cache (reprezentującej szukany i-węzeł). Struktura ta, pod przesunięciem, pod którym kod przechodzący po strukturach jffs2_raw_node_ref spodziewałby się wkaźnika do kolejnej struktury jffs2_raw_node_ref lub wartości NULL, posiada właśnie wartość NULL, dzięki czemu kod przeszukujący wie, że wystarczy zrzutować wskaźnik na odpowiedni typ (jffs2_inode_cache), by móc odczytać numer i-węzła i inne potrzebne dane.
W trakcie działania do metody systemu plików read_inode() przekazywany jest numer i-węzła, w jej wyniku zaś zostaje wypełniona odpowiednimi informacjami struktura danych struct inode. Odbywa się to w następujący sposób:
- na podstawie numeru i-węzła wyszukiwana jest w tablicy haszującej odpowiednia struktura jffs2_inode_cache
- z tej struktury odczytywany jest wskaźnik na listę węzłów odpowiadającą szukanemu i-węzłowi
- węzły na liście są odwiedzane po kolei
- z każdego węzła odczytywane są informacje o fizycznym położeniu fragmentu danych należących do i-węzła
- na podstawie tych informacji budowana jest pełna struktura i-węzła
- struktura ta pozostaje w pamięci do czasu, gdy jądro, zmuszone brakiem pamięci, decyduje o wyczyszczeniu pamięci, w której przechowywane są pełne i-węzły; w pamięci pozostają jedynie referencje do węzłów (jffs2_raw_node_ref) i małe struktury jffs2_inode_cache dla i-węzłów (czyli oryginalne struktury danych w JFFS2).
[edytuj] Wady
- Wszystkie węzły muszą być przeskanowane w czasie montowania. Ten proces jest dość wolny, co staje się coraz większym problemem, ponieważ urządzenia flash mają coraz większe pojemności .
- Zapisywanie wielu małych bloków z danymi może doprowadzić do tego, że zajmą one więcej miejsca na nośniku, niż w przypadku, gdyby algorytmy kompresji nie były stosowane. Programy powinny w związku z tym używać przy zapisie dużych buforów.
- Nie można stwierdzić, ile dokładnie wolnej przestrzeni znajduje się na urządzeniu; zależy to zarówno od stopnia kompresji danych, jak i kolejności ich zapisu.
[edytuj] Patrz także:
- system plików
- JFFS
- YAFFS
[edytuj] Źródła
- Woodhouse, David. JFFS: The Journalling Flash File System.
