# Ćwiczenia 5, grupa cz. 10-12, 17 listopada 2022

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

## Deklaracje

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

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

:::warning
Można dodeklarować zadania 4, 7 i 8 z listy 4.
Link do formularza z listą 4: [kliknij tu](https://hackmd.io/@iiuwr-kba/HJsYRgZro/edit)
:::

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

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

## Zadanie 1
:::success
Autor: Zuzanna Kania

1. Read i write zablokują się w momencie, kiedy odpowiednio read nie ma co przeczytać / write nie ma dokąd pisać.
2. Bufor rury to pamięć w przestrzeni jądra, do której piszą / z której czytają połączone z nią procesy. Domyślnie jedna rura ma rozmiar 16 stron, czyli najczęściej 64KiB.
3. Jeśli do rury pisze wiele procesów, a każdy z nich ciąg danych nie większy niż `PIPE_BUF` (czyli na Linuxie 4KiB), to mamy gwarancję, że zapisy będą atomowe, tj. każdy ciąg danych zostanie zapisany w całości i nie będzie zawierał znaków z wpisów innych procesów.
4. Zgodnie ze specyfikacją, jeżeli wszystkie końce rury do zapisu zostaną zamknięte, to przy najbliższej próbie odczytu read przeczyta EOF. Z kolei jeśli wszystkie końce rury do odczytu zostaną zamknięte, to każdy proces, który spróbuje do niej pisać, otrzyma `SIGPIPE`. Domyślną akcją dla nieobsłużonego `SIGPIPE` jest zabicie procesu.
5. "Short count" to sytuacja, kiedy przeczytane/zapisane zostało mniej bajtów niż podano w argumencie count.
Read:
On success, the number of bytes read is returned (zero indicates
end of file), and the file position is advanced by this number.
It is not an error if this number is smaller than the number of
bytes requested; this may happen for example because fewer bytes
are actually available right now (maybe because we were close to
end-of-file, or because we are reading from a pipe, or from a
terminal), or because read() was interrupted by a signal.
Write:
Note that a successful write() may transfer fewer than count
bytes. Such partial writes can occur for various reasons; for
example, because there was insufficient space on the disk device
to write all of the requested bytes, or because a blocked write()
to a socket, pipe, or similar was interrupted by a signal handler
after it had transferred some, but before it had transferred all
of the requested bytes.
6. Dowolne dwa procesy można połączyć rurą (a dokładniej potokiem) za pomocą pliku FIFO, czyli nazwanego potoku. Po otwarciu pliku FIFO przez przynajmniej jeden proces podobnie jak w przypadku zwykłego potoku w jądrze jest alokowana pamięć do wymiany danych, także pomimo istnienia pliku na dysku, to żadne dane z procesów nie są na dysku zapisywane.

:::

## Zadanie 2
:::success
Autor: Jan Jankowicz
:::
Wywołanie systemowe ioctl służy do kontroli urządzeń zewnętrznych przy użyciu specjalnych plików, które pełnią rolę komunikacyjnego medium pomiędzy kodem użytkownika a danym urządzeniem. Argumentami ioctl są deskryptor pliku urządzenia, odpowiednio spreparowany kod żądania oraz ewentualny argument potrzebny do jego wykonania. Drugi argument - kod żądania - składa się z informacji nt. kierunku kierunku transferu danych (in, out, inout), długości ewentualnego parametru, a także grupę i kod komendy, którą chcemy zrealizować.


Urządzenie znakowe - czytanie znak po znaku (strumień)
Urządzenie blokowe - czytanie blokami

#define DIOCEJECT _IOW('d', 112, int) /* eject removable disk */
#define KIOCTYPE _IOR('k', 9, int) /* get keyboard type */
#define SIOCGIFCONF _IOWR('i', 38, struct ifconf) /* get ifnet list */ - zwraca listę interfejsów sieciowych

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


Każdy katalog zawiera w sobie pewną liczbę bloków dysku. W katalogu rekordy oznaczające pliki i katalogi znajdują sie w nieposortowanym porządku. Każdy rekord jest bezpośrednio po poprzednim. Rekordy nie zajmują całego bloku dysku, dlatego może istnieć niewykorzystana przestrzeń na końcu bloku.
Części rekordów:
- numer i-węzła (i-node)
- długość w bajtach tego rekordu (ale być może wraz z nieużytkami)
- typ, np. F (file -- plik), D (directory -- katalog), itd.
- prawdziwa długość nazwy w bajtach
- sama nazwa

Gdy usuwamy plik, to jedyne co zmieniamy, to długość poprzedniego rekordu katologu - zwiększamy ją o długość usuwanego rekordu. W ten sposób przechodząc po kolei po rekordach, skacząc dzięki długościom rekordów pominiemy usunięty plik. Tak generują się nieużytki.

Gdy za usuwanym rekordem jest usunięty wcześniej rekord, to wszystko działa, bo w jego długość jest już wliczony ten nieużytek. W przypadku gdy wcześniej jest nieużytek również wszystko działa, bo żeby znaleźć poprzedni rekord i tak musimy przeszukać liniowo listę rekordów od początku, bo nie mamy żadnych "strzałek" wstecz.

Gdy dodajemy plik to szukamy odpowiednio długiego nieużytku na wstawienie nowego rekordu katalogu. Gdy takiego nie znajdziemy, bo luki są krótkie, to kompaktujemy, czyli przepisujemy całą listę rekordów, ale bez nieużytków. Teraz możemy na końcu tej listy dopisać nasze informacje (jeśli jest tam miejsce). Mówimy, że dzieje się to leniwie, bo robimy to gdy naprawdę nie mamy już wyboru.

:::

## Zadanie 4
:::success
Autor: Miriam Bouhajeb

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

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

Algorytm trawersuje od i-node’a nr 2, gdyż jest to numer katalogu roota (/)

struct stat {
dev_t st_dev; /* ID of device containing file */
ino_t st_ino; /* inode number */
mode_t st_mode; /* protection */
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; /* blocksize for file system I/O */
blkcnt_t st_blocks; /* number of 512B blocks allocated */
time_t st_atime; /* time of last access */
time_t st_mtime; /* time of last modification */
time_t st_ctime; /* time of last status change */
};


Dowiązania są częścią systemu plików, a system zamontowany może mieć inny sposób przechowywania ich niż obecny. W dwóch systemach plików możemy mieć dwa pliki o tym samym numerze i-node.
Nie da się tworzyć dowiązań do innych systemów plików, gdyż aby
usunąć plik to należy usunąć wszystkie dowiązania do niego, a jesli istniałoby dowiązanie do innego systemu plików, to po odłączeniu go nie moglibyśmy usunąć pliku.
Sterownik wie gdzie na dysku jest i-ty bajt pliku, gdyż mamy drzewiastą strukturę która przechowuje informacje o blokach pliku i ich rozmieszczeniach na dysku.
:::

## Zadanie 5
:::success
Autor: Kacper Chmielewski

https://www.gnu.org/software/libc/manual/html_node/Testing-File-Type.html

Macro: int S_ISCHR (mode_t m)
Preliminary: | MT-Safe | AS-Safe | AC-Safe | See POSIX Safety Concepts.

This macro returns non-zero if the file is a character special file (a device like a terminal).

Macro: int S_ISBLK (mode_t m)
Preliminary: | MT-Safe | AS-Safe | AC-Safe | See POSIX Safety Concepts.

This macro returns non-zero if the file is a block special file (a device like a disk).

man inode

  S_ISUID     04000   set-user-ID bit (see execve(2))
           S_ISGID     02000   set-group-ID bit (see below)
           S_ISVTX     01000   sticky bit (see below)

    struct linux_dirent {
               unsigned long  d_ino;      Inode number 
               unsigned long  d_off;      Offset to next linux_dirent 
               unsigned short d_reclen;   Length of this linux_dirent 
               char           d_name[];   Filename (null-terminated) 
                                  length is actually (d_reclen - 2 -
                                    offsetof(struct linux_dirent, d_name)) 
               
               char           pad;        Zero padding byte
               char           d_type;     File type (only since Linux
                                          2.6.4); offset is (d_reclen - 1)
               
           }
           
    The stat structure
       All of these system calls return a stat structure, which contains
       the following fields:

           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
           };

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

  ux = (m & S_ISUID) ? 's' : ux;
  gx = (m & S_ISGID) ? 's' : gx;
  ox = (m & S_ISVTX) ? '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. DONE */

  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. DONE */
  if(S_ISCHR(sb->st_mode) || S_ISBLK(sb->st_mode))
    printf("%d, %d", major(sb->st_rdev), minor(sb->st_rdev));
  else
    printf("%d", (int) 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. */
    char buf[DIRBUFSZ + 1];
    ssize_t res = Readlinkat(dirfd, name, buf, DIRBUFSZ);
    buf[res + 1] = '\0';
    printf(" -> %s", buf);
  }

  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. DONE */
    for(void* i = buf; i != buf + n; i += d->d_reclen){
      d = (struct linux_dirent*) i;
      if(d->d_name[0] != '.')
        file_info(dirfd, d->d_name);
    }

  }

  Close(dirfd);
  return EXIT_SUCCESS;
}

:::

## Zadanie 6
:::success
Autor: Daniel Sarniak

// tworzy lancuch podprocesow - kazdy polaczony ze swoim poprzednikiem
static noreturn void filter_chain(pipe_t in) {
  long prime;

  /* TODO: Something is missing here! */
  
  if (!ReadNum(in, &prime)) {
    exit(EXIT_SUCCESS);
  }
  pipe_t out = MakePipe();

  // w tym momencie mamy pewnosc, ze pierwsza liczba w rurze 'in' jest pierwsza
  printf("%ld\n", prime);

  pid_t pid = Fork();
  if (pid)
   { /* parent */
      CloseWriteEnd(out);
      CloseReadEnd(in);   
      filter_chain(out);  
      Wait(NULL);
   }
   else
   { /* child */
      CloseReadEnd(out);
      //nasza liczba pierwsza z tego procesu jest juz odczytana z 'in' wiec w filtrze filtrujemy jej wielokrotnosci i na wejsciu zostawiamy kolejna liczbe pierwsza
      filter(in, out, prime);
   }

  
  //ostatnia liczba pierwsza dla n = 10 000
  //(nie jest to zawartosc wlasciwego programu)
  if(prime == 9973)
    {
      //sleep(3);
      FILE *p;
      int ch;
      p = popen("ps -e | grep prime | wc -l","r");
      if( p == NULL)
      {
        puts("Unable to open process");
        exit(EXIT_FAILURE);
      }
      printf("ps -e | grep prime | wc -l: ");
      while( (ch=fgetc(p)) != EOF )
        putchar(ch);
      pclose(p);

      p = popen("lsof | grep prime | grep FIFO","r");
      if( p == NULL)
      {
        puts("Unable to open process");
        exit(EXIT_FAILURE);
      }
      printf("lsof | grep prime | grep FIFO: \n");
      while( (ch=fgetc(p)) != EOF )
        putchar(ch);
      pclose(p);

      printf("Print from program: \n");
      printf("out.read: %d, pid(%d) \n", out.read, getpid());
      printf("in.write: %d, pid(%d) \n", in.write, getpid());
      printf("in.read: %d, pid(%d) \n", in.read, getpid());
    }

  exit(EXIT_SUCCESS);
}

:::

## Zadanie 7
:::success
Autor: Paweł Tkocz
:::

#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();
  int ppid = getpid();
  int left_child_pid = -1;
  int right_child_pid = -1;

  /* TODO: Spawn left child. */
  if(Fork()){
    //parent
    Close(left.child_fd);
  }
  else{
    //left child
    left_child_pid = getpid();
    Close(left.parent_fd);
  }

  sockpair_t right = MakeSocketPair();
  /* TODO: Spawn right child. */
  if (getpid() == ppid){
    if(Fork()){
        //parent
        Close(right.child_fd);
    }
    else{
        //right child
        right_child_pid = getpid();
        Close(right.parent_fd);
        Close(left.parent_fd);
    }
  }

  /* TODO Send elements to children and merge returned values afterwards */
  if(getpid() == ppid){
    SendElem(parent_fd, left.parent_fd, nelem/2);
    SendElem(parent_fd, right.parent_fd, nelem - nelem/2);
    Merge(left.parent_fd, right.parent_fd, parent_fd);
  }
  if(getpid() == right_child_pid){
    Sort(right.child_fd);
    exit(EXIT_SUCCESS);
  }
  if(getpid() == left_child_pid){
    Sort(left.child_fd);
    exit(EXIT_SUCCESS);
  }

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

Wywołanie mergesorta dla argumentu, będącego wynikiem działania programu gen-nums można wywołać komendą:
python3 gen-nums.py 1000 | ./mergesort