WebSVN – Kolibri OS – Blame – /programs/develop/open watcom/trunk/clib/src/mem.c

Rev	Author	Line No.	Line
359	serge	1	/****************************************************************************
		2	*
		3	* Open Watcom Project
		4	*
		5	* Portions Copyright (c) 1983-2002 Sybase, Inc. All Rights Reserved.
		6	*
		7	* ========================================================================
		8	*
		9	* This file contains Original Code and/or Modifications of Original
		10	* Code as defined in and that are subject to the Sybase Open Watcom
		11	* Public License version 1.0 (the 'License'). You may not use this file
		12	* except in compliance with the License. BY USING THIS FILE YOU AGREE TO
		13	* ALL TERMS AND CONDITIONS OF THE LICENSE. A copy of the License is
		14	* provided with the Original Code and Modifications, and is also
		15	* available at www.sybase.com/developer/opensource.
		16	*
		17	* The Original Code and all software distributed under the License are
		18	* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
		19	* EXPRESS OR IMPLIED, AND SYBASE AND ALL CONTRIBUTORS HEREBY DISCLAIM
		20	* ALL SUCH WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF
		21	* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR
		22	* NON-INFRINGEMENT. Please see the License for the specific language
		23	* governing rights and limitations under the License.
		24	*
		25	* ========================================================================
		26	*
		27	* Description: Heart of the heap manager. Do not break
		28	* unless you have a death wish.
		29	*
		30	****************************************************************************/
		31
		32
		33	#include "variety.h"
		34	#include
		35	#include
		36	#include "heap.h"
		37
		38
		39	#if defined(M_I86)
		40	extern unsigned setup_ds( unsigned );
		41	#pragma aux setup_ds = \
		42	"push ax" \
		43	"mov ax,ds" \
		44	"pop ds" \
		45	parm [ax] value [ax];
		46	#define setup_segment( _x ) _x = setup_ds( _x );
		47	#else
		48	#define setup_segment( _x ) (void)(_x = _x);
		49	#endif
		50
		51	//
		52	// input:
		53	// size - #bytes to allocate
		54	// segment - 16bit Intel data selector containing heap
		55	// offset - address of heap control block
		56	// if 16bit Intel -> offset within segment
		57	// else -> absolute pointer value
		58	//
		59	// output:
		60	// result - address of allocated storage or zero on failure
		61	// if 16bit Intel -> offset within segment
		62	// else -> absolute pointer value
		63	//
		64	unsigned __MemAllocator( unsigned size, unsigned segment, unsigned offset )
		65	{
		66	frlptr result;
		67	result = 0; // assume the worst
		68
		69	setup_segment( segment ); // setup DS for 16bit Intel
		70
		71	if( size != 0 ) { // quit if size is zero
		72	unsigned new_size;
		73	new_size = size + TAG_SIZE + ROUND_SIZE;// round up size
		74	if( new_size >= size ) { // quit if overflowed
		75	struct heapblkp _WCI86NEAR *heap;
		76	unsigned largest;
		77	heap = (struct heapblkp _WCI86NEAR *)offset;
		78	size = new_size & ~ROUND_SIZE; // make size even
		79	largest = heap->largest_blk;
		80	if( size < FRL_SIZE ) {
		81	size = FRL_SIZE;
		82	}
		83	if( size <= largest ) { // quit if size too big
		84	frlptr pcur;
		85	unsigned len;
		86	pcur = heap->rover; // start at rover
		87	largest = heap->b4rover;
		88	if( size <= largest ) { // check size with rover
		89	pcur = heap->freehead.next; // start at beginning
		90	largest = 0; // reset largest block size
		91	}
		92	for(;;) { // search free list
		93	len = pcur->len;
		94	if( size <= len ) { // found one
		95	break;
		96	}
		97	if( len > largest ) { // update largest block size
		98	largest = len;
		99	}
		100	pcur = pcur->next; // advance to next entry
		101	if( pcur == // if back at start
		102	(frlptr)&(heap->freehead)) {
		103	heap->largest_blk = largest; // update largest
		104	setup_segment( segment ); // 16bit Intel restore
		105	return( (unsigned)result ); // return 0
		106	}
		107	}
		108	heap->b4rover = largest; // update rover size
		109	heap->numalloc++; // udpate allocation count
		110	len -= size; // compute leftover size
		111	if( len >= FRL_SIZE ) { // if leftover big enough
		112	// split into two chunks
		113	frlptr pprev; // before current
		114	frlptr pnext; // after current
		115	frlptr pnew; // start of new piece
		116	pnew = (frlptr)((PTR)pcur + size);
		117	heap->rover = pnew; // update rover
		118	pnew->len = len; // set new size
		119	pcur->len = size; // reset current size
		120	pprev = pcur->prev; // update next/prev links
		121	pnew->prev = pprev;
		122	pnext = pcur->next;
		123	pnew->next = pnext;
		124	pprev->next = pnew;
		125	pnext->prev = pnew;
		126	} else { // just use this chunk
		127	frlptr pprev; // before current
		128	frlptr pnext; // after current
		129	heap->numfree--; // 1 fewer entries in free list
		130	pprev = pcur->prev;
		131	heap->rover = pprev; // update rover
		132	pnext = pcur->next; // update next/prev links
		133	pprev->next = pnext;
		134	pnext->prev = pprev;
		135	}
		136	pcur->len \|= 1; // mark as allocated
		137	// get pointer to user area
		138	result = (frlptr)((PTR)pcur + TAG_SIZE);
		139	}
		140	}
		141	}
		142	setup_segment( segment ); // 16bit Intel restore
		143	return( (unsigned)result );
		144	}
		145
		146	//
		147	// input:
		148	// pointer - address of block to free
		149	// if 16bit Intel -> offset within segment
		150	// else -> absolute pointer value
		151	// segment - 16bit Intel data selector containing heap
		152	// offset - address of heap control block
		153	// if 16bit Intel -> offset within segment
		154	// else -> absolute pointer value
		155	//
		156	// output:
		157	// none
		158	//
		159	void __MemFree( unsigned pointer, unsigned segment, unsigned offset )
		160	{
		161	setup_segment( segment ); // setup DS for 16bit Intel
		162
		163	if( pointer != 0 ) { // quit if pointer is zero
		164	frlptr pfree;
		165	pfree = (frlptr)(pointer - TAG_SIZE);
		166	if( pfree->len & 1 ) { // quit if storage is free
		167	struct heapblkp _WCI86NEAR *heap;
		168	frlptr pnext;
		169	frlptr pprev;
		170	frlptr ptr;
		171	unsigned len;
		172	heap = (struct heapblkp _WCI86NEAR *)offset;
		173	do { // this allows break statement
		174	unsigned average;
		175	unsigned numfree;
		176
		177	// look at next block to try and coalesce
		178	len = pfree->len & ~1; // get next block
		179	pnext = (frlptr)((PTR)pfree + len);
		180	if( (pnext->len & 1) == 0 ) { // if it is free
		181	len += pnext->len; // include the length
		182	pfree->len = len; // update pfree length
		183	if( pnext == heap->rover ) { // check for rover
		184	heap->rover = pfree; // update rover
		185	}
		186	pprev = pnext->prev; // fixup next/prev links
		187	pnext = pnext->next;
		188	pprev->next = pnext;
		189	pnext->prev = pprev;
		190	heap->numfree--; // reduce numfree
		191	break; // proceed to coalesce code
		192	}
		193
		194	// following block is not free
		195	// we must now try to figure out where pfree
		196	// is in relation to the entries in the free list
		197	pfree->len = len; // remove allocated marker
		198
		199	// check a few special places
		200	// see if pfree is:
		201	// - just before or just after the rover
		202	// - at the very beginning or very end of the heap
		203	pnext = heap->rover; // get rover
		204	if( pfree < pnext ) { // where is pfree?
		205	// pfree is before rover
		206	if( pfree > pnext->prev ) { // where is pfree?
		207	// pfree is next to rover
		208	break; // proceed to coalesce code
		209	}
		210	pnext = heap->freehead.next; // get start of free list
		211	if( pfree < pnext ) { // where is pfree?
		212	// pfree is at start of list
		213	break; // proceed to coalesce code
		214	}
		215	} else { // pfree is after rover
		216	pnext = pnext->next; // pnext is after rover
		217	if( pfree < pnext ) { // where is pfree?
		218	// pfree is just after rover
		219	break; // proceed to coalesce code
		220	}
		221	// get end of free list
		222	pnext = (frlptr)&(heap->freehead);
		223	pprev = pnext->prev;
		224	if( pfree > pprev ) { // where is pfree?
		225	// pfree is at end of list
		226	break; // proceed to coalesce code
		227	}
		228	}
		229
		230	// Calculate the average number of allocated blocks we may
		231	// have to skip until we expect to find a free block. If
		232	// this number is less than the total number of free blocks,
		233	// chances are that we can find the correct position in the
		234	// free list by scanning ahead for a free block and linking
		235	// this free block before the found free block. We protect
		236	// ourself against the degenerate case where there is an
		237	// extremely long string of allocated blocks by limiting the
		238	// number of blocks we will search to twice the calculated
		239	// average.
		240
		241	numfree = heap->numfree;
		242	average = heap->numalloc / (numfree+1);
		243	if( average < numfree ) {
		244
		245	// There are lots of allocated blocks and lots of free
		246	// blocks. On average we should find a free block
		247	// quickly by following the allocated blocks, but the
		248	// worst case can be very bad. So, we try scanning the
		249	// allocated blocks and give up once we have looked at
		250	// twice the average.
		251
		252	unsigned worst;
		253	worst = heap->numalloc - numfree;
		254	average *= 2; // give up after this many
		255	if( worst <= numfree ) {
		256	average = UINT_MAX; // we won't give up loop
		257	}
		258	// point at next allocated
		259	pnext = (frlptr)((PTR)pfree + pfree->len);
		260	for(;;) {
		261	len = pnext->len;
		262	if( len & 1 ) { // pnext is allocated
		263	if( len != END_TAG ) { // check for end TAG
		264	len &= ~1; // advance pnext
		265	pnext = (frlptr)((PTR)pnext + len);
		266	average--;
		267	if( !average ) { // give up search
		268	break;
		269	}
		270	} else {
		271	break; // stop at end tag
		272	}
		273	} else {
		274	// break twice!
		275	goto found_it; // we have the spot
		276	}
		277	}
		278	}
		279
		280	// when all else fails, search the free list
		281	pnext = heap->rover; // begin at rover
		282	if( pfree < pnext ) { // is pfree before rover?
		283	// then begin at start
		284	pnext = heap->freehead.next;
		285	}
		286	for(;;) {
		287	if( pfree < pnext ) { // if pfree before pnext
		288	break; // we found it
		289	}
		290	pnext = pnext->next; // advance pnext
		291
		292	if( pfree < pnext ) { // if pfree before pnext
		293	break; // we found it
		294	}
		295	pnext = pnext->next; // advance pnext
		296
		297	if( pfree < pnext ) { // if pfree before pnext
		298	break; // we found it
		299	}
		300	pnext = pnext->next; // advance pnext
		301	}
		302	} while( 0 ); // only do once
		303
		304	found_it:
		305	// if we are here, then we found the spot
		306	pprev = pnext->prev; // setup pprev
		307
		308	// pprev, pfree, pnext are all setup
		309	len = pfree->len;
		310
		311	// check pprev and pfree
		312	ptr = (frlptr)((PTR)pprev + pprev->len);
		313	if( ptr == pfree ) { // are they adjacent?
		314	// coalesce pprev and pfree
		315	len += pprev->len; // udpate len
		316	pprev->len = len;
		317	if( heap->rover == pfree ) { // check rover impact
		318	heap->rover = pprev; // update rover
		319	}
		320	pfree = pprev; // now work with coalesced blk
		321	} else {
		322	heap->numfree++; // one more free entry
		323	pfree->next = pnext; // update next/prev entries
		324	pfree->prev = pprev;
		325	pprev->next = pfree;
		326	pnext->prev = pfree;
		327	}
		328	heap->numalloc--; // one fewer allocated
		329
		330	if( pfree < heap->rover ) { // check rover impact
		331	if( len > heap->b4rover ) { // is len bigger than b4rover
		332	heap->b4rover = len; // then update b4rover
		333	}
		334	}
		335
		336	if( len > heap->largest_blk ) { // check largest block
		337	heap->largest_blk = len;
		338	}
		339	}
		340	}
		341
		342	setup_segment( segment ); // 16bit Intel restore
		343	}

Subversion Repositories Kolibri OS

(root)/programs/develop/open watcom/trunk/clib/src/mem.c – Rev 552