SO update

7 files changed, 538 insertions, 0 deletions

diff --git a/semestr-5/so/lista6/so21_lista_6/Makefile.include b/semestr-5/so/lista6/so21_lista_6/Makefile.include
new file mode 100644
index 0000000..196c9a5
--- /dev/null
+++ b/semestr-5/so/lista6/so21_lista_6/Makefile.include
@@ -0,0 +1,105 @@
+CC = gcc -g
+CFLAGS = -Og -Wall -Werror -Wstrict-prototypes
+AS = as -g
+ASFLAGS = 
+CPPFLAGS = -Iinclude
+LDLIBS = -Llibcsapp -lcsapp
+SED = sed
+
+# Recognize operating system
+ifeq ($(shell uname -s), Darwin)
+CPPFLAGS += -DMACOS
+SED = gsed
+endif
+
+ifeq ($(shell uname -s), Linux)
+CPPFLAGS += -DLINUX
+endif
+
+ifeq ($(shell uname -s), FreeBSD)
+CPPFLAGS += -DFREEBSD
+endif
+
+# Pass "VERBOSE=1" at command line to display command being invoked by GNU Make
+ifneq ($(VERBOSE), 1)
+.SILENT:
+endif
+
+LIBSRC_C = $(wildcard libcsapp/*.c)
+LIBSRC_S = $(wildcard libcsapp/*.s)
+LIBSRC_H = $(wildcard include/*.h)
+LIBSRCS = $(LIBSRC_C) $(LIBSRC_S) $(LIBSRC_H)
+LIBOBJS = $(LIBSRC_C:%.c=%.o)
+ifneq ($(shell uname -s), Darwin)
+LIBOBJS += $(LIBSRC_S:%.s=%.o)
+endif
+LIB = libcsapp/libcsapp.a
+
+SRC_C = $(wildcard *.c)
+SRC_S = $(wildcard *.s)
+SRC_H = $(wildcard *.h)
+SRCS = $(SRC_C) $(SRC_S)
+OBJS = $(SRC_C:%.c=%.o) 
+
+SOURCES = $(SRCS) $(LIBSRCS)
+OBJECTS = $(OBJS) $(LIBOBJS)
+DEPFILES = $(foreach f,$(SRC_C) $(LIBSRC_C),\
+	     $(dir $(f))$(patsubst %.c,.%.d,$(notdir $(f))))
+
+ARCHIVE = so$(shell date +'%y')_$(shell basename $(PWD))
+FILES = Makefile Makefile.include $(EXTRA-FILES)
+
+all: $(DEPFILES) $(LIB) $(PROGS)
+
+$(LIB): $(LIBOBJS)
+
+# Generate dependencies automatically
+ifeq ($(words $(findstring $(MAKECMDGOALS), archive clean)), 0)
+  -include $(DEPFILES)
+endif
+
+# Disable all built-in recipes and define our own
+.SUFFIXES:
+
+.%.d: %.c
+	$(CC) $(CPPFLAGS) -MM -MG -o $@ $<
+
+%.o: %.c .%.d
+	@echo "[CC] $@ <- $<"
+	$(CC) $(CPPFLAGS) $(CFLAGS) -c -o $@ $<
+
+%.o: %.s
+	@echo "[AS] $@ <- $<"
+	$(AS) $(ASFLAGS) -c -o $@ $<
+
+%.a:
+	@echo "[AR] $@ <- $^"
+	$(AR) rc $@ $^
+
+%: %.o $(LIB)
+	@echo "[LD] $@ <- $^"
+	$(CC) $(LDFLAGS) -o $@ $^ $(LDLIBS)
+
+clean:
+	rm -vf $(PROGS) $(OBJECTS) $(DEPFILES) $(LIB)
+	rm -vf $(shell find -L . -iname '*~')
+	rm -vf $(ARCHIVE).tar.gz
+	rm -vrf $(EXTRA-CLEAN) *.dSYM
+
+format:
+	clang-format --style=file -i $(LIBSRC_C) $(LIBSRC_H) $(SRC_C) $(SRC_H)
+
+archive: clean
+	mkdir -p $(ARCHIVE) $(ARCHIVE)/libcsapp $(ARCHIVE)/include
+	cp -L $(SRCS) $(SRC_H) $(FILES) $(ARCHIVE)/
+	cp -L $(LIBSRCS) $(ARCHIVE)/libcsapp/
+	cp -L $(LIBSRC_H) $(ARCHIVE)/include/
+	for f in $(SRCS:%=$(ARCHIVE)/%); do \
+	  $(SED) --in-place='' -e '/^#if.*STUDENT/,/^#endif.*STUDENT/d' $$f; \
+	done
+	tar cvzhf $(ARCHIVE).tar.gz $(ARCHIVE)
+	rm -rf $(ARCHIVE)
+
+.PHONY: all clean format archive 
+
+# vim: ts=8 sw=8 noet
diff --git a/semestr-5/so/lista6/so21_lista_6/writeperf.c b/semestr-5/so/lista6/so21_lista_6/writeperf.c
new file mode 100644
index 0000000..b397188
--- /dev/null
+++ b/semestr-5/so/lista6/so21_lista_6/writeperf.c
@@ -0,0 +1,88 @@
+#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; 
+
+    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;
+    }
+
+    buf = malloc(size + 1);
+    /* 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, length + 1 - k, 1, 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 k = 0; k < length; k++) {
+      iov[k].iov_base = line + k;
+      iov[k].iov_len = length + 1 - k;    
+    }
+    for (int j = 0; j < times; j++)
+      Writev(1, iov, length); 
+  }
+
+
+  free(line);
+
+  if (dosync && !isatty(STDOUT_FILENO))
+    fsync(STDOUT_FILENO);
+
+  return 0;
+}
diff --git a/semestr-5/so/lista6/so21_lista_6/writeperf.sh b/semestr-5/so/lista6/so21_lista_6/writeperf.sh
new file mode 100755
index 0000000..55f34ae
--- /dev/null
+++ b/semestr-5/so/lista6/so21_lista_6/writeperf.sh
@@ -0,0 +1,17 @@
+#!/bin/bash
+
+OPTS="-l 1000 -t 1000"
+
+runtest() {
+  echo "Method: $1"
+  time ./writeperf $OPTS $1 > test
+  md5sum test
+  rm test
+  echo ""
+}
+
+runtest write
+runtest fwrite
+runtest fwrite-line
+runtest fwrite-full
+runtest writev
diff --git a/semestr-5/so/lista7/so21_lista_7.pdf b/semestr-5/so/lista7/so21_lista_7.pdf
new file mode 100644
index 0000000..698cee0
--- /dev/null
+++ b/semestr-5/so/lista7/so21_lista_7.pdf
diff --git a/semestr-5/so/lista7/so21_lista_7/forksort.c b/semestr-5/so/lista7/so21_lista_7/forksort.c
new file mode 100644
index 0000000..e93ad8c
--- /dev/null
+++ b/semestr-5/so/lista7/so21_lista_7/forksort.c
@@ -0,0 +1,121 @@
+#include "csapp.h"
+
+static void InsertionSort(long table[], size_t left, size_t right) {
+  for (size_t pivot = left + 1; pivot <= right; pivot++) {
+    size_t insert = left;
+
+    while ((insert < pivot) && (table[insert] < table[pivot]))
+      insert++;
+
+    if (insert < pivot) {
+      size_t n = pivot - insert;
+      long tmp = table[pivot];
+      memmove(&table[insert + 1], &table[insert], n * sizeof(long));
+      table[insert] = tmp;
+    }
+  }
+}
+
+static void SwapElem(long table[], size_t i, size_t j) {
+  long tmp = table[i];
+  table[i] = table[j];
+  table[j] = tmp;
+}
+
+static size_t Partition(long table[], size_t begin, size_t end, long pivot) {
+  size_t left = begin;
+  size_t right = end;
+
+  while (left < right) {
+    while ((left < right) && (table[left] < pivot))
+      left++;
+
+    while ((left < right) && (table[right] >= pivot))
+      right--;
+
+    if (left < right)
+      SwapElem(table, left, right);
+  }
+
+  return left;
+}
+
+#define INSERTSORT_MAX 32
+#define FORKSORT_MIN (1L << 18)
+
+static int QuickSort(long table[], size_t left, size_t right) {
+  pid_t pid_left = -1, pid_right = -1, pid = -1;
+
+  /* TODO: If there is more to sort than FORKSORT_MIN start a subprocess. */
+  // bool forked = false;
+  // if (right - left >= FORKSORT_MIN) {
+  //   if ((pid = Fork())) {
+  //     return pid;
+  //   } else {
+  //     forked = true;
+  //   }
+  // }
+
+  if (left < right) {
+    if (right - left <= INSERTSORT_MAX) {
+      InsertionSort(table, left, right);
+    } else {
+      size_t pivot = left + random() % (right - left + 1);
+      size_t split = Partition(table, left, right, table[pivot]);
+
+      if (left == split) {
+        SwapElem(table, left, pivot);
+        split++;
+      } else {
+        pid_left = QuickSort(table, left, split - 1);
+      }
+
+      pid_right = QuickSort(table, split, right);
+
+      /* TODO: Wait for possible children and exit if created a subprocess. */
+      // if (pid_left != -1) {
+      //   waitpid(pid_left, NULL, 0);
+      // }
+      // if (pid_right != -1) {
+      //   waitpid(pid_right, NULL, 0);
+      // }
+      // if (forked) exit(EXIT_SUCCESS);
+    }
+  }
+
+  return pid;
+}
+
+#define NELEMS (1L << 26)
+
+int main(void) {
+  /* Table size in bytes must be divisible by page size. */
+  size_t size = NELEMS * sizeof(long);
+  assert((size & (getpagesize() - 1)) == 0);
+
+  /* Initialize PRNG seed. */
+  struct timeval tv;
+  gettimeofday(&tv, NULL);
+  srandom(tv.tv_usec);
+
+  /* TODO: Allocate table... */
+
+  long *table = mmap(NULL, size, PROT_WRITE | PROT_READ, MAP_SHARED | MAP_ANONYMOUS, -1, 0);
+
+  /* ... and fill it in with random elements. */
+  for (size_t i = 0; i < NELEMS; i++)
+    table[i] = random();
+
+  /* Sort it using hybrid algorithm... */
+  if (QuickSort(table, 0, NELEMS - 1) > 0)
+    Wait(NULL);
+
+  /* ... and verify if the table is actually sorted. */
+  long prev = LONG_MIN;
+  for (size_t i = 0; i < NELEMS; i++) {
+    assert(prev <= table[i]);
+    prev = table[i];
+  }
+
+  return 0;
+}
diff --git a/semestr-5/so/lista7/so21_lista_7/hashdb.c b/semestr-5/so/lista7/so21_lista_7/hashdb.c
new file mode 100644
index 0000000..d63c32a
--- /dev/null
+++ b/semestr-5/so/lista7/so21_lista_7/hashdb.c
@@ -0,0 +1,207 @@
+#include "csapp.h"
+
+#define ENT_LENGTH 48
+
+#define DB_MODE (S_IWUSR | S_IRUSR | S_IRGRP | S_IROTH)
+#define DB_PROT (PROT_READ | PROT_WRITE)
+
+typedef enum { DB_QUERY, DB_INSERT } op_t;
+typedef char entry_t[ENT_LENGTH];
+
+typedef struct db {
+  entry_t *entry;
+  ssize_t size;
+  char *name;
+} db_t;
+
+static bool db_action(db_t *db, const char *str, op_t op) {
+  /* Do not insert empty strings. Database doesn't store them. */
+  if (*str == '\0')
+    return op == DB_INSERT;
+  size_t len = strnlen(str, ENT_LENGTH);
+  int chain_len = max((db->size >> 14) - 1, 3);
+  uint32_t chain = jenkins_hash(str, len, HASHINIT);
+  for (int c = 0; c < chain_len; c++) {
+    size_t idx = (chain + c) % db->size;
+    if (!db->entry[idx][0] && op == DB_INSERT) {
+      strncpy(db->entry[idx], str, ENT_LENGTH);
+      return true;
+    }
+    if (strncmp(str, db->entry[idx], ENT_LENGTH) == 0)
+      return true;
+  }
+  return false;
+}
+
+#define db_query(db, key) db_action(db, key, DB_QUERY)
+#define db_maybe_insert(db, key) db_action(db, key, DB_INSERT)
+
+/* Open (`size` = 0) or create (`size` > 0) database from `name` file. */
+static void db_open(db_t *db, const char *name, size_t size) {
+  assert(powerof2(size));
+
+  int fd = Open(name, O_RDWR | O_CREAT | (size ? O_EXCL : 0), DB_MODE);
+
+  if (size == 0) {
+    struct stat sb;
+    Fstat(fd, &sb);
+    size = sb.st_size / sizeof(entry_t);
+    if (size == 0)
+      size = 1;
+  }
+
+  /* TODO: Setup DB structure, set file size and map the file into memory.
+           Inform OS that we're going to read DB in random order. */
+  db->size = size;
+  printf("Size: %ld\n", db->size * sizeof(entry_t));
+  Ftruncate(fd, db->size * sizeof(entry_t));
+  db->name = name;
+  db->entry = Mmap(NULL, 
+                   db->size * sizeof(entry_t), 
+                   DB_PROT, 
+                   MAP_SHARED, 
+                   fd, 
+                   0);
+  Madvise(db->entry, db->size * sizeof(entry_t), MADV_RANDOM);
+  Close(fd);
+}
+
+/* Remove DB memory mapping and release associated memory. */
+static void db_close(db_t *db) {
+  Munmap(db->entry, db->size * sizeof(entry_t));
+  free(db->name);
+}
+
+/* Attempt to increase size of database. */
+static bool db_rehash(db_t *db, size_t new_size) {
+  assert(powerof2(new_size));
+
+  /* Create new database. */
+  db_t new[1];
+
+  char *name = alloca(strlen(db->name) + sizeof(".reshash") + 1);
+  strcpy(name, db->name);
+  strcat(name, ".rehash");
+  db_open(new, name, new_size);
+
+  /* Copy everything from old database to new database. */
+  /* TODO: Inform OS that we're going to read DB sequentially. */
+  Madvise(db->entry, db->size * sizeof(entry_t), MADV_SEQUENTIAL);
+  for (size_t i = 0; i < db->size; i++) {
+    if (!db_maybe_insert(new, db->entry[i])) {
+      /* Oops... rehashing failed. Need to increase db size and try again. */
+      /* TODO: Remove new database, since rehashing failed. */
+      Unlink(name);
+      Munmap(new->entry, new->size * sizeof(entry_t));
+      return false;
+    }
+  }
+
+  /* TODO Replace old database with new one, remove old database. */
+  // truncate(db->name, new->size * sizeof(entry_t));
+  // Munmap(db->entry, db->size * sizeof(entry_t));
+  // printf("Going to sleep for a minute\n");
+  // sleep(100);
+  
+  /* Why this doesn't work?????? */
+  // Munmap(db->entry, db->size * sizeof(entry_t));
+  // Unlink(db->name);
+  // db_open(db, db->name, new->size);
+  // Rename(new->name, db->name);
+  // Munmap(new->entry, new->size * sizeof(entry_t));
+  
+  Unlink(db->name);
+  Rename(new->name, db->name);
+  Munmap(db->entry, db->size * sizeof(entry_t));
+  
+  db->entry = new->entry;
+  db->size = new->size;  
+  return true;
+  
+  return true;
+}
+
+/* Insert key into database and possibly increase DB size. */
+static void db_insert(db_t *db, const char *str) {
+  while (!db_maybe_insert(db, str)) {
+    size_t size = db->size;
+    do {
+      size *= 2;
+      fprintf(stderr, "db_rehash: %ld -> %ld\n", db->size, size);
+    } while (!db_rehash(db, size));
+  }
+}
+
+/* Read a key from buffer and perform `mode` operation of the database. */
+static char *consume_line(char *buf, db_t *db, op_t mode) {
+  /* Terminate string at new line character. */
+  char *end = strchr(buf, '\n');
+  if (end) {
+    if (buf < end && end[-1] == '\r')
+      end[-1] = '\0';
+    *end++ = '\0';
+  }
+
+  /* Skip if line is empty. */
+  if (*buf) {
+    if (mode == DB_INSERT)
+      db_insert(db, buf);
+    else if (mode == DB_QUERY)
+      puts(db_query(db, buf) ? "YES" : "NO");
+  }
+
+  /* Return pointer to next line or NULL. */
+  if (end == NULL) {
+    exit(EXIT_FAILURE);
+  }
+  return end;
+}
+
+static void doit(const char *path, op_t mode) {
+  db_t db;
+  db_open(&db, path, 0);
+
+  /* If input file is a terminal device then use standard reading technique. */
+  /* TODO: Use fstat instead to handle pipes correctly. */
+  struct stat sb;
+  Fstat(STDIN_FILENO, &sb);
+
+  if (S_ISCHR(sb.st_mode) || S_ISFIFO(sb.st_mode)) {
+    char buf[ENT_LENGTH + 1];
+    while (fgets(buf, ENT_LENGTH + 1, stdin))
+      consume_line(buf, &db, mode);
+  } else {
+    /* TODO: Map stdin into memory, and read it line by line. */
+    char *input = Mmap(NULL, sb.st_size + 1, PROT_READ | PROT_WRITE, 
+                       MAP_PRIVATE, STDIN_FILENO, 0);
+    printf("strlen: %ld\n", strlen(input));
+    while ((input = consume_line(input, &db, mode)));
+  }
+
+  db_close(&db);
+}
+
+static noreturn void usage(int argc, char **argv) {
+  app_error("Usage: %s [-i|-q] [FILE]", argv[0]);
+}
+
+int main(int argc, char **argv) {
+  op_t mode = -1;
+  int opt;
+
+  while ((opt = getopt(argc, argv, "iq")) != -1) {
+    if (opt == 'i')
+      mode = DB_INSERT;
+    else if (opt == 'q')
+      mode = DB_QUERY;
+    else
+      usage(argc, argv);
+  }
+
+  if (optind >= argc || mode == -1)
+    usage(argc, argv);
+
+  doit(argv[optind], mode);
+
+  return 0;
+}
diff --git a/semestr-5/so/so-shell-new b/semestr-5/so/so-shell-new
new file mode 160000
+Subproject 7d6acaffb78868557a347a84a98ba8193693237