summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorJon Santmyer <jon@jonsantmyer.com>2021-12-13 20:20:49 -0500
committerJon Santmyer <jon@jonsantmyer.com>2021-12-13 20:20:49 -0500
commitb337de3146f5c619514b05d6a7f4fde964a3663c (patch)
tree1b4c1973a4e3ae710352c63ca2f39efab0ca9825
parentc250be0fe2a7214431cfc5a41f8a12ad5a16209f (diff)
downloadmodit-slim-master.tar.gz
modit-slim-master.tar.bz2
modit-slim-master.zip
Kernel: Simplify src treeHEADmaster
-rw-r--r--.gitignore2
-rw-r--r--.gitmodules2
-rw-r--r--Makefile4
m---------kernel0
-rw-r--r--lib/c/stdlib/heap.c362
-rw-r--r--lib/c/stdlib/heap.h131
6 files changed, 358 insertions, 143 deletions
diff --git a/.gitignore b/.gitignore
index 2b21c41..851d4fa 100644
--- a/.gitignore
+++ b/.gitignore
@@ -10,5 +10,7 @@ bochsout.txt
*.iso
*.a
*.o
+.cache
initrd
root/usr/include/modit
+compile_commands.json
diff --git a/.gitmodules b/.gitmodules
index 5f1e6ad..48619cf 100644
--- a/.gitmodules
+++ b/.gitmodules
@@ -1,3 +1,3 @@
[submodule "kernel"]
path = kernel
- url = git@git.jonsantmyer.com:modit-kernel
+ url = git@git.jonsantmyer.com:modit-kernel
diff --git a/Makefile b/Makefile
index fbfa6a9..0111afc 100644
--- a/Makefile
+++ b/Makefile
@@ -33,11 +33,7 @@ clean:
kernel: tools/$(ARCH)_$(BITS) Makefile
$(MAKE) -C kernel ARCH=$(ARCH) BITS=$(BITS) CC=$(CC) LD=$(LD) AS=$(AS) AR=$(AR) MODORDER="$(shell cat $(PWD)/modorder)" LOGLEVEL=$(LOGLEVEL)
mv kernel/kernel.elf root/boot/
- mkdir -p $(PWD)/root/usr/include/modit
mkdir -p $(PWD)/initrd/boot
- cp kernel/include/arch_$(ARCH)/$(BITS)/* root/usr/include/modit/
- cp kernel/include/arch_$(ARCH)/common/* root/usr/include/modit/
- cp kernel/include/arch_common/* root/usr/include/modit/
.PHONY: initrd
initrd: tools/$(ARCH)_$(BITS) apps Makefile
diff --git a/kernel b/kernel
-Subproject 63a5f312b06143951a49faad190d1ab2fd37fcc
+Subproject 24f2cb11c07eaa572cae6f24457699a7ac932f2
diff --git a/lib/c/stdlib/heap.c b/lib/c/stdlib/heap.c
index 54b8db6..8050144 100644
--- a/lib/c/stdlib/heap.c
+++ b/lib/c/stdlib/heap.c
@@ -1,174 +1,275 @@
+#include "heap.h"
#include <stdlib.h>
-#include "sys/mem.h"
-#include "sys/lock.h"
+#include <string.h>
-#include <stdint.h>
+struct heap stdlib_heap;
-struct bucket {
- struct bucket *prev;
- struct bucket *next;
- uintptr_t addr;
- size_t flags;
-};
+uintptr_t __pbrk;
+extern uintptr_t _end[];
-#define BUCKET_SIZE sizeof(struct bucket)
-#define BLOCK_SIZE 4096
-#define BLOCK_BUCKETS ((BLOCK_SIZE - sizeof(uintptr_t)) / BUCKET_SIZE)
+void
+__heap_expand(size_t by)
+{
+ alloc(__pbrk, by + 0x1000);
+ __pbrk += by;
+}
-struct block {
- struct block *next;
- struct bucket buckets[BLOCK_BUCKETS];
-};
+int
+__heap_create(struct heap *heap)
+{
+ struct crate *firstcrate = NULL;
+ struct bucket *cratebucket = NULL;
-static struct block *block_tail = NULL;
-static struct block *block_head = NULL;
+ memset(heap, 0, sizeof(struct heap));
+
+ heap->start = __pbrk;
+ heap->size = 0x40000000;
-static struct bucket *bucket_tail = NULL;
-static struct bucket *bucket_head = NULL;
+ /*Populate first crate*/
+ heap->crates_tail = heap->crates_head = firstcrate = (struct crate*)__pbrk;
+ cratebucket = &firstcrate->buckets[0];
-static struct bucket *free_tail = NULL;
+ heap->used = HEAP_CRATE_SIZE;
+ __heap_expand(HEAP_CRATE_SIZE);
-static uintptr_t heapend;
-static mutex_t heap_lock;
+ memset(firstcrate, 0, HEAP_CRATE_SIZE);
-uintptr_t __pbrk;
+ /*Allocate first bucket for crate*/
+ heap->buckets_tail = heap->buckets_head = cratebucket;
+ cratebucket->address = (uintptr_t)firstcrate;
+ cratebucket->sizetaken = HEAP_CRATE_SIZE | 1;
-extern uintptr_t _end[];
+ /*Set buckets after 1 to link to free list*/
+ for(size_t i = 2; i < HEAP_CRATE_BUCKETS; i++) {
+ struct bucket *prev = &firstcrate->buckets[i - 1];
+ struct bucket *bucket = &firstcrate->buckets[i];
-static void
-growbrk(size_t by)
-{
- //Round to nearest granularity address
- uintptr_t exp = (by + (HEAP_BUCKET_ALLOC_GRANULARITY - 1) / HEAP_BUCKET_ALLOC_GRANULARITY) * HEAP_BUCKET_ALLOC_GRANULARITY;
- alloc(__pbrk, exp);
- __pbrk += exp;
+ prev->next = bucket;
+ bucket->prev = prev;
+ }
+ heap->buckets_unused_tail = &firstcrate->buckets[1];
+
+ return 0;
}
-static void
-growto(uintptr_t addr)
+struct bucket*
+__heap_bucket_findbest(struct heap *heap, size_t size)
{
- if(addr > __pbrk) growbrk(addr - __pbrk);
- heapend = addr;
+ struct bucket *best = NULL;
+ for(struct bucket *bucket = heap->buckets_tail;
+ bucket != NULL;
+ bucket = bucket->next)
+ {
+ if(HEAP_BUCKET_TAKEN(bucket)) continue;
+ if(bucket->sizetaken < size) continue;
+ if(best == NULL) best = bucket;
+ if(best->sizetaken > bucket->sizetaken) best = bucket;
+ }
+
+ return best;
}
-static void
-growby(size_t by)
+struct bucket*
+__heap_crate_create(struct heap *heap)
{
- growto(heapend + by);
+ size_t remaining = heap->size - heap->used;
+ struct bucket *crate_bucket = NULL;
+ struct crate *crate = NULL;
+
+ /*Check for room in heap*/
+ if(remaining < HEAP_CRATE_SIZE) {
+ return NULL;
+ }
+
+ /*Take crate bucket from crate head*/
+ crate_bucket = &heap->crates_head->reserved;
+
+ /*Populate crate bucket*/
+ crate_bucket->address = heap->start + heap->used;
+ crate_bucket->sizetaken = HEAP_CRATE_SIZE | 1;
+ crate_bucket->prev = heap->buckets_head;
+ heap->buckets_head = crate_bucket;
+
+ /*Populate crate, linking buckets together*/
+ crate = (struct crate*)crate_bucket->address;
+
+ __heap_expand(HEAP_CRATE_SIZE);
+ memset(crate, 0, HEAP_CRATE_SIZE);
+
+ for(size_t i = 0; i < HEAP_CRATE_BUCKETS; i++) {
+ struct bucket *bucket = &crate->buckets[i];
+ struct bucket *prev = &crate->buckets[i-1];
+
+ bucket->prev = prev;
+ prev->next = bucket;
+ }
+
+ /*Set unused tail to first bucket*/
+ heap->buckets_unused_tail = &crate->buckets[0];
+
+ /*Add crate to crate list*/
+ heap->crates_head->next = crate;
+ heap->crates_head = crate;
+
+ /*Add used memory to heap info*/
+ heap->used += HEAP_CRATE_SIZE;
+
+ return heap->buckets_unused_tail;
}
-static void
-heap_allocbucket(struct bucket *bucket, size_t size)
+struct bucket*
+__heap_bucket_append(struct heap *heap, struct bucket *bucket, size_t size)
{
- bucket->addr = heapend;
- bucket->flags = size;
- growby(size);
-
- //Add bucket to bucket list
- if(bucket_head != NULL) {
- bucket_head->next = bucket;
- bucket->prev = bucket_head;
+ /*Get free bucket from crate*/
+ struct bucket *free = heap->buckets_unused_tail;
+ if(free == NULL) {
+ free = __heap_crate_create(heap);
+ if(free == NULL) return NULL;
}
- bucket->next = NULL;
- bucket_head = bucket;
+ heap->buckets_unused_tail = heap->buckets_unused_tail->next;
+
+ /*Append free to bucket chain*/
+ free->prev = bucket;
+ free->next = bucket->next;
+ if(free->next != NULL) free->next->prev = free;
+ bucket->next = free;
+
+ /*Mark up to head used memory*/
+ if(free->next == NULL) {
+ heap->used += size;
+ __heap_expand(size);
+ heap->buckets_head = free;
+ }
+
+ /*Populate free bucket*/
+ free->address = bucket->address + bucket->sizetaken;
+ free->sizetaken = size;
+
+ return free;
}
-static void
-heap_allocblock(struct bucket *bucket)
+void
+__heap_bucket_release(struct heap *heap, struct bucket *bucket)
{
- //Set bucket addr to heapend, expand heap to match
- heap_allocbucket(bucket, BLOCK_SIZE);
- bucket->flags |= 1;
-
- //Add block to blocklist
- block_head->next = (struct block*)bucket->addr;
- block_head = (struct block*)bucket->addr;
-
- //Add buckets to freelist
- for(size_t i = 0; i < BLOCK_BUCKETS - 1; i++) {
- block_head->buckets[i].next = &block_head->buckets[i+1];
- block_head->buckets[i+1].prev = &block_head->buckets[i];
+ /*Disconnect bucket from main chain*/
+ if(bucket->prev != NULL) {
+ bucket->prev->next = bucket->next;
+ }else{
+ heap->buckets_tail = bucket->next;
+ }
+
+ if(bucket->next != NULL) {
+ bucket->next->prev = bucket->prev;
+ }else{
+ heap->buckets_head = bucket->prev;
}
- free_tail = &block_head->buckets[0];
+
+ /*Attach bucket to unused list*/
+ bucket->next = heap->buckets_unused_tail;
+ bucket->prev = NULL;
+
+ heap->buckets_unused_tail = bucket;
}
-static struct bucket*
-heap_takebucket(void)
+void
+__heap_bucket_split(struct heap *heap, struct bucket *bucket, size_t size)
{
- //Get free bucket
- struct bucket *taken = free_tail;
-
- //Check if bucket is last in freelist, so there is always room for a new block
- if(taken->next == NULL) {
- //Allocate new block with free bucket
- heap_allocblock(taken);
- }
+ /*Check if split is required*/
+ intmax_t diff = bucket->sizetaken - size;
+ if(diff <= 0) return;
- free_tail = taken->next;
- free_tail->prev = NULL;
+ /*Shrink bucket to required size*/
+ bucket->sizetaken = size;
-
- return taken;
+ /*Create new bucket with remainder*/
+ __heap_bucket_append(heap, bucket, diff);
}
-static struct bucket*
-heap_search(size_t size)
+void
+__heap_bucket_merge(struct heap *heap, struct bucket *bucket)
{
- struct bucket *best = NULL;
- //Search through all allocated heap buckets
- for(struct bucket *bucket = bucket_tail; bucket; bucket = bucket->next) {
- if(bucket->flags & 1) continue; //Skip taken
- if(bucket->flags < size) continue; //Skip too small
- if(best == NULL) { //First best is the first that fits
- best = bucket;
- }else if(best->flags > bucket->flags) best = bucket; //Total best is the smallest fit
+ struct bucket *prev = bucket->prev;
+ struct bucket *next = bucket->next;
+
+ /*Merge bucket with prev*/
+ if(prev != NULL) {
+ if(!HEAP_BUCKET_TAKEN(prev)) {
+ prev->sizetaken += bucket->sizetaken;
+ __heap_bucket_release(heap, bucket);
+ __heap_bucket_merge(heap, prev);
+ return;
+ }
+ }
+ /*Merge bucket with next*/
+ if(next != NULL) {
+ if(!HEAP_BUCKET_TAKEN(next)) {
+ bucket->sizetaken += next->sizetaken;
+ __heap_bucket_release(heap, next);
+ __heap_bucket_merge(heap, bucket);
+ }
}
- return best;
}
void*
-malloc(size_t size)
+__heap_alloc(struct heap *heap, size_t size)
{
+ struct bucket *bestfit = NULL;
+ size_t remaining = heap->size - heap->used;
if(size == 0) return NULL;
- mutex_take(&heap_lock);
- size += (size % 2);
-
- //Search blocks for empty buckets matching size
- struct bucket *bucket = heap_search(size);
-
- //Resize top if none matching
- if(bucket == NULL) {
- if(!(bucket_head->flags & 1)) {
- bucket = bucket_head;
- bucket->flags = size;
+ /*Check for room in heap*/
+ if(remaining < size) return NULL;
+
+ /*Resize to fit with granularity*/
+ size = ((size + (HEAP_ALLOC_GRAN - 1)) / HEAP_ALLOC_GRAN) * HEAP_ALLOC_GRAN;
+
+ bestfit = __heap_bucket_findbest(heap, size);
+ if(bestfit == NULL) {
+ if(!HEAP_BUCKET_TAKEN(heap->buckets_head)) {
+ /*Expand empty head to fit*/
+ heap->buckets_head->sizetaken = size;
+ bestfit = heap->buckets_head;
}else{
- //Allocate bucket if no valid target
- bucket = heap_takebucket();
- heap_allocbucket(bucket, size);
+ /*Append new bucket to list*/
+ bestfit = __heap_bucket_append(heap, heap->buckets_head, size);
}
+ if(bestfit == NULL) return NULL; /*Heap ran out of space*/
}
-
- //Claim bucket
- bucket->flags |= 1;
- mutex_leave(&heap_lock);
- return (void*)bucket->addr;
+
+ /*Split bucket into perfectly sized piece*/
+ __heap_bucket_split(heap, bestfit, size);
+
+ bestfit->sizetaken |= 1;
+ return (void*)bestfit->address;
}
-void
-free(void *ptr)
+int
+__heap_free(struct heap *heap, void *ptr)
{
- if(ptr == NULL) return;
- mutex_take(&heap_lock);
- //Search blocklist for address at token
- for(struct bucket *bucket = bucket_tail; bucket; bucket = bucket->next) {
- if(bucket->addr == (uintptr_t)ptr) {
- bucket->flags &= (~1);
- mutex_leave(&heap_lock);
- return;
+ uintptr_t addr = (uintptr_t)ptr;
+ for(struct bucket *bucket = heap->buckets_tail;
+ bucket != NULL;
+ bucket = bucket->next)
+ {
+ if(bucket->address == addr) {
+ bucket->sizetaken &= ~1;
+ __heap_bucket_merge(heap, bucket);
+ return 0;
}
}
- mutex_leave(&heap_lock);
+ return -1;
+}
+
+void*
+malloc(size_t size)
+{
+ return __heap_alloc(&stdlib_heap, size);
+}
+
+void
+free(void *ptr)
+{
+ __heap_free(&stdlib_heap, ptr);
}
void
@@ -177,21 +278,6 @@ __stdlib_heap_init(void)
//Match pbrk to page boundary (so it's cleaner for granularity sake)
__pbrk = (uintptr_t)_end;
__pbrk = ((__pbrk + 0xFFF) / 0x1000) * 0x1000;
- heapend = __pbrk;
-
- block_head = block_tail = (struct block*)heapend;
- growby(BLOCK_SIZE);
- memset(block_tail, 0, BLOCK_SIZE);
-
- //Link block buckets in freelist
- for(size_t i = 1; i < BLOCK_BUCKETS - 1; i++) {
- block_head->buckets[i].next = &block_head->buckets[i+1];
- block_head->buckets[i+1].prev = &block_head->buckets[i];
- }
- free_tail = &block_head->buckets[1];
- //Set bucket 1 to root block
- block_head->buckets[0].addr = (uintptr_t)block_head;
- block_head->buckets[0].flags = BLOCK_SIZE | 1;
- bucket_head = bucket_tail = &(block_head->buckets[0]);
+ __heap_create(&stdlib_heap);
}
diff --git a/lib/c/stdlib/heap.h b/lib/c/stdlib/heap.h
new file mode 100644
index 0000000..f51ffe5
--- /dev/null
+++ b/lib/c/stdlib/heap.h
@@ -0,0 +1,131 @@
+/**
+ * heap.h
+ * Copyright (c) 2021 Jon Santmyer <jon@jonsantmyer.com>
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+
+/**
+ * File : heap.h
+ * Author : Jon Santmyer <jon@jonsantmyer.com>
+ * Date : 10.12.2021
+ *
+ * A simple thread-unsafe double linked-list bucket heap allocator.
+ * Written for moderately fast variable size object allocations without
+ * external memory regions
+ * Heap object is expected to be allocated by the system
+ * Heap members (lists, buckets, crates) are stored in the heap memory region.
+ * Users are expected to write wrapper functions that handles errors and
+ * provides a locking mechanism for threaded applications.
+ *
+ * Required functions and headers:
+ * stdint.h
+ * uintptr_t, uintmax_t
+ * stddef.h
+ * size_t
+ * string.h
+ * memset
+ *
+ * Lists are defined by the elements they contain: they are named thusly.
+ * The first element of the list is suffixed by _tail
+ * The last element of the list is suffixed by _head
+ *
+ * Crates are page-sized bucket containers allocated inside of heap memory
+ * designed to allow the heap to dynamically create and destroy buckets.
+ * The amount of buckets each crate can hold depends on the preset size defined
+ * in HEAP_CRATE_SIZE, calculated in HEAP_CRATE_BUCKETS.
+ * Crates are stored in the previous crate's reserved bucket, except for the
+ * initial crate, which stores itself.
+ * Crates are singly linked, with the head and tail stored in the heap
+ * data structure.
+ *
+ * Buckets hold information about which memory region it represents, it's
+ * neighbors, and if it's been taken by an allocation.
+ * Buckets determine if they are taken by setting the first bit in the
+ * sizetaken field. 0 represents free, 1 represents taken.
+ * Buckets currently in-use by the heap are stored in the general
+ * buckets list, with buckets reserved for future allocations stored in
+ * the buckets_unused list.
+ *
+ * The heap datatype stores information about where allocations can take
+ * place, the buckets allocated, a list of crates, and a list of
+ * unused buckets.
+ * Unused buckets are taken when a bucket is split into two, or a bucket needs
+ * to be appended to the heap.
+ *
+ * When buckets assigned to an allocation are bigger than the needed size, the
+ * bucket is "split". the difference in sizes are stored, the bucket is
+ * resized to the requested size, and a new bucket is appended to the old
+ * bucket with the difference as it's size.
+ * When a bucket is freed, the bucket checks it's neighbors to see if it can be
+ * combined. If two adjacent buckets are not taken, they are "merged".
+ * both buckets' sizes are added into the left-most bucket, and the right-most
+ * bucket is released into the unused list.
+ * These actions are made to ensure that memory allocations are as compact
+ * as possible.
+ *
+ * When the unused list is empty and a bucket needs to be appended, the heap
+ * calls for a new crate to be created. The new crate occupies the reserved
+ * bucket of the head crate, and the bucket is pointed to the last address
+ * in the bucket list. The crates' buckets are initialized to link with
+ * eachother and are set as the head of the unused list.
+ */
+#ifndef JSH_HEAP_H
+#define JSH_HEAP_H 1
+
+#include <stdint.h>
+#include <stddef.h>
+
+//I want the crate to be loaded into the l1 cache
+#define HEAP_CRATE_SIZE 4096
+#define HEAP_BUCKET_SIZE sizeof(struct bucket)
+#define HEAP_CRATE_BUCKETS (((HEAP_CRATE_SIZE - sizeof(uintptr_t)) / HEAP_BUCKET_SIZE) - 1)
+
+#define HEAP_BUCKET_TAKEN(b) (b->sizetaken & 1)
+#define HEAP_ALLOC_GRAN sizeof(uintptr_t)
+
+struct bucket
+{
+ uintptr_t address;
+ uintmax_t sizetaken;
+ struct bucket *prev;
+ struct bucket *next;
+};
+
+struct crate
+{
+ struct bucket buckets[HEAP_CRATE_BUCKETS];
+ struct bucket reserved;
+ struct crate *next;
+};
+
+struct heap
+{
+ uintptr_t start;
+ size_t size;
+ size_t used;
+
+ struct crate *crates_tail;
+ struct crate *crates_head;
+ struct bucket *buckets_tail;
+ struct bucket *buckets_head;
+ struct bucket *buckets_unused_tail;
+};
+
+#endif