xref: /titanic_44/usr/src/lib/libast/common/vmalloc/vmprivate.c (revision 3e14f97f673e8a630f076077de35afdd43dc1587)
1da2e3ebdSchin /***********************************************************************
2da2e3ebdSchin *                                                                      *
3da2e3ebdSchin *               This software is part of the ast package               *
4*3e14f97fSRoger A. Faulkner *          Copyright (c) 1985-2010 AT&T Intellectual Property          *
5da2e3ebdSchin *                      and is licensed under the                       *
6da2e3ebdSchin *                  Common Public License, Version 1.0                  *
77c2fbfb3SApril Chin *                    by AT&T Intellectual Property                     *
8da2e3ebdSchin *                                                                      *
9da2e3ebdSchin *                A copy of the License is available at                 *
10da2e3ebdSchin *            http://www.opensource.org/licenses/cpl1.0.txt             *
11da2e3ebdSchin *         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
12da2e3ebdSchin *                                                                      *
13da2e3ebdSchin *              Information and Software Systems Research               *
14da2e3ebdSchin *                            AT&T Research                             *
15da2e3ebdSchin *                           Florham Park NJ                            *
16da2e3ebdSchin *                                                                      *
17da2e3ebdSchin *                 Glenn Fowler <gsf@research.att.com>                  *
18da2e3ebdSchin *                  David Korn <dgk@research.att.com>                   *
19da2e3ebdSchin *                   Phong Vo <kpv@research.att.com>                    *
20da2e3ebdSchin *                                                                      *
21da2e3ebdSchin ***********************************************************************/
22da2e3ebdSchin #if defined(_UWIN) && defined(_BLD_ast)
23da2e3ebdSchin 
_STUB_vmprivate()24da2e3ebdSchin void _STUB_vmprivate(){}
25da2e3ebdSchin 
26da2e3ebdSchin #else
27da2e3ebdSchin 
28da2e3ebdSchin #include	"vmhdr.h"
29da2e3ebdSchin 
30*3e14f97fSRoger A. Faulkner static char*	Version = "\n@(#)$Id: Vmalloc (AT&T Research) 2010-01-01 $\0\n";
31da2e3ebdSchin 
32da2e3ebdSchin /*	Private code used in the vmalloc library
33da2e3ebdSchin **
34da2e3ebdSchin **	Written by Kiem-Phong Vo, kpv@research.att.com, 01/16/94.
35da2e3ebdSchin */
36da2e3ebdSchin 
37da2e3ebdSchin /* Get more memory for a region */
38da2e3ebdSchin #if __STD_C
vmextend(reg Vmalloc_t * vm,size_t size,Vmsearch_f searchf)39da2e3ebdSchin static Block_t* vmextend(reg Vmalloc_t* vm, size_t size, Vmsearch_f searchf )
40da2e3ebdSchin #else
41da2e3ebdSchin static Block_t* vmextend(vm, size, searchf )
42da2e3ebdSchin reg Vmalloc_t*	vm;		/* region to increase in size	*/
43da2e3ebdSchin size_t		size;		/* desired amount of space	*/
44da2e3ebdSchin Vmsearch_f	searchf;	/* tree search function		*/
45da2e3ebdSchin #endif
46da2e3ebdSchin {
47da2e3ebdSchin 	reg size_t	s;
48da2e3ebdSchin 	reg Seg_t*	seg;
49da2e3ebdSchin 	reg Block_t	*bp, *t;
50da2e3ebdSchin 	reg Vmuchar_t*	addr = (Vmuchar_t*)Version; /* shut compiler warning */
51da2e3ebdSchin 	reg Vmdata_t*	vd = vm->data;
52da2e3ebdSchin 	reg Vmemory_f	memoryf = vm->disc->memoryf;
53da2e3ebdSchin 	reg Vmexcept_f	exceptf = vm->disc->exceptf;
54da2e3ebdSchin 
55da2e3ebdSchin 	GETPAGESIZE(_Vmpagesize);
56da2e3ebdSchin 
57da2e3ebdSchin #if DEBUG /* trace all allocation calls through the heap */
58da2e3ebdSchin 	if(!_Vmtrace && vm == Vmheap && (vd->mode&VM_TRUST) )
59*3e14f97fSRoger A. Faulkner 		VMOPTIONS();
60da2e3ebdSchin #endif
61da2e3ebdSchin 
62da2e3ebdSchin 	if(vd->incr <= 0) /* this is just _Vmheap on the first call */
6334f9b3eeSRoland Mainz 		vd->incr = VMHEAPINCR;
64da2e3ebdSchin 
65da2e3ebdSchin 	/* Get slightly more for administrative data */
66da2e3ebdSchin 	s = size + sizeof(Seg_t) + sizeof(Block_t) + sizeof(Head_t) + 2*ALIGN;
67da2e3ebdSchin 	if(s <= size)	/* size was too large and we have wrapped around */
68da2e3ebdSchin 		return NIL(Block_t*);
69da2e3ebdSchin 	if((size = ROUND(s,vd->incr)) < s)
70da2e3ebdSchin 		return NIL(Block_t*);
71da2e3ebdSchin 
72da2e3ebdSchin 	/* increase the rounding factor to reduce # of future extensions */
73da2e3ebdSchin 	if(size > 2*vd->incr && vm->disc->round < vd->incr)
74da2e3ebdSchin 		vd->incr *= 2;
75da2e3ebdSchin 
76da2e3ebdSchin 	/* see if we can extend the current segment */
77da2e3ebdSchin 	if(!(seg = vd->seg) )
78da2e3ebdSchin 		addr = NIL(Vmuchar_t*);
79da2e3ebdSchin 	else
80da2e3ebdSchin 	{	if(!vd->wild || SEG(vd->wild) != seg)
81da2e3ebdSchin 			s = 0;
82da2e3ebdSchin 		else
83da2e3ebdSchin 		{	s = SIZE(vd->wild) + sizeof(Head_t);
84da2e3ebdSchin 			if((s = (s/vd->incr)*vd->incr) == size)
85da2e3ebdSchin 				size += vd->incr;
86da2e3ebdSchin 		}
87da2e3ebdSchin 		addr = (Vmuchar_t*)(*memoryf)(vm,seg->addr,seg->extent,
88da2e3ebdSchin 					  seg->extent+size-s,vm->disc);
89da2e3ebdSchin 		if(!addr)
90da2e3ebdSchin 			seg = NIL(Seg_t*);
91da2e3ebdSchin 		else
92da2e3ebdSchin 		{	/**/ASSERT(addr == (Vmuchar_t*)seg->addr);
93da2e3ebdSchin 			addr += seg->extent;
94da2e3ebdSchin 			size -= s;
95da2e3ebdSchin 		}
96da2e3ebdSchin 	}
97da2e3ebdSchin 
98da2e3ebdSchin 	while(!addr)	/* try to get space */
99da2e3ebdSchin 	{	if((addr = (Vmuchar_t*)(*memoryf)(vm,NIL(Void_t*),0,size,vm->disc)) )
100da2e3ebdSchin 			break;
101da2e3ebdSchin 
102da2e3ebdSchin 		/* check with exception handler to see if we should continue */
103da2e3ebdSchin 		if(!exceptf)
104da2e3ebdSchin 			return NIL(Block_t*);
105da2e3ebdSchin 		else
106da2e3ebdSchin 		{	int	rv, lock;
107da2e3ebdSchin 			lock = vd->mode&VM_LOCK;
108da2e3ebdSchin 			vd->mode &= ~VM_LOCK;
109da2e3ebdSchin 			rv = (*exceptf)(vm,VM_NOMEM,(Void_t*)size,vm->disc);
110da2e3ebdSchin 			vd->mode |= lock;
111da2e3ebdSchin 			if(rv <= 0)
112da2e3ebdSchin 			{	if(rv == 0)
113da2e3ebdSchin 					vd->mode |= VM_AGAIN;
114da2e3ebdSchin 				return NIL(Block_t*);
115da2e3ebdSchin 			}
116da2e3ebdSchin 		}
117da2e3ebdSchin 	}
118da2e3ebdSchin 
119da2e3ebdSchin 	if(seg)
120da2e3ebdSchin 	{	/* extending current segment */
121*3e14f97fSRoger A. Faulkner 		bp = BLOCK(seg->baddr);
122da2e3ebdSchin 
123da2e3ebdSchin 		if(vd->mode&(VM_MTBEST|VM_MTDEBUG|VM_MTPROFILE) )
124*3e14f97fSRoger A. Faulkner 		{	/**/ ASSERT((SIZE(bp)&~BITS) == 0);
125*3e14f97fSRoger A. Faulkner 			/**/ ASSERT(SEG(bp) == seg);
126*3e14f97fSRoger A. Faulkner 			if(!ISPFREE(SIZE(bp)) )
127da2e3ebdSchin 				SIZE(bp) = size - sizeof(Head_t);
128da2e3ebdSchin 			else
129da2e3ebdSchin 			{	/**/ ASSERT(searchf);
130da2e3ebdSchin 				bp = LAST(bp);
131da2e3ebdSchin 				if(bp == vd->wild)
132da2e3ebdSchin 					vd->wild = NIL(Block_t*);
133da2e3ebdSchin 				else	REMOVE(vd,bp,INDEX(SIZE(bp)),t,(*searchf));
134da2e3ebdSchin 				SIZE(bp) += size;
135da2e3ebdSchin 			}
136da2e3ebdSchin 		}
137da2e3ebdSchin 		else
138da2e3ebdSchin 		{	if(seg->free)
139da2e3ebdSchin 			{	bp = seg->free;
140da2e3ebdSchin 				seg->free = NIL(Block_t*);
141da2e3ebdSchin 				SIZE(bp) += size;
142da2e3ebdSchin 			}
143*3e14f97fSRoger A. Faulkner 			else
144*3e14f97fSRoger A. Faulkner 			{	SEG(bp) = seg;
145*3e14f97fSRoger A. Faulkner 				SIZE(bp) = size - sizeof(Head_t);
146*3e14f97fSRoger A. Faulkner 			}
147da2e3ebdSchin 		}
148da2e3ebdSchin 
149da2e3ebdSchin 		seg->size += size;
150da2e3ebdSchin 		seg->extent += size;
151da2e3ebdSchin 		seg->baddr += size;
152da2e3ebdSchin 	}
153da2e3ebdSchin 	else
154da2e3ebdSchin 	{	/* creating a new segment */
155da2e3ebdSchin 		reg Seg_t	*sp, *lastsp;
156da2e3ebdSchin 
157da2e3ebdSchin 		if((s = (size_t)(VLONG(addr)%ALIGN)) != 0)
158da2e3ebdSchin 			addr += ALIGN-s;
159da2e3ebdSchin 
160da2e3ebdSchin 		seg = (Seg_t*)addr;
161*3e14f97fSRoger A. Faulkner 		seg->vmdt = vd;
162da2e3ebdSchin 		seg->addr = (Void_t*)(addr - (s ? ALIGN-s : 0));
163da2e3ebdSchin 		seg->extent = size;
164da2e3ebdSchin 		seg->baddr = addr + size - (s ? 2*ALIGN : 0);
165da2e3ebdSchin 		seg->free = NIL(Block_t*);
166da2e3ebdSchin 		bp = SEGBLOCK(seg);
167da2e3ebdSchin 		SEG(bp) = seg;
168da2e3ebdSchin 		SIZE(bp) = seg->baddr - (Vmuchar_t*)bp - 2*sizeof(Head_t);
169da2e3ebdSchin 
170da2e3ebdSchin 		/* NOTE: for Vmbest, Vmdebug and Vmprofile the region's segment list
171da2e3ebdSchin 		   is reversely ordered by addresses. This is so that we can easily
172da2e3ebdSchin 		   check for the wild block.
173da2e3ebdSchin 		*/
174da2e3ebdSchin 		lastsp = NIL(Seg_t*);
175da2e3ebdSchin 		sp = vd->seg;
176da2e3ebdSchin 		if(vd->mode&(VM_MTBEST|VM_MTDEBUG|VM_MTPROFILE))
177da2e3ebdSchin 			for(; sp; lastsp = sp, sp = sp->next)
178da2e3ebdSchin 				if(seg->addr > sp->addr)
179da2e3ebdSchin 					break;
180da2e3ebdSchin 		seg->next = sp;
181da2e3ebdSchin 		if(lastsp)
182da2e3ebdSchin 			lastsp->next = seg;
183da2e3ebdSchin 		else	vd->seg = seg;
184da2e3ebdSchin 
185da2e3ebdSchin 		seg->size = SIZE(bp);
186da2e3ebdSchin 	}
187da2e3ebdSchin 
188da2e3ebdSchin 	/* make a fake header for possible segmented memory */
189da2e3ebdSchin 	t = NEXT(bp);
190da2e3ebdSchin 	SEG(t) = seg;
191da2e3ebdSchin 	SIZE(t) = BUSY;
192da2e3ebdSchin 
193da2e3ebdSchin 	/* see if the wild block is still wild */
194da2e3ebdSchin 	if((t = vd->wild) && (seg = SEG(t)) != vd->seg)
195da2e3ebdSchin 	{	CLRPFREE(SIZE(NEXT(t)));
196da2e3ebdSchin 		if(vd->mode&(VM_MTBEST|VM_MTDEBUG|VM_MTPROFILE) )
197da2e3ebdSchin 		{	SIZE(t) |= BUSY|JUNK;
198da2e3ebdSchin 			LINK(t) = CACHE(vd)[C_INDEX(SIZE(t))];
199da2e3ebdSchin 			CACHE(vd)[C_INDEX(SIZE(t))] = t;
200da2e3ebdSchin 		}
201da2e3ebdSchin 		else	seg->free = t;
202da2e3ebdSchin 
203da2e3ebdSchin 		vd->wild = NIL(Block_t*);
204da2e3ebdSchin 	}
205da2e3ebdSchin 
206da2e3ebdSchin 	return bp;
207da2e3ebdSchin }
208da2e3ebdSchin 
209da2e3ebdSchin /* Truncate a segment if possible */
210da2e3ebdSchin #if __STD_C
vmtruncate(Vmalloc_t * vm,Seg_t * seg,size_t size,int exact)211da2e3ebdSchin static ssize_t vmtruncate(Vmalloc_t* vm, Seg_t* seg, size_t size, int exact)
212da2e3ebdSchin #else
213da2e3ebdSchin static ssize_t vmtruncate(vm, seg, size, exact)
214da2e3ebdSchin Vmalloc_t*	vm;	/* containing region		*/
215da2e3ebdSchin Seg_t*		seg;	/* the one to be truncated	*/
216da2e3ebdSchin size_t		size;	/* amount of free space		*/
217da2e3ebdSchin int		exact;
218da2e3ebdSchin #endif
219da2e3ebdSchin {
220da2e3ebdSchin 	reg Void_t*	caddr;
221da2e3ebdSchin 	reg Seg_t*	last;
222da2e3ebdSchin 	reg Vmdata_t*	vd = vm->data;
223da2e3ebdSchin 	reg Vmemory_f	memoryf = vm->disc->memoryf;
224da2e3ebdSchin 
225da2e3ebdSchin 	caddr = seg->addr;
226da2e3ebdSchin 
227da2e3ebdSchin 	if(size < seg->size)
228da2e3ebdSchin 	{	reg ssize_t	less;
229da2e3ebdSchin 
230da2e3ebdSchin 		if(exact)
231da2e3ebdSchin 			less = size;
232da2e3ebdSchin 		else /* keep truncated amount to discipline requirements */
233da2e3ebdSchin 		{	if((less = vm->disc->round) <= 0)
234da2e3ebdSchin 				less = _Vmpagesize;
235da2e3ebdSchin 			less = (size/less)*less;
236da2e3ebdSchin 			less = (less/vd->incr)*vd->incr;
237*3e14f97fSRoger A. Faulkner 			if(less > 0 && size > (size_t)less && (size-(size_t)less) < sizeof(Block_t) )
238*3e14f97fSRoger A. Faulkner 				less = (size_t)less <= vd->incr ? 0 : (size_t)less - vd->incr;
239da2e3ebdSchin 		}
240da2e3ebdSchin 
241da2e3ebdSchin 		if(less <= 0 ||
242da2e3ebdSchin 		   (*memoryf)(vm,caddr,seg->extent,seg->extent-less,vm->disc) != caddr)
243da2e3ebdSchin 			return 0;
244da2e3ebdSchin 
245da2e3ebdSchin 		seg->extent -= less;
246da2e3ebdSchin 		seg->size -= less;
247da2e3ebdSchin 		seg->baddr -= less;
248da2e3ebdSchin 		SEG(BLOCK(seg->baddr)) = seg;
249da2e3ebdSchin 		SIZE(BLOCK(seg->baddr)) = BUSY;
250da2e3ebdSchin 
251da2e3ebdSchin 		return less;
252da2e3ebdSchin 	}
253da2e3ebdSchin 	else
254da2e3ebdSchin 	{	/* unlink segment from region */
255da2e3ebdSchin 		if(seg == vd->seg)
256da2e3ebdSchin 		{	vd->seg = seg->next;
257da2e3ebdSchin 			last = NIL(Seg_t*);
258da2e3ebdSchin 		}
259da2e3ebdSchin 		else
260da2e3ebdSchin 		{	for(last = vd->seg; last->next != seg; last = last->next)
261da2e3ebdSchin 				;
262da2e3ebdSchin 			last->next = seg->next;
263da2e3ebdSchin 		}
264da2e3ebdSchin 
265da2e3ebdSchin 		/* now delete it */
266da2e3ebdSchin 		if((*memoryf)(vm,caddr,seg->extent,0,vm->disc) == caddr)
267da2e3ebdSchin 			return size;
268da2e3ebdSchin 
269da2e3ebdSchin 		/* space reduction failed, reinsert segment */
270da2e3ebdSchin 		if(last)
271da2e3ebdSchin 		{	seg->next = last->next;
272da2e3ebdSchin 			last->next = seg;
273da2e3ebdSchin 		}
274da2e3ebdSchin 		else
275da2e3ebdSchin 		{	seg->next = vd->seg;
276da2e3ebdSchin 			vd->seg = seg;
277da2e3ebdSchin 		}
278da2e3ebdSchin 		return 0;
279da2e3ebdSchin 	}
280da2e3ebdSchin }
281da2e3ebdSchin 
282da2e3ebdSchin /* Externally visible names but local to library */
283da2e3ebdSchin Vmextern_t	_Vmextern =
284da2e3ebdSchin {	vmextend,						/* _Vmextend	*/
285da2e3ebdSchin 	vmtruncate,						/* _Vmtruncate	*/
286da2e3ebdSchin 	0,							/* _Vmpagesize	*/
287da2e3ebdSchin 	NIL(char*(*)_ARG_((char*,const char*,int))),		/* _Vmstrcpy	*/
288da2e3ebdSchin 	NIL(char*(*)_ARG_((Vmulong_t,int))),			/* _Vmitoa	*/
289da2e3ebdSchin 	NIL(void(*)_ARG_((Vmalloc_t*,
290da2e3ebdSchin 			  Vmuchar_t*,Vmuchar_t*,size_t,size_t))), /* _Vmtrace	*/
291da2e3ebdSchin 	NIL(void(*)_ARG_((Vmalloc_t*)))				/* _Vmpfclose	*/
292da2e3ebdSchin };
293da2e3ebdSchin 
294da2e3ebdSchin #endif
295