+/rtos
git clone https://git.julia.blue/+/rtos
021d2d4
master
1#include "heap.h" 2#include "OS.h" 3#include "interpreter.h" 4#include "io.h" 5#include "printf.h" 6#include "std.h" 7#include <stdint.h> 8 9const uint32_t MIN_ALLOCATION = 4 ; 10 11extern uint32_t _heap ; 12extern uint32_t _eheap ; 13 14static HeapNode * head ; 15static Sema4 heap_mutex ; 16 17static uint16_t total_heap_size ; 18static uint16_t free_space ; 19static uint16_t used_space ; 20 21void heap_init (void ) { 22total_heap_size = (uint32_t )& _eheap - (uint32_t )& _heap ; 23free_space = total_heap_size - sizeof (HeapNode ); 24used_space = 0 ; 25head = (HeapNode * )& _heap ; 26* head = (HeapNode ){0 ,free_space }; 27OS_InitSemaphore (& heap_mutex ,0 ); 28} 29 30HeapNode * heap_node_from_alloc (void * alloc ) { 31return (HeapNode * )((uint8_t * )alloc - sizeof (HeapNode )); 32} 33 34static HeapNode * heap_next_node (HeapNode * current ) { 35return (HeapNode * )((uint8_t * )current + current -> size + sizeof (HeapNode )); 36} 37 38static bool try_splitting_block (HeapNode * node ,uint32_t size ) { 39if (node -> size < size + sizeof (HeapNode )+ MIN_ALLOCATION ) { 40return false; 41 } 42HeapNode * new = (HeapNode * )(((uint8_t * )node )+ sizeof (HeapNode )+ 43max (size ,MIN_ALLOCATION )); 44new -> next = node -> next ; 45new -> size = node -> size - sizeof (HeapNode )- size ; 46node -> size = max (size ,MIN_ALLOCATION ); 47node -> next = new ; 48free_space -= sizeof (HeapNode ); 49return true; 50} 51 52// attempt to merge two heap nodes to reduce fragmentation 53// 'a' should be the node at a lower memory address 54static bool try_combining (HeapNode * a ,HeapNode * b ) { 55if (heap_next_node (a )== b ) { 56a -> size += b -> size + sizeof (HeapNode ); 57free_space += sizeof (HeapNode ); 58return true; 59 } 60return false; 61} 62 63static uint32_t align4 (uint32_t n ) { 64return n += n %4 ?4 - n %4 :0 ; 65} 66 67void * _malloc (uint32_t size ) { 68size = align4 (size ); 69HeapNode * prev ; 70HeapNode * current = head ; 71while (current ) { 72if (current -> size >=size ) { 73try_splitting_block (current ,size ); 74if (current == head ) { 75head = current -> next ; 76 }else { 77prev -> next = current -> next ; 78 } 79used_space += current -> size ; 80free_space -= current -> size ; 81return ((uint8_t * )current )+ sizeof (HeapNode ); 82 } 83prev = current ; 84current = current -> next ; 85 } 86return 0 ; 87} 88 89void _free (void * allocation ) { 90if (!allocation ) { 91 __asm("BKPT" );// you've fucked up 92 } 93HeapNode * this = heap_node_from_alloc (allocation ); 94// move along the linked list until prev/current bracket 'this' in terms 95// of their location 96HeapNode * current = head ; 97HeapNode * prev ; 98while (current && this > current ) { 99prev = current ,current = current -> next ; 100 } 101used_space -= this -> size ; 102free_space += this -> size ; 103// attempt to merge this block with the adjacent ones before and after it 104if (current == head ) { 105head = this ; 106 }else { 107if (try_combining (prev ,this )) { 108this = prev ; 109 }else { 110prev -> next = this ; 111 } 112 } 113this -> next = try_combining (this ,current ) ?current -> next :current ; 114} 115 116void * _realloc (void * allocation ,uint32_t size ) { 117if (!allocation ) { 118return malloc (size ); 119 } 120size = align4 (size ); 121HeapNode * this = heap_node_from_alloc (allocation ); 122uint16_t original_size = this -> size ; 123// if shrinking, try splitting the block to return unused space 124if (this -> size > size ) { 125bool temp = try_splitting_block (this ,size ); 126if (temp ) { 127free_space += sizeof (HeapNode ); 128used_space -= sizeof (HeapNode ); 129_free ((uint8_t * )heap_next_node (this )+ sizeof (HeapNode )); 130 } 131return allocation ; 132 } 133// otherwise, grow into adjacent block if possible to avoid copying 134HeapNode * current = head ; 135while (current && this > current ) {current = current -> next ; } 136if (try_combining (this ,current )) { 137this -> next = current -> next ; 138try_splitting_block (this ,size ); 139uint16_t additional_space = this -> size - original_size ; 140used_space += additional_space ; 141free_space -= additional_space ; 142if (current == head ) { 143head = this -> next ; 144 } 145return allocation ; 146 } 147// if neither works, grab a new allocation, copy, and free the old 148void * new = _malloc (size ); 149if (new ) { 150memcpy (new ,allocation ,this -> size ); 151_free (allocation ); 152 } 153return new ; 154} 155 156// TODO: check whether critical sections are required or if the mutex is fine 157void * malloc (uint32_t size ) { 158OS_Wait (& heap_mutex ); 159void * temp = _malloc (size ); 160OS_Signal (& heap_mutex ); 161return temp ; 162} 163 164void free (void * allocation ) { 165OS_Wait (& heap_mutex ); 166_free (allocation ); 167OS_Signal (& heap_mutex ); 168} 169 170void * realloc (void * allocation ,uint32_t size ) { 171OS_Wait (& heap_mutex ); 172void * temp = _realloc (allocation ,size ); 173OS_Signal (& heap_mutex ); 174return temp ; 175} 176 177void * calloc (uint32_t size ) { 178uint8_t * temp = (uint8_t * )malloc (size ); 179if (temp ) { 180memset (temp ,0 ,size ); 181 } 182return temp ; 183} 184 185uint32_t heap_get_space (void ) { 186return free_space ; 187} 188 189uint32_t heap_get_max (void ) { 190uint16_t largest = 0 ; 191OS_Wait (& heap_mutex ); 192HeapNode * current = head ; 193while (current ) { 194largest = max (largest ,current -> size ); 195current = current -> next ; 196 } 197OS_Signal (& heap_mutex ); 198return largest ; 199} 200 201const int graph_width = 80 ; 202void heap_stats (void ) { 203printf ("Total bytes available: %d\n\r" ,total_heap_size ); 204printf ("Bytes in use: " RED "%d" NORMAL "\n\r" ,used_space ); 205printf ("Bytes still available: " CYAN "%d" NORMAL "\n\r" ,free_space ); 206uint16_t wasted = total_heap_size - used_space - free_space ; 207printf ("Bytes wasted: " YELLOW "%d" NORMAL "\n\r" ,wasted ); 208printf ("[" RED ); 209for (int i = 0 ;i < graph_width ;++ i ) { 210if (used_space * graph_width /total_heap_size == i ) { 211printf (YELLOW ); 212 } 213if ((used_space + wasted )* graph_width /total_heap_size == i ) { 214printf (CYAN ); 215 } 216putchar ('#' ); 217 } 218printf (NORMAL "]\n\rLargest possible allocation: %d bytes.\n\r" , 219heap_get_max ()); 220}