# Lista 5
###### tags: `SO2022`

:::spoiler
:::

## Deklaracja
:::spoiler

| Zadanie | 1 | 2 | 3 | 4 | 5 | 6 | 7 (2p) |
|-----------|---|---|---|---|---|---|--------|
|Deklaracja |:heavy_check_mark:|:heavy_check_mark:|:heavy_check_mark:|:heavy_check_mark:|:heavy_check_mark:|:heavy_check_mark:|:heavy_check_mark:|

:::

## Zadanie 1

* ### Co robi operacja `read(2)` i `write(2)`, jeśli bufor rury jest:
* pusty:
`read` - proces jest zablokowany (uśpiony) do momentu aż nie pojawią się dane
* pełny:
`write` - proces jest zablokowany (uśpiony) do momentu aż nie zwolni się miejce w buforze

* ### Jakie gwarancje daje nam operacja `write` na rurze, do której pisze wiele procesów – każdy z nich wiersze tekstu nie dłuższe niż `PIPE_BUF`?
`write` dopisuje wtedy do bufora atomowo, tj. jeżeli wiersz tekstu z procesów `A` i `B` mieszczą się w `PIPE_BUF`, to każdy z wierszy jest zapisywany do bufora bez rozbicia

* ### Czemu wszystkie procesy należące do potoku zakończą się bez interwencji powłoki, jeśli co najmniej jeden z nich umrze?
`ps -ef | grep sh | wc -l`

Jeśli wszystkie deskryptory piszące do pipe'a zostaną zamknięte `read odczyta znak końca pliku`

Jeśli wszystkie deskryptory czytające zostaną zamknięte wysłany zostanie sygnał `SIGPIPE` do procesu próbującego wpisać coś do pipe'a

:::spoiler
If all file descriptors referring to the **write end** of a pipe have been **closed**, then an attempt
to read(2) from the **pipe will see end-of-file (read(2) will return 0). If all file descriptors**
referring to the read end of a pipe have been closed, then a **write(2) will cause a SIGPIPE sig‐
nal to be generated for the calling process.** If the calling process is **ignoring** this signal,
then **write(2)** fails with the error **EPIPE**. An application that uses pipe(2) and fork(2) should
use suitable close(2) calls to close unnecessary duplicate file descriptors; this ensures that
**end-of-file** and **SIGPIPE/EPIPE** are delivered when appropriate.
:::

* ### Kiedy operacje read i write na rurze zwracają *„short count”*?
Rury zachowują się przy odczycie jak zwykłe pliki, zatem `short count` jest zwracany wtedy gdy przeczytaliśmy mniej danych niż oczekiwaliśmy
np. osiągneliśmy znak końca pliku '\0' lub w buforze jeszcze nie ma tylu danych ile oczekiwaliśmy

Prz zapisie nigdy nie dostaniemy `„short count` zapiszemy co chemy lub dotaniemy error



* ### Jak można połączyć rodzica i dziecko rurą, która została utworzona po uruchomieniu dziecka?
Nie można połączyć istniejących procesów pipem


## Zadanie 2

* ### [*ioctl and fcntl Are an Embarrassment*](http://www.catb.org/~esr/writings/taoup/html/ch20s03.html)

* ### Do czego służy wywołanie systemowe `ioctl(2)`?
Manipuluje paramtertami sterowników urządzeń I/O (TTY, urządzenia szeregowe, itp.)
Wysyła sygnały do innych funkcji urządzeń oraz systemu plików.

* ### Na podstawie pliku [`ioccom.h`](https://nxr.netbsd.org/xref/src/sys/sys/ioccom.h) wyjaśnij znaczenie drugiego i trzeciego parametru wywołania ioctl.
*

    #ifndef	_SYS_IOCCOM_H_
    #define	_SYS_IOCCOM_H_

    /*
     * Ioctl's have the command encoded in the lower word, and the size of
     * any in or out parameters in the upper word.  The high 3 bits of the
     * upper word are used to encode the in/out status of the parameter.
     *
     *	 31 29 28                     16 15            8 7             0
     *	+---------------------------------------------------------------+
     *	| I/O | Parameter Length        | Command Group | Command       |
     *	+---------------------------------------------------------------+
     */
    #define	IOCPARM_MASK	0x1fff		/* parameter length, at most 13 bits */
    #define	IOCPARM_SHIFT	16
    #define	IOCGROUP_SHIFT	8
    #define	IOCPARM_LEN(x)	(((x) >> IOCPARM_SHIFT) & IOCPARM_MASK)
    #define	IOCBASECMD(x)	((x) & ~(IOCPARM_MASK << IOCPARM_SHIFT))
    #define	IOCGROUP(x)	(((x) >> IOCGROUP_SHIFT) & 0xff)

    #define	IOCPARM_MAX	NBPG	/* max size of ioctl args, mult. of NBPG */
                    /* no parameters */
    #define	IOC_VOID	(unsigned long)0x20000000
                    /* copy parameters out */
    #define	IOC_OUT		(unsigned long)0x40000000
                    /* copy parameters in */
    #define	IOC_IN		(unsigned long)0x80000000
                    /* copy parameters in and out */
    #define	IOC_INOUT	(IOC_IN|IOC_OUT)
                    /* mask for IN/OUT/VOID */
    #define	IOC_DIRMASK	(unsigned long)0xe0000000

    #define	_IOC(inout, group, num, len) \
        ((inout) | (((len) & IOCPARM_MASK) << IOCPARM_SHIFT) | \
        ((group) << IOCGROUP_SHIFT) | (num))
    #define	_IO(g,n)	_IOC(IOC_VOID,	(g), (n), 0)
    #define	_IOR(g,n,t)	_IOC(IOC_OUT,	(g), (n), sizeof(t))
    #define	_IOW(g,n,t)	_IOC(IOC_IN,	(g), (n), sizeof(t))
    /* this should be _IORW, but stdio got there first */
    #define	_IOWR(g,n,t)	_IOC(IOC_INOUT,	(g), (n), sizeof(t))

    #define IOCSNPRINTF(buf, len, cmd) \
        snprintf((buf), (len), "_IO%s%s('%c', %hhu)", \
        (((cmd) >> 30) & 1) ? "R" : "", \
        (((cmd) >> 30) & 2) ? "W" : "", \
        (char)IOCGROUP(cmd), (unsigned char)(cmd))


    #endif /* !_SYS_IOCCOM_H_ */

Makro `_IOC` definiuje mam schemat w jakim ma zostać przekazany drugi argument wywołania `Ioctl` widzmy w nim informację czy ma to być odczut czy zapis długość argumentu przekazywanego w trzecim parametrze oraz iformacje o grupie i konkretnej instrukcji specyficznej dla dajego urządzenia

* ### Używając przeglądarki kodu jądra NetBSD znajdź definicje operacji `DIOCEJECT`, `KIOCTYPE` i `SIOCGIFCONF`, a następnie wytłumacz co one robią.
* [DIOCEJECT](https://nxr.netbsd.org/xref/src/sys/sys/dkio.h)
`#define DIOCEJECT _IOW('d', 112, int) /* wysuwa dysk zewnętrzny */`
* [KIOCTYPE](https://nxr.netbsd.org/xref/src/sys/dev/sun/kbio.h)
`#define KIOCTYPE _IOR('k', 9, int) /* pobiera typ klawiatury */`
* [SIOCGIFCONF](https://nxr.netbsd.org/xref/src/sys/sys/sockio.h)
`#define SIOCGIFCONF _IOWR('i', 38, struct ifconf) /* pobiera listę ifnet (interfejsy sieciowe) */`

## Zadanie 3


* ### Przedstaw reprezentację katalogu, a następnie wyjaśnij jak przebiegają operacje:
[Dokumentacja ext4](https://ext4.wiki.kernel.org/index.php/Ext4_Disk_Layout#Block_and_Inode_Allocation_Policy)

* *usuwania pliku*:
* Standardowo:
Pozostawiamy nieużytek i zwiększamy rozmiar poprzedzającego go wpisu
* Gdy w reprezentacji katalogu za lub przed usuwanym wpisem istnieją nieużytki:
Zwiększamy rozmiar pierwszego ważnego poprzedzającego wpisu
* *dodawania pliku*:
* Standardowo:
Znajdujemy pierwsze wystarczająco duże miejsce w strukturze i wpisujemy tam katalog
* Gdy w pliku katalogu nie udaje się znaleźć wystarczająco dużo miejsca na przechowanie wpisu.
Przeprowadzamy kompaktowanie katalogu, tzn. przenosimy wprzystkie wpisy jak najbardziej na lewo, a końcowe miejsce zwalniamy
Jeśli dalej nie będzie miejsca to allokujemy nowy blok

* ### Jądro leniwie wykonuje operację kompaktowania na katalogach – kiedy opłaca się ją zrobić?
W wyniku konkretnego zdarzenia, zależne od implementacji np. gdy nie można znaleść wolnego miejsca

## Zadanie 4

* ### Korzystając z poleceń `stat` i `ls -lia` zaprezentuj jak jądro systemu operacyjnego trawersuje ścieżkę bezwzględną `/usr/bin/cc`.

* ### Od jakiego numeru i-węzła algorytm zaczyna działanie?
* ext4: inode: 2
* btrfs: inode 256

* ### Skąd sterownik uniksowego systemu plików wie gdzie na dysku znajduje się i-ty bajt pliku?
Sterownik wie z informacji zawartych w inodzie danego pliku - rozmiar pliku, adresy do bloków (są różne poziomy w razie, gdyby nie mieściły się bloki)
* ext2/ext3:

* ext4:
* btrfs:

* ### 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?
Osobne systemy plików posiadają osobnie numerowane i-node'y, więc nie możemy tworzyć linków między systemami plików


## Zadanie 5

#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. */

  // S_ISUID - set-user-ID bit
  // S_ISGID - set-group-ID bit
  // S_ISVTX - sticky bit
  
  // set-uid - pozwala wykonywać program na prawach właściciela dowolnemu urzytkownikowi posiadającegmu dostęp
  ux = (m & S_ISUID) ? ((m & S_IXUSR) ? 's' : 'S') : ux;
  // set-gid - pozwala wykonywać program na prawach grupy dowolnemu urzytkownikowi posiadającegmu dostęp
  gx = (m & S_ISGID) ? ((m & S_IXGRP) ? 's' : 'S') : gx;
  // sticky  - pozwala usuwać pliki w katalogu tylko właścicielowi
  ox = (m & S_ISVTX) ? ((m & S_IXOTH) ? 't' : 'T') : ox;

  /* TODO: End */

  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. */

  // Czytamy konkretne wejście z podanego deskryptora katalogu,
  // AT_SYMLINK_NOFOLLOW - wyłącza domyślne rozwiązywanie linków symblicznych
  if (fstatat(dirfd, name, sb, AT_SYMLINK_NOFOLLOW) == -1) {
      perror("fstatat");
      exit(EXIT_FAILURE);
  }

  /* TODO: End */

  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. */

  // S_IFCHR - character device
  // S_IFBLK - block device

  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);
  
  /* TODO: End */

  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. */

    // S_ISLNK - symbolic link
    char buf[DIRBUFSZ];
    int n;
    if ((n = readlinkat(dirfd, name, buf, DIRBUFSZ)) == -1) {
      perror("readlink");
      exit(EXIT_FAILURE);
    }
    buf[n] = '\0'; // buf nie musi być zakończony znakiem końca
    printf(" -> %s", buf);
  
  /* TODO: End */
  }

  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. */

    // Sposób iterowania po wartościach z man gendents
    for (long bpos = 0; bpos < n;) {
      d = (struct linux_dirent *) (buf + bpos);
      bpos += d->d_reclen;
      file_info(dirfd, d->d_name);
    }

    /* TODO: End */
  }

  Close(dirfd);
  return EXIT_SUCCESS;
}

## Zadanie 6

#include "csapp.h"

typedef struct {
  int read;
  int write;
} pipe_t;

static inline pipe_t MakePipe(void) {
  int fds[2];
  Pipe(fds);
  return (pipe_t){.read = fds[0], .write = fds[1]};
}

static inline void CloseReadEnd(pipe_t p) {
  Close(p.read);
}

static inline void CloseWriteEnd(pipe_t p) {
  Close(p.write);
}

static bool ReadNum(pipe_t p, long *valp) {
  return Read(p.read, valp, sizeof(long)) == sizeof(long);
}

static bool WriteNum(pipe_t p, long val) {
  return Write(p.write, &val, sizeof(long)) == sizeof(long);
}

static noreturn void generator(pipe_t out, long maxprime) {
  for (long n = 2; n <= maxprime; n++)
    WriteNum(out, n);
  exit(EXIT_SUCCESS);
}

static void filter(pipe_t in, pipe_t out, long prime) {
  long num;
  while (ReadNum(in, &num)) {
    if (num % prime != 0)
      WriteNum(out, num);
  }
}

static noreturn void filter_chain(pipe_t in) {
  long prime;

  /* TODO: Something is missing here! */
  pipe_t in_pipe = in;
  pipe_t out_pipe;

  pid_t res;

  while (true) {
    if (ReadNum(in_pipe, &prime)) //opczytujemy pierwszą liczbę jako naszą liczbę pierwszą
      printf("PID:%d: %ld\n", getpid(), prime);
    else //jeśli readnum nic otrzymał kończymy proces
       exit(EXIT_SUCCESS);

    out_pipe = MakePipe(); // tworzymy nowe połączenie
    if ((res = Fork())) { /* parent */
      CloseReadEnd(out_pipe); //zamykamy niepotrzebne wejśćie 
      filter(in_pipe, out_pipe, prime); //tworzymy filtr
      break;
    } else { /* child */
      CloseReadEnd(in_pipe); //zamykamy starego pipa wejściowego
      in_pipe = out_pipe; // nowo utworzony zostaje wejściem syna
      CloseWriteEnd(in_pipe); // zamykamy niepotrzebne wyjście
    }
  }

  CloseWriteEnd(out_pipe); //Zamykamy potok jawnie żeby zakomunikowac dziecku że to koniec
  Wait(NULL);
  /* TODO: End */

  exit(EXIT_SUCCESS);
}

int main(int argc, char *argv[]) {
  if (argc != 2)
    app_error("Usage: %s [MAXPRIME]", argv[0]);

  long maxprime = atol(argv[1]);

  if (maxprime < 2 || maxprime > 10000)
    app_error("Give maximum prime number in range from 2 to 10000!");

  /* Spawn generator. */
  pipe_t gen_pipe = MakePipe();
  if (Fork()) { /* parent */
    CloseWriteEnd(gen_pipe);
  } else { /* child */
    CloseReadEnd(gen_pipe);
    generator(gen_pipe, maxprime);
  }

  /* Spawn filter chain. */
  if (Fork()) { /* parent */
    CloseReadEnd(gen_pipe);
  } else { /* child */
    filter_chain(gen_pipe);
  }

  for (int i = 0; i < 2; i++)
    Wait(NULL);

  return 0;
}

## Zadanie 7

#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()) {/* parent */
    Close(left.child_fd);
    SendElem(parent_fd, left.parent_fd, nelem/2);
  } else { /* child */
    Close(left.parent_fd);
    Sort(left.child_fd);
    exit(EXIT_SUCCESS);
  }

  /* TODO: End */

  sockpair_t right = MakeSocketPair();
  /* TODO: Spawn right child. */

  if (Fork()) {/* parent */
    Close(right.child_fd);
    SendElem(parent_fd, right.parent_fd, nelem/2 + nelem % 2); //zakresy nieparzyste niekoniecznie równe
    
  } else { /* child */
  Close(right.parent_fd);
    Sort(right.child_fd);
    exit(EXIT_SUCCESS);
  }

  /* TODO: End */
  /* TODO: Send elements to children and merge returned values afterwards. */
  
  Merge(left.parent_fd, right.parent_fd, parent_fd);

  /* TODO: End */
  /* 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;
}

* ### Posługując się rysunkiem wyjaśnij strukturę programu.
NotImplemented

* ### Kiedy tworzysz podprocesy i gniazda?
Tworzymy nowe gniazdo zaraz przed stworzeniem procesu, ten tworzymy gdy chcemy posotrować część danych

* ### Kiedy zamykasz niepotrzebne gniazda?
Każdy proces ma swój deskryptor, zatem niepotrzebne gniazda zamykamy odrazu po forku

* ### Jak wygląda przepływ danych?
Dane płyną od procesu startowego przez kolejne pokolenia do najmłodzeszego dziecka, a następnie pracają tą samą drogą do procesu startowego