Annotation of src/usr.bin/patch/malloc.c, Revision 1.1
1.1 ! deraadt 1: /*
! 2: * from: @(#)nmalloc.c 1 (Caltech) 2/21/82
! 3: * $Id: malloc.c,v 1.2 1993/08/01 18:10:10 mycroft Exp $
! 4: *
! 5: * U of M Modified: 20 Jun 1983 ACT: strange hacks for Emacs
! 6: *
! 7: * Nov 1983, Mike@BRL, Added support for 4.1C/4.2 BSD.
! 8: *
! 9: * This is a very fast storage allocator. It allocates blocks of a small
! 10: * number of different sizes, and keeps free lists of each size. Blocks
! 11: * that don't exactly fit are passed up to the next larger size. In this
! 12: * implementation, the available sizes are (2^n)-4 (or -16) bytes long.
! 13: * This is designed for use in a program that uses vast quantities of
! 14: * memory, but bombs when it runs out. To make it a little better, it
! 15: * warns the user when he starts to get near the end.
! 16: *
! 17: * June 84, ACT: modified rcheck code to check the range given to malloc,
! 18: * rather than the range determined by the 2-power used.
! 19: *
! 20: * Jan 85, RMS: calls malloc_warning to issue warning on nearly full.
! 21: * No longer Emacs-specific; can serve as all-purpose malloc for GNU.
! 22: * You should call malloc_init to reinitialize after loading dumped Emacs.
! 23: * Call malloc_stats to get info on memory stats if MSTATS turned on.
! 24: * realloc knows how to return same block given, just changing its size,
! 25: * if the power of 2 is correct.
! 26: */
! 27:
! 28: /*
! 29: * nextf[i] is the pointer to the next free block of size 2^(i+3). The
! 30: * smallest allocatable block is 8 bytes. The overhead information will
! 31: * go in the first int of the block, and the returned pointer will point
! 32: * to the second.
! 33: *
! 34: #ifdef MSTATS
! 35: * nmalloc[i] is the difference between the number of mallocs and frees
! 36: * for a given block size.
! 37: #endif /* MSTATS */
! 38: */
! 39:
! 40: #define ISALLOC ((char) 0xf7) /* magic byte that implies allocation */
! 41: #define ISFREE ((char) 0x54) /* magic byte that implies free block */
! 42: /* this is for error checking only */
! 43:
! 44: extern char etext;
! 45:
! 46: /* end of the program; can be changed by calling init_malloc */
! 47: static char *endofpure = &etext;
! 48:
! 49: #ifdef MSTATS
! 50: static int nmalloc[30];
! 51: static int nmal, nfre;
! 52: #endif /* MSTATS */
! 53:
! 54: /* If range checking is not turned on, all we have is a flag indicating
! 55: whether memory is allocated, an index in nextf[], and a size field; to
! 56: realloc() memory we copy either size bytes or 1<<(index+3) bytes depending
! 57: on whether the former can hold the exact size (given the value of
! 58: 'index'). If range checking is on, we always need to know how much space
! 59: is allocated, so the 'size' field is never used. */
! 60:
! 61: struct mhead {
! 62: char mh_alloc; /* ISALLOC or ISFREE */
! 63: char mh_index; /* index in nextf[] */
! 64: /* Remainder are valid only when block is allocated */
! 65: unsigned short mh_size; /* size, if < 0x10000 */
! 66: #ifdef rcheck
! 67: unsigned mh_nbytes; /* number of bytes allocated */
! 68: int mh_magic4; /* should be == MAGIC4 */
! 69: #endif /* rcheck */
! 70: };
! 71:
! 72: /* Access free-list pointer of a block.
! 73: It is stored at block + 4.
! 74: This is not a field in the mhead structure
! 75: because we want sizeof (struct mhead)
! 76: to describe the overhead for when the block is in use,
! 77: and we do not want the free-list pointer to count in that. */
! 78:
! 79: #define CHAIN(a) \
! 80: (*(struct mhead **) (sizeof (char *) + (char *) (a)))
! 81:
! 82: #ifdef rcheck
! 83:
! 84: /* To implement range checking, we write magic values in at the beginning and
! 85: end of each allocated block, and make sure they are undisturbed whenever a
! 86: free or a realloc occurs. */
! 87: /* Written in each of the 4 bytes following the block's real space */
! 88: #define MAGIC1 0x55
! 89: /* Written in the 4 bytes before the block's real space */
! 90: #define MAGIC4 0x55555555
! 91: #define ASSERT(p) if (!(p)) botch("p"); else
! 92: static
! 93: botch(s)
! 94: char *s;
! 95: {
! 96:
! 97: printf("assertion botched: %s\n", s);
! 98: abort();
! 99: }
! 100: #define EXTRA 4 /* 4 bytes extra for MAGIC1s */
! 101: #else
! 102: #define ASSERT(p)
! 103: #define EXTRA 0
! 104: #endif /* rcheck */
! 105:
! 106: /* nextf[i] is free list of blocks of size 2**(i + 3) */
! 107:
! 108: static struct mhead *nextf[30];
! 109:
! 110: #ifdef M_WARN
! 111: /* Number of bytes of writable memory we can expect to be able to get */
! 112: static int lim_data;
! 113: /* Level number of warnings already issued.
! 114: 0 -- no warnings issued.
! 115: 1 -- 75% warning already issued.
! 116: 2 -- 85% warning already issued.
! 117: */
! 118: static int warnlevel;
! 119: #endif /* M_WARN */
! 120:
! 121: /* nonzero once initial bunch of free blocks made */
! 122: static int gotpool;
! 123:
! 124: /* Cause reinitialization based on job parameters;
! 125: also declare where the end of pure storage is. */
! 126: malloc_init (end)
! 127: char *end; {
! 128: endofpure = end;
! 129: #ifdef M_WARN
! 130: lim_data = 0;
! 131: warnlevel = 0;
! 132: #endif /* M_WARN */
! 133: }
! 134:
! 135: static
! 136: morecore (nu) /* ask system for more memory */
! 137: register int nu; { /* size index to get more of */
! 138: char *sbrk ();
! 139: register char *cp;
! 140: register int nblks;
! 141: register int siz;
! 142:
! 143: #ifdef M_WARN
! 144: #ifndef BSD42
! 145: #ifdef USG
! 146: extern long ulimit ();
! 147: if (lim_data == 0) /* find out how much we can get */
! 148: lim_data = ulimit (3, 0) - TEXT_START;
! 149: #else /*HMS: was endif */
! 150: if (lim_data == 0) /* find out how much we can get */
! 151: lim_data = vlimit (LIM_DATA, -1);
! 152: #endif /* USG */ /HMS:* was not here */
! 153: #else
! 154: if (lim_data == 0) {
! 155: struct rlimit XXrlimit;
! 156:
! 157: getrlimit (RLIMIT_DATA, &XXrlimit);
! 158: lim_data = XXrlimit.rlim_cur;} /* soft limit */
! 159: #endif /* BSD42 */
! 160: #endif /* M_WARN */
! 161:
! 162: /* On initial startup, get two blocks of each size up to 1k bytes */
! 163: if (!gotpool)
! 164: getpool (), getpool (), gotpool = 1;
! 165:
! 166: /* Find current end of memory and issue warning if getting near max */
! 167:
! 168: cp = sbrk (0);
! 169: siz = cp - endofpure;
! 170: #ifdef M_WARN
! 171: switch (warnlevel) {
! 172: case 0:
! 173: if (siz > (lim_data / 4) * 3) {
! 174: warnlevel++;
! 175: malloc_warning ("Warning: past 75% of memory limit");}
! 176: break;
! 177: case 1:
! 178: if (siz > (lim_data / 20) * 17) {
! 179: warnlevel++;
! 180: malloc_warning ("Warning: past 85% of memory limit");}
! 181: break;
! 182: case 2:
! 183: if (siz > (lim_data / 20) * 19) {
! 184: warnlevel++;
! 185: malloc_warning ("Warning: past 95% of memory limit");}
! 186: break;}
! 187: #endif /* M_WARN */
! 188:
! 189: if ((int) cp & 0x3ff) /* land on 1K boundaries */
! 190: sbrk (1024 - ((int) cp & 0x3ff));
! 191:
! 192: /* Take at least 2k, and figure out how many blocks of the desired size we're about to get */
! 193: nblks = 1;
! 194: if ((siz = nu) < 8)
! 195: nblks = 1 << ((siz = 8) - nu);
! 196:
! 197: if ((cp = sbrk (1 << (siz + 3))) == (char *) -1)
! 198: return; /* no more room! */
! 199: if ((int) cp & 7) { /* shouldn't happen, but just in case */
! 200: cp = (char *) (((int) cp + 8) & ~7);
! 201: nblks--;}
! 202:
! 203: /* save new header and link the nblks blocks together */
! 204: nextf[nu] = (struct mhead *) cp;
! 205: siz = 1 << (nu + 3);
! 206: while (1) {
! 207: ((struct mhead *) cp) -> mh_alloc = ISFREE;
! 208: ((struct mhead *) cp) -> mh_index = nu;
! 209: if (--nblks <= 0) break;
! 210: CHAIN ((struct mhead *) cp) = (struct mhead *) (cp + siz);
! 211: cp += siz;}
! 212: /* CHAIN ((struct mhead *) cp) = 0; /* since sbrk() returns cleared core, this is already set */
! 213: }
! 214:
! 215: static
! 216: getpool () {
! 217: register int nu;
! 218: register char *cp = sbrk (0);
! 219:
! 220: if ((int) cp & 0x3ff) /* land on 1K boundaries */
! 221: sbrk (1024 - ((int) cp & 0x3ff));
! 222:
! 223: /* Get 2k of storage */
! 224:
! 225: cp = sbrk (04000);
! 226: if (cp == (char *) -1)
! 227: return;
! 228:
! 229: /* Divide it into an initial 8-word block
! 230: plus one block of size 2**nu for nu = 3 ... 10. */
! 231:
! 232: CHAIN (cp) = nextf[0];
! 233: nextf[0] = (struct mhead *) cp;
! 234: ((struct mhead *) cp) -> mh_alloc = ISFREE;
! 235: ((struct mhead *) cp) -> mh_index = 0;
! 236: cp += 8;
! 237:
! 238: for (nu = 0; nu < 7; nu++) {
! 239: CHAIN (cp) = nextf[nu];
! 240: nextf[nu] = (struct mhead *) cp;
! 241: ((struct mhead *) cp) -> mh_alloc = ISFREE;
! 242: ((struct mhead *) cp) -> mh_index = nu;
! 243: cp += 8 << nu;}}
! 244:
! 245: char *
! 246: malloc (n) /* get a block */
! 247: unsigned n; {
! 248: register struct mhead *p;
! 249: register unsigned int nbytes;
! 250: register int nunits = 0;
! 251:
! 252: /* Figure out how many bytes are required, rounding up to the nearest
! 253: multiple of 4, then figure out which nextf[] area to use */
! 254: nbytes = (n + sizeof *p + EXTRA + 3) & ~3;
! 255: {
! 256: register unsigned int shiftr = (nbytes - 1) >> 2;
! 257:
! 258: while (shiftr >>= 1)
! 259: nunits++;
! 260: }
! 261:
! 262: /* If there are no blocks of the appropriate size, go get some */
! 263: /* COULD SPLIT UP A LARGER BLOCK HERE ... ACT */
! 264: if (nextf[nunits] == 0)
! 265: morecore (nunits);
! 266:
! 267: /* Get one block off the list, and set the new list head */
! 268: if ((p = nextf[nunits]) == 0)
! 269: return 0;
! 270: nextf[nunits] = CHAIN (p);
! 271:
! 272: /* Check for free block clobbered */
! 273: /* If not for this check, we would gobble a clobbered free chain ptr */
! 274: /* and bomb out on the NEXT allocate of this size block */
! 275: if (p -> mh_alloc != ISFREE || p -> mh_index != nunits)
! 276: #ifdef rcheck
! 277: botch ("block on free list clobbered");
! 278: #else
! 279: abort ();
! 280: #endif /* rcheck */
! 281:
! 282: /* Fill in the info, and if range checking, set up the magic numbers */
! 283: p -> mh_alloc = ISALLOC;
! 284: #ifdef rcheck
! 285: p -> mh_nbytes = n;
! 286: p -> mh_magic4 = MAGIC4;
! 287: {
! 288: register char *m = (char *) (p + 1) + n;
! 289:
! 290: *m++ = MAGIC1, *m++ = MAGIC1, *m++ = MAGIC1, *m = MAGIC1;
! 291: }
! 292: #else
! 293: p -> mh_size = n;
! 294: #endif /* rcheck */
! 295: #ifdef MSTATS
! 296: nmalloc[nunits]++;
! 297: nmal++;
! 298: #endif /* MSTATS */
! 299: return (char *) (p + 1);}
! 300:
! 301: free (mem)
! 302: char *mem; {
! 303: register struct mhead *p;
! 304: {
! 305: register char *ap = mem;
! 306:
! 307: ASSERT (ap != 0);
! 308: p = (struct mhead *) ap - 1;
! 309: ASSERT (p -> mh_alloc == ISALLOC);
! 310: #ifdef rcheck
! 311: ASSERT (p -> mh_magic4 == MAGIC4);
! 312: ap += p -> mh_nbytes;
! 313: ASSERT (*ap++ == MAGIC1); ASSERT (*ap++ == MAGIC1);
! 314: ASSERT (*ap++ == MAGIC1); ASSERT (*ap == MAGIC1);
! 315: #endif /* rcheck */
! 316: }
! 317: {
! 318: register int nunits = p -> mh_index;
! 319:
! 320: ASSERT (nunits <= 29);
! 321: p -> mh_alloc = ISFREE;
! 322: CHAIN (p) = nextf[nunits];
! 323: nextf[nunits] = p;
! 324: #ifdef MSTATS
! 325: nmalloc[nunits]--;
! 326: nfre++;
! 327: #endif /* MSTATS */
! 328: }
! 329: }
! 330:
! 331: char *
! 332: realloc (mem, n)
! 333: char *mem;
! 334: register unsigned n; {
! 335: register struct mhead *p;
! 336: register unsigned int tocopy;
! 337: register int nbytes;
! 338: register int nunits;
! 339:
! 340: if ((p = (struct mhead *) mem) == 0)
! 341: return malloc (n);
! 342: p--;
! 343: nunits = p -> mh_index;
! 344: ASSERT (p -> mh_alloc == ISALLOC);
! 345: #ifdef rcheck
! 346: ASSERT (p -> mh_magic4 == MAGIC4);
! 347: {
! 348: register char *m = mem + (tocopy = p -> mh_nbytes);
! 349: ASSERT (*m++ == MAGIC1); ASSERT (*m++ == MAGIC1);
! 350: ASSERT (*m++ == MAGIC1); ASSERT (*m == MAGIC1);
! 351: }
! 352: #else
! 353: if (p -> mh_index >= 13)
! 354: tocopy = (1 << (p -> mh_index + 3)) - sizeof *p;
! 355: else
! 356: tocopy = p -> mh_size;
! 357: #endif /* rcheck */
! 358:
! 359: /* See if desired size rounds to same power of 2 as actual size. */
! 360: nbytes = (n + sizeof *p + EXTRA + 7) & ~7;
! 361:
! 362: /* If ok, use the same block, just marking its size as changed. */
! 363: if (nbytes > (4 << nunits) && nbytes <= (8 << nunits)) {
! 364: #ifdef rcheck
! 365: register char *m = mem + tocopy;
! 366: *m++ = 0; *m++ = 0; *m++ = 0; *m++ = 0;
! 367: p-> mh_nbytes = n;
! 368: m = mem + n;
! 369: *m++ = MAGIC1; *m++ = MAGIC1; *m++ = MAGIC1; *m++ = MAGIC1;
! 370: #else
! 371: p -> mh_size = n;
! 372: #endif /* rcheck */
! 373: return mem;}
! 374:
! 375: if (n < tocopy)
! 376: tocopy = n;
! 377: {
! 378: register char *new;
! 379: void bcopy(); /*HMS: here? */
! 380:
! 381: if ((new = malloc (n)) == 0)
! 382: return 0;
! 383: bcopy (mem, new, tocopy);
! 384: free (mem);
! 385: return new;
! 386: }
! 387: }
! 388:
! 389: #ifdef MSTATS
! 390: /* Return statistics describing allocation of blocks of size 2**n. */
! 391:
! 392: struct mstats_value {
! 393: int blocksize;
! 394: int nfree;
! 395: int nused;
! 396: };
! 397:
! 398: struct mstats_value
! 399: malloc_stats (size)
! 400: int size; {
! 401: struct mstats_value v;
! 402: register int i;
! 403: register struct mhead *p;
! 404:
! 405: v.nfree = 0;
! 406:
! 407: if (size < 0 || size >= 30) {
! 408: v.blocksize = 0;
! 409: v.nused = 0;
! 410: return v;}
! 411:
! 412: v.blocksize = 1 << (size + 3);
! 413: v.nused = nmalloc[size];
! 414:
! 415: for (p = nextf[size]; p; p = CHAIN (p))
! 416: v.nfree++;
! 417:
! 418: return v;}
! 419: #endif
! 420:
! 421: /* how much space is available? */
! 422:
! 423: unsigned freespace() {
! 424: register int i, j;
! 425: register struct mhead *p;
! 426: register unsigned space = 0;
! 427: int local; /* address only is used */
! 428:
! 429: space = (char *)&local - sbrk(0); /* stack space */
! 430:
! 431: for (i = 0; i < 30; i++) {
! 432: for (j = 0, p = nextf[i]; p; p = CHAIN (p), j++) ;
! 433: space += j * (1 << (i + 3));}
! 434:
! 435: return(space);}
! 436:
! 437: /* How big is this cell? */
! 438:
! 439: unsigned mc_size(cp)
! 440: char *cp;{
! 441: register struct mhead *p;
! 442:
! 443: if ((p = (struct mhead *) cp) == 0) {
! 444: /*HMS? */
! 445: }
! 446: p--;
! 447: #ifdef rcheck
! 448: return p -> mh_nbytes;
! 449: #else
! 450: return (1 << (p -> mh_index + 3)) - sizeof *p;
! 451: /**/
! 452: /* if (p -> mh_index >= 13)
! 453: /* return (1 << (p -> mh_index + 3)) - sizeof *p;
! 454: /* else
! 455: /* return p -> mh_size;
! 456: /**/
! 457: #endif /* rcheck */
! 458: }
! 459:
! 460: /*HMS: Really should use memcpy, if available... */
! 461:
! 462: void bcopy(source, dest, len)
! 463: register char *source, *dest;
! 464: register len; {
! 465: register i;
! 466:
! 467: for (i = 0; i < len; i++)
! 468: *dest++ = *source++;}
![[BACK]](/icons/back.gif){kind=icon}
Return to malloc.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / patch