cde/programs/dtksh/ksh93/src/lib/libast/misc/malloc.c

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these librararies and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23 /* $XConsortium: malloc.c /main/3 1995/11/01 17:58:31 rswiston $ */
  24 /***************************************************************
  25 *                                                              *
  26 *                      AT&T - PROPRIETARY                      *
  27 *                                                              *
  28 *        THIS IS UNPUBLISHED PROPRIETARY SOURCE CODE OF        *
  29 *                    AT&T BELL LABORATORIES                    *
  30 *         AND IS NOT TO BE DISCLOSED OR USED EXCEPT IN         *
  31 *            ACCORDANCE WITH APPLICABLE AGREEMENTS             *
  32 *                                                              *
  33 *          Copyright (c) 1994 AT&T Bell Laboratories           *
  34 *              Unpublished & Not for Publication               *
  35 *                     All Rights Reserved                      *
  36 *                                                              *
  37 *       The copyright notice above does not evidence any       *
  38 *      actual or intended publication of such source code      *
  39 *                                                              *
  40 *               This software was created by the               *
  41 *           Software Engineering Research Department           *
  42 *                    AT&T Bell Laboratories                    *
  43 *                                                              *
  44 *               For further information contact                *
  45 *                   advsoft@research.att.com                   *
  46 *                 Randy Hackbarth 908-582-5245                 *
  47 *                  Dave Belanger 908-582-7427                  *
  48 *                                                              *
  49 ***************************************************************/
  50
  51 /* : : generated by proto : : */
  52
  53 #line 1
  54
  55 #if !defined(__PROTO__)
  56 #if defined(__STDC__) || defined(__cplusplus) || defined(_proto) || defined(c_plusplus)
  57 #if defined(__cplusplus)
  58 #define __MANGLE__      "C"
  59 #else
  60 #define __MANGLE__
  61 #endif
  62 #define __STDARG__
  63 #define __PROTO__(x)    x
  64 #define __OTORP__(x)
  65 #define __PARAM__(n,o)  n
  66 #if !defined(__STDC__) && !defined(__cplusplus)
  67 #if !defined(c_plusplus)
  68 #define const
  69 #endif
  70 #define signed
  71 #define void            int
  72 #define volatile
  73 #define __V_            char
  74 #else
  75 #define __V_            void
  76 #endif
  77 #else
  78 #define __PROTO__(x)    ()
  79 #define __OTORP__(x)    x
  80 #define __PARAM__(n,o)  o
  81 #define __MANGLE__
  82 #define __V_            char
  83 #define const
  84 #define signed
  85 #define void            int
  86 #define volatile
  87 #endif
  88 #if defined(__cplusplus) || defined(c_plusplus)
  89 #define __VARARG__      ...
  90 #else
  91 #define __VARARG__
  92 #endif
  93 #if defined(__STDARG__)
  94 #define __VA_START__(p,a)       va_start(p,a)
  95 #else
  96 #define __VA_START__(p,a)       va_start(p)
  97 #endif
  98 #endif
  99
 100 #line 3
 101 #include <ast_lib.h>
 102
 103 #if _std_malloc || _INSTRUMENT_ || cray
 104
 105 int     _STUB_malloc;
 106
 107 #else /* cray */
 108
 109 #ifdef _TRACE_
 110 #ifndef MTRACE
 111 #define MTRACE  1
 112 #endif
 113 #endif
 114
 115 /**********************************************************************
 116         Memory management: malloc(), realloc(), free(), M_brksize.
 117         M_brksize: if > 0 is the maximum amount that the bottom free
 118                 block can grow to. If not SEGMENT, GETCORE() will
 119                 be used to compact bottom space.
 120
 121         The following #-parameters may be redefined:
 122         SEGMENT: if defined, memory requests are assumed to be
 123                 non-contiguous across calls of GETCORE's. SEGMENT defines
 124                 the size of each GETCORE request.
 125         CORESIZE: min number of bytes to used with GETCORE.
 126                 On a SEGMENT machine, this should be defined
 127                 as the size of a segment. Default is 4096.
 128         GETCORE: a function to get more core memory. If not SEGMENT,
 129                 GETCORE(0) is assumed to return the next available
 130                 address. Default is 'sbrk'.
 131         ERRCORE: the error code as returned by GETCORE.
 132                 Default is ((char*)(-1)).
 133         MTRACE: if #define-d, code is included to trace and certify that
 134                 malloc-ed blocks are not corrupted. Available functions
 135                 and variables:
 136                 int (*Mt_corrupt)(addr,size,stamp)
 137                         The function called when a corrupted block is detected.
 138                                 addr: address of the corrupted block
 139                                 size: size of the block.
 140                                 stamp: a user/program-defined stamp (below).
 141                         If Mt_corrupt is NULL, a default function is used.
 142                 Mt_certify: if not 0, indicates that the arena should
 143                         be automatically certified on each call to malloc,
 144                         realloc, or free. Default is 0.
 145                 Mt_trace: if >= 0, is the file descriptor to write out
 146                         a trace of all calls to malloc, free, realloc.
 147                         Default is -1.
 148                 mt_stamp(VOID *data, VOID *stamp)
 149                         Set a stamp for a malloc-ed block. This stamp is used
 150                         in (*corrupt)() calls. For example, a stamp may be
 151                         an indicator of the place where malloc was called.
 152                 mt_certify()
 153                         Check all blocks to see if they are ok. If a block is
 154                         corrupted, (*corrupt)() is called as above.
 155                 mt_stat(int fd)
 156                         Print arena statistics.
 157
 158         With minor variations, the basic allocation strategy is best-fit.
 159         Lists of free blocks of the same size are kept in a splay tree.
 160         For results on splay trees, see:
 161                 Self-Adjusting Binary Trees,
 162                 DD Sleator & RE Tarjan, JACM 1985.
 163
 164         The header of a block contains the size of the data part in bytes.
 165         Since the size of a block is 0%4, the low two bits of the header
 166         are free and used as follows:
 167                 BIT0:   1 for busy (block is in use), 0 for free.
 168                 BIT1:   if the block is busy, this bit is 1 if the
 169                         preceding block in contiguous memory is free.
 170                         Otherwise, it is always 0.
 171
 172         Kiem-Phong Vo, AT&T Bell Laboratories
 173 **********************************************************************/
 174
 175 int     M_brksize;      /* the max size for Bottom */
 176
 177 /* debugging macros */
 178 #ifdef  DEBUG
 179 #define VOID            unsigned char
 180 #define ASSERT(p)       ((void) ((p) ? 0 : (abort(),0)))
 181 #define COUNT(n)        ((void) ((n) += 1))
 182 #define DISCOUNT(n)     ((void) ((n) -= 1))
 183 static int              N_malloc, N_realloc, N_free, N_block, N_list;
 184 #else
 185 #define VOID            char
 186 #define ASSERT(p)
 187 #define COUNT(n)
 188 #define DISCOUNT(n)
 189 #endif /*DEBUG*/
 190
 191 /* system call to get more core */
 192 #ifdef SEGMENT
 193 #define CORESIZE        SEGMENT
 194 #else
 195 #define CORESIZE        (4096)
 196 #endif
 197 #define GETCORE         sbrk
 198 #define ERRCORE         ((VOID*)(-1))
 199
 200 #define size_t          unsigned int
 201 #define ssize_t         int
 202
 203 extern __MANGLE__ __V_* GETCORE __PROTO__((ssize_t));
 204 extern __MANGLE__ __V_* malloc __PROTO__((size_t));
 205 extern __MANGLE__ __V_* realloc __PROTO__((__V_*, size_t));
 206 extern __MANGLE__ void  free __PROTO__((__V_*));
 207 extern __MANGLE__ void  nomalloc __PROTO__((void));
 208
 209 /* function to copy data from one area to another */
 210 #ifdef  _lib_bcopy
 211 #undef  memcpy
 212 #define memcpy(to,fr,n)         bcopy(fr,to,n)
 213 extern __MANGLE__ void                  bcopy __PROTO__((__V_*, __V_*, int));
 214 #endif
 215
 216 /* for conveniences */
 217 #define uchar           unsigned char
 218 #define NULL            (0L)
 219 #define NIL(p)          ((p)(NULL))
 220 #define MINSIZE         ((int)(sizeof(TREE)-sizeof(WORD)))
 221 #define ROUND(x,y)      ((((x)+((y)-1))/(y))*(y))
 222
 223 /* the following structures are used to compute a suitable alignment for all types */
 224 typedef union _u_
 225 {
 226         int     i;
 227         VOID*   s;
 228         double  d;
 229         VOID    big[1024];
 230 } _ua_;
 231 typedef struct _s_
 232 {
 233         VOID    c;
 234         _ua_    u;
 235 } _sa_;
 236 #define ALIGN           ((int)(sizeof(_sa_) - sizeof(_ua_)))
 237 #define WORDSIZE        ROUND((int)ALIGN,4)
 238
 239 typedef union _w_
 240 {       /* the proto-word */
 241         size_t          w_i;            /* an int */
 242         struct _t_      *w_p;           /* a pointer */
 243         VOID            w_a[ALIGN];     /* to force alignment */
 244 } WORD;
 245
 246 typedef struct _t_
 247 {       /* structure of a node in the free tree */
 248         WORD    t_s;    /* size of this element */
 249         WORD    t_n;    /* next in link list */
 250         WORD    t_l;    /* left child */
 251         WORD    t_r;    /* right child */
 252         WORD    t_d;    /* stub to reserve space for self-pointer */
 253 } TREE;
 254
 255 /* usable # of bytes in the block */
 256 #define SIZE(b)         (((b)->t_s).w_i)
 257
 258 /* free tree pointers */
 259 #define LEFT(b)         (((b)->t_l).w_p)
 260 #define RIGHT(b)        (((b)->t_r).w_p)
 261
 262 /* links in linked lists */
 263 #define LINK(b)         (((b)->t_n).w_p)
 264 #define BACK(b)         (((b)->t_l).w_p)
 265
 266 /* set/test indicator to see if a block is in the tree or in a list */
 267 #define SETNOTREE(b)    (RIGHT(b) = (TREE*)(~0))
 268 #define ISNOTREE(b)     (RIGHT(b) == (TREE*)(~0))
 269
 270 /* functions to get information on a block */
 271 #define DATA(b)         (((VOID*) (b)) + WORDSIZE)
 272 #define BLOCK(d)        ((TREE*) ((d) - WORDSIZE))
 273 #define SELFP(b)        ((TREE**) (((VOID*) (b)) + SIZE(b)))
 274 #define LAST(b)         (*((TREE**) (((VOID*) (b)) - WORDSIZE)))
 275 #define NEXT(b)         ((TREE*) (((VOID*) (b)) + SIZE(b) + WORDSIZE))
 276 #define BOTTOM(b)       ((DATA(b)+SIZE(b)+WORDSIZE) == Baddr)
 277
 278 /* functions to set and test the lowest two bits of a word */
 279 #define BIT0            (01)    /* ....01 */
 280 #define BIT1            (02)    /* ...010 */
 281 #define BITS01          (03)    /* ...011 */
 282 #define ISBIT0(w)       ((w) & BIT0)
 283 #define ISBIT1(w)       ((w) & BIT1)
 284 #define SETBIT0(w)      ((w) |= BIT0)
 285 #define SETBIT1(w)      ((w) |= BIT1)
 286 #define CLRBIT0(w)      ((w) &= ~BIT0)
 287 #define CLRBIT1(w)      ((w) &= ~BIT1)
 288 #define ISBITS01(w)     ((w) & BITS01)
 289 #define SETBITS01(w)    ((w) |= BITS01)
 290 #define CLRBITS01(w)    ((w) &= ~BITS01)
 291 #define CPYBITS01(w,f)  ((w) |= (f)&BITS01)
 292
 293 static TREE     *Root,          /* root of the free tree */
 294                 *Bottom;        /* the last free chunk in the arena */
 295
 296 static VOID     *Baddr,         /* current high address of the arena */
 297                 *Lfree,         /* last free block with data intact */
 298                 *Nofree;        /* this block is not to be freed */
 299
 300 /* lists of small blocks */
 301 #define LGET    16
 302 static TREE     *List[(MINSIZE-WORDSIZE)/WORDSIZE];
 303
 304 /* circular queue of delayed free blocks */
 305 #define QSIZE   (1<<8)
 306 #define QMASK   (QSIZE-1)
 307 static VOID     **Qfree;
 308 static int      Qhead = -1, Qtail = 0;
 309 #define CYCLE(n)        (n = (n+1)&QMASK)
 310 #define REWIND(n)       (n = (n+QMASK)&QMASK)
 311 #define QVOID()         (Qhead < 0)
 312 #define QFULL()         (Qtail == Qhead)
 313 #define QENDADD()       (Qhead < 0 ? (Qhead = 0) : 0)
 314 #define QENDDEL()       (Qtail == Qhead ? (Qhead = -1, Qtail = 0) : 0)
 315 #define ENQUEUE(x)      ((Qfree[Qtail] = (x)), CYCLE(Qtail), QENDADD())
 316 #define DEQUEUE(x)      (((x) = Qfree[Qhead]), CYCLE(Qhead), QENDDEL())
 317 #define DESTACK(x)      (REWIND(Qtail), ((x) = Qfree[Qtail]), QENDDEL())
 318
 319 /*
 320 **      Coalesce adjacent blocks and free left-over memory.
 321 */
 322 #define UNLINK(u)       { if(LINK(u)) \
 323                                 BACK(LINK(u)) = BACK(u); \
 324                           LINK(BACK(u)) = LINK(u);      /**/ DISCOUNT(N_block); \
 325                         }
 326 #define FMERGE(t,n)     { n = NEXT(t); \
 327                           if(!ISBIT0(SIZE(n))) \
 328                           {     if(n != Bottom) \
 329                                 {       if(!ISNOTREE(n)) \
 330                                                 t_search(SIZE(n)); \
 331                                         else    UNLINK(n); \
 332                                 } \
 333                                 else    Bottom = NIL(TREE*); \
 334                                 SIZE(t) += SIZE(n)+WORDSIZE; \
 335                                 CLRBIT1(SIZE(NEXT(t))); \
 336                                 /**/ ASSERT(ISBIT0(SIZE(NEXT(t)))); \
 337                           } \
 338                         }
 339 #define BMERGE(t,n)     { n = LAST(t); \
 340                           if(!ISNOTREE(n)) \
 341                                 t_search(SIZE(n)); \
 342                           else  UNLINK(n); \
 343                           SIZE(n) += SIZE(t)+WORDSIZE; \
 344                           t = n; \
 345                         }
 346 #define FREE(f)         { if(BOTTOM(f)) \
 347                                 Bottom = f; \
 348                           else \
 349                           {     SETBIT0(SIZE(f)); /**/ ASSERT(!Lfree); \
 350                                 Lfree = DATA(f); \
 351                           } \
 352                         }
 353 /*
 354 ** Trace malloc/free patterns.
 355 */
 356 #ifdef MTRACE
 357 #define MTNONE          0
 358 #define MTFREE          1
 359 #define MTMALLOC        2
 360 #define MTREALLOC       3
 361 #define MTSPACE         (3*WORDSIZE)
 362 #define MTSIZE(b)       (SIZE(b)&(~BITS01))
 363 #define MTNEXT(b)       ((TREE*)(DATA(b) + MTSIZE(b)))
 364 #define USIZE(b)        (*((size_t*)(DATA(b)+MTSIZE(b)-(2*WORDSIZE))))
 365 #define USTAMP(b)       (*((VOID**)(DATA(b)+MTSIZE(b)-WORDSIZE)))
 366 #define MTSETFREE(b)    (USTAMP(b) = (VOID*)(~0))
 367 #define MTISFREE(b)     (!ISBITS01(SIZE(b)) || USTAMP(b) == (VOID*)(~0))
 368 #define SMAGIC(b)       ((uchar*)(DATA(b)+USIZE(b)))
 369 #define EMAGIC(b)       ((uchar*)(DATA(b)+MTSIZE(b)-(2*WORDSIZE)))
 370 #define MAGIC           0253    /* 10101011 pattern */
 371
 372 static VOID     *Laddr;         /* low address of the arena */
 373 int     (*Mt_corrupt) __PROTO__((VOID*,size_t,VOID*));  /* function to process corrupted blocks */
 374 int     Mt_certify;             /* automatically certify the arena */
 375 int     Mt_trace = -1;          /* print trace of mallocs and frees */
 376
 377 /* Convert an int to a string */
 378 static itoa __PARAM__((register size_t i, register char* buf), (i, buf)) __OTORP__(register size_t i; register char* buf;)
 379 #line 281
 380 {
 381         register int    k, c;
 382
 383         k = 0;
 384         do
 385         {
 386                 buf[k++] = '0' + i%10;
 387                 i /= 10;
 388         }       while(i != 0);
 389         buf[k] = '\0';
 390         for(i = 0; i < k/2; ++i)
 391         {
 392                 c = buf[i];
 393                 buf[i] = buf[(k-i)-1];
 394                 buf[(k-i)-1] = c;
 395         }
 396 }
 397
 398 /* Convert an int to a hex string */
 399 static xtoa __PARAM__((register size_t i, register char* buf), (i, buf)) __OTORP__(register size_t i; register char* buf;)
 400 #line 301
 401 {
 402         register int    k;
 403
 404         static char dig[] = "0123456789ABCDEF";
 405
 406         *buf++ = '0';
 407         *buf++ = 'x';
 408         buf += 2 * sizeof(size_t);
 409         *buf = 0;
 410         for (k = 0; k < 2 * sizeof(size_t); k++, i >>= 4)
 411                 *--buf = dig[i & 0xF];
 412 }
 413
 414 /* internal function for warning on corruption */
 415 static int mt_corrupt __PARAM__((register VOID* addr, register size_t usize, register VOID* stamp), (addr, usize, stamp)) __OTORP__(register VOID* addr; register size_t usize; register VOID* stamp;)
 416 #line 316
 417 {
 418         char    buf[64], *mesg;
 419
 420         mesg = "corrupt:addr=";
 421         write(2,mesg,strlen(mesg));
 422         xtoa((size_t)addr,buf);
 423         write(2,buf,strlen(buf));
 424
 425         mesg = ":size=";
 426         write(2,mesg,strlen(mesg));
 427         itoa(usize,buf);
 428         write(2,buf,strlen(buf));
 429
 430         mesg = ":stamp=";
 431         write(2,mesg,strlen(mesg));
 432         xtoa((size_t)stamp,buf);
 433         write(2,buf,strlen(buf));
 434
 435         write(2,"\n",1);
 436 }
 437
 438 /* Print trace information */
 439 static mt_trace __PARAM__((register VOID* addr, register int type), (addr, type)) __OTORP__(register VOID* addr; register int type;)
 440 #line 339
 441 {
 442         char    *mesg, buf[64];
 443
 444         mesg =  type == MTMALLOC ? "malloc" : type == MTFREE ? "free" : "realloc";
 445         write(Mt_trace,mesg,strlen(mesg));
 446
 447         mesg = ":addr=";
 448         write(Mt_trace,mesg,strlen(mesg));
 449         xtoa((size_t)addr,buf);
 450         write(Mt_trace,buf,strlen(buf));
 451
 452         mesg = ":size=";
 453         write(Mt_trace,mesg,strlen(mesg));
 454         itoa(USIZE(BLOCK(addr)),buf);
 455         write(Mt_trace,buf,strlen(buf));
 456
 457         write(Mt_trace,"\n",1);
 458 }
 459
 460 /* Print a warning */
 461 static mt_didfree __PARAM__((register VOID* addr, register int type), (addr, type)) __OTORP__(register VOID* addr; register int type;)
 462 #line 360
 463 {
 464         char    *mesg, buf[64];
 465
 466         mesg = type == MTFREE ? "free:addr=" : "realloc:addr=";
 467         write(2,mesg,strlen(mesg));
 468         xtoa((size_t)addr,buf);
 469         write(2,buf,strlen(buf));
 470         mesg = ":already freed\n";
 471         write(2,mesg,strlen(mesg));
 472 }
 473
 474 /* Set trace info for a block */
 475 static mt_setinfo __PARAM__((register TREE* bp, register size_t usize, int type), (bp, usize, type)) __OTORP__(register TREE* bp; register size_t usize; int type;)
 476 #line 373
 477 {
 478         register uchar  *magic, *emagic;
 479
 480         USIZE(bp) = usize;
 481         USTAMP(bp) = NIL(VOID*);
 482         for(magic = SMAGIC(bp), emagic = EMAGIC(bp); magic < emagic; ++magic)
 483                 *magic = MAGIC;
 484
 485         if(Mt_trace >= 0 && type != MTNONE)
 486                 mt_trace(DATA(bp),type);
 487 }
 488
 489 /* Set a stamp */
 490 mt_stamp __PARAM__((register VOID* addr, register VOID* stamp), (addr, stamp)) __OTORP__(register VOID* addr; register VOID* stamp;)
 491 #line 387
 492 {
 493         USTAMP(BLOCK(addr)) = stamp;
 494 }
 495
 496 /* Certify that no data block has been corrupted */
 497 mt_certify __PARAM__((void), ())
 498 #line 393
 499 {
 500         register TREE   *bp, *endb;
 501         register uchar  *magic, *endm;
 502
 503         if(!Mt_corrupt)
 504                 Mt_corrupt = mt_corrupt;
 505
 506         for(bp = (TREE*)Laddr, endb = (TREE*) Baddr; bp < endb; bp = MTNEXT(bp))
 507         {
 508                 if(MTISFREE(bp) || MTSIZE(bp) == 0)
 509                         continue;
 510                 if(USIZE(bp) >= MTSIZE(bp))
 511                         (*Mt_corrupt)(DATA(bp),USIZE(bp),USTAMP(bp));
 512                 else for(magic = SMAGIC(bp), endm = EMAGIC(bp); magic < endm; ++magic)
 513                         if(*magic != MAGIC)
 514                         {
 515                                 (*Mt_corrupt)(DATA(bp),USIZE(bp),USTAMP(bp));
 516                                 break;
 517                         }
 518         }
 519 }
 520
 521 /* Print block statistics */
 522 mt_stat __PARAM__((int fd), (fd)) __OTORP__(int fd;)
 523 #line 417
 524 {
 525         register TREE   *bp, *endb;
 526         register size_t nbusy, sfree, sbusy, mbusy;
 527         char            buf[64], *mesg;
 528
 529         nbusy = sfree = sbusy = mbusy = 0;
 530         for(bp = (TREE*)Laddr, endb = (TREE*) Baddr; bp < endb; bp = MTNEXT(bp))
 531         {
 532                 if(MTISFREE(bp) || MTSIZE(bp) == 0)
 533                         sfree += MTSIZE(bp);
 534                 else
 535                 {
 536                         nbusy += 1;
 537                         sbusy += USIZE(bp);
 538                         mbusy += MTSIZE(bp);
 539                 }
 540         }
 541
 542         mesg="free_space=";
 543         write(fd,mesg,strlen(mesg));
 544         itoa(sfree,buf);
 545         write(fd,buf,strlen(buf));
 546
 547         mesg=", busy_blocks=";
 548         write(fd,mesg,strlen(mesg));
 549         itoa(nbusy,buf);
 550         write(fd,buf,strlen(buf));
 551
 552         mesg=", user_space=";
 553         write(fd,mesg,strlen(mesg));
 554         itoa(sbusy,buf);
 555         write(fd,buf,strlen(buf));
 556
 557         mesg=", malloc_space=";
 558         write(fd,mesg,strlen(mesg));
 559         itoa(mbusy,buf);
 560         write(fd,buf,strlen(buf));
 561
 562         write(fd,"\n",1);
 563 }
 564 #endif  /* MTRACE */
 565
 566 /*
 567 **      Get more core. Gaps in memory are noted as busy blocks.
 568 */
 569 static TREE *morecore __PARAM__((register size_t size), (size)) __OTORP__(register size_t size;)
 570 #line 463
 571 {
 572         register TREE   *tp, *bp;
 573         register VOID   *addr;
 574
 575         /* space for queue of delayed free blocks */
 576         if(!Qfree)
 577                 size += QSIZE*sizeof(Qfree[0]);
 578
 579         /* try to extend the Bottom block if possible */
 580         bp = Bottom;
 581         Bottom = NIL(TREE*);
 582
 583         /* get memory */
 584         size += 2*WORDSIZE;
 585         size = ROUND(size,CORESIZE);
 586         if((addr = (VOID*)GETCORE(size)) == ERRCORE)
 587         {
 588                 Bottom = bp;
 589                 return NIL(TREE*);
 590         }
 591
 592         if(addr == Baddr)
 593         {       /* contiguous memory, merge with previous bottom */
 594                 if(bp)
 595                 {
 596                         addr = ((VOID*)bp);
 597                         size += SIZE(bp) + 2*WORDSIZE;
 598                 }
 599                 else
 600                 {
 601                         addr = Baddr-WORDSIZE;
 602                         size += WORDSIZE;
 603                 }
 604         }
 605         else
 606         {
 607 #ifndef SEGMENT
 608                 if((((size_t)addr)%ALIGN) != 0)
 609                 {       /* make sure alignment is correct */
 610                         register size_t n = ALIGN - ((size_t)addr)%ALIGN;
 611                         if((VOID*)GETCORE(n) == ERRCORE)
 612                         {
 613                                 Bottom = bp;
 614                                 return NIL(TREE*);
 615                         }
 616                         addr += n;
 617                 }
 618 #endif
 619                 if(!Qfree)
 620                 {       /* space for the free queue */
 621                         Qfree = (VOID**) addr;
 622                         addr += QSIZE*sizeof(Qfree[0]);
 623                         size -= QSIZE*sizeof(Qfree[0]);
 624                 }
 625 #ifdef MTRACE
 626                 if(!Laddr)
 627                         Laddr = addr;
 628 #endif
 629         }
 630
 631         /* new bottom address */
 632         Baddr = addr + size;
 633
 634         /* new bottom block */
 635         tp = ((TREE*) addr);
 636         SIZE(tp) = size - 2*WORDSIZE;   /**/ASSERT((SIZE(tp)%WORDSIZE) == 0);
 637
 638         /* reserved the last word to head any noncontiguous memory */
 639         SETBIT0(SIZE(NEXT(tp)));
 640
 641         if(bp && bp != tp)
 642         {       /* non-contiguous memory, free old bottom block */
 643                 /**/ ASSERT(!Lfree && QVOID());
 644                 SETBIT0(SIZE(bp));
 645                 ENQUEUE(DATA(bp));
 646         }
 647
 648         return tp;
 649 }
 650
 651 /*
 652 **      Tree rotation functions
 653 */
 654 #define RROTATE(t,r)    (t = LEFT(r), LEFT(r) = RIGHT(t), RIGHT(t) = r, r = t)
 655 #define LROTATE(t,r)    (t = RIGHT(r), RIGHT(r) = LEFT(t), LEFT(t) = r, r = t)
 656 #define RLINK(r,s,x)    (r ? (s = LEFT(s) = x) : (r = s = x))
 657 #define LLINK(r,s,x)    (r ? (s = RIGHT(s) = x) : (r = s = x))
 658 #define RTWICE(t,r)     (LEFT(LEFT(r)) = RIGHT(t), RIGHT(t) = r, r = t)
 659 #define LTWICE(t,r)     (RIGHT(RIGHT(r)) = LEFT(t), LEFT(t) = r, r = t)
 660
 661 /*
 662 **      Look up a suitable element in the tree. If found, delete it from
 663 **      the tree and return its address.
 664 **      This uses the top-down splay strategy.
 665 */
 666 static TREE *t_search __PARAM__((register int size), (size)) __OTORP__(register int size;)
 667 #line 559
 668 {
 669         register int            cmp;
 670         register TREE   *t, *del, *left, *right, *lroot, *rroot;
 671
 672         /* find the right one to delete */
 673         del = Root;
 674         lroot = rroot = NIL(TREE*);
 675         while(del)
 676         {       /**/ ASSERT(!ISBITS01(size) && !ISBITS01(SIZE(del)));
 677                 if((cmp = size - SIZE(del)) == 0)
 678                         break;
 679                 if(cmp < 0)
 680                 {
 681                         if((t = LEFT(del)) == NIL(TREE*))
 682                         {
 683                                 RLINK(rroot,right,del);
 684                                 del = NIL(TREE*);
 685                         }
 686                         else if((cmp = size - SIZE(t)) <= 0)
 687                         {       /* left,left case */
 688                                 RROTATE(t,del);
 689                                 if(cmp == 0)
 690                                         break;
 691                                 RLINK(rroot,right,del);
 692                                 del = LEFT(del);
 693                         }
 694                         else
 695                         {       /* left, right case */
 696                                 RLINK(rroot,right,del);
 697                                 LLINK(lroot,left,t);
 698                                 del = RIGHT(t);
 699                         }
 700                 }
 701                 else
 702                 {
 703                         if((t = RIGHT(del)) == NIL(TREE*))
 704                         {
 705                                 LLINK(lroot,left,del);
 706                                 del = NIL(TREE*);
 707                         }
 708                         else if((cmp = size - SIZE(t)) >= 0)
 709                         {       /* right, right case */
 710                                 LROTATE(t,del);
 711                                 if(cmp == 0)
 712                                         break;
 713                                 LLINK(lroot,left,t);
 714                                 del = RIGHT(del);
 715                         }
 716                         else
 717                         {       /* right, left case */
 718                                 LLINK(lroot,left,del);
 719                                 RLINK(rroot,right,t);
 720                                 del = LEFT(t);
 721                         }
 722                 }
 723         }
 724
 725         if(del)
 726         {
 727                 if(lroot)
 728                 {
 729                         RIGHT(left) = LEFT(del);
 730                         LEFT(del) = lroot;
 731                 }
 732                 if(rroot)
 733                 {
 734                         LEFT(right) = RIGHT(del);
 735                         RIGHT(del) = rroot;
 736                 }
 737         }
 738         else
 739         {
 740                 if(lroot)
 741                         RIGHT(left) = NIL(TREE*);
 742                 if(rroot)
 743                 {       /* get least one > size */
 744                         LEFT(right) = NIL(TREE*);
 745                         while(LEFT(rroot))
 746                         {       /* left zig-zig case */
 747                                 if((t = LEFT(LEFT(rroot))) != NIL(TREE*))
 748                                         RTWICE(t,rroot);
 749                                 else    RROTATE(t,rroot);
 750                         }
 751                         LEFT(rroot) = lroot;
 752                         del = rroot;
 753                 }
 754                 else
 755                 {
 756                         Root = lroot;
 757                         return NIL(TREE*);
 758                 }
 759         }
 760
 761         if((t = LINK(del)) != NIL(TREE*))
 762         {       /* start of a non-singleton list */
 763                 LEFT(t) = LEFT(del);
 764                 RIGHT(t) = RIGHT(del);
 765                 Root = t;       /**/ ASSERT(!ISNOTREE(t));
 766         }
 767         else
 768         {       /**/ DISCOUNT(N_list);
 769                 if((right = RIGHT(del)) != NIL(TREE*))
 770                 {       /* make least elt of right tree the root */
 771                         while(LEFT(right))
 772                         {       /* left zig-zig case */
 773                                 if((t = LEFT(LEFT(right))) != NIL(TREE*))
 774                                         RTWICE(t,right);
 775                                 else    RROTATE(t,right);
 776                         }
 777                         LEFT(right) = LEFT(del);
 778                         Root = right;
 779                 }
 780                 else    Root = LEFT(del);
 781         }       /**/ DISCOUNT(N_block);
 782
 783         return del;
 784 }
 785
 786 /*
 787 **      malloc().
 788 */
 789 __V_* malloc __PARAM__((register size_t size), (size)) __OTORP__(register size_t size;)
 790 #line 681
 791 {
 792         register TREE   *tp, *np, *fp;
 793         register int            n, i;
 794 #ifdef MTRACE
 795         /* save true size and make size large enough to hold our data */
 796         register size_t mtsize = size;
 797         size = size <= (MINSIZE-MTSPACE) ? MINSIZE : size + MTSPACE;
 798         if(Mt_certify)
 799                 mt_certify();
 800 #endif
 801         /**/ COUNT(N_malloc);
 802
 803         size = size == 0 ? WORDSIZE : ROUND(size,WORDSIZE);
 804         tp = NIL(TREE*);
 805         if(Lfree)
 806         {       /* see if the last free block can be used */
 807                 fp = BLOCK(Lfree);
 808                 Lfree = NIL(VOID*);
 809                 n = SIZE(fp);
 810                 CLRBITS01(SIZE(fp));
 811                 if(SIZE(fp) == size)
 812                 {       /* exact match, use it as is */
 813                         SIZE(fp) = n;
 814                         if(!QVOID())
 815                                 DESTACK(Lfree);
 816 #ifdef MTRACE
 817                         mt_setinfo(fp,mtsize,MTMALLOC);
 818 #endif
 819                         return DATA(fp);
 820                 }
 821                 else if(n >= MINSIZE && size >= MINSIZE && !ISBIT1(n))
 822                 {       /* see if good enough */
 823                         FMERGE(fp,np);
 824                         if(!BOTTOM(fp) && SIZE(fp) >= size)
 825                                 tp = fp;
 826                 }
 827                 else    SIZE(fp) = n;
 828                 if(!tp)
 829                         free(Lfree = DATA(fp));
 830         }
 831
 832         if(size < MINSIZE)
 833         {       /**/ ASSERT(!Lfree && QVOID());
 834                 n = size/WORDSIZE - 1;
 835                 if(List[n] == NIL(TREE*))
 836                 {       /* get a bunch of these small blocks */
 837                         if(!(tp = (TREE*) malloc((size+WORDSIZE)*LGET)))
 838                         {
 839 #if _PACKAGE_ast
 840                                 nomalloc();
 841 #endif
 842                                 return NIL(VOID*);
 843                         }
 844                         List[n] = tp;
 845                         for(i = LGET-1; i > 0; --i)
 846                         {
 847                                 SIZE(tp) = size;
 848                                 tp = LINK(tp) = NEXT(tp);
 849                         }
 850                         SIZE(tp) = size;
 851                         LINK(tp) = NIL(TREE*);
 852                 }
 853                 tp = List[n];
 854                 List[n] = LINK(tp);
 855                 return DATA(tp);
 856         }
 857
 858         if(!tp)
 859         {       /* normal malloc requests */
 860                 if(Root && (tp = t_search(size)) != NIL(TREE*))
 861                         CLRBIT1(SIZE(NEXT(tp)));
 862                 else if((tp = Bottom) != NIL(TREE*) && SIZE(tp) >= size)
 863                         Bottom = NIL(TREE*);
 864                 else if((tp = morecore(size)) == NIL(TREE*))
 865                 {
 866 #if _PACKAGE_ast
 867                         nomalloc();
 868 #endif
 869                         return NIL(VOID*);
 870                 }
 871         }       /**/ ASSERT(tp && !ISBITS01(SIZE(tp)));
 872
 873         if((n = SIZE(tp)-size) >= (MINSIZE+WORDSIZE))
 874         {       /* the leftover is enough for a new free piece */
 875                 SIZE(tp) = size;
 876                 np = NEXT(tp);
 877                 SIZE(np) = n-WORDSIZE;
 878 #ifdef MTRACE
 879                 MTSETFREE(np);
 880 #endif
 881                 FREE(np);
 882         }
 883
 884         /* peel out a pending free block */
 885         if(!Lfree && !QVOID())
 886                 DESTACK(Lfree);
 887
 888         /* return the allocated space */
 889 #ifdef MTRACE
 890         mt_setinfo(tp,mtsize,MTMALLOC);
 891 #endif
 892         SETBIT0(SIZE(tp));
 893         return DATA(tp);
 894 }
 895
 896 /*
 897 **      realloc().
 898 */
 899 __V_* realloc __PARAM__((__V_* old, register size_t size), (old, size)) __OTORP__(__V_* old; register size_t size;)
 900 #line 790
 901 {
 902         register TREE   *tp, *np;
 903         register int    n, ts;
 904         register VOID   *newp;
 905 #ifdef MTRACE
 906         register size_t mtsize = size;
 907         if(old)
 908         {
 909                 size = size < (MINSIZE-MTSPACE) ? MINSIZE : size + MTSPACE;
 910                 if(Mt_certify)
 911                         mt_certify();
 912                 if(MTISFREE(BLOCK((VOID*)old)))
 913                         mt_didfree((VOID*)old,MTREALLOC);
 914                 if(Mt_trace >= 0)
 915                         mt_trace((VOID*)old,MTREALLOC);
 916         }
 917 #endif
 918         /**/ COUNT(N_realloc);
 919
 920         if(!old)
 921                 return malloc(size);
 922
 923         if(Lfree)
 924         {       /* free everything except old */
 925                 Nofree = (VOID*)old;
 926                 free(Lfree);
 927                 Nofree = NIL(VOID*);
 928         }
 929
 930         size = size == 0 ? WORDSIZE : ROUND(size,WORDSIZE);
 931         tp = BLOCK((VOID*)old);
 932         ts = SIZE(tp);
 933         if(size >= MINSIZE && ts >= MINSIZE)
 934         {
 935                 CLRBITS01(SIZE(tp));
 936                 if((n = SIZE(tp)-size) < 0)
 937                 {       /* growing, try forward merging */
 938                         FMERGE(tp,np);
 939                         n = SIZE(tp) - size;
 940 #ifndef SEGMENT
 941                         if(n < 0 && BOTTOM(tp) && (VOID*)GETCORE(0) == Baddr)
 942                         {       /* try extending core */
 943                                 Bottom = tp;
 944                                 if((tp = morecore(size)) != NIL(TREE*))
 945                                         n = SIZE(tp) - size;
 946                         }
 947 #endif /*!SEGMENT*/
 948                 }
 949                 if(n >= (MINSIZE+WORDSIZE))
 950                 {       /* left over is enough for a new piece */
 951                         SIZE(tp) = size;
 952                         np = NEXT(tp);
 953                         SIZE(np) = (n-WORDSIZE);
 954 #ifdef MTRACE
 955                         MTSETFREE(np);
 956 #endif
 957                         FREE(np);
 958                 }
 959                 CPYBITS01(SIZE(tp),ts);
 960                 if(n >= 0) /* got it */
 961                 {
 962 #ifdef MTRACE
 963                         mt_setinfo(tp,mtsize,MTMALLOC);
 964 #endif
 965                         return old;
 966                 }
 967         }
 968 #ifdef MTRACE
 969         MTSETFREE(BLOCK((VOID*)old));
 970 #endif
 971         /* call malloc to get a new block */
 972         CLRBITS01(ts);
 973         if((newp = (VOID*)malloc(size)) != NIL(VOID*))
 974                 memcpy(newp,old,ts < size ? ts : size);
 975
 976         /**/ ASSERT(!QFULL());
 977         if(!Lfree)
 978                 Lfree = (VOID*)old;
 979         else    ENQUEUE((VOID*)old);
 980 #ifdef MTRACE
 981         mt_setinfo(BLOCK(newp),mtsize,MTNONE);
 982 #endif
 983         return newp;
 984 }
 985
 986 /*
 987 **      free().
 988 */
 989 void free __PARAM__((__V_* aold), (aold)) __OTORP__(__V_* aold;)
 990 #line 879
 991 {
 992         register VOID*  old = (VOID*)aold;
 993         register int    size;
 994         register TREE   *tp, *np, *sp;
 995         register VOID   *dequeue;
 996 #ifdef MTRACE
 997         if(Lfree != old)
 998         {
 999                 if(Mt_certify)
1000                         mt_certify();
1001                 if(MTISFREE(BLOCK(old)))
1002                         mt_didfree(old,MTFREE);
1003                 else    MTSETFREE(BLOCK(old));
1004                 if(Mt_trace >= 0)
1005                         mt_trace(old,MTFREE);
1006         }
1007 #endif
1008         /**/ COUNT(N_free);
1009
1010         if(!old)
1011                 old = Lfree;
1012
1013         dequeue = NIL(VOID*);
1014         if(Lfree != old)
1015         {       /* this is a normal free call */
1016                 if(Lfree)
1017                 {       /* make queue space for current Lfree */
1018                         if(QFULL())
1019                                 DEQUEUE(dequeue);       /**/ ASSERT(!QFULL());
1020                         ENQUEUE(Lfree);
1021                 }
1022                 Lfree = old;
1023                 old = dequeue;
1024         }
1025         else    Lfree = NIL(VOID*);
1026
1027         while(old)
1028         {
1029                 if(Nofree == old)
1030                         goto next;
1031
1032                 tp = BLOCK(old);
1033                 if((size = SIZE(tp)) < MINSIZE)
1034                 {       /* small block */
1035                         size = size/WORDSIZE - 1;
1036                         LINK(tp) = List[size];
1037                         List[size] = tp;
1038                         goto next;
1039                 }
1040
1041                 /* merge adjacent free blocks */
1042                 CLRBITS01(SIZE(tp));
1043                 FMERGE(tp,np);
1044                 if(ISBIT1(size))
1045                         BMERGE(tp,np);
1046
1047                 if(BOTTOM(tp))
1048                 {       /* bottom block */
1049                         Bottom = tp;
1050 #ifndef SEGMENT
1051                         if(M_brksize > 0 && (VOID*)GETCORE(0) == Baddr)
1052                         {
1053                                 M_brksize = ROUND(M_brksize,CORESIZE);
1054                                 if((size = SIZE(tp)-MINSIZE) >= M_brksize)
1055                                 {
1056                                         size = (size/CORESIZE)*CORESIZE;
1057                                         GETCORE(-size);
1058                                         if((old = (VOID*)GETCORE(0)) != Baddr)
1059                                         {
1060                                                 Baddr = old;
1061                                                 SIZE(tp) = (old-WORDSIZE) - DATA(tp);
1062                                                 SIZE(NEXT(tp)) = BIT0;
1063                                         }
1064                                 }
1065                         }
1066 #endif
1067                         goto next;
1068                 }
1069
1070                 /* tell next block that this one is free */
1071                 SETBIT1(SIZE(NEXT(tp)));        /**/ ASSERT(ISBIT0(SIZE(NEXT(tp))));
1072
1073                 /* leaf insert into the free tree */
1074                 LEFT(tp) = RIGHT(tp) = LINK(tp) = NIL(TREE*);
1075                 *(SELFP(tp)) = tp;
1076                 /**/ COUNT(N_block);
1077
1078                 if(!Root)
1079                 {       /**/ COUNT(N_list);
1080                         Root = tp;
1081                         goto next;
1082                 }
1083
1084                 np = Root;
1085                 size = SIZE(tp);
1086                 while(1)
1087                 {
1088                         if(SIZE(np) > size)
1089                         {
1090                                 if((sp = LEFT(np)) != NIL(TREE*))
1091                                         np = sp;
1092                                 else
1093                                 {       /**/ COUNT(N_list);
1094                                         LEFT(np) = tp;
1095                                         break;
1096                                 }
1097                         }
1098                         else if(SIZE(np) < size)
1099                         {
1100                                 if((sp = RIGHT(np)) != NIL(TREE*))
1101                                         np = sp;
1102                                 else
1103                                 {       /**/ COUNT(N_list);
1104                                         RIGHT(np) = tp;
1105                                         break;
1106                                 }
1107                         }
1108                         else /* SIZE(np) == size */
1109                         {
1110                                 if((sp = LINK(np)) != NIL(TREE*))
1111                                 {
1112                                         LINK(tp) = sp;
1113                                         BACK(sp) = tp;
1114                                 }
1115                                 LINK(np) = tp;
1116                                 BACK(tp) = np;
1117                                 SETNOTREE(tp);
1118                                 break;
1119                         }
1120                 }
1121         next:
1122                 if(dequeue || QVOID())
1123                         old = 0;
1124                 else    DEQUEUE(old);
1125         }
1126 }
1127
1128 #endif /* cray */