Rewrite syslog buffer to use a generic fifo

Trivia: I wrote this ring buffer implementation in half an hour during a Google interview and it somehow works better than the old one which took me half a day.
mehfooz09 · Jan 6, 2019 · a0ca767 · a0ca767
1 parent 032a218
commit a0ca767
Show file tree

Hide file tree

Showing 4 changed files with 131 additions and 56 deletions.
diff --git a/kernel/log.c b/kernel/log.c
@@ -7,13 +7,14 @@
 #endif
 #include "kernel/calls.h"
 #include "util/sync.h"
+#include "util/fifo.h"
 #include "kernel/task.h"
 #include "misc.h"
 
 #define LOG_BUF_SHIFT 20
-static char log_buf[1 << LOG_BUF_SHIFT];
-static size_t log_head = 0;
-static size_t log_size = 0;
+static char log_buffer[1 << LOG_BUF_SHIFT];
+static struct fifo log_buf = FIFO_INIT(log_buffer);
+static size_t log_max_since_clear = 0;
 static lock_t log_lock = LOCK_INITIALIZER;
 
 #define SYSLOG_ACTION_CLOSE_ 0
@@ -28,55 +29,44 @@ static lock_t log_lock = LOCK_INITIALIZER;
 #define SYSLOG_ACTION_SIZE_UNREAD_ 9
 #define SYSLOG_ACTION_SIZE_BUFFER_ 10
 
-static int syslog_read(size_t start, addr_t buf_addr, int_t total) {
-    if (total > log_size)
-        total = log_size;
-    size_t remaining = total;
-    size_t log_p = log_head;
-    char buf[total];
-    char *b = buf;
-    while (remaining > 0) {
-        size_t len = remaining;
-        if (len > sizeof(log_buf) - log_head)
-            len = sizeof(log_buf) - log_head;
-        memcpy(b, &log_buf[log_p], len);
-        log_p = (log_p + len) % sizeof(log_buf);
-        b += len;
-        remaining -= len;
+static int syslog_read(addr_t buf_addr, int_t len, int flags) {
+    if (len < 0)
+        return _EINVAL;
+    if (flags & FIFO_LAST) {
+        if ((size_t) len > log_max_since_clear)
+            len = log_max_since_clear;
+    } else {
+        if ((size_t) len > fifo_capacity(&log_buf))
+            len = fifo_capacity(&log_buf);
     }
-    if (user_write(buf_addr, buf, total))
-        return -1;
-    return total;
-}
-static int syslog_read_all(addr_t buf_addr, addr_t len) {
-    if (len > log_size)
-        len = log_size;
-    return syslog_read((log_head + log_size - len) % sizeof(log_buf), buf_addr, len);
+    char buf[len];
+    fifo_read(&log_buf, buf, len, flags);
+    if (user_write(buf_addr, buf, len))
+        return _EFAULT;
+    return len;
 }
 
 static int do_syslog(int type, addr_t buf_addr, int_t len) {
+    int res;
     switch (type) {
         case SYSLOG_ACTION_READ_:
-            len = syslog_read(log_head, buf_addr, len);
-            if (len < 0)
-                return _EFAULT;
-            log_head = (log_head + len) % sizeof(log_buf);
-            log_size -= len;
-            return len;
+            return syslog_read(buf_addr, len, 0);
         case SYSLOG_ACTION_READ_ALL_:
-            return syslog_read_all(buf_addr, len);
+            return syslog_read(buf_addr, len, FIFO_LAST | FIFO_PEEK);
+
         case SYSLOG_ACTION_READ_CLEAR_:
-            len = syslog_read_all(buf_addr, len);
-            log_head = log_size = 0;
-            return len;
+            res = syslog_read(buf_addr, len, FIFO_LAST | FIFO_PEEK);
+            if (res < 0)
+                return res;
+            // fallthrough
         case SYSLOG_ACTION_CLEAR_:
-            log_head = log_size = 0;
+            log_max_since_clear = 0;
             return 0;
 
         case SYSLOG_ACTION_SIZE_UNREAD_:
-            return log_size;
+            return fifo_size(&log_buf);
         case SYSLOG_ACTION_SIZE_BUFFER_:
-            return sizeof(log_buf);
+            return fifo_capacity(&log_buf);
 
         case SYSLOG_ACTION_CLOSE_:
         case SYSLOG_ACTION_OPEN_:
@@ -96,23 +86,10 @@ int_t sys_syslog(int_t type, addr_t buf_addr, int_t len) {
 }
 
 static void log_buf_append(const char *msg) {
-    size_t log_p = (log_head + log_size) % sizeof(log_buf);
-    size_t remaining = strlen(msg);
-    while (*msg != '\0') {
-        size_t log_tail = (log_head + log_size) % sizeof(log_buf);
-        size_t len = sizeof(log_buf) - log_tail;
-        if (len > remaining)
-            len = remaining;
-        memcpy(&log_buf[log_p], msg, len);
-        log_size += len;
-        if (log_size > sizeof(log_buf)) {
-            log_head = (log_head + log_size - sizeof(log_buf)) % sizeof(log_buf);
-            log_size = sizeof(log_buf);
-        }
-        log_p = (log_p + len) % sizeof(log_buf);
-        msg += len;
-        remaining -= len;
-    }
+    fifo_write(&log_buf, msg, strlen(msg), FIFO_OVERWRITE);
+    log_max_since_clear += strlen(msg);
+    if (log_max_since_clear > fifo_capacity(&log_buf))
+        log_max_since_clear = fifo_capacity(&log_buf);
 }
 static void log_line(const char *line);
 static void output_line(const char *line) {

diff --git a/meson.build b/meson.build
@@ -94,6 +94,7 @@ src = [
 
     'util/timer.c',
     'util/sync.c',
+    'util/fifo.c',
 
     'emu/memory.c',
     'emu/tlb.c',

diff --git a/util/fifo.c b/util/fifo.c
@@ -0,0 +1,66 @@
+#include <stdlib.h>
+#include <string.h>
+#include "util/fifo.h"
+
+void fifo_init(struct fifo *fifo, size_t capacity) {
+    fifo->buf = malloc(capacity);
+    fifo->capacity = capacity;
+    fifo->size = fifo->start = 0;
+}
+
+void fifo_destroy(struct fifo *fifo) {
+    free(fifo->buf);
+}
+
+size_t fifo_capacity(struct fifo *fifo) {
+    return fifo->capacity;
+}
+size_t fifo_size(struct fifo *fifo) {
+    return fifo->size;
+}
+size_t fifo_remaining(struct fifo *fifo) {
+    return fifo->capacity - fifo->size;
+}
+
+int fifo_write(struct fifo *fifo, const void *data, size_t size, int flags) {
+    if (size > fifo_remaining(fifo)) {
+        if (!(flags & FIFO_OVERWRITE))
+            return 1;
+        size_t excess = size - fifo_remaining(fifo);
+        fifo->start = (fifo->start + excess) % fifo->capacity;
+        fifo->size -= excess;
+    }
+
+    size_t first_copy_size = fifo->capacity - fifo->start - fifo->size;
+    if (first_copy_size > size)
+        first_copy_size = size;
+    memcpy(&fifo->buf[fifo->start + fifo->size], data, first_copy_size);
+    memcpy(&fifo->buf[0], (char *) data + first_copy_size, size - first_copy_size);
+    fifo->size += size;
+    return 0;
+}
+
+int fifo_read(struct fifo *fifo, void *buf, size_t size, int flags) {
+    if (size > fifo_size(fifo))
+        return 1;
+
+    size_t start = fifo->start;
+    if (flags & FIFO_LAST)
+        start = (start + (fifo->size - size)) % fifo->capacity;
+
+    size_t first_copy_size = fifo->capacity - fifo->start;
+    if (first_copy_size > size)
+        first_copy_size = size;
+    memcpy(buf, &fifo->buf[start], first_copy_size);
+    memcpy((char *) buf + first_copy_size, &fifo->buf[0], size - first_copy_size);
+
+    if (!(flags & FIFO_PEEK)) {
+        fifo->start = (start + size) % fifo->capacity;
+        fifo->size -= size;
+    }
+    return 0;
+}
+
+void fifo_flush(struct fifo *fifo) {
+    fifo->size = 0;
+}
diff --git a/util/fifo.h b/util/fifo.h
@@ -0,0 +1,31 @@
+#ifndef UTIL_FIFO_H
+#define UTIL_FIFO_H
+#include <sys/types.h>
+
+struct fifo {
+    char *buf;
+    size_t capacity;
+    size_t size;
+    size_t start;
+};
+
+#define FIFO_INIT(b) ((struct fifo) {.buf = b, .capacity = sizeof(b)})
+void fifo_init(struct fifo *fifo, size_t capacity);
+void fifo_destroy(struct fifo *fifo);
+
+size_t fifo_capacity(struct fifo *fifo);
+size_t fifo_size(struct fifo *fifo);
+size_t fifo_remaining(struct fifo *fifo);
+
+// return 0 on success, 1 if size > fifo_remaining and FIFO_OVERWRITE was not specified
+#define FIFO_OVERWRITE 1
+int fifo_write(struct fifo *fifo, const void *data, size_t size, int flags);
+
+// return 0 on success, 1 if size > fifo_size
+#define FIFO_PEEK 1 // don't remove the bytes
+#define FIFO_LAST 2 // return bytes from the end, not the start
+int fifo_read(struct fifo *fifo, void *buf, size_t size, int flags);
+
+void fifo_flush(struct fifo *fifo);
+
+#endif