![[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 (;;) {
1.1.1.5 ! root 373: page = vm_page_grab();
1.1.1.4 root 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);
1.1.1.5 ! root 392: vm_page_release(page, FALSE, FALSE);
1.1.1.4 root 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:
1.1.1.5 ! root 498: slab->cache = cache;
1.1 root 499: list_node_init(&slab->list_node);
500: rbtree_node_init(&slab->tree_node);
501: slab->nr_refs = 0;
502: slab->first_free = NULL;
1.1.1.4 root 503: slab->addr = (void *)(slab_buf + color);
1.1 root 504:
505: buf_size = cache->buf_size;
506: bufctl = kmem_buf_to_bufctl(slab->addr, cache);
507:
508: for (buffers = cache->bufs_per_slab; buffers != 0; buffers--) {
509: bufctl->next = slab->first_free;
510: slab->first_free = bufctl;
511: bufctl = (union kmem_bufctl *)((void *)bufctl + buf_size);
512: }
513:
514: if (cache->flags & KMEM_CF_VERIFY)
515: kmem_slab_create_verify(slab, cache);
516:
517: return slab;
518: }
519:
520: static void kmem_slab_destroy_verify(struct kmem_slab *slab,
521: struct kmem_cache *cache)
522: {
523: struct kmem_buftag *buftag;
524: size_t buf_size;
525: unsigned long buffers;
526: void *buf, *addr;
527:
528: buf_size = cache->buf_size;
529: buf = slab->addr;
530: buftag = kmem_buf_to_buftag(buf, cache);
531:
532: for (buffers = cache->bufs_per_slab; buffers != 0; buffers--) {
533: if (buftag->state != KMEM_BUFTAG_FREE)
534: kmem_cache_error(cache, buf, KMEM_ERR_BUFTAG, buftag);
535:
536: addr = kmem_buf_verify(buf, KMEM_FREE_PATTERN, cache->bufctl_dist);
537:
538: if (addr != NULL)
539: kmem_cache_error(cache, buf, KMEM_ERR_MODIFIED, addr);
540:
541: buf += buf_size;
542: buftag = kmem_buf_to_buftag(buf, cache);
543: }
544: }
545:
546: /*
547: * Destroy a slab.
548: *
549: * The caller must drop all locks before calling this function.
550: */
551: static void kmem_slab_destroy(struct kmem_slab *slab, struct kmem_cache *cache)
552: {
553: vm_offset_t slab_buf;
554:
555: assert(slab->nr_refs == 0);
556: assert(slab->first_free != NULL);
557:
558: if (cache->flags & KMEM_CF_VERIFY)
559: kmem_slab_destroy_verify(slab, cache);
560:
561: slab_buf = (vm_offset_t)P2ALIGN((unsigned long)slab->addr, PAGE_SIZE);
562:
1.1.1.4 root 563: if (cache->flags & KMEM_CF_SLAB_EXTERNAL) {
564: if (cache->flags & KMEM_CF_USE_PAGE) {
565: struct vm_page *page;
566:
567: /* Not strictly needed, but let's increase safety */
568: page = vm_page_lookup_pa(kvtophys(slab_buf));
569: assert(page != NULL);
570: vm_page_set_priv(page, NULL);
571: }
1.1 root 572:
573: kmem_cache_free(&kmem_slab_cache, (vm_offset_t)slab);
1.1.1.4 root 574: }
1.1 root 575:
1.1.1.4 root 576: kmem_pagefree(slab_buf, cache->slab_size, cache->flags);
1.1 root 577: }
578:
579: static inline int kmem_slab_cmp_lookup(const void *addr,
580: const struct rbtree_node *node)
581: {
582: struct kmem_slab *slab;
583:
584: slab = rbtree_entry(node, struct kmem_slab, tree_node);
585:
586: if (addr == slab->addr)
587: return 0;
588: else if (addr < slab->addr)
589: return -1;
590: else
591: return 1;
592: }
593:
594: static inline int kmem_slab_cmp_insert(const struct rbtree_node *a,
595: const struct rbtree_node *b)
596: {
597: struct kmem_slab *slab;
598:
599: slab = rbtree_entry(a, struct kmem_slab, tree_node);
600: return kmem_slab_cmp_lookup(slab->addr, b);
601: }
602:
603: #if SLAB_USE_CPU_POOLS
604: static void kmem_cpu_pool_init(struct kmem_cpu_pool *cpu_pool,
605: struct kmem_cache *cache)
606: {
607: simple_lock_init(&cpu_pool->lock);
608: cpu_pool->flags = cache->flags;
609: cpu_pool->size = 0;
610: cpu_pool->transfer_size = 0;
611: cpu_pool->nr_objs = 0;
612: cpu_pool->array = NULL;
613: }
614:
615: /*
616: * Return a CPU pool.
617: *
618: * This function will generally return the pool matching the CPU running the
619: * calling thread. Because of context switches and thread migration, the
620: * caller might be running on another processor after this function returns.
621: * Although not optimal, this should rarely happen, and it doesn't affect the
622: * allocator operations in any other way, as CPU pools are always valid, and
623: * their access is serialized by a lock.
624: */
625: static inline struct kmem_cpu_pool * kmem_cpu_pool_get(struct kmem_cache *cache)
626: {
627: return &cache->cpu_pools[cpu_number()];
628: }
629:
630: static inline void kmem_cpu_pool_build(struct kmem_cpu_pool *cpu_pool,
631: struct kmem_cache *cache, void **array)
632: {
633: cpu_pool->size = cache->cpu_pool_type->array_size;
634: cpu_pool->transfer_size = (cpu_pool->size
635: + KMEM_CPU_POOL_TRANSFER_RATIO - 1)
636: / KMEM_CPU_POOL_TRANSFER_RATIO;
637: cpu_pool->array = array;
638: }
639:
640: static inline void * kmem_cpu_pool_pop(struct kmem_cpu_pool *cpu_pool)
641: {
642: cpu_pool->nr_objs--;
643: return cpu_pool->array[cpu_pool->nr_objs];
644: }
645:
646: static inline void kmem_cpu_pool_push(struct kmem_cpu_pool *cpu_pool, void *obj)
647: {
648: cpu_pool->array[cpu_pool->nr_objs] = obj;
649: cpu_pool->nr_objs++;
650: }
651:
652: static int kmem_cpu_pool_fill(struct kmem_cpu_pool *cpu_pool,
653: struct kmem_cache *cache)
654: {
655: kmem_cache_ctor_t ctor;
656: void *buf;
657: int i;
658:
659: ctor = (cpu_pool->flags & KMEM_CF_VERIFY) ? NULL : cache->ctor;
660:
661: simple_lock(&cache->lock);
662:
663: for (i = 0; i < cpu_pool->transfer_size; i++) {
664: buf = kmem_cache_alloc_from_slab(cache);
665:
666: if (buf == NULL)
667: break;
668:
669: if (ctor != NULL)
670: ctor(buf);
671:
672: kmem_cpu_pool_push(cpu_pool, buf);
673: }
674:
675: simple_unlock(&cache->lock);
676:
677: return i;
678: }
679:
680: static void kmem_cpu_pool_drain(struct kmem_cpu_pool *cpu_pool,
681: struct kmem_cache *cache)
682: {
683: void *obj;
684: int i;
685:
686: simple_lock(&cache->lock);
687:
688: for (i = cpu_pool->transfer_size; i > 0; i--) {
689: obj = kmem_cpu_pool_pop(cpu_pool);
690: kmem_cache_free_to_slab(cache, obj);
691: }
692:
693: simple_unlock(&cache->lock);
694: }
695: #endif /* SLAB_USE_CPU_POOLS */
696:
697: static void kmem_cache_error(struct kmem_cache *cache, void *buf, int error,
698: void *arg)
699: {
700: struct kmem_buftag *buftag;
701:
1.1.1.2 root 702: kmem_warn("cache: %s, buffer: %p", cache->name, (void *)buf);
1.1 root 703:
704: switch(error) {
705: case KMEM_ERR_INVALID:
706: kmem_error("freeing invalid address");
707: break;
708: case KMEM_ERR_DOUBLEFREE:
709: kmem_error("attempting to free the same address twice");
710: break;
711: case KMEM_ERR_BUFTAG:
712: buftag = arg;
713: kmem_error("invalid buftag content, buftag state: %p",
714: (void *)buftag->state);
715: break;
716: case KMEM_ERR_MODIFIED:
717: kmem_error("free buffer modified, fault address: %p, "
718: "offset in buffer: %td", arg, arg - buf);
719: break;
720: case KMEM_ERR_REDZONE:
721: kmem_error("write beyond end of buffer, fault address: %p, "
722: "offset in buffer: %td", arg, arg - buf);
723: break;
724: default:
725: kmem_error("unknown error");
726: }
727:
728: /*
729: * Never reached.
730: */
731: }
732:
733: /*
1.1.1.4 root 734: * Compute properties such as slab size for the given cache.
1.1 root 735: *
736: * Once the slab size is known, this function sets the related properties
1.1.1.4 root 737: * (buffers per slab and maximum color). It can also set some KMEM_CF_xxx
738: * flags depending on the resulting layout.
1.1 root 739: */
1.1.1.4 root 740: static void kmem_cache_compute_properties(struct kmem_cache *cache, int flags)
1.1 root 741: {
1.1.1.4 root 742: size_t size, waste;
743: int embed;
1.1 root 744:
1.1.1.4 root 745: if (cache->buf_size < KMEM_BUF_SIZE_THRESHOLD)
1.1 root 746: flags |= KMEM_CACHE_NOOFFSLAB;
747:
1.1.1.4 root 748: cache->slab_size = PAGE_SIZE;
1.1 root 749:
1.1.1.4 root 750: for (;;) {
1.1 root 751: if (flags & KMEM_CACHE_NOOFFSLAB)
752: embed = 1;
1.1.1.4 root 753: else {
754: waste = cache->slab_size % cache->buf_size;
755: embed = (sizeof(struct kmem_slab) <= waste);
1.1 root 756: }
757:
1.1.1.4 root 758: size = cache->slab_size;
1.1 root 759:
1.1.1.4 root 760: if (embed)
761: size -= sizeof(struct kmem_slab);
1.1 root 762:
1.1.1.4 root 763: if (size >= cache->buf_size)
764: break;
765:
766: cache->slab_size += PAGE_SIZE;
767: }
768:
769: cache->bufs_per_slab = size / cache->buf_size;
770: cache->color_max = size % cache->buf_size;
1.1 root 771:
772: if (cache->color_max >= PAGE_SIZE)
1.1.1.4 root 773: cache->color_max = 0;
774:
775: if (!embed)
776: cache->flags |= KMEM_CF_SLAB_EXTERNAL;
777:
778: if ((flags & KMEM_CACHE_PHYSMEM) || (cache->slab_size == PAGE_SIZE)) {
779: cache->flags |= KMEM_CF_PHYSMEM;
1.1 root 780:
1.1.1.4 root 781: /*
782: * Avoid using larger-than-page slabs backed by the direct physical
783: * mapping to completely prevent physical memory fragmentation from
784: * making slab allocations fail.
785: */
786: if (cache->slab_size != PAGE_SIZE)
787: panic("slab: invalid cache parameters");
788: }
789:
790: if (cache->flags & KMEM_CF_VERIFY)
791: cache->flags |= KMEM_CF_USE_TREE;
792:
793: if (cache->flags & KMEM_CF_SLAB_EXTERNAL) {
794: if (cache->flags & KMEM_CF_PHYSMEM)
795: cache->flags |= KMEM_CF_USE_PAGE;
796: else
797: cache->flags |= KMEM_CF_USE_TREE;
798: } else {
1.1 root 799: if (cache->slab_size == PAGE_SIZE)
800: cache->flags |= KMEM_CF_DIRECT;
1.1.1.4 root 801: else
802: cache->flags |= KMEM_CF_USE_TREE;
1.1 root 803: }
804: }
805:
806: void kmem_cache_init(struct kmem_cache *cache, const char *name,
1.1.1.4 root 807: size_t obj_size, size_t align,
808: kmem_cache_ctor_t ctor, int flags)
1.1 root 809: {
810: #if SLAB_USE_CPU_POOLS
811: struct kmem_cpu_pool_type *cpu_pool_type;
812: size_t i;
813: #endif /* SLAB_USE_CPU_POOLS */
814: size_t buf_size;
815:
816: #if SLAB_VERIFY
817: cache->flags = KMEM_CF_VERIFY;
818: #else /* SLAB_VERIFY */
819: cache->flags = 0;
820: #endif /* SLAB_VERIFY */
821:
822: if (flags & KMEM_CACHE_VERIFY)
823: cache->flags |= KMEM_CF_VERIFY;
824:
825: if (align < KMEM_ALIGN_MIN)
826: align = KMEM_ALIGN_MIN;
827:
828: assert(obj_size > 0);
829: assert(ISP2(align));
830:
831: buf_size = P2ROUND(obj_size, align);
832:
833: simple_lock_init(&cache->lock);
834: list_node_init(&cache->node);
835: list_init(&cache->partial_slabs);
836: list_init(&cache->free_slabs);
837: rbtree_init(&cache->active_slabs);
838: cache->obj_size = obj_size;
839: cache->align = align;
840: cache->buf_size = buf_size;
841: cache->bufctl_dist = buf_size - sizeof(union kmem_bufctl);
842: cache->color = 0;
843: cache->nr_objs = 0;
844: cache->nr_bufs = 0;
845: cache->nr_slabs = 0;
846: cache->nr_free_slabs = 0;
847: cache->ctor = ctor;
848: strncpy(cache->name, name, sizeof(cache->name));
849: cache->name[sizeof(cache->name) - 1] = '\0';
850: cache->buftag_dist = 0;
851: cache->redzone_pad = 0;
852:
853: if (cache->flags & KMEM_CF_VERIFY) {
854: cache->bufctl_dist = buf_size;
855: cache->buftag_dist = cache->bufctl_dist + sizeof(union kmem_bufctl);
856: cache->redzone_pad = cache->bufctl_dist - cache->obj_size;
857: buf_size += sizeof(union kmem_bufctl) + sizeof(struct kmem_buftag);
858: buf_size = P2ROUND(buf_size, align);
859: cache->buf_size = buf_size;
860: }
861:
1.1.1.4 root 862: kmem_cache_compute_properties(cache, flags);
1.1 root 863:
864: #if SLAB_USE_CPU_POOLS
865: for (cpu_pool_type = kmem_cpu_pool_types;
866: buf_size <= cpu_pool_type->buf_size;
867: cpu_pool_type++);
868:
869: cache->cpu_pool_type = cpu_pool_type;
870:
871: for (i = 0; i < ARRAY_SIZE(cache->cpu_pools); i++)
872: kmem_cpu_pool_init(&cache->cpu_pools[i], cache);
873: #endif /* SLAB_USE_CPU_POOLS */
874:
875: simple_lock(&kmem_cache_list_lock);
876: list_insert_tail(&kmem_cache_list, &cache->node);
877: kmem_nr_caches++;
878: simple_unlock(&kmem_cache_list_lock);
879: }
880:
881: static inline int kmem_cache_empty(struct kmem_cache *cache)
882: {
883: return cache->nr_objs == cache->nr_bufs;
884: }
885:
886: static int kmem_cache_grow(struct kmem_cache *cache)
887: {
888: struct kmem_slab *slab;
889: size_t color;
890: int empty;
891:
892: simple_lock(&cache->lock);
893:
894: if (!kmem_cache_empty(cache)) {
895: simple_unlock(&cache->lock);
896: return 1;
897: }
898:
899: color = cache->color;
900: cache->color += cache->align;
901:
902: if (cache->color > cache->color_max)
903: cache->color = 0;
904:
905: simple_unlock(&cache->lock);
906:
907: slab = kmem_slab_create(cache, color);
908:
909: simple_lock(&cache->lock);
910:
911: if (slab != NULL) {
912: list_insert_head(&cache->free_slabs, &slab->list_node);
913: cache->nr_bufs += cache->bufs_per_slab;
914: cache->nr_slabs++;
915: cache->nr_free_slabs++;
916: }
917:
918: /*
919: * Even if our slab creation failed, another thread might have succeeded
920: * in growing the cache.
921: */
922: empty = kmem_cache_empty(cache);
923:
924: simple_unlock(&cache->lock);
925:
926: return !empty;
927: }
928:
1.1.1.5 ! root 929: static void kmem_cache_reap(struct kmem_cache *cache, struct list *dead_slabs)
1.1 root 930: {
931: simple_lock(&cache->lock);
1.1.1.5 ! root 932:
! 933: list_concat(dead_slabs, &cache->free_slabs);
1.1 root 934: list_init(&cache->free_slabs);
1.1.1.5 ! root 935: cache->nr_bufs -= cache->bufs_per_slab * cache->nr_free_slabs;
! 936: cache->nr_slabs -= cache->nr_free_slabs;
1.1 root 937: cache->nr_free_slabs = 0;
938:
1.1.1.5 ! root 939: simple_unlock(&cache->lock);
1.1 root 940: }
941:
942: /*
943: * Allocate a raw (unconstructed) buffer from the slab layer of a cache.
944: *
945: * The cache must be locked before calling this function.
946: */
947: static void * kmem_cache_alloc_from_slab(struct kmem_cache *cache)
948: {
949: struct kmem_slab *slab;
950: union kmem_bufctl *bufctl;
951:
952: if (!list_empty(&cache->partial_slabs))
953: slab = list_first_entry(&cache->partial_slabs, struct kmem_slab,
954: list_node);
955: else if (!list_empty(&cache->free_slabs))
956: slab = list_first_entry(&cache->free_slabs, struct kmem_slab,
957: list_node);
958: else
959: return NULL;
960:
961: bufctl = slab->first_free;
962: assert(bufctl != NULL);
963: slab->first_free = bufctl->next;
964: slab->nr_refs++;
965: cache->nr_objs++;
966:
967: if (slab->nr_refs == cache->bufs_per_slab) {
968: /* The slab has become complete */
969: list_remove(&slab->list_node);
970:
971: if (slab->nr_refs == 1)
972: cache->nr_free_slabs--;
973: } else if (slab->nr_refs == 1) {
974: /*
975: * The slab has become partial. Insert the new slab at the end of
976: * the list to reduce fragmentation.
977: */
978: list_remove(&slab->list_node);
979: list_insert_tail(&cache->partial_slabs, &slab->list_node);
980: cache->nr_free_slabs--;
981: }
982:
1.1.1.4 root 983: if ((slab->nr_refs == 1) && (cache->flags & KMEM_CF_USE_TREE))
1.1 root 984: rbtree_insert(&cache->active_slabs, &slab->tree_node,
985: kmem_slab_cmp_insert);
986:
987: return kmem_bufctl_to_buf(bufctl, cache);
988: }
989:
990: /*
991: * Release a buffer to the slab layer of a cache.
992: *
993: * The cache must be locked before calling this function.
994: */
995: static void kmem_cache_free_to_slab(struct kmem_cache *cache, void *buf)
996: {
997: struct kmem_slab *slab;
998: union kmem_bufctl *bufctl;
999:
1000: if (cache->flags & KMEM_CF_DIRECT) {
1001: assert(cache->slab_size == PAGE_SIZE);
1002: slab = (struct kmem_slab *)P2END((unsigned long)buf, cache->slab_size)
1003: - 1;
1.1.1.4 root 1004: } else if (cache->flags & KMEM_CF_USE_PAGE) {
1005: struct vm_page *page;
1006:
1007: page = vm_page_lookup_pa(kvtophys((vm_offset_t)buf));
1008: assert(page != NULL);
1009: slab = vm_page_get_priv(page);
1.1 root 1010: } else {
1011: struct rbtree_node *node;
1012:
1.1.1.4 root 1013: assert(cache->flags & KMEM_CF_USE_TREE);
1.1 root 1014: node = rbtree_lookup_nearest(&cache->active_slabs, buf,
1015: kmem_slab_cmp_lookup, RBTREE_LEFT);
1016: assert(node != NULL);
1017: slab = rbtree_entry(node, struct kmem_slab, tree_node);
1018: }
1019:
1.1.1.4 root 1020: assert((unsigned long)buf >= (unsigned long)slab->addr);
1021: assert(((unsigned long)buf + cache->buf_size)
1022: <= vm_page_trunc((unsigned long)slab->addr + cache->slab_size));
1023:
1.1 root 1024: assert(slab->nr_refs >= 1);
1025: assert(slab->nr_refs <= cache->bufs_per_slab);
1026: bufctl = kmem_buf_to_bufctl(buf, cache);
1027: bufctl->next = slab->first_free;
1028: slab->first_free = bufctl;
1029: slab->nr_refs--;
1030: cache->nr_objs--;
1031:
1032: if (slab->nr_refs == 0) {
1033: /* The slab has become free */
1034:
1.1.1.4 root 1035: if (cache->flags & KMEM_CF_USE_TREE)
1.1 root 1036: rbtree_remove(&cache->active_slabs, &slab->tree_node);
1037:
1038: if (cache->bufs_per_slab > 1)
1039: list_remove(&slab->list_node);
1040:
1041: list_insert_head(&cache->free_slabs, &slab->list_node);
1042: cache->nr_free_slabs++;
1043: } else if (slab->nr_refs == (cache->bufs_per_slab - 1)) {
1044: /* The slab has become partial */
1045: list_insert_head(&cache->partial_slabs, &slab->list_node);
1046: }
1047: }
1048:
1049: static void kmem_cache_alloc_verify(struct kmem_cache *cache, void *buf,
1050: int construct)
1051: {
1052: struct kmem_buftag *buftag;
1053: union kmem_bufctl *bufctl;
1054: void *addr;
1055:
1056: buftag = kmem_buf_to_buftag(buf, cache);
1057:
1058: if (buftag->state != KMEM_BUFTAG_FREE)
1059: kmem_cache_error(cache, buf, KMEM_ERR_BUFTAG, buftag);
1060:
1061: addr = kmem_buf_verify_fill(buf, KMEM_FREE_PATTERN, KMEM_UNINIT_PATTERN,
1062: cache->bufctl_dist);
1063:
1064: if (addr != NULL)
1065: kmem_cache_error(cache, buf, KMEM_ERR_MODIFIED, addr);
1066:
1067: addr = buf + cache->obj_size;
1068: memset(addr, KMEM_REDZONE_BYTE, cache->redzone_pad);
1069:
1070: bufctl = kmem_buf_to_bufctl(buf, cache);
1071: bufctl->redzone = KMEM_REDZONE_WORD;
1072: buftag->state = KMEM_BUFTAG_ALLOC;
1073:
1074: if (construct && (cache->ctor != NULL))
1075: cache->ctor(buf);
1076: }
1077:
1078: vm_offset_t kmem_cache_alloc(struct kmem_cache *cache)
1079: {
1080: int filled;
1081: void *buf;
1082:
1083: #if SLAB_USE_CPU_POOLS
1084: struct kmem_cpu_pool *cpu_pool;
1085:
1086: cpu_pool = kmem_cpu_pool_get(cache);
1087:
1088: if (cpu_pool->flags & KMEM_CF_NO_CPU_POOL)
1089: goto slab_alloc;
1090:
1091: simple_lock(&cpu_pool->lock);
1092:
1093: fast_alloc:
1094: if (likely(cpu_pool->nr_objs > 0)) {
1095: buf = kmem_cpu_pool_pop(cpu_pool);
1096: simple_unlock(&cpu_pool->lock);
1097:
1098: if (cpu_pool->flags & KMEM_CF_VERIFY)
1099: kmem_cache_alloc_verify(cache, buf, KMEM_AV_CONSTRUCT);
1100:
1101: return (vm_offset_t)buf;
1102: }
1103:
1104: if (cpu_pool->array != NULL) {
1105: filled = kmem_cpu_pool_fill(cpu_pool, cache);
1106:
1107: if (!filled) {
1108: simple_unlock(&cpu_pool->lock);
1109:
1110: filled = kmem_cache_grow(cache);
1111:
1112: if (!filled)
1113: return 0;
1114:
1115: simple_lock(&cpu_pool->lock);
1116: }
1117:
1118: goto fast_alloc;
1119: }
1120:
1121: simple_unlock(&cpu_pool->lock);
1122: #endif /* SLAB_USE_CPU_POOLS */
1123:
1124: slab_alloc:
1125: simple_lock(&cache->lock);
1126: buf = kmem_cache_alloc_from_slab(cache);
1127: simple_unlock(&cache->lock);
1128:
1129: if (buf == NULL) {
1130: filled = kmem_cache_grow(cache);
1131:
1132: if (!filled)
1133: return 0;
1134:
1135: goto slab_alloc;
1136: }
1137:
1138: if (cache->flags & KMEM_CF_VERIFY)
1139: kmem_cache_alloc_verify(cache, buf, KMEM_AV_NOCONSTRUCT);
1140:
1141: if (cache->ctor != NULL)
1142: cache->ctor(buf);
1143:
1144: return (vm_offset_t)buf;
1145: }
1146:
1147: static void kmem_cache_free_verify(struct kmem_cache *cache, void *buf)
1148: {
1149: struct rbtree_node *node;
1150: struct kmem_buftag *buftag;
1151: struct kmem_slab *slab;
1152: union kmem_bufctl *bufctl;
1153: unsigned char *redzone_byte;
1154: unsigned long slabend;
1155:
1.1.1.4 root 1156: assert(cache->flags & KMEM_CF_USE_TREE);
1157:
1.1 root 1158: simple_lock(&cache->lock);
1159: node = rbtree_lookup_nearest(&cache->active_slabs, buf,
1160: kmem_slab_cmp_lookup, RBTREE_LEFT);
1161: simple_unlock(&cache->lock);
1162:
1163: if (node == NULL)
1164: kmem_cache_error(cache, buf, KMEM_ERR_INVALID, NULL);
1165:
1166: slab = rbtree_entry(node, struct kmem_slab, tree_node);
1167: slabend = P2ALIGN((unsigned long)slab->addr + cache->slab_size, PAGE_SIZE);
1168:
1169: if ((unsigned long)buf >= slabend)
1170: kmem_cache_error(cache, buf, KMEM_ERR_INVALID, NULL);
1171:
1172: if ((((unsigned long)buf - (unsigned long)slab->addr) % cache->buf_size)
1173: != 0)
1174: kmem_cache_error(cache, buf, KMEM_ERR_INVALID, NULL);
1175:
1176: /*
1177: * As the buffer address is valid, accessing its buftag is safe.
1178: */
1179: buftag = kmem_buf_to_buftag(buf, cache);
1180:
1181: if (buftag->state != KMEM_BUFTAG_ALLOC) {
1182: if (buftag->state == KMEM_BUFTAG_FREE)
1183: kmem_cache_error(cache, buf, KMEM_ERR_DOUBLEFREE, NULL);
1184: else
1185: kmem_cache_error(cache, buf, KMEM_ERR_BUFTAG, buftag);
1186: }
1187:
1188: redzone_byte = buf + cache->obj_size;
1189: bufctl = kmem_buf_to_bufctl(buf, cache);
1190:
1191: while (redzone_byte < (unsigned char *)bufctl) {
1192: if (*redzone_byte != KMEM_REDZONE_BYTE)
1193: kmem_cache_error(cache, buf, KMEM_ERR_REDZONE, redzone_byte);
1194:
1195: redzone_byte++;
1196: }
1197:
1198: if (bufctl->redzone != KMEM_REDZONE_WORD) {
1199: unsigned long word;
1200:
1201: word = KMEM_REDZONE_WORD;
1202: redzone_byte = kmem_buf_verify_bytes(&bufctl->redzone, &word,
1203: sizeof(bufctl->redzone));
1204: kmem_cache_error(cache, buf, KMEM_ERR_REDZONE, redzone_byte);
1205: }
1206:
1207: kmem_buf_fill(buf, KMEM_FREE_PATTERN, cache->bufctl_dist);
1208: buftag->state = KMEM_BUFTAG_FREE;
1209: }
1210:
1211: void kmem_cache_free(struct kmem_cache *cache, vm_offset_t obj)
1212: {
1213: #if SLAB_USE_CPU_POOLS
1214: struct kmem_cpu_pool *cpu_pool;
1215: void **array;
1216:
1217: cpu_pool = kmem_cpu_pool_get(cache);
1218:
1219: if (cpu_pool->flags & KMEM_CF_VERIFY) {
1220: #else /* SLAB_USE_CPU_POOLS */
1221: if (cache->flags & KMEM_CF_VERIFY) {
1222: #endif /* SLAB_USE_CPU_POOLS */
1223: kmem_cache_free_verify(cache, (void *)obj);
1224: }
1225:
1226: #if SLAB_USE_CPU_POOLS
1227: if (cpu_pool->flags & KMEM_CF_NO_CPU_POOL)
1228: goto slab_free;
1229:
1230: simple_lock(&cpu_pool->lock);
1231:
1232: fast_free:
1233: if (likely(cpu_pool->nr_objs < cpu_pool->size)) {
1234: kmem_cpu_pool_push(cpu_pool, (void *)obj);
1235: simple_unlock(&cpu_pool->lock);
1236: return;
1237: }
1238:
1239: if (cpu_pool->array != NULL) {
1240: kmem_cpu_pool_drain(cpu_pool, cache);
1241: goto fast_free;
1242: }
1243:
1244: simple_unlock(&cpu_pool->lock);
1245:
1246: array = (void *)kmem_cache_alloc(cache->cpu_pool_type->array_cache);
1247:
1248: if (array != NULL) {
1249: simple_lock(&cpu_pool->lock);
1250:
1251: /*
1252: * Another thread may have built the CPU pool while the lock was
1253: * dropped.
1254: */
1255: if (cpu_pool->array != NULL) {
1256: simple_unlock(&cpu_pool->lock);
1257: kmem_cache_free(cache->cpu_pool_type->array_cache,
1258: (vm_offset_t)array);
1259: simple_lock(&cpu_pool->lock);
1260: goto fast_free;
1261: }
1262:
1263: kmem_cpu_pool_build(cpu_pool, cache, array);
1264: goto fast_free;
1265: }
1266:
1267: slab_free:
1268: #endif /* SLAB_USE_CPU_POOLS */
1269:
1270: simple_lock(&cache->lock);
1271: kmem_cache_free_to_slab(cache, (void *)obj);
1272: simple_unlock(&cache->lock);
1273: }
1274:
1275: void slab_collect(void)
1276: {
1277: struct kmem_cache *cache;
1.1.1.5 ! root 1278: struct kmem_slab *slab;
! 1279: struct list dead_slabs;
1.1 root 1280:
1281: if (elapsed_ticks <= (kmem_gc_last_tick + KMEM_GC_INTERVAL))
1282: return;
1283:
1284: kmem_gc_last_tick = elapsed_ticks;
1285:
1.1.1.5 ! root 1286: list_init(&dead_slabs);
! 1287:
1.1 root 1288: simple_lock(&kmem_cache_list_lock);
1289:
1290: list_for_each_entry(&kmem_cache_list, cache, node)
1.1.1.5 ! root 1291: kmem_cache_reap(cache, &dead_slabs);
1.1 root 1292:
1293: simple_unlock(&kmem_cache_list_lock);
1.1.1.5 ! root 1294:
! 1295: while (!list_empty(&dead_slabs)) {
! 1296: slab = list_first_entry(&dead_slabs, struct kmem_slab, list_node);
! 1297: list_remove(&slab->list_node);
! 1298: kmem_slab_destroy(slab, slab->cache);
! 1299: }
1.1 root 1300: }
1301:
1302: void slab_bootstrap(void)
1303: {
1304: /* Make sure a bufctl can always be stored in a buffer */
1305: assert(sizeof(union kmem_bufctl) <= KMEM_ALIGN_MIN);
1306:
1307: list_init(&kmem_cache_list);
1308: simple_lock_init(&kmem_cache_list_lock);
1309: }
1310:
1311: void slab_init(void)
1312: {
1313: #if SLAB_USE_CPU_POOLS
1314: struct kmem_cpu_pool_type *cpu_pool_type;
1315: char name[KMEM_CACHE_NAME_SIZE];
1316: size_t i, size;
1317: #endif /* SLAB_USE_CPU_POOLS */
1318:
1319: #if SLAB_USE_CPU_POOLS
1320: for (i = 0; i < ARRAY_SIZE(kmem_cpu_pool_types); i++) {
1321: cpu_pool_type = &kmem_cpu_pool_types[i];
1322: cpu_pool_type->array_cache = &kmem_cpu_array_caches[i];
1323: sprintf(name, "kmem_cpu_array_%d", cpu_pool_type->array_size);
1324: size = sizeof(void *) * cpu_pool_type->array_size;
1325: kmem_cache_init(cpu_pool_type->array_cache, name, size,
1.1.1.4 root 1326: cpu_pool_type->array_align, NULL, 0);
1.1 root 1327: }
1328: #endif /* SLAB_USE_CPU_POOLS */
1329:
1330: /*
1331: * Prevent off slab data for the slab cache to avoid infinite recursion.
1332: */
1333: kmem_cache_init(&kmem_slab_cache, "kmem_slab", sizeof(struct kmem_slab),
1.1.1.4 root 1334: 0, NULL, KMEM_CACHE_NOOFFSLAB);
1.1 root 1335: }
1336:
1337: void kalloc_init(void)
1338: {
1339: char name[KMEM_CACHE_NAME_SIZE];
1340: size_t i, size;
1341:
1342: size = 1 << KALLOC_FIRST_SHIFT;
1343:
1344: for (i = 0; i < ARRAY_SIZE(kalloc_caches); i++) {
1345: sprintf(name, "kalloc_%lu", size);
1.1.1.4 root 1346: kmem_cache_init(&kalloc_caches[i], name, size, 0, NULL, 0);
1.1 root 1347: size <<= 1;
1348: }
1349: }
1350:
1351: /*
1352: * Return the kalloc cache index matching the given allocation size, which
1353: * must be strictly greater than 0.
1354: */
1355: static inline size_t kalloc_get_index(unsigned long size)
1356: {
1357: assert(size != 0);
1358:
1359: size = (size - 1) >> KALLOC_FIRST_SHIFT;
1360:
1361: if (size == 0)
1362: return 0;
1363: else
1364: return (sizeof(long) * 8) - __builtin_clzl(size);
1365: }
1366:
1367: static void kalloc_verify(struct kmem_cache *cache, void *buf, size_t size)
1368: {
1369: size_t redzone_size;
1370: void *redzone;
1371:
1372: assert(size <= cache->obj_size);
1373:
1374: redzone = buf + size;
1375: redzone_size = cache->obj_size - size;
1376: memset(redzone, KMEM_REDZONE_BYTE, redzone_size);
1377: }
1378:
1379: vm_offset_t kalloc(vm_size_t size)
1380: {
1381: size_t index;
1382: void *buf;
1383:
1384: if (size == 0)
1385: return 0;
1386:
1387: index = kalloc_get_index(size);
1388:
1389: if (index < ARRAY_SIZE(kalloc_caches)) {
1390: struct kmem_cache *cache;
1391:
1392: cache = &kalloc_caches[index];
1393: buf = (void *)kmem_cache_alloc(cache);
1394:
1395: if ((buf != 0) && (cache->flags & KMEM_CF_VERIFY))
1396: kalloc_verify(cache, buf, size);
1.1.1.4 root 1397: } else {
1398: buf = (void *)kmem_pagealloc_virtual(size, 0);
1399: }
1.1 root 1400:
1401: return (vm_offset_t)buf;
1402: }
1403:
1404: static void kfree_verify(struct kmem_cache *cache, void *buf, size_t size)
1405: {
1406: unsigned char *redzone_byte, *redzone_end;
1407:
1408: assert(size <= cache->obj_size);
1409:
1410: redzone_byte = buf + size;
1411: redzone_end = buf + cache->obj_size;
1412:
1413: while (redzone_byte < redzone_end) {
1414: if (*redzone_byte != KMEM_REDZONE_BYTE)
1415: kmem_cache_error(cache, buf, KMEM_ERR_REDZONE, redzone_byte);
1416:
1417: redzone_byte++;
1418: }
1419: }
1420:
1421: void kfree(vm_offset_t data, vm_size_t size)
1422: {
1423: size_t index;
1424:
1425: if ((data == 0) || (size == 0))
1426: return;
1427:
1428: index = kalloc_get_index(size);
1429:
1430: if (index < ARRAY_SIZE(kalloc_caches)) {
1431: struct kmem_cache *cache;
1432:
1433: cache = &kalloc_caches[index];
1434:
1435: if (cache->flags & KMEM_CF_VERIFY)
1436: kfree_verify(cache, (void *)data, size);
1437:
1438: kmem_cache_free(cache, data);
1439: } else {
1.1.1.4 root 1440: kmem_pagefree_virtual(data, size);
1.1 root 1441: }
1442: }
1443:
1.1.1.3 root 1444: static void _slab_info(int (printx)(const char *fmt, ...))
1.1 root 1445: {
1446: struct kmem_cache *cache;
1.1.1.3 root 1447: vm_size_t mem_usage, mem_reclaimable, mem_total, mem_total_reclaimable;
1448:
1449: mem_total = 0;
1450: mem_total_reclaimable = 0;
1.1 root 1451:
1.1.1.3 root 1452: printx("cache obj slab bufs objs bufs"
1453: " total reclaimable\n"
1454: "name flags size size /slab usage count"
1455: " memory memory\n");
1.1 root 1456:
1457: simple_lock(&kmem_cache_list_lock);
1458:
1459: list_for_each_entry(&kmem_cache_list, cache, node) {
1460: simple_lock(&cache->lock);
1461:
1462: mem_usage = (cache->nr_slabs * cache->slab_size) >> 10;
1463: mem_reclaimable = (cache->nr_free_slabs * cache->slab_size) >> 10;
1464:
1.1.1.3 root 1465: printx("%-20s %04x %7lu %3luk %4lu %6lu %6lu %7uk %10uk\n",
1466: cache->name, cache->flags, cache->obj_size,
1467: cache->slab_size >> 10,
1.1 root 1468: cache->bufs_per_slab, cache->nr_objs, cache->nr_bufs,
1469: mem_usage, mem_reclaimable);
1470:
1471: simple_unlock(&cache->lock);
1.1.1.3 root 1472:
1473: mem_total += mem_usage;
1474: mem_total_reclaimable += mem_reclaimable;
1.1 root 1475: }
1476:
1477: simple_unlock(&kmem_cache_list_lock);
1.1.1.3 root 1478:
1479: printx("total: %uk, reclaimable: %uk\n",
1480: mem_total, mem_total_reclaimable);
1481: }
1482:
1483: void slab_info(void)
1484: {
1485: _slab_info(printf);
1.1 root 1486: }
1487:
1.1.1.3 root 1488: #if MACH_KDB
1489: #include <ddb/db_output.h>
1490:
1491: void db_show_slab_info(void)
1492: {
1493: _slab_info(db_printf);
1494: }
1495:
1496: #endif /* MACH_KDB */
1497:
1.1 root 1498: #if MACH_DEBUG
1499: kern_return_t host_slab_info(host_t host, cache_info_array_t *infop,
1500: unsigned int *infoCntp)
1501: {
1502: struct kmem_cache *cache;
1503: cache_info_t *info;
1504: unsigned int i, nr_caches;
1.1.1.5 ! root 1505: vm_size_t info_size;
1.1 root 1506: kern_return_t kr;
1507:
1508: if (host == HOST_NULL)
1509: return KERN_INVALID_HOST;
1510:
1.1.1.5 ! root 1511: /* Assume the cache list is mostly unaltered once the kernel is ready */
1.1 root 1512:
1.1.1.5 ! root 1513: retry:
! 1514: /* Harmless unsynchronized access, real value checked later */
1.1 root 1515: nr_caches = kmem_nr_caches;
1.1.1.5 ! root 1516: info_size = nr_caches * sizeof(*info);
! 1517: info = (cache_info_t *)kalloc(info_size);
1.1 root 1518:
1519: if (info == NULL)
1520: return KERN_RESOURCE_SHORTAGE;
1521:
1522: i = 0;
1523:
1.1.1.5 ! root 1524: simple_lock(&kmem_cache_list_lock);
! 1525:
! 1526: if (nr_caches != kmem_nr_caches) {
! 1527: simple_unlock(&kmem_cache_list_lock);
! 1528: kfree((vm_offset_t)info, info_size);
! 1529: goto retry;
! 1530: }
! 1531:
1.1 root 1532: list_for_each_entry(&kmem_cache_list, cache, node) {
1.1.1.3 root 1533: simple_lock(&cache->lock);
1.1.1.4 root 1534: info[i].flags = cache->flags;
1.1 root 1535: #if SLAB_USE_CPU_POOLS
1536: info[i].cpu_pool_size = cache->cpu_pool_type->array_size;
1537: #else /* SLAB_USE_CPU_POOLS */
1538: info[i].cpu_pool_size = 0;
1539: #endif /* SLAB_USE_CPU_POOLS */
1540: info[i].obj_size = cache->obj_size;
1541: info[i].align = cache->align;
1542: info[i].buf_size = cache->buf_size;
1543: info[i].slab_size = cache->slab_size;
1544: info[i].bufs_per_slab = cache->bufs_per_slab;
1545: info[i].nr_objs = cache->nr_objs;
1546: info[i].nr_bufs = cache->nr_bufs;
1547: info[i].nr_slabs = cache->nr_slabs;
1548: info[i].nr_free_slabs = cache->nr_free_slabs;
1549: strncpy(info[i].name, cache->name, sizeof(info[i].name));
1550: info[i].name[sizeof(info[i].name) - 1] = '\0';
1551: simple_unlock(&cache->lock);
1552:
1553: i++;
1554: }
1555:
1.1.1.5 ! root 1556: simple_unlock(&kmem_cache_list_lock);
! 1557:
! 1558: if (nr_caches <= *infoCntp) {
! 1559: memcpy(*infop, info, info_size);
! 1560: } else {
! 1561: vm_offset_t info_addr;
! 1562: vm_size_t total_size;
1.1 root 1563: vm_map_copy_t copy;
1564:
1.1.1.5 ! root 1565: kr = kmem_alloc_pageable(ipc_kernel_map, &info_addr, info_size);
1.1 root 1566:
1.1.1.5 ! root 1567: if (kr != KERN_SUCCESS)
! 1568: goto out;
1.1 root 1569:
1.1.1.5 ! root 1570: memcpy((char *)info_addr, info, info_size);
! 1571: total_size = round_page(info_size);
1.1 root 1572:
1.1.1.5 ! root 1573: if (info_size < total_size)
! 1574: memset((char *)(info_addr + info_size),
! 1575: 0, total_size - info_size);
! 1576:
! 1577: kr = vm_map_copyin(ipc_kernel_map, info_addr, info_size, TRUE, ©);
1.1 root 1578: assert(kr == KERN_SUCCESS);
1579: *infop = (cache_info_t *)copy;
1580: }
1581:
1582: *infoCntp = nr_caches;
1.1.1.5 ! root 1583: kr = KERN_SUCCESS;
! 1584:
! 1585: out:
! 1586: kfree((vm_offset_t)info, info_size);
1.1 root 1587:
1.1.1.5 ! root 1588: return kr;
1.1 root 1589: }
1590: #endif /* MACH_DEBUG */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.