xref: /onnv-gate/usr/src/lib/libast/common/vmalloc/vmlast.c (revision 12068:08a39a083754)
14887Schin /***********************************************************************
24887Schin *                                                                      *
34887Schin *               This software is part of the ast package               *
4*12068SRoger.Faulkner@Oracle.COM *          Copyright (c) 1985-2010 AT&T Intellectual Property          *
54887Schin *                      and is licensed under the                       *
64887Schin *                  Common Public License, Version 1.0                  *
78462SApril.Chin@Sun.COM *                    by AT&T Intellectual Property                     *
84887Schin *                                                                      *
94887Schin *                A copy of the License is available at                 *
104887Schin *            http://www.opensource.org/licenses/cpl1.0.txt             *
114887Schin *         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
124887Schin *                                                                      *
134887Schin *              Information and Software Systems Research               *
144887Schin *                            AT&T Research                             *
154887Schin *                           Florham Park NJ                            *
164887Schin *                                                                      *
174887Schin *                 Glenn Fowler <gsf@research.att.com>                  *
184887Schin *                  David Korn <dgk@research.att.com>                   *
194887Schin *                   Phong Vo <kpv@research.att.com>                    *
204887Schin *                                                                      *
214887Schin ***********************************************************************/
224887Schin #if defined(_UWIN) && defined(_BLD_ast)
234887Schin 
_STUB_vmlast()244887Schin void _STUB_vmlast(){}
254887Schin 
264887Schin #else
274887Schin 
284887Schin #include	"vmhdr.h"
294887Schin 
304887Schin /*	Allocation with freeing and reallocing of last allocated block only.
314887Schin **
324887Schin **	Written by Kiem-Phong Vo, kpv@research.att.com, 01/16/94.
334887Schin */
344887Schin 
354887Schin #if __STD_C
lastalloc(Vmalloc_t * vm,size_t size)364887Schin static Void_t* lastalloc(Vmalloc_t* vm, size_t size)
374887Schin #else
384887Schin static Void_t* lastalloc(vm, size)
394887Schin Vmalloc_t*	vm;
404887Schin size_t		size;
414887Schin #endif
424887Schin {
434887Schin 	reg Block_t	*tp, *next;
444887Schin 	reg Seg_t	*seg, *last;
454887Schin 	reg size_t	s;
464887Schin 	reg Vmdata_t*	vd = vm->data;
478462SApril.Chin@Sun.COM 	reg int		local, inuse;
484887Schin 	size_t		orgsize = 0;
494887Schin 
508462SApril.Chin@Sun.COM 	SETINUSE(vd, inuse);
514887Schin 	if(!(local = vd->mode&VM_TRUST))
524887Schin 	{	GETLOCAL(vd,local);
534887Schin 		if(ISLOCK(vd,local))
548462SApril.Chin@Sun.COM 		{	CLRINUSE(vd, inuse);
554887Schin 			return NIL(Void_t*);
568462SApril.Chin@Sun.COM 		}
574887Schin 		SETLOCK(vd,local);
584887Schin 		orgsize = size;
594887Schin 	}
604887Schin 
614887Schin 	size = size < ALIGN ? ALIGN : ROUND(size,ALIGN);
624887Schin 	for(;;)
634887Schin 	{	for(last = NIL(Seg_t*), seg = vd->seg; seg; last = seg, seg = seg->next)
644887Schin 		{	if(!(tp = seg->free) || (SIZE(tp)+sizeof(Head_t)) < size)
654887Schin 				continue;
664887Schin 			if(last)
674887Schin 			{	last->next = seg->next;
684887Schin 				seg->next = vd->seg;
694887Schin 				vd->seg = seg;
704887Schin 			}
714887Schin 			goto got_block;
724887Schin 		}
734887Schin 
744887Schin 		/* there is no usable free space in region, try extending */
754887Schin 		if((tp = (*_Vmextend)(vm,size,NIL(Vmsearch_f))) )
764887Schin 		{	seg = SEG(tp);
774887Schin 			goto got_block;
784887Schin 		}
794887Schin 		else if(vd->mode&VM_AGAIN)
804887Schin 			vd->mode &= ~VM_AGAIN;
814887Schin 		else	goto done;
824887Schin 	}
834887Schin 
844887Schin got_block:
854887Schin 	if((s = SIZE(tp)) >= size)
864887Schin 	{	next = (Block_t*)((Vmuchar_t*)tp+size);
874887Schin 		SIZE(next) = s - size;
884887Schin 		SEG(next) = seg;
894887Schin 		seg->free = next;
904887Schin 	}
914887Schin 	else	seg->free = NIL(Block_t*);
924887Schin 
934887Schin 	vd->free = seg->last = tp;
944887Schin 
954887Schin 	if(!local && (vd->mode&VM_TRACE) && _Vmtrace)
964887Schin 		(*_Vmtrace)(vm, NIL(Vmuchar_t*), (Vmuchar_t*)tp, orgsize, 0);
974887Schin 
984887Schin done:
994887Schin 	CLRLOCK(vd,local);
1004887Schin 	ANNOUNCE(local, vm, VM_ALLOC, (Void_t*)tp, vm->disc);
1018462SApril.Chin@Sun.COM 	CLRINUSE(vd, inuse);
1024887Schin 	return (Void_t*)tp;
1034887Schin }
1044887Schin 
1054887Schin #if __STD_C
lastfree(Vmalloc_t * vm,reg Void_t * data)1064887Schin static int lastfree(Vmalloc_t* vm, reg Void_t* data )
1074887Schin #else
1084887Schin static int lastfree(vm, data)
1094887Schin Vmalloc_t*	vm;
1104887Schin reg Void_t*	data;
1114887Schin #endif
1124887Schin {
1134887Schin 	reg Seg_t*	seg;
1144887Schin 	reg Block_t*	fp;
1154887Schin 	reg size_t	s;
1164887Schin 	reg Vmdata_t*	vd = vm->data;
1178462SApril.Chin@Sun.COM 	reg int		local, inuse;
1184887Schin 
1194887Schin 	if(!data)
1204887Schin 		return 0;
1218462SApril.Chin@Sun.COM 
1228462SApril.Chin@Sun.COM 	SETINUSE(vd, inuse);
1234887Schin 	if(!(local = vd->mode&VM_TRUST) )
1244887Schin 	{	GETLOCAL(vd, local);
1254887Schin 		if(ISLOCK(vd, local))
1268462SApril.Chin@Sun.COM 		{	CLRINUSE(vd, inuse);
1274887Schin 			return -1;
1288462SApril.Chin@Sun.COM 		}
1294887Schin 		SETLOCK(vd, local);
1304887Schin 	}
1314887Schin 	if(data != (Void_t*)vd->free)
1324887Schin 	{	if(!local && vm->disc->exceptf)
1334887Schin 			(void)(*vm->disc->exceptf)(vm,VM_BADADDR,data,vm->disc);
1344887Schin 		CLRLOCK(vd, local);
1358462SApril.Chin@Sun.COM 		CLRINUSE(vd, inuse);
1364887Schin 		return -1;
1374887Schin 	}
1384887Schin 
1394887Schin 	seg = vd->seg;
1404887Schin 	if(!local && (vd->mode&VM_TRACE) && _Vmtrace)
1414887Schin 	{	if(seg->free )
1424887Schin 			s = (Vmuchar_t*)(seg->free) - (Vmuchar_t*)data;
1434887Schin 		else	s = (Vmuchar_t*)BLOCK(seg->baddr) - (Vmuchar_t*)data;
1444887Schin 		(*_Vmtrace)(vm, (Vmuchar_t*)data, NIL(Vmuchar_t*), s, 0);
1454887Schin 	}
1464887Schin 
1474887Schin 	vd->free = NIL(Block_t*);
1484887Schin 	fp = (Block_t*)data;
1494887Schin 	SEG(fp)  = seg;
1504887Schin 	SIZE(fp) = ((Vmuchar_t*)BLOCK(seg->baddr) - (Vmuchar_t*)data) - sizeof(Head_t);
1514887Schin 	seg->free = fp;
1524887Schin 	seg->last = NIL(Block_t*);
1534887Schin 
1544887Schin 	CLRLOCK(vd, local);
1554887Schin 	ANNOUNCE(local, vm, VM_FREE, data, vm->disc);
15610898Sroland.mainz@nrubsig.org 
1578462SApril.Chin@Sun.COM 	CLRINUSE(vd, inuse);
1584887Schin 	return 0;
1594887Schin }
1604887Schin 
1614887Schin #if __STD_C
lastresize(Vmalloc_t * vm,reg Void_t * data,size_t size,int type)1624887Schin static Void_t* lastresize(Vmalloc_t* vm, reg Void_t* data, size_t size, int type )
1634887Schin #else
1644887Schin static Void_t* lastresize(vm, data, size, type )
1654887Schin Vmalloc_t*	vm;
1664887Schin reg Void_t*	data;
1674887Schin size_t		size;
1684887Schin int		type;
1694887Schin #endif
1704887Schin {
1714887Schin 	reg Block_t*	tp;
1724887Schin 	reg Seg_t	*seg;
1734887Schin 	reg size_t	oldsize;
1744887Schin 	reg ssize_t	s, ds;
1754887Schin 	reg Vmdata_t*	vd = vm->data;
1768462SApril.Chin@Sun.COM 	reg int		local, inuse;
1774887Schin 	reg Void_t*	addr;
1784887Schin 	Void_t*		orgdata = NIL(Void_t*);
1794887Schin 	size_t		orgsize = 0;
1804887Schin 
1818462SApril.Chin@Sun.COM 	SETINUSE(vd, inuse);
1824887Schin 	if(!data)
1834887Schin 	{	oldsize = 0;
1844887Schin 		data = lastalloc(vm,size);
1854887Schin 		goto done;
1864887Schin 	}
1874887Schin 	if(size <= 0)
1884887Schin 	{	(void)lastfree(vm,data);
1898462SApril.Chin@Sun.COM 		CLRINUSE(vd, inuse);
1904887Schin 		return NIL(Void_t*);
1914887Schin 	}
1924887Schin 
1934887Schin 	if(!(local = vd->mode&VM_TRUST))
1944887Schin 	{	GETLOCAL(vd, local);
1954887Schin 		if(ISLOCK(vd, local))
1968462SApril.Chin@Sun.COM 		{	CLRINUSE(vd, inuse);
1974887Schin 			return NIL(Void_t*);
1988462SApril.Chin@Sun.COM 		}
1994887Schin 		SETLOCK(vd, local);
2004887Schin 		orgdata = data;
2014887Schin 		orgsize = size;
2024887Schin 	}
2034887Schin 
2044887Schin 	if(data == (Void_t*)vd->free)
2054887Schin 		seg = vd->seg;
2064887Schin 	else
2074887Schin 	{	/* see if it was one of ours */
2084887Schin 		for(seg = vd->seg; seg; seg = seg->next)
2094887Schin 			if(data >= seg->addr && data < (Void_t*)seg->baddr)
2104887Schin 				break;
2114887Schin 		if(!seg || (VLONG(data)%ALIGN) != 0 ||
2124887Schin 		   (seg->last && (Vmuchar_t*)data > (Vmuchar_t*)seg->last) )
2134887Schin 		{	CLRLOCK(vd,0);
2148462SApril.Chin@Sun.COM 			CLRINUSE(vd, inuse);
2154887Schin 			return NIL(Void_t*);
2164887Schin 		}
2174887Schin 	}
2184887Schin 
2194887Schin 	/* set 's' to be the current available space */
2204887Schin 	if(data != seg->last)
2214887Schin 	{	if(seg->last && (Vmuchar_t*)data < (Vmuchar_t*)seg->last)
2224887Schin 			oldsize = (Vmuchar_t*)seg->last - (Vmuchar_t*)data;
2234887Schin 		else	oldsize = (Vmuchar_t*)BLOCK(seg->baddr) - (Vmuchar_t*)data;
2244887Schin 		s = -1;
2254887Schin 	}
2264887Schin 	else
2274887Schin 	{	s = (Vmuchar_t*)BLOCK(seg->baddr) - (Vmuchar_t*)data;
2284887Schin 		if(!(tp = seg->free) )
2294887Schin 			oldsize = s;
2304887Schin 		else
2314887Schin 		{	oldsize = (Vmuchar_t*)tp - (Vmuchar_t*)data;
2324887Schin 			seg->free = NIL(Block_t*);
2334887Schin 		}
2344887Schin 	}
2354887Schin 
2364887Schin 	size = size < ALIGN ? ALIGN : ROUND(size,ALIGN);
2374887Schin 	if(s < 0 || (ssize_t)size > s)
2384887Schin 	{	if(s >= 0) /* amount to extend */
2394887Schin 		{	ds = size-s; ds = ROUND(ds,vd->incr);
2404887Schin 			addr = (*vm->disc->memoryf)(vm, seg->addr, seg->extent,
2414887Schin 						    seg->extent+ds, vm->disc);
2424887Schin 			if(addr == seg->addr)
2434887Schin 			{	s += ds;
2444887Schin 				seg->size += ds;
2454887Schin 				seg->extent += ds;
2464887Schin 				seg->baddr += ds;
2474887Schin 				SIZE(BLOCK(seg->baddr)) = BUSY;
2484887Schin 			}
2494887Schin 			else	goto do_alloc;
2504887Schin 		}
2514887Schin 		else
2524887Schin 		{ do_alloc:
2534887Schin 			if(!(type&(VM_RSMOVE|VM_RSCOPY)) )
2544887Schin 				data = NIL(Void_t*);
2554887Schin 			else
2564887Schin 			{	tp = vd->free;
2574887Schin 				if(!(addr = KPVALLOC(vm,size,lastalloc)) )
2584887Schin 				{	vd->free = tp;
2594887Schin 					data = NIL(Void_t*);
2604887Schin 				}
2614887Schin 				else
2624887Schin 				{	if(type&VM_RSCOPY)
2634887Schin 					{	ds = oldsize < size ? oldsize : size;
2644887Schin 						memcpy(addr, data, ds);
2654887Schin 					}
2664887Schin 
2674887Schin 					if(s >= 0 && seg != vd->seg)
2684887Schin 					{	tp = (Block_t*)data;
2694887Schin 						SEG(tp) = seg;
2704887Schin 						SIZE(tp) = s - sizeof(Head_t);
2714887Schin 						seg->free = tp;
2724887Schin 					}
2734887Schin 
2744887Schin 					/* new block and size */
2754887Schin 					data = addr;
2764887Schin 					seg = vd->seg;
2774887Schin 					s = (Vmuchar_t*)BLOCK(seg->baddr) -
2784887Schin 					    (Vmuchar_t*)data;
2794887Schin 					seg->free = NIL(Block_t*);
2804887Schin 				}
2814887Schin 			}
2824887Schin 		}
2834887Schin 	}
2844887Schin 
2854887Schin 	if(data)
2864887Schin 	{	if(s >= (ssize_t)(size+sizeof(Head_t)) )
2874887Schin 		{	tp = (Block_t*)((Vmuchar_t*)data + size);
2884887Schin 			SEG(tp) = seg;
2894887Schin 			SIZE(tp) = (s - size) - sizeof(Head_t);
2904887Schin 			seg->free = tp;
2914887Schin 		}
2924887Schin 
2934887Schin 		vd->free = seg->last = (Block_t*)data;
2944887Schin 
2954887Schin 		if(!local && (vd->mode&VM_TRACE) && _Vmtrace)
2964887Schin 			(*_Vmtrace)(vm,(Vmuchar_t*)orgdata,(Vmuchar_t*)data,orgsize,0);
2974887Schin 	}
2984887Schin 
2994887Schin 	CLRLOCK(vd, local);
3004887Schin 	ANNOUNCE(local, vm, VM_RESIZE, data, vm->disc);
3014887Schin 
3024887Schin done:	if(data && (type&VM_RSZERO) && size > oldsize)
3034887Schin 		memset((Void_t*)((Vmuchar_t*)data + oldsize), 0, size-oldsize);
3044887Schin 
3058462SApril.Chin@Sun.COM 	CLRINUSE(vd, inuse);
3064887Schin 	return data;
3074887Schin }
3084887Schin 
3094887Schin 
3104887Schin #if __STD_C
lastaddr(Vmalloc_t * vm,Void_t * addr)3114887Schin static long lastaddr(Vmalloc_t* vm, Void_t* addr)
3124887Schin #else
3134887Schin static long lastaddr(vm, addr)
3144887Schin Vmalloc_t*	vm;
3154887Schin Void_t*		addr;
3164887Schin #endif
3174887Schin {
3184887Schin 	reg Vmdata_t*	vd = vm->data;
3194887Schin 
3204887Schin 	if(!(vd->mode&VM_TRUST) && ISLOCK(vd,0))
3214887Schin 		return -1L;
3224887Schin 	if(!vd->free || addr < (Void_t*)vd->free || addr >= (Void_t*)vd->seg->baddr)
3234887Schin 		return -1L;
3244887Schin 	else	return (Vmuchar_t*)addr - (Vmuchar_t*)vd->free;
3254887Schin }
3264887Schin 
3274887Schin #if __STD_C
lastsize(Vmalloc_t * vm,Void_t * addr)3284887Schin static long lastsize(Vmalloc_t* vm, Void_t* addr)
3294887Schin #else
3304887Schin static long lastsize(vm, addr)
3314887Schin Vmalloc_t*	vm;
3324887Schin Void_t*		addr;
3334887Schin #endif
3344887Schin {
3354887Schin 	reg Vmdata_t*	vd = vm->data;
3364887Schin 
3374887Schin 	if(!(vd->mode&VM_TRUST) && ISLOCK(vd,0))
3384887Schin 		return -1L;
3394887Schin 	if(!vd->free || addr != (Void_t*)vd->free )
3404887Schin 		return -1L;
3414887Schin 	else if(vd->seg->free)
3424887Schin 		return (Vmuchar_t*)vd->seg->free - (Vmuchar_t*)addr;
3434887Schin 	else	return (Vmuchar_t*)vd->seg->baddr - (Vmuchar_t*)addr - sizeof(Head_t);
3444887Schin }
3454887Schin 
3464887Schin #if __STD_C
lastcompact(Vmalloc_t * vm)3474887Schin static int lastcompact(Vmalloc_t* vm)
3484887Schin #else
3494887Schin static int lastcompact(vm)
3504887Schin Vmalloc_t*	vm;
3514887Schin #endif
3524887Schin {
3534887Schin 	reg Block_t*	fp;
3544887Schin 	reg Seg_t	*seg, *next;
3554887Schin 	reg size_t	s;
3564887Schin 	reg Vmdata_t*	vd = vm->data;
3578462SApril.Chin@Sun.COM 	reg int		inuse;
3584887Schin 
3598462SApril.Chin@Sun.COM 	SETINUSE(vd, inuse);
3604887Schin 	if(!(vd->mode&VM_TRUST))
3614887Schin 	{	if(ISLOCK(vd,0))
3628462SApril.Chin@Sun.COM 		{	CLRINUSE(vd, inuse);
3634887Schin 			return -1;
3648462SApril.Chin@Sun.COM 		}
3654887Schin 		SETLOCK(vd,0);
3664887Schin 	}
3674887Schin 
3684887Schin 	for(seg = vd->seg; seg; seg = next)
3694887Schin 	{	next = seg->next;
3704887Schin 
3714887Schin 		if(!(fp = seg->free))
3724887Schin 			continue;
3734887Schin 
3744887Schin 		seg->free = NIL(Block_t*);
3754887Schin 		if(seg->size == (s = SIZE(fp)&~BITS))
3764887Schin 			s = seg->extent;
3774887Schin 		else	s += sizeof(Head_t);
3784887Schin 
3794887Schin 		if((*_Vmtruncate)(vm,seg,s,1) == s)
3804887Schin 			seg->free = fp;
3814887Schin 	}
3824887Schin 
3834887Schin 	if((vd->mode&VM_TRACE) && _Vmtrace)
3844887Schin 		(*_Vmtrace)(vm,(Vmuchar_t*)0,(Vmuchar_t*)0,0,0);
3854887Schin 
3864887Schin 	CLRLOCK(vd,0);
3878462SApril.Chin@Sun.COM 	CLRINUSE(vd, inuse);
3884887Schin 	return 0;
3894887Schin }
3904887Schin 
3914887Schin #if __STD_C
lastalign(Vmalloc_t * vm,size_t size,size_t align)3924887Schin static Void_t* lastalign(Vmalloc_t* vm, size_t size, size_t align)
3934887Schin #else
3944887Schin static Void_t* lastalign(vm, size, align)
3954887Schin Vmalloc_t*	vm;
3964887Schin size_t		size;
3974887Schin size_t		align;
3984887Schin #endif
3994887Schin {
4004887Schin 	reg Vmuchar_t*	data;
4014887Schin 	reg Seg_t*	seg;
4024887Schin 	reg Block_t*	next;
4038462SApril.Chin@Sun.COM 	reg int		local, inuse;
4044887Schin 	reg size_t	s, orgsize = 0, orgalign = 0;
4054887Schin 	reg Vmdata_t*	vd = vm->data;
4064887Schin 
4074887Schin 	if(size <= 0 || align <= 0)
4084887Schin 		return NIL(Void_t*);
4094887Schin 
4108462SApril.Chin@Sun.COM 	SETINUSE(vd, inuse);
4114887Schin 	if(!(local = vd->mode&VM_TRUST) )
4124887Schin 	{	GETLOCAL(vd,local);
4134887Schin 		if(ISLOCK(vd,local) )
4148462SApril.Chin@Sun.COM 		{	CLRINUSE(vd, inuse);
4154887Schin 			return NIL(Void_t*);
4168462SApril.Chin@Sun.COM 		}
4174887Schin 		SETLOCK(vd,local);
4184887Schin 		orgsize = size;
4194887Schin 		orgalign = align;
4204887Schin 	}
4214887Schin 
4224887Schin 	size = size <= TINYSIZE ? TINYSIZE : ROUND(size,ALIGN);
4234887Schin 	align = MULTIPLE(align,ALIGN);
4244887Schin 
4254887Schin 	s = size + align;
4264887Schin 	if(!(data = (Vmuchar_t*)KPVALLOC(vm,s,lastalloc)) )
4274887Schin 		goto done;
4284887Schin 
4294887Schin 	/* find the segment containing this block */
4304887Schin 	for(seg = vd->seg; seg; seg = seg->next)
4314887Schin 		if(seg->last == (Block_t*)data)
4324887Schin 			break;
4334887Schin 	/**/ASSERT(seg);
4344887Schin 
4354887Schin 	/* get a suitably aligned address */
4364887Schin 	if((s = (size_t)(VLONG(data)%align)) != 0)
4374887Schin 		data += align-s; /**/ASSERT((VLONG(data)%align) == 0);
4384887Schin 
4394887Schin 	/* free the unused tail */
4404887Schin 	next = (Block_t*)(data+size);
4414887Schin 	if((s = (seg->baddr - (Vmuchar_t*)next)) >= sizeof(Block_t))
4424887Schin 	{	SEG(next) = seg;
4434887Schin 		SIZE(next) = s - sizeof(Head_t);
4444887Schin 		seg->free = next;
4454887Schin 	}
4464887Schin 
4474887Schin 	vd->free = seg->last = (Block_t*)data;
4484887Schin 
4494887Schin 	if(!local && !(vd->mode&VM_TRUST) && _Vmtrace && (vd->mode&VM_TRACE) )
4504887Schin 		(*_Vmtrace)(vm,NIL(Vmuchar_t*),data,orgsize,orgalign);
4514887Schin 
4524887Schin done:
4534887Schin 	CLRLOCK(vd,local);
4544887Schin 	ANNOUNCE(local, vm, VM_ALLOC, (Void_t*)data, vm->disc);
4554887Schin 
4568462SApril.Chin@Sun.COM 	CLRINUSE(vd, inuse);
4574887Schin 	return (Void_t*)data;
4584887Schin }
4594887Schin 
4604887Schin /* Public method for free-1 allocation */
4614887Schin static Vmethod_t _Vmlast =
4624887Schin {
4634887Schin 	lastalloc,
4644887Schin 	lastresize,
4654887Schin 	lastfree,
4664887Schin 	lastaddr,
4674887Schin 	lastsize,
4684887Schin 	lastcompact,
4694887Schin 	lastalign,
4704887Schin 	VM_MTLAST
4714887Schin };
4724887Schin 
4734887Schin __DEFINE__(Vmethod_t*,Vmlast,&_Vmlast);
4744887Schin 
4754887Schin #ifdef NoF
4764887Schin NoF(vmlast)
4774887Schin #endif
4784887Schin 
4794887Schin #endif
480