From 2e0702c597e3099316c8c82379c3425ecc7a2dd2 Mon Sep 17 00:00:00 2001 From: aqua Date: Sun, 6 Nov 2022 14:29:39 +0200 Subject: lib/malloc: add linked list implementation --- lib/Makefile | 3 ++ lib/stdlib.h | 6 +++ lib/stdlib/linked_list_allocator.c | 77 ++++++++++++++++++++++++++++++ lib/test/mem.c | 17 ------- lib/test/string.c | 34 ------------- lib/tst/allocator.hh | 22 +++++++++ lib/tst/linked_list_allocator.cc | 98 ++++++++++++++++++++++++++++++++++++++ lib/tst/mem.c | 17 +++++++ lib/tst/string.c | 34 +++++++++++++ 9 files changed, 257 insertions(+), 51 deletions(-) create mode 100644 lib/stdlib.h create mode 100644 lib/stdlib/linked_list_allocator.c delete mode 100644 lib/test/mem.c delete mode 100644 lib/test/string.c create mode 100644 lib/tst/allocator.hh create mode 100644 lib/tst/linked_list_allocator.cc create mode 100644 lib/tst/mem.c create mode 100644 lib/tst/string.c (limited to 'lib') 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 + +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 +#include + +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/test/mem.c b/lib/test/mem.c deleted file mode 100644 index bccb3a3..0000000 --- a/lib/test/mem.c +++ /dev/null @@ -1,17 +0,0 @@ -#include - -static const unsigned char data[] = {0xde, 0xca, 0xfa, 0xde}; -static unsigned char buffer[4]; - -void *memset(void *s, int c, long unsigned n); -void *memcpy(void *restrict dest, const void *restrict src, long unsigned n); - -int -main(void) -{ - memset(buffer, 0xae, sizeof(data)); - for (unsigned i = 0; i < sizeof(data); ++i) assert(buffer[i] == 0xae); - - memcpy(buffer, data, sizeof(data)); - for (unsigned i = 0; i < sizeof(data); ++i) assert(buffer[i] == data[i]); -} diff --git a/lib/test/string.c b/lib/test/string.c deleted file mode 100644 index 725d547..0000000 --- a/lib/test/string.c +++ /dev/null @@ -1,34 +0,0 @@ -#include "../string.h" -#include - -static const char *dec = "12341234"; -static const char *neg_dec = "-12341234"; -static const char *u32_hex = "decafade"; -static const char *i32_hex = "7fffffff"; -static char buffer[64]; - -int -main() -{ - { // utoa - char *r; - - r = utoa(buffer, 12341234u, 10); - for (unsigned i = 0; dec[i] != '\0'; ++i) assert(r[i] == dec[i]); - - r = utoa(buffer, 0xdecafade, 16); - for (unsigned i = 0; u32_hex[i] != '\0'; ++i) assert(r[i] == u32_hex[i]); - } - { // itoa - char *r; - - r = itoa(buffer, 12341234, 10); - for (unsigned i = 0; dec[i] != '\0'; ++i) assert(r[i] == dec[i]); - - r = itoa(buffer, -12341234, 10); - for (unsigned i = 0; neg_dec[i] != '\0'; ++i) assert(r[i] == neg_dec[i]); - - r = itoa(buffer, 0x7fffffff, 16); - for (unsigned i = 0; i32_hex[i] != '\0'; ++i) assert(r[i] == i32_hex[i]); - } -} 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 +#include +#include + +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(ptr0), + reinterpret_cast(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(ptr1), + reinterpret_cast(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/tst/mem.c b/lib/tst/mem.c new file mode 100644 index 0000000..bccb3a3 --- /dev/null +++ b/lib/tst/mem.c @@ -0,0 +1,17 @@ +#include + +static const unsigned char data[] = {0xde, 0xca, 0xfa, 0xde}; +static unsigned char buffer[4]; + +void *memset(void *s, int c, long unsigned n); +void *memcpy(void *restrict dest, const void *restrict src, long unsigned n); + +int +main(void) +{ + memset(buffer, 0xae, sizeof(data)); + for (unsigned i = 0; i < sizeof(data); ++i) assert(buffer[i] == 0xae); + + memcpy(buffer, data, sizeof(data)); + for (unsigned i = 0; i < sizeof(data); ++i) assert(buffer[i] == data[i]); +} diff --git a/lib/tst/string.c b/lib/tst/string.c new file mode 100644 index 0000000..725d547 --- /dev/null +++ b/lib/tst/string.c @@ -0,0 +1,34 @@ +#include "../string.h" +#include + +static const char *dec = "12341234"; +static const char *neg_dec = "-12341234"; +static const char *u32_hex = "decafade"; +static const char *i32_hex = "7fffffff"; +static char buffer[64]; + +int +main() +{ + { // utoa + char *r; + + r = utoa(buffer, 12341234u, 10); + for (unsigned i = 0; dec[i] != '\0'; ++i) assert(r[i] == dec[i]); + + r = utoa(buffer, 0xdecafade, 16); + for (unsigned i = 0; u32_hex[i] != '\0'; ++i) assert(r[i] == u32_hex[i]); + } + { // itoa + char *r; + + r = itoa(buffer, 12341234, 10); + for (unsigned i = 0; dec[i] != '\0'; ++i) assert(r[i] == dec[i]); + + r = itoa(buffer, -12341234, 10); + for (unsigned i = 0; neg_dec[i] != '\0'; ++i) assert(r[i] == neg_dec[i]); + + r = itoa(buffer, 0x7fffffff, 16); + for (unsigned i = 0; i32_hex[i] != '\0'; ++i) assert(r[i] == i32_hex[i]); + } +} -- cgit v1.2.1