1 /* 2 * free.c 3 * 4 * Very simple linked-list based malloc()/free(). 5 */ 6 7 #include <syslinux/firmware.h> 8 #include <stdlib.h> 9 #include <dprintf.h> 10 #include "malloc.h" 11 12 #include <stdio.h> 13 14 static struct free_arena_header * 15 __free_block(struct free_arena_header *ah) 16 { 17 struct free_arena_header *pah, *nah; 18 struct free_arena_header *head = 19 &__core_malloc_head[ARENA_HEAP_GET(ah->a.attrs)]; 20 21 pah = ah->a.prev; 22 nah = ah->a.next; 23 if ( ARENA_TYPE_GET(pah->a.attrs) == ARENA_TYPE_FREE && 24 (char *)pah+ARENA_SIZE_GET(pah->a.attrs) == (char *)ah ) { 25 /* Coalesce into the previous block */ 26 ARENA_SIZE_SET(pah->a.attrs, ARENA_SIZE_GET(pah->a.attrs) + 27 ARENA_SIZE_GET(ah->a.attrs)); 28 pah->a.next = nah; 29 nah->a.prev = pah; 30 31 #ifdef DEBUG_MALLOC 32 ARENA_TYPE_SET(ah->a.attrs, ARENA_TYPE_DEAD); 33 #endif 34 35 ah = pah; 36 pah = ah->a.prev; 37 } else { 38 /* Need to add this block to the free chain */ 39 ARENA_TYPE_SET(ah->a.attrs, ARENA_TYPE_FREE); 40 ah->a.tag = MALLOC_FREE; 41 42 ah->next_free = head->next_free; 43 ah->prev_free = head; 44 head->next_free = ah; 45 ah->next_free->prev_free = ah; 46 } 47 48 /* In either of the previous cases, we might be able to merge 49 with the subsequent block... */ 50 if ( ARENA_TYPE_GET(nah->a.attrs) == ARENA_TYPE_FREE && 51 (char *)ah+ARENA_SIZE_GET(ah->a.attrs) == (char *)nah ) { 52 ARENA_SIZE_SET(ah->a.attrs, ARENA_SIZE_GET(ah->a.attrs) + 53 ARENA_SIZE_GET(nah->a.attrs)); 54 55 /* Remove the old block from the chains */ 56 nah->next_free->prev_free = nah->prev_free; 57 nah->prev_free->next_free = nah->next_free; 58 ah->a.next = nah->a.next; 59 nah->a.next->a.prev = ah; 60 61 #ifdef DEBUG_MALLOC 62 ARENA_TYPE_SET(nah->a.attrs, ARENA_TYPE_DEAD); 63 #endif 64 } 65 66 /* Return the block that contains the called block */ 67 return ah; 68 } 69 70 void bios_free(void *ptr) 71 { 72 struct free_arena_header *ah; 73 74 ah = (struct free_arena_header *) 75 ((struct arena_header *)ptr - 1); 76 77 #ifdef DEBUG_MALLOC 78 if (ah->a.magic != ARENA_MAGIC) 79 dprintf("failed free() magic check: %p\n", ptr); 80 81 if (ARENA_TYPE_GET(ah->a.attrs) != ARENA_TYPE_USED) 82 dprintf("invalid arena type: %d\n", ARENA_TYPE_GET(ah->a.attrs)); 83 #endif 84 85 __free_block(ah); 86 } 87 88 __export void free(void *ptr) 89 { 90 dprintf("free(%p) @ %p\n", ptr, __builtin_return_address(0)); 91 92 if ( !ptr ) 93 return; 94 95 sem_down(&__malloc_semaphore, 0); 96 firmware->mem->free(ptr); 97 sem_up(&__malloc_semaphore); 98 99 /* Here we could insert code to return memory to the system. */ 100 } 101 102 /* 103 * This is used to insert a block which is not previously on the 104 * free list. Only the a.size field of the arena header is assumed 105 * to be valid. 106 */ 107 void __inject_free_block(struct free_arena_header *ah) 108 { 109 struct free_arena_header *head = 110 &__core_malloc_head[ARENA_HEAP_GET(ah->a.attrs)]; 111 struct free_arena_header *nah; 112 size_t a_end = (size_t) ah + ARENA_SIZE_GET(ah->a.attrs); 113 size_t n_end; 114 115 dprintf("inject: %#zx bytes @ %p, heap %u (%p)\n", 116 ARENA_SIZE_GET(ah->a.attrs), ah, 117 ARENA_HEAP_GET(ah->a.attrs), head); 118 119 sem_down(&__malloc_semaphore, 0); 120 121 for (nah = head->a.next ; nah != head ; nah = nah->a.next) { 122 n_end = (size_t) nah + ARENA_SIZE_GET(nah->a.attrs); 123 124 /* Is nah entirely beyond this block? */ 125 if ((size_t) nah >= a_end) 126 break; 127 128 /* Is this block entirely beyond nah? */ 129 if ((size_t) ah >= n_end) 130 continue; 131 132 printf("conflict:ah: %p, a_end: %p, nah: %p, n_end: %p\n", ah, a_end, nah, n_end); 133 134 /* Otherwise we have some sort of overlap - reject this block */ 135 sem_up(&__malloc_semaphore); 136 return; 137 } 138 139 /* Now, nah should point to the successor block */ 140 ah->a.next = nah; 141 ah->a.prev = nah->a.prev; 142 nah->a.prev = ah; 143 ah->a.prev->a.next = ah; 144 145 __free_block(ah); 146 147 sem_up(&__malloc_semaphore); 148 } 149 150 /* 151 * Free all memory which is tagged with a specific tag. 152 */ 153 static void __free_tagged(malloc_tag_t tag) { 154 struct free_arena_header *fp, *head; 155 int i; 156 157 sem_down(&__malloc_semaphore, 0); 158 159 for (i = 0; i < NHEAP; i++) { 160 dprintf("__free_tagged(%u) heap %d\n", tag, i); 161 head = &__core_malloc_head[i]; 162 for (fp = head->a.next ; fp != head ; fp = fp->a.next) { 163 if (ARENA_TYPE_GET(fp->a.attrs) == ARENA_TYPE_USED && 164 fp->a.tag == tag) 165 fp = __free_block(fp); 166 } 167 } 168 169 sem_up(&__malloc_semaphore); 170 dprintf("__free_tagged(%u) done\n", tag); 171 } 172 173 void comboot_cleanup_lowmem(com32sys_t *regs) 174 { 175 (void)regs; 176 177 __free_tagged(MALLOC_MODULE); 178 } 179