---
# System prepended metadata

title: 'Lista 9, 19 maja 2021'
tags: [sju21, ćwiczenia]

---

# Lista 9, 19 maja 2021

###### tags: `sju21` `ćwiczenia`

## Deklaracje

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

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

:::success
|                       | 9-1 | 9-2 | 9-3 | 9-4 |
| ---------------------:| --- | --- | --- | --- |
|           Jacek Bizub |  X  |==X==|  X  |  X  | 4
|     Wojciech Jasiński |==X==|  X  |     |  X  | 3
|        Artur Juraszek |  X  |  X  |     |==X==| 3
|     Michał Myczkowski |     |     |     |     | 0
|   Michał Jan Odorczuk |  X  |  X  |==X==|  X  | 4
|       Damian Ratajski |     |     |     |     | 0
|         Łukasz Siudek |     |     |     |     | 0
|           Błażej Sowa |  X  |  X  |     |  X  | 3
|         Andrzej Turko |     |     |     |     | 0
|  Maksymilian Zawartko |     |     |     |     | 0
:::

## Zadanie 9-1

:::info
Autor: Wojciech Jasiński
:::
  * Wymień główne zadania pełnione przez system tłumaczenia ścieżek [namei(9)](http://mdoc.su/f/9/namei)
    - kopiowanie ścieżki do tłumaczenia z przestrzeni użytkownika
    - ustalanie punktu startowego ścieżki
    - trawersowanie ścieżki (także na wskroś dowiązań symbolicznych i punktów montażowych) za pomocą funkcji lookup zależnej od systemu plików
  * Zidentyfikuj w kodzie [namei](https://mimiker.ii.uni.wroc.pl/source/xref/FreeBSD/sys/kern/vfs_lookup.c?r=80f39bd9#namei) i [lookup](https://mimiker.ii.uni.wroc.pl/source/xref/FreeBSD/sys/kern/vfs_lookup.c?r=80f39bd9#lookup) fragmenty odpowiedzialne za obsługę trawersowania ścieżki przez: katalogi, dowiązania symboliczne i punkty montażowe
    - 555: copy in name
    - 573: lookup cache
    - 596: get starting directory
      - nameisetup: 335
    - 607: while (!done && !error):
      - 609: call lookup on the path.
        - lookup:
          - 853..859..: select path component
          - 945..1019: special cases for ".." component
            - 986: if current dir is a mount, continue from containing vnode
          - 1056: VOP_LOOKUP
          - 1127..: if the new directory was mounted on
              - 1138: VFS_ROOT: look up the root of the mounted filesystem (and proceed)
          - 1150..1177: check for symbolic link, manage locks 
      - ..654..: if symbolic link, massage name in buffer and continue
          - 654: VOP_READLINK
## Zadanie 9-2

:::info
Autor: Jacek Bizub
:::

> Przeczytaj [1,§7.4, „The Name Cache”] i odpowiedz na następujące pytania.

---

> Jaką rolę pełni podsystem `buforowania ścieżek` [namecache(9)](http://man.netbsd.org/namecache.9)?

The name lookup cache is the mechanism to allow the file system type
     dependent algorithms to quickly resolve a file's vnode from its pathname.
     The name lookup cache is generally accessed through the higher-level
     namei(9) interface.

The name of the file is used to look up an entry associated with the file
     in the name lookup cache.  If no entry is found, one is created for it.
     If an entry is found, the information obtained from the cache lookup con-
     tains information about the file which is useful to the file system type
     dependent functions.

The name lookup cache is managed by a least recently used (LRU) algorithm
     so frequently used names will hang around.  The cache itself is a hash
     table called nchashtbl, containing namecache entries that are allocated
     dynamically from a kernel memory pool.

---

> Kiedy  użycie `wpisów zaprzeczających` (ang.negative entry) o istnieniu  danej  ścieżki  ma  sens?

- Przyklad: przeszukiwanie `PATH`

Wpisujemy do terminala `gcc ...` - nie jest to wbudowane polecenie a program. Program ten trzeba odnaleźć. W tym celu przeszukujemy katalogi ze zmiennej `PATH`. Katalogów jest kilka, zazwyczaj zawierają względnie dużo wpisów (vide `/bin`). Przeszukiwanie całości za każdym razem kiedy wołamy jakiś program jest nieefektywne. Jeżeli wiemy, że w danym katalogu nie ma danego pliku to możemy to explicite zaznaczyć stosujać wpis negatywny. Wtedy przy następnym poszukiwaniu pliku będziemy mogli prawie od razu odrzucić dany katalog.

---

> W  implementacji  systemu  plików [ext2](https://mimiker.ii.uni.wroc.pl/source/xref/NetBSD/sys/ufs/ext2fs/) wskaż  funkcję  interfejsu [vnodeops(9)](http://man.netbsd.org/vnodeops.9), która wykorzystuje funkcje «cache_lookup», «cache_enter» i «cache_purge». Wytłumacz do czego służą te funkcje na podstawie wskaznaych przypadków użycia.

[lookup](https://mimiker.ii.uni.wroc.pl/source/xref/NetBSD/sys/ufs/ext2fs/ext2fs_lookup.c?r=1fe5c4da&mo=10983&fi=332#332)

[enter](https://mimiker.ii.uni.wroc.pl/source/search?full=cache_enter&path=%22%2FNetBSD%2Fsys%2Fufs%2Fext2fs%2F%22&project=NetBSD)


[purge](https://mimiker.ii.uni.wroc.pl/source/search?project=NetBSD&full=cache_purge&defs=&refs=&path=%22%2FNetBSD%2Fsys%2Fufs%2Fext2fs%2F%22&hist=&type=&xrd=&nn=1&si=full&si=full)

- cache_lookup(dvp, name, namelen, nameiop, nameiflags, iswhiteout, vpp)

Look for a name in the cache.  cache_lookup() is called with dvp
           pointing to the vnode of the directory to search.  The name and
           namelen arguments specify the name to look for.  The nameiop and
           nameiflags should be taken from the cn_nameiop and cn_flags fields
           of struct componentname.

The lookup can produce either a cache miss or a cache hit, and a
           cache hit can either be a positive hit, where the name looked up
           refers to some existing object, or a negative hit, where the name
           looked up is known to refer to no existing object.  (The lookup
           cannot fail, in the sense of generating an error condition that
           requires aborting the operation in progress.)
          
- cache_enter(dvp, vp, name, namelen, nameiflags)

Add an entry to the cache.  The name and namelen arguments specify
           the name to add to the cache.  The dvp argument specifies the
           directory the name appears in.  The vp argument specifies the
           object to enter in the cache.  The nameiflags argument should come
           from the cn_flags member of struct componentname.

If vp is NULL, a negative cache entry is created, specifying that
           the entry does not exist in the file system.
           
           
- cache_purge(vp)

Flush the cache of a particular vnode vp.  cache_purge() is called
           when a vnode is renamed to hide entries that would now be invalid.

---

> Jakie kroki należy przedsięwziąć, gdy użytkownik zmieni nazwę katalogu lub zdemontuje system plików?

Wszystkie ścieżki, które prowadziły przez dany katalog/fs przestają być aktualne. Trzeba każdą taką usunać z cache'u.

## Zadanie 9-3

:::success
Autor: Michał Jan Odorczuk
:::

> Przeczytaj [1, §7.4, „Buffer Management”] i odpowiedz na następujące pytania dotyczące pamięci podręcznej bloków (ang. block cache). Jaką rolę pełnią kolejki LOCKED, DIRTY, CLEAN i EMPTY z poniższego obrazka. Kto odpowiada za synchronizację brudnych bloków z dyskiem? Na podstawie procedury [incore] wytłumacz jak szybko dowiedzieć się czy dany fragment pliku jest w buforze. Przeprowadź uczestników zajęć przez procedurę [bread]. Rozważ dwa scenariusze (a) bufor zawierający blok jest w pamięci podręcznej (b) trzeba wczytać blok z dysku do nowo utworzonego bufora. Ogranicz się do procedur «getblk», «bio_doread» i «biowait». ![](https://i.imgur.com/hn3rUJB.png)

[incore]:https://mimiker.ii.uni.wroc.pl/source/xref/NetBSD/sys/kern/vfs_bio.c?r=1fe5c4da#incore

[bread]:https://mimiker.ii.uni.wroc.pl/source/xref/NetBSD/sys/kern/vfs_bio.c?r=1fe5c4da#bread

- LOCKED - kolejka dla buforów użytkowanych w tle
- DIRTY - kolejka buforów po edycji przed flushem
- CLEAN - kolejka buforów gotowych do użycia bez zaległych zapisów do dysku
- EMPTY - kolejka niezmapowanych buforów

Zapis do dysku zachodzi na buforach DIRTY regularnie 20-30 sekund od ostatniej edycji. Użytkownik może przyspieszyć ten proces.

Znajdź hash bloku zawierającego dany fragment i namierz w bufhash namiar do bufora.

bread:
* [wywołanie bio_doread](https://mimiker.ii.uni.wroc.pl/source/xref/NetBSD/sys/kern/vfs_bio.c?r=1fe5c4da#747):
    * [wywołanie getblk](https://mimiker.ii.uni.wroc.pl/source/xref/NetBSD/sys/kern/vfs_bio.c?r=1fe5c4da#685):
        * wyszukaj blok za pomocą [incore](https://mimiker.ii.uni.wroc.pl/source/xref/NetBSD/sys/kern/vfs_bio.c?r=1fe5c4da#1210)
        * [jeżeli nie ma](https://mimiker.ii.uni.wroc.pl/source/xref/NetBSD/sys/kern/vfs_bio.c?r=1fe5c4da#1211), to dodaj do [bufora](https://mimiker.ii.uni.wroc.pl/source/xref/NetBSD/sys/kern/vfs_bio.c?r=1fe5c4da#1230) i [sprawdź](https://mimiker.ii.uni.wroc.pl/source/xref/NetBSD/sys/kern/vfs_bio.c?r=1fe5c4da#1233), czy po drodze nie został dodany z zewnątrz. Jeśli nie to dodaj do [bufhasha](https://mimiker.ii.uni.wroc.pl/source/xref/NetBSD/sys/kern/vfs_bio.c?r=1fe5c4da#1239), w przeciwnym wypadku [zwolnij](https://mimiker.ii.uni.wroc.pl/source/xref/NetBSD/sys/kern/vfs_bio.c?r=1fe5c4da#1235) nowo powstały.
        * po uzyskaniu bufora sprawdź, czy nie jest [zablokowany](https://mimiker.ii.uni.wroc.pl/source/xref/NetBSD/sys/kern/vfs_bio.c?r=1fe5c4da#1257), jeśli jest to usuń z bufora.
    * [rozpocznij czytanie](https://mimiker.ii.uni.wroc.pl/source/xref/NetBSD/sys/kern/vfs_bio.c?r=1fe5c4da#702) - [VOP_STRATEGY](https://man.netbsd.org/VOP_STRATEGY.9) czyta z vnode'a do uzyskanego bufora
* zwróć wynik czytania.

## Zadanie 9-4

:::info
Autor: Artur Juraszek
:::


* _superblok_ - znajdująca się pod stałym offsetem struktura (dokładnie jedna w danej instancji systemu plików), która przechowuje pewne opisujące go zmienne - takie jak liczba wszystkich inode'ów/bloków na dane, daty ostatniego podmontowania, jakiś UUID, etc
* grupy bloków - powtarzające się kubełki na inode'y i bloki, grupowanie ich ułatwia alokację
* zakresy bloków - alternatywa dla "klasycznych" struktur, które każdemu z bloków przyporządkowują jeden wskaźnik - zamiast tego przechowujemy informację "od fizycznego bloku X do bloku Y znajdują się logiczne bloki A do B danego pliku"
* _dowiązanie symboliczne_ (symlink) - plik, który stanowi jedynie wskaźnik do innego pliku - przy czym wskazuje na niego używając pełnej ścieżki, a nie linkując do inode'a - dzięki czemu plik źródłowy i docelowy mogą znajdować się w różnych systemach plików
* i-węzeł - "prawdziwy" byt określający plik, zawiera wszystkie opisujące go informacje poza nazwą - jeden plik może mieć jednak kilka nazw, jeśli wskazuje na niego kilka wspisów katalog{u, ów}

**stats**

```
Filesystem volume name:   <none>
Last mounted on:          /
Filesystem UUID:          9cf7dcf9-7343-4421-ad2d-745f3c8d4e1d
Filesystem magic number:  0xEF53
Filesystem revision #:    1 (dynamic)
Filesystem features:      has_journal ext_attr resize_inode dir_index filetype needs_recovery extent 64bit flex_bg sparse_super large_file huge_file dir_nlink extra_isize metadata_csum
Filesystem flags:         signed_directory_hash
Default mount options:    user_xattr acl
Filesystem state:         clean
Errors behavior:          Continue
Filesystem OS type:       Linux
Inode count:              16457728
Block count:              65816214
Reserved block count:     3290810
Free blocks:              5351130
Free inodes:              8234346
First block:              0
Block size:               4096
Fragment size:            4096
Group descriptor size:    64
Reserved GDT blocks:      1008
Blocks per group:         32768
Fragments per group:      32768
Inodes per group:         8192
Inode blocks per group:   512
Flex block group size:    16
Filesystem created:       Thu Oct  3 22:05:57 2019
Last mount time:          Wed May 19 09:44:32 2021
Last write time:          Wed May 19 09:44:32 2021
Mount count:              22
Maximum mount count:      -1
Last checked:             Tue May  4 08:45:57 2021
Check interval:           0 (<none>)
Lifetime writes:          9 TB
Reserved blocks uid:      0 (user root)
Reserved blocks gid:      0 (group root)
First inode:              11
Inode size:	          256
Required extra isize:     32
Desired extra isize:      32
Journal inode:            8
First orphan inode:       4604580
Default directory hash:   half_md4
Directory Hash Seed:      7e234981-47b9-4d16-98b5-67b7fb986d43
Journal backup:           inode blocks
Checksum type:            crc32c
Checksum:                 0x721f8fee
Directories:              1679320
 Group  0: block bitmap at 1041, inode bitmap at 1057, inode table at 1073
           1394 free blocks, 8157 free inodes, 2 used directories, 8157 unused inodes
           [Checksum 0x5338]
 Group  1: block bitmap at 1042, inode bitmap at 1058, inode table at 1585
           941 free blocks, 8174 free inodes, 18 used directories, 6205 unused inodes
           [Checksum 0x9413]
 Group  2: block bitmap at 1043, inode bitmap at 1059, inode table at 2097
           682 free blocks, 8192 free inodes, 0 used directories, 8192 unused inodes
           [Inode not init, Checksum 0x5194]
```           

**extents**

```
Level Entries       Logical            Physical Length Flags
 0/ 1   1/  1     0 - 37662 17432684             37663
 1/ 1   1/ 69     0 -   511 22648320 - 22648831    512
 1/ 1   2/ 69   512 -   515 22660096 - 22660099      4
 1/ 1   3/ 69   516 -  1107 25728073 - 25728664    592
 1/ 1   4/ 69  1108 -  1515 25725072 - 25725479    408
 1/ 1   5/ 69  1516 -  1740 25724563 - 25724787    225
 1/ 1   6/ 69  1741 -  2047 53538049 - 53538355    307
 1/ 1   7/ 69  2048 -  2904 53511419 - 53512275    857
 1/ 1   8/ 69  2905 -  4094 53572442 - 53573631   1190
 1/ 1   9/ 69  4095 -  4095 53552336 - 53552336      1
```

dowiązanie symboliczne przechowujące swój plik docelowy w blokach danych:

```
debugfs:  stat /home/wolny-symlink
Inode: 4088044   Type: symlink    Mode:  0777   Flags: 0x80000
Generation: 3331975705    Version: 0x00000000:00000001
User:     0   Group:     0   Project:     0   Size: 70
File ACL: 0
Links: 1   Blockcount: 8
Fragment:  Address: 0    Number: 0    Size: 0
 ctime: 0x5ff672f1:86d869ec -- Thu Jan  7 03:33:21 2021
 atime: 0x5ff672f1:86d869ec -- Thu Jan  7 03:33:21 2021
 mtime: 0x5ff672f1:86d869ec -- Thu Jan  7 03:33:21 2021
crtime: 0x5ff672f1:86d869ec -- Thu Jan  7 03:33:21 2021
Size of extra inode fields: 32
Inode checksum: 0xdc847f02
EXTENTS:
(0):16261732
```

```
debugfs:  cat /home/wolny-symlink
/szescdziesiat/bajtow/to/za/malo/by/mnie/pomiescic/aaa/bbb/ccc/ddd/eeedebugfs:
```

dowiązanie, które nie posiada _żadnych_ bloków danych - przechowuje target w miejscu przeznaczonym na adresy bloków:

```
debugfs:  cat /home/szybki-symlink
cat: Invalid argument while reading ext2 file
```

```
debugfs:  stat /home/szybki-symlink
Inode: 4088061   Type: symlink    Mode:  0777   Flags: 0x0
Generation: 771639858    Version: 0x00000000:00000001
User:     0   Group:     0   Project:     0   Size: 15
File ACL: 0
Links: 1   Blockcount: 0
Fragment:  Address: 0    Number: 0    Size: 0
 ctime: 0x5ff6722f:d5691b9c -- Thu Jan  7 03:30:07 2021
 atime: 0x5ff6722f:d5691b9c -- Thu Jan  7 03:30:07 2021
 mtime: 0x5ff6722f:d5691b9c -- Thu Jan  7 03:30:07 2021
crtime: 0x5ff6722f:d5691b9c -- Thu Jan  7 03:30:07 2021
Size of extra inode fields: 32
Inode checksum: 0x28322afc
Fast link dest: "/krotka/sciezka"
```

```
debugfs:  idump /home/szybki-symlink
0000  ffa1 0000 0f00 0000 2f72 f65f 2f72 f65f  ......../r._/r._
0020  2f72 f65f 0000 0000 0000 0100 0000 0000  /r._............
0040  0000 0000 0100 0000 2f6b 726f 746b 612f  ......../krotka/
0060  7363 6965 7a6b 6100 0000 0000 0000 0000  sciezka.........
0100  0000 0000 0000 0000 0000 0000 0000 0000  ................
*
0140  0000 0000 324a fe2d 0000 0000 0000 0000  ....2J.-........
0160  0000 0000 0000 0000 0000 0000 fc2a 0000  .............*..
0200  2000 3228 9c1b 69d5 9c1b 69d5 9c1b 69d5   .2(..i...i...i.
0220  2f72 f65f 9c1b 69d5 0000 0000 0000 0000  /r._..i.........
0240  0000 0000 0000 0000 0000 0000 0000 0000  ................
*
```

**bloki danego inode'a**

```
debugfs:  stat /usr/bin/
Inode: 6816664   Type: directory    Mode:  0755   Flags: 0x81000
Generation: 3116953973    Version: 0x00000000:00014479
User:     0   Group:     0   Project:     0   Size: 135168
File ACL: 0
Links: 6   Blockcount: 272
Fragment:  Address: 0    Number: 0    Size: 0
 ctime: 0x60a0e32c:b2505efc -- Sun May 16 11:17:32 2021
 atime: 0x5fef6dc8:43e16a48 -- Fri Jan  1 19:45:28 2021
 mtime: 0x60a0e32c:b2505efc -- Sun May 16 11:17:32 2021
crtime: 0x5d9661d3:1af475c8 -- Thu Oct  3 23:02:11 2019
Size of extra inode fields: 32
Inode checksum: 0x2b31aa8a
EXTENTS:
(ETB0):27271856, (0):27271245, (1-2):27271814-27271815, (3):27271826, (4):27271831, (5):27271855, (6):27271933, (7):27271935, (8):27271948, (9-10):27272678-27272679, (11):27273330, (12):27273226, (13):27273234, (
14):27273236, (15-16):27273917-27273918, (17):27272890, (18-20):27273153-27273155, (21):27272637, (22):27272676, (23):27272639, (24):27272822, (25):27293297, (26):27294003, (27):27281151, (28):27286222, (29):2727
3900, (30):27273933, (31):27273712, (32):27272481
```

```
debugfs:  icheck 27271855
Block	Inode number
27271855	6816664
```
```
debugfs:  ncheck 6816664
Inode	Pathname
6816664	/usr/bin
```

**bdump**

```
debugfs:  blocks /
9265
```

```
debugfs:  bdump 9265
0000  0200 0000 0c00 0102 2e00 0000 0200 0000  ................
0020  0c00 0202 2e2e 0000 0b00 0000 1400 0a02  ................
0040  6c6f 7374 2b66 6f75 6e64 0000 0100 7800  lost+found....x.
0060  0c00 0402 626f 6f74 0100 0400 0c00 0302  ....boot........
0100  7661 7200 0100 1800 0c00 0302 6465 7600  var.........dev.
0120  0100 5c00 0c00 0302 7275 6e00 0100 6000  ..\.....run...`.
0140  0c00 0302 6574 6300 0100 0200 0c00 0302  ....etc.........
0160  746d 7000 0100 1000 0c00 0302 7379 7300  tmp.........sys.
0200  0100 5400 0c00 0402 7072 6f63 0100 6800  ..T.....proc..h.
0220  0c00 0302 7573 7200 0c00 0000 0c00 0307  ....usr.........
0240  6269 6e00 0100 3e00 0c00 0402 686f 6d65  bin...>.....home
0260  0d00 0000 0c00 0307 6c69 6200 0e00 0000  ........lib.....
0300  1000 0507 6c69 6236 3400 0000 0100 5000  ....lib64.....P.
0320  0c00 0302 6d6e 7400 0100 3000 0c00 0302  ....mnt...0.....
0340  6f70 7400 0100 6c00 0c00 0402 726f 6f74  opt...l.....root
0360  0f00 0000 0c00 0407 7362 696e 0100 0600  ........sbin....
0400  0c00 0302 7372 7600 0100 b800 ec0e 0502  ....srv.........
0420  6d65 6469 6175 6e74 1700 0000 dc0e 1201  mediaunt........
0440  2e69 736d 6f75 6e74 2d74 6573 742d 6669  .ismount-test-fi
0460  6c65 2201 6f70 6572 612d 7365 7276 6963  le".opera-servic
0500  6573 2d73 7973 7465 6d73 2d78 322e 6365  es-systems-x2.ce
0520  7274 2e63 7274 0000 0000 0000 0000 0000  rt.crt..........
0540  0000 0000 0000 0000 0000 0000 0000 0000  ................
*
7760  0000 0000 0000 0000 0c00 00de 0cde 69ae  ..............i.
```