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