# Systemy Operacyjne 11
## Zadanie 1

_Wyjaśnij czym są punkty montażowe, a następnie wyświetl listę zamontowanych systemów plików_

**Punkt montażowy** - Miejsce w partycji używane jako korzeń systemu plików (A mount point is a location in the partition used as a root filesystem)

Można wyświetlić zamontowane (mounted) systemi plików przy pomocy `findmnt`.

_wyjaśnij co znajduje się w poszczególnych kolumnach wydruku._

https://www.tecmint.com/find-mounted-file-systems-in-linux/
Wskazany punkt montażowy (TARGET),
urządzenie źródłowe (SOURCE),
typ systemu plików (FSTYPE),
opcje zamontowania każdego systemu(OPTIONS).

_Które z punktów montażowych dają dostęp do instancji pseudo systemów plików?_

``findmnt --pseudo``

**pseudo system plików** - hierarchiczny interfejs dla nie-plikowych obiektów, które wyglądają jak noramalne pliki, w drzewie opartym-na-dysku lub długoterminowego-przechowywania systemu plików.
:::spoiler
**pseudo file system**
In computer science, a synthetic file system or a pseudo file system is a hierarchical interface to non-file objects that appear as if they were regular files in the tree of a disk-based or long-term-storage file system.

For example, /proc on many OSes is a procfs which dynamically generates directories for every process. Similarly, /sys on Linux generates files and directories to represent hardware layouts.
:::

_Na podstawie mount(8) wyjaśnij znaczenie następujących atrybutów punktów montażowych: «relatime», «noexec» i «nodev», a następnie podaj scenariusz, w którym ich zastosowanie jest pożądane._

- `relatime`- zaktualizuj dostępy czasu inode'a w stosunku do czasu modyfikacji lub zmiany.
- `noexec`- nie pozwalaj na bezpośrednie wykonywanie binarek na zamontowanych (mounted) systemach plików. Dla bezpieczeństwa.
- `nodev` - nie interpretuj urządzeń znakowych ani blokowych na (montowanym) systemie plików. Dla bezpieczeństwa.
:::spoiler
`relatime`- Update inode access times relative to modify or change time. Access time is only updated if the previous access time was earlier than the current modify or change time. (Similar to noatime, but it doesn’t break mutt(1) or other applications that need to know if a file has been read since the last time it was modified.)

`noexec`- Do not permit direct execution of any binaries on the mounted filesystem.

`nodev` - Do not interpret character or block special devices on the filesystem.
The nodev mount option specifies that the filesystem cannot contain special devices: This is a security precaution. You don't want a user world-accessible filesystem like this to have the potential for the creation of character devices or access to random device hardware.

:::

## Zadanie 2 Marcin

**superblok** - jest zasadniczo metadanymi systemu plików i definiuje typ systemu plików, rozmiar, stan oraz informacje o innych strukturach metadanych (metadane metadanych). Superblok jest bardzo krytyczny dla systemu plików i dlatego jest przechowywany w wielu nadmiarowych kopiach dla każdego systemu plików. Superblok to bardzo „wysokopoziomowa” struktura metadanych dla systemu plików. Na przykład, jeśli superblok partycji, /var, ulegnie uszkodzeniu, dany system plików (/var) nie może zostać zamontowany przez system operacyjny. Główna kopia superbloku jest przechowywana na offsecie 1024 bajtów od początku urządzenia.

**blok** - W `EXT2` blokiem nazywa się sektory, na które podzielone są partycje, dyski, pliki i urządzenia blokowe.
Każdy system plików ext2 składa się z bloków, które są podzielone na grupy bloków. Bloki mogą mieć długość 1k, 2k lub 4k.

**tablica deskryptorów grupy bloków** - Każda grupa bloków ma opisującą ją strukturę danych. Podobnie jak Superblok, wszystkie deskryptory grup dla wszystkich grup bloków są duplikowane w każdej grupie bloków w przypadku uszkodzenia systemu plików.

Każdy deskryptor grupy zawiera następujące informacje:

* Mapy bitowe bloków -Numer bloku mapy bitowej alokacji bloków dla tej grupy bloków. Jest to używane podczas alokacji i zwalniania bloków,
* Bitmapa inod - Numer bloku mapy bitowej alokacji inod dla tej grupy bloków. Jest to używane podczas alokacji i zwalniania inod,
* Tabela inod -Numer bloku początkowego dla tablicy inod dla tej grupy bloków. Każda inoda jest reprezentowana przez opisaną poniżej strukturę danych inod `EXT2`.
* Liczba wolnych bloków, liczba wolnych i-węzłów, liczba używanych katalogów

Deskryptory grup są umieszczane jeden po drugim i razem tworzą tablicę deskryptorów grup. Każda Grupa Bloków zawiera całą tablicę deskryptorów grup po swojej kopii Superbloku. Tylko pierwsza kopia (w grupie bloków 0) jest faktycznie używana przez system plików `EXT2`. Inne kopie są tam, podobnie jak kopie Superbloku, na wypadek gdyby główna kopia była uszkodzona.

**grupa bloków** - Grupy bloków zmniejszają fragmentację plików, ponieważ jądro stara się, jeśli to możliwe, przechowywać bloki danych należące do pliku w tej samej grupie bloków. Każdy blok w grupie bloków zawiera jedną z następujących informacji :
* Kopię superbloku
* Kopię deskryptorów grupy
* Mapę bitowa bloku danych
* Bitmapa inod
* Tablica inod
* Fragment danych należący do pliku; tj. bloki danych

Każda grupa bloków zawiera tyle bloków, ile jeden blok może pomieścić mapę bitową, więc przy rozmiarze bloku 1k ​​grupa bloków zawiera 8192 bloków (1024 bajty * 8 bitów), a przy rozmiarze bloku 4k grupa bloków zawiera 32768 bloków. Grupy są numerowane począwszy od 0 i występują jedna po drugiej na dysku, w kolejności, bez przerw między nimi.

Rozmiar bloku: `block size = 1024 << s_log_block_size`.
Liczba inod w grupie: `s_inodes_per_group`.
Liczba bloków w grupie: `s_blocks_per_group`.
Liczba wpisów tablicy deskryptorów grup bloków: `s_blocks_count / s_blocks_per_group`.

Każda grupa bloków składa się z kopii superbloku, kopii tablicy deskryptorów grupy bloków, bitmapy bloku, bitmapy inody, tablicy inod i bloków z danymi. Rozmiar obu bitmap to 1 bajt dla każdej, tablica inod zajmuje `s_inodes_per_group / inodes_per_block`, gdzie `inodes_per_block = block_size / s_inode_size`, a resztę miejsca zajmują bloki z danymi.
## Zadanie 3

**Blok pośredni** (ang. indirect block) to blok zawierający wskaźniki na inne bloki pośrednie lub na bloki danych, zwykle jest używany przy pracy z dużymi plikami.

**Zapis synchroniczny** wykonywany jest za pomocą polecenia fsync(2) lub fdatasync(2). Oznacza to, że dane zapisywane są do deskryptora pliku fd na dysku (lub innym urządzeniu) w taki sposób, że po crashu systemu lub reboocie pliki nadal mogą zostać odzyskane.

**Spójność systemu plików** polega na zapisie plików o podobnym zastosowaniu w grupach (lub jakiejś przestrzeni nazw, która łączy te pliki).

_Podaj listę kroków niezbędnych do realizacji funkcji dopisującej n bloków na koniec pliku._

Wybieramy wolne bloki i zapalamy ich bity, aby zaznaczyć, że są używane. Następnie zapisujemy zawartość tych bloków i dodajemy bloki do i-węzła: w razie potrzeby tworzymy bloki pośrednie lub modyfikujemy aktualnie istniejące, a później aktualizujemy metadane i-węzła: wskaźniki na bloki, rozmiar i timestamp.

Aby dodać plik do katalogu, w którym nie ma miejsca, wybieramy jakiś wolny blok B i zapalamy bit użycia (tak jak wyżej). Załóżmy też, że korzystamy z linked list, a nie bardziej skomplikowanej struktury jak drzewo. W wybranym bloku B dodajemy wpis pliku do linked list, a więc ustawiamy odpowiedni i-węzeł inode, nazwę name, długość nazwy name_len i typ type, a następnie koniec bieżącego katalogu rec_len. Ostatnim zadaniem jest dodanie bloku B do i-węzła katalogu w taki sposób, jak wyżej.

## Zadanie 4

**Atomowość** polega na wykonaniu operacji w pełni, albo w ogóle. Oznacza to, że plik zostanie przeniesiony w całości, albo wcale, nie może się wydarzyć nic “pomiędzy”. Sprawia to, że wykonywanie różnych akcji jest bezpieczniejsze, jako że mamy pewność, że nie zostanie wykonany jakiś ułamek całości.

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

rename może zakończyć się błędem EXDEV, gdy oldpath i newpath nie są zamontowane w tym samym systemie plików lub gdy są zamontowane w kilku miejscach - Linux zezwala na takie zachowanie, jednak samo działanie rename jest zdefiniowane w taki sposób, że nie pozwala na przenoszenie plików między różnymi punktami montowania.

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

Zwiększamy licznik dowiązań i_links_count w i-węźle przenoszonego pliku, a jeśli w katalogu docelowym jest wyzerowany wpis (katalog pusty), to zmieniamy go na wpis pliku, który przenosimy. W przeciwnym wypadku dodajemy do katalogu docelowego wpis przenoszonego pliku i modyfikujemy poprzedni w taki sposób, aby nie wskazywał na koniec bloku. W poprzednim katalogu “usuwamy” wpis zmieniając wartość inode na 0 i zmieniamy licznik dowiązań w i-węźle tego pliku (przed przeniesieniem i po powinien być taki sam - jest to pewnego rodzaju niezmiennik, jako że nie wykonujemy kopii, to w systemie powinno być tyle samo dowiązań).

## Zadanie 5 Kornelia

_Powtórz polecenia z zadania 3 dla funkcji usuwającej plik zwykły z katalogu._

??????

Działanie `unlink()` :
Usuwa dowiązanie do pliku oraz zmniejsza o jeden licznik dowiązań do tego pliku (w i-węźle). Jeśli licznik wynosi teraz 0, to zwalnia i-węzeł oraz bloki.

_Kiedy możliwe jest odwrócenie operacji usunięcia pliku tj. odkasowania (ang. undelete)?_

Kiedy i-node i bloki pliku nie zostały jeszcze nadpisane.

_Zauważ, że usunięcie pliku nie odbiera procesom możliwości czytania jego zawartości, o ile go otworzyły przed wywołaniem unlink(2). Kiedy w takim razie plik zostanie faktycznie usunięty z dysku?_

Plik zostanie usunięty, gdy wywołamy `unlink()` na ostatnim dowiązaniu do pliku i wszystkie deskryptory wskazujące na plik zostaną zamknięte.

:::spoiler man

unlink() deletes a name from the filesystem.  If that name was
       the last link to a file and no processes have the file open, the
       file is deleted and the space it was using is made available for
       reuse.

       If the name was the last link to a file but any processes still
       have the file open, the file will remain in existence until the
       last file descriptor referring to it is closed.

:::

## Zadanie 6 Kuba

_Wyjaśnij co robi system plików ext2 przy tworzeniu dowiązania twardego (ang. hard link) i symbolicznego (ang. symbolic link). Gdzie jest przechowywana zawartość dowiązania symbolicznego?_

**Dowiązanie twarde** (ang. hard link) to wskaźnik na i-węzeł pliku, wlicza się do licznika referencji do pliku. W i-węźle zwiększany jest licznik dowiązań `i_links_count`, a w katalogu tworzone jest mapowanie `name - inode`, czyli wiele wpisów pliku z różnych katalogów wskazuje na ten sam i-węzeł.

**Dowiązanie symboliczne** (ang. symbolic link) to dowiązanie kodujące ścieżkę, do której należy przekierować algorytm rozwiązywania nazw. Dla wszystkich dowiązań symbolicznych krótszych niż 60 bajtów dane są przechowywane w i-węźle.

Różnicę między dowiązaniami można przedstawić w taki sposób:

      +--------- inode     symlink
      |            |          |
 hard link         +-- file --+

_Jak za pomocą dowiązania symbolicznego stworzyć w systemie plików pętlę?_

Należy w dowolnym katalogu stworzyć dowiązanie symboliczne (flaga `-s`) do katalogu `.`, a więc tego, w którym się aktualnie znajdujemy, lub do katalogu `../[katalog]`:

~/foo$ ln -s . link
~/foo$ ln -s ../foo/ link2

_Kiedy jądro systemu operacyjnego ją wykryje i zwróci błąd «ELOOP»?_

Z podręcznika `path_resolution(7)` na temat błędu `ELOOP` dowiadujemy się tyle, że zostaje on zwracany, gdy zostanie przekroczona maksymalna głębokość rekursji (dla symlinków).

_Czemu pętli nie da się zrobić z użyciem dowiązania twardego?_

Gdyż struktura danych systemu plików jest skierowanym grafem acyklicznym, a dowiązanie twarde stworzyłoby cykl, co sobie przeczy.

## Zadanie 7 kasia
::: spoiler artykul
**Delayed allocation** is a well-known technique in which block allocations are postponed to page flush time, rather than during the write() operation [3]. This method provides the opportunity to combine many block allocation requests into a single request, reducing possible fragmentation and saving CPU cycles. Delayed allocation also avoids unnecessary block allocation for shortlived files.

The ext3 filesystem uses an indirect block mapping scheme providing one-to-one mapping from logical blocks to disk blocks. This scheme is very efficient for sparse or small files, but has high overhead for larger files, performing poorly especially on large file delete and truncate operations.

An **extent** is a single descriptor which represents a range of contiguous physical blocks. The physical block field in an extents structure takes 48 bits. A single extent can represent 215 contiguous blocks, or 128 MB, with 4 KB
block size. The MSB of the extent length is used to flag
uninitialized extents, used for the preallocation feature.
:::
_Czemu fragmentacja systemu plików jest szkodliwym zjawiskiem?_

Plik jest pofragmentowany, jeśli jest przechowywany na dysku w więcej niż jednym spójnym fragmencie.
Zmiana pozycji głowicy dysku magnetycznego jest kosztowna.
Losowe dostępy do dysku SSD są również wolniejsze niż sekwencyjne.

_Opisz w jaki sposób odroczony przydział bloków (ang. delayed allocation) [§3.2] zapobiega powstawaniu fragmentacji._

odroczony przydział bloków - na k sekund, grupujemy w pamięci zapisy wymagające przydziału nowych bloków w nadziei na zmniejszenie ogólnej liczby fragmentów.

_Wytłumacz jak zakresy (ang. extents) [§2.2] pomagają w ograniczaniu rozmiaru metadanych przechowujących adresy bloków należących do danego pliku._

**Zakresy** ograniczają metadane pliku, zamiast przechowywać dokładne mapowanie dla każdego bloku, grupujemy je w zakresy. Zakres to pojedynczy deskryptor reprezentujący przedział ciągłych fizycznych bloków. Struktura zakresu zajmuje 48 bitów a może reprezentować 2^15 ciągłych bloków. 128MB danych.
:::spoiler
Każdy węzeł w drzewie zaczyna się nagłówkiem, który zawiera liczbę poprawnych wpisów w węźle. Sposób, w jaki zakresy pomagają w ograniczaniu rozmiaru metadanych jest dość prosty: tworzony jest tymczasowy i-węzeł, a następnie alokowany w nim jest ciągły zakres. Następnie dane są kopiowane z oryginalnego i-węzła do tymczasowego, do czego wykorzystywany jest odroczony przydział bloków. Na samym końcu przepinane są wskaźniki na bloki z tymczasowego i-węzła do oryginalnego. W taki sposób odbywa się defragmentacja, dzięki której możemy uzyskać więcej wolnych bloków - używane będzie mniej zakresów, niż poprzednio.
:::
_Czy po defragmentacji systemu plików ext4 liczba wolnych bloków może wzrosnąć?_

usuwamy drzazgi, wiec tak

_Jak mógłby wyglądać najprostszy algorytm defragmentacji [§3.3]?_

For each file, the tool creates a temporary inode and allocates contiguous extents to the temporary inode using multiple block allocation. It then copies the original file data to the page cache and flushes the dirty pages to the temporary inode’s blocks. Finally, it migrates the block pointers from the temporary inode to the original inode.

## Zadanie 8

>>>sudo debugfs /dev/sda5
>>>debugfs: freefrag
Opisuje fragmentację wolnego miejsca w aktualnie otwartym systemie plików. 
Jeśli podano opcję -c, polecenie wypisze ile wolnych fragmentów 
o podanym rozmiarze można znaleźć w systemie plików.

>>>debugfs: stats
Wypisz zawartość superbloku i deskryptory grup bloków. 
Jeśli podano opcję -h, wypisuje tylko zawartość superbloku.

>>>fallocate -l 10GB largefile
>>>sudo debugfs -R "dump_extents home/usr/largefile" /dev/sda5

Wypisuje drzewo przydziałów specyfikacji pliku i-węzła. Flaga -n spowoduje, że dump_extents wyświetli tylko wewnętrzne węzły w drzewie przydziałów. Flaga -l spowoduje, że dump_extents wyświetli tylko węzły liści w drzewie przydziałów.

>>>ln -s /home/usr/so/lista9/so20_lista_9 /home/usr
>>>sudo debugfs /dev/sda5
>>>inode_dump /home/usr/so20_lista_9

0000  ffa1 e803 2100 0000 f02a f65f f02a f65f  ....!....*._.*._
0020  f02a f65f 0000 0000 e803 0100 0000 0000  .*._............
0040  0000 0000 0100 0000 2f68 6f6d 652f 6567  ......../home/us
0060  6f72 2f73 6f2f 6c69 7374 6139 2f73 6f32  r/so/lista9/so20
0100  305f 6c69 7374 615f 3900 0000 0000 0000  _lista_9........
0120  0000 0000 0000 0000 0000 0000 0000 0000  ................
0140  0000 0000 f460 d809 0000 0000 0000 0000  .....`..........
0160  0000 0000 0000 0000 0000 0000 7eaa 0000  ............~...
0200  2000 0bf4 00e0 7b81 00e0 7b81 a805 7082   .....{...{...p.
0220  f02a f65f 00e0 7b81 0000 0000 0000 0000  .*._..{.........
0240  0000 0000 0000 0000 0000 0000 0000 0000  ................

>>>debugfs:  blocks /home/usr/jbs
>>>3737548 3737549 3737550
>>>debugfs:  icheck 3737549
>>>Block	Inode number
   3737549	924778
>>>debugfs:  ncheck 924778
>>>Inode	Pathname
   924778	/home/usr/jbs


>>>debugfs:  blocks /home/usr/Downloads
>>>3681327
>>>debugfs:  block_dump 3681327
>>>
0000  9b60 0e00 0c00 0102 2e00 0000 e119 0e00  .`..............
0020  0c00 0202 2e2e 0000 ec06 0400 1c00 1301  ................
0040  736f 3230 5f6c 6973 7461 5f39 2e74 6172  so20_lista_9.tar
0060  2e67 7a00 e904 0600 c00f 0901 3267 7261  .gz.........2gra
0100  6d73 2e67 7a00 0000 5b02 0e00 ac0f 0601  ms.gz...[.......
0120  3267 7261 6d73 2e67 7a2e 7061 7274 0000  2grams.gz.part..
0140  0000 0000 0000 0000 0000 0000 0000 0000  ................
*
7760  0000 0000 0000 0000 0c00 00de f9c0 f568  ...............h

## Zadanie 9(Bonus)

## Zadanie 10(Bonus)