Commit | Line | Data |
---|---|---|
d4202556 KM |
1 | /* |
2 | * Copyright (c) 1987 Regents of the University of California. | |
2420c94a | 3 | * All rights reserved. |
d4202556 | 4 | * |
dbf0c423 | 5 | * %sccs.include.redist.c% |
2420c94a | 6 | * |
9d4095a1 | 7 | * @(#)kern_malloc.c 7.21 (Berkeley) %G% |
d4202556 KM |
8 | */ |
9 | ||
10 | #include "param.h" | |
d4202556 KM |
11 | #include "cmap.h" |
12 | #include "time.h" | |
13 | #include "proc.h" | |
14 | #include "map.h" | |
15 | #include "kernel.h" | |
16 | #include "malloc.h" | |
9d4095a1 KM |
17 | #include "../vm/vm_param.h" |
18 | #include "../vm/vm_map.h" | |
19 | #include "../vm/vm_kern.h" | |
d4202556 KM |
20 | |
21 | struct kmembuckets bucket[MINBUCKET + 16]; | |
22 | struct kmemstats kmemstats[M_LAST]; | |
23 | struct kmemusage *kmemusage; | |
9d4095a1 | 24 | char *kmembase, *kmemlimit; |
79ce1cef | 25 | char *memname[] = INITKMEMNAMES; |
c029fe44 KS |
26 | long malloc_reentered; |
27 | #define IN { if (malloc_reentered) panic("malloc reentered");\ | |
28 | else malloc_reentered = 1;} | |
29 | #define OUT (malloc_reentered = 0) | |
d4202556 KM |
30 | |
31 | /* | |
32 | * Allocate a block of memory | |
33 | */ | |
738ba0d6 KM |
34 | qaddr_t |
35 | malloc(size, type, flags) | |
d4202556 | 36 | unsigned long size; |
47516941 | 37 | int type, flags; |
d4202556 KM |
38 | { |
39 | register struct kmembuckets *kbp; | |
40 | register struct kmemusage *kup; | |
47516941 MK |
41 | long indx, npg, alloc, allocsize; |
42 | int s; | |
d4202556 KM |
43 | caddr_t va, cp; |
44 | #ifdef KMEMSTATS | |
fd78e9f6 | 45 | register struct kmemstats *ksp = &kmemstats[type]; |
dbe43ea1 MK |
46 | |
47 | if (((unsigned long)type) > M_LAST) | |
a2aebb63 | 48 | panic("malloc - bogus type"); |
d4202556 | 49 | #endif |
fd78e9f6 | 50 | |
d4202556 KM |
51 | indx = BUCKETINDX(size); |
52 | kbp = &bucket[indx]; | |
53 | s = splimp(); | |
c029fe44 | 54 | IN; |
fd78e9f6 | 55 | #ifdef KMEMSTATS |
0a4aff4d | 56 | while (ksp->ks_memuse >= ksp->ks_limit) { |
fd78e9f6 | 57 | if (flags & M_NOWAIT) { |
c029fe44 | 58 | OUT; |
fd78e9f6 KM |
59 | splx(s); |
60 | return (0); | |
61 | } | |
62 | if (ksp->ks_limblocks < 65535) | |
63 | ksp->ks_limblocks++; | |
c029fe44 | 64 | OUT; |
79ce1cef | 65 | tsleep((caddr_t)ksp, PSWP+2, memname[type], 0); |
c029fe44 | 66 | IN; |
fd78e9f6 KM |
67 | } |
68 | #endif | |
d4202556 KM |
69 | if (kbp->kb_next == NULL) { |
70 | if (size > MAXALLOCSAVE) | |
71 | allocsize = roundup(size, CLBYTES); | |
72 | else | |
73 | allocsize = 1 << indx; | |
74 | npg = clrnd(btoc(allocsize)); | |
9d4095a1 KM |
75 | va = (caddr_t) kmem_malloc(kmem_map, (vm_size_t)ctob(npg), |
76 | !(flags & M_NOWAIT)); | |
77 | if (va == NULL) { | |
c029fe44 | 78 | OUT; |
d4202556 KM |
79 | splx(s); |
80 | return (0); | |
81 | } | |
d4202556 KM |
82 | #ifdef KMEMSTATS |
83 | kbp->kb_total += kbp->kb_elmpercl; | |
84 | #endif | |
85 | kup = btokup(va); | |
86 | kup->ku_indx = indx; | |
87 | if (allocsize > MAXALLOCSAVE) { | |
88 | if (npg > 65535) | |
89 | panic("malloc: allocation too large"); | |
90 | kup->ku_pagecnt = npg; | |
fd78e9f6 KM |
91 | #ifdef KMEMSTATS |
92 | ksp->ks_memuse += allocsize; | |
93 | #endif | |
d4202556 KM |
94 | goto out; |
95 | } | |
96 | #ifdef KMEMSTATS | |
97 | kup->ku_freecnt = kbp->kb_elmpercl; | |
98 | kbp->kb_totalfree += kbp->kb_elmpercl; | |
99 | #endif | |
100 | kbp->kb_next = va + (npg * NBPG) - allocsize; | |
c029fe44 KS |
101 | for (cp = kbp->kb_next; cp >= va; cp -= allocsize) { |
102 | ((caddr_t *)cp)[2] = (cp > va ? cp - allocsize : NULL); | |
103 | if (indx == 7) { | |
104 | long *lp = (long *)cp; | |
105 | lp[0] = lp[1] = lp[3] = lp[4] = -1; | |
106 | } | |
107 | } | |
d4202556 KM |
108 | } |
109 | va = kbp->kb_next; | |
c029fe44 KS |
110 | kbp->kb_next = ((caddr_t *)va)[2]; |
111 | if (indx == 7) { | |
112 | long *lp = (long *)va; | |
113 | if (lp[0] != -1 || lp[1] != -1 || lp[3] != -1 || lp[4] != -1) | |
114 | panic("malloc meddled"); | |
115 | } | |
d4202556 KM |
116 | #ifdef KMEMSTATS |
117 | kup = btokup(va); | |
118 | if (kup->ku_indx != indx) | |
119 | panic("malloc: wrong bucket"); | |
120 | if (kup->ku_freecnt == 0) | |
121 | panic("malloc: lost data"); | |
122 | kup->ku_freecnt--; | |
123 | kbp->kb_totalfree--; | |
fd78e9f6 | 124 | ksp->ks_memuse += 1 << indx; |
d4202556 KM |
125 | out: |
126 | kbp->kb_calls++; | |
127 | ksp->ks_inuse++; | |
128 | ksp->ks_calls++; | |
0a4aff4d KM |
129 | if (ksp->ks_memuse > ksp->ks_maxused) |
130 | ksp->ks_maxused = ksp->ks_memuse; | |
d4202556 KM |
131 | #else |
132 | out: | |
133 | #endif | |
c029fe44 | 134 | OUT; |
d4202556 KM |
135 | splx(s); |
136 | return ((qaddr_t)va); | |
137 | } | |
138 | ||
71029b66 KM |
139 | #ifdef DIAGNOSTIC |
140 | long addrmask[] = { 0x00000000, | |
141 | 0x00000001, 0x00000003, 0x00000007, 0x0000000f, | |
142 | 0x0000001f, 0x0000003f, 0x0000007f, 0x000000ff, | |
143 | 0x000001ff, 0x000003ff, 0x000007ff, 0x00000fff, | |
144 | 0x00001fff, 0x00003fff, 0x00007fff, 0x0000ffff, | |
145 | }; | |
146 | #endif /* DIAGNOSTIC */ | |
147 | ||
d4202556 KM |
148 | /* |
149 | * Free a block of memory allocated by malloc. | |
150 | */ | |
738ba0d6 KM |
151 | void |
152 | free(addr, type) | |
d4202556 | 153 | caddr_t addr; |
47516941 | 154 | int type; |
d4202556 KM |
155 | { |
156 | register struct kmembuckets *kbp; | |
157 | register struct kmemusage *kup; | |
47516941 MK |
158 | long alloc, size; |
159 | int s; | |
fd78e9f6 KM |
160 | #ifdef KMEMSTATS |
161 | register struct kmemstats *ksp = &kmemstats[type]; | |
162 | #endif | |
d4202556 KM |
163 | |
164 | kup = btokup(addr); | |
71029b66 KM |
165 | size = 1 << kup->ku_indx; |
166 | #ifdef DIAGNOSTIC | |
167 | if (size > NBPG * CLSIZE) | |
168 | alloc = addrmask[BUCKETINDX(NBPG * CLSIZE)]; | |
169 | else | |
170 | alloc = addrmask[kup->ku_indx]; | |
171 | if (((u_long)addr & alloc) != 0) { | |
172 | printf("free: unaligned addr 0x%x, size %d, type %d, mask %d\n", | |
173 | addr, size, type, alloc); | |
174 | panic("free: unaligned addr"); | |
175 | } | |
176 | #endif /* DIAGNOSTIC */ | |
738ba0d6 | 177 | kbp = &bucket[kup->ku_indx]; |
d4202556 | 178 | s = splimp(); |
c029fe44 | 179 | IN; |
0a4aff4d | 180 | if (size > MAXALLOCSAVE) { |
9d4095a1 | 181 | kmem_free(kmem_map, (vm_offset_t)addr, ctob(kup->ku_pagecnt)); |
d4202556 | 182 | #ifdef KMEMSTATS |
0a4aff4d KM |
183 | size = kup->ku_pagecnt << PGSHIFT; |
184 | ksp->ks_memuse -= size; | |
d4202556 KM |
185 | kup->ku_indx = 0; |
186 | kup->ku_pagecnt = 0; | |
0a4aff4d KM |
187 | if (ksp->ks_memuse + size >= ksp->ks_limit && |
188 | ksp->ks_memuse < ksp->ks_limit) | |
fd78e9f6 KM |
189 | wakeup((caddr_t)ksp); |
190 | ksp->ks_inuse--; | |
738ba0d6 | 191 | kbp->kb_total -= 1; |
d4202556 KM |
192 | #endif |
193 | splx(s); | |
194 | return; | |
195 | } | |
c029fe44 KS |
196 | if (size == 128) { |
197 | long *lp = (long *)addr; | |
198 | lp[0] = lp[1] = lp[3] = lp[4] = -1; | |
199 | } | |
d4202556 KM |
200 | #ifdef KMEMSTATS |
201 | kup->ku_freecnt++; | |
202 | if (kup->ku_freecnt >= kbp->kb_elmpercl) | |
203 | if (kup->ku_freecnt > kbp->kb_elmpercl) | |
204 | panic("free: multiple frees"); | |
205 | else if (kbp->kb_totalfree > kbp->kb_highwat) | |
206 | kbp->kb_couldfree++; | |
207 | kbp->kb_totalfree++; | |
0a4aff4d KM |
208 | ksp->ks_memuse -= size; |
209 | if (ksp->ks_memuse + size >= ksp->ks_limit && | |
210 | ksp->ks_memuse < ksp->ks_limit) | |
fd78e9f6 KM |
211 | wakeup((caddr_t)ksp); |
212 | ksp->ks_inuse--; | |
d4202556 | 213 | #endif |
c029fe44 | 214 | ((caddr_t *)addr)[2] = kbp->kb_next; |
d4202556 | 215 | kbp->kb_next = addr; |
c029fe44 | 216 | OUT; |
d4202556 KM |
217 | splx(s); |
218 | } | |
219 | ||
220 | /* | |
221 | * Initialize the kernel memory allocator | |
222 | */ | |
223 | kmeminit() | |
224 | { | |
225 | register long indx; | |
738ba0d6 | 226 | int npg; |
d4202556 | 227 | |
47516941 MK |
228 | #if ((MAXALLOCSAVE & (MAXALLOCSAVE - 1)) != 0) |
229 | ERROR!_kmeminit:_MAXALLOCSAVE_not_power_of_2 | |
230 | #endif | |
231 | #if (MAXALLOCSAVE > MINALLOCSIZE * 32768) | |
232 | ERROR!_kmeminit:_MAXALLOCSAVE_too_big | |
233 | #endif | |
234 | #if (MAXALLOCSAVE < CLBYTES) | |
235 | ERROR!_kmeminit:_MAXALLOCSAVE_too_small | |
236 | #endif | |
9d4095a1 KM |
237 | npg = VM_KMEM_SIZE/ NBPG; |
238 | kmemusage = (struct kmemusage *) kmem_alloc(kernel_map, | |
239 | (vm_size_t)(npg * sizeof(struct kmemusage))); | |
240 | kmem_map = kmem_suballoc(kernel_map, (vm_offset_t)&kmembase, | |
241 | (vm_offset_t)&kmemlimit, (vm_size_t)(npg * NBPG), FALSE); | |
d4202556 KM |
242 | #ifdef KMEMSTATS |
243 | for (indx = 0; indx < MINBUCKET + 16; indx++) { | |
244 | if (1 << indx >= CLBYTES) | |
245 | bucket[indx].kb_elmpercl = 1; | |
246 | else | |
247 | bucket[indx].kb_elmpercl = CLBYTES / (1 << indx); | |
248 | bucket[indx].kb_highwat = 5 * bucket[indx].kb_elmpercl; | |
249 | } | |
250 | for (indx = 0; indx < M_LAST; indx++) | |
5aeb6f6a | 251 | kmemstats[indx].ks_limit = npg * NBPG * 6 / 10; |
d4202556 KM |
252 | #endif |
253 | } |