xnu-2050.48.11.tar.gz

[apple/xnu.git] / osfmk / kern / kalloc.c

diff --git a/osfmk/kern/kalloc.c b/osfmk/kern/kalloc.c
index 03c55052d94ec4bf10746bc99f4873491ca2491d..a5febf94c7fa14740329e8676b38760f76700d6e 100644 (file)
--- a/osfmk/kern/kalloc.c
+++ b/osfmk/kern/kalloc.c
@@ -1,5 +1,5 @@
 /*
 /*

- * Copyright (c) 2000-2006 Apple Computer, Inc. All rights reserved.
+ * Copyright (c) 2000-2011 Apple Computer, Inc. All rights reserved.

  *
  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
  * 
  *
  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
  * 


@@ -73,6 +73,7 @@
 #include <kern/zalloc.h>
 #include <kern/kalloc.h>
 #include <kern/lock.h>
 #include <kern/zalloc.h>
 #include <kern/kalloc.h>
 #include <kern/lock.h>

+#include <kern/ledger.h>

 #include <vm/vm_kern.h>
 #include <vm/vm_object.h>
 #include <vm/vm_map.h>
 #include <vm/vm_kern.h>
 #include <vm/vm_object.h>
 #include <vm/vm_map.h>


@@ -92,39 +93,192 @@ vm_size_t kalloc_kernmap_size;     /* size of kallocs that can come from kernel map
 unsigned int kalloc_large_inuse;
 vm_size_t    kalloc_large_total;
 vm_size_t    kalloc_large_max;
 unsigned int kalloc_large_inuse;
 vm_size_t    kalloc_large_total;
 vm_size_t    kalloc_large_max;

-volatile vm_size_t    kalloc_largest_allocated = 0;
+vm_size_t    kalloc_largest_allocated = 0;
+uint64_t    kalloc_large_sum;
+
+int    kalloc_fake_zone_index = -1; /* index of our fake zone in statistics arrays */

 
 vm_offset_t    kalloc_map_min;
 vm_offset_t    kalloc_map_max;
 
 
 vm_offset_t    kalloc_map_min;
 vm_offset_t    kalloc_map_max;
 

+#ifdef MUTEX_ZONE
+/*
+ * Diagnostic code to track mutexes separately rather than via the 2^ zones
+ */
+       zone_t          lck_mtx_zone;
+#endif
+
+static void
+KALLOC_ZINFO_SALLOC(vm_size_t bytes)
+{
+       thread_t thr = current_thread();
+       task_t task;
+       zinfo_usage_t zinfo;
+
+       ledger_debit(thr->t_ledger, task_ledgers.tkm_shared, bytes);
+
+       if (kalloc_fake_zone_index != -1 && 
+           (task = thr->task) != NULL && (zinfo = task->tkm_zinfo) != NULL)
+               zinfo[kalloc_fake_zone_index].alloc += bytes;
+}
+
+static void
+KALLOC_ZINFO_SFREE(vm_size_t bytes)
+{
+       thread_t thr = current_thread();
+       task_t task;
+       zinfo_usage_t zinfo;
+
+       ledger_credit(thr->t_ledger, task_ledgers.tkm_shared, bytes);
+
+       if (kalloc_fake_zone_index != -1 && 
+           (task = thr->task) != NULL && (zinfo = task->tkm_zinfo) != NULL)
+               zinfo[kalloc_fake_zone_index].free += bytes;
+}
+

 /*
  *     All allocations of size less than kalloc_max are rounded to the
 /*
  *     All allocations of size less than kalloc_max are rounded to the

- *     next highest power of 2.  This allocator is built on top of
+ *     next nearest sized zone.  This allocator is built on top of

  *     the zone allocator.  A zone is created for each potential size
  *     that we are willing to get in small blocks.
  *
  *     We assume that kalloc_max is not greater than 64K;
  *     the zone allocator.  A zone is created for each potential size
  *     that we are willing to get in small blocks.
  *
  *     We assume that kalloc_max is not greater than 64K;

- *     thus 16 is a safe array size for k_zone and k_zone_name.

  *
  *     Note that kalloc_max is somewhat confusingly named.
  *     It represents the first power of two for which no zone exists.
  *     kalloc_max_prerounded is the smallest allocation size, before
  *     rounding, for which no zone exists.
  *
  *     Note that kalloc_max is somewhat confusingly named.
  *     It represents the first power of two for which no zone exists.
  *     kalloc_max_prerounded is the smallest allocation size, before
  *     rounding, for which no zone exists.

- *  Also if the allocation size is more than kalloc_kernmap_size 
- *  then allocate from kernel map rather than kalloc_map.
+ *
+ *     Also if the allocation size is more than kalloc_kernmap_size 
+ *     then allocate from kernel map rather than kalloc_map.
+ */
+
+#if KALLOC_MINSIZE == 16 && KALLOC_LOG2_MINALIGN == 4
+
+/*
+ * "Legacy" aka "power-of-2" backing zones with 16-byte minimum
+ * size and alignment.  Users of this profile would probably
+ * benefit from some tuning.
+ */
+
+#define K_ZONE_SIZES                   \
+       16,                             \
+       32,                             \
+/* 6 */        64,                             \
+       128,                            \
+       256,                            \
+/* 9 */        512,                            \
+       1024,                           \
+       2048,                           \
+/* C */        4096
+
+
+#define K_ZONE_NAMES                   \
+       "kalloc.16",                    \
+       "kalloc.32",                    \
+/* 6 */        "kalloc.64",                    \
+       "kalloc.128",                   \
+       "kalloc.256",                   \
+/* 9 */        "kalloc.512",                   \
+       "kalloc.1024",                  \
+       "kalloc.2048",                  \
+/* C */        "kalloc.4096"
+
+#define K_ZONE_MAXIMA                  \
+       1024,                           \
+       4096,                           \
+/* 6 */        4096,                           \
+       4096,                           \
+       4096,                           \
+/* 9 */        1024,                           \
+       1024,                           \
+       1024,                           \
+/* C */        1024
+
+#elif KALLOC_MINSIZE == 8 && KALLOC_LOG2_MINALIGN == 3
+
+/*
+ * Tweaked for ARM (and x64) in 04/2011

  */
 
  */
 

-int first_k_zone = -1;
-struct zone *k_zone[16];
-static const char *k_zone_name[16] = {
-       "kalloc.1",             "kalloc.2",
-       "kalloc.4",             "kalloc.8",
-       "kalloc.16",            "kalloc.32",
-       "kalloc.64",            "kalloc.128",
-       "kalloc.256",           "kalloc.512",
-       "kalloc.1024",          "kalloc.2048",
-       "kalloc.4096",          "kalloc.8192",
-       "kalloc.16384",         "kalloc.32768"
+#define K_ZONE_SIZES                   \
+/* 3 */        8,                              \
+       16,     24,                     \
+       32,     40,     48,             \
+/* 6 */        64,     88,     112,            \
+       128,    192,                    \
+       256,    384,                    \
+/* 9 */        512,    768,                    \
+       1024,   1536,                   \
+       2048,   3072,                   \
+       4096,   6144
+
+#define K_ZONE_NAMES                   \
+/* 3 */        "kalloc.8",                     \
+       "kalloc.16",    "kalloc.24",    \
+       "kalloc.32",    "kalloc.40",    "kalloc.48",    \
+/* 6 */        "kalloc.64",    "kalloc.88",    "kalloc.112",   \
+       "kalloc.128",   "kalloc.192",   \
+       "kalloc.256",   "kalloc.384",   \
+/* 9 */        "kalloc.512",   "kalloc.768",   \
+       "kalloc.1024",  "kalloc.1536",  \
+       "kalloc.2048",  "kalloc.3072",  \
+       "kalloc.4096",  "kalloc.6144"
+
+#define        K_ZONE_MAXIMA                   \
+/* 3 */        1024,                           \
+       1024,   1024,                   \
+       4096,   4096,   4096,           \
+/* 6 */        4096,   4096,   4096,           \
+       4096,   4096,                   \
+       4096,   4096,                   \
+/* 9 */        1024,   1024,                   \
+       1024,   1024,                   \
+       1024,   1024,                   \
+/* C */        1024,   64
+
+#else
+#error missing zone size parameters for kalloc
+#endif
+
+#define KALLOC_MINALIGN (1 << KALLOC_LOG2_MINALIGN)
+
+static const int k_zone_size[] = {
+       K_ZONE_SIZES,
+       8192,
+       16384,
+/* F */        32768
+};
+
+#define N_K_ZONE       (sizeof (k_zone_size) / sizeof (k_zone_size[0]))
+
+/*
+ * Many kalloc() allocations are for small structures containing a few
+ * pointers and longs - the k_zone_dlut[] direct lookup table, indexed by
+ * size normalized to the minimum alignment, finds the right zone index
+ * for them in one dereference.
+ */
+
+#define INDEX_ZDLUT(size)      \
+                       (((size) + KALLOC_MINALIGN - 1) / KALLOC_MINALIGN)
+#define N_K_ZDLUT      (2048 / KALLOC_MINALIGN)
+                               /* covers sizes [0 .. 2048 - KALLOC_MINALIGN] */
+#define MAX_SIZE_ZDLUT ((N_K_ZDLUT - 1) * KALLOC_MINALIGN)
+
+static int8_t k_zone_dlut[N_K_ZDLUT];  /* table of indices into k_zone[] */
+
+/*
+ * If there's no hit in the DLUT, then start searching from k_zindex_start.
+ */
+static int k_zindex_start;
+
+static zone_t k_zone[N_K_ZONE];
+
+static const char *k_zone_name[N_K_ZONE] = {
+       K_ZONE_NAMES,
+       "kalloc.8192",
+       "kalloc.16384",
+/* F */        "kalloc.32768"

 };
 
 /*
 };
 
 /*


@@ -133,36 +287,38 @@ static const char *k_zone_name[16] = {
  *  based on need, rather than just guessing; it also
  *  means its patchable in case you're wrong!
  */
  *  based on need, rather than just guessing; it also
  *  means its patchable in case you're wrong!
  */

-unsigned long k_zone_max[16] = {
-      1024,            /*      1 Byte  */
-      1024,            /*      2 Byte  */
-      1024,            /*      4 Byte  */
-      1024,            /*      8 Byte  */
-      1024,            /*     16 Byte  */
-      4096,            /*     32 Byte  */
-      4096,            /*     64 Byte  */
-      4096,            /*    128 Byte  */
-      4096,            /*    256 Byte  */
-      1024,            /*    512 Byte  */
-      1024,            /*   1024 Byte  */
-      1024,            /*   2048 Byte  */
-      1024,            /*   4096 Byte  */
-      4096,            /*   8192 Byte  */
-      64,              /*  16384 Byte  */
-      64,              /*  32768 Byte  */
+unsigned int k_zone_max[N_K_ZONE] = {
+       K_ZONE_MAXIMA,
+       4096,
+       64,
+/* F */        64

 };
 
 };
 

+/* #define KALLOC_DEBUG                1 */
+

 /* forward declarations */
 void * kalloc_canblock(
                vm_size_t       size,
                boolean_t       canblock);
 
 
 /* forward declarations */
 void * kalloc_canblock(
                vm_size_t       size,
                boolean_t       canblock);
 
 

+lck_grp_t *kalloc_lck_grp;
+lck_mtx_t kalloc_lock;
+
+#define kalloc_spin_lock()     lck_mtx_lock_spin(&kalloc_lock)
+#define kalloc_unlock()                lck_mtx_unlock(&kalloc_lock)
+
+

 /* OSMalloc local data declarations */
 static
 queue_head_t    OSMalloc_tag_list;
 
 /* OSMalloc local data declarations */
 static
 queue_head_t    OSMalloc_tag_list;
 

-decl_simple_lock_data(static,OSMalloc_tag_lock)
+lck_grp_t *OSMalloc_tag_lck_grp;
+lck_mtx_t OSMalloc_tag_lock;
+
+#define OSMalloc_tag_spin_lock()       lck_mtx_lock_spin(&OSMalloc_tag_lock)
+#define OSMalloc_tag_unlock()          lck_mtx_unlock(&OSMalloc_tag_lock)
+

 
 /* OSMalloc forward declarations */
 void OSMalloc_init(void);
 
 /* OSMalloc forward declarations */
 void OSMalloc_init(void);


@@ -225,20 +381,105 @@ kalloc_init(
 
        /*
         *      Allocate a zone for each size we are going to handle.
 
        /*
         *      Allocate a zone for each size we are going to handle.

-        *      We specify non-paged memory.
+        *      We specify non-paged memory.  Don't charge the caller
+        *      for the allocation, as we aren't sure how the memory
+        *      will be handled.

         */
         */

-       for (i = 0, size = 1; size < kalloc_max; i++, size <<= 1) {
-               if (size < KALLOC_MINSIZE) {
-                       k_zone[i] = NULL;
-                       continue;
-               }
-               if (size == KALLOC_MINSIZE) {
-                       first_k_zone = i;
-               }
+       for (i = 0; (size = k_zone_size[i]) < kalloc_max; i++) {

                k_zone[i] = zinit(size, k_zone_max[i] * size, size,
                                  k_zone_name[i]);
                k_zone[i] = zinit(size, k_zone_max[i] * size, size,
                                  k_zone_name[i]);

+               zone_change(k_zone[i], Z_CALLERACCT, FALSE);

        }
        }

+
+       /*
+        * Build the Direct LookUp Table for small allocations
+        */
+       for (i = 0, size = 0; i <= N_K_ZDLUT; i++, size += KALLOC_MINALIGN) {
+               int zindex = 0;
+
+               while ((vm_size_t)k_zone_size[zindex] < size)
+                       zindex++;
+
+               if (i == N_K_ZDLUT) {
+                       k_zindex_start = zindex;
+                       break;
+               }
+               k_zone_dlut[i] = (int8_t)zindex;
+       }
+
+#ifdef KALLOC_DEBUG
+       printf("kalloc_init: k_zindex_start %d\n", k_zindex_start);
+
+       /*
+        * Do a quick synthesis to see how well/badly we can
+        * find-a-zone for a given size.
+        * Useful when debugging/tweaking the array of zone sizes.
+        * Cache misses probably more critical than compare-branches!
+        */
+       for (i = 0; i < (int)N_K_ZONE; i++) {
+               vm_size_t testsize = (vm_size_t)k_zone_size[i] - 1;
+               int compare = 0;
+               int zindex;
+
+               if (testsize < MAX_SIZE_ZDLUT) {
+                       compare += 1;   /* 'if' (T) */
+
+                       long dindex = INDEX_ZDLUT(testsize);
+                       zindex = (int)k_zone_dlut[dindex];
+
+               } else if (testsize < kalloc_max_prerounded) {
+
+                       compare += 2;   /* 'if' (F), 'if' (T) */
+
+                       zindex = k_zindex_start;
+                       while ((vm_size_t)k_zone_size[zindex] < testsize) {
+                               zindex++;
+                               compare++;      /* 'while' (T) */
+                       }
+                       compare++;      /* 'while' (F) */
+               } else
+                       break;  /* not zone-backed */
+
+               zone_t z = k_zone[zindex];
+               printf("kalloc_init: req size %4lu: %11s took %d compare%s\n",
+                   (unsigned long)testsize, z->zone_name, compare,
+                   compare == 1 ? "" : "s");
+       }
+#endif
+       kalloc_lck_grp = lck_grp_alloc_init("kalloc.large", LCK_GRP_ATTR_NULL);
+       lck_mtx_init(&kalloc_lock, kalloc_lck_grp, LCK_ATTR_NULL);

        OSMalloc_init();
        OSMalloc_init();

+#ifdef MUTEX_ZONE      
+       lck_mtx_zone = zinit(sizeof(struct _lck_mtx_), 1024*256, 4096, "lck_mtx");
+#endif 
+}
+
+/*
+ * Given an allocation size, return the kalloc zone it belongs to.
+ * Direct LookUp Table variant.
+ */
+static __inline zone_t
+get_zone_dlut(vm_size_t size)
+{
+       long dindex = INDEX_ZDLUT(size);
+       int zindex = (int)k_zone_dlut[dindex];
+       return (k_zone[zindex]);
+}
+
+/* As above, but linear search k_zone_size[] for the next zone that fits. */
+
+static __inline zone_t
+get_zone_search(vm_size_t size, int zindex)
+{
+       assert(size < kalloc_max_prerounded);
+
+       while ((vm_size_t)k_zone_size[zindex] < size)
+               zindex++;
+
+       assert((unsigned)zindex < N_K_ZONE &&
+           (vm_size_t)k_zone_size[zindex] < kalloc_max);
+
+       return (k_zone[zindex]);

 }
 
 void *
 }
 
 void *


@@ -246,67 +487,69 @@ kalloc_canblock(
                vm_size_t       size,
                boolean_t       canblock)
 {
                vm_size_t       size,
                boolean_t       canblock)
 {

-       register int zindex;
-       register vm_size_t allocsize;
-       vm_map_t alloc_map = VM_MAP_NULL;
-
-       /*
-        * If size is too large for a zone, then use kmem_alloc.
-        * (We use kmem_alloc instead of kmem_alloc_kobject so that
-        * krealloc can use kmem_realloc.)
-        */
-
-       if (size >= kalloc_max_prerounded) {
+       zone_t z;
+
+       if (size < MAX_SIZE_ZDLUT)
+               z = get_zone_dlut(size);
+       else if (size < kalloc_max_prerounded)
+               z = get_zone_search(size, k_zindex_start);
+       else {
+               /*
+                * If size is too large for a zone, then use kmem_alloc.
+                * (We use kmem_alloc instead of kmem_alloc_kobject so that
+                * krealloc can use kmem_realloc.)
+                */
+               vm_map_t alloc_map;

                void *addr;
 
                /* kmem_alloc could block so we return if noblock */
                if (!canblock) {
                void *addr;
 
                /* kmem_alloc could block so we return if noblock */
                if (!canblock) {

-                 return(NULL);
+                       return(NULL);

                }
 
                }
 

-               if (size >= kalloc_kernmap_size) {
-                       volatile vm_offset_t prev_largest;
+               if (size >= kalloc_kernmap_size)

                        alloc_map = kernel_map;
                        alloc_map = kernel_map;

-                       /* Thread-safe version of the workaround for 4740071
-                        * (a double FREE())
-                        */
-                       do {
-                               prev_largest = kalloc_largest_allocated;
-                       } while ((size > prev_largest) && !OSCompareAndSwap((UInt32)prev_largest, (UInt32)size, (volatile UInt32 *) &kalloc_largest_allocated));
-               } else
+               else

                        alloc_map = kalloc_map;
 
                if (kmem_alloc(alloc_map, (vm_offset_t *)&addr, size) != KERN_SUCCESS) {
                        if (alloc_map != kernel_map) {
                                if (kmem_alloc(kernel_map, (vm_offset_t *)&addr, size) != KERN_SUCCESS)
                                        addr = NULL;
                        alloc_map = kalloc_map;
 
                if (kmem_alloc(alloc_map, (vm_offset_t *)&addr, size) != KERN_SUCCESS) {
                        if (alloc_map != kernel_map) {
                                if (kmem_alloc(kernel_map, (vm_offset_t *)&addr, size) != KERN_SUCCESS)
                                        addr = NULL;

-               }
+                       }

                        else
                                addr = NULL;
                }
 
                if (addr != NULL) {
                        else
                                addr = NULL;
                }
 
                if (addr != NULL) {

+                       kalloc_spin_lock();
+                       /*
+                        * Thread-safe version of the workaround for 4740071
+                        * (a double FREE())
+                        */
+                       if (size > kalloc_largest_allocated)
+                               kalloc_largest_allocated = size;
+

                        kalloc_large_inuse++;
                        kalloc_large_total += size;
                        kalloc_large_inuse++;
                        kalloc_large_total += size;

+                       kalloc_large_sum += size;

 
                        if (kalloc_large_total > kalloc_large_max)
                                kalloc_large_max = kalloc_large_total;
 
                        if (kalloc_large_total > kalloc_large_max)
                                kalloc_large_max = kalloc_large_total;

-               }
-               return(addr);
-       }

 
 

-       /* compute the size of the block that we will actually allocate */
+                       kalloc_unlock();

 
 

-       allocsize = KALLOC_MINSIZE;
-       zindex = first_k_zone;
-       while (allocsize < size) {
-               allocsize <<= 1;
-               zindex++;
+                       KALLOC_ZINFO_SALLOC(size);
+               }
+               return(addr);

        }
        }

-
-       /* allocate from the appropriate zone */
-       assert(allocsize < kalloc_max);
-       return(zalloc_canblock(k_zone[zindex], canblock));
+#ifdef KALLOC_DEBUG
+       if (size > z->elem_size)
+               panic("%s: z %p (%s) but requested size %lu", __func__,
+                   z, z->zone_name, (unsigned long)size);
+#endif
+       assert(size <= z->elem_size);
+       return (zalloc_canblock(z, canblock));

 }
 
 void *
 }
 
 void *


@@ -323,156 +566,6 @@ kalloc_noblock(
        return( kalloc_canblock(size, FALSE) );
 }
 
        return( kalloc_canblock(size, FALSE) );
 }
 

-
-void
-krealloc(
-       void            **addrp,
-       vm_size_t       old_size,
-       vm_size_t       new_size,
-       simple_lock_t   lock)
-{
-       register int zindex;
-       register vm_size_t allocsize;
-       void *naddr;
-       vm_map_t alloc_map = VM_MAP_NULL;
-
-       /* can only be used for increasing allocation size */
-
-       assert(new_size > old_size);
-
-       /* if old_size is zero, then we are simply allocating */
-
-       if (old_size == 0) {
-               simple_unlock(lock);
-               naddr = kalloc(new_size);
-               simple_lock(lock);
-               *addrp = naddr;
-               return;
-       }
-
-       /* if old block was kmem_alloc'd, then use kmem_realloc if necessary */
-
-       if (old_size >= kalloc_max_prerounded) {
-               if (old_size >=  kalloc_kernmap_size) 
-                       alloc_map = kernel_map;
-               else
-                       alloc_map = kalloc_map;
-
-               old_size = round_page(old_size);
-               new_size = round_page(new_size);
-               if (new_size > old_size) {
-
-                       if (KERN_SUCCESS != kmem_realloc(alloc_map, 
-                           (vm_offset_t)*addrp, old_size,
-                           (vm_offset_t *)&naddr, new_size))
-                               panic("krealloc: kmem_realloc");
-
-                       simple_lock(lock);
-                       *addrp = (void *) naddr;
-
-                       /* kmem_realloc() doesn't free old page range. */
-                       kmem_free(alloc_map, (vm_offset_t)*addrp, old_size);
-
-                       kalloc_large_total += (new_size - old_size);
-
-                       if (kalloc_large_total > kalloc_large_max)
-                               kalloc_large_max = kalloc_large_total;
-
-               }
-               return;
-       }
-
-       /* compute the size of the block that we actually allocated */
-
-       allocsize = KALLOC_MINSIZE;
-       zindex = first_k_zone;
-       while (allocsize < old_size) {
-               allocsize <<= 1;
-               zindex++;
-       }
-
-       /* if new size fits in old block, then return */
-
-       if (new_size <= allocsize) {
-               return;
-       }
-
-       /* if new size does not fit in zone, kmem_alloc it, else zalloc it */
-
-       simple_unlock(lock);
-       if (new_size >= kalloc_max_prerounded) {
-               if (new_size >=  kalloc_kernmap_size) 
-                       alloc_map = kernel_map;
-               else
-                       alloc_map = kalloc_map;
-               if (KERN_SUCCESS != kmem_alloc(alloc_map, 
-                   (vm_offset_t *)&naddr, new_size)) {
-                       panic("krealloc: kmem_alloc");
-                       simple_lock(lock);
-                       *addrp = NULL;
-                       return;
-               }
-               kalloc_large_inuse++;
-               kalloc_large_total += new_size;
-
-               if (kalloc_large_total > kalloc_large_max)
-                       kalloc_large_max = kalloc_large_total;
-       } else {
-               register int new_zindex;
-
-               allocsize <<= 1;
-               new_zindex = zindex + 1;
-               while (allocsize < new_size) {
-                       allocsize <<= 1;
-                       new_zindex++;
-               }
-               naddr = zalloc(k_zone[new_zindex]);
-       }
-       simple_lock(lock);
-
-       /* copy existing data */
-
-       bcopy((const char *)*addrp, (char *)naddr, old_size);
-
-       /* free old block, and return */
-
-       zfree(k_zone[zindex], *addrp);
-
-       /* set up new address */
-
-       *addrp = (void *) naddr;
-}
-
-
-void *
-kget(
-       vm_size_t       size)
-{
-       register int zindex;
-       register vm_size_t allocsize;
-
-       /* size must not be too large for a zone */
-
-       if (size >= kalloc_max_prerounded) {
-               /* This will never work, so we might as well panic */
-               panic("kget");
-       }
-
-       /* compute the size of the block that we will actually allocate */
-
-       allocsize = KALLOC_MINSIZE;
-       zindex = first_k_zone;
-       while (allocsize < size) {
-               allocsize <<= 1;
-               zindex++;
-       }
-
-       /* allocate from the appropriate zone */
-
-       assert(allocsize < kalloc_max);
-       return(zget(k_zone[zindex]));
-}
-

 volatile SInt32 kfree_nop_count = 0;
 
 void
 volatile SInt32 kfree_nop_count = 0;
 
 void


@@ -480,19 +573,23 @@ kfree(
        void            *data,
        vm_size_t       size)
 {
        void            *data,
        vm_size_t       size)
 {

-       register int zindex;
-       register vm_size_t freesize;
-       vm_map_t alloc_map = kernel_map;
+       zone_t z;
+
+       if (size < MAX_SIZE_ZDLUT)
+               z = get_zone_dlut(size);
+       else if (size < kalloc_max_prerounded)
+               z = get_zone_search(size, k_zindex_start);
+       else {
+               /* if size was too large for a zone, then use kmem_free */

 
 

-       /* if size was too large for a zone, then use kmem_free */
+               vm_map_t alloc_map = kernel_map;

 
 

-       if (size >= kalloc_max_prerounded) {

                if ((((vm_offset_t) data) >= kalloc_map_min) && (((vm_offset_t) data) <= kalloc_map_max))
                        alloc_map = kalloc_map;
                if (size > kalloc_largest_allocated) {
                                /*
                                 * work around double FREEs of small MALLOCs
                if ((((vm_offset_t) data) >= kalloc_map_min) && (((vm_offset_t) data) <= kalloc_map_max))
                        alloc_map = kalloc_map;
                if (size > kalloc_largest_allocated) {
                                /*
                                 * work around double FREEs of small MALLOCs

-                                * this use to end up being a nop
+                                * this used to end up being a nop

                                 * since the pointer being freed from an
                                 * alloc backed by the zalloc world could
                                 * never show up in the kalloc_map... however,
                                 * since the pointer being freed from an
                                 * alloc backed by the zalloc world could
                                 * never show up in the kalloc_map... however,


@@ -503,7 +600,7 @@ kfree(
                                 * the underlying allocation... that pointer ends up 
                                 * looking like a really big size on the 2nd FREE and
                                 * pushes the kfree into the kernel_map...  we
                                 * the underlying allocation... that pointer ends up 
                                 * looking like a really big size on the 2nd FREE and
                                 * pushes the kfree into the kernel_map...  we

-                                * end up removing a ton of virutal space before we panic
+                                * end up removing a ton of virtual space before we panic

                                 * this check causes us to ignore the kfree for a size
                                 * that must be 'bogus'... note that it might not be due
                                 * to the above scenario, but it would still be wrong and
                                 * this check causes us to ignore the kfree for a size
                                 * that must be 'bogus'... note that it might not be due
                                 * to the above scenario, but it would still be wrong and


@@ -515,25 +612,25 @@ kfree(
                }
                kmem_free(alloc_map, (vm_offset_t)data, size);
 
                }
                kmem_free(alloc_map, (vm_offset_t)data, size);
 

+               kalloc_spin_lock();
+

                kalloc_large_total -= size;
                kalloc_large_inuse--;
 
                kalloc_large_total -= size;
                kalloc_large_inuse--;
 

-               return;
-       }
-
-       /* compute the size of the block that we actually allocated from */
+               kalloc_unlock();

 
 

-       freesize = KALLOC_MINSIZE;
-       zindex = first_k_zone;
-       while (freesize < size) {
-               freesize <<= 1;
-               zindex++;
+               KALLOC_ZINFO_SFREE(size);
+               return;

        }
 
        /* free to the appropriate zone */
        }
 
        /* free to the appropriate zone */

-
-       assert(freesize < kalloc_max);
-       zfree(k_zone[zindex], data);
+#ifdef KALLOC_DEBUG
+       if (size > z->elem_size)
+               panic("%s: z %p (%s) but requested size %lu", __func__,
+                   z, z->zone_name, (unsigned long)size);
+#endif
+       assert(size <= z->elem_size);
+       zfree(z, data);

 }
 
 #ifdef MACH_BSD
 }
 
 #ifdef MACH_BSD


@@ -541,37 +638,40 @@ zone_t
 kalloc_zone(
        vm_size_t       size)
 {
 kalloc_zone(
        vm_size_t       size)
 {

-       register int zindex = 0;
-       register vm_size_t allocsize;
-
-       /* compute the size of the block that we will actually allocate */
-
-       allocsize = size;
-       if (size <= kalloc_max) {
-               allocsize = KALLOC_MINSIZE;
-               zindex = first_k_zone;
-               while (allocsize < size) {
-                       allocsize <<= 1;
-                       zindex++;
-               }
-               return (k_zone[zindex]);
-       }
+       if (size < MAX_SIZE_ZDLUT)
+               return (get_zone_dlut(size));
+       if (size <= kalloc_max)
+               return (get_zone_search(size, k_zindex_start));

        return (ZONE_NULL);
 }
 #endif
 
        return (ZONE_NULL);
 }
 #endif
 

+void
+kalloc_fake_zone_init(int zone_index)
+{
+       kalloc_fake_zone_index = zone_index;
+}

 
 void
 
 void

-kalloc_fake_zone_info(int *count, vm_size_t *cur_size, vm_size_t *max_size, vm_size_t *elem_size,
-                    vm_size_t *alloc_size, int *collectable, int *exhaustable)
+kalloc_fake_zone_info(int *count, 
+                     vm_size_t *cur_size, vm_size_t *max_size, vm_size_t *elem_size, vm_size_t *alloc_size,
+                     uint64_t *sum_size, int *collectable, int *exhaustable, int *caller_acct)

 {
        *count      = kalloc_large_inuse;
        *cur_size   = kalloc_large_total;
        *max_size   = kalloc_large_max;
 {
        *count      = kalloc_large_inuse;
        *cur_size   = kalloc_large_total;
        *max_size   = kalloc_large_max;

-       *elem_size  = kalloc_large_total / kalloc_large_inuse;
-       *alloc_size = kalloc_large_total / kalloc_large_inuse;
+
+       if (kalloc_large_inuse) {
+               *elem_size  = kalloc_large_total / kalloc_large_inuse;
+               *alloc_size = kalloc_large_total / kalloc_large_inuse;
+       } else {
+               *elem_size  = 0;
+               *alloc_size = 0;
+       }
+       *sum_size   = kalloc_large_sum;

        *collectable = 0;
        *exhaustable = 0;
        *collectable = 0;
        *exhaustable = 0;

+       *caller_acct = 0;

 }
 
 
 }
 
 


@@ -580,7 +680,9 @@ OSMalloc_init(
        void)
 {
        queue_init(&OSMalloc_tag_list);
        void)
 {
        queue_init(&OSMalloc_tag_list);

-       simple_lock_init(&OSMalloc_tag_lock, 0);
+
+       OSMalloc_tag_lck_grp = lck_grp_alloc_init("OSMalloc_tag", LCK_GRP_ATTR_NULL);
+       lck_mtx_init(&OSMalloc_tag_lock, OSMalloc_tag_lck_grp, LCK_ATTR_NULL);

 }
 
 OSMallocTag
 }
 
 OSMallocTag


@@ -601,9 +703,9 @@ OSMalloc_Tagalloc(
 
        strncpy(OSMTag->OSMT_name, str, OSMT_MAX_NAME);
 
 
        strncpy(OSMTag->OSMT_name, str, OSMT_MAX_NAME);
 

-       simple_lock(&OSMalloc_tag_lock);
+       OSMalloc_tag_spin_lock();

        enqueue_tail(&OSMalloc_tag_list, (queue_entry_t)OSMTag);
        enqueue_tail(&OSMalloc_tag_list, (queue_entry_t)OSMTag);

-       simple_unlock(&OSMalloc_tag_lock);
+       OSMalloc_tag_unlock();

        OSMTag->OSMT_state = OSMT_VALID;
        return(OSMTag);
 }
        OSMTag->OSMT_state = OSMT_VALID;
        return(OSMTag);
 }


@@ -613,7 +715,7 @@ OSMalloc_Tagref(
         OSMallocTag            tag)
 {
        if (!((tag->OSMT_state & OSMT_VALID_MASK) == OSMT_VALID)) 
         OSMallocTag            tag)
 {
        if (!((tag->OSMT_state & OSMT_VALID_MASK) == OSMT_VALID)) 

-               panic("OSMalloc_Tagref(): bad state 0x%08X\n",tag->OSMT_state);
+               panic("OSMalloc_Tagref():'%s' has bad state 0x%08X\n", tag->OSMT_name, tag->OSMT_state);

 
        (void)hw_atomic_add(&tag->OSMT_refcnt, 1);
 }
 
        (void)hw_atomic_add(&tag->OSMT_refcnt, 1);
 }


@@ -623,16 +725,16 @@ OSMalloc_Tagrele(
         OSMallocTag            tag)
 {
        if (!((tag->OSMT_state & OSMT_VALID_MASK) == OSMT_VALID))
         OSMallocTag            tag)
 {
        if (!((tag->OSMT_state & OSMT_VALID_MASK) == OSMT_VALID))

-               panic("OSMalloc_Tagref(): bad state 0x%08X\n",tag->OSMT_state);
+               panic("OSMalloc_Tagref():'%s' has bad state 0x%08X\n", tag->OSMT_name, tag->OSMT_state);

 
        if (hw_atomic_sub(&tag->OSMT_refcnt, 1) == 0) {
                if (hw_compare_and_store(OSMT_VALID|OSMT_RELEASED, OSMT_VALID|OSMT_RELEASED, &tag->OSMT_state)) {
 
        if (hw_atomic_sub(&tag->OSMT_refcnt, 1) == 0) {
                if (hw_compare_and_store(OSMT_VALID|OSMT_RELEASED, OSMT_VALID|OSMT_RELEASED, &tag->OSMT_state)) {

-                       simple_lock(&OSMalloc_tag_lock);
+                       OSMalloc_tag_spin_lock();

                        (void)remque((queue_entry_t)tag);
                        (void)remque((queue_entry_t)tag);

-                       simple_unlock(&OSMalloc_tag_lock);
+                       OSMalloc_tag_unlock();

                        kfree((void*)tag, sizeof(*tag));
                } else
                        kfree((void*)tag, sizeof(*tag));
                } else

-                       panic("OSMalloc_Tagrele(): refcnt 0\n");
+                       panic("OSMalloc_Tagrele():'%s' has refcnt 0\n", tag->OSMT_name);

        }
 }
 
        }
 }
 


@@ -641,12 +743,12 @@ OSMalloc_Tagfree(
         OSMallocTag            tag)
 {
        if (!hw_compare_and_store(OSMT_VALID, OSMT_VALID|OSMT_RELEASED, &tag->OSMT_state))
         OSMallocTag            tag)
 {
        if (!hw_compare_and_store(OSMT_VALID, OSMT_VALID|OSMT_RELEASED, &tag->OSMT_state))

-               panic("OSMalloc_Tagfree(): bad state 0x%08X\n", tag->OSMT_state);
+               panic("OSMalloc_Tagfree():'%s' has bad state 0x%08X \n", tag->OSMT_name, tag->OSMT_state);

 
        if (hw_atomic_sub(&tag->OSMT_refcnt, 1) == 0) {
 
        if (hw_atomic_sub(&tag->OSMT_refcnt, 1) == 0) {

-               simple_lock(&OSMalloc_tag_lock);
+               OSMalloc_tag_spin_lock();

                (void)remque((queue_entry_t)tag);
                (void)remque((queue_entry_t)tag);

-               simple_unlock(&OSMalloc_tag_lock);
+               OSMalloc_tag_unlock();

                kfree((void*)tag, sizeof(*tag));
        }
 }
                kfree((void*)tag, sizeof(*tag));
        }
 }


@@ -721,7 +823,7 @@ OSFree(
            && (size & ~PAGE_MASK)) {
                kmem_free(kernel_map, (vm_offset_t)addr, size);
        } else
            && (size & ~PAGE_MASK)) {
                kmem_free(kernel_map, (vm_offset_t)addr, size);
        } else

-               kfree((void*)addr, size);
+               kfree((void *)addr, size);

 
        OSMalloc_Tagrele(tag);
 }
 
        OSMalloc_Tagrele(tag);
 }