/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License, Version 1.0 only
* (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
* 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 1986 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
#pragma ident "%Z%%M% %I% %E% SMI"
/*
* file: malloc.c
* description:
* Yet another memory allocator, this one based on a method
* described in C.J. Stephenson, "Fast Fits"
*
* The basic data structure is a "Cartesian" binary tree, in which
* nodes are ordered by ascending addresses (thus minimizing free
* list insertion time) and block sizes decrease with depth in the
* tree (thus minimizing search time for a block of a given size).
*
* In other words: for any node s, let D(s) denote the set of
* descendents of s; for all x in D(left(s)) and all y in
* D(right(s)), we have:
*
* a. addr(x) < addr(s) < addr(y)
* b. len(x) <= len(s) >= len(y)
*/
#include "mallint.h"
#include <errno.h>
#include <stdlib.h>
#include <stdarg.h>
/* system interface */
extern char *sbrk();
extern int getpagesize();
#ifdef S5EMUL
#define free_return(x) return
#else
#define free_return(x) return(x)
#endif
/* SystemV-compatible information structure */
#define INIT_MXFAST 0
0,0,0,0,0,0,0,0,0,0, /* basic info */
0,0,0
};
/* heap data structures */
/* free header list management */
static Freehdr getfreehdr(void);
static void putfreehdr(Freehdr);
/* error checking */
static void error(char *, ...);
/* sets errno; prints msg and aborts if DEBUG is on */
#ifdef DEBUG /* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> */
int malloc_debug(int);
int malloc_verify(void);
/*
* A block with a negative size, a size that is not a multiple
* of ALIGNSIZ, a size greater than the current extent of the
* heap, or a size which extends beyond the end of the heap is
* considered bad.
*/
( (size) < SMALLEST_BLK \
#else /* !DEBUG ================================================= */
#define debug_level 0
#endif /* !DEBUG <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< */
/*
* insert (newblk, len)
* Inserts a new node in the free space tree, placing it
* in the correct position with respect to the existing nodes.
*
* algorithm:
* Starting from the root, a binary search is made for the new
* node. If this search were allowed to continue, it would
* eventually fail (since there cannot already be a node at the
* given address); but in fact it stops when it reaches a node in
* the tree which has a length less than that of the new node (or
* when it reaches a null tree pointer).
*
* The new node is then inserted at the root of the subtree for
* which the shorter node forms the old root (or in place of the
* null pointer).
*
* Arguments
* newblk: Ptr to the block to insert
* len: Length of new node
*/
static void
{
Freehdr x;
/*
* check for bad block size.
*/
return;
}
/*
* Search for the first node which has a weight less
* than that of the new node; this will be the
* point at which we insert the new node.
*/
x = *fpp;
else
x = *fpp;
}
/*
* Perform root insertion. The variable x traces a path through
* the fpp, and with the help of left_hook and right_hook,
* rewrites all links that cross the territory occupied
* by newblk.
*/
/* Error message returned by getfreehdr() */
return;
}
/*
* set length word in the block for consistency with the header.
*/
while (x != NIL) {
/*
* Remark:
* The name 'left_hook' is somewhat confusing, since
* it is always set to the address of a .right link
* field. However, its value is always an address
* below (i.e., to the left of) newblk. Similarly
* for right_hook. The values of left_hook and
* right_hook converge toward the value of newblk,
* as in a classical binary search.
*/
/*
* rewrite link crossing from the left
*/
*left_hook = x;
x = x->right;
} else {
/*
* rewrite link crossing from the right
*/
*right_hook = x;
right_hook = &x->left;
x = x->left;
} /*else*/
} /*while*/
} /*insert*/
/*
* delete(p)
* deletes a node from a cartesian tree. p is the address of
* a pointer to the node which is to be deleted.
*
* algorithm:
* The left and right branches of the node to be deleted define two
* subtrees which are to be merged and attached in place of the
* deleted node. Each node on the inside edges of these two
* subtrees is examined and longer nodes are placed above the
* shorter ones.
*
* On entry:
* *p is assumed to be non-null.
*/
static void
{
Freehdr x;
x = *p;
left_branch = x->left;
right_branch = x->right;
while (left_branch != right_branch) {
/*
* iterate until left branch and right branch are
* both NIL.
*/
if ( left_weight >= right_weight ) {
/*
* promote the left branch
*/
if (left_branch != NIL) {
if (left_weight == 0) {
/* zero-length block */
error("blocksize=0 at %#x\n",
break;
}
*p = left_branch;
p = &left_branch->right;
left_branch = *p;
}
} else {
/*
* promote the right branch
*/
if (right_branch != NIL) {
if (right_weight == 0) {
/* zero-length block */
error("blocksize=0 at %#x\n",
break;
}
*p = right_branch;
p = &right_branch->left;
right_branch = *p;
}
}/*else*/
}/*while*/
*p = NIL;
putfreehdr(x);
} /*delete*/
/*
* demote(p)
* Demotes a node in a cartesian tree, if necessary, to establish
* the required vertical ordering.
*
* algorithm:
* The left and right subtrees of the node to be demoted are to
* be partially merged and attached in place of the demoted node.
* The nodes on the inside edges of these two subtrees are
* examined and the longer nodes are placed above the shorter
* ones, until a node is reached which has a length no greater
* than that of the node being demoted (or until a null pointer
* is reached). The node is then attached at this point, and
* the remaining subtrees (if any) become its descendants.
*
* on entry:
* a. All the nodes in the tree, including the one to be demoted,
* must be correctly ordered horizontally;
* b. All the nodes except the one to be demoted must also be
* correctly positioned vertically. The node to be demoted
* may be already correctly positioned vertically, or it may
* have a length which is less than that of one or both of
* its progeny.
* c. *p is non-null
*/
static void
{
Freehdr x; /* addr of node to be demoted */
x = *p;
left_branch = x->left;
right_branch = x->right;
/*
* select a descendant branch for promotion
*/
if (left_weight >= right_weight) {
/*
* promote the left branch
*/
*p = left_branch;
p = &left_branch->right;
left_branch = *p;
} else {
/*
* promote the right branch
*/
*p = right_branch;
p = &right_branch->left;
right_branch = *p;
} /*else*/
} /*while*/
*p = x; /* attach demoted node here */
x->left = left_branch;
x->right = right_branch;
} /*demote*/
/*
* char*
* malloc(nbytes)
* Allocates a block of length specified in bytes. If nbytes is
* zero, a valid pointer (that should not be dereferenced) is returned.
*
* algorithm:
* The freelist is searched by descending the tree from the root
* so that at each decision point the "better fitting" branch node
* is chosen (i.e., the shorter one, if it is long enough, or
* the longer one, otherwise). The descent stops when both
* branch nodes are too short.
*
* function result:
* Malloc returns a pointer to the allocated block. A null
* pointer indicates an error.
*
* diagnostics:
*
* ENOMEM: storage could not be allocated.
*
* EINVAL: either the argument was invalid, or the heap was found
* to be in an inconsistent state. More detailed information may
* be obtained by enabling range checks (cf., malloc_debug()).
*
* Note: In this implementation, each allocated block includes a
* length word, which occurs before the address seen by the caller.
* Allocation requests are rounded up to a multiple of wordsize.
*/
{
/*
* if rigorous checking was requested, do it.
*/
if (debug_level >= 2) {
}
/*
* add the size of a length word to the request, and
* guarantee at least one word of usable data.
*/
if (nbytes < SMALLEST_BLK) {
} else {
}
/*
* ensure that at least one block is big enough to satisfy
* the request.
*/
/*
* the largest block is not enough.
*/
return 0;
}
/*
* search down through the tree until a suitable block is
* found. At each decision point, select the better
* fitting node.
*/
if (left_weight <= right_weight) {
if (left_weight >= nbytes) {
} else {
}
} else {
if (right_weight >= nbytes) {
} else {
}
}
} /*while*/
/*
* allocate storage from the selected node.
*/
/*
* not big enough to split; must leave at least
* a dblk's worth of space.
*/
} else {
/*
* Split the selected block n bytes from the top. The
* n bytes at the top are returned to the caller; the
* remainder of the block goes back to free space.
*/
/*
* Change the selected node to point at the newly split
* block, and move the node to its proper place in
* the free space list.
*/
/*
* set the length field of the allocated block; we need
* this because free() does not specify a length.
*/
}
/* maintain statistics */
} /*malloc*/
/*
* free(p)
* return a block to the free space tree.
*
* algorithm:
* Starting at the root, search for and coalesce free blocks
* adjacent to one given. When the appropriate place in the
* tree is found, insert the given block.
*
* Some sanity checks to avoid total confusion in the tree.
* If the block has already been freed, return.
* If the ptr is not from the sbrk'ed space, return.
* If the block size is invalid, return.
*/
{
/*
* if rigorous checking was requested, do it.
*/
if (debug_level >= 2) {
}
/*
* Check the address of the old block.
*/
if ( misaligned(ptr) ) {
free_return(0);
}
/*
* Freeing something that wasn't allocated isn't
* exactly kosher, but fclose() does it routinely.
*/
free_return(0);
}
/*
* Get node length by backing up by the size of a header.
* Check for a valid length. It must be a positive
* multiple of ALIGNSIZ, at least as large as SMALLEST_BLK,
* no larger than the extent of the heap, and must not
* extend beyond the end of the heap.
*/
error("free: bad block size (%d) at %#x\n",
free_return(0);
}
/* maintain statistics */
/*
* Search the tree for the correct insertion point for this
* node, coalescing adjacent free blocks along the way.
*/
if (oldblk < neighbor_blk) {
if (nblk == neighbor_blk) {
/*
* Absorb and delete right neighbor
*/
nbytes += neighbor_size;
} else if (nblk > neighbor_blk) {
/*
* The block being freed overlaps
* another block in the tree. This
* is bad news. Return to avoid
* further fouling up the the tree.
*/
error("free: blocks %#x, %#x overlap\n",
(int)oldblk, (int)neighbor_blk);
free_return(0);
} else {
/*
* Search to the left
*/
}
} else if (oldblk > neighbor_blk) {
/*
* Absorb and delete left neighbor
*/
nbytes += neighbor_size;
/*
* This block has already been freed
*/
error("free: block %#x was already free\n",
(int)ptr);
free_return(0);
} else {
/*
* search to the right
*/
}
} else {
/*
* This block has already been freed
* as "oldblk == neighbor_blk"
*/
free_return(0);
} /*else*/
/*
* Note that this depends on a side effect of
* delete(fpp) in order to terminate the loop!
*/
} /*while*/
/*
* Insert the new node into the free space tree
*/
free_return(1);
} /*free*/
/*
* char*
* shrink(oldblk, oldsize, newsize)
* Decreases the size of an old block to a new size.
* Returns the remainder to free space. Returns the
* truncated block to the caller.
*/
static char *
{
/*
* Block is to be contracted. Split the old block
* and return the remainder to free space.
*/
/* maintain statistics */
}
}
/*
* char*
* realloc(ptr, nbytes)
*
* Reallocate an old block with a new size, returning the old block
* if possible. The block returned is guaranteed to preserve the
* contents of the old block up to min(size(old block), newsize).
*
* For backwards compatibility, ptr is allowed to reference
* a block freed since the LAST call of malloc(). Thus the old
* block may be busy, free, or may even be nested within a free
* block.
*
* Some old programs have been known to do things like the following,
* which is guaranteed not to work:
*
* free(ptr);
* free(dummy);
* dummy = malloc(1);
* ptr = realloc(ptr,nbytes);
*
* This atrocity was found in the source for diff(1).
*/
{
/*
* work correctly when running in BCP mode
*/
}
/*
* if rigorous checking was requested, do it.
*/
if (debug_level >= 2) {
}
/*
* Check the address of the old block.
*/
if ( misaligned(ptr) ||
return(NULL);
}
/*
* check location and size of the old block and its
* neighboring block to the right. If the old block is
* at end of memory, the neighboring block is undefined.
*/
error("realloc: bad block size (%d) at %#x\n",
return(NULL);
}
/* *** tree search code pulled into separate subroutine *** */
return(NULL); /* internal error */
}
/*
* At this point, we can guarantee that oldblk is out of free
* space. What we do next depends on a comparison of the size
* of the old block and the requested new block size. To do
* this, first round up the new size request.
*/
if (newsize < SMALLEST_BLK) {
} else {
}
/*
* Next, examine the size of the old block, and compare it
* with the requested new size.
*/
/*
* Block is to be made smaller.
*/
}
/*
* Block is to be expanded. Look for adjacent free memory.
*/
/*
* Search for the adjacent block in the free
* space tree. Note that the tree may have been
* modified in the earlier loop.
*/
error("realloc: bad blocksize(%d) at %#x\n",
return(NULL);
}
if (oldneighbor < freeblk) {
/*
* search to the left
*/
}
else if (oldneighbor > freeblk) {
/*
* search to the right
*/
}
else { /* oldneighbor == freeblk */
/*
* neighboring block is free; is it big enough?
*/
/*
* Big enough. Delete freeblk, join
* oldblk to neighbor, return newsize
* bytes to the caller, and return the
* remainder to free storage.
*/
/* maintain statistics */
} else {
/*
* Not big enough. Stop looking for a
* free lunch.
*/
break;
} /*else*/
} /*else*/
}/*while*/
} /*if*/
/*
* At this point, we know there is no free space in which to
* expand. Malloc a new block, copy the old block to the new,
* and free the old block, IN THAT ORDER.
*/
}
return(ptr);
} /* realloc */
/*
* *** The following code was pulled out of realloc() ***
*
* int
* reclaim(oldblk, oldsize, flag)
* If a block containing 'oldsize' bytes from 'oldblk'
* is in the free list, remove it from the free list.
* 'oldblk' and 'oldsize' are assumed to include the free block header.
*
* Returns 1 if block was successfully removed.
* Returns 0 if block was not in free list.
* if 'flag' == 1).
*/
static int
{
/*
* Search the free space list for a node describing oldblk,
* or a node describing a block containing oldblk. Assuming
* the size of blocks decreases monotonically with depth in
* the tree, the loop may terminate as soon as a block smaller
* than oldblk is encountered.
*/
error("realloc: bad block size (%d) at %#x\n",
return(-1);
}
/*
* |<-- freeblk ...
* _________________________________
* |<-- oldblk ...
* ---------------------------------
* Found oldblk in the free space tree; delete it.
*/
/* maintain statistics */
return(1);
}
/*
* |<-- freeblk ...
* _________________________________
* |<--oldblk ...
* ---------------------------------
* Search to the left for oldblk
*/
}
else {
/*
* |<-- freeblk ...
* _________________________________
* | |<--oldblk--->|<--oldneighbor
* ---------------------------------
* oldblk is somewhere to the right of freeblk.
* Check to see if it lies within freeblk.
*/
if (oldblk >= freeneighbor) {
/*
* |<-- freeblk--->|<--- freeneighbor ...
* _________________________________
* | |<--oldblk--->|
* ---------------------------------
* no such luck; search to the right.
*/
}
else {
/*
* freeblk < oldblk < freeneighbor;
* i.e., oldblk begins within freeblk.
*/
if (oldneighbor > freeneighbor) {
/*
* |<-- freeblk--->|<--- freeneighbor
* _________________________________
* | |<--oldblk--->|<--oldneighbor
* ---------------------------------
* oldblk straddles a block boundary!
*/
if (flag) {
}
return(-1);
}
else if ( oldneighbor == freeneighbor ) {
/*
* |<-------- freeblk------------->|
* _________________________________
* | |<--oldblk--->|
* ---------------------------------
* Oldblk is on the right end of
* freeblk. Delete freeblk, split
* into two fragments, and return
* the one on the left to free space.
*/
/* maintain statistics */
return(1);
}
else {
/*
* |<-------- freeblk------------->|
* _________________________________
* | |oldblk | oldneighbor |
* ---------------------------------
* Oldblk is in the middle of freeblk.
* Delete freeblk, split into three
* fragments, and return the ones on
* the ends to free space.
*/
/* maintain statistics */
/*
* split the left fragment by
* subtracting the size of oldblk
* and oldblk's neighbor
*/
( (char*)freeneighbor
- (char*)oldblk );
/*
* split the right fragment by
* setting oldblk's neighbor's size
*/
oldneighbor->size =
(char*)freeneighbor
- (char*)oldneighbor;
/*
* return the fragments to free space
*/
return(1);
} /*else*/
} /*else*/
} /* else */
} /*while*/
return(0); /* free block not found */
}
/*
* bool
* morecore(nbytes)
* Add a block of at least nbytes from end-of-memory to the
* free space tree.
*
* return value:
* true if at least n bytes can be allocated
* false otherwise
*
* remarks:
*
* -- free space (delimited by the extern variable _ubound) is
* extended by an amount determined by rounding nbytes up to
* a multiple of the system page size.
*
* -- The lower bound of the heap is determined the first time
* this routine is entered. It does NOT necessarily begin at
* the end of static data space, since startup code (e.g., for
* profiling) may have invoked sbrk() before we got here.
*/
static bool
{
Dblk p;
if (nbpg == 0) {
nbpg = getpagesize();
/* hack to avoid fragmenting the heap with the first
freehdr page */
/* Error message returned by getfreehdr() */
return(false);
}
(void)putfreehdr(newhdr);
}
if (p == (Dblk) -1) {
return(false); /* errno = ENOMEM */
}
_lbound = (char*) p;
/* maintain statistics */
return(true);
} /*morecore*/
/*
* Get a free block header from the free header list.
* When the list is empty, allocate an array of headers.
* When the array is empty, allocate another one.
* When we can't allocate another array, we're in deep weeds.
*/
static Freehdr
getfreehdr(void)
{
Freehdr r;
if (freehdrlist != NIL) {
r = freehdrlist;
return(r);
}
if (nfreehdrs <= 0) {
if ((int)blk == -1) {
malloc_debug(1);
error("getfreehdr: out of memory");
return(NIL);
}
/* maintain statistics */
}
nfreehdrs--;
return(freehdrptr++);
}
/*
* Free a free block header
* Add it to the list of available headers.
*/
static void
{
p->left = freehdrlist;
freehdrlist = p;
}
#ifndef DEBUG /* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> */
/*
* stubs for error handling and diagnosis routines. These are what
* you get in the standard C library; for non-placebo diagnostics
* load /usr/lib/malloc.debug.o with your program.
*/
/*ARGSUSED*/
static void
{
}
#endif /* !DEBUG <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< */
#ifdef DEBUG /* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> */
/*
* malloc_debug(level)
*
* description:
*
* Controls the level of error diagnosis and consistency checking
* done by malloc() and free(). level is interpreted as follows:
*
* 0: malloc() and free() return 0 if error detected in arguments
* (errno is set to EINVAL)
* 1: malloc() and free() abort if errors detected in arguments
* 2: same as 1, but scan entire heap for errors on every call
* to malloc() or free()
*
* function result:
* returns the previous level of error reporting.
*/
int
{
int old_level;
debug_level = level;
return (old_level);
}
/*
* check a free space tree pointer. Should be in
* the static free pool or somewhere in the heap.
*/
#define chkblk(p)\
if ( misaligned(p)\
blkerror(p);\
return 0;\
}
static
{
error("Illegal block address (%#x)\n", (p));
}
/*
* cartesian(p)
* returns 1 if free space tree p satisfies internal consistency
* checks.
*/
static int
{
if (p == NIL) /* no tree to test */
return 1;
/*
* check that root has a data block
*/
chkhdr(p);
/*
* check that the child blocks are no larger than the parent block.
*/
return 0;
}
return 0;
}
/*
* test data addresses in the left subtree,
* starting at the left subroot and probing to
* the right. All data addresses must be < p->block.
*/
return 0;
}
/*
* test data addresses in the right subtree,
* starting at the right subroot and probing to
* the left. All addresses must be > nextblk(p->block).
*/
return 0;
}
}
/*
* malloc_verify()
*
* This is a verification routine. It walks through all blocks
* in the heap (both free and busy) and checks for bad blocks.
* malloc_verify returns 1 if the heap contains no detectably bad
* blocks; otherwise it returns 0.
*/
int
malloc_verify(void)
{
int maxsize;
int hdrsize;
int size;
Dblk p;
extern char end[];
return 1;
/*
* first check heap bounds pointers
*/
error("malloc_verify: illegal heap lower bound (%#x)\n",
_lbound);
return 0;
}
error("malloc_verify: illegal heap upper bound (%#x)\n",
_ubound);
return 0;
}
if ( (size) < SMALLEST_BLK
error("malloc_verify: bad block size (%d) at %#x\n",
size, p);
return(0); /* Badness */
}
}
error("malloc_verify: heap corrupted\n");
return(0);
}
error("malloc_verify: free space tree corrupted\n");
return(0);
}
return(1);
}
/*
* The following is a kludge to avoid dependency on stdio, which
* uses malloc() and free(), one of which probably got us here in
* the first place.
*/
extern int fileno(); /*bletch*/
/*
* Error routine.
* If debug_level == 0, does nothing except set errno = EINVAL.
* Otherwise, prints an error message to stderr and generates a
* core image.
*/
static void
{
static int n = 0; /* prevents infinite recursion when using stdio */
int nbytes;
if (debug_level == 0)
return;
if (!n++) {
}
abort();
}
#endif /* DEBUG <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< */