17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate * CDDL HEADER START
37c478bd9Sstevel@tonic-gate *
47c478bd9Sstevel@tonic-gate * The contents of this file are subject to the terms of the
52333b8a2Sraf * Common Development and Distribution License (the "License").
62333b8a2Sraf * You may not use this file except in compliance with the License.
77c478bd9Sstevel@tonic-gate *
87c478bd9Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
97c478bd9Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
107c478bd9Sstevel@tonic-gate * See the License for the specific language governing permissions
117c478bd9Sstevel@tonic-gate * and limitations under the License.
127c478bd9Sstevel@tonic-gate *
137c478bd9Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
147c478bd9Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
157c478bd9Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
167c478bd9Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
177c478bd9Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
187c478bd9Sstevel@tonic-gate *
197c478bd9Sstevel@tonic-gate * CDDL HEADER END
207c478bd9Sstevel@tonic-gate */
212333b8a2Sraf
227c478bd9Sstevel@tonic-gate /*
238cd45542Sraf * Copyright 2008 Sun Microsystems, Inc. All rights reserved.
247c478bd9Sstevel@tonic-gate * Use is subject to license terms.
257c478bd9Sstevel@tonic-gate */
267c478bd9Sstevel@tonic-gate
277c478bd9Sstevel@tonic-gate /* Copyright (c) 1988 AT&T */
287c478bd9Sstevel@tonic-gate /* All Rights Reserved */
297c478bd9Sstevel@tonic-gate
30*7257d1b4Sraf #pragma ident "%Z%%M% %I% %E% SMI"
31*7257d1b4Sraf
327c478bd9Sstevel@tonic-gate /*
337c478bd9Sstevel@tonic-gate * Memory management: malloc(), realloc(), free().
347c478bd9Sstevel@tonic-gate *
357c478bd9Sstevel@tonic-gate * The following #-parameters may be redefined:
367c478bd9Sstevel@tonic-gate * SEGMENTED: if defined, memory requests are assumed to be
377c478bd9Sstevel@tonic-gate * non-contiguous across calls of GETCORE's.
387c478bd9Sstevel@tonic-gate * GETCORE: a function to get more core memory. If not SEGMENTED,
397c478bd9Sstevel@tonic-gate * GETCORE(0) is assumed to return the next available
407c478bd9Sstevel@tonic-gate * address. Default is 'sbrk'.
417c478bd9Sstevel@tonic-gate * ERRCORE: the error code as returned by GETCORE.
427c478bd9Sstevel@tonic-gate * Default is (char *)(-1).
437c478bd9Sstevel@tonic-gate * CORESIZE: a desired unit (measured in bytes) to be used
447c478bd9Sstevel@tonic-gate * with GETCORE. Default is (1024*ALIGN).
457c478bd9Sstevel@tonic-gate *
467c478bd9Sstevel@tonic-gate * This algorithm is based on a best fit strategy with lists of
477c478bd9Sstevel@tonic-gate * free elts maintained in a self-adjusting binary tree. Each list
487c478bd9Sstevel@tonic-gate * contains all elts of the same size. The tree is ordered by size.
497c478bd9Sstevel@tonic-gate * For results on self-adjusting trees, see the paper:
507c478bd9Sstevel@tonic-gate * Self-Adjusting Binary Trees,
517c478bd9Sstevel@tonic-gate * DD Sleator & RE Tarjan, JACM 1985.
527c478bd9Sstevel@tonic-gate *
537c478bd9Sstevel@tonic-gate * The header of a block contains the size of the data part in bytes.
547c478bd9Sstevel@tonic-gate * Since the size of a block is 0%4, the low two bits of the header
557c478bd9Sstevel@tonic-gate * are free and used as follows:
567c478bd9Sstevel@tonic-gate *
577c478bd9Sstevel@tonic-gate * BIT0: 1 for busy (block is in use), 0 for free.
587c478bd9Sstevel@tonic-gate * BIT1: if the block is busy, this bit is 1 if the
597c478bd9Sstevel@tonic-gate * preceding block in contiguous memory is free.
607c478bd9Sstevel@tonic-gate * Otherwise, it is always 0.
617c478bd9Sstevel@tonic-gate */
627c478bd9Sstevel@tonic-gate
63*7257d1b4Sraf #include "lint.h"
647c478bd9Sstevel@tonic-gate #include "mallint.h"
657c478bd9Sstevel@tonic-gate #include "mtlib.h"
667c478bd9Sstevel@tonic-gate
677c478bd9Sstevel@tonic-gate /*
687c478bd9Sstevel@tonic-gate * Some abusers of the system (notably java1.2) acquire __malloc_lock
697c478bd9Sstevel@tonic-gate * in order to prevent threads from holding it while they are being
707c478bd9Sstevel@tonic-gate * suspended via thr_suspend() or thr_suspend_allmutators().
712333b8a2Sraf * This never worked when alternate malloc() libraries were used
722333b8a2Sraf * because they don't use __malloc_lock for their locking strategy.
732333b8a2Sraf * We leave __malloc_lock as an external variable to satisfy these
742333b8a2Sraf * old programs, but we define a new lock, private to libc, to do the
752333b8a2Sraf * real locking: libc_malloc_lock. This puts libc's malloc() package
762333b8a2Sraf * on the same footing as all other malloc packages.
777c478bd9Sstevel@tonic-gate */
787c478bd9Sstevel@tonic-gate mutex_t __malloc_lock = DEFAULTMUTEX;
797c478bd9Sstevel@tonic-gate mutex_t libc_malloc_lock = DEFAULTMUTEX;
807c478bd9Sstevel@tonic-gate
817c478bd9Sstevel@tonic-gate static TREE *Root, /* root of the free tree */
827c478bd9Sstevel@tonic-gate *Bottom, /* the last free chunk in the arena */
837c478bd9Sstevel@tonic-gate *_morecore(size_t); /* function to get more core */
847c478bd9Sstevel@tonic-gate
857c478bd9Sstevel@tonic-gate static char *Baddr; /* current high address of the arena */
867c478bd9Sstevel@tonic-gate static char *Lfree; /* last freed block with data intact */
877c478bd9Sstevel@tonic-gate
887c478bd9Sstevel@tonic-gate static void t_delete(TREE *);
897c478bd9Sstevel@tonic-gate static void t_splay(TREE *);
907c478bd9Sstevel@tonic-gate static void realfree(void *);
917c478bd9Sstevel@tonic-gate static void cleanfree(void *);
927c478bd9Sstevel@tonic-gate static void *_malloc_unlocked(size_t);
937c478bd9Sstevel@tonic-gate
947c478bd9Sstevel@tonic-gate #define FREESIZE (1<<5) /* size for preserving free blocks until next malloc */
957c478bd9Sstevel@tonic-gate #define FREEMASK FREESIZE-1
967c478bd9Sstevel@tonic-gate
977c478bd9Sstevel@tonic-gate static void *flist[FREESIZE]; /* list of blocks to be freed on next malloc */
987c478bd9Sstevel@tonic-gate static int freeidx; /* index of free blocks in flist % FREESIZE */
997c478bd9Sstevel@tonic-gate
1007c478bd9Sstevel@tonic-gate /*
1012333b8a2Sraf * Interfaces used only by atfork_init() functions.
1022333b8a2Sraf */
1032333b8a2Sraf void
malloc_locks(void)1042333b8a2Sraf malloc_locks(void)
1052333b8a2Sraf {
1068cd45542Sraf (void) mutex_lock(&libc_malloc_lock);
1072333b8a2Sraf }
1082333b8a2Sraf
1092333b8a2Sraf void
malloc_unlocks(void)1102333b8a2Sraf malloc_unlocks(void)
1112333b8a2Sraf {
1128cd45542Sraf (void) mutex_unlock(&libc_malloc_lock);
1132333b8a2Sraf }
1142333b8a2Sraf
1152333b8a2Sraf /*
1167c478bd9Sstevel@tonic-gate * Allocation of small blocks
1177c478bd9Sstevel@tonic-gate */
1187c478bd9Sstevel@tonic-gate static TREE *List[MINSIZE/WORDSIZE-1]; /* lists of small blocks */
1197c478bd9Sstevel@tonic-gate
1207c478bd9Sstevel@tonic-gate static void *
_smalloc(size_t size)1217c478bd9Sstevel@tonic-gate _smalloc(size_t size)
1227c478bd9Sstevel@tonic-gate {
1237c478bd9Sstevel@tonic-gate TREE *tp;
1247c478bd9Sstevel@tonic-gate size_t i;
1257c478bd9Sstevel@tonic-gate
1267c478bd9Sstevel@tonic-gate ASSERT(size % WORDSIZE == 0);
1277c478bd9Sstevel@tonic-gate /* want to return a unique pointer on malloc(0) */
1287c478bd9Sstevel@tonic-gate if (size == 0)
1297c478bd9Sstevel@tonic-gate size = WORDSIZE;
1307c478bd9Sstevel@tonic-gate
1317c478bd9Sstevel@tonic-gate /* list to use */
1327c478bd9Sstevel@tonic-gate i = size / WORDSIZE - 1;
1337c478bd9Sstevel@tonic-gate
1347c478bd9Sstevel@tonic-gate if (List[i] == NULL) {
1357c478bd9Sstevel@tonic-gate TREE *np;
1367c478bd9Sstevel@tonic-gate int n;
1377c478bd9Sstevel@tonic-gate /* number of blocks to get at one time */
1387c478bd9Sstevel@tonic-gate #define NPS (WORDSIZE*8)
1397c478bd9Sstevel@tonic-gate ASSERT((size + WORDSIZE) * NPS >= MINSIZE);
1407c478bd9Sstevel@tonic-gate
1417c478bd9Sstevel@tonic-gate /* get NPS of these block types */
1427c478bd9Sstevel@tonic-gate if ((List[i] = _malloc_unlocked((size + WORDSIZE) * NPS)) == 0)
1437c478bd9Sstevel@tonic-gate return (0);
1447c478bd9Sstevel@tonic-gate
1457c478bd9Sstevel@tonic-gate /* make them into a link list */
1467c478bd9Sstevel@tonic-gate for (n = 0, np = List[i]; n < NPS; ++n) {
1477c478bd9Sstevel@tonic-gate tp = np;
1487c478bd9Sstevel@tonic-gate SIZE(tp) = size;
1497c478bd9Sstevel@tonic-gate np = NEXT(tp);
1507c478bd9Sstevel@tonic-gate AFTER(tp) = np;
1517c478bd9Sstevel@tonic-gate }
1527c478bd9Sstevel@tonic-gate AFTER(tp) = NULL;
1537c478bd9Sstevel@tonic-gate }
1547c478bd9Sstevel@tonic-gate
1557c478bd9Sstevel@tonic-gate /* allocate from the head of the queue */
1567c478bd9Sstevel@tonic-gate tp = List[i];
1577c478bd9Sstevel@tonic-gate List[i] = AFTER(tp);
1587c478bd9Sstevel@tonic-gate SETBIT0(SIZE(tp));
1597c478bd9Sstevel@tonic-gate return (DATA(tp));
1607c478bd9Sstevel@tonic-gate }
1617c478bd9Sstevel@tonic-gate
1627c478bd9Sstevel@tonic-gate void *
malloc(size_t size)1637c478bd9Sstevel@tonic-gate malloc(size_t size)
1647c478bd9Sstevel@tonic-gate {
1657c478bd9Sstevel@tonic-gate void *ret;
1667c478bd9Sstevel@tonic-gate
1677c478bd9Sstevel@tonic-gate if (!primary_link_map) {
1687c478bd9Sstevel@tonic-gate errno = ENOTSUP;
1697c478bd9Sstevel@tonic-gate return (NULL);
1707c478bd9Sstevel@tonic-gate }
1717c478bd9Sstevel@tonic-gate assert_no_libc_locks_held();
1728cd45542Sraf (void) mutex_lock(&libc_malloc_lock);
1737c478bd9Sstevel@tonic-gate ret = _malloc_unlocked(size);
1748cd45542Sraf (void) mutex_unlock(&libc_malloc_lock);
1757c478bd9Sstevel@tonic-gate return (ret);
1767c478bd9Sstevel@tonic-gate }
1777c478bd9Sstevel@tonic-gate
1787c478bd9Sstevel@tonic-gate static void *
_malloc_unlocked(size_t size)1797c478bd9Sstevel@tonic-gate _malloc_unlocked(size_t size)
1807c478bd9Sstevel@tonic-gate {
1817c478bd9Sstevel@tonic-gate size_t n;
1827c478bd9Sstevel@tonic-gate TREE *tp, *sp;
1837c478bd9Sstevel@tonic-gate size_t o_bit1;
1847c478bd9Sstevel@tonic-gate
1857c478bd9Sstevel@tonic-gate COUNT(nmalloc);
1867c478bd9Sstevel@tonic-gate ASSERT(WORDSIZE == ALIGN);
1877c478bd9Sstevel@tonic-gate
1887c478bd9Sstevel@tonic-gate /* check for size that could overflow calculations */
1897c478bd9Sstevel@tonic-gate if (size > MAX_MALLOC) {
1907c478bd9Sstevel@tonic-gate errno = ENOMEM;
1917c478bd9Sstevel@tonic-gate return (NULL);
1927c478bd9Sstevel@tonic-gate }
1937c478bd9Sstevel@tonic-gate
1947c478bd9Sstevel@tonic-gate /* make sure that size is 0 mod ALIGN */
1957c478bd9Sstevel@tonic-gate ROUND(size);
1967c478bd9Sstevel@tonic-gate
1977c478bd9Sstevel@tonic-gate /* see if the last free block can be used */
1987c478bd9Sstevel@tonic-gate if (Lfree) {
1997c478bd9Sstevel@tonic-gate sp = BLOCK(Lfree);
2007c478bd9Sstevel@tonic-gate n = SIZE(sp);
2017c478bd9Sstevel@tonic-gate CLRBITS01(n);
2027c478bd9Sstevel@tonic-gate if (n == size) {
2037c478bd9Sstevel@tonic-gate /*
2047c478bd9Sstevel@tonic-gate * exact match, use it as is
2057c478bd9Sstevel@tonic-gate */
2067c478bd9Sstevel@tonic-gate freeidx = (freeidx + FREESIZE - 1) &
2077c478bd9Sstevel@tonic-gate FREEMASK; /* 1 back */
2087c478bd9Sstevel@tonic-gate flist[freeidx] = Lfree = NULL;
2097c478bd9Sstevel@tonic-gate return (DATA(sp));
2107c478bd9Sstevel@tonic-gate } else if (size >= MINSIZE && n > size) {
2117c478bd9Sstevel@tonic-gate /*
2127c478bd9Sstevel@tonic-gate * got a big enough piece
2137c478bd9Sstevel@tonic-gate */
2147c478bd9Sstevel@tonic-gate freeidx = (freeidx + FREESIZE - 1) &
2157c478bd9Sstevel@tonic-gate FREEMASK; /* 1 back */
2167c478bd9Sstevel@tonic-gate flist[freeidx] = Lfree = NULL;
2177c478bd9Sstevel@tonic-gate o_bit1 = SIZE(sp) & BIT1;
2187c478bd9Sstevel@tonic-gate SIZE(sp) = n;
2197c478bd9Sstevel@tonic-gate goto leftover;
2207c478bd9Sstevel@tonic-gate }
2217c478bd9Sstevel@tonic-gate }
2227c478bd9Sstevel@tonic-gate o_bit1 = 0;
2237c478bd9Sstevel@tonic-gate
2247c478bd9Sstevel@tonic-gate /* perform free's of space since last malloc */
2257c478bd9Sstevel@tonic-gate cleanfree(NULL);
2267c478bd9Sstevel@tonic-gate
2277c478bd9Sstevel@tonic-gate /* small blocks */
2287c478bd9Sstevel@tonic-gate if (size < MINSIZE)
2297c478bd9Sstevel@tonic-gate return (_smalloc(size));
2307c478bd9Sstevel@tonic-gate
2317c478bd9Sstevel@tonic-gate /* search for an elt of the right size */
2327c478bd9Sstevel@tonic-gate sp = NULL;
2337c478bd9Sstevel@tonic-gate n = 0;
2347c478bd9Sstevel@tonic-gate if (Root) {
2357c478bd9Sstevel@tonic-gate tp = Root;
2367c478bd9Sstevel@tonic-gate for (;;) {
2377c478bd9Sstevel@tonic-gate /* branch left */
2387c478bd9Sstevel@tonic-gate if (SIZE(tp) >= size) {
2397c478bd9Sstevel@tonic-gate if (n == 0 || n >= SIZE(tp)) {
2407c478bd9Sstevel@tonic-gate sp = tp;
2417c478bd9Sstevel@tonic-gate n = SIZE(tp);
2427c478bd9Sstevel@tonic-gate }
2437c478bd9Sstevel@tonic-gate if (LEFT(tp))
2447c478bd9Sstevel@tonic-gate tp = LEFT(tp);
2457c478bd9Sstevel@tonic-gate else
2467c478bd9Sstevel@tonic-gate break;
2477c478bd9Sstevel@tonic-gate } else { /* branch right */
2487c478bd9Sstevel@tonic-gate if (RIGHT(tp))
2497c478bd9Sstevel@tonic-gate tp = RIGHT(tp);
2507c478bd9Sstevel@tonic-gate else
2517c478bd9Sstevel@tonic-gate break;
2527c478bd9Sstevel@tonic-gate }
2537c478bd9Sstevel@tonic-gate }
2547c478bd9Sstevel@tonic-gate
2557c478bd9Sstevel@tonic-gate if (sp) {
2567c478bd9Sstevel@tonic-gate t_delete(sp);
2577c478bd9Sstevel@tonic-gate } else if (tp != Root) {
2587c478bd9Sstevel@tonic-gate /* make the searched-to element the root */
2597c478bd9Sstevel@tonic-gate t_splay(tp);
2607c478bd9Sstevel@tonic-gate Root = tp;
2617c478bd9Sstevel@tonic-gate }
2627c478bd9Sstevel@tonic-gate }
2637c478bd9Sstevel@tonic-gate
2647c478bd9Sstevel@tonic-gate /* if found none fitted in the tree */
2657c478bd9Sstevel@tonic-gate if (!sp) {
2667c478bd9Sstevel@tonic-gate if (Bottom && size <= SIZE(Bottom)) {
2677c478bd9Sstevel@tonic-gate sp = Bottom;
2687c478bd9Sstevel@tonic-gate CLRBITS01(SIZE(sp));
2697c478bd9Sstevel@tonic-gate } else if ((sp = _morecore(size)) == NULL) /* no more memory */
2707c478bd9Sstevel@tonic-gate return (NULL);
2717c478bd9Sstevel@tonic-gate }
2727c478bd9Sstevel@tonic-gate
2737c478bd9Sstevel@tonic-gate /* tell the forward neighbor that we're busy */
2747c478bd9Sstevel@tonic-gate CLRBIT1(SIZE(NEXT(sp)));
2757c478bd9Sstevel@tonic-gate
2767c478bd9Sstevel@tonic-gate ASSERT(ISBIT0(SIZE(NEXT(sp))));
2777c478bd9Sstevel@tonic-gate
2787c478bd9Sstevel@tonic-gate leftover:
2797c478bd9Sstevel@tonic-gate /* if the leftover is enough for a new free piece */
2807c478bd9Sstevel@tonic-gate if ((n = (SIZE(sp) - size)) >= MINSIZE + WORDSIZE) {
2817c478bd9Sstevel@tonic-gate n -= WORDSIZE;
2827c478bd9Sstevel@tonic-gate SIZE(sp) = size;
2837c478bd9Sstevel@tonic-gate tp = NEXT(sp);
2847c478bd9Sstevel@tonic-gate SIZE(tp) = n|BIT0;
2857c478bd9Sstevel@tonic-gate realfree(DATA(tp));
2867c478bd9Sstevel@tonic-gate } else if (BOTTOM(sp))
2877c478bd9Sstevel@tonic-gate Bottom = NULL;
2887c478bd9Sstevel@tonic-gate
2897c478bd9Sstevel@tonic-gate /* return the allocated space */
2907c478bd9Sstevel@tonic-gate SIZE(sp) |= BIT0 | o_bit1;
2917c478bd9Sstevel@tonic-gate return (DATA(sp));
2927c478bd9Sstevel@tonic-gate }
2937c478bd9Sstevel@tonic-gate
2947c478bd9Sstevel@tonic-gate
2957c478bd9Sstevel@tonic-gate /*
2967c478bd9Sstevel@tonic-gate * realloc().
2977c478bd9Sstevel@tonic-gate *
2987c478bd9Sstevel@tonic-gate * If the block size is increasing, we try forward merging first.
2997c478bd9Sstevel@tonic-gate * This is not best-fit but it avoids some data recopying.
3007c478bd9Sstevel@tonic-gate */
3017c478bd9Sstevel@tonic-gate void *
realloc(void * old,size_t size)3027c478bd9Sstevel@tonic-gate realloc(void *old, size_t size)
3037c478bd9Sstevel@tonic-gate {
3047c478bd9Sstevel@tonic-gate TREE *tp, *np;
3057c478bd9Sstevel@tonic-gate size_t ts;
3067c478bd9Sstevel@tonic-gate char *new;
3077c478bd9Sstevel@tonic-gate
3087c478bd9Sstevel@tonic-gate if (!primary_link_map) {
3097c478bd9Sstevel@tonic-gate errno = ENOTSUP;
3107c478bd9Sstevel@tonic-gate return (NULL);
3117c478bd9Sstevel@tonic-gate }
3127c478bd9Sstevel@tonic-gate
3137c478bd9Sstevel@tonic-gate assert_no_libc_locks_held();
3147c478bd9Sstevel@tonic-gate COUNT(nrealloc);
3157c478bd9Sstevel@tonic-gate
3167c478bd9Sstevel@tonic-gate /* check for size that could overflow calculations */
3177c478bd9Sstevel@tonic-gate if (size > MAX_MALLOC) {
3187c478bd9Sstevel@tonic-gate errno = ENOMEM;
3197c478bd9Sstevel@tonic-gate return (NULL);
3207c478bd9Sstevel@tonic-gate }
3217c478bd9Sstevel@tonic-gate
3227c478bd9Sstevel@tonic-gate /* pointer to the block */
3238cd45542Sraf (void) mutex_lock(&libc_malloc_lock);
3247c478bd9Sstevel@tonic-gate if (old == NULL) {
3257c478bd9Sstevel@tonic-gate new = _malloc_unlocked(size);
3268cd45542Sraf (void) mutex_unlock(&libc_malloc_lock);
3277c478bd9Sstevel@tonic-gate return (new);
3287c478bd9Sstevel@tonic-gate }
3297c478bd9Sstevel@tonic-gate
3307c478bd9Sstevel@tonic-gate /* perform free's of space since last malloc */
3317c478bd9Sstevel@tonic-gate cleanfree(old);
3327c478bd9Sstevel@tonic-gate
3337c478bd9Sstevel@tonic-gate /* make sure that size is 0 mod ALIGN */
3347c478bd9Sstevel@tonic-gate ROUND(size);
3357c478bd9Sstevel@tonic-gate
3367c478bd9Sstevel@tonic-gate tp = BLOCK(old);
3377c478bd9Sstevel@tonic-gate ts = SIZE(tp);
3387c478bd9Sstevel@tonic-gate
3397c478bd9Sstevel@tonic-gate /* if the block was freed, data has been destroyed. */
3407c478bd9Sstevel@tonic-gate if (!ISBIT0(ts)) {
3418cd45542Sraf (void) mutex_unlock(&libc_malloc_lock);
3427c478bd9Sstevel@tonic-gate return (NULL);
3437c478bd9Sstevel@tonic-gate }
3447c478bd9Sstevel@tonic-gate
3457c478bd9Sstevel@tonic-gate /* nothing to do */
3467c478bd9Sstevel@tonic-gate CLRBITS01(SIZE(tp));
3477c478bd9Sstevel@tonic-gate if (size == SIZE(tp)) {
3487c478bd9Sstevel@tonic-gate SIZE(tp) = ts;
3498cd45542Sraf (void) mutex_unlock(&libc_malloc_lock);
3507c478bd9Sstevel@tonic-gate return (old);
3517c478bd9Sstevel@tonic-gate }
3527c478bd9Sstevel@tonic-gate
3537c478bd9Sstevel@tonic-gate /* special cases involving small blocks */
3547c478bd9Sstevel@tonic-gate if (size < MINSIZE || SIZE(tp) < MINSIZE) {
3557c478bd9Sstevel@tonic-gate /* free is size is zero */
3567c478bd9Sstevel@tonic-gate if (size == 0) {
3577c478bd9Sstevel@tonic-gate SETOLD01(SIZE(tp), ts);
3587c478bd9Sstevel@tonic-gate _free_unlocked(old);
3598cd45542Sraf (void) mutex_unlock(&libc_malloc_lock);
3607c478bd9Sstevel@tonic-gate return (NULL);
3617c478bd9Sstevel@tonic-gate } else {
3627c478bd9Sstevel@tonic-gate goto call_malloc;
3637c478bd9Sstevel@tonic-gate }
3647c478bd9Sstevel@tonic-gate }
3657c478bd9Sstevel@tonic-gate
3667c478bd9Sstevel@tonic-gate /* block is increasing in size, try merging the next block */
3677c478bd9Sstevel@tonic-gate if (size > SIZE(tp)) {
3687c478bd9Sstevel@tonic-gate np = NEXT(tp);
3697c478bd9Sstevel@tonic-gate if (!ISBIT0(SIZE(np))) {
3707c478bd9Sstevel@tonic-gate ASSERT(SIZE(np) >= MINSIZE);
3717c478bd9Sstevel@tonic-gate ASSERT(!ISBIT1(SIZE(np)));
3727c478bd9Sstevel@tonic-gate SIZE(tp) += SIZE(np) + WORDSIZE;
3737c478bd9Sstevel@tonic-gate if (np != Bottom)
3747c478bd9Sstevel@tonic-gate t_delete(np);
3757c478bd9Sstevel@tonic-gate else
3767c478bd9Sstevel@tonic-gate Bottom = NULL;
3777c478bd9Sstevel@tonic-gate CLRBIT1(SIZE(NEXT(np)));
3787c478bd9Sstevel@tonic-gate }
3797c478bd9Sstevel@tonic-gate
3807c478bd9Sstevel@tonic-gate #ifndef SEGMENTED
3817c478bd9Sstevel@tonic-gate /* not enough & at TRUE end of memory, try extending core */
3827c478bd9Sstevel@tonic-gate if (size > SIZE(tp) && BOTTOM(tp) && GETCORE(0) == Baddr) {
3837c478bd9Sstevel@tonic-gate Bottom = tp;
3847c478bd9Sstevel@tonic-gate if ((tp = _morecore(size)) == NULL) {
3857c478bd9Sstevel@tonic-gate tp = Bottom;
3867c478bd9Sstevel@tonic-gate Bottom = NULL;
3877c478bd9Sstevel@tonic-gate }
3887c478bd9Sstevel@tonic-gate }
3897c478bd9Sstevel@tonic-gate #endif
3907c478bd9Sstevel@tonic-gate }
3917c478bd9Sstevel@tonic-gate
3927c478bd9Sstevel@tonic-gate /* got enough space to use */
3937c478bd9Sstevel@tonic-gate if (size <= SIZE(tp)) {
3947c478bd9Sstevel@tonic-gate size_t n;
3957c478bd9Sstevel@tonic-gate
3967c478bd9Sstevel@tonic-gate chop_big:
3977c478bd9Sstevel@tonic-gate if ((n = (SIZE(tp) - size)) >= MINSIZE + WORDSIZE) {
3987c478bd9Sstevel@tonic-gate n -= WORDSIZE;
3997c478bd9Sstevel@tonic-gate SIZE(tp) = size;
4007c478bd9Sstevel@tonic-gate np = NEXT(tp);
4017c478bd9Sstevel@tonic-gate SIZE(np) = n|BIT0;
4027c478bd9Sstevel@tonic-gate realfree(DATA(np));
4037c478bd9Sstevel@tonic-gate } else if (BOTTOM(tp))
4047c478bd9Sstevel@tonic-gate Bottom = NULL;
4057c478bd9Sstevel@tonic-gate
4067c478bd9Sstevel@tonic-gate /* the previous block may be free */
4077c478bd9Sstevel@tonic-gate SETOLD01(SIZE(tp), ts);
4088cd45542Sraf (void) mutex_unlock(&libc_malloc_lock);
4097c478bd9Sstevel@tonic-gate return (old);
4107c478bd9Sstevel@tonic-gate }
4117c478bd9Sstevel@tonic-gate
4127c478bd9Sstevel@tonic-gate /* call malloc to get a new block */
4137c478bd9Sstevel@tonic-gate call_malloc:
4147c478bd9Sstevel@tonic-gate SETOLD01(SIZE(tp), ts);
4157c478bd9Sstevel@tonic-gate if ((new = _malloc_unlocked(size)) != NULL) {
4167c478bd9Sstevel@tonic-gate CLRBITS01(ts);
4177c478bd9Sstevel@tonic-gate if (ts > size)
4187c478bd9Sstevel@tonic-gate ts = size;
4197c478bd9Sstevel@tonic-gate MEMCOPY(new, old, ts);
4207c478bd9Sstevel@tonic-gate _free_unlocked(old);
4218cd45542Sraf (void) mutex_unlock(&libc_malloc_lock);
4227c478bd9Sstevel@tonic-gate return (new);
4237c478bd9Sstevel@tonic-gate }
4247c478bd9Sstevel@tonic-gate
4257c478bd9Sstevel@tonic-gate /*
4267c478bd9Sstevel@tonic-gate * Attempt special case recovery allocations since malloc() failed:
4277c478bd9Sstevel@tonic-gate *
4287c478bd9Sstevel@tonic-gate * 1. size <= SIZE(tp) < MINSIZE
4297c478bd9Sstevel@tonic-gate * Simply return the existing block
4307c478bd9Sstevel@tonic-gate * 2. SIZE(tp) < size < MINSIZE
4317c478bd9Sstevel@tonic-gate * malloc() may have failed to allocate the chunk of
4327c478bd9Sstevel@tonic-gate * small blocks. Try asking for MINSIZE bytes.
4337c478bd9Sstevel@tonic-gate * 3. size < MINSIZE <= SIZE(tp)
4347c478bd9Sstevel@tonic-gate * malloc() may have failed as with 2. Change to
4357c478bd9Sstevel@tonic-gate * MINSIZE allocation which is taken from the beginning
4367c478bd9Sstevel@tonic-gate * of the current block.
4377c478bd9Sstevel@tonic-gate * 4. MINSIZE <= SIZE(tp) < size
4387c478bd9Sstevel@tonic-gate * If the previous block is free and the combination of
4397c478bd9Sstevel@tonic-gate * these two blocks has at least size bytes, then merge
4407c478bd9Sstevel@tonic-gate * the two blocks copying the existing contents backwards.
4417c478bd9Sstevel@tonic-gate */
4427c478bd9Sstevel@tonic-gate CLRBITS01(SIZE(tp));
4437c478bd9Sstevel@tonic-gate if (SIZE(tp) < MINSIZE) {
4447c478bd9Sstevel@tonic-gate if (size < SIZE(tp)) { /* case 1. */
4457c478bd9Sstevel@tonic-gate SETOLD01(SIZE(tp), ts);
4468cd45542Sraf (void) mutex_unlock(&libc_malloc_lock);
4477c478bd9Sstevel@tonic-gate return (old);
4487c478bd9Sstevel@tonic-gate } else if (size < MINSIZE) { /* case 2. */
4497c478bd9Sstevel@tonic-gate size = MINSIZE;
4507c478bd9Sstevel@tonic-gate goto call_malloc;
4517c478bd9Sstevel@tonic-gate }
4527c478bd9Sstevel@tonic-gate } else if (size < MINSIZE) { /* case 3. */
4537c478bd9Sstevel@tonic-gate size = MINSIZE;
4547c478bd9Sstevel@tonic-gate goto chop_big;
4557c478bd9Sstevel@tonic-gate } else if (ISBIT1(ts) &&
4567c478bd9Sstevel@tonic-gate (SIZE(np = LAST(tp)) + SIZE(tp) + WORDSIZE) >= size) {
4577c478bd9Sstevel@tonic-gate ASSERT(!ISBIT0(SIZE(np)));
4587c478bd9Sstevel@tonic-gate t_delete(np);
4597c478bd9Sstevel@tonic-gate SIZE(np) += SIZE(tp) + WORDSIZE;
4607c478bd9Sstevel@tonic-gate /*
4617c478bd9Sstevel@tonic-gate * Since the copy may overlap, use memmove() if available.
4627c478bd9Sstevel@tonic-gate * Otherwise, copy by hand.
4637c478bd9Sstevel@tonic-gate */
4647c478bd9Sstevel@tonic-gate (void) memmove(DATA(np), old, SIZE(tp));
4657c478bd9Sstevel@tonic-gate old = DATA(np);
4667c478bd9Sstevel@tonic-gate tp = np;
4677c478bd9Sstevel@tonic-gate CLRBIT1(ts);
4687c478bd9Sstevel@tonic-gate goto chop_big;
4697c478bd9Sstevel@tonic-gate }
4707c478bd9Sstevel@tonic-gate SETOLD01(SIZE(tp), ts);
4718cd45542Sraf (void) mutex_unlock(&libc_malloc_lock);
4727c478bd9Sstevel@tonic-gate return (NULL);
4737c478bd9Sstevel@tonic-gate }
4747c478bd9Sstevel@tonic-gate
4757c478bd9Sstevel@tonic-gate
4767c478bd9Sstevel@tonic-gate /*
4777c478bd9Sstevel@tonic-gate * realfree().
4787c478bd9Sstevel@tonic-gate *
4797c478bd9Sstevel@tonic-gate * Coalescing of adjacent free blocks is done first.
4807c478bd9Sstevel@tonic-gate * Then, the new free block is leaf-inserted into the free tree
4817c478bd9Sstevel@tonic-gate * without splaying. This strategy does not guarantee the amortized
4827c478bd9Sstevel@tonic-gate * O(nlogn) behaviour for the insert/delete/find set of operations
4837c478bd9Sstevel@tonic-gate * on the tree. In practice, however, free is much more infrequent
4847c478bd9Sstevel@tonic-gate * than malloc/realloc and the tree searches performed by these
4857c478bd9Sstevel@tonic-gate * functions adequately keep the tree in balance.
4867c478bd9Sstevel@tonic-gate */
4877c478bd9Sstevel@tonic-gate static void
realfree(void * old)4887c478bd9Sstevel@tonic-gate realfree(void *old)
4897c478bd9Sstevel@tonic-gate {
4907c478bd9Sstevel@tonic-gate TREE *tp, *sp, *np;
4917c478bd9Sstevel@tonic-gate size_t ts, size;
4927c478bd9Sstevel@tonic-gate
4937c478bd9Sstevel@tonic-gate COUNT(nfree);
4947c478bd9Sstevel@tonic-gate
4957c478bd9Sstevel@tonic-gate /* pointer to the block */
4967c478bd9Sstevel@tonic-gate tp = BLOCK(old);
4977c478bd9Sstevel@tonic-gate ts = SIZE(tp);
4987c478bd9Sstevel@tonic-gate if (!ISBIT0(ts))
4997c478bd9Sstevel@tonic-gate return;
5007c478bd9Sstevel@tonic-gate CLRBITS01(SIZE(tp));
5017c478bd9Sstevel@tonic-gate
5027c478bd9Sstevel@tonic-gate /* small block, put it in the right linked list */
5037c478bd9Sstevel@tonic-gate if (SIZE(tp) < MINSIZE) {
5047c478bd9Sstevel@tonic-gate ASSERT(SIZE(tp) / WORDSIZE >= 1);
5057c478bd9Sstevel@tonic-gate ts = SIZE(tp) / WORDSIZE - 1;
5067c478bd9Sstevel@tonic-gate AFTER(tp) = List[ts];
5077c478bd9Sstevel@tonic-gate List[ts] = tp;
5087c478bd9Sstevel@tonic-gate return;
5097c478bd9Sstevel@tonic-gate }
5107c478bd9Sstevel@tonic-gate
5117c478bd9Sstevel@tonic-gate /* see if coalescing with next block is warranted */
5127c478bd9Sstevel@tonic-gate np = NEXT(tp);
5137c478bd9Sstevel@tonic-gate if (!ISBIT0(SIZE(np))) {
5147c478bd9Sstevel@tonic-gate if (np != Bottom)
5157c478bd9Sstevel@tonic-gate t_delete(np);
5167c478bd9Sstevel@tonic-gate SIZE(tp) += SIZE(np) + WORDSIZE;
5177c478bd9Sstevel@tonic-gate }
5187c478bd9Sstevel@tonic-gate
5197c478bd9Sstevel@tonic-gate /* the same with the preceding block */
5207c478bd9Sstevel@tonic-gate if (ISBIT1(ts)) {
5217c478bd9Sstevel@tonic-gate np = LAST(tp);
5227c478bd9Sstevel@tonic-gate ASSERT(!ISBIT0(SIZE(np)));
5237c478bd9Sstevel@tonic-gate ASSERT(np != Bottom);
5247c478bd9Sstevel@tonic-gate t_delete(np);
5257c478bd9Sstevel@tonic-gate SIZE(np) += SIZE(tp) + WORDSIZE;
5267c478bd9Sstevel@tonic-gate tp = np;
5277c478bd9Sstevel@tonic-gate }
5287c478bd9Sstevel@tonic-gate
5297c478bd9Sstevel@tonic-gate /* initialize tree info */
5307c478bd9Sstevel@tonic-gate PARENT(tp) = LEFT(tp) = RIGHT(tp) = LINKFOR(tp) = NULL;
5317c478bd9Sstevel@tonic-gate
5327c478bd9Sstevel@tonic-gate /* the last word of the block contains self's address */
5337c478bd9Sstevel@tonic-gate *(SELFP(tp)) = tp;
5347c478bd9Sstevel@tonic-gate
5357c478bd9Sstevel@tonic-gate /* set bottom block, or insert in the free tree */
5367c478bd9Sstevel@tonic-gate if (BOTTOM(tp))
5377c478bd9Sstevel@tonic-gate Bottom = tp;
5387c478bd9Sstevel@tonic-gate else {
5397c478bd9Sstevel@tonic-gate /* search for the place to insert */
5407c478bd9Sstevel@tonic-gate if (Root) {
5417c478bd9Sstevel@tonic-gate size = SIZE(tp);
5427c478bd9Sstevel@tonic-gate np = Root;
5437c478bd9Sstevel@tonic-gate for (;;) {
5447c478bd9Sstevel@tonic-gate if (SIZE(np) > size) {
5457c478bd9Sstevel@tonic-gate if (LEFT(np))
5467c478bd9Sstevel@tonic-gate np = LEFT(np);
5477c478bd9Sstevel@tonic-gate else {
5487c478bd9Sstevel@tonic-gate LEFT(np) = tp;
5497c478bd9Sstevel@tonic-gate PARENT(tp) = np;
5507c478bd9Sstevel@tonic-gate break;
5517c478bd9Sstevel@tonic-gate }
5527c478bd9Sstevel@tonic-gate } else if (SIZE(np) < size) {
5537c478bd9Sstevel@tonic-gate if (RIGHT(np))
5547c478bd9Sstevel@tonic-gate np = RIGHT(np);
5557c478bd9Sstevel@tonic-gate else {
5567c478bd9Sstevel@tonic-gate RIGHT(np) = tp;
5577c478bd9Sstevel@tonic-gate PARENT(tp) = np;
5587c478bd9Sstevel@tonic-gate break;
5597c478bd9Sstevel@tonic-gate }
5607c478bd9Sstevel@tonic-gate } else {
5617c478bd9Sstevel@tonic-gate if ((sp = PARENT(np)) != NULL) {
5627c478bd9Sstevel@tonic-gate if (np == LEFT(sp))
5637c478bd9Sstevel@tonic-gate LEFT(sp) = tp;
5647c478bd9Sstevel@tonic-gate else
5657c478bd9Sstevel@tonic-gate RIGHT(sp) = tp;
5667c478bd9Sstevel@tonic-gate PARENT(tp) = sp;
5677c478bd9Sstevel@tonic-gate } else
5687c478bd9Sstevel@tonic-gate Root = tp;
5697c478bd9Sstevel@tonic-gate
5707c478bd9Sstevel@tonic-gate /* insert to head of list */
5717c478bd9Sstevel@tonic-gate if ((sp = LEFT(np)) != NULL)
5727c478bd9Sstevel@tonic-gate PARENT(sp) = tp;
5737c478bd9Sstevel@tonic-gate LEFT(tp) = sp;
5747c478bd9Sstevel@tonic-gate
5757c478bd9Sstevel@tonic-gate if ((sp = RIGHT(np)) != NULL)
5767c478bd9Sstevel@tonic-gate PARENT(sp) = tp;
5777c478bd9Sstevel@tonic-gate RIGHT(tp) = sp;
5787c478bd9Sstevel@tonic-gate
5797c478bd9Sstevel@tonic-gate /* doubly link list */
5807c478bd9Sstevel@tonic-gate LINKFOR(tp) = np;
5817c478bd9Sstevel@tonic-gate LINKBAK(np) = tp;
5827c478bd9Sstevel@tonic-gate SETNOTREE(np);
5837c478bd9Sstevel@tonic-gate
5847c478bd9Sstevel@tonic-gate break;
5857c478bd9Sstevel@tonic-gate }
5867c478bd9Sstevel@tonic-gate }
5877c478bd9Sstevel@tonic-gate } else
5887c478bd9Sstevel@tonic-gate Root = tp;
5897c478bd9Sstevel@tonic-gate }
5907c478bd9Sstevel@tonic-gate
5917c478bd9Sstevel@tonic-gate /* tell next block that this one is free */
5927c478bd9Sstevel@tonic-gate SETBIT1(SIZE(NEXT(tp)));
5937c478bd9Sstevel@tonic-gate
5947c478bd9Sstevel@tonic-gate ASSERT(ISBIT0(SIZE(NEXT(tp))));
5957c478bd9Sstevel@tonic-gate }
5967c478bd9Sstevel@tonic-gate
5977c478bd9Sstevel@tonic-gate /*
5987c478bd9Sstevel@tonic-gate * Get more core. Gaps in memory are noted as busy blocks.
5997c478bd9Sstevel@tonic-gate */
6007c478bd9Sstevel@tonic-gate static TREE *
_morecore(size_t size)6017c478bd9Sstevel@tonic-gate _morecore(size_t size)
6027c478bd9Sstevel@tonic-gate {
6037c478bd9Sstevel@tonic-gate TREE *tp;
6047c478bd9Sstevel@tonic-gate ssize_t n, offset;
6057c478bd9Sstevel@tonic-gate char *addr;
6067c478bd9Sstevel@tonic-gate ssize_t nsize;
6077c478bd9Sstevel@tonic-gate
6087c478bd9Sstevel@tonic-gate /* compute new amount of memory to get */
6097c478bd9Sstevel@tonic-gate tp = Bottom;
6107c478bd9Sstevel@tonic-gate n = (ssize_t)size + 2 * WORDSIZE;
6117c478bd9Sstevel@tonic-gate addr = GETCORE(0);
6127c478bd9Sstevel@tonic-gate
6137c478bd9Sstevel@tonic-gate if (addr == ERRCORE)
6147c478bd9Sstevel@tonic-gate return (NULL);
6157c478bd9Sstevel@tonic-gate
6167c478bd9Sstevel@tonic-gate /* need to pad size out so that addr is aligned */
6177c478bd9Sstevel@tonic-gate if ((((uintptr_t)addr) % ALIGN) != 0)
6187c478bd9Sstevel@tonic-gate offset = ALIGN - (uintptr_t)addr % ALIGN;
6197c478bd9Sstevel@tonic-gate else
6207c478bd9Sstevel@tonic-gate offset = 0;
6217c478bd9Sstevel@tonic-gate
6227c478bd9Sstevel@tonic-gate #ifndef SEGMENTED
6237c478bd9Sstevel@tonic-gate /* if not segmented memory, what we need may be smaller */
6247c478bd9Sstevel@tonic-gate if (addr == Baddr) {
6257c478bd9Sstevel@tonic-gate n -= WORDSIZE;
6267c478bd9Sstevel@tonic-gate if (tp != NULL)
6277c478bd9Sstevel@tonic-gate n -= SIZE(tp);
6287c478bd9Sstevel@tonic-gate }
6297c478bd9Sstevel@tonic-gate #endif
6307c478bd9Sstevel@tonic-gate
6317c478bd9Sstevel@tonic-gate /* get a multiple of CORESIZE */
6327c478bd9Sstevel@tonic-gate n = ((n - 1) / CORESIZE + 1) * CORESIZE;
6337c478bd9Sstevel@tonic-gate nsize = n + offset;
6347c478bd9Sstevel@tonic-gate
6357c478bd9Sstevel@tonic-gate /* check if nsize request could overflow in GETCORE */
6367c478bd9Sstevel@tonic-gate if ((size_t)nsize > MAX_MALLOC - (uintptr_t)addr) {
6377c478bd9Sstevel@tonic-gate errno = ENOMEM;
6387c478bd9Sstevel@tonic-gate return (NULL);
6397c478bd9Sstevel@tonic-gate }
6407c478bd9Sstevel@tonic-gate
6417c478bd9Sstevel@tonic-gate if ((size_t)nsize <= MAX_GETCORE) {
6427c478bd9Sstevel@tonic-gate if (GETCORE(nsize) == ERRCORE)
6437c478bd9Sstevel@tonic-gate return (NULL);
6447c478bd9Sstevel@tonic-gate } else {
6457c478bd9Sstevel@tonic-gate intptr_t delta;
6467c478bd9Sstevel@tonic-gate /*
6477c478bd9Sstevel@tonic-gate * the value required is too big for GETCORE() to deal with
6487c478bd9Sstevel@tonic-gate * in one go, so use GETCORE() at most 2 times instead.
6497c478bd9Sstevel@tonic-gate * Argument to GETCORE() must be multiple of ALIGN.
6507c478bd9Sstevel@tonic-gate * If not, GETCORE(-MAX_GETCORE) will not return brk point
6517c478bd9Sstevel@tonic-gate * to previous value, but will be ALIGN more.
6527c478bd9Sstevel@tonic-gate * This would leave a small hole.
6537c478bd9Sstevel@tonic-gate */
6547c478bd9Sstevel@tonic-gate delta = MAX_GETCORE;
6557c478bd9Sstevel@tonic-gate while (delta > 0) {
6567c478bd9Sstevel@tonic-gate if (GETCORE(delta) == ERRCORE) {
6577c478bd9Sstevel@tonic-gate if (addr != GETCORE(0))
6587c478bd9Sstevel@tonic-gate (void) GETCORE(-MAX_GETCORE);
6597c478bd9Sstevel@tonic-gate return (NULL);
6607c478bd9Sstevel@tonic-gate }
6617c478bd9Sstevel@tonic-gate nsize -= MAX_GETCORE;
6627c478bd9Sstevel@tonic-gate delta = nsize;
6637c478bd9Sstevel@tonic-gate }
6647c478bd9Sstevel@tonic-gate }
6657c478bd9Sstevel@tonic-gate
6667c478bd9Sstevel@tonic-gate /* contiguous memory */
6677c478bd9Sstevel@tonic-gate if (addr == Baddr) {
6687c478bd9Sstevel@tonic-gate ASSERT(offset == 0);
6697c478bd9Sstevel@tonic-gate if (tp) {
6707c478bd9Sstevel@tonic-gate addr = (char *)tp;
6717c478bd9Sstevel@tonic-gate n += SIZE(tp) + 2 * WORDSIZE;
6727c478bd9Sstevel@tonic-gate } else {
6737c478bd9Sstevel@tonic-gate addr = Baddr - WORDSIZE;
6747c478bd9Sstevel@tonic-gate n += WORDSIZE;
6757c478bd9Sstevel@tonic-gate }
6767c478bd9Sstevel@tonic-gate } else
6777c478bd9Sstevel@tonic-gate addr += offset;
6787c478bd9Sstevel@tonic-gate
6797c478bd9Sstevel@tonic-gate /* new bottom address */
6807c478bd9Sstevel@tonic-gate Baddr = addr + n;
6817c478bd9Sstevel@tonic-gate
6827c478bd9Sstevel@tonic-gate /* new bottom block */
6837c478bd9Sstevel@tonic-gate tp = (TREE *)(uintptr_t)addr;
6847c478bd9Sstevel@tonic-gate SIZE(tp) = n - 2 * WORDSIZE;
6857c478bd9Sstevel@tonic-gate ASSERT((SIZE(tp) % ALIGN) == 0);
6867c478bd9Sstevel@tonic-gate
6877c478bd9Sstevel@tonic-gate /* reserved the last word to head any noncontiguous memory */
6887c478bd9Sstevel@tonic-gate SETBIT0(SIZE(NEXT(tp)));
6897c478bd9Sstevel@tonic-gate
6907c478bd9Sstevel@tonic-gate /* non-contiguous memory, free old bottom block */
6917c478bd9Sstevel@tonic-gate if (Bottom && Bottom != tp) {
6927c478bd9Sstevel@tonic-gate SETBIT0(SIZE(Bottom));
6937c478bd9Sstevel@tonic-gate realfree(DATA(Bottom));
6947c478bd9Sstevel@tonic-gate }
6957c478bd9Sstevel@tonic-gate
6967c478bd9Sstevel@tonic-gate return (tp);
6977c478bd9Sstevel@tonic-gate }
6987c478bd9Sstevel@tonic-gate
6997c478bd9Sstevel@tonic-gate
7007c478bd9Sstevel@tonic-gate /*
7017c478bd9Sstevel@tonic-gate * Tree rotation functions (BU: bottom-up, TD: top-down)
7027c478bd9Sstevel@tonic-gate */
7037c478bd9Sstevel@tonic-gate
7047c478bd9Sstevel@tonic-gate #define LEFT1(x, y) \
7057c478bd9Sstevel@tonic-gate if ((RIGHT(x) = LEFT(y)) != NULL) PARENT(RIGHT(x)) = x;\
7067c478bd9Sstevel@tonic-gate if ((PARENT(y) = PARENT(x)) != NULL)\
7077c478bd9Sstevel@tonic-gate if (LEFT(PARENT(x)) == x) LEFT(PARENT(y)) = y;\
7087c478bd9Sstevel@tonic-gate else RIGHT(PARENT(y)) = y;\
7097c478bd9Sstevel@tonic-gate LEFT(y) = x; PARENT(x) = y
7107c478bd9Sstevel@tonic-gate
7117c478bd9Sstevel@tonic-gate #define RIGHT1(x, y) \
7127c478bd9Sstevel@tonic-gate if ((LEFT(x) = RIGHT(y)) != NULL) PARENT(LEFT(x)) = x;\
7137c478bd9Sstevel@tonic-gate if ((PARENT(y) = PARENT(x)) != NULL)\
7147c478bd9Sstevel@tonic-gate if (LEFT(PARENT(x)) == x) LEFT(PARENT(y)) = y;\
7157c478bd9Sstevel@tonic-gate else RIGHT(PARENT(y)) = y;\
7167c478bd9Sstevel@tonic-gate RIGHT(y) = x; PARENT(x) = y
7177c478bd9Sstevel@tonic-gate
7187c478bd9Sstevel@tonic-gate #define BULEFT2(x, y, z) \
7197c478bd9Sstevel@tonic-gate if ((RIGHT(x) = LEFT(y)) != NULL) PARENT(RIGHT(x)) = x;\
7207c478bd9Sstevel@tonic-gate if ((RIGHT(y) = LEFT(z)) != NULL) PARENT(RIGHT(y)) = y;\
7217c478bd9Sstevel@tonic-gate if ((PARENT(z) = PARENT(x)) != NULL)\
7227c478bd9Sstevel@tonic-gate if (LEFT(PARENT(x)) == x) LEFT(PARENT(z)) = z;\
7237c478bd9Sstevel@tonic-gate else RIGHT(PARENT(z)) = z;\
7247c478bd9Sstevel@tonic-gate LEFT(z) = y; PARENT(y) = z; LEFT(y) = x; PARENT(x) = y
7257c478bd9Sstevel@tonic-gate
7267c478bd9Sstevel@tonic-gate #define BURIGHT2(x, y, z) \
7277c478bd9Sstevel@tonic-gate if ((LEFT(x) = RIGHT(y)) != NULL) PARENT(LEFT(x)) = x;\
7287c478bd9Sstevel@tonic-gate if ((LEFT(y) = RIGHT(z)) != NULL) PARENT(LEFT(y)) = y;\
7297c478bd9Sstevel@tonic-gate if ((PARENT(z) = PARENT(x)) != NULL)\
7307c478bd9Sstevel@tonic-gate if (LEFT(PARENT(x)) == x) LEFT(PARENT(z)) = z;\
7317c478bd9Sstevel@tonic-gate else RIGHT(PARENT(z)) = z;\
7327c478bd9Sstevel@tonic-gate RIGHT(z) = y; PARENT(y) = z; RIGHT(y) = x; PARENT(x) = y
7337c478bd9Sstevel@tonic-gate
7347c478bd9Sstevel@tonic-gate #define TDLEFT2(x, y, z) \
7357c478bd9Sstevel@tonic-gate if ((RIGHT(y) = LEFT(z)) != NULL) PARENT(RIGHT(y)) = y;\
7367c478bd9Sstevel@tonic-gate if ((PARENT(z) = PARENT(x)) != NULL)\
7377c478bd9Sstevel@tonic-gate if (LEFT(PARENT(x)) == x) LEFT(PARENT(z)) = z;\
7387c478bd9Sstevel@tonic-gate else RIGHT(PARENT(z)) = z;\
7397c478bd9Sstevel@tonic-gate PARENT(x) = z; LEFT(z) = x;
7407c478bd9Sstevel@tonic-gate
7417c478bd9Sstevel@tonic-gate #define TDRIGHT2(x, y, z) \
7427c478bd9Sstevel@tonic-gate if ((LEFT(y) = RIGHT(z)) != NULL) PARENT(LEFT(y)) = y;\
7437c478bd9Sstevel@tonic-gate if ((PARENT(z) = PARENT(x)) != NULL)\
7447c478bd9Sstevel@tonic-gate if (LEFT(PARENT(x)) == x) LEFT(PARENT(z)) = z;\
7457c478bd9Sstevel@tonic-gate else RIGHT(PARENT(z)) = z;\
7467c478bd9Sstevel@tonic-gate PARENT(x) = z; RIGHT(z) = x;
7477c478bd9Sstevel@tonic-gate
7487c478bd9Sstevel@tonic-gate /*
7497c478bd9Sstevel@tonic-gate * Delete a tree element
7507c478bd9Sstevel@tonic-gate */
7517c478bd9Sstevel@tonic-gate static void
t_delete(TREE * op)7527c478bd9Sstevel@tonic-gate t_delete(TREE *op)
7537c478bd9Sstevel@tonic-gate {
7547c478bd9Sstevel@tonic-gate TREE *tp, *sp, *gp;
7557c478bd9Sstevel@tonic-gate
7567c478bd9Sstevel@tonic-gate /* if this is a non-tree node */
7577c478bd9Sstevel@tonic-gate if (ISNOTREE(op)) {
7587c478bd9Sstevel@tonic-gate tp = LINKBAK(op);
7597c478bd9Sstevel@tonic-gate if ((sp = LINKFOR(op)) != NULL)
7607c478bd9Sstevel@tonic-gate LINKBAK(sp) = tp;
7617c478bd9Sstevel@tonic-gate LINKFOR(tp) = sp;
7627c478bd9Sstevel@tonic-gate return;
7637c478bd9Sstevel@tonic-gate }
7647c478bd9Sstevel@tonic-gate
7657c478bd9Sstevel@tonic-gate /* make op the root of the tree */
7667c478bd9Sstevel@tonic-gate if (PARENT(op))
7677c478bd9Sstevel@tonic-gate t_splay(op);
7687c478bd9Sstevel@tonic-gate
7697c478bd9Sstevel@tonic-gate /* if this is the start of a list */
7707c478bd9Sstevel@tonic-gate if ((tp = LINKFOR(op)) != NULL) {
7717c478bd9Sstevel@tonic-gate PARENT(tp) = NULL;
7727c478bd9Sstevel@tonic-gate if ((sp = LEFT(op)) != NULL)
7737c478bd9Sstevel@tonic-gate PARENT(sp) = tp;
7747c478bd9Sstevel@tonic-gate LEFT(tp) = sp;
7757c478bd9Sstevel@tonic-gate
7767c478bd9Sstevel@tonic-gate if ((sp = RIGHT(op)) != NULL)
7777c478bd9Sstevel@tonic-gate PARENT(sp) = tp;
7787c478bd9Sstevel@tonic-gate RIGHT(tp) = sp;
7797c478bd9Sstevel@tonic-gate
7807c478bd9Sstevel@tonic-gate Root = tp;
7817c478bd9Sstevel@tonic-gate return;
7827c478bd9Sstevel@tonic-gate }
7837c478bd9Sstevel@tonic-gate
7847c478bd9Sstevel@tonic-gate /* if op has a non-null left subtree */
7857c478bd9Sstevel@tonic-gate if ((tp = LEFT(op)) != NULL) {
7867c478bd9Sstevel@tonic-gate PARENT(tp) = NULL;
7877c478bd9Sstevel@tonic-gate
7887c478bd9Sstevel@tonic-gate if (RIGHT(op)) {
7897c478bd9Sstevel@tonic-gate /* make the right-end of the left subtree its root */
7907c478bd9Sstevel@tonic-gate while ((sp = RIGHT(tp)) != NULL) {
7917c478bd9Sstevel@tonic-gate if ((gp = RIGHT(sp)) != NULL) {
7927c478bd9Sstevel@tonic-gate TDLEFT2(tp, sp, gp);
7937c478bd9Sstevel@tonic-gate tp = gp;
7947c478bd9Sstevel@tonic-gate } else {
7957c478bd9Sstevel@tonic-gate LEFT1(tp, sp);
7967c478bd9Sstevel@tonic-gate tp = sp;
7977c478bd9Sstevel@tonic-gate }
7987c478bd9Sstevel@tonic-gate }
7997c478bd9Sstevel@tonic-gate
8007c478bd9Sstevel@tonic-gate /* hook the right subtree of op to the above elt */
8017c478bd9Sstevel@tonic-gate RIGHT(tp) = RIGHT(op);
8027c478bd9Sstevel@tonic-gate PARENT(RIGHT(tp)) = tp;
8037c478bd9Sstevel@tonic-gate }
8047c478bd9Sstevel@tonic-gate } else if ((tp = RIGHT(op)) != NULL) /* no left subtree */
8057c478bd9Sstevel@tonic-gate PARENT(tp) = NULL;
8067c478bd9Sstevel@tonic-gate
8077c478bd9Sstevel@tonic-gate Root = tp;
8087c478bd9Sstevel@tonic-gate }
8097c478bd9Sstevel@tonic-gate
8107c478bd9Sstevel@tonic-gate /*
8117c478bd9Sstevel@tonic-gate * Bottom up splaying (simple version).
8127c478bd9Sstevel@tonic-gate * The basic idea is to roughly cut in half the
8137c478bd9Sstevel@tonic-gate * path from Root to tp and make tp the new root.
8147c478bd9Sstevel@tonic-gate */
8157c478bd9Sstevel@tonic-gate static void
t_splay(TREE * tp)8167c478bd9Sstevel@tonic-gate t_splay(TREE *tp)
8177c478bd9Sstevel@tonic-gate {
8187c478bd9Sstevel@tonic-gate TREE *pp, *gp;
8197c478bd9Sstevel@tonic-gate
8207c478bd9Sstevel@tonic-gate /* iterate until tp is the root */
8217c478bd9Sstevel@tonic-gate while ((pp = PARENT(tp)) != NULL) {
8227c478bd9Sstevel@tonic-gate /* grandparent of tp */
8237c478bd9Sstevel@tonic-gate gp = PARENT(pp);
8247c478bd9Sstevel@tonic-gate
8257c478bd9Sstevel@tonic-gate /* x is a left child */
8267c478bd9Sstevel@tonic-gate if (LEFT(pp) == tp) {
8277c478bd9Sstevel@tonic-gate if (gp && LEFT(gp) == pp) {
8287c478bd9Sstevel@tonic-gate BURIGHT2(gp, pp, tp);
8297c478bd9Sstevel@tonic-gate } else {
8307c478bd9Sstevel@tonic-gate RIGHT1(pp, tp);
8317c478bd9Sstevel@tonic-gate }
8327c478bd9Sstevel@tonic-gate } else {
8337c478bd9Sstevel@tonic-gate ASSERT(RIGHT(pp) == tp);
8347c478bd9Sstevel@tonic-gate if (gp && RIGHT(gp) == pp) {
8357c478bd9Sstevel@tonic-gate BULEFT2(gp, pp, tp);
8367c478bd9Sstevel@tonic-gate } else {
8377c478bd9Sstevel@tonic-gate LEFT1(pp, tp);
8387c478bd9Sstevel@tonic-gate }
8397c478bd9Sstevel@tonic-gate }
8407c478bd9Sstevel@tonic-gate }
8417c478bd9Sstevel@tonic-gate }
8427c478bd9Sstevel@tonic-gate
8437c478bd9Sstevel@tonic-gate
8447c478bd9Sstevel@tonic-gate /*
8457c478bd9Sstevel@tonic-gate * free().
8467c478bd9Sstevel@tonic-gate * Performs a delayed free of the block pointed to
8477c478bd9Sstevel@tonic-gate * by old. The pointer to old is saved on a list, flist,
8487c478bd9Sstevel@tonic-gate * until the next malloc or realloc. At that time, all the
8497c478bd9Sstevel@tonic-gate * blocks pointed to in flist are actually freed via
8507c478bd9Sstevel@tonic-gate * realfree(). This allows the contents of free blocks to
8517c478bd9Sstevel@tonic-gate * remain undisturbed until the next malloc or realloc.
8527c478bd9Sstevel@tonic-gate */
8537c478bd9Sstevel@tonic-gate void
free(void * old)8547c478bd9Sstevel@tonic-gate free(void *old)
8557c478bd9Sstevel@tonic-gate {
8568cd45542Sraf if (!primary_link_map) {
8578cd45542Sraf errno = ENOTSUP;
8588cd45542Sraf return;
8598cd45542Sraf }
8607c478bd9Sstevel@tonic-gate assert_no_libc_locks_held();
8618cd45542Sraf (void) mutex_lock(&libc_malloc_lock);
8627c478bd9Sstevel@tonic-gate _free_unlocked(old);
8638cd45542Sraf (void) mutex_unlock(&libc_malloc_lock);
8647c478bd9Sstevel@tonic-gate }
8657c478bd9Sstevel@tonic-gate
8667c478bd9Sstevel@tonic-gate
8677c478bd9Sstevel@tonic-gate void
_free_unlocked(void * old)8687c478bd9Sstevel@tonic-gate _free_unlocked(void *old)
8697c478bd9Sstevel@tonic-gate {
8707c478bd9Sstevel@tonic-gate int i;
8717c478bd9Sstevel@tonic-gate
8728cd45542Sraf if (old == NULL)
8737c478bd9Sstevel@tonic-gate return;
8747c478bd9Sstevel@tonic-gate
8757c478bd9Sstevel@tonic-gate /*
8767c478bd9Sstevel@tonic-gate * Make sure the same data block is not freed twice.
8777c478bd9Sstevel@tonic-gate * 3 cases are checked. It returns immediately if either
8787c478bd9Sstevel@tonic-gate * one of the conditions is true.
8797c478bd9Sstevel@tonic-gate * 1. Last freed.
8807c478bd9Sstevel@tonic-gate * 2. Not in use or freed already.
8817c478bd9Sstevel@tonic-gate * 3. In the free list.
8827c478bd9Sstevel@tonic-gate */
8837c478bd9Sstevel@tonic-gate if (old == Lfree)
8847c478bd9Sstevel@tonic-gate return;
8857c478bd9Sstevel@tonic-gate if (!ISBIT0(SIZE(BLOCK(old))))
8867c478bd9Sstevel@tonic-gate return;
8877c478bd9Sstevel@tonic-gate for (i = 0; i < freeidx; i++)
8887c478bd9Sstevel@tonic-gate if (old == flist[i])
8897c478bd9Sstevel@tonic-gate return;
8907c478bd9Sstevel@tonic-gate
8917c478bd9Sstevel@tonic-gate if (flist[freeidx] != NULL)
8927c478bd9Sstevel@tonic-gate realfree(flist[freeidx]);
8937c478bd9Sstevel@tonic-gate flist[freeidx] = Lfree = old;
8947c478bd9Sstevel@tonic-gate freeidx = (freeidx + 1) & FREEMASK; /* one forward */
8957c478bd9Sstevel@tonic-gate }
8967c478bd9Sstevel@tonic-gate
8977c478bd9Sstevel@tonic-gate /*
8987c478bd9Sstevel@tonic-gate * cleanfree() frees all the blocks pointed to be flist.
8997c478bd9Sstevel@tonic-gate *
9007c478bd9Sstevel@tonic-gate * realloc() should work if it is called with a pointer
9017c478bd9Sstevel@tonic-gate * to a block that was freed since the last call to malloc() or
9027c478bd9Sstevel@tonic-gate * realloc(). If cleanfree() is called from realloc(), ptr
9037c478bd9Sstevel@tonic-gate * is set to the old block and that block should not be
9047c478bd9Sstevel@tonic-gate * freed since it is actually being reallocated.
9057c478bd9Sstevel@tonic-gate */
9067c478bd9Sstevel@tonic-gate static void
cleanfree(void * ptr)9077c478bd9Sstevel@tonic-gate cleanfree(void *ptr)
9087c478bd9Sstevel@tonic-gate {
9097c478bd9Sstevel@tonic-gate char **flp;
9107c478bd9Sstevel@tonic-gate
9117c478bd9Sstevel@tonic-gate flp = (char **)&(flist[freeidx]);
9127c478bd9Sstevel@tonic-gate for (;;) {
9137c478bd9Sstevel@tonic-gate if (flp == (char **)&(flist[0]))
9147c478bd9Sstevel@tonic-gate flp = (char **)&(flist[FREESIZE]);
9157c478bd9Sstevel@tonic-gate if (*--flp == NULL)
9167c478bd9Sstevel@tonic-gate break;
9177c478bd9Sstevel@tonic-gate if (*flp != ptr)
9187c478bd9Sstevel@tonic-gate realfree(*flp);
9197c478bd9Sstevel@tonic-gate *flp = NULL;
9207c478bd9Sstevel@tonic-gate }
9217c478bd9Sstevel@tonic-gate freeidx = 0;
9227c478bd9Sstevel@tonic-gate Lfree = NULL;
9237c478bd9Sstevel@tonic-gate }
924