1 /*********************************************************************** 2 * * 3 * This software is part of the ast package * 4 * Copyright (c) 1985-2012 AT&T Intellectual Property * 5 * and is licensed under the * 6 * Eclipse Public License, Version 1.0 * 7 * by AT&T Intellectual Property * 8 * * 9 * A copy of the License is available at * 10 * http://www.eclipse.org/org/documents/epl-v10.html * 11 * (with md5 checksum b35adb5213ca9657e911e9befb180842) * 12 * * 13 * Information and Software Systems Research * 14 * AT&T Research * 15 * Florham Park NJ * 16 * * 17 * Glenn Fowler <gsf@research.att.com> * 18 * David Korn <dgk@research.att.com> * 19 * Phong Vo <kpv@research.att.com> * 20 * * 21 ***********************************************************************/ 22 #ifndef _VMHDR_H 23 #define _VMHDR_H 1 24 #ifndef _BLD_vmalloc 25 #define _BLD_vmalloc 1 26 #endif 27 28 /* Common types, and macros for vmalloc functions. 29 ** 30 ** Written by Kiem-Phong Vo, kpv@research.att.com, 01/16/94. 31 */ 32 33 #ifndef __STD_C /* this is normally in vmalloc.h but it's included late here */ 34 #ifdef __STDC__ 35 #define __STD_C 1 36 #else 37 #if __cplusplus || c_plusplus 38 #define __STD_C 1 39 #else 40 #define __STD_C 0 41 #endif /*__cplusplus*/ 42 #endif /*__STDC__*/ 43 #endif /*__STD_C*/ 44 45 #if _PACKAGE_ast 46 47 #if !_UWIN 48 #define getpagesize ______getpagesize 49 #define _npt_getpagesize 1 50 #define brk ______brk 51 #define sbrk ______sbrk 52 #define _npt_sbrk 1 53 #endif 54 55 #include <ast.h> 56 57 #if _npt_getpagesize 58 #undef getpagesize 59 #endif 60 #if _npt_sbrk 61 #undef brk 62 #undef sbrk 63 #endif 64 65 #else 66 67 #include <ast_common.h> 68 69 #if !_UWIN 70 #define _npt_getpagesize 1 71 #define _npt_sbrk 1 72 #endif 73 74 #undef free 75 #undef malloc 76 #undef realloc 77 78 #endif /*_PACKAGE_ast*/ 79 80 #include "FEATURE/vmalloc" 81 82 #include <aso.h> /* atomic scalor operations */ 83 #include <setjmp.h> /* use the type jmp_buf for alignment */ 84 85 /* extra information needed about methods to get memory from the system */ 86 #if defined(_WIN32) 87 #define _mem_win32 1 /* use the VirtualAlloc interface */ 88 #endif 89 #if !_mem_win32 && !_mem_sbrk && !_mem_mmap_anon && !_mem_mmap_zero 90 #undef _std_malloc 91 #define _std_malloc 1 /* use native malloc/free/realloc */ 92 #endif 93 94 typedef unsigned char Vmuchar_t; 95 typedef unsigned long Vmulong_t; 96 97 typedef union _head_u Head_t; 98 typedef union _body_u Body_t; 99 typedef struct _block_s Block_t; 100 typedef struct _seg_s Seg_t; 101 typedef struct _pfobj_s Pfobj_t; 102 103 #define NIL(t) ((t)0) 104 #define reg register 105 #if __STD_C 106 #define NOTUSED(x) (void)(x) 107 #else 108 #define NOTUSED(x) (&x,1) 109 #endif 110 111 112 /* convert an address to an integral value */ 113 #define VLONG(addr) ((Vmulong_t)((Vmuchar_t*)((Vmulong_t)addr) - (Vmuchar_t*)0) ) 114 115 /* Round x up to a multiple of y. ROUND2 does powers-of-2 and ROUNDX does others */ 116 #define ROUND2(x,y) (((x) + ((y)-1)) & ~((y)-1)) 117 #define ROUNDX(x,y) ((((x) + ((y)-1)) / (y)) * (y)) 118 #define ROUND(x,y) (((y)&((y)-1)) ? ROUNDX((x),(y)) : ROUND2((x),(y)) ) 119 120 /* compute a value that is a common multiple of x and y */ 121 #define MULTIPLE(x,y) ((x)%(y) == 0 ? (x) : (y)%(x) == 0 ? (y) : (y)*(x)) 122 123 #define VM_abort 0x0001 /* abort() on assertion failure */ 124 #define VM_break 0x0002 /* try sbrk() block allocator first */ 125 #define VM_check 0x0004 /* enable detailed checks */ 126 #define VM_free 0x0008 /* disable addfreelist() */ 127 #define VM_keep 0x0010 /* disable free() */ 128 #define VM_mmap 0x0020 /* try mmap() block allocator first */ 129 130 #if _UWIN 131 #include <ast_windows.h> 132 #endif 133 134 #ifndef DEBUG 135 #ifdef _BLD_DEBUG 136 #define DEBUG 1 137 #endif /*_BLD_DEBUG*/ 138 #endif /*DEBUG*/ 139 #if DEBUG 140 extern void _vmmessage _ARG_((const char*, long, const char*, long)); 141 #define MESSAGE(s) _vmmessage(__FILE__,__LINE__,s,0) 142 #define ABORT() (_Vmassert & VM_abort) 143 #define CHECK() (_Vmassert & VM_check) 144 #define ASSERT(p) ((p) ? 0 : (MESSAGE("Assertion failed"), ABORT() ? (abort(),0) : 0)) 145 #define COUNT(n) ((n) += 1) 146 #else 147 #define ABORT() (0) 148 #define ASSERT(p) 149 #define CHECK() (0) 150 #define COUNT(n) 151 #define MESSAGE(s) (0) 152 #endif /*DEBUG*/ 153 154 #define VMPAGESIZE 8192 155 #if _lib_getpagesize 156 #define GETPAGESIZE(x) ((x) ? (x) : ((x)=getpagesize()) ) 157 #else 158 #define GETPAGESIZE(x) ((x) = VMPAGESIZE) 159 #endif 160 161 /* Blocks are allocated such that their sizes are 0%(BITS+1) 162 ** This frees up enough low order bits to store state information 163 */ 164 #define BUSY (01) /* block is busy */ 165 #define PFREE (02) /* preceding block is free */ 166 #define JUNK (04) /* marked as freed but not yet processed */ 167 #define BITS (07) /* (BUSY|PFREE|JUNK) */ 168 #define ALIGNB (8) /* size must be a multiple of BITS+1 */ 169 170 #define ISBITS(w) ((w) & BITS) 171 #define CLRBITS(w) ((w) &= ~BITS) 172 #define CPYBITS(w,f) ((w) |= ((f)&BITS) ) 173 174 #define ISBUSY(w) ((w) & BUSY) 175 #define SETBUSY(w) ((w) |= BUSY) 176 #define CLRBUSY(w) ((w) &= ~BUSY) 177 178 #define ISPFREE(w) ((w) & PFREE) 179 #define SETPFREE(w) ((w) |= PFREE) 180 #define CLRPFREE(w) ((w) &= ~PFREE) 181 182 #define ISJUNK(w) ((w) & JUNK) 183 #define SETJUNK(w) ((w) |= JUNK) 184 #define CLRJUNK(w) ((w) &= ~JUNK) 185 186 #define OFFSET(t,e) ((size_t)(&(((t*)0)->e)) ) 187 188 #define VMETHOD(vd) ((vd)->mode&VM_METHODS) 189 190 /* lock and unlock regions during concurrent accesses */ 191 #define SETLOCK(vm,l) ((l) ? 0 : _vmlock((vm), 1) ) 192 #define CLRLOCK(vm,l) ((l) ? 0 : _vmlock((vm), 0) ) 193 194 /* local calls */ 195 #define KPVALLOC(vm,sz,func) (func((vm),(sz),1) ) 196 #define KPVRESIZE(vm,dt,sz,mv,func) (func((vm),(dt),(sz),(mv),1) ) 197 #define KPVFREE(vm,dt,func) (func((vm),(dt),1) ) 198 #define KPVADDR(vm,addr,func) (func((vm),(addr),1) ) 199 #define KPVSIZE(vm,addr,func) (func((vm),(addr),1) ) 200 #define KPVCOMPACT(vm,func) (func((vm),1) ) 201 #define KPVALIGN(vm,sz,al,func) (func((vm),(sz),(al),1) ) 202 203 /* ALIGN is chosen so that a block can store all primitive types. 204 ** It should also be a multiple of ALIGNB==(BITS+1) so the size field 205 ** of Block_t will always be 0%(BITS+1) as noted above. 206 ** Of paramount importance is the ALIGNA macro below. If the local compile 207 ** environment is strange enough that the below method does not calculate 208 ** ALIGNA right, then the code below should be commented out and ALIGNA 209 ** redefined to the appropriate requirement. 210 */ 211 union _align_u 212 { char c, *cp; 213 int i, *ip; 214 long l, *lp; 215 double d, *dp, ***dppp[8]; 216 size_t s, *sp; 217 void(* fn)(); 218 union _align_u* align; 219 Head_t* head; 220 Body_t* body; 221 Block_t* block; 222 Vmuchar_t a[ALIGNB]; 223 _ast_fltmax_t ld, *ldp; 224 jmp_buf jmp; 225 }; 226 struct _a_s 227 { char c; 228 union _align_u a; 229 }; 230 #define ALIGNA (sizeof(struct _a_s) - sizeof(union _align_u)) 231 struct _align_s 232 { char data[MULTIPLE(ALIGNA,ALIGNB)]; 233 }; 234 #undef ALIGN /* bsd sys/param.h defines this */ 235 #define ALIGN sizeof(struct _align_s) 236 237 /* make sure that the head of a block is a multiple of ALIGN */ 238 struct _head_s 239 { union 240 { Seg_t* seg; /* the containing segment */ 241 Block_t* link; /* possible link list usage */ 242 Pfobj_t* pf; /* profile structure pointer */ 243 char* file; /* for file name in Vmdebug */ 244 } seg; 245 union 246 { size_t size; /* size of data area in bytes */ 247 Block_t* link; /* possible link list usage */ 248 int line; /* for line number in Vmdebug */ 249 } size; 250 }; 251 #define HEADSIZE ROUND(sizeof(struct _head_s),ALIGN) 252 union _head_u 253 { Vmuchar_t data[HEADSIZE]; /* to standardize size */ 254 struct _head_s head; 255 }; 256 257 /* now make sure that the body of a block is a multiple of ALIGN */ 258 struct _body_s 259 { Block_t* link; /* next in link list */ 260 Block_t* left; /* left child in free tree */ 261 Block_t* right; /* right child in free tree */ 262 Block_t** self; /* self pointer when free */ 263 }; 264 #define BODYSIZE ROUND(sizeof(struct _body_s),ALIGN) 265 266 union _body_u 267 { Vmuchar_t data[BODYSIZE]; /* to standardize size */ 268 struct _body_s body; 269 Block_t* self[1]; 270 }; 271 272 /* After all the songs and dances, we should now have: 273 ** sizeof(Head_t)%ALIGN == 0 274 ** sizeof(Body_t)%ALIGN == 0 275 ** and sizeof(Block_t) = sizeof(Head_t)+sizeof(Body_t) 276 */ 277 struct _block_s 278 { Head_t head; 279 Body_t body; 280 }; 281 282 /* requirements for smallest block type */ 283 struct _tiny_s 284 { Block_t* link; 285 Block_t* self; 286 }; 287 #define TINYSIZE ROUND(sizeof(struct _tiny_s),ALIGN) 288 #define S_TINY 1 /* # of tiny blocks */ 289 #define MAXTINY (S_TINY*ALIGN + TINYSIZE) 290 #define TLEFT(b) ((b)->head.head.seg.link) /* instead of LEFT */ 291 #define TINIEST(b) (SIZE(b) == TINYSIZE) /* this type uses TLEFT */ 292 293 #define DIV(x,y) ((y) == 8 ? ((x)>>3) : (x)/(y) ) 294 #define INDEX(s) DIV((s)-TINYSIZE,ALIGN) 295 296 /* small block types kept in separate caches for quick allocation */ 297 #define S_CACHE 6 /* # of types of small blocks to be cached */ 298 #define N_CACHE 32 /* on allocation, create this many at a time */ 299 #define MAXCACHE (S_CACHE*ALIGN + TINYSIZE) 300 #define C_INDEX(s) (s < MAXCACHE ? INDEX(s) : S_CACHE) 301 302 #define TINY(vd) ((vd)->tiny) 303 #define CACHE(vd) ((vd)->cache) 304 305 struct _vmdata_s /* core region data - could be in shared/persistent memory */ 306 { unsigned int lock; /* lock status */ 307 int mode; /* current mode for region */ 308 size_t incr; /* allocate in multiple of this */ 309 size_t pool; /* size of an elt in a Vmpool region */ 310 Seg_t* seg; /* list of segments */ 311 Block_t* free; /* most recent free block */ 312 Block_t* wild; /* wilderness block */ 313 Block_t* root; /* root of free tree */ 314 Block_t* tiny[S_TINY]; /* small blocks */ 315 Block_t* cache[S_CACHE+1]; /* delayed free blocks */ 316 }; 317 318 #include "vmalloc.h" 319 320 #if !_PACKAGE_ast 321 /* we don't use these here and they interfere with some local names */ 322 #undef malloc 323 #undef free 324 #undef realloc 325 #endif 326 327 /* segment structure */ 328 struct _seg_s 329 { Vmdata_t* vmdt; /* the data region holding this */ 330 Seg_t* next; /* next segment */ 331 Void_t* addr; /* starting segment address */ 332 size_t extent; /* extent of segment */ 333 Vmuchar_t* baddr; /* bottom of usable memory */ 334 size_t size; /* allocable size */ 335 Block_t* free; /* recent free blocks */ 336 Block_t* last; /* Vmlast last-allocated block */ 337 }; 338 339 /* starting block of a segment */ 340 #define SEGBLOCK(s) ((Block_t*)(((Vmuchar_t*)(s)) + ROUND(sizeof(Seg_t),ALIGN))) 341 342 /* short-hands for block data */ 343 #define SEG(b) ((b)->head.head.seg.seg) 344 #define SEGLINK(b) ((b)->head.head.seg.link) 345 #define SIZE(b) ((b)->head.head.size.size) 346 #define SIZELINK(b) ((b)->head.head.size.link) 347 #define LINK(b) ((b)->body.body.link) 348 #define LEFT(b) ((b)->body.body.left) 349 #define RIGHT(b) ((b)->body.body.right) 350 351 #define DATA(b) ((Void_t*)((b)->body.data) ) 352 #define BLOCK(d) ((Block_t*)((char*)(d) - sizeof(Head_t)) ) 353 #define SELF(b) (b)->body.self[SIZE(b)/sizeof(Block_t*)-1] 354 #define LAST(b) (*((Block_t**)(((char*)(b)) - sizeof(Block_t*)) ) ) 355 #define NEXT(b) ((Block_t*)((b)->body.data + SIZE(b)) ) 356 357 /* functions to manipulate link lists of elts of the same size */ 358 #define SETLINK(b) (RIGHT(b) = (b) ) 359 #define ISLINK(b) (RIGHT(b) == (b) ) 360 #define UNLINK(vd,b,i,t) \ 361 ((((t) = LINK(b)) ? (LEFT(t) = LEFT(b)) : NIL(Block_t*) ), \ 362 (((t) = LEFT(b)) ? (LINK(t) = LINK(b)) : (TINY(vd)[i] = LINK(b)) ) ) 363 364 /* delete a block from a link list or the free tree. 365 ** The test in the below macro is worth scratching your head a bit. 366 ** Even though tiny blocks (size < BODYSIZE) are kept in separate lists, 367 ** only the TINIEST ones require TLEFT(b) for the back link. Since this 368 ** destroys the SEG(b) pointer, it must be carefully restored in bestsearch(). 369 ** Other tiny blocks have enough space to use the usual LEFT(b). 370 ** In this case, I have also carefully arranged so that RIGHT(b) and 371 ** SELF(b) can be overlapped and the test ISLINK() will go through. 372 */ 373 #define REMOVE(vd,b,i,t,func) \ 374 ((!TINIEST(b) && ISLINK(b)) ? UNLINK((vd),(b),(i),(t)) : \ 375 func((vd),SIZE(b),(b)) ) 376 377 /* see if a block is the wilderness block */ 378 #define SEGWILD(b) (((b)->body.data+SIZE(b)+sizeof(Head_t)) >= SEG(b)->baddr) 379 #define VMWILD(vd,b) (((b)->body.data+SIZE(b)+sizeof(Head_t)) >= vd->seg->baddr) 380 381 #define VMFLF(vm,fi,ln,fn) ((fi) = (vm)->file, (vm)->file = NIL(char*), \ 382 (ln) = (vm)->line, (vm)->line = 0 , \ 383 (fn) = (vm)->func, (vm)->func = NIL(Void_t*) ) 384 385 /* The lay-out of a Vmprofile block is this: 386 ** seg_ size ----data---- _pf_ size 387 ** _________ ____________ _________ 388 ** seg_, size: header required by Vmbest. 389 ** data: actual data block. 390 ** _pf_: pointer to the corresponding Pfobj_t struct 391 ** size: the true size of the block. 392 ** So each block requires an extra Head_t. 393 */ 394 #define PF_EXTRA sizeof(Head_t) 395 #define PFDATA(d) ((Head_t*)((Vmuchar_t*)(d)+(SIZE(BLOCK(d))&~BITS)-sizeof(Head_t)) ) 396 #define PFOBJ(d) (PFDATA(d)->head.seg.pf) 397 #define PFSIZE(d) (PFDATA(d)->head.size.size) 398 399 /* The lay-out of a block allocated by Vmdebug is this: 400 ** seg_ size file size seg_ magi ----data---- --magi-- magi line 401 ** --------- --------- --------- ------------ -------- --------- 402 ** seg_,size: header required by Vmbest management. 403 ** file: the file where it was created. 404 ** size: the true byte count of the block 405 ** seg_: should be the same as the previous seg_. 406 ** This allows the function vmregion() to work. 407 ** magi: magic bytes to detect overwrites. 408 ** data: the actual data block. 409 ** magi: more magic bytes. 410 ** line: the line number in the file where it was created. 411 ** So for each allocated block, we'll need 3 extra Head_t. 412 */ 413 414 /* convenient macros for accessing the above fields */ 415 #define DB_HEAD (2*sizeof(Head_t)) 416 #define DB_TAIL (2*sizeof(Head_t)) 417 #define DB_EXTRA (DB_HEAD+DB_TAIL) 418 #define DBBLOCK(d) ((Block_t*)((Vmuchar_t*)(d) - 3*sizeof(Head_t)) ) 419 #define DBBSIZE(d) (SIZE(DBBLOCK(d)) & ~BITS) 420 #define DBSEG(d) (((Head_t*)((Vmuchar_t*)(d) - sizeof(Head_t)))->head.seg.seg ) 421 #define DBSIZE(d) (((Head_t*)((Vmuchar_t*)(d) - 2*sizeof(Head_t)))->head.size.size ) 422 #define DBFILE(d) (((Head_t*)((Vmuchar_t*)(d) - 2*sizeof(Head_t)))->head.seg.file ) 423 #define DBLN(d) (((Head_t*)((Vmuchar_t*)DBBLOCK(d)+DBBSIZE(d)))->head.size.line ) 424 #define DBLINE(d) (DBLN(d) < 0 ? -DBLN(d) : DBLN(d)) 425 426 /* forward/backward translation for addresses between Vmbest and Vmdebug */ 427 #define DB2BEST(d) ((Vmuchar_t*)(d) - 2*sizeof(Head_t)) 428 #define DB2DEBUG(b) ((Vmuchar_t*)(b) + 2*sizeof(Head_t)) 429 430 /* set file and line number, note that DBLN > 0 so that DBISBAD will work */ 431 #define DBSETFL(d,f,l) (DBFILE(d) = (f), DBLN(d) = (f) ? (l) : 1) 432 433 /* set and test the state of known to be corrupted */ 434 #define DBSETBAD(d) (DBLN(d) > 0 ? (DBLN(d) = -DBLN(d)) : -1) 435 #define DBISBAD(d) (DBLN(d) <= 0) 436 437 #define DB_MAGIC 0255 /* 10101101 */ 438 439 /* compute the bounds of the magic areas */ 440 #define DBHEAD(d,begp,endp) \ 441 (((begp) = (Vmuchar_t*)(&DBSEG(d)) + sizeof(Seg_t*)), ((endp) = (d)) ) 442 #define DBTAIL(d,begp,endp) \ 443 (((begp) = (Vmuchar_t*)(d)+DBSIZE(d)), ((endp) = (Vmuchar_t*)(&DBLN(d))) ) 444 445 446 /* external symbols for use inside vmalloc only */ 447 typedef Block_t* (*Vmsearch_f)_ARG_((Vmdata_t*, size_t, Block_t*)); 448 typedef struct _vmextern_s 449 { Block_t* (*vm_extend)_ARG_((Vmalloc_t*, size_t, Vmsearch_f )); 450 ssize_t (*vm_truncate)_ARG_((Vmalloc_t*, Seg_t*, size_t, int)); 451 size_t vm_pagesize; 452 char* (*vm_strcpy)_ARG_((char*, const char*, int)); 453 char* (*vm_itoa)_ARG_((Vmulong_t, int)); 454 void (*vm_trace)_ARG_((Vmalloc_t*, 455 Vmuchar_t*, Vmuchar_t*, size_t, size_t)); 456 void (*vm_pfclose)_ARG_((Vmalloc_t*)); 457 unsigned int vm_lock; 458 int vm_assert; 459 int vm_options; 460 } Vmextern_t; 461 462 #define _Vmextend (_Vmextern.vm_extend) 463 #define _Vmtruncate (_Vmextern.vm_truncate) 464 #define _Vmpagesize (_Vmextern.vm_pagesize) 465 #define _Vmstrcpy (_Vmextern.vm_strcpy) 466 #define _Vmitoa (_Vmextern.vm_itoa) 467 #define _Vmtrace (_Vmextern.vm_trace) 468 #define _Vmpfclose (_Vmextern.vm_pfclose) 469 #define _Vmlock (_Vmextern.vm_lock) 470 #define _Vmassert (_Vmextern.vm_assert) 471 #define _Vmoptions (_Vmextern.vm_options) 472 473 #define VMOPTIONS() do { if (!_Vmoptions) { _vmoptions(); } } while (0) 474 475 extern int _vmbestcheck _ARG_((Vmdata_t*, Block_t*)); 476 extern int _vmfd _ARG_((int)); 477 extern int _vmlock _ARG_((Vmalloc_t*, int)); 478 extern void _vmoptions _ARG_((void)); 479 480 _BEGIN_EXTERNS_ 481 482 extern Vmextern_t _Vmextern; 483 484 #if _PACKAGE_ast 485 486 #if _npt_getpagesize 487 extern int getpagesize _ARG_((void)); 488 #endif 489 #if _npt_sbrk 490 extern int brk _ARG_(( void* )); 491 extern Void_t* sbrk _ARG_(( ssize_t )); 492 #endif 493 494 #else 495 496 #if _hdr_unistd 497 #include <unistd.h> 498 #else 499 extern void abort _ARG_(( void )); 500 extern ssize_t write _ARG_(( int, const void*, size_t )); 501 extern int getpagesize _ARG_((void)); 502 extern Void_t* sbrk _ARG_((ssize_t)); 503 #endif 504 505 #if !__STDC__ && !_hdr_stdlib 506 extern size_t strlen _ARG_(( const char* )); 507 extern char* strcpy _ARG_(( char*, const char* )); 508 extern int strcmp _ARG_(( const char*, const char* )); 509 extern int atexit _ARG_(( void(*)(void) )); 510 extern char* getenv _ARG_(( const char* )); 511 extern Void_t* memcpy _ARG_(( Void_t*, const Void_t*, size_t )); 512 extern Void_t* memset _ARG_(( Void_t*, int, size_t )); 513 #else 514 #include <stdlib.h> 515 #include <string.h> 516 #endif 517 518 /* for vmexit.c */ 519 extern int onexit _ARG_(( void(*)(void) )); 520 extern void _exit _ARG_(( int )); 521 extern void _cleanup _ARG_(( void )); 522 523 #endif /*_PACKAGE_ast*/ 524 525 /* for vmdcsbrk.c */ 526 #if !_typ_ssize_t 527 typedef int ssize_t; 528 #endif 529 530 _END_EXTERNS_ 531 532 #endif /* _VMHDR_H */ 533