kern_malloc.c revision 1.42
1 /* $NetBSD: kern_malloc.c,v 1.42 1999/05/26 19:16:36 thorpej Exp $ */ 2 3 /* 4 * Copyright (c) 1996 Christopher G. Demetriou. All rights reserved. 5 * Copyright (c) 1987, 1991, 1993 6 * The Regents of the University of California. All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 3. All advertising materials mentioning features or use of this software 17 * must display the following acknowledgement: 18 * This product includes software developed by the University of 19 * California, Berkeley and its contributors. 20 * 4. Neither the name of the University nor the names of its contributors 21 * may be used to endorse or promote products derived from this software 22 * without specific prior written permission. 23 * 24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 34 * SUCH DAMAGE. 35 * 36 * @(#)kern_malloc.c 8.4 (Berkeley) 5/20/95 37 */ 38 39 #include "opt_lockdebug.h" 40 41 #include <sys/param.h> 42 #include <sys/proc.h> 43 #include <sys/map.h> 44 #include <sys/kernel.h> 45 #include <sys/malloc.h> 46 #include <sys/systm.h> 47 48 #include <vm/vm.h> 49 #include <vm/vm_kern.h> 50 51 #include <uvm/uvm_extern.h> 52 53 static struct vm_map kmem_map_store; 54 vm_map_t kmem_map = NULL; 55 56 #include "opt_kmemstats.h" 57 #include "opt_malloclog.h" 58 59 struct kmembuckets bucket[MINBUCKET + 16]; 60 struct kmemstats kmemstats[M_LAST]; 61 struct kmemusage *kmemusage; 62 char *kmembase, *kmemlimit; 63 const char *memname[] = INITKMEMNAMES; 64 65 #ifdef MALLOCLOG 66 #ifndef MALLOCLOGSIZE 67 #define MALLOCLOGSIZE 100000 68 #endif 69 70 struct malloclog { 71 void *addr; 72 long size; 73 int type; 74 int action; 75 const char *file; 76 long line; 77 } malloclog[MALLOCLOGSIZE]; 78 79 long malloclogptr; 80 81 static void domlog __P((void *a, long size, int type, int action, 82 const char *file, long line)); 83 static void hitmlog __P((void *a)); 84 85 static void 86 domlog(a, size, type, action, file, line) 87 void *a; 88 long size; 89 int type; 90 int action; 91 const char *file; 92 long line; 93 { 94 95 malloclog[malloclogptr].addr = a; 96 malloclog[malloclogptr].size = size; 97 malloclog[malloclogptr].type = type; 98 malloclog[malloclogptr].action = action; 99 malloclog[malloclogptr].file = file; 100 malloclog[malloclogptr].line = line; 101 malloclogptr++; 102 if (malloclogptr >= MALLOCLOGSIZE) 103 malloclogptr = 0; 104 } 105 106 static void 107 hitmlog(a) 108 void *a; 109 { 110 struct malloclog *lp; 111 long l; 112 113 #define PRT \ 114 if (malloclog[l].addr == a && malloclog[l].action) { \ 115 lp = &malloclog[l]; \ 116 printf("malloc log entry %ld:\n", l); \ 117 printf("\taddr = %p\n", lp->addr); \ 118 printf("\tsize = %ld\n", lp->size); \ 119 printf("\ttype = %s\n", memname[lp->type]); \ 120 printf("\taction = %s\n", lp->action == 1 ? "alloc" : "free"); \ 121 printf("\tfile = %s\n", lp->file); \ 122 printf("\tline = %ld\n", lp->line); \ 123 } 124 125 for (l = malloclogptr; l < MALLOCLOGSIZE; l++) 126 PRT 127 128 for (l = 0; l < malloclogptr; l++) 129 PRT 130 } 131 #endif /* MALLOCLOG */ 132 133 #ifdef DIAGNOSTIC 134 /* 135 * This structure provides a set of masks to catch unaligned frees. 136 */ 137 long addrmask[] = { 0, 138 0x00000001, 0x00000003, 0x00000007, 0x0000000f, 139 0x0000001f, 0x0000003f, 0x0000007f, 0x000000ff, 140 0x000001ff, 0x000003ff, 0x000007ff, 0x00000fff, 141 0x00001fff, 0x00003fff, 0x00007fff, 0x0000ffff, 142 }; 143 144 /* 145 * The WEIRD_ADDR is used as known text to copy into free objects so 146 * that modifications after frees can be detected. 147 */ 148 #define WEIRD_ADDR ((unsigned) 0xdeadbeef) 149 #define MAX_COPY 32 150 151 /* 152 * Normally the freelist structure is used only to hold the list pointer 153 * for free objects. However, when running with diagnostics, the first 154 * 8 bytes of the structure is unused except for diagnostic information, 155 * and the free list pointer is at offst 8 in the structure. Since the 156 * first 8 bytes is the portion of the structure most often modified, this 157 * helps to detect memory reuse problems and avoid free list corruption. 158 */ 159 struct freelist { 160 int32_t spare0; 161 int16_t type; 162 int16_t spare1; 163 caddr_t next; 164 }; 165 #else /* !DIAGNOSTIC */ 166 struct freelist { 167 caddr_t next; 168 }; 169 #endif /* DIAGNOSTIC */ 170 171 /* 172 * Allocate a block of memory 173 */ 174 #ifdef MALLOCLOG 175 void * 176 _malloc(size, type, flags, file, line) 177 unsigned long size; 178 int type, flags; 179 const char *file; 180 long line; 181 #else 182 void * 183 malloc(size, type, flags) 184 unsigned long size; 185 int type, flags; 186 #endif /* MALLOCLOG */ 187 { 188 register struct kmembuckets *kbp; 189 register struct kmemusage *kup; 190 register struct freelist *freep; 191 long indx, npg, allocsize; 192 int s; 193 caddr_t va, cp, savedlist; 194 #ifdef DIAGNOSTIC 195 int32_t *end, *lp; 196 int copysize; 197 const char *savedtype; 198 #endif 199 #ifdef LOCKDEBUG 200 extern int simplelockrecurse; 201 #endif 202 #ifdef KMEMSTATS 203 register struct kmemstats *ksp = &kmemstats[type]; 204 205 if (((unsigned long)type) > M_LAST) 206 panic("malloc - bogus type"); 207 #endif 208 indx = BUCKETINDX(size); 209 kbp = &bucket[indx]; 210 s = splimp(); 211 #ifdef KMEMSTATS 212 while (ksp->ks_memuse >= ksp->ks_limit) { 213 if (flags & M_NOWAIT) { 214 splx(s); 215 return ((void *) NULL); 216 } 217 if (ksp->ks_limblocks < 65535) 218 ksp->ks_limblocks++; 219 tsleep((caddr_t)ksp, PSWP+2, memname[type], 0); 220 } 221 ksp->ks_size |= 1 << indx; 222 #endif 223 #ifdef DIAGNOSTIC 224 copysize = 1 << indx < MAX_COPY ? 1 << indx : MAX_COPY; 225 #endif 226 #ifdef LOCKDEBUG 227 if (flags & M_NOWAIT) 228 simplelockrecurse++; 229 #endif 230 if (kbp->kb_next == NULL) { 231 kbp->kb_last = NULL; 232 if (size > MAXALLOCSAVE) 233 allocsize = roundup(size, CLBYTES); 234 else 235 allocsize = 1 << indx; 236 npg = clrnd(btoc(allocsize)); 237 va = (caddr_t) uvm_km_kmemalloc(kmem_map, uvmexp.kmem_object, 238 (vsize_t)ctob(npg), 239 (flags & M_NOWAIT) ? UVM_KMF_NOWAIT : 0); 240 if (va == NULL) { 241 /* 242 * Kmem_malloc() can return NULL, even if it can 243 * wait, if there is no map space avaiable, because 244 * it can't fix that problem. Neither can we, 245 * right now. (We should release pages which 246 * are completely free and which are in buckets 247 * with too many free elements.) 248 */ 249 if ((flags & M_NOWAIT) == 0) 250 panic("malloc: out of space in kmem_map"); 251 #ifdef LOCKDEBUG 252 simplelockrecurse--; 253 #endif 254 splx(s); 255 return ((void *) NULL); 256 } 257 #ifdef KMEMSTATS 258 kbp->kb_total += kbp->kb_elmpercl; 259 #endif 260 kup = btokup(va); 261 kup->ku_indx = indx; 262 if (allocsize > MAXALLOCSAVE) { 263 if (npg > 65535) 264 panic("malloc: allocation too large"); 265 kup->ku_pagecnt = npg; 266 #ifdef KMEMSTATS 267 ksp->ks_memuse += allocsize; 268 #endif 269 goto out; 270 } 271 #ifdef KMEMSTATS 272 kup->ku_freecnt = kbp->kb_elmpercl; 273 kbp->kb_totalfree += kbp->kb_elmpercl; 274 #endif 275 /* 276 * Just in case we blocked while allocating memory, 277 * and someone else also allocated memory for this 278 * bucket, don't assume the list is still empty. 279 */ 280 savedlist = kbp->kb_next; 281 kbp->kb_next = cp = va + (npg * NBPG) - allocsize; 282 for (;;) { 283 freep = (struct freelist *)cp; 284 #ifdef DIAGNOSTIC 285 /* 286 * Copy in known text to detect modification 287 * after freeing. 288 */ 289 end = (int32_t *)&cp[copysize]; 290 for (lp = (int32_t *)cp; lp < end; lp++) 291 *lp = WEIRD_ADDR; 292 freep->type = M_FREE; 293 #endif /* DIAGNOSTIC */ 294 if (cp <= va) 295 break; 296 cp -= allocsize; 297 freep->next = cp; 298 } 299 freep->next = savedlist; 300 if (kbp->kb_last == NULL) 301 kbp->kb_last = (caddr_t)freep; 302 } 303 va = kbp->kb_next; 304 kbp->kb_next = ((struct freelist *)va)->next; 305 #ifdef DIAGNOSTIC 306 freep = (struct freelist *)va; 307 savedtype = (unsigned)freep->type < M_LAST ? 308 memname[freep->type] : "???"; 309 if (kbp->kb_next) { 310 int rv; 311 vaddr_t addr = (vaddr_t)kbp->kb_next; 312 313 vm_map_lock_read(kmem_map); 314 rv = uvm_map_checkprot(kmem_map, addr, 315 addr + sizeof(struct freelist), 316 VM_PROT_WRITE); 317 vm_map_unlock_read(kmem_map); 318 319 if (!rv) 320 { 321 printf( 322 "%s %ld of object %p size %ld %s %s (invalid addr %p)\n", 323 "Data modified on freelist: word", 324 (long)((int32_t *)&kbp->kb_next - (int32_t *)kbp), 325 va, size, "previous type", savedtype, kbp->kb_next); 326 #ifdef MALLOCLOG 327 hitmlog(va); 328 #endif 329 kbp->kb_next = NULL; 330 } 331 } 332 333 /* Fill the fields that we've used with WEIRD_ADDR */ 334 #if BYTE_ORDER == BIG_ENDIAN 335 freep->type = WEIRD_ADDR >> 16; 336 #endif 337 #if BYTE_ORDER == LITTLE_ENDIAN 338 freep->type = (short)WEIRD_ADDR; 339 #endif 340 end = (int32_t *)&freep->next + 341 (sizeof(freep->next) / sizeof(int32_t)); 342 for (lp = (int32_t *)&freep->next; lp < end; lp++) 343 *lp = WEIRD_ADDR; 344 345 /* and check that the data hasn't been modified. */ 346 end = (int32_t *)&va[copysize]; 347 for (lp = (int32_t *)va; lp < end; lp++) { 348 if (*lp == WEIRD_ADDR) 349 continue; 350 printf("%s %ld of object %p size %ld %s %s (0x%x != 0x%x)\n", 351 "Data modified on freelist: word", 352 (long)(lp - (int32_t *)va), va, size, "previous type", 353 savedtype, *lp, WEIRD_ADDR); 354 #ifdef MALLOCLOG 355 hitmlog(va); 356 #endif 357 break; 358 } 359 360 freep->spare0 = 0; 361 #endif /* DIAGNOSTIC */ 362 #ifdef KMEMSTATS 363 kup = btokup(va); 364 if (kup->ku_indx != indx) 365 panic("malloc: wrong bucket"); 366 if (kup->ku_freecnt == 0) 367 panic("malloc: lost data"); 368 kup->ku_freecnt--; 369 kbp->kb_totalfree--; 370 ksp->ks_memuse += 1 << indx; 371 out: 372 kbp->kb_calls++; 373 ksp->ks_inuse++; 374 ksp->ks_calls++; 375 if (ksp->ks_memuse > ksp->ks_maxused) 376 ksp->ks_maxused = ksp->ks_memuse; 377 #else 378 out: 379 #endif 380 #ifdef MALLOCLOG 381 domlog(va, size, type, 1, file, line); 382 #endif 383 splx(s); 384 #ifdef LOCKDEBUG 385 if (flags & M_NOWAIT) 386 simplelockrecurse--; 387 #endif 388 return ((void *) va); 389 } 390 391 /* 392 * Free a block of memory allocated by malloc. 393 */ 394 #ifdef MALLOCLOG 395 void 396 _free(addr, type, file, line) 397 void *addr; 398 int type; 399 const char *file; 400 long line; 401 #else 402 void 403 free(addr, type) 404 void *addr; 405 int type; 406 #endif /* MALLOCLOG */ 407 { 408 register struct kmembuckets *kbp; 409 register struct kmemusage *kup; 410 register struct freelist *freep; 411 long size; 412 int s; 413 #ifdef DIAGNOSTIC 414 caddr_t cp; 415 int32_t *end, *lp; 416 long alloc, copysize; 417 #endif 418 #ifdef KMEMSTATS 419 register struct kmemstats *ksp = &kmemstats[type]; 420 #endif 421 422 kup = btokup(addr); 423 size = 1 << kup->ku_indx; 424 kbp = &bucket[kup->ku_indx]; 425 s = splimp(); 426 #ifdef MALLOCLOG 427 domlog(addr, 0, type, 2, file, line); 428 #endif 429 #ifdef DIAGNOSTIC 430 /* 431 * Check for returns of data that do not point to the 432 * beginning of the allocation. 433 */ 434 if (size > NBPG * CLSIZE) 435 alloc = addrmask[BUCKETINDX(NBPG * CLSIZE)]; 436 else 437 alloc = addrmask[kup->ku_indx]; 438 if (((u_long)addr & alloc) != 0) 439 panic("free: unaligned addr %p, size %ld, type %s, mask %ld\n", 440 addr, size, memname[type], alloc); 441 #endif /* DIAGNOSTIC */ 442 if (size > MAXALLOCSAVE) { 443 uvm_km_free(kmem_map, (vaddr_t)addr, ctob(kup->ku_pagecnt)); 444 #ifdef KMEMSTATS 445 size = kup->ku_pagecnt << PGSHIFT; 446 ksp->ks_memuse -= size; 447 kup->ku_indx = 0; 448 kup->ku_pagecnt = 0; 449 if (ksp->ks_memuse + size >= ksp->ks_limit && 450 ksp->ks_memuse < ksp->ks_limit) 451 wakeup((caddr_t)ksp); 452 ksp->ks_inuse--; 453 kbp->kb_total -= 1; 454 #endif 455 splx(s); 456 return; 457 } 458 freep = (struct freelist *)addr; 459 #ifdef DIAGNOSTIC 460 /* 461 * Check for multiple frees. Use a quick check to see if 462 * it looks free before laboriously searching the freelist. 463 */ 464 if (freep->spare0 == WEIRD_ADDR) { 465 for (cp = kbp->kb_next; cp; 466 cp = ((struct freelist *)cp)->next) { 467 if (addr != cp) 468 continue; 469 printf("multiply freed item %p\n", addr); 470 #ifdef MALLOCLOG 471 hitmlog(addr); 472 #endif 473 panic("free: duplicated free"); 474 } 475 } 476 #ifdef LOCKDEBUG 477 /* 478 * Check if we're freeing a locked simple lock. 479 */ 480 simple_lock_freecheck(addr, (char *)addr + size); 481 #endif 482 /* 483 * Copy in known text to detect modification after freeing 484 * and to make it look free. Also, save the type being freed 485 * so we can list likely culprit if modification is detected 486 * when the object is reallocated. 487 */ 488 copysize = size < MAX_COPY ? size : MAX_COPY; 489 end = (int32_t *)&((caddr_t)addr)[copysize]; 490 for (lp = (int32_t *)addr; lp < end; lp++) 491 *lp = WEIRD_ADDR; 492 freep->type = type; 493 #endif /* DIAGNOSTIC */ 494 #ifdef KMEMSTATS 495 kup->ku_freecnt++; 496 if (kup->ku_freecnt >= kbp->kb_elmpercl) { 497 if (kup->ku_freecnt > kbp->kb_elmpercl) 498 panic("free: multiple frees"); 499 else if (kbp->kb_totalfree > kbp->kb_highwat) 500 kbp->kb_couldfree++; 501 } 502 kbp->kb_totalfree++; 503 ksp->ks_memuse -= size; 504 if (ksp->ks_memuse + size >= ksp->ks_limit && 505 ksp->ks_memuse < ksp->ks_limit) 506 wakeup((caddr_t)ksp); 507 ksp->ks_inuse--; 508 #endif 509 if (kbp->kb_next == NULL) 510 kbp->kb_next = addr; 511 else 512 ((struct freelist *)kbp->kb_last)->next = addr; 513 freep->next = NULL; 514 kbp->kb_last = addr; 515 splx(s); 516 } 517 518 /* 519 * Change the size of a block of memory. 520 */ 521 void * 522 realloc(curaddr, newsize, type, flags) 523 void *curaddr; 524 unsigned long newsize; 525 int type, flags; 526 { 527 register struct kmemusage *kup; 528 long cursize; 529 void *newaddr; 530 #ifdef DIAGNOSTIC 531 long alloc; 532 #endif 533 534 /* 535 * Realloc() with a NULL pointer is the same as malloc(). 536 */ 537 if (curaddr == NULL) 538 return (malloc(newsize, type, flags)); 539 540 /* 541 * Realloc() with zero size is the same as free(). 542 */ 543 if (newsize == 0) { 544 free(curaddr, type); 545 return (NULL); 546 } 547 548 /* 549 * Find out how large the old allocation was (and do some 550 * sanity checking). 551 */ 552 kup = btokup(curaddr); 553 cursize = 1 << kup->ku_indx; 554 555 #ifdef DIAGNOSTIC 556 /* 557 * Check for returns of data that do not point to the 558 * beginning of the allocation. 559 */ 560 if (cursize > NBPG * CLSIZE) 561 alloc = addrmask[BUCKETINDX(NBPG * CLSIZE)]; 562 else 563 alloc = addrmask[kup->ku_indx]; 564 if (((u_long)curaddr & alloc) != 0) 565 panic("realloc: unaligned addr %p, size %ld, type %s, mask %ld\n", 566 curaddr, cursize, memname[type], alloc); 567 #endif /* DIAGNOSTIC */ 568 569 if (cursize > MAXALLOCSAVE) 570 cursize = ctob(kup->ku_pagecnt); 571 572 /* 573 * If we already actually have as much as they want, we're done. 574 */ 575 if (newsize <= cursize) 576 return (curaddr); 577 578 /* 579 * Can't satisfy the allocation with the existing block. 580 * Allocate a new one and copy the data. 581 */ 582 newaddr = malloc(newsize, type, flags); 583 if (newaddr == NULL) { 584 /* 585 * Malloc() failed, because flags included M_NOWAIT. 586 * Return NULL to indicate that failure. The old 587 * pointer is still valid. 588 */ 589 return NULL; 590 } 591 memcpy(newaddr, curaddr, cursize); 592 593 /* 594 * We were successful: free the old allocation and return 595 * the new one. 596 */ 597 free(curaddr, type); 598 return (newaddr); 599 } 600 601 /* 602 * Initialize the kernel memory allocator 603 */ 604 void 605 kmeminit() 606 { 607 #ifdef KMEMSTATS 608 register long indx; 609 #endif 610 int npg; 611 612 #if ((MAXALLOCSAVE & (MAXALLOCSAVE - 1)) != 0) 613 ERROR!_kmeminit:_MAXALLOCSAVE_not_power_of_2 614 #endif 615 #if (MAXALLOCSAVE > MINALLOCSIZE * 32768) 616 ERROR!_kmeminit:_MAXALLOCSAVE_too_big 617 #endif 618 #if (MAXALLOCSAVE < CLBYTES) 619 ERROR!_kmeminit:_MAXALLOCSAVE_too_small 620 #endif 621 622 if (sizeof(struct freelist) > (1 << MINBUCKET)) 623 panic("minbucket too small/struct freelist too big"); 624 625 npg = VM_KMEM_SIZE/ NBPG; 626 kmemusage = (struct kmemusage *) uvm_km_zalloc(kernel_map, 627 (vsize_t)(npg * sizeof(struct kmemusage))); 628 kmem_map = uvm_km_suballoc(kernel_map, (vaddr_t *)&kmembase, 629 (vaddr_t *)&kmemlimit, (vsize_t)(npg * NBPG), 630 VM_MAP_INTRSAFE, FALSE, &kmem_map_store); 631 #ifdef KMEMSTATS 632 for (indx = 0; indx < MINBUCKET + 16; indx++) { 633 if (1 << indx >= CLBYTES) 634 bucket[indx].kb_elmpercl = 1; 635 else 636 bucket[indx].kb_elmpercl = CLBYTES / (1 << indx); 637 bucket[indx].kb_highwat = 5 * bucket[indx].kb_elmpercl; 638 } 639 for (indx = 0; indx < M_LAST; indx++) 640 kmemstats[indx].ks_limit = npg * NBPG * 6 / 10; 641 #endif 642 } 643 644 #ifdef DDB 645 #include <ddb/db_output.h> 646 647 /* 648 * Dump kmem statistics from ddb. 649 * 650 * usage: call dump_kmemstats 651 */ 652 void dump_kmemstats __P((void)); 653 654 void 655 dump_kmemstats() 656 { 657 #ifdef KMEMSTATS 658 const char *name; 659 int i; 660 661 for (i = 0; i < M_LAST; i++) { 662 name = memname[i] ? memname[i] : ""; 663 664 db_printf("%2d %s%.*s %ld\n", i, name, 665 (int)(20 - strlen(name)), " ", 666 kmemstats[i].ks_memuse); 667 } 668 #else 669 db_printf("Kmem stats are not being collected.\n"); 670 #endif /* KMEMSTATS */ 671 } 672 #endif /* DDB */ 673
Indexes created Sat Sep 20 22:09:52 GMT 2025