[BACK]Return to gc_hdrs.h CVS log [TXT][DIR] Up to [local] / OpenXM_contrib / gc / include / private

Annotation of OpenXM_contrib/gc/include/private/gc_hdrs.h, Revision 1.1.1.3

1.1       maekawa     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.
1.1.1.3 ! maekawa    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.
1.1       maekawa    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:
1.1.1.3 ! maekawa    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:
1.1       maekawa   180: typedef struct bi {
                    181:     hdr * index[BOTTOM_SZ];
                    182:        /*
                    183:         * The bottom level index contains one of three kinds of values:
1.1.1.2   maekawa   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.
1.1       maekawa   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    */
1.1.1.2   maekawa   192:                                /* ascending order...           */
                    193:     struct bi * desc_link;     /* ... and in descending order. */
1.1       maekawa   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))
1.1.1.3 ! maekawa   232: #   define GET_HDR2(p1, hhdr1, p2, hhdr2) \
        !           233:        { GET_HDR(p1, hhdr1); GET_HDR(p2, hhdr2); }
1.1       maekawa   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))
1.1.1.3 ! maekawa   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:        }
1.1       maekawa   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>