many, many changes; settings is broken

4 files changed, 137 insertions, 114 deletions

diff --git a/src/user/knob/block.c b/src/user/knob/block.c
index 9f3f353..8b9971f 100644
--- a/src/user/knob/block.c
+++ b/src/user/knob/block.c
@@ -1,4 +1,5 @@
 #include <knob/panic.h>
+#include <knob/block.h>
 #include <knob/heap.h>
 #include <stdbool.h>
 #include <stdint.h>
@@ -28,13 +29,22 @@ uint32_t strcpy(char *to, const char *from) {
 }
 
 char *strdup(const char *from) {
-  const char *end = from;
-  while (*(end++))
-    ;
-  char *buf = get_block(end - from);
-  if (!buf)
-    PANIC("get_block returned 0 in strdup");
-  blockcpy(buf, from, end - from);
+  const uint32_t len = strlen(from) + 1;
+  char *buf = get_block(len);
+  blockcpy(buf, from, len);
+  return buf;
+}
+
+char *strndup(const char *from, uint32_t n) {
+  uint32_t len = strlen(from) + 1;
+  if (n < len) {
+    char *buf = get_block(n + 1);
+    blockcpy(buf, from, n);
+    buf[n] = '\0';
+    return buf;
+  }
+  char *buf = get_block(len);
+  blockcpy(buf, from, len);
   return buf;
 }
 
diff --git a/src/user/knob/file.c b/src/user/knob/file.c
index 999778e..d844588 100644
--- a/src/user/knob/file.c
+++ b/src/user/knob/file.c
@@ -29,7 +29,7 @@ struct file {
 };
 
 struct file *open_file(const char *path) {
-  _file_handle_t h = _open_file(0, path);
+  _file_handle_t h = _open_file(path);
   if (!h)
     return 0;
 
@@ -125,13 +125,13 @@ void trunc_file(struct file *f) {
 
 //return value must be manually freed, unless it is a null pointer
 _dir_info_entry_t *get_directory_info(const char *path, uint32_t *count_out) {
-  uint32_t count = _count_of_dir(0, path);
+  uint32_t count = _count_of_dir(path);
   if (!count) {
     *count_out = 0;
     return 0;
   }
 
   _dir_info_entry_t *buffer = get_block(count * sizeof(_dir_info_entry_t));
-  *count_out = _enumerate_dir(0, path, buffer, count);
+  *count_out = _enumerate_dir(path, buffer, count);
   return buffer;
 }
\ No newline at end of file
diff --git a/src/user/knob/heap.c b/src/user/knob/heap.c
index 6e57000..c4b810e 100644
--- a/src/user/knob/heap.c
+++ b/src/user/knob/heap.c
@@ -1,128 +1,141 @@
-#include <knob/format.h>
-
 #include <pland/syscall.h>
-
+#include <pland/pcrt.h>
 #include <stdbool.h>
 #include <stdint.h>
 
-//structure appears at the start of each block
-struct block_header {
-  struct block_header *next;
-  struct block_header *prev;
+#define MIN_NEW_CHUNK_PAGES 16
 
-  //does not include header
-  uint32_t length;
-  bool allocated;
+struct desc_page_head {
+  void *next_page;//0 for last one
 };
 
-static struct block_header *first_block = 0;
+struct chunk_desc {
+  void *start;//0 for a desc not in use
+  uint32_t length;
+  bool available;
+} __attribute__ ((packed));
+//without packing, it is 12 bytes and we get 341 per page
+//with    packing, it is  9 bytes and we get 454 per page
+//maybe i should make available just the top bit of length
+//then we get 511 per page, but length has a max of 2^31-1
+
+static struct desc_page_head *first_desc_page = 0;
+static struct desc_page_head *last_desc_page = 0;
+
+#define DESCS_PER_PAGE ((4096 - sizeof(struct desc_page_head)) / sizeof(struct chunk_desc))
+#define PAGE_AS_ARRAY(p) ((struct chunk_desc *)((void *)p + sizeof(struct desc_page_head)))
+
+static char size_was_buf[] = "size was ......... kB";
+//kb should be < 1 000 000 000
+static void log_size_was(uint32_t kb) {
+  for (int8_t d = 9; d != -1; --d) {
+    size_was_buf[9 + d] = (kb % 10) + '0';
+    kb /= 10;
+  }
+  _system_log(size_was_buf);
+}
 
-static void add_header(struct block_header *bh) {
-  bh->next = first_block;
-  bh->prev = 0;
-  if (first_block)
-    first_block->prev = bh;
-  first_block = bh;
+static const char *const hextab = "0123456789abcdef";
+static char caller_was_buf[] = "return address is 0x........";
+static void log_caller_was(void *addr) {
+  const uint32_t as_int = (uint32_t)addr;
+  for (uint8_t i = 0; i < 8; ++i)
+    caller_was_buf[27 - i] = hextab[(as_int >> (4 * i)) & 0xf];
+  _system_log(caller_was_buf);
 }
 
-//static const char *const hextab = "0123456789abcdef";
-//static char *const get_debug = "getting 0x........ byte block";
-//static char *const free_debug = "freeing 0x........ byte block";
+static struct desc_page_head *new_desc_page() {
+  struct desc_page_head *dph = _allocate_ram(1);
+  if (!dph) {
+    _system_log("knob heap could not allocate new descriptor page");
+    log_size_was(4);
+    __pcrt_quit();
+  }
+  dph->next_page = 0;
+  if (last_desc_page)
+    last_desc_page->next_page = dph;
+  last_desc_page = dph;
+
+  struct chunk_desc *const a = PAGE_AS_ARRAY(dph);
+  for (uint32_t i = 0; i < DESCS_PER_PAGE; ++i)
+    a[i].start = 0;
 
-__attribute__ ((malloc))
-void *get_block(uint32_t bytes) {
-  if (!bytes)
-    return 0;
-//for (uint8_t i = 0; i < 8; ++i)
-//  get_debug[10 + 7 - i] = hextab[(bytes >> (i * 4)) & 0xf];
-//_system_log(get_debug);
-
-  struct block_header *header = 0;
-  for (struct block_header *ptr = first_block; ptr; ptr = ptr->next) {
-    if (ptr->allocated)
-      continue;
-    if (ptr->length == bytes) {
-      header = ptr;
-      break;
-    }
-    if (ptr->length > bytes + sizeof(struct block_header)) {
-      struct block_header *bh = (void *)ptr + sizeof(struct block_header) + bytes;
+  return dph;
+}
+
+static struct chunk_desc *unused_desc() {
+  for (struct desc_page_head *i = first_desc_page; i; i = i->next_page) {
+    struct chunk_desc *const a = PAGE_AS_ARRAY(i);
+    for (uint32_t i = 0; i < DESCS_PER_PAGE; ++i)
+      if (!a[i].start)
+        return a + i;
+  }
 
-      bh->length = ptr->length - sizeof(struct block_header) - bytes;
-      bh->allocated = false;
-      add_header(bh);
+  return PAGE_AS_ARRAY(new_desc_page());
+}
 
-      ptr->length = bytes;
-      header = ptr;
-      break;
+__attribute__ ((malloc))
+void *get_block(uint32_t bytes) {
+  if (!first_desc_page)
+    first_desc_page = new_desc_page();
+
+  struct chunk_desc *best_fit = 0;
+
+  for (struct desc_page_head *i = first_desc_page; i; i = i->next_page) {
+    struct chunk_desc *const a = PAGE_AS_ARRAY(i);
+    for (uint32_t i = 0; i < DESCS_PER_PAGE; ++i) {
+      if (!a[i].start || !a[i].available || (a[i].length < bytes))
+        continue;
+      if (a[i].length == bytes) {
+        a[i].available = false;
+        return a[i].start;
+      }
+      if (!best_fit || (a[i].length < best_fit->length))
+        best_fit = a + i;
     }
   }
 
-  if (!header) {
-    uint32_t size_with_header = bytes + sizeof(struct block_header);
-    if (!(size_with_header % 4096)) {
-      header = _allocate_ram(size_with_header / 4096);
-      if (!header)
-        return 0;
-      header->length = bytes;
-      add_header(header);
+  if (!best_fit) {
+    const uint32_t pages_needed = (bytes - 1) / 4096 + 1;
+    const uint32_t allocating = pages_needed < MIN_NEW_CHUNK_PAGES ? MIN_NEW_CHUNK_PAGES : pages_needed;
+    void *const new_chunk = _allocate_ram(allocating);
+    if (!new_chunk) {
+      _system_log("knob heap could not allocate new chunk");
+      log_size_was(allocating * 4);
+      log_caller_was(__builtin_return_address(0));
+      __pcrt_quit();
     }
-    else {
-      uint32_t pages = (bytes + sizeof(struct block_header) * 2) / 4096 + 1;
-      header = _allocate_ram(pages);
-      if (!header)
-        return 0;
-      header->length = bytes;
-      add_header(header);
-
-      struct block_header *bh = (void *)header + sizeof(struct block_header) + bytes;
-      bh->length = pages * 4096 - bytes - 2 * sizeof(struct block_header);
-      bh->allocated = false;
-      add_header(bh);
+    best_fit = unused_desc();
+    best_fit->start = new_chunk;
+    best_fit->length = allocating * 4096;
+
+    if (bytes == allocating * 4096) {
+      best_fit->available = false;
+      return new_chunk;
     }
   }
 
-  header->allocated = true;
-  return (void *)header + sizeof(struct block_header);
-}
-
-static void remove_header(struct block_header *bh) {
-  if (bh == first_block)
-    first_block = bh->next;
-  if (bh->prev)
-    bh->prev->next = bh->next;
-  if (bh->next)
-    bh->next->prev = bh->prev;
-}
+  void *const old_end = best_fit->start + best_fit->length;
+  void *const new_end = best_fit->start + bytes;
 
-void free_block(void *block) {
-  struct block_header *header = block - sizeof(struct block_header);
+  best_fit->length = bytes;
+  best_fit->available = false;
 
-//for (uint8_t i = 0; i < 8; ++i)
-//  free_debug[10 + 7 - i] = hextab[(header->length >> (i * 4)) & 0xf];
-//_system_log(free_debug);
+  struct chunk_desc *const leftover = unused_desc();
+  leftover->start = new_end;
+  leftover->length = old_end - new_end;
 
-  header->allocated = false;
+  return best_fit->start;
+}
 
-  void *after = block + header->length;
-  for (struct block_header *ptr = first_block; ptr; ptr = ptr->next) {
-    if (ptr == after) {
-      if (!ptr->allocated) {
-        header->length += ptr->length + sizeof(struct block_header);
-        remove_header(ptr);
+void free_block(const void *block) {
+  for (struct desc_page_head *i = first_desc_page; i; i = i->next_page) {
+    struct chunk_desc *const a = PAGE_AS_ARRAY(i);
+    for (uint32_t i = 0; i < DESCS_PER_PAGE; ++i)
+      if (a[i].start == block) {
+        //TODO: consolidate this with surrounding free chunks
+        a[i].available = true;
+        return;
       }
-      break;
-    }
   }
-
-  //we traverse the linked list twice. it would probably be more efficient
-  //to do both finding the after and finding the before in the same loop.
-  for (struct block_header *ptr = first_block; ptr; ptr = ptr->next)
-    if ((void *)ptr + sizeof(struct block_header) + ptr->length == header) {
-      if (!ptr->allocated) {
-        ptr->length += sizeof(struct block_header) + header->length;
-        remove_header(header);
-      }
-      break;
-    }
-}
\ No newline at end of file
+}
diff --git a/src/user/knob/task.c b/src/user/knob/task.c
index 9bf2c83..ba0ac36 100644
--- a/src/user/knob/task.c
+++ b/src/user/knob/task.c
@@ -14,12 +14,12 @@ _task_handle_t run_command(const char *path, _task_handle_t stdio_task) {
       blockcpy(new_path, path, ptr - path);
       new_path[ptr - path] = '\0';
 
-      _task_handle_t handle = _start_task(0, new_path, ptr + 1, stdio_task);
+      _task_handle_t handle = _start_task(new_path, ptr + 1, stdio_task);
       free_block(new_path);
       return handle;
     }
 
-  return _start_task(0, path, "", stdio_task);
+  return _start_task(path, "", stdio_task);
 }
 
 bool try_run_command_blocking(const char *path, _task_handle_t stdio_task) {