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