/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */

/*
 * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

/*      Copyright (c) 1988 AT&T */
/*        All Rights Reserved   */

/*
 *      Memory management: malloc(), realloc(), free(), memalign().
 *
 *      The following #-parameters may be redefined:
 *      GETCORE: a function to get more core memory.
 *              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 "mallint.h"

static  mutex_t __watch_malloc_lock = DEFAULTMUTEX;

static  TREE    *Root;          /* root of the free tree */
static  TREE    *Bottom;        /* the last free chunk in the arena */
static  char    *Baddr;         /* current high address of the arena */

static  void    t_delete(TREE *);
static  void    t_splay(TREE *);
static  void    realfree(void *);
static  void    *malloc_unlocked(size_t);
static  void    free_unlocked(void *);
static  TREE    *morecore(size_t);

static  void    protect(TREE *);
static  void    unprotect(TREE *);

#define FREEPAT 0
#define LIVEPAT 1

/*
 * Patterns to be copied into freed blocks and allocated blocks.
 * 0xfeedbeef and 0xfeedface are invalid pointer values in all programs.
 */
static  uint64_t        patterns[2] = {
        0xdeadbeefdeadbeefULL,  /* pattern in a freed block */
        0xbaddcafebaddcafeULL   /* pattern in an allocated block */
};

static void
copy_pattern(int pat, TREE *tp)
{
        uint64_t pattern = patterns[pat];
        size_t sz = SIZE(tp) / sizeof (uint64_t);
        /* LINTED improper alignment */
        uint64_t *datap = (uint64_t *)DATA(tp);

        while (sz--)
                *datap++ = pattern;
}

/*
 * Keep lists of small blocks, LIFO order.
 */
static  TREE    *List[MINSIZE/WORDSIZE-1];
static  TREE    *Last[MINSIZE/WORDSIZE-1];

/* number of blocks to get at one time */
#define NPS     (WORDSIZE*8)

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;
                ASSERT((size + WORDSIZE) * NPS >= MINSIZE);

                /* get NPS of these block types */
                if ((np = malloc_unlocked((size + WORDSIZE)*NPS)) == NULL)
                        return (NULL);

                /* make them into a link list */
                for (n = 0, List[i] = np; n < NPS; ++n) {
                        tp = np;
                        SIZE(tp) = size;
                        copy_pattern(FREEPAT, tp);
                        if (n == NPS - 1) {
                                Last[i] = tp;
                                np = NULL;
                        } else {
                                /* LINTED improper alignment */
                                np = NEXT(tp);
                        }
                        AFTER(tp) = np;
                        protect(tp);
                }
        }

        /* allocate from the head of the queue */
        tp = List[i];
        unprotect(tp);
        if ((List[i] = AFTER(tp)) == NULL)
                Last[i] = NULL;
        copy_pattern(LIVEPAT, tp);
        SETBIT0(SIZE(tp));
        protect(tp);
        return (DATA(tp));
}

void *
malloc(size_t size)
{
        void    *ret;
        (void) mutex_lock(&__watch_malloc_lock);
        ret = malloc_unlocked(size);
        (void) mutex_unlock(&__watch_malloc_lock);
        return (ret);
}

static void *
malloc_unlocked(size_t size)
{
        size_t  n;
        TREE    *tp, *sp, *tmp;

        COUNT(nmalloc);
        ASSERT(WORDSIZE == ALIGN);

        /* check for size that could overflow calculations */
        if (size > MAX_MALLOC) {
                errno = ENOMEM;
                return (NULL);
        }
        /* make sure that size is 0 mod ALIGN */
        ROUND(size);

        /* small blocks */
        if (size < MINSIZE)
                return (smalloc(size));

        /* search for an elt of the right size */
        sp = NULL;
        n = 0;
        if (Root) {
                tp = Root;
                for (;;) {
                        unprotect(tp);
                        if (SIZE(tp) >= size) { /* branch left */
                                if (n == 0 || n >= SIZE(tp)) {
                                        sp = tp;
                                        n = SIZE(tp);
                                }
                                if ((tmp = LEFT(tp)) != NULL) {
                                        protect(tp);
                                        tp = tmp;
                                } else {
                                        protect(tp);
                                        break;
                                }
                        } else {                /* branch right */
                                if ((tmp = RIGHT(tp)) != NULL) {
                                        protect(tp);
                                        tp = tmp;
                                } else {
                                        protect(tp);
                                        break;
                                }
                        }
                }

                if (sp) {
                        unprotect(sp);
                        t_delete(sp);
                } else if (tp != Root) {
                        /* make the searched-to element the root */
                        unprotect(tp);
                        t_splay(tp);
                        protect(tp);
                        Root = tp;
                }
        }

        /* if found none fitted in the tree */
        if (sp == NULL) {
                if (Bottom) {
                        unprotect(Bottom);
                        if (size <= SIZE(Bottom)) {
                                sp = Bottom;
                                CLRBITS01(SIZE(sp));
                        } else {
                                protect(Bottom);
                                if ((sp = morecore(size)) == NULL)
                                        return (NULL);
                        }
                } else {
                        if ((sp = morecore(size)) == NULL)
                                return (NULL);
                }
        }

        /* tell the forward neighbor that we're busy */
        /* LINTED improper alignment */
        tmp = NEXT(sp);
        unprotect(tmp);
        CLRBIT1(SIZE(tmp));
        ASSERT(ISBIT0(SIZE(tmp)));
        protect(tmp);

        /* if the leftover is enough for a new free piece */
        if ((n = (SIZE(sp) - size)) >= MINSIZE + WORDSIZE) {
                n -= WORDSIZE;
                SIZE(sp) = size;
                /* LINTED improper alignment */
                tp = NEXT(sp);
                SIZE(tp) = n | BIT0;
                realfree(DATA(tp));
        } else if (BOTTOM(sp))
                Bottom = NULL;

        /* return the allocated space */
        copy_pattern(LIVEPAT, sp);
        SIZE(sp) |= BIT0;
        protect(sp);
        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);

        /* check for size that could overflow calculations */
        if (size > MAX_MALLOC) {
                errno = ENOMEM;
                return (NULL);
        }

        /* pointer to the block */
        (void) mutex_lock(&__watch_malloc_lock);
        if (old == NULL) {
                new = malloc_unlocked(size);
                (void) mutex_unlock(&__watch_malloc_lock);
                return (new);
        }

        /* make sure that size is 0 mod ALIGN */
        ROUND(size);

        /* LINTED improper alignment */
        tp = BLOCK(old);
        unprotect(tp);
        ts = SIZE(tp);

        /* if the block was freed, data has been destroyed. */
        if (!ISBIT0(ts)) {
                /* XXX; complain here! */
                protect(tp);
                (void) mutex_unlock(&__watch_malloc_lock);
                errno = EINVAL;
                return (NULL);
        }

        CLRBITS01(SIZE(tp));
        if (size == SIZE(tp)) { /* nothing to do */
                SIZE(tp) = ts;
                protect(tp);
                (void) mutex_unlock(&__watch_malloc_lock);
                return (old);
        }

        /* special cases involving small blocks */
        if (size < MINSIZE || SIZE(tp) < MINSIZE) {
                if (size == 0) {
                        SETOLD01(SIZE(tp), ts);
                        free_unlocked(old);
                        (void) mutex_unlock(&__watch_malloc_lock);
                        return (NULL);
                }
                goto call_malloc;
        }

        /* block is increasing in size, try merging the next block */
        if (size > SIZE(tp)) {
                /* LINTED improper alignment */
                np = NEXT(tp);
                unprotect(np);
                if (ISBIT0(SIZE(np)))
                        protect(np);
                else {
                        TREE *tmp;
                        ASSERT(SIZE(np) >= MINSIZE);
                        ASSERT(!ISBIT1(SIZE(np)));
                        SIZE(tp) += SIZE(np) + WORDSIZE;
                        if (np != Bottom)
                                t_delete(np);
                        else
                                Bottom = NULL;
                        /* LINTED improper alignment */
                        tmp = NEXT(np);
                        unprotect(tmp);
                        CLRBIT1(SIZE(tmp));
                        protect(tmp);
                }

                /* not enough & at TRUE end of memory, try extending core */
                if (size > SIZE(tp) && BOTTOM(tp) && GETCORE(0) == Baddr) {
                        Bottom = tp;
                        protect(Bottom);
                        if ((tp = morecore(size)) == NULL) {
                                tp = Bottom;
                                Bottom = NULL;
                                unprotect(tp);
                        }
                }
        }

        /* 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;
                        /* LINTED improper alignment */
                        np = NEXT(tp);
                        SIZE(np) = n | BIT0;
                        realfree(DATA(np));
                } else if (BOTTOM(tp))
                        Bottom = NULL;

                /* the previous block may be free */
                SETOLD01(SIZE(tp), ts);
                protect(tp);
                (void) mutex_unlock(&__watch_malloc_lock);
                return (old);
        }

call_malloc:    /* call malloc to get a new block */
        SETOLD01(SIZE(tp), ts);
        if ((new = malloc_unlocked(size)) != NULL) {
                CLRBITS01(ts);
                if (ts > size)
                        ts = size;
                (void) memcpy(new, old, ts);
                free_unlocked(old);
                (void) mutex_unlock(&__watch_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);
                        protect(tp);
                        (void) mutex_unlock(&__watch_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)) {
                np = LAST(tp);
                unprotect(np);
                if ((SIZE(np) + SIZE(tp) + WORDSIZE) >= size) {
                        ASSERT(!ISBIT0(SIZE(np)));
                        t_delete(np);
                        SIZE(np) += SIZE(tp) + WORDSIZE;
                        /*
                         * Since the copy may overlap, use memmove().
                         */
                        (void) memmove(DATA(np), old, SIZE(tp));
                        old = DATA(np);
                        tp = np;
                        CLRBIT1(ts);
                        goto chop_big;
                }
                protect(np);
        }
        SETOLD01(SIZE(tp), ts);
        protect(tp);
        (void) mutex_unlock(&__watch_malloc_lock);
        /* malloc() sets errno */
        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) behaviour 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, *tmp;
        size_t  ts, size;

        COUNT(nfree);

        /* pointer to the block */
        /* LINTED improper alignment */
        tp = BLOCK(old);
        unprotect(tp);
        ts = SIZE(tp);
        if (!ISBIT0(ts)) {      /* block is not busy; previously freed? */
                protect(tp);    /* force a watchpoint trap */
                CLRBIT0(SIZE(tp));
                return;
        }
        CLRBITS01(SIZE(tp));
        copy_pattern(FREEPAT, tp);

        /* small block, return it to the tail of its queue */
        if (SIZE(tp) < MINSIZE) {
                ASSERT(SIZE(tp) / WORDSIZE >= 1);
                ts = SIZE(tp) / WORDSIZE - 1;
                AFTER(tp) = NULL;
                protect(tp);
                if (List[ts] == NULL) {
                        List[ts] = tp;
                        Last[ts] = tp;
                } else {
                        sp = Last[ts];
                        unprotect(sp);
                        AFTER(sp) = tp;
                        protect(sp);
                        Last[ts] = tp;
                }
                return;
        }

        /* see if coalescing with next block is warranted */
        /* LINTED improper alignment */
        np = NEXT(tp);
        unprotect(np);
        if (ISBIT0(SIZE(np)))
                protect(np);
        else {
                if (np != Bottom)
                        t_delete(np);
                SIZE(tp) += SIZE(np) + WORDSIZE;
        }

        /* the same with the preceding block */
        if (ISBIT1(ts)) {
                np = LAST(tp);
                unprotect(np);
                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;

        /* 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;
                        for (;;) {
                                unprotect(np);
                                if (SIZE(np) > size) {
                                        if ((tmp = LEFT(np)) != NULL) {
                                                protect(np);
                                                np = tmp;
                                        } else {
                                                LEFT(np) = tp;
                                                PARENT(tp) = np;
                                                protect(np);
                                                break;
                                        }
                                } else if (SIZE(np) < size) {
                                        if ((tmp = RIGHT(np)) != NULL) {
                                                protect(np);
                                                np = tmp;
                                        } else {
                                                RIGHT(np) = tp;
                                                PARENT(tp) = np;
                                                protect(np);
                                                break;
                                        }
                                } else {
                                        if ((sp = PARENT(np)) != NULL) {
                                                unprotect(sp);
                                                if (np == LEFT(sp))
                                                        LEFT(sp) = tp;
                                                else
                                                        RIGHT(sp) = tp;
                                                PARENT(tp) = sp;
                                                protect(sp);
                                        } else
                                                Root = tp;

                                        /* insert to head of list */
                                        if ((sp = LEFT(np)) != NULL) {
                                                unprotect(sp);
                                                PARENT(sp) = tp;
                                                protect(sp);
                                        }
                                        LEFT(tp) = sp;

                                        if ((sp = RIGHT(np)) != NULL) {
                                                unprotect(sp);
                                                PARENT(sp) = tp;
                                                protect(sp);
                                        }
                                        RIGHT(tp) = sp;

                                        /* doubly link list */
                                        LINKFOR(tp) = np;
                                        LINKBAK(np) = tp;
                                        SETNOTREE(np);
                                        protect(np);

                                        break;
                                }
                        }
                } else {
                        Root = tp;
                }
        }

        /*
         * Tell next block that this one is free.
         * The first WORD of the next block contains self's address.
         */
        /* LINTED improper alignment */
        tmp = NEXT(tp);
        unprotect(tmp);
        /* LINTED improper alignment */
        *(SELFP(tp)) = tp;
        SETBIT1(SIZE(tmp));
        ASSERT(ISBIT0(SIZE(tmp)));
        protect(tmp);
        protect(tp);
}

/*
 * Get more core. Gaps in memory are noted as busy blocks.
 */
static TREE *
morecore(size_t size)
{
        TREE    *tp;
        size_t  n, offset, requestsize;
        char    *addr;

        /* compute new amount of memory to get */
        tp = Bottom;
        n = size + 2 * WORDSIZE;
        addr = GETCORE(0);

        if (addr == ERRCORE)
                /* errno set by GETCORE sbrk */
                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;

        if (tp)
                unprotect(tp);

        /* if not segmented memory, what we need may be smaller */
        if (addr == Baddr) {
                n -= WORDSIZE;
                if (tp != NULL)
                        n -= SIZE(tp);
        }

        /* get a multiple of CORESIZE */
        n = ((n - 1) / CORESIZE + 1) * CORESIZE;
        requestsize = n + offset;

        /* check if nsize request could overflow in GETCORE */
        if (requestsize > MAX_MALLOC - (size_t)addr) {
                if (tp)
                        protect(tp);
                errno = ENOMEM;
                return (NULL);
        }

        if (requestsize > MAX_GETCORE) {
                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.
                 * Argument to GETCORE() must be multiple of ALIGN.
                 * If not, GETCORE(-MAX_GETCORE) will not return brk point
                 * to previous value, but will be ALIGN more.
                 * This would leave a small hole.
                 */
                delta = MAX_GETCORE;
                while (delta > 0) {
                        if (GETCORE(delta) == ERRCORE) {
                                if (tp)
                                        protect(tp);
                                if (addr != GETCORE(0))
                                        (void) GETCORE(-MAX_GETCORE);
                                return (NULL);
                        }
                        requestsize -= MAX_GETCORE;
                        delta = requestsize;
                }
        } else if (GETCORE(requestsize) == ERRCORE) {
                if (tp)
                        protect(tp);
                return (NULL);
        }

        /* 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 */
        /* LINTED improper alignment */
        tp = ((TREE *)addr);
        SIZE(tp) = n - 2 * WORDSIZE;
        ASSERT((SIZE(tp) % ALIGN) == 0);

        /* reserved the last word to head any noncontiguous memory */
        /* LINTED improper alignment */
        SETBIT0(SIZE(NEXT(tp)));

        /* non-contiguous memory, free old bottom block */
        if (Bottom && Bottom != tp) {
                SETBIT0(SIZE(Bottom));
                realfree(DATA(Bottom));
        }

        return (tp);
}

/*
 * Utility function to avoid protecting a tree node twice.
 * Return true if tp is in the NULL-terminated array of tree nodes.
 */
static int
in_list(TREE *tp, TREE **npp)
{
        TREE *sp;

        while ((sp = *npp++) != NULL)
                if (tp == sp)
                        return (1);
        return (0);
}

/*
 * Tree rotation functions (BU: bottom-up, TD: top-down).
 * All functions are entered with the arguments unprotected.
 * They must return in the same condition, with all other elements
 * that have been unprotected during the operation re-protected.
 */
static void
LEFT1(TREE *x, TREE *y)
{
        TREE *node[3];
        TREE **npp = node;
        TREE *tp;

        if ((RIGHT(x) = LEFT(y)) != NULL) {
                unprotect(*npp++ = RIGHT(x));
                PARENT(RIGHT(x)) = x;
        }
        if ((PARENT(y) = PARENT(x)) != NULL) {
                unprotect(*npp++ = PARENT(x));
                if (LEFT(PARENT(x)) == x)
                        LEFT(PARENT(y)) = y;
                else
                        RIGHT(PARENT(y)) = y;
        }
        LEFT(y) = x;
        PARENT(x) = y;

        *npp = NULL;
        npp = node;
        while ((tp = *npp++) != NULL)
                if (tp != x && tp != y && !in_list(tp, npp))
                        protect(tp);
}

static void
RIGHT1(TREE *x, TREE *y)
{
        TREE *node[3];
        TREE **npp = node;
        TREE *tp;

        if ((LEFT(x) = RIGHT(y)) != NULL) {
                unprotect(*npp++ = LEFT(x));
                PARENT(LEFT(x)) = x;
        }
        if ((PARENT(y) = PARENT(x)) != NULL) {
                unprotect(*npp++ = PARENT(x));
                if (LEFT(PARENT(x)) == x)
                        LEFT(PARENT(y)) = y;
                else
                        RIGHT(PARENT(y)) = y;
        }
        RIGHT(y) = x;
        PARENT(x) = y;

        *npp = NULL;
        npp = node;
        while ((tp = *npp++) != NULL)
                if (tp != x && tp != y && !in_list(tp, npp))
                        protect(tp);
}

static void
BULEFT2(TREE *x, TREE *y, TREE *z)
{
        TREE *node[4];
        TREE **npp = node;
        TREE *tp;

        if ((RIGHT(x) = LEFT(y)) != NULL) {
                unprotect(*npp++ = RIGHT(x));
                PARENT(RIGHT(x)) = x;
        }
        if ((RIGHT(y) = LEFT(z)) != NULL) {
                unprotect(*npp++ = RIGHT(y));
                PARENT(RIGHT(y)) = y;
        }
        if ((PARENT(z) = PARENT(x)) != NULL) {
                unprotect(*npp++ = PARENT(x));
                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;

        *npp = NULL;
        npp = node;
        while ((tp = *npp++) != NULL)
                if (tp != x && tp != y && tp != z && !in_list(tp, npp))
                        protect(tp);
}

static void
BURIGHT2(TREE *x, TREE *y, TREE *z)
{
        TREE *node[4];
        TREE **npp = node;
        TREE *tp;

        if ((LEFT(x) = RIGHT(y)) != NULL) {
                unprotect(*npp++ = LEFT(x));
                PARENT(LEFT(x)) = x;
        }
        if ((LEFT(y) = RIGHT(z)) != NULL) {
                unprotect(*npp++ = LEFT(y));
                PARENT(LEFT(y)) = y;
        }
        if ((PARENT(z) = PARENT(x)) != NULL) {
                unprotect(*npp++ = PARENT(x));
                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;

        *npp = NULL;
        npp = node;
        while ((tp = *npp++) != NULL)
                if (tp != x && tp != y && tp != z && !in_list(tp, npp))
                        protect(tp);
}

static void
TDLEFT2(TREE *x, TREE *y, TREE *z)
{
        TREE *node[3];
        TREE **npp = node;
        TREE *tp;

        if ((RIGHT(y) = LEFT(z)) != NULL) {
                unprotect(*npp++ = RIGHT(y));
                PARENT(RIGHT(y)) = y;
        }
        if ((PARENT(z) = PARENT(x)) != NULL) {
                unprotect(*npp++ = PARENT(x));
                if (LEFT(PARENT(x)) == x)
                        LEFT(PARENT(z)) = z;
                else
                        RIGHT(PARENT(z)) = z;
        }
        PARENT(x) = z;
        LEFT(z) = x;

        *npp = NULL;
        npp = node;
        while ((tp = *npp++) != NULL)
                if (tp != x && tp != y && tp != z && !in_list(tp, npp))
                        protect(tp);
}

#if 0   /* Not used, for now */
static void
TDRIGHT2(TREE *x, TREE *y, TREE *z)
{
        TREE *node[3];
        TREE **npp = node;
        TREE *tp;

        if ((LEFT(y) = RIGHT(z)) != NULL) {
                unprotect(*npp++ = LEFT(y));
                PARENT(LEFT(y)) = y;
        }
        if ((PARENT(z) = PARENT(x)) != NULL) {
                unprotect(*npp++ = PARENT(x));
                if (LEFT(PARENT(x)) == x)
                        LEFT(PARENT(z)) = z;
                else
                        RIGHT(PARENT(z)) = z;
        }
        PARENT(x) = z;
        RIGHT(z) = x;

        *npp = NULL;
        npp = node;
        while ((tp = *npp++) != NULL)
                if (tp != x && tp != y && tp != z && !in_list(tp, npp))
                        protect(tp);
}
#endif

/*
 *      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);
                unprotect(tp);
                if ((sp = LINKFOR(op)) != NULL) {
                        unprotect(sp);
                        LINKBAK(sp) = tp;
                        protect(sp);
                }
                LINKFOR(tp) = sp;
                protect(tp);
                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) {
                unprotect(tp);
                PARENT(tp) = NULL;
                if ((sp = LEFT(op)) != NULL) {
                        unprotect(sp);
                        PARENT(sp) = tp;
                        protect(sp);
                }
                LEFT(tp) = sp;

                if ((sp = RIGHT(op)) != NULL) {
                        unprotect(sp);
                        PARENT(sp) = tp;
                        protect(sp);
                }
                RIGHT(tp) = sp;

                Root = tp;
                protect(tp);
                return;
        }

        /* if op has a non-null left subtree */
        if ((tp = LEFT(op)) != NULL) {
                unprotect(tp);
                PARENT(tp) = NULL;
                if (RIGHT(op)) {
                        /* make the right-end of the left subtree its root */
                        while ((sp = RIGHT(tp)) != NULL) {
                                unprotect(sp);
                                if ((gp = RIGHT(sp)) != NULL) {
                                        unprotect(gp);
                                        TDLEFT2(tp, sp, gp);
                                        protect(sp);
                                        protect(tp);
                                        tp = gp;
                                } else {
                                        LEFT1(tp, sp);
                                        protect(tp);
                                        tp = sp;
                                }
                        }

                        /* hook the right subtree of op to the above elt */
                        RIGHT(tp) = sp = RIGHT(op);
                        unprotect(sp);
                        PARENT(sp) = tp;
                        protect(sp);
                }
                protect(tp);
        } else if ((tp = RIGHT(op)) != NULL) {  /* no left subtree */
                unprotect(tp);
                PARENT(tp) = NULL;
                protect(tp);
        }

        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) {
                unprotect(pp);
                /* grandparent of tp */
                gp = PARENT(pp);
                if (gp)
                        unprotect(gp);

                /* x is a left child */
                if (LEFT(pp) == tp) {
                        if (gp && LEFT(gp) == pp) {
                                BURIGHT2(gp, pp, tp);
                                protect(gp);
                        } else {
                                if (gp)
                                        protect(gp);
                                RIGHT1(pp, tp);
                        }
                } else {
                        ASSERT(RIGHT(pp) == tp);
                        if (gp && RIGHT(gp) == pp) {
                                BULEFT2(gp, pp, tp);
                                protect(gp);
                        } else {
                                if (gp)
                                        protect(gp);
                                LEFT1(pp, tp);
                        }
                }
                protect(pp);
                unprotect(tp);  /* just in case */
        }
}

void
free(void *old)
{
        (void) mutex_lock(&__watch_malloc_lock);
        free_unlocked(old);
        (void) mutex_unlock(&__watch_malloc_lock);
}


static void
free_unlocked(void *old)
{
        if (old != NULL)
                realfree(old);
}


/*
 * memalign(align,nbytes)
 *
 * Description:
 *      Returns a block of specified size on a specified alignment boundary.
 *
 * Algorithm:
 *      Malloc enough to ensure that a block can be aligned correctly.
 *      Find the alignment point and return the fragments
 *      before and after the block.
 *
 * Errors:
 *      Returns NULL and sets errno as follows:
 *      [EINVAL]
 *              if nbytes = 0,
 *              or if alignment is misaligned,
 *              or if the heap has been detectably corrupted.
 *      [ENOMEM]
 *              if the requested memory could not be allocated.
 */

#define misaligned(p)           ((unsigned)(p) & 3)
                /* 4-byte "word" alignment is considered ok in LP64 */
#define nextblk(p, size)        ((TREE *)((char *)(p) + (size)))

void *
memalign(size_t align, size_t nbytes)
{
        size_t  reqsize;        /* Num of bytes to get from malloc() */
        TREE    *p;             /* Ptr returned from malloc() */
        TREE    *blk;           /* For addressing fragment blocks */
        size_t  blksize;        /* Current (shrinking) block size */
        TREE    *alignedp;      /* Ptr to properly aligned boundary */
        TREE    *aligned_blk;   /* The block to be returned */
        size_t  frag_size;      /* size of fragments fore and aft */
        size_t  x;

        /*
         * check for valid size and alignment parameters
         * MAX_ALIGN check prevents overflow in later calculation.
         */
        if (nbytes == 0 || misaligned(align) || align == 0 ||
            align > MAX_ALIGN) {
                errno = EINVAL;
                return (NULL);
        }

        /*
         * Malloc enough memory to guarantee that the result can be
         * aligned correctly. The worst case is when malloc returns
         * a block so close to the next alignment boundary that a
         * fragment of minimum size cannot be created.  In order to
         * make sure we can handle this, we need to force the
         * alignment to be at least as large as the minimum frag size
         * (MINSIZE + WORDSIZE).
         */

        /* check for size that could overflow ROUND calculation */
        if (nbytes > MAX_MALLOC) {
                errno = ENOMEM;
                return (NULL);
        }
        ROUND(nbytes);
        if (nbytes < MINSIZE)
                nbytes = MINSIZE;
        ROUND(align);
        while (align < MINSIZE + WORDSIZE)
                align <<= 1;
        reqsize = nbytes + align + (MINSIZE + WORDSIZE);
        /* check for overflow */
        if (reqsize < nbytes) {
                errno = ENOMEM;
                return (NULL);
        }
        p = (TREE *) malloc(reqsize);
        if (p == (TREE *) NULL) {
                /* malloc sets errno */
                return (NULL);
        }
        (void) mutex_lock(&__watch_malloc_lock);

        /*
         * get size of the entire block (overhead and all)
         */
        /* LINTED improper alignment */
        blk = BLOCK(p);                 /* back up to get length word */
        unprotect(blk);
        blksize = SIZE(blk);
        CLRBITS01(blksize);

        /*
         * locate the proper alignment boundary within the block.
         */
        x = (size_t)p;
        if (x % align != 0)
                x += align - (x % align);
        alignedp = (TREE *)x;
        /* LINTED improper alignment */
        aligned_blk = BLOCK(alignedp);

        /*
         * Check out the space to the left of the alignment
         * boundary, and split off a fragment if necessary.
         */
        frag_size = (size_t)aligned_blk - (size_t)blk;
        if (frag_size != 0) {
                /*
                 * Create a fragment to the left of the aligned block.
                 */
                if (frag_size < MINSIZE + WORDSIZE) {
                        /*
                         * Not enough space. So make the split
                         * at the other end of the alignment unit.
                         * We know this yields enough space, because
                         * we forced align >= MINSIZE + WORDSIZE above.
                         */
                        frag_size += align;
                        /* LINTED improper alignment */
                        aligned_blk = nextblk(aligned_blk, align);
                }
                blksize -= frag_size;
                SIZE(aligned_blk) = blksize | BIT0;
                frag_size -= WORDSIZE;
                SIZE(blk) = frag_size | BIT0 | ISBIT1(SIZE(blk));
                free_unlocked(DATA(blk));
                /*
                 * free_unlocked(DATA(blk)) has the side-effect of calling
                 * protect() on the block following blk, that is, aligned_blk.
                 * We recover from this by unprotect()ing it here.
                 */
                unprotect(aligned_blk);
        }

        /*
         * Is there a (sufficiently large) fragment to the
         * right of the aligned block?
         */
        frag_size = blksize - nbytes;
        if (frag_size >= MINSIZE + WORDSIZE) {
                /*
                 * split and free a fragment on the right
                 */
                blksize = SIZE(aligned_blk);
                SIZE(aligned_blk) = nbytes;
                /* LINTED improper alignment */
                blk = NEXT(aligned_blk);
                SETOLD01(SIZE(aligned_blk), blksize);
                frag_size -= WORDSIZE;
                SIZE(blk) = frag_size | BIT0;
                free_unlocked(DATA(blk));
        }
        copy_pattern(LIVEPAT, aligned_blk);
        protect(aligned_blk);
        (void) mutex_unlock(&__watch_malloc_lock);
        return (DATA(aligned_blk));
}

void *
valloc(size_t size)
{
        static unsigned pagesize;
        if (!pagesize)
                pagesize = _sysconf(_SC_PAGESIZE);
        return (memalign(pagesize, size));
}

void *
calloc(size_t num, size_t size)
{
        void *mp;
        size_t total;

        total = num * size;

        /* check for overflow */
        if (num != 0 && total / num != size) {
                errno = ENOMEM;
                return (NULL);
        }
        if ((mp = malloc(total)) != NULL)
                (void) memset(mp, 0, total);
        return (mp);
}

/* ARGSUSED1 */
void
cfree(void *p, size_t num, size_t size)
{
        free(p);
}

typedef struct {
        long cmd;
        prwatch_t prwatch;
} ctl_t;

static pid_t my_pid = 0;        /* to check for whether we fork()d */
static int dont_watch = 0;
static int do_stop = 0;
static int ctlfd = -1;
struct stat ctlstatb;
static int wflags = WA_WRITE;

static void
init_watch()
{
        char str[80];
        char *s;

        my_pid = getpid();

        dont_watch = 1;

        if ((s = getenv("MALLOC_DEBUG")) == NULL)
                return;

        s = strncpy(str, s, sizeof (str));
        while (s != NULL) {
                char *e = strchr(s, ',');
                if (e)
                        *e++ = '\0';
                if (strcmp(s, "STOP") == 0)
                        do_stop = 1;
                else if (strcmp(s, "WATCH") == 0)
                        dont_watch = 0;
                else if (strcmp(s, "RW") == 0) {
                        dont_watch = 0;
                        wflags = WA_READ|WA_WRITE;
                }
                s = e;
        }

        if (dont_watch)
                return;

        if ((ctlfd = open("/proc/self/ctl", O_WRONLY)) < 0 ||
            fstat(ctlfd, &ctlstatb) != 0) {
                if (ctlfd >= 0)
                        (void) close(ctlfd);
                ctlfd = -1;
                dont_watch = 1;
                return;
        }
        /* close-on-exec */
        (void) fcntl(ctlfd, F_SETFD, 1);

        if (do_stop) {
                int pfd;
                pstatus_t pstatus;
                struct {
                        long cmd;
                        fltset_t fltset;
                } ctl;

                /*
                 * Play together with some /proc controller
                 * that has set other stop-on-fault flags.
                 */
                premptyset(&ctl.fltset);
                if ((pfd = open("/proc/self/status", O_RDONLY)) >= 0) {
                        if (read(pfd, &pstatus, sizeof (pstatus))
                            == sizeof (pstatus))
                                ctl.fltset = pstatus.pr_flttrace;
                        (void) close(pfd);
                }
                praddset(&ctl.fltset, FLTWATCH);
                ctl.cmd = PCSFAULT;
                (void) write(ctlfd, &ctl, sizeof (ctl));
        }
}

static int
nowatch()
{
        struct stat statb;

        if (dont_watch)
                return (1);
        if (ctlfd < 0)  /* first time */
                init_watch();
        else if (fstat(ctlfd, &statb) != 0 ||
            statb.st_dev != ctlstatb.st_dev ||
            statb.st_ino != ctlstatb.st_ino) {
                /*
                 * Someone closed our file descriptor.
                 * Just open another one.
                 */
                if ((ctlfd = open("/proc/self/ctl", O_WRONLY)) < 0 ||
                    fstat(ctlfd, &ctlstatb) != 0) {
                        if (ctlfd >= 0)
                                (void) close(ctlfd);
                        ctlfd = -1;
                        dont_watch = 1;
                        return (1);
                }
                /* close-on-exec */
                (void) fcntl(ctlfd, F_SETFD, 1);
        }
        if (my_pid != getpid()) {
                /*
                 * We fork()d since the last call to the allocator.
                 * watchpoints are not inherited across fork().
                 * XXX: how to recover from this ???
                 */
                dont_watch = 1;
                (void) close(ctlfd);
                ctlfd = -1;
        }
        return (dont_watch);
}

static void
protect(TREE *tp)
{
        ctl_t ctl;
        size_t size, sz;

        if (nowatch())
                return;
        if (tp == NULL || DATA(tp) == Baddr)
                return;

        sz = size = SIZE(tp);
        CLRBITS01(size);
        if (size == 0)
                return;
        if (ISBIT0(sz))         /* block is busy, protect only the head */
                size = 0;
        ctl.cmd = PCWATCH;
        ctl.prwatch.pr_vaddr = (uintptr_t)tp;
        ctl.prwatch.pr_size = size + WORDSIZE;
        ctl.prwatch.pr_wflags = wflags;
        (void) write(ctlfd, &ctl, sizeof (ctl));
}

static void
unprotect(TREE *tp)
{
        ctl_t ctl;

        if (nowatch())
                return;
        if (tp == NULL || DATA(tp) == Baddr)
                return;

        ctl.cmd = PCWATCH;
        ctl.prwatch.pr_vaddr = (uintptr_t)tp;
        ctl.prwatch.pr_size = WORDSIZE;         /* size is arbitrary */
        ctl.prwatch.pr_wflags = 0;              /* clear the watched area */
        (void) write(ctlfd, &ctl, sizeof (ctl));
}

static void
malloc_prepare()
{
        (void) mutex_lock(&__watch_malloc_lock);
}

static void
malloc_release()
{
        (void) mutex_unlock(&__watch_malloc_lock);
}

#pragma init(malloc_init)
static void
malloc_init(void)
{
        (void) pthread_atfork(malloc_prepare, malloc_release, malloc_release);
}