Commit | Line | Data |
---|---|---|
ecc449eb KB |
1 | /*- |
2 | * Copyright (c) 1983, 1991 The Regents of the University of California. | |
3 | * All rights reserved. | |
4 | * | |
5 | * %sccs.include.redist.c% | |
b79f4fa9 DF |
6 | */ |
7 | ||
3fb44be6 | 8 | #ifndef lint |
6e37afca | 9 | static char sccsid[] = "@(#)alloc.c 5.6 (Berkeley) %G%"; |
ecc449eb KB |
10 | #endif /* not lint */ |
11 | ||
3fb44be6 | 12 | /* |
6e37afca | 13 | * tc.alloc.c from malloc.c (Caltech) 2/21/82 |
3fb44be6 KL |
14 | * Chris Kingsley, kingsley@cit-20. |
15 | * | |
6e37afca | 16 | * This is a very fast storage allocator. It allocates blocks of a small |
3fb44be6 | 17 | * number of different sizes, and keeps free lists of each size. Blocks that |
6e37afca KB |
18 | * don't exactly fit are passed up to the next larger size. In this |
19 | * implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long. | |
20 | * This is designed for use in a program that uses vast quantities of memory, | |
21 | * but bombs when it runs out. | |
3fb44be6 KL |
22 | */ |
23 | ||
6e37afca KB |
24 | #include "sh.h" |
25 | ||
26 | char *memtop = NULL; /* PWP: top of current memory */ | |
27 | char *membot = NULL; /* PWP: bottom of allocatable memory */ | |
28 | ||
29 | #ifndef SYSMALLOC | |
30 | ||
31 | #undef RCHECK | |
32 | #undef DEBUG | |
3fb44be6 | 33 | |
6e37afca KB |
34 | |
35 | #ifndef NULL | |
3fb44be6 | 36 | #define NULL 0 |
6e37afca KB |
37 | #endif |
38 | ||
39 | typedef unsigned char U_char; /* we don't really have signed chars */ | |
40 | typedef unsigned int U_int; | |
41 | typedef unsigned short U_short; | |
42 | static int findbucket(); | |
43 | static void morecore(); | |
3fb44be6 KL |
44 | |
45 | /* | |
46 | * The overhead on a block is at least 4 bytes. When free, this space | |
47 | * contains a pointer to the next free block, and the bottom two bits must | |
48 | * be zero. When in use, the first byte is set to MAGIC, and the second | |
49 | * byte is the size index. The remaining bytes are for alignment. | |
6e37afca KB |
50 | * If range checking is enabled and the size of the block fits |
51 | * in two bytes, then the top two bytes hold the size of the requested block | |
52 | * plus the range checking words, and the header word MINUS ONE. | |
3fb44be6 | 53 | */ |
6e37afca KB |
54 | |
55 | #ifdef SUNOS4 | |
56 | /* | |
57 | * SunOS localtime() overwrites the 9th byte on an 8 byte malloc().... | |
58 | * So we align to 16 bytes... | |
59 | */ | |
60 | #define ROUNDUP 15 | |
61 | #else | |
62 | #define ROUNDUP 7 | |
63 | #endif | |
64 | ||
65 | #define ALIGN(a) (((a) + ROUNDUP) & ~ROUNDUP) | |
66 | ||
67 | union overhead { | |
68 | union overhead *ov_next; /* when free */ | |
69 | struct { | |
70 | U_char ovu_magic; /* magic number */ | |
71 | U_char ovu_index; /* bucket # */ | |
3fb44be6 | 72 | #ifdef RCHECK |
6e37afca KB |
73 | U_short ovu_size; /* actual block size */ |
74 | U_int ovu_rmagic; /* range magic number */ | |
3fb44be6 | 75 | #endif |
6e37afca | 76 | } ovu; |
3fb44be6 KL |
77 | #define ov_magic ovu.ovu_magic |
78 | #define ov_index ovu.ovu_index | |
2914fb3a | 79 | #define ov_size ovu.ovu_size |
6e37afca | 80 | #define ov_rmagic ovu.ovu_rmagic |
3fb44be6 KL |
81 | }; |
82 | ||
6e37afca KB |
83 | #define MAGIC 0xfd /* magic # on accounting info */ |
84 | #define RMAGIC 0x55555555 /* magic # on range info */ | |
3fb44be6 | 85 | #ifdef RCHECK |
6e37afca | 86 | #define RSLOP sizeof (U_int) |
3fb44be6 KL |
87 | #else |
88 | #define RSLOP 0 | |
89 | #endif | |
90 | ||
91 | /* | |
92 | * nextf[i] is the pointer to the next free block of size 2^(i+3). The | |
93 | * smallest allocatable block is 8 bytes. The overhead information | |
94 | * precedes the data area returned to the user. | |
95 | */ | |
96 | #define NBUCKETS 30 | |
6e37afca | 97 | static union overhead *nextf[NBUCKETS]; |
3fb44be6 | 98 | |
6e37afca KB |
99 | #ifdef notdef |
100 | extern char *sbrk(); | |
101 | ||
102 | #endif | |
2914fb3a | 103 | |
3fb44be6 KL |
104 | /* |
105 | * nmalloc[i] is the difference between the number of mallocs and frees | |
106 | * for a given block size. | |
107 | */ | |
6e37afca | 108 | static U_int nmalloc[NBUCKETS]; |
fc71ebc6 | 109 | |
6e37afca KB |
110 | |
111 | #ifdef DEBUG | |
112 | #define CHECK(a, str, p) \ | |
113 | if (a) { \ | |
114 | xprintf(str, p); \ | |
115 | xprintf("memtop = %lx membot = %lx.\n", memtop, membot); \ | |
116 | abort(); \ | |
117 | } \ | |
118 | else | |
fc71ebc6 | 119 | #else |
6e37afca KB |
120 | #define CHECK(a, str, p) \ |
121 | if (a) { \ | |
122 | xprintf(str, p); \ | |
123 | xprintf("memtop = %lx membot = %lx.\n", memtop, membot); \ | |
124 | return; \ | |
125 | } \ | |
126 | else | |
fc71ebc6 BJ |
127 | #endif |
128 | ||
6e37afca | 129 | ptr_t |
fc71ebc6 | 130 | malloc(nbytes) |
6e37afca | 131 | register size_t nbytes; |
fc71ebc6 | 132 | { |
6e37afca KB |
133 | #ifndef lint |
134 | register union overhead *p; | |
135 | register int bucket = 0; | |
136 | register unsigned shiftr; | |
3fb44be6 | 137 | |
6e37afca KB |
138 | /* |
139 | * Convert amount of memory requested into closest block size stored in | |
140 | * hash buckets which satisfies request. Account for space used per block | |
141 | * for accounting. | |
142 | */ | |
143 | nbytes = ALIGN(ALIGN(sizeof(union overhead)) + nbytes + RSLOP); | |
144 | shiftr = (nbytes - 1) >> 2; | |
145 | ||
146 | /* apart from this loop, this is O(1) */ | |
147 | while (shiftr >>= 1) | |
148 | bucket++; | |
149 | /* | |
150 | * If nothing in hash bucket right now, request more memory from the | |
151 | * system. | |
152 | */ | |
153 | if (nextf[bucket] == NULL) | |
154 | morecore(bucket); | |
155 | if ((p = (union overhead *) nextf[bucket]) == NULL) { | |
156 | child++; | |
157 | #ifndef DEBUG | |
158 | stderror(ERR_NOMEM); | |
2914fb3a | 159 | #else |
6e37afca KB |
160 | showall(); |
161 | xprintf("nbytes=%d: Out of memory\n", nbytes); | |
162 | abort(); | |
2914fb3a | 163 | #endif |
6e37afca KB |
164 | /* fool lint */ |
165 | return ((ptr_t) 0); | |
166 | } | |
167 | /* remove from linked list */ | |
168 | nextf[bucket] = nextf[bucket]->ov_next; | |
169 | p->ov_magic = MAGIC; | |
170 | p->ov_index = bucket; | |
171 | nmalloc[bucket]++; | |
3fb44be6 | 172 | #ifdef RCHECK |
6e37afca KB |
173 | /* |
174 | * Record allocated size of block and bound space with magic numbers. | |
175 | */ | |
176 | if (nbytes <= 0x10000) | |
177 | p->ov_size = nbytes - 1; | |
178 | p->ov_rmagic = RMAGIC; | |
179 | *((U_int *) (((caddr_t) p) + nbytes - RSLOP)) = RMAGIC; | |
3fb44be6 | 180 | #endif |
6e37afca KB |
181 | return ((ptr_t) (((caddr_t) p) + ALIGN(sizeof(union overhead)))); |
182 | #else | |
183 | if (nbytes) | |
184 | return ((ptr_t) 0); | |
185 | else | |
186 | return ((ptr_t) 0); | |
187 | #endif /* !lint */ | |
fc71ebc6 BJ |
188 | } |
189 | ||
6e37afca | 190 | #ifndef lint |
3fb44be6 KL |
191 | /* |
192 | * Allocate more memory to the indicated bucket. | |
193 | */ | |
6e37afca | 194 | static void |
3fb44be6 | 195 | morecore(bucket) |
6e37afca | 196 | register bucket; |
fc71ebc6 | 197 | { |
6e37afca KB |
198 | register union overhead *op; |
199 | register int rnu; /* 2^rnu bytes will be requested */ | |
200 | register int nblks; /* become nblks blocks of the desired size */ | |
201 | register int siz; | |
3fb44be6 | 202 | |
6e37afca KB |
203 | if (nextf[bucket]) |
204 | return; | |
205 | /* | |
206 | * Insure memory is allocated on a page boundary. Should make getpageize | |
207 | * call? | |
208 | */ | |
209 | op = (union overhead *) sbrk(0); | |
210 | memtop = (char *) op; | |
211 | if (membot == NULL) | |
212 | membot = memtop; | |
213 | if ((int) op & 0x3ff) { | |
214 | memtop = (char *) sbrk(1024 - ((int) op & 0x3ff)); | |
215 | memtop += 1024 - ((int) op & 0x3ff); | |
216 | } | |
217 | ||
218 | /* take 2k unless the block is bigger than that */ | |
219 | rnu = (bucket <= 8) ? 11 : bucket + 3; | |
220 | nblks = 1 << (rnu - (bucket + 3)); /* how many blocks to get */ | |
221 | if (rnu < bucket) | |
222 | rnu = bucket; | |
223 | memtop = (char *) sbrk(1 << rnu); /* PWP */ | |
224 | op = (union overhead *) memtop; | |
225 | memtop += 1 << rnu; | |
226 | /* no more room! */ | |
227 | if ((int) op == -1) | |
228 | return; | |
229 | /* | |
230 | * Round up to minimum allocation size boundary and deduct from block count | |
231 | * to reflect. | |
232 | */ | |
233 | if (((U_int) op) & ROUNDUP) { | |
234 | op = (union overhead *) (((U_int) op + (ROUNDUP + 1)) & ~ROUNDUP); | |
235 | nblks--; | |
236 | } | |
237 | /* | |
238 | * Add new memory allocated to that on free list for this hash bucket. | |
239 | */ | |
240 | nextf[bucket] = op; | |
241 | siz = 1 << (bucket + 3); | |
242 | while (--nblks > 0) { | |
243 | op->ov_next = (union overhead *) (((caddr_t) op) + siz); | |
244 | op = (union overhead *) (((caddr_t) op) + siz); | |
245 | } | |
fc71ebc6 BJ |
246 | } |
247 | ||
6e37afca KB |
248 | #endif |
249 | ||
250 | #ifdef sun | |
251 | int | |
fc71ebc6 | 252 | #else |
6e37afca | 253 | void |
fc71ebc6 | 254 | #endif |
6e37afca KB |
255 | free(cp) |
256 | ptr_t cp; | |
257 | { | |
258 | #ifndef lint | |
259 | register int size; | |
260 | register union overhead *op; | |
261 | ||
262 | if (cp == NULL) | |
263 | return; | |
264 | CHECK(!memtop || !membot, "free(%lx) called before any allocations.", cp); | |
265 | CHECK(cp > (ptr_t) memtop, "free(%lx) above top of memory.", cp); | |
266 | CHECK(cp < (ptr_t) membot, "free(%lx) above top of memory.", cp); | |
267 | op = (union overhead *) (((caddr_t) cp) - ALIGN(sizeof(union overhead))); | |
268 | CHECK(op->ov_magic != MAGIC, "free(%lx) bad block.", cp); | |
269 | ||
3fb44be6 | 270 | #ifdef RCHECK |
6e37afca KB |
271 | if (op->ov_index <= 13) |
272 | CHECK(*(U_int *) ((caddr_t) op + op->ov_size + 1 - RSLOP) != RMAGIC, | |
273 | "free(%lx) bad range check.", cp); | |
274 | #endif | |
275 | CHECK(op->ov_index >= NBUCKETS, "free(%lx) bad block index.", cp); | |
276 | size = op->ov_index; | |
277 | op->ov_next = nextf[size]; | |
278 | nextf[size] = op; | |
279 | ||
280 | nmalloc[size]--; | |
281 | ||
282 | #else | |
283 | if (cp == NULL) | |
284 | return; | |
285 | #endif | |
286 | } | |
287 | ||
288 | ptr_t | |
289 | calloc(i, j) | |
290 | size_t i, j; | |
291 | { | |
292 | #ifndef lint | |
293 | register char *cp, *scp; | |
294 | ||
295 | i *= j; | |
296 | scp = cp = (char *) xmalloc((size_t) i); | |
297 | if (i != 0) | |
298 | do | |
299 | *cp++ = 0; | |
300 | while (--i); | |
301 | ||
302 | return (scp); | |
303 | #else | |
304 | if (i && j) | |
305 | return ((ptr_t) 0); | |
306 | else | |
307 | return ((ptr_t) 0); | |
3fb44be6 | 308 | #endif |
fc71ebc6 | 309 | } |
3fb44be6 KL |
310 | |
311 | /* | |
312 | * When a program attempts "storage compaction" as mentioned in the | |
313 | * old malloc man page, it realloc's an already freed block. Usually | |
314 | * this is the last block it freed; occasionally it might be farther | |
315 | * back. We have to search all the free lists for the block in order | |
316 | * to determine its bucket: 1st we make one pass thru the lists | |
317 | * checking only the first block in each; if that fails we search | |
318 | * ``realloc_srchlen'' blocks in each list for a match (the variable | |
319 | * is extern so the caller can modify it). If that fails we just copy | |
320 | * however many bytes was given to realloc() and hope it's not huge. | |
321 | */ | |
6e37afca KB |
322 | #ifndef lint |
323 | int realloc_srchlen = 4; /* 4 should be plenty, -1 =>'s whole list */ | |
324 | ||
325 | #endif /* lint */ | |
3fb44be6 | 326 | |
6e37afca | 327 | ptr_t |
3fb44be6 | 328 | realloc(cp, nbytes) |
6e37afca KB |
329 | ptr_t cp; |
330 | size_t nbytes; | |
331 | { | |
332 | #ifndef lint | |
333 | register U_int onb; | |
334 | union overhead *op; | |
335 | char *res; | |
336 | register int i; | |
337 | int was_alloced = 0; | |
338 | ||
339 | if (cp == NULL) | |
340 | return (malloc(nbytes)); | |
341 | op = (union overhead *) (((caddr_t) cp) - ALIGN(sizeof(union overhead))); | |
342 | if (op->ov_magic == MAGIC) { | |
343 | was_alloced++; | |
344 | i = op->ov_index; | |
345 | } | |
346 | else | |
347 | /* | |
348 | * Already free, doing "compaction". | |
349 | * | |
350 | * Search for the old block of memory on the free list. First, check the | |
351 | * most common case (last element free'd), then (this failing) the last | |
352 | * ``realloc_srchlen'' items free'd. If all lookups fail, then assume | |
353 | * the size of the memory block being realloc'd is the smallest | |
354 | * possible. | |
355 | */ | |
356 | if ((i = findbucket(op, 1)) < 0 && | |
357 | (i = findbucket(op, realloc_srchlen)) < 0) | |
358 | i = 0; | |
359 | ||
360 | onb = ALIGN(nbytes + ALIGN(sizeof(union overhead)) + RSLOP); | |
361 | ||
362 | /* avoid the copy if same size block */ | |
363 | if (was_alloced && (onb < (1 << (i + 3))) && (onb >= (1 << (i + 2)))) | |
364 | return ((ptr_t) cp); | |
365 | if ((res = malloc(nbytes)) == NULL) | |
366 | return ((ptr_t) 0); | |
367 | if (cp != res) /* common optimization */ | |
368 | bcopy(cp, res, nbytes); | |
369 | if (was_alloced) | |
370 | free(cp); | |
371 | return (res); | |
372 | #else | |
373 | if (cp && nbytes) | |
374 | return ((ptr_t) 0); | |
375 | else | |
376 | return ((ptr_t) 0); | |
377 | #endif /* !lint */ | |
3fb44be6 KL |
378 | } |
379 | ||
6e37afca KB |
380 | |
381 | ||
382 | #ifndef lint | |
3fb44be6 KL |
383 | /* |
384 | * Search ``srchlen'' elements of each free list for a block whose | |
385 | * header starts at ``freep''. If srchlen is -1 search the whole list. | |
386 | * Return bucket number, or -1 if not found. | |
387 | */ | |
6e37afca | 388 | static int |
3fb44be6 | 389 | findbucket(freep, srchlen) |
6e37afca KB |
390 | union overhead *freep; |
391 | int srchlen; | |
3fb44be6 | 392 | { |
6e37afca KB |
393 | register union overhead *p; |
394 | register int i, j; | |
395 | ||
396 | for (i = 0; i < NBUCKETS; i++) { | |
397 | j = 0; | |
398 | for (p = nextf[i]; p && j != srchlen; p = p->ov_next) { | |
399 | if (p == freep) | |
400 | return (i); | |
401 | j++; | |
2914fb3a | 402 | } |
6e37afca KB |
403 | } |
404 | return (-1); | |
3fb44be6 | 405 | } |
fc71ebc6 | 406 | |
6e37afca KB |
407 | #endif |
408 | ||
409 | ||
410 | #else /* SYSMALLOC */ | |
411 | ||
412 | /** | |
413 | ** ``Protected versions'' of malloc, realloc, calloc, and free | |
414 | ** | |
415 | ** On many systems: | |
416 | ** | |
417 | ** 1. malloc(0) is bad | |
418 | ** 2. free(0) is bad | |
419 | ** 3. realloc(0, n) is bad | |
420 | ** 4. realloc(n, 0) is bad | |
421 | ** | |
422 | ** Also we call our error routine if we run out of memory. | |
423 | **/ | |
424 | char * | |
425 | Malloc(n) | |
426 | size_t n; | |
427 | { | |
428 | ptr_t ptr; | |
429 | ||
430 | n = n ? n : 1; | |
431 | ||
432 | if ((ptr = malloc(n)) == (ptr_t) 0) { | |
433 | child++; | |
434 | stderror(ERR_NOMEM); | |
435 | } | |
436 | return ((char *) ptr); | |
437 | } | |
438 | ||
439 | char * | |
440 | Realloc(p, n) | |
441 | ptr_t p; | |
442 | size_t n; | |
443 | { | |
444 | ptr_t ptr; | |
445 | ||
446 | n = n ? n : 1; | |
447 | if ((ptr = (p ? realloc(p, n) : malloc(n))) == (ptr_t) 0) { | |
448 | child++; | |
449 | stderror(ERR_NOMEM); | |
450 | } | |
451 | return ((char *) ptr); | |
452 | } | |
453 | ||
454 | char * | |
455 | Calloc(s, n) | |
456 | size_t s, n; | |
457 | { | |
458 | char *sptr; | |
459 | ptr_t ptr; | |
460 | ||
461 | n *= s; | |
462 | n = n ? n : 1; | |
463 | if ((ptr = malloc(n)) == (ptr_t) 0) { | |
464 | child++; | |
465 | stderror(ERR_NOMEM); | |
466 | } | |
467 | ||
468 | sptr = (char *) ptr; | |
469 | if (n != 0) | |
470 | do | |
471 | *sptr++ = 0; | |
472 | while (--n); | |
473 | ||
474 | return ((char *) ptr); | |
475 | } | |
476 | ||
477 | void | |
478 | Free(p) | |
479 | ptr_t p; | |
480 | { | |
481 | if (p) | |
482 | free(p); | |
483 | } | |
484 | ||
485 | #endif /* SYSMALLOC */ | |
486 | ||
3fb44be6 KL |
487 | /* |
488 | * mstats - print out statistics about malloc | |
6e37afca | 489 | * |
3fb44be6 KL |
490 | * Prints two lines of numbers, one showing the length of the free list |
491 | * for each size category, the second showing the number of mallocs - | |
492 | * frees for each size category. | |
493 | */ | |
6e37afca KB |
494 | void |
495 | showall() | |
fc71ebc6 | 496 | { |
6e37afca KB |
497 | #ifndef SYSMALLOC |
498 | register int i, j; | |
499 | register union overhead *p; | |
500 | int totfree = 0, totused = 0; | |
501 | ||
502 | xprintf("csh current memory allocation:\nfree:\t"); | |
503 | for (i = 0; i < NBUCKETS; i++) { | |
504 | for (j = 0, p = nextf[i]; p; p = p->ov_next, j++); | |
505 | xprintf(" %4d", j); | |
506 | totfree += j * (1 << (i + 3)); | |
507 | } | |
508 | xprintf("\nused:\t"); | |
509 | for (i = 0; i < NBUCKETS; i++) { | |
510 | xprintf(" %4d", nmalloc[i]); | |
511 | totused += nmalloc[i] * (1 << (i + 3)); | |
512 | } | |
513 | xprintf("\n\tTotal in use: %d, total free: %d\n", | |
514 | totused, totfree); | |
515 | xprintf("\tAllocated memory from 0x%lx to 0x%lx. Real top at 0x%lx\n", | |
516 | membot, memtop, (char *) sbrk(0)); | |
517 | #else | |
518 | xprintf("Allocated memory from 0x%lx to 0x%lx (%ld).\n", | |
519 | membot, memtop = (char *) sbrk(0), memtop - membot); | |
520 | #endif /* SYSMALLOC */ | |
fc71ebc6 | 521 | } |