Home | History | Annotate | Line # | Download | only in kern
subr_kmem.c revision 1.35 
      1 /*	$NetBSD: subr_kmem.c,v 1.35 2011/07/17 20:54:52 joerg 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.35 2011/07/17 20:54:52 joerg 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 #define	KMEM_QUANTUM_SIZE	(ALIGNBYTES + 1)
     83 #define	KMEM_QCACHE_MAX		(KMEM_QUANTUM_SIZE * 32)
     84 #define	KMEM_CACHE_COUNT	16
     85 
     86 typedef struct kmem_cache {
     87 	pool_cache_t		kc_cache;
     88 	struct pool_allocator	kc_pa;
     89 	char			kc_name[12];
     90 } kmem_cache_t;
     91 
     92 static vmem_t *kmem_arena;
     93 static struct callback_entry kmem_kva_reclaim_entry;
     94 
     95 static kmem_cache_t kmem_cache[KMEM_CACHE_COUNT + 1];
     96 static size_t kmem_cache_max;
     97 static size_t kmem_cache_min;
     98 static size_t kmem_cache_mask;
     99 static int kmem_cache_shift;
    100 
    101 #if defined(DEBUG)
    102 int kmem_guard_depth = 0;
    103 size_t kmem_guard_size;
    104 static struct uvm_kmguard kmem_guard;
    105 static void *kmem_freecheck;
    106 #define	KMEM_POISON
    107 #define	KMEM_REDZONE
    108 #define	KMEM_SIZE
    109 #define	KMEM_GUARD
    110 #endif /* defined(DEBUG) */
    111 
    112 #if defined(KMEM_POISON)
    113 static void kmem_poison_fill(void *, size_t);
    114 static void kmem_poison_check(void *, size_t);
    115 #else /* defined(KMEM_POISON) */
    116 #define	kmem_poison_fill(p, sz)		/* nothing */
    117 #define	kmem_poison_check(p, sz)	/* nothing */
    118 #endif /* defined(KMEM_POISON) */
    119 
    120 #if defined(KMEM_REDZONE)
    121 #define	REDZONE_SIZE	1
    122 #else /* defined(KMEM_REDZONE) */
    123 #define	REDZONE_SIZE	0
    124 #endif /* defined(KMEM_REDZONE) */
    125 
    126 #if defined(KMEM_SIZE)
    127 #define	SIZE_SIZE	(max(KMEM_QUANTUM_SIZE, sizeof(size_t)))
    128 static void kmem_size_set(void *, size_t);
    129 static void kmem_size_check(const void *, size_t);
    130 #else
    131 #define	SIZE_SIZE	0
    132 #define	kmem_size_set(p, sz)	/* nothing */
    133 #define	kmem_size_check(p, sz)	/* nothing */
    134 #endif
    135 
    136 static vmem_addr_t kmem_backend_alloc(vmem_t *, vmem_size_t, vmem_size_t *,
    137     vm_flag_t);
    138 static void kmem_backend_free(vmem_t *, vmem_addr_t, vmem_size_t);
    139 static int kmem_kva_reclaim_callback(struct callback_entry *, void *, void *);
    140 
    141 CTASSERT(KM_SLEEP == PR_WAITOK);
    142 CTASSERT(KM_NOSLEEP == PR_NOWAIT);
    143 
    144 static inline vm_flag_t
    145 kmf_to_vmf(km_flag_t kmflags)
    146 {
    147 	vm_flag_t vmflags;
    148 
    149 	KASSERT((kmflags & (KM_SLEEP|KM_NOSLEEP)) != 0);
    150 	KASSERT((~kmflags & (KM_SLEEP|KM_NOSLEEP)) != 0);
    151 
    152 	vmflags = 0;
    153 	if ((kmflags & KM_SLEEP) != 0) {
    154 		vmflags |= VM_SLEEP;
    155 	}
    156 	if ((kmflags & KM_NOSLEEP) != 0) {
    157 		vmflags |= VM_NOSLEEP;
    158 	}
    159 
    160 	return vmflags;
    161 }
    162 
    163 static void *
    164 kmem_poolpage_alloc(struct pool *pool, int prflags)
    165 {
    166 
    167 	return (void *)vmem_alloc(kmem_arena, pool->pr_alloc->pa_pagesz,
    168 	    kmf_to_vmf(prflags) | VM_INSTANTFIT);
    169 
    170 }
    171 
    172 static void
    173 kmem_poolpage_free(struct pool *pool, void *addr)
    174 {
    175 
    176 	vmem_free(kmem_arena, (vmem_addr_t)addr, pool->pr_alloc->pa_pagesz);
    177 }
    178 
    179 /* ---- kmem API */
    180 
    181 /*
    182  * kmem_alloc: allocate wired memory.
    183  *
    184  * => must not be called from interrupt context.
    185  */
    186 
    187 void *
    188 kmem_alloc(size_t size, km_flag_t kmflags)
    189 {
    190 	kmem_cache_t *kc;
    191 	uint8_t *p;
    192 
    193 	KASSERT(!cpu_intr_p());
    194 	KASSERT(!cpu_softintr_p());
    195 	KASSERT(size > 0);
    196 
    197 #ifdef KMEM_GUARD
    198 	if (size <= kmem_guard_size) {
    199 		return uvm_kmguard_alloc(&kmem_guard, size,
    200 		    (kmflags & KM_SLEEP) != 0);
    201 	}
    202 #endif
    203 
    204 	size += REDZONE_SIZE + SIZE_SIZE;
    205 	if (size >= kmem_cache_min && size <= kmem_cache_max) {
    206 		kc = &kmem_cache[(size + kmem_cache_mask) >> kmem_cache_shift];
    207 		KASSERT(size <= kc->kc_pa.pa_pagesz);
    208 		kmflags &= (KM_SLEEP | KM_NOSLEEP);
    209 		p = pool_cache_get(kc->kc_cache, kmflags);
    210 	} else {
    211 		p = (void *)vmem_alloc(kmem_arena, size,
    212 		    kmf_to_vmf(kmflags) | VM_INSTANTFIT);
    213 	}
    214 	if (__predict_true(p != NULL)) {
    215 		kmem_poison_check(p, kmem_roundup_size(size));
    216 		FREECHECK_OUT(&kmem_freecheck, p);
    217 		kmem_size_set(p, size);
    218 		p = (uint8_t *)p + SIZE_SIZE;
    219 	}
    220 	return p;
    221 }
    222 
    223 /*
    224  * kmem_zalloc: allocate wired memory.
    225  *
    226  * => must not be called from interrupt context.
    227  */
    228 
    229 void *
    230 kmem_zalloc(size_t size, km_flag_t kmflags)
    231 {
    232 	void *p;
    233 
    234 	p = kmem_alloc(size, kmflags);
    235 	if (p != NULL) {
    236 		memset(p, 0, size);
    237 	}
    238 	return p;
    239 }
    240 
    241 /*
    242  * kmem_free: free wired memory allocated by kmem_alloc.
    243  *
    244  * => must not be called from interrupt context.
    245  */
    246 
    247 void
    248 kmem_free(void *p, size_t size)
    249 {
    250 	kmem_cache_t *kc;
    251 
    252 	KASSERT(!cpu_intr_p());
    253 	KASSERT(!cpu_softintr_p());
    254 	KASSERT(p != NULL);
    255 	KASSERT(size > 0);
    256 
    257 #ifdef KMEM_GUARD
    258 	if (size <= kmem_guard_size) {
    259 		uvm_kmguard_free(&kmem_guard, size, p);
    260 		return;
    261 	}
    262 #endif
    263 	size += SIZE_SIZE;
    264 	p = (uint8_t *)p - SIZE_SIZE;
    265 	kmem_size_check(p, size + REDZONE_SIZE);
    266 	FREECHECK_IN(&kmem_freecheck, p);
    267 	LOCKDEBUG_MEM_CHECK(p, size);
    268 	kmem_poison_check((char *)p + size,
    269 	    kmem_roundup_size(size + REDZONE_SIZE) - size);
    270 	kmem_poison_fill(p, size);
    271 	size += REDZONE_SIZE;
    272 	if (size >= kmem_cache_min && size <= kmem_cache_max) {
    273 		kc = &kmem_cache[(size + kmem_cache_mask) >> kmem_cache_shift];
    274 		KASSERT(size <= kc->kc_pa.pa_pagesz);
    275 		pool_cache_put(kc->kc_cache, p);
    276 	} else {
    277 		vmem_free(kmem_arena, (vmem_addr_t)p, size);
    278 	}
    279 }
    280 
    281 
    282 void
    283 kmem_init(void)
    284 {
    285 	kmem_cache_t *kc;
    286 	size_t sz;
    287 	int i;
    288 
    289 #ifdef KMEM_GUARD
    290 	uvm_kmguard_init(&kmem_guard, &kmem_guard_depth, &kmem_guard_size,
    291 	    kernel_map);
    292 #endif
    293 
    294 	kmem_arena = vmem_create("kmem", 0, 0, KMEM_QUANTUM_SIZE,
    295 	    kmem_backend_alloc, kmem_backend_free, NULL, KMEM_QCACHE_MAX,
    296 	    VM_SLEEP, IPL_NONE);
    297 	callback_register(&vm_map_to_kernel(kernel_map)->vmk_reclaim_callback,
    298 	    &kmem_kva_reclaim_entry, kmem_arena, kmem_kva_reclaim_callback);
    299 
    300 	/*
    301 	 * kmem caches start at twice the size of the largest vmem qcache
    302 	 * and end at PAGE_SIZE or earlier.  assert that KMEM_QCACHE_MAX
    303 	 * is a power of two.
    304 	 */
    305 	KASSERT(ffs(KMEM_QCACHE_MAX) != 0);
    306 	KASSERT(KMEM_QCACHE_MAX - (1 << (ffs(KMEM_QCACHE_MAX) - 1)) == 0);
    307 	kmem_cache_shift = ffs(KMEM_QCACHE_MAX);
    308 	kmem_cache_min = 1 << kmem_cache_shift;
    309 	kmem_cache_mask = kmem_cache_min - 1;
    310 	for (i = 1; i <= KMEM_CACHE_COUNT; i++) {
    311 		sz = i << kmem_cache_shift;
    312 		if (sz > PAGE_SIZE) {
    313 			break;
    314 		}
    315 		kmem_cache_max = sz;
    316 		kc = &kmem_cache[i];
    317 		kc->kc_pa.pa_pagesz = sz;
    318 		kc->kc_pa.pa_alloc = kmem_poolpage_alloc;
    319 		kc->kc_pa.pa_free = kmem_poolpage_free;
    320 		sprintf(kc->kc_name, "kmem-%zu", sz);
    321 		kc->kc_cache = pool_cache_init(sz,
    322 		    KMEM_QUANTUM_SIZE, 0, PR_NOALIGN | PR_NOTOUCH,
    323 		    kc->kc_name, &kc->kc_pa, IPL_NONE,
    324 		    NULL, NULL, NULL);
    325 		KASSERT(kc->kc_cache != NULL);
    326 	}
    327 }
    328 
    329 size_t
    330 kmem_roundup_size(size_t size)
    331 {
    332 
    333 	return vmem_roundup_size(kmem_arena, size);
    334 }
    335 
    336 /* ---- uvm glue */
    337 
    338 static vmem_addr_t
    339 kmem_backend_alloc(vmem_t *dummy, vmem_size_t size, vmem_size_t *resultsize,
    340     vm_flag_t vmflags)
    341 {
    342 	uvm_flag_t uflags;
    343 	vaddr_t va;
    344 
    345 	KASSERT(dummy == NULL);
    346 	KASSERT(size != 0);
    347 	KASSERT((vmflags & (VM_SLEEP|VM_NOSLEEP)) != 0);
    348 	KASSERT((~vmflags & (VM_SLEEP|VM_NOSLEEP)) != 0);
    349 
    350 	if ((vmflags & VM_NOSLEEP) != 0) {
    351 		uflags = UVM_KMF_TRYLOCK | UVM_KMF_NOWAIT;
    352 	} else {
    353 		uflags = UVM_KMF_WAITVA;
    354 	}
    355 	*resultsize = size = round_page(size);
    356 	va = uvm_km_alloc(kernel_map, size, 0,
    357 	    uflags | UVM_KMF_WIRED | UVM_KMF_CANFAIL);
    358 	if (va != 0) {
    359 		kmem_poison_fill((void *)va, size);
    360 	}
    361 	return (vmem_addr_t)va;
    362 }
    363 
    364 static void
    365 kmem_backend_free(vmem_t *dummy, vmem_addr_t addr, vmem_size_t size)
    366 {
    367 
    368 	KASSERT(dummy == NULL);
    369 	KASSERT(addr != 0);
    370 	KASSERT(size != 0);
    371 	KASSERT(size == round_page(size));
    372 
    373 	kmem_poison_check((void *)addr, size);
    374 	uvm_km_free(kernel_map, (vaddr_t)addr, size, UVM_KMF_WIRED);
    375 }
    376 
    377 static int
    378 kmem_kva_reclaim_callback(struct callback_entry *ce, void *obj, void *arg)
    379 {
    380 	vmem_t *vm = obj;
    381 
    382 	vmem_reap(vm);
    383 	return CALLBACK_CHAIN_CONTINUE;
    384 }
    385 
    386 /* ---- debug */
    387 
    388 #if defined(KMEM_POISON)
    389 
    390 #if defined(_LP64)
    391 #define	PRIME	0x9e37fffffffc0001UL
    392 #else /* defined(_LP64) */
    393 #define	PRIME	0x9e3779b1
    394 #endif /* defined(_LP64) */
    395 
    396 static inline uint8_t
    397 kmem_poison_pattern(const void *p)
    398 {
    399 
    400 	return (uint8_t)((((uintptr_t)p) * PRIME)
    401 	    >> ((sizeof(uintptr_t) - sizeof(uint8_t))) * CHAR_BIT);
    402 }
    403 
    404 static void
    405 kmem_poison_fill(void *p, size_t sz)
    406 {
    407 	uint8_t *cp;
    408 	const uint8_t *ep;
    409 
    410 	cp = p;
    411 	ep = cp + sz;
    412 	while (cp < ep) {
    413 		*cp = kmem_poison_pattern(cp);
    414 		cp++;
    415 	}
    416 }
    417 
    418 static void
    419 kmem_poison_check(void *p, size_t sz)
    420 {
    421 	uint8_t *cp;
    422 	const uint8_t *ep;
    423 
    424 	cp = p;
    425 	ep = cp + sz;
    426 	while (cp < ep) {
    427 		const uint8_t expected = kmem_poison_pattern(cp);
    428 
    429 		if (*cp != expected) {
    430 			panic("%s: %p: 0x%02x != 0x%02x\n",
    431 			    __func__, cp, *cp, expected);
    432 		}
    433 		cp++;
    434 	}
    435 }
    436 
    437 #endif /* defined(KMEM_POISON) */
    438 
    439 #if defined(KMEM_SIZE)
    440 static void
    441 kmem_size_set(void *p, size_t sz)
    442 {
    443 
    444 	memcpy(p, &sz, sizeof(sz));
    445 }
    446 
    447 static void
    448 kmem_size_check(const void *p, size_t sz)
    449 {
    450 	size_t psz;
    451 
    452 	memcpy(&psz, p, sizeof(psz));
    453 	if (psz != sz) {
    454 		panic("kmem_free(%p, %zu) != allocated size %zu",
    455 		    (const uint8_t *)p + SIZE_SIZE, sz - SIZE_SIZE, psz);
    456 	}
    457 }
    458 #endif	/* defined(KMEM_SIZE) */
    459 
    460 /*
    461  * Used to dynamically allocate string with kmem accordingly to format.
    462  */
    463 char *
    464 kmem_asprintf(const char *fmt, ...)
    465 {
    466 	int size, str_len;
    467 	va_list va;
    468 	char *str;
    469 	char buf[1];
    470 
    471 	va_start(va, fmt);
    472 	str_len = vsnprintf(buf, sizeof(buf), fmt, va) + 1;
    473 	va_end(va);
    474 
    475 	str = kmem_alloc(str_len, KM_SLEEP);
    476 
    477 	if ((size = vsnprintf(str, str_len, fmt, va)) == -1) {
    478 		kmem_free(str, str_len);
    479 		return NULL;
    480 	}
    481 
    482 	return str;
    483 }
    484