The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/kern/kern_malloc.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

    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


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.