da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/***********************************************************************
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* This software is part of the ast package *
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner* Copyright (c) 1985-2010 AT&T Intellectual Property *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* and is licensed under the *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Common Public License, Version 1.0 *
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin* by AT&T Intellectual Property *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* A copy of the License is available at *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9) *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Information and Software Systems Research *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* AT&T Research *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Florham Park NJ *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Glenn Fowler <gsf@research.att.com> *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* David Korn <dgk@research.att.com> *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Phong Vo <kpv@research.att.com> *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin***********************************************************************/
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* Common types, and macros for vmalloc functions.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** Written by Kiem-Phong Vo, kpv@research.att.com, 01/16/94.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#ifndef __STD_C /* this is normally in vmalloc.h but it's included late here */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#endif /*__cplusplus*/
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#endif /*__STDC__*/
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#endif /*__STD_C*/
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner#define integralof(x) (((char*)(x))-((char*)0))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#endif /*_PACKAGE_ast*/
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* the below macros decide which combinations of sbrk() or mmap() to used */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#if defined(_WIN32)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#if !_mem_win32 && !_mem_sbrk && !_mem_mmap_anon && !_mem_mmap_zero
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define _std_malloc 1 /* do not define malloc/free/realloc */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* convert an address to an integral value */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define VLONG(addr) ((Vmulong_t)((char*)(addr) - (char*)0) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* Round x up to a multiple of y. ROUND2 does powers-of-2 and ROUNDX does others */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define ROUND(x,y) (((y)&((y)-1)) ? ROUNDX((x),(y)) : ROUND2((x),(y)) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* compute a value that is a common multiple of x and y */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define MULTIPLE(x,y) ((x)%(y) == 0 ? (x) : (y)%(x) == 0 ? (y) : (y)*(x))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define VM_abort 0x0002 /* abort() on assertion failure */
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin#define VM_region 0x0004 /* enable region segment checks */
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin#define VM_mmap 0x0010 /* favor mmap allocation */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#endif /*_BLD_DEBUG*/
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#endif /*DEBUG*/
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern void _vmmessage _ARG_((const char*, long, const char*, long));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define ASSERT(p) ((p) ? 0 : (MESSAGE("Assertion failed"), ABORT() ? (abort(),0) : 0))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#endif /*DEBUG*/
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin (((x)=getpagesize()) < VMPAGESIZE ? ((x)=VMPAGESIZE) : (x)) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* Blocks are allocated such that their sizes are 0%(BITS+1)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** This frees up enough low order bits to store state information
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define JUNK (04) /* marked as freed but not yet processed */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define ALIGNB (8) /* size must be a multiple of BITS+1 */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* these bits share the "mode" field with the public bits */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define VM_AGAIN 0010000 /* research the arena for space */
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin#define VM_INUSE 0004000 /* some operation is running */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* test/set/clear lock state */
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin#define SETINUSE(vd,iu) (((iu) = (vd)->mode&VM_INUSE), ((vd)->mode |= VM_INUSE) )
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin#define CLRINUSE(vd,iu) ((iu) ? 0 : ((vd)->mode &= ~VM_INUSE) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define GETLOCAL(vd,l) (((l) = (vd)->mode&VM_LOCAL), ((vd)->mode &= ~VM_LOCAL) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define ISLOCK(vd,l) ((l) ? 0 : ((vd)->mode & VM_LOCK) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define SETLOCK(vd,l) ((l) ? 0 : ((vd)->mode |= VM_LOCK) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define CLRLOCK(vd,l) ((l) ? 0 : ((vd)->mode &= ~VM_LOCK) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* announcing entry/exit of allocation calls */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin (( ((lc)&VM_LOCAL) || !(dc) || !(dc)->exceptf ) ? 0 : \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* local calls */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define KPVALLOC(vm,sz,func) (SETLOCAL((vm)->data), func((vm),(sz)) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define KPVALIGN(vm,sz,al,func) (SETLOCAL((vm)->data), func((vm),(sz),(al)) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define KPVFREE(vm,d,func) (SETLOCAL((vm)->data), func((vm),(d)) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define KPVRESIZE(vm,d,sz,mv,func) (SETLOCAL((vm)->data), func((vm),(d),(sz),(mv)) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define KPVADDR(vm,addr,func) (SETLOCAL((vm)->data), func((vm),(addr)) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define KPVCOMPACT(vm,func) (SETLOCAL((vm)->data), func((vm)) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* ALIGN is chosen so that a block can store all primitive types.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** It should also be a multiple of ALIGNB==(BITS+1) so the size field
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** of Block_t will always be 0%(BITS+1) as noted above.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** Of paramount importance is the ALIGNA macro below. If the local compile
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** environment is strange enough that the below method does not calculate
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** ALIGNA right, then the code below should be commented out and ALIGNA
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** redefined to the appropriate requirement.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define ALIGNA (sizeof(struct _a_s) - sizeof(union _align_u))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* make sure that the head of a block is a multiple of ALIGN */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* now make sure that the body of a block is a multiple of ALIGN */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* After all the songs and dances, we should now have:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** sizeof(Head_t)%ALIGN == 0
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** sizeof(Body_t)%ALIGN == 0
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** and sizeof(Block_t) = sizeof(Head_t)+sizeof(Body_t)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* requirements for smallest block type */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define TLEFT(b) ((b)->head.head.seg.link) /* instead of LEFT */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define TINIEST(b) (SIZE(b) == TINYSIZE) /* this type uses TLEFT */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* small block types kept in separate caches for quick allocation */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define S_CACHE 6 /* # of types of small blocks to be cached */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define N_CACHE 32 /* on allocation, create this many at a time */
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner/* Vmdata_t typedef in <vmalloc.h> */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* we don't use these here and they interfere with some local names */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* segment structure */
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner{ Vmdata_t* vmdt; /* the data region holding this */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* starting block of a segment */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define SEGBLOCK(s) ((Block_t*)(((Vmuchar_t*)(s)) + ROUND(sizeof(Seg_t),ALIGN)))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* short-hands for block data */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define BLOCK(d) ((Block_t*)((char*)(d) - sizeof(Head_t)) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define SELF(b) ((Block_t**)((b)->body.data + SIZE(b) - sizeof(Block_t*)) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define LAST(b) (*((Block_t**)(((char*)(b)) - sizeof(Block_t*)) ) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* functions to manipulate link lists of elts of the same size */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin ((((t) = LINK(b)) ? (LEFT(t) = LEFT(b)) : NIL(Block_t*) ), \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin (((t) = LEFT(b)) ? (LINK(t) = LINK(b)) : (TINY(vd)[i] = LINK(b)) ) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* delete a block from a link list or the free tree.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** The test in the below macro is worth scratching your head a bit.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** Even though tiny blocks (size < BODYSIZE) are kept in separate lists,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** only the TINIEST ones require TLEFT(b) for the back link. Since this
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** destroys the SEG(b) pointer, it must be carefully restored in bestsearch().
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** Other tiny blocks have enough space to use the usual LEFT(b).
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** In this case, I have also carefully arranged so that RIGHT(b) and
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** SELF(b) can be overlapped and the test ISLINK() will go through.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin ((!TINIEST(b) && ISLINK(b)) ? UNLINK((vd),(b),(i),(t)) : \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* see if a block is the wilderness block */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define SEGWILD(b) (((b)->body.data+SIZE(b)+sizeof(Head_t)) >= SEG(b)->baddr)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define VMWILD(vd,b) (((b)->body.data+SIZE(b)+sizeof(Head_t)) >= vd->seg->baddr)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define VMFLF(vm,fi,ln,fn) ((fi) = (vm)->file, (vm)->file = NIL(char*), \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* The lay-out of a Vmprofile block is this:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** seg_ size ----data---- _pf_ size
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** _________ ____________ _________
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** seg_, size: header required by Vmbest.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** data: actual data block.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** _pf_: pointer to the corresponding Pfobj_t struct
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** size: the true size of the block.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** So each block requires an extra Head_t.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define PFDATA(d) ((Head_t*)((Vmuchar_t*)(d)+(SIZE(BLOCK(d))&~BITS)-sizeof(Head_t)) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* The lay-out of a block allocated by Vmdebug is this:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** seg_ size file size seg_ magi ----data---- --magi-- magi line
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** --------- --------- --------- ------------ -------- ---------
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** seg_,size: header required by Vmbest management.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** file: the file where it was created.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** size: the true byte count of the block
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** seg_: should be the same as the previous seg_.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** This allows the function vmregion() to work.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** magi: magic bytes to detect overwrites.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** data: the actual data block.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** magi: more magic bytes.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** line: the line number in the file where it was created.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** So for each allocated block, we'll need 3 extra Head_t.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* convenient macros for accessing the above fields */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DBBLOCK(d) ((Block_t*)((Vmuchar_t*)(d) - 3*sizeof(Head_t)) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DBSEG(d) (((Head_t*)((Vmuchar_t*)(d) - sizeof(Head_t)))->head.seg.seg )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DBSIZE(d) (((Head_t*)((Vmuchar_t*)(d) - 2*sizeof(Head_t)))->head.size.size )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DBFILE(d) (((Head_t*)((Vmuchar_t*)(d) - 2*sizeof(Head_t)))->head.seg.file )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DBLN(d) (((Head_t*)((Vmuchar_t*)DBBLOCK(d)+DBBSIZE(d)))->head.size.line )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* forward/backward translation for addresses between Vmbest and Vmdebug */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DB2DEBUG(b) ((Vmuchar_t*)(b) + 2*sizeof(Head_t))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* set file and line number, note that DBLN > 0 so that DBISBAD will work */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DBSETFL(d,f,l) (DBFILE(d) = (f), DBLN(d) = (f) ? (l) : 1)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* set and test the state of known to be corrupted */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DBSETBAD(d) (DBLN(d) > 0 ? (DBLN(d) = -DBLN(d)) : -1)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* compute the bounds of the magic areas */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin (((begp) = (Vmuchar_t*)(&DBSEG(d)) + sizeof(Seg_t*)), ((endp) = (d)) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin (((begp) = (Vmuchar_t*)(d)+DBSIZE(d)), ((endp) = (Vmuchar_t*)(&DBLN(d))) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* external symbols for internal use by vmalloc */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef Block_t* (*Vmsearch_f)_ARG_((Vmdata_t*, size_t, Block_t*));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{ Block_t* (*vm_extend)_ARG_((Vmalloc_t*, size_t, Vmsearch_f ));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin ssize_t (*vm_truncate)_ARG_((Vmalloc_t*, Seg_t*, size_t, int));
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner#define VMOPTIONS() do { if (!_Vmoptions) { _vmoptions(); } } while (0)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern ssize_t write _ARG_(( int, const void*, size_t ));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern Void_t* memcpy _ARG_(( Void_t*, const Void_t*, size_t ));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#endif /*_PACKAGE_ast*/
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#endif /* _VMHDR_H */