Move everything into a new repo.

3 files changed, 377 insertions, 0 deletions

diff --git a/userland/libc/malloc/malloc.c b/userland/libc/malloc/malloc.c
new file mode 100644
index 0000000..f351291
--- /dev/null
+++ b/userland/libc/malloc/malloc.c
@@ -0,0 +1,232 @@
+#include <assert.h>
+#include <errno.h>
+#include <malloc/malloc.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <string.h>
+#include <unistd.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;
+  struct MallocHeader *n;
+} MallocHeader;
+
+size_t max(size_t a, size_t b) { return (a > b) ? a : b; }
+
+//;size_t min(size_t a, size_t b) { return (a < b) ? a : b; }
+
+uint64_t delta_page(uint64_t a) { return 0x1000 - (a % 0x1000); }
+
+MallocHeader *head = NULL;
+MallocHeader *final = NULL;
+uint32_t 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->size = NEW_ALLOC_SIZE - sizeof(MallocHeader);
+  head->flags = IS_FREE | IS_FINAL;
+  head->n = NULL;
+  final = head;
+  return 1;
+}
+
+int add_heap_memory(size_t min_desired) {
+  min_desired += sizeof(MallocHeader) + 0x1000;
+  size_t allocation_size = max(min_desired, NEW_ALLOC_SIZE);
+  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);
+  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;
+  final->n = new_entry;
+  final = new_entry;
+  return 1;
+}
+
+MallocHeader *next_header(MallocHeader *a) { return a->n; }
+
+MallocHeader *next_close_header(MallocHeader *a) {
+  if (!a) {
+    printf("next close header fail\n");
+    for (;;)
+      ;
+  }
+  if (a->flags & IS_FINAL)
+    return NULL;
+  return next_header(a);
+}
+
+MallocHeader *find_free_entry(uint32_t s, int align) {
+  // A new header is required as well as the newly allocated chunk
+  if (!head)
+    init_heap();
+  MallocHeader *p = head;
+  for (; p; p = next_header(p)) {
+    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)
+      continue;
+    return p;
+  }
+  return NULL;
+}
+
+void merge_headers(MallocHeader *b) {
+  if (!(b->flags & IS_FREE))
+    return;
+
+  MallocHeader *n = next_close_header(b);
+  if (!n)
+    return;
+
+  if (n > 0xf58c0820 - 0x8 && n < 0xf58c0820 + 0x8) {
+    printf("b: %x\n", b);
+    printf("b->n: %x\n", b->n);
+    asm("hlt");
+    assert(0);
+  }
+  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)
+    final = b;
+}
+
+extern int errno;
+// https://pubs.opengroup.org/onlinepubs/9699919799/
+void *int_malloc(size_t s, int align) {
+  if (!head)
+    init_heap();
+  size_t n = s;
+  MallocHeader *free_entry = find_free_entry(s, align);
+  if (!free_entry) {
+    if (!add_heap_memory(s)) {
+      errno = ENOMEM;
+      printf("ENOMEM\n");
+      return NULL;
+    }
+    return int_malloc(s, align);
+  }
+
+  void *rc = (void *)((uint32_t)free_entry + sizeof(MallocHeader));
+
+  if (align) {
+    uint64_t d = delta_page((uint32_t)rc);
+    n = d;
+    n -= sizeof(MallocHeader);
+  }
+
+  // Create a new header
+  MallocHeader *new_entry =
+      (MallocHeader *)((uint32_t)free_entry + n + sizeof(MallocHeader));
+  new_entry->magic = MALLOC_HEADER_MAGIC;
+  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)
+    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;
+  }
+  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)
+    return 0;
+  return ((MallocHeader *)(ptr - sizeof(MallocHeader)))->size;
+}
+
+void *realloc(void *ptr, size_t size) {
+  void *rc = malloc(size);
+  if (!rc)
+    return NULL;
+  size_t l = get_mem_size(ptr);
+  size_t to_copy = min(l, size);
+  memcpy(rc, ptr, to_copy);
+  free(ptr);
+  return rc;
+}
+
+void free(void *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) {
+    printf("h->magic: %x\n", h->magic);
+    printf("&h->magic: %x\n", &(h->magic));
+    assert(0);
+  }
+  if (h->flags & IS_FREE)
+    return;
+
+  h->flags |= IS_FREE;
+  merge_headers(h);
+}
diff --git a/userland/libc/malloc/malloc.h b/userland/libc/malloc/malloc.h
new file mode 100644
index 0000000..082d8ad
--- /dev/null
+++ b/userland/libc/malloc/malloc.h
@@ -0,0 +1,9 @@
+#ifndef MALLOC_H
+#define MALLOC_H
+#include <stdint.h>
+#include <stddef.h>
+
+void *malloc(size_t s);
+void *calloc(size_t nelem, size_t elsize);
+void free(void *p);
+#endif
diff --git a/userland/libc/malloc/oldmalloc.c b/userland/libc/malloc/oldmalloc.c
new file mode 100644
index 0000000..042049d
--- /dev/null
+++ b/userland/libc/malloc/oldmalloc.c
@@ -0,0 +1,136 @@
+#include "stdio.h"
+#include "stdlib.h"
+#include "../errno.h"
+#include <stdint.h>
+#include <stddef.h>
+#include <string.h>
+
+#define NEW_ALLOC_SIZE 0x1000
+
+#define IS_FREE (1 << 0)
+#define IS_FINAL (1 << 1)
+
+typedef struct MallocHeader {
+  uint32_t size;
+  uint8_t flags;
+} MallocHeader;
+
+MallocHeader *head = NULL;
+MallocHeader *final = NULL;
+uint32_t total_heap_size = 0;
+
+int init_heap(void) {
+  head = sbrk(NEW_ALLOC_SIZE);
+  if ((void *)-1 == head) {
+    // perror("sbrk");
+    return 0;
+  }
+  total_heap_size += NEW_ALLOC_SIZE;
+  head->size = NEW_ALLOC_SIZE;
+  head->flags = IS_FREE | IS_FINAL;
+  final = head;
+  return 1;
+}
+
+int add_heap_memory(void) {
+  if ((void *)-1 == sbrk(NEW_ALLOC_SIZE)) {
+    // perror("sbrk");
+    return 0;
+  }
+  total_heap_size += NEW_ALLOC_SIZE;
+  final->size += NEW_ALLOC_SIZE;
+  return 1;
+}
+
+MallocHeader *next_header(MallocHeader *a) {
+  if (a->flags & IS_FINAL)
+    return NULL;
+  return ((void *)a) + a->size;
+}
+
+MallocHeader *find_free_entry(uint32_t s) {
+  // A new header is required as well as the newly allocated chunk
+  s += sizeof(MallocHeader);
+  if (!head)
+    init_heap();
+  MallocHeader *p = head;
+  for (; p; p = next_header(p)) {
+    if (!(p->flags & IS_FREE))
+      continue;
+    if (p->size < s)
+      continue;
+    return p;
+  }
+  return NULL;
+}
+
+void merge_headers(MallocHeader *b) {
+  if (!(b->flags & IS_FREE))
+    return;
+
+  MallocHeader *n = next_header(b);
+  if (!n)
+    return;
+
+  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;
+  if (b->flags & IS_FINAL)
+    final = b;
+}
+
+extern int errno;
+// https://pubs.opengroup.org/onlinepubs/9699919799/
+void *malloc(size_t s) {
+  if(s == 0)
+      s = 1;
+
+  MallocHeader *free_entry = find_free_entry(s);
+  if (!free_entry) {
+    if (!add_heap_memory()) {
+        errno = ENOMEM;
+      return NULL;
+    }
+    return malloc(s);
+  }
+
+  // Create a new header
+  MallocHeader *new_entry = ((void *)free_entry) + s;
+  new_entry->flags |= IS_FREE;
+  new_entry->size = free_entry->size - s - sizeof(MallocHeader);
+  new_entry->flags |= free_entry->flags & IS_FINAL;
+  if (new_entry->flags & IS_FINAL)
+    final = new_entry;
+  merge_headers(new_entry);
+
+  // Modify the free entry
+  free_entry->size = s;
+  free_entry->flags = 0;
+
+  return ((void *)free_entry) + sizeof(MallocHeader);
+}
+
+// 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;
+}
+
+void free(void *p) {
+  // FIXME: This assumes that p is at the start of a allocated area.
+  // Is this a assumption that can be made?
+  MallocHeader *h = p - sizeof(MallocHeader);
+  if (h->flags & IS_FREE)
+    return;
+
+  h->flags |= IS_FREE;
+  merge_headers(h);
+}