xnu-517.tar.gz

[apple/xnu.git] / libsa / malloc.c

diff --git a/libsa/malloc.c b/libsa/malloc.c
index c5bcb1ec922e55a2b1d2e08dd940357c5cd6f9a2..00a94e54e2acfc380f11ab029ead1b65b4dfcf5b 100644 (file)
--- a/libsa/malloc.c
+++ b/libsa/malloc.c
@@ -22,43 +22,17 @@
  * 
  * @APPLE_LICENSE_HEADER_END@
  */
  * 
  * @APPLE_LICENSE_HEADER_END@
  */

-#include <vm/vm_kern.h>
-#include <kern/queue.h>

 #include <string.h>
 
 #include <string.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
+#include <kern/queue.h>
+#include <kern/kalloc.h>
+#include <kern/lock.h>
+#include <kern/assert.h> 
+#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,
 
 /*********************************************************************
 * Structure for a client memory block. Contains linked-list pointers,


@@ -67,171 +41,49 @@ typedef struct malloc_region {
 * field is guaranteed to lie on a 16-byte boundary.
 *********************************************************************/
 typedef struct malloc_block {
 * 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;
+       unsigned int            malSize;
+       unsigned int            malActl;
+} 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) {
 __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 = (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 */

 
 } /* malloc() */
 
 
 } /* malloc() */
 


@@ -239,56 +91,45 @@ void * malloc(size_t size) {
 /*********************************************************************
 * free()
 *
 /*********************************************************************
 * free()
 *

-* Moves a block from the allocated list to the free list. Neither
-* list is kept sorted!

 *********************************************************************/
 __private_extern__
 void free(void * address) {
 *********************************************************************/
 __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() */
 
 
 } /* free() */
 

+/*********************************************************************
+* 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;
+}
+

 
 /*********************************************************************
 * malloc_reset()
 
 /*********************************************************************
 * malloc_reset()


@@ -299,20 +140,27 @@ void free(void * address) {
 *********************************************************************/
 __private_extern__
 void malloc_reset(void) {
 *********************************************************************/
 __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() */
     return;
 
 } /* malloc_reset() */


@@ -327,270 +175,22 @@ void malloc_reset(void) {
 *********************************************************************/
 __private_extern__
 void * realloc(void * address, size_t new_client_size) {
 *********************************************************************/
 __private_extern__
 void * realloc(void * address, size_t new_client_size) {

-    malloc_region * found_region = NULL;
-    malloc_block  * found_block = NULL;

     void * new_address;
     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() */
 
 
 
 } /* 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(&region->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;
-}