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