176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* 276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * free.c 376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Very simple linked-list based malloc()/free(). 576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <syslinux/firmware.h> 876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <stdlib.h> 976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <dprintf.h> 1076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include "malloc.h" 1176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 1276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <stdio.h> 1376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 1476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic struct free_arena_header * 1576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman__free_block(struct free_arena_header *ah) 1676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 1776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct free_arena_header *pah, *nah; 1876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct free_arena_header *head = 1976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman &__core_malloc_head[ARENA_HEAP_GET(ah->a.attrs)]; 2076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 2176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman pah = ah->a.prev; 2276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman nah = ah->a.next; 2376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if ( ARENA_TYPE_GET(pah->a.attrs) == ARENA_TYPE_FREE && 2476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman (char *)pah+ARENA_SIZE_GET(pah->a.attrs) == (char *)ah ) { 2576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Coalesce into the previous block */ 2676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ARENA_SIZE_SET(pah->a.attrs, ARENA_SIZE_GET(pah->a.attrs) + 2776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ARENA_SIZE_GET(ah->a.attrs)); 2876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman pah->a.next = nah; 2976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman nah->a.prev = pah; 3076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 3176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#ifdef DEBUG_MALLOC 3276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ARENA_TYPE_SET(ah->a.attrs, ARENA_TYPE_DEAD); 3376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#endif 3476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 3576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ah = pah; 3676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman pah = ah->a.prev; 3776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } else { 3876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Need to add this block to the free chain */ 3976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ARENA_TYPE_SET(ah->a.attrs, ARENA_TYPE_FREE); 4076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ah->a.tag = MALLOC_FREE; 4176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 4276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ah->next_free = head->next_free; 4376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ah->prev_free = head; 4476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman head->next_free = ah; 4576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ah->next_free->prev_free = ah; 4676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 4776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 4876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* In either of the previous cases, we might be able to merge 4976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman with the subsequent block... */ 5076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if ( ARENA_TYPE_GET(nah->a.attrs) == ARENA_TYPE_FREE && 5176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman (char *)ah+ARENA_SIZE_GET(ah->a.attrs) == (char *)nah ) { 5276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ARENA_SIZE_SET(ah->a.attrs, ARENA_SIZE_GET(ah->a.attrs) + 5376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ARENA_SIZE_GET(nah->a.attrs)); 5476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 5576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Remove the old block from the chains */ 5676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman nah->next_free->prev_free = nah->prev_free; 5776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman nah->prev_free->next_free = nah->next_free; 5876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ah->a.next = nah->a.next; 5976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman nah->a.next->a.prev = ah; 6076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 6176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#ifdef DEBUG_MALLOC 6276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ARENA_TYPE_SET(nah->a.attrs, ARENA_TYPE_DEAD); 6376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#endif 6476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 6576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 6676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Return the block that contains the called block */ 6776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return ah; 6876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 6976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 7076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanvoid bios_free(void *ptr) 7176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 7276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct free_arena_header *ah; 7376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 7476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ah = (struct free_arena_header *) 7576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ((struct arena_header *)ptr - 1); 7676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 7776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#ifdef DEBUG_MALLOC 7876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (ah->a.magic != ARENA_MAGIC) 7976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("failed free() magic check: %p\n", ptr); 8076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 8176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (ARENA_TYPE_GET(ah->a.attrs) != ARENA_TYPE_USED) 8276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("invalid arena type: %d\n", ARENA_TYPE_GET(ah->a.attrs)); 8376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#endif 8476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 8576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman __free_block(ah); 8676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 8776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 8876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman__export void free(void *ptr) 8976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 9076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("free(%p) @ %p\n", ptr, __builtin_return_address(0)); 9176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 9276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if ( !ptr ) 9376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return; 9476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 9576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman sem_down(&__malloc_semaphore, 0); 9676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman firmware->mem->free(ptr); 9776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman sem_up(&__malloc_semaphore); 9876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 9976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Here we could insert code to return memory to the system. */ 10076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 10176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 10276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* 10376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * This is used to insert a block which is not previously on the 10476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * free list. Only the a.size field of the arena header is assumed 10576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * to be valid. 10676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 10776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanvoid __inject_free_block(struct free_arena_header *ah) 10876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 10976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct free_arena_header *head = 11076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman &__core_malloc_head[ARENA_HEAP_GET(ah->a.attrs)]; 11176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct free_arena_header *nah; 11276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman size_t a_end = (size_t) ah + ARENA_SIZE_GET(ah->a.attrs); 11376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman size_t n_end; 11476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 11576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("inject: %#zx bytes @ %p, heap %u (%p)\n", 11676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ARENA_SIZE_GET(ah->a.attrs), ah, 11776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ARENA_HEAP_GET(ah->a.attrs), head); 11876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 11976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman sem_down(&__malloc_semaphore, 0); 12076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 12176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (nah = head->a.next ; nah != head ; nah = nah->a.next) { 12276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman n_end = (size_t) nah + ARENA_SIZE_GET(nah->a.attrs); 12376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 12476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Is nah entirely beyond this block? */ 12576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if ((size_t) nah >= a_end) 12676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman break; 12776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 12876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Is this block entirely beyond nah? */ 12976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if ((size_t) ah >= n_end) 13076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman continue; 13176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 13276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman printf("conflict:ah: %p, a_end: %p, nah: %p, n_end: %p\n", ah, a_end, nah, n_end); 13376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 13476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Otherwise we have some sort of overlap - reject this block */ 13576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman sem_up(&__malloc_semaphore); 13676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return; 13776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 13876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 13976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Now, nah should point to the successor block */ 14076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ah->a.next = nah; 14176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ah->a.prev = nah->a.prev; 14276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman nah->a.prev = ah; 14376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ah->a.prev->a.next = ah; 14476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 14576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman __free_block(ah); 14676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 14776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman sem_up(&__malloc_semaphore); 14876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 14976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 15076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* 15176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Free all memory which is tagged with a specific tag. 15276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 15376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic void __free_tagged(malloc_tag_t tag) { 15476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct free_arena_header *fp, *head; 15576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman int i; 15676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 15776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman sem_down(&__malloc_semaphore, 0); 15876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 15976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (i = 0; i < NHEAP; i++) { 16076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("__free_tagged(%u) heap %d\n", tag, i); 16176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman head = &__core_malloc_head[i]; 16276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (fp = head->a.next ; fp != head ; fp = fp->a.next) { 16376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (ARENA_TYPE_GET(fp->a.attrs) == ARENA_TYPE_USED && 16476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman fp->a.tag == tag) 16576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman fp = __free_block(fp); 16676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 16776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 16876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 16976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman sem_up(&__malloc_semaphore); 17076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("__free_tagged(%u) done\n", tag); 17176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 17276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 17376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanvoid comboot_cleanup_lowmem(com32sys_t *regs) 17476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 17576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman (void)regs; 17676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 17776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman __free_tagged(MALLOC_MODULE); 17876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 179