lib/malloc: add linked list implementation

12 files changed, 222 insertions, 1 deletions

diff --git a/.gitignore b/.gitignore
index 1796b0a..2ca6696 100644
--- a/.gitignore
+++ b/.gitignore
@@ -7,3 +7,4 @@ build*
 isodir
 src/conf.h
 .config.old
+test_*
diff --git a/Makefile b/Makefile
index 9e781b3..d3d8968 100644
--- a/Makefile
+++ b/Makefile
@@ -26,6 +26,7 @@ info:
 
 test:
 	grep -r 'asm' devices lib src
+	make -C lib test
 
 FORCE:
 
diff --git a/Makefile.config b/Makefile.config
index c3f80ad..a683ac8 100644
--- a/Makefile.config
+++ b/Makefile.config
@@ -37,4 +37,7 @@ AR      := i686-elf-ar
 ARFLAGS := -crus
 STRIP   := i686-elf-strip
 
+# test framework
+GTEST   := $(shell pkg-config --cflags --libs gtest gtest_main)
+GMOCK   := $(shell pkg-config --cflags --libs gmock)
 
diff --git a/i686/toolchain.mk b/i686/toolchain.mk
index 1c0d922..1747a8b 100644
--- a/i686/toolchain.mk
+++ b/i686/toolchain.mk
@@ -13,4 +13,7 @@ AR      := i686-elf-ar
 ARFLAGS := -crus
 STRIP   := i686-elf-strip
 
+# test framework
+GTEST   := $(shell pkg-config --cflags --libs gtest gtest_main)
+GMOCK   := $(shell pkg-config --cflags --libs gmock)
 
diff --git a/lib/Makefile b/lib/Makefile
index 0da59de..042eccc 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -6,3 +6,6 @@ libk.SRCS = memcpy.c memset.c stdio/printf.c string/itoa.c
 
 include ../rules.mk
 
+.PHONY: test
+test: tst/test_linked_list_allocator
+	@$(foreach f,$^,./$f)
diff --git a/lib/stdlib.h b/lib/stdlib.h
new file mode 100644
index 0000000..6b8e09d
--- /dev/null
+++ b/lib/stdlib.h
@@ -0,0 +1,6 @@
+#pragma once
+
+#include <stddef.h>
+
+void *malloc(size_t size);
+void free(void *ptr);
diff --git a/lib/stdlib/linked_list_allocator.c b/lib/stdlib/linked_list_allocator.c
new file mode 100644
index 0000000..66c63d1
--- /dev/null
+++ b/lib/stdlib/linked_list_allocator.c
@@ -0,0 +1,77 @@
+#include <stdint.h>
+#include <stdlib.h>
+
+struct Chunk {
+  struct Chunk *prev;
+  struct Chunk *next;
+  int used;
+  size_t size;
+};
+
+void
+Chunk_ctor(struct Chunk *self, size_t size)
+{
+  self->prev = NULL;
+  self->next = NULL;
+  self->used = 0;
+  self->size = size - sizeof(struct Chunk);
+}
+
+static struct Chunk *begin = NULL;
+
+void
+alloc_init(void *mem, size_t size)
+{
+  if (size < sizeof(struct Chunk)) return;
+
+  begin = (struct Chunk *)mem;
+  Chunk_ctor(begin, size);
+}
+
+void *
+malloc(size_t size)
+{
+  if (begin == NULL) return NULL;
+
+  // find free chunk that is at least (size + sizeof(struct Chunk))
+  for (struct Chunk *iter = begin; iter != NULL; iter = iter->next) {
+    if (iter->used != 0 || iter->size < size) continue;
+
+    // if there's at least sizeof(struct Chunk) bytes left over, create a new Chunk
+    if (iter->size >= (size + 2 * sizeof(struct Chunk))) {
+      struct Chunk *next = (struct Chunk *)((uintptr_t)iter + sizeof(struct Chunk) + size);
+      Chunk_ctor(next, iter->size - size - sizeof(struct Chunk));
+      next->prev = iter;
+
+      iter->size = size;
+      iter->next = next;
+    }
+
+    iter->used = 1;
+    return (void *)((uintptr_t)iter + sizeof(struct Chunk));
+  }
+
+  return NULL;
+}
+
+void
+free(void *ptr)
+{
+  if (ptr == NULL) return;
+  struct Chunk *chunk = (struct Chunk *)((uintptr_t)ptr - sizeof(struct Chunk));
+  chunk->used = 0;
+
+  // merge next chunk
+  if (chunk->next != NULL && chunk->next->used == 0) {
+    chunk->size += chunk->next->size + sizeof(struct Chunk);
+    chunk->next = chunk->next->next;
+    if (chunk->next != NULL) chunk->next->prev = chunk;
+  }
+
+  // merge into prev chunk
+  if (chunk->prev != NULL && chunk->prev->used == 0) {
+    chunk->prev->size += chunk->size + sizeof(struct Chunk);
+    chunk->prev->next = chunk->next;
+    if (chunk->next != NULL) chunk->next->prev = chunk->prev;
+  }
+}
diff --git a/lib/tst/allocator.hh b/lib/tst/allocator.hh
new file mode 100644
index 0000000..3bc1715
--- /dev/null
+++ b/lib/tst/allocator.hh
@@ -0,0 +1,22 @@
+#pragma once
+
+class TestAllocator : public ::testing::Test {
+protected:
+  void
+  SetUp() override
+  {
+    memory = malloc(memory_size);
+    libk::alloc_init(memory, memory_size);
+    ASSERT_EQ(libk::begin, memory);
+  }
+
+  void
+  TearDown() override
+  {
+    free(memory);
+    libk::begin = nullptr;
+  }
+
+  const size_t memory_size = 4096;
+  void *memory = nullptr;
+};
diff --git a/lib/tst/linked_list_allocator.cc b/lib/tst/linked_list_allocator.cc
new file mode 100644
index 0000000..f3af8e2
--- /dev/null
+++ b/lib/tst/linked_list_allocator.cc
@@ -0,0 +1,98 @@
+#include <gtest/gtest.h>
+#include <iomanip>
+#include <iostream>
+
+namespace libk {
+#include "../stdlib/linked_list_allocator.c"
+
+std::ostream &
+operator<<(std::ostream &os, const Chunk &begin)
+{
+  for (const Chunk *iter = &begin; iter != nullptr; iter = iter->next) {
+    os << iter << "   used=" << iter->used << "  size=" << std::setw(4) << iter->size << "  next=" << iter->next
+       << std::endl;
+  }
+  return os;
+}
+}; // namespace libk
+
+#include "allocator.hh"
+
+TEST(UninitializedAllocator, malloc) { EXPECT_EQ(libk::malloc(1024), nullptr); }
+
+TEST_F(TestAllocator, mallocMoreThanAvialable)
+{
+  void *ptr = libk::malloc(memory_size);
+  EXPECT_EQ(ptr, nullptr) << *libk::begin;
+}
+
+TEST_F(TestAllocator, mallocExactlyAvialable)
+{
+  void *ptr = libk::malloc(memory_size - sizeof(libk::Chunk));
+  EXPECT_NE(ptr, nullptr) << *libk::begin;
+}
+
+TEST_F(TestAllocator, malloc)
+{
+  libk::Chunk *begin = libk::begin;
+
+  void *ptr0 = libk::malloc(1024);
+  EXPECT_NE(ptr0, nullptr) << *libk::begin;
+  EXPECT_EQ(reinterpret_cast<std::uintptr_t>(ptr0),
+            reinterpret_cast<std::uintptr_t>(libk::begin) + sizeof(libk::Chunk));
+  EXPECT_EQ(begin->used, 1);
+  EXPECT_EQ(begin->size, 1024);
+  ASSERT_NE(begin->next, nullptr);
+  begin = begin->next;
+
+  void *ptr1 = libk::malloc(512);
+  EXPECT_NE(ptr1, nullptr) << *libk::begin;
+  EXPECT_EQ(reinterpret_cast<std::uintptr_t>(ptr1),
+            reinterpret_cast<std::uintptr_t>(libk::begin) + 2 * sizeof(libk::Chunk) + 1024);
+  EXPECT_EQ(begin->used, 1);
+  EXPECT_EQ(begin->size, 512);
+  ASSERT_NE(begin->next, nullptr);
+}
+
+TEST_F(TestAllocator, freeNullptr)
+{
+  void *ptr0 = libk::malloc(1024);
+  EXPECT_NE(ptr0, nullptr) << *libk::begin;
+  void *ptr1 = libk::malloc(512);
+  EXPECT_NE(ptr1, nullptr) << *libk::begin;
+
+  libk::free(nullptr);
+  libk::Chunk *begin = libk::begin;
+  EXPECT_EQ(begin->used, 1);
+  EXPECT_NE(begin->next, nullptr);
+  begin = begin->next;
+  EXPECT_EQ(begin->used, 1);
+  EXPECT_NE(begin->next, nullptr);
+  begin = begin->next;
+  EXPECT_EQ(begin->used, 0);
+  EXPECT_EQ(begin->next, nullptr);
+}
+
+TEST_F(TestAllocator, free)
+{
+  void *ptr0 = libk::malloc(1024);
+  EXPECT_NE(ptr0, nullptr) << *libk::begin;
+  void *ptr1 = libk::malloc(512);
+  EXPECT_NE(ptr1, nullptr) << *libk::begin;
+
+  libk::free(ptr0);
+  libk::Chunk *begin = libk::begin;
+  EXPECT_EQ(begin->used, 0) << ptr0 << ": ptr0" << std::endl << *libk::begin;
+  EXPECT_NE(begin->next, nullptr);
+  begin = begin->next;
+  EXPECT_EQ(begin->used, 1);
+  EXPECT_NE(begin->next, nullptr);
+  begin = begin->next;
+  EXPECT_EQ(begin->used, 0);
+  EXPECT_EQ(begin->next, nullptr);
+
+  libk::free(ptr1);
+  begin = libk::begin;
+  EXPECT_EQ(begin->used, 0) << ptr0 << ": ptr0" << std::endl << *libk::begin;
+  EXPECT_EQ(begin->next, nullptr);
+}
diff --git a/lib/test/mem.c b/lib/tst/mem.c
index bccb3a3..bccb3a3 100644
--- a/lib/test/mem.c
+++ b/lib/tst/mem.c
diff --git a/lib/test/string.c b/lib/tst/string.c
index 725d547..725d547 100644
--- a/lib/test/string.c
+++ b/lib/tst/string.c
diff --git a/rules.mk b/rules.mk
index 21c2f7e..92ca71d 100644
--- a/rules.mk
+++ b/rules.mk
@@ -23,7 +23,14 @@ $(foreach V,$(filter %.SRCS, ${.VARIABLES}),\
 	@echo '  CC   $^'
 	@$(CC) $(CCFLAGS) -c -o $@ $^
 
+# Test rules
+tst/test_%: tst/%.cc FORCE
+	@echo '  CXX  $@'
+	@${CXX} $< -o $@ $(GTEST) $(GMOCK)
+
 # clean target
-.PHONY: clean
+.PHONY: clean FORCE
 clean:
 	@$(foreach V,$(filter %.OBJS, ${.VARIABLES}), rm -rf $($(V)))
+
+FORCE: