malloc.c

操作系统SunOS 4.1.3版本的源码

				allocp = right_branch;
			} else {
				fpp = &allocp->left;
				allocp = left_branch;
			}
		}
		left_branch = allocp->left;
		right_branch = allocp->right;
		left_weight = weight(left_branch);
		right_weight = weight(right_branch);
	} /*while*/	

	/*
	 * allocate storage from the selected node.
	 */
	
	if (allocp->size - nbytes <= SMALLEST_BLK) {
		/*
		 * not big enough to split; must leave at least
		 * a dblk's worth of space.
		 */
		retblk = allocp->block;
		delete(fpp);
	} 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.
		 */
		register Dblk nblk;

		retblk = allocp->block;
		nblk = nextblk(retblk, nbytes);		/* ^next block */
		nblk->size =  allocp->size = retblk->size - nbytes; 
		__mallinfo.ordblks++;			/* count fragments */

		/*
		 * Change the selected node to point at the newly split
		 * block, and move the node to its proper place in
		 * the free space list.
		 */
		allocp->block = nblk;
		demote(fpp);

		/*
		 * set the length field of the allocated block; we need
		 * this because free() does not specify a length.
		 */
		retblk->size = nbytes;
	}
	/* maintain statistics */
	__mallinfo.uordbytes += retblk->size;		/* bytes allocated */
	__mallinfo.allocated++;				/* frags allocated */
	if (nbytes < __mallinfo.mxfast)
		__mallinfo.smblks++;	/* kludge to pass the SVVS */

	if (__LwpLibInit != 0)
                UNLOCK();
	return(retblk->data);

} /*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.
 */
free(ptr)
	char *ptr;
{
	register uint 	 nbytes;	/* Size of node to be released */
	register Freehdr *fpp;		/* For deletion from free list */
	register Freehdr neighbor;	/* Node to be coalesced */
	register Dblk	 neighbor_blk;	/* Ptr to potential neighbor */
	register uint	 neighbor_size;	/* Size of potential neighbor */
	register Dblk	 oldblk;	/* Ptr to block to be freed */

	if (__LwpLibInit != 0)
                LOCK();
	/*
	 * if rigorous checking was requested, do it.
	 */
	if (debug_level >= 2) {
		malloc_verify();
	}

	/*
	 * Check the address of the old block.
	 */
	if ( misaligned(ptr) ) {
		error("free: illegal address (%#x)\n", ptr);
		if (__LwpLibInit != 0)
                	UNLOCK();
		return(0);
	}

	/*
	 * Freeing something that wasn't allocated isn't
	 * exactly kosher, but fclose() does it routinely.
	 */
	if( ptr < _lbound || ptr > _ubound ) {
		errno = EINVAL;
		if (__LwpLibInit != 0)
                	UNLOCK();
		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.
	 */
	oldblk = (Dblk)(ptr - ALIGNSIZ);
	nbytes = oldblk->size;
	if (badblksize(oldblk,nbytes)) {
		error("free: bad block size (%d) at %#x\n",
			(int)nbytes, (int)oldblk );
		if (__LwpLibInit != 0)
                	UNLOCK();
		return 0;
	}

	/* maintain statistics */
	__mallinfo.uordbytes -= nbytes;		/* bytes allocated */
	__mallinfo.allocated--;			/* frags allocated */

	/*
	 * Search the tree for the correct insertion point for this
	 *	node, coalescing adjacent free blocks along the way.
	 */
	fpp = &_root;
	neighbor = *fpp;
	while (neighbor != NIL) {
		neighbor_blk = neighbor->block;
		neighbor_size = neighbor->size;
		if (oldblk < neighbor_blk) {
			Dblk nblk = nextblk(oldblk,nbytes);
			if (nblk == neighbor_blk) {
				/*
				 * Absorb and delete right neighbor
				 */
				nbytes += neighbor_size;
				__mallinfo.ordblks--;
				delete(fpp);
			} 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);
				if (__LwpLibInit != 0)
                			UNLOCK();
				 return 0;
			} else {
				/*
				 * Search to the left
			 	 */
				fpp = &neighbor->left;
			}
		} else if (oldblk > neighbor_blk) {
			Dblk nblk = nextblk(neighbor_blk, neighbor_size);
			if (nblk == oldblk) {
				/*
				 * Absorb and delete left neighbor
				 */
				oldblk = neighbor_blk;
				nbytes += neighbor_size;
				__mallinfo.ordblks--;
				delete(fpp);
			} else if (nblk > oldblk) {
				/*
				 * This block has already been freed
				 */
				error("free: block %#x was already free\n",
					(int)ptr);
				if (__LwpLibInit != 0)
                			UNLOCK();
				return 0;
			} else {
				/*
				 * search to the right
				 */
				fpp = &neighbor->right;
			}
		} else {
			/*
			 * This block has already been freed
			 * as "oldblk == neighbor_blk"
			 */
			error("free: block %#x was already free\n", (int)ptr);
			if (__LwpLibInit != 0)
                		UNLOCK();
			return 0;
		} /*else*/

		/*
		 * Note that this depends on a side effect of
		 * delete(fpp) in order to terminate the loop!
		 */
		neighbor = *fpp;

	} /*while*/

	/*
	 * Insert the new node into the free space tree
	 */
	insert( oldblk, nbytes );
	if (__LwpLibInit != 0)
                UNLOCK();
	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 *
shrink(oldblk, oldsize, newsize)
	register Dblk oldblk;
	register uint oldsize, newsize;
{
	register Dblk remainder;
	if (oldsize - newsize >= SMALLEST_BLK) {
		/*
		 * Block is to be contracted. Split the old block
		 * and return the remainder to free space.
		 */
		remainder = nextblk(oldblk, newsize);
		remainder->size = oldsize - newsize;
		oldblk->size = newsize;

		/* maintain statistics */
		__mallinfo.ordblks++;		/* count fragments */
		__mallinfo.allocated++;		/* negate effect of free() */

		(void)free(remainder->data);
	}
	return(oldblk->data);
}


/*
 * 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).
 */
char *
realloc(ptr, nbytes)
	char	*ptr;
	uint	nbytes;
{
	register Freehdr *fpp;
	register Freehdr fp;
	register Dblk	oldblk;
	register Dblk	freeblk;
	register Dblk	oldneighbor;
	register uint	oldsize;
	register uint	newsize;
	register uint	oldneighborsize;

	/*
	 * if rigorous checking was requested, do it.
	 */
	if (debug_level >= 2) {
		malloc_verify();
	}

	/*
	 * Check the address of the old block.
	 */
	if ( misaligned(ptr) || ptr < _lbound || ptr > _ubound ) {
		error("realloc: illegal address (%#x)\n", 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.
	 */
	oldblk = (Dblk)(ptr - ALIGNSIZ);
	oldsize = oldblk->size;
	if (badblksize(oldblk,oldsize)) {
		error("realloc: bad block size (%d) at %#x\n",
			oldsize, oldblk);
		return(NULL);
	}
	oldneighbor = nextblk(oldblk,oldsize);

	/* *** tree search code pulled into separate subroutine *** */
	if (reclaim(oldblk, oldsize, 1) == -1) {
		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.
	 */
	newsize = nbytes + ALIGNSIZ;		/* add size of a length word */
	if (newsize < SMALLEST_BLK) {
		newsize = SMALLEST_BLK;
	} else {
		newsize = roundup(newsize, ALIGNSIZ);
	}

	/*
	 * Next, examine the size of the old block, and compare it
	 * with the requested new size.
	 */

	if (oldsize >= newsize) {
		/*
		 * Block is to be made smaller.
		 */
		return(shrink(oldblk, oldsize, newsize));
	}

	/*
	 * Block is to be expanded.  Look for adjacent free memory.
	 */
	if ( oldneighbor < (Dblk)_ubound ) {
		/*
		 * Search for the adjacent block in the free
		 * space tree.  Note that the tree may have been
		 * modified in the earlier loop.
		 */
		fpp = &_root;
		fp = *fpp;
		oldneighborsize = oldneighbor->size;
		if ( badblksize(oldneighbor, oldneighborsize) ) {
			error("realloc: bad blocksize(%d) at %#x\n",
				oldneighborsize, oldneighbor);
			return(NULL);
		}
		while ( weight(fp) >= oldneighborsize ) {
			freeblk = fp->block;
			if (oldneighbor < freeblk) {
				/*
				 * search to the left
				 */
				fpp = &(fp->left);
				fp = *fpp;
			}
			else if (oldneighbor > freeblk) {
				/*
				 * search to the right
				 */
				fpp = &(fp->right);
				fp = *fpp;
			}
			else {		/* oldneighbor == freeblk */
				/*
				 * neighboring block is free; is it big enough?
				 */
				if (oldsize + oldneighborsize >= newsize) {
					/*
					 * Big enough. Delete freeblk, join
					 * oldblk to neighbor, return newsize
					 * bytes to the caller, and return the
					 * remainder to free storage.
					 */
					delete(fpp);

					/* maintain statistics */
					__mallinfo.ordblks--;
					__mallinfo.uordbytes += oldneighborsize;

					oldsize += oldneighborsize;
					oldblk->size = oldsize;
					return(shrink(oldblk, oldsize, newsize));
				} 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.
	 */
	ptr = malloc(nbytes);
	if (ptr != NULL) {
		bcopy(oldblk->data, ptr, oldsize);
		(void)free(oldblk->data);
	}
	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.
 *	Returns -1 if block spans a free/allocated boundary (error() called
 *						if 'flag' == 1).
 */
static int
reclaim(oldblk, oldsize, flag)
	register Dblk oldblk;
	uint oldsize;
	int flag;
{
	register Dblk oldneighbor;
	register Freehdr	*fpp;
	register Freehdr	fp;
	register Dblk		freeblk;
	register uint		size;

	/*
	 * 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.
	 */

	oldneighbor = nextblk(oldblk, oldsize);

	fpp = &_root;
	fp = *fpp;
	while ( (size = weight(fp)) >= oldsize ) {
		freeblk = fp->block;
		if (badblksize(freeblk,size)) {
			error("realloc: bad block size (%d) at %#x\n",
				size, freeblk);
			return(-1);
		}
		if ( oldblk == freeblk ) {
			/*
			 * |<-- freeblk ...
			 * _________________________________
			 * |<-- oldblk ...
			 * ---------------------------------
			 * Found oldblk in the free space tree; delete it.
			 */
			delete(fpp);

			/* maintain statistics */
			__mallinfo.uordbytes += oldsize;
			__mallinfo.allocated++;
			return(1);
		}
		else if (oldblk < freeblk) {
			/*
			 * 		|<-- freeblk ...
			 * _________________________________
			 * |<--oldblk ...
			 * ---------------------------------
			 * Search to the left for oldblk
			 */
			fpp = &fp->left;
			fp = *fpp;
		}
		else { 
			/*
			 * |<-- freeblk ...
			 * _________________________________
			 * |     		|<--oldblk--->|<--oldneighbor
			 * ---------------------------------
			 * oldblk is somewhere to the right of freeblk.
			 * Check to see if it lies within freeblk.
			 */
			register Dblk freeneighbor;