*
* @APPLE_LICENSE_HEADER_END@
*/
+#include <vm/vm_kern.h>
+#include <kern/queue.h>
#include <string.h>
-#include <kern/queue.h>
-#include <kern/lock.h>
-#include <kern/assert.h>
-#include <vm/vm_kern.h>
+#include <libsa/malloc.h>
+
+#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;
+
+/*********************************************************************
+* 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
+
+ vm_size_t free_size; // size of unused area
+ void * free_address; // points at the unused area
+
+ char buffer[0]; // beginning of useable area
+} malloc_region;
-#include "libsa/malloc.h"
/*********************************************************************
* Structure for a client memory block. Contains linked-list pointers,
* field is guaranteed to lie on a 16-byte boundary.
*********************************************************************/
typedef struct malloc_block {
-
- struct malloc_block *malFwd;
- struct malloc_block *malBwd;
- unsigned int malSize;
- unsigned int malActl;
+ 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;
-static malloc_block malAnchor = {&malAnchor, &malAnchor, 0, 0};
-static int malInited = 0;
-static mutex_t *malloc_lock;
+/*********************************************************************
+* 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;
+
+static size_t current_block_total = 0;
+static double peak_usage = 0.0;
+static double min_usage = 100.0;
+#endif /* CLIENT_DEBUG */
+
+
+/*********************************************************************
+* 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);
+
- 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 = (unsigned int)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 */
+ /* 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;
} /* malloc() */
/*********************************************************************
* 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);
- 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 (found_block == NULL) {
+ return;
+ // FIXME: panic?
+ }
- 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 */
+ /* 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);
- mutex_unlock(malloc_lock); /* Unlock now */
-
- kfree((void *)amem->malActl, amem->malSize); /* Toss it */
+ 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;
+ }
+ }
- return;
-} /* free() */
+ /* 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);
+ }
-/*********************************************************************
-* malloc_reset()
-*
-* Allocate the mutual exclusion lock that protect malloc's data.
-*********************************************************************/
-__private_extern__ void
-malloc_init(void)
-{
- malloc_lock = mutex_alloc(ETAP_IO_AHA);
- malInited = 1;
-}
+
+#ifdef CLIENT_DEBUG
+ current_block_total -= found_block->block_size;
+#endif /* CLIENT_DEBUG */
+
+ return;
+
+} /* free() */
/*********************************************************************
*********************************************************************/
__private_extern__
void malloc_reset(void) {
-
- 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((void *)amem->malActl, amem->malSize); /* Toss it */
- amem = bmem; /* Skip to it */
-
- }
-
- malAnchor.malFwd = 0x666; /* Cause a fault if we try again */
- malAnchor.malBwd = 0x666; /* Cause a fault if we try again */
-
- mutex_unlock(malloc_lock); /* Unlock now */
-
- mutex_free(malloc_lock);
+ 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();
+ }
+ }
+
return;
} /* malloc_reset() */
*********************************************************************/
__private_extern__
void * realloc(void * address, size_t new_client_size) {
+ malloc_region * found_region = NULL;
+ malloc_block * found_block = NULL;
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;
+ 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;
} /* 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;
+}
projects / apple / xnu.git / blobdiff