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