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