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