xref: /csrg-svn/sys/kern/kern_malloc.c (revision 33497)
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 this notice is preserved and that due credit is given
7  * to the University of California at Berkeley. The name of the University
8  * may not be used to endorse or promote products derived from this
9  * software without specific prior written permission. This software
10  * is provided ``as is'' without express or implied warranty.
11  *
12  *	@(#)kern_malloc.c	7.7 (Berkeley) 02/18/88
13  */
14 
15 #include "param.h"
16 #include "vm.h"
17 #include "cmap.h"
18 #include "time.h"
19 #include "proc.h"
20 #include "map.h"
21 #include "kernel.h"
22 #include "malloc.h"
23 
24 #include "../machine/pte.h"
25 
26 struct kmembuckets bucket[MINBUCKET + 16];
27 struct kmemstats kmemstats[M_LAST];
28 struct kmemusage *kmemusage;
29 long wantkmemmap;
30 
31 /*
32  * Allocate a block of memory
33  */
34 qaddr_t
35 malloc(size, type, flags)
36 	unsigned long size;
37 	long type, flags;
38 {
39 	register struct kmembuckets *kbp;
40 	register struct kmemusage *kup;
41 	long indx, npg, alloc, allocsize, s;
42 	caddr_t va, cp;
43 #ifdef KMEMSTATS
44 	register struct kmemstats *ksp = &kmemstats[type];
45 #endif
46 
47 	indx = BUCKETINDX(size);
48 	kbp = &bucket[indx];
49 	s = splimp();
50 again:
51 #ifdef KMEMSTATS
52 	while (ksp->ks_inuse >= ksp->ks_limit) {
53 		if (flags & M_NOWAIT) {
54 			splx(s);
55 			return (0);
56 		}
57 		if (ksp->ks_limblocks < 65535)
58 			ksp->ks_limblocks++;
59 		sleep((caddr_t)ksp, PSWP+2);
60 	}
61 #endif
62 	if (kbp->kb_next == NULL) {
63 		if (size > MAXALLOCSAVE)
64 			allocsize = roundup(size, CLBYTES);
65 		else
66 			allocsize = 1 << indx;
67 		npg = clrnd(btoc(allocsize));
68 		if ((flags & M_NOWAIT) && freemem < npg) {
69 			splx(s);
70 			return (0);
71 		}
72 		alloc = rmalloc(kmemmap, npg);
73 		if (alloc == 0) {
74 			if (flags & M_NOWAIT) {
75 				splx(s);
76 				return (0);
77 			}
78 #ifdef KMEMSTATS
79 			if (ksp->ks_mapblocks < 65535)
80 				ksp->ks_mapblocks++;
81 #endif
82 			wantkmemmap++;
83 			sleep((caddr_t)&wantkmemmap, PSWP+2);
84 			goto again;
85 		}
86 		alloc -= CLSIZE;		/* convert to base 0 */
87 		(void) vmemall(&kmempt[alloc], npg, &proc[0], CSYS);
88 		va = (caddr_t) kmemxtob(alloc);
89 		vmaccess(&kmempt[alloc], va, npg);
90 #ifdef KMEMSTATS
91 		kbp->kb_total += kbp->kb_elmpercl;
92 #endif
93 		kup = btokup(va);
94 		kup->ku_indx = indx;
95 		if (allocsize > MAXALLOCSAVE) {
96 			if (npg > 65535)
97 				panic("malloc: allocation too large");
98 			kup->ku_pagecnt = npg;
99 #ifdef KMEMSTATS
100 			ksp->ks_memuse += allocsize;
101 #endif
102 			goto out;
103 		}
104 #ifdef KMEMSTATS
105 		kup->ku_freecnt = kbp->kb_elmpercl;
106 		kbp->kb_totalfree += kbp->kb_elmpercl;
107 #endif
108 		kbp->kb_next = va + (npg * NBPG) - allocsize;
109 		for (cp = kbp->kb_next; cp > va; cp -= allocsize)
110 			*(caddr_t *)cp = cp - allocsize;
111 		*(caddr_t *)cp = NULL;
112 	}
113 	va = kbp->kb_next;
114 	kbp->kb_next = *(caddr_t *)va;
115 #ifdef KMEMSTATS
116 	kup = btokup(va);
117 	if (kup->ku_indx != indx)
118 		panic("malloc: wrong bucket");
119 	if (kup->ku_freecnt == 0)
120 		panic("malloc: lost data");
121 	kup->ku_freecnt--;
122 	kbp->kb_totalfree--;
123 	ksp->ks_memuse += 1 << indx;
124 out:
125 	kbp->kb_calls++;
126 	ksp->ks_inuse++;
127 	ksp->ks_calls++;
128 	if (ksp->ks_inuse > ksp->ks_maxused)
129 		ksp->ks_maxused = ksp->ks_inuse;
130 #else
131 out:
132 #endif
133 	splx(s);
134 	return ((qaddr_t)va);
135 }
136 
137 /*
138  * Free a block of memory allocated by malloc.
139  */
140 void
141 free(addr, type)
142 	caddr_t addr;
143 	long type;
144 {
145 	register struct kmembuckets *kbp;
146 	register struct kmemusage *kup;
147 	long alloc, s;
148 #ifdef KMEMSTATS
149 	register struct kmemstats *ksp = &kmemstats[type];
150 #endif
151 
152 	kup = btokup(addr);
153 	kbp = &bucket[kup->ku_indx];
154 	s = splimp();
155 	if (1 << kup->ku_indx > MAXALLOCSAVE) {
156 		alloc = btokmemx(addr);
157 		(void) memfree(&kmempt[alloc], kup->ku_pagecnt, 0);
158 		rmfree(kmemmap, (long)kup->ku_pagecnt, alloc + CLSIZE);
159 		if (wantkmemmap) {
160 			wakeup((caddr_t)&wantkmemmap);
161 			wantkmemmap = 0;
162 		}
163 #ifdef KMEMSTATS
164 		ksp->ks_memuse -= kup->ku_pagecnt << PGSHIFT;
165 		kup->ku_indx = 0;
166 		kup->ku_pagecnt = 0;
167 		if (ksp->ks_inuse == ksp->ks_limit)
168 			wakeup((caddr_t)ksp);
169 		ksp->ks_inuse--;
170 		kbp->kb_total -= 1;
171 #endif
172 		splx(s);
173 		return;
174 	}
175 #ifdef KMEMSTATS
176 	kup->ku_freecnt++;
177 	if (kup->ku_freecnt >= kbp->kb_elmpercl)
178 		if (kup->ku_freecnt > kbp->kb_elmpercl)
179 			panic("free: multiple frees");
180 		else if (kbp->kb_totalfree > kbp->kb_highwat)
181 			kbp->kb_couldfree++;
182 	kbp->kb_totalfree++;
183 	if (ksp->ks_inuse == ksp->ks_limit)
184 		wakeup((caddr_t)ksp);
185 	ksp->ks_inuse--;
186 	ksp->ks_memuse -= 1 << kup->ku_indx;
187 #endif
188 	*(caddr_t *)addr = kbp->kb_next;
189 	kbp->kb_next = addr;
190 	splx(s);
191 }
192 
193 /*
194  * Initialize the kernel memory allocator
195  */
196 kmeminit()
197 {
198 	register long indx;
199 	int npg;
200 
201 	if (!powerof2(MAXALLOCSAVE))
202 		panic("kmeminit: MAXALLOCSAVE not power of 2");
203 	if (MAXALLOCSAVE > MINALLOCSIZE * 32768)
204 		panic("kmeminit: MAXALLOCSAVE too big");
205 	if (MAXALLOCSAVE < CLBYTES)
206 		panic("kmeminit: MAXALLOCSAVE too small");
207 	npg = ekmempt - kmempt;
208 	rminit(kmemmap, npg, (long)CLSIZE, "malloc map", npg);
209 #ifdef KMEMSTATS
210 	for (indx = 0; indx < MINBUCKET + 16; indx++) {
211 		if (1 << indx >= CLBYTES)
212 			bucket[indx].kb_elmpercl = 1;
213 		else
214 			bucket[indx].kb_elmpercl = CLBYTES / (1 << indx);
215 		bucket[indx].kb_highwat = 5 * bucket[indx].kb_elmpercl;
216 	}
217 	for (indx = 0; indx < M_LAST; indx++)
218 		kmemstats[indx].ks_limit = npg * CLBYTES * 8 / 10;
219 #endif
220 }
221