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#define POOLFREE 0x55555555L /* block free indicator */
17
18/* Method for pool allocation.
19** All elements in a pool have the same size.
20** The following fields of Vmdata_t are used as:
21** pool: size of a block.
22** free: list of free blocks.
23**
24** Written by Kiem-Phong Vo, kpv@research.att.com, 01/16/94.
25*/
26
27static void *poolalloc(Vmalloc_t * vm, reg size_t size)
28{
29 reg Vmdata_t *vd = vm->data;
30 reg Block_t *tp, *next;
31 reg size_t s;
32 reg Seg_t *seg;
33 reg int local;
34
35 if (size <= 0)
36 return NIL(void *);
37 else if (size != vd->pool) {
38 if (vd->pool <= 0)
39 vd->pool = size;
40 else
41 return NIL(void *);
42 }
43
44 if (!(local = vd->mode & VM_TRUST)) {
45 if (ISLOCK(vd, 0))
46 return NIL(void *);
47 SETLOCK(vd, 0);
48 }
49
50 if ((tp = vd->free)) { /* there is a ready free block */
51 vd->free = SEGLINK(tp);
52 goto done;
53 }
54
55 size = ROUND(size, ALIGN);
56
57 /* look through all segments for a suitable free block */
58 for (tp = NIL(Block_t *), seg = vd->seg; seg; seg = seg->next) {
59 if ((tp = seg->free) &&
60 (s = (SIZE(tp) & ~BITS) + sizeof(Head_t)) >= size)
61 goto has_blk;
62 }
63
64 for (;;) { /* must extend region */
65 if ((tp =
66 (*_Vmextend) (vm, ROUND(size, vd->incr), NIL(Vmsearch_f)))) {
67 s = (SIZE(tp) & ~BITS) + sizeof(Head_t);
68 seg = SEG(tp);
69 goto has_blk;
70 } else if (vd->mode & VM_AGAIN)
71 vd->mode &= ~VM_AGAIN;
72 else
73 goto done;
74 }
75
76 has_blk: /* if get here, (tp, s, seg) must be well-defined */
77 next = (Block_t *) ((Vmuchar_t *) tp + size);
78 if ((s -= size) <= (size + sizeof(Head_t))) {
79 for (; s >= size; s -= size) {
80 SIZE(next) = POOLFREE;
81 SEGLINK(next) = vd->free;
82 vd->free = next;
83 next = (Block_t *) ((Vmuchar_t *) next + size);
84 }
85 seg->free = NIL(Block_t *);
86 } else {
87 SIZE(next) = s - sizeof(Head_t);
88 SEG(next) = seg;
89 seg->free = next;
90 }
91
92 done:
93 if (!local && (vd->mode & VM_TRACE) && _Vmtrace && tp)
94 (*_Vmtrace) (vm, NIL(Vmuchar_t *), (Vmuchar_t *) tp, vd->pool, 0);
95
96 CLRLOCK(vd, 0);
97 return (void *) tp;
98}
99
100static long pooladdr(Vmalloc_t * vm, reg void * addr)
101{
102 reg Block_t *bp, *tp;
103 reg Vmuchar_t *laddr, *baddr;
104 reg size_t size;
105 reg Seg_t *seg;
106 reg long offset;
107 reg Vmdata_t *vd = vm->data;
108 reg int local;
109
110 if (!(local = vd->mode & VM_TRUST)) {
111 GETLOCAL(vd, local);
112 if (ISLOCK(vd, local))
113 return -1L;
114 SETLOCK(vd, local);
115 }
116
117 offset = -1L;
118 for (seg = vd->seg; seg; seg = seg->next) {
119 laddr = (Vmuchar_t *) SEGBLOCK(seg);
120 baddr = seg->baddr - sizeof(Head_t);
121 if ((Vmuchar_t *) addr < laddr || (Vmuchar_t *) addr >= baddr)
122 continue;
123
124 /* the block that has this address */
125 size = ROUND(vd->pool, ALIGN);
126 tp = (Block_t *) (laddr +
127 (((Vmuchar_t *) addr - laddr) / size) * size);
128
129 /* see if this block has been freed */
130 if (SIZE(tp) == POOLFREE) /* may be a coincidence - make sure */
131 for (bp = vd->free; bp; bp = SEGLINK(bp))
132 if (bp == tp)
133 goto done;
134
135 offset = (Vmuchar_t *) addr - (Vmuchar_t *) tp;
136 goto done;
137 }
138
139 done:
140 CLRLOCK(vd, local);
141 return offset;
142}
143
144static int poolfree(reg Vmalloc_t * vm, reg void * data)
145{
146 reg Block_t *bp;
147 reg Vmdata_t *vd = vm->data;
148 reg int local;
149
150 if (!data)
151 return 0;
152
153 if (!(local = vd->mode & VM_TRUST)) {
154 if (ISLOCK(vd, 0) || vd->pool <= 0)
155 return -1;
156
157 if (KPVADDR(vm, data, pooladdr) != 0) {
158 if (vm->disc->exceptf)
159 (void) (*vm->disc->exceptf) (vm, VM_BADADDR, data,
160 vm->disc);
161 return -1;
162 }
163
164 SETLOCK(vd, 0);
165 }
166
167 bp = (Block_t *) data;
168 SIZE(bp) = POOLFREE;
169 SEGLINK(bp) = vd->free;
170 vd->free = bp;
171
172 if (!local && (vd->mode & VM_TRACE) && _Vmtrace)
173 (*_Vmtrace) (vm, (Vmuchar_t *) data, NIL(Vmuchar_t *), vd->pool,
174 0);
175
176 CLRLOCK(vd, local);
177 return 0;
178}
179
180static void *poolresize(Vmalloc_t * vm, void * data, size_t size,
181 int type)
182{
183 reg Vmdata_t *vd = vm->data;
184
185 NOTUSED(type);
186
187 if (!data) {
188 if ((data = poolalloc(vm, size)) && (type & VM_RSZERO)) {
189 reg int *d = (int *) data, *ed =
190 (int *) ((char *) data + size);
191 do {
192 *d++ = 0;
193 } while (d < ed);
194 }
195 return data;
196 }
197 if (size == 0) {
198 (void) poolfree(vm, data);
199 return NIL(void *);
200 }
201
202 if (!(vd->mode & VM_TRUST)) {
203 if (ISLOCK(vd, 0))
204 return NIL(void *);
205
206 if (size != vd->pool || KPVADDR(vm, data, pooladdr) != 0) {
207 if (vm->disc->exceptf)
208 (void) (*vm->disc->exceptf) (vm, VM_BADADDR, data,
209 vm->disc);
210 return NIL(void *);
211 }
212
213 if ((vd->mode & VM_TRACE) && _Vmtrace)
214 (*_Vmtrace) (vm, (Vmuchar_t *) data, (Vmuchar_t *) data, size,
215 0);
216 }
217
218 return data;
219}
220
221static long poolsize(Vmalloc_t * vm, void * addr)
222{
223 return pooladdr(vm, addr) == 0 ? (long) vm->data->pool : -1L;
224}
225
226static int poolcompact(Vmalloc_t * vm)
227{
228 reg Block_t *fp;
229 reg Seg_t *seg, *next;
230 reg size_t s;
231 reg Vmdata_t *vd = vm->data;
232
233 if (!(vd->mode & VM_TRUST)) {
234 if (ISLOCK(vd, 0))
235 return -1;
236 SETLOCK(vd, 0);
237 }
238
239 for (seg = vd->seg; seg; seg = next) {
240 next = seg->next;
241
242 if (!(fp = seg->free))
243 continue;
244
245 seg->free = NIL(Block_t *);
246 if (seg->size == (s = SIZE(fp) & ~BITS))
247 s = seg->extent;
248 else
249 s += sizeof(Head_t);
250
251 if ((*_Vmtruncate) (vm, seg, s, 1) < 0)
252 seg->free = fp;
253 }
254
255 if ((vd->mode & VM_TRACE) && _Vmtrace)
256 (*_Vmtrace) (vm, (Vmuchar_t *) 0, (Vmuchar_t *) 0, 0, 0);
257
258 CLRLOCK(vd, 0);
259 return 0;
260}
261
262static void *poolalign(Vmalloc_t * vm, size_t size, size_t align)
263{
264 NOTUSED(vm);
265 NOTUSED(size);
266 NOTUSED(align);
267 return NIL(void *);
268}
269
270/* Public interface */
271static Vmethod_t _Vmpool = {
272 poolalloc,
273 poolresize,
274 poolfree,
275 pooladdr,
276 poolsize,
277 poolcompact,
278 poolalign,
279 VM_MTPOOL
280};
281
282Vmethod_t* Vmpool = &_Vmpool;
283