1 /*- 2 * Copyright (c) 1983, 1991 The Regents of the University of California. 3 * All rights reserved. 4 * 5 * %sccs.include.redist.c% 6 */ 7 8 #ifndef lint 9 static char sccsid[] = "@(#)alloc.c 5.7 (Berkeley) 06/07/91"; 10 #endif /* not lint */ 11 12 /* 13 * tc.alloc.c from 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 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. 22 */ 23 24 #include "csh.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 33 34 35 #ifndef NULL 36 #define NULL 0 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(); 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. 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. 53 */ 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 # */ 72 #ifdef RCHECK 73 U_short ovu_size; /* actual block size */ 74 U_int ovu_rmagic; /* range magic number */ 75 #endif 76 } ovu; 77 #define ov_magic ovu.ovu_magic 78 #define ov_index ovu.ovu_index 79 #define ov_size ovu.ovu_size 80 #define ov_rmagic ovu.ovu_rmagic 81 }; 82 83 #define MAGIC 0xfd /* magic # on accounting info */ 84 #define RMAGIC 0x55555555 /* magic # on range info */ 85 #ifdef RCHECK 86 #define RSLOP sizeof (U_int) 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 97 static union overhead *nextf[NBUCKETS]; 98 99 #ifdef notdef 100 extern char *sbrk(); 101 102 #endif 103 104 /* 105 * nmalloc[i] is the difference between the number of mallocs and frees 106 * for a given block size. 107 */ 108 static U_int nmalloc[NBUCKETS]; 109 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 119 #else 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 127 #endif 128 129 ptr_t 130 malloc(nbytes) 131 register size_t nbytes; 132 { 133 #ifndef lint 134 register union overhead *p; 135 register int bucket = 0; 136 register unsigned shiftr; 137 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); 159 #else 160 showall(); 161 xprintf("nbytes=%d: Out of memory\n", nbytes); 162 abort(); 163 #endif 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]++; 172 #ifdef RCHECK 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; 180 #endif 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 */ 188 } 189 190 #ifndef lint 191 /* 192 * Allocate more memory to the indicated bucket. 193 */ 194 static void 195 morecore(bucket) 196 register bucket; 197 { 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; 202 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 } 246 } 247 248 #endif 249 250 #ifdef sun 251 int 252 #else 253 void 254 #endif 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 270 #ifdef RCHECK 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); 308 #endif 309 } 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 */ 322 #ifndef lint 323 int realloc_srchlen = 4; /* 4 should be plenty, -1 =>'s whole list */ 324 325 #endif /* lint */ 326 327 ptr_t 328 realloc(cp, nbytes) 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 */ 378 } 379 380 381 382 #ifndef lint 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 */ 388 static int 389 findbucket(freep, srchlen) 390 union overhead *freep; 391 int srchlen; 392 { 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++; 402 } 403 } 404 return (-1); 405 } 406 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 487 /* 488 * mstats - print out statistics about malloc 489 * 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 */ 494 void 495 showall() 496 { 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 */ 521 } 522