git.marmaro.de Git - mmh/blob - docs/historical/mh-6.8.5/miscellany/patch-2.0.12u8/malloc.c

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