kern_malloc.c revision 1.30
1 /* $NetBSD: kern_malloc.c,v 1.30 1998/02/08 06:15:57 thorpej Exp $ */ 2 3 /* 4 * Copyright 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.3 (Berkeley) 1/4/94 37 */ 38 39 #include <sys/param.h> 40 #include <sys/proc.h> 41 #include <sys/map.h> 42 #include <sys/kernel.h> 43 #include <sys/malloc.h> 44 #include <sys/systm.h> 45 46 #include <vm/vm.h> 47 #include <vm/vm_kern.h> 48 49 #if defined(UVM) 50 #include <uvm/uvm_extern.h> 51 52 static struct vm_map kmem_map_store; 53 vm_map_t kmem_map = NULL; 54 #endif 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 KMEMSTATS 200 register struct kmemstats *ksp = &kmemstats[type]; 201 202 if (((unsigned long)type) > M_LAST) 203 panic("malloc - bogus type"); 204 #endif 205 indx = BUCKETINDX(size); 206 kbp = &bucket[indx]; 207 s = splimp(); 208 #ifdef KMEMSTATS 209 while (ksp->ks_memuse >= ksp->ks_limit) { 210 if (flags & M_NOWAIT) { 211 splx(s); 212 return ((void *) NULL); 213 } 214 if (ksp->ks_limblocks < 65535) 215 ksp->ks_limblocks++; 216 tsleep((caddr_t)ksp, PSWP+2, memname[type], 0); 217 } 218 ksp->ks_size |= 1 << indx; 219 #endif 220 #ifdef DIAGNOSTIC 221 copysize = 1 << indx < MAX_COPY ? 1 << indx : MAX_COPY; 222 #endif 223 if (kbp->kb_next == NULL) { 224 kbp->kb_last = NULL; 225 if (size > MAXALLOCSAVE) 226 allocsize = roundup(size, CLBYTES); 227 else 228 allocsize = 1 << indx; 229 npg = clrnd(btoc(allocsize)); 230 #if defined(UVM) 231 va = (caddr_t) uvm_km_kmemalloc(kmem_map, uvmexp.kmem_object, 232 (vm_size_t)ctob(npg), 233 (flags & M_NOWAIT) ? UVM_KMF_NOWAIT : 0); 234 #else 235 va = (caddr_t) kmem_malloc(kmem_map, (vm_size_t)ctob(npg), 236 !(flags & M_NOWAIT)); 237 #endif 238 if (va == NULL) { 239 /* 240 * Kmem_malloc() can return NULL, even if it can 241 * wait, if there is no map space avaiable, because 242 * it can't fix that problem. Neither can we, 243 * right now. (We should release pages which 244 * are completely free and which are in buckets 245 * with too many free elements.) 246 */ 247 if ((flags & M_NOWAIT) == 0) 248 panic("malloc: out of space in kmem_map"); 249 splx(s); 250 return ((void *) NULL); 251 } 252 #ifdef KMEMSTATS 253 kbp->kb_total += kbp->kb_elmpercl; 254 #endif 255 kup = btokup(va); 256 kup->ku_indx = indx; 257 if (allocsize > MAXALLOCSAVE) { 258 if (npg > 65535) 259 panic("malloc: allocation too large"); 260 kup->ku_pagecnt = npg; 261 #ifdef KMEMSTATS 262 ksp->ks_memuse += allocsize; 263 #endif 264 goto out; 265 } 266 #ifdef KMEMSTATS 267 kup->ku_freecnt = kbp->kb_elmpercl; 268 kbp->kb_totalfree += kbp->kb_elmpercl; 269 #endif 270 /* 271 * Just in case we blocked while allocating memory, 272 * and someone else also allocated memory for this 273 * bucket, don't assume the list is still empty. 274 */ 275 savedlist = kbp->kb_next; 276 kbp->kb_next = cp = va + (npg * NBPG) - allocsize; 277 for (;;) { 278 freep = (struct freelist *)cp; 279 #ifdef DIAGNOSTIC 280 /* 281 * Copy in known text to detect modification 282 * after freeing. 283 */ 284 end = (int32_t *)&cp[copysize]; 285 for (lp = (int32_t *)cp; lp < end; lp++) 286 *lp = WEIRD_ADDR; 287 freep->type = M_FREE; 288 #endif /* DIAGNOSTIC */ 289 if (cp <= va) 290 break; 291 cp -= allocsize; 292 freep->next = cp; 293 } 294 freep->next = savedlist; 295 if (kbp->kb_last == NULL) 296 kbp->kb_last = (caddr_t)freep; 297 } 298 va = kbp->kb_next; 299 kbp->kb_next = ((struct freelist *)va)->next; 300 #ifdef DIAGNOSTIC 301 freep = (struct freelist *)va; 302 savedtype = (unsigned)freep->type < M_LAST ? 303 memname[freep->type] : "???"; 304 #if defined(UVM) 305 if (kbp->kb_next) { 306 int rv; 307 vm_offset_t addr = (vm_offset_t)kbp->kb_next; 308 309 vm_map_lock_read(kmem_map); 310 rv = uvm_map_checkprot(kmem_map, addr, 311 addr + sizeof(struct freelist), 312 VM_PROT_WRITE); 313 vm_map_unlock_read(kmem_map); 314 315 if (!rv) 316 #else 317 if (kbp->kb_next && 318 !kernacc(kbp->kb_next, sizeof(struct freelist), 0)) 319 #endif 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 #if defined(UVM) 331 } 332 #endif 333 } 334 335 /* Fill the fields that we've used with WEIRD_ADDR */ 336 #if BYTE_ORDER == BIG_ENDIAN 337 freep->type = WEIRD_ADDR >> 16; 338 #endif 339 #if BYTE_ORDER == LITTLE_ENDIAN 340 freep->type = (short)WEIRD_ADDR; 341 #endif 342 end = (int32_t *)&freep->next + 343 (sizeof(freep->next) / sizeof(int32_t)); 344 for (lp = (int32_t *)&freep->next; lp < end; lp++) 345 *lp = WEIRD_ADDR; 346 347 /* and check that the data hasn't been modified. */ 348 end = (int32_t *)&va[copysize]; 349 for (lp = (int32_t *)va; lp < end; lp++) { 350 if (*lp == WEIRD_ADDR) 351 continue; 352 printf("%s %ld of object %p size %ld %s %s (0x%x != 0x%x)\n", 353 "Data modified on freelist: word", 354 (long)(lp - (int32_t *)va), va, size, "previous type", 355 savedtype, *lp, WEIRD_ADDR); 356 #ifdef MALLOCLOG 357 hitmlog(va); 358 #endif 359 break; 360 } 361 362 freep->spare0 = 0; 363 #endif /* DIAGNOSTIC */ 364 #ifdef KMEMSTATS 365 kup = btokup(va); 366 if (kup->ku_indx != indx) 367 panic("malloc: wrong bucket"); 368 if (kup->ku_freecnt == 0) 369 panic("malloc: lost data"); 370 kup->ku_freecnt--; 371 kbp->kb_totalfree--; 372 ksp->ks_memuse += 1 << indx; 373 out: 374 kbp->kb_calls++; 375 ksp->ks_inuse++; 376 ksp->ks_calls++; 377 if (ksp->ks_memuse > ksp->ks_maxused) 378 ksp->ks_maxused = ksp->ks_memuse; 379 #else 380 out: 381 #endif 382 #ifdef MALLOCLOG 383 domlog(va, size, type, 1, file, line); 384 #endif 385 splx(s); 386 return ((void *) va); 387 } 388 389 /* 390 * Free a block of memory allocated by malloc. 391 */ 392 #ifdef MALLOCLOG 393 void 394 _free(addr, type, file, line) 395 void *addr; 396 int type; 397 const char *file; 398 long line; 399 #else 400 void 401 free(addr, type) 402 void *addr; 403 int type; 404 #endif /* MALLOCLOG */ 405 { 406 register struct kmembuckets *kbp; 407 register struct kmemusage *kup; 408 register struct freelist *freep; 409 long size; 410 int s; 411 #ifdef DIAGNOSTIC 412 caddr_t cp; 413 int32_t *end, *lp; 414 long alloc, copysize; 415 #endif 416 #ifdef KMEMSTATS 417 register struct kmemstats *ksp = &kmemstats[type]; 418 #endif 419 420 kup = btokup(addr); 421 size = 1 << kup->ku_indx; 422 kbp = &bucket[kup->ku_indx]; 423 s = splimp(); 424 #ifdef MALLOCLOG 425 domlog(addr, 0, type, 2, file, line); 426 #endif 427 #ifdef DIAGNOSTIC 428 /* 429 * Check for returns of data that do not point to the 430 * beginning of the allocation. 431 */ 432 if (size > NBPG * CLSIZE) 433 alloc = addrmask[BUCKETINDX(NBPG * CLSIZE)]; 434 else 435 alloc = addrmask[kup->ku_indx]; 436 if (((u_long)addr & alloc) != 0) 437 panic("free: unaligned addr %p, size %ld, type %s, mask %ld\n", 438 addr, size, memname[type], alloc); 439 #endif /* DIAGNOSTIC */ 440 if (size > MAXALLOCSAVE) { 441 #if defined(UVM) 442 uvm_km_free(kmem_map, (vm_offset_t)addr, ctob(kup->ku_pagecnt)); 443 #else 444 kmem_free(kmem_map, (vm_offset_t)addr, ctob(kup->ku_pagecnt)); 445 #endif 446 #ifdef KMEMSTATS 447 size = kup->ku_pagecnt << PGSHIFT; 448 ksp->ks_memuse -= size; 449 kup->ku_indx = 0; 450 kup->ku_pagecnt = 0; 451 if (ksp->ks_memuse + size >= ksp->ks_limit && 452 ksp->ks_memuse < ksp->ks_limit) 453 wakeup((caddr_t)ksp); 454 ksp->ks_inuse--; 455 kbp->kb_total -= 1; 456 #endif 457 splx(s); 458 return; 459 } 460 freep = (struct freelist *)addr; 461 #ifdef DIAGNOSTIC 462 /* 463 * Check for multiple frees. Use a quick check to see if 464 * it looks free before laboriously searching the freelist. 465 */ 466 if (freep->spare0 == WEIRD_ADDR) { 467 for (cp = kbp->kb_next; cp; 468 cp = ((struct freelist *)cp)->next) { 469 if (addr != cp) 470 continue; 471 printf("multiply freed item %p\n", addr); 472 #ifdef MALLOCLOG 473 hitmlog(addr); 474 #endif 475 panic("free: duplicated free"); 476 } 477 } 478 /* 479 * Copy in known text to detect modification after freeing 480 * and to make it look free. Also, save the type being freed 481 * so we can list likely culprit if modification is detected 482 * when the object is reallocated. 483 */ 484 copysize = size < MAX_COPY ? size : MAX_COPY; 485 end = (int32_t *)&((caddr_t)addr)[copysize]; 486 for (lp = (int32_t *)addr; lp < end; lp++) 487 *lp = WEIRD_ADDR; 488 freep->type = type; 489 #endif /* DIAGNOSTIC */ 490 #ifdef KMEMSTATS 491 kup->ku_freecnt++; 492 if (kup->ku_freecnt >= kbp->kb_elmpercl) 493 if (kup->ku_freecnt > kbp->kb_elmpercl) 494 panic("free: multiple frees"); 495 else if (kbp->kb_totalfree > kbp->kb_highwat) 496 kbp->kb_couldfree++; 497 kbp->kb_totalfree++; 498 ksp->ks_memuse -= size; 499 if (ksp->ks_memuse + size >= ksp->ks_limit && 500 ksp->ks_memuse < ksp->ks_limit) 501 wakeup((caddr_t)ksp); 502 ksp->ks_inuse--; 503 #endif 504 if (kbp->kb_next == NULL) 505 kbp->kb_next = addr; 506 else 507 ((struct freelist *)kbp->kb_last)->next = addr; 508 freep->next = NULL; 509 kbp->kb_last = addr; 510 splx(s); 511 } 512 513 /* 514 * Change the size of a block of memory. 515 */ 516 void * 517 realloc(curaddr, newsize, type, flags) 518 void *curaddr; 519 unsigned long newsize; 520 int type, flags; 521 { 522 register struct kmemusage *kup; 523 long cursize; 524 void *newaddr; 525 #ifdef DIAGNOSTIC 526 long alloc; 527 #endif 528 529 /* 530 * Realloc() with a NULL pointer is the same as malloc(). 531 */ 532 if (curaddr == NULL) 533 return (malloc(newsize, type, flags)); 534 535 /* 536 * Realloc() with zero size is the same as free(). 537 */ 538 if (newsize == 0) { 539 free(curaddr, type); 540 return (NULL); 541 } 542 543 /* 544 * Find out how large the old allocation was (and do some 545 * sanity checking). 546 */ 547 kup = btokup(curaddr); 548 cursize = 1 << kup->ku_indx; 549 550 #ifdef DIAGNOSTIC 551 /* 552 * Check for returns of data that do not point to the 553 * beginning of the allocation. 554 */ 555 if (cursize > NBPG * CLSIZE) 556 alloc = addrmask[BUCKETINDX(NBPG * CLSIZE)]; 557 else 558 alloc = addrmask[kup->ku_indx]; 559 if (((u_long)curaddr & alloc) != 0) 560 panic("realloc: unaligned addr %p, size %ld, type %s, mask %ld\n", 561 curaddr, cursize, memname[type], alloc); 562 #endif /* DIAGNOSTIC */ 563 564 if (cursize > MAXALLOCSAVE) 565 cursize = ctob(kup->ku_pagecnt); 566 567 /* 568 * If we already actually have as much as they want, we're done. 569 */ 570 if (newsize <= cursize) 571 return (curaddr); 572 573 /* 574 * Can't satisfy the allocation with the existing block. 575 * Allocate a new one and copy the data. 576 */ 577 newaddr = malloc(newsize, type, flags); 578 if (newaddr == NULL) { 579 /* 580 * Malloc() failed, because flags included M_NOWAIT. 581 * Return NULL to indicate that failure. The old 582 * pointer is still valid. 583 */ 584 return NULL; 585 } 586 bcopy(curaddr, newaddr, cursize); 587 588 /* 589 * We were successful: free the old allocation and return 590 * the new one. 591 */ 592 free(curaddr, type); 593 return (newaddr); 594 } 595 596 /* 597 * Initialize the kernel memory allocator 598 */ 599 void 600 kmeminit() 601 { 602 #ifdef KMEMSTATS 603 register long indx; 604 #endif 605 int npg; 606 607 #if ((MAXALLOCSAVE & (MAXALLOCSAVE - 1)) != 0) 608 ERROR!_kmeminit:_MAXALLOCSAVE_not_power_of_2 609 #endif 610 #if (MAXALLOCSAVE > MINALLOCSIZE * 32768) 611 ERROR!_kmeminit:_MAXALLOCSAVE_too_big 612 #endif 613 #if (MAXALLOCSAVE < CLBYTES) 614 ERROR!_kmeminit:_MAXALLOCSAVE_too_small 615 #endif 616 617 if (sizeof(struct freelist) > (1 << MINBUCKET)) 618 panic("minbucket too small/struct freelist too big"); 619 620 npg = VM_KMEM_SIZE/ NBPG; 621 #if defined(UVM) 622 kmemusage = (struct kmemusage *) uvm_km_zalloc(kernel_map, 623 (vm_size_t)(npg * sizeof(struct kmemusage))); 624 kmem_map = uvm_km_suballoc(kernel_map, (vm_offset_t *)&kmembase, 625 (vm_offset_t *)&kmemlimit, (vm_size_t)(npg * NBPG), 626 FALSE, FALSE, &kmem_map_store); 627 #else 628 kmemusage = (struct kmemusage *) kmem_alloc(kernel_map, 629 (vm_size_t)(npg * sizeof(struct kmemusage))); 630 kmem_map = kmem_suballoc(kernel_map, (vm_offset_t *)&kmembase, 631 (vm_offset_t *)&kmemlimit, (vm_size_t)(npg * NBPG), FALSE); 632 #endif 633 #ifdef KMEMSTATS 634 for (indx = 0; indx < MINBUCKET + 16; indx++) { 635 if (1 << indx >= CLBYTES) 636 bucket[indx].kb_elmpercl = 1; 637 else 638 bucket[indx].kb_elmpercl = CLBYTES / (1 << indx); 639 bucket[indx].kb_highwat = 5 * bucket[indx].kb_elmpercl; 640 } 641 for (indx = 0; indx < M_LAST; indx++) 642 kmemstats[indx].ks_limit = npg * NBPG * 6 / 10; 643 #endif 644 } 645
Indexes created Sat Sep 20 22:09:52 GMT 2025