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