< Spis treści

• Informacje ogólne
• Bibliografia

• zwykły plik, ale o specjalnej strukturze
• składa się z ciągu pozycji katalogowych

Opis pozycji katalogowej

inode	jednoznaczny numer i-węzła
rec_len	rozmiar pozycji
name_len	długość nazwy
name	nazwa



• może zawierać pozycje z numerem i-węzla równym 0 (pozycja usunięta)
• zawsze zawiera pliki o nazwach: . i ..

• prawa dostępu

Prawa dostępu dla katalogów

czytanie	możliwość przeglądania zawartości katalogu
pisanie	tworzenie i usuwanie plików
wykonywanie	możliwość przeszukiwania katalogu



• procesy czytają katalogi w taki sam sposób jak zwykłe pliki
• jądro systemu posiada wyłączne prawo do zapisywania katalogu

• M. J. Bach "Budowa systemu operacyjnego Unix"
• Projekty:
• Linux
• LabLinux
• LinuxPrezentacje

< Spis treści

• Opis_algorytmu
• Struktury_danych_i_funkcje

W pamięci znajduje się lista mieszająca dentry_hashtable , której elementami są dwukierunkowe listy. Elementami tych list są właśnie pozycje katalogowe.

static struct list_head dentry_hashtable[D_HASHSIZE];

D\_HASHSIZE = 1Kb

Funkcja mieszająca zależy od:

• struktury dentry ojca
• nazwy katalogu
• długości katalogu

Pozycje aktualnie nieużywane (tzn. d\_count = 0) przechowywane są w kolejce LRU dentry_unused.
 
 

struct dentry {

int d_count; /*ilu jest użytkowników*/

unsigned int d_flags;struct inode * d_inode; /*struktura inode naszego katalogu lub NULL*/

struct dentry * d_parent; /*nadkatalog - ojciec katalogu*/

struct dentry * d_mounts;

struct dentry * d_covers;

struct list_head d_hash; /*lista mieszająca, do której należy ten katalog*/

struct list_head d_lru; /*lista pozycji katalogowych nieużywanych występuje tylko przy d_cout = 0*/

struct list_head d_child; /*lista podkatalogów ojca naszego katalogu - dzieci naszego ojca*/

struct list_head d_subdirs; /*lista dzieci naszego ojca*/

struct list_head d_alias; /*aliasy d_inode*/

struct qstr d_name; /*dane nazwy katalogu*/

unsigned long d_time;

struct dentry_operations *d_op;

struct super_block * d_sb; /*korzeń drzewa, w którym znajduje się nasz katalog*/

unsigned long d_reftime; /*czas ostatniego odwołania*/

void * d_fsdata;

unsigned char d_iname[DNAME_INLINE_LEN] /*występuje przy krótkich nazwach*/}

struct sqstr{

const unsigned char* name;

unsigned int len;

unsigned int hash;}

/*zmienna hash w tej strukturze zależy od nazwy i jej długości*/

Funkcje:

• d_add - dodaje strukturę dentry naszego katalogu do listy mieszającej
• d_delete - jeśli jest ostatnim użytkownikiem to usuwa nasz katalog, wpp. usuwa listę mieszającą d_hash
• dget - dodaje użytkownika (tzn. zwiększa d_count)
• dput - usuwa użytkownika, jeśli jesteśmy ostatni i mamy strukturę dentry naszego katalogu to sprawdzamy również naszych przodków
• d_lookup szuka naszego katalogu mając dane: ojca i nazwę

< Spis treści

• Wstęp
• Schemat działania algorytmu
• Podział algorytmu na funkcje
• Sposób wykorzystania algorytmu
• Kilka uwag
• Bibliografia

Geneza algorytmu:

• użytkownik systemu posługuje sie nazwami ścieżkowymi
• jądro systemu wewnętrznie operuje na numerach i-węzłów
• potrzebny mechanizm pozwalający przekształcić scieżkę opisującą dostęp do pliku na numer odpowiedniego i-węzła

• przegląda on nazwę ścieżkową składowa po składowej (oddziela je "/")
• przekształca każdą składową na numer i-węzła zgodnie z nazwą składowej i przeszukiwanym katalogiem
• jako wynik przekazuje i-wezeł związany z wejściową nazwą ścieżkową

• Algorytm namei w standardowej postaci wystepuje w dwóch wersjach: namei() oraz lnamei(). Jedyną różnicą jest to, iż namei() dopuszcza dowiązania symboliczne, a lnamei() - nie. Są one używane przez proste polecenia np. chmod. Wywołania tych funkcji są przez makro (plik "include/linux/fs.h") zamieniane bezpośrednio na wywołania funkcji __namei().

  #define namei(pathname)        __namei(pathname, 1)
  #define lnamei(pathname)       __namei(pathname, 0)

• struct dentry * __namei(const char *pathname,
  				unsigned int lookup_flags)

  Zwraca i-węzeł odpowiadający plikowi o podanej nazwie ścieżkowej. Używa funkcji lookup_dentry().

• struct dentry * lookup_dentry(const char * name, 
  		struct dentry * base, unsigned int lookup_flags)

  Rzeczywista realizacja algorytmu namei w najprostszej postaci. Funkcja przekształca nazwę ścieżkową na końcowy i-węzeł.

• struct dentry * open_namei(const char * pathname, int flag, int mode)

  Jest to bardziej skomplikowana wesja funkcji namei(), wykorzystywana przez funkcję open(). Różni się od poprzedniej sprawdzaniem większej liczby warunków.

• static struct dentry * cached_lookup(struct dentry * parent, 
  	    	struct qstr *name, int flags)
  static struct dentry * real_lookup(struct dentry * parent, 
  	struct qstr *name, int flags)

  Powyższe funkcje znajdują i-węzeł odpowiadający pierwszemu elementowi podanej ścieżki, zaczynając od danego i-węzła. Różnią się tym, że pierwsza wykorzystuje podręczną pamięć buforową nazw katalogów, a druga - nie.

• Warto zauważyć, że realizacja algorytmu namei w najprostszej wersji (namei()) jest zasadniczo zgodna z opisem podanym przez Bacha w jego książce "Budowa systemu operacyjnego UNIX" (str. 85-88). Jedyne różnice wynikają stąd, że jądro Linuksa nie wie w jaki sposób system plików przechowuje informacje o plikach i katalogach, więc wywołuje odpowiednie funkcje.
• Porównując implementację algorytmu namei zawartą w jądrze 2.2.12 z poprzednimi (w stabilnej wersji sprzed 2.2.0) warto zauważyć, że funkcje dir_namei(), _namei() oraz follow_link() zostały połączone w jedną lookup_dentry(), która obejmuje wszystkie szczególne przypadki poprzedniego kodu.

• M. J. Bach "Budowa systemu operacyjnego Unix"
• pliki źródlowe jądra Linux 2.2.12
• fs/namei.c
• include/linux/fs.h
• Projekty:
• Linux
• LabLinux
• LinuxPrezentacje

< Spis treści

Spis rzeczy

6.1. Wstęp
6.2. Mount table
6.3. Montowanie - funkcja mount()
6.4. Odmontowywanie - funkcja umount()
6.5. Przekraczanie punktów montowania podczas analizy ścieżek plików

W Linuksie systemy plików z punktu widzenia użytkownika są reprezentowane jako jedno wspólne hierarchiczne drzewo katalogów.

Różne systemy plików są identyfikowane jako poddrzewa "zaczepione" w pewnych węzłach drzewa katalogów. Czynność takiego "zaczepiania" zwana jest montowaniem systemów plików.

Węzeł będący korzeniem drzewa zamontowanego systemu nazywamy punktem zamontowania (mount point). Po inicjalizacji systemu istnieje zawsze co najmniej jeden system plików, tzw. "root file system" - katalog "/" jest jego punktem montowania.

Zalety montowania:

• prosty dostęp do katalogów montowanych systemów poleceniem cd
  
  

• przezroczystość dla oprogramowania użytkowego (nie musi ono wiedzieć czy katalog należy do lokalnego dysku, czy może do odległego komputera via Network File System)

Uwagi:

• współistnienie bardzo wielu różnych typów systemów plików wewnątrz jednego drzewa jest możliwe dzięki stworzeniu abstrakcji systemu plików - VFS (Virtual File System)
  
  

• reprezentacja zamontowanych systemów plików w jądrze za pomocą tablicy super bloków
  
  

• informacje o zamontowanym systemie plików można pobrać także z i-węzła odpowiadającego punktowi zamontowania tego systemu plików
  
  

• istnieje lista możliwych do zamontowania przez jądro systemów plików, rozszerzalna przez doładowywanie odpowiednich modułów (np. moduł obsługi NTFS-u)
  
  

• poprzednia zawartość katalogu, w którym został zamontowany system plików przestaje być widoczna aż do jego odmontowania
  
  

• montować można również systemy plików urządzeń wirtualnych, ciekawym przykładem jest system plików proc, NFS lub ramdysk
  
  

• prawo do montowania i odmontowywania systemów plików ma użytkownik-root; inni użytkownicy mogą to robić jedynie w odniesieniu do systemów plików, dla których został ustawiony parametr users w pliku /etc/fstab
  
  

• istnieje możliwość przemontowania systemu plików z innymi parametrami

Informacje o zamontowanych systemach plików są przechowywane w tzw. tablicy montowania.
W rzeczywistości jest ona zrealizowana jako lista jednokierunkowa, o początku w zmiennej vfsmntlist i elemencie typu vfsmount:

struct vfsmount  {

kdev_t mnt_dev - nr urządzenia
char *mnt_devname - nazwa urządzenia
char *mnt_dirname - punkt montowania
unsigned int mnt_flags - flagi zamontowania systemu 
				plików;
struct super_block *mnt_sb - wskaźnik do superbloku 
			zaalokowanego przez system plików;
struct vfsmount *mnt_next - następny system plików
					na liście
}

• ostatnio zamontowanego sys. plików - vfsmnttail,
• ostatnio używanego sys. plików - mru_vfsmnt

Typy systemów plików obsługiwanych przez Linuxa, to m.in:

• minix - pierwotny system plików używany przez Linuxa, posiadający wiele ograniczeń,
• ext - zaprojektowany specjalnie dla Linuxa,
• ext2 - obecna, ulepszona wersja systemu ext,
• fat, vfat - używane przez MS-DOS, MS Windows,
• umsdos - rozszerzenie funkcjonalności zwykłych partycji DOSowych przez dodanie kontroli uprawnień dostępu do plików podobnej jak w ext2,
• ntfs - (nie myl z nfs), używany przez Windows NT,
• nfs - sieciowy, rozproszony system plików,
• proc - wirtualny system plików udostępniający informacje o systemie,
• iso9660 - system plików używany do zapisu dysków CD

Algorytm montowania:

• sprawdź, czy użytkownik ma prawo do montowania tego systemu plików,
• pobierz i-węzły: urządzenia i punktu montowania,
• sprawdź, czy punkt montowania jest istniejącym katalogiem (jeśli nie to błąd),
• przeglądnij listę (file_system_type *file_systems) aktualnie możliwych do zamontowania (zarejestrowanych) typów sys. plików w poszukiwaniu żądanego typu
  • jeśli nie udało się, to jądro może się zwrócić do kernel demona - kdemon - aby załadował moduł do obsługi danego typu systemu plików (i zarejestrował ten typ); w przypadku porażki - błąd,
• użyj numeru urządzenia do znalezienia tablicy funkcji obsługi danego urządzenia blokowego,
• odczytaj (utwórz) super-blok systemu plików czerpiąc informację z urządzenia blokowego (jeśli istnieje),
• dodaj nową pozycję do tablicy montowania,
• wpisz dowiązanie i-węzła "przykrywanego" katalogu do super-bloku systemu plików,
• wpisz do i-węzła katalogu montowania w dentry->d_mounts wskaźnik do i-węzła korzenia zamontowanego systemu plików
  
  

• operacja montowania nie powiedzie się, gdy:
  • system plików jest już używany (zamontowany),
  • katalog będący punktem montowania systemu plików jest już użyty do zamontowania innego sys. lub jest bieżącym katalogiem dla jakiegoś procesu,
• w przypadku systemu ext2 utworzenie super-bloku jest proste dzięki podobieństwu jego struktur do VFS-u; inaczej jest np. dla systemu NFS - wymagane są bardziej skomplikowane działania, m.in. połączenie się z serwerem NFS

Przykład polecenia montowania - dla partycji MS-DOS:

# mount -t vfat /dev/hda5 /mnt/dos

• ścieżka do urządzenia blokowego, np. "/dev/hda2"
  lub
  
• ścieżka do punktu montowania, np. "/mnt/dos"

Algorytm funkcji umount():

• pobierz i-węzeł pliku będącego parametrem i sprawdź, czy (1) należy on do urządzenia blokowego, czy (2) do katalogu (punktu montowania):
  • w przypadku (1) pobierz z tablicy super-bloków odpowiedni super-blok systemu plików odpowiadający urz. blokowemu, stamtąd zaś pobierz i-węzeł punktu montowania,
  • w przypadku (2) pobierz super-blok wskazywany przez jedno z pól i-węzła punktu montowania
  • jeśli i-węzeł nie odpowiada powyższym przypadkom, to błąd,
• sprawdź, czy są jakieś otwarte pliki we wskazanym systemie plików lub czy jakiś proces nie ma aktualnego katalogu ustawionego na katalog tego systemu - jeśli tak jest, to nie można odmontować; sprawdzenie polega na wykryciu obecności w pamięci aktywnych i-węzłów systemu plików,
• wyczyść pole d_mounts i-węzła punktu montowania,
• usuń z pamięci i-węzeł punktu montowania oraz i-węzeł korzenia drzewa katalogów odmontowanego systemu,
• w razie potrzeby zapisz super-blok odmontowanego systemu

# cd /mnt/dos/programy
# cd ../..

• pobranie i-węzła drzewa katalogów,
• znalezienie pliku katalogu opisanego przez "/" i znalezienie w nim nazwy "mnt",
• wyznaczenie numeru i-węzła dla nazwy "/mnt" i znalezienie go w pamięci funkcją iget,
• stwierdzenie, że pole d_mounts tego i-węzła jest <>NULL, zatem jest to punkt montowania jakiegoś sys. plików,
• korzystając z d_mounts->d_inode->i_sb->s_root (w jądrze 2.0 było to jedno pole) znajdujemy wskaźnik do korzenia drzewa katalogów systemu plików, który jest podmontowany w "/mnt",
• znalezienie (ponownie funkcją iget) i-węzła dla katalogu "/programy" w drzewie zamontowanego systemu plików, po czym ustalany jest ten i-węzeł jako bieżący katalog procesu

• po dokonaniu analizy ścieżki ".." - tak jak dla poprzednio, znajdujemy i-węzeł odpowiadający korzeniowi zamontowanego systemu plików /dev/hda5
• wyszukanie w ten sam sposób pozycji ".." dla znalezionego i-węzła nie mogło by się udać, gdyż jest to i-węzeł korzenia,
• należy sprawdzić, czy i-węzeł korzenia odpowiada korzeniowi pewnego zamontowanego systemu plików (/dev/hda5) - wystarczy sprawdzić w super-bloku wskazywanym przez ten i-węzeł, czy katalog montowania nie jest korzeniem,
• powyższe sprawdzenie daje pomyślny wynik, więc należy pobrać z d_inode->i_sb->s_root (przechodząc przez super-blok) i-węzeł punktu zamontowania ("/mnt/dos"), po czym wykonać dla niego operację "..", przechodząc do katalogu "/mnt"

< Spis treści

7. Struktury danych procesów związane z systemem plików

   W systemie Linux związek procesu z systemem plików opisany jest przez pola fs i files struktury task_struct. Są one odpowiednio typów fs_struct oraz files_struct, które przedstawione są na rysunku 7.1:

Funkcje struktury fs_struct

• definiuje domyślną maskę praw nadawaną plikom tworzonym przez proces
• ustala korzeń systemu plików dla procesu
• ustala aktualny katalog procesu

Funkcje struktury files_struct

• pamięta wszystkie deskryptory plików otwartych przez proces
• pamięta zbiór deskryptorów, które mają zostać zamknięte po wywołaniu przez proces funkcji exec

Definicje struktur z opisem pól

Bibliografia

• M. Beck, H. Boehme, ... , Linux kernel - Jądro systemu.
• Źródła linuksa (ścieżki względne od /usr/src/linux):
  • fs/file.c
  • fs/open.c
  • include/linux/sched.h
  • include/linux/file.h

< Spis treści

Za sprawą systemu operacyjnego użytkownik postrzega plik jako ciągły strumień bajtów o określonej długości. W rzeczywistości plik nie jest trzymany na dysku w sposób ciągły. Gdyby bowiem tak było, tzn. plik zajmowałby następujące po sobie bloki, dochodziłoby do fragmentacji zewnętrznej oraz ciężko byłoby zwiększyć jego rozmiar.

 W systemie ext2 plik jest przechowywany na dysku w wielu nie występujących po sobie blokach. Opis jego rozłożenia na bloki dyskowe oraz dodatkowe informacje związane z nim (tj. właściciel, prawa dostępu, rozmiar itp.) są zapisane w i-węźle (ext2_inode).

Strategia ta pozwala na dużą elastyczność systemu plików, lecz zarazem komplikuje sposób lokalizacji danych. Przechowywanie bowiem w i-węźle listy numerów bloków zajmowanych przez plik jest nieefektywne ze względu na obsługę tej listy i zmusza do narzucenia dużych ograniczeń na rozmiar pliku, badź do wprowadzenia i-węzłów o zmiennej wielkości.

Przyjęte zostało więc inne rozwiązanie. W i-węźle znajduje się tablica o nazwie

W tablicy tej przechowywane są cztery typy adresów:

• bezpośredni - wskazuje na blok z danymi. Liczbę  odresów bezpośrednich  w tablicy określa stała EXT2_NDIR_BLOCK równa 12.
• pojedynczy pośredni - jest to adres bloku, który zawiera listę adresów bezpośrednich.   Rozmiar bloku wynosi standardowo 1024 B, a rozmiar wskaźnika do bloku 4 B, zatem w bloku pośrednim pamiętanych jest 256 adresów bloków.
• podwójny pośredni - adres bloku zawierającego listę adresów bloków pojedynczych pośrednich.
• potrójny pośredni - jest to adres bloku zawierającego listę bloków podwójnych pośrednich.

W ten sposób można zapamiętać plik o rozmiarze 16 GB. Pliki jednak mogą mieć co najwyżej 4 GB, bo i-węźle pole rozmiaru pliku zajmuje 32 bity. Z tego też powodu nie ma bloków poczwórnych pośrednich. Niektóre numery bloków mogą być równe zero, co oznacza, że na pewnej przestrzeni pliku nie zostało nic zapisane - na takie bloki nie zużywa się miejsca na dysku. Do wspomnianej sytuacji może dojść w wyniku wywołania funkcji lseek.

Stałe określające wielkość tablicy i_block i jej podział zdefiniowane są w pliku include/linux/ext2_fs.h.

#define EXT2_NDIR_BLOCKS 12                    - liczba bloków bezpośrednich
#define EXT2_IND_BLOCK   EXT2_NDIR_BLOCKS      - pozycja w tablicy bloku pośredniego
#define EXT2_DIND_BLOCK  (EXT2_IND_BLOCK + 1)  - ... podwójnego pośredniego 
#define EXT2_TIND_BLOCK  (EXT2_DIND_BLOCK + 1) - ... potrójnego pośredniego
#define EXT2_N_BLOCKS    (EXT2_TIND_BLOCK + 1) - liczba wszystkich bloków

1. Pliki zródłowe Linuxa:
• include/linux/ext2_fs.h (stałe wymienione wyżej i struktura i-węzła na dysku)
• include/linux/ext2_fs_i.h (struktura i-węzła w pamieci)

< Spis treści

Struktury odpowiadające fizycznym plikom przechowywane są na dwukierunkowej liście cyklicznej. Proszę zwrócić uwagę, że wygodniej było pamietać element przedostatni zamiast bezpośrednio poprzedzającego. Dostęp do tablicy plików możliwy jest za pomocą globalnego wskaźnika first_file.

Poniżej zamieszczamy opisy struktur oraz stalych wykorzystywanych przez strukture file:

struct fown_struct {
    int pid;          /* pid albo -pgrp do którego powinien zostać wyslany sygnal SIGIO */
    uid_t uid, euid;  /* uid/euid procesu ustawiającego nowego właściciela */
    int signum;       /* posix.1b rt sygnał, który ma zostać wyemitowany do IO */
};

• O_CREATE - plik zostaje utworzony jeżeli jeszcze nie istnieje
• O_EXCL- flaga ta jest zazwyczaj łączona z O_CREATE, zwraca błąd jeśli plik istnieje
• O_RDONLY - plik zostaje otwarty jedynie do czytania
• O_ WRONLY - plik zostaje otwarty jedynie do pisania
• O_APPEND - dane będa dopisywane na koniec pliku nawet jeżeli już ma niezerowa długość
• O_RDWR- plik zostaje otwarty zarówno do czytania jak i do pisania
• O_SYNC - operacje będą blokowały proces aż do ich rzeczywistego wykonania
• O_NOCTTY - jeżeli pathname odnosi się do terminala to nie stanie on się terminalem sterującym
• O_NONBLOK - jeżeli trzeba czekać na dowolna operacje to zostanie zwrócony bład
• O_NDELAY - jak wyżej
• O_TRUNC - wskaźnik końca pliku zostanie ustawiony na bieżącą pozycje w pliku

Prawa nadane procesowi, który otworzył plik:

• FMODE_WRITE - prawo czytania
• FMODE_READ - prawo pisania

struct file_operations {
    loff_t (*llseek) (struct file *, loff_t, int);
    ssize_t (*read) (struct file *, char *, size_t, loff_t *);
    ssize_t (*write) (struct file *, const char *, size_t, loff_t *);
    int (*readdir) (struct file *, void *, filldir_t);
    unsigned int (*poll) (struct file *, struct poll_table_struct *);
    int (*ioctl) (struct inode *, struct file *, unsigned int, unsigned long);
    int (*mmap) (struct file *, struct vm_area_struct *);
    int (*open) (struct inode *, struct file *);
    int (*flush) (struct file *);
    int (*release) (struct inode *, struct file *);
    int (*fsync) (struct file *, struct dentry *);
    int (*fasync) (int, struct file *, int);
    int (*check_media_change) (kdev_t dev);
    int (*revalidate) (kdev_t dev);
    int (*lock) (struct file *, int, struct file_lock *);
};

< Spis treści

9. Dostęp do danych z pliku - funkcja bmap()

Wstęp

 int bmap( struct inode *inode,int block)

struct inode * inode

wskaźnik do i-węzła pliku

int block

żądany logiczny number bloku z pliku: block=logiczny-number-bajtu/rozmiar-bloku

• 0 gdy wystapił błąd
• fizyczny numer bloku na dysku w przeciwnym wypadku

Implementacja

Dla przykładu omówię funkcję ext2_bmap( struct inode * inode, int block). Jest ona zadeklarowana w pliku include/linux/ext2_fs.h. Implementacja znajduje się w fs/ext2/inode.c. W tym pliku znajdują się również funkcje/makra pomocnicze:

inode_bmap(inode, nr)

makro, zwraca pozycję nr z tablicy bloków i-węzła. Parametr nr musi należeć do przedziału [0, EXT2_N_BLOCKS-1]

int block_bmap(struct buffer_head * bh, int nr )

funkcja, traktując zawarty w bh odczytany blok jako tablicę wartości 32-bitowych, zwraca jej pozycję o numerze nr. Zwalnia bufor przez wywołanie brelse(bh).

W funkcji zdefiniowane są następujące zmienne pomocnicze:

int addr_per_block

określa, ile fizycznych adresów bloków mieści się w jednym bloku

int addr_per_block_bits

jej wartością jest log2(addr_per_block) (patrz fs/ext2/super.c linia 548)

Bloki pliku należą do czterech kategorii. Zaczynając od zera, mamy:

bloków bezpośrednich:

EXT2_NDIR_BLOCKS (=12)

bloków pośrednich pierwszego poziomu:

2^(addr_per_block_bits) = addr_per_block

bloków pośrednich drugiego poziomu:

2^(2*addr_per_block_bits) = addr_per_block^2

bloków pośrednich trzeciego poziomu:

2^(3*addr_per_block_bits) = addr_per_block^3

Pseudo-kod algorytmu bmap

ext2_bmap( struct inode * inode, int block)
{
  /*czy wartość block mieści się w odpowiednich granicach*/ 
   if ( block < 0 ) return 0;
   if ( block >= max) return 0;

  
   if ( block < EXT2_NDIR_BLOCKS )
     {  /*blok bezpośredni*/ 
       return inode( inode, block );
     }
	
  /* pomijamy bloki bezpośrednie, wartością zmiennej block staje 
     sie numer bloku pośredniego poziomu I, II lub III*/ 
   block-= EXT2_NDIR_BLOCKS;    

   if ( block < addr_per_block )
     {       /* jest to blok pośredni pierwszego poziomu */ 
       i= inode_bmap( inode, EXT2_IND_BLOCK ); 
       if ( i == 0 ) return 0;
	     /* w i jest teraz adres bloku pośredniego poziomu I*/ 
             /* trzeba wczytac blok o adresie i (to robi bread(...)) */ 

       return block_bmap( bread(..., i), block );  /* szukany adres bloku */ 
     }

   /* pomijamy bloki pośrednie poziomu I, wartością zmiennej block staje 
      sie numer bloku pośredniego poziomu II lub III*/ 
   block-= addr_per_block;

   if ( block < (1 << (addr_per_block_bits*2) ))
     {       /* jest to blok pośredni drugiego poziomu */ 
       i= inode_bmap( inode, EXT2_DIND_BLOCK ); 
       if ( i == 0 ) return 0;
	     /* w i jest teraz adres bloku pośredniego poziomu I*/ 

       bl= bread(..., i);   
             /* w tym bloku znajduje się adres bloku pośredniego poziomu II */ 
       i= block_bmap( bl, block >> addr_per_block_bits );
       if ( i == 0 ) return 0;
             /* szukany adres: */ 
       return block_bmap( bread(..., i), block & (addr_per_block-1) );
     }
   /* jest to blok pośredni poziomu III: block staje się numerem bloku
      pośredniego poziomu III */ 
   block-= (1 << (addr_per_block_bits*2) );
   /*  czytamy kolejne bloki pośrednie... */ 
   i= inode_bmap( inode, EXT2_TIND_BLOCK );
   if ( i == 0 ) return 0;
   i= block_bmap( bread(..., i), block >> (addr_per_block_bits*2));
   if ( i == 0 ) return 0;
   i= block_bmap( bread(..., i), (block >> addr_per_block_bits) &
	(addr_per_block-1));
   if ( i == 0 ) return 0;
   /*  ... i mamy wynik  */
   return block_bmap( bread(..., i), block & (addr_per_block-1));
}
    

Jak widać, algorytm ten najszybciej działa dla krótkich plików. Im plik dłuższy, tym więcej trzeba dostępów do dysku, aby znaleźć żądany blok.

Przypuśćmy, ze układ bloków pewnego pliku jest taki, jak na rysunku poniżej:

block= 22

Ponieważ 22 >= 12=EXT2_NDIR_BLOCK, to blok nie należy do bloków bezpośrednich.

block= block-12 = 22-12 = 10

10 >= addr_per_block=4, więc blok nie należy do bloków jednokrotnie pośrednich.

block= block - addr_per_block = 10 - 4 = 6

block = 6 < addr_per_block^2 = 16, więc blok należy do bloków podwójnie pośrednich.

Pobieramy adres bloku podwójnego pośredniego w i-węźle (indeks 13): 185.

Wczytujemy ten blok.

Liczymy 6 >> addr_per_block_bits = 6 >> 2 = 1.

Odczytujemy więc drugą pozycję w bloku 185 - jest to 114.

Wczytujemy blok 114.

Numer szukanego bloku znajduje się na pozycji 6 & (addr_per_block - 1) = 6 & 3 = 0110b & 0011B = 0010b = 2.

Zatem numer fizyczny bloku o numerze logicznym 22 to 600.

• include/linux/fs.h
  deklaracja funkcji bmap
• fs/inode.c
  definicja funkcji bmap
• include/linux/ext2_fs.h
  deklaracja funkcji ext2_bmap
• fs/ext2/inode.c
  definicja funkcji ext2_bmap, makro inode_bmap, funkcja block_bmap

< Spis treści

10.1. Tworzenie i otwieranie pliku

• Wprowadzenie
• Definicja
• Struktury danych
• Implementacja
• Uwagi
• Bibliografia

Wprowadzenie

int open(const char*pathname, int flags, int mode);

Wynik - deskryptor pliku(>=0), lub -1 w przypadku bledu
pathname - sciezka dostepu do pliku
flags - okresla sposob otwierania pliku
mode - uzywane z flaga OCREAT(wpp ignorowana). Okresla prawa dostepu do pliku.
Jest modyfikowane przez atrybut umask procesu: prawa dostepu do tworzonego 
pliku beda rowne (mode & ~umask).

Uzywane jako parametr flags:

O_RDONLY,O_WRONLY,O_RDWR (otwieranie pliku odpowiednio tylko do czytania,
tylko do pisania, do czytania/pisania. Flagi te mozemy modyfikowac bitowa
operacja OR flagami opisanymi ponizyej)

O_CREAT (jesli plik nie istnieje istnieje bedzie stworzony)
O_EXCL (uzywany z flaga O_CREAT, jesli plik juz istnieje zwroc blad)
O_NOCTTY (jesli pathname odnosi sie do terminala, to nie stanie sie on
          terminalem sterujacym, nawet jesli takowego procesu nie posiada)
O_TRUNC (jesli plik juz istnieje obetnij go)
O_APPEND (poczatkowo oraz przed kazdym pisaniem wskaznik do pliku bedzie
           ustawiany na jego koncu)
O_NBLOCK / O_NDELAY (open oraz kazda inna nastepna operacja na zwroconym
                     deskryptorze bedzie konczyla sie bledem w przypadku
                     koniecznosci czekania na jakies zdarzenie np. zdjecie 
                     blokady z pliku);
O_SYNC (dowolne operacje pisania na deskryptorze beda blokowaly proces 
       az do momentu wykonania fizycznego zapisu na urzadzeniu docelowym)

EEXIST (plik pathname juz istnieje - O_CREAT i O_EXECL ustawione)
EISDIR (otwierano katalog do pisania)
ETXTBSY (otwierano plik wykonaywalny do pisania)
EFAULT (pathname wskazuje na obszar poza przestrzenia adresowa procesu)
EACCES (dostep do pliku zabroniony, lub jeden z katalogow w pathname nie 
        zezwala na przeszukiwanie (wykonywanie))
ENAMETOOLONG (nazwa pathname zbyt dluga)
ENOENT (katalog skladowy uzyty w sciezce nie istnieje lub jest 
       nieprawidlowym dowiazaniem)
ENFILE (prog na maksymalna liczbe otwartych plikow w systemie zostal 
       osiagniety)       
ENOMEM (niewystarczajaca ilosc pamieci dostepnej jadru systemu)       
EROFS (plik z systemu plikow typu read-only otwierano do pisania)
ELOOP (pathname zawiera dowiazania cykliczne tj. takie, ze jego rozwiniecie
      nadal uzywa tego dowiazania)
ENOSPC (brak miejsca na urzadzeniu na utworzenie nowego pliku)      

• Proces moze miec maksymalnie min{NR_OPEN=256, rlim[RLIMIT_NOFILE].rlim_cur /*inicjalizowane na NR_OPEN*/} otwartych plikow.rlim jest lokalna tablica procesu.
• lista("tablica") plikow nie moze miec wiecej niz NR_FILE= 1024 pozycji

int open(const char*pathname, int flags, int mode)
{
  file= get empty filp(); /*file - wolna pozycja w tablicy plikow*/
  mode = mode & ~umask;/* uwzglednienie umask procesu*/
  Sprawdzenie praw, poprawnosci argumentow;
  if (flag&)_CREAT){
        inode= get_empty_inode();/*inode-wolna pozycja w tablicy i-wezlow*/
        zainicjalizowanie pozycji inode w tablicy i-wezlow; 
  }else
        inode=i-wezel pliku o nazwie pathname;
  if (flag&O_TRUNC)
      do truncate();
  if (plik otwarto do pisania )
     inode->i_writecount++;
  Zaincjalizowanie pozycji file w tablicy plikow;
  Poszukiwanie wolnej pozycji nr w tablicy deskryptorow fd procesu;
  fd[nr]=file;
  return (nr);
}

2. Gdy nie ma wolnej pozycji w tablicy plikow, wowczas alokowana
   jest nie jedna struktura file lecz cala strona pamieci na
   (PAGE_SIZE/sizeof(struct file)) nowych pozycji w tablicy plikow.

3. Definicja funkcji jest zawarta w "./includ/asm-alpha/unistd.h".
   Widac tam, ze funkcja open kozysta z funkcji sys_open, ktorej
   implementacja jest w "./fs/open.c";

4. W opisie funkcji open zostalo dokonane niewielkie przeklamanie,
   tzn. w przypadku bledu funkcja zwraca tak naprawde kod bledu a nie
   -1. Mialo to jednak sluzyc wiekszej przejzystosci tekstu, ktory moze
   byc czytany przez potencjalnych czytelnikow programistow.

• Tworzenie, otwieranie i zamykanie pliku - Krzysztof Juchimiuk
• Funkcje : read() i write() - Jakub Lenart
• Obsługa łączy nienazwanych i blokowanie plików - Michal Domagała

< Spis treści

• funkcje obslugujace istniejace pliki,
• sluzace do tworzenia nowych plikow,
• obslugujace i-wezel,
• pozwalaace przemieszczac sie w systemie plikow,
• rozszerzajace drzewo systemu plikow i zmieniaja struktore hierarchii systemu plikow

• Sluzy do obslugi istniejacego pliku;
• Wczytanie odpowiednia ilosc bajtow danych z otwartego pliku do odpowiedniej struktory danych uzytkownika;
• Zwieksza wskaznik o liczbe przeczytanych bajtow;
• Sekwencyjne wczytywanie kolejnych blokow dyskowych i w konsekwencji wczytuje dane z wyprzedzeniem.

Funkcja read:

DEFINICJA:

int read(unsigned int fd, char *buf, unsigned int count );

WYNIK: liczba wczytanych bajtow, 
                 0 w przypadku napotkania na koniec pliku,
                 -1 w przypadku bledu; 

        errno = EDEADLOCK(jezeli na plik lub rekordy jest zalozona blokada)
                EFAULT(w przestrzeni wirtualnej nie ma zaalokowanego
                              bufora uzytkownika )
                 EINVAL(jezeli nie mozemy wywolac funkcji read dla konkreatnego                               
                 EBADF(niepoprawny deskryptor pliku)
systemu plikow)

Dla wszystkich systemu plikow dana jest ta sama funkcja read:

{

• pobieramy i-wezel korzystajac z deskryptora pliku uzytkownika
• sprawdzamy w tablicy plikow prawo do czytania dla pliku
• sprawdzamy czy mozemy wywolac read dla konkretnego systemu plikow
• upewniamy sie czy nie ma blokady na rekord do czytania
• upewniamy sie czy struktura danych uzytkownika jest zaalokowana w jego przestrzeni
• dla systemu plikow EXT2 wywolujemy funkcje generic_file_read

loff_t f_pos; /* pozycja w pliku */

f_rawin; /*rozmiar danych wczytanych w trakcie ostatnio wykonywanego czytania z wyprzedzeniem */

f_ramax; /*aktualny maksymalny rozmiar danych, ktore mozna przeczytac z wyprzedzeniem */

Funkcja generic_file_read():

Parametry buf i count takie same jak w wywolaniu read.
inode jest i-wezlem czytanego pliku
filp pozycja w tablicy plikow odpowiadajaca danemu plikowi
buf jest adresem struktory danych uzytkownika do ktorego wczytujemy dane
count jest to liczba bajtow, ktore chce wczytac uzytkownik

Funkcja generic_file_read() wykorzystuje czytanie z wyprzedzeniem, gdy stwierdzi ze odczyt jest sekwencyjny. W strukturze struct_file czytanego pliku znajduja sie pola :

• f_ramax - wartosc ta zmienia sie dynamicznie w trakcie wykonywania sie funkcji read i dodatkowo musi byc wieksza niz MIN_READAHEAD=PAGE_SIZE*3, i wieksza niz: MAX_READAHEAD=PAGE_SIZE*18, gdzie PAGE_SIZE jest rozmiarem ramki w pamieci operacyjnej.
• f_rawin

Z tych pol korzysta funkcja generic_file _readahead(), ktora zwraca nam ramke pamieci czytajac z wyprzedzeniem lub 0 gdy nie udalo sie jej znalezc lub stworzyc nowej ramki.

Algorytm funkcji generic_file_read():

{

• Jesli aktualna pozycja w pliku znajduje sie poza obszarem poprzednio wczytanym z wyprzedzeniem, to ustawiamy pola f_rawin, f_ramax na 0 W przeciwnym przypadku stwierdzamy, ze dostep do pliku jest sekwencyjny i kontynuujemy czytanie z wyprzedzeniem ustawiajac zmienna reada_ok na 1
• Jesli ilosc danych do przeczytania z pliku jest mniejsza niz polowa rozmiaru ramki pamieci(PAGE_SIZE=4kb) to f_ramax=0 W przeciwnym przypadku jesli ilosc bajtow do przeczytania jest wieksza niz f_ramax to f_ramax=(ilosc danych do przeczytania)
• for(;;) {
 
• Probujemy znalezc ramke pamieci zawierajaca dane z pliku na aktualnej pozycji
• Jesli udalo sie nam to idziemy do etykiety znaleziono_ramke Jesli nie to do etykiety nie_znaleziono_ramki znaleziono_ramke:
• Jesli ramka jest aktualna lub zablokowana(np. z powodu zapelniania jej danymi) to probujemy dostac nastepna ramke wywolujac funkcje generic_file_read () W przeciwnym przypadku pole f_ramax ustawiamy na MIN_READAHEAD
• Czekamy na ramke(nie na ta dodatkowa byc moze zwrocona przez generic_file_readahead)
• Jesli ramka jest nieaktualna to idziemy do etykiety ramka_blad Jesli jest aktualna to do etykiety sukces sukces:
• Obliczamy ilosc bajtow, ktore mamy wczytac z ramki
• Kopjujemy dane z ramki do bufora uzytkownika
• Nie zwalniamy ramki ale zmniejszamy licznik odwolan do niej
• Zwiekszamy pozycje w pliku, pozycje w buforze, ilosc przeczytanych bajtow i ilosc bajtow, ktore mamy do przeczytania o ilosc bajtow przeczytanych z ramki
• Jesli nie mamy nic do czytania to jesli trzeba to szeregujemy procesy (schedule()) a nastepnie wyskocz z petli for W przeciwnym przypadku idz na poczatek petli for(continue) nie_znaleziono_ramki:
• Jesli nie mamy dodatkowej ramki przeczytanej z wyprzedzeniem to tworzymy nowa ramke(_get_free_page) i jesli funkcja nie zwrocila bledu to idziemy na poczatek petli for(continue) W przeciwnym przypadku jesli mamy dodatkowa ramke pamieci to dodajemy ja do kolejki haszujacej ramek (wywolujemy funkcje add_to_page_cache) a nastepnie wywolujemy funkcje readpage zglaszajac zadanie zapisania ramki danymi z dysku
• Jesli operacja zakonczy sie pomyslnie to idziemy do etykiety znaleziono_ramke
• Jesli blad to wyskakujemy z petli for ramka_blad:: /*znalezlismy ramke ale nie jest aktualna*/
• Zglaszamy zadanie zapisu ramki (funkcja readpage)
• Jesli wszystko poszlo dobrze to czekamy na ramke (byc moze jest w trakcie zapelniania) i idziemy do etykiety sukces W przeciwnym przypadku wyskakujemy z petli for }/*koniec petli for*/
• Jesli mamy dodatkowa ramke to ja zwalniamy
• Jesli i-wezel nie jest tylko do odczytu to aktualizujemy czas ostatniego dostepu do i-wezla na aktualny
• Zaznaczamy ze i-wezel jest brudny
• Zwracamy ilosc przeczytanych bajtow }/*koniec algorytmu funkcji generic_file_read

1. Funkcja systemowa read() nie moze opozniac wczytywania danych, tak jak to robi funkcja write() w przypadku zapisu. Jesli dane nie znajduja sie w wewnetrznym buforze jadra, to proces musi zaczekac na pobranie ich z dysku.
2. W przypadku plików specjalnych oraz laczy komunikacyjnych powrot z funkcji read() jest natychmiastowy, jesli plik byl otworzony z flaga O_NDELAY i nie ma danych do przeslania.
3. Jesli system nie jest zbyt przeciazony i dane moga przez pewien czas pozostawaæ w buforze, to w przypadku czytania sekwencyjnego, zastosowane wczytywanie z wyprzedzeniem jest skuteczne i w znaczny sposób poprawia wydajnosc systemu.
4. Implementacja funkcji read() w Linux 2.2.12 jest taka sama jak w wersji 2.0.20. Natomiast troche zmodyfikowana zostala funkcja generic_file_read(). A mianowicie dodano wywolanie funkcji szeregujacej procesy schedule(), zapewne w celu zoptymalizowania pracy systemu. Dodano takze wywolanie funkcji UPDATE_ATIME(inode) do aktualizacji atrybutow i-wezla.

< Spis treści

 

bit setuid - bit nadawania efektywnego identyfikatora uzytkownika (fsuid) dla procesu wykonujacego plik,

bit setgid - to samo dla fsgid,

bit przyklejania - gdy 1, to w pamieci zostaje kopia pliku po jego wykonaniu,

typ pliku (4 bity z lewej, ósemkowo):

001 - FIFO

002 - Character Device

004 - Directory

inne: Regular (zwykly), Block Device, Link, Socket.

struktury file:

mode_t f_mode; /* tryb otwarcia pliku (pisanie/czytanie) - to nie jest ten sam tryb, co w i-wezle (patrz wyzej) */

loff_t f_pos; /* pozycja w pliku */

struct file_operations *f_op; /* operacje na pliku w konkretnym file-systemie */

unsigned short f_flags; /* czy plik ma szczególne wlasciwosci (tylko do nadpisywania, niezmienialny, do pisania synchronicznego lub inne) - dotyczy konkretnego otwarcia pliku, a nie wspolnego dla wszystkich otwarc i-wezla*/

struct file *f_next, *f_prev; /* wskaznik do poprzedniego i nastepnego pliku w tablicy plikow, ktora wcale nie jest tablica, ale lista dwukierunkowa. Jadro trzyma wskaznik do pierwszego pliku. Maksymalny rozmiar tej listy to 1024 = NR_FILE = maksymalna liczba plikow otwartych w systemie */

struct inode *f_inode; /* i-wezel odpowiadajacy plikowi */

... (i inne, dla mojego tematu nieistotne)

Funkcja write()

• Sluzy do pisania do pliku (w tym rowniez gniazda, gdyz gniazdo jest typem pliku).
• funkcja write() sklada sie z dwóch czesci: niezaleznej i zaleznej od systemu plików;
• Opuszcza semafor na i-wezle;
• Czesc zalezna od systemu plikow;
• Podnosi semafor na i-wezle;
• Sprawdzenie prawa tylko do odczytu;
• Ustala miejsce odkad nastapi pisanie;
• Warunek : biezaca pozycja w pliku <= 2GB;
• Pobierany jest bufor odpowiadajacy i-wezlowi pliku i obliczonemu numerowi bloku;
• Wczytanie porcji danych do pobranego przed chwila bufora;
• Uaktualnienie wskaznikow biezacej pozycji w pliku i biezacego miejsca pobierania danych z miejsca wskazanego przy wywolaniu funkcji;
• Jesli plik zostal otwarty do operacji synchronicznych , wykorzystywany jest algorytm "pisania z opoznieniem". Jesli nie, to zajety blok jest natychmiast zwalniany.
• Gdy tablica z buforami zapelni sie jej zawartosc jest zapisywana w calosci, a zajmowane bufory - zwalniane.
• Modyfikacja czasu ostatniej modyfikacji pliku i  i-wezla (ustawiane sa na czas biezacy).;
• Modyfikacja dlugosci pliku zapisana w i-wezle.;
• Zaznaczenie i-wezla jako "brudnego" i zwolnienia blokady nalozonej na i-wezel funkcja konczy dzialanie.

  ---

WYNIK:
liczba zapisanych bajtow lub blad.

DANE:
deskryptor pliku (fd), wskaznik do danych do zapisania (buf), ilosc bajtow do zapisania (licznik).

Algorytm:

{

• Sprawdz w tablicy plikow prawo do pisania (pole file->mode); Jezeli licznik=0, zwroc zero;

• Upewnij sie, ze:

• nie ma blokady na rekord do zapisania (locks_verify_area);

• mozemy czytac z obszaru pamieci wskazywanego przez buf o dlugosci licznik (verify_area);

• Jesli proces nie ma euid=0 (effective user id), czyli nie jest jednym z superuserow, to:

• skasuj bit setuid;

• jezeli bit setgid jest ustawiony, a grupa nie ma prawa wykonywania (odpowiedni bit w slowie dostepu do pliku w i-wezle jest zerem), to zostaw bit setgid, gdyz plik jest kandydatem do obowiazkowego blokowania (mandatory locking), w p.p. skasuj bit setgid (utrata nadawania efektywnego identyfikatora grupy dla procesu przy pisaniu do pliku);

• Opusc semafor w i-wezle (zabezpieczenie przed jednoczesnym pisaniem);

• Wywolaj write dla konkretnego file-systemu lub, jesli mamy do czynienia z gniazdem, to write dla gniazda - po prostu funkcje ze struktury file_operations;

• Podnies semafor;

struct file_operations {

int (* lseek) (struct inode *, struct file *, off_t, int);

int (* read) (struct inode *, struct file *, char *, int);

int (* write) (struct inode *, struct file *, const char *, int);

int (* open) (struct inode *, struct file *);

i inne ... (plik fs.h)

Do struktury tej prowadzi wskaznik z kazdego pliku w tablicy plikow.

Funkcja ext2_file_write()

WYNIK:
liczba zapisanych bajtow lub blad.

DANE:
plik oraz odpowiadajacy mu i-wezel, buf i licznik - to wskaznik i rozmiar obszaru w pamieci z danymi (te same, co w funkcji write).
Algorytm pisania, c.d. :

{

Upewnij sie, ze:

file-system nie jest zamontowany read-only;

jestesmy plikiem regularnym, tzn. nie gniazdem, katalogiem, FIFO, etc.
 

Jesli plik jest tylko do nadpisywania (mówi o tym pole f_flags w strukturze file), to zacznij pisac na koncu pliku, w p.p. zacznij od aktualnej pozycji pliku;

Oblicz numer bloku logicznego, w którym znajduje sie pozycja w pliku, na której bedziemy pisali, oraz offset (to jest tak, ze pozycje mozna traktowac jako adres: bity mowiace o numerze bloku i o przesunieciu);

while (licznik>0)

{

Jesli wyszlismy poza pozycje nr 2GB, to zakoncz petle, a na wartosc wynikowa przypisz blad;

Pobierz bufor odpowiadajacy logicznemu blokowi i-wezla ( getblk() );

Liczba bajtów do zapisania := min{liczba bajtów od offsetu do konca bloku, licznik}. Chodzi o to, ze piszemy albo do konca bloku, albo mniej. Urzadzenie blokowe potrafi zapisac tylko caly blok, a nie pojedynczy bajt.

Odlicz od licznika liczbe bajtow pozostalych do konca bloku;

Jezli bufor nie jest aktualny i nie mamy go calego zapisac (po to obliczalismy liczbe bajtow do zapisania), to wczytaj odpowiadajacy mu blok z dysku (funkcja ll_rw_block(READ,...));

Skopiuj dane w pamieci z (argumentu funkcji) 'buf' do pobranego bufora;

Zaktualizuj Virtual Memory Cache odnosnie danego bloku - pobierz strone, zapisz do niej dane z bloku i zwolnij ja ( funkcja update_vm_cache() );

Przesun pozycje do pisania w pliku oraz miejsce pobierania danych w 'buf';

Zaznacz, ze bufor jest aktualny i nie jest brudny (brudny oznacza, ze co innego jest na dysku, niz w pamieci, oraz dane w pamieci sa lepsze);

Jesli plik jest do pisania synchronicznego, to zapisz bufor do tymczasowej tablicy i nie zapisuj go na dysk, dopoki jej nie zapelnisz (rozmiar tablicy: NBUF =16);

w p.p. (zapis nie synchroniczny) zwolnij bufor;

Jesli tablica jest juz pelna, to zapisz ja cala ( funkcja ll_rw_block(WRITE,...) ) i pozwalniaj bufory;

Zajmij sie nastepnym blokiem w pliku i ustaw w nim offset na 0.

}

Jesli zostaly bufory w tymczasowej tablicy (liczba blokow nie byla wielokrotnoscia 16), to je pozapisuj i pozwalniaj;

Jesli pozycja, w której skonczylismy pisac jest wieksza niz rozmiar pliku, to zwieksz jego rozmiar;

Ustaw w i-wezle czas ostatniej modyfikacji pliku (mtime) i i-wezla (ctime) na obecny;

Ustaw pozycje pliku w tablicy plików na ta, gdzie skonczylismy pisac;

Zaznacz, ze i-wezel jest brudny.

}