# Ćwiczenia 11, grupa cz. 10-12, 12 stycznia 2023

###### tags: `SO22` `ćwiczenia` `pwit`

## Deklaracje

Gotowość rozwiązania zadania należy wyrazić poprzez postawienie X w odpowiedniej kolumnie! Jeśli pożądasz zreferować dane zadanie (co najwyżej jedno!) w trakcie dyskusji oznacz je znakiem ==X== na żółtym tle.

**UWAGA: Tabelkę wolno edytować tylko wtedy, gdy jest na zielonym tle!**

:::warning
**Uwaga**: Dzisiaj deklarujemy zadania **5 -- 8** z **listy 10** oraz **1 -- 5** z **listy 11**.

Formularz deklaracji **listy 10**:
[https://hackmd.io/@iiuwr-kba/rJ9iwWE5s/edit](https://hackmd.io/@iiuwr-kba/rJ9iwWE5s/edit)
:::

:::danger
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
Miriam Bouhajeb | X | X | X | X | X | X | X | X | | |
Kacper Chmielewski | X | X | X | X | X | X | X | X | | X |
Jan Jankowicz | X | X | X | X | X | X | | | | |
Jakub Kaczmarek | | | | | | | | | | |
Jarosław Kadecki | X | X | X | X | | | | | | |
Zuzanna Kania | X | X | X | X | | X | X | X | | |
Julia Konefał | | | X | X | | X | | | | |
Daniel Sarniak | | | | | | X | | | | |
Paweł Tkocz | | X | X | X | X | X | | | | |
Miłosz Urbanik | X | X | X | X | X | X | | X | | |
Tomasz Wołczański | X | X | X | X | | X | | | | |
Radosław Śliwiński | X | X | X | X | | | | | | |
:::

:::info
**Uwaga:** Po rozwiązaniu zadania należy zmienić kolor nagłówka na zielony.
:::

## Zadanie 1
:::success
Autor: Miriam Bouhajeb

Punkt montażowy jest katalogiem lub plikiem, w którym mamy dostęp do innego systemu plików. Dzięki nim istnieje łatwy sposób do dostania się do innych dysków. Aby zmontażować katalog lub system plików, punkt montażowy musi być katalogiem; aby zmontować plik, punkt montażowy musi być plikiem.


Major:minor - nazwy którymi jądro posługuje się aby wewnętrznie identyfikować urządzenia. Pierwsza z liczb sygnalizuje, jakiego sterownika jądro musi używać do komunikacji z tym urządzniem.

SIZE - raczej oczywiste

loop → urządzenie blokowe, którego zawartość jest odwzorowanaw plik zwykły,
part → partycja,
sr → pamięć stała

RM - wartości boolowskie sygnalizujące czy urządzenie można usunąć lub nie
RO - wartości boolowskie sygnalizujące czy urządzenie jest read-only
TYPE - typ urządzenia, takie jak dyski, partycje, loopbacki
MOUNTPOINT - punkt montażowy w którym plik jest zamontowany

Psuedo system pliku - trzyma informacje o obecnej sesji systemu. Nie zostaje ona po ponownych uruchomieniach. Zamiast plików ma wpisy wirtualne które system tworzy na bieżąco np. /proc na wielu systemahc operacyjnych dynamicznie generuje katalogi dla każdego procesu

/proc /sys /dev

relatime - aktualizuje czas dostępu do inode'a zależnie od czasu zmiany pliku. Czas dostępu pliku jest tylko aktualizowany, jesli poprzedni czas dostępu był przed obecnym czasem zmiany. Podobny do noatime, ale nie buguje się gdy jakieś oprogramowanie musi wiedzieć czy plik był czytany od ostatniego czasu modyfikacji.

noexec - zabrania uruchamiania plików binarnych na tym systemie plików

nodev - nie odczytuj specjalnych urządzeń blokowych na tym systemie plików. Również ma na celu ograniczenie zagrożenia. Nie pozwala to systemowi plików tworzyć urządzeń znakowych i zabiera dostęp do hardware'u komputera.
:::

## Zadanie 2
:::success
Autor: Zuzanna Kania


**Superblok** - specjalnie wydzielone miejsce (zawsze na offsecie 1024B od początku urządzenia), w którym przechowywane są metadane systemu plików takie jak np. rozmiar bloku.


**Blok** - najmniejsza jednostka, na jaką podzielone są urządzenia blokowe

**Grupa bloków** - pojedyncze bloki są połączone w grupy, co ogranicza fragmentację i czas odczytu dużej liczby danych.
Zawartość pojedynczej grupy bloków:
* $k$ zależy od liczby grup
* $n$ zależy od liczby i-węzłów w grupie i rozmiaru pojedynczego i-węzła
* $m$ to pozostała liczba bloków w grupie

**Tablica deskryptorów grup bloków** - tablica zawierająca deskryptory dla wszystkich grup bloków. W strukturze deskryptora przechowywane są takie informacje jak np.: lokalizacja bitmap bloków i inode'ów, czy liczba wolnych bloków. Kopie zapasowe tablicy deskryptorów są przechowywane bezpośrednio po każdej kopii superbloku.

### Rozmiar bloku:

### Liczba i-węzłów i bloków przechowywanych w grupie bloków:


### Liczba wpisów tablicy deskryptorów grup bloków:
`s_blocks_count / s_blocks_per_group` - wpisów jest tyle, ile grup
:::

## Zadanie 3
:::success
Autor: Julia Konefał


blok pośredni : blok, który zawiera wskaźniki na inne bloki. Jest wykorzystywany, gdy plik zajmuje dużo miejsca i wymaga dużo bloków.

zapis synchroniczny : zapis, na którego zakończenie czekamy i dopiero wtedy kontynuujemy pracę. Do braku spójności może dojść, gdy na przykład dwa pliki używają tego samego bloku

spójność systemu plików : sytuacja, gdy system plików zawsze operuje na poprawnie zainicjalizowanych strukturach wewnętrznych, nie dochodzi do konfliktów wskaźników (np. dwa pliki niebędące dowiązaniem używają tego samego bloku) oraz nie zawiera wiszących zasobów (np. blok jest zaalokowany ale nie jest używany przez żaden zasób)

Dopisanie n bloków, bądź dopisanie plików do katalogu:

* znajdź niezaalokowany jeszcze blok i oznacz go jako zaalokowany,
* zapisz do niego dane,
* spróbuj dopisać blok z danymi do i-węzła pliku docelowego:
* spróbuj dopisać wskaźnik do bloków bezpośrednich,
* jeśli nie ma miejsca to spróbuj dopisać do listy bloków pośrednich,
* jeśli w drzewie bloków pośrednich nie ma miejsca, to zaalokuj nowe bloki dla bloków pośrednich,
* powiąż ze sobą nowo zaalokowane bloki (bloki pośrednie będziemy alokować od dołu (liścia) do góry, by zapobiec problemom ze spójnością w przypadku awarii),
* dopisz nową gałąź bloków pośrednich do i-węzła pliku docelowego,
* dopisz wskaźnik na blok z danymi do i-węzła pliku, do którego chcemy dopisać dane,
* zaktualizuj metadane i-węzła pliku docelowego (rozmiar, ilość używanych bloków),
* powtórz dopóki są dane do zapisu

:::

## Zadanie 4
:::success
Autor: Jan Jankowicz
:::

Instrukcja atomowa - instrukcja, której wykonanie możemy traktować niepodzielnie, to znaczy tak, jakby wykonywała się w jednym punkcie w czasie

>Czemu «rename» zakończy się błędem «EXDEV» kiedy próbujemy przenieść plik do innego systemu plików?

Przenoszenie plików pomiędzy różnymi systemami plików jest niedozwolone, gdyż docelowy systemowy plików może mieć zupełnie inną reprezentację plików niż np. i-węzły systemu ext2.

>Powtórz polecenia z zadania 3 dla funkcji przenoszącej plik między dwoma różnymi katalogami w obrębie tego samego systemu plików. Zakładamy, że w katalogu docelowym jest wystarczająco dużo miejsca na dodanie wpisu. Pamiętaj, że wpis katalogu nie może przecinać granicy między blokami!


Do przeniesienia pliku pomiędzy katalogami w obrębie tego samego systemu plika będziemy potrzebować wykonać następujące instrukcje:
1. Zaczniemy od znalezienia wpisu katalogowego związanego z plikiem przenoszonym oraz i-node katalogu docelowego.
Ponieważ drugi i-węzeł w tablicy i-węzłów jest powiązany z katalogiem głównym systemu pliku, zaczniemy od niego szukanie katalogu, bądź pliku. Znajdujemy i-węzeł główny i sprawdzając po kolei nazwy w podanej ścieżce, uzyskujemy powiązane z tymi nazwami i-węzły, a tym samy katalogi lub ostatecznie pliki. Tym sposobem wczytamy i-węzeł katalogu pliku źródłowego i i-węzeł katalogu docelowego.
2. W blokach danych katalogu pliku źródłowego znajdujemy wpis linkujący podaną nazwę pliku z i-węzłem pliku, odczytujemy wielkość wpisu z pola rec_len i kopiujemy cały wpis.
3. W blokach danych katalogu docelowego szukamy miejsca na nowy wpis z plikiem. Przechodzimy kolejno wpisy katalogu, aż do:
a) napotkania wpisu z i-węzłem równym 0 (nieużywanym) i jednocześnie o rozmiarze co najmniej równym wpisowi pliku źródłowego;
b) dotarcia do ostatniego wpisu i sprawdzeniu, że pozostała ilość miejsca w bloku jest wystarczająca do dodania nowego wpisu;
Jeśli w bloku katalogu nie uda się znaleźć takiego miejsca, to przechodzimy do następnego bloku.
4. Po znalezieniu wolnego miejsca dodajemy w nim kopię wpisu źródłowego.
5. We wpisie źródłowym ustawiamy wartość i-węzła na 0.

## Zadanie 5
:::success
Autor: Miłosz Urbanik
:::

1. Sprowadzamy inode'a usuwanego pliku zmniejszmy, links_count o 1.
3. Sprowadzamy blok katalogu, który zawiera wpis pliku i go usuwamy.
2. Jeśli links_count > 1 pliku - KONIEC
3. Jeśli istnieją otwarte deskryptory pliku odwołujące się do pliku, czekamy aż zostaną usunięte.
4. Przechodzimy po kolejnych blokach wskazywanych przez inode'a pliku i w ich grupach oznaczamy je jako wolne, oznaczamy inode'a pliku jako wolny
5. Modyfikujemy superblok

Plik można przywrócić jeśli:
* w inodzie pliku i_links_count >= 1
* inode'a pliku nie został nadpisany, i wszystkie bloki na, które wskazuje, również nie zostały nadpisane.

Plik jest faktycznie usunięty, gdy wszystkie jego bloki zostaną nadpisane. Takie zachowanie można wymusić używając bezpiecznego usuwania. W systemie plików `ext2` dostępna jest dla inode'ów flaga `secure delete`.

## Zadanie 6
:::success
Autor: Tomasz Wołczański
:::

Dowiązanie twarde do i-węzła jest tworzone poprzez dodanie do katalogu rekordu zawierającego numer tego i-węzła.

Dowiązanie symboliczne jest plikiem, który zawiera ścieżkę do innego pliku. To oznacza, że do utworzenia dowiązania symbolicznego konieczne jest utworzenie nowego i-węzła.

Zawartość dowiązań symbolicznych krótszych niż 60 bajtów jest przechowywana bezpośrednio w i-węźle (w polach, w których normalnie znajdują się wskaźniki do bloków danych).

Pętlę w systemie plików można stworzyć w następujący sposób:

$ ln -s link1 link2
$ ln -s link2 link1

Zostanie ona wykryta przez jądro w wywołaniu systemowym korzystającym z algorytmu rozwiązywania ścieżek (np. `open`). Takie wywołanie zwróci wtedy błąd `ELOOP`.

Nie da się utworzyć pętli z użyciem dowiązań twardych, bo nie są one same w sobie i-węzłami, a jedynie wpisami w i-węzłach katalogów.

## Zadanie 7
:::success
Autor: Zuzanna Kania

**Fragmentacja systemu plików** polega na tym, że fragmenty jednego pliku są zaalokowane w różnych miejscach na dysku. Jest to zjawisko szkodliwe, ponieważ losowe dostępy do pamięci są zawsze bardziej kosztowne niż dostępy ciągłe.

**Odroczony przydział bloków** polega na tym, że zamiast wykonywać alokację już w momencie operacji write, wykonuje się ją dopiero przy okazji flusha strony cache. Wpływa to po pierwsze na wydajność dzięki ograniczeniu liczby wykonywanych przez CPU operacji. Po drugie dzięki zgromadzeniu większej liczby informacji w momencie faktycznej alokacji umożliwia nie tylko zmniejszenie fragmentacji pojedynczego pliku, ale również zaalokowanie w jego sąsiedzwie plików powiązanych (np. z tego samego katalogu).

**Zakresy** to sposób przechowywania metadanych o adresach bloków, który znacząco zmniejsza ich rozmiar, zwłaszcza w przypadku plików mało pofragementowanych. Jest tak ponieważ zamiast trzymać osobny 6 bajtowy wskaźnik na każdy z bloków, w jednej 12-bajtowej strukturze trzymamy tylko adres pierwszego z nich oraz liczbę kolejnych występujących po nim bloków.

> Extents are arranged as a tree. Each node of the tree begins with a struct ext4_extent_header. If the node is an interior node (eh.eh_depth > 0), the header is followed by eh.eh_entries instances of struct ext4_extent_idx; each of these index entries points to a block containing more nodes in the extent tree. If the node is a leaf node (eh.eh_depth == 0), then the header is followed by eh.eh_entries instances of struct ext4_extent; these instances point to the file's data blocks. The root node of the extent tree is stored in inode.i_block, which allows for the first four extents to be recorded without the use of extra metadata blocks.


**Jak mógłby wyglądać najprostszy algorytm defragmentacji?**
Dla każdego pliku tworzymy tymczasowy i-węzeł, któremu alokujemy ciągły fragment pamięci. Następnie kopiujemy zawartość oryginalnego pliku do pamięci podręcznej, a stamtąd do bloków węzła tymczasowego. Na końcu podmieniamy wskaźniki na bloki w pliku oryginalnym na wskaźniki z pliku tymczasowego.

Po takiej defragmentacji liczba wolnych bloków może wzrosnąć, ponieważ dzięki niej zmniejsza się liczba zakresów koniecznych do zapamiętania całej zawartości pliku.
:::

## Zadanie 8
:::success
Autor: Miłosz Urbanik

:::

**partycja** - wydzielona część dysku, na której znajduje się system plików. Podział dysku na partycje opisany jest w strukturze na początku dysku np. `MBR (master boot record)` lub `GPT (GUID partition table)`

Poniższe polecenia wykonywane są w trybie interaktywnym programu `debugfs` uruchomionym na zamontowanej partycji

- `freefrag` - fragmentacja wolnego miejsca
- `show_super_stats` - informacje o superbloku i grupach bloków
- `filefrag -v <nazwa_pliku>` - informacje o przedziałach bloków
- `inode_dump <nazwa_linku_symbolicznego>` - wypisana zawartość inode'a
- `blocks <nazwa_pliku>` - bloki należące do pliku
- `icheck <nr bloku>` - inode'y używające bloku
- `ncheck <nr inode'a>` - ścieżki plików wskazujących na inode'a
- `dump <nazwa_katalogu> <plik_docelowy>` - zawartość bloków katalogu

Program `filefrag` z opcją `-v` wypisuje ciągłe przedziały pliku, adresy logiczne, fizyczne i oczekiwane przedziałów oraz ich długość.
Adres przedziału *expected* to poprostu suma adresu fizycznego i rozmiaru poprzedniego przedziału.

Kod źródłowy programu`filefrag` z pakietu `debugfs`
https://github.com/tytso/e2fsprogs/blob/master/debugfs/filefrag.c.

## Zadanie 9
:::danger
Autor: dodeklarować/PWit
:::

## Zadanie 10
:::success
Autor: Kacper Chmielewski

**dziennik** - rejestrowane sa w nim wszystkie aktualizacje metadanych
**transakcja** - grupa bloków, która zawiera informacje o ostatnio rejestrowanych aktualizacjach
**idempotentne** - oznacza, że operacje mogą być powtarzane tak często jak to potrzeba bez szkody, np. "Update the bitmap to mark i-node k or block n as free"

**Opisz znaczenie poszczególnych bloków z których może składać się pojedyncza transakcja.**

**TxB** - mówi nam o aktualizacji, w tym oczekujących aktualizacjach systemu plików oraz identyfikator transakcji (TID)

Pomiedzy TxB i TxE są bloki z dokładnymi danymi, które chcemy zaksięgować.

**TxE** - blok końcowy, jest oznaczeniem końca transakcji, również zawiera TID

**Czym różni się księgowanie metadanych od księgowania danych?**
**Księgowanie danych:**

**Księgowanie metadanych:**

**Czemu operacje składowane w dzienniku muszą być idempotentne?**
Po to aby ewentualne przywrócenie danych systemu, było szybkie i bezpieczne

Journal starts at block 23333, transaction 10932
Found expected sequence 10932, type 1 (descriptor block) at block 23333
Found expected sequence 10932, type 2 (commit block) at block 23340
Found expected sequence 10933, type 1 (descriptor block) at block 23341
Found expected sequence 10933, type 2 (commit block) at block 23362
Found expected sequence 10934, type 1 (descriptor block) at block 23363
Found expected sequence 10934, type 2 (commit block) at block 23366
Found expected sequence 10935, type 1 (descriptor block) at block 23367
Found expected sequence 10935, type 2 (commit block) at block 23383

:::