4abf4760a9d0c5937bcdd8ce735da07897c74471
[dragonfly.git] / sys / kern / kern_slaballoc.c
1 /*
2  * (MPSAFE)
3  *
4  * KERN_SLABALLOC.C     - Kernel SLAB memory allocator
5  * 
6  * Copyright (c) 2003,2004,2010 The DragonFly Project.  All rights reserved.
7  * 
8  * This code is derived from software contributed to The DragonFly Project
9  * by Matthew Dillon <dillon@backplane.com>
10  * 
11  * Redistribution and use in source and binary forms, with or without
12  * modification, are permitted provided that the following conditions
13  * are met:
14  * 
15  * 1. Redistributions of source code must retain the above copyright
16  *    notice, this list of conditions and the following disclaimer.
17  * 2. Redistributions in binary form must reproduce the above copyright
18  *    notice, this list of conditions and the following disclaimer in
19  *    the documentation and/or other materials provided with the
20  *    distribution.
21  * 3. Neither the name of The DragonFly Project nor the names of its
22  *    contributors may be used to endorse or promote products derived
23  *    from this software without specific, prior written permission.
24  * 
25  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
26  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
27  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
28  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
29  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
30  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
31  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
32  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
33  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
34  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
35  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
36  * SUCH DAMAGE.
37  *
38  * This module implements a slab allocator drop-in replacement for the
39  * kernel malloc().
40  *
41  * A slab allocator reserves a ZONE for each chunk size, then lays the
42  * chunks out in an array within the zone.  Allocation and deallocation
43  * is nearly instantanious, and fragmentation/overhead losses are limited
44  * to a fixed worst-case amount.
45  *
46  * The downside of this slab implementation is in the chunk size
47  * multiplied by the number of zones.  ~80 zones * 128K = 10MB of VM per cpu.
48  * In a kernel implementation all this memory will be physical so
49  * the zone size is adjusted downward on machines with less physical
50  * memory.  The upside is that overhead is bounded... this is the *worst*
51  * case overhead.
52  *
53  * Slab management is done on a per-cpu basis and no locking or mutexes
54  * are required, only a critical section.  When one cpu frees memory
55  * belonging to another cpu's slab manager an asynchronous IPI message
56  * will be queued to execute the operation.   In addition, both the
57  * high level slab allocator and the low level zone allocator optimize
58  * M_ZERO requests, and the slab allocator does not have to pre initialize
59  * the linked list of chunks.
60  *
61  * XXX Balancing is needed between cpus.  Balance will be handled through
62  * asynchronous IPIs primarily by reassigning the z_Cpu ownership of chunks.
63  *
64  * XXX If we have to allocate a new zone and M_USE_RESERVE is set, use of
65  * the new zone should be restricted to M_USE_RESERVE requests only.
66  *
67  *      Alloc Size      Chunking        Number of zones
68  *      0-127           8               16
69  *      128-255         16              8
70  *      256-511         32              8
71  *      512-1023        64              8
72  *      1024-2047       128             8
73  *      2048-4095       256             8
74  *      4096-8191       512             8
75  *      8192-16383      1024            8
76  *      16384-32767     2048            8
77  *      (if PAGE_SIZE is 4K the maximum zone allocation is 16383)
78  *
79  *      Allocations >= ZoneLimit go directly to kmem.
80  *
81  *                      API REQUIREMENTS AND SIDE EFFECTS
82  *
83  *    To operate as a drop-in replacement to the FreeBSD-4.x malloc() we
84  *    have remained compatible with the following API requirements:
85  *
86  *    + small power-of-2 sized allocations are power-of-2 aligned (kern_tty)
87  *    + all power-of-2 sized allocations are power-of-2 aligned (twe)
88  *    + malloc(0) is allowed and returns non-NULL (ahc driver)
89  *    + ability to allocate arbitrarily large chunks of memory
90  */
91
92 #include "opt_vm.h"
93
94 #include <sys/param.h>
95 #include <sys/systm.h>
96 #include <sys/kernel.h>
97 #include <sys/slaballoc.h>
98 #include <sys/mbuf.h>
99 #include <sys/vmmeter.h>
100 #include <sys/lock.h>
101 #include <sys/thread.h>
102 #include <sys/globaldata.h>
103 #include <sys/sysctl.h>
104 #include <sys/ktr.h>
105
106 #include <vm/vm.h>
107 #include <vm/vm_param.h>
108 #include <vm/vm_kern.h>
109 #include <vm/vm_extern.h>
110 #include <vm/vm_object.h>
111 #include <vm/pmap.h>
112 #include <vm/vm_map.h>
113 #include <vm/vm_page.h>
114 #include <vm/vm_pageout.h>
115
116 #include <machine/cpu.h>
117
118 #include <sys/thread2.h>
119
120 #define arysize(ary)    (sizeof(ary)/sizeof((ary)[0]))
121
122 #define btokup(z)       (&pmap_kvtom((vm_offset_t)(z))->ku_pagecnt)
123
124 #define MEMORY_STRING   "ptr=%p type=%p size=%d flags=%04x"
125 #define MEMORY_ARG_SIZE (sizeof(void *) * 2 + sizeof(unsigned long) +   \
126                         sizeof(int))
127
128 #if !defined(KTR_MEMORY)
129 #define KTR_MEMORY      KTR_ALL
130 #endif
131 KTR_INFO_MASTER(memory);
132 KTR_INFO(KTR_MEMORY, memory, malloc_beg, 0, "malloc begin", 0);
133 KTR_INFO(KTR_MEMORY, memory, malloc_end, 1, MEMORY_STRING, MEMORY_ARG_SIZE);
134 KTR_INFO(KTR_MEMORY, memory, free_zero, 2, MEMORY_STRING, MEMORY_ARG_SIZE);
135 KTR_INFO(KTR_MEMORY, memory, free_ovsz, 3, MEMORY_STRING, MEMORY_ARG_SIZE);
136 KTR_INFO(KTR_MEMORY, memory, free_ovsz_delayed, 4, MEMORY_STRING, MEMORY_ARG_SIZE);
137 KTR_INFO(KTR_MEMORY, memory, free_chunk, 5, MEMORY_STRING, MEMORY_ARG_SIZE);
138 #ifdef SMP
139 KTR_INFO(KTR_MEMORY, memory, free_request, 6, MEMORY_STRING, MEMORY_ARG_SIZE);
140 KTR_INFO(KTR_MEMORY, memory, free_rem_beg, 7, MEMORY_STRING, MEMORY_ARG_SIZE);
141 KTR_INFO(KTR_MEMORY, memory, free_rem_end, 8, MEMORY_STRING, MEMORY_ARG_SIZE);
142 #endif
143 KTR_INFO(KTR_MEMORY, memory, free_beg, 9, "free begin", 0);
144 KTR_INFO(KTR_MEMORY, memory, free_end, 10, "free end", 0);
145
146 #define logmemory(name, ptr, type, size, flags)                         \
147         KTR_LOG(memory_ ## name, ptr, type, size, flags)
148 #define logmemory_quick(name)                                           \
149         KTR_LOG(memory_ ## name)
150
151 /*
152  * Fixed globals (not per-cpu)
153  */
154 static int ZoneSize;
155 static int ZoneLimit;
156 static int ZonePageCount;
157 static uintptr_t ZoneMask;
158 static int ZoneBigAlloc;                /* in KB */
159 static int ZoneGenAlloc;                /* in KB */
160 struct malloc_type *kmemstatistics;     /* exported to vmstat */
161 static int32_t weirdary[16];
162
163 static void *kmem_slab_alloc(vm_size_t bytes, vm_offset_t align, int flags);
164 static void kmem_slab_free(void *ptr, vm_size_t bytes);
165
166 #if defined(INVARIANTS)
167 static void chunk_mark_allocated(SLZone *z, void *chunk);
168 static void chunk_mark_free(SLZone *z, void *chunk);
169 #else
170 #define chunk_mark_allocated(z, chunk)
171 #define chunk_mark_free(z, chunk)
172 #endif
173
174 /*
175  * Misc constants.  Note that allocations that are exact multiples of 
176  * PAGE_SIZE, or exceed the zone limit, fall through to the kmem module.
177  * IN_SAME_PAGE_MASK is used to sanity-check the per-page free lists.
178  */
179 #define MIN_CHUNK_SIZE          8               /* in bytes */
180 #define MIN_CHUNK_MASK          (MIN_CHUNK_SIZE - 1)
181 #define ZONE_RELS_THRESH        2               /* threshold number of zones */
182 #define IN_SAME_PAGE_MASK       (~(intptr_t)PAGE_MASK | MIN_CHUNK_MASK)
183
184 /*
185  * The WEIRD_ADDR is used as known text to copy into free objects to
186  * try to create deterministic failure cases if the data is accessed after
187  * free.
188  */    
189 #define WEIRD_ADDR      0xdeadc0de
190 #define MAX_COPY        sizeof(weirdary)
191 #define ZERO_LENGTH_PTR ((void *)-8)
192
193 /*
194  * Misc global malloc buckets
195  */
196
197 MALLOC_DEFINE(M_CACHE, "cache", "Various Dynamically allocated caches");
198 MALLOC_DEFINE(M_DEVBUF, "devbuf", "device driver memory");
199 MALLOC_DEFINE(M_TEMP, "temp", "misc temporary data buffers");
200  
201 MALLOC_DEFINE(M_IP6OPT, "ip6opt", "IPv6 options");
202 MALLOC_DEFINE(M_IP6NDP, "ip6ndp", "IPv6 Neighbor Discovery");
203
204 /*
205  * Initialize the slab memory allocator.  We have to choose a zone size based
206  * on available physical memory.  We choose a zone side which is approximately
207  * 1/1024th of our memory, so if we have 128MB of ram we have a zone size of
208  * 128K.  The zone size is limited to the bounds set in slaballoc.h
209  * (typically 32K min, 128K max). 
210  */
211 static void kmeminit(void *dummy);
212
213 char *ZeroPage;
214
215 SYSINIT(kmem, SI_BOOT1_ALLOCATOR, SI_ORDER_FIRST, kmeminit, NULL)
216
217 #ifdef INVARIANTS
218 /*
219  * If enabled any memory allocated without M_ZERO is initialized to -1.
220  */
221 static int  use_malloc_pattern;
222 SYSCTL_INT(_debug, OID_AUTO, use_malloc_pattern, CTLFLAG_RW,
223                 &use_malloc_pattern, 0, "");
224 #endif
225
226 SYSCTL_INT(_kern, OID_AUTO, zone_big_alloc, CTLFLAG_RD, &ZoneBigAlloc, 0, "");
227 SYSCTL_INT(_kern, OID_AUTO, zone_gen_alloc, CTLFLAG_RD, &ZoneGenAlloc, 0, "");
228
229 static void
230 kmeminit(void *dummy)
231 {
232     size_t limsize;
233     int usesize;
234     int i;
235
236     limsize = (size_t)vmstats.v_page_count * PAGE_SIZE;
237     if (limsize > KvaSize)
238         limsize = KvaSize;
239
240     usesize = (int)(limsize / 1024);    /* convert to KB */
241
242     ZoneSize = ZALLOC_MIN_ZONE_SIZE;
243     while (ZoneSize < ZALLOC_MAX_ZONE_SIZE && (ZoneSize << 1) < usesize)
244         ZoneSize <<= 1;
245     ZoneLimit = ZoneSize / 4;
246     if (ZoneLimit > ZALLOC_ZONE_LIMIT)
247         ZoneLimit = ZALLOC_ZONE_LIMIT;
248     ZoneMask = ~(uintptr_t)(ZoneSize - 1);
249     ZonePageCount = ZoneSize / PAGE_SIZE;
250
251     for (i = 0; i < arysize(weirdary); ++i)
252         weirdary[i] = WEIRD_ADDR;
253
254     ZeroPage = kmem_slab_alloc(PAGE_SIZE, PAGE_SIZE, M_WAITOK|M_ZERO);
255
256     if (bootverbose)
257         kprintf("Slab ZoneSize set to %dKB\n", ZoneSize / 1024);
258 }
259
260 /*
261  * Initialize a malloc type tracking structure.
262  */
263 void
264 malloc_init(void *data)
265 {
266     struct malloc_type *type = data;
267     size_t limsize;
268
269     if (type->ks_magic != M_MAGIC)
270         panic("malloc type lacks magic");
271                                            
272     if (type->ks_limit != 0)
273         return;
274
275     if (vmstats.v_page_count == 0)
276         panic("malloc_init not allowed before vm init");
277
278     limsize = (size_t)vmstats.v_page_count * PAGE_SIZE;
279     if (limsize > KvaSize)
280         limsize = KvaSize;
281     type->ks_limit = limsize / 10;
282
283     type->ks_next = kmemstatistics;
284     kmemstatistics = type;
285 }
286
287 void
288 malloc_uninit(void *data)
289 {
290     struct malloc_type *type = data;
291     struct malloc_type *t;
292 #ifdef INVARIANTS
293     int i;
294     long ttl;
295 #endif
296
297     if (type->ks_magic != M_MAGIC)
298         panic("malloc type lacks magic");
299
300     if (vmstats.v_page_count == 0)
301         panic("malloc_uninit not allowed before vm init");
302
303     if (type->ks_limit == 0)
304         panic("malloc_uninit on uninitialized type");
305
306 #ifdef SMP
307     /* Make sure that all pending kfree()s are finished. */
308     lwkt_synchronize_ipiqs("muninit");
309 #endif
310
311 #ifdef INVARIANTS
312     /*
313      * memuse is only correct in aggregation.  Due to memory being allocated
314      * on one cpu and freed on another individual array entries may be 
315      * negative or positive (canceling each other out).
316      */
317     for (i = ttl = 0; i < ncpus; ++i)
318         ttl += type->ks_memuse[i];
319     if (ttl) {
320         kprintf("malloc_uninit: %ld bytes of '%s' still allocated on cpu %d\n",
321             ttl, type->ks_shortdesc, i);
322     }
323 #endif
324     if (type == kmemstatistics) {
325         kmemstatistics = type->ks_next;
326     } else {
327         for (t = kmemstatistics; t->ks_next != NULL; t = t->ks_next) {
328             if (t->ks_next == type) {
329                 t->ks_next = type->ks_next;
330                 break;
331             }
332         }
333     }
334     type->ks_next = NULL;
335     type->ks_limit = 0;
336 }
337
338 /*
339  * Increase the kmalloc pool limit for the specified pool.  No changes
340  * are the made if the pool would shrink.
341  */
342 void
343 kmalloc_raise_limit(struct malloc_type *type, size_t bytes)
344 {
345     if (type->ks_limit == 0)
346         malloc_init(type);
347     if (bytes == 0)
348         bytes = KvaSize;
349     if (type->ks_limit < bytes)
350         type->ks_limit = bytes;
351 }
352
353 /*
354  * Dynamically create a malloc pool.  This function is a NOP if *typep is
355  * already non-NULL.
356  */
357 void
358 kmalloc_create(struct malloc_type **typep, const char *descr)
359 {
360         struct malloc_type *type;
361
362         if (*typep == NULL) {
363                 type = kmalloc(sizeof(*type), M_TEMP, M_WAITOK | M_ZERO);
364                 type->ks_magic = M_MAGIC;
365                 type->ks_shortdesc = descr;
366                 malloc_init(type);
367                 *typep = type;
368         }
369 }
370
371 /*
372  * Destroy a dynamically created malloc pool.  This function is a NOP if
373  * the pool has already been destroyed.
374  */
375 void
376 kmalloc_destroy(struct malloc_type **typep)
377 {
378         if (*typep != NULL) {
379                 malloc_uninit(*typep);
380                 kfree(*typep, M_TEMP);
381                 *typep = NULL;
382         }
383 }
384
385 /*
386  * Calculate the zone index for the allocation request size and set the
387  * allocation request size to that particular zone's chunk size.
388  */
389 static __inline int
390 zoneindex(unsigned long *bytes)
391 {
392     unsigned int n = (unsigned int)*bytes;      /* unsigned for shift opt */
393     if (n < 128) {
394         *bytes = n = (n + 7) & ~7;
395         return(n / 8 - 1);              /* 8 byte chunks, 16 zones */
396     }
397     if (n < 256) {
398         *bytes = n = (n + 15) & ~15;
399         return(n / 16 + 7);
400     }
401     if (n < 8192) {
402         if (n < 512) {
403             *bytes = n = (n + 31) & ~31;
404             return(n / 32 + 15);
405         }
406         if (n < 1024) {
407             *bytes = n = (n + 63) & ~63;
408             return(n / 64 + 23);
409         } 
410         if (n < 2048) {
411             *bytes = n = (n + 127) & ~127;
412             return(n / 128 + 31);
413         }
414         if (n < 4096) {
415             *bytes = n = (n + 255) & ~255;
416             return(n / 256 + 39);
417         }
418         *bytes = n = (n + 511) & ~511;
419         return(n / 512 + 47);
420     }
421 #if ZALLOC_ZONE_LIMIT > 8192
422     if (n < 16384) {
423         *bytes = n = (n + 1023) & ~1023;
424         return(n / 1024 + 55);
425     }
426 #endif
427 #if ZALLOC_ZONE_LIMIT > 16384
428     if (n < 32768) {
429         *bytes = n = (n + 2047) & ~2047;
430         return(n / 2048 + 63);
431     }
432 #endif
433     panic("Unexpected byte count %d", n);
434     return(0);
435 }
436
437 /*
438  * kmalloc()    (SLAB ALLOCATOR)
439  *
440  *      Allocate memory via the slab allocator.  If the request is too large,
441  *      or if it page-aligned beyond a certain size, we fall back to the
442  *      KMEM subsystem.  A SLAB tracking descriptor must be specified, use
443  *      &SlabMisc if you don't care.
444  *
445  *      M_RNOWAIT       - don't block.
446  *      M_NULLOK        - return NULL instead of blocking.
447  *      M_ZERO          - zero the returned memory.
448  *      M_USE_RESERVE   - allow greater drawdown of the free list
449  *      M_USE_INTERRUPT_RESERVE - allow the freelist to be exhausted
450  *
451  * MPSAFE
452  */
453 void *
454 kmalloc(unsigned long size, struct malloc_type *type, int flags)
455 {
456     SLZone *z;
457     SLChunk *chunk;
458 #ifdef SMP
459     SLChunk *bchunk;
460 #endif
461     SLGlobalData *slgd;
462     struct globaldata *gd;
463     int zi;
464 #ifdef INVARIANTS
465     int i;
466 #endif
467
468     logmemory_quick(malloc_beg);
469     gd = mycpu;
470     slgd = &gd->gd_slab;
471
472     /*
473      * XXX silly to have this in the critical path.
474      */
475     if (type->ks_limit == 0) {
476         crit_enter();
477         if (type->ks_limit == 0)
478             malloc_init(type);
479         crit_exit();
480     }
481     ++type->ks_calls;
482
483     /*
484      * Handle the case where the limit is reached.  Panic if we can't return
485      * NULL.  The original malloc code looped, but this tended to
486      * simply deadlock the computer.
487      *
488      * ks_loosememuse is an up-only limit that is NOT MP-synchronized, used
489      * to determine if a more complete limit check should be done.  The
490      * actual memory use is tracked via ks_memuse[cpu].
491      */
492     while (type->ks_loosememuse >= type->ks_limit) {
493         int i;
494         long ttl;
495
496         for (i = ttl = 0; i < ncpus; ++i)
497             ttl += type->ks_memuse[i];
498         type->ks_loosememuse = ttl;     /* not MP synchronized */
499         if ((ssize_t)ttl < 0)           /* deal with occassional race */
500                 ttl = 0;
501         if (ttl >= type->ks_limit) {
502             if (flags & M_NULLOK) {
503                 logmemory(malloc_end, NULL, type, size, flags);
504                 return(NULL);
505             }
506             panic("%s: malloc limit exceeded", type->ks_shortdesc);
507         }
508     }
509
510     /*
511      * Handle the degenerate size == 0 case.  Yes, this does happen.
512      * Return a special pointer.  This is to maintain compatibility with
513      * the original malloc implementation.  Certain devices, such as the
514      * adaptec driver, not only allocate 0 bytes, they check for NULL and
515      * also realloc() later on.  Joy.
516      */
517     if (size == 0) {
518         logmemory(malloc_end, ZERO_LENGTH_PTR, type, size, flags);
519         return(ZERO_LENGTH_PTR);
520     }
521
522     /*
523      * Handle hysteresis from prior frees here in malloc().  We cannot
524      * safely manipulate the kernel_map in free() due to free() possibly
525      * being called via an IPI message or from sensitive interrupt code.
526      *
527      * NOTE: ku_pagecnt must be cleared before we free the slab or we
528      *       might race another cpu allocating the kva and setting
529      *       ku_pagecnt.
530      */
531     while (slgd->NFreeZones > ZONE_RELS_THRESH && (flags & M_RNOWAIT) == 0) {
532         crit_enter();
533         if (slgd->NFreeZones > ZONE_RELS_THRESH) {      /* crit sect race */
534             int *kup;
535
536             z = slgd->FreeZones;
537             slgd->FreeZones = z->z_Next;
538             --slgd->NFreeZones;
539             kup = btokup(z);
540             *kup = 0;
541             kmem_slab_free(z, ZoneSize);        /* may block */
542             atomic_add_int(&ZoneGenAlloc, -(int)ZoneSize / 1024);
543         }
544         crit_exit();
545     }
546
547     /*
548      * XXX handle oversized frees that were queued from kfree().
549      */
550     while (slgd->FreeOvZones && (flags & M_RNOWAIT) == 0) {
551         crit_enter();
552         if ((z = slgd->FreeOvZones) != NULL) {
553             vm_size_t tsize;
554
555             KKASSERT(z->z_Magic == ZALLOC_OVSZ_MAGIC);
556             slgd->FreeOvZones = z->z_Next;
557             tsize = z->z_ChunkSize;
558             kmem_slab_free(z, tsize);   /* may block */
559             atomic_add_int(&ZoneBigAlloc, -(int)tsize / 1024);
560         }
561         crit_exit();
562     }
563
564     /*
565      * Handle large allocations directly.  There should not be very many of
566      * these so performance is not a big issue.
567      *
568      * The backend allocator is pretty nasty on a SMP system.   Use the
569      * slab allocator for one and two page-sized chunks even though we lose
570      * some efficiency.  XXX maybe fix mmio and the elf loader instead.
571      */
572     if (size >= ZoneLimit || ((size & PAGE_MASK) == 0 && size > PAGE_SIZE*2)) {
573         int *kup;
574
575         size = round_page(size);
576         chunk = kmem_slab_alloc(size, PAGE_SIZE, flags);
577         if (chunk == NULL) {
578             logmemory(malloc_end, NULL, type, size, flags);
579             return(NULL);
580         }
581         atomic_add_int(&ZoneBigAlloc, (int)size / 1024);
582         flags &= ~M_ZERO;       /* result already zero'd if M_ZERO was set */
583         flags |= M_PASSIVE_ZERO;
584         kup = btokup(chunk);
585         *kup = size / PAGE_SIZE;
586         crit_enter();
587         goto done;
588     }
589
590     /*
591      * Attempt to allocate out of an existing zone.  First try the free list,
592      * then allocate out of unallocated space.  If we find a good zone move
593      * it to the head of the list so later allocations find it quickly
594      * (we might have thousands of zones in the list).
595      *
596      * Note: zoneindex() will panic of size is too large.
597      */
598     zi = zoneindex(&size);
599     KKASSERT(zi < NZONES);
600     crit_enter();
601
602     if ((z = slgd->ZoneAry[zi]) != NULL) {
603         /*
604          * Locate a chunk - we have to have at least one.  If this is the
605          * last chunk go ahead and do the work to retrieve chunks freed
606          * from remote cpus, and if the zone is still empty move it off
607          * the ZoneAry.
608          */
609         if (--z->z_NFree <= 0) {
610             KKASSERT(z->z_NFree == 0);
611
612 #ifdef SMP
613             /*
614              * WARNING! This code competes with other cpus.  It is ok
615              * for us to not drain RChunks here but we might as well, and
616              * it is ok if more accumulate after we're done.
617              *
618              * Set RSignal before pulling rchunks off, indicating that we
619              * will be moving ourselves off of the ZoneAry.  Remote ends will
620              * read RSignal before putting rchunks on thus interlocking
621              * their IPI signaling.
622              */
623             if (z->z_RChunks == NULL)
624                 atomic_swap_int(&z->z_RSignal, 1);
625
626             while ((bchunk = z->z_RChunks) != NULL) {
627                 cpu_ccfence();
628                 if (atomic_cmpset_ptr(&z->z_RChunks, bchunk, NULL)) {
629                     *z->z_LChunksp = bchunk;
630                     while (bchunk) {
631                         chunk_mark_free(z, bchunk);
632                         z->z_LChunksp = &bchunk->c_Next;
633                         bchunk = bchunk->c_Next;
634                         ++z->z_NFree;
635                     }
636                     break;
637                 }
638             }
639 #endif
640             /*
641              * Remove from the zone list if no free chunks remain.
642              * Clear RSignal
643              */
644             if (z->z_NFree == 0) {
645                 slgd->ZoneAry[zi] = z->z_Next;
646                 z->z_Next = NULL;
647             } else {
648                 z->z_RSignal = 0;
649             }
650         }
651
652         /*
653          * Fast path, we have chunks available in z_LChunks.
654          */
655         chunk = z->z_LChunks;
656         if (chunk) {
657                 chunk_mark_allocated(z, chunk);
658                 z->z_LChunks = chunk->c_Next;
659                 if (z->z_LChunks == NULL)
660                         z->z_LChunksp = &z->z_LChunks;
661                 goto done;
662         }
663
664         /*
665          * No chunks are available in LChunks, the free chunk MUST be
666          * in the never-before-used memory area, controlled by UIndex.
667          *
668          * The consequences are very serious if our zone got corrupted so
669          * we use an explicit panic rather than a KASSERT.
670          */
671         if (z->z_UIndex + 1 != z->z_NMax)
672             ++z->z_UIndex;
673         else
674             z->z_UIndex = 0;
675
676         if (z->z_UIndex == z->z_UEndIndex)
677             panic("slaballoc: corrupted zone");
678
679         chunk = (SLChunk *)(z->z_BasePtr + z->z_UIndex * size);
680         if ((z->z_Flags & SLZF_UNOTZEROD) == 0) {
681             flags &= ~M_ZERO;
682             flags |= M_PASSIVE_ZERO;
683         }
684         chunk_mark_allocated(z, chunk);
685         goto done;
686     }
687
688     /*
689      * If all zones are exhausted we need to allocate a new zone for this
690      * index.  Use M_ZERO to take advantage of pre-zerod pages.  Also see
691      * UAlloc use above in regards to M_ZERO.  Note that when we are reusing
692      * a zone from the FreeZones list UAlloc'd data will not be zero'd, and
693      * we do not pre-zero it because we do not want to mess up the L1 cache.
694      *
695      * At least one subsystem, the tty code (see CROUND) expects power-of-2
696      * allocations to be power-of-2 aligned.  We maintain compatibility by
697      * adjusting the base offset below.
698      */
699     {
700         int off;
701         int *kup;
702
703         if ((z = slgd->FreeZones) != NULL) {
704             slgd->FreeZones = z->z_Next;
705             --slgd->NFreeZones;
706             bzero(z, sizeof(SLZone));
707             z->z_Flags |= SLZF_UNOTZEROD;
708         } else {
709             z = kmem_slab_alloc(ZoneSize, ZoneSize, flags|M_ZERO);
710             if (z == NULL)
711                 goto fail;
712             atomic_add_int(&ZoneGenAlloc, (int)ZoneSize / 1024);
713         }
714
715         /*
716          * How big is the base structure?
717          */
718 #if defined(INVARIANTS)
719         /*
720          * Make room for z_Bitmap.  An exact calculation is somewhat more
721          * complicated so don't make an exact calculation.
722          */
723         off = offsetof(SLZone, z_Bitmap[(ZoneSize / size + 31) / 32]);
724         bzero(z->z_Bitmap, (ZoneSize / size + 31) / 8);
725 #else
726         off = sizeof(SLZone);
727 #endif
728
729         /*
730          * Guarentee power-of-2 alignment for power-of-2-sized chunks.
731          * Otherwise just 8-byte align the data.
732          */
733         if ((size | (size - 1)) + 1 == (size << 1))
734             off = (off + size - 1) & ~(size - 1);
735         else
736             off = (off + MIN_CHUNK_MASK) & ~MIN_CHUNK_MASK;
737         z->z_Magic = ZALLOC_SLAB_MAGIC;
738         z->z_ZoneIndex = zi;
739         z->z_NMax = (ZoneSize - off) / size;
740         z->z_NFree = z->z_NMax - 1;
741         z->z_BasePtr = (char *)z + off;
742         z->z_UIndex = z->z_UEndIndex = slgd->JunkIndex % z->z_NMax;
743         z->z_ChunkSize = size;
744         z->z_CpuGd = gd;
745         z->z_Cpu = gd->gd_cpuid;
746         z->z_LChunksp = &z->z_LChunks;
747         chunk = (SLChunk *)(z->z_BasePtr + z->z_UIndex * size);
748         z->z_Next = slgd->ZoneAry[zi];
749         slgd->ZoneAry[zi] = z;
750         if ((z->z_Flags & SLZF_UNOTZEROD) == 0) {
751             flags &= ~M_ZERO;   /* already zero'd */
752             flags |= M_PASSIVE_ZERO;
753         }
754         kup = btokup(z);
755         *kup = -(z->z_Cpu + 1); /* -1 to -(N+1) */
756         chunk_mark_allocated(z, chunk);
757
758         /*
759          * Slide the base index for initial allocations out of the next
760          * zone we create so we do not over-weight the lower part of the
761          * cpu memory caches.
762          */
763         slgd->JunkIndex = (slgd->JunkIndex + ZALLOC_SLAB_SLIDE)
764                                 & (ZALLOC_MAX_ZONE_SIZE - 1);
765     }
766
767 done:
768     ++type->ks_inuse[gd->gd_cpuid];
769     type->ks_memuse[gd->gd_cpuid] += size;
770     type->ks_loosememuse += size;       /* not MP synchronized */
771     crit_exit();
772
773     if (flags & M_ZERO)
774         bzero(chunk, size);
775 #ifdef INVARIANTS
776     else if ((flags & (M_ZERO|M_PASSIVE_ZERO)) == 0) {
777         if (use_malloc_pattern) {
778             for (i = 0; i < size; i += sizeof(int)) {
779                 *(int *)((char *)chunk + i) = -1;
780             }
781         }
782         chunk->c_Next = (void *)-1; /* avoid accidental double-free check */
783     }
784 #endif
785     logmemory(malloc_end, chunk, type, size, flags);
786     return(chunk);
787 fail:
788     crit_exit();
789     logmemory(malloc_end, NULL, type, size, flags);
790     return(NULL);
791 }
792
793 /*
794  * kernel realloc.  (SLAB ALLOCATOR) (MP SAFE)
795  *
796  * Generally speaking this routine is not called very often and we do
797  * not attempt to optimize it beyond reusing the same pointer if the
798  * new size fits within the chunking of the old pointer's zone.
799  */
800 void *
801 krealloc(void *ptr, unsigned long size, struct malloc_type *type, int flags)
802 {
803     unsigned long osize;
804     SLZone *z;
805     void *nptr;
806     int *kup;
807
808     KKASSERT((flags & M_ZERO) == 0);    /* not supported */
809
810     if (ptr == NULL || ptr == ZERO_LENGTH_PTR)
811         return(kmalloc(size, type, flags));
812     if (size == 0) {
813         kfree(ptr, type);
814         return(NULL);
815     }
816
817     /*
818      * Handle oversized allocations.  XXX we really should require that a
819      * size be passed to free() instead of this nonsense.
820      */
821     kup = btokup(ptr);
822     if (*kup > 0) {
823         osize = *kup << PAGE_SHIFT;
824         if (osize == round_page(size))
825             return(ptr);
826         if ((nptr = kmalloc(size, type, flags)) == NULL)
827             return(NULL);
828         bcopy(ptr, nptr, min(size, osize));
829         kfree(ptr, type);
830         return(nptr);
831     }
832
833     /*
834      * Get the original allocation's zone.  If the new request winds up
835      * using the same chunk size we do not have to do anything.
836      */
837     z = (SLZone *)((uintptr_t)ptr & ZoneMask);
838     kup = btokup(z);
839     KKASSERT(*kup < 0);
840     KKASSERT(z->z_Magic == ZALLOC_SLAB_MAGIC);
841
842     /*
843      * Allocate memory for the new request size.  Note that zoneindex has
844      * already adjusted the request size to the appropriate chunk size, which
845      * should optimize our bcopy().  Then copy and return the new pointer.
846      *
847      * Resizing a non-power-of-2 allocation to a power-of-2 size does not
848      * necessary align the result.
849      *
850      * We can only zoneindex (to align size to the chunk size) if the new
851      * size is not too large.
852      */
853     if (size < ZoneLimit) {
854         zoneindex(&size);
855         if (z->z_ChunkSize == size)
856             return(ptr);
857     }
858     if ((nptr = kmalloc(size, type, flags)) == NULL)
859         return(NULL);
860     bcopy(ptr, nptr, min(size, z->z_ChunkSize));
861     kfree(ptr, type);
862     return(nptr);
863 }
864
865 /*
866  * Return the kmalloc limit for this type, in bytes.
867  */
868 long
869 kmalloc_limit(struct malloc_type *type)
870 {
871     if (type->ks_limit == 0) {
872         crit_enter();
873         if (type->ks_limit == 0)
874             malloc_init(type);
875         crit_exit();
876     }
877     return(type->ks_limit);
878 }
879
880 /*
881  * Allocate a copy of the specified string.
882  *
883  * (MP SAFE) (MAY BLOCK)
884  */
885 char *
886 kstrdup(const char *str, struct malloc_type *type)
887 {
888     int zlen;   /* length inclusive of terminating NUL */
889     char *nstr;
890
891     if (str == NULL)
892         return(NULL);
893     zlen = strlen(str) + 1;
894     nstr = kmalloc(zlen, type, M_WAITOK);
895     bcopy(str, nstr, zlen);
896     return(nstr);
897 }
898
899 #ifdef SMP
900 /*
901  * Notify our cpu that a remote cpu has freed some chunks in a zone that
902  * we own.  RCount will be bumped so the memory should be good, but validate
903  * that it really is.
904  */
905 static
906 void
907 kfree_remote(void *ptr)
908 {
909     SLGlobalData *slgd;
910     SLChunk *bchunk;
911     SLZone *z;
912     int nfree;
913     int *kup;
914
915     slgd = &mycpu->gd_slab;
916     z = ptr;
917     kup = btokup(z);
918     KKASSERT(*kup == -((int)mycpuid + 1));
919     KKASSERT(z->z_RCount > 0);
920     atomic_subtract_int(&z->z_RCount, 1);
921
922     logmemory(free_rem_beg, z, NULL, 0, 0);
923     KKASSERT(z->z_Magic == ZALLOC_SLAB_MAGIC);
924     KKASSERT(z->z_Cpu  == mycpu->gd_cpuid);
925     nfree = z->z_NFree;
926
927     /*
928      * Indicate that we will no longer be off of the ZoneAry by
929      * clearing RSignal.
930      */
931     if (z->z_RChunks)
932         z->z_RSignal = 0;
933
934     /*
935      * Atomically extract the bchunks list and then process it back
936      * into the lchunks list.  We want to append our bchunks to the
937      * lchunks list and not prepend since we likely do not have
938      * cache mastership of the related data (not that it helps since
939      * we are using c_Next).
940      */
941     while ((bchunk = z->z_RChunks) != NULL) {
942         cpu_ccfence();
943         if (atomic_cmpset_ptr(&z->z_RChunks, bchunk, NULL)) {
944             *z->z_LChunksp = bchunk;
945             while (bchunk) {
946                     chunk_mark_free(z, bchunk);
947                     z->z_LChunksp = &bchunk->c_Next;
948                     bchunk = bchunk->c_Next;
949                     ++z->z_NFree;
950             }
951             break;
952         }
953     }
954     if (z->z_NFree && nfree == 0) {
955         z->z_Next = slgd->ZoneAry[z->z_ZoneIndex];
956         slgd->ZoneAry[z->z_ZoneIndex] = z;
957     }
958
959     /*
960      * If the zone becomes totally free, and there are other zones we
961      * can allocate from, move this zone to the FreeZones list.  Since
962      * this code can be called from an IPI callback, do *NOT* try to mess
963      * with kernel_map here.  Hysteresis will be performed at malloc() time.
964      *
965      * Do not move the zone if there is an IPI inflight, otherwise MP
966      * races can result in our free_remote code accessing a destroyed
967      * zone.
968      */
969     if (z->z_NFree == z->z_NMax &&
970         (z->z_Next || slgd->ZoneAry[z->z_ZoneIndex] != z) &&
971         z->z_RCount == 0
972     ) {
973         SLZone **pz;
974         int *kup;
975
976         for (pz = &slgd->ZoneAry[z->z_ZoneIndex];
977              z != *pz;
978              pz = &(*pz)->z_Next) {
979             ;
980         }
981         *pz = z->z_Next;
982         z->z_Magic = -1;
983         z->z_Next = slgd->FreeZones;
984         slgd->FreeZones = z;
985         ++slgd->NFreeZones;
986         kup = btokup(z);
987         *kup = 0;
988     }
989     logmemory(free_rem_end, z, bchunk, 0, 0);
990 }
991
992 #endif
993
994 /*
995  * free (SLAB ALLOCATOR)
996  *
997  * Free a memory block previously allocated by malloc.  Note that we do not
998  * attempt to update ks_loosememuse as MP races could prevent us from
999  * checking memory limits in malloc.
1000  *
1001  * MPSAFE
1002  */
1003 void
1004 kfree(void *ptr, struct malloc_type *type)
1005 {
1006     SLZone *z;
1007     SLChunk *chunk;
1008     SLGlobalData *slgd;
1009     struct globaldata *gd;
1010     int *kup;
1011     unsigned long size;
1012 #ifdef SMP
1013     SLChunk *bchunk;
1014     int rsignal;
1015 #endif
1016
1017     logmemory_quick(free_beg);
1018     gd = mycpu;
1019     slgd = &gd->gd_slab;
1020
1021     if (ptr == NULL)
1022         panic("trying to free NULL pointer");
1023
1024     /*
1025      * Handle special 0-byte allocations
1026      */
1027     if (ptr == ZERO_LENGTH_PTR) {
1028         logmemory(free_zero, ptr, type, -1, 0);
1029         logmemory_quick(free_end);
1030         return;
1031     }
1032
1033     /*
1034      * Panic on bad malloc type
1035      */
1036     if (type->ks_magic != M_MAGIC)
1037         panic("free: malloc type lacks magic");
1038
1039     /*
1040      * Handle oversized allocations.  XXX we really should require that a
1041      * size be passed to free() instead of this nonsense.
1042      *
1043      * This code is never called via an ipi.
1044      */
1045     kup = btokup(ptr);
1046     if (*kup > 0) {
1047         size = *kup << PAGE_SHIFT;
1048         *kup = 0;
1049 #ifdef INVARIANTS
1050         KKASSERT(sizeof(weirdary) <= size);
1051         bcopy(weirdary, ptr, sizeof(weirdary));
1052 #endif
1053         /*
1054          * NOTE: For oversized allocations we do not record the
1055          *           originating cpu.  It gets freed on the cpu calling
1056          *           kfree().  The statistics are in aggregate.
1057          *
1058          * note: XXX we have still inherited the interrupts-can't-block
1059          * assumption.  An interrupt thread does not bump
1060          * gd_intr_nesting_level so check TDF_INTTHREAD.  This is
1061          * primarily until we can fix softupdate's assumptions about free().
1062          */
1063         crit_enter();
1064         --type->ks_inuse[gd->gd_cpuid];
1065         type->ks_memuse[gd->gd_cpuid] -= size;
1066         if (mycpu->gd_intr_nesting_level ||
1067             (gd->gd_curthread->td_flags & TDF_INTTHREAD))
1068         {
1069             logmemory(free_ovsz_delayed, ptr, type, size, 0);
1070             z = (SLZone *)ptr;
1071             z->z_Magic = ZALLOC_OVSZ_MAGIC;
1072             z->z_Next = slgd->FreeOvZones;
1073             z->z_ChunkSize = size;
1074             slgd->FreeOvZones = z;
1075             crit_exit();
1076         } else {
1077             crit_exit();
1078             logmemory(free_ovsz, ptr, type, size, 0);
1079             kmem_slab_free(ptr, size);  /* may block */
1080             atomic_add_int(&ZoneBigAlloc, -(int)size / 1024);
1081         }
1082         logmemory_quick(free_end);
1083         return;
1084     }
1085
1086     /*
1087      * Zone case.  Figure out the zone based on the fact that it is
1088      * ZoneSize aligned. 
1089      */
1090     z = (SLZone *)((uintptr_t)ptr & ZoneMask);
1091     kup = btokup(z);
1092     KKASSERT(*kup < 0);
1093     KKASSERT(z->z_Magic == ZALLOC_SLAB_MAGIC);
1094
1095     /*
1096      * If we do not own the zone then use atomic ops to free to the
1097      * remote cpu linked list and notify the target zone using a
1098      * passive message.
1099      *
1100      * The target zone cannot be deallocated while we own a chunk of it,
1101      * so the zone header's storage is stable until the very moment
1102      * we adjust z_RChunks.  After that we cannot safely dereference (z).
1103      *
1104      * (no critical section needed)
1105      */
1106     if (z->z_CpuGd != gd) {
1107 #ifdef SMP
1108         /*
1109          * Making these adjustments now allow us to avoid passing (type)
1110          * to the remote cpu.  Note that ks_inuse/ks_memuse is being
1111          * adjusted on OUR cpu, not the zone cpu, but it should all still
1112          * sum up properly and cancel out.
1113          */
1114         crit_enter();
1115         --type->ks_inuse[gd->gd_cpuid];
1116         type->ks_memuse[gd->gd_cpuid] -= z->z_ChunkSize;
1117         crit_exit();
1118
1119         /*
1120          * WARNING! This code competes with other cpus.  Once we
1121          *          successfully link the chunk to RChunks the remote
1122          *          cpu can rip z's storage out from under us.
1123          *
1124          *          Bumping RCount prevents z's storage from getting
1125          *          ripped out.
1126          */
1127         rsignal = z->z_RSignal;
1128         cpu_lfence();
1129         if (rsignal)
1130                 atomic_add_int(&z->z_RCount, 1);
1131
1132         chunk = ptr;
1133         for (;;) {
1134             bchunk = z->z_RChunks;
1135             cpu_ccfence();
1136             chunk->c_Next = bchunk;
1137             cpu_sfence();
1138
1139             if (atomic_cmpset_ptr(&z->z_RChunks, bchunk, chunk))
1140                 break;
1141         }
1142
1143         /*
1144          * We have to signal the remote cpu if our actions will cause
1145          * the remote zone to be placed back on ZoneAry so it can
1146          * move the zone back on.
1147          *
1148          * We only need to deal with NULL->non-NULL RChunk transitions
1149          * and only if z_RSignal is set.  We interlock by reading rsignal
1150          * before adding our chunk to RChunks.  This should result in
1151          * virtually no IPI traffic.
1152          *
1153          * We can use a passive IPI to reduce overhead even further.
1154          */
1155         if (bchunk == NULL && rsignal) {
1156             logmemory(free_request, ptr, type, z->z_ChunkSize, 0);
1157             lwkt_send_ipiq_passive(z->z_CpuGd, kfree_remote, z);
1158             /* z can get ripped out from under us from this point on */
1159         } else if (rsignal) {
1160             atomic_subtract_int(&z->z_RCount, 1);
1161             /* z can get ripped out from under us from this point on */
1162         }
1163 #else
1164         panic("Corrupt SLZone");
1165 #endif
1166         logmemory_quick(free_end);
1167         return;
1168     }
1169
1170     /*
1171      * kfree locally
1172      */
1173     logmemory(free_chunk, ptr, type, z->z_ChunkSize, 0);
1174
1175     crit_enter();
1176     chunk = ptr;
1177     chunk_mark_free(z, chunk);
1178
1179     /*
1180      * Put weird data into the memory to detect modifications after freeing,
1181      * illegal pointer use after freeing (we should fault on the odd address),
1182      * and so forth.  XXX needs more work, see the old malloc code.
1183      */
1184 #ifdef INVARIANTS
1185     if (z->z_ChunkSize < sizeof(weirdary))
1186         bcopy(weirdary, chunk, z->z_ChunkSize);
1187     else
1188         bcopy(weirdary, chunk, sizeof(weirdary));
1189 #endif
1190
1191     /*
1192      * Add this free non-zero'd chunk to a linked list for reuse.  Add
1193      * to the front of the linked list so it is more likely to be
1194      * reallocated, since it is already in our L1 cache.
1195      */
1196 #ifdef INVARIANTS
1197     if ((vm_offset_t)chunk < KvaStart || (vm_offset_t)chunk >= KvaEnd)
1198         panic("BADFREE %p", chunk);
1199 #endif
1200     chunk->c_Next = z->z_LChunks;
1201     z->z_LChunks = chunk;
1202     if (chunk->c_Next == NULL)
1203             z->z_LChunksp = &chunk->c_Next;
1204
1205 #ifdef INVARIANTS
1206     if (chunk->c_Next && (vm_offset_t)chunk->c_Next < KvaStart)
1207         panic("BADFREE2");
1208 #endif
1209
1210     /*
1211      * Bump the number of free chunks.  If it becomes non-zero the zone
1212      * must be added back onto the appropriate list.
1213      */
1214     if (z->z_NFree++ == 0) {
1215         z->z_Next = slgd->ZoneAry[z->z_ZoneIndex];
1216         slgd->ZoneAry[z->z_ZoneIndex] = z;
1217     }
1218
1219     --type->ks_inuse[z->z_Cpu];
1220     type->ks_memuse[z->z_Cpu] -= z->z_ChunkSize;
1221
1222     /*
1223      * If the zone becomes totally free, and there are other zones we
1224      * can allocate from, move this zone to the FreeZones list.  Since
1225      * this code can be called from an IPI callback, do *NOT* try to mess
1226      * with kernel_map here.  Hysteresis will be performed at malloc() time.
1227      */
1228     if (z->z_NFree == z->z_NMax && 
1229         (z->z_Next || slgd->ZoneAry[z->z_ZoneIndex] != z) &&
1230         z->z_RCount == 0
1231     ) {
1232         SLZone **pz;
1233         int *kup;
1234
1235         for (pz = &slgd->ZoneAry[z->z_ZoneIndex]; z != *pz; pz = &(*pz)->z_Next)
1236             ;
1237         *pz = z->z_Next;
1238         z->z_Magic = -1;
1239         z->z_Next = slgd->FreeZones;
1240         slgd->FreeZones = z;
1241         ++slgd->NFreeZones;
1242         kup = btokup(z);
1243         *kup = 0;
1244     }
1245     logmemory_quick(free_end);
1246     crit_exit();
1247 }
1248
1249 #if defined(INVARIANTS)
1250
1251 /*
1252  * Helper routines for sanity checks
1253  */
1254 static
1255 void
1256 chunk_mark_allocated(SLZone *z, void *chunk)
1257 {
1258     int bitdex = ((char *)chunk - (char *)z->z_BasePtr) / z->z_ChunkSize;
1259     __uint32_t *bitptr;
1260
1261     KKASSERT((((intptr_t)chunk ^ (intptr_t)z) & ZoneMask) == 0);
1262     KASSERT(bitdex >= 0 && bitdex < z->z_NMax,
1263             ("memory chunk %p bit index %d is illegal", chunk, bitdex));
1264     bitptr = &z->z_Bitmap[bitdex >> 5];
1265     bitdex &= 31;
1266     KASSERT((*bitptr & (1 << bitdex)) == 0,
1267             ("memory chunk %p is already allocated!", chunk));
1268     *bitptr |= 1 << bitdex;
1269 }
1270
1271 static
1272 void
1273 chunk_mark_free(SLZone *z, void *chunk)
1274 {
1275     int bitdex = ((char *)chunk - (char *)z->z_BasePtr) / z->z_ChunkSize;
1276     __uint32_t *bitptr;
1277
1278     KKASSERT((((intptr_t)chunk ^ (intptr_t)z) & ZoneMask) == 0);
1279     KASSERT(bitdex >= 0 && bitdex < z->z_NMax,
1280             ("memory chunk %p bit index %d is illegal!", chunk, bitdex));
1281     bitptr = &z->z_Bitmap[bitdex >> 5];
1282     bitdex &= 31;
1283     KASSERT((*bitptr & (1 << bitdex)) != 0,
1284             ("memory chunk %p is already free!", chunk));
1285     *bitptr &= ~(1 << bitdex);
1286 }
1287
1288 #endif
1289
1290 /*
1291  * kmem_slab_alloc()
1292  *
1293  *      Directly allocate and wire kernel memory in PAGE_SIZE chunks with the
1294  *      specified alignment.  M_* flags are expected in the flags field.
1295  *
1296  *      Alignment must be a multiple of PAGE_SIZE.
1297  *
1298  *      NOTE! XXX For the moment we use vm_map_entry_reserve/release(),
1299  *      but when we move zalloc() over to use this function as its backend
1300  *      we will have to switch to kreserve/krelease and call reserve(0)
1301  *      after the new space is made available.
1302  *
1303  *      Interrupt code which has preempted other code is not allowed to
1304  *      use PQ_CACHE pages.  However, if an interrupt thread is run
1305  *      non-preemptively or blocks and then runs non-preemptively, then
1306  *      it is free to use PQ_CACHE pages.
1307  */
1308 static void *
1309 kmem_slab_alloc(vm_size_t size, vm_offset_t align, int flags)
1310 {
1311     vm_size_t i;
1312     vm_offset_t addr;
1313     int count, vmflags, base_vmflags;
1314     vm_page_t mp[ZALLOC_MAX_ZONE_SIZE / PAGE_SIZE];
1315     thread_t td;
1316
1317     size = round_page(size);
1318     addr = vm_map_min(&kernel_map);
1319
1320     /*
1321      * Reserve properly aligned space from kernel_map.  RNOWAIT allocations
1322      * cannot block.
1323      */
1324     if (flags & M_RNOWAIT) {
1325         if (lwkt_trytoken(&vm_token) == 0)
1326             return(NULL);
1327     } else {
1328         lwkt_gettoken(&vm_token);
1329     }
1330     count = vm_map_entry_reserve(MAP_RESERVE_COUNT);
1331     crit_enter();
1332     vm_map_lock(&kernel_map);
1333     if (vm_map_findspace(&kernel_map, addr, size, align, 0, &addr)) {
1334         vm_map_unlock(&kernel_map);
1335         if ((flags & M_NULLOK) == 0)
1336             panic("kmem_slab_alloc(): kernel_map ran out of space!");
1337         vm_map_entry_release(count);
1338         crit_exit();
1339         lwkt_reltoken(&vm_token);
1340         return(NULL);
1341     }
1342
1343     /*
1344      * kernel_object maps 1:1 to kernel_map.
1345      */
1346     vm_object_reference(&kernel_object);
1347     vm_map_insert(&kernel_map, &count, 
1348                     &kernel_object, addr, addr, addr + size,
1349                     VM_MAPTYPE_NORMAL,
1350                     VM_PROT_ALL, VM_PROT_ALL,
1351                     0);
1352
1353     td = curthread;
1354
1355     base_vmflags = 0;
1356     if (flags & M_ZERO)
1357         base_vmflags |= VM_ALLOC_ZERO;
1358     if (flags & M_USE_RESERVE)
1359         base_vmflags |= VM_ALLOC_SYSTEM;
1360     if (flags & M_USE_INTERRUPT_RESERVE)
1361         base_vmflags |= VM_ALLOC_INTERRUPT;
1362     if ((flags & (M_RNOWAIT|M_WAITOK)) == 0) {
1363         panic("kmem_slab_alloc: bad flags %08x (%p)",
1364               flags, ((int **)&size)[-1]);
1365     }
1366
1367
1368     /*
1369      * Allocate the pages.  Do not mess with the PG_ZERO flag yet.
1370      */
1371     for (i = 0; i < size; i += PAGE_SIZE) {
1372         vm_page_t m;
1373
1374         /*
1375          * VM_ALLOC_NORMAL can only be set if we are not preempting.
1376          *
1377          * VM_ALLOC_SYSTEM is automatically set if we are preempting and
1378          * M_WAITOK was specified as an alternative (i.e. M_USE_RESERVE is
1379          * implied in this case), though I'm not sure if we really need to
1380          * do that.
1381          */
1382         vmflags = base_vmflags;
1383         if (flags & M_WAITOK) {
1384             if (td->td_preempted)
1385                 vmflags |= VM_ALLOC_SYSTEM;
1386             else
1387                 vmflags |= VM_ALLOC_NORMAL;
1388         }
1389
1390         m = vm_page_alloc(&kernel_object, OFF_TO_IDX(addr + i), vmflags);
1391         if ((i / PAGE_SIZE) < (sizeof(mp) / sizeof(mp[0])))
1392                 mp[i / PAGE_SIZE] = m;
1393
1394         /*
1395          * If the allocation failed we either return NULL or we retry.
1396          *
1397          * If M_WAITOK is specified we wait for more memory and retry.
1398          * If M_WAITOK is specified from a preemption we yield instead of
1399          * wait.  Livelock will not occur because the interrupt thread
1400          * will not be preempting anyone the second time around after the
1401          * yield.
1402          */
1403         if (m == NULL) {
1404             if (flags & M_WAITOK) {
1405                 if (td->td_preempted) {
1406                     vm_map_unlock(&kernel_map);
1407                     lwkt_switch();
1408                     vm_map_lock(&kernel_map);
1409                 } else {
1410                     vm_map_unlock(&kernel_map);
1411                     vm_wait(0);
1412                     vm_map_lock(&kernel_map);
1413                 }
1414                 i -= PAGE_SIZE; /* retry */
1415                 continue;
1416             }
1417
1418             /*
1419              * We were unable to recover, cleanup and return NULL
1420              *
1421              * (vm_token already held)
1422              */
1423             while (i != 0) {
1424                 i -= PAGE_SIZE;
1425                 m = vm_page_lookup(&kernel_object, OFF_TO_IDX(addr + i));
1426                 /* page should already be busy */
1427                 vm_page_free(m);
1428             }
1429             vm_map_delete(&kernel_map, addr, addr + size, &count);
1430             vm_map_unlock(&kernel_map);
1431             vm_map_entry_release(count);
1432             crit_exit();
1433             lwkt_reltoken(&vm_token);
1434             return(NULL);
1435         }
1436     }
1437
1438     /*
1439      * Success!
1440      *
1441      * Mark the map entry as non-pageable using a routine that allows us to
1442      * populate the underlying pages.
1443      *
1444      * The pages were busied by the allocations above.
1445      */
1446     vm_map_set_wired_quick(&kernel_map, addr, size, &count);
1447     crit_exit();
1448
1449     /*
1450      * Enter the pages into the pmap and deal with PG_ZERO and M_ZERO.
1451      */
1452     for (i = 0; i < size; i += PAGE_SIZE) {
1453         vm_page_t m;
1454
1455         if ((i / PAGE_SIZE) < (sizeof(mp) / sizeof(mp[0])))
1456            m = mp[i / PAGE_SIZE];
1457         else 
1458            m = vm_page_lookup(&kernel_object, OFF_TO_IDX(addr + i));
1459         m->valid = VM_PAGE_BITS_ALL;
1460         /* page should already be busy */
1461         vm_page_wire(m);
1462         vm_page_wakeup(m);
1463         pmap_enter(&kernel_pmap, addr + i, m, VM_PROT_ALL, 1);
1464         if ((m->flags & PG_ZERO) == 0 && (flags & M_ZERO))
1465             bzero((char *)addr + i, PAGE_SIZE);
1466         vm_page_flag_clear(m, PG_ZERO);
1467         KKASSERT(m->flags & (PG_WRITEABLE | PG_MAPPED));
1468         vm_page_flag_set(m, PG_REFERENCED);
1469     }
1470     vm_map_unlock(&kernel_map);
1471     vm_map_entry_release(count);
1472     lwkt_reltoken(&vm_token);
1473     return((void *)addr);
1474 }
1475
1476 /*
1477  * kmem_slab_free()
1478  */
1479 static void
1480 kmem_slab_free(void *ptr, vm_size_t size)
1481 {
1482     crit_enter();
1483     lwkt_gettoken(&vm_token);
1484     vm_map_remove(&kernel_map, (vm_offset_t)ptr, (vm_offset_t)ptr + size);
1485     lwkt_reltoken(&vm_token);
1486     crit_exit();
1487 }
1488