[BACK]Return to gc_hdrs.h CVS log [TXT][DIR] Up to [local] / OpenXM_contrib2 / asir2000 / gc5.3

Annotation of OpenXM_contrib2/asir2000/gc5.3/gc_hdrs.h, Revision 1.1

1.1     ! noro        1: /*
        !             2:  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
        !             3:  * Copyright (c) 1991-1994 by Xerox Corporation.  All rights reserved.
        !             4:  *
        !             5:  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
        !             6:  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
        !             7:  *
        !             8:  * Permission is hereby granted to use or copy this program
        !             9:  * for any purpose,  provided the above notices are retained on all copies.
        !            10:  * Permission to modify the code and to distribute modified code is granted,
        !            11:  * provided the above notices are retained, and a notice that the code was
        !            12:  * modified is included with the above copyright notice.
        !            13:  */
        !            14: /* Boehm, July 11, 1995 11:54 am PDT */
        !            15: # ifndef GC_HEADERS_H
        !            16: # define GC_HEADERS_H
        !            17: typedef struct hblkhdr hdr;
        !            18:
        !            19: # if CPP_WORDSZ != 32 && CPP_WORDSZ < 36
        !            20:        --> Get a real machine.
        !            21: # endif
        !            22:
        !            23: /*
        !            24:  * The 2 level tree data structure that is used to find block headers.
        !            25:  * If there are more than 32 bits in a pointer, the top level is a hash
        !            26:  * table.
        !            27:  *
        !            28:  * This defines HDR, GET_HDR, and SET_HDR, the main macros used to
        !            29:  * retrieve and set object headers.  We also define some variants to
        !            30:  * retrieve 2 unrelated headers in interleaved fashion.  This
        !            31:  * slightly improves scheduling.
        !            32:  *
        !            33:  * Since 5.0 alpha 5, we can also take advantage of a header lookup
        !            34:  * cache.  This is a locally declared direct mapped cache, used inside
        !            35:  * the marker.  The HC_GET_HDR and HC_GET_HDR2 macros use and maintain this
        !            36:  * cache.  Assuming we get reasonable hit rates, this shaves a few
        !            37:  * memory references from each pointer validation.
        !            38:  */
        !            39:
        !            40: # if CPP_WORDSZ > 32
        !            41: #   define HASH_TL
        !            42: # endif
        !            43:
        !            44: /* Define appropriate out-degrees for each of the two tree levels      */
        !            45: # ifdef SMALL_CONFIG
        !            46: #   define LOG_BOTTOM_SZ 11
        !            47:        /* Keep top index size reasonable with smaller blocks. */
        !            48: # else
        !            49: #   define LOG_BOTTOM_SZ 10
        !            50: # endif
        !            51: # ifndef HASH_TL
        !            52: #   define LOG_TOP_SZ (WORDSZ - LOG_BOTTOM_SZ - LOG_HBLKSIZE)
        !            53: # else
        !            54: #   define LOG_TOP_SZ 11
        !            55: # endif
        !            56: # define TOP_SZ (1 << LOG_TOP_SZ)
        !            57: # define BOTTOM_SZ (1 << LOG_BOTTOM_SZ)
        !            58:
        !            59: #ifndef SMALL_CONFIG
        !            60: # define USE_HDR_CACHE
        !            61: #endif
        !            62:
        !            63: /* #define COUNT_HDR_CACHE_HITS  */
        !            64:
        !            65: extern hdr * GC_invalid_header; /* header for an imaginary block       */
        !            66:                                /* containing no objects.               */
        !            67:
        !            68:
        !            69: /* Check whether p and corresponding hhdr point to long or invalid     */
        !            70: /* object.  If so, advance them        to                                      */
        !            71: /* beginning of        block, or set hhdr to GC_invalid_header.                */
        !            72: #define ADVANCE(p, hhdr, source) \
        !            73:             if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) { \
        !            74:               p = GC_FIND_START(p, hhdr, (word)source); \
        !            75:               if (p == 0) { \
        !            76:                hhdr = GC_invalid_header; \
        !            77:              } else { \
        !            78:                 hhdr = GC_find_header(p); \
        !            79:              } \
        !            80:            }
        !            81:
        !            82: #ifdef USE_HDR_CACHE
        !            83:
        !            84: # ifdef COUNT_HDR_CACHE_HITS
        !            85:     extern word GC_hdr_cache_hits;
        !            86:     extern word GC_hdr_cache_misses;
        !            87: #   define HC_HIT() ++GC_hdr_cache_hits
        !            88: #   define HC_MISS() ++GC_hdr_cache_misses
        !            89: # else
        !            90: #   define HC_HIT()
        !            91: #   define HC_MISS()
        !            92: # endif
        !            93:
        !            94:   typedef struct hce {
        !            95:     word block_addr;   /* right shifted by LOG_HBLKSIZE */
        !            96:     hdr * hce_hdr;
        !            97:   } hdr_cache_entry;
        !            98:
        !            99: # define HDR_CACHE_SIZE 8  /* power of 2 */
        !           100:
        !           101: # define DECLARE_HDR_CACHE \
        !           102:        hdr_cache_entry hdr_cache[HDR_CACHE_SIZE]
        !           103:
        !           104: # define INIT_HDR_CACHE BZERO(hdr_cache, sizeof(hdr_cache));
        !           105:
        !           106: # define HCE(h) hdr_cache + (((word)(h) >> LOG_HBLKSIZE) & (HDR_CACHE_SIZE-1))
        !           107:
        !           108: # define HCE_VALID_FOR(hce,h) ((hce) -> block_addr == \
        !           109:                                ((word)(h) >> LOG_HBLKSIZE))
        !           110:
        !           111: # define HCE_HDR(h) ((hce) -> hce_hdr)
        !           112:
        !           113:
        !           114: /* Analogous to GET_HDR, except that in the case of large objects, it  */
        !           115: /* Returns the header for the object beginning, and updates p.         */
        !           116: /* Returns &GC_bad_header instead of 0.  All of this saves a branch    */
        !           117: /* in the fast path.                                                   */
        !           118: # define HC_GET_HDR(p, hhdr, source) \
        !           119:        { \
        !           120:          hdr_cache_entry * hce = HCE(p); \
        !           121:          if (HCE_VALID_FOR(hce, p)) { \
        !           122:            HC_HIT(); \
        !           123:            hhdr = hce -> hce_hdr; \
        !           124:          } else { \
        !           125:            HC_MISS(); \
        !           126:            GET_HDR(p, hhdr); \
        !           127:            ADVANCE(p, hhdr, source); \
        !           128:            hce -> block_addr = (word)(p) >> LOG_HBLKSIZE; \
        !           129:            hce -> hce_hdr = hhdr; \
        !           130:          } \
        !           131:        }
        !           132:
        !           133: # define HC_GET_HDR2(p1, hhdr1, source1, p2, hhdr2, source2) \
        !           134:        { \
        !           135:          hdr_cache_entry * hce1 = HCE(p1); \
        !           136:          hdr_cache_entry * hce2 = HCE(p2); \
        !           137:          if (HCE_VALID_FOR(hce1, p1)) { \
        !           138:            HC_HIT(); \
        !           139:            hhdr1 = hce1 -> hce_hdr; \
        !           140:          } else { \
        !           141:            HC_MISS(); \
        !           142:            GET_HDR(p1, hhdr1); \
        !           143:            ADVANCE(p1, hhdr1, source1); \
        !           144:            hce1 -> block_addr = (word)(p1) >> LOG_HBLKSIZE; \
        !           145:            hce1 -> hce_hdr = hhdr1; \
        !           146:          } \
        !           147:          if (HCE_VALID_FOR(hce2, p2)) { \
        !           148:            HC_HIT(); \
        !           149:            hhdr2 = hce2 -> hce_hdr; \
        !           150:          } else { \
        !           151:            HC_MISS(); \
        !           152:            GET_HDR(p2, hhdr2); \
        !           153:            ADVANCE(p2, hhdr2, source2); \
        !           154:            hce2 -> block_addr = (word)(p2) >> LOG_HBLKSIZE; \
        !           155:            hce2 -> hce_hdr = hhdr2; \
        !           156:          } \
        !           157:        }
        !           158:
        !           159: #else /* !USE_HDR_CACHE */
        !           160:
        !           161: # define DECLARE_HDR_CACHE
        !           162:
        !           163: # define INIT_HDR_CACHE
        !           164:
        !           165: # define HC_GET_HDR(p, hhdr, source) \
        !           166:        { \
        !           167:          GET_HDR(p, hhdr); \
        !           168:          ADVANCE(p, hhdr, source); \
        !           169:        }
        !           170:
        !           171: # define HC_GET_HDR2(p1, hhdr1, source1, p2, hhdr2, source2) \
        !           172:        { \
        !           173:          GET_HDR2(p1, hhdr1, p2, hhdr2); \
        !           174:          ADVANCE(p1, hhdr1, source1); \
        !           175:          ADVANCE(p2, hhdr2, source2); \
        !           176:        }
        !           177:
        !           178: #endif
        !           179:
        !           180: typedef struct bi {
        !           181:     hdr * index[BOTTOM_SZ];
        !           182:        /*
        !           183:         * The bottom level index contains one of three kinds of values:
        !           184:         * 0 means we're not responsible for this block,
        !           185:         *   or this is a block other than the first one in a free block.
        !           186:         * 1 < (long)X <= MAX_JUMP means the block starts at least
        !           187:         *        X * HBLKSIZE bytes before the current address.
        !           188:         * A valid pointer points to a hdr structure. (The above can't be
        !           189:         * valid pointers due to the GET_MEM return convention.)
        !           190:         */
        !           191:     struct bi * asc_link;      /* All indices are linked in    */
        !           192:                                /* ascending order...           */
        !           193:     struct bi * desc_link;     /* ... and in descending order. */
        !           194:     word key;                  /* high order address bits.     */
        !           195: # ifdef HASH_TL
        !           196:     struct bi * hash_link;     /* Hash chain link.             */
        !           197: # endif
        !           198: } bottom_index;
        !           199:
        !           200: /* extern bottom_index GC_all_nils; - really part of GC_arrays */
        !           201:
        !           202: /* extern bottom_index * GC_top_index []; - really part of GC_arrays */
        !           203:                                /* Each entry points to a bottom_index. */
        !           204:                                /* On a 32 bit machine, it points to    */
        !           205:                                /* the index for a set of high order    */
        !           206:                                /* bits equal to the index.  For longer */
        !           207:                                /* addresses, we hash the high order    */
        !           208:                                /* bits to compute the index in         */
        !           209:                                /* GC_top_index, and each entry points  */
        !           210:                                /* to a hash chain.                     */
        !           211:                                /* The last entry in each chain is      */
        !           212:                                /* GC_all_nils.                         */
        !           213:
        !           214:
        !           215: # define MAX_JUMP (HBLKSIZE - 1)
        !           216:
        !           217: # define HDR_FROM_BI(bi, p) \
        !           218:                ((bi)->index[((word)(p) >> LOG_HBLKSIZE) & (BOTTOM_SZ - 1)])
        !           219: # ifndef HASH_TL
        !           220: #   define BI(p) (GC_top_index \
        !           221:                [(word)(p) >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE)])
        !           222: #   define HDR_INNER(p) HDR_FROM_BI(BI(p),p)
        !           223: #   ifdef SMALL_CONFIG
        !           224: #      define HDR(p) GC_find_header((ptr_t)(p))
        !           225: #   else
        !           226: #      define HDR(p) HDR_INNER(p)
        !           227: #   endif
        !           228: #   define GET_BI(p, bottom_indx) (bottom_indx) = BI(p)
        !           229: #   define GET_HDR(p, hhdr) (hhdr) = HDR(p)
        !           230: #   define SET_HDR(p, hhdr) HDR_INNER(p) = (hhdr)
        !           231: #   define GET_HDR_ADDR(p, ha) (ha) = &(HDR_INNER(p))
        !           232: #   define GET_HDR2(p1, hhdr1, p2, hhdr2) \
        !           233:        { GET_HDR(p1, hhdr1); GET_HDR(p2, hhdr2); }
        !           234: # else /* hash */
        !           235: /*  Hash function for tree top level */
        !           236: #   define TL_HASH(hi) ((hi) & (TOP_SZ - 1))
        !           237: /*  Set bottom_indx to point to the bottom index for address p */
        !           238: #   define GET_BI(p, bottom_indx) \
        !           239:        { \
        !           240:            register word hi = \
        !           241:                (word)(p) >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE); \
        !           242:            register bottom_index * _bi = GC_top_index[TL_HASH(hi)]; \
        !           243:            \
        !           244:            while (_bi -> key != hi && _bi != GC_all_nils) \
        !           245:                _bi = _bi -> hash_link; \
        !           246:            (bottom_indx) = _bi; \
        !           247:        }
        !           248: #   define GET_HDR_ADDR(p, ha) \
        !           249:        { \
        !           250:            register bottom_index * bi; \
        !           251:            \
        !           252:            GET_BI(p, bi);      \
        !           253:            (ha) = &(HDR_FROM_BI(bi, p)); \
        !           254:        }
        !           255: #   define GET_HDR(p, hhdr) { register hdr ** _ha; GET_HDR_ADDR(p, _ha); \
        !           256:                              (hhdr) = *_ha; }
        !           257: #   define SET_HDR(p, hhdr) { register hdr ** _ha; GET_HDR_ADDR(p, _ha); \
        !           258:                              *_ha = (hhdr); }
        !           259: #   define HDR(p) GC_find_header((ptr_t)(p))
        !           260:     /* And some interleaved versions for two pointers at once.         */
        !           261:     /* This hopefully helps scheduling on processors like IA64.                */
        !           262: #   define GET_BI2(p1, bottom_indx1, p2, bottom_indx2) \
        !           263:        { \
        !           264:            register word hi1 = \
        !           265:                (word)(p1) >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE); \
        !           266:            register word hi2 = \
        !           267:                (word)(p2) >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE); \
        !           268:            register bottom_index * _bi1 = GC_top_index[TL_HASH(hi1)]; \
        !           269:            register bottom_index * _bi2 = GC_top_index[TL_HASH(hi2)]; \
        !           270:            \
        !           271:            while (_bi1 -> key != hi1 && _bi1 != GC_all_nils) \
        !           272:                _bi1 = _bi1 -> hash_link; \
        !           273:            while (_bi2 -> key != hi2 && _bi2 != GC_all_nils) \
        !           274:                _bi2 = _bi2 -> hash_link; \
        !           275:            (bottom_indx1) = _bi1; \
        !           276:            (bottom_indx2) = _bi2; \
        !           277:        }
        !           278: #   define GET_HDR_ADDR2(p1, ha1, p2, ha2) \
        !           279:        { \
        !           280:            register bottom_index * bi1; \
        !           281:            register bottom_index * bi2; \
        !           282:            \
        !           283:            GET_BI2(p1, bi1, p2, bi2);  \
        !           284:            (ha1) = &(HDR_FROM_BI(bi1, p1)); \
        !           285:            (ha2) = &(HDR_FROM_BI(bi2, p2)); \
        !           286:        }
        !           287: #   define GET_HDR2(p1, hhdr1, p2, hhdr2) \
        !           288:        { register hdr ** _ha1;  \
        !           289:          register hdr ** _ha2;  \
        !           290:          GET_HDR_ADDR2(p1, _ha1, p2, _ha2); \
        !           291:          (hhdr1) = *_ha1;  \
        !           292:          (hhdr2) = *_ha2;  \
        !           293:        }
        !           294: # endif
        !           295:
        !           296: /* Is the result a forwarding address to someplace closer to the       */
        !           297: /* beginning of the block or NIL?                                      */
        !           298: # define IS_FORWARDING_ADDR_OR_NIL(hhdr) ((unsigned long) (hhdr) <= MAX_JUMP)
        !           299:
        !           300: /* Get an HBLKSIZE aligned address closer to the beginning of the block */
        !           301: /* h.  Assumes hhdr == HDR(h) and IS_FORWARDING_ADDR(hhdr).            */
        !           302: # define FORWARDED_ADDR(h, hhdr) ((struct hblk *)(h) - (unsigned long)(hhdr))
        !           303: # endif /*  GC_HEADERS_H */

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>