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