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