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