first commit

1 files changed, 187 insertions, 0 deletions

diff --git a/lib/malloc/malloc.c b/lib/malloc/malloc.c
new file mode 100644
index 0000000..a0e9ebf
--- /dev/null
+++ b/lib/malloc/malloc.c
@@ -0,0 +1,187 @@
+#include "malloc.h"
+
+#include "../sys/brk.h"
+
+/** DOC
+ * @type typename
+ * @name segment_t
+ *
+ * @member void      *ptr
+ * @member u64       size
+ * @member u8        free
+ * @member segment_t *next
+ *
+ * @description
+ * A segment is a meta block for an allocated area.
+ * It contains the pointer `(void *ptr)` for the memory location
+ * its size and if its free `(u8 free)`. 
+ * The segment_t is a single linked list node because of that
+ * it also holds a `(segment_t *next)` pointer to the next segment.
+ */
+typedef struct __segment_t {
+	void                *ptr;
+	u64                 size;
+	u8                  free;
+	struct __segment_t  *next;
+} segment_t;
+
+
+/** DOC
+ * @type instance
+ * @name mbrk
+ *
+ * @member u64       initial
+ * @member u64       current
+ * @member segment_t *first
+ * @member segment_t *last
+ *
+ * @description
+ * The mbrk instance holds the current brk `(see [man 2 brk])`
+ * and the first and last element of the segement list.
+ */
+struct __break {
+	u64        initial;
+	u64        current;
+	segment_t  *first;
+	segment_t  *last;
+} mbrk = {
+	.initial = 0,
+	.current = 0,
+	.first = 0,
+	.last = 0
+};
+
+
+void  __initialize_memory();
+segment_t *__find_free_segment(u64 size);
+segment_t *__allocate_new(u64 size);
+
+
+/** DOC
+ * @type function
+ * @name malloc
+ *
+ * @param  u64 size
+ * @return void*
+ *
+ * @description
+ * Allocates memory. If there is no space left requests new space.
+ */
+void* malloc(u64 size)
+{
+	segment_t *seg;
+
+	if (!mbrk.initial)
+		__initialize_memory();
+	
+	seg = __find_free_segment(size);
+
+	if (!seg)
+		seg = __allocate_new(size);
+
+	seg->free = 0;
+	return seg->ptr;
+}
+
+
+/** DOC
+ * @type function
+ * @name free
+ *
+ * @param  void *ptr
+ * @return void
+ *
+ * @description
+ * Frees the memory allocated by `malloc`.
+ *
+ * ``IMPORTANT`` this function does not free the memory to be accessible
+ * for the whole system. The freed memory is only accessible for the current
+ * process and is released on exit.
+ */
+void free(void *ptr)
+{
+	segment_t * seg = mbrk.first;
+
+	for (; seg; seg = seg->next) {
+		if (ptr == seg->ptr) {
+			seg->free = 1;
+			break;
+		}
+	}
+}
+
+
+/** DOC
+ * @type function
+ * @name __initialize_memory
+ *
+ * @description
+ * Initalizes `mbrk` by calling `brk(0)`.
+ * Is only called if `mbrk.initial` is zero.
+ */
+void __initialize_memory()
+{
+	mbrk.initial = brk(0);
+	mbrk.current = mbrk.initial;
+}
+
+
+/** DOC
+ * @type function
+ * @name __find_free_segment
+ *
+ * @param  u64 size
+ * @return segment_t*
+ *
+ * @description
+ * Searches a segment with the given `size` in
+ * the segment linked-list.
+ * If there is no such segment it returns `0`
+ */
+segment_t *__find_free_segment(u64 size)
+{
+	segment_t * seg = mbrk.first;
+
+	for (; seg; seg = seg->next) {
+		if (seg->free && size == seg->size)
+			return seg;
+	}
+
+	return 0;
+}
+
+/** DOC
+ * @type function
+ * @name __allocate_new
+ *
+ * @param  u64 size
+ * @return segment_t*
+ *
+ * @description
+ * Allocates a new segement.
+ * This function is only called if no free segment with
+ * the given `size` was found. A new segment is allocated
+ * by using the `brk` syscall and adding `size + sizeof(segment_t)`
+ * new memory to the process.
+ */
+segment_t *__allocate_new(u64 size)
+{
+	u64 last = mbrk.current;
+	mbrk.current += size + sizeof(segment_t);
+	brk((void*)mbrk.current);
+
+	segment_t *seg = (segment_t*)last;
+	seg->ptr = (void*)(mbrk.current - size);
+	seg->size = size;
+	seg->free = 0;
+	seg->next = 0;
+
+	if (!mbrk.first)
+		mbrk.first = seg;
+	else
+		mbrk.last->next = seg;
+	
+	mbrk.last = seg;
+
+	return seg;
+}