1/* $Id$ $Revision$ */
2/* vim:set shiftwidth=4 ts=8: */
3
4/*************************************************************************
5 * Copyright (c) 2011 AT&T Intellectual Property
6 * All rights reserved. This program and the accompanying materials
7 * are made available under the terms of the Eclipse Public License v1.0
8 * which accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
10 *
11 * Contributors: See CVS logs. Details at http://www.graphviz.org/
12 *************************************************************************/
13
14#include "vmhdr.h"
15
16#if 0 /* not used */
17static char *Version = "\n@(#)Vmalloc (AT&T Labs - kpv) 1999-08-05\0\n";
18#endif
19
20
21/* Private code used in the vmalloc library
22**
23** Written by Kiem-Phong Vo, kpv@research.att.com, 01/16/94.
24*/
25
26/**
27 * Get more memory for a region
28 *
29 * @param vm region to increase in size
30 * @param size desired amount of space
31 * @param searchf tree search function
32 */
33static Block_t *vmextend(reg Vmalloc_t * vm, size_t size,
34 Vmsearch_f searchf)
35{
36 reg size_t s;
37 reg Seg_t *seg;
38 reg Block_t *bp, *t;
39 reg Vmuchar_t *addr;
40 reg Vmdata_t *vd = vm->data;
41 reg Vmemory_f memoryf = vm->disc->memoryf;
42 reg Vmexcept_f exceptf = vm->disc->exceptf;
43
44 GETPAGESIZE(_Vmpagesize);
45
46 if (vd->incr <= 0) /* this is just _Vmheap on the first call */
47 vd->incr = 4 * _Vmpagesize;
48
49 /* Get slightly more for administrative data */
50 s = size + sizeof(Seg_t) + sizeof(Block_t) + sizeof(Head_t) +
51 2 * ALIGN;
52 if (s <= size) /* size was too large and we have wrapped around */
53 return NIL(Block_t *);
54 if ((size = ROUND(s, vd->incr)) < s)
55 return NIL(Block_t *);
56
57 /* see if we can extend the current segment */
58 if (!(seg = vd->seg))
59 addr = NIL(Vmuchar_t *);
60 else {
61 if (!vd->wild || SEG(vd->wild) != seg)
62 s = 0;
63 else {
64 s = SIZE(vd->wild) + sizeof(Head_t);
65 if ((s = (s / vd->incr) * vd->incr) == size)
66 size += vd->incr;
67 }
68 addr = (Vmuchar_t *) (*memoryf) (vm, seg->addr, seg->extent,
69 seg->extent + size - s, vm->disc);
70 if (!addr)
71 seg = NIL(Seg_t *);
72 else {
73 /**/ ASSERT(addr == (Vmuchar_t *) seg->addr);
74 addr += seg->extent;
75 size -= s;
76 }
77 }
78
79 while (!addr) { /* try to get space */
80 if ((addr =
81 (Vmuchar_t *) (*memoryf) (vm, NIL(void *), 0, size,
82 vm->disc)))
83 break;
84
85 /* check with exception handler to see if we should continue */
86 if (!exceptf)
87 return NIL(Block_t *);
88 else {
89 int rv, lock;
90 lock = vd->mode & VM_LOCK;
91 vd->mode &= ~VM_LOCK;
92 rv = (*exceptf) (vm, VM_NOMEM, (void *) size, vm->disc);
93 vd->mode |= lock;
94 if (rv <= 0) {
95 if (rv == 0)
96 vd->mode |= VM_AGAIN;
97 return NIL(Block_t *);
98 }
99 }
100 }
101
102 if (seg) { /* extending current segment */
103 bp = BLOCK(seg->baddr);
104 /**/ ASSERT((SIZE(bp) & ~BITS) == 0);
105 /**/ ASSERT(SEG(bp) == seg);
106
107 if (vd->mode & (VM_MTBEST | VM_MTDEBUG | VM_MTPROFILE)) {
108 if (!ISPFREE(SIZE(bp)))
109 SIZE(bp) = size - sizeof(Head_t);
110 else {
111 /**/ ASSERT(searchf);
112 bp = LAST(bp);
113 if (bp == vd->wild)
114 vd->wild = NIL(Block_t *);
115 else
116 REMOVE(vd, bp, INDEX(SIZE(bp)), t, (*searchf));
117 SIZE(bp) += size;
118 }
119 } else {
120 if (seg->free) {
121 bp = seg->free;
122 seg->free = NIL(Block_t *);
123 SIZE(bp) += size;
124 } else
125 SIZE(bp) = size - sizeof(Head_t);
126 }
127
128 seg->size += size;
129 seg->extent += size;
130 seg->baddr += size;
131 } else { /* creating a new segment */
132 reg Seg_t *sp, *lastsp;
133
134 if ((s = (size_t) (VLONG(addr) % ALIGN)) != 0)
135 addr += ALIGN - s;
136
137 seg = (Seg_t *) addr;
138 seg->vm = vm;
139 seg->addr = (void *) (addr - (s ? ALIGN - s : 0));
140 seg->extent = size;
141 seg->baddr = addr + size - (s ? 2 * ALIGN : 0);
142 seg->free = NIL(Block_t *);
143 bp = SEGBLOCK(seg);
144 SEG(bp) = seg;
145 SIZE(bp) = seg->baddr - (Vmuchar_t *) bp - 2 * sizeof(Head_t);
146
147 /* NOTE: for Vmbest, Vmdebug and Vmprofile the region's segment list
148 is reversely ordered by addresses. This is so that we can easily
149 check for the wild block.
150 */
151 lastsp = NIL(Seg_t *);
152 sp = vd->seg;
153 if (vd->mode & (VM_MTBEST | VM_MTDEBUG | VM_MTPROFILE))
154 for (; sp; lastsp = sp, sp = sp->next)
155 if (seg->addr > sp->addr)
156 break;
157 seg->next = sp;
158 if (lastsp)
159 lastsp->next = seg;
160 else
161 vd->seg = seg;
162
163 seg->size = SIZE(bp);
164 }
165
166 /* make a fake header for possible segmented memory */
167 t = NEXT(bp);
168 SEG(t) = seg;
169 SIZE(t) = BUSY;
170
171 /* see if the wild block is still wild */
172 if ((t = vd->wild) && (seg = SEG(t)) != vd->seg) {
173 CLRPFREE(SIZE(NEXT(t)));
174 if (vd->mode & (VM_MTBEST | VM_MTDEBUG | VM_MTPROFILE)) {
175 SIZE(t) |= BUSY | JUNK;
176 LINK(t) = CACHE(vd)[C_INDEX(SIZE(t))];
177 CACHE(vd)[C_INDEX(SIZE(t))] = t;
178 } else
179 seg->free = t;
180
181 vd->wild = NIL(Block_t *);
182 }
183
184 return bp;
185}
186
187/**
188 * Truncate a segment if possible
189 *
190 * @param vm containing region
191 * @param seg the one to be truncated
192 * @param size amount of free space
193 * @param exact amount given was exact
194 */
195static int vmtruncate(Vmalloc_t * vm, Seg_t * seg, size_t size, int exact)
196{
197 reg void *caddr;
198 reg Seg_t *last;
199 reg Vmdata_t *vd = vm->data;
200 reg Vmemory_f memoryf = vm->disc->memoryf;
201
202 caddr = seg->addr;
203
204 if (size < seg->size) {
205 reg size_t less;
206
207 /* the truncated amount must satisfy the discipline requirement */
208 if ((less = vm->disc->round) <= 0)
209 less = _Vmpagesize;
210 less = (size / less) * less;
211 less = (less / ALIGN) * ALIGN;
212
213 if (!exact) /* only truncate multiples of incr */
214 less = (less / vd->incr) * vd->incr;
215
216 if (less > 0 && size > less && (size - less) < sizeof(Block_t))
217 less -= vd->incr;
218
219 if (less <= 0 ||
220 (*memoryf) (vm, caddr, seg->extent, seg->extent - less,
221 vm->disc) != caddr)
222 return -1;
223
224 seg->extent -= less;
225 seg->size -= less;
226 seg->baddr -= less;
227 SIZE(BLOCK(seg->baddr)) = BUSY;
228 return 0;
229 }
230
231 /* unlink segment from region */
232 if (seg == vd->seg) {
233 vd->seg = seg->next;
234 last = NIL(Seg_t *);
235 } else {
236 for (last = vd->seg; last->next != seg; last = last->next);
237 last->next = seg->next;
238 }
239
240 /* now delete it */
241 if ((*memoryf) (vm, caddr, seg->extent, 0, vm->disc) == caddr)
242 return 0;
243
244 /* space reduction failed, reinsert segment */
245 if (last) {
246 seg->next = last->next;
247 last->next = seg;
248 } else {
249 seg->next = vd->seg;
250 vd->seg = seg;
251 }
252 return -1;
253}
254
255/* Externally visible names but local to library */
256Vmextern_t _Vmextern = { vmextend, /* _Vmextend */
257 vmtruncate, /* _Vmtruncate */
258 0, /* _Vmpagesize */
259 NIL(char *(*)(char *, char *, int)), /* _Vmstrcpy */
260 NIL(char *(*)(Vmulong_t, int)), /* _Vmitoa */
261 NIL(void (*)(Vmalloc_t *,
262 Vmuchar_t *, Vmuchar_t *, size_t, size_t)), /* _Vmtrace */
263 NIL(void (*)(Vmalloc_t *)) /* _Vmpfclose */
264};
265