# SO Lista 5

## Zadanie 1

### Co robi operacja read(2) i write(2), jeśli bufor rury jest odpowiednio pusty albo pełny?
Pipe'y wykonywane są jednocześnie, ale mogą być wstrzymywane.
Jeśli proces będzie czytać z pustego pipe'a wtedy `read` zostanie zablokowany, dopóki dane nie będą dostępne.
Jeśli proces będzie pisać do pełnego pipe'a wtedy `write` będzie blokowany do momentu przeczytania części danych.

### 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?
Pipe_buf mówi ile bajtów można zapisać w jednej operacji.
Jeśli rozmiar jest do Pipe_buf to operacje wykonują się jednorazowo, bez żadnego zakłócenia.

### Czemu wszystkie porocesy należące do potoku zakończą się bez interwencji powłoki, jeśli co najmniej jeden z nich umrze?
`????????????????`
No bo te procesy co są przed umierającym procesem dostaną SIGPIPE a te po EOF I guess, i wszystko umiera samoistnie.

### Kiedy operacja read i write na na rurze zwracją "short count"?
<!-- http://csapp.cs.cmu.edu/2e/ch10-preview.pdf 5-6 strona-->

### Jak można połączyć rodzica i dziecko rurą, która została utworzona po uruchomieniu dziecka?

Rodzica i dziecka nie można połączyć pipem utworzonym po uruchomieniu dziecka, mówi o tym The Linux Programming Interface (938 pdf):
Jako że dziecko powstaje najpierw (w naszym przypadku), takie połączenie dziecka i rodzica pipem nie jest możliwe.

## Zadanie 2
### Do czego służy wywołanie systemowe ioctl(2)?
Wywołanie systemowe ioctl(2) jest wykorzystywane do specyficznych dla danego urządzenia operacji I/O i innych operacji, których nie można wyrazić zwykłymi syscallami.

int ioctl(int fd, unsigned long request, char *argp, ...);

fd -> open file's descriptor
request -> device-dependent request code
pointer -> untyped pointer to memory. It's
traditionally char *argp

### Urządzenia 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. Np. konsole, myszki ram

### 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. Np. dyski, partycje, dyskietki

### Definicje operacji
#### DIOCEJECT (eject removable disk)
wysuwa dysk wymienny

#### KIOCTYPE
zwraca typ klawiatury (np. czy usb, czy terminal udający klawiaturę)

#### SIOCGIFCONF (get ifnet list)
zwraca listę ifnet (interfejsów jądra do zarządzania)

## Zadanie 3

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

### Kompaktowanie
1. Operacja, która zmniejsza rozmiar katalogu - usuwane są nieużytki, “uklepujemy” katalog.
2. Opłaca się ją robić, gdy wiadomo, że w danym katalogu jest dużo nieużytków, czyli zystamy na tej operacji dużo miejsca.

### Usuwanie pliku
1. Przegląda się cały katolog, żeby wiedzieć, czy jest plik
2. 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).

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

fajny link - https://linux-kernel-labs.github.io/refs/heads/master/labs/filesystems_part2.html

### Ścieżka bezwzględna
Ścieżka zaczynająca się od katalogu /

### i-node
struktura przechowująca metadane

### Dowiązania
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.

### Od jakiego numeru i-node algorytm zaczyna działanie?
Od 2 bo jest to u-node katalogu /

### Skąd sterownik uniksowego systemu plików wie gdzie na dysku znajduje się i-ty bajt pliku?

dobra moze ten wzór na koncu to nie prawda ale byłoby to logiczne

### Czemu nie możemy tworzyć dowiązań do plików znajdujących się w odrębie innych zamontowanych systemów plików?
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 5


#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' : '-';

  if(S_ISVTX & m) ox = 't';
  if(S_ISGID & m) gx = 's';   
  if(S_ISUID & m) ux = 's';
  

  /* TODO: Fix code to report set-uid/set-gid/sticky bit as 'ls' does. */

  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(sb->st_rdev == 0 && !S_ISBLK(sb->st_mode) && !S_ISCHR(sb->st_mode))
  {
    printf(" %8ld ", sb->st_size);
  } else 
  {
    printf(" %4d %3d ", major(sb->st_rdev), minor(sb->st_rdev));
  }
  
  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. DONE */

    char buf[DIRBUFSZ];
    if(readlinkat(dirfd,name,buf,sizeof(buf)))
      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;
    for(long bpos = 0; bpos < n;)
    {
      d = (struct linux_dirent *) (buf + bpos);
      file_info(dirfd,d->d_name);
      bpos += d->d_reclen;
    }
    /* TODO: Iterate over directory entries and call file_info on them. */
  }

  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! */
  if(!ReadNum(in, &prime)){
    CloseReadEnd(in);
    exit(EXIT_SUCCESS);
  }

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

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

  sockpair_t right = MakeSocketPair();
  /* TODO: Spawn right child. */
  if(!Fork()){
    Close(parent_fd);
    Close(left.parent_fd);
    Close(right.parent_fd);
    Sort(right.child_fd);
    exit(EXIT_SUCCESS);
  }
  else
    Close(right.child_fd);

  /* TODO: Send elements to children and merge returned values afterwards. */
  SendElem(parent_fd,left.parent_fd,(int)nelem/2);
  SendElem(parent_fd,right.parent_fd,(int)(nelem - (nelem/2)));
  Merge(left.parent_fd,right.parent_fd,parent_fd);
  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(stdout, "%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;
}