libc: fix malloc implementation

I don't know what was wrong but memory allocations were failing. I
removed the old code and replaced it with the malloc implementation
which exists in the kernel.

Now it doesn't crash so I guess it is fine ¯\_(ツ)_/¯

1 files changed, 97 insertions, 96 deletions

diff --git a/userland/libc/malloc/malloc.c b/userland/libc/malloc/malloc.c
index 79d1d5f..d1bc5ca 100644
--- a/userland/libc/malloc/malloc.c
+++ b/userland/libc/malloc/malloc.c
@@ -1,41 +1,32 @@
 #include <assert.h>
-#include <errno.h>
-#include <malloc/malloc.h>
 #include <math.h>
 #include <stddef.h>
-#include <stdint.h>
-#include <stdio.h>
-#include <string.h>
-#include <unistd.h>
-
+#include <stdlib.h>
+#include <typedefs.h>
 #define NEW_ALLOC_SIZE 0x20000
-#define MALLOC_HEADER_MAGIC 0x1337F00D
-#define MALLOC_HEADER_PAD 0x11223344
 
 #define IS_FREE (1 << 0)
 #define IS_FINAL (1 << 1)
 
 typedef struct MallocHeader {
-  uint32_t magic;
-  uint32_t size;
-  uint8_t flags;
+  u64 magic;
+  u32 size;
+  u8 flags;
   struct MallocHeader *n;
 } MallocHeader;
 
-uint64_t delta_page(uint64_t a) { return 0x1000 - (a % 0x1000); }
+u64 delta_page(u64 a) {
+  return 0x1000 - (a % 0x1000);
+}
 
 MallocHeader *head = NULL;
 MallocHeader *final = NULL;
-uint32_t total_heap_size = 0;
+u32 total_heap_size = 0;
 
 int init_heap(void) {
   head = (MallocHeader *)sbrk(NEW_ALLOC_SIZE);
-  if ((void *)-1 == head) {
-    perror("sbrk");
-    exit(1);
-  }
   total_heap_size += NEW_ALLOC_SIZE - sizeof(MallocHeader);
-  head->magic = MALLOC_HEADER_MAGIC;
+  head->magic = 0xdde51ab9410268b1;
   head->size = NEW_ALLOC_SIZE - sizeof(MallocHeader);
   head->flags = IS_FREE | IS_FINAL;
   head->n = NULL;
@@ -49,27 +40,37 @@ int add_heap_memory(size_t min_desired) {
   allocation_size += delta_page(allocation_size);
   void *p;
   if ((void *)(-1) == (p = (void *)sbrk(allocation_size))) {
-    perror("sbrk");
     return 0;
   }
   total_heap_size += allocation_size - sizeof(MallocHeader);
   void *e = final;
-  e = (void *)((uint32_t)e + final->size);
+  e = (void *)((u32)e + final->size);
   if (p == e) {
     final->size += allocation_size - sizeof(MallocHeader);
     return 1;
   }
   MallocHeader *new_entry = p;
-  new_entry->magic = MALLOC_HEADER_MAGIC;
   new_entry->size = allocation_size - sizeof(MallocHeader);
   new_entry->flags = IS_FREE | IS_FINAL;
   new_entry->n = NULL;
+  new_entry->magic = 0xdde51ab9410268b1;
   final->n = new_entry;
   final = new_entry;
   return 1;
 }
 
-MallocHeader *next_header(MallocHeader *a) { return a->n; }
+MallocHeader *next_header(MallocHeader *a) {
+  assert(a->magic == 0xdde51ab9410268b1);
+  if (a->n) {
+    if (a->n->magic != 0xdde51ab9410268b1) {
+      printf("Real magic value is: %x\n", a->n->magic);
+      printf("location: %x\n", &(a->n->magic));
+      assert(0);
+    }
+    return a->n;
+  }
+  return NULL;
+}
 
 MallocHeader *next_close_header(MallocHeader *a) {
   if (!a) {
@@ -77,127 +78,107 @@ MallocHeader *next_close_header(MallocHeader *a) {
     for (;;)
       ;
   }
-  if (a->flags & IS_FINAL)
+  if (a->flags & IS_FINAL) {
     return NULL;
+  }
   return next_header(a);
 }
 
-MallocHeader *find_free_entry(uint32_t s, int align) {
+MallocHeader *find_free_entry(u32 s) {
   // A new header is required as well as the newly allocated chunk
-  if (!head)
+  s += sizeof(MallocHeader);
+  if (!head) {
     init_heap();
+  }
   MallocHeader *p = head;
   for (; p; p = next_header(p)) {
-    if (!(p->flags & IS_FREE))
+    assert(p->magic == 0xdde51ab9410268b1);
+    if (!(p->flags & IS_FREE)) {
       continue;
-    uint64_t required_size = s;
-    if (align) {
-      void *addy = p;
-      addy = (void *)((uint32_t)addy + sizeof(MallocHeader));
-      uint64_t d = delta_page((uint32_t)addy);
-      if (d < sizeof(MallocHeader) && d != 0)
-        continue;
-      required_size += d;
     }
-    if (p->size < required_size)
+    u64 required_size = s;
+    if (p->size < required_size) {
       continue;
+    }
     return p;
   }
   return NULL;
 }
 
 void merge_headers(MallocHeader *b) {
-  if (!(b->flags & IS_FREE))
+  if (!(b->flags & IS_FREE)) {
     return;
+  }
 
   MallocHeader *n = next_close_header(b);
-  if (!n)
+  if (!n) {
     return;
+  }
 
-  if (!(n->flags & IS_FREE))
+  if (!(n->flags & IS_FREE)) {
     return;
+  }
 
-  // Remove the next header and just increase the newly freed header
   b->size += n->size;
   b->flags |= n->flags & IS_FINAL;
   b->n = n->n;
-  if (n == final)
+  if (n == final) {
     final = b;
+  }
 }
 
-extern int errno;
-// https://pubs.opengroup.org/onlinepubs/9699919799/
-void *int_malloc(size_t s, int align) {
-  if (!head)
-    init_heap();
+void *malloc(size_t s) {
+  s += 0x1000;
   size_t n = s;
-  MallocHeader *free_entry = find_free_entry(s, align);
+  MallocHeader *free_entry = find_free_entry(s);
   if (!free_entry) {
     if (!add_heap_memory(s)) {
-      errno = ENOMEM;
-      printf("ENOMEM\n");
+      assert(0);
       return NULL;
     }
-    return int_malloc(s, align);
+    return malloc(s);
   }
 
-  void *rc = (void *)((uint32_t)free_entry + sizeof(MallocHeader));
-
-  if (align) {
-    uint64_t d = delta_page((uint32_t)rc);
-    n = d;
-    n -= sizeof(MallocHeader);
-  }
+  void *rc = (void *)(free_entry + 1);
 
   // Create a new header
-  MallocHeader *new_entry =
-      (MallocHeader *)((uint32_t)free_entry + n + sizeof(MallocHeader));
-  new_entry->magic = MALLOC_HEADER_MAGIC;
+  MallocHeader *new_entry = (MallocHeader *)((uintptr_t)rc + n);
   new_entry->flags = free_entry->flags;
   new_entry->n = free_entry->n;
   new_entry->size = free_entry->size - n - sizeof(MallocHeader);
-  if (free_entry == final)
+  new_entry->magic = 0xdde51ab9410268b1;
+
+  if (free_entry == final) {
     final = new_entry;
+  }
   merge_headers(new_entry);
 
   // Modify the free entry
   free_entry->size = n;
   free_entry->flags = 0;
   free_entry->n = new_entry;
-
-  if (align && ((uint32_t)rc % 0x1000) != 0) {
-    void *c = int_malloc(s, 1);
-    free(rc);
-    rc = c;
-    return rc;
+  free_entry->magic = 0xdde51ab9410268b1;
+  for (int i = 0; i < s; i++) {
+    *(char *)rc = 'A';
   }
-  randomfill(rc, s);
-  return rc;
-}
-
-void *malloc(size_t s) { return int_malloc(s + 1, 0); }
-
-// https://pubs.opengroup.org/onlinepubs/9699919799/
-void *calloc(size_t nelem, size_t elsize) {
-  // The calloc() function shall allocate unused space for an array of
-  // nelem elements each of whose size in bytes is elsize.
-  size_t alloc_size = nelem * elsize;
-  void *rc = malloc(alloc_size);
-  // The space shall be initialized to all bits 0.
-  memset(rc, 0, alloc_size);
   return rc;
 }
 
 size_t get_mem_size(void *ptr) {
-  if (!ptr)
+  if (!ptr) {
     return 0;
-  return ((MallocHeader *)((u32)ptr - sizeof(MallocHeader)))->size;
+  }
+  return ((MallocHeader *)((uintptr_t)ptr - sizeof(MallocHeader)))->size;
 }
 
 void *realloc(void *ptr, size_t size) {
   void *rc = malloc(size);
-  if (!rc)
+  if (!rc) {
     return NULL;
+  }
+  if (!ptr) {
+    return rc;
+  }
   size_t l = get_mem_size(ptr);
   size_t to_copy = min(l, size);
   memcpy(rc, ptr, to_copy);
@@ -205,24 +186,44 @@ void *realloc(void *ptr, size_t size) {
   return rc;
 }
 
+// This is sqrt(SIZE_MAX+1), as s1*s2 <= SIZE_MAX
+// if both s1 < MUL_NO_OVERFLOW and s2 < MUL_NO_OVERFLOW
+#define MUL_NO_OVERFLOW ((size_t)1 << (sizeof(size_t) * 4))
+
+void *reallocarray(void *ptr, size_t nmemb, size_t size) {
+  if ((nmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) && nmemb > 0 &&
+      SIZE_MAX / nmemb < size) {
+    return NULL;
+  }
+
+  return realloc(ptr, nmemb * size);
+}
+
+void *allocarray(size_t nmemb, size_t size) {
+  return reallocarray(NULL, nmemb, size);
+}
+
+void *calloc(size_t nelem, size_t elsize) {
+  void *rc = allocarray(nelem, elsize);
+  if (!rc) {
+    return NULL;
+  }
+  memset(rc, 0, nelem * elsize);
+  return rc;
+}
+
 void free(void *p) {
-  if (!p)
+  if (!p) {
     return;
+  }
   // FIXME: This assumes that p is at the start of a allocated area.
-  // Is this a assumption that can be made?
-  MallocHeader *h = (MallocHeader *)((uint32_t)p - sizeof(MallocHeader));
-  if (MALLOC_HEADER_MAGIC != h->magic) {
-#ifdef LIBC_DEBUG
-    printf("LibC Malloc: free() is attempted at the incorrect location or at a corrupted header.\n");
-    printf("h->magic: %x\n", h->magic);
-    printf("&h->magic: %x\n", &(h->magic));
-#endif
+  // Could this be avoided in a simple way?
+  MallocHeader *h = (MallocHeader *)((uintptr_t)p - sizeof(MallocHeader));
+  assert(h->magic == 0xdde51ab9410268b1);
+  if (h->flags & IS_FREE) {
     return;
   }
-  if (h->flags & IS_FREE)
-    return;
 
-  randomfill(p, h->size);
   h->flags |= IS_FREE;
   merge_headers(h);
 }