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-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-2  -  FREEBSD-11-1  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-4  -  FREEBSD-10-3  -  FREEBSD-10-2  -  FREEBSD-10-1  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-3  -  FREEBSD-9-2  -  FREEBSD-9-1  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-4  -  FREEBSD-8-3  -  FREEBSD-8-2  -  FREEBSD-8-1  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-4  -  FREEBSD-7-3  -  FREEBSD-7-2  -  FREEBSD-7-1  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-4  -  FREEBSD-6-3  -  FREEBSD-6-2  -  FREEBSD-6-1  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-5  -  FREEBSD-5-4  -  FREEBSD-5-3  -  FREEBSD-5-2  -  FREEBSD-5-1  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  linux-2.6  -  linux-2.4.22  -  MK83  -  MK84  -  PLAN9  -  DFBSD  -  NETBSD  -  NETBSD5  -  NETBSD4  -  NETBSD3  -  NETBSD20  -  OPENBSD  -  xnu-517  -  xnu-792  -  xnu-792.6.70  -  xnu-1228  -  xnu-1456.1.26  -  xnu-1699.24.8  -  xnu-2050.18.24  -  OPENSOLARIS  -  minix-3-1-1 
SearchContext: -  none  -  3  -  10 

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

Cache object: 42148b8d845df741d82b06e344966357


[ 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.