**diff options**

-rw-r--r-- | .gitignore | 2 | ||||

-rw-r--r-- | .gitmodules | 2 | ||||

-rw-r--r-- | Makefile | 4 | ||||

m--------- | kernel | 0 | ||||

-rw-r--r-- | lib/c/stdlib/heap.c | 362 | ||||

-rw-r--r-- | lib/c/stdlib/heap.h | 131 |

6 files changed, 358 insertions, 143 deletions

@@ -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 @@ -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 |