malloc.c

操作系统源代码

/**********************************************************/
/*
/*		 This was file READ_ME
/*
/**********************************************************/

/*
	PROGRAM
		malloc(), free(), realloc()
	AUTHOR
		Dick Grune, Free University, Amsterdam
		Modified by Ceriel Jacobs, Free University, Amsterdam,
		to make it faster
	VERSION
		$Header: READ_ME,v 1.1 91/12/19 14:45:04 philip Exp $
	DESCRIPTION
	This is an independent rewrite of the malloc/free package; it is
	fast and efficient.  Free blocks are kept in doubly linked lists,
	list N holding blocks with sizes between 2**N and 2**(N+1)-1.
	Consequently neither malloc nor free have to do any searching:
	the cost of a call of malloc() (or free()) is constant, however
	many blocks you have got.
	
	If you switch on the NON_STANDARD macro (see param.h) every block
	costs 2 pointers overhead (otherwise it's 4).
*/
/*
	There is an organisational problem here: during devellopment
	I want the package divided into modules, which implies external
	names for the communication.  The only external names I want in
	the finished product are malloc, realloc and free.  This requires
	some hanky-panky.
*/


/**********************************************************/
/*
/*		 This was file size_type.h
/*
/**********************************************************/

#if	_EM_WSIZE == _EM_PSIZE
typedef unsigned int size_type;
#elif	_EM_LSIZE == _EM_PSIZE
typedef unsigned long size_type;
#else
#error funny pointer size
#endif
#include	<stdlib.h>
#include	<stdio.h>


/**********************************************************/
/*
/*		 This was file param.h
/*
/**********************************************************/

/* $Header: param.h,v 1.1 91/12/19 14:45:25 philip Exp $ */
/*
 * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
 * See the copyright notice in the ACK home directory, in the file "Copyright".
 */

#	undef	NON_STANDARD	/*	If defined, the contents of a block
					will NOT be left undisturbed after it
					is freed, as opposed to what it says
					in the manual (malloc(2)).
					Setting this option reduces the memory
					overhead considerably.  I personally
					consider the specified behaviour an
					artefact of the original
					implementation.
				*/

#	define	ASSERT		/*	If defined, some inexpensive tests
					will be made to ensure the
					correctness of some sensitive data.
					It often turns an uncontrolled crash
					into a controlled one.
				*/

#	define	CHECK		/*	If defined, extensive and expensive
					tests will be done, inculding a
					checksum on the mallinks (chunk
					information blocks).  The resulting
					information will be printed on a file
					called mal.out .
					Additionally a function
						maldump(n) int n;
					will be defined, which will dump
					pertinent info in pseudo-readable
					form; it aborts afterwards if n != 0.
				*/

#	undef	EXTERN		/*	If defined, all static names will
					become extern, which is a help in
					using adb(1) or prof(1)
				*/

#	define	STORE		/*	If defined, separate free lists will
					be kept of chunks with small sizes,
					to speed things up a little.
				*/

#	undef SYSTEM		/*	If defined, the system module is used.
					Otherwise, "sbrk" is called directly.
				*/

#define	ALIGNMENT	8	
				/* alignment common to all types */
#define	LOG_MIN_SIZE	3
#define	LOG_MAX_SIZE	24


/**********************************************************/
/*
/*		 This was file impl.h
/*
/**********************************************************/

/* $Header: impl.h,v 1.1 91/12/19 14:45:16 philip Exp $ */
/*
 * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
 * See the copyright notice in the ACK home directory, in the file "Copyright".
 */
/*	This file essentially describes how the mallink info block
	is implemented.
*/

#define	MIN_SIZE	(1<<LOG_MIN_SIZE)
#define	MAX_FLIST	(LOG_MAX_SIZE - LOG_MIN_SIZE)
#if ALIGNMENT != 4 && ALIGNMENT != 8 && ALIGNMENT != 16
#error ALIGNMENT must be 4, 8 or 16
#elif ALIGNMENT % _EM_LSIZE
/* since calloc() does it's initialization in longs */
#error ALIGNMENT must be a multiple of the long size
#endif
#define align(n)	(((n) + (ALIGNMENT - 1)) & ~(ALIGNMENT - 1))

union _inf {
	union _inf *ptr;
	size_type ui;
};

typedef union _inf mallink;
#define	MAL_NULL	((mallink *)0)

/*	Access macros; only these macros know where to find values.
	They are also lvalues.
*/
#ifndef	NON_STANDARD
#define	OFF_SET	0
#else	/* def NON_STANDARD */
#define	OFF_SET	2
#endif	/* NON_STANDARD */

#define	_log_prev_of(ml)	((ml)[-1+OFF_SET]).ptr
#define	_log_next_of(ml)	((ml)[-2+OFF_SET]).ptr
#define	_phys_prev_of(ml)	((ml)[-3+OFF_SET]).ptr
#define	_this_size_of(ml)	((ml)[-4+OFF_SET]).ui
#ifndef	CHECK
#define	N_WORDS			4
#else	/* ifdef	CHECK */
#define	_checksum_of(ml)	((ml)[-5+OFF_SET]).ui
#define	_print_of(ml)		((ml)[-6+OFF_SET]).ui
#define	_mark_of(ml)		((ml)[-7+OFF_SET]).ui
#define	N_WORDS			7
#endif	/* CHECK */

#define	mallink_size()		(size_t) \
	align((N_WORDS - OFF_SET) * sizeof (mallink))

#ifdef	CHECK
#define	set_mark(ml,e)		(_mark_of(ml) = (e))
#define	mark_of(ml)		(_mark_of(ml))

#define	set_checksum(ml,e)	(_checksum_of(ml) = (e))
#define	checksum_of(ml)		(_checksum_of(ml))
#endif	/* CHECK */

#define new_mallink(ml)		( _log_prev_of(ml) = 0, \
				  _log_next_of(ml) = 0, \
				  _phys_prev_of(ml) = 0, \
				  _this_size_of(ml) = 0 )

#define	block_of_mallink(ml)	((void *)ml)
#define	mallink_of_block(addr)	((mallink *)addr)

#define	public	extern
#define	publicdata	extern
#ifndef	EXTERN
#define	private	static
#define	privatedata	static
#else	/* def	EXTERN */
#define	private	extern
#define	privatedata
#endif	/* EXTERN */

#ifdef	ASSERT
private m_assert(const char *fn, int ln);
#define	assert(b)		(!(b) ? m_assert(__FILE__, __LINE__) : 0)
#else	/* ndef	ASSERT */
#define	assert(b)		0
#endif	/* ASSERT */


/**********************************************************/
/*
/*		 This was file check.h
/*
/**********************************************************/

/* $Header: check.h,v 1.1 91/12/19 14:45:11 philip Exp $ */
/*
 * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
 * See the copyright notice in the ACK home directory, in the file "Copyright".
 */
#ifdef	CHECK

private check_mallinks(const char *s), calc_checksum(mallink *ml);
private check_work_empty(const char *s);
private started_working_on(mallink *ml), stopped_working_on(mallink *ml);

#else	/* ifndef	CHECK */

#define	maldump(n)		abort()
#define	check_mallinks(s)	0
#define	calc_checksum(ml)	0
#define	started_working_on(ml)	0
#define	stopped_working_on(ml)	0
#define	check_work_empty(s)	0

#endif	/* CHECK */


/**********************************************************/
/*
/*		 This was file log.h
/*
/**********************************************************/

/* $Header: log.h,v 1.1 91/12/19 14:45:21 philip Exp $ */
/*
 * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
 * See the copyright notice in the ACK home directory, in the file "Copyright".
 */
/*	Algorithms to manipulate the doubly-linked lists of free
	chunks.
*/

private link_free_chunk(mallink *ml), unlink_free_chunk(mallink *ml);
private mallink *first_present(int class);
private mallink *search_free_list(int class, size_t n);

#ifdef STORE
#define in_store(ml)		((size_type)_phys_prev_of(ml) & STORE_BIT)
#define set_store(ml, e) \
	(_phys_prev_of(ml) = (mallink *) \
		((e) ? (size_type) _phys_prev_of(ml) | STORE_BIT : \
		       (size_type) _phys_prev_of(ml) & ~STORE_BIT))
#endif
#define	set_log_prev(ml,e)	(_log_prev_of(ml) = (e))
#define	log_prev_of(ml)		(mallink *) (_log_prev_of(ml))

#define	set_log_next(ml,e)	(_log_next_of(ml) = (e))
#define	log_next_of(ml)		(mallink *) (_log_next_of(ml))



/**********************************************************/
/*
/*		 This was file phys.h
/*
/**********************************************************/

/* $Header: phys.h,v 1.1 91/12/19 14:45:30 philip Exp $ */
/*
 * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
 * See the copyright notice in the ACK home directory, in the file "Copyright".
 */
/*	Algorithms to manipulate the doubly-linked list of physical
	chunks.
*/
privatedata mallink *ml_last;

#define FREE_BIT		01
#ifdef STORE
#define STORE_BIT		02
#define BITS			(FREE_BIT|STORE_BIT)
#else
#define BITS			(FREE_BIT)
#endif

#define __bits(ml)		((int)((size_type)_phys_prev_of(ml) & BITS))
#define	__free_of(ml)		((int)((size_type)_phys_prev_of(ml) & FREE_BIT))
#define __phys_prev_of(ml)	((mallink *)((size_type)_phys_prev_of(ml) & ~BITS))
#define prev_size_of(ml)	((char *)(ml) - \
				 (char *)__phys_prev_of(ml) - \
				 mallink_size() \
				)
#define	set_phys_prev(ml,e) \
	(_phys_prev_of(ml) = (mallink *) ((char *)e + __bits(ml)))

#ifdef	CHECK
private Error(const char *fmt, const char *s, mallink *ml);
#define	phys_prev_of(ml)	(mallink *) \
	(first_mallink(ml) ? \
		(char *)Error("phys_prev_of first_mallink %p", "somewhere", ml) : \
		(char *)__phys_prev_of(ml) \
	)
#else	/* ndef	CHECK */
#define	phys_prev_of(ml)	__phys_prev_of(ml)
#endif	/* CHECK */

#define	first_mallink(ml)	(int) (__phys_prev_of(ml) == 0)
#define	last_mallink(ml)	(int) ((ml) == ml_last)

/*	There is an ambiguity in the semantics of phys_next_of: sometimes
	one wants it to return MAL_NULL if there is no next chunk, at
	other times one wants the address of the virtual chunk at the
	end of memory.  The present version returns the address of the
	(virtual) chunk and relies on the user to test last_mallink(ml)
	first.
*/
#define size_of(ml)		(_this_size_of(ml) - mallink_size())
#define	set_phys_next(ml,e) \
	(_this_size_of(ml) = (size_type)((char *)(e) - (char *)(ml)))
#define	phys_next_of(ml)	(mallink *) ((char *)(ml) + _this_size_of(ml))

#define	set_free(ml,e) \
	(_phys_prev_of(ml) = (mallink *) \
		((e) ? (size_type) _phys_prev_of(ml) | FREE_BIT : \
		       (size_type) _phys_prev_of(ml) & ~FREE_BIT))
#define	free_of(ml)		(__free_of(ml))

#define coalesce_forw(ml,nxt)	( unlink_free_chunk(nxt), \
				  combine_chunks((ml), (nxt)))

#define coalesce_backw(ml,prv)	( unlink_free_chunk(prv), \
				  stopped_working_on(ml), \
				  combine_chunks((prv), (ml)), \
				  started_working_on(prv))

#ifdef	CHECK
#define	set_print(ml,e)		(_print_of(ml) = (e))
#define	print_of(ml)		(_print_of(ml))
#endif	/* CHECK */

private truncate(mallink *ml, size_t size);
private combine_chunks(register mallink *ml1, register mallink *ml2);
private mallink *create_chunk(void *p, size_t n);


/**********************************************************/
/*
/*		 This was file mal.c
/*
/**********************************************************/

/* $Header: mal.c,v 1.1 91/12/19 14:45:23 philip Exp $ */
/*
 * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
 * See the copyright notice in the ACK home directory, in the file "Copyright".
 */
#include	<limits.h>
#include	<stdlib.h>

/*	Malloc space is traversed by N doubly-linked lists of chunks, each
	containing a couple of house-keeping data addressed as a
	'mallink' and a piece of useful space, called the block.
	The N lists are accessed through their starting pointers in
	free_list[].  Free_list[n] points to a list of chunks between
	2**(n+LOG_MIN_SIZE) and 2**(n+LOG_MIN_SIZE+1)-1, which means
	that the smallest chunk is 2**LOG_MIN_SIZE (== MIN_SIZE).
*/

#ifdef SYSTEM
#include	<system.h>
#define SBRK	sys_break
#else
#define SBRK	_sbrk
#define	ILL_BREAK		(void *)(-1)	/* funny failure value */
#endif
extern void *SBRK(int incr);
#ifdef STORE
#define	MAX_STORE	32
private do_free(mallink *ml), sell_out(void);
privatedata mallink *store[MAX_STORE];
#endif /* STORE */

void *privious_free= (void *)-1;
void *
malloc(register size_t n)
{check_mallinks("malloc entry");{
	register mallink *ml;
	register int min_class;
	void *tmp;

{ static int reent= 0; if (!reent) { reent++; printf("malloc\n"); reent--; } }
privious_free= (void *)-1;
	if (n == 0) {
		return NULL;
	}
	if (n < MIN_SIZE) n = align(MIN_SIZE); else n = align(n);
#ifdef STORE
	if (n <= MAX_STORE*MIN_SIZE)	{
		/* look in the store first */
		register mallink **stp = &store[(n >> LOG_MIN_SIZE) - 1];
		
		if (ml = *stp)	{
			*stp = log_next_of(ml);
			set_store(ml, 0);
			check_mallinks("malloc fast exit");
			assert(! in_store(ml));
			tmp= block_of_mallink(ml);
{ static int reent= 0; if (!reent) { reent++; printf("= 0x%x\n", tmp);reent--; } }
			return tmp;
		}
	}
#endif /* STORE */

	check_work_empty("malloc, entry");

	/*	Acquire a chunk of at least size n if at all possible;
		Try everything.
	*/
	{
		/*	Inline substitution of "smallest".
		*/
		register size_t n1 = n;