summaryrefslogtreecommitdiff
path: root/src/user/knob/heap.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/user/knob/heap.c')
-rw-r--r--src/user/knob/heap.c217
1 files changed, 115 insertions, 102 deletions
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 <knob/format.h>
-
#include <pland/syscall.h>
-
+#include <pland/pcrt.h>
#include <stdbool.h>
#include <stdint.h>
-//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
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-21 15:23:16 +0000