System plików

Algorytm przekształcania nazwy ścieżkowej na i-węzeł - namei

Krzysztof Sikora

1. Wstęp

Katalogi w bardzo naturalny sposób pozwalają gromadzić, a przede wszystkim sortować dane. Ponieważ operowanie i-węzłami podczas ich tworzenia, usuwania i modyfikacji byłoby uciążliwe i niepraktyczne, użytkownik korzysta z nazw katalogów (np. /home/inf/k/ks181291). Jednak szkieletem systemu plików w jądrze są i-węzły, musi więc istnieć sposób tłumaczenia nazwy ścieżkowej na postać zrozumiałą dla jądra. Tym właśnie zajmuje się algorytm namei. Korzystają z niego między innymi open, stat i mkdir.

2. Lokalizacja

Algorytm namei znajduje się w pliku fs/namei.c.

3. Działanie

Algorytm namei jest właściwie funkcją __user_walk, do której odwołują się odpowiednie makra. Główna cześć algorytmu to funkcja path_walk.

Nagłówek:

int __user_walk(const char *name, unsigned flags, struct nameidata *nd)

Dane wejściowe:

Dane wyjściowe:

Idea działania algorytmy wydaje się być prosta (Rysunek 1). Polega on na przeglądaniu ścieżki i odcinaniu kolejnych jej składowych. Każda składowa jest przekształcana na numer i-węzła. Zwracany jest i-węzeł odpowiadający ostatniej składowej. Jednak podczas przeglądania czyhają zasadzki w postaci dowiązań symbolicznych, praw dostępu i punktów montowania innych systemów plików.
Przyjrzyjmy się wiec dokładniej działaniu algorytmu namei. Dla przykładu weźmy katalog /home/ks181291/dijkstra.c. Nazwa ścieżki zaczyna się od '/', wiec przeszukiwanie zaczynamy od korzenia struktury katalogów, którego i-węzeł staje się i-węzłem roboczym (funkcja walk_init_root). Zostają sprawdzone prawa do przeglądania katalogu. Następnie pobieramy kolejną cześć ścieżki czyli home i przeszukujemy pozycje katalogowe roboczego i-węzła w celu odnalezienia pozycji rozpatrywanej składowej (najpierw szukamy w pamięci podręcznej katalogów cached_lookup, w przypadku niepowodzenia na dysku read_lookup). Tam też zostaje zamieniony roboczy i-węzeł na i-węzeł znalezionej pozycji (gdybyśmy takiej nie znaleźli oznaczałoby to nieprawidłową ścieżkę). Sprawdzamy czy nie jest to punkt montowania systemu plików lub dowiązanie symboliczne. Te instrukcje kończą główna pętle. Zostaje odcięta składowa ks181291, a potem dijkstra.c, która okazuje się ostatnią. Zostaje wiec zwrócony i-węzeł tej składowej.

Rysunek 1: Schemat blokowy algorytmu namei

4. Uwagi

Należy zaznaczyć, ze funkcja namei jest odporna na znaki '/'. To znaczy może być ich dowolna ilość na początku, na końcu i między nazwami katalogów.

5. Poprzednie wersje

Funkcja namei została przepisana na nowo.
Zmieniły się zasady przechodzenia po dowiązaniach symbolicznych. Stosuje się w następującej kolejności: