X-Git-Url: https://git.saurik.com/apple/xnu.git/blobdiff_plain/de355530ae67247cbd0da700edb3a2a1dae884c2..743b15655a24ee3fe9f458f383003e011db0558f:/libsa/malloc.c diff --git a/libsa/malloc.c b/libsa/malloc.c index a1a0b4733..300583b59 100644 --- a/libsa/malloc.c +++ b/libsa/malloc.c @@ -1,5 +1,5 @@ /* - * Copyright (c) 2000 Apple Computer, Inc. All rights reserved. + * Copyright (c) 2000-2004 Apple Computer, Inc. All rights reserved. * * @APPLE_LICENSE_HEADER_START@ * @@ -19,43 +19,21 @@ * * @APPLE_LICENSE_HEADER_END@ */ -#include -#include #include -#include - -#undef CLIENT_DEBUG - - -/********************************************************************* -* I'm not sure this is really necessary.... -*********************************************************************/ -static inline size_t round_to_long(size_t size) { - return (size + sizeof(long int)) & ~(sizeof(long int) - 1); -} - - -typedef struct queue_entry queue_entry; +#include -/********************************************************************* -* Structure for an allocation region. Each one is created using -* kmem_alloc(), and the whole list of these is destroyed by calling -* malloc_reset(). Client blocks are allocated from a linked list of these -* regions, on a first-fit basis, and are never freed. -*********************************************************************/ -typedef struct malloc_region { - queue_entry links; // Uses queue.h for linked list - vm_size_t region_size; // total size w/ this bookeeping info - - queue_entry block_list; // list of allocated blocks; uses queue.h +#include +#include +#include +#include +#include - vm_size_t free_size; // size of unused area - void * free_address; // points at the unused area +#include - char buffer[0]; // beginning of useable area -} malloc_region; +#include "libsa/malloc.h" +extern void panic(const char *string, ...); /********************************************************************* * Structure for a client memory block. Contains linked-list pointers, @@ -64,171 +42,49 @@ typedef struct malloc_region { * field is guaranteed to lie on a 16-byte boundary. *********************************************************************/ typedef struct malloc_block { - queue_entry links; // Uses queue.h for linked list - malloc_region * region; -#ifdef CLIENT_DEBUG - size_t request_size; -#endif /* CLIENT_DEBUG */ - size_t block_size; // total size w/ all bookeeping info - - // the client's memory block - char buffer[0] __attribute__((aligned(16))); -} malloc_block; - - -/********************************************************************* -* Private functions. -* -* malloc_create_region() -* size - The size in bytes of the region. This is rounded up -* to a multiple of the VM page size. -* Returns a pointer to the new region. -* -* malloc_free_region() -* region - The region to free. -* Returns whatever vm_deallocate() returns. -* -* malloc_create_block_in_region() -* region - The region to alloate a block from. -* size - The total size, including the header, of the block to -* allocate. -* Returns a pointer to the block, or NULL on failure. -* -* malloc_find_block() -* address - The address of the client buffer to find a block for. -* block (out) - The block header for the address. -* region (out) - The region the block was found in, or NULL. -*********************************************************************/ -static malloc_region * malloc_create_region(vm_size_t size); -static kern_return_t malloc_free_region(malloc_region * region); -static malloc_block * malloc_create_block_in_region( - malloc_region * region, - size_t size); -static void malloc_find_block( - void * address, - malloc_block ** block, - malloc_region ** region); -static void malloc_get_free_block( - size_t size, - malloc_block ** block, - malloc_region ** region); - - -/********************************************************************* -* Pointers to the linked list of VM-allocated regions, and a high -* water mark used in testing/debugging. -*********************************************************************/ -static queue_entry malloc_region_list = { - &malloc_region_list, // the "next" field - &malloc_region_list // the "prev" field -}; - -static queue_entry sorted_free_block_list = { - &sorted_free_block_list, - &sorted_free_block_list -}; -#ifdef CLIENT_DEBUG -static size_t malloc_hiwater_mark = 0; -static long int num_regions = 0; + struct malloc_block *malFwd; + struct malloc_block *malBwd; + void *malActl; + unsigned int malSize; +} malloc_block; -static size_t current_block_total = 0; -static double peak_usage = 0.0; -static double min_usage = 100.0; -#endif /* CLIENT_DEBUG */ +static malloc_block malAnchor = {&malAnchor, &malAnchor, 0, 0}; +static int malInited = 0; +static mutex_t *malloc_lock; -/********************************************************************* -* malloc() -*********************************************************************/ __private_extern__ void * malloc(size_t size) { - size_t need_size; - malloc_region * cur_region = NULL; - malloc_region * use_region = NULL; - malloc_block * client_block = NULL; - void * client_buffer = NULL; - - /* Add the size of the block header to the request size. - */ - need_size = round_to_long(size + sizeof(malloc_block)); - - - /* See if there's a previously-freed block that we can reuse. - */ - malloc_get_free_block(need_size, - &client_block, &use_region); - - - /* If we found a free block that we can reuse, then reuse it. - */ - if (client_block != NULL) { - - /* Remove the found block from the list of free blocks - * and tack it onto the list of allocated blocks. - */ - queue_remove(&sorted_free_block_list, client_block, malloc_block *, links); - queue_enter(&use_region->block_list, client_block, malloc_block *, links); - client_buffer = client_block->buffer; - // Don't return here! There's bookkeeping done below. - - } else { - - /* Didn't find a freed block to reuse. */ - - /* Look for a region with enough unused space to carve out a new block. - */ - queue_iterate(&malloc_region_list, cur_region, malloc_region *, links) { - if (use_region == NULL && cur_region->free_size >= need_size) { - use_region = cur_region; - break; - } - } - - - /* If we haven't found a region with room, create a new one and - * put it at the end of the list of regions. - */ - if (use_region == NULL) { - use_region = malloc_create_region(need_size); - if (use_region == NULL) { - return NULL; - // FIXME: panic? - } - } - - /* Create a new block in the found/created region. - */ - client_block = malloc_create_block_in_region(use_region, need_size); - if (client_block != NULL) { - client_buffer = client_block->buffer; - // Don't return here! There's bookkeeping done below. - } - } - -#ifdef CLIENT_DEBUG - if (client_block != NULL) { - size_t region_usage = malloc_region_usage(); - double current_usage; - - current_block_total += client_block->block_size; - if (region_usage > 0) { - current_usage = (double)current_block_total / (double)malloc_region_usage(); - if (current_usage > peak_usage) { - peak_usage = current_usage; - } - - if (current_usage < min_usage) { - min_usage = current_usage; - } - } - - client_block->request_size = size; - } -#endif /* CLIENT_DEBUG */ - - return client_buffer; + unsigned int nsize; + unsigned int nmem, rmem; + malloc_block *amem; + + assert(malInited); + + nsize = size + sizeof(malloc_block) + 15; /* Make sure we get enough to fit */ + + nmem = (unsigned int)kalloc(nsize); /* Get some */ + if(!nmem) { /* Got any? */ + panic("malloc: no memory for a %08X sized request\n", nsize); + } + + rmem = (nmem + 15) & -16; /* Round to 16 byte boundary */ + amem = (malloc_block *)rmem; /* Point to the block */ + amem->malActl = nmem; /* Set the actual address */ + amem->malSize = nsize; /* Size */ + + mutex_lock(malloc_lock); + + amem->malFwd = malAnchor.malFwd; /* Move anchor to our forward */ + amem->malBwd = &malAnchor; /* We point back to anchor */ + malAnchor.malFwd->malBwd = amem; /* The old forward's back points to us */ + malAnchor.malFwd = amem; /* Now we point the anchor to us */ + + mutex_unlock(malloc_lock); /* Unlock now */ + + return (void *)(rmem + 16); /* Return the block */ } /* malloc() */ @@ -236,56 +92,45 @@ void * malloc(size_t size) { /********************************************************************* * free() * -* Moves a block from the allocated list to the free list. Neither -* list is kept sorted! *********************************************************************/ __private_extern__ void free(void * address) { - malloc_region * found_region = NULL; - malloc_block * found_block = NULL; - malloc_block * cur_block = NULL; - - /* Find the block and region for the given address. - */ - malloc_find_block(address, &found_block, &found_region); - if (found_block == NULL) { - return; - // FIXME: panic? - } - - - /* Remove the found block from the list of allocated blocks - * and tack it onto the list of free blocks. - */ - queue_remove(&found_region->block_list, found_block, malloc_block *, links); - - found_block->links.next = NULL; - queue_iterate(&sorted_free_block_list, cur_block, malloc_block *, links) { - if (cur_block->block_size > found_block->block_size) { - queue_insert_before(&sorted_free_block_list, found_block, cur_block, - malloc_block *, links); - break; - } - } + malloc_block *amem, *fore, *aft; + + if(!(unsigned int)address) return; /* Leave if they try to free nothing */ + + + amem = (malloc_block *)((unsigned int)address - sizeof(malloc_block)); /* Point to the header */ - /* If the "next" link is still NULL, then either the list is empty or the - * freed block has to go on the end, so just tack it on. - */ - if (found_block->links.next == NULL) { - queue_enter(&sorted_free_block_list, found_block, malloc_block *, links); - } + mutex_lock(malloc_lock); + fore = amem->malFwd; /* Get the guy in front */ + aft = amem->malBwd; /* And the guy behind */ + fore->malBwd = aft; /* The next guy's previous is now my previous */ + aft->malFwd = fore; /* The previous guy's forward is now mine */ -#ifdef CLIENT_DEBUG - current_block_total -= found_block->block_size; -#endif /* CLIENT_DEBUG */ + mutex_unlock(malloc_lock); /* Unlock now */ + + kfree(amem->malActl, amem->malSize); /* Toss it */ - return; + return; } /* free() */ +/********************************************************************* +* malloc_reset() +* +* Allocate the mutual exclusion lock that protect malloc's data. +*********************************************************************/ +__private_extern__ void +malloc_init(void) +{ + malloc_lock = mutex_alloc(0); + malInited = 1; +} + /********************************************************************* * malloc_reset() @@ -296,20 +141,27 @@ void free(void * address) { *********************************************************************/ __private_extern__ void malloc_reset(void) { - malloc_region * cur_region; - - while (! queue_empty(&malloc_region_list)) { - kern_return_t kern_result; - queue_remove_first(&malloc_region_list, cur_region, - malloc_region *, links); - kern_result = malloc_free_region(cur_region); - if (kern_result != KERN_SUCCESS) { - // what sort of error checking can we even do here? - // printf("malloc_free_region() failed.\n"); - // panic(); - } - } - + + malloc_block *amem, *bmem; + + mutex_lock(malloc_lock); + + amem = malAnchor.malFwd; /* Get the first one */ + + while(amem != &malAnchor) { /* Go until we hit the anchor */ + + bmem = amem->malFwd; /* Next one */ + kfree(amem->malActl, amem->malSize); /* Toss it */ + amem = bmem; /* Skip to it */ + + } + + malAnchor.malFwd = (struct malloc_block *) 0x666; /* Cause a fault if we try again */ + malAnchor.malBwd = (struct malloc_block *) 0x666; /* Cause a fault if we try again */ + + mutex_unlock(malloc_lock); /* Unlock now */ + + mutex_free(malloc_lock); return; } /* malloc_reset() */ @@ -324,270 +176,22 @@ void malloc_reset(void) { *********************************************************************/ __private_extern__ void * realloc(void * address, size_t new_client_size) { - malloc_region * found_region = NULL; - malloc_block * found_block = NULL; void * new_address; - size_t new_block_size; - size_t copy_bytecount; - - - malloc_find_block(address, &found_block, &found_region); - - - /* If we couldn't find the requested block, - * the caller is in error so return NULL. - */ - if (found_block == NULL) { - // printf("realloc() called with invalid block.\n"); - return NULL; - // FIXME: panic? - } - - - /* Figure out how much memory is actually needed. - */ - new_block_size = new_client_size + sizeof(malloc_block); - - - /* If the new size is <= the current size, don't bother. - */ - if (new_block_size <= found_block->block_size) { -#ifdef CLIENT_DEBUG - if (new_client_size > found_block->request_size) { - found_block->request_size = new_client_size; - } -#endif /* CLIENT_DEBUG */ - return address; - } - - - /* Create a new block of the requested size. - */ - new_address = malloc(new_client_size); - - if (new_address == NULL) { - // printf("error in realloc()\n"); - return NULL; - // FIXME: panic? - } - - - /* Copy the data from the old block to the new one. - * Make sure to copy only the lesser of the existing and - * requested new size. (Note: The code above currently - * screens out a realloc to a smaller size, but it might - * not always do that.) - */ - copy_bytecount = found_block->block_size - sizeof(malloc_block); - - if (new_client_size < copy_bytecount) { - copy_bytecount = new_client_size; - } - - memcpy(new_address, address, copy_bytecount); - - - /* Free the old block. - */ - free(address); - - return (void *)new_address; + malloc_block *amem; + + amem = (malloc_block *)((unsigned int)address - sizeof(malloc_block)); /* Point to allocation block */ + + new_address = malloc(new_client_size); /* get a new one */ + if(!new_address) { /* Did we get it? */ + panic("realloc: can not reallocate one of %08X size\n", new_client_size); + } + + memcpy(new_address, address, amem->malSize - sizeof(malloc_block)); /* Copy the old in */ + + free(address); /* Toss the old one */ + + return new_address; } /* realloc() */ -/********************************************************************* -********************************************************************** -***** PACKAGE-INTERNAL FUNCTIONS BELOW HERE ***** -********************************************************************** -*********************************************************************/ - - - -/********************************************************************* -* malloc_create_region() -* -* Package-internal function. VM-allocates a new region and adds it to -* the given region list. -*********************************************************************/ -__private_extern__ -malloc_region * malloc_create_region(vm_size_t block_size) { - - malloc_region * new_region; - vm_address_t vm_address; - vm_size_t region_size; - kern_return_t kern_result; - - - /* Figure out how big the region needs to be and allocate it. - */ - region_size = block_size + sizeof(malloc_region); - region_size = round_page(region_size); - - kern_result = kmem_alloc(kernel_map, - &vm_address, region_size); - - if (kern_result != KERN_SUCCESS) { - // printf("kmem_alloc() failed in malloc_create_region()\n"); - return NULL; - // panic(); - } - - - /* Cast the allocated pointer to a region header. - */ - new_region = (malloc_region *)vm_address; - - - /* Initialize the region header fields and link it onto - * the previous region. - */ - new_region->region_size = region_size; - queue_init(&new_region->block_list); -// queue_init(&new_region->free_list); - - new_region->free_size = region_size - sizeof(malloc_region); - new_region->free_address = &new_region->buffer; - - queue_enter(&malloc_region_list, new_region, malloc_region *, links); - - /* If debugging, add the new region's size to the total. - */ -#ifdef CLIENT_DEBUG - malloc_hiwater_mark += region_size; - num_regions++; -#endif /* CLIENT_DEBUG */ - - return new_region; - -} /* malloc_create_region() */ - - -/********************************************************************* -* malloc_free_region() -* -* Package-internal function. VM-deallocates the given region. -*********************************************************************/ -__private_extern__ -kern_return_t malloc_free_region(malloc_region * region) { - - kmem_free(kernel_map, - (vm_address_t)region, - region->region_size); - -#ifdef CLIENT_DEBUG - num_regions--; -#endif /* CLIENT_DEBUG */ - return KERN_SUCCESS; - -} /* malloc_free_region() */ - - -/********************************************************************* -* malloc_create_block_in_region() -* -* Package-internal function. Allocates a new block out of the given -* region. The requested size must include the block header. If the -* size requested is larger than the region's free size, returns NULL. -*********************************************************************/ -__private_extern__ -malloc_block * malloc_create_block_in_region( - malloc_region * region, - size_t block_size) { - - malloc_block * new_block = NULL; - - - /* Sanity checking. - */ - if (block_size > region->free_size) { - return NULL; - // FIXME: panic? - } - - - /* Carve out a new block. - */ - new_block = (malloc_block *)region->free_address; - region->free_address = (char *)region->free_address + block_size; - region->free_size -= block_size; - - memset(new_block, 0, sizeof(malloc_block)); - - new_block->region = region; - new_block->block_size = block_size; - - /* Record the new block as the last one in the region. - */ - queue_enter(®ion->block_list, new_block, malloc_block *, links); - - return new_block; - -} /* malloc_create_block_in_region() */ - - -/********************************************************************* -* malloc_find_block() -* -* Package-internal function. Given a client buffer address, find the -* malloc_block for it. -*********************************************************************/ -__private_extern__ -void malloc_find_block(void * address, - malloc_block ** block, - malloc_region ** region) { - - malloc_region * cur_region; - - *block = NULL; - *region = NULL; - - queue_iterate(&malloc_region_list, cur_region, malloc_region *, links) { - - malloc_block * cur_block; - - queue_iterate(&cur_region->block_list, cur_block, malloc_block *, links) { - if (cur_block->buffer == address) { - *block = cur_block; - *region = cur_region; - return; - } - } - } - - return; - -} /* malloc_find_block() */ - - -/********************************************************************* -* malloc_get_free_block() -*********************************************************************/ -__private_extern__ -void malloc_get_free_block( - size_t size, - malloc_block ** block, - malloc_region ** region) { - - malloc_block * cur_block; - size_t fit_threshold = 512; - - *block = NULL; - *region = NULL; - - queue_iterate(&sorted_free_block_list, cur_block, malloc_block *, links) { - - /* If we find a block large enough, but not too large to waste memory, - * pull it out and return it, along with its region. - */ - if (cur_block->block_size >= size && - cur_block->block_size < (size + fit_threshold)) { - - queue_remove(&sorted_free_block_list, cur_block, malloc_block *, links); - *block = cur_block; - *region = cur_block->region; - return; - } - } - return; -}