Commit | Line | Data |
---|---|---|
b79f4fa9 | 1 | /* |
2914fb3a JL |
2 | * Copyright (c) 1983 Regents of the University of California. |
3 | * All rights reserved. The Berkeley software License Agreement | |
b79f4fa9 DF |
4 | * specifies the terms and conditions for redistribution. |
5 | */ | |
6 | ||
3fb44be6 | 7 | #ifndef lint |
2914fb3a JL |
8 | /* From "@(#)malloc.c 5.5 (Berkeley) 2/25/86"; */ |
9 | static char *sccsid = "@(#)alloc.c 5.3 (Berkeley) %G%"; | |
10 | #endif not lint | |
3fb44be6 KL |
11 | |
12 | /* | |
13 | * malloc.c (Caltech) 2/21/82 | |
14 | * Chris Kingsley, kingsley@cit-20. | |
15 | * | |
16 | * This is a very fast storage allocator. It allocates blocks of a small | |
17 | * number of different sizes, and keeps free lists of each size. Blocks that | |
18 | * don't exactly fit are passed up to the next larger size. In this | |
2914fb3a JL |
19 | * implementation, the available sizes are 2^n-4 (or 2^n-10) bytes long. |
20 | * This is designed for use in a virtual memory environment. | |
3fb44be6 KL |
21 | */ |
22 | ||
23 | #include <sys/types.h> | |
24 | ||
25 | #define NULL 0 | |
26 | ||
27 | /* | |
28 | * The overhead on a block is at least 4 bytes. When free, this space | |
29 | * contains a pointer to the next free block, and the bottom two bits must | |
30 | * be zero. When in use, the first byte is set to MAGIC, and the second | |
31 | * byte is the size index. The remaining bytes are for alignment. | |
2914fb3a JL |
32 | * If range checking is enabled then a second word holds the size of the |
33 | * requested block, less 1, rounded up to a multiple of sizeof(RMAGIC). | |
34 | * The order of elements is critical: ov_magic must overlay the low order | |
35 | * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern. | |
3fb44be6 KL |
36 | */ |
37 | union overhead { | |
38 | union overhead *ov_next; /* when free */ | |
39 | struct { | |
40 | u_char ovu_magic; /* magic number */ | |
41 | u_char ovu_index; /* bucket # */ | |
42 | #ifdef RCHECK | |
2914fb3a JL |
43 | u_short ovu_rmagic; /* range magic number */ |
44 | u_int ovu_size; /* actual block size */ | |
3fb44be6 KL |
45 | #endif |
46 | } ovu; | |
47 | #define ov_magic ovu.ovu_magic | |
48 | #define ov_index ovu.ovu_index | |
3fb44be6 | 49 | #define ov_rmagic ovu.ovu_rmagic |
2914fb3a | 50 | #define ov_size ovu.ovu_size |
3fb44be6 KL |
51 | }; |
52 | ||
2914fb3a JL |
53 | #define MAGIC 0xef /* magic # on accounting info */ |
54 | #define RMAGIC 0x5555 /* magic # on range info */ | |
55 | ||
3fb44be6 | 56 | #ifdef RCHECK |
2914fb3a | 57 | #define RSLOP sizeof (u_short) |
3fb44be6 KL |
58 | #else |
59 | #define RSLOP 0 | |
60 | #endif | |
61 | ||
62 | /* | |
63 | * nextf[i] is the pointer to the next free block of size 2^(i+3). The | |
64 | * smallest allocatable block is 8 bytes. The overhead information | |
65 | * precedes the data area returned to the user. | |
66 | */ | |
67 | #define NBUCKETS 30 | |
68 | static union overhead *nextf[NBUCKETS]; | |
69 | extern char *sbrk(); | |
70 | ||
2914fb3a JL |
71 | static int pagesz; /* page size */ |
72 | static int pagebucket; /* page size bucket */ | |
73 | ||
3fb44be6 KL |
74 | /* |
75 | * nmalloc[i] is the difference between the number of mallocs and frees | |
76 | * for a given block size. | |
77 | */ | |
78 | static u_int nmalloc[NBUCKETS]; | |
fc71ebc6 | 79 | |
2914fb3a JL |
80 | #if defined(DEBUG) || defined(RCHECK) |
81 | #define ASSERT(p) if (!(p)) botch("p") | |
3fb44be6 | 82 | static |
fc71ebc6 | 83 | botch(s) |
2914fb3a | 84 | char *s; |
fc71ebc6 | 85 | { |
2914fb3a | 86 | printf("\r\nassertion botched: %s\r\n", s); |
fc71ebc6 BJ |
87 | abort(); |
88 | } | |
89 | #else | |
3fb44be6 | 90 | #define ASSERT(p) |
fc71ebc6 BJ |
91 | #endif |
92 | ||
fc71ebc6 BJ |
93 | char * |
94 | malloc(nbytes) | |
2914fb3a | 95 | unsigned nbytes; |
fc71ebc6 | 96 | { |
2914fb3a JL |
97 | register union overhead *op; |
98 | register int bucket; | |
99 | register unsigned amt, n; | |
3fb44be6 KL |
100 | |
101 | /* | |
2914fb3a JL |
102 | * First time malloc is called, setup page size and |
103 | * align break pointer so all data will be page aligned. | |
3fb44be6 | 104 | */ |
2914fb3a JL |
105 | if (pagesz == 0) { |
106 | pagesz = n = getpagesize(); | |
107 | op = (union overhead *)sbrk(0); | |
108 | n = n - sizeof (*op) - ((int)op & (n - 1)); | |
109 | if (n < 0) | |
110 | n += pagesz; | |
111 | if (n) { | |
112 | if (sbrk(n) == (char *)-1) | |
113 | return (NULL); | |
114 | } | |
115 | bucket = 0; | |
116 | amt = 8; | |
117 | while (pagesz > amt) { | |
118 | amt <<= 1; | |
119 | bucket++; | |
120 | } | |
121 | pagebucket = bucket; | |
122 | } | |
123 | /* | |
124 | * Convert amount of memory requested into closest block size | |
125 | * stored in hash buckets which satisfies request. | |
126 | * Account for space used per block for accounting. | |
127 | */ | |
128 | if (nbytes <= (n = pagesz - sizeof (*op) - RSLOP)) { | |
129 | #ifndef RCHECK | |
130 | amt = 8; /* size of first bucket */ | |
131 | bucket = 0; | |
132 | #else | |
133 | amt = 16; /* size of first bucket */ | |
134 | bucket = 1; | |
135 | #endif | |
136 | n = -(sizeof (*op) + RSLOP); | |
137 | } else { | |
138 | amt = pagesz; | |
139 | bucket = pagebucket; | |
140 | } | |
141 | while (nbytes > amt + n) { | |
142 | amt <<= 1; | |
143 | if (amt == 0) | |
144 | return (NULL); | |
145 | bucket++; | |
146 | } | |
3fb44be6 KL |
147 | /* |
148 | * If nothing in hash bucket right now, | |
149 | * request more memory from the system. | |
150 | */ | |
2914fb3a | 151 | if ((op = nextf[bucket]) == NULL) { |
3fb44be6 | 152 | morecore(bucket); |
2914fb3a JL |
153 | if ((op = nextf[bucket]) == NULL) |
154 | return (NULL); | |
155 | } | |
3fb44be6 | 156 | /* remove from linked list */ |
2914fb3a JL |
157 | nextf[bucket] = op->ov_next; |
158 | op->ov_magic = MAGIC; | |
159 | op->ov_index = bucket; | |
3fb44be6 | 160 | nmalloc[bucket]++; |
3fb44be6 KL |
161 | #ifdef RCHECK |
162 | /* | |
163 | * Record allocated size of block and | |
164 | * bound space with magic numbers. | |
165 | */ | |
2914fb3a JL |
166 | op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1); |
167 | op->ov_rmagic = RMAGIC; | |
168 | *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC; | |
3fb44be6 | 169 | #endif |
2914fb3a | 170 | return ((char *)(op + 1)); |
fc71ebc6 BJ |
171 | } |
172 | ||
3fb44be6 KL |
173 | /* |
174 | * Allocate more memory to the indicated bucket. | |
175 | */ | |
3fb44be6 | 176 | morecore(bucket) |
2914fb3a | 177 | int bucket; |
fc71ebc6 | 178 | { |
3fb44be6 | 179 | register union overhead *op; |
2914fb3a JL |
180 | register int sz; /* size of desired block */ |
181 | int amt; /* amount to allocate */ | |
182 | int nblks; /* how many blocks we get */ | |
3fb44be6 | 183 | |
3fb44be6 | 184 | /* |
2914fb3a JL |
185 | * sbrk_size <= 0 only for big, FLUFFY, requests (about |
186 | * 2^30 bytes on a VAX, I think) or for a negative arg. | |
3fb44be6 | 187 | */ |
2914fb3a JL |
188 | sz = 1 << (bucket + 3); |
189 | #ifdef DEBUG | |
190 | ASSERT(sz > 0); | |
191 | #else | |
192 | if (sz <= 0) | |
193 | return; | |
194 | #endif | |
195 | if (sz < pagesz) { | |
196 | amt = pagesz; | |
197 | nblks = amt / sz; | |
198 | } else { | |
199 | amt = sz + pagesz; | |
200 | nblks = 1; | |
201 | } | |
202 | op = (union overhead *)sbrk(amt); | |
3fb44be6 KL |
203 | /* no more room! */ |
204 | if ((int)op == -1) | |
205 | return; | |
3fb44be6 KL |
206 | /* |
207 | * Add new memory allocated to that on | |
208 | * free list for this hash bucket. | |
209 | */ | |
210 | nextf[bucket] = op; | |
3fb44be6 | 211 | while (--nblks > 0) { |
2914fb3a JL |
212 | op->ov_next = (union overhead *)((caddr_t)op + sz); |
213 | op = (union overhead *)((caddr_t)op + sz); | |
3fb44be6 | 214 | } |
fc71ebc6 BJ |
215 | } |
216 | ||
3fb44be6 KL |
217 | free(cp) |
218 | char *cp; | |
219 | { | |
220 | register int size; | |
221 | register union overhead *op; | |
fc71ebc6 | 222 | |
3fb44be6 KL |
223 | if (cp == NULL) |
224 | return; | |
225 | op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); | |
3fb44be6 | 226 | /* |
2914fb3a JL |
227 | * The following botch is because csh tries to free a free block |
228 | * when processing the =~ or !~ operators. -- layer@ucbmonet | |
3fb44be6 | 229 | */ |
2914fb3a | 230 | #ifdef CSHbotch /* was DEBUG */ |
3fb44be6 | 231 | ASSERT(op->ov_magic == MAGIC); /* make sure it was in use */ |
fc71ebc6 | 232 | #else |
3fb44be6 KL |
233 | if (op->ov_magic != MAGIC) |
234 | return; /* sanity */ | |
fc71ebc6 | 235 | #endif |
3fb44be6 KL |
236 | #ifdef RCHECK |
237 | ASSERT(op->ov_rmagic == RMAGIC); | |
2914fb3a | 238 | ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC); |
3fb44be6 | 239 | #endif |
3fb44be6 | 240 | size = op->ov_index; |
2914fb3a JL |
241 | ASSERT(size < NBUCKETS); |
242 | op->ov_next = nextf[size]; /* also clobbers ov_magic */ | |
3fb44be6 | 243 | nextf[size] = op; |
3fb44be6 | 244 | nmalloc[size]--; |
fc71ebc6 | 245 | } |
3fb44be6 KL |
246 | |
247 | /* | |
248 | * When a program attempts "storage compaction" as mentioned in the | |
249 | * old malloc man page, it realloc's an already freed block. Usually | |
250 | * this is the last block it freed; occasionally it might be farther | |
251 | * back. We have to search all the free lists for the block in order | |
252 | * to determine its bucket: 1st we make one pass thru the lists | |
253 | * checking only the first block in each; if that fails we search | |
254 | * ``realloc_srchlen'' blocks in each list for a match (the variable | |
255 | * is extern so the caller can modify it). If that fails we just copy | |
256 | * however many bytes was given to realloc() and hope it's not huge. | |
257 | */ | |
2914fb3a | 258 | int realloc_srchlen = 4; /* 4 should be plenty, -1 =>'s whole list */ |
3fb44be6 KL |
259 | |
260 | char * | |
261 | realloc(cp, nbytes) | |
262 | char *cp; | |
263 | unsigned nbytes; | |
264 | { | |
2914fb3a | 265 | register u_int onb, i; |
3fb44be6 KL |
266 | union overhead *op; |
267 | char *res; | |
3fb44be6 KL |
268 | int was_alloced = 0; |
269 | ||
270 | if (cp == NULL) | |
271 | return (malloc(nbytes)); | |
272 | op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); | |
273 | if (op->ov_magic == MAGIC) { | |
274 | was_alloced++; | |
275 | i = op->ov_index; | |
2914fb3a JL |
276 | } else { |
277 | /* | |
278 | * Already free, doing "compaction". | |
279 | * | |
280 | * Search for the old block of memory on the | |
281 | * free list. First, check the most common | |
282 | * case (last element free'd), then (this failing) | |
283 | * the last ``realloc_srchlen'' items free'd. | |
284 | * If all lookups fail, then assume the size of | |
285 | * the memory block being realloc'd is the | |
286 | * largest possible (so that all "nbytes" of new | |
287 | * memory are copied into). Note that this could cause | |
288 | * a memory fault if the old area was tiny, and the moon | |
289 | * is gibbous. However, that is very unlikely. | |
290 | */ | |
3fb44be6 KL |
291 | if ((i = findbucket(op, 1)) < 0 && |
292 | (i = findbucket(op, realloc_srchlen)) < 0) | |
2914fb3a JL |
293 | i = NBUCKETS; |
294 | } | |
295 | onb = 1 << (i + 3); | |
296 | if (onb < pagesz) | |
297 | onb -= sizeof (*op) + RSLOP; | |
298 | else | |
299 | onb += pagesz - sizeof (*op) - RSLOP; | |
300 | /* avoid the copy if same size block */ | |
301 | if (was_alloced) { | |
302 | if (i) { | |
303 | i = 1 << (i + 2); | |
304 | if (i < pagesz) | |
305 | i -= sizeof (*op) + RSLOP; | |
306 | else | |
307 | i += pagesz - sizeof (*op) - RSLOP; | |
308 | } | |
309 | if (nbytes <= onb && nbytes > i) { | |
310 | #ifdef RCHECK | |
311 | op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1); | |
312 | *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC; | |
313 | #endif | |
314 | return(cp); | |
315 | } else | |
316 | free(cp); | |
3fb44be6 | 317 | } |
3fb44be6 KL |
318 | if ((res = malloc(nbytes)) == NULL) |
319 | return (NULL); | |
2914fb3a | 320 | if (cp != res) /* common optimization if "compacting" */ |
3fb44be6 | 321 | bcopy(cp, res, (nbytes < onb) ? nbytes : onb); |
3fb44be6 KL |
322 | return (res); |
323 | } | |
324 | ||
325 | /* | |
326 | * Search ``srchlen'' elements of each free list for a block whose | |
327 | * header starts at ``freep''. If srchlen is -1 search the whole list. | |
328 | * Return bucket number, or -1 if not found. | |
329 | */ | |
330 | static | |
331 | findbucket(freep, srchlen) | |
2914fb3a JL |
332 | union overhead *freep; |
333 | int srchlen; | |
3fb44be6 KL |
334 | { |
335 | register union overhead *p; | |
336 | register int i, j; | |
337 | ||
2914fb3a JL |
338 | for (i = 0; i < NBUCKETS; i++) { |
339 | j = 0; | |
340 | for (p = nextf[i]; p && j != srchlen; p = p->ov_next) { | |
3fb44be6 KL |
341 | if (p == freep) |
342 | return (i); | |
2914fb3a JL |
343 | j++; |
344 | } | |
345 | } | |
3fb44be6 KL |
346 | return (-1); |
347 | } | |
fc71ebc6 | 348 | |
3fb44be6 KL |
349 | /* |
350 | * mstats - print out statistics about malloc | |
351 | * | |
352 | * Prints two lines of numbers, one showing the length of the free list | |
353 | * for each size category, the second showing the number of mallocs - | |
354 | * frees for each size category. | |
355 | */ | |
356 | showall(s) | |
35371dec | 357 | char **s; |
fc71ebc6 | 358 | { |
35371dec EW |
359 | register int i, j; |
360 | register union overhead *p; | |
361 | int totfree = 0, | |
362 | totused = 0; | |
3fb44be6 KL |
363 | |
364 | if (s[1]) | |
35371dec EW |
365 | printf("Memory allocation statistics %s\nfree:", s[1]); |
366 | for (i = 0; i < NBUCKETS; i++) { | |
367 | for (j = 0, p = nextf[i]; p; p = p->ov_next, j++) | |
368 | ; | |
35371dec EW |
369 | if (s[1]) |
370 | printf(" %d", j); | |
371 | totfree += j * (1 << (i + 3)); | |
372 | } | |
3fb44be6 | 373 | if (s[1]) |
35371dec EW |
374 | printf("\nused:"); |
375 | for (i = 0; i < NBUCKETS; i++) { | |
376 | if (s[1]) | |
377 | printf(" %d", nmalloc[i]); | |
378 | totused += nmalloc[i] * (1 << (i + 3)); | |
379 | } | |
3fb44be6 | 380 | if (s[1]) |
35371dec EW |
381 | printf("\n"); |
382 | printf("Total in use: %d, total free: %d\n", totused, totfree); | |
fc71ebc6 | 383 | } |