1 /*********************************************************************** 2 * * 3 * This software is part of the ast package * 4 * Copyright (c) 1985-2013 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 <glenn.s.fowler@gmail.com> * 18 * David Korn <dgkorn@gmail.com> * 19 * Phong Vo <phongvo@gmail.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, phongvo@gmail.com, 01/16/94. 31 */ 32 33 #if _PACKAGE_ast 34 35 #if !_UWIN 36 #define getpagesize ______getpagesize 37 #define _npt_getpagesize 1 38 #endif 39 40 #include <ast.h> 41 42 #if _npt_getpagesize 43 #undef getpagesize 44 #endif 45 46 #else 47 48 #include <ast_common.h> 49 #include <sys/types.h> 50 #include <unistd.h> 51 52 #if !_UWIN 53 #define _npt_getpagesize 1 54 #endif 55 56 #ifndef O_cloexec 57 #ifdef O_CLOEXEC 58 #define O_cloexec O_CLOEXEC 59 #else 60 #define O_cloexec 0 61 #endif 62 #endif 63 64 #ifndef F_dupfd_cloexec 65 #ifdef F_DUPFD_CLOEXEC 66 #define F_dupfd_cloexec F_DUPFD_CLOEXEC 67 #else 68 #define F_dupfd_cloexec F_DUPFD 69 #endif 70 #endif 71 72 #undef free 73 #undef malloc 74 #undef realloc 75 76 #endif /*_PACKAGE_ast*/ 77 78 #include "FEATURE/vmalloc" 79 #include "vmalloc.h" 80 81 #include <aso.h> /* atomic scalar operations */ 82 #include <setjmp.h> /* use the type jmp_buf for alignment */ 83 #include <debug.h> /* DEBUG_ASSERT() and friends */ 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 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; /* the header of a memory block */ 98 typedef union _body_u Body_t; /* the body of a memory block when free */ 99 typedef struct _block_s Block_t; /* the type of a memory block */ 100 typedef struct _seg_s Seg_t; /* the type of a raw memory segment */ 101 102 #define NIL(t) ((t)0) 103 #if __STD_C 104 #define NOTUSED(x) (void)(x) 105 #else 106 #define NOTUSED(x) (&x,1) 107 #endif 108 109 /* safe typecasting of scalar values */ 110 #define VMCAST(ty,x) ((ty)((Vmulong_t)(x)) ) 111 112 /* convert an address to an integral value */ 113 #define VMLONG(addr) ((Vmulong_t)(VMCAST(Vmuchar_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 /* _Vmassert flags -- 0x0001..0x8000 reserved for test du jour via TEST=0x.... */ 124 125 #define VM_test 0x0000ffff /* any TEST set */ 126 127 #define VM_abort 0x00010000 /* abort() on assertion failure */ 128 #define VM_check_reg 0x00020000 /* enable region integrity checks */ 129 #define VM_check_seg 0x00040000 /* enable segment availability prechecks*/ 130 #define VM_debug 0x00080000 /* test=debug */ 131 #define VM_keep 0x00100000 /* disable free() */ 132 #define VM_pause 0x00200000 /* pause() on assertion failure */ 133 #define VM_usage 0x00400000 /* usage stats at each getmemory */ 134 #define VM_verbose 0x00800000 /* verbose messages to standard error */ 135 136 #define VM_anon 0x01000000 /* MAP_ANON block allocator */ 137 #define VM_break 0x02000000 /* sbrk() block allocator */ 138 #define VM_native 0x04000000 /* native malloc() block allocator */ 139 #define VM_safe 0x08000000 /* safe MAP_ANON emulation of sbrk() */ 140 #define VM_zero 0x10000000 /* /dev/zero block allocator */ 141 142 #define VM_GETMEMORY (VM_anon|VM_break|VM_native|VM_safe|VM_zero) 143 144 #if _UWIN 145 #include <ast_windows.h> 146 #endif 147 148 #ifndef DEBUG 149 #ifdef _BLD_DEBUG 150 #define DEBUG 1 151 #endif /*_BLD_DEBUG*/ 152 #endif /*DEBUG*/ 153 extern void _vmmessage _ARG_((const char*, long, const char*, long)); 154 #if DEBUG 155 #define MESSAGE(s) _vmmessage(__FILE__,__LINE__, (s), 0) 156 #define PRINT(s,n) _vmmessage(__FILE__,__LINE__, (s), (n)) 157 #define ABORT() ((_Vmassert & VM_abort) ) 158 #define PAUSE() ((_Vmassert & VM_pause) ) 159 #define ASSERT(p) ((p) ? 0 : (MESSAGE("Assertion failed"), \ 160 (ABORT() ? (abort(),0) : PAUSE() ? (pause(),0) : 0)) ) 161 #define COUNT(n) ((n) += 1) 162 #define ACCOUNT(a,b) ((a) += (b)) 163 #define INITMEMORY(m,z) ((m) ? (memset((m), 'i', (z) > 2*MEM_ALIGN ? 2*MEM_ALIGN : (z)), 0) : 0 ) 164 #define SETBUSYMEM(m,z) (memset(((char*)(m))+2*MEM_ALIGN, 'b', (z) <= 2*MEM_ALIGN ? 0 : MEM_ALIGN ) ) 165 #define CHKBUSYMEM(m,z) (memcmp(((char*)(m))+2*MEM_ALIGN, "bbbbbbbb", (z) <= 2*MEM_ALIGN ? 0 : 8) == 0 ? 1 : 0 ) 166 #define SETFREEMEM(m,z) (memset(((char*)(m))+2*MEM_ALIGN, 'f', (z) <= 2*MEM_ALIGN ? 0 : MEM_ALIGN ) ) 167 #define CHKFREEMEM(m,z) (memcmp(((char*)(m))+2*MEM_ALIGN, "ffffffff", (z) <= 2*MEM_ALIGN ? 0 : 8) == 0 ? 1 : 0 ) 168 #define DEBUGDECL(_ty_,_ob_) _ty_ _ob_; 169 #else 170 #define ABORT() (0) 171 #define ASSERT(p) 172 #define COUNT(n) 173 #define MESSAGE(s) (0) 174 #define ACCOUNT(a,b) 175 #define INITMEMORY(m,z) 176 #define SETBUSYMEM(m,z) 177 #define CHKBUSYMEM(m,z) 178 #define SETFREEMEM(m,z) 179 #define CHKFREEMEM(m,z) 180 #define DEBUGDECL(_ty_,_ob_) 181 #endif /*DEBUG*/ 182 183 #define VM_PAGESIZE 8192 /* default assumed page size */ 184 #define VMPAGESIZE() (_Vmpagesize ? _Vmpagesize : _vmpagesize()) 185 #define VMBOUNDARIES() (_Vmmemaddr ? 0 : _vmboundaries()) 186 187 /* get file name and line number recorded in region */ 188 #define VMFLF(vm,fi,ln,fn) ((fi) = (vm)->file, (vm)->file = NIL(char*), \ 189 (ln) = (vm)->line, (vm)->line = 0 , \ 190 (fn) = (vm)->func, (vm)->func = NIL(Void_t*) ) 191 192 /* local recursive calls */ 193 #define KPVALLOC(vm,sz,func) (func((vm),(sz),1) ) 194 #define KPVRESIZE(vm,dt,sz,mv,func) (func((vm),(dt),(sz),(mv),1) ) 195 #define KPVFREE(vm,dt,func) (func((vm),(dt),1) ) 196 #define KPVALIGN(vm,sz,al,func) (func((vm),(sz),(al),1) ) 197 198 /* Block sizes will always be 0%(BITS+1) so the below bits will be free */ 199 #define BUSY (0x1) /* a normal (Vmbest) block is busy */ 200 #define PFREE (0x2) /* preceding normal block is free */ 201 #define SMALL (0x4) /* a segment block is busy */ 202 #define MARK (0x8) /* for marking usage (eg, beststat()) */ 203 #define BITS (BUSY|PFREE|SMALL|MARK) 204 #define ALIGNB (BITS+1) /* to guarantee blksize == 0%(BITS+1) */ 205 206 /* MEM_ALIGN is chosen for three conditions: 207 ** 1. Able to address all primitive types. 208 ** 2. A multiple of ALIGNB==(BITS+1) as discussed above. 209 ** 3. Large enough to cover two pointers. Note that on some machines 210 ** a double value will be that large anyway. 211 ** 212 ** Of paramount importance is the ALIGNA macro below. If the compilation 213 ** environment is too strange to calculate ALIGNA right, then the below 214 ** code should be commented out and ALIGNA redefined as needed. 215 */ 216 union _align_u 217 { char c, *cp; 218 int i, *ip; 219 long l, *lp; 220 double d, *dp; 221 size_t s, *sp; 222 void(* fn)(); 223 union _align_u* align; 224 Head_t* head; 225 Body_t* body; 226 Block_t* block; 227 _ast_fltmax_t ld, *ldp; 228 _ast_intmax_t li, *lip; 229 Vmuchar_t a[ALIGNB]; 230 jmp_buf jmp; 231 }; 232 struct _a_s 233 { char c; 234 union _align_u a; 235 }; 236 struct _two_s 237 { void* one; 238 void* two; 239 }; 240 #define ALIGNA (sizeof(struct _a_s) - sizeof(union _align_u)) 241 #undef MEM_ALIGN /* Blocks will be aligned on both ALIGNA & ALIGNB */ 242 #define ALIGNAB MULTIPLE(ALIGNA,ALIGNB) 243 #define MEM_ALIGN MULTIPLE(ALIGNAB, sizeof(struct _two_s)) 244 245 typedef union _word_u 246 { size_t size; /* to store a size_t */ 247 unsigned int intdt; /* to store an integer */ 248 Void_t* ptrdt; /* to store a pointer */ 249 } Word_t; 250 251 struct _head_s /* a block header has two words */ 252 { Word_t one; 253 Word_t two; 254 }; 255 #define HEADSIZE ROUND(sizeof(struct _head_s), MEM_ALIGN) 256 union _head_u 257 { Vmuchar_t data[HEADSIZE]; /* to standardize size */ 258 struct _head_s head; 259 }; 260 261 struct _body_s /* Note that self is actually at end of block */ 262 { Block_t* link; /* next in link list */ 263 Block_t* rght; /* right child in free tree */ 264 Block_t* left; /* left child in free tree */ 265 Block_t** self; /* self pointer when free */ 266 }; 267 #define BODYSIZE ROUND(sizeof(struct _body_s), MEM_ALIGN) 268 union _body_u 269 { Vmuchar_t data[BODYSIZE]; /* to standardize size */ 270 struct _body_s body; 271 }; 272 273 /* After all the songs and dances, we should now have: 274 ** sizeof(Head_t)%MEM_ALIGN == 0 275 ** sizeof(Body_t)%MEM_ALIGN == 0 276 ** and sizeof(Block_t) = sizeof(Head_t)+sizeof(Body_t) 277 */ 278 struct _block_s 279 { Head_t head; 280 Body_t body; 281 }; 282 283 #define SEG(b) ((b)->head.head.one.ptrdt) /* the containing segment */ 284 #define SIZE(b) ((b)->head.head.two.size) /* field containing block size */ 285 #define BDSZ(b) (SIZE(b) & ~BITS) /* naked size of block */ 286 287 #define PACK(b) ((b)->head.head.one.ptrdt) /* the containing pack */ 288 289 #define LINK(b) ((b)->body.body.link) /* linked list */ 290 #define LEFT(b) ((b)->body.body.left) /* left child in splay tree */ 291 #define RGHT(b) ((b)->body.body.rght) /* right child in splay tree */ 292 293 /* translating between a block and its data area */ 294 #define DATA(b) ((Void_t*)((b)->body.data) ) 295 #define BLOCK(d) ((Block_t*)((Vmuchar_t*)(d) - sizeof(Head_t)) ) 296 297 /* when a block is free, its last word stores a pointer to itself. 298 ** in this way, a block can find its predecessor if the predecessor is free. 299 */ 300 #define SELF(b) ((Block_t**)((b)->body.data + BDSZ(b) - sizeof(Block_t*)) ) 301 #define PREV(b) (*((Block_t**)(((Vmuchar_t*)(b)) - sizeof(Block_t*)) ) ) 302 #define NEXT(b) ((Block_t*)((b)->body.data + BDSZ(b)) ) 303 304 #if _ast_sizeof_pointer == 4 305 #define SMENCODE(i) ((uint32_t)(i) << 24) /* code index of a small block */ 306 #define SMDECODE(i) ((uint32_t)(i) >> 24) /* code index of a small block */ 307 #define SMBITS (BITS | SMENCODE(0xff)) /* bits not related to size */ 308 #else 309 #define SMENCODE(i) ((uint64_t)(i) << 24) /* code index of a small block */ 310 #define SMDECODE(i) ((uint64_t)(i) >> 24) /* code index of a small block */ 311 #define SMBITS (BITS | SMENCODE(0xffff)) /* bits not related to size */ 312 #endif 313 314 #define SMINDEXB(b) (SMDECODE(SIZE(b))) /* get index of a small block */ 315 #define SMBDSZ(b) (SIZE(b) & ~SMBITS) /* size of small block */ 316 #define TRUESIZE(z) ((z) & (((z)&SMALL) ? ~SMBITS : ~BITS) ) 317 #define TRUEBDSZ(b) ((SIZE(b)&SMALL) ? SMBDSZ(b) : BDSZ(b)) 318 #define TRUENEXT(b) ((Block_t*)((b)->body.data + TRUEBDSZ(b)) ) 319 320 /* the sentinel block at the end of a "segment block" */ 321 #define ENDB(sgb) ((Block_t*)((Vmuchar_t*)NEXT(sgb) - sizeof(Head_t)) ) 322 323 /* the start of allocatable memory in a segment */ 324 #define SEGDATA(sg) ((Vmuchar_t*)(sg) + ROUND(sizeof(Seg_t),MEM_ALIGN) ) 325 326 /* testing to see if "sg" is the root segment of a region */ 327 #define SEGROOT(sg) ((Vmuchar_t*)(sg)->vmdt >= (sg)->base && \ 328 (Vmuchar_t*)(sg)->vmdt < (Vmuchar_t*)(sg) ) 329 330 #if !_PACKAGE_ast 331 /* we don't use these here and they interfere with some local names */ 332 #undef malloc 333 #undef free 334 #undef realloc 335 #endif 336 337 typedef struct _vmuser_s Vmuser_t; /* structure for user's data */ 338 struct _vmuser_s 339 { Vmuser_t* next; 340 unsigned int dtid; /* key to identify data item */ 341 ssize_t size; /* size of data area */ 342 Void_t* data; /* user data area */ 343 }; 344 345 struct _seg_s /* a segment of raw memory obtained via Vmdisc_t.memoryf */ 346 { Vmdata_t* vmdt; /* region holding this segment */ 347 Vmuchar_t* base; /* true base address of segment */ 348 size_t size; /* true size of segment */ 349 int iffy; /* should not extend segment */ 350 Block_t* begb; /* starting allocatable memory */ 351 Block_t* endb; /* block at end of memory */ 352 Seg_t* next; /* next segment in linked list */ 353 }; 354 355 struct _free_s /* list of objects locked out by concurrent free() */ 356 { 357 struct _free_s* next; 358 }; 359 typedef struct _free_s Free_t; 360 361 struct Vmdata_s /* Vmdata_t: common region data */ 362 { int mode; /* operation modes */ 363 unsigned int lock; /* lock for segment management */ 364 size_t incr; /* to round memory requests */ 365 Seg_t* seg; /* list of raw memory segments */ 366 Vmuchar_t* segmin; /* min address in all segments */ 367 Vmuchar_t* segmax; /* max address in all segments */ 368 Block_t* free; /* not allocated to method yet */ 369 Vmuser_t* user; /* user data identified by key */ 370 unsigned int ulck; /* lock of user list for update */ 371 unsigned int dlck; /* lock used by Vmdebug */ 372 Free_t* delay; /* delayed free list */ 373 }; 374 375 typedef struct _vmhold_s Vmhold_t; /* to hold open regions */ 376 struct _vmhold_s 377 { Vmhold_t* next; 378 Vmalloc_t* vm; 379 }; 380 381 #define VM_SEGEXTEND (01) /* physically extend memory as needed */ 382 #define VM_SEGALL (02) /* always return entire segment */ 383 384 /* external symbols for use inside vmalloc only */ 385 typedef struct _vmextern_s 386 { Block_t* (*vm_seginit)_ARG_((Vmdata_t*, Seg_t*, Vmuchar_t*, ssize_t, int)); 387 Block_t* (*vm_segalloc)_ARG_((Vmalloc_t*, Block_t*, ssize_t, int )); 388 void (*vm_segfree)_ARG_((Vmalloc_t*, Block_t*)); 389 char* (*vm_strcpy)_ARG_((char*, const char*, int)); 390 char* (*vm_itoa)_ARG_((Vmulong_t, int)); 391 ssize_t (*vm_lcm)_ARG_((ssize_t, ssize_t)); 392 void (*vm_trace)_ARG_((Vmalloc_t*, Vmuchar_t*, Vmuchar_t*, size_t, size_t)); 393 int (*vm_chkmem)_ARG_((Vmuchar_t*, size_t)); 394 Vmuchar_t* vm_memmin; /* address lower abound */ 395 Vmuchar_t* vm_memmax; /* address upper abound */ 396 Vmuchar_t* vm_memaddr; /* vmmaddress() memory */ 397 Vmuchar_t* vm_memsbrk; /* Vmdcsystem's memory */ 398 Vmhold_t* vm_hold; /* list to hold regions */ 399 size_t vm_pagesize; /* OS memory page size */ 400 size_t vm_segsize; /* min segment size */ 401 unsigned int vm_sbrklock; /* lock for sbrkmem */ 402 unsigned int vm_assert; /* options for ASSERT() */ 403 } Vmextern_t; 404 405 #define _Vmseginit (_Vmextern.vm_seginit) 406 #define _Vmsegalloc (_Vmextern.vm_segalloc) 407 #define _Vmsegfree (_Vmextern.vm_segfree) 408 #define _Vmstrcpy (_Vmextern.vm_strcpy) 409 #define _Vmitoa (_Vmextern.vm_itoa) 410 #define _Vmlcm (_Vmextern.vm_lcm) 411 #define _Vmtrace (_Vmextern.vm_trace) 412 #define _Vmchkmem (_Vmextern.vm_chkmem) 413 #define _Vmmemmin (_Vmextern.vm_memmin) 414 #define _Vmmemmax (_Vmextern.vm_memmax) 415 #define _Vmmemaddr (_Vmextern.vm_memaddr) 416 #define _Vmmemsbrk (_Vmextern.vm_memsbrk) 417 #define _Vmpagesize (_Vmextern.vm_pagesize) 418 #define _Vmsegsize (_Vmextern.vm_segsize) 419 #define _Vmsbrklock (_Vmextern.vm_sbrklock) 420 #define _Vmhold (_Vmextern.vm_hold) 421 #define _Vmassert (_Vmextern.vm_assert) 422 423 extern Vmalloc_t* _vmheapinit _ARG_((Vmalloc_t*)); /* initialize Vmheap */ 424 extern int _vmheapbusy _ARG_((void)); /* initializing Vmheap */ 425 extern ssize_t _vmpagesize _ARG_((void)); /* get system page size */ 426 extern int _vmboundaries _ARG_((void)); /* get mem boundaries */ 427 extern Vmalloc_t* _vmopen _ARG_((Vmalloc_t*, Vmdisc_t*, Vmethod_t*, int)); 428 extern void _vmoptions _ARG_((int)); /* VMALLOC_OPTIONS preferences */ 429 extern int _vmstat _ARG_((Vmalloc_t*, Vmstat_t*, size_t)); /* internal vmstat() */ 430 431 _BEGIN_EXTERNS_ 432 433 extern Vmextern_t _Vmextern; 434 435 #if _PACKAGE_ast 436 437 #if _npt_getpagesize 438 extern int getpagesize _ARG_((void)); 439 #endif 440 441 #else 442 443 #if _hdr_unistd 444 #include <unistd.h> 445 #else 446 extern void abort _ARG_(( void )); 447 extern ssize_t write _ARG_(( int, const void*, size_t )); 448 extern int getpagesize _ARG_((void)); 449 extern Void_t* sbrk _ARG_((ssize_t)); 450 #endif 451 452 #if !__STDC__ && !_hdr_stdlib 453 extern size_t strlen _ARG_(( const char* )); 454 extern char* strcpy _ARG_(( char*, const char* )); 455 extern int strcmp _ARG_(( const char*, const char* )); 456 extern int atexit _ARG_(( void(*)(void) )); 457 extern char* getenv _ARG_(( const char* )); 458 extern Void_t* memcpy _ARG_(( Void_t*, const Void_t*, size_t )); 459 extern Void_t* memset _ARG_(( Void_t*, int, size_t )); 460 #else 461 #include <stdlib.h> 462 #include <string.h> 463 #endif 464 465 /* for vmexit.c */ 466 extern int onexit _ARG_(( void(*)(void) )); 467 extern void _exit _ARG_(( int )); 468 extern void _cleanup _ARG_(( void )); 469 470 #endif /*_PACKAGE_ast*/ 471 472 /* for vmdcsbrk.c */ 473 #if !_typ_ssize_t 474 typedef int ssize_t; 475 #endif 476 477 _END_EXTERNS_ 478 479 #endif /* _VMHDR_H */ 480