usr/src/sys/kern/kern_malloc.c

/*
 * Copyright (c) 1987 Regents of the University of California.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms are permitted
 * provided that the above copyright notice and this paragraph are
 * duplicated in all such forms and that any documentation,
 * advertising materials, and other materials related to such
 * distribution and use acknowledge that the software was developed
 * by the University of California, Berkeley.  The name of the
 * University may not be used to endorse or promote products derived
 * from this software without specific prior written permission.
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
 * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 *
 *	@(#)kern_malloc.c	7.16 (Berkeley) %G%
 */

#include "param.h"
#include "vm.h"
#include "cmap.h"
#include "time.h"
#include "proc.h"
#include "map.h"
#include "kernel.h"
#include "malloc.h"

#include "machine/pte.h"

struct kmembuckets bucket[MINBUCKET + 16];
struct kmemstats kmemstats[M_LAST];
struct kmemusage *kmemusage;
long wantkmemmap;
long malloc_reentered;
#define IN { if (malloc_reentered) panic("malloc reentered");\
			else malloc_reentered = 1;}
#define OUT (malloc_reentered = 0)

/*
 * Allocate a block of memory
 */
qaddr_t
malloc(size, type, flags)
	unsigned long size;
	int type, flags;
{
	register struct kmembuckets *kbp;
	register struct kmemusage *kup;
	long indx, npg, alloc, allocsize;
	int s;
	caddr_t va, cp;
#ifdef KMEMSTATS
	register struct kmemstats *ksp = &kmemstats[type];

	if (((unsigned long)type) > M_LAST)
		panic("malloc - bogus type");
#endif

	indx = BUCKETINDX(size);
	kbp = &bucket[indx];
	s = splimp();
	IN;
again:
#ifdef KMEMSTATS
	while (ksp->ks_memuse >= ksp->ks_limit) {
		if (flags & M_NOWAIT) {
			OUT;
			splx(s);
			return (0);
		}
		if (ksp->ks_limblocks < 65535)
			ksp->ks_limblocks++;
		OUT;
		sleep((caddr_t)ksp, PSWP+2);
		IN;
	}
#endif
	if (kbp->kb_next == NULL) {
		if (size > MAXALLOCSAVE)
			allocsize = roundup(size, CLBYTES);
		else
			allocsize = 1 << indx;
		npg = clrnd(btoc(allocsize));
		if ((flags & M_NOWAIT) && freemem < npg) {
			OUT;
			splx(s);
			return (0);
		}
		alloc = rmalloc(kmemmap, npg);
		if (alloc == 0) {
			if (flags & M_NOWAIT) {
				OUT;
				splx(s);
				return (0);
			}
#ifdef KMEMSTATS
			if (ksp->ks_mapblocks < 65535)
				ksp->ks_mapblocks++;
#endif
			wantkmemmap++;
			OUT;
			sleep((caddr_t)&wantkmemmap, PSWP+2);
			IN;
			goto again;
		}
		alloc -= CLSIZE;		/* convert to base 0 */
		(void) vmemall(&kmempt[alloc], (int)npg, &proc[0], CSYS);
		va = (caddr_t) kmemxtob(alloc);
		vmaccess(&kmempt[alloc], va, (int)npg);
#ifdef KMEMSTATS
		kbp->kb_total += kbp->kb_elmpercl;
#endif
		kup = btokup(va);
		kup->ku_indx = indx;
		if (allocsize > MAXALLOCSAVE) {
			if (npg > 65535)
				panic("malloc: allocation too large");
			kup->ku_pagecnt = npg;
#ifdef KMEMSTATS
			ksp->ks_memuse += allocsize;
#endif
			goto out;
		}
#ifdef KMEMSTATS
		kup->ku_freecnt = kbp->kb_elmpercl;
		kbp->kb_totalfree += kbp->kb_elmpercl;
#endif
		kbp->kb_next = va + (npg * NBPG) - allocsize;
		for (cp = kbp->kb_next; cp >= va; cp -= allocsize) {
			((caddr_t *)cp)[2] = (cp > va ? cp - allocsize : NULL);
			if (indx == 7) {
				long *lp = (long *)cp;
				lp[0] = lp[1] = lp[3] = lp[4] = -1;
			}
		}
	}
	va = kbp->kb_next;
	kbp->kb_next = ((caddr_t *)va)[2];
	if (indx == 7) {
		long *lp = (long *)va;
		if (lp[0] != -1 || lp[1] != -1 || lp[3] != -1 || lp[4] != -1)
			panic("malloc meddled");
	}
#ifdef KMEMSTATS
	kup = btokup(va);
	if (kup->ku_indx != indx)
		panic("malloc: wrong bucket");
	if (kup->ku_freecnt == 0)
		panic("malloc: lost data");
	kup->ku_freecnt--;
	kbp->kb_totalfree--;
	ksp->ks_memuse += 1 << indx;
out:
	kbp->kb_calls++;
	ksp->ks_inuse++;
	ksp->ks_calls++;
	if (ksp->ks_memuse > ksp->ks_maxused)
		ksp->ks_maxused = ksp->ks_memuse;
#else
out:
#endif
	OUT;
	splx(s);
	return ((qaddr_t)va);
}

/*
 * Free a block of memory allocated by malloc.
 */
void
free(addr, type)
	caddr_t addr;
	int type;
{
	register struct kmembuckets *kbp;
	register struct kmemusage *kup;
	long alloc, size;
	int s;
#ifdef KMEMSTATS
	register struct kmemstats *ksp = &kmemstats[type];
#endif

	kup = btokup(addr);
	kbp = &bucket[kup->ku_indx];
	s = splimp();
	IN;
	size = 1 << kup->ku_indx;
	if (size > MAXALLOCSAVE) {
		alloc = btokmemx(addr);
		(void) memfree(&kmempt[alloc], (int)kup->ku_pagecnt, 1);
		rmfree(kmemmap, (long)kup->ku_pagecnt, alloc + CLSIZE);
		OUT;
		if (wantkmemmap) {
			wakeup((caddr_t)&wantkmemmap);
			wantkmemmap = 0;
		}
#ifdef KMEMSTATS
		size = kup->ku_pagecnt << PGSHIFT;
		ksp->ks_memuse -= size;
		kup->ku_indx = 0;
		kup->ku_pagecnt = 0;
		if (ksp->ks_memuse + size >= ksp->ks_limit &&
		    ksp->ks_memuse < ksp->ks_limit)
			wakeup((caddr_t)ksp);
		ksp->ks_inuse--;
		kbp->kb_total -= 1;
#endif
		splx(s);
		return;
	}
	if (size == 128) {
		long *lp = (long *)addr;
		lp[0] = lp[1] = lp[3] = lp[4] = -1;
	}
#ifdef KMEMSTATS
	kup->ku_freecnt++;
	if (kup->ku_freecnt >= kbp->kb_elmpercl)
		if (kup->ku_freecnt > kbp->kb_elmpercl)
			panic("free: multiple frees");
		else if (kbp->kb_totalfree > kbp->kb_highwat)
			kbp->kb_couldfree++;
	kbp->kb_totalfree++;
	ksp->ks_memuse -= size;
	if (ksp->ks_memuse + size >= ksp->ks_limit &&
	    ksp->ks_memuse < ksp->ks_limit)
		wakeup((caddr_t)ksp);
	ksp->ks_inuse--;
#endif
	((caddr_t *)addr)[2] = kbp->kb_next;
	kbp->kb_next = addr;
	OUT;
	splx(s);
}

/*
 * Initialize the kernel memory allocator
 */
kmeminit()
{
	register long indx;
	int npg;

#if	((MAXALLOCSAVE & (MAXALLOCSAVE - 1)) != 0)
		ERROR!_kmeminit:_MAXALLOCSAVE_not_power_of_2
#endif
#if	(MAXALLOCSAVE > MINALLOCSIZE * 32768)
		ERROR!_kmeminit:_MAXALLOCSAVE_too_big
#endif
#if	(MAXALLOCSAVE < CLBYTES)
		ERROR!_kmeminit:_MAXALLOCSAVE_too_small
#endif
	npg = ekmempt - kmempt;
	rminit(kmemmap, (long)npg, (long)CLSIZE, "malloc map", npg);
#ifdef KMEMSTATS
	for (indx = 0; indx < MINBUCKET + 16; indx++) {
		if (1 << indx >= CLBYTES)
			bucket[indx].kb_elmpercl = 1;
		else
			bucket[indx].kb_elmpercl = CLBYTES / (1 << indx);
		bucket[indx].kb_highwat = 5 * bucket[indx].kb_elmpercl;
	}
	for (indx = 0; indx < M_LAST; indx++)
		kmemstats[indx].ks_limit = npg * CLBYTES * 8 / 10;
#endif
}
Commit	Line	Data
	1	/*
	2	* Copyright (c) 1987 Regents of the University of California.
	3	* All rights reserved.
	4	*
	5	* Redistribution and use in source and binary forms are permitted
	6	* provided that the above copyright notice and this paragraph are
	7	* duplicated in all such forms and that any documentation,
	8	* advertising materials, and other materials related to such
	9	* distribution and use acknowledge that the software was developed
	10	* by the University of California, Berkeley. The name of the
	11	* University may not be used to endorse or promote products derived
	12	* from this software without specific prior written permission.
	13	* THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
	14	* IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
	15	* WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
	16	*
	17	* @(#)kern_malloc.c 7.16 (Berkeley) %G%
	18	*/
	19
	20	#include "param.h"
	21	#include "vm.h"
	22	#include "cmap.h"
	23	#include "time.h"
	24	#include "proc.h"
	25	#include "map.h"
	26	#include "kernel.h"
	27	#include "malloc.h"
	28
	29	#include "machine/pte.h"
	30
	31	struct kmembuckets bucket[MINBUCKET + 16];
	32	struct kmemstats kmemstats[M_LAST];
	33	struct kmemusage *kmemusage;
	34	long wantkmemmap;
	35	long malloc_reentered;
	36	#define IN { if (malloc_reentered) panic("malloc reentered");\
	37	else malloc_reentered = 1;}
	38	#define OUT (malloc_reentered = 0)
	39
	40	/*
	41	* Allocate a block of memory
	42	*/
	43	qaddr_t
	44	malloc(size, type, flags)
	45	unsigned long size;
	46	int type, flags;
	47	{
	48	register struct kmembuckets *kbp;
	49	register struct kmemusage *kup;
	50	long indx, npg, alloc, allocsize;
	51	int s;
	52	caddr_t va, cp;
	53	#ifdef KMEMSTATS
	54	register struct kmemstats *ksp = &kmemstats[type];
	55
	56	if (((unsigned long)type) > M_LAST)
	57	panic("malloc - bogus type");
	58	#endif
	59
	60	indx = BUCKETINDX(size);
	61	kbp = &bucket[indx];
	62	s = splimp();
	63	IN;
	64	again:
	65	#ifdef KMEMSTATS
	66	while (ksp->ks_memuse >= ksp->ks_limit) {
	67	if (flags & M_NOWAIT) {
	68	OUT;
	69	splx(s);
	70	return (0);
	71	}
	72	if (ksp->ks_limblocks < 65535)
	73	ksp->ks_limblocks++;
	74	OUT;
	75	sleep((caddr_t)ksp, PSWP+2);
	76	IN;
	77	}
	78	#endif
	79	if (kbp->kb_next == NULL) {
	80	if (size > MAXALLOCSAVE)
	81	allocsize = roundup(size, CLBYTES);
	82	else
	83	allocsize = 1 << indx;
	84	npg = clrnd(btoc(allocsize));
	85	if ((flags & M_NOWAIT) && freemem < npg) {
	86	OUT;
	87	splx(s);
	88	return (0);
	89	}
	90	alloc = rmalloc(kmemmap, npg);
	91	if (alloc == 0) {
	92	if (flags & M_NOWAIT) {
	93	OUT;
	94	splx(s);
	95	return (0);
	96	}
	97	#ifdef KMEMSTATS
	98	if (ksp->ks_mapblocks < 65535)
	99	ksp->ks_mapblocks++;
	100	#endif
	101	wantkmemmap++;
	102	OUT;
	103	sleep((caddr_t)&wantkmemmap, PSWP+2);
	104	IN;
	105	goto again;
	106	}
	107	alloc -= CLSIZE; /* convert to base 0 */
	108	(void) vmemall(&kmempt[alloc], (int)npg, &proc[0], CSYS);
	109	va = (caddr_t) kmemxtob(alloc);
	110	vmaccess(&kmempt[alloc], va, (int)npg);
	111	#ifdef KMEMSTATS
	112	kbp->kb_total += kbp->kb_elmpercl;
	113	#endif
	114	kup = btokup(va);
	115	kup->ku_indx = indx;
	116	if (allocsize > MAXALLOCSAVE) {
	117	if (npg > 65535)
	118	panic("malloc: allocation too large");
	119	kup->ku_pagecnt = npg;
	120	#ifdef KMEMSTATS
	121	ksp->ks_memuse += allocsize;
	122	#endif
	123	goto out;
	124	}
	125	#ifdef KMEMSTATS
	126	kup->ku_freecnt = kbp->kb_elmpercl;
	127	kbp->kb_totalfree += kbp->kb_elmpercl;
	128	#endif
	129	kbp->kb_next = va + (npg * NBPG) - allocsize;
	130	for (cp = kbp->kb_next; cp >= va; cp -= allocsize) {
	131	((caddr_t *)cp)[2] = (cp > va ? cp - allocsize : NULL);
	132	if (indx == 7) {
	133	long lp = (long )cp;
	134	lp[0] = lp[1] = lp[3] = lp[4] = -1;
	135	}
	136	}
	137	}
	138	va = kbp->kb_next;
	139	kbp->kb_next = ((caddr_t *)va)[2];
	140	if (indx == 7) {
	141	long lp = (long )va;
	142	if (lp[0] != -1 \|\| lp[1] != -1 \|\| lp[3] != -1 \|\| lp[4] != -1)
	143	panic("malloc meddled");
	144	}
	145	#ifdef KMEMSTATS
	146	kup = btokup(va);
	147	if (kup->ku_indx != indx)
	148	panic("malloc: wrong bucket");
	149	if (kup->ku_freecnt == 0)
	150	panic("malloc: lost data");
	151	kup->ku_freecnt--;
	152	kbp->kb_totalfree--;
	153	ksp->ks_memuse += 1 << indx;
	154	out:
	155	kbp->kb_calls++;
	156	ksp->ks_inuse++;
	157	ksp->ks_calls++;
	158	if (ksp->ks_memuse > ksp->ks_maxused)
	159	ksp->ks_maxused = ksp->ks_memuse;
	160	#else
	161	out:
	162	#endif
	163	OUT;
	164	splx(s);
	165	return ((qaddr_t)va);
	166	}
	167
	168	/*
	169	* Free a block of memory allocated by malloc.
	170	*/
	171	void
	172	free(addr, type)
	173	caddr_t addr;
	174	int type;
	175	{
	176	register struct kmembuckets *kbp;
	177	register struct kmemusage *kup;
	178	long alloc, size;
	179	int s;
	180	#ifdef KMEMSTATS
	181	register struct kmemstats *ksp = &kmemstats[type];
	182	#endif
	183
	184	kup = btokup(addr);
	185	kbp = &bucket[kup->ku_indx];
	186	s = splimp();
	187	IN;
	188	size = 1 << kup->ku_indx;
	189	if (size > MAXALLOCSAVE) {
	190	alloc = btokmemx(addr);
	191	(void) memfree(&kmempt[alloc], (int)kup->ku_pagecnt, 1);
	192	rmfree(kmemmap, (long)kup->ku_pagecnt, alloc + CLSIZE);
	193	OUT;
	194	if (wantkmemmap) {
	195	wakeup((caddr_t)&wantkmemmap);
	196	wantkmemmap = 0;
	197	}
	198	#ifdef KMEMSTATS
	199	size = kup->ku_pagecnt << PGSHIFT;
	200	ksp->ks_memuse -= size;
	201	kup->ku_indx = 0;
	202	kup->ku_pagecnt = 0;
	203	if (ksp->ks_memuse + size >= ksp->ks_limit &&
	204	ksp->ks_memuse < ksp->ks_limit)
	205	wakeup((caddr_t)ksp);
	206	ksp->ks_inuse--;
	207	kbp->kb_total -= 1;
	208	#endif
	209	splx(s);
	210	return;
	211	}
	212	if (size == 128) {
	213	long lp = (long )addr;
	214	lp[0] = lp[1] = lp[3] = lp[4] = -1;
	215	}
	216	#ifdef KMEMSTATS
	217	kup->ku_freecnt++;
	218	if (kup->ku_freecnt >= kbp->kb_elmpercl)
	219	if (kup->ku_freecnt > kbp->kb_elmpercl)
	220	panic("free: multiple frees");
	221	else if (kbp->kb_totalfree > kbp->kb_highwat)
	222	kbp->kb_couldfree++;
	223	kbp->kb_totalfree++;
	224	ksp->ks_memuse -= size;
	225	if (ksp->ks_memuse + size >= ksp->ks_limit &&
	226	ksp->ks_memuse < ksp->ks_limit)
	227	wakeup((caddr_t)ksp);
	228	ksp->ks_inuse--;
	229	#endif
	230	((caddr_t *)addr)[2] = kbp->kb_next;
	231	kbp->kb_next = addr;
	232	OUT;
	233	splx(s);
	234	}
	235
	236	/*
	237	* Initialize the kernel memory allocator
	238	*/
	239	kmeminit()
	240	{
	241	register long indx;
	242	int npg;
	243
	244	#if ((MAXALLOCSAVE & (MAXALLOCSAVE - 1)) != 0)
	245	ERROR!_kmeminit:_MAXALLOCSAVE_not_power_of_2
	246	#endif
	247	#if (MAXALLOCSAVE > MINALLOCSIZE * 32768)
	248	ERROR!_kmeminit:_MAXALLOCSAVE_too_big
	249	#endif
	250	#if (MAXALLOCSAVE < CLBYTES)
	251	ERROR!_kmeminit:_MAXALLOCSAVE_too_small
	252	#endif
	253	npg = ekmempt - kmempt;
	254	rminit(kmemmap, (long)npg, (long)CLSIZE, "malloc map", npg);
	255	#ifdef KMEMSTATS
	256	for (indx = 0; indx < MINBUCKET + 16; indx++) {
	257	if (1 << indx >= CLBYTES)
	258	bucket[indx].kb_elmpercl = 1;
	259	else
	260	bucket[indx].kb_elmpercl = CLBYTES / (1 << indx);
	261	bucket[indx].kb_highwat = 5 * bucket[indx].kb_elmpercl;
	262	}
	263	for (indx = 0; indx < M_LAST; indx++)
	264	kmemstats[indx].ks_limit = npg * CLBYTES * 8 / 10;
	265	#endif
	266	}