JFFS2

Journalling Flash File System version 2 lub JFFS2 (nie mylić z systemem plików JFS) – system plików o strukturze dziennika używany w urządzeniach z pamięcią Flash. Jest następcą 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.

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.

Projekt

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 bloku kasowania)

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 version
    • 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 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”.

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 blok kasowania 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

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).

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.

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).

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:

Struktura jffs2_inode_cache reprezentująca i-węzeł
  • 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 .

Struktura jffs2_raw_node_ref

Dla każdego węzła przechowywana jest w pamięci struktura jffs2_raw_node_ref, która przechowuje:

Struktura jffs2_raw_node_ref reprezentująca odnośnik do węzła
  • 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)

Wykorzystanie struktur

Lista odnośników do węzłów

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ę wskaź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).

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.
  • Obraz systemu plików może być niekompatybilny między różnymi platformami sprzętowymi ze względu na zastosowaną w niej pamięć flash o innym rozmiarze bloku kasowania lub stosowania odwrotnej kolejność bajtów przez procesor.

Zobacz też

Bibliografia

Linki zewnętrzne