xref: /netbsd-src/sys/kern/kern_malloc.c (revision 21e37cc72a480a47828990a439cde7ac9ffaf0c6)
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
951