Home | History | Annotate | Line # | Download | only in kern
subr_kmem.c revision 1.32.2.1 
      1 /*	$NetBSD: subr_kmem.c,v 1.32.2.1 2010/04/30 14:44:12 uebayasi Exp $	*/
      2 
      3 /*-
      4  * Copyright (c) 2009 The NetBSD Foundation, Inc.
      5  * All rights reserved.
      6  *
      7  * This code is derived from software contributed to The NetBSD Foundation
      8  * by Andrew Doran.
      9  *
     10  * Redistribution and use in source and binary forms, with or without
     11  * modification, are permitted provided that the following conditions
     12  * are met:
     13  * 1. Redistributions of source code must retain the above copyright
     14  *    notice, this list of conditions and the following disclaimer.
     15  * 2. Redistributions in binary form must reproduce the above copyright
     16  *    notice, this list of conditions and the following disclaimer in the
     17  *    documentation and/or other materials provided with the distribution.
     18  *
     19  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
     20  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
     21  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
     22  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
     23  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
     24  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
     25  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
     26  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
     27  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
     28  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
     29  * POSSIBILITY OF SUCH DAMAGE.
     30  */
     31 
     32 /*-
     33  * Copyright (c)2006 YAMAMOTO Takashi,
     34  * All rights reserved.
     35  *
     36  * Redistribution and use in source and binary forms, with or without
     37  * modification, are permitted provided that the following conditions
     38  * are met:
     39  * 1. Redistributions of source code must retain the above copyright
     40  *    notice, this list of conditions and the following disclaimer.
     41  * 2. Redistributions in binary form must reproduce the above copyright
     42  *    notice, this list of conditions and the following disclaimer in the
     43  *    documentation and/or other materials provided with the distribution.
     44  *
     45  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
     46  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     47  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     48  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
     49  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     50  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     51  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     52  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     53  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     54  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     55  * SUCH DAMAGE.
     56  */
     57 
     58 /*
     59  * allocator of kernel wired memory.
     60  *
     61  * TODO:
     62  * -	worth to have "intrsafe" version?  maybe..
     63  */
     64 
     65 #include <sys/cdefs.h>
     66 __KERNEL_RCSID(0, "$NetBSD: subr_kmem.c,v 1.32.2.1 2010/04/30 14:44:12 uebayasi Exp $");
     67 
     68 #include <sys/param.h>
     69 #include <sys/callback.h>
     70 #include <sys/kmem.h>
     71 #include <sys/vmem.h>
     72 #include <sys/debug.h>
     73 #include <sys/lockdebug.h>
     74 #include <sys/cpu.h>
     75 
     76 #include <uvm/uvm_extern.h>
     77 #include <uvm/uvm_map.h>
     78 #include <uvm/uvm_kmguard.h>
     79 
     80 #include <lib/libkern/libkern.h>
     81 
     82 #include <machine/stdarg.h>
     83 
     84 #define	KMEM_QUANTUM_SIZE	(ALIGNBYTES + 1)
     85 #define	KMEM_QCACHE_MAX		(KMEM_QUANTUM_SIZE * 32)
     86 #define	KMEM_CACHE_COUNT	16
     87 
     88 typedef struct kmem_cache {
     89 	pool_cache_t		kc_cache;
     90 	struct pool_allocator	kc_pa;
     91 	char			kc_name[12];
     92 } kmem_cache_t;
     93 
     94 static vmem_t *kmem_arena;
     95 static struct callback_entry kmem_kva_reclaim_entry;
     96 
     97 static kmem_cache_t kmem_cache[KMEM_CACHE_COUNT + 1];
     98 static size_t kmem_cache_max;
     99 static size_t kmem_cache_min;
    100 static size_t kmem_cache_mask;
    101 static int kmem_cache_shift;
    102 
    103 #if defined(DEBUG)
    104 int kmem_guard_depth;
    105 size_t kmem_guard_size;
    106 static struct uvm_kmguard kmem_guard;
    107 static void *kmem_freecheck;
    108 #define	KMEM_POISON
    109 #define	KMEM_REDZONE
    110 #define	KMEM_SIZE
    111 #define	KMEM_GUARD
    112 #endif /* defined(DEBUG) */
    113 
    114 #if defined(KMEM_POISON)
    115 static void kmem_poison_fill(void *, size_t);
    116 static void kmem_poison_check(void *, size_t);
    117 #else /* defined(KMEM_POISON) */
    118 #define	kmem_poison_fill(p, sz)		/* nothing */
    119 #define	kmem_poison_check(p, sz)	/* nothing */
    120 #endif /* defined(KMEM_POISON) */
    121 
    122 #if defined(KMEM_REDZONE)
    123 #define	REDZONE_SIZE	1
    124 #else /* defined(KMEM_REDZONE) */
    125 #define	REDZONE_SIZE	0
    126 #endif /* defined(KMEM_REDZONE) */
    127 
    128 #if defined(KMEM_SIZE)
    129 #define	SIZE_SIZE	(max(KMEM_QUANTUM_SIZE, sizeof(size_t)))
    130 static void kmem_size_set(void *, size_t);
    131 static void kmem_size_check(const void *, size_t);
    132 #else
    133 #define	SIZE_SIZE	0
    134 #define	kmem_size_set(p, sz)	/* nothing */
    135 #define	kmem_size_check(p, sz)	/* nothing */
    136 #endif
    137 
    138 static vmem_addr_t kmem_backend_alloc(vmem_t *, vmem_size_t, vmem_size_t *,
    139     vm_flag_t);
    140 static void kmem_backend_free(vmem_t *, vmem_addr_t, vmem_size_t);
    141 static int kmem_kva_reclaim_callback(struct callback_entry *, void *, void *);
    142 
    143 CTASSERT(KM_SLEEP == PR_WAITOK);
    144 CTASSERT(KM_NOSLEEP == PR_NOWAIT);
    145 
    146 static inline vm_flag_t
    147 kmf_to_vmf(km_flag_t kmflags)
    148 {
    149 	vm_flag_t vmflags;
    150 
    151 	KASSERT((kmflags & (KM_SLEEP|KM_NOSLEEP)) != 0);
    152 	KASSERT((~kmflags & (KM_SLEEP|KM_NOSLEEP)) != 0);
    153 
    154 	vmflags = 0;
    155 	if ((kmflags & KM_SLEEP) != 0) {
    156 		vmflags |= VM_SLEEP;
    157 	}
    158 	if ((kmflags & KM_NOSLEEP) != 0) {
    159 		vmflags |= VM_NOSLEEP;
    160 	}
    161 
    162 	return vmflags;
    163 }
    164 
    165 static void *
    166 kmem_poolpage_alloc(struct pool *pool, int prflags)
    167 {
    168 
    169 	return (void *)vmem_alloc(kmem_arena, pool->pr_alloc->pa_pagesz,
    170 	    kmf_to_vmf(prflags) | VM_INSTANTFIT);
    171 
    172 }
    173 
    174 static void
    175 kmem_poolpage_free(struct pool *pool, void *addr)
    176 {
    177 
    178 	vmem_free(kmem_arena, (vmem_addr_t)addr, pool->pr_alloc->pa_pagesz);
    179 }
    180 
    181 /* ---- kmem API */
    182 
    183 /*
    184  * kmem_alloc: allocate wired memory.
    185  *
    186  * => must not be called from interrupt context.
    187  */
    188 
    189 void *
    190 kmem_alloc(size_t size, km_flag_t kmflags)
    191 {
    192 	kmem_cache_t *kc;
    193 	uint8_t *p;
    194 
    195 	KASSERT(!cpu_intr_p());
    196 	KASSERT(!cpu_softintr_p());
    197 	KASSERT(size > 0);
    198 
    199 #ifdef KMEM_GUARD
    200 	if (size <= kmem_guard_size) {
    201 		return uvm_kmguard_alloc(&kmem_guard, size,
    202 		    (kmflags & KM_SLEEP) != 0);
    203 	}
    204 #endif
    205 
    206 	size += REDZONE_SIZE + SIZE_SIZE;
    207 	if (size >= kmem_cache_min && size <= kmem_cache_max) {
    208 		kc = &kmem_cache[(size + kmem_cache_mask) >> kmem_cache_shift];
    209 		KASSERT(size <= kc->kc_pa.pa_pagesz);
    210 		kmflags &= (KM_SLEEP | KM_NOSLEEP);
    211 		p = pool_cache_get(kc->kc_cache, kmflags);
    212 	} else {
    213 		p = (void *)vmem_alloc(kmem_arena, size,
    214 		    kmf_to_vmf(kmflags) | VM_INSTANTFIT);
    215 	}
    216 	if (__predict_true(p != NULL)) {
    217 		kmem_poison_check(p, kmem_roundup_size(size));
    218 		FREECHECK_OUT(&kmem_freecheck, p);
    219 		kmem_size_set(p, size);
    220 		p = (uint8_t *)p + SIZE_SIZE;
    221 	}
    222 	return p;
    223 }
    224 
    225 /*
    226  * kmem_zalloc: allocate wired memory.
    227  *
    228  * => must not be called from interrupt context.
    229  */
    230 
    231 void *
    232 kmem_zalloc(size_t size, km_flag_t kmflags)
    233 {
    234 	void *p;
    235 
    236 	p = kmem_alloc(size, kmflags);
    237 	if (p != NULL) {
    238 		memset(p, 0, size);
    239 	}
    240 	return p;
    241 }
    242 
    243 /*
    244  * kmem_free: free wired memory allocated by kmem_alloc.
    245  *
    246  * => must not be called from interrupt context.
    247  */
    248 
    249 void
    250 kmem_free(void *p, size_t size)
    251 {
    252 	kmem_cache_t *kc;
    253 
    254 	KASSERT(!cpu_intr_p());
    255 	KASSERT(!cpu_softintr_p());
    256 	KASSERT(p != NULL);
    257 	KASSERT(size > 0);
    258 
    259 #ifdef KMEM_GUARD
    260 	if (size <= kmem_guard_size) {
    261 		uvm_kmguard_free(&kmem_guard, size, p);
    262 		return;
    263 	}
    264 #endif
    265 	size += SIZE_SIZE;
    266 	p = (uint8_t *)p - SIZE_SIZE;
    267 	kmem_size_check(p, size + REDZONE_SIZE);
    268 	FREECHECK_IN(&kmem_freecheck, p);
    269 	LOCKDEBUG_MEM_CHECK(p, size);
    270 	kmem_poison_check((char *)p + size,
    271 	    kmem_roundup_size(size + REDZONE_SIZE) - size);
    272 	kmem_poison_fill(p, size);
    273 	size += REDZONE_SIZE;
    274 	if (size >= kmem_cache_min && size <= kmem_cache_max) {
    275 		kc = &kmem_cache[(size + kmem_cache_mask) >> kmem_cache_shift];
    276 		KASSERT(size <= kc->kc_pa.pa_pagesz);
    277 		pool_cache_put(kc->kc_cache, p);
    278 	} else {
    279 		vmem_free(kmem_arena, (vmem_addr_t)p, size);
    280 	}
    281 }
    282 
    283 
    284 void
    285 kmem_init(void)
    286 {
    287 	kmem_cache_t *kc;
    288 	size_t sz;
    289 	int i;
    290 
    291 #ifdef KMEM_GUARD
    292 	uvm_kmguard_init(&kmem_guard, &kmem_guard_depth, &kmem_guard_size,
    293 	    kernel_map);
    294 #endif
    295 
    296 	kmem_arena = vmem_create("kmem", 0, 0, KMEM_QUANTUM_SIZE,
    297 	    kmem_backend_alloc, kmem_backend_free, NULL, KMEM_QCACHE_MAX,
    298 	    VM_SLEEP, IPL_NONE);
    299 	callback_register(&vm_map_to_kernel(kernel_map)->vmk_reclaim_callback,
    300 	    &kmem_kva_reclaim_entry, kmem_arena, kmem_kva_reclaim_callback);
    301 
    302 	/*
    303 	 * kmem caches start at twice the size of the largest vmem qcache
    304 	 * and end at PAGE_SIZE or earlier.  assert that KMEM_QCACHE_MAX
    305 	 * is a power of two.
    306 	 */
    307 	KASSERT(ffs(KMEM_QCACHE_MAX) != 0);
    308 	KASSERT(KMEM_QCACHE_MAX - (1 << (ffs(KMEM_QCACHE_MAX) - 1)) == 0);
    309 	kmem_cache_shift = ffs(KMEM_QCACHE_MAX);
    310 	kmem_cache_min = 1 << kmem_cache_shift;
    311 	kmem_cache_mask = kmem_cache_min - 1;
    312 	for (i = 1; i <= KMEM_CACHE_COUNT; i++) {
    313 		sz = i << kmem_cache_shift;
    314 		if (sz > PAGE_SIZE) {
    315 			break;
    316 		}
    317 		kmem_cache_max = sz;
    318 		kc = &kmem_cache[i];
    319 		kc->kc_pa.pa_pagesz = sz;
    320 		kc->kc_pa.pa_alloc = kmem_poolpage_alloc;
    321 		kc->kc_pa.pa_free = kmem_poolpage_free;
    322 		sprintf(kc->kc_name, "kmem-%zu", sz);
    323 		kc->kc_cache = pool_cache_init(sz,
    324 		    KMEM_QUANTUM_SIZE, 0, PR_NOALIGN | PR_NOTOUCH,
    325 		    kc->kc_name, &kc->kc_pa, IPL_NONE,
    326 		    NULL, NULL, NULL);
    327 		KASSERT(kc->kc_cache != NULL);
    328 	}
    329 }
    330 
    331 size_t
    332 kmem_roundup_size(size_t size)
    333 {
    334 
    335 	return vmem_roundup_size(kmem_arena, size);
    336 }
    337 
    338 /* ---- uvm glue */
    339 
    340 static vmem_addr_t
    341 kmem_backend_alloc(vmem_t *dummy, vmem_size_t size, vmem_size_t *resultsize,
    342     vm_flag_t vmflags)
    343 {
    344 	uvm_flag_t uflags;
    345 	vaddr_t va;
    346 
    347 	KASSERT(dummy == NULL);
    348 	KASSERT(size != 0);
    349 	KASSERT((vmflags & (VM_SLEEP|VM_NOSLEEP)) != 0);
    350 	KASSERT((~vmflags & (VM_SLEEP|VM_NOSLEEP)) != 0);
    351 
    352 	if ((vmflags & VM_NOSLEEP) != 0) {
    353 		uflags = UVM_KMF_TRYLOCK | UVM_KMF_NOWAIT;
    354 	} else {
    355 		uflags = UVM_KMF_WAITVA;
    356 	}
    357 	*resultsize = size = round_page(size);
    358 	va = uvm_km_alloc(kernel_map, size, 0,
    359 	    uflags | UVM_KMF_WIRED | UVM_KMF_CANFAIL);
    360 	if (va != 0) {
    361 		kmem_poison_fill((void *)va, size);
    362 	}
    363 	return (vmem_addr_t)va;
    364 }
    365 
    366 static void
    367 kmem_backend_free(vmem_t *dummy, vmem_addr_t addr, vmem_size_t size)
    368 {
    369 
    370 	KASSERT(dummy == NULL);
    371 	KASSERT(addr != 0);
    372 	KASSERT(size != 0);
    373 	KASSERT(size == round_page(size));
    374 
    375 	kmem_poison_check((void *)addr, size);
    376 	uvm_km_free(kernel_map, (vaddr_t)addr, size, UVM_KMF_WIRED);
    377 }
    378 
    379 static int
    380 kmem_kva_reclaim_callback(struct callback_entry *ce, void *obj, void *arg)
    381 {
    382 	vmem_t *vm = obj;
    383 
    384 	vmem_reap(vm);
    385 	return CALLBACK_CHAIN_CONTINUE;
    386 }
    387 
    388 /* ---- debug */
    389 
    390 #if defined(KMEM_POISON)
    391 
    392 #if defined(_LP64)
    393 #define	PRIME	0x9e37fffffffc0001UL
    394 #else /* defined(_LP64) */
    395 #define	PRIME	0x9e3779b1
    396 #endif /* defined(_LP64) */
    397 
    398 static inline uint8_t
    399 kmem_poison_pattern(const void *p)
    400 {
    401 
    402 	return (uint8_t)((((uintptr_t)p) * PRIME)
    403 	    >> ((sizeof(uintptr_t) - sizeof(uint8_t))) * CHAR_BIT);
    404 }
    405 
    406 static void
    407 kmem_poison_fill(void *p, size_t sz)
    408 {
    409 	uint8_t *cp;
    410 	const uint8_t *ep;
    411 
    412 	cp = p;
    413 	ep = cp + sz;
    414 	while (cp < ep) {
    415 		*cp = kmem_poison_pattern(cp);
    416 		cp++;
    417 	}
    418 }
    419 
    420 static void
    421 kmem_poison_check(void *p, size_t sz)
    422 {
    423 	uint8_t *cp;
    424 	const uint8_t *ep;
    425 
    426 	cp = p;
    427 	ep = cp + sz;
    428 	while (cp < ep) {
    429 		const uint8_t expected = kmem_poison_pattern(cp);
    430 
    431 		if (*cp != expected) {
    432 			panic("%s: %p: 0x%02x != 0x%02x\n",
    433 			    __func__, cp, *cp, expected);
    434 		}
    435 		cp++;
    436 	}
    437 }
    438 
    439 #endif /* defined(KMEM_POISON) */
    440 
    441 #if defined(KMEM_SIZE)
    442 static void
    443 kmem_size_set(void *p, size_t sz)
    444 {
    445 
    446 	memcpy(p, &sz, sizeof(sz));
    447 }
    448 
    449 static void
    450 kmem_size_check(const void *p, size_t sz)
    451 {
    452 	size_t psz;
    453 
    454 	memcpy(&psz, p, sizeof(psz));
    455 	if (psz != sz) {
    456 		panic("kmem_free(%p, %zu) != allocated size %zu",
    457 		    (const uint8_t *)p + SIZE_SIZE, sz - SIZE_SIZE, psz);
    458 	}
    459 }
    460 #endif	/* defined(KMEM_SIZE) */
    461 
    462 /*
    463  * Used to dynamically allocate string with kmem accordingly to format.
    464  */
    465 char *
    466 kmem_asprintf(const char *fmt, ...)
    467 {
    468 	int size, str_len;
    469 	va_list va;
    470 	char *str;
    471 	char buf[1];
    472 
    473 	va_start(va, fmt);
    474 	str_len = vsnprintf(buf, sizeof(buf), fmt, va) + 1;
    475 	va_end(va);
    476 
    477 	str = kmem_alloc(str_len, KM_SLEEP);
    478 
    479 	if ((size = vsnprintf(str, str_len, fmt, va)) == -1) {
    480 		kmem_free(str, str_len);
    481 		return NULL;
    482 	}
    483 
    484 	return str;
    485 }
    486