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