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#ifdef __cplusplus
15extern "C" {
16#endif
17
18#ifndef _VMHDR_H
19#define _VMHDR_H 1
20#ifndef _BLD_vmalloc
21#define _BLD_vmalloc 1
22#endif
23#ifdef _WIN32
24#include <io.h>
25#endif
26
27/* Common types, and macros for vmalloc functions.
28**
29** Written by Kiem-Phong Vo, kpv@research.att.com, 01/16/94.
30*/
31
32#include "config.h"
33
34#include <inttypes.h>
35#include <stdlib.h>
36
37#ifdef HAVE_SYS_TYPES_H
38# include <sys/types.h>
39#endif // HAVE_SYS_TYPES_H
40
41#undef free
42#undef malloc
43#undef realloc
44#undef BITS
45
46 typedef unsigned char Vmuchar_t;
47 typedef uint64_t Vmulong_t;
48
49 typedef union _head_u Head_t;
50 typedef union _body_u Body_t;
51 typedef struct _block_s Block_t;
52 typedef struct _seg_s Seg_t;
53 typedef struct _pfobj_s Pfobj_t;
54
55#define NIL(t) ((t)0)
56#define reg register
57#define NOTUSED(x) (void)(x)
58
59/* convert an address to an integral value */
60#define VLONG(addr) ((Vmulong_t)((char*)(addr) - (char*)0) )
61
62/* Round x up to a multiple of y. ROUND2 does powers-of-2 and ROUNDX does others */
63#define ROUND2(x,y) (((x) + ((y)-1)) & ~((y)-1))
64#define ROUNDX(x,y) ((((x) + ((y)-1)) / (y)) * (y))
65#define ROUND(x,y) (((y)&((y)-1)) ? ROUNDX((x),(y)) : ROUND2((x),(y)) )
66
67/* compute a value that is a common multiple of x and y */
68#define MULTIPLE(x,y) ((x)%(y) == 0 ? (x) : (y)%(x) == 0 ? (y) : (y)*(x))
69
70#ifndef DEBUG
71#define ASSERT(p)
72#define COUNT(n)
73#else
74 extern int printf(const char *, ...);
75#if defined(__LINE__) && defined(__FILE__)
76#define PRFILELINE printf("Assertion failed at %s:%d\n",__FILE__,__LINE__)
77#else
78#define PRFILELINE 0
79#endif
80#define ASSERT(p) ((p) ? 0 : (PRFILELINE, abort(), 0) )
81#define COUNT(n) ((n) += 1)
82#endif /*DEBUG*/
83#define VMPAGESIZE 8192
84#ifdef HAVE_GETPAGESIZE
85#define GETPAGESIZE(x) ((x) ? (x) : \
86 (((x)=getpagesize()) < VMPAGESIZE ? ((x)=VMPAGESIZE) : (x)) )
87#else
88#define GETPAGESIZE(x) ((x) = VMPAGESIZE)
89#endif
90/* Blocks are allocated such that their sizes are 0%(BITS+1)
91** This frees up enough low order bits to store state information
92*/
93#define BUSY (01) /* block is busy */
94#define PFREE (02) /* preceding block is free */
95#define JUNK (04) /* marked as freed but not yet processed */
96#define BITS (07) /* (BUSY|PFREE|JUNK) */
97#define ALIGNB (8) /* size must be a multiple of BITS+1 */
98#define ISBITS(w) ((w) & BITS)
99#define CLRBITS(w) ((w) &= ~BITS)
100#define CPYBITS(w,f) ((w) |= ((f)&BITS) )
101#define ISBUSY(w) ((w) & BUSY)
102#define SETBUSY(w) ((w) |= BUSY)
103#define CLRBUSY(w) ((w) &= ~BUSY)
104#define ISPFREE(w) ((w) & PFREE)
105#define SETPFREE(w) ((w) |= PFREE)
106#define CLRPFREE(w) ((w) &= ~PFREE)
107#define ISJUNK(w) ((w) & JUNK)
108#define SETJUNK(w) ((w) |= JUNK)
109#define CLRJUNK(w) ((w) &= ~JUNK)
110#define OFFSET(t,e) ((size_t)(&(((t*)0)->e)) )
111/* these bits share the "mode" field with the public bits */
112#define VM_AGAIN 0010000 /* research the arena for space */
113#define VM_LOCK 0020000 /* region is locked */
114#define VM_LOCAL 0040000 /* local call, bypass lock */
115#define VM_UNUSED 0104060
116#define VMETHOD(vd) ((vd)->mode&VM_METHODS)
117/* test/set/clear lock state */
118#define SETLOCAL(vd) ((vd)->mode |= VM_LOCAL)
119#define GETLOCAL(vd,l) (((l) = (vd)->mode&VM_LOCAL), ((vd)->mode &= ~VM_LOCAL) )
120#define ISLOCK(vd,l) ((l) ? 0 : ((vd)->mode & VM_LOCK) )
121#define SETLOCK(vd,l) ((l) ? 0 : ((vd)->mode |= VM_LOCK) )
122#define CLRLOCK(vd,l) ((l) ? 0 : ((vd)->mode &= ~VM_LOCK) )
123/* local calls */
124#define KPVALLOC(vm,sz,func) (SETLOCAL((vm)->data), func((vm),(sz)) )
125#define KPVALIGN(vm,sz,al,func) (SETLOCAL((vm)->data), func((vm),(sz),(al)) )
126#define KPVFREE(vm,d,func) (SETLOCAL((vm)->data), func((vm),(d)) )
127#define KPVRESIZE(vm,d,sz,mv,func) (SETLOCAL((vm)->data), func((vm),(d),(sz),(mv)) )
128#define KPVADDR(vm,addr,func) (SETLOCAL((vm)->data), func((vm),(addr)) )
129/* ALIGN is chosen so that a block can store all primitive types.
130** It should also be a multiple of ALIGNB==(BITS+1) so the size field
131** of Block_t will always be 0%(BITS+1) as noted above.
132** Of paramount importance is the ALIGNA macro below. If the local compile
133** environment is strange enough that the below method does not calculate
134** ALIGNA right, then the code below should be commented out and ALIGNA
135** redefined to the appropriate requirement.
136*/
137 union _align_u {
138 char c, *cp;
139 int i, *ip;
140 long l, *lp;
141 double d, *dp, ***dppp[8];
142 size_t s, *sp;
143 void (*fn) (void);
144 union _align_u *align;
145 Head_t *head;
146 Body_t *body;
147 Block_t *block;
148 Vmuchar_t a[ALIGNB];
149#if _long_double
150 long double ld, *ldp;
151#endif
152 };
153 struct _a_s {
154 char c;
155 union _align_u a;
156 };
157#define ALIGNA (sizeof(struct _a_s) - sizeof(union _align_u))
158 struct _align_s {
159 char data[MULTIPLE(ALIGNA, ALIGNB)];
160 };
161#define ALIGN sizeof(struct _align_s)
162
163/* make sure that the head of a block is a multiple of ALIGN */
164 struct _head_s {
165 union {
166 Seg_t *seg; /* the containing segment */
167 Block_t *link; /* possible link list usage */
168 Pfobj_t *pf; /* profile structure pointer */
169 char *file; /* for file name in Vmdebug */
170 } seg;
171 union {
172 size_t size; /* size of data area in bytes */
173 Block_t *link; /* possible link list usage */
174 int line; /* for line number in Vmdebug */
175 } size;
176 };
177#define HEADSIZE ROUND(sizeof(struct _head_s),ALIGN)
178 union _head_u {
179 Vmuchar_t data[HEADSIZE]; /* to standardize size */
180 struct _head_s head;
181 };
182
183/* now make sure that the body of a block is a multiple of ALIGN */
184 struct _body_s {
185 Block_t *link; /* next in link list */
186 Block_t *left; /* left child in free tree */
187 Block_t *right; /* right child in free tree */
188 Block_t **self; /* self pointer when free */
189 };
190#define BODYSIZE ROUND(sizeof(struct _body_s),ALIGN)
191 union _body_u {
192 Vmuchar_t data[BODYSIZE]; /* to standardize size */
193 struct _body_s body;
194 };
195
196/* After all the songs and dances, we should now have:
197** sizeof(Head_t)%ALIGN == 0
198** sizeof(Body_t)%ALIGN == 0
199** and sizeof(Block_t) = sizeof(Head_t)+sizeof(Body_t)
200*/
201 struct _block_s {
202 Head_t head;
203 Body_t body;
204 };
205
206/* requirements for smallest block type */
207 struct _tiny_s {
208 Block_t *link;
209 Block_t *self;
210 };
211#define TINYSIZE ROUND(sizeof(struct _tiny_s),ALIGN)
212#define S_TINY 7 /* # of tiny blocks */
213#define MAXTINY (S_TINY*ALIGN + TINYSIZE)
214#define TLEFT(b) ((b)->head.head.seg.link) /* instead of LEFT */
215#define TINIEST(b) (SIZE(b) == TINYSIZE) /* this type uses TLEFT */
216
217#define DIV(x,y) ((y) == 8 ? ((x)>>3) : (x)/(y) )
218#define INDEX(s) DIV((s)-TINYSIZE,ALIGN)
219
220/* number of small block types that can be cached after free */
221#define S_CACHE 7
222#define MAXCACHE (S_CACHE*ALIGN + TINYSIZE)
223#define C_INDEX(s) (s < MAXCACHE ? INDEX(s) : S_CACHE)
224
225#define TINY(vd) ((vd)->tiny)
226#define CACHE(vd) ((vd)->cache)
227
228 typedef struct _vmdata_s {
229 int mode; /* current mode for region */
230 size_t incr; /* allocate in multiple of this */
231 size_t pool; /* size of an elt in a Vmpool region */
232 Seg_t *seg; /* list of segments */
233 Block_t *free; /* most recent free block */
234 Block_t *wild; /* wilderness block */
235 Block_t *root; /* root of free tree */
236 Block_t *tiny[S_TINY]; /* small blocks */
237 Block_t *cache[S_CACHE + 1]; /* delayed free blocks */
238 } Vmdata_t;
239
240/* private parts of Vmalloc_t */
241#define _VM_PRIVATE_ \
242 Vmdisc_t* disc; /* discipline to get space */ \
243 Vmdata_t* data; /* the real region data */ \
244 Vmalloc_t* next; /* linked list of regions */
245
246#include "vmalloc.h"
247
248/* we don't use these here and they interfere with some local names */
249#undef malloc
250#undef free
251#undef realloc
252
253/* segment structure */
254 struct _seg_s {
255 Vmalloc_t *vm; /* the region that holds this */
256 Seg_t *next; /* next segment */
257 void *addr; /* starting segment address */
258 size_t extent; /* extent of segment */
259 Vmuchar_t *baddr; /* bottom of usable memory */
260 size_t size; /* allocable size */
261 Block_t *free; /* recent free blocks */
262 Block_t *last; /* Vmlast last-allocated block */
263 };
264
265/* starting block of a segment */
266#define SEGBLOCK(s) ((Block_t*)(((Vmuchar_t*)(s)) + ROUND(sizeof(Seg_t),ALIGN)))
267
268/* short-hands for block data */
269#define SEG(b) ((b)->head.head.seg.seg)
270#define SEGLINK(b) ((b)->head.head.seg.link)
271#define SIZE(b) ((b)->head.head.size.size)
272#define SIZELINK(b) ((b)->head.head.size.link)
273#define LINK(b) ((b)->body.body.link)
274#define LEFT(b) ((b)->body.body.left)
275#define RIGHT(b) ((b)->body.body.right)
276#define VM(b) (SEG(b)->vm)
277
278#define DATA(b) ((void*)((b)->body.data) )
279#define BLOCK(d) ((Block_t*)((char*)(d) - sizeof(Head_t)) )
280#define SELF(b) ((Block_t**)((b)->body.data + SIZE(b) - sizeof(Block_t*)) )
281#define LAST(b) (*((Block_t**)(((char*)(b)) - sizeof(Block_t*)) ) )
282#define NEXT(b) ((Block_t*)((b)->body.data + SIZE(b)) )
283
284/* functions to manipulate link lists of elts of the same size */
285#define SETLINK(b) (RIGHT(b) = (b) )
286#define ISLINK(b) (RIGHT(b) == (b) )
287#define UNLINK(vd,b,i,t) \
288 ((((t) = LINK(b)) ? (LEFT(t) = LEFT(b)) : NIL(Block_t*) ), \
289 (((t) = LEFT(b)) ? (LINK(t) = LINK(b)) : (TINY(vd)[i] = LINK(b)) ) )
290
291/* delete a block from a link list or the free tree.
292** The test in the below macro is worth scratching your head a bit.
293** Even though tiny blocks (size < BODYSIZE) are kept in separate lists,
294** only the TINIEST ones require TLEFT(b) for the back link. Since this
295** destroys the SEG(b) pointer, it must be carefully restored in bestsearch().
296** Other tiny blocks have enough space to use the usual LEFT(b).
297** In this case, I have also carefully arranged so that RIGHT(b) and
298** SELF(b) can be overlapped and the test ISLINK() will go through.
299*/
300#define REMOVE(vd,b,i,t,func) \
301 ((!TINIEST(b) && ISLINK(b)) ? UNLINK((vd),(b),(i),(t)) : \
302 func((vd),SIZE(b),(b)) )
303
304/* see if a block is the wilderness block */
305#define SEGWILD(b) (((b)->body.data+SIZE(b)+sizeof(Head_t)) >= SEG(b)->baddr)
306#define VMWILD(vd,b) (((b)->body.data+SIZE(b)+sizeof(Head_t)) >= vd->seg->baddr)
307
308#define VMFILELINE(vm,f,l) ((f) = (vm)->file, (vm)->file = NIL(char*), \
309 (l) = (vm)->line, (vm)->line = 0 )
310
311/* The lay-out of a Vmprofile block is this:
312** seg_ size ----data---- _pf_ size
313** _________ ____________ _________
314** seg_, size: header required by Vmbest.
315** data: actual data block.
316** _pf_: pointer to the corresponding Pfobj_t struct
317** size: the true size of the block.
318** So each block requires an extra Head_t.
319*/
320#define PF_EXTRA sizeof(Head_t)
321#define PFDATA(d) ((Head_t*)((Vmuchar_t*)(d)+(SIZE(BLOCK(d))&~BITS)-sizeof(Head_t)) )
322#define PFOBJ(d) (PFDATA(d)->head.seg.pf)
323#define PFSIZE(d) (PFDATA(d)->head.size.size)
324
325/* The lay-out of a block allocated by Vmdebug is this:
326** seg_ size file size seg_ magi ----data---- --magi-- magi line
327** --------- --------- --------- ------------ -------- ---------
328** seg_,size: header required by Vmbest management.
329** file: the file where it was created.
330** size: the true byte count of the block
331** seg_: should be the same as the previous seg_.
332** This allows the function vmregion() to work.
333** magi: magic bytes to detect overwrites.
334** data: the actual data block.
335** magi: more magic bytes.
336** line: the line number in the file where it was created.
337** So for each allocated block, we'll need 3 extra Head_t.
338*/
339
340/* convenient macros for accessing the above fields */
341#define DB_HEAD (2*sizeof(Head_t))
342#define DB_TAIL (2*sizeof(Head_t))
343#define DB_EXTRA (DB_HEAD+DB_TAIL)
344#define DBBLOCK(d) ((Block_t*)((Vmuchar_t*)(d) - 3*sizeof(Head_t)) )
345#define DBBSIZE(d) (SIZE(DBBLOCK(d)) & ~BITS)
346#define DBSEG(d) (((Head_t*)((Vmuchar_t*)(d) - sizeof(Head_t)))->head.seg.seg )
347#define DBSIZE(d) (((Head_t*)((Vmuchar_t*)(d) - 2*sizeof(Head_t)))->head.size.size )
348#define DBFILE(d) (((Head_t*)((Vmuchar_t*)(d) - 2*sizeof(Head_t)))->head.seg.file )
349#define DBLN(d) (((Head_t*)((Vmuchar_t*)DBBLOCK(d)+DBBSIZE(d)))->head.size.line )
350#define DBLINE(d) (DBLN(d) < 0 ? -DBLN(d) : DBLN(d))
351
352/* forward/backward translation for addresses between Vmbest and Vmdebug */
353#define DB2BEST(d) ((Vmuchar_t*)(d) - 2*sizeof(Head_t))
354#define DB2DEBUG(b) ((Vmuchar_t*)(b) + 2*sizeof(Head_t))
355
356/* set file and line number, note that DBLN > 0 so that DBISBAD will work */
357#define DBSETFL(d,f,l) (DBFILE(d) = (f), DBLN(d) = (f) ? (l) : 1)
358
359/* set and test the state of known to be corrupted */
360#define DBSETBAD(d) (DBLN(d) > 0 ? (DBLN(d) = -DBLN(d)) : -1)
361#define DBISBAD(d) (DBLN(d) <= 0)
362
363#define DB_MAGIC 0255 /* 10101101 */
364
365/* compute the bounds of the magic areas */
366#define DBHEAD(d,begp,endp) \
367 (((begp) = (Vmuchar_t*)(&DBSEG(d)) + sizeof(Seg_t*)), ((endp) = (d)) )
368#define DBTAIL(d,begp,endp) \
369 (((begp) = (Vmuchar_t*)(d)+DBSIZE(d)), ((endp) = (Vmuchar_t*)(&DBLN(d))) )
370
371/* clear and copy functions */
372#define INTCOPY(to,fr,n) \
373 switch(n/sizeof(int)) \
374 { default: memcpy((void*)to,(void*)fr,n); break; \
375 case 7: *to++ = *fr++; \
376 case 6: *to++ = *fr++; \
377 case 5: *to++ = *fr++; \
378 case 4: *to++ = *fr++; \
379 case 3: *to++ = *fr++; \
380 case 2: *to++ = *fr++; \
381 case 1: *to++ = *fr++; \
382 }
383#define INTZERO(d,n) \
384 switch(n/sizeof(int)) \
385 { default: memset((void*)d,0,n); break; \
386 case 7: *d++ = 0; \
387 case 6: *d++ = 0; \
388 case 5: *d++ = 0; \
389 case 4: *d++ = 0; \
390 case 3: *d++ = 0; \
391 case 2: *d++ = 0; \
392 case 1: *d++ = 0; \
393 }
394
395/* external symbols for internal use by vmalloc */
396 typedef Block_t *(*Vmsearch_f) (Vmdata_t *, size_t, Block_t *);
397 typedef struct _vmextern_ {
398 Block_t *(*vm_extend) (Vmalloc_t *, size_t, Vmsearch_f);
399 int (*vm_truncate) (Vmalloc_t *, Seg_t *, size_t, int);
400 size_t vm_pagesize;
401 char *(*vm_strcpy) (char *, char *, int);
402 char *(*vm_itoa) (Vmulong_t, int);
403 void (*vm_trace) (Vmalloc_t *,
404 Vmuchar_t *, Vmuchar_t *, size_t, size_t);
405 void (*vm_pfclose) (Vmalloc_t *);
406 } Vmextern_t;
407
408#define _Vmextend (_Vmextern.vm_extend)
409#define _Vmtruncate (_Vmextern.vm_truncate)
410#define _Vmpagesize (_Vmextern.vm_pagesize)
411#define _Vmstrcpy (_Vmextern.vm_strcpy)
412#define _Vmitoa (_Vmextern.vm_itoa)
413#define _Vmtrace (_Vmextern.vm_trace)
414#define _Vmpfclose (_Vmextern.vm_pfclose)
415
416 extern Vmextern_t _Vmextern;
417
418 extern size_t getpagesize(void);
419
420#ifndef _WIN32
421 extern void abort(void);
422 extern ssize_t write(int, const void *, size_t);
423#endif
424
425#ifndef cfree
426#define cfree ______cfree
427#endif
428#include <stdlib.h>
429#undef cfree
430#include <string.h>
431
432/* for malloc.c */
433#ifndef _WIN32
434 extern int creat(const char *, int);
435 extern int close(int);
436#endif
437 extern int getpid(void);
438
439/* for vmexit.c */
440#ifndef _WIN32
441 extern int onexit(void(*)(void));
442 extern void _exit(int);
443#endif
444 extern void _cleanup(void);
445
446/* for vmdcsbrk.c */
447#if !defined(_WIN32)
448 extern Vmuchar_t *sbrk(ssize_t);
449#endif
450
451#endif /* _VMHDR_H */
452#ifdef __cplusplus
453}
454#endif
455