![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to alloc.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSD / bin / csh|
Return to alloc.c CVS log | Up to [CSRG BSD Unix] / 43BSD / bin / csh |
1.1 ! root 1: /* ! 2: * Copyright (c) 1983 Regents of the University of California. ! 3: * All rights reserved. The Berkeley software License Agreement ! 4: * specifies the terms and conditions for redistribution. ! 5: */ ! 6: ! 7: #ifndef lint ! 8: /* From "@(#)malloc.c 5.5 (Berkeley) 2/25/86"; */ ! 9: static char *sccsid = "@(#)alloc.c 5.3 (Berkeley) 3/29/86"; ! 10: #endif not lint ! 11: ! 12: /* ! 13: * 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-10) bytes long. ! 20: * This is designed for use in a virtual memory environment. ! 21: */ ! 22: ! 23: #include <sys/types.h> ! 24: ! 25: #define NULL 0 ! 26: ! 27: /* ! 28: * The overhead on a block is at least 4 bytes. When free, this space ! 29: * contains a pointer to the next free block, and the bottom two bits must ! 30: * be zero. When in use, the first byte is set to MAGIC, and the second ! 31: * byte is the size index. The remaining bytes are for alignment. ! 32: * If range checking is enabled then a second word holds the size of the ! 33: * requested block, less 1, rounded up to a multiple of sizeof(RMAGIC). ! 34: * The order of elements is critical: ov_magic must overlay the low order ! 35: * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern. ! 36: */ ! 37: union overhead { ! 38: union overhead *ov_next; /* when free */ ! 39: struct { ! 40: u_char ovu_magic; /* magic number */ ! 41: u_char ovu_index; /* bucket # */ ! 42: #ifdef RCHECK ! 43: u_short ovu_rmagic; /* range magic number */ ! 44: u_int ovu_size; /* actual block size */ ! 45: #endif ! 46: } ovu; ! 47: #define ov_magic ovu.ovu_magic ! 48: #define ov_index ovu.ovu_index ! 49: #define ov_rmagic ovu.ovu_rmagic ! 50: #define ov_size ovu.ovu_size ! 51: }; ! 52: ! 53: #define MAGIC 0xef /* magic # on accounting info */ ! 54: #define RMAGIC 0x5555 /* magic # on range info */ ! 55: ! 56: #ifdef RCHECK ! 57: #define RSLOP sizeof (u_short) ! 58: #else ! 59: #define RSLOP 0 ! 60: #endif ! 61: ! 62: /* ! 63: * nextf[i] is the pointer to the next free block of size 2^(i+3). The ! 64: * smallest allocatable block is 8 bytes. The overhead information ! 65: * precedes the data area returned to the user. ! 66: */ ! 67: #define NBUCKETS 30 ! 68: static union overhead *nextf[NBUCKETS]; ! 69: extern char *sbrk(); ! 70: ! 71: static int pagesz; /* page size */ ! 72: static int pagebucket; /* page size bucket */ ! 73: ! 74: /* ! 75: * nmalloc[i] is the difference between the number of mallocs and frees ! 76: * for a given block size. ! 77: */ ! 78: static u_int nmalloc[NBUCKETS]; ! 79: ! 80: #if defined(DEBUG) || defined(RCHECK) ! 81: #define ASSERT(p) if (!(p)) botch("p") ! 82: static ! 83: botch(s) ! 84: char *s; ! 85: { ! 86: printf("\r\nassertion botched: %s\r\n", s); ! 87: abort(); ! 88: } ! 89: #else ! 90: #define ASSERT(p) ! 91: #endif ! 92: ! 93: char * ! 94: malloc(nbytes) ! 95: unsigned nbytes; ! 96: { ! 97: register union overhead *op; ! 98: register int bucket; ! 99: register unsigned amt, n; ! 100: ! 101: /* ! 102: * First time malloc is called, setup page size and ! 103: * align break pointer so all data will be page aligned. ! 104: */ ! 105: if (pagesz == 0) { ! 106: pagesz = n = getpagesize(); ! 107: op = (union overhead *)sbrk(0); ! 108: n = n - sizeof (*op) - ((int)op & (n - 1)); ! 109: if (n < 0) ! 110: n += pagesz; ! 111: if (n) { ! 112: if (sbrk(n) == (char *)-1) ! 113: return (NULL); ! 114: } ! 115: bucket = 0; ! 116: amt = 8; ! 117: while (pagesz > amt) { ! 118: amt <<= 1; ! 119: bucket++; ! 120: } ! 121: pagebucket = bucket; ! 122: } ! 123: /* ! 124: * Convert amount of memory requested into closest block size ! 125: * stored in hash buckets which satisfies request. ! 126: * Account for space used per block for accounting. ! 127: */ ! 128: if (nbytes <= (n = pagesz - sizeof (*op) - RSLOP)) { ! 129: #ifndef RCHECK ! 130: amt = 8; /* size of first bucket */ ! 131: bucket = 0; ! 132: #else ! 133: amt = 16; /* size of first bucket */ ! 134: bucket = 1; ! 135: #endif ! 136: n = -(sizeof (*op) + RSLOP); ! 137: } else { ! 138: amt = pagesz; ! 139: bucket = pagebucket; ! 140: } ! 141: while (nbytes > amt + n) { ! 142: amt <<= 1; ! 143: if (amt == 0) ! 144: return (NULL); ! 145: bucket++; ! 146: } ! 147: /* ! 148: * If nothing in hash bucket right now, ! 149: * request more memory from the system. ! 150: */ ! 151: if ((op = nextf[bucket]) == NULL) { ! 152: morecore(bucket); ! 153: if ((op = nextf[bucket]) == NULL) ! 154: return (NULL); ! 155: } ! 156: /* remove from linked list */ ! 157: nextf[bucket] = op->ov_next; ! 158: op->ov_magic = MAGIC; ! 159: op->ov_index = bucket; ! 160: nmalloc[bucket]++; ! 161: #ifdef RCHECK ! 162: /* ! 163: * Record allocated size of block and ! 164: * bound space with magic numbers. ! 165: */ ! 166: op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1); ! 167: op->ov_rmagic = RMAGIC; ! 168: *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC; ! 169: #endif ! 170: return ((char *)(op + 1)); ! 171: } ! 172: ! 173: /* ! 174: * Allocate more memory to the indicated bucket. ! 175: */ ! 176: morecore(bucket) ! 177: int bucket; ! 178: { ! 179: register union overhead *op; ! 180: register int sz; /* size of desired block */ ! 181: int amt; /* amount to allocate */ ! 182: int nblks; /* how many blocks we get */ ! 183: ! 184: /* ! 185: * sbrk_size <= 0 only for big, FLUFFY, requests (about ! 186: * 2^30 bytes on a VAX, I think) or for a negative arg. ! 187: */ ! 188: sz = 1 << (bucket + 3); ! 189: #ifdef DEBUG ! 190: ASSERT(sz > 0); ! 191: #else ! 192: if (sz <= 0) ! 193: return; ! 194: #endif ! 195: if (sz < pagesz) { ! 196: amt = pagesz; ! 197: nblks = amt / sz; ! 198: } else { ! 199: amt = sz + pagesz; ! 200: nblks = 1; ! 201: } ! 202: op = (union overhead *)sbrk(amt); ! 203: /* no more room! */ ! 204: if ((int)op == -1) ! 205: return; ! 206: /* ! 207: * Add new memory allocated to that on ! 208: * free list for this hash bucket. ! 209: */ ! 210: nextf[bucket] = op; ! 211: while (--nblks > 0) { ! 212: op->ov_next = (union overhead *)((caddr_t)op + sz); ! 213: op = (union overhead *)((caddr_t)op + sz); ! 214: } ! 215: } ! 216: ! 217: free(cp) ! 218: char *cp; ! 219: { ! 220: register int size; ! 221: register union overhead *op; ! 222: ! 223: if (cp == NULL) ! 224: return; ! 225: op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); ! 226: /* ! 227: * The following botch is because csh tries to free a free block ! 228: * when processing the =~ or !~ operators. -- layer@ucbmonet ! 229: */ ! 230: #ifdef CSHbotch /* was DEBUG */ ! 231: ASSERT(op->ov_magic == MAGIC); /* make sure it was in use */ ! 232: #else ! 233: if (op->ov_magic != MAGIC) ! 234: return; /* sanity */ ! 235: #endif ! 236: #ifdef RCHECK ! 237: ASSERT(op->ov_rmagic == RMAGIC); ! 238: ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC); ! 239: #endif ! 240: size = op->ov_index; ! 241: ASSERT(size < NBUCKETS); ! 242: op->ov_next = nextf[size]; /* also clobbers ov_magic */ ! 243: nextf[size] = op; ! 244: nmalloc[size]--; ! 245: } ! 246: ! 247: /* ! 248: * When a program attempts "storage compaction" as mentioned in the ! 249: * old malloc man page, it realloc's an already freed block. Usually ! 250: * this is the last block it freed; occasionally it might be farther ! 251: * back. We have to search all the free lists for the block in order ! 252: * to determine its bucket: 1st we make one pass thru the lists ! 253: * checking only the first block in each; if that fails we search ! 254: * ``realloc_srchlen'' blocks in each list for a match (the variable ! 255: * is extern so the caller can modify it). If that fails we just copy ! 256: * however many bytes was given to realloc() and hope it's not huge. ! 257: */ ! 258: int realloc_srchlen = 4; /* 4 should be plenty, -1 =>'s whole list */ ! 259: ! 260: char * ! 261: realloc(cp, nbytes) ! 262: char *cp; ! 263: unsigned nbytes; ! 264: { ! 265: register u_int onb, i; ! 266: union overhead *op; ! 267: char *res; ! 268: int was_alloced = 0; ! 269: ! 270: if (cp == NULL) ! 271: return (malloc(nbytes)); ! 272: op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); ! 273: if (op->ov_magic == MAGIC) { ! 274: was_alloced++; ! 275: i = op->ov_index; ! 276: } else { ! 277: /* ! 278: * Already free, doing "compaction". ! 279: * ! 280: * Search for the old block of memory on the ! 281: * free list. First, check the most common ! 282: * case (last element free'd), then (this failing) ! 283: * the last ``realloc_srchlen'' items free'd. ! 284: * If all lookups fail, then assume the size of ! 285: * the memory block being realloc'd is the ! 286: * largest possible (so that all "nbytes" of new ! 287: * memory are copied into). Note that this could cause ! 288: * a memory fault if the old area was tiny, and the moon ! 289: * is gibbous. However, that is very unlikely. ! 290: */ ! 291: if ((i = findbucket(op, 1)) < 0 && ! 292: (i = findbucket(op, realloc_srchlen)) < 0) ! 293: i = NBUCKETS; ! 294: } ! 295: onb = 1 << (i + 3); ! 296: if (onb < pagesz) ! 297: onb -= sizeof (*op) + RSLOP; ! 298: else ! 299: onb += pagesz - sizeof (*op) - RSLOP; ! 300: /* avoid the copy if same size block */ ! 301: if (was_alloced) { ! 302: if (i) { ! 303: i = 1 << (i + 2); ! 304: if (i < pagesz) ! 305: i -= sizeof (*op) + RSLOP; ! 306: else ! 307: i += pagesz - sizeof (*op) - RSLOP; ! 308: } ! 309: if (nbytes <= onb && nbytes > i) { ! 310: #ifdef RCHECK ! 311: op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1); ! 312: *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC; ! 313: #endif ! 314: return(cp); ! 315: } else ! 316: free(cp); ! 317: } ! 318: if ((res = malloc(nbytes)) == NULL) ! 319: return (NULL); ! 320: if (cp != res) /* common optimization if "compacting" */ ! 321: bcopy(cp, res, (nbytes < onb) ? nbytes : onb); ! 322: return (res); ! 323: } ! 324: ! 325: /* ! 326: * Search ``srchlen'' elements of each free list for a block whose ! 327: * header starts at ``freep''. If srchlen is -1 search the whole list. ! 328: * Return bucket number, or -1 if not found. ! 329: */ ! 330: static ! 331: findbucket(freep, srchlen) ! 332: union overhead *freep; ! 333: int srchlen; ! 334: { ! 335: register union overhead *p; ! 336: register int i, j; ! 337: ! 338: for (i = 0; i < NBUCKETS; i++) { ! 339: j = 0; ! 340: for (p = nextf[i]; p && j != srchlen; p = p->ov_next) { ! 341: if (p == freep) ! 342: return (i); ! 343: j++; ! 344: } ! 345: } ! 346: return (-1); ! 347: } ! 348: ! 349: /* ! 350: * mstats - print out statistics about malloc ! 351: * ! 352: * Prints two lines of numbers, one showing the length of the free list ! 353: * for each size category, the second showing the number of mallocs - ! 354: * frees for each size category. ! 355: */ ! 356: showall(s) ! 357: char **s; ! 358: { ! 359: register int i, j; ! 360: register union overhead *p; ! 361: int totfree = 0, ! 362: totused = 0; ! 363: ! 364: if (s[1]) ! 365: printf("Memory allocation statistics %s\nfree:", s[1]); ! 366: for (i = 0; i < NBUCKETS; i++) { ! 367: for (j = 0, p = nextf[i]; p; p = p->ov_next, j++) ! 368: ; ! 369: if (s[1]) ! 370: printf(" %d", j); ! 371: totfree += j * (1 << (i + 3)); ! 372: } ! 373: if (s[1]) ! 374: printf("\nused:"); ! 375: for (i = 0; i < NBUCKETS; i++) { ! 376: if (s[1]) ! 377: printf(" %d", nmalloc[i]); ! 378: totused += nmalloc[i] * (1 << (i + 3)); ! 379: } ! 380: if (s[1]) ! 381: printf("\n"); ! 382: printf("Total in use: %d, total free: %d\n", totused, totfree); ! 383: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.