Return to slab.c CVS log

Up to [GnuMach] / Gnu-Mach / kern

Annotation of Gnu-Mach/kern/slab.c, revision 1.1

1.1     ! root        1: /*
        !             2:  * Copyright (c) 2011 Free Software Foundation.
        !             3:  *
        !             4:  * This program is free software; you can redistribute it and/or modify
        !             5:  * it under the terms of the GNU General Public License as published by
        !             6:  * the Free Software Foundation; either version 2 of the License, or
        !             7:  * (at your option) any later version.
        !             8:  *
        !             9:  * This program is distributed in the hope that it will be useful,
        !            10:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
        !            11:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
        !            12:  * GNU General Public License for more details.
        !            13:  *
        !            14:  * You should have received a copy of the GNU General Public License along
        !            15:  * with this program; if not, write to the Free Software Foundation, Inc.,
        !            16:  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
        !            17:  */
        !            18: 
        !            19: /*
        !            20:  * Copyright (c) 2010, 2011 Richard Braun.
        !            21:  * All rights reserved.
        !            22:  *
        !            23:  * Redistribution and use in source and binary forms, with or without
        !            24:  * modification, are permitted provided that the following conditions
        !            25:  * are met:
        !            26:  * 1. Redistributions of source code must retain the above copyright
        !            27:  *    notice, this list of conditions and the following disclaimer.
        !            28:  * 2. Redistributions in binary form must reproduce the above copyright
        !            29:  *    notice, this list of conditions and the following disclaimer in the
        !            30:  *    documentation and/or other materials provided with the distribution.
        !            31:  *
        !            32:  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
        !            33:  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
        !            34:  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
        !            35:  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
        !            36:  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
        !            37:  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
        !            38:  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
        !            39:  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
        !            40:  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
        !            41:  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
        !            42:  *
        !            43:  *
        !            44:  * Object caching and general purpose memory allocator.
        !            45:  *
        !            46:  * This allocator is based on the paper "The Slab Allocator: An Object-Caching
        !            47:  * Kernel Memory Allocator" by Jeff Bonwick.
        !            48:  *
        !            49:  * It allows the allocation of objects (i.e. fixed-size typed buffers) from
        !            50:  * caches and is efficient in both space and time. This implementation follows
        !            51:  * many of the indications from the paper mentioned. The most notable
        !            52:  * differences are outlined below.
        !            53:  *
        !            54:  * The per-cache self-scaling hash table for buffer-to-bufctl conversion,
        !            55:  * described in 3.2.3 "Slab Layout for Large Objects", has been replaced by
        !            56:  * a red-black tree storing slabs, sorted by address. The use of a
        !            57:  * self-balancing tree for buffer-to-slab conversions provides a few advantages
        !            58:  * over a hash table. Unlike a hash table, a BST provides a "lookup nearest"
        !            59:  * operation, so obtaining the slab data (whether it is embedded in the slab or
        !            60:  * off slab) from a buffer address simply consists of a "lookup nearest towards
        !            61:  * 0" tree search. Storing slabs instead of buffers also considerably reduces
        !            62:  * the number of elements to retain. Finally, a self-balancing tree is a true
        !            63:  * self-scaling data structure, whereas a hash table requires periodic
        !            64:  * maintenance and complete resizing, which is expensive. The only drawback is
        !            65:  * that releasing a buffer to the slab layer takes logarithmic time instead of
        !            66:  * constant time. But as the data set size is kept reasonable (because slabs
        !            67:  * are stored instead of buffers) and because the CPU pool layer services most
        !            68:  * requests, avoiding many accesses to the slab layer, it is considered an
        !            69:  * acceptable tradeoff.
        !            70:  *
        !            71:  * This implementation uses per-cpu pools of objects, which service most
        !            72:  * allocation requests. These pools act as caches (but are named differently
        !            73:  * to avoid confusion with CPU caches) that reduce contention on multiprocessor
        !            74:  * systems. When a pool is empty and cannot provide an object, it is filled by
        !            75:  * transferring multiple objects from the slab layer. The symmetric case is
        !            76:  * handled likewise.
        !            77:  */
        !            78: 
        !            79: #include <string.h>
        !            80: #include <kern/assert.h>
        !            81: #include <kern/mach_clock.h>
        !            82: #include <kern/printf.h>
        !            83: #include <kern/slab.h>
        !            84: #include <kern/kalloc.h>
        !            85: #include <kern/cpu_number.h>
        !            86: #include <mach/vm_param.h>
        !            87: #include <mach/machine/vm_types.h>
        !            88: #include <vm/vm_kern.h>
        !            89: #include <vm/vm_types.h>
        !            90: #include <sys/types.h>
        !            91: 
        !            92: #ifdef MACH_DEBUG
        !            93: #include <mach_debug/slab_info.h>
        !            94: #endif
        !            95: 
        !            96: /*
        !            97:  * Utility macros.
        !            98:  */
        !            99: #define ARRAY_SIZE(x)   (sizeof(x) / sizeof((x)[0]))
        !           100: #define P2ALIGNED(x, a) (((x) & ((a) - 1)) == 0)
        !           101: #define ISP2(x)         P2ALIGNED(x, x)
        !           102: #define P2ALIGN(x, a)   ((x) & -(a))
        !           103: #define P2ROUND(x, a)   (-(-(x) & -(a)))
        !           104: #define P2END(x, a)     (-(~(x) & -(a)))
        !           105: #define likely(expr)    __builtin_expect(!!(expr), 1)
        !           106: #define unlikely(expr)  __builtin_expect(!!(expr), 0)
        !           107: 
        !           108: /*
        !           109:  * Minimum required alignment.
        !           110:  */
        !           111: #define KMEM_ALIGN_MIN 8
        !           112: 
        !           113: /*
        !           114:  * Minimum number of buffers per slab.
        !           115:  *
        !           116:  * This value is ignored when the slab size exceeds a threshold.
        !           117:  */
        !           118: #define KMEM_MIN_BUFS_PER_SLAB 8
        !           119: 
        !           120: /*
        !           121:  * Special slab size beyond which the minimum number of buffers per slab is
        !           122:  * ignored when computing the slab size of a cache.
        !           123:  */
        !           124: #define KMEM_SLAB_SIZE_THRESHOLD (8 * PAGE_SIZE)
        !           125: 
        !           126: /*
        !           127:  * Special buffer size under which slab data is unconditionnally allocated
        !           128:  * from its associated slab.
        !           129:  */
        !           130: #define KMEM_BUF_SIZE_THRESHOLD (PAGE_SIZE / 8)
        !           131: 
        !           132: /*
        !           133:  * Time (in ticks) between two garbage collection operations.
        !           134:  */
        !           135: #define KMEM_GC_INTERVAL (5 * hz)
        !           136: 
        !           137: /*
        !           138:  * The transfer size of a CPU pool is computed by dividing the pool size by
        !           139:  * this value.
        !           140:  */
        !           141: #define KMEM_CPU_POOL_TRANSFER_RATIO 2
        !           142: 
        !           143: /*
        !           144:  * Redzone guard word.
        !           145:  */
        !           146: #ifdef __LP64__
        !           147: #if _HOST_BIG_ENDIAN
        !           148: #define KMEM_REDZONE_WORD 0xfeedfacefeedfaceUL
        !           149: #else /* _HOST_BIG_ENDIAN */
        !           150: #define KMEM_REDZONE_WORD 0xcefaedfecefaedfeUL
        !           151: #endif /* _HOST_BIG_ENDIAN */
        !           152: #else /* __LP64__ */
        !           153: #if _HOST_BIG_ENDIAN
        !           154: #define KMEM_REDZONE_WORD 0xfeedfaceUL
        !           155: #else /* _HOST_BIG_ENDIAN */
        !           156: #define KMEM_REDZONE_WORD 0xcefaedfeUL
        !           157: #endif /* _HOST_BIG_ENDIAN */
        !           158: #endif /* __LP64__ */
        !           159: 
        !           160: /*
        !           161:  * Redzone byte for padding.
        !           162:  */
        !           163: #define KMEM_REDZONE_BYTE 0xbb
        !           164: 
        !           165: /*
        !           166:  * Size of the VM submap from which default backend functions allocate.
        !           167:  */
        !           168: #define KMEM_MAP_SIZE (128 * 1024 * 1024)
        !           169: 
        !           170: /*
        !           171:  * Shift for the first kalloc cache size.
        !           172:  */
        !           173: #define KALLOC_FIRST_SHIFT 5
        !           174: 
        !           175: /*
        !           176:  * Number of caches backing general purpose allocations.
        !           177:  */
        !           178: #define KALLOC_NR_CACHES 13
        !           179: 
        !           180: /*
        !           181:  * Values the buftag state member can take.
        !           182:  */
        !           183: #ifdef __LP64__
        !           184: #if _HOST_BIG_ENDIAN
        !           185: #define KMEM_BUFTAG_ALLOC   0xa110c8eda110c8edUL
        !           186: #define KMEM_BUFTAG_FREE    0xf4eeb10cf4eeb10cUL
        !           187: #else /* _HOST_BIG_ENDIAN */
        !           188: #define KMEM_BUFTAG_ALLOC   0xedc810a1edc810a1UL
        !           189: #define KMEM_BUFTAG_FREE    0x0cb1eef40cb1eef4UL
        !           190: #endif /* _HOST_BIG_ENDIAN */
        !           191: #else /* __LP64__ */
        !           192: #if _HOST_BIG_ENDIAN
        !           193: #define KMEM_BUFTAG_ALLOC   0xa110c8edUL
        !           194: #define KMEM_BUFTAG_FREE    0xf4eeb10cUL
        !           195: #else /* _HOST_BIG_ENDIAN */
        !           196: #define KMEM_BUFTAG_ALLOC   0xedc810a1UL
        !           197: #define KMEM_BUFTAG_FREE    0x0cb1eef4UL
        !           198: #endif /* _HOST_BIG_ENDIAN */
        !           199: #endif /* __LP64__ */
        !           200: 
        !           201: /*
        !           202:  * Free and uninitialized patterns.
        !           203:  *
        !           204:  * These values are unconditionnally 64-bit wide since buffers are at least
        !           205:  * 8-byte aligned.
        !           206:  */
        !           207: #if _HOST_BIG_ENDIAN
        !           208: #define KMEM_FREE_PATTERN   0xdeadbeefdeadbeefULL
        !           209: #define KMEM_UNINIT_PATTERN 0xbaddcafebaddcafeULL
        !           210: #else /* _HOST_BIG_ENDIAN */
        !           211: #define KMEM_FREE_PATTERN   0xefbeaddeefbeaddeULL
        !           212: #define KMEM_UNINIT_PATTERN 0xfecaddbafecaddbaULL
        !           213: #endif /* _HOST_BIG_ENDIAN */
        !           214: 
        !           215: /*
        !           216:  * Cache flags.
        !           217:  *
        !           218:  * The flags don't change once set and can be tested without locking.
        !           219:  */
        !           220: #define KMEM_CF_NO_CPU_POOL     0x01    /* CPU pool layer disabled */
        !           221: #define KMEM_CF_SLAB_EXTERNAL   0x02    /* Slab data is off slab */
        !           222: #define KMEM_CF_NO_RECLAIM      0x04    /* Slabs are not reclaimable */
        !           223: #define KMEM_CF_VERIFY          0x08    /* Debugging facilities enabled */
        !           224: #define KMEM_CF_DIRECT          0x10    /* No buf-to-slab tree lookup */
        !           225: 
        !           226: /*
        !           227:  * Options for kmem_cache_alloc_verify().
        !           228:  */
        !           229: #define KMEM_AV_NOCONSTRUCT 0
        !           230: #define KMEM_AV_CONSTRUCT   1
        !           231: 
        !           232: /*
        !           233:  * Error codes for kmem_cache_error().
        !           234:  */
        !           235: #define KMEM_ERR_INVALID    0   /* Invalid address being freed */
        !           236: #define KMEM_ERR_DOUBLEFREE 1   /* Freeing already free address */
        !           237: #define KMEM_ERR_BUFTAG     2   /* Invalid buftag content */
        !           238: #define KMEM_ERR_MODIFIED   3   /* Buffer modified while free */
        !           239: #define KMEM_ERR_REDZONE    4   /* Redzone violation */
        !           240: 
        !           241: #if SLAB_USE_CPU_POOLS
        !           242: /*
        !           243:  * Available CPU pool types.
        !           244:  *
        !           245:  * For each entry, the CPU pool size applies from the entry buf_size
        !           246:  * (excluded) up to (and including) the buf_size of the preceding entry.
        !           247:  *
        !           248:  * See struct kmem_cpu_pool_type for a description of the values.
        !           249:  */
        !           250: static struct kmem_cpu_pool_type kmem_cpu_pool_types[] = {
        !           251:     {  32768,   1, 0,           NULL },
        !           252:     {   4096,   8, CPU_L1_SIZE, NULL },
        !           253:     {    256,  64, CPU_L1_SIZE, NULL },
        !           254:     {      0, 128, CPU_L1_SIZE, NULL }
        !           255: };
        !           256: 
        !           257: /*
        !           258:  * Caches where CPU pool arrays are allocated from.
        !           259:  */
        !           260: static struct kmem_cache kmem_cpu_array_caches[ARRAY_SIZE(kmem_cpu_pool_types)];
        !           261: #endif /* SLAB_USE_CPU_POOLS */
        !           262: 
        !           263: /*
        !           264:  * Cache for off slab data.
        !           265:  */
        !           266: static struct kmem_cache kmem_slab_cache;
        !           267: 
        !           268: /*
        !           269:  * General purpose caches array.
        !           270:  */
        !           271: static struct kmem_cache kalloc_caches[KALLOC_NR_CACHES];
        !           272: 
        !           273: /*
        !           274:  * List of all caches managed by the allocator.
        !           275:  */
        !           276: static struct list kmem_cache_list;
        !           277: static unsigned int kmem_nr_caches;
        !           278: static simple_lock_data_t __attribute__((used)) kmem_cache_list_lock;
        !           279: 
        !           280: /*
        !           281:  * VM submap for slab caches.
        !           282:  */
        !           283: static struct vm_map kmem_map_store;
        !           284: vm_map_t kmem_map = &kmem_map_store;
        !           285: 
        !           286: /*
        !           287:  * Time of the last memory reclaim, in clock ticks.
        !           288:  */
        !           289: static unsigned long kmem_gc_last_tick;
        !           290: 
        !           291: #define kmem_error(format, ...)                         \
        !           292:     printf("mem: error: %s(): " format "\n", __func__,  \
        !           293:            ## __VA_ARGS__)
        !           294: 
        !           295: #define kmem_warn(format, ...)                              \
        !           296:     printf("mem: warning: %s(): " format "\n", __func__,    \
        !           297:            ## __VA_ARGS__)
        !           298: 
        !           299: #define kmem_print(format, ...) \
        !           300:     printf(format "\n", ## __VA_ARGS__)
        !           301: 
        !           302: static void kmem_cache_error(struct kmem_cache *cache, void *buf, int error,
        !           303:                              void *arg);
        !           304: static void * kmem_cache_alloc_from_slab(struct kmem_cache *cache);
        !           305: static void kmem_cache_free_to_slab(struct kmem_cache *cache, void *buf);
        !           306: 
        !           307: static void * kmem_buf_verify_bytes(void *buf, void *pattern, size_t size)
        !           308: {
        !           309:     char *ptr, *pattern_ptr, *end;
        !           310: 
        !           311:     end = buf + size;
        !           312: 
        !           313:     for (ptr = buf, pattern_ptr = pattern; ptr < end; ptr++, pattern_ptr++)
        !           314:         if (*ptr != *pattern_ptr)
        !           315:             return ptr;
        !           316: 
        !           317:     return NULL;
        !           318: }
        !           319: 
        !           320: static void * kmem_buf_verify(void *buf, uint64_t pattern, vm_size_t size)
        !           321: {
        !           322:     uint64_t *ptr, *end;
        !           323: 
        !           324:     assert(P2ALIGNED((unsigned long)buf, sizeof(uint64_t)));
        !           325:     assert(P2ALIGNED(size, sizeof(uint64_t)));
        !           326: 
        !           327:     end = buf + size;
        !           328: 
        !           329:     for (ptr = buf; ptr < end; ptr++)
        !           330:         if (*ptr != pattern)
        !           331:             return kmem_buf_verify_bytes(ptr, &pattern, sizeof(pattern));
        !           332: 
        !           333:     return NULL;
        !           334: }
        !           335: 
        !           336: static void kmem_buf_fill(void *buf, uint64_t pattern, size_t size)
        !           337: {
        !           338:     uint64_t *ptr, *end;
        !           339: 
        !           340:     assert(P2ALIGNED((unsigned long)buf, sizeof(uint64_t)));
        !           341:     assert(P2ALIGNED(size, sizeof(uint64_t)));
        !           342: 
        !           343:     end = buf + size;
        !           344: 
        !           345:     for (ptr = buf; ptr < end; ptr++)
        !           346:         *ptr = pattern;
        !           347: }
        !           348: 
        !           349: static void * kmem_buf_verify_fill(void *buf, uint64_t old, uint64_t new,
        !           350:                                    size_t size)
        !           351: {
        !           352:     uint64_t *ptr, *end;
        !           353: 
        !           354:     assert(P2ALIGNED((unsigned long)buf, sizeof(uint64_t)));
        !           355:     assert(P2ALIGNED(size, sizeof(uint64_t)));
        !           356: 
        !           357:     end = buf + size;
        !           358: 
        !           359:     for (ptr = buf; ptr < end; ptr++) {
        !           360:         if (*ptr != old)
        !           361:             return kmem_buf_verify_bytes(ptr, &old, sizeof(old));
        !           362: 
        !           363:         *ptr = new;
        !           364:     }
        !           365: 
        !           366:     return NULL;
        !           367: }
        !           368: 
        !           369: static inline union kmem_bufctl *
        !           370: kmem_buf_to_bufctl(void *buf, struct kmem_cache *cache)
        !           371: {
        !           372:     return (union kmem_bufctl *)(buf + cache->bufctl_dist);
        !           373: }
        !           374: 
        !           375: static inline struct kmem_buftag *
        !           376: kmem_buf_to_buftag(void *buf, struct kmem_cache *cache)
        !           377: {
        !           378:     return (struct kmem_buftag *)(buf + cache->buftag_dist);
        !           379: }
        !           380: 
        !           381: static inline void * kmem_bufctl_to_buf(union kmem_bufctl *bufctl,
        !           382:                                         struct kmem_cache *cache)
        !           383: {
        !           384:     return (void *)bufctl - cache->bufctl_dist;
        !           385: }
        !           386: 
        !           387: static vm_offset_t kmem_pagealloc(vm_size_t size)
        !           388: {
        !           389:     vm_offset_t addr;
        !           390:     kern_return_t kr;
        !           391: 
        !           392:     kr = kmem_alloc_wired(kmem_map, &addr, size);
        !           393: 
        !           394:     if (kr != KERN_SUCCESS)
        !           395:         return 0;
        !           396: 
        !           397:     return addr;
        !           398: }
        !           399: 
        !           400: static void kmem_pagefree(vm_offset_t ptr, vm_size_t size)
        !           401: {
        !           402:     kmem_free(kmem_map, ptr, size);
        !           403: }
        !           404: 
        !           405: static void kmem_slab_create_verify(struct kmem_slab *slab,
        !           406:                                     struct kmem_cache *cache)
        !           407: {
        !           408:     struct kmem_buftag *buftag;
        !           409:     size_t buf_size;
        !           410:     unsigned long buffers;
        !           411:     void *buf;
        !           412: 
        !           413:     buf_size = cache->buf_size;
        !           414:     buf = slab->addr;
        !           415:     buftag = kmem_buf_to_buftag(buf, cache);
        !           416: 
        !           417:     for (buffers = cache->bufs_per_slab; buffers != 0; buffers--) {
        !           418:         kmem_buf_fill(buf, KMEM_FREE_PATTERN, cache->bufctl_dist);
        !           419:         buftag->state = KMEM_BUFTAG_FREE;
        !           420:         buf += buf_size;
        !           421:         buftag = kmem_buf_to_buftag(buf, cache);
        !           422:     }
        !           423: }
        !           424: 
        !           425: /*
        !           426:  * Create an empty slab for a cache.
        !           427:  *
        !           428:  * The caller must drop all locks before calling this function.
        !           429:  */
        !           430: static struct kmem_slab * kmem_slab_create(struct kmem_cache *cache,
        !           431:                                            size_t color)
        !           432: {
        !           433:     struct kmem_slab *slab;
        !           434:     union kmem_bufctl *bufctl;
        !           435:     size_t buf_size;
        !           436:     unsigned long buffers;
        !           437:     void *slab_buf;
        !           438: 
        !           439:     if (cache->slab_alloc_fn == NULL)
        !           440:         slab_buf = (void *)kmem_pagealloc(cache->slab_size);
        !           441:     else
        !           442:         slab_buf = (void *)cache->slab_alloc_fn(cache->slab_size);
        !           443: 
        !           444:     if (slab_buf == NULL)
        !           445:         return NULL;
        !           446: 
        !           447:     if (cache->flags & KMEM_CF_SLAB_EXTERNAL) {
        !           448:         assert(!(cache->flags & KMEM_CF_NO_RECLAIM));
        !           449:         slab = (struct kmem_slab *)kmem_cache_alloc(&kmem_slab_cache);
        !           450: 
        !           451:         if (slab == NULL) {
        !           452:             if (cache->slab_free_fn == NULL)
        !           453:                 kmem_pagefree((vm_offset_t)slab_buf, cache->slab_size);
        !           454:             else
        !           455:                 cache->slab_free_fn((vm_offset_t)slab_buf, cache->slab_size);
        !           456: 
        !           457:             return NULL;
        !           458:         }
        !           459:     } else {
        !           460:         slab = (struct kmem_slab *)(slab_buf + cache->slab_size) - 1;
        !           461:     }
        !           462: 
        !           463:     list_node_init(&slab->list_node);
        !           464:     rbtree_node_init(&slab->tree_node);
        !           465:     slab->nr_refs = 0;
        !           466:     slab->first_free = NULL;
        !           467:     slab->addr = slab_buf + color;
        !           468: 
        !           469:     buf_size = cache->buf_size;
        !           470:     bufctl = kmem_buf_to_bufctl(slab->addr, cache);
        !           471: 
        !           472:     for (buffers = cache->bufs_per_slab; buffers != 0; buffers--) {
        !           473:         bufctl->next = slab->first_free;
        !           474:         slab->first_free = bufctl;
        !           475:         bufctl = (union kmem_bufctl *)((void *)bufctl + buf_size);
        !           476:     }
        !           477: 
        !           478:     if (cache->flags & KMEM_CF_VERIFY)
        !           479:         kmem_slab_create_verify(slab, cache);
        !           480: 
        !           481:     return slab;
        !           482: }
        !           483: 
        !           484: static void kmem_slab_destroy_verify(struct kmem_slab *slab,
        !           485:                                      struct kmem_cache *cache)
        !           486: {
        !           487:     struct kmem_buftag *buftag;
        !           488:     size_t buf_size;
        !           489:     unsigned long buffers;
        !           490:     void *buf, *addr;
        !           491: 
        !           492:     buf_size = cache->buf_size;
        !           493:     buf = slab->addr;
        !           494:     buftag = kmem_buf_to_buftag(buf, cache);
        !           495: 
        !           496:     for (buffers = cache->bufs_per_slab; buffers != 0; buffers--) {
        !           497:         if (buftag->state != KMEM_BUFTAG_FREE)
        !           498:             kmem_cache_error(cache, buf, KMEM_ERR_BUFTAG, buftag);
        !           499: 
        !           500:         addr = kmem_buf_verify(buf, KMEM_FREE_PATTERN, cache->bufctl_dist);
        !           501: 
        !           502:         if (addr != NULL)
        !           503:             kmem_cache_error(cache, buf, KMEM_ERR_MODIFIED, addr);
        !           504: 
        !           505:         buf += buf_size;
        !           506:         buftag = kmem_buf_to_buftag(buf, cache);
        !           507:     }
        !           508: }
        !           509: 
        !           510: /*
        !           511:  * Destroy a slab.
        !           512:  *
        !           513:  * The caller must drop all locks before calling this function.
        !           514:  */
        !           515: static void kmem_slab_destroy(struct kmem_slab *slab, struct kmem_cache *cache)
        !           516: {
        !           517:     vm_offset_t slab_buf;
        !           518: 
        !           519:     assert(slab->nr_refs == 0);
        !           520:     assert(slab->first_free != NULL);
        !           521:     assert(!(cache->flags & KMEM_CF_NO_RECLAIM));
        !           522: 
        !           523:     if (cache->flags & KMEM_CF_VERIFY)
        !           524:         kmem_slab_destroy_verify(slab, cache);
        !           525: 
        !           526:     slab_buf = (vm_offset_t)P2ALIGN((unsigned long)slab->addr, PAGE_SIZE);
        !           527: 
        !           528:     if (cache->slab_free_fn == NULL)
        !           529:         kmem_pagefree(slab_buf, cache->slab_size);
        !           530:     else
        !           531:         cache->slab_free_fn(slab_buf, cache->slab_size);
        !           532: 
        !           533:     if (cache->flags & KMEM_CF_SLAB_EXTERNAL)
        !           534:         kmem_cache_free(&kmem_slab_cache, (vm_offset_t)slab);
        !           535: }
        !           536: 
        !           537: static inline int kmem_slab_use_tree(int flags)
        !           538: {
        !           539:     return !(flags & KMEM_CF_DIRECT) || (flags & KMEM_CF_VERIFY);
        !           540: }
        !           541: 
        !           542: static inline int kmem_slab_cmp_lookup(const void *addr,
        !           543:                                        const struct rbtree_node *node)
        !           544: {
        !           545:     struct kmem_slab *slab;
        !           546: 
        !           547:     slab = rbtree_entry(node, struct kmem_slab, tree_node);
        !           548: 
        !           549:     if (addr == slab->addr)
        !           550:         return 0;
        !           551:     else if (addr < slab->addr)
        !           552:         return -1;
        !           553:     else
        !           554:         return 1;
        !           555: }
        !           556: 
        !           557: static inline int kmem_slab_cmp_insert(const struct rbtree_node *a,
        !           558:                                        const struct rbtree_node *b)
        !           559: {
        !           560:     struct kmem_slab *slab;
        !           561: 
        !           562:     slab = rbtree_entry(a, struct kmem_slab, tree_node);
        !           563:     return kmem_slab_cmp_lookup(slab->addr, b);
        !           564: }
        !           565: 
        !           566: #if SLAB_USE_CPU_POOLS
        !           567: static void kmem_cpu_pool_init(struct kmem_cpu_pool *cpu_pool,
        !           568:                                struct kmem_cache *cache)
        !           569: {
        !           570:     simple_lock_init(&cpu_pool->lock);
        !           571:     cpu_pool->flags = cache->flags;
        !           572:     cpu_pool->size = 0;
        !           573:     cpu_pool->transfer_size = 0;
        !           574:     cpu_pool->nr_objs = 0;
        !           575:     cpu_pool->array = NULL;
        !           576: }
        !           577: 
        !           578: /*
        !           579:  * Return a CPU pool.
        !           580:  *
        !           581:  * This function will generally return the pool matching the CPU running the
        !           582:  * calling thread. Because of context switches and thread migration, the
        !           583:  * caller might be running on another processor after this function returns.
        !           584:  * Although not optimal, this should rarely happen, and it doesn't affect the
        !           585:  * allocator operations in any other way, as CPU pools are always valid, and
        !           586:  * their access is serialized by a lock.
        !           587:  */
        !           588: static inline struct kmem_cpu_pool * kmem_cpu_pool_get(struct kmem_cache *cache)
        !           589: {
        !           590:     return &cache->cpu_pools[cpu_number()];
        !           591: }
        !           592: 
        !           593: static inline void kmem_cpu_pool_build(struct kmem_cpu_pool *cpu_pool,
        !           594:                                        struct kmem_cache *cache, void **array)
        !           595: {
        !           596:     cpu_pool->size = cache->cpu_pool_type->array_size;
        !           597:     cpu_pool->transfer_size = (cpu_pool->size
        !           598:                                + KMEM_CPU_POOL_TRANSFER_RATIO - 1)
        !           599:                               / KMEM_CPU_POOL_TRANSFER_RATIO;
        !           600:     cpu_pool->array = array;
        !           601: }
        !           602: 
        !           603: static inline void * kmem_cpu_pool_pop(struct kmem_cpu_pool *cpu_pool)
        !           604: {
        !           605:     cpu_pool->nr_objs--;
        !           606:     return cpu_pool->array[cpu_pool->nr_objs];
        !           607: }
        !           608: 
        !           609: static inline void kmem_cpu_pool_push(struct kmem_cpu_pool *cpu_pool, void *obj)
        !           610: {
        !           611:     cpu_pool->array[cpu_pool->nr_objs] = obj;
        !           612:     cpu_pool->nr_objs++;
        !           613: }
        !           614: 
        !           615: static int kmem_cpu_pool_fill(struct kmem_cpu_pool *cpu_pool,
        !           616:                               struct kmem_cache *cache)
        !           617: {
        !           618:     kmem_cache_ctor_t ctor;
        !           619:     void *buf;
        !           620:     int i;
        !           621: 
        !           622:     ctor = (cpu_pool->flags & KMEM_CF_VERIFY) ? NULL : cache->ctor;
        !           623: 
        !           624:     simple_lock(&cache->lock);
        !           625: 
        !           626:     for (i = 0; i < cpu_pool->transfer_size; i++) {
        !           627:         buf = kmem_cache_alloc_from_slab(cache);
        !           628: 
        !           629:         if (buf == NULL)
        !           630:             break;
        !           631: 
        !           632:         if (ctor != NULL)
        !           633:             ctor(buf);
        !           634: 
        !           635:         kmem_cpu_pool_push(cpu_pool, buf);
        !           636:     }
        !           637: 
        !           638:     simple_unlock(&cache->lock);
        !           639: 
        !           640:     return i;
        !           641: }
        !           642: 
        !           643: static void kmem_cpu_pool_drain(struct kmem_cpu_pool *cpu_pool,
        !           644:                                 struct kmem_cache *cache)
        !           645: {
        !           646:     void *obj;
        !           647:     int i;
        !           648: 
        !           649:     simple_lock(&cache->lock);
        !           650: 
        !           651:     for (i = cpu_pool->transfer_size; i > 0; i--) {
        !           652:         obj = kmem_cpu_pool_pop(cpu_pool);
        !           653:         kmem_cache_free_to_slab(cache, obj);
        !           654:     }
        !           655: 
        !           656:     simple_unlock(&cache->lock);
        !           657: }
        !           658: #endif /* SLAB_USE_CPU_POOLS */
        !           659: 
        !           660: static void kmem_cache_error(struct kmem_cache *cache, void *buf, int error,
        !           661:                              void *arg)
        !           662: {
        !           663:     struct kmem_buftag *buftag;
        !           664: 
        !           665:     kmem_error("cache: %s, buffer: %p", cache->name, (void *)buf);
        !           666: 
        !           667:     switch(error) {
        !           668:     case KMEM_ERR_INVALID:
        !           669:         kmem_error("freeing invalid address");
        !           670:         break;
        !           671:     case KMEM_ERR_DOUBLEFREE:
        !           672:         kmem_error("attempting to free the same address twice");
        !           673:         break;
        !           674:     case KMEM_ERR_BUFTAG:
        !           675:         buftag = arg;
        !           676:         kmem_error("invalid buftag content, buftag state: %p",
        !           677:                    (void *)buftag->state);
        !           678:         break;
        !           679:     case KMEM_ERR_MODIFIED:
        !           680:         kmem_error("free buffer modified, fault address: %p, "
        !           681:                    "offset in buffer: %td", arg, arg - buf);
        !           682:         break;
        !           683:     case KMEM_ERR_REDZONE:
        !           684:         kmem_error("write beyond end of buffer, fault address: %p, "
        !           685:                    "offset in buffer: %td", arg, arg - buf);
        !           686:         break;
        !           687:     default:
        !           688:         kmem_error("unknown error");
        !           689:     }
        !           690: 
        !           691:     /*
        !           692:      * Never reached.
        !           693:      */
        !           694: }
        !           695: 
        !           696: /*
        !           697:  * Compute an appropriate slab size for the given cache.
        !           698:  *
        !           699:  * Once the slab size is known, this function sets the related properties
        !           700:  * (buffers per slab and maximum color). It can also set the KMEM_CF_DIRECT
        !           701:  * and/or KMEM_CF_SLAB_EXTERNAL flags depending on the resulting layout.
        !           702:  */
        !           703: static void kmem_cache_compute_sizes(struct kmem_cache *cache, int flags)
        !           704: {
        !           705:     size_t i, buffers, buf_size, slab_size, free_slab_size, optimal_size;
        !           706:     size_t waste, waste_min;
        !           707:     int embed, optimal_embed = optimal_embed;
        !           708: 
        !           709:     buf_size = cache->buf_size;
        !           710: 
        !           711:     if (buf_size < KMEM_BUF_SIZE_THRESHOLD)
        !           712:         flags |= KMEM_CACHE_NOOFFSLAB;
        !           713: 
        !           714:     i = 0;
        !           715:     waste_min = (size_t)-1;
        !           716: 
        !           717:     do {
        !           718:         i++;
        !           719:         slab_size = P2ROUND(i * buf_size, PAGE_SIZE);
        !           720:         free_slab_size = slab_size;
        !           721: 
        !           722:         if (flags & KMEM_CACHE_NOOFFSLAB)
        !           723:             free_slab_size -= sizeof(struct kmem_slab);
        !           724: 
        !           725:         buffers = free_slab_size / buf_size;
        !           726:         waste = free_slab_size % buf_size;
        !           727: 
        !           728:         if (buffers > i)
        !           729:             i = buffers;
        !           730: 
        !           731:         if (flags & KMEM_CACHE_NOOFFSLAB)
        !           732:             embed = 1;
        !           733:         else if (sizeof(struct kmem_slab) <= waste) {
        !           734:             embed = 1;
        !           735:             waste -= sizeof(struct kmem_slab);
        !           736:         } else {
        !           737:             embed = 0;
        !           738:         }
        !           739: 
        !           740:         if (waste <= waste_min) {
        !           741:             waste_min = waste;
        !           742:             optimal_size = slab_size;
        !           743:             optimal_embed = embed;
        !           744:         }
        !           745:     } while ((buffers < KMEM_MIN_BUFS_PER_SLAB)
        !           746:              && (slab_size < KMEM_SLAB_SIZE_THRESHOLD));
        !           747: 
        !           748:     assert(!(flags & KMEM_CACHE_NOOFFSLAB) || optimal_embed);
        !           749: 
        !           750:     cache->slab_size = optimal_size;
        !           751:     slab_size = cache->slab_size - (optimal_embed
        !           752:                 ? sizeof(struct kmem_slab)
        !           753:                 : 0);
        !           754:     cache->bufs_per_slab = slab_size / buf_size;
        !           755:     cache->color_max = slab_size % buf_size;
        !           756: 
        !           757:     if (cache->color_max >= PAGE_SIZE)
        !           758:         cache->color_max = PAGE_SIZE - 1;
        !           759: 
        !           760:     if (optimal_embed) {
        !           761:         if (cache->slab_size == PAGE_SIZE)
        !           762:             cache->flags |= KMEM_CF_DIRECT;
        !           763:     } else {
        !           764:         cache->flags |= KMEM_CF_SLAB_EXTERNAL;
        !           765:     }
        !           766: }
        !           767: 
        !           768: void kmem_cache_init(struct kmem_cache *cache, const char *name,
        !           769:                      size_t obj_size, size_t align, kmem_cache_ctor_t ctor,
        !           770:                      kmem_slab_alloc_fn_t slab_alloc_fn,
        !           771:                      kmem_slab_free_fn_t slab_free_fn, int flags)
        !           772: {
        !           773: #if SLAB_USE_CPU_POOLS
        !           774:     struct kmem_cpu_pool_type *cpu_pool_type;
        !           775:     size_t i;
        !           776: #endif /* SLAB_USE_CPU_POOLS */
        !           777:     size_t buf_size;
        !           778: 
        !           779: #if SLAB_VERIFY
        !           780:     cache->flags = KMEM_CF_VERIFY;
        !           781: #else /* SLAB_VERIFY */
        !           782:     cache->flags = 0;
        !           783: #endif /* SLAB_VERIFY */
        !           784: 
        !           785:     if (flags & KMEM_CACHE_NOCPUPOOL)
        !           786:         cache->flags |= KMEM_CF_NO_CPU_POOL;
        !           787: 
        !           788:     if (flags & KMEM_CACHE_NORECLAIM) {
        !           789:         assert(slab_free_fn == NULL);
        !           790:         flags |= KMEM_CACHE_NOOFFSLAB;
        !           791:         cache->flags |= KMEM_CF_NO_RECLAIM;
        !           792:     }
        !           793: 
        !           794:     if (flags & KMEM_CACHE_VERIFY)
        !           795:         cache->flags |= KMEM_CF_VERIFY;
        !           796: 
        !           797:     if (align < KMEM_ALIGN_MIN)
        !           798:         align = KMEM_ALIGN_MIN;
        !           799: 
        !           800:     assert(obj_size > 0);
        !           801:     assert(ISP2(align));
        !           802:     assert(align < PAGE_SIZE);
        !           803: 
        !           804:     buf_size = P2ROUND(obj_size, align);
        !           805: 
        !           806:     simple_lock_init(&cache->lock);
        !           807:     list_node_init(&cache->node);
        !           808:     list_init(&cache->partial_slabs);
        !           809:     list_init(&cache->free_slabs);
        !           810:     rbtree_init(&cache->active_slabs);
        !           811:     cache->obj_size = obj_size;
        !           812:     cache->align = align;
        !           813:     cache->buf_size = buf_size;
        !           814:     cache->bufctl_dist = buf_size - sizeof(union kmem_bufctl);
        !           815:     cache->color = 0;
        !           816:     cache->nr_objs = 0;
        !           817:     cache->nr_bufs = 0;
        !           818:     cache->nr_slabs = 0;
        !           819:     cache->nr_free_slabs = 0;
        !           820:     cache->ctor = ctor;
        !           821:     cache->slab_alloc_fn = slab_alloc_fn;
        !           822:     cache->slab_free_fn = slab_free_fn;
        !           823:     strncpy(cache->name, name, sizeof(cache->name));
        !           824:     cache->name[sizeof(cache->name) - 1] = '\0';
        !           825:     cache->buftag_dist = 0;
        !           826:     cache->redzone_pad = 0;
        !           827: 
        !           828:     if (cache->flags & KMEM_CF_VERIFY) {
        !           829:         cache->bufctl_dist = buf_size;
        !           830:         cache->buftag_dist = cache->bufctl_dist + sizeof(union kmem_bufctl);
        !           831:         cache->redzone_pad = cache->bufctl_dist - cache->obj_size;
        !           832:         buf_size += sizeof(union kmem_bufctl) + sizeof(struct kmem_buftag);
        !           833:         buf_size = P2ROUND(buf_size, align);
        !           834:         cache->buf_size = buf_size;
        !           835:     }
        !           836: 
        !           837:     kmem_cache_compute_sizes(cache, flags);
        !           838: 
        !           839: #if SLAB_USE_CPU_POOLS
        !           840:     for (cpu_pool_type = kmem_cpu_pool_types;
        !           841:          buf_size <= cpu_pool_type->buf_size;
        !           842:          cpu_pool_type++);
        !           843: 
        !           844:     cache->cpu_pool_type = cpu_pool_type;
        !           845: 
        !           846:     for (i = 0; i < ARRAY_SIZE(cache->cpu_pools); i++)
        !           847:         kmem_cpu_pool_init(&cache->cpu_pools[i], cache);
        !           848: #endif /* SLAB_USE_CPU_POOLS */
        !           849: 
        !           850:     simple_lock(&kmem_cache_list_lock);
        !           851:     list_insert_tail(&kmem_cache_list, &cache->node);
        !           852:     kmem_nr_caches++;
        !           853:     simple_unlock(&kmem_cache_list_lock);
        !           854: }
        !           855: 
        !           856: static inline int kmem_cache_empty(struct kmem_cache *cache)
        !           857: {
        !           858:     return cache->nr_objs == cache->nr_bufs;
        !           859: }
        !           860: 
        !           861: static int kmem_cache_grow(struct kmem_cache *cache)
        !           862: {
        !           863:     struct kmem_slab *slab;
        !           864:     size_t color;
        !           865:     int empty;
        !           866: 
        !           867:     simple_lock(&cache->lock);
        !           868: 
        !           869:     if (!kmem_cache_empty(cache)) {
        !           870:         simple_unlock(&cache->lock);
        !           871:         return 1;
        !           872:     }
        !           873: 
        !           874:     color = cache->color;
        !           875:     cache->color += cache->align;
        !           876: 
        !           877:     if (cache->color > cache->color_max)
        !           878:         cache->color = 0;
        !           879: 
        !           880:     simple_unlock(&cache->lock);
        !           881: 
        !           882:     slab = kmem_slab_create(cache, color);
        !           883: 
        !           884:     simple_lock(&cache->lock);
        !           885: 
        !           886:     if (slab != NULL) {
        !           887:         list_insert_head(&cache->free_slabs, &slab->list_node);
        !           888:         cache->nr_bufs += cache->bufs_per_slab;
        !           889:         cache->nr_slabs++;
        !           890:         cache->nr_free_slabs++;
        !           891:     }
        !           892: 
        !           893:     /*
        !           894:      * Even if our slab creation failed, another thread might have succeeded
        !           895:      * in growing the cache.
        !           896:      */
        !           897:     empty = kmem_cache_empty(cache);
        !           898: 
        !           899:     simple_unlock(&cache->lock);
        !           900: 
        !           901:     return !empty;
        !           902: }
        !           903: 
        !           904: static void kmem_cache_reap(struct kmem_cache *cache)
        !           905: {
        !           906:     struct kmem_slab *slab;
        !           907:     struct list dead_slabs;
        !           908:     unsigned long nr_free_slabs;
        !           909: 
        !           910:     if (cache->flags & KMEM_CF_NO_RECLAIM)
        !           911:         return;
        !           912: 
        !           913:     simple_lock(&cache->lock);
        !           914:     list_set_head(&dead_slabs, &cache->free_slabs);
        !           915:     list_init(&cache->free_slabs);
        !           916:     nr_free_slabs = cache->nr_free_slabs;
        !           917:     cache->nr_bufs -= cache->bufs_per_slab * nr_free_slabs;
        !           918:     cache->nr_slabs -= nr_free_slabs;
        !           919:     cache->nr_free_slabs = 0;
        !           920:     simple_unlock(&cache->lock);
        !           921: 
        !           922:     while (!list_empty(&dead_slabs)) {
        !           923:         slab = list_first_entry(&dead_slabs, struct kmem_slab, list_node);
        !           924:         list_remove(&slab->list_node);
        !           925:         kmem_slab_destroy(slab, cache);
        !           926:         nr_free_slabs--;
        !           927:     }
        !           928: 
        !           929:     assert(nr_free_slabs == 0);
        !           930: }
        !           931: 
        !           932: /*
        !           933:  * Allocate a raw (unconstructed) buffer from the slab layer of a cache.
        !           934:  *
        !           935:  * The cache must be locked before calling this function.
        !           936:  */
        !           937: static void * kmem_cache_alloc_from_slab(struct kmem_cache *cache)
        !           938: {
        !           939:     struct kmem_slab *slab;
        !           940:     union kmem_bufctl *bufctl;
        !           941: 
        !           942:     if (!list_empty(&cache->partial_slabs))
        !           943:         slab = list_first_entry(&cache->partial_slabs, struct kmem_slab,
        !           944:                                 list_node);
        !           945:     else if (!list_empty(&cache->free_slabs))
        !           946:         slab = list_first_entry(&cache->free_slabs, struct kmem_slab,
        !           947:                                 list_node);
        !           948:     else
        !           949:         return NULL;
        !           950: 
        !           951:     bufctl = slab->first_free;
        !           952:     assert(bufctl != NULL);
        !           953:     slab->first_free = bufctl->next;
        !           954:     slab->nr_refs++;
        !           955:     cache->nr_objs++;
        !           956: 
        !           957:     if (slab->nr_refs == cache->bufs_per_slab) {
        !           958:         /* The slab has become complete */
        !           959:         list_remove(&slab->list_node);
        !           960: 
        !           961:         if (slab->nr_refs == 1)
        !           962:             cache->nr_free_slabs--;
        !           963:     } else if (slab->nr_refs == 1) {
        !           964:         /*
        !           965:          * The slab has become partial. Insert the new slab at the end of
        !           966:          * the list to reduce fragmentation.
        !           967:          */
        !           968:         list_remove(&slab->list_node);
        !           969:         list_insert_tail(&cache->partial_slabs, &slab->list_node);
        !           970:         cache->nr_free_slabs--;
        !           971:     }
        !           972: 
        !           973:     if ((slab->nr_refs == 1) && kmem_slab_use_tree(cache->flags))
        !           974:         rbtree_insert(&cache->active_slabs, &slab->tree_node,
        !           975:                       kmem_slab_cmp_insert);
        !           976: 
        !           977:     return kmem_bufctl_to_buf(bufctl, cache);
        !           978: }
        !           979: 
        !           980: /*
        !           981:  * Release a buffer to the slab layer of a cache.
        !           982:  *
        !           983:  * The cache must be locked before calling this function.
        !           984:  */
        !           985: static void kmem_cache_free_to_slab(struct kmem_cache *cache, void *buf)
        !           986: {
        !           987:     struct kmem_slab *slab;
        !           988:     union kmem_bufctl *bufctl;
        !           989: 
        !           990:     if (cache->flags & KMEM_CF_DIRECT) {
        !           991:         assert(cache->slab_size == PAGE_SIZE);
        !           992:         slab = (struct kmem_slab *)P2END((unsigned long)buf, cache->slab_size)
        !           993:                - 1;
        !           994:     } else {
        !           995:         struct rbtree_node *node;
        !           996: 
        !           997:         node = rbtree_lookup_nearest(&cache->active_slabs, buf,
        !           998:                                      kmem_slab_cmp_lookup, RBTREE_LEFT);
        !           999:         assert(node != NULL);
        !          1000:         slab = rbtree_entry(node, struct kmem_slab, tree_node);
        !          1001:         assert((unsigned long)buf < (P2ALIGN((unsigned long)slab->addr
        !          1002:                                              + cache->slab_size, PAGE_SIZE)));
        !          1003:     }
        !          1004: 
        !          1005:     assert(slab->nr_refs >= 1);
        !          1006:     assert(slab->nr_refs <= cache->bufs_per_slab);
        !          1007:     bufctl = kmem_buf_to_bufctl(buf, cache);
        !          1008:     bufctl->next = slab->first_free;
        !          1009:     slab->first_free = bufctl;
        !          1010:     slab->nr_refs--;
        !          1011:     cache->nr_objs--;
        !          1012: 
        !          1013:     if (slab->nr_refs == 0) {
        !          1014:         /* The slab has become free */
        !          1015: 
        !          1016:         if (kmem_slab_use_tree(cache->flags))
        !          1017:             rbtree_remove(&cache->active_slabs, &slab->tree_node);
        !          1018: 
        !          1019:         if (cache->bufs_per_slab > 1)
        !          1020:             list_remove(&slab->list_node);
        !          1021: 
        !          1022:         list_insert_head(&cache->free_slabs, &slab->list_node);
        !          1023:         cache->nr_free_slabs++;
        !          1024:     } else if (slab->nr_refs == (cache->bufs_per_slab - 1)) {
        !          1025:         /* The slab has become partial */
        !          1026:         list_insert_head(&cache->partial_slabs, &slab->list_node);
        !          1027:     }
        !          1028: }
        !          1029: 
        !          1030: static void kmem_cache_alloc_verify(struct kmem_cache *cache, void *buf,
        !          1031:                                     int construct)
        !          1032: {
        !          1033:     struct kmem_buftag *buftag;
        !          1034:     union kmem_bufctl *bufctl;
        !          1035:     void *addr;
        !          1036: 
        !          1037:     buftag = kmem_buf_to_buftag(buf, cache);
        !          1038: 
        !          1039:     if (buftag->state != KMEM_BUFTAG_FREE)
        !          1040:         kmem_cache_error(cache, buf, KMEM_ERR_BUFTAG, buftag);
        !          1041: 
        !          1042:     addr = kmem_buf_verify_fill(buf, KMEM_FREE_PATTERN, KMEM_UNINIT_PATTERN,
        !          1043:                                 cache->bufctl_dist);
        !          1044: 
        !          1045:     if (addr != NULL)
        !          1046:         kmem_cache_error(cache, buf, KMEM_ERR_MODIFIED, addr);
        !          1047: 
        !          1048:     addr = buf + cache->obj_size;
        !          1049:     memset(addr, KMEM_REDZONE_BYTE, cache->redzone_pad);
        !          1050: 
        !          1051:     bufctl = kmem_buf_to_bufctl(buf, cache);
        !          1052:     bufctl->redzone = KMEM_REDZONE_WORD;
        !          1053:     buftag->state = KMEM_BUFTAG_ALLOC;
        !          1054: 
        !          1055:     if (construct && (cache->ctor != NULL))
        !          1056:         cache->ctor(buf);
        !          1057: }
        !          1058: 
        !          1059: vm_offset_t kmem_cache_alloc(struct kmem_cache *cache)
        !          1060: {
        !          1061:     int filled;
        !          1062:     void *buf;
        !          1063: 
        !          1064: #if SLAB_USE_CPU_POOLS
        !          1065:     struct kmem_cpu_pool *cpu_pool;
        !          1066: 
        !          1067:     cpu_pool = kmem_cpu_pool_get(cache);
        !          1068: 
        !          1069:     if (cpu_pool->flags & KMEM_CF_NO_CPU_POOL)
        !          1070:         goto slab_alloc;
        !          1071: 
        !          1072:     simple_lock(&cpu_pool->lock);
        !          1073: 
        !          1074: fast_alloc:
        !          1075:     if (likely(cpu_pool->nr_objs > 0)) {
        !          1076:         buf = kmem_cpu_pool_pop(cpu_pool);
        !          1077:         simple_unlock(&cpu_pool->lock);
        !          1078: 
        !          1079:         if (cpu_pool->flags & KMEM_CF_VERIFY)
        !          1080:             kmem_cache_alloc_verify(cache, buf, KMEM_AV_CONSTRUCT);
        !          1081: 
        !          1082:         return (vm_offset_t)buf;
        !          1083:     }
        !          1084: 
        !          1085:     if (cpu_pool->array != NULL) {
        !          1086:         filled = kmem_cpu_pool_fill(cpu_pool, cache);
        !          1087: 
        !          1088:         if (!filled) {
        !          1089:             simple_unlock(&cpu_pool->lock);
        !          1090: 
        !          1091:             filled = kmem_cache_grow(cache);
        !          1092: 
        !          1093:             if (!filled)
        !          1094:                 return 0;
        !          1095: 
        !          1096:             simple_lock(&cpu_pool->lock);
        !          1097:         }
        !          1098: 
        !          1099:         goto fast_alloc;
        !          1100:     }
        !          1101: 
        !          1102:     simple_unlock(&cpu_pool->lock);
        !          1103: #endif /* SLAB_USE_CPU_POOLS */
        !          1104: 
        !          1105: slab_alloc:
        !          1106:     simple_lock(&cache->lock);
        !          1107:     buf = kmem_cache_alloc_from_slab(cache);
        !          1108:     simple_unlock(&cache->lock);
        !          1109: 
        !          1110:     if (buf == NULL) {
        !          1111:         filled = kmem_cache_grow(cache);
        !          1112: 
        !          1113:         if (!filled)
        !          1114:             return 0;
        !          1115: 
        !          1116:         goto slab_alloc;
        !          1117:     }
        !          1118: 
        !          1119:     if (cache->flags & KMEM_CF_VERIFY)
        !          1120:         kmem_cache_alloc_verify(cache, buf, KMEM_AV_NOCONSTRUCT);
        !          1121: 
        !          1122:     if (cache->ctor != NULL)
        !          1123:         cache->ctor(buf);
        !          1124: 
        !          1125:     return (vm_offset_t)buf;
        !          1126: }
        !          1127: 
        !          1128: static void kmem_cache_free_verify(struct kmem_cache *cache, void *buf)
        !          1129: {
        !          1130:     struct rbtree_node *node;
        !          1131:     struct kmem_buftag *buftag;
        !          1132:     struct kmem_slab *slab;
        !          1133:     union kmem_bufctl *bufctl;
        !          1134:     unsigned char *redzone_byte;
        !          1135:     unsigned long slabend;
        !          1136: 
        !          1137:     simple_lock(&cache->lock);
        !          1138:     node = rbtree_lookup_nearest(&cache->active_slabs, buf,
        !          1139:                                  kmem_slab_cmp_lookup, RBTREE_LEFT);
        !          1140:     simple_unlock(&cache->lock);
        !          1141: 
        !          1142:     if (node == NULL)
        !          1143:         kmem_cache_error(cache, buf, KMEM_ERR_INVALID, NULL);
        !          1144: 
        !          1145:     slab = rbtree_entry(node, struct kmem_slab, tree_node);
        !          1146:     slabend = P2ALIGN((unsigned long)slab->addr + cache->slab_size, PAGE_SIZE);
        !          1147: 
        !          1148:     if ((unsigned long)buf >= slabend)
        !          1149:         kmem_cache_error(cache, buf, KMEM_ERR_INVALID, NULL);
        !          1150: 
        !          1151:     if ((((unsigned long)buf - (unsigned long)slab->addr) % cache->buf_size)
        !          1152:         != 0)
        !          1153:         kmem_cache_error(cache, buf, KMEM_ERR_INVALID, NULL);
        !          1154: 
        !          1155:     /*
        !          1156:      * As the buffer address is valid, accessing its buftag is safe.
        !          1157:      */
        !          1158:     buftag = kmem_buf_to_buftag(buf, cache);
        !          1159: 
        !          1160:     if (buftag->state != KMEM_BUFTAG_ALLOC) {
        !          1161:         if (buftag->state == KMEM_BUFTAG_FREE)
        !          1162:             kmem_cache_error(cache, buf, KMEM_ERR_DOUBLEFREE, NULL);
        !          1163:         else
        !          1164:             kmem_cache_error(cache, buf, KMEM_ERR_BUFTAG, buftag);
        !          1165:     }
        !          1166: 
        !          1167:     redzone_byte = buf + cache->obj_size;
        !          1168:     bufctl = kmem_buf_to_bufctl(buf, cache);
        !          1169: 
        !          1170:     while (redzone_byte < (unsigned char *)bufctl) {
        !          1171:         if (*redzone_byte != KMEM_REDZONE_BYTE)
        !          1172:             kmem_cache_error(cache, buf, KMEM_ERR_REDZONE, redzone_byte);
        !          1173: 
        !          1174:         redzone_byte++;
        !          1175:     }
        !          1176: 
        !          1177:     if (bufctl->redzone != KMEM_REDZONE_WORD) {
        !          1178:         unsigned long word;
        !          1179: 
        !          1180:         word = KMEM_REDZONE_WORD;
        !          1181:         redzone_byte = kmem_buf_verify_bytes(&bufctl->redzone, &word,
        !          1182:                                              sizeof(bufctl->redzone));
        !          1183:         kmem_cache_error(cache, buf, KMEM_ERR_REDZONE, redzone_byte);
        !          1184:     }
        !          1185: 
        !          1186:     kmem_buf_fill(buf, KMEM_FREE_PATTERN, cache->bufctl_dist);
        !          1187:     buftag->state = KMEM_BUFTAG_FREE;
        !          1188: }
        !          1189: 
        !          1190: void kmem_cache_free(struct kmem_cache *cache, vm_offset_t obj)
        !          1191: {
        !          1192: #if SLAB_USE_CPU_POOLS
        !          1193:     struct kmem_cpu_pool *cpu_pool;
        !          1194:     void **array;
        !          1195: 
        !          1196:     cpu_pool = kmem_cpu_pool_get(cache);
        !          1197: 
        !          1198:     if (cpu_pool->flags & KMEM_CF_VERIFY) {
        !          1199: #else /* SLAB_USE_CPU_POOLS */
        !          1200:     if (cache->flags & KMEM_CF_VERIFY) {
        !          1201: #endif /* SLAB_USE_CPU_POOLS */
        !          1202:         kmem_cache_free_verify(cache, (void *)obj);
        !          1203:     }
        !          1204: 
        !          1205: #if SLAB_USE_CPU_POOLS
        !          1206:     if (cpu_pool->flags & KMEM_CF_NO_CPU_POOL)
        !          1207:         goto slab_free;
        !          1208: 
        !          1209:     simple_lock(&cpu_pool->lock);
        !          1210: 
        !          1211: fast_free:
        !          1212:     if (likely(cpu_pool->nr_objs < cpu_pool->size)) {
        !          1213:         kmem_cpu_pool_push(cpu_pool, (void *)obj);
        !          1214:         simple_unlock(&cpu_pool->lock);
        !          1215:         return;
        !          1216:     }
        !          1217: 
        !          1218:     if (cpu_pool->array != NULL) {
        !          1219:         kmem_cpu_pool_drain(cpu_pool, cache);
        !          1220:         goto fast_free;
        !          1221:     }
        !          1222: 
        !          1223:     simple_unlock(&cpu_pool->lock);
        !          1224: 
        !          1225:     array = (void *)kmem_cache_alloc(cache->cpu_pool_type->array_cache);
        !          1226: 
        !          1227:     if (array != NULL) {
        !          1228:         simple_lock(&cpu_pool->lock);
        !          1229: 
        !          1230:         /*
        !          1231:          * Another thread may have built the CPU pool while the lock was
        !          1232:          * dropped.
        !          1233:          */
        !          1234:         if (cpu_pool->array != NULL) {
        !          1235:             simple_unlock(&cpu_pool->lock);
        !          1236:             kmem_cache_free(cache->cpu_pool_type->array_cache,
        !          1237:                             (vm_offset_t)array);
        !          1238:             simple_lock(&cpu_pool->lock);
        !          1239:             goto fast_free;
        !          1240:         }
        !          1241: 
        !          1242:         kmem_cpu_pool_build(cpu_pool, cache, array);
        !          1243:         goto fast_free;
        !          1244:     }
        !          1245: 
        !          1246: slab_free:
        !          1247: #endif /* SLAB_USE_CPU_POOLS */
        !          1248: 
        !          1249:     simple_lock(&cache->lock);
        !          1250:     kmem_cache_free_to_slab(cache, (void *)obj);
        !          1251:     simple_unlock(&cache->lock);
        !          1252: }
        !          1253: 
        !          1254: void slab_collect(void)
        !          1255: {
        !          1256:     struct kmem_cache *cache;
        !          1257: 
        !          1258:     if (elapsed_ticks <= (kmem_gc_last_tick + KMEM_GC_INTERVAL))
        !          1259:         return;
        !          1260: 
        !          1261:     kmem_gc_last_tick = elapsed_ticks;
        !          1262: 
        !          1263:     simple_lock(&kmem_cache_list_lock);
        !          1264: 
        !          1265:     list_for_each_entry(&kmem_cache_list, cache, node)
        !          1266:         kmem_cache_reap(cache);
        !          1267: 
        !          1268:     simple_unlock(&kmem_cache_list_lock);
        !          1269: }
        !          1270: 
        !          1271: void slab_bootstrap(void)
        !          1272: {
        !          1273:     /* Make sure a bufctl can always be stored in a buffer */
        !          1274:     assert(sizeof(union kmem_bufctl) <= KMEM_ALIGN_MIN);
        !          1275: 
        !          1276:     list_init(&kmem_cache_list);
        !          1277:     simple_lock_init(&kmem_cache_list_lock);
        !          1278: }
        !          1279: 
        !          1280: void slab_init(void)
        !          1281: {
        !          1282:     vm_offset_t min, max;
        !          1283: 
        !          1284: #if SLAB_USE_CPU_POOLS
        !          1285:     struct kmem_cpu_pool_type *cpu_pool_type;
        !          1286:     char name[KMEM_CACHE_NAME_SIZE];
        !          1287:     size_t i, size;
        !          1288: #endif /* SLAB_USE_CPU_POOLS */
        !          1289: 
        !          1290:     kmem_submap(kmem_map, kernel_map, &min, &max, KMEM_MAP_SIZE, FALSE);
        !          1291: 
        !          1292: #if SLAB_USE_CPU_POOLS
        !          1293:     for (i = 0; i < ARRAY_SIZE(kmem_cpu_pool_types); i++) {
        !          1294:         cpu_pool_type = &kmem_cpu_pool_types[i];
        !          1295:         cpu_pool_type->array_cache = &kmem_cpu_array_caches[i];
        !          1296:         sprintf(name, "kmem_cpu_array_%d", cpu_pool_type->array_size);
        !          1297:         size = sizeof(void *) * cpu_pool_type->array_size;
        !          1298:         kmem_cache_init(cpu_pool_type->array_cache, name, size,
        !          1299:                         cpu_pool_type->array_align, NULL, NULL, NULL, 0);
        !          1300:     }
        !          1301: #endif /* SLAB_USE_CPU_POOLS */
        !          1302: 
        !          1303:     /*
        !          1304:      * Prevent off slab data for the slab cache to avoid infinite recursion.
        !          1305:      */
        !          1306:     kmem_cache_init(&kmem_slab_cache, "kmem_slab", sizeof(struct kmem_slab),
        !          1307:                     0, NULL, NULL, NULL, KMEM_CACHE_NOOFFSLAB);
        !          1308: }
        !          1309: 
        !          1310: static vm_offset_t kalloc_pagealloc(vm_size_t size)
        !          1311: {
        !          1312:     vm_offset_t addr;
        !          1313:     kern_return_t kr;
        !          1314: 
        !          1315:     kr = kmem_alloc_wired(kmem_map, &addr, size);
        !          1316: 
        !          1317:     if (kr != KERN_SUCCESS)
        !          1318:         return 0;
        !          1319: 
        !          1320:     return addr;
        !          1321: }
        !          1322: 
        !          1323: static void kalloc_pagefree(vm_offset_t ptr, vm_size_t size)
        !          1324: {
        !          1325:     kmem_free(kmem_map, ptr, size);
        !          1326: }
        !          1327: 
        !          1328: void kalloc_init(void)
        !          1329: {
        !          1330:     char name[KMEM_CACHE_NAME_SIZE];
        !          1331:     size_t i, size;
        !          1332: 
        !          1333:     size = 1 << KALLOC_FIRST_SHIFT;
        !          1334: 
        !          1335:     for (i = 0; i < ARRAY_SIZE(kalloc_caches); i++) {
        !          1336:         sprintf(name, "kalloc_%lu", size);
        !          1337:         kmem_cache_init(&kalloc_caches[i], name, size, 0, NULL,
        !          1338:                         kalloc_pagealloc, kalloc_pagefree, 0);
        !          1339:         size <<= 1;
        !          1340:     }
        !          1341: }
        !          1342: 
        !          1343: /*
        !          1344:  * Return the kalloc cache index matching the given allocation size, which
        !          1345:  * must be strictly greater than 0.
        !          1346:  */
        !          1347: static inline size_t kalloc_get_index(unsigned long size)
        !          1348: {
        !          1349:     assert(size != 0);
        !          1350: 
        !          1351:     size = (size - 1) >> KALLOC_FIRST_SHIFT;
        !          1352: 
        !          1353:     if (size == 0)
        !          1354:         return 0;
        !          1355:     else
        !          1356:         return (sizeof(long) * 8) - __builtin_clzl(size);
        !          1357: }
        !          1358: 
        !          1359: static void kalloc_verify(struct kmem_cache *cache, void *buf, size_t size)
        !          1360: {
        !          1361:     size_t redzone_size;
        !          1362:     void *redzone;
        !          1363: 
        !          1364:     assert(size <= cache->obj_size);
        !          1365: 
        !          1366:     redzone = buf + size;
        !          1367:     redzone_size = cache->obj_size - size;
        !          1368:     memset(redzone, KMEM_REDZONE_BYTE, redzone_size);
        !          1369: }
        !          1370: 
        !          1371: vm_offset_t kalloc(vm_size_t size)
        !          1372: {
        !          1373:     size_t index;
        !          1374:     void *buf;
        !          1375: 
        !          1376:     if (size == 0)
        !          1377:         return 0;
        !          1378: 
        !          1379:     index = kalloc_get_index(size);
        !          1380: 
        !          1381:     if (index < ARRAY_SIZE(kalloc_caches)) {
        !          1382:         struct kmem_cache *cache;
        !          1383: 
        !          1384:         cache = &kalloc_caches[index];
        !          1385:         buf = (void *)kmem_cache_alloc(cache);
        !          1386: 
        !          1387:         if ((buf != 0) && (cache->flags & KMEM_CF_VERIFY))
        !          1388:             kalloc_verify(cache, buf, size);
        !          1389:     } else
        !          1390:         buf = (void *)kalloc_pagealloc(size);
        !          1391: 
        !          1392:     return (vm_offset_t)buf;
        !          1393: }
        !          1394: 
        !          1395: static void kfree_verify(struct kmem_cache *cache, void *buf, size_t size)
        !          1396: {
        !          1397:     unsigned char *redzone_byte, *redzone_end;
        !          1398: 
        !          1399:     assert(size <= cache->obj_size);
        !          1400: 
        !          1401:     redzone_byte = buf + size;
        !          1402:     redzone_end = buf + cache->obj_size;
        !          1403: 
        !          1404:     while (redzone_byte < redzone_end) {
        !          1405:         if (*redzone_byte != KMEM_REDZONE_BYTE)
        !          1406:             kmem_cache_error(cache, buf, KMEM_ERR_REDZONE, redzone_byte);
        !          1407: 
        !          1408:         redzone_byte++;
        !          1409:     }
        !          1410: }
        !          1411: 
        !          1412: void kfree(vm_offset_t data, vm_size_t size)
        !          1413: {
        !          1414:     size_t index;
        !          1415: 
        !          1416:     if ((data == 0) || (size == 0))
        !          1417:         return;
        !          1418: 
        !          1419:     index = kalloc_get_index(size);
        !          1420: 
        !          1421:     if (index < ARRAY_SIZE(kalloc_caches)) {
        !          1422:         struct kmem_cache *cache;
        !          1423: 
        !          1424:         cache = &kalloc_caches[index];
        !          1425: 
        !          1426:         if (cache->flags & KMEM_CF_VERIFY)
        !          1427:             kfree_verify(cache, (void *)data, size);
        !          1428: 
        !          1429:         kmem_cache_free(cache, data);
        !          1430:     } else {
        !          1431:         kalloc_pagefree(data, size);
        !          1432:     }
        !          1433: }
        !          1434: 
        !          1435: void slab_info(void)
        !          1436: {
        !          1437:     struct kmem_cache *cache;
        !          1438:     vm_size_t mem_usage, mem_reclaimable;
        !          1439: 
        !          1440:     printf("cache                  obj slab  bufs   objs   bufs "
        !          1441:            "   total reclaimable\n"
        !          1442:            "name                  size size /slab  usage  count "
        !          1443:            "  memory      memory\n");
        !          1444: 
        !          1445:     simple_lock(&kmem_cache_list_lock);
        !          1446: 
        !          1447:     list_for_each_entry(&kmem_cache_list, cache, node) {
        !          1448:         simple_lock(&cache->lock);
        !          1449: 
        !          1450:         mem_usage = (cache->nr_slabs * cache->slab_size) >> 10;
        !          1451:         mem_reclaimable = (cache->nr_free_slabs * cache->slab_size) >> 10;
        !          1452: 
        !          1453:         printf("%-19s %6lu %3luk  %4lu %6lu %6lu %7uk %10uk\n",
        !          1454:                cache->name, cache->obj_size, cache->slab_size >> 10,
        !          1455:                cache->bufs_per_slab, cache->nr_objs, cache->nr_bufs,
        !          1456:                mem_usage, mem_reclaimable);
        !          1457: 
        !          1458:         simple_unlock(&cache->lock);
        !          1459:     }
        !          1460: 
        !          1461:     simple_unlock(&kmem_cache_list_lock);
        !          1462: }
        !          1463: 
        !          1464: #if MACH_DEBUG
        !          1465: kern_return_t host_slab_info(host_t host, cache_info_array_t *infop,
        !          1466:                              unsigned int *infoCntp)
        !          1467: {
        !          1468:     struct kmem_cache *cache;
        !          1469:     cache_info_t *info;
        !          1470:     unsigned int i, nr_caches;
        !          1471:     vm_size_t info_size = info_size;
        !          1472:     kern_return_t kr;
        !          1473: 
        !          1474:     if (host == HOST_NULL)
        !          1475:         return KERN_INVALID_HOST;
        !          1476: 
        !          1477:     /*
        !          1478:      * Assume the cache list is unaltered once the kernel is ready.
        !          1479:      */
        !          1480: 
        !          1481:     simple_lock(&kmem_cache_list_lock);
        !          1482:     nr_caches = kmem_nr_caches;
        !          1483:     simple_unlock(&kmem_cache_list_lock);
        !          1484: 
        !          1485:     if (nr_caches <= *infoCntp)
        !          1486:         info = *infop;
        !          1487:     else {
        !          1488:         vm_offset_t info_addr;
        !          1489: 
        !          1490:         info_size = round_page(nr_caches * sizeof(*info));
        !          1491:         kr = kmem_alloc_pageable(ipc_kernel_map, &info_addr, info_size);
        !          1492: 
        !          1493:         if (kr != KERN_SUCCESS)
        !          1494:             return kr;
        !          1495: 
        !          1496:         info = (cache_info_t *)info_addr;
        !          1497:     }
        !          1498: 
        !          1499:     if (info == NULL)
        !          1500:         return KERN_RESOURCE_SHORTAGE;
        !          1501: 
        !          1502:     i = 0;
        !          1503: 
        !          1504:     list_for_each_entry(&kmem_cache_list, cache, node) {
        !          1505:         simple_lock(&cache_lock);
        !          1506:         info[i].flags = ((cache->flags & KMEM_CF_NO_CPU_POOL)
        !          1507:                          ? CACHE_FLAGS_NO_CPU_POOL : 0)
        !          1508:                         | ((cache->flags & KMEM_CF_SLAB_EXTERNAL)
        !          1509:                            ? CACHE_FLAGS_SLAB_EXTERNAL : 0)
        !          1510:                         | ((cache->flags & KMEM_CF_NO_RECLAIM)
        !          1511:                            ? CACHE_FLAGS_NO_RECLAIM : 0)
        !          1512:                         | ((cache->flags & KMEM_CF_VERIFY)
        !          1513:                            ? CACHE_FLAGS_VERIFY : 0)
        !          1514:                         | ((cache->flags & KMEM_CF_DIRECT)
        !          1515:                            ? CACHE_FLAGS_DIRECT : 0);
        !          1516: #if SLAB_USE_CPU_POOLS
        !          1517:         info[i].cpu_pool_size = cache->cpu_pool_type->array_size;
        !          1518: #else /* SLAB_USE_CPU_POOLS */
        !          1519:         info[i].cpu_pool_size = 0;
        !          1520: #endif /* SLAB_USE_CPU_POOLS */
        !          1521:         info[i].obj_size = cache->obj_size;
        !          1522:         info[i].align = cache->align;
        !          1523:         info[i].buf_size = cache->buf_size;
        !          1524:         info[i].slab_size = cache->slab_size;
        !          1525:         info[i].bufs_per_slab = cache->bufs_per_slab;
        !          1526:         info[i].nr_objs = cache->nr_objs;
        !          1527:         info[i].nr_bufs = cache->nr_bufs;
        !          1528:         info[i].nr_slabs = cache->nr_slabs;
        !          1529:         info[i].nr_free_slabs = cache->nr_free_slabs;
        !          1530:         strncpy(info[i].name, cache->name, sizeof(info[i].name));
        !          1531:         info[i].name[sizeof(info[i].name) - 1] = '\0';
        !          1532:         simple_unlock(&cache->lock);
        !          1533: 
        !          1534:         i++;
        !          1535:     }
        !          1536: 
        !          1537:     if (info != *infop) {
        !          1538:         vm_map_copy_t copy;
        !          1539:         vm_size_t used;
        !          1540: 
        !          1541:         used = nr_caches * sizeof(*info);
        !          1542: 
        !          1543:         if (used != info_size)
        !          1544:             memset((char *)info + used, 0, info_size - used);
        !          1545: 
        !          1546:         kr = vm_map_copyin(ipc_kernel_map, (vm_offset_t)info, used, TRUE,
        !          1547:                            &copy);
        !          1548: 
        !          1549:         assert(kr == KERN_SUCCESS);
        !          1550:         *infop = (cache_info_t *)copy;
        !          1551:     }
        !          1552: 
        !          1553:     *infoCntp = nr_caches;
        !          1554: 
        !          1555:     return KERN_SUCCESS;
        !          1556: }
        !          1557: #endif /* MACH_DEBUG */

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.