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