/*
- * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
+ * Copyright (c) 2000-2004 Apple Computer, Inc. All rights reserved.
*
- * @APPLE_LICENSE_HEADER_START@
+ * @APPLE_LICENSE_OSREFERENCE_HEADER_START@
*
- * Copyright (c) 1999-2003 Apple Computer, Inc. All Rights Reserved.
- *
- * This file contains Original Code and/or Modifications of Original Code
- * as defined in and that are subject to the Apple Public Source License
- * Version 2.0 (the 'License'). You may not use this file except in
- * compliance with the License. Please obtain a copy of the License at
- * http://www.opensource.apple.com/apsl/ and read it before using this
+ * This file contains Original Code and/or Modifications of Original Code
+ * as defined in and that are subject to the Apple Public Source License
+ * Version 2.0 (the 'License'). You may not use this file except in
+ * compliance with the License. The rights granted to you under the
+ * License may not be used to create, or enable the creation or
+ * redistribution of, unlawful or unlicensed copies of an Apple operating
+ * system, or to circumvent, violate, or enable the circumvention or
+ * violation of, any terms of an Apple operating system software license
+ * agreement.
+ *
+ * Please obtain a copy of the License at
+ * http://www.opensource.apple.com/apsl/ and read it before using this
* file.
- *
- * The Original Code and all software distributed under the License are
- * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
- * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
- * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
- * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
- * Please see the License for the specific language governing rights and
+ *
+ * The Original Code and all software distributed under the License are
+ * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
+ * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
+ * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
+ * Please see the License for the specific language governing rights and
* limitations under the License.
- *
- * @APPLE_LICENSE_HEADER_END@
+ *
+ * @APPLE_LICENSE_OSREFERENCE_HEADER_END@
*/
-#include <vm/vm_kern.h>
-#include <kern/queue.h>
#include <string.h>
-#include <libsa/malloc.h>
-
-#undef CLIENT_DEBUG
-
+#include <mach/mach_types.h>
-/*********************************************************************
-* 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
+#include <kern/kern_types.h>
+#include <kern/queue.h>
+#include <kern/kalloc.h>
+#include <kern/lock.h>
+#include <kern/assert.h>
- vm_size_t free_size; // size of unused area
- void * free_address; // points at the unused area
+#include <vm/vm_kern.h>
- 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,
* 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);
+ struct malloc_block *malFwd;
+ struct malloc_block *malBwd;
+ void *malActl;
+ unsigned int malSize;
+} malloc_block;
-/*********************************************************************
-* 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 */
+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() */
/*********************************************************************
* 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()
*********************************************************************/
__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() */
*********************************************************************/
__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;
-}
projects / apple / xnu.git / blobdiff