Implemented the Algorithms necessary, but
the functions don't work yet.
Signed-off-by: Kevin Trogant <greenfoxlight.42@xxxxxxxxx>
---
kernel/core/include/heap.h | 5 ++
kernel/core/src/heap/malloc.c | 157 ++++++++++++++++++++++++++++++++++++++++++
kernel/core/src/main.c | 18 +++++
3 files changed, 180 insertions(+)
create mode 100644 kernel/core/src/heap/malloc.c
diff --git a/kernel/core/include/heap.h b/kernel/core/include/heap.h
index 1a861c9..2b63a74 100644
--- a/kernel/core/include/heap.h
+++ b/kernel/core/include/heap.h
@@ -39,4 +39,9 @@ void* sbrk(intptr_t increment);
*/
void* malloc(size_t size);
+/** \brief free a previously allocated region on the heap.
+ * \param ptr pointer to the region on the heap.
+ */
+void free(void* ptr);
+
#endif
diff --git a/kernel/core/src/heap/malloc.c b/kernel/core/src/heap/malloc.c
new file mode 100644
index 0000000..f7e2927
--- /dev/null
+++ b/kernel/core/src/heap/malloc.c
@@ -0,0 +1,157 @@
+/** \file malloc.c
+ * \brief kernel malloc function
+ *
+ * Created: 04.07.2015 14:47:11
+ * by: Kevin Trogant (kt), greenfoxlight.42@xxxxxxxxx
+ */
+
+#include <stdint.h>
+#include <stddef.h>
+
+#include <heap.h>
+
+#define M_HDR_FREE 0
+#define M_HDR_USED 1
+
+#define SPLIT_LEFTOVER 8
+
+struct m_hdr {
+ uintptr_t start;
+ size_t size;
+ uint8_t free;
+ struct m_hdr* next;
+ struct m_hdr* prev;
+};
+
+struct m_hdr* __anchor = NULL;
+
+/* append a new header to the list of
+ * existing headers
+ */
+void __append_hdr(struct m_hdr* new) {
+ struct m_hdr* hdr = __anchor;
+ if (hdr == NULL) {
+ __anchor = new;
+ __anchor->next = NULL;
+ __anchor->prev = NULL;
+ return;
+ }
+ /* find last header */
+ while (hdr->next != NULL) {
+ hdr = __anchor->next;
+ }
+ hdr->next = new;
+ new->prev = hdr;
+ new->next = NULL;
+}
+
+/* join 2 reagions together,
+ * does _not_ check if both reside
+ * beside each other
+ */
+void __coalesce(struct m_hdr* a, struct m_hdr* b) {
+ a->size += b->size + sizeof(struct m_hdr);
+ a->next = b->next;
+}
+
+void __coalesce_free_spaces(void) {
+ struct m_hdr* space = __anchor;
+ while (space->next != NULL) {
+ if ((space->free == M_HDR_FREE) &&
+ (space->next->free == M_HDR_FREE)) {
+ __coalesce(space, space->next);
+ if (space->next == NULL) {
+ break;
+ }
+ }
+ space = space->next;
+ }
+}
+
+/* Search for an free region
+ * containing at least "s" bytes.
+ * Returns best fit
+ */
+struct m_hdr* __find_space(size_t s) {
+ struct m_hdr* min = NULL;
+ struct m_hdr* hdr = __anchor;
+ int found = 0;
+ while (hdr != NULL) {
+ if (hdr->free == M_HDR_USED) {
+ hdr = hdr->next;
+ continue;
+ }
+ if (hdr->size > s) {
+ found = 1;
+ if (min == NULL) {
+ min = hdr;
+ } else if (min->size > hdr->size) {
+ min = hdr;
+ }
+ } else if (hdr->size == s) {
+ found = 1;
+ min = hdr;
+ break;
+ }
+ hdr = hdr->next;
+ }
+ if (found == 0) {
+ return NULL;
+ }
+ return min;
+}
+
+struct m_hdr* __increase_heap(size_t s) {
+ struct m_hdr* new = sbrk(sizeof(struct m_hdr) + s);
+ new->size = s;
+ new->free = M_HDR_FREE;
+ new->start = (uintptr_t)new + sizeof(struct m_hdr);
+ return new;
+}
+
+/* splits "space" into 2 parts,
+ * if enough space is left-over after allocating "needed"
+ * bytes on space.
+ */
+void __split_space(struct m_hdr* space, size_t needed) {
+ struct m_hdr* new = NULL;
+ if ((space->size - needed) >= (sizeof(struct m_hdr) + SPLIT_LEFTOVER)) {
+ new = (struct m_hdr*)((uintptr_t)space + sizeof(struct m_hdr) +
needed);
+ new->prev = space;
+ space->next = new;
+ new->next = space->next;
+ new->free = M_HDR_FREE;
+ }
+}
+
+void* malloc(size_t size) {
+ struct m_hdr* new = __find_space(size);
+ if (new == NULL) {
+ new = __increase_heap(size);
+ if (new == NULL) {
+ return NULL;
+ }
+ new->free = M_HDR_USED;
+ __append_hdr(new);
+ } else {
+ new->free = M_HDR_USED;
+ __split_space(new, size);
+ }
+ return (void*)(new->start);
+}
+
+void free(void* ptr) {
+ struct m_hdr* space = __anchor;
+ uintptr_t addr = (uintptr_t)ptr;
+ if (space == NULL) {
+ return;
+ }
+ while (space->next != NULL) {
+ if ((space->start <= addr) && ((space->start + space->size) >
addr)) {
+ space->free = M_HDR_FREE;
+ break;
+ }
+ space = space->next;
+ }
+ __coalesce_free_spaces();
+}
diff --git a/kernel/core/src/main.c b/kernel/core/src/main.c
index 0a7c425..062e27b 100644
--- a/kernel/core/src/main.c
+++ b/kernel/core/src/main.c
@@ -17,10 +17,28 @@
void core_main(struct boot_core_transition* transition) {
int* a = NULL;
+ int* b = NULL;
kprintf("[core] Initializing physical memory manager...\t");
if (phys_init(transition->memory_map) != 0) {
kprintf("Failed.\n");
return;
}
kprintf("Done.\n");
+ a = malloc(sizeof(int));
+ kprintf("Allocated 0x%x...", (uint32_t)a);
+ kprintf("Done.\n");
+ kprintf("Writing... ");
+ *a = 5;
+ kprintf("Done.\n");
+ b = malloc(sizeof(int));
+ kprintf("Allocated 0x%x...", (uint32_t)b);
+ kprintf("Done.\n");
+ kprintf("Freeing 0x%x\n", (uint32_t)b);
+ free(b);
+ kprintf("Freeing 0x%x\n", (uint32_t)a);
+ free(a);
+ a = malloc(sizeof(int) * 2);
+ kprintf("Allocated 0x%x...", (uint32_t)a);
+ free(a);
+ kprintf("Done.\n");
}
--
2.4.5
