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