1da2e3ebchin/***********************************************************************
2da2e3ebchin*                                                                      *
3da2e3ebchin*               This software is part of the ast package               *
43e14f97Roger A. Faulkner*          Copyright (c) 1985-2010 AT&T Intellectual Property          *
5da2e3ebchin*                      and is licensed under the                       *
6da2e3ebchin*                  Common Public License, Version 1.0                  *
77c2fbfbApril Chin*                    by AT&T Intellectual Property                     *
8da2e3ebchin*                                                                      *
9da2e3ebchin*                A copy of the License is available at                 *
10da2e3ebchin*            http://www.opensource.org/licenses/cpl1.0.txt             *
11da2e3ebchin*         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
12da2e3ebchin*                                                                      *
13da2e3ebchin*              Information and Software Systems Research               *
14da2e3ebchin*                            AT&T Research                             *
15da2e3ebchin*                           Florham Park NJ                            *
16da2e3ebchin*                                                                      *
17da2e3ebchin*                 Glenn Fowler <gsf@research.att.com>                  *
18da2e3ebchin*                  David Korn <dgk@research.att.com>                   *
19da2e3ebchin*                   Phong Vo <kpv@research.att.com>                    *
20da2e3ebchin*                                                                      *
21da2e3ebchin***********************************************************************/
22da2e3ebchin#if defined(_UWIN) && defined(_BLD_ast)
23da2e3ebchin
24da2e3ebchinvoid _STUB_vmbest(){}
25da2e3ebchin
26da2e3ebchin#else
27da2e3ebchin
28da2e3ebchin#include	"vmhdr.h"
29da2e3ebchin
30da2e3ebchin/*	Best-fit allocation method. This is based on a best-fit strategy
31da2e3ebchin**	using a splay tree for storage of lists of free blocks of the same
32da2e3ebchin**	size. Recent free blocks may be cached for fast reuse.
33da2e3ebchin**
34da2e3ebchin**	Written by Kiem-Phong Vo, kpv@research.att.com, 01/16/94.
35da2e3ebchin*/
36da2e3ebchin
37da2e3ebchin#ifdef DEBUG
38da2e3ebchinstatic int	N_free;		/* # of free calls			*/
39da2e3ebchinstatic int	N_alloc;	/* # of alloc calls			*/
40da2e3ebchinstatic int	N_resize;	/* # of resize calls			*/
41da2e3ebchinstatic int	N_wild;		/* # allocated from the wild block	*/
42da2e3ebchinstatic int	N_last;		/* # allocated from last free block	*/
43da2e3ebchinstatic int	N_reclaim;	/* # of bestreclaim calls		*/
44da2e3ebchin
45da2e3ebchin#undef	VM_TRUST		/* always check for locking, etc.s	*/
46da2e3ebchin#define	VM_TRUST	0
47da2e3ebchin#endif /*DEBUG*/
48da2e3ebchin
493e14f97Roger A. Faulkner#if _BLD_posix
503e14f97Roger A. Faulkner#define logmsg(d,a ...)	logsrc(d,__FILE__,__LINE__,a)
513e14f97Roger A. Faulkner
523e14f97Roger A. Faulknerextern int	logsrc(int, const char*, int, const char*, ...);
533e14f97Roger A. Faulkner#endif /*_BLD_posix*/
543e14f97Roger A. Faulkner
55da2e3ebchin#define COMPACT		8	/* factor to decide when to compact	*/
56da2e3ebchin
57da2e3ebchin/* Check to see if a block is in the free tree */
58da2e3ebchin#if __STD_C
59da2e3ebchinstatic int vmintree(Block_t* node, Block_t* b)
60da2e3ebchin#else
61da2e3ebchinstatic int vmintree(node,b)
62da2e3ebchinBlock_t*	node;
63da2e3ebchinBlock_t*	b;
64da2e3ebchin#endif
65da2e3ebchin{	Block_t*	t;
66da2e3ebchin
67da2e3ebchin	for(t = node; t; t = LINK(t))
68da2e3ebchin		if(t == b)
69da2e3ebchin			return 1;
70da2e3ebchin	if(LEFT(node) && vmintree(LEFT(node),b))
71da2e3ebchin		return 1;
72da2e3ebchin	if(RIGHT(node) && vmintree(RIGHT(node),b))
73da2e3ebchin		return 1;
74da2e3ebchin	return 0;
75da2e3ebchin}
76da2e3ebchin
77da2e3ebchin#if __STD_C
78da2e3ebchinstatic int vmonlist(Block_t* list, Block_t* b)
79da2e3ebchin#else
80da2e3ebchinstatic int vmonlist(list,b)
81da2e3ebchinBlock_t*	list;
82da2e3ebchinBlock_t*	b;
83da2e3ebchin#endif
84da2e3ebchin{
85da2e3ebchin	for(; list; list = LINK(list))
86da2e3ebchin		if(list == b)
87da2e3ebchin			return 1;
88da2e3ebchin	return 0;
89da2e3ebchin}
90da2e3ebchin
91da2e3ebchin/* Check to see if a block is known to be free */
92da2e3ebchin#if __STD_C
93da2e3ebchinstatic int vmisfree(Vmdata_t* vd, Block_t* b)
94da2e3ebchin#else
95da2e3ebchinstatic int vmisfree(vd,b)
96da2e3ebchinVmdata_t*	vd;
97da2e3ebchinBlock_t*	b;
98da2e3ebchin#endif
99da2e3ebchin{
100da2e3ebchin	if(SIZE(b) & (BUSY|JUNK|PFREE))
101da2e3ebchin		return 0;
102da2e3ebchin
103da2e3ebchin	if(b == vd->wild)
104da2e3ebchin		return 1;
105da2e3ebchin
106da2e3ebchin	if(SIZE(b) < MAXTINY)
107da2e3ebchin		return vmonlist(TINY(vd)[INDEX(SIZE(b))], b);
108da2e3ebchin
109da2e3ebchin	if(vd->root)
110da2e3ebchin		return vmintree(vd->root, b);
111da2e3ebchin
112da2e3ebchin	return 0;
113da2e3ebchin}
114da2e3ebchin
115da2e3ebchin/* Check to see if a block is known to be junked */
116da2e3ebchin#if __STD_C
117da2e3ebchinstatic int vmisjunk(Vmdata_t* vd, Block_t* b)
118da2e3ebchin#else
119da2e3ebchinstatic int vmisjunk(vd,b)
120da2e3ebchinVmdata_t*	vd;
121da2e3ebchinBlock_t*	b;
122da2e3ebchin#endif
123da2e3ebchin{
124da2e3ebchin	Block_t*	t;
125da2e3ebchin
126da2e3ebchin	if((SIZE(b)&BUSY) == 0 || (SIZE(b)&JUNK) == 0)
127da2e3ebchin		return 0;
128da2e3ebchin
129da2e3ebchin	if(b == vd->free) /* recently freed */
130da2e3ebchin		return 1;
131da2e3ebchin
132da2e3ebchin	/* check the list that b is supposed to be in */
133da2e3ebchin	for(t = CACHE(vd)[C_INDEX(SIZE(b))]; t; t = LINK(t))
134da2e3ebchin		if(t == b)
135da2e3ebchin			return 1;
136da2e3ebchin
137da2e3ebchin	/* on occasions, b may be put onto the catch-all list */
138da2e3ebchin	if(C_INDEX(SIZE(b)) < S_CACHE)
139da2e3ebchin		for(t = CACHE(vd)[S_CACHE]; t; t = LINK(t))
140da2e3ebchin			if(t == b)
141da2e3ebchin				return 1;
142da2e3ebchin
143da2e3ebchin	return 0;
144da2e3ebchin}
145da2e3ebchin
146da2e3ebchin/* check to see if the free tree is in good shape */
147da2e3ebchin#if __STD_C
148da2e3ebchinstatic int vmchktree(Block_t* node)
149da2e3ebchin#else
150da2e3ebchinstatic int vmchktree(node)
151da2e3ebchinBlock_t*	node;
152da2e3ebchin#endif
153da2e3ebchin{	Block_t*	t;
154da2e3ebchin
155da2e3ebchin	if(SIZE(node) & BITS)
156da2e3ebchin		{ /**/ASSERT(0); return -1; }
157da2e3ebchin
158da2e3ebchin	for(t = LINK(node); t; t = LINK(t))
159da2e3ebchin		if(SIZE(t) != SIZE(node))
160da2e3ebchin			{ /**/ASSERT(0); return -1; }
161da2e3ebchin
162da2e3ebchin	if((t = LEFT(node)) )
163da2e3ebchin	{	if(SIZE(t) >= SIZE(node) )
164da2e3ebchin			{ /**/ASSERT(0); return -1; }
165da2e3ebchin		else	return vmchktree(t);
166da2e3ebchin	}
167da2e3ebchin	if((t = RIGHT(node)) )
168da2e3ebchin	{	if(SIZE(t) <= SIZE(node) )
169da2e3ebchin			{ /**/ASSERT(0); return -1; }
170da2e3ebchin		else	return vmchktree(t);
171da2e3ebchin	}
172da2e3ebchin
173da2e3ebchin	return 0;
174da2e3ebchin}
175da2e3ebchin
176da2e3ebchin#if __STD_C
177da2e3ebchinint _vmbestcheck(Vmdata_t* vd, Block_t* freeb)
178da2e3ebchin#else
179da2e3ebchinint _vmbestcheck(vd, freeb)
180da2e3ebchinVmdata_t*	vd;
181da2e3ebchinBlock_t*	freeb; /* known to be free but not on any free list */
182da2e3ebchin#endif
183da2e3ebchin{
184da2e3ebchin	reg Seg_t	*seg;
185da2e3ebchin	reg Block_t	*b, *endb, *nextb;
186da2e3ebchin	int		rv = 0;
187da2e3ebchin
188da2e3ebchin	if(!CHECK())
189da2e3ebchin		return 0;
190da2e3ebchin
191da2e3ebchin	/* make sure the free tree is still in shape */
192da2e3ebchin	if(vd->root && vmchktree(vd->root) < 0 )
193da2e3ebchin		{ rv = -1; /**/ASSERT(0); }
194da2e3ebchin
195da2e3ebchin	for(seg = vd->seg; seg && rv == 0; seg = seg->next)
196da2e3ebchin	{	b = SEGBLOCK(seg);
197da2e3ebchin		endb = (Block_t*)(seg->baddr - sizeof(Head_t));
198da2e3ebchin		for(; b < endb && rv == 0; b = nextb)
199da2e3ebchin		{	nextb = (Block_t*)((Vmuchar_t*)DATA(b) + (SIZE(b)&~BITS) );
200da2e3ebchin
201da2e3ebchin			if(!ISBUSY(SIZE(b)) ) /* a completely free block */
202da2e3ebchin			{	/* there should be no marked bits of any type */
203da2e3ebchin				if(SIZE(b) & (BUSY|JUNK|PFREE) )
204da2e3ebchin					{ rv = -1; /**/ASSERT(0); }
205da2e3ebchin
206da2e3ebchin				/* next block must be busy and marked PFREE */
207da2e3ebchin				if(!ISBUSY(SIZE(nextb)) || !ISPFREE(SIZE(nextb)) )
208da2e3ebchin					{ rv = -1; /**/ASSERT(0); }
209da2e3ebchin
210da2e3ebchin				/* must have a self-reference pointer */
211da2e3ebchin				if(*SELF(b) != b)
212da2e3ebchin					{ rv = -1; /**/ASSERT(0); }
213da2e3ebchin
214da2e3ebchin				/* segment pointer should be well-defined */
215da2e3ebchin				if(!TINIEST(b) && SEG(b) != seg)
216da2e3ebchin					{ rv = -1; /**/ASSERT(0); }
217da2e3ebchin
218da2e3ebchin				/* must be on a free list */
219da2e3ebchin				if(b != freeb && !vmisfree(vd, b) )
220da2e3ebchin					{ rv = -1; /**/ASSERT(0); }
221da2e3ebchin			}
222da2e3ebchin			else
223da2e3ebchin			{	/* segment pointer should be well-defined */
224da2e3ebchin				if(SEG(b) != seg)
225da2e3ebchin					{ rv = -1; /**/ASSERT(0); }
226da2e3ebchin
227da2e3ebchin				/* next block should not be marked PFREE */
228da2e3ebchin				if(ISPFREE(SIZE(nextb)) )
229da2e3ebchin					{ rv = -1; /**/ASSERT(0); }
230da2e3ebchin
231da2e3ebchin				/* if PFREE, last block should be free */
232da2e3ebchin				if(ISPFREE(SIZE(b)) && LAST(b) != freeb &&
233da2e3ebchin				   !vmisfree(vd, LAST(b)) )
234da2e3ebchin					{ rv = -1; /**/ASSERT(0); }
235da2e3ebchin
236da2e3ebchin				/* if free but unreclaimed, should be junk */
237da2e3ebchin				if(ISJUNK(SIZE(b)) && !vmisjunk(vd, b))
238da2e3ebchin					{ rv = -1; /**/ASSERT(0); }
239da2e3ebchin			}
240da2e3ebchin		}
241da2e3ebchin	}
242da2e3ebchin
243da2e3ebchin	return rv;
244da2e3ebchin}
245da2e3ebchin
246da2e3ebchin/* Tree rotation functions */
247da2e3ebchin#define RROTATE(x,y)	(LEFT(x) = RIGHT(y), RIGHT(y) = (x), (x) = (y))
248da2e3ebchin#define LROTATE(x,y)	(RIGHT(x) = LEFT(y), LEFT(y) = (x), (x) = (y))
249da2e3ebchin#define RLINK(s,x)	((s) = LEFT(s) = (x))
250da2e3ebchin#define LLINK(s,x)	((s) = RIGHT(s) = (x))
251da2e3ebchin
252da2e3ebchin/* Find and delete a suitable element in the free tree. */
253da2e3ebchin#if __STD_C
254da2e3ebchinstatic Block_t* bestsearch(Vmdata_t* vd, reg size_t size, Block_t* wanted)
255da2e3ebchin#else
256da2e3ebchinstatic Block_t* bestsearch(vd, size, wanted)
257da2e3ebchinVmdata_t*	vd;
258da2e3ebchinreg size_t	size;
259da2e3ebchinBlock_t*	wanted;
260da2e3ebchin#endif
261da2e3ebchin{
262da2e3ebchin	reg size_t	s;
263da2e3ebchin	reg Block_t	*t, *root, *l, *r;
264da2e3ebchin	Block_t		link;
265da2e3ebchin
266da2e3ebchin	/* extracting a tiniest block from its list */
267da2e3ebchin	if((root = wanted) && size == TINYSIZE)
268da2e3ebchin	{	reg Seg_t*	seg;
269da2e3ebchin
270da2e3ebchin		l = TLEFT(root);
271da2e3ebchin		if((r = LINK(root)) )
272da2e3ebchin			TLEFT(r) = l;
273da2e3ebchin		if(l)
274da2e3ebchin			LINK(l) = r;
275da2e3ebchin		else	TINY(vd)[0] = r;
276da2e3ebchin
277da2e3ebchin		seg = vd->seg;
278da2e3ebchin		if(!seg->next)
279da2e3ebchin			SEG(root) = seg;
280da2e3ebchin		else for(;; seg = seg->next)
281da2e3ebchin		{	if((Vmuchar_t*)root > (Vmuchar_t*)seg->addr &&
282da2e3ebchin			   (Vmuchar_t*)root < seg->baddr)
283da2e3ebchin			{	SEG(root) = seg;
284da2e3ebchin				break;
285da2e3ebchin			}
286da2e3ebchin		}
287da2e3ebchin
288da2e3ebchin		return root;
289da2e3ebchin	}
290da2e3ebchin
291da2e3ebchin	/**/ASSERT(!vd->root || vmchktree(vd->root) == 0);
292da2e3ebchin
293da2e3ebchin	/* find the right one to delete */
294da2e3ebchin	l = r = &link;
295da2e3ebchin	if((root = vd->root) ) do
296da2e3ebchin	{	/**/ ASSERT(!ISBITS(size) && !ISBITS(SIZE(root)));
297da2e3ebchin		if(size == (s = SIZE(root)) )
298da2e3ebchin			break;
299da2e3ebchin		if(size < s)
300da2e3ebchin		{	if((t = LEFT(root)) )
301da2e3ebchin			{	if(size <= (s = SIZE(t)) )
302da2e3ebchin				{	RROTATE(root,t);
303da2e3ebchin					if(size == s)
304da2e3ebchin						break;
305da2e3ebchin					t = LEFT(root);
306da2e3ebchin				}
307da2e3ebchin				else
308da2e3ebchin				{	LLINK(l,t);
309da2e3ebchin					t = RIGHT(t);
310da2e3ebchin				}
311da2e3ebchin			}
312da2e3ebchin			RLINK(r,root);
313da2e3ebchin		}
314da2e3ebchin		else
315da2e3ebchin		{	if((t = RIGHT(root)) )
316da2e3ebchin			{	if(size >= (s = SIZE(t)) )
317da2e3ebchin				{	LROTATE(root,t);
318da2e3ebchin					if(size == s)
319da2e3ebchin						break;
320da2e3ebchin					t = RIGHT(root);
321da2e3ebchin				}
322da2e3ebchin				else
323da2e3ebchin				{	RLINK(r,t);
324da2e3ebchin					t = LEFT(t);
325da2e3ebchin				}
326da2e3ebchin			}
327da2e3ebchin			LLINK(l,root);
328da2e3ebchin		}
329da2e3ebchin		/**/ ASSERT(root != t);
330da2e3ebchin	} while((root = t) );
331da2e3ebchin
332da2e3ebchin	if(root)	/* found it, now isolate it */
333da2e3ebchin	{	RIGHT(l) = LEFT(root);
334da2e3ebchin		LEFT(r) = RIGHT(root);
335da2e3ebchin	}
336da2e3ebchin	else		/* nothing exactly fit	*/
337da2e3ebchin	{	LEFT(r) = NIL(Block_t*);
338da2e3ebchin		RIGHT(l) = NIL(Block_t*);
339da2e3ebchin
340da2e3ebchin		/* grab the least one from the right tree */
341da2e3ebchin		if((root = LEFT(&link)) )
342da2e3ebchin		{	while((t = LEFT(root)) )
343da2e3ebchin				RROTATE(root,t);
344da2e3ebchin			LEFT(&link) = RIGHT(root);
345da2e3ebchin		}
346da2e3ebchin	}
347da2e3ebchin
348da2e3ebchin	if(root && (r = LINK(root)) )
349da2e3ebchin	{	/* head of a link list, use next one for root */
350da2e3ebchin		LEFT(r) = RIGHT(&link);
351da2e3ebchin		RIGHT(r) = LEFT(&link);
352da2e3ebchin	}
353da2e3ebchin	else if(!(r = LEFT(&link)) )
354da2e3ebchin		r = RIGHT(&link);
355da2e3ebchin	else /* graft left tree to right tree */
356da2e3ebchin	{	while((t = LEFT(r)) )
357da2e3ebchin			RROTATE(r,t);
358da2e3ebchin		LEFT(r) = RIGHT(&link);
359da2e3ebchin	}
360da2e3ebchin	vd->root = r; /**/ASSERT(!r || !ISBITS(SIZE(r)));
361da2e3ebchin
362da2e3ebchin	/**/ASSERT(!vd->root || vmchktree(vd->root) == 0);
363da2e3ebchin	/**/ASSERT(!wanted || wanted == root);
364da2e3ebchin
365da2e3ebchin	return root;
366da2e3ebchin}
367da2e3ebchin
368da2e3ebchin/* Reclaim all delayed free blocks into the free tree */
369da2e3ebchin#if __STD_C
370da2e3ebchinstatic int bestreclaim(reg Vmdata_t* vd, Block_t* wanted, int c)
371da2e3ebchin#else
372da2e3ebchinstatic int bestreclaim(vd, wanted, c)
373da2e3ebchinreg Vmdata_t*	vd;
374da2e3ebchinBlock_t*	wanted;
375da2e3ebchinint		c;
376da2e3ebchin#endif
377da2e3ebchin{
378da2e3ebchin	reg size_t	size, s;
379da2e3ebchin	reg Block_t	*fp, *np, *t, *list;
380da2e3ebchin	reg int		n, saw_wanted;
381da2e3ebchin	reg Seg_t	*seg;
382da2e3ebchin
383da2e3ebchin	/**/COUNT(N_reclaim);
384da2e3ebchin	/**/ASSERT(_vmbestcheck(vd, NIL(Block_t*)) == 0);
385da2e3ebchin
386da2e3ebchin	if((fp = vd->free) )
387da2e3ebchin	{	LINK(fp) = CACHE(vd)[S_CACHE]; CACHE(vd)[S_CACHE] = fp;
388da2e3ebchin		vd->free = NIL(Block_t*);
389da2e3ebchin	}
390da2e3ebchin
391da2e3ebchin	saw_wanted = wanted ? 0 : 1;
392da2e3ebchin	for(n = S_CACHE; n >= c; --n)
393da2e3ebchin	{	list = CACHE(vd)[n]; CACHE(vd)[n] = NIL(Block_t*);
394da2e3ebchin		while((fp = list) )
395da2e3ebchin		{	/* Note that below here we allow ISJUNK blocks to be
396da2e3ebchin			** forward-merged even though they are not removed from
397da2e3ebchin			** the list immediately. In this way, the list is
398da2e3ebchin			** scanned only once. It works because the LINK and SIZE
399da2e3ebchin			** fields are not destroyed during the merging. This can
400da2e3ebchin			** be seen by observing that a tiniest block has a 2-word
401da2e3ebchin			** header and a 2-word body. Merging a tiniest block
402da2e3ebchin			** (1seg) and the next block (2seg) looks like this:
403da2e3ebchin			**	1seg  size  link  left  2seg size link left ....
404da2e3ebchin			**	1seg  size  link  left  rite xxxx xxxx .... self
405da2e3ebchin			** After the merge, the 2seg word is replaced by the RIGHT
406da2e3ebchin			** pointer of the new block and somewhere beyond the
407da2e3ebchin			** two xxxx fields, the SELF pointer will replace some
408da2e3ebchin			** other word. The important part is that the two xxxx
409da2e3ebchin			** fields are kept intact.
410da2e3ebchin			*/
411da2e3ebchin			list = LINK(list); /**/ASSERT(!vmonlist(list,fp));
412da2e3ebchin
413da2e3ebchin			size = SIZE(fp);
414da2e3ebchin			if(!ISJUNK(size))	/* already done */
415da2e3ebchin				continue;
416da2e3ebchin
417da2e3ebchin			if(_Vmassert & VM_region)
418da2e3ebchin			{	/* see if this address is from region */
419da2e3ebchin				for(seg = vd->seg; seg; seg = seg->next)
420da2e3ebchin					if(fp >= SEGBLOCK(seg) && fp < (Block_t*)seg->baddr )
421da2e3ebchin						break;
422da2e3ebchin				if(!seg) /* must be a bug in application code! */
423da2e3ebchin				{	/**/ ASSERT(seg != NIL(Seg_t*));
424da2e3ebchin					continue;
425da2e3ebchin				}
426da2e3ebchin			}
427da2e3ebchin
428da2e3ebchin			if(ISPFREE(size))	/* backward merge */
429da2e3ebchin			{	fp = LAST(fp);
4303e14f97Roger A. Faulkner#if _BLD_posix
4313e14f97Roger A. Faulkner				if (fp < (Block_t*)0x00120000)
4323e14f97Roger A. Faulkner				{
4333e14f97Roger A. Faulkner					logmsg(0, "bestreclaim fp=%p", fp);
4343e14f97Roger A. Faulkner					ASSERT(!fp);
4353e14f97Roger A. Faulkner				}
4363e14f97Roger A. Faulkner#endif
437da2e3ebchin				s = SIZE(fp); /**/ASSERT(!(s&BITS));
438da2e3ebchin				REMOVE(vd,fp,INDEX(s),t,bestsearch);
439da2e3ebchin				size = (size&~BITS) + s + sizeof(Head_t);
440da2e3ebchin			}
441da2e3ebchin			else	size &= ~BITS;
442da2e3ebchin
443da2e3ebchin			for(;;)	/* forward merge */
444da2e3ebchin			{	np = (Block_t*)((Vmuchar_t*)fp+size+sizeof(Head_t));
4453e14f97Roger A. Faulkner#if _BLD_posix
4463e14f97Roger A. Faulkner				if (np < (Block_t*)0x00120000)
4473e14f97Roger A. Faulkner				{
4483e14f97Roger A. Faulkner					logmsg(0, "bestreclaim np=%p", np);
4493e14f97Roger A. Faulkner					ASSERT(!np);
4503e14f97Roger A. Faulkner				}
4513e14f97Roger A. Faulkner#endif
452da2e3ebchin				s = SIZE(np);	/**/ASSERT(s > 0);
453da2e3ebchin				if(!ISBUSY(s))
454da2e3ebchin				{	/**/ASSERT((s&BITS) == 0);
455da2e3ebchin					if(np == vd->wild)
456da2e3ebchin						vd->wild = NIL(Block_t*);
457da2e3ebchin					else	REMOVE(vd,np,INDEX(s),t,bestsearch);
458da2e3ebchin				}
459da2e3ebchin				else if(ISJUNK(s))
460da2e3ebchin				{	/* reclaim any touched junk list */
461da2e3ebchin					if((int)C_INDEX(s) < c)
462da2e3ebchin						c = C_INDEX(s);
463da2e3ebchin					SIZE(np) = 0;
464da2e3ebchin					CLRBITS(s);
465da2e3ebchin				}
466da2e3ebchin				else	break;
467da2e3ebchin				size += s + sizeof(Head_t);
468da2e3ebchin			}
469da2e3ebchin			SIZE(fp) = size;
470da2e3ebchin
471da2e3ebchin			/* tell next block that this one is free */
472da2e3ebchin			np = NEXT(fp);	/**/ASSERT(ISBUSY(SIZE(np)));
473da2e3ebchin					/**/ASSERT(!ISJUNK(SIZE(np)));
474da2e3ebchin			SETPFREE(SIZE(np));
475da2e3ebchin			*(SELF(fp)) = fp;
476da2e3ebchin
477da2e3ebchin			if(fp == wanted) /* to be consumed soon */
478da2e3ebchin			{	/**/ASSERT(!saw_wanted); /* should be seen just once */
479da2e3ebchin				saw_wanted = 1;
480da2e3ebchin				continue;
481da2e3ebchin			}
482da2e3ebchin
483da2e3ebchin			/* wilderness preservation */
484da2e3ebchin			if(np->body.data >= vd->seg->baddr)
485da2e3ebchin			{	vd->wild = fp;
486da2e3ebchin				continue;
487da2e3ebchin			}
488da2e3ebchin
489da2e3ebchin			/* tiny block goes to tiny list */
490da2e3ebchin			if(size < MAXTINY)
491da2e3ebchin			{	s = INDEX(size);
492da2e3ebchin				np = LINK(fp) = TINY(vd)[s];
493da2e3ebchin				if(s == 0)	/* TINIEST block */
494da2e3ebchin				{	if(np)
495da2e3ebchin						TLEFT(np) = fp;
496da2e3ebchin					TLEFT(fp) = NIL(Block_t*);
497da2e3ebchin				}
498da2e3ebchin				else
499da2e3ebchin				{	if(np)
500da2e3ebchin						LEFT(np)  = fp;
501da2e3ebchin					LEFT(fp) = NIL(Block_t*);
502da2e3ebchin					SETLINK(fp);
503da2e3ebchin				}
504da2e3ebchin				TINY(vd)[s] = fp;
505da2e3ebchin				continue;
506da2e3ebchin			}
507da2e3ebchin
508da2e3ebchin			LEFT(fp) = RIGHT(fp) = LINK(fp) = NIL(Block_t*);
509da2e3ebchin			if(!(np = vd->root) )	/* inserting into an empty tree	*/
510da2e3ebchin			{	vd->root = fp;
511da2e3ebchin				continue;
512da2e3ebchin			}
513da2e3ebchin
514da2e3ebchin			size = SIZE(fp);
515da2e3ebchin			while(1)	/* leaf insertion */
516da2e3ebchin			{	/**/ASSERT(np != fp);
517da2e3ebchin				if((s = SIZE(np)) > size)
518da2e3ebchin				{	if((t = LEFT(np)) )
519da2e3ebchin					{	/**/ ASSERT(np != t);
520da2e3ebchin						np = t;
521da2e3ebchin					}
522da2e3ebchin					else
523da2e3ebchin					{	LEFT(np) = fp;
524da2e3ebchin						break;
525da2e3ebchin					}
526da2e3ebchin				}
527da2e3ebchin				else if(s < size)
528da2e3ebchin				{	if((t = RIGHT(np)) )
529da2e3ebchin					{	/**/ ASSERT(np != t);
530da2e3ebchin						np = t;
531da2e3ebchin					}
532da2e3ebchin					else
533da2e3ebchin					{	RIGHT(np) = fp;
534da2e3ebchin						break;
535da2e3ebchin					}
536da2e3ebchin				}
537da2e3ebchin				else /* s == size */
538da2e3ebchin				{	if((t = LINK(np)) )
539da2e3ebchin					{	LINK(fp) = t;
540da2e3ebchin						LEFT(t) = fp;
541da2e3ebchin					}
542da2e3ebchin					LINK(np) = fp;
543da2e3ebchin					LEFT(fp) = np;
544da2e3ebchin					SETLINK(fp);
545da2e3ebchin					break;
546da2e3ebchin				}
547da2e3ebchin			}
548da2e3ebchin		}
549da2e3ebchin	}
550da2e3ebchin
551da2e3ebchin	/**/ASSERT(!wanted || saw_wanted == 1);
552da2e3ebchin	/**/ASSERT(_vmbestcheck(vd, wanted) == 0);
553da2e3ebchin	return saw_wanted;
554da2e3ebchin}
555da2e3ebchin
556da2e3ebchin#if __STD_C
557da2e3ebchinstatic int bestcompact(Vmalloc_t* vm)
558da2e3ebchin#else
559da2e3ebchinstatic int bestcompact(vm)
560da2e3ebchinVmalloc_t*	vm;
561da2e3ebchin#endif
562da2e3ebchin{
563da2e3ebchin	reg Seg_t	*seg, *next;
564da2e3ebchin	reg Block_t	*bp, *t;
565da2e3ebchin	reg size_t	size, segsize, round;
5667c2fbfbApril Chin	reg int		local, inuse;
567da2e3ebchin	reg Vmdata_t*	vd = vm->data;
568da2e3ebchin
5697c2fbfbApril Chin	SETINUSE(vd, inuse);
5707c2fbfbApril Chin
571da2e3ebchin	if(!(local = vd->mode&VM_TRUST) )
572da2e3ebchin	{	GETLOCAL(vd,local);
573da2e3ebchin		if(ISLOCK(vd,local))
5747c2fbfbApril Chin		{	CLRINUSE(vd, inuse);
575da2e3ebchin			return -1;
5767c2fbfbApril Chin		}
577da2e3ebchin		SETLOCK(vd,local);
578da2e3ebchin	}
579da2e3ebchin
580da2e3ebchin	bestreclaim(vd,NIL(Block_t*),0);
581da2e3ebchin
582da2e3ebchin	for(seg = vd->seg; seg; seg = next)
583da2e3ebchin	{	next = seg->next;
584da2e3ebchin
585da2e3ebchin		bp = BLOCK(seg->baddr);
586da2e3ebchin		if(!ISPFREE(SIZE(bp)) )
587da2e3ebchin			continue;
588da2e3ebchin
589da2e3ebchin		bp = LAST(bp);	/**/ASSERT(vmisfree(vd,bp));
590da2e3ebchin		size = SIZE(bp);
591da2e3ebchin		if(bp == vd->wild)
592da2e3ebchin		{	/* During large block allocations, _Vmextend might
593da2e3ebchin			** have been enlarged the rounding factor. Reducing
594da2e3ebchin			** it a bit help avoiding getting large raw memory.
595da2e3ebchin			*/
596da2e3ebchin			if((round = vm->disc->round) == 0)
597da2e3ebchin				round = _Vmpagesize;
598da2e3ebchin			if(size > COMPACT*vd->incr && vd->incr > round)
599da2e3ebchin				vd->incr /= 2;
600da2e3ebchin
601da2e3ebchin			/* for the bottom segment, we don't necessarily want
602da2e3ebchin			** to return raw memory too early. vd->pool has an
603da2e3ebchin			** approximation of the average size of recently freed
604da2e3ebchin			** blocks. If this is large, the application is managing
605da2e3ebchin			** large blocks so we throttle back memory chopping
606da2e3ebchin			** to avoid thrashing the underlying memory system.
607da2e3ebchin			*/
608da2e3ebchin			if(size <= COMPACT*vd->incr || size <= COMPACT*vd->pool)
609da2e3ebchin				continue;
610da2e3ebchin
611da2e3ebchin			vd->wild = NIL(Block_t*);
612da2e3ebchin			vd->pool = 0;
613da2e3ebchin		}
614da2e3ebchin		else	REMOVE(vd,bp,INDEX(size),t,bestsearch);
615da2e3eb