Simple Flash File System (SFFS) - prosty system plików dla pamięci typu flash Autor: Marek 'March' Szyprowski Licencja kodów źródłowych: GNU GPL >=2 1. Założenia projektowe a. Nośnik System plików ma zapisywać dane na nośnikach pamięci typu flash. Pamięć można programować z ziarnistością jednego sektora. Sektor po wyczyszczeniu binarnie jest wypełniony samymi jedynkami. W wyniku programowania, część jedynek jest zamieniana na zera. Istnieje możliwość ponownego nagrania sektora tylko wówczas, gdy wszystkie zmiany między bitami starymi i nowymi są zmianami z 1 na 0. Zmiany odwrotne wymagają wyczyszczenia danego sektora. Pamięć w wyniku czyszczenia jest zużywana i powinno dążyć się do tego, aby nie było sektorów, które są częściej czyszczone niż pozostałe. b. Docelowy system System plików powinien być tak napisany, aby była możliwa jego implementacja w systemie mikroprocesorowym opartym na procesorze 8 bitowym z bardzo ograniczoną ilością pamięci RAM (4kb?) oraz ROM na kod programu. System powinien mieć możliwość wykonania następujących operacji: - przejście do ustalonego katalogu po ścieżce - odczyt pliku - utworzenie nowego pliku - dopisywanie danych do otwartego pliku (z ziarnistością bajtów lub sektorów) - utworzenie katalogu W przypadku awarii systemu uszkodzenia struktury z niej wynikające powinny ograniczyć się tylko do ostatnio modyfikowanych danych. c. Docelowy system zarządzający Do zarządzania danymi na nośniku ma być wykorzystany komputer z odpowiednim czytnikiem kart flash oraz systemem Linux. Nośnik ma być zamontowany i obsługiwany jako normalny system plików. System plików ma obsługiwać tylko 2 typy plików - katalogi (zbiory zawierające inne pliki) i rzeczywiste pliki z danymi. Ma być dostępna możliwość wykonywania wszystkich standardowych operacji na plikach i katalogach: - odczyt pliku/katalogu - utworzenie pliku/katalogu - zapis danych do pliku - zmiana nazwy pliku/katalogu - skasowanie pliku/katalogu - zmiana rozmiaru pliku Z założenia nośniki używane z tym systemem plików są użytkowane na zasadach "zamontuj/odmontuj" i nie jest wymagane prowadzenie dziennika (journal) pozwalającego szybkie odtworzenie w przypadku awarii systemu. d. Sposób użytkowania Standardowo system plików ma być utworzeny w systemie zarządzającym. Nagrane mają być podstawowych dane oraz pliki startowe dla docelowego systemu mikroprocesorowego. Następnie nośnik jest zapełniany w docelowym systemie mikroprocesorowym. Co jakiś czas dane z nośnika są zgrywane w systemie zarządzającym. Zmiany w strukturze dysku oraz usuwanie danych wykonywane jest sporadycznie. Dopuszczana jest możliwość przeformatowania nośnika po jego zapełnieniu. 2. Analiza założeń i wnioski Żaden z obecnie wolnodostępnych systemów plików dla nośników typu pamięć flash nie spełnia wymogu działania w warunkach określonych w punkcie 1b, głównie z powodu bardzo ograniczonej pamięci RAM. Również wszelkie systemy plików ogólnego przeznaczenia (FAT, EXT2) dość dużym stopniu używają określone sektory na nośniku. Ze sposobu użytkowania (punkt 1d) wynika, że podstawową operacją wykonywaną na takim systemie plików jest dopisywanie danych do pliku. Ta operacja powinna być więc wykonywana w sposób zapewniający równomierne zużycie nośnika. Z racji ograniczonego miejsca na kod systemu plików w pamięci ROM (punkt 1b) operacja ta powinna być również niezbyt skomplikowana - tak aby funkcje ją realizujące były w miarę proste i nie wymagały dużej ilości innych funkcji do działania. Tak przyjęte ograniczenia wymuszają następujące odstępstwa względem typowych systemów plików dla pamięci flash: - dane plików są przechowywane bezpośrednio w sektorach; modyfikacja danych powoduje skasowanie i ponowne zaprogramowanie danego sektora - z założenia dane są jednak tylko nagrywane na nośnik, a modyfikacje plików są sporadyczne - informacje o wolnych sektorach ze względu na bardzo ograniczoną ilość pamięci ram w systemie mikroprocesorowym muszą być zapisane na nośniku zamiast wyliczane na bieżąco; sensownym rozwiązaniem jest mapa bitowa zajętych sektorów, w której "1" oznacza sektor wolny, a "0" zajęty (co pozwala na alokowanie bloków bez czyszczenia sektora z fragmentem bitmapy) - pozycja bitmapy na dysku nie może jednak być na sztywno określona (powinna się zmieniać po kolejnych formatowaniach nośnika) 3. Struktura systemu plików Wszystkie dane zapisywane w strukturach systemu plików są zapisywane w konwencji big-endian (z najbardziej znaczącymi bitami na początku). A. Superblok: #define SFFS_MAX_SB_BLOCK 256 struct sffs_super_block { u32 id; /* SFFS */ u8 log_block_size; /* 9 -> 512, 10 -> 1024, 11 -> 2048, 12 -> 4096 */ u8 flags_rw; /* features that are rw compatible */ u8 flags_ro; /* features that are read-only compatible */ u8 flags_incompat; /* features that are incompatible */ u16 reserved_blocks; /* reserved block at the begging of partition/disk */ u16 format_count; /* format counter */ u32 format_time; /* last format time */ u32 total_blocks; /* total number of blocks on partition/disk */ u32 sb_block; /* position of current superblock */ u32 bitmap_block; /* start block of disk bitmap */ u32 rootdir_block; /* root directory inode block */ u32 badblocks_block; /* badblocks inode block */ u32 sb_backup; /* backup superblock */ }; Superblok może być zapisany na dowolnym z pierwszych SFFS_MAX_SB_BLOCK bloków, co pozwala ominąć nadmierne zużywanie konkretnego (najczęściej pierwszego) bloku. Pierwszy znaleziony superblok uznawany jest za właściwy. Dodatkowo gdzieś na dysku utworzony jest blok zawierający dokładną kopię superbloku, co może być przydatne w przypadku konieczności odzyskiwania danych z uszkodzonego nośnika. Poszczególne pola w superbloku nie wymagają zmian w czasie normalnego używania systemu plików. Nowy superblok jest tworzony tylko w czasie formatowania nośnika. Program formatujący zapewnia, że kolejny superblok będzie utworzony na innym bloku, co pozwala na wielokrotne i bezpieczne dla nośnika formatowanie. Istotne pola superbloku to blok, w którym zapisany jest główny katalog oraz blok, w którym zaczyna się bitmapa. Pozostałe pola służą celom identyfikacyjnym, kontrolnym oraz ewentualnie ratunkowym. B. I-węzeł (Inode): #define SFFS_INODE_ID MAKE_ID('F', 'S', 'I', 'N') #define SFFS_MAX_FILENAME_LEN 48 struct sffs_raw_inode { u32 id; /* FSIN */ u32 time; /* creation time */ u8 flags; /* inode flags */ u8 type; /* inode type: 0x00 - unknown, 0x01 - regular file, 0x02 - directory */ u8 pad; /* */ u8 name_len; /* inode name length */ u8 name[SFFS_MAX_FILENAME_LEN]; /* inode name */ u32 next_block; /* next data block */ /* file data */ u32 data[0]; /* inode data block */ }; #define SFFS_INODE_TYPE_FILE 0x01 #define SFFS_INODE_TYPE_DIR 0x02 Numer i-węzła określa blok, w którym został on zapisany. Konstrukcja i-węzła jest bardzo prosta i jego pola ograniczone zostały do minimum. Ze względu na wymagania dotyczące nośnika oraz prostotę systemu plików, nazwa pliku skojarzonego z i-węzłem została przeniesiona bezpośrednio do i-węzła. Poza tym w i-węźle zawaty jest jeszcze identyfikator, czas utworzenia, typ oraz ewentualne dodatkowe flagi. Rozmiar i-węzła i ilość zajmowanych bloków jest wyliczana na bierząco na podstawie tabeli przydzielonych bloków. C. Tabela bloków i-węzła #define SFFS_DATA_ID MAKE_ID('D', 'A', 'T', 'A') struct sffs_raw_data { u32 id; /* FSIN */ u32 next_block; /* next data block */ /* file data */ u32 data[0]; /* inode data block */ }; Struktura ta jest podobna do końcowych pól i-węzła. C. Alokacja bloków z danymi dla poszczególnych i-węzłów W strukturze i-węzła przewidziane jest miejsce na tablicę alokacji bloków. Do tej tablicy wpisywane są kolejne bloki, które przydzielone zostałe do danego i-węzła. Numery bloków są zapisywane jako liczby 32-bitowe z włączonym najbardziej znaczącym bitem. Ostatni blok, który nie został w całości wypełniony danymi jest oznaczany poprzez specjalny znacznik zapisany po numerze bloku. Znacznik jest liczbą 16-bitową, bez włączonego najbardziej znaczącego bitu. Pomiędzy kolejnymi blokami w tabeli mogą być obszary, które wypełnione są samymi zerami - są to skasowane znaczniki końca pliku i należy je ignorować. Jeżeli miejsce w tabeli się skończy, alokowany jest nowy blok (struktura sffs_raw_data) dla kolejnej tabeli bloków. Jego numer jest umieszczany w polu next_blok, znajdującym się tuż przed tabelą z blokami. Dopisanie danych do pliku wykonywane jest poprzez nadpisanie ewentualnego znacznika końca pliku samymi zerami i zapisaniu albo nowego rozmiaru zapisanych danych w ostatnim bloku, albo wpisaniu numeru kolejnego (lub kolejnych) przydzielonych bloków. Jeżeli po numerze bloku w tabeli nie występuje znacznik końca pliku to oznacza to, że blok jest w pełni wykorzystany. Przykład (rozmiar bloku 512 bajtów): Początkowa tabela bloków: 0x80000010 0x80000011 0x80000012 0x0020ffff 0xffffffff 0xffffffff Przy tak wyglądającej tabeli do pliku przydzielone są bloki nr 16 [0x10], 17 [0x0x11] i 18 [0x12] (w ostatnim bloku wykorzystane są tylko 32 [0x20] bajty) - plik ma 512*2 + 32 = 1056 bajtów Dopisanie 64 bajtów do pliku zmieni tabelę tak: 0x80000010 0x80000011 0x80000012 0x00000060 0xffffffff 0xffffffff Dopisanie kolejnych 33 bajtów: 0x80000010 0x80000011 0x80000012 0x00000000 0x0081ffff 0xffffffff Dopisanie kolejnych 512 bajtów: 0x80000010 0x80000011 0x80000012 0x00000000 0x00008000 0x00130081 (zaalokowany został kolejny blok nr 19 [0x13] i wpisany do tabeli - wyrównanie jest tylko do liczb 16 bitowych) Oznaczanie numerów bloków poprzez włączenie najbardziej znaczącego bitu pozwala na proste odróżnienie ich od znacznika końca pliku. Zapisywanie znacznika końca pliku jako liczby 16-bitowej (a nie 32-bitowej jak numery bloków) pozwala na częściowe zaoszczędzenie miejsca w tabeli, dla często modyfikowanych plików. Jeżeli nie ma już miejsca w tabeli na dopisanie znacznika końca pliku alokowana jest następna tabeli bloków, a ostatni blok jest do niej przeniesiony (starej tabeli jest on nadpisywane zerami). Jest to jedyny momement tworzący sytuację potencjalnie niebezpieczną - może się bowiem okazać, że na dysku nie ma już wolnego bloku. Dlatego steronik zamin zezwoli na modyfikację/dopisywanie do pliku oraz przydzieli kolejny blok do pliku musi sprawdzić, czy jest jeszcze jeden dodatkowy wolny blok. Taki sposób przechowywania informacji o przydzielonych blokach eliminuje potrzebę nadmiernego zużywania bloków w pamięci flash, ponieważ dane są modyfikowane tylko "w jednym kierunku" (z bitowych 1 na bitowe 0). Wadą tego rozwiązania jest konieczność wyliczania rozmiaru pliku poprzez odczyt wszystkich tabeli bloków dla danego pliku, co dla dużych plików może być procesem czasochłonnym. Taki sposób alokacji danych ogranicza również ostatniego adres bloku do 2^30-2 (2147483646) co przy bloku 512 bajtów pozwala zaadresować 1TB. D. Struktura katalogu Zawartość bloków przydzielonych do i-węzła, który jest katalogiem w pewnym stopniu przypomina tabele alokacji bloków z i-węzłów. Dane katalogu to tabela liczb 32 bitowych, które są po prostu numerami i-węzłów, które należą do tego katalogu. Wpisy zawierające same bitowe zera oraz same bitowe jedynki są ignorowane. Kolejny i-węzeł dodany do katalogu wpisywany jest w pierwsze wolne (zawierające same bitowe 1) miejsce. Usunięcie danego i-węzła z katalogu wykonywane jest przez nadpisanie jego numeru zamymi bitowymi zerami. Dane katalogu przydzielane są porcjami równymi rozmiarowi bloku co upraszcza budowę katalogu. E. Struktura mapy bitowej dysku Mapa bitowa służy do określania, które bloki są już używane, a które wolne. Ponieważ z założenia system plików ma służyć do zapisywani coraz to nowszych danych i alokowania kolejnych bloków, bitowe "1" w bitmapie oznaczają blok wolny, a "0" blok zajęty. Przy takiej konwencji zaalokowanie bloku odbywa się bez potrzeby wykasowywania danego bloku na nośniku. Traktując bitmapę jako tablicę liczb 8-bitowych, kolejne bloki dysku odpowiadają coraz to mniej znaczącym bitom danego bajtu: Mapa bitowa (bitowo) - kolejne bity odpowiadają kolejnym blokom dysku: 11000011 11111000 11100000 | | | | | | 0 7 8 15 16 23 Ta sama mapa bitowa (jako liczby 8 bitowe): 0xc3 0xf8 0xe0 Bitmapa jest zapisana w kolejnych blokach od bloku okre ślonego w superbloku. W ostatnim bloku, bity odpowiadające blokom większym od ostatniego bloku dysku są ustawione na 0 - zajęte, co pozwala nie uwzględniać tego bloku jako przypadku szczególnego. F. Podsumowanie struktury dysku Tak przyjęta organizacja dysku pozwala na zapełnienie całego dysku bez konieczności wykasowywania jakiegokolwiek bloku przy założeniu, że na początku wszystkie bloki były wypełnione samymi bitowymi jedynkami. 5. Obecna implementacja sterownika systemu plików dla systemu Linux Załączona implementacja tego systemu plików jest ograniczona tylko do odczytu danych z dysku sformatowanego pod tym system plików. Opcje dostępne przy jego montowaniu to: * mode=[0644] - określa prawa dostępu do wszystkich plików; katalogi otrzymują takie same prawa oraz dodatkowo prawa X (wykonanie) dla odpowiadającym im prawom R (odczyt); domyślnie 0644 * setuid=[0] - określa UID właściciela wszystkich plików i katalogów; domyślnie 0 (root) * setgid=[0] - określa GID grupy właściciela wszystkich plikół i katalogów; domyślnie 0 (root) 6. Przykładowe programy A. mkfs.sffs - program do tworzenia systemu plików Tworzy on czysty system plików na wskazanym urządzeniu. Jeżeli wykryje tam istniejący system plików sffs, położenie wszystkich bloków "stałych" (bitmapa, główny katalog, superblok) jest przesuwane, tak, aby nie używać bloków, w których dane te były zapisane poprzednio. B. sffs_admin - program do zarządzania systemem plików Program powstał w ramach testowania systemu plików i jest właściwie zbiorem procedur do wykonywania wszystkich potrzebnych operacji na systemie plików. Pisany był z myślą o łatwym przeniesieniu ich na system 8 bitowy. Pozwala utworzyć pliki i katalogi, dopisać dane do istniejącego plik, odczytać zawartość katalogu oraz zapisać (skopiować) dane z istniejącego pliku do pliku o wskazanej nazwie na dysku w formacie sffs. Program służy głównie celom demonstracyjnym i nie posiada zbyt rozbudowanej kontroli błędów oraz wypisuje dość dużo różnych informacji potrzebnych przy testowaniu systemu plików. Dostępne komendy: * read_inode NUMER - odczytuje i pokazuje zawartość iwęzła o podanym numerze * read_dir [NUMER] - odczytuje i pokazuje zawartość katalogu o podanym numerze iwęzła (domyślnie jest to katalog główny) * create_file NAZWA_PLIKU [NUMER_KATALOGU] - tworzy nowy pusty plik o podanej nazwie w katalogu o podanym numerze iwęzła (domyślnie jest to katalog główny) * create_dir NAZWA_KATALOGU [NUMER_KATALOGU] - tworzy nowy katalog o podanej nazwie w katalogu o podanym numerze iwęzła (domyślnie jest to katalog główny) * append_file NUMER - dopisuje do pliku o podanym numerze iwęzła ciąg znaków "abcdefghijklmnopqrstuvwxyz" - do celów testowych * copy_file NAZWA_PLIKU_DOCELOWEGO PLIK_ZRODLOWY [NUMER_KATALOGU] - kopiuje istnejący plik (PLIK_ZRODLOWY) do pliku o nazwie NAZWA_PLIKU_DOCELOWEGO w katalogu o podanym numerze iwęzła (domyślnie jest to katalog główny) 7. Uwagli końcowe W przypadku rozszerzenia implementacji sterownika dla systemu Linux wskazane byłoby używanie kart pamięci w specjalnym czytniku kart, którego sterownik sprawdzałby, czy przy zapisie danego bloku rzeczywiście zachodzi konieczność czyszczenia bloku, czy nie. W przypaku czytników podłączanych przez USB, które są widziane jako zwykłe urządzenie MassStorage wykonanie takiego sprawdzenia jest raczej niemożliwe. Nie udało mi się zdobyć informacji, czy czytniki takie robią taką rzecz same z siebie. Zagadnienie to należałoby dokładniej zbadać.