Heap-Based Overflows on SolarisSPARC

Heap-Based Overflows on Solaris/SPARC

Heap-based overflows are most likely more commonly discovered than stack-based overflows in modern vulnerability research. They are commonly exploited with great reliability; however, they are definitely less reliable to exploit than stack-based overflows. Unlike on the stack, execution flow information isn't stored by definition on the heap.

There are two general methods for executing arbitrary code via a heap overflow. An attacker can either attempt to overwrite program-specific data stored on the heap or to corrupt the heap control structures. Not all heap implementations store control structures in-line on the heap; however, the Solaris System V implementation does.

A stack overflow can be seen as a two-step process. The first step is the actual overflow, which overwrites a saved program counter. The second step is a return, which goes to an arbitrary location in memory. In contrast, a heap overflow, which corrupts control structures, can generally be seen as a three-step process. The first step is of course the overflow, which overwrites control structures. The second step would be the heap implementation processing of the corrupted control structures, resulting in an arbitrary memory overwrite. The final step would be some program operation that results in execution going to a specified location in memory, possibly calling a function pointer or returning with a changed saved instruction pointer. The extra step involved adds a certain degree of unreliability and complicates the process of heap overflows. To exploit them reliably, you must often either repeat an attack or have specific knowledge about the system being exploited.

If useful program-specific information is stored on the heap within reach of the overflow, it is frequently more desirable to overwrite this than control structures. The best target for overwrite is any function pointer, and if it's possible to overwrite one, this method can make heap overflow exploitation more reliable than is possible by overwriting control structures.

Solaris System V Heap Introduction

The Solaris heap implementation is based on a self-adjusting binary tree, ordered by the size of chunks . This leads to a reasonably complicated heap implementation, which results in several ways to achieve exploitation. As is the case on many other heap implementations, chunk locations and sizes are aligned to an 8-byte boundary. The lowest bit of the chunk size is reserved to specify if the current chunk is in use, and the second lowest bit is reserved to specify if the previous block in memory is free.

The free() function ( _free_unlocked ) itself does virtually nothing, and all the operations associated with freeing a memory chunk are performed by a function named realfree() . The free() function simply performs some minimal sanity checks on the chunk being freed and then places it in a free list which will be dealt with later. When the free list becomes full, or malloc/realloc are called, a function called cleanfree() flushes the free list.

The Solaris heap implementation performs operations typical of most heap implementations. The heap is grown via the sbrk system call when necessary, and adjacent free chunks are consolidated when possible.

Heap Tree Structure

It is not truly necessary to understand the tree structure of the Solaris heap to exploit heap-based overflows; however, for methods other than the most simple knowing the tree structure is useful. The full source code for the heap implementation used in the generic Solaris libc is shown below. The first source code is malloc.c; the second, mallint.h .

 /*     Copyright (c) 1988 AT&T     */ /*     All Rights Reserved         */     /*   THIS IS UNPUBLISHED PROPRIETARY SOURCE CODE OF AT&T */ /*   The copyright notice above does not evidence any    */ /*   actual or intended publication of such source code. */     /*  * Copyright (c) 1996, by Sun Microsystems, Inc.  * All rights reserved.  */     #pragma    ident   "@(#)malloc.c  1.18  98/07/21 SMI"  /* SVr4.0 1.30 */     /*LINTLIBRARY*/     /*  *   Memory management: malloc(), realloc(), free().  *  *   The following #-parameters may be redefined:  *   SEGMENTED: if defined, memory requests are assumed to be  *          non-contiguous across calls of GETCORE's.  *   GETCORE: a function to get more core memory. If not SEGMENTED,  *          GETCORE(0) is assumed to return the next available  *          address. Default is 'sbrk'.  *   ERRCORE: the error code as returned by GETCORE.  *          Default is (char *)(-1).  *   CORESIZE: a desired unit (measured in bytes) to be used  *          with GETCORE. Default is (1024*ALIGN).  *  *   This algorithm is based on a  best fit strategy with lists of  *   free elts maintained in a self-adjusting binary tree. Each list  *   contains all elts of the same size. The tree is ordered by size.  *   For results on self-adjusting trees, see the paper:  *          Self-Adjusting Binary Trees,  *          DD Sleator & RE Tarjan, JACM 1985.  *  *   The header of a block contains the size of the data part in bytes.  *   Since the size of a block is 0%4, the low two bits of the header  *   are free and used as follows:  *  *          BIT0:   1 for busy (block is in use), 0 for free.  *          BIT1:   if the block is busy, this bit is 1 if the  *                  preceding block in contiguous memory is free.  *                  Otherwise, it is always 0.  */     #include "synonyms.h" #include <mtlib.h> #include <sys/types.h> #include <stdlib.h> #include <string.h> #include <limits.h> #include "mallint.h"     static TREE  *Root,         /* root of the free tree */              *Bottom,       /* the last free chunk in the arena */              *_morecore(size_t);  /* function to get more core */     static char  *Baddr;             /* current high address of the arena */ static char  *Lfree;        /* last freed block with data intact */     static void  t_delete(TREE *); static void  t_splay(TREE *); static void  realfree(void *); static void  cleanfree(void *); static void  *_malloc_unlocked(size_t);     #define      FREESIZE (1<<5) /* size for preserving free blocks until next malloc */ #define     FREEMASK FREESIZE-1     static void *flist[FREESIZE];     /* list of blocks to be freed on next malloc */ static int freeidx;         /* index of free blocks in flist % FREESIZE */     /*  *   Allocation of small blocks  */ static TREE  *List[MINSIZE/WORDSIZE-1]; /* lists of small blocks */     static void * _smalloc(size_t size) {      TREE    *tp;      size_t  i;          ASSERT(size % WORDSIZE == 0);      /* want to return a unique pointer on malloc(0) */      if (size == 0)             size = WORDSIZE;          /* list to use */      i = size / WORDSIZE - 1;          if (List[i] == NULL) {             TREE *np;             int n;             /* number of blocks to get at one time */ #define     NPS (WORDSIZE*8)             ASSERT((size + WORDSIZE) * NPS >= MINSIZE);                 /* get NPS of these block types */             if ((List[i] = _malloc_unlocked((size + WORDSIZE) * NPS)) == 0)                     return (0);                 /* make them into a link list */             for (n = 0, np = List[i]; n < NPS; ++n) {                     tp = np;                     SIZE(tp) = size;                     np = NEXT(tp);                     AFTER(tp) = np;             }             AFTER(tp) = NULL;      }          /* allocate from the head of the queue */      tp = List[i];      List[i] = AFTER(tp);      SETBIT0(SIZE(tp));      return (DATA(tp)); }     void * malloc(size_t size) {      void *ret;      (void) _mutex_lock(&__malloc_lock);      ret = _malloc_unlocked(size);      (void) _mutex_unlock(&__malloc_lock);      return (ret); }     static void * _malloc_unlocked(size_t size) {      size_t  n;      TREE    *tp, *sp;      size_t  o_bit1;          COUNT(nmalloc);      ASSERT(WORDSIZE == ALIGN);          /* make sure that size is 0 mod ALIGN */      ROUND(size);          /* see if the last free block can be used */      if (Lfree) {             sp = BLOCK(Lfree);             n = SIZE(sp);             CLRBITS01(n);             if (n == size) {                     /*                      * exact match, use it as is                      */                     freeidx = (freeidx + FREESIZE - 1) &                            FREEMASK; /* 1 back */                     flist[freeidx] = Lfree = NULL;                     return (DATA(sp));              } else if (size >= MINSIZE && n > size) {                     /*                      * got a big enough piece                      */                     freeidx = (freeidx + FREESIZE - 1) &                             FREEMASK; /* 1 back */                     flist[freeidx] = Lfree = NULL;                     o_bit1 = SIZE(sp) & BIT1;                     SIZE(sp) = n;                     goto leftover;              }      }      o_bit1 = 0;          /* perform free's of space since last malloc */      cleanfree(NULL);          /* small blocks */      if (size < MINSIZE)             return (_smalloc(size));          /* search for an elt of the right size */      sp = NULL;      n  = 0;      if (Root) {             tp = Root;             while (1) {                     /* branch left */                     if (SIZE(tp) >= size) {                            if (n == 0  n >= SIZE(tp)) {                                    sp = tp;                                    n = SIZE(tp);                            }                            if (LEFT(tp))                                    tp = LEFT(tp);                            else                                    break;                     } else { /* branch right */                            if (RIGHT(tp))                                    tp = RIGHT(tp);                            else                                    break;                     }              }                  if (sp) {                     t_delete(sp);              } else if (tp != Root) {                     /* make the searched-to element the root */                     t_splay(tp);                     Root = tp;              }           }               /* if found none fitted in the tree */      if (!sp) {           if (Bottom && size <= SIZE(Bottom)) {                sp = Bottom;                CLRBITS01(SIZE(sp));           } else if ((sp = _morecore(size)) == NULL) /* no more memory */                return (NULL);      }          /* tell the forward neighbor that we're busy */      CLRBIT1(SIZE(NEXT(sp)));          ASSERT(ISBIT0(SIZE(NEXT(sp))));     leftover:      /* if the leftover is enough for a new free piece */      if ((n = (SIZE(sp) - size)) >= MINSIZE + WORDSIZE) {           n -= WORDSIZE;           SIZE(sp) = size;           tp = NEXT(sp);           SIZE(tp) = nBIT0;           realfree(DATA(tp));      } else if (BOTTOM(sp))           Bottom = NULL;          /* return the allocated space */      SIZE(sp) = BIT0  o_bit1;      return (DATA(sp)); }     /*  * realloc().  *  * If the block size is increasing, we try forward merging first.  * This is not best-fit but it avoids some data recopying.  */ void * realloc(void *old, size_t size) {      TREE     *tp, *np;      size_t     ts;      char     *new;          COUNT(nrealloc);          /* pointer to the block */      (void) _mutex_lock(&__malloc_lock);      if (old == NULL) {           new = _malloc_unlocked(size);           (void) _mutex_unlock(&__malloc_lock);           return (new);      }          /* perform free's of space since last malloc */      cleanfree(old);          /* make sure that size is 0 mod ALIGN */      ROUND(size);          tp = BLOCK(old);      ts = SIZE(tp);          /* if the block was freed, data has been destroyed. */      if (!ISBIT0(ts)) {           (void) _mutex_unlock(&__malloc_lock);           return (NULL);      }          /* nothing to do */      CLRBITS01(SIZE(tp));      if (size == SIZE(tp)) {           SIZE(tp) = ts;           (void) _mutex_unlock(&__malloc_lock);           return (old);      }          /* special cases involving small blocks */      if (size < MINSIZE  SIZE(tp) < MINSIZE)           goto call_malloc;          /* block is increasing in size, try merging the next block */      if (size > SIZE(tp)) {           np = NEXT(tp);           if (!ISBIT0(SIZE(np))) {                ASSERT(SIZE(np) >= MINSIZE);                ASSERT(!ISBIT1(SIZE(np)));                SIZE(tp) += SIZE(np) + WORDSIZE;                if (np != Bottom)                     t_delete(np);                else                     Bottom = NULL;                CLRBIT1(SIZE(NEXT(np)));           }     #ifndef SEGMENTED           /* not enough & at TRUE end of memory, try extending core */           if (size > SIZE(tp) && BOTTOM(tp) && GETCORE(0) == Baddr) {                Bottom = tp;                if ((tp = _morecore(size)) == NULL) {                     tp = Bottom;                     Bottom = NULL;                     }           } #endif      }          /* got enough space to use */      if (size <= SIZE(tp)) {           size_t n;     chop_big:           if ((n = (SIZE(tp) - size)) >= MINSIZE + WORDSIZE) {                n -= WORDSIZE;                SIZE(tp) = size;                np = NEXT(tp);                SIZE(np) = nBIT0;                realfree(DATA(np));           } else if (BOTTOM(tp))                Bottom = NULL;               /* the previous block may be free */           SETOLD01(SIZE(tp), ts);           (void) _mutex_unlock(&__malloc_lock);           return (old);      }          /* call malloc to get a new block */ call_malloc:      SETOLD01(SIZE(tp), ts);      if ((new = _malloc_unlocked(size)) != NULL) {           CLRBITS01(ts);           if (ts > size)                ts = size;           MEMCOPY(new, old, ts);           _free_unlocked(old);           (void) _mutex_unlock(&__malloc_lock);           return (new);      }          /*       * Attempt special case recovery allocations since malloc() failed:       *       * 1. size <= SIZE(tp) < MINSIZE       *     Simply return the existing block       * 2. SIZE(tp) < size < MINSIZE       *     malloc() may have failed to allocate the chunk of       *     small blocks. Try asking for MINSIZE bytes.       * 3. size < MINSIZE <= SIZE(tp)       *     malloc() may have failed as with 2.  Change to       *     MINSIZE allocation which is taken from the beginning       *     of the current block.       * 4. MINSIZE <= SIZE(tp) < size       *     If the previous block is free and the combination of       *     these two blocks has at least size bytes, then merge       *     the two blocks copying the existing contents backwards.       */      CLRBITS01(SIZE(tp));      if (SIZE(tp) < MINSIZE) {           if (size < SIZE(tp)) {               /* case 1. */                SETOLD01(SIZE(tp), ts);                (void) _mutex_unlock(&__malloc_lock);                return (old);           } else if (size < MINSIZE) {          /* case 2. */                size = MINSIZE;                goto call_malloc;           }      } else if (size < MINSIZE) {               /* case 3. */           size = MINSIZE;           goto chop_big;      } else if (ISBIT1(ts) &&          (SIZE(np = LAST(tp)) + SIZE(tp) + WORDSIZE) >= size) {           ASSERT(!ISBIT0(SIZE(np)));           t_delete(np);           SIZE(np) += SIZE(tp) + WORDSIZE;           /*            * Since the copy may overlap, use memmove() if available.            * Otherwise, copy by hand.            */           (void) memmove(DATA(np), old, SIZE(tp));           old = DATA(np);           tp = np;           CLRBIT1(ts);           goto chop_big;      }      SETOLD01(SIZE(tp), ts);      (void) _mutex_unlock(&__malloc_lock);      return (NULL); }     /*  * realfree().  *  * Coalescing of adjacent free blocks is done first.  * Then, the new free block is leaf-inserted into the free tree  * without splaying. This strategy does not guarantee the amortized  * O(nlogn) behavior for the insert/delete/find set of operations  * on the tree. In practice, however, free is much more infrequent  * than malloc/realloc and the tree searches performed by these  * functions adequately keep the tree in balance.  */ static void realfree(void *old) {      TREE     *tp, *sp, *np;      size_t     ts, size;          COUNT(nfree);          /* pointer to the block */      tp = BLOCK(old);      ts = SIZE(tp);      if (!ISBIT0(ts))           return;      CLRBITS01(SIZE(tp));          /* small block, put it in the right linked list */      if (SIZE(tp) < MINSIZE) {           ASSERT(SIZE(tp) / WORDSIZE >= 1);           ts = SIZE(tp) / WORDSIZE - 1;           AFTER(tp) = List[ts];           List[ts] = tp;           return;      }          /* see if coalescing with next block is warranted */      np = NEXT(tp);      if (!ISBIT0(SIZE(np))) {           if (np != Bottom)                t_delete(np);           SIZE(tp) += SIZE(np) + WORDSIZE;      }          /* the same with the preceding block */      if (ISBIT1(ts)) {           np = LAST(tp);           ASSERT(!ISBIT0(SIZE(np)));           ASSERT(np != Bottom);           t_delete(np);           SIZE(np) += SIZE(tp) + WORDSIZE;           tp = np;      }          /* initialize tree info */      PARENT(tp) = LEFT(tp) = RIGHT(tp) = LINKFOR(tp) = NULL;          /* the last word of the block contains self's address */      *(SELFP(tp)) = tp;          /* set bottom block, or insert in the free tree */      if (BOTTOM(tp))           Bottom = tp;      else {           /* search for the place to insert */           if (Root) {                size = SIZE(tp);                np = Root;                while (1) {                     if (SIZE(np) > size) {                          if (LEFT(np))                               np = LEFT(np);                          else {                               LEFT(np) = tp;                               PARENT(tp) = np;                               break;                          }                     } else if (SIZE(np) < size) {                          if (RIGHT(np))                               np = RIGHT(np);                          else {                               RIGHT(np) = tp;                               PARENT(tp) = np;                               break;                          }                     } else {                          if ((sp = PARENT(np)) != NULL) {                               if (np == LEFT(sp))                                    LEFT(sp) = tp;                               else                                    RIGHT(sp) = tp;                               PARENT(tp) = sp;                          } else                               Root = tp;                              /* insert to head of list */                          if ((sp = LEFT(np)) != NULL)                               PARENT(sp) = tp;                          LEFT(tp) = sp;                              if ((sp = RIGHT(np)) != NULL)                               PARENT(sp) = tp;                          RIGHT(tp) = sp;                              /* doubly link list */                          LINKFOR(tp) = np;                          LINKBAK(np) = tp;                          SETNOTREE(np);                              break;                     }                }           } else                Root = tp;      }          /* tell next block that this one is free */      SETBIT1(SIZE(NEXT(tp)));          ASSERT(ISBIT0(SIZE(NEXT(tp)))); }     /*  * Get more core. Gaps in memory are noted as busy blocks.  */ static TREE * _morecore(size_t size) {      TREE     *tp;      size_t     n, offset;      char     *addr;      size_t     nsize;          /* compute new amount of memory to get */      tp = Bottom;      n = size + 2 * WORDSIZE;      addr = GETCORE(0);          if (addr == ERRCORE)           return (NULL);          /* need to pad size out so that addr is aligned */      if ((((size_t)addr) % ALIGN) != 0)           offset = ALIGN - (size_t)addr % ALIGN;      else           offset = 0;     #ifndef SEGMENTED      /* if not segmented memory, what we need may be smaller */      if (addr == Baddr) {           n -= WORDSIZE;           if (tp != NULL)                n -= SIZE(tp);      } #endif          /* get a multiple of CORESIZE */      n = ((n - 1) / CORESIZE + 1) * CORESIZE;      nsize = n + offset;          if (nsize == ULONG_MAX)           return (NULL);          if (nsize <= LONG_MAX) {           if (GETCORE(nsize) == ERRCORE)                return (NULL);      } else {           intptr_t     delta;           /*            * the value required is too big for GETCORE() to deal with            * in one go, so use GETCORE() at most 2 times instead.            */           delta = LONG_MAX;           while (delta > 0) {                if (GETCORE(delta) == ERRCORE) {                     if (addr != GETCORE(0))                          (void) GETCORE(-LONG_MAX);                     return (NULL);                }                nsize -= LONG_MAX;                delta = nsize;           }      }          /* contiguous memory */      if (addr == Baddr) {           ASSERT(offset == 0);           if (tp) {                addr = (char *)tp;                n += SIZE(tp) + 2 * WORDSIZE;           } else {                addr = Baddr - WORDSIZE;                n += WORDSIZE;           }      } else           addr += offset;          /* new bottom address */      Baddr = addr + n;          /* new bottom block */      tp = (TREE *)addr;      SIZE(tp) = n - 2 * WORDSIZE;      ASSERT((SIZE(tp) % ALIGN) == 0);          /* reserved the last word to head any noncontiguous memory */      SETBIT0(SIZE(NEXT(tp)));          /* non-contiguous memory, free old bottom block */      if (Bottom && Bottom != tp) {           SETBIT0(SIZE(Bottom));           realfree(DATA(Bottom));      }          return (tp); }     /*  * Tree rotation functions (BU: bottom-up, TD: top-down)  */     #define     LEFT1(x, y)          \                if ((RIGHT(x) = LEFT(y)) != NULL) PARENT(RIGHT(x)) = x;\                if ((PARENT(y) = PARENT(x)) != NULL)\                     if (LEFT(PARENT(x)) == x) LEFT(PARENT(y)) = y;\                     else RIGHT(PARENT(y)) = y;\                LEFT(y) = x; PARENT(x) = y     #define     RIGHT1(x, y)          \                if ((LEFT(x) = RIGHT(y)) != NULL) PARENT(LEFT(x)) = x;\                if ((PARENT(y) = PARENT(x)) != NULL)\                     if (LEFT(PARENT(x)) == x) LEFT(PARENT(y)) = y;\                     else RIGHT(PARENT(y)) = y;\                RIGHT(y) = x; PARENT(x) = y     #define     BULEFT2(x, y, z)     \                if ((RIGHT(x) = LEFT(y)) != NULL) PARENT(RIGHT(x)) = x;\                if ((RIGHT(y) = LEFT(z)) != NULL) PARENT(RIGHT(y)) = y;\                if ((PARENT(z) = PARENT(x)) != NULL)\                     if (LEFT(PARENT(x)) == x) LEFT(PARENT(z)) = z;\                     else RIGHT(PARENT(z)) = z;\                LEFT(z) = y; PARENT(y) = z; LEFT(y) = x; PARENT(x) = y     #define     BURIGHT2(x, y, z)     \                if ((LEFT(x) = RIGHT(y)) != NULL) PARENT(LEFT(x)) = x;\                if ((LEFT(y) = RIGHT(z)) != NULL) PARENT(LEFT(y)) = y;\                if ((PARENT(z) = PARENT(x)) != NULL)\                     if (LEFT(PARENT(x)) == x) LEFT(PARENT(z)) = z;\                     else RIGHT(PARENT(z)) = z;\                RIGHT(z) = y; PARENT(y) = z; RIGHT(y) = x; PARENT(x) = y     #define     TDLEFT2(x, y, z)     \                if ((RIGHT(y) = LEFT(z)) != NULL) PARENT(RIGHT(y)) = y;\                if ((PARENT(z) = PARENT(x)) != NULL)\                     if (LEFT(PARENT(x)) == x) LEFT(PARENT(z)) = z;\                     else RIGHT(PARENT(z)) = z;\                PARENT(x) = z; LEFT(z) = x;     #define     TDRIGHT2(x, y, z)     \                if ((LEFT(y) = RIGHT(z)) != NULL) PARENT(LEFT(y)) = y;\                if ((PARENT(z) = PARENT(x)) != NULL)\                     if (LEFT(PARENT(x)) == x) LEFT(PARENT(z)) = z;\                     else RIGHT(PARENT(z)) = z;\                PARENT(x) = z; RIGHT(z) = x;     /*  * Delete a tree element  */ static void t_delete(TREE *op) {      TREE     *tp, *sp, *gp;          /* if this is a non-tree node */      if (ISNOTREE(op)) {           tp = LINKBAK(op);           if ((sp = LINKFOR(op)) != NULL)                LINKBAK(sp) = tp;           LINKFOR(tp) = sp;           return;      }          /* make op the root of the tree */      if (PARENT(op))           t_splay(op);          /* if this is the start of a list */      if ((tp = LINKFOR(op)) != NULL) {           PARENT(tp) = NULL;           if ((sp = LEFT(op)) != NULL)                PARENT(sp) = tp;           LEFT(tp) = sp;               if ((sp = RIGHT(op)) != NULL)                PARENT(sp) = tp;           RIGHT(tp) = sp;               Root = tp;           return;      }          /* if op has a non-null left subtree */      if ((tp = LEFT(op)) != NULL) {           PARENT(tp) = NULL;               if (RIGHT(op)) {                /* make the right-end of the left subtree its root */                while ((sp = RIGHT(tp)) != NULL) {                     if ((gp = RIGHT(sp)) != NULL) {                          TDLEFT2(tp, sp, gp);                          tp = gp;                     } else {                          LEFT1(tp, sp);                          tp = sp;                     }                }                    /* hook the right subtree of op to the above elt */                RIGHT(tp) = RIGHT(op);                PARENT(RIGHT(tp)) = tp;           }      } else if ((tp = RIGHT(op)) != NULL)     /* no left subtree */           PARENT(tp) = NULL;          Root = tp; }     /*  * Bottom up splaying (simple version).  * The basic idea is to roughly cut in half the  * path from Root to tp and make tp the new root.  */ static void t_splay(TREE *tp) {      TREE     *pp, *gp;          /* iterate until tp is the root */      while ((pp = PARENT(tp)) != NULL) {           /* grandparent of tp */           gp = PARENT(pp);               /* x is a left child */           if (LEFT(pp) == tp) {                if (gp && LEFT(gp) == pp) {                     BURIGHT2(gp, pp, tp);                } else {                     RIGHT1(pp, tp);                }           } else {                ASSERT(RIGHT(pp) == tp);                if (gp && RIGHT(gp) == pp) {                     BULEFT2(gp, pp, tp);                } else {                     LEFT1(pp, tp);                }           }      } }      /*  *     free().  *     Performs a delayed free of the block pointed to  *     by old. The pointer to old is saved on a list, flist,  *     until the next malloc or realloc. At that time, all the  *     blocks pointed to in flist are actually freed via  *     realfree(). This allows the contents of free blocks to  *     remain undisturbed until the next malloc or realloc.  */ void free(void *old) {      (void) _mutex_lock(&__malloc_lock);      _free_unlocked(old);      (void) _mutex_unlock(&__malloc_lock); }     void _free_unlocked(void *old) {      int     i;          if (old == NULL)           return;          /*       * Make sure the same data block is not freed twice.       * 3 cases are checked.  It returns immediately if either       * one of the conditions is true.       *     1. Last freed.       *     2. Not in use or freed already.       *     3. In the free list.       */      if (old == Lfree)           return;      if (!ISBIT0(SIZE(BLOCK(old))))           return;      for (i = 0; i < freeidx; i++)           if (old == flist[i])                return;          if (flist[freeidx] != NULL)           realfree(flist[freeidx]);      flist[freeidx] = Lfree = old;      freeidx = (freeidx + 1) & FREEMASK; /* one forward */ }     /*  * cleanfree() frees all the blocks pointed to be flist.  *  * realloc() should work if it is called with a pointer  * to a block that was freed since the last call to malloc() or  * realloc(). If cleanfree() is called from realloc(), ptr  * is set to the old block and that block should not be  * freed since it is actually being reallocated.  */ static void cleanfree(void *ptr) {      char     **flp;          flp = (char **)&(flist[freeidx]);      for (;;) {           if (flp == (char **)&(flist[0]))                flp = (char **)&(flist[FREESIZE]);           if (*--flp == NULL)                break;           if (*flp != ptr)                realfree(*flp);           *flp = NULL;      }      freeidx = 0;      Lfree = NULL; }     /*     Copyright (c) 1988 AT&T     */ /*       All Rights Reserved       */     /*     THIS IS UNPUBLISHED PROPRIETARY SOURCE CODE OF AT&T     */ /*     The copyright notice above does not evidence any        */ /*     actual or intended publication of such source code.     */     /*  * Copyright (c) 1996-1997 by Sun Microsystems, Inc.  * All rights reserved.  */     #pragma     ident     "@(#)mallint.h     1.11     97/12/02 SMI"     /* SVr4.0 1.2     */     #include <sys/isa_defs.h> #include <stdlib.h> #include <memory.h> #include <thread.h> #include <synch.h> #include <mtlib.h>     /* debugging macros */ #ifdef     DEBUG #define     ASSERT(p)     ((void) ((p)  (abort(), 0))) #define     COUNT(n)     ((void) n++) static int          nmalloc, nrealloc, nfree; #else #define     ASSERT(p)     ((void)0) #define     COUNT(n)     ((void)0) #endif /* DEBUG */     /* function to copy data from one area to another */ #define     MEMCOPY(to, fr, n)     ((void) memcpy(to, fr, n))     /* for conveniences */ #ifndef NULL #define     NULL          (0) #endif     #define     reg          register #define     WORDSIZE     (sizeof (WORD)) #define     MINSIZE          (sizeof (TREE) - sizeof (WORD)) #define     ROUND(s)     if (s % WORDSIZE) s += (WORDSIZE - (s % WORDSIZE))     #ifdef     DEBUG32 /*  * The following definitions ease debugging  * on a machine in which sizeof(pointer) == sizeof(int) == 4.  * These definitions are not portable.  *  * Alignment (ALIGN) changed to 8 for SPARC ldd/std. */ #define     ALIGN     8 typedef int     WORD; typedef struct _t_ {      size_t          t_s;      struct _t_     *t_p;      struct _t_     *t_l;      struct _t_     *t_r;      struct _t_     *t_n;      struct _t_     *t_d; } TREE; #define     SIZE(b)          ((b)->t_s) #define     AFTER(b)     ((b)->t_p) #define     PARENT(b)     ((b)->t_p) #define     LEFT(b)          ((b)->t_l) #define     RIGHT(b)     ((b)->t_r) #define     LINKFOR(b)     ((b)->t_n) #define     LINKBAK(b)     ((b)->t_p)     #else     /* !DEBUG32 */ /*  * All of our allocations will be aligned on the least multiple of 4,  * at least, so the two low order bits are guaranteed to be available.  */ #ifdef _LP64 #define     ALIGN          16 #else #define     ALIGN          8 #endif     /* the proto-word; size must be ALIGN bytes */ typedef union _w_ {      size_t          w_i;          /* an unsigned int */      struct _t_     *w_p;          /* a pointer */      char          w_a[ALIGN];     /* to force size */ } WORD;     /* structure of a node in the free tree */ typedef struct _t_ {      WORD     t_s;     /* size of this element */      WORD     t_p;     /* parent node */      WORD     t_l;     /* left child */      WORD     t_r;     /* right child */      WORD     t_n;     /* next in link list */      WORD     t_d;     /* dummy to reserve space for self-pointer */ } TREE;     /* usable # of bytes in the block */ #define     SIZE(b)          (((b)->t_s).w_i)     /* free tree pointers */ #define     PARENT(b)     (((b)->t_p).w_p) #define     LEFT(b)          (((b)->t_l).w_p) #define     RIGHT(b)     (((b)->t_r).w_p)     /* forward link in lists of small blocks */ #define     AFTER(b)     (((b)->t_p).w_p)     /* forward and backward links for lists in the tree */ #define     LINKFOR(b)     (((b)->t_n).w_p) #define     LINKBAK(b)     (((b)->t_p).w_p)     #endif     /* DEBUG32 */     /* set/test indicator if a block is in the tree or in a list */ #define     SETNOTREE(b)     (LEFT(b) = (TREE *)(-1)) #define     ISNOTREE(b)     (LEFT(b) == (TREE *)(-1))     /* functions to get information on a block */ #define     DATA(b)          (((char *)(b)) + WORDSIZE) #define     BLOCK(d)     ((TREE *)(((char *)(d)) - WORDSIZE)) #define     SELFP(b)     ((TREE **)(((char *)(b)) + SIZE(b))) #define     LAST(b)          (*((TREE **)(((char *)(b)) - WORDSIZE))) #define     NEXT(b)          ((TREE *)(((char *)(b)) + SIZE(b) + WORDSIZE)) #define     BOTTOM(b)     ((DATA(b) + SIZE(b) + WORDSIZE) == Baddr)     /* functions to set and test the lowest two bits of a word */ #define     BIT0          (01)          /* ...001 */ #define     BIT1          (02)          /* ...010 */ #define     BITS01          (03)          /* ...011 */ #define     ISBIT0(w)     ((w) & BIT0)     /* Is busy? */ #define     ISBIT1(w)     ((w) & BIT1)     /* Is the preceding free? */ #define     SETBIT0(w)     ((w) = BIT0)     /* Block is busy */ #define     SETBIT1(w)     ((w) = BIT1)     /* The preceding is free */ #define     CLRBIT0(w)     ((w) &= ~BIT0)     /* Clean bit0 */ #define     CLRBIT1(w)     ((w) &= ~BIT1)     /* Clean bit1 */ #define     SETBITS01(w)     ((w) = BITS01)     /* Set bits 0 & 1 */ #define     CLRBITS01(w)     ((w) &= ~BITS01) /* Clean bits 0 & 1 */ #define     SETOLD01(n, o)     ((n) = (BITS01 & (o)))     /* system call to get more core */ #define     GETCORE          sbrk #define     ERRCORE          ((void *)(-1)) #define     CORESIZE     (1024*ALIGN)     extern void     *GETCORE(size_t); extern void     _free_unlocked(void *);     #ifdef _REENTRANT extern mutex_t __malloc_lock; #endif /* _REENTRANT */ 

The basic element of the TREE structure is defined as a WORD , having the following definition:

 /* the proto-word; size must be ALIGN bytes */ typedef union _w_ {      size_t          w_i;          /* an unsigned int */      struct _t_     *w_p;          /* a pointer */      char          w_a[ALIGN];     /* to force size */ } WORD; 

ALIGN is defined to be 8 for the 32-bit version of libc, giving the union a total size of 8 bytes.

The structure of a node in the free tree is defined as follows:

 typedef struct _t_ {      WORD     t_s;     /* size of this element */      WORD     t_p;     /* parent node */      WORD     t_l;     /* left child */      WORD     t_r;     /* right child */      WORD     t_n;     /* next in link list */      WORD     t_d;     /* dummy to reserve space for self-pointer */ } TREE; 

This structure is composed of six WORD elements, and therefore has a size of 48 bytes. This ends up being the minimum size for any true heap chunk, including the basic header.