malloc.c

操作系统SunOS 4.1.3版本的源码

			freeneighbor =  nextblk(freeblk, freeblk->size); 
			if (oldblk >= freeneighbor) {
				/*
				 * |<-- freeblk--->|<--- freeneighbor ...
				 * _________________________________
				 * |  		      |<--oldblk--->|
				 * ---------------------------------
				 * no such luck; search to the right.
				 */
				fpp =  &fp->right;
				fp = *fpp;
			}
			else { 
				/*
				 * freeblk < oldblk < freeneighbor;
				 * i.e., oldblk begins within freeblk.
				 */
				if (oldneighbor > freeneighbor) {
					/*
					 * |<-- freeblk--->|<--- freeneighbor
					 * _________________________________
					 * |     |<--oldblk--->|<--oldneighbor
					 * ---------------------------------
					 * oldblk straddles a block boundary!
					 */
					if (flag) {
	    error("realloc: block %#x straddles free block boundary\n", oldblk);
					}
					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.
					 */
					delete(fpp);

					/* maintain statistics */
					__mallinfo.ordblks++;
					__mallinfo.uordbytes += oldsize;
					__mallinfo.allocated += 2;

					freeblk->size -= oldsize;
					(void)free(freeblk->data);
					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.
					 */
					delete(fpp);

					/* maintain statistics */
					__mallinfo.ordblks += 2;
					__mallinfo.uordbytes += freeblk->size;
					__mallinfo.allocated += 3;

					/*
					 * split the left fragment by
					 * subtracting the size of oldblk
					 * and oldblk's neighbor
					 */
					freeblk->size -=
						( (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
					 */
					(void)free(freeblk->data);
					(void)free(oldneighbor->data);
					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
morecore(nbytes)
	uint nbytes;
{
	Dblk p;

	if (nbpg == 0)
		nbpg = getpagesize();
	nbytes = roundup(nbytes, nbpg);
	p = (Dblk) sbrk((int)nbytes);
	if (p == (Dblk) -1)
		return(false);	/* errno = ENOMEM */
	if (_lbound == NULL)	/* set _lbound the first time through */
		_lbound = (char*) p;
	_ubound = (char *) p + nbytes;
	p->size = nbytes;

	/* maintain statistics */
	__mallinfo.arena = _ubound - _lbound;
	__mallinfo.uordbytes += nbytes;
	__mallinfo.ordblks++;
	__mallinfo.allocated++;

	(void)free(p->data);
	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()
{
	Freehdr	r;
	register Dblk	blk;
	register uint	size;

	if (freehdrlist != NIL) {
		r = freehdrlist;
		freehdrlist = freehdrlist->left;
		return(r);
	}
	if (nfreehdrs <= 0) {
		size = NFREE_HDRS*sizeof(struct freehdr) + ALIGNSIZ;
		blk = (Dblk) sbrk(size);
		if ((int)blk == -1) {
			malloc_debug(1);
			error("getfreehdr: out of memory");
			/* NOTREACHED */
		}
		if (_lbound == NULL)	/* set _lbound on first allocation */
			_lbound = (char*)blk;
		blk->size = size;
		freehdrptr = (Freehdr)blk->data;
		nfreehdrs = NFREE_HDRS;
		_ubound = (char*) nextblk(blk,size);

		/* maintain statistics */
		__mallinfo.arena = _ubound - _lbound;
		__mallinfo.treeoverhead += size;
	}
	nfreehdrs--;
	return(freehdrptr++);
}

/*
 * Free a free block header
 * Add it to the list of available headers.
 */
static
putfreehdr(p)
	Freehdr	p;
{
	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
error(fmt, arg1, arg2, arg3)
	char	*fmt;
	int arg1, arg2, arg3;
{
	errno = EINVAL;
}

#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
malloc_debug(level)
	int level;
{
	int old_level;
	old_level = debug_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)\
		|| ((Dblk)(p) < (Dblk)_lbound || (Dblk)(p) > (Dblk)_ubound)){\
		blkerror(p);\
		return 0;\
	}

#define chkhdr(p) chkblk(p)

static blkerror(p)
	Freehdr p;
{
	error("Illegal block address (%#x)\n", (p));
}

/*
 * cartesian(p)
 *	returns 1 if free space tree p satisfies internal consistency
 *	checks.
 */

static int
cartesian(p)
	register Freehdr p;
{
	register Freehdr probe;
	register Dblk db,pdb;

	if (p == NIL)				/* no tree to test */
		return 1;
	/*
	 * check that root has a data block
	 */
	chkhdr(p);
	pdb = p->block;
	chkblk(pdb);

	/*
	 * check that the child blocks are no larger than the parent block.
	 */
	probe = p->left;
	if (probe != NIL) {
		chkhdr(probe);
		db = probe->block;
		chkblk(db);
		if (probe->size > p->size)	/* child larger than parent */
			return 0;
	}
	probe = p->right;
	if (probe != NIL) {
		chkhdr(probe);
		db = probe->block;
		chkblk(db);
		if (probe->size > p->size)	/* child larger than parent */
			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.
	 */
	probe = p->left;
	while (probe != NIL) {
		chkhdr(probe);
		db = probe->block;
		chkblk(db);
		if ( nextblk(db, probe->size) >= pdb )	/* overlap */
			return 0;
		probe = probe->right;
	}
	/*
	 * test data addresses in the right subtree,
	 * starting at the right subroot and probing to
	 * the left.  All addresses must be > nextblk(p->block).
	 */
	pdb = nextblk(pdb, p->size);
	probe = p->right;
	while (probe != NIL) {
		chkhdr(probe);
		db = probe->block;
		chkblk(db);
		if (db == NULL || db <= pdb)		/* overlap */
			return 0;
		probe = probe->left;
	}
	return (cartesian(p->left) && cartesian(p->right));
}

/*
 * 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()
{
	register int	maxsize;
	register int	hdrsize;
	register int	size;
	register Dblk	p;
	uint	lb,ub;

	extern  char	end[];

	if (_lbound == NULL)	/* no allocation yet */
		return 1;

	/*
	 * first check heap bounds pointers
	 */
	lb = (uint)end;
	ub = (uint)sbrk(0);

	if ((uint)_lbound < lb || (uint)_lbound > ub) {
		error("malloc_verify: illegal heap lower bound (%#x)\n",
			_lbound);
		return 0;
	}
	if ((uint)_ubound < lb || (uint)_ubound > ub) {
		error("malloc_verify: illegal heap upper bound (%#x)\n",
			_ubound);
		return 0;
	}
	maxsize = heapsize();
	p = (Dblk)_lbound;
	while (p < (Dblk) _ubound) {
		size = p->size;
		if ( (size) < SMALLEST_BLK 
			|| (size) & (ALIGNSIZ-1)
			|| (size) > heapsize()
			|| ((char*)(p))+(size) > _ubound ) {
			error("malloc_verify: bad block size (%d) at %#x\n",
				size, p);
			return(0);		/* Badness */
		}
		p = nextblk(p, size);
	}
	if (p > (Dblk) _ubound) {
		error("malloc_verify: heap corrupted\n");
		return(0);
	}
	if (!cartesian(_root)){
		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.
 */

#define putchar(c) (*buf++ = (c))
#define fileno(x) x		/*bletch*/
#define stderr 2		/*bletch*/
#define	LBUFSIZ	256

static	char	stderrbuf[LBUFSIZ];

/*VARARGS2*/
static
sprintf( string, fmt, x1, x2, x3 )
	char *string;
	register char *fmt;
	uint x1,x2,x3;
{
	register char *buf = string;
	uint *argp = &x1;
	register char c;

	while ( c = *fmt++ ) {
		if (c != '%') {
			putchar(c);
		} else {
			/*
			 * print formatted argument
			 */
			register uint x;
			unsigned short radix;
			char prbuf[12];
			register char *cp;

			x = *argp++;

			switch( c = *fmt++ ) {
			case 'd':
				radix = 10;
				if ((int)x < 0) {
					putchar('-');
					x = (unsigned)(-(int)x);
				}
				break;
			case '#':
				c = *fmt++;
				if (c == 'x') {
					putchar('0');
					putchar(c);
				}
				/*FALL THROUGH*/
			case 'x':
				radix = 16;
				break;
			default:
				putchar(c);
				continue;
			} /*switch*/

			cp = prbuf;
			do {
				*cp++ = "0123456789abcdef"[x%radix];
				x /= radix;
			} while(x);
			do {
				putchar(*--cp);
			} while(cp > prbuf);
		}/*if*/
	} /*while*/

	putchar('\0');
	return(buf - string);

} /*sprintf*/

/*
 * Error routine.
 * If debug_level == 0, does nothing except set errno = EINVAL.
 * Otherwise, prints an error message to stderr and generates a
 * core image.
 */

/*VARARGS1*/
static
error(fmt, arg1, arg2, arg3)
	char	*fmt;
	int arg1, arg2, arg3;
{
	static n = 0;	/* prevents infinite recursion when using stdio */
	register int nbytes;

	errno = EINVAL;
	if (debug_level == 0)
		return;
	if (!n++) {
		nbytes = sprintf(stderrbuf, fmt, arg1, arg2, arg3);
		stderrbuf[nbytes++] = '\n';
		stderrbuf[nbytes] = '\0';
		write(fileno(stderr), stderrbuf, nbytes);
	}
	abort();
}

#endif	DEBUG		<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<