Commit | Line | Data |
---|---|---|
d4202556 KM |
1 | /* |
2 | * Copyright (c) 1987 Regents of the University of California. | |
2420c94a | 3 | * All rights reserved. |
d4202556 | 4 | * |
2420c94a | 5 | * Redistribution and use in source and binary forms are permitted |
616d42db KB |
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. | |
2420c94a | 16 | * |
5aeb6f6a | 17 | * @(#)kern_malloc.c 7.17 (Berkeley) %G% |
d4202556 KM |
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 | ||
40ed2c45 | 29 | #include "machine/pte.h" |
d4202556 KM |
30 | |
31 | struct kmembuckets bucket[MINBUCKET + 16]; | |
32 | struct kmemstats kmemstats[M_LAST]; | |
33 | struct kmemusage *kmemusage; | |
fd78e9f6 | 34 | long wantkmemmap; |
c029fe44 KS |
35 | long malloc_reentered; |
36 | #define IN { if (malloc_reentered) panic("malloc reentered");\ | |
37 | else malloc_reentered = 1;} | |
38 | #define OUT (malloc_reentered = 0) | |
d4202556 KM |
39 | |
40 | /* | |
41 | * Allocate a block of memory | |
42 | */ | |
738ba0d6 KM |
43 | qaddr_t |
44 | malloc(size, type, flags) | |
d4202556 | 45 | unsigned long size; |
47516941 | 46 | int type, flags; |
d4202556 KM |
47 | { |
48 | register struct kmembuckets *kbp; | |
49 | register struct kmemusage *kup; | |
47516941 MK |
50 | long indx, npg, alloc, allocsize; |
51 | int s; | |
d4202556 KM |
52 | caddr_t va, cp; |
53 | #ifdef KMEMSTATS | |
fd78e9f6 | 54 | register struct kmemstats *ksp = &kmemstats[type]; |
dbe43ea1 MK |
55 | |
56 | if (((unsigned long)type) > M_LAST) | |
a2aebb63 | 57 | panic("malloc - bogus type"); |
d4202556 | 58 | #endif |
fd78e9f6 | 59 | |
d4202556 KM |
60 | indx = BUCKETINDX(size); |
61 | kbp = &bucket[indx]; | |
62 | s = splimp(); | |
c029fe44 | 63 | IN; |
fd78e9f6 KM |
64 | again: |
65 | #ifdef KMEMSTATS | |
0a4aff4d | 66 | while (ksp->ks_memuse >= ksp->ks_limit) { |
fd78e9f6 | 67 | if (flags & M_NOWAIT) { |
c029fe44 | 68 | OUT; |
fd78e9f6 KM |
69 | splx(s); |
70 | return (0); | |
71 | } | |
72 | if (ksp->ks_limblocks < 65535) | |
73 | ksp->ks_limblocks++; | |
c029fe44 | 74 | OUT; |
fd78e9f6 | 75 | sleep((caddr_t)ksp, PSWP+2); |
c029fe44 | 76 | IN; |
fd78e9f6 KM |
77 | } |
78 | #endif | |
d4202556 KM |
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) { | |
c029fe44 | 86 | OUT; |
d4202556 KM |
87 | splx(s); |
88 | return (0); | |
89 | } | |
90 | alloc = rmalloc(kmemmap, npg); | |
91 | if (alloc == 0) { | |
fd78e9f6 | 92 | if (flags & M_NOWAIT) { |
c029fe44 | 93 | OUT; |
fd78e9f6 KM |
94 | splx(s); |
95 | return (0); | |
96 | } | |
97 | #ifdef KMEMSTATS | |
98 | if (ksp->ks_mapblocks < 65535) | |
99 | ksp->ks_mapblocks++; | |
100 | #endif | |
101 | wantkmemmap++; | |
c029fe44 | 102 | OUT; |
fd78e9f6 | 103 | sleep((caddr_t)&wantkmemmap, PSWP+2); |
c029fe44 | 104 | IN; |
fd78e9f6 | 105 | goto again; |
d4202556 | 106 | } |
7656fce5 | 107 | alloc -= CLSIZE; /* convert to base 0 */ |
47516941 | 108 | (void) vmemall(&kmempt[alloc], (int)npg, &proc[0], CSYS); |
d4202556 | 109 | va = (caddr_t) kmemxtob(alloc); |
47516941 | 110 | vmaccess(&kmempt[alloc], va, (int)npg); |
d4202556 KM |
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; | |
fd78e9f6 KM |
120 | #ifdef KMEMSTATS |
121 | ksp->ks_memuse += allocsize; | |
122 | #endif | |
d4202556 KM |
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; | |
c029fe44 KS |
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 | } | |
d4202556 KM |
137 | } |
138 | va = kbp->kb_next; | |
c029fe44 KS |
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 | } | |
d4202556 KM |
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--; | |
fd78e9f6 | 153 | ksp->ks_memuse += 1 << indx; |
d4202556 KM |
154 | out: |
155 | kbp->kb_calls++; | |
156 | ksp->ks_inuse++; | |
157 | ksp->ks_calls++; | |
0a4aff4d KM |
158 | if (ksp->ks_memuse > ksp->ks_maxused) |
159 | ksp->ks_maxused = ksp->ks_memuse; | |
d4202556 KM |
160 | #else |
161 | out: | |
162 | #endif | |
c029fe44 | 163 | OUT; |
d4202556 KM |
164 | splx(s); |
165 | return ((qaddr_t)va); | |
166 | } | |
167 | ||
168 | /* | |
169 | * Free a block of memory allocated by malloc. | |
170 | */ | |
738ba0d6 KM |
171 | void |
172 | free(addr, type) | |
d4202556 | 173 | caddr_t addr; |
47516941 | 174 | int type; |
d4202556 KM |
175 | { |
176 | register struct kmembuckets *kbp; | |
177 | register struct kmemusage *kup; | |
47516941 MK |
178 | long alloc, size; |
179 | int s; | |
fd78e9f6 KM |
180 | #ifdef KMEMSTATS |
181 | register struct kmemstats *ksp = &kmemstats[type]; | |
182 | #endif | |
d4202556 KM |
183 | |
184 | kup = btokup(addr); | |
738ba0d6 | 185 | kbp = &bucket[kup->ku_indx]; |
d4202556 | 186 | s = splimp(); |
c029fe44 | 187 | IN; |
0a4aff4d KM |
188 | size = 1 << kup->ku_indx; |
189 | if (size > MAXALLOCSAVE) { | |
d4202556 | 190 | alloc = btokmemx(addr); |
030ec347 | 191 | (void) memfree(&kmempt[alloc], (int)kup->ku_pagecnt, 1); |
fd78e9f6 | 192 | rmfree(kmemmap, (long)kup->ku_pagecnt, alloc + CLSIZE); |
c029fe44 | 193 | OUT; |
fd78e9f6 KM |
194 | if (wantkmemmap) { |
195 | wakeup((caddr_t)&wantkmemmap); | |
196 | wantkmemmap = 0; | |
197 | } | |
d4202556 | 198 | #ifdef KMEMSTATS |
0a4aff4d KM |
199 | size = kup->ku_pagecnt << PGSHIFT; |
200 | ksp->ks_memuse -= size; | |
d4202556 KM |
201 | kup->ku_indx = 0; |
202 | kup->ku_pagecnt = 0; | |
0a4aff4d KM |
203 | if (ksp->ks_memuse + size >= ksp->ks_limit && |
204 | ksp->ks_memuse < ksp->ks_limit) | |
fd78e9f6 KM |
205 | wakeup((caddr_t)ksp); |
206 | ksp->ks_inuse--; | |
738ba0d6 | 207 | kbp->kb_total -= 1; |
d4202556 KM |
208 | #endif |
209 | splx(s); | |
210 | return; | |
211 | } | |
c029fe44 KS |
212 | if (size == 128) { |
213 | long *lp = (long *)addr; | |
214 | lp[0] = lp[1] = lp[3] = lp[4] = -1; | |
215 | } | |
d4202556 KM |
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++; | |
0a4aff4d KM |
224 | ksp->ks_memuse -= size; |
225 | if (ksp->ks_memuse + size >= ksp->ks_limit && | |
226 | ksp->ks_memuse < ksp->ks_limit) | |
fd78e9f6 KM |
227 | wakeup((caddr_t)ksp); |
228 | ksp->ks_inuse--; | |
d4202556 | 229 | #endif |
c029fe44 | 230 | ((caddr_t *)addr)[2] = kbp->kb_next; |
d4202556 | 231 | kbp->kb_next = addr; |
c029fe44 | 232 | OUT; |
d4202556 KM |
233 | splx(s); |
234 | } | |
235 | ||
236 | /* | |
237 | * Initialize the kernel memory allocator | |
238 | */ | |
239 | kmeminit() | |
240 | { | |
241 | register long indx; | |
738ba0d6 | 242 | int npg; |
d4202556 | 243 | |
47516941 MK |
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 | |
738ba0d6 | 253 | npg = ekmempt - kmempt; |
47516941 | 254 | rminit(kmemmap, (long)npg, (long)CLSIZE, "malloc map", npg); |
d4202556 KM |
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++) | |
5aeb6f6a | 264 | kmemstats[indx].ks_limit = npg * NBPG * 6 / 10; |
d4202556 KM |
265 | #endif |
266 | } |