aboutsummaryrefslogtreecommitdiff
path: root/semestr-5/so
diff options
context:
space:
mode:
Diffstat (limited to 'semestr-5/so')
-rw-r--r--semestr-5/so/lista6/so21_lista_6/Makefile.include105
-rw-r--r--semestr-5/so/lista6/so21_lista_6/writeperf.c88
-rwxr-xr-xsemestr-5/so/lista6/so21_lista_6/writeperf.sh17
-rw-r--r--semestr-5/so/lista7/so21_lista_7.pdfbin0 -> 307756 bytes
-rw-r--r--semestr-5/so/lista7/so21_lista_7/forksort.c121
-rw-r--r--semestr-5/so/lista7/so21_lista_7/hashdb.c207
m---------semestr-5/so/so-shell-new0
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
Binary files differ
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
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-22 06:04:09 +0000