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.8 (Berkeley) 06/08/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 xprintf(str, p); \ 110 xprintf("memtop = %lx membot = %lx.\n", memtop, membot); \ 111 abort(); \ 112 } \ 113 else 114 #else 115 #define CHECK(a, str, p) \ 116 if (a) { \ 117 xprintf(str, p); \ 118 xprintf("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 xprintf("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 #ifdef sun 246 int 247 #else 248 void 249 #endif 250 free(cp) 251 ptr_t cp; 252 { 253 #ifndef lint 254 register int size; 255 register union overhead *op; 256 257 if (cp == NULL) 258 return; 259 CHECK(!memtop || !membot, "free(%lx) called before any allocations.", cp); 260 CHECK(cp > (ptr_t) memtop, "free(%lx) above top of memory.", cp); 261 CHECK(cp < (ptr_t) membot, "free(%lx) above top of memory.", cp); 262 op = (union overhead *) (((caddr_t) cp) - ALIGN(sizeof(union overhead))); 263 CHECK(op->ov_magic != MAGIC, "free(%lx) bad block.", cp); 264 265 #ifdef RCHECK 266 if (op->ov_index <= 13) 267 CHECK(*(u_int *) ((caddr_t) op + op->ov_size + 1 - RSLOP) != RMAGIC, 268 "free(%lx) bad range check.", cp); 269 #endif 270 CHECK(op->ov_index >= NBUCKETS, "free(%lx) bad block index.", cp); 271 size = op->ov_index; 272 op->ov_next = nextf[size]; 273 nextf[size] = op; 274 275 nmalloc[size]--; 276 277 #else 278 if (cp == NULL) 279 return; 280 #endif 281 } 282 283 ptr_t 284 calloc(i, j) 285 size_t i, j; 286 { 287 #ifndef lint 288 register char *cp, *scp; 289 290 i *= j; 291 scp = cp = (char *) xmalloc((size_t) i); 292 if (i != 0) 293 do 294 *cp++ = 0; 295 while (--i); 296 297 return (scp); 298 #else 299 if (i && j) 300 return ((ptr_t) 0); 301 else 302 return ((ptr_t) 0); 303 #endif 304 } 305 306 /* 307 * When a program attempts "storage compaction" as mentioned in the 308 * old malloc man page, it realloc's an already freed block. Usually 309 * this is the last block it freed; occasionally it might be farther 310 * back. We have to search all the free lists for the block in order 311 * to determine its bucket: 1st we make one pass thru the lists 312 * checking only the first block in each; if that fails we search 313 * ``realloc_srchlen'' blocks in each list for a match (the variable 314 * is extern so the caller can modify it). If that fails we just copy 315 * however many bytes was given to realloc() and hope it's not huge. 316 */ 317 #ifndef lint 318 int realloc_srchlen = 4; /* 4 should be plenty, -1 =>'s whole list */ 319 320 #endif /* lint */ 321 322 ptr_t 323 realloc(cp, nbytes) 324 ptr_t cp; 325 size_t nbytes; 326 { 327 #ifndef lint 328 register u_int onb; 329 union overhead *op; 330 char *res; 331 register int i; 332 int was_alloced = 0; 333 334 if (cp == NULL) 335 return (malloc(nbytes)); 336 op = (union overhead *) (((caddr_t) cp) - ALIGN(sizeof(union overhead))); 337 if (op->ov_magic == MAGIC) { 338 was_alloced++; 339 i = op->ov_index; 340 } 341 else 342 /* 343 * Already free, doing "compaction". 344 * 345 * Search for the old block of memory on the free list. First, check the 346 * most common case (last element free'd), then (this failing) the last 347 * ``realloc_srchlen'' items free'd. If all lookups fail, then assume 348 * the size of the memory block being realloc'd is the smallest 349 * possible. 350 */ 351 if ((i = findbucket(op, 1)) < 0 && 352 (i = findbucket(op, realloc_srchlen)) < 0) 353 i = 0; 354 355 onb = ALIGN(nbytes + ALIGN(sizeof(union overhead)) + RSLOP); 356 357 /* avoid the copy if same size block */ 358 if (was_alloced && (onb < (1 << (i + 3))) && (onb >= (1 << (i + 2)))) 359 return ((ptr_t) cp); 360 if ((res = malloc(nbytes)) == NULL) 361 return ((ptr_t) 0); 362 if (cp != res) /* common optimization */ 363 bcopy(cp, res, nbytes); 364 if (was_alloced) 365 free(cp); 366 return (res); 367 #else 368 if (cp && nbytes) 369 return ((ptr_t) 0); 370 else 371 return ((ptr_t) 0); 372 #endif /* !lint */ 373 } 374 375 376 377 #ifndef lint 378 /* 379 * Search ``srchlen'' elements of each free list for a block whose 380 * header starts at ``freep''. If srchlen is -1 search the whole list. 381 * Return bucket number, or -1 if not found. 382 */ 383 static int 384 findbucket(freep, srchlen) 385 union overhead *freep; 386 int srchlen; 387 { 388 register union overhead *p; 389 register int i, j; 390 391 for (i = 0; i < NBUCKETS; i++) { 392 j = 0; 393 for (p = nextf[i]; p && j != srchlen; p = p->ov_next) { 394 if (p == freep) 395 return (i); 396 j++; 397 } 398 } 399 return (-1); 400 } 401 402 #endif 403 404 405 #else /* SYSMALLOC */ 406 407 /** 408 ** ``Protected versions'' of malloc, realloc, calloc, and free 409 ** 410 ** On many systems: 411 ** 412 ** 1. malloc(0) is bad 413 ** 2. free(0) is bad 414 ** 3. realloc(0, n) is bad 415 ** 4. realloc(n, 0) is bad 416 ** 417 ** Also we call our error routine if we run out of memory. 418 **/ 419 char * 420 Malloc(n) 421 size_t n; 422 { 423 ptr_t ptr; 424 425 n = n ? n : 1; 426 427 if ((ptr = malloc(n)) == (ptr_t) 0) { 428 child++; 429 stderror(ERR_NOMEM); 430 } 431 return ((char *) ptr); 432 } 433 434 char * 435 Realloc(p, n) 436 ptr_t p; 437 size_t n; 438 { 439 ptr_t ptr; 440 441 n = n ? n : 1; 442 if ((ptr = (p ? realloc(p, n) : malloc(n))) == (ptr_t) 0) { 443 child++; 444 stderror(ERR_NOMEM); 445 } 446 return ((char *) ptr); 447 } 448 449 char * 450 Calloc(s, n) 451 size_t s, n; 452 { 453 char *sptr; 454 ptr_t ptr; 455 456 n *= s; 457 n = n ? n : 1; 458 if ((ptr = malloc(n)) == (ptr_t) 0) { 459 child++; 460 stderror(ERR_NOMEM); 461 } 462 463 sptr = (char *) ptr; 464 if (n != 0) 465 do 466 *sptr++ = 0; 467 while (--n); 468 469 return ((char *) ptr); 470 } 471 472 void 473 Free(p) 474 ptr_t p; 475 { 476 if (p) 477 free(p); 478 } 479 480 #endif /* SYSMALLOC */ 481 482 /* 483 * mstats - print out statistics about malloc 484 * 485 * Prints two lines of numbers, one showing the length of the free list 486 * for each size category, the second showing the number of mallocs - 487 * frees for each size category. 488 */ 489 void 490 showall() 491 { 492 #ifndef SYSMALLOC 493 register int i, j; 494 register union overhead *p; 495 int totfree = 0, totused = 0; 496 497 xprintf("csh current memory allocation:\nfree:\t"); 498 for (i = 0; i < NBUCKETS; i++) { 499 for (j = 0, p = nextf[i]; p; p = p->ov_next, j++); 500 xprintf(" %4d", j); 501 totfree += j * (1 << (i + 3)); 502 } 503 xprintf("\nused:\t"); 504 for (i = 0; i < NBUCKETS; i++) { 505 xprintf(" %4d", nmalloc[i]); 506 totused += nmalloc[i] * (1 << (i + 3)); 507 } 508 xprintf("\n\tTotal in use: %d, total free: %d\n", 509 totused, totfree); 510 xprintf("\tAllocated memory from 0x%lx to 0x%lx. Real top at 0x%lx\n", 511 membot, memtop, (char *) sbrk(0)); 512 #else 513 xprintf("Allocated memory from 0x%lx to 0x%lx (%ld).\n", 514 membot, memtop = (char *) sbrk(0), memtop - membot); 515 #endif /* SYSMALLOC */ 516 } 517