sys/kern/kern_malloc.c

   1 /*      $NetBSD: kern_malloc.c,v 1.126 2009/01/07 21:06:31 pooka 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.126 2009/01/07 21:06:31 pooka 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 static void
 219 hitmlog(void *a)
 220 {
 221         struct malloclog *lp;
 222         long l;
 223
 224 #define PRT do { \
 225         lp = &malloclog[l]; \
 226         if (lp->addr == a && lp->action) { \
 227                 printf("malloc log entry %ld:\n", l); \
 228                 printf("\taddr = %p\n", lp->addr); \
 229                 printf("\tsize = %ld\n", lp->size); \
 230                 printf("\ttype = %s\n", lp->type->ks_shortdesc); \
 231                 printf("\taction = %s\n", lp->action == 1 ? "alloc" : "free"); \
 232                 printf("\tfile = %s\n", lp->file); \
 233                 printf("\tline = %ld\n", lp->line); \
 234         } \
 235 } while (/* CONSTCOND */0)
 236
 237 /*
 238  * Print fuzzy matched "neighbour" - look for the memory block that has
 239  * been allocated below the address we are interested in.  We look for a
 240  * base address + size that is within malloclog_fuzz of our target
 241  * address. If the base address and target address are the same then it is
 242  * likely we have found a free (size is 0 in this case) so we won't report
 243  * those, they will get reported by PRT anyway.
 244  */
 245 #define NPRT do { \
 246         __uintptr_t fuzz_mask = ~(malloclog_fuzz); \
 247         lp = &malloclog[l]; \
 248         if ((__uintptr_t)lp->addr != (__uintptr_t)a && \
 249             (((__uintptr_t)lp->addr + lp->size + malloclog_fuzz) & fuzz_mask) \
 250             == ((__uintptr_t)a & fuzz_mask) && lp->action) {            \
 251                 printf("neighbour malloc log entry %ld:\n", l); \
 252                 printf("\taddr = %p\n", lp->addr); \
 253                 printf("\tsize = %ld\n", lp->size); \
 254                 printf("\ttype = %s\n", lp->type->ks_shortdesc); \
 255                 printf("\taction = %s\n", lp->action == 1 ? "alloc" : "free"); \
 256                 printf("\tfile = %s\n", lp->file); \
 257                 printf("\tline = %ld\n", lp->line); \
 258         } \
 259 } while (/* CONSTCOND */0)
 260
 261         for (l = malloclogptr; l < MALLOCLOGSIZE; l++) {
 262                 PRT;
 263                 NPRT;
 264         }
 265
 266
 267         for (l = 0; l < malloclogptr; l++) {
 268                 PRT;
 269                 NPRT;
 270         }
 271
 272 #undef PRT
 273 }
 274 #endif /* MALLOCLOG */
 275
 276 #ifdef DIAGNOSTIC
 277 /*
 278  * This structure provides a set of masks to catch unaligned frees.
 279  */
 280 const long addrmask[] = { 0,
 281         0x00000001, 0x00000003, 0x00000007, 0x0000000f,
 282         0x0000001f, 0x0000003f, 0x0000007f, 0x000000ff,
 283         0x000001ff, 0x000003ff, 0x000007ff, 0x00000fff,
 284         0x00001fff, 0x00003fff, 0x00007fff, 0x0000ffff,
 285 };
 286
 287 /*
 288  * The WEIRD_ADDR is used as known text to copy into free objects so
 289  * that modifications after frees can be detected.
 290  */
 291 #define WEIRD_ADDR      ((uint32_t) 0xdeadbeef)
 292 #ifdef DEBUG
 293 #define MAX_COPY        PAGE_SIZE
 294 #else
 295 #define MAX_COPY        32
 296 #endif
 297
 298 /*
 299  * Normally the freelist structure is used only to hold the list pointer
 300  * for free objects.  However, when running with diagnostics, the first
 301  * 8/16 bytes of the structure is unused except for diagnostic information,
 302  * and the free list pointer is at offset 8/16 in the structure.  Since the
 303  * first 8 bytes is the portion of the structure most often modified, this
 304  * helps to detect memory reuse problems and avoid free list corruption.
 305  */
 306 struct freelist {
 307         uint32_t spare0;
 308 #ifdef _LP64
 309         uint32_t spare1;                /* explicit padding */
 310 #endif
 311         struct malloc_type *type;
 312         void *  next;
 313 };
 314 #else /* !DIAGNOSTIC */
 315 struct freelist {
 316         void *  next;
 317 };
 318 #endif /* DIAGNOSTIC */
 319
 320 kmutex_t malloc_lock;
 321
 322 /*
 323  * Allocate a block of memory
 324  */
 325 #ifdef MALLOCLOG
 326 void *
 327 _kern_malloc(unsigned long size, struct malloc_type *ksp, int flags,
 328     const char *file, long line)
 329 #else
 330 void *
 331 kern_malloc(unsigned long size, struct malloc_type *ksp, int flags)
 332 #endif /* MALLOCLOG */
 333 {
 334         struct kmembuckets *kbp;
 335         struct kmemusage *kup;
 336         struct freelist *freep;
 337         long indx, npg, allocsize;
 338         char *va, *cp, *savedlist;
 339 #ifdef DIAGNOSTIC
 340         uint32_t *end, *lp;
 341         int copysize;
 342 #endif
 343
 344 #ifdef LOCKDEBUG
 345         if ((flags & M_NOWAIT) == 0) {
 346                 ASSERT_SLEEPABLE();
 347         }
 348 #endif
 349 #ifdef MALLOC_DEBUG
 350         if (debug_malloc(size, ksp, flags, (void *) &va)) {
 351                 if (va != 0) {
 352                         FREECHECK_OUT(&malloc_freecheck, (void *)va);
 353                 }
 354                 return ((void *) va);
 355         }
 356 #endif
 357         indx = BUCKETINDX(size);
 358         kbp = &kmembuckets[indx];
 359         mutex_spin_enter(&malloc_lock);
 360 #ifdef KMEMSTATS
 361         while (ksp->ks_memuse >= ksp->ks_limit) {
 362                 if (flags & M_NOWAIT) {
 363                         mutex_spin_exit(&malloc_lock);
 364                         return ((void *) NULL);
 365                 }
 366                 if (ksp->ks_limblocks < 65535)
 367                         ksp->ks_limblocks++;
 368                 mtsleep((void *)ksp, PSWP+2, ksp->ks_shortdesc, 0,
 369                         &malloc_lock);
 370         }
 371         ksp->ks_size |= 1 << indx;
 372 #endif
 373 #ifdef DIAGNOSTIC
 374         copysize = 1 << indx < MAX_COPY ? 1 << indx : MAX_COPY;
 375 #endif
 376         if (kbp->kb_next == NULL) {
 377                 int s;
 378                 kbp->kb_last = NULL;
 379                 if (size > MAXALLOCSAVE)
 380                         allocsize = round_page(size);
 381                 else
 382                         allocsize = 1 << indx;
 383                 npg = btoc(allocsize);
 384                 mutex_spin_exit(&malloc_lock);
 385                 s = splvm();
 386                 va = (void *) uvm_km_alloc(kmem_map,
 387                     (vsize_t)ctob(npg), 0,
 388                     ((flags & M_NOWAIT) ? UVM_KMF_NOWAIT : 0) |
 389                     ((flags & M_CANFAIL) ? UVM_KMF_CANFAIL : 0) |
 390                     UVM_KMF_WIRED);
 391                 splx(s);
 392                 if (__predict_false(va == NULL)) {
 393                         /*
 394                          * Kmem_malloc() can return NULL, even if it can
 395                          * wait, if there is no map space available, because
 396                          * it can't fix that problem.  Neither can we,
 397                          * right now.  (We should release pages which
 398                          * are completely free and which are in kmembuckets
 399                          * with too many free elements.)
 400                          */
 401                         if ((flags & (M_NOWAIT|M_CANFAIL)) == 0)
 402                                 panic("malloc: out of space in kmem_map");
 403                         return (NULL);
 404                 }
 405                 mutex_spin_enter(&malloc_lock);
 406 #ifdef KMEMSTATS
 407                 kbp->kb_total += kbp->kb_elmpercl;
 408 #endif
 409                 kup = btokup(va);
 410                 kup->ku_indx = indx;
 411                 if (allocsize > MAXALLOCSAVE) {
 412                         if (npg > 65535)
 413                                 panic("malloc: allocation too large");
 414                         kup->ku_pagecnt = npg;
 415 #ifdef KMEMSTATS
 416                         ksp->ks_memuse += allocsize;
 417 #endif
 418                         goto out;
 419                 }
 420 #ifdef KMEMSTATS
 421                 kup->ku_freecnt = kbp->kb_elmpercl;
 422                 kbp->kb_totalfree += kbp->kb_elmpercl;
 423 #endif
 424                 /*
 425                  * Just in case we blocked while allocating memory,
 426                  * and someone else also allocated memory for this
 427                  * kmembucket, don't assume the list is still empty.
 428                  */
 429                 savedlist = kbp->kb_next;
 430                 kbp->kb_next = cp = va + (npg << PAGE_SHIFT) - allocsize;
 431                 for (;;) {
 432                         freep = (struct freelist *)cp;
 433 #ifdef DIAGNOSTIC
 434                         /*
 435                          * Copy in known text to detect modification
 436                          * after freeing.
 437                          */
 438                         end = (uint32_t *)&cp[copysize];
 439                         for (lp = (uint32_t *)cp; lp < end; lp++)
 440                                 *lp = WEIRD_ADDR;
 441                         freep->type = M_FREE;
 442 #endif /* DIAGNOSTIC */
 443                         if (cp <= va)
 444                                 break;
 445                         cp -= allocsize;
 446                         freep->next = cp;
 447                 }
 448                 freep->next = savedlist;
 449                 if (savedlist == NULL)
 450                         kbp->kb_last = (void *)freep;
 451         }
 452         va = kbp->kb_next;
 453         kbp->kb_next = ((struct freelist *)va)->next;
 454 #ifdef DIAGNOSTIC
 455         freep = (struct freelist *)va;
 456         /* XXX potential to get garbage pointer here. */
 457         if (kbp->kb_next) {
 458                 int rv;
 459                 vaddr_t addr = (vaddr_t)kbp->kb_next;
 460
 461                 vm_map_lock(kmem_map);
 462                 rv = uvm_map_checkprot(kmem_map, addr,
 463                     addr + sizeof(struct freelist), VM_PROT_WRITE);
 464                 vm_map_unlock(kmem_map);
 465
 466                 if (__predict_false(rv == 0)) {
 467                         printf("Data modified on freelist: "
 468                             "word %ld of object %p size %ld previous type %s "
 469                             "(invalid addr %p)\n",
 470                             (long)((int32_t *)&kbp->kb_next - (int32_t *)kbp),
 471                             va, size, "foo", kbp->kb_next);
 472 #ifdef MALLOCLOG
 473                         hitmlog(va);
 474 #endif
 475                         kbp->kb_next = NULL;
 476                 }
 477         }
 478
 479         /* Fill the fields that we've used with WEIRD_ADDR */
 480 #ifdef _LP64
 481         freep->type = (struct malloc_type *)
 482             (WEIRD_ADDR | (((u_long) WEIRD_ADDR) << 32));
 483 #else
 484         freep->type = (struct malloc_type *) WEIRD_ADDR;
 485 #endif
 486         end = (uint32_t *)&freep->next +
 487             (sizeof(freep->next) / sizeof(int32_t));
 488         for (lp = (uint32_t *)&freep->next; lp < end; lp++)
 489                 *lp = WEIRD_ADDR;
 490
 491         /* and check that the data hasn't been modified. */
 492         end = (uint32_t *)&va[copysize];
 493         for (lp = (uint32_t *)va; lp < end; lp++) {
 494                 if (__predict_true(*lp == WEIRD_ADDR))
 495                         continue;
 496                 printf("Data modified on freelist: "
 497                     "word %ld of object %p size %ld previous type %s "
 498                     "(0x%x != 0x%x)\n",
 499                     (long)(lp - (uint32_t *)va), va, size,
 500                     "bar", *lp, WEIRD_ADDR);
 501 #ifdef MALLOCLOG
 502                 hitmlog(va);
 503 #endif
 504                 break;
 505         }
 506
 507         freep->spare0 = 0;
 508 #endif /* DIAGNOSTIC */
 509 #ifdef KMEMSTATS
 510         kup = btokup(va);
 511         if (kup->ku_indx != indx)
 512                 panic("malloc: wrong bucket");
 513         if (kup->ku_freecnt == 0)
 514                 panic("malloc: lost data");
 515         kup->ku_freecnt--;
 516         kbp->kb_totalfree--;
 517         ksp->ks_memuse += 1 << indx;
 518 out:
 519         kbp->kb_calls++;
 520         ksp->ks_inuse++;
 521         ksp->ks_calls++;
 522         if (ksp->ks_memuse > ksp->ks_maxused)
 523                 ksp->ks_maxused = ksp->ks_memuse;
 524 #else
 525 out:
 526 #endif
 527 #ifdef MALLOCLOG
 528         domlog(va, size, ksp, 1, file, line);
 529 #endif
 530         mutex_spin_exit(&malloc_lock);
 531         if ((flags & M_ZERO) != 0)
 532                 memset(va, 0, size);
 533         FREECHECK_OUT(&malloc_freecheck, (void *)va);
 534         return ((void *) va);
 535 }
 536
 537 /*
 538  * Free a block of memory allocated by malloc.
 539  */
 540 #ifdef MALLOCLOG
 541 void
 542 _kern_free(void *addr, struct malloc_type *ksp, const char *file, long line)
 543 #else
 544 void
 545 kern_free(void *addr, struct malloc_type *ksp)
 546 #endif /* MALLOCLOG */
 547 {
 548         struct kmembuckets *kbp;
 549         struct kmemusage *kup;
 550         struct freelist *freep;
 551         long size;
 552 #ifdef DIAGNOSTIC
 553         void *cp;
 554         int32_t *end, *lp;
 555         long alloc, copysize;
 556 #endif
 557
 558         FREECHECK_IN(&malloc_freecheck, addr);
 559 #ifdef MALLOC_DEBUG
 560         if (debug_free(addr, ksp))
 561                 return;
 562 #endif
 563
 564 #ifdef DIAGNOSTIC
 565         /*
 566          * Ensure that we're free'ing something that we could
 567          * have allocated in the first place.  That is, check
 568          * to see that the address is within kmem_map.
 569          */
 570         if (__predict_false((vaddr_t)addr < vm_map_min(kmem_map) ||
 571             (vaddr_t)addr >= vm_map_max(kmem_map)))
 572                 panic("free: addr %p not within kmem_map", addr);
 573 #endif
 574
 575         kup = btokup(addr);
 576         size = 1 << kup->ku_indx;
 577         kbp = &kmembuckets[kup->ku_indx];
 578
 579         LOCKDEBUG_MEM_CHECK(addr,
 580             size <= MAXALLOCSAVE ? size : ctob(kup->ku_pagecnt));
 581
 582         mutex_spin_enter(&malloc_lock);
 583 #ifdef MALLOCLOG
 584         domlog(addr, 0, ksp, 2, file, line);
 585 #endif
 586 #ifdef DIAGNOSTIC
 587         /*
 588          * Check for returns of data that do not point to the
 589          * beginning of the allocation.
 590          */
 591         if (size > PAGE_SIZE)
 592                 alloc = addrmask[BUCKETINDX(PAGE_SIZE)];
 593         else
 594                 alloc = addrmask[kup->ku_indx];
 595         if (((u_long)addr & alloc) != 0)
 596                 panic("free: unaligned addr %p, size %ld, type %s, mask %ld",
 597                     addr, size, ksp->ks_shortdesc, alloc);
 598 #endif /* DIAGNOSTIC */
 599         if (size > MAXALLOCSAVE) {
 600                 uvm_km_free(kmem_map, (vaddr_t)addr, ctob(kup->ku_pagecnt),
 601                     UVM_KMF_WIRED);
 602 #ifdef KMEMSTATS
 603                 size = kup->ku_pagecnt << PGSHIFT;
 604                 ksp->ks_memuse -= size;
 605                 kup->ku_indx = 0;
 606                 kup->ku_pagecnt = 0;
 607                 if (ksp->ks_memuse + size >= ksp->ks_limit &&
 608                     ksp->ks_memuse < ksp->ks_limit)
 609                         wakeup((void *)ksp);
 610 #ifdef DIAGNOSTIC
 611                 if (ksp->ks_inuse == 0)
 612                         panic("free 1: inuse 0, probable double free");
 613 #endif
 614                 ksp->ks_inuse--;
 615                 kbp->kb_total -= 1;
 616 #endif
 617                 mutex_spin_exit(&malloc_lock);
 618                 return;
 619         }
 620         freep = (struct freelist *)addr;
 621 #ifdef DIAGNOSTIC
 622         /*
 623          * Check for multiple frees. Use a quick check to see if
 624          * it looks free before laboriously searching the freelist.
 625          */
 626         if (__predict_false(freep->spare0 == WEIRD_ADDR)) {
 627                 for (cp = kbp->kb_next; cp;
 628                     cp = ((struct freelist *)cp)->next) {
 629                         if (addr != cp)
 630                                 continue;
 631                         printf("multiply freed item %p\n", addr);
 632 #ifdef MALLOCLOG
 633                         hitmlog(addr);
 634 #endif
 635                         panic("free: duplicated free");
 636                 }
 637         }
 638
 639         /*
 640          * Copy in known text to detect modification after freeing
 641          * and to make it look free. Also, save the type being freed
 642          * so we can list likely culprit if modification is detected
 643          * when the object is reallocated.
 644          */
 645         copysize = size < MAX_COPY ? size : MAX_COPY;
 646         end = (int32_t *)&((char *)addr)[copysize];
 647         for (lp = (int32_t *)addr; lp < end; lp++)
 648                 *lp = WEIRD_ADDR;
 649         freep->type = ksp;
 650 #endif /* DIAGNOSTIC */
 651 #ifdef KMEMSTATS
 652         kup->ku_freecnt++;
 653         if (kup->ku_freecnt >= kbp->kb_elmpercl) {
 654                 if (kup->ku_freecnt > kbp->kb_elmpercl)
 655                         panic("free: multiple frees");
 656                 else if (kbp->kb_totalfree > kbp->kb_highwat)
 657                         kbp->kb_couldfree++;
 658         }
 659         kbp->kb_totalfree++;
 660         ksp->ks_memuse -= size;
 661         if (ksp->ks_memuse + size >= ksp->ks_limit &&
 662             ksp->ks_memuse < ksp->ks_limit)
 663                 wakeup((void *)ksp);
 664 #ifdef DIAGNOSTIC
 665         if (ksp->ks_inuse == 0)
 666                 panic("free 2: inuse 0, probable double free");
 667 #endif
 668         ksp->ks_inuse--;
 669 #endif
 670         if (kbp->kb_next == NULL)
 671                 kbp->kb_next = addr;
 672         else
 673                 ((struct freelist *)kbp->kb_last)->next = addr;
 674         freep->next = NULL;
 675         kbp->kb_last = addr;
 676         mutex_spin_exit(&malloc_lock);
 677 }
 678
 679 /*
 680  * Change the size of a block of memory.
 681  */
 682 void *
 683 kern_realloc(void *curaddr, unsigned long newsize, struct malloc_type *ksp,
 684     int flags)
 685 {
 686         struct kmemusage *kup;
 687         unsigned long cursize;
 688         void *newaddr;
 689 #ifdef DIAGNOSTIC
 690         long alloc;
 691 #endif
 692
 693         /*
 694          * realloc() with a NULL pointer is the same as malloc().
 695          */
 696         if (curaddr == NULL)
 697                 return (malloc(newsize, ksp, flags));
 698
 699         /*
 700          * realloc() with zero size is the same as free().
 701          */
 702         if (newsize == 0) {
 703                 free(curaddr, ksp);
 704                 return (NULL);
 705         }
 706
 707 #ifdef LOCKDEBUG
 708         if ((flags & M_NOWAIT) == 0) {
 709                 ASSERT_SLEEPABLE();
 710         }
 711 #endif
 712
 713         /*
 714          * Find out how large the old allocation was (and do some
 715          * sanity checking).
 716          */
 717         kup = btokup(curaddr);
 718         cursize = 1 << kup->ku_indx;
 719
 720 #ifdef DIAGNOSTIC
 721         /*
 722          * Check for returns of data that do not point to the
 723          * beginning of the allocation.
 724          */
 725         if (cursize > PAGE_SIZE)
 726                 alloc = addrmask[BUCKETINDX(PAGE_SIZE)];
 727         else
 728                 alloc = addrmask[kup->ku_indx];
 729         if (((u_long)curaddr & alloc) != 0)
 730                 panic("realloc: "
 731                     "unaligned addr %p, size %ld, type %s, mask %ld\n",
 732                     curaddr, cursize, ksp->ks_shortdesc, alloc);
 733 #endif /* DIAGNOSTIC */
 734
 735         if (cursize > MAXALLOCSAVE)
 736                 cursize = ctob(kup->ku_pagecnt);
 737
 738         /*
 739          * If we already actually have as much as they want, we're done.
 740          */
 741         if (newsize <= cursize)
 742                 return (curaddr);
 743
 744         /*
 745          * Can't satisfy the allocation with the existing block.
 746          * Allocate a new one and copy the data.
 747          */
 748         newaddr = malloc(newsize, ksp, flags);
 749         if (__predict_false(newaddr == NULL)) {
 750                 /*
 751                  * malloc() failed, because flags included M_NOWAIT.
 752                  * Return NULL to indicate that failure.  The old
 753                  * pointer is still valid.
 754                  */
 755                 return (NULL);
 756         }
 757         memcpy(newaddr, curaddr, cursize);
 758
 759         /*
 760          * We were successful: free the old allocation and return
 761          * the new one.
 762          */
 763         free(curaddr, ksp);
 764         return (newaddr);
 765 }
 766
 767 /*
 768  * Roundup size to the actual allocation size.
 769  */
 770 unsigned long
 771 malloc_roundup(unsigned long size)
 772 {
 773
 774         if (size > MAXALLOCSAVE)
 775                 return (roundup(size, PAGE_SIZE));
 776         else
 777                 return (1 << BUCKETINDX(size));
 778 }
 779
 780 /*
 781  * Add a malloc type to the system.
 782  */
 783 void
 784 malloc_type_attach(struct malloc_type *type)
 785 {
 786
 787         if (nkmempages == 0)
 788                 panic("malloc_type_attach: nkmempages == 0");
 789
 790         if (type->ks_magic != M_MAGIC)
 791                 panic("malloc_type_attach: bad magic");
 792
 793 #ifdef DIAGNOSTIC
 794         {
 795                 struct malloc_type *ksp;
 796                 for (ksp = kmemstatistics; ksp != NULL; ksp = ksp->ks_next) {
 797                         if (ksp == type)
 798                                 panic("malloc_type_attach: already on list");
 799                 }
 800         }
 801 #endif
 802
 803 #ifdef KMEMSTATS
 804         if (type->ks_limit == 0)
 805                 type->ks_limit = ((u_long)nkmempages << PAGE_SHIFT) * 6U / 10U;
 806 #else
 807         type->ks_limit = 0;
 808 #endif
 809
 810         type->ks_next = kmemstatistics;
 811         kmemstatistics = type;
 812 }
 813
 814 /*
 815  * Remove a malloc type from the system..
 816  */
 817 void
 818 malloc_type_detach(struct malloc_type *type)
 819 {
 820         struct malloc_type *ksp;
 821
 822 #ifdef DIAGNOSTIC
 823         if (type->ks_magic != M_MAGIC)
 824                 panic("malloc_type_detach: bad magic");
 825 #endif
 826
 827         if (type == kmemstatistics)
 828                 kmemstatistics = type->ks_next;
 829         else {
 830                 for (ksp = kmemstatistics; ksp->ks_next != NULL;
 831                      ksp = ksp->ks_next) {
 832                         if (ksp->ks_next == type) {
 833                                 ksp->ks_next = type->ks_next;
 834                                 break;
 835                         }
 836                 }
 837 #ifdef DIAGNOSTIC
 838                 if (ksp->ks_next == NULL)
 839                         panic("malloc_type_detach: not on list");
 840 #endif
 841         }
 842         type->ks_next = NULL;
 843 }
 844
 845 /*
 846  * Set the limit on a malloc type.
 847  */
 848 void
 849 malloc_type_setlimit(struct malloc_type *type, u_long limit)
 850 {
 851 #ifdef KMEMSTATS
 852         mutex_spin_enter(&malloc_lock);
 853         type->ks_limit = limit;
 854         mutex_spin_exit(&malloc_lock);
 855 #endif
 856 }
 857
 858 /*
 859  * Compute the number of pages that kmem_map will map, that is,
 860  * the size of the kernel malloc arena.
 861  */
 862 void
 863 kmeminit_nkmempages(void)
 864 {
 865         int npages;
 866
 867         if (nkmempages != 0) {
 868                 /*
 869                  * It's already been set (by us being here before, or
 870                  * by patching or kernel config options), bail out now.
 871                  */
 872                 return;
 873         }
 874
 875         npages = physmem;
 876
 877         if (npages > NKMEMPAGES_MAX)
 878                 npages = NKMEMPAGES_MAX;
 879
 880         if (npages < NKMEMPAGES_MIN)
 881                 npages = NKMEMPAGES_MIN;
 882
 883         nkmempages = npages;
 884 }
 885
 886 /*
 887  * Initialize the kernel memory allocator
 888  */
 889 void
 890 kmeminit(void)
 891 {
 892         __link_set_decl(malloc_types, struct malloc_type);
 893         struct malloc_type * const *ksp;
 894         vaddr_t kmb, kml;
 895 #ifdef KMEMSTATS
 896         long indx;
 897 #endif
 898
 899 #if     ((MAXALLOCSAVE & (MAXALLOCSAVE - 1)) != 0)
 900                 ERROR!_kmeminit:_MAXALLOCSAVE_not_power_of_2
 901 #endif
 902 #if     (MAXALLOCSAVE > MINALLOCSIZE * 32768)
 903                 ERROR!_kmeminit:_MAXALLOCSAVE_too_big
 904 #endif
 905 #if     (MAXALLOCSAVE < NBPG)
 906                 ERROR!_kmeminit:_MAXALLOCSAVE_too_small
 907 #endif
 908
 909         if (sizeof(struct freelist) > (1 << MINBUCKET))
 910                 panic("minbucket too small/struct freelist too big");
 911
 912         mutex_init(&malloc_lock, MUTEX_DEFAULT, IPL_VM);
 913
 914         /*
 915          * Compute the number of kmem_map pages, if we have not
 916          * done so already.
 917          */
 918         kmeminit_nkmempages();
 919
 920         kmemusage = (struct kmemusage *) uvm_km_alloc(kernel_map,
 921             (vsize_t)(nkmempages * sizeof(struct kmemusage)), 0,
 922             UVM_KMF_WIRED|UVM_KMF_ZERO);
 923         kmb = 0;
 924         kmem_map = uvm_km_suballoc(kernel_map, &kmb,
 925             &kml, ((vsize_t)nkmempages << PAGE_SHIFT),
 926             VM_MAP_INTRSAFE, false, &kmem_map_store);
 927         uvm_km_vacache_init(kmem_map, "kvakmem", 0);
 928         kmembase = (char *)kmb;
 929         kmemlimit = (char *)kml;
 930 #ifdef KMEMSTATS
 931         for (indx = 0; indx < MINBUCKET + 16; indx++) {
 932                 if (1 << indx >= PAGE_SIZE)
 933                         kmembuckets[indx].kb_elmpercl = 1;
 934                 else
 935                         kmembuckets[indx].kb_elmpercl = PAGE_SIZE / (1 << indx);
 936                 kmembuckets[indx].kb_highwat =
 937                         5 * kmembuckets[indx].kb_elmpercl;
 938         }
 939 #endif
 940
 941         /* Attach all of the statically-linked malloc types. */
 942         __link_set_foreach(ksp, malloc_types)
 943                 malloc_type_attach(*ksp);
 944
 945 #ifdef MALLOC_DEBUG
 946         debug_malloc_init();
 947 #endif
 948 }
 949
 950 #ifdef DDB
 951 #include <ddb/db_output.h>
 952
 953 /*
 954  * Dump kmem statistics from ddb.
 955  *
 956  * usage: call dump_kmemstats
 957  */
 958 void    dump_kmemstats(void);
 959
 960 void
 961 dump_kmemstats(void)
 962 {
 963 #ifdef KMEMSTATS
 964         struct malloc_type *ksp;
 965
 966         for (ksp = kmemstatistics; ksp != NULL; ksp = ksp->ks_next) {
 967                 if (ksp->ks_memuse == 0)
 968                         continue;
 969                 db_printf("%s%.*s %ld\n", ksp->ks_shortdesc,
 970                     (int)(20 - strlen(ksp->ks_shortdesc)),
 971                     "                    ",
 972                     ksp->ks_memuse);
 973         }
 974 #else
 975         db_printf("Kmem stats are not being collected.\n");
 976 #endif /* KMEMSTATS */
 977 }
 978 #endif /* DDB */
 979
 980
 981 #if 0
 982 /*
 983  * Diagnostic messages about "Data modified on
 984  * freelist" indicate a memory corruption, but
 985  * they do not help tracking it down.
 986  * This function can be called at various places
 987  * to sanity check malloc's freelist and discover
 988  * where does the corruption take place.
 989  */
 990 int
 991 freelist_sanitycheck(void) {
 992         int i,j;
 993         struct kmembuckets *kbp;
 994         struct freelist *freep;
 995         int rv = 0;
 996
 997         for (i = MINBUCKET; i <= MINBUCKET + 15; i++) {
 998                 kbp = &kmembuckets[i];
 999                 freep = (struct freelist *)kbp->kb_next;
1000                 j = 0;
1001                 while(freep) {
1002                         vm_map_lock(kmem_map);
1003                         rv = uvm_map_checkprot(kmem_map, (vaddr_t)freep,
1004                             (vaddr_t)freep + sizeof(struct freelist),
1005                             VM_PROT_WRITE);
1006                         vm_map_unlock(kmem_map);
1007
1008                         if ((rv == 0) || (*(int *)freep != WEIRD_ADDR)) {
1009                                 printf("bucket %i, chunck %d at %p modified\n",
1010                                     i, j, freep);
1011                                 return 1;
1012                         }
1013                         freep = (struct freelist *)freep->next;
1014                         j++;
1015                 }
1016         }
1017
1018         return 0;
1019 }
1020 #endif