1 /* $NetBSD: kern_malloc.c,v 1.121.4.1 2010/02/14 13:37:42 bouyer Exp $ */
2
3 /*
4 * Copyright (c) 1987, 1991, 1993
5 * The Regents of the University of California. All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 * 3. Neither the name of the University nor the names of its contributors
16 * may be used to endorse or promote products derived from this software
17 * without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 * SUCH DAMAGE.
30 *
31 * @(#)kern_malloc.c 8.4 (Berkeley) 5/20/95
32 */
33
34 /*
35 * Copyright (c) 1996 Christopher G. Demetriou. All rights reserved.
36 *
37 * Redistribution and use in source and binary forms, with or without
38 * modification, are permitted provided that the following conditions
39 * are met:
40 * 1. Redistributions of source code must retain the above copyright
41 * notice, this list of conditions and the following disclaimer.
42 * 2. Redistributions in binary form must reproduce the above copyright
43 * notice, this list of conditions and the following disclaimer in the
44 * documentation and/or other materials provided with the distribution.
45 * 3. All advertising materials mentioning features or use of this software
46 * must display the following acknowledgement:
47 * This product includes software developed by the University of
48 * California, Berkeley and its contributors.
49 * 4. Neither the name of the University nor the names of its contributors
50 * may be used to endorse or promote products derived from this software
51 * without specific prior written permission.
52 *
53 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
54 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
55 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
56 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
57 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
58 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
59 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
60 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
61 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
62 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
63 * SUCH DAMAGE.
64 *
65 * @(#)kern_malloc.c 8.4 (Berkeley) 5/20/95
66 */
67
68 #include <sys/cdefs.h>
69 __KERNEL_RCSID(0, "$NetBSD: kern_malloc.c,v 1.121.4.1 2010/02/14 13:37:42 bouyer Exp $");
70
71 #include <sys/param.h>
72 #include <sys/proc.h>
73 #include <sys/kernel.h>
74 #include <sys/malloc.h>
75 #include <sys/systm.h>
76 #include <sys/debug.h>
77 #include <sys/mutex.h>
78 #include <sys/lockdebug.h>
79
80 #include <uvm/uvm_extern.h>
81
82 static struct vm_map_kernel kmem_map_store;
83 struct vm_map *kmem_map = NULL;
84
85 #include "opt_kmempages.h"
86
87 #ifdef NKMEMCLUSTERS
88 #error NKMEMCLUSTERS is obsolete; remove it from your kernel config file and use NKMEMPAGES instead or let the kernel auto-size
89 #endif
90
91 /*
92 * Default number of pages in kmem_map. We attempt to calculate this
93 * at run-time, but allow it to be either patched or set in the kernel
94 * config file.
95 */
96 #ifndef NKMEMPAGES
97 #define NKMEMPAGES 0
98 #endif
99 int nkmempages = NKMEMPAGES;
100
101 /*
102 * Defaults for lower- and upper-bounds for the kmem_map page count.
103 * Can be overridden by kernel config options.
104 */
105 #ifndef NKMEMPAGES_MIN
106 #define NKMEMPAGES_MIN NKMEMPAGES_MIN_DEFAULT
107 #endif
108
109 #ifndef NKMEMPAGES_MAX
110 #define NKMEMPAGES_MAX NKMEMPAGES_MAX_DEFAULT
111 #endif
112
113 #include "opt_kmemstats.h"
114 #include "opt_malloclog.h"
115 #include "opt_malloc_debug.h"
116
117 #define MINALLOCSIZE (1 << MINBUCKET)
118 #define BUCKETINDX(size) \
119 ((size) <= (MINALLOCSIZE * 128) \
120 ? (size) <= (MINALLOCSIZE * 8) \
121 ? (size) <= (MINALLOCSIZE * 2) \
122 ? (size) <= (MINALLOCSIZE * 1) \
123 ? (MINBUCKET + 0) \
124 : (MINBUCKET + 1) \
125 : (size) <= (MINALLOCSIZE * 4) \
126 ? (MINBUCKET + 2) \
127 : (MINBUCKET + 3) \
128 : (size) <= (MINALLOCSIZE* 32) \
129 ? (size) <= (MINALLOCSIZE * 16) \
130 ? (MINBUCKET + 4) \
131 : (MINBUCKET + 5) \
132 : (size) <= (MINALLOCSIZE * 64) \
133 ? (MINBUCKET + 6) \
134 : (MINBUCKET + 7) \
135 : (size) <= (MINALLOCSIZE * 2048) \
136 ? (size) <= (MINALLOCSIZE * 512) \
137 ? (size) <= (MINALLOCSIZE * 256) \
138 ? (MINBUCKET + 8) \
139 : (MINBUCKET + 9) \
140 : (size) <= (MINALLOCSIZE * 1024) \
141 ? (MINBUCKET + 10) \
142 : (MINBUCKET + 11) \
143 : (size) <= (MINALLOCSIZE * 8192) \
144 ? (size) <= (MINALLOCSIZE * 4096) \
145 ? (MINBUCKET + 12) \
146 : (MINBUCKET + 13) \
147 : (size) <= (MINALLOCSIZE * 16384) \
148 ? (MINBUCKET + 14) \
149 : (MINBUCKET + 15))
150
151 /*
152 * Array of descriptors that describe the contents of each page
153 */
154 struct kmemusage {
155 short ku_indx; /* bucket index */
156 union {
157 u_short freecnt;/* for small allocations, free pieces in page */
158 u_short pagecnt;/* for large allocations, pages alloced */
159 } ku_un;
160 };
161 #define ku_freecnt ku_un.freecnt
162 #define ku_pagecnt ku_un.pagecnt
163
164 struct kmembuckets kmembuckets[MINBUCKET + 16];
165 struct kmemusage *kmemusage;
166 char *kmembase, *kmemlimit;
167
168 #ifdef DEBUG
169 static void *malloc_freecheck;
170 #endif
171
172 /*
173 * Turn virtual addresses into kmem map indicies
174 */
175 #define btokup(addr) (&kmemusage[((char *)(addr) - kmembase) >> PGSHIFT])
176
177 struct malloc_type *kmemstatistics;
178
179 #ifdef MALLOCLOG
180 #ifndef MALLOCLOGSIZE
181 #define MALLOCLOGSIZE 100000
182 #endif
183
184 struct malloclog {
185 void *addr;
186 long size;
187 struct malloc_type *type;
188 int action;
189 const char *file;
190 long line;
191 } malloclog[MALLOCLOGSIZE];
192
193 long malloclogptr;
194
195 /*
196 * Fuzz factor for neighbour address match this must be a mask of the lower
197 * bits we wish to ignore when comparing addresses
198 */
199 __uintptr_t malloclog_fuzz = 0x7FL;
200
201
202 static void
203 domlog(void *a, long size, struct malloc_type *type, int action,
204 const char *file, long line)
205 {
206
207 malloclog[malloclogptr].addr = a;
208 malloclog[malloclogptr].size = size;
209 malloclog[malloclogptr].type = type;
210 malloclog[malloclogptr].action = action;
211 malloclog[malloclogptr].file = file;
212 malloclog[malloclogptr].line = line;
213 malloclogptr++;
214 if (malloclogptr >= MALLOCLOGSIZE)
215 malloclogptr = 0;
216 }
217
218 #ifdef DIAGNOSTIC
219 static void
220 hitmlog(void *a)
221 {
222 struct malloclog *lp;
223 long l;
224
225 #define PRT do { \
226 lp = &malloclog[l]; \
227 if (lp->addr == a && lp->action) { \
228 printf("malloc log entry %ld:\n", l); \
229 printf("\taddr = %p\n", lp->addr); \
230 printf("\tsize = %ld\n", lp->size); \
231 printf("\ttype = %s\n", lp->type->ks_shortdesc); \
232 printf("\taction = %s\n", lp->action == 1 ? "alloc" : "free"); \
233 printf("\tfile = %s\n", lp->file); \
234 printf("\tline = %ld\n", lp->line); \
235 } \
236 } while (/* CONSTCOND */0)
237
238 /*
239 * Print fuzzy matched "neighbour" - look for the memory block that has
240 * been allocated below the address we are interested in. We look for a
241 * base address + size that is within malloclog_fuzz of our target
242 * address. If the base address and target address are the same then it is
243 * likely we have found a free (size is 0 in this case) so we won't report
244 * those, they will get reported by PRT anyway.
245 */
246 #define NPRT do { \
247 __uintptr_t fuzz_mask = ~(malloclog_fuzz); \
248 lp = &malloclog[l]; \
249 if ((__uintptr_t)lp->addr != (__uintptr_t)a && \
250 (((__uintptr_t)lp->addr + lp->size + malloclog_fuzz) & fuzz_mask) \
251 == ((__uintptr_t)a & fuzz_mask) && lp->action) { \
252 printf("neighbour malloc log entry %ld:\n", l); \
253 printf("\taddr = %p\n", lp->addr); \
254 printf("\tsize = %ld\n", lp->size); \
255 printf("\ttype = %s\n", lp->type->ks_shortdesc); \
256 printf("\taction = %s\n", lp->action == 1 ? "alloc" : "free"); \
257 printf("\tfile = %s\n", lp->file); \
258 printf("\tline = %ld\n", lp->line); \
259 } \
260 } while (/* CONSTCOND */0)
261
262 for (l = malloclogptr; l < MALLOCLOGSIZE; l++) {
263 PRT;
264 NPRT;
265 }
266
267
268 for (l = 0; l < malloclogptr; l++) {
269 PRT;
270 NPRT;
271 }
272
273 #undef PRT
274 }
275 #endif /* DIAGNOSTIC */
276 #endif /* MALLOCLOG */
277
278 #ifdef DIAGNOSTIC
279 /*
280 * This structure provides a set of masks to catch unaligned frees.
281 */
282 const long addrmask[] = { 0,
283 0x00000001, 0x00000003, 0x00000007, 0x0000000f,
284 0x0000001f, 0x0000003f, 0x0000007f, 0x000000ff,
285 0x000001ff, 0x000003ff, 0x000007ff, 0x00000fff,
286 0x00001fff, 0x00003fff, 0x00007fff, 0x0000ffff,
287 };
288
289 /*
290 * The WEIRD_ADDR is used as known text to copy into free objects so
291 * that modifications after frees can be detected.
292 */
293 #define WEIRD_ADDR ((uint32_t) 0xdeadbeef)
294 #ifdef DEBUG
295 #define MAX_COPY PAGE_SIZE
296 #else
297 #define MAX_COPY 32
298 #endif
299
300 /*
301 * Normally the freelist structure is used only to hold the list pointer
302 * for free objects. However, when running with diagnostics, the first
303 * 8/16 bytes of the structure is unused except for diagnostic information,
304 * and the free list pointer is at offset 8/16 in the structure. Since the
305 * first 8 bytes is the portion of the structure most often modified, this
306 * helps to detect memory reuse problems and avoid free list corruption.
307 */
308 struct freelist {
309 uint32_t spare0;
310 #ifdef _LP64
311 uint32_t spare1; /* explicit padding */
312 #endif
313 struct malloc_type *type;
314 void * next;
315 };
316 #else /* !DIAGNOSTIC */
317 struct freelist {
318 void * next;
319 };
320 #endif /* DIAGNOSTIC */
321
322 kmutex_t malloc_lock;
323
324 /*
325 * Allocate a block of memory
326 */
327 #ifdef MALLOCLOG
328 void *
329 _malloc(unsigned long size, struct malloc_type *ksp, int flags,
330 const char *file, long line)
331 #else
332 void *
333 malloc(unsigned long size, struct malloc_type *ksp, int flags)
334 #endif /* MALLOCLOG */
335 {
336 struct kmembuckets *kbp;
337 struct kmemusage *kup;
338 struct freelist *freep;
339 long indx, npg, allocsize;
340 char *va, *cp, *savedlist;
341 #ifdef DIAGNOSTIC
342 uint32_t *end, *lp;
343 int copysize;
344 #endif
345
346 #ifdef LOCKDEBUG
347 if ((flags & M_NOWAIT) == 0) {
348 ASSERT_SLEEPABLE();
349 }
350 #endif
351 #ifdef MALLOC_DEBUG
352 if (debug_malloc(size, ksp, flags, (void *) &va)) {
353 if (va != 0)
354 FREECHECK_OUT(&malloc_freecheck, (void *)va);
355 return ((void *) va);
356 }
357 #endif
358 indx = BUCKETINDX(size);
359 kbp = &kmembuckets[indx];
360 mutex_spin_enter(&malloc_lock);
361 #ifdef KMEMSTATS
362 while (ksp->ks_memuse >= ksp->ks_limit) {
363 if (flags & M_NOWAIT) {
364 mutex_spin_exit(&malloc_lock);
365 return ((void *) NULL);
366 }
367 if (ksp->ks_limblocks < 65535)
368 ksp->ks_limblocks++;
369 mtsleep((void *)ksp, PSWP+2, ksp->ks_shortdesc, 0,
370 &malloc_lock);
371 }
372 ksp->ks_size |= 1 << indx;
373 #endif
374 #ifdef DIAGNOSTIC
375 copysize = 1 << indx < MAX_COPY ? 1 << indx : MAX_COPY;
376 #endif
377 if (kbp->kb_next == NULL) {
378 int s;
379 kbp->kb_last = NULL;
380 if (size > MAXALLOCSAVE)
381 allocsize = round_page(size);
382 else
383 allocsize = 1 << indx;
384 npg = btoc(allocsize);
385 mutex_spin_exit(&malloc_lock);
386 s = splvm();
387 va = (void *) uvm_km_alloc(kmem_map,
388 (vsize_t)ctob(npg), 0,
389 ((flags & M_NOWAIT) ? UVM_KMF_NOWAIT : 0) |
390 ((flags & M_CANFAIL) ? UVM_KMF_CANFAIL : 0) |
391 UVM_KMF_WIRED);
392 splx(s);
393 if (__predict_false(va == NULL)) {
394 /*
395 * Kmem_malloc() can return NULL, even if it can
396 * wait, if there is no map space available, because
397 * it can't fix that problem. Neither can we,
398 * right now. (We should release pages which
399 * are completely free and which are in kmembuckets
400 * with too many free elements.)
401 */
402 if ((flags & (M_NOWAIT|M_CANFAIL)) == 0)
403 panic("malloc: out of space in kmem_map");
404 return (NULL);
405 }
406 mutex_spin_enter(&malloc_lock);
407 #ifdef KMEMSTATS
408 kbp->kb_total += kbp->kb_elmpercl;
409 #endif
410 kup = btokup(va);
411 kup->ku_indx = indx;
412 if (allocsize > MAXALLOCSAVE) {
413 if (npg > 65535)
414 panic("malloc: allocation too large");
415 kup->ku_pagecnt = npg;
416 #ifdef KMEMSTATS
417 ksp->ks_memuse += allocsize;
418 #endif
419 goto out;
420 }
421 #ifdef KMEMSTATS
422 kup->ku_freecnt = kbp->kb_elmpercl;
423 kbp->kb_totalfree += kbp->kb_elmpercl;
424 #endif
425 /*
426 * Just in case we blocked while allocating memory,
427 * and someone else also allocated memory for this
428 * kmembucket, don't assume the list is still empty.
429 */
430 savedlist = kbp->kb_next;
431 kbp->kb_next = cp = va + (npg << PAGE_SHIFT) - allocsize;
432 for (;;) {
433 freep = (struct freelist *)cp;
434 #ifdef DIAGNOSTIC
435 /*
436 * Copy in known text to detect modification
437 * after freeing.
438 */
439 end = (uint32_t *)&cp[copysize];
440 for (lp = (uint32_t *)cp; lp < end; lp++)
441 *lp = WEIRD_ADDR;
442 freep->type = M_FREE;
443 #endif /* DIAGNOSTIC */
444 if (cp <= va)
445 break;
446 cp -= allocsize;
447 freep->next = cp;
448 }
449 freep->next = savedlist;
450 if (savedlist == NULL)
451 kbp->kb_last = (void *)freep;
452 }
453 va = kbp->kb_next;
454 kbp->kb_next = ((struct freelist *)va)->next;
455 #ifdef DIAGNOSTIC
456 freep = (struct freelist *)va;
457 /* XXX potential to get garbage pointer here. */
458 if (kbp->kb_next) {
459 int rv;
460 vaddr_t addr = (vaddr_t)kbp->kb_next;
461
462 vm_map_lock(kmem_map);
463 rv = uvm_map_checkprot(kmem_map, addr,
464 addr + sizeof(struct freelist), VM_PROT_WRITE);
465 vm_map_unlock(kmem_map);
466
467 if (__predict_false(rv == 0)) {
468 printf("Data modified on freelist: "
469 "word %ld of object %p size %ld previous type %s "
470 "(invalid addr %p)\n",
471 (long)((int32_t *)&kbp->kb_next - (int32_t *)kbp),
472 va, size, "foo", kbp->kb_next);
473 #ifdef MALLOCLOG
474 hitmlog(va);
475 #endif
476 kbp->kb_next = NULL;
477 }
478 }
479
480 /* Fill the fields that we've used with WEIRD_ADDR */
481 #ifdef _LP64
482 freep->type = (struct malloc_type *)
483 (WEIRD_ADDR | (((u_long) WEIRD_ADDR) << 32));
484 #else
485 freep->type = (struct malloc_type *) WEIRD_ADDR;
486 #endif
487 end = (uint32_t *)&freep->next +
488 (sizeof(freep->next) / sizeof(int32_t));
489 for (lp = (uint32_t *)&freep->next; lp < end; lp++)
490 *lp = WEIRD_ADDR;
491
492 /* and check that the data hasn't been modified. */
493 end = (uint32_t *)&va[copysize];
494 for (lp = (uint32_t *)va; lp < end; lp++) {
495 if (__predict_true(*lp == WEIRD_ADDR))
496 continue;
497 printf("Data modified on freelist: "
498 "word %ld of object %p size %ld previous type %s "
499 "(0x%x != 0x%x)\n",
500 (long)(lp - (uint32_t *)va), va, size,
501 "bar", *lp, WEIRD_ADDR);
502 #ifdef MALLOCLOG
503 hitmlog(va);
504 #endif
505 break;
506 }
507
508 freep->spare0 = 0;
509 #endif /* DIAGNOSTIC */
510 #ifdef KMEMSTATS
511 kup = btokup(va);
512 if (kup->ku_indx != indx)
513 panic("malloc: wrong bucket");
514 if (kup->ku_freecnt == 0)
515 panic("malloc: lost data");
516 kup->ku_freecnt--;
517 kbp->kb_totalfree--;
518 ksp->ks_memuse += 1 << indx;
519 out:
520 kbp->kb_calls++;
521 ksp->ks_inuse++;
522 ksp->ks_calls++;
523 if (ksp->ks_memuse > ksp->ks_maxused)
524 ksp->ks_maxused = ksp->ks_memuse;
525 #else
526 out:
527 #endif
528 #ifdef MALLOCLOG
529 domlog(va, size, ksp, 1, file, line);
530 #endif
531 mutex_spin_exit(&malloc_lock);
532 if ((flags & M_ZERO) != 0)
533 memset(va, 0, size);
534 FREECHECK_OUT(&malloc_freecheck, (void *)va);
535 return ((void *) va);
536 }
537
538 /*
539 * Free a block of memory allocated by malloc.
540 */
541 #ifdef MALLOCLOG
542 void
543 _free(void *addr, struct malloc_type *ksp, const char *file, long line)
544 #else
545 void
546 free(void *addr, struct malloc_type *ksp)
547 #endif /* MALLOCLOG */
548 {
549 struct kmembuckets *kbp;
550 struct kmemusage *kup;
551 struct freelist *freep;
552 long size;
553 #ifdef DIAGNOSTIC
554 void *cp;
555 int32_t *end, *lp;
556 long alloc, copysize;
557 #endif
558
559 FREECHECK_IN(&malloc_freecheck, addr);
560 #ifdef MALLOC_DEBUG
561 if (debug_free(addr, ksp))
562 return;
563 #endif
564
565 #ifdef DIAGNOSTIC
566 /*
567 * Ensure that we're free'ing something that we could
568 * have allocated in the first place. That is, check
569 * to see that the address is within kmem_map.
570 */
571 if (__predict_false((vaddr_t)addr < vm_map_min(kmem_map) ||
572 (vaddr_t)addr >= vm_map_max(kmem_map)))
573 panic("free: addr %p not within kmem_map", addr);
574 #endif
575
576 kup = btokup(addr);
577 size = 1 << kup->ku_indx;
578 kbp = &kmembuckets[kup->ku_indx];
579
580 LOCKDEBUG_MEM_CHECK(addr,
581 size <= MAXALLOCSAVE ? size : ctob(kup->ku_pagecnt));
582
583 mutex_spin_enter(&malloc_lock);
584 #ifdef MALLOCLOG
585 domlog(addr, 0, ksp, 2, file, line);
586 #endif
587 #ifdef DIAGNOSTIC
588 /*
589 * Check for returns of data that do not point to the
590 * beginning of the allocation.
591 */
592 if (size > PAGE_SIZE)
593 alloc = addrmask[BUCKETINDX(PAGE_SIZE)];
594 else
595 alloc = addrmask[kup->ku_indx];
596 if (((u_long)addr & alloc) != 0)
597 panic("free: unaligned addr %p, size %ld, type %s, mask %ld",
598 addr, size, ksp->ks_shortdesc, alloc);
599 #endif /* DIAGNOSTIC */
600 if (size > MAXALLOCSAVE) {
601 uvm_km_free(kmem_map, (vaddr_t)addr, ctob(kup->ku_pagecnt),
602 UVM_KMF_WIRED);
603 #ifdef KMEMSTATS
604 size = kup->ku_pagecnt << PGSHIFT;
605 ksp->ks_memuse -= size;
606 kup->ku_indx = 0;
607 kup->ku_pagecnt = 0;
608 if (ksp->ks_memuse + size >= ksp->ks_limit &&
609 ksp->ks_memuse < ksp->ks_limit)
610 wakeup((void *)ksp);
611 #ifdef DIAGNOSTIC
612 if (ksp->ks_inuse == 0)
613 panic("free 1: inuse 0, probable double free");
614 #endif
615 ksp->ks_inuse--;
616 kbp->kb_total -= 1;
617 #endif
618 mutex_spin_exit(&malloc_lock);
619 return;
620 }
621 freep = (struct freelist *)addr;
622 #ifdef DIAGNOSTIC
623 /*
624 * Check for multiple frees. Use a quick check to see if
625 * it looks free before laboriously searching the freelist.
626 */
627 if (__predict_false(freep->spare0 == WEIRD_ADDR)) {
628 for (cp = kbp->kb_next; cp;
629 cp = ((struct freelist *)cp)->next) {
630 if (addr != cp)
631 continue;
632 printf("multiply freed item %p\n", addr);
633 #ifdef MALLOCLOG
634 hitmlog(addr);
635 #endif
636 panic("free: duplicated free");
637 }
638 }
639
640 /*
641 * Copy in known text to detect modification after freeing
642 * and to make it look free. Also, save the type being freed
643 * so we can list likely culprit if modification is detected
644 * when the object is reallocated.
645 */
646 copysize = size < MAX_COPY ? size : MAX_COPY;
647 end = (int32_t *)&((char *)addr)[copysize];
648 for (lp = (int32_t *)addr; lp < end; lp++)
649 *lp = WEIRD_ADDR;
650 freep->type = ksp;
651 #endif /* DIAGNOSTIC */
652 #ifdef KMEMSTATS
653 kup->ku_freecnt++;
654 if (kup->ku_freecnt >= kbp->kb_elmpercl) {
655 if (kup->ku_freecnt > kbp->kb_elmpercl)
656 panic("free: multiple frees");
657 else if (kbp->kb_totalfree > kbp->kb_highwat)
658 kbp->kb_couldfree++;
659 }
660 kbp->kb_totalfree++;
661 ksp->ks_memuse -= size;
662 if (ksp->ks_memuse + size >= ksp->ks_limit &&
663 ksp->ks_memuse < ksp->ks_limit)
664 wakeup((void *)ksp);
665 #ifdef DIAGNOSTIC
666 if (ksp->ks_inuse == 0)
667 panic("free 2: inuse 0, probable double free");
668 #endif
669 ksp->ks_inuse--;
670 #endif
671 if (kbp->kb_next == NULL)
672 kbp->kb_next = addr;
673 else
674 ((struct freelist *)kbp->kb_last)->next = addr;
675 freep->next = NULL;
676 kbp->kb_last = addr;
677 mutex_spin_exit(&malloc_lock);
678 }
679
680 /*
681 * Change the size of a block of memory.
682 */
683 void *
684 realloc(void *curaddr, unsigned long newsize, struct malloc_type *ksp,
685 int flags)
686 {
687 struct kmemusage *kup;
688 unsigned long cursize;
689 void *newaddr;
690 #ifdef DIAGNOSTIC
691 long alloc;
692 #endif
693
694 /*
695 * realloc() with a NULL pointer is the same as malloc().
696 */
697 if (curaddr == NULL)
698 return (malloc(newsize, ksp, flags));
699
700 /*
701 * realloc() with zero size is the same as free().
702 */
703 if (newsize == 0) {
704 free(curaddr, ksp);
705 return (NULL);
706 }
707
708 #ifdef LOCKDEBUG
709 if ((flags & M_NOWAIT) == 0) {
710 ASSERT_SLEEPABLE();
711 }
712 #endif
713
714 /*
715 * Find out how large the old allocation was (and do some
716 * sanity checking).
717 */
718 kup = btokup(curaddr);
719 cursize = 1 << kup->ku_indx;
720
721 #ifdef DIAGNOSTIC
722 /*
723 * Check for returns of data that do not point to the
724 * beginning of the allocation.
725 */
726 if (cursize > PAGE_SIZE)
727 alloc = addrmask[BUCKETINDX(PAGE_SIZE)];
728 else
729 alloc = addrmask[kup->ku_indx];
730 if (((u_long)curaddr & alloc) != 0)
731 panic("realloc: "
732 "unaligned addr %p, size %ld, type %s, mask %ld\n",
733 curaddr, cursize, ksp->ks_shortdesc, alloc);
734 #endif /* DIAGNOSTIC */
735
736 if (cursize > MAXALLOCSAVE)
737 cursize = ctob(kup->ku_pagecnt);
738
739 /*
740 * If we already actually have as much as they want, we're done.
741 */
742 if (newsize <= cursize)
743 return (curaddr);
744
745 /*
746 * Can't satisfy the allocation with the existing block.
747 * Allocate a new one and copy the data.
748 */
749 newaddr = malloc(newsize, ksp, flags);
750 if (__predict_false(newaddr == NULL)) {
751 /*
752 * malloc() failed, because flags included M_NOWAIT.
753 * Return NULL to indicate that failure. The old
754 * pointer is still valid.
755 */
756 return (NULL);
757 }
758 memcpy(newaddr, curaddr, cursize);
759
760 /*
761 * We were successful: free the old allocation and return
762 * the new one.
763 */
764 free(curaddr, ksp);
765 return (newaddr);
766 }
767
768 /*
769 * Roundup size to the actual allocation size.
770 */
771 unsigned long
772 malloc_roundup(unsigned long size)
773 {
774
775 if (size > MAXALLOCSAVE)
776 return (roundup(size, PAGE_SIZE));
777 else
778 return (1 << BUCKETINDX(size));
779 }
780
781 /*
782 * Add a malloc type to the system.
783 */
784 void
785 malloc_type_attach(struct malloc_type *type)
786 {
787
788 if (nkmempages == 0)
789 panic("malloc_type_attach: nkmempages == 0");
790
791 if (type->ks_magic != M_MAGIC)
792 panic("malloc_type_attach: bad magic");
793
794 #ifdef DIAGNOSTIC
795 {
796 struct malloc_type *ksp;
797 for (ksp = kmemstatistics; ksp != NULL; ksp = ksp->ks_next) {
798 if (ksp == type)
799 panic("malloc_type_attach: already on list");
800 }
801 }
802 #endif
803
804 #ifdef KMEMSTATS
805 if (type->ks_limit == 0)
806 type->ks_limit = ((u_long)nkmempages << PAGE_SHIFT) * 6U / 10U;
807 #else
808 type->ks_limit = 0;
809 #endif
810
811 type->ks_next = kmemstatistics;
812 kmemstatistics = type;
813 }
814
815 /*
816 * Remove a malloc type from the system..
817 */
818 void
819 malloc_type_detach(struct malloc_type *type)
820 {
821 struct malloc_type *ksp;
822
823 #ifdef DIAGNOSTIC
824 if (type->ks_magic != M_MAGIC)
825 panic("malloc_type_detach: bad magic");
826 #endif
827
828 if (type == kmemstatistics)
829 kmemstatistics = type->ks_next;
830 else {
831 for (ksp = kmemstatistics; ksp->ks_next != NULL;
832 ksp = ksp->ks_next) {
833 if (ksp->ks_next == type) {
834 ksp->ks_next = type->ks_next;
835 break;
836 }
837 }
838 #ifdef DIAGNOSTIC
839 if (ksp->ks_next == NULL)
840 panic("malloc_type_detach: not on list");
841 #endif
842 }
843 type->ks_next = NULL;
844 }
845
846 /*
847 * Set the limit on a malloc type.
848 */
849 void
850 malloc_type_setlimit(struct malloc_type *type, u_long limit)
851 {
852 #ifdef KMEMSTATS
853 mutex_spin_enter(&malloc_lock);
854 type->ks_limit = limit;
855 mutex_spin_exit(&malloc_lock);
856 #endif
857 }
858
859 /*
860 * Compute the number of pages that kmem_map will map, that is,
861 * the size of the kernel malloc arena.
862 */
863 void
864 kmeminit_nkmempages(void)
865 {
866 int npages;
867
868 if (nkmempages != 0) {
869 /*
870 * It's already been set (by us being here before, or
871 * by patching or kernel config options), bail out now.
872 */
873 return;
874 }
875
876 npages = physmem;
877
878 if (npages > NKMEMPAGES_MAX)
879 npages = NKMEMPAGES_MAX;
880
881 if (npages < NKMEMPAGES_MIN)
882 npages = NKMEMPAGES_MIN;
883
884 nkmempages = npages;
885 }
886
887 /*
888 * Initialize the kernel memory allocator
889 */
890 void
891 kmeminit(void)
892 {
893 __link_set_decl(malloc_types, struct malloc_type);
894 struct malloc_type * const *ksp;
895 vaddr_t kmb, kml;
896 #ifdef KMEMSTATS
897 long indx;
898 #endif
899
900 #if ((MAXALLOCSAVE & (MAXALLOCSAVE - 1)) != 0)
901 ERROR!_kmeminit:_MAXALLOCSAVE_not_power_of_2
902 #endif
903 #if (MAXALLOCSAVE > MINALLOCSIZE * 32768)
904 ERROR!_kmeminit:_MAXALLOCSAVE_too_big
905 #endif
906 #if (MAXALLOCSAVE < NBPG)
907 ERROR!_kmeminit:_MAXALLOCSAVE_too_small
908 #endif
909
910 if (sizeof(struct freelist) > (1 << MINBUCKET))
911 panic("minbucket too small/struct freelist too big");
912
913 mutex_init(&malloc_lock, MUTEX_DEFAULT, IPL_VM);
914
915 /*
916 * Compute the number of kmem_map pages, if we have not
917 * done so already.
918 */
919 kmeminit_nkmempages();
920
921 kmemusage = (struct kmemusage *) uvm_km_alloc(kernel_map,
922 (vsize_t)(nkmempages * sizeof(struct kmemusage)), 0,
923 UVM_KMF_WIRED|UVM_KMF_ZERO);
924 kmb = 0;
925 kmem_map = uvm_km_suballoc(kernel_map, &kmb,
926 &kml, ((vsize_t)nkmempages << PAGE_SHIFT),
927 VM_MAP_INTRSAFE, false, &kmem_map_store);
928 uvm_km_vacache_init(kmem_map, "kvakmem", 0);
929 kmembase = (char *)kmb;
930 kmemlimit = (char *)kml;
931 #ifdef KMEMSTATS
932 for (indx = 0; indx < MINBUCKET + 16; indx++) {
933 if (1 << indx >= PAGE_SIZE)
934 kmembuckets[indx].kb_elmpercl = 1;
935 else
936 kmembuckets[indx].kb_elmpercl = PAGE_SIZE / (1 << indx);
937 kmembuckets[indx].kb_highwat =
938 5 * kmembuckets[indx].kb_elmpercl;
939 }
940 #endif
941
942 /* Attach all of the statically-linked malloc types. */
943 __link_set_foreach(ksp, malloc_types)
944 malloc_type_attach(*ksp);
945 }
946
947 #ifdef DDB
948 #include <ddb/db_output.h>
949
950 /*
951 * Dump kmem statistics from ddb.
952 *
953 * usage: call dump_kmemstats
954 */
955 void dump_kmemstats(void);
956
957 void
958 dump_kmemstats(void)
959 {
960 #ifdef KMEMSTATS
961 struct malloc_type *ksp;
962
963 for (ksp = kmemstatistics; ksp != NULL; ksp = ksp->ks_next) {
964 if (ksp->ks_memuse == 0)
965 continue;
966 db_printf("%s%.*s %ld\n", ksp->ks_shortdesc,
967 (int)(20 - strlen(ksp->ks_shortdesc)),
968 " ",
969 ksp->ks_memuse);
970 }
971 #else
972 db_printf("Kmem stats are not being collected.\n");
973 #endif /* KMEMSTATS */
974 }
975 #endif /* DDB */
976
977
978 #if 0
979 /*
980 * Diagnostic messages about "Data modified on
981 * freelist" indicate a memory corruption, but
982 * they do not help tracking it down.
983 * This function can be called at various places
984 * to sanity check malloc's freelist and discover
985 * where does the corruption take place.
986 */
987 int
988 freelist_sanitycheck(void) {
989 int i,j;
990 struct kmembuckets *kbp;
991 struct freelist *freep;
992 int rv = 0;
993
994 for (i = MINBUCKET; i <= MINBUCKET + 15; i++) {
995 kbp = &kmembuckets[i];
996 freep = (struct freelist *)kbp->kb_next;
997 j = 0;
998 while(freep) {
999 vm_map_lock(kmem_map);
1000 rv = uvm_map_checkprot(kmem_map, (vaddr_t)freep,
1001 (vaddr_t)freep + sizeof(struct freelist),
1002 VM_PROT_WRITE);
1003 vm_map_unlock(kmem_map);
1004
1005 if ((rv == 0) || (*(int *)freep != WEIRD_ADDR)) {
1006 printf("bucket %i, chunck %d at %p modified\n",
1007 i, j, freep);
1008 return 1;
1009 }
1010 freep = (struct freelist *)freep->next;
1011 j++;
1012 }
1013 }
1014
1015 return 0;
1016 }
1017 #endif
Cache object: 51e01fb46cdc37c7328daac11bc324fe
|