From f57e2eabe0a10c9732c83532e01654a499fb8dcf Mon Sep 17 00:00:00 2001 From: Benji Dial Date: Mon, 21 Jun 2021 17:47:13 -0400 Subject: many, many changes; settings is broken --- src/user/knob/heap.c | 217 +++++++++++++++++++++++++++------------------------ 1 file changed, 115 insertions(+), 102 deletions(-) (limited to 'src/user/knob/heap.c') diff --git a/src/user/knob/heap.c b/src/user/knob/heap.c index 6e57000..c4b810e 100644 --- a/src/user/knob/heap.c +++ b/src/user/knob/heap.c @@ -1,128 +1,141 @@ -#include - #include - +#include #include #include -//structure appears at the start of each block -struct block_header { - struct block_header *next; - struct block_header *prev; +#define MIN_NEW_CHUNK_PAGES 16 - //does not include header - uint32_t length; - bool allocated; +struct desc_page_head { + void *next_page;//0 for last one }; -static struct block_header *first_block = 0; +struct chunk_desc { + void *start;//0 for a desc not in use + uint32_t length; + bool available; +} __attribute__ ((packed)); +//without packing, it is 12 bytes and we get 341 per page +//with packing, it is 9 bytes and we get 454 per page +//maybe i should make available just the top bit of length +//then we get 511 per page, but length has a max of 2^31-1 + +static struct desc_page_head *first_desc_page = 0; +static struct desc_page_head *last_desc_page = 0; + +#define DESCS_PER_PAGE ((4096 - sizeof(struct desc_page_head)) / sizeof(struct chunk_desc)) +#define PAGE_AS_ARRAY(p) ((struct chunk_desc *)((void *)p + sizeof(struct desc_page_head))) + +static char size_was_buf[] = "size was ......... kB"; +//kb should be < 1 000 000 000 +static void log_size_was(uint32_t kb) { + for (int8_t d = 9; d != -1; --d) { + size_was_buf[9 + d] = (kb % 10) + '0'; + kb /= 10; + } + _system_log(size_was_buf); +} -static void add_header(struct block_header *bh) { - bh->next = first_block; - bh->prev = 0; - if (first_block) - first_block->prev = bh; - first_block = bh; +static const char *const hextab = "0123456789abcdef"; +static char caller_was_buf[] = "return address is 0x........"; +static void log_caller_was(void *addr) { + const uint32_t as_int = (uint32_t)addr; + for (uint8_t i = 0; i < 8; ++i) + caller_was_buf[27 - i] = hextab[(as_int >> (4 * i)) & 0xf]; + _system_log(caller_was_buf); } -//static const char *const hextab = "0123456789abcdef"; -//static char *const get_debug = "getting 0x........ byte block"; -//static char *const free_debug = "freeing 0x........ byte block"; +static struct desc_page_head *new_desc_page() { + struct desc_page_head *dph = _allocate_ram(1); + if (!dph) { + _system_log("knob heap could not allocate new descriptor page"); + log_size_was(4); + __pcrt_quit(); + } + dph->next_page = 0; + if (last_desc_page) + last_desc_page->next_page = dph; + last_desc_page = dph; + + struct chunk_desc *const a = PAGE_AS_ARRAY(dph); + for (uint32_t i = 0; i < DESCS_PER_PAGE; ++i) + a[i].start = 0; -__attribute__ ((malloc)) -void *get_block(uint32_t bytes) { - if (!bytes) - return 0; -//for (uint8_t i = 0; i < 8; ++i) -// get_debug[10 + 7 - i] = hextab[(bytes >> (i * 4)) & 0xf]; -//_system_log(get_debug); - - struct block_header *header = 0; - for (struct block_header *ptr = first_block; ptr; ptr = ptr->next) { - if (ptr->allocated) - continue; - if (ptr->length == bytes) { - header = ptr; - break; - } - if (ptr->length > bytes + sizeof(struct block_header)) { - struct block_header *bh = (void *)ptr + sizeof(struct block_header) + bytes; + return dph; +} + +static struct chunk_desc *unused_desc() { + for (struct desc_page_head *i = first_desc_page; i; i = i->next_page) { + struct chunk_desc *const a = PAGE_AS_ARRAY(i); + for (uint32_t i = 0; i < DESCS_PER_PAGE; ++i) + if (!a[i].start) + return a + i; + } - bh->length = ptr->length - sizeof(struct block_header) - bytes; - bh->allocated = false; - add_header(bh); + return PAGE_AS_ARRAY(new_desc_page()); +} - ptr->length = bytes; - header = ptr; - break; +__attribute__ ((malloc)) +void *get_block(uint32_t bytes) { + if (!first_desc_page) + first_desc_page = new_desc_page(); + + struct chunk_desc *best_fit = 0; + + for (struct desc_page_head *i = first_desc_page; i; i = i->next_page) { + struct chunk_desc *const a = PAGE_AS_ARRAY(i); + for (uint32_t i = 0; i < DESCS_PER_PAGE; ++i) { + if (!a[i].start || !a[i].available || (a[i].length < bytes)) + continue; + if (a[i].length == bytes) { + a[i].available = false; + return a[i].start; + } + if (!best_fit || (a[i].length < best_fit->length)) + best_fit = a + i; } } - if (!header) { - uint32_t size_with_header = bytes + sizeof(struct block_header); - if (!(size_with_header % 4096)) { - header = _allocate_ram(size_with_header / 4096); - if (!header) - return 0; - header->length = bytes; - add_header(header); + if (!best_fit) { + const uint32_t pages_needed = (bytes - 1) / 4096 + 1; + const uint32_t allocating = pages_needed < MIN_NEW_CHUNK_PAGES ? MIN_NEW_CHUNK_PAGES : pages_needed; + void *const new_chunk = _allocate_ram(allocating); + if (!new_chunk) { + _system_log("knob heap could not allocate new chunk"); + log_size_was(allocating * 4); + log_caller_was(__builtin_return_address(0)); + __pcrt_quit(); } - else { - uint32_t pages = (bytes + sizeof(struct block_header) * 2) / 4096 + 1; - header = _allocate_ram(pages); - if (!header) - return 0; - header->length = bytes; - add_header(header); - - struct block_header *bh = (void *)header + sizeof(struct block_header) + bytes; - bh->length = pages * 4096 - bytes - 2 * sizeof(struct block_header); - bh->allocated = false; - add_header(bh); + best_fit = unused_desc(); + best_fit->start = new_chunk; + best_fit->length = allocating * 4096; + + if (bytes == allocating * 4096) { + best_fit->available = false; + return new_chunk; } } - header->allocated = true; - return (void *)header + sizeof(struct block_header); -} - -static void remove_header(struct block_header *bh) { - if (bh == first_block) - first_block = bh->next; - if (bh->prev) - bh->prev->next = bh->next; - if (bh->next) - bh->next->prev = bh->prev; -} + void *const old_end = best_fit->start + best_fit->length; + void *const new_end = best_fit->start + bytes; -void free_block(void *block) { - struct block_header *header = block - sizeof(struct block_header); + best_fit->length = bytes; + best_fit->available = false; -//for (uint8_t i = 0; i < 8; ++i) -// free_debug[10 + 7 - i] = hextab[(header->length >> (i * 4)) & 0xf]; -//_system_log(free_debug); + struct chunk_desc *const leftover = unused_desc(); + leftover->start = new_end; + leftover->length = old_end - new_end; - header->allocated = false; + return best_fit->start; +} - void *after = block + header->length; - for (struct block_header *ptr = first_block; ptr; ptr = ptr->next) { - if (ptr == after) { - if (!ptr->allocated) { - header->length += ptr->length + sizeof(struct block_header); - remove_header(ptr); +void free_block(const void *block) { + for (struct desc_page_head *i = first_desc_page; i; i = i->next_page) { + struct chunk_desc *const a = PAGE_AS_ARRAY(i); + for (uint32_t i = 0; i < DESCS_PER_PAGE; ++i) + if (a[i].start == block) { + //TODO: consolidate this with surrounding free chunks + a[i].available = true; + return; } - break; - } } - - //we traverse the linked list twice. it would probably be more efficient - //to do both finding the after and finding the before in the same loop. - for (struct block_header *ptr = first_block; ptr; ptr = ptr->next) - if ((void *)ptr + sizeof(struct block_header) + ptr->length == header) { - if (!ptr->allocated) { - ptr->length += sizeof(struct block_header) + header->length; - remove_header(header); - } - break; - } -} \ No newline at end of file +} -- cgit v1.2.3