← Back to branch summary

~ubuntu-branches/ubuntu/quantal/libgc/quantal

« back to all changes in this revision

Viewing changes to include/private/gc_pmark.h

  • Committer: Bazaar Package Importer
  • Author(s): Christoph Egger
  • Date: 2011-02-19 12:19:56 UTC
  • mfrom: (1.3.2 upstream) (0.1.5 experimental)
  • mto: This revision was merged to the branch mainline in revision 14.
  • Revision ID: james.westby@ubuntu.com-20110219121956-67rb69xlt5nud3v2
Tags: 1:7.1-5
Upload to unstable

Show diffs side-by-side

added added

removed removed

Lines of Context:
include/private/gc_pmark.h
54
54
        (((word)1 << (WORDSZ - GC_DS_TAG_BITS - GC_LOG_MAX_MARK_PROCS)) - 1)
55
55
 
56
56
 
57
 
extern word GC_n_mark_procs;
 
57
extern unsigned GC_n_mark_procs;
58
58
 
59
59
/* Number of mark stack entries to discard on overflow. */
60
60
#define GC_MARK_STACK_DISCARDS (INITIAL_MARK_STACK_SIZE/8)
61
61
 
62
62
typedef struct GC_ms_entry {
63
 
    GC_word * mse_start;   /* First word of object */
 
63
    ptr_t mse_start;   /* First word of object, word aligned  */
64
64
    GC_word mse_descr;  /* Descriptor; low order two bits are tags,     */
65
 
                        /* identifying the upper 30 bits as one of the  */
66
 
                        /* following:                                   */
 
65
                        /* as described in gc_mark.h.                   */
67
66
} mse;
68
67
 
69
 
extern word GC_mark_stack_size;
 
68
extern size_t GC_mark_stack_size;
70
69
 
71
70
extern mse * GC_mark_stack_limit;
72
71
 
73
72
#ifdef PARALLEL_MARK
74
 
  extern mse * VOLATILE GC_mark_stack_top;
 
73
  extern mse * volatile GC_mark_stack_top;
75
74
#else
76
75
  extern mse * GC_mark_stack_top;
77
76
#endif
117
116
                                        /* once it returns to 0, it     */
118
117
                                        /* stays zero for the cycle.    */
119
118
    /* GC_mark_stack_top is also protected by mark lock.        */
120
 
    extern mse * VOLATILE GC_first_nonempty;
121
 
                                        /* Lowest entry on mark stack   */
122
 
                                        /* that may be nonempty.        */
123
 
                                        /* Updated only by initiating   */
124
 
                                        /* thread.                      */
125
119
    /*
126
120
     * GC_notify_all_marker() is used when GC_help_wanted is first set,
127
121
     * when the last helper becomes inactive,
134
128
 
135
129
/* Return a pointer to within 1st page of object.       */
136
130
/* Set *new_hdr_p to corr. hdr.                         */
137
 
#ifdef __STDC__
138
 
  ptr_t GC_find_start(ptr_t current, hdr *hhdr, hdr **new_hdr_p);
139
 
#else
140
 
  ptr_t GC_find_start();
141
 
#endif
142
 
 
143
 
mse * GC_signal_mark_stack_overflow GC_PROTO((mse *msp));
144
 
 
145
 
# ifdef GATHERSTATS
146
 
#   define ADD_TO_ATOMIC(sz) GC_atomic_in_use += (sz)
147
 
#   define ADD_TO_COMPOSITE(sz) GC_composite_in_use += (sz)
148
 
# else
149
 
#   define ADD_TO_ATOMIC(sz)
150
 
#   define ADD_TO_COMPOSITE(sz)
151
 
# endif
 
131
ptr_t GC_find_start(ptr_t current, hdr *hhdr, hdr **new_hdr_p);
 
132
 
 
133
mse * GC_signal_mark_stack_overflow(mse *msp);
152
134
 
153
135
/* Push the object obj with corresponding heap block header hhdr onto   */
154
136
/* the mark stack.                                                      */
156
138
{ \
157
139
    register word _descr = (hhdr) -> hb_descr; \
158
140
        \
159
 
    if (_descr == 0) { \
160
 
        ADD_TO_ATOMIC((hhdr) -> hb_sz); \
161
 
    } else { \
162
 
        ADD_TO_COMPOSITE((hhdr) -> hb_sz); \
 
141
    if (_descr != 0) { \
163
142
        mark_stack_top++; \
164
143
        if (mark_stack_top >= mark_stack_limit) { \
165
144
          mark_stack_top = GC_signal_mark_stack_overflow(mark_stack_top); \
177
156
                       source, exit_label) \
178
157
{ \
179
158
    hdr * my_hhdr; \
180
 
    ptr_t my_current = current; \
181
 
 \
182
 
    GET_HDR(my_current, my_hhdr); \
183
 
    if (IS_FORWARDING_ADDR_OR_NIL(my_hhdr)) { \
184
 
         hdr * new_hdr = GC_invalid_header; \
185
 
         my_current = GC_find_start(my_current, my_hhdr, &new_hdr); \
186
 
         my_hhdr = new_hdr; \
187
 
    } \
188
 
    PUSH_CONTENTS_HDR(my_current, mark_stack_top, mark_stack_limit, \
189
 
                  source, exit_label, my_hhdr); \
190
 
exit_label: ; \
191
 
}
192
 
 
193
 
/* As above, but use header cache for header lookup.    */
194
 
# define HC_PUSH_CONTENTS(current, mark_stack_top, mark_stack_limit, \
195
 
                       source, exit_label) \
196
 
{ \
197
 
    hdr * my_hhdr; \
198
 
    ptr_t my_current = current; \
199
 
 \
200
 
    HC_GET_HDR(my_current, my_hhdr, source); \
201
 
    PUSH_CONTENTS_HDR(my_current, mark_stack_top, mark_stack_limit, \
202
 
                  source, exit_label, my_hhdr); \
 
159
 \
 
160
    HC_GET_HDR(current, my_hhdr, source, exit_label); \
 
161
    PUSH_CONTENTS_HDR(current, mark_stack_top, mark_stack_limit, \
 
162
                  source, exit_label, my_hhdr, TRUE);   \
203
163
exit_label: ; \
204
164
}
205
165
 
206
166
/* Set mark bit, exit if it was already set.    */
207
167
 
208
 
# ifdef USE_MARK_BYTES
209
 
    /* Unlike the mark bit case, there is a race here, and we may set   */
210
 
    /* the bit twice in the concurrent case.  This can result in the    */
211
 
    /* object being pushed twice.  But that's only a performance issue. */
212
 
#   define SET_MARK_BIT_EXIT_IF_SET(hhdr,displ,exit_label) \
213
 
    { \
214
 
        register VOLATILE char * mark_byte_addr = \
215
 
                                hhdr -> hb_marks + ((displ) >> 1); \
216
 
        register char mark_byte = *mark_byte_addr; \
 
168
# ifdef USE_MARK_BITS
 
169
#   ifdef PARALLEL_MARK
 
170
      /* The following may fail to exit even if the bit was already set.    */
 
171
      /* For our uses, that's benign:                                       */
 
172
#     define OR_WORD_EXIT_IF_SET(addr, bits, exit_label) \
 
173
        { \
 
174
          if (!(*(addr) & (mask))) { \
 
175
            AO_or((AO_t *)(addr), (mask); \
 
176
          } else { \
 
177
            goto label; \
 
178
          } \
 
179
        }
 
180
#   else
 
181
#     define OR_WORD_EXIT_IF_SET(addr, bits, exit_label) \
 
182
        { \
 
183
           word old = *(addr); \
 
184
           word my_bits = (bits); \
 
185
           if (old & my_bits) goto exit_label; \
 
186
           *(addr) = (old | my_bits); \
 
187
         }
 
188
#   endif /* !PARALLEL_MARK */
 
189
#   define SET_MARK_BIT_EXIT_IF_SET(hhdr,bit_no,exit_label) \
 
190
    { \
 
191
        word * mark_word_addr = hhdr -> hb_marks + divWORDSZ(bit_no); \
 
192
      \
 
193
        OR_WORD_EXIT_IF_SET(mark_word_addr, (word)1 << modWORDSZ(bit_no), \
 
194
                            exit_label); \
 
195
    }
 
196
# endif
 
197
 
 
198
 
 
199
#ifdef USE_MARK_BYTES
 
200
# if defined(I386) && defined(__GNUC__)
 
201
#  define LONG_MULT(hprod, lprod, x, y) { \
 
202
        asm("mull %2" : "=a"(lprod), "=d"(hprod) : "g"(y), "0"(x)); \
 
203
   }
 
204
# else /* No in-line X86 assembly code */
 
205
#  define LONG_MULT(hprod, lprod, x, y) { \
 
206
        unsigned long long prod = (unsigned long long)x \
 
207
                                  * (unsigned long long)y; \
 
208
        hprod = prod >> 32;  \
 
209
        lprod = (unsigned32)prod;  \
 
210
   }
 
211
# endif
 
212
 
 
213
  /* There is a race here, and we may set                               */
 
214
  /* the bit twice in the concurrent case.  This can result in the      */
 
215
  /* object being pushed twice.  But that's only a performance issue.   */
 
216
# define SET_MARK_BIT_EXIT_IF_SET(hhdr,bit_no,exit_label) \
 
217
    { \
 
218
        char * mark_byte_addr = (char *)hhdr -> hb_marks + (bit_no); \
 
219
        char mark_byte = *mark_byte_addr; \
217
220
          \
218
221
        if (mark_byte) goto exit_label; \
219
222
        *mark_byte_addr = 1;  \
220
223
    } 
221
 
# else
222
 
#   define SET_MARK_BIT_EXIT_IF_SET(hhdr,displ,exit_label) \
223
 
    { \
224
 
        register word * mark_word_addr = hhdr -> hb_marks + divWORDSZ(displ); \
225
 
          \
226
 
        OR_WORD_EXIT_IF_SET(mark_word_addr, (word)1 << modWORDSZ(displ), \
227
 
                            exit_label); \
228
 
    } 
229
 
# endif /* USE_MARK_BYTES */
230
 
 
 
224
#endif /* USE_MARK_BYTES */
 
225
 
 
226
#ifdef PARALLEL_MARK
 
227
# define INCR_MARKS(hhdr) \
 
228
        AO_store(&(hhdr -> hb_n_marks), AO_load(&(hhdr -> hb_n_marks))+1);
 
229
#else
 
230
# define INCR_MARKS(hhdr) ++(hhdr -> hb_n_marks)
 
231
#endif
 
232
 
 
233
#ifdef ENABLE_TRACE
 
234
# define TRACE(source, cmd) \
 
235
        if (GC_trace_addr != 0 && (ptr_t)(source) == GC_trace_addr) cmd
 
236
# define TRACE_TARGET(target, cmd) \
 
237
        if (GC_trace_addr != 0 && (target) == *(ptr_t *)GC_trace_addr) cmd
 
238
#else
 
239
# define TRACE(source, cmd)
 
240
# define TRACE_TARGET(source, cmd)
 
241
#endif
231
242
/* If the mark bit corresponding to current is not set, set it, and     */
232
 
/* push the contents of the object on the mark stack.  For a small      */
233
 
/* object we assume that current is the (possibly interior) pointer     */
234
 
/* to the object.  For large objects we assume that current points      */
235
 
/* to somewhere inside the first page of the object.  If                */
236
 
/* GC_all_interior_pointers is set, it may have been previously         */
237
 
/* adjusted to make that true.                                          */
238
 
# define PUSH_CONTENTS_HDR(current, mark_stack_top, mark_stack_limit, \
239
 
                           source, exit_label, hhdr) \
240
 
{ \
241
 
    int displ;  /* Displacement in block; first bytes, then words */ \
242
 
    int map_entry; \
243
 
    \
244
 
    displ = HBLKDISPL(current); \
245
 
    map_entry = MAP_ENTRY((hhdr -> hb_map), displ); \
246
 
    displ = BYTES_TO_WORDS(displ); \
247
 
    if (map_entry > CPP_MAX_OFFSET) { \
248
 
        if (map_entry == OFFSET_TOO_BIG) { \
249
 
          map_entry = displ % (hhdr -> hb_sz); \
250
 
          displ -= map_entry; \
251
 
          if (displ + (hhdr -> hb_sz) > BYTES_TO_WORDS(HBLKSIZE) \
252
 
              && displ != 0) { \
253
 
            GC_ADD_TO_BLACK_LIST_NORMAL((word)current, source); \
254
 
            goto exit_label; \
255
 
          } \
256
 
        } else { \
257
 
          GC_ADD_TO_BLACK_LIST_NORMAL((word)current, source); goto exit_label; \
258
 
        } \
259
 
    } else { \
260
 
        displ -= map_entry; \
261
 
    } \
262
 
    GC_ASSERT(displ >= 0 && displ < MARK_BITS_PER_HBLK); \
263
 
    SET_MARK_BIT_EXIT_IF_SET(hhdr, displ, exit_label); \
264
 
    GC_STORE_BACK_PTR((ptr_t)source, (ptr_t)HBLKPTR(current) \
265
 
                                      + WORDS_TO_BYTES(displ)); \
266
 
    PUSH_OBJ(((word *)(HBLKPTR(current)) + displ), hhdr, \
267
 
             mark_stack_top, mark_stack_limit) \
268
 
}
 
243
/* push the contents of the object on the mark stack.  Current points   */
 
244
/* to the bginning of the object.  We rely on the fact that the         */
 
245
/* preceding header calculation will succeed for a pointer past the     */
 
246
/* first page of an object, only if it is in fact a valid pointer       */
 
247
/* to the object.  Thus we can omit the otherwise necessary tests       */
 
248
/* here.  Note in particular that the "displ" value is the displacement */
 
249
/* from the beginning of the heap block, which may itself be in the     */
 
250
/* interior of a large object.                                          */
 
251
#ifdef MARK_BIT_PER_GRANULE
 
252
# define PUSH_CONTENTS_HDR(current, mark_stack_top, mark_stack_limit, \
 
253
                           source, exit_label, hhdr, do_offset_check) \
 
254
{ \
 
255
    size_t displ = HBLKDISPL(current); /* Displacement in block; in bytes. */\
 
256
    /* displ is always within range.  If current doesn't point to       */ \
 
257
    /* first block, then we are in the all_interior_pointers case, and  */ \
 
258
    /* it is safe to use any displacement value.                        */ \
 
259
    size_t gran_displ = BYTES_TO_GRANULES(displ); \
 
260
    size_t gran_offset = hhdr -> hb_map[gran_displ];    \
 
261
    size_t byte_offset = displ & (GRANULE_BYTES - 1); \
 
262
    ptr_t base = current;  \
 
263
    /* The following always fails for large block references. */ \
 
264
    if (EXPECT((gran_offset | byte_offset) != 0, FALSE))  { \
 
265
        if (hhdr -> hb_large_block) { \
 
266
          /* gran_offset is bogus.      */ \
 
267
          size_t obj_displ; \
 
268
          base = (ptr_t)(hhdr -> hb_block); \
 
269
          obj_displ = (ptr_t)(current) - base;  \
 
270
          if (obj_displ != displ) { \
 
271
            GC_ASSERT(obj_displ < hhdr -> hb_sz); \
 
272
            /* Must be in all_interior_pointer case, not first block */ \
 
273
            /* already did validity check on cache miss.             */ \
 
274
            ; \
 
275
          } else { \
 
276
            if (do_offset_check && !GC_valid_offsets[obj_displ]) { \
 
277
              GC_ADD_TO_BLACK_LIST_NORMAL(current, source); \
 
278
              goto exit_label; \
 
279
            } \
 
280
          } \
 
281
          gran_displ = 0; \
 
282
          GC_ASSERT(hhdr -> hb_sz > HBLKSIZE || \
 
283
                    hhdr -> hb_block == HBLKPTR(current)); \
 
284
          GC_ASSERT((ptr_t)(hhdr -> hb_block) <= (ptr_t) current); \
 
285
        } else { \
 
286
          size_t obj_displ = GRANULES_TO_BYTES(gran_offset) \
 
287
                             + byte_offset; \
 
288
          if (do_offset_check && !GC_valid_offsets[obj_displ]) { \
 
289
            GC_ADD_TO_BLACK_LIST_NORMAL(current, source); \
 
290
            goto exit_label; \
 
291
          } \
 
292
          gran_displ -= gran_offset; \
 
293
          base -= obj_displ; \
 
294
        } \
 
295
    } \
 
296
    GC_ASSERT(hhdr == GC_find_header(base)); \
 
297
    GC_ASSERT(gran_displ % BYTES_TO_GRANULES(hhdr -> hb_sz) == 0); \
 
298
    TRACE(source, GC_log_printf("GC:%d: passed validity tests\n",GC_gc_no)); \
 
299
    SET_MARK_BIT_EXIT_IF_SET(hhdr, gran_displ, exit_label); \
 
300
    TRACE(source, GC_log_printf("GC:%d: previously unmarked\n",GC_gc_no)); \
 
301
    TRACE_TARGET(base, \
 
302
        GC_log_printf("GC:%d: marking %p from %p instead\n", GC_gc_no, \
 
303
                      base, source)); \
 
304
    INCR_MARKS(hhdr); \
 
305
    GC_STORE_BACK_PTR((ptr_t)source, base); \
 
306
    PUSH_OBJ(base, hhdr, mark_stack_top, mark_stack_limit); \
 
307
}
 
308
#endif /* MARK_BIT_PER_GRANULE */
 
309
 
 
310
#ifdef MARK_BIT_PER_OBJ
 
311
# define PUSH_CONTENTS_HDR(current, mark_stack_top, mark_stack_limit, \
 
312
                           source, exit_label, hhdr, do_offset_check) \
 
313
{ \
 
314
    size_t displ = HBLKDISPL(current); /* Displacement in block; in bytes. */\
 
315
    unsigned32 low_prod, high_prod, offset_fraction; \
 
316
    unsigned32 inv_sz = hhdr -> hb_inv_sz; \
 
317
    ptr_t base = current;  \
 
318
    LONG_MULT(high_prod, low_prod, displ, inv_sz); \
 
319
    /* product is > and within sz_in_bytes of displ * sz_in_bytes * 2**32 */ \
 
320
    if (EXPECT(low_prod >> 16 != 0, FALSE))  { \
 
321
            FIXME: fails if offset is a multiple of HBLKSIZE which becomes 0 \
 
322
        if (inv_sz == LARGE_INV_SZ) { \
 
323
          size_t obj_displ; \
 
324
          base = (ptr_t)(hhdr -> hb_block); \
 
325
          obj_displ = (ptr_t)(current) - base;  \
 
326
          if (obj_displ != displ) { \
 
327
            GC_ASSERT(obj_displ < hhdr -> hb_sz); \
 
328
            /* Must be in all_interior_pointer case, not first block */ \
 
329
            /* already did validity check on cache miss.             */ \
 
330
            ; \
 
331
          } else { \
 
332
            if (do_offset_check && !GC_valid_offsets[obj_displ]) { \
 
333
              GC_ADD_TO_BLACK_LIST_NORMAL(current, source); \
 
334
              goto exit_label; \
 
335
            } \
 
336
          } \
 
337
          GC_ASSERT(hhdr -> hb_sz > HBLKSIZE || \
 
338
                    hhdr -> hb_block == HBLKPTR(current)); \
 
339
          GC_ASSERT((ptr_t)(hhdr -> hb_block) < (ptr_t) current); \
 
340
        } else { \
 
341
          /* Accurate enough if HBLKSIZE <= 2**15.      */ \
 
342
          GC_ASSERT(HBLKSIZE <= (1 << 15)); \
 
343
          size_t obj_displ = (((low_prod >> 16) + 1) * (hhdr -> hb_sz)) >> 16; \
 
344
          if (do_offset_check && !GC_valid_offsets[obj_displ]) { \
 
345
            GC_ADD_TO_BLACK_LIST_NORMAL(current, source); \
 
346
            goto exit_label; \
 
347
          } \
 
348
          base -= obj_displ; \
 
349
        } \
 
350
    } \
 
351
    /* May get here for pointer to start of block not at        */ \
 
352
    /* beginning of object.  If so, it's valid, and we're fine. */ \
 
353
    GC_ASSERT(high_prod >= 0 && high_prod <= HBLK_OBJS(hhdr -> hb_sz)); \
 
354
    TRACE(source, GC_log_printf("GC:%d: passed validity tests\n",GC_gc_no)); \
 
355
    SET_MARK_BIT_EXIT_IF_SET(hhdr, high_prod, exit_label); \
 
356
    TRACE(source, GC_log_printf("GC:%d: previously unmarked\n",GC_gc_no)); \
 
357
    TRACE_TARGET(base, \
 
358
        GC_log_printf("GC:%d: marking %p from %p instead\n", GC_gc_no, \
 
359
                      base, source)); \
 
360
    INCR_MARKS(hhdr); \
 
361
    GC_STORE_BACK_PTR((ptr_t)source, base); \
 
362
    PUSH_OBJ(base, hhdr, mark_stack_top, mark_stack_limit); \
 
363
}
 
364
#endif /* MARK_BIT_PER_OBJ */
269
365
 
270
366
#if defined(PRINT_BLACK_LIST) || defined(KEEP_BACK_PTRS)
271
367
#   define PUSH_ONE_CHECKED_STACK(p, source) \
286
382
# if NEED_FIXUP_POINTER
287
383
    /* Try both the raw version and the fixed up one.   */
288
384
#   define GC_PUSH_ONE_STACK(p, source) \
289
 
      if ((ptr_t)(p) >= (ptr_t)GC_least_plausible_heap_addr     \
290
 
         && (ptr_t)(p) < (ptr_t)GC_greatest_plausible_heap_addr) {      \
 
385
      if ((p) >= (ptr_t)GC_least_plausible_heap_addr    \
 
386
         && (p) < (ptr_t)GC_greatest_plausible_heap_addr) {     \
291
387
         PUSH_ONE_CHECKED_STACK(p, source);     \
292
388
      } \
293
389
      FIXUP_POINTER(p); \
294
 
      if ((ptr_t)(p) >= (ptr_t)GC_least_plausible_heap_addr     \
295
 
         && (ptr_t)(p) < (ptr_t)GC_greatest_plausible_heap_addr) {      \
 
390
      if ((p) >= (ptr_t)GC_least_plausible_heap_addr    \
 
391
         && (p) < (ptr_t)GC_greatest_plausible_heap_addr) {     \
296
392
         PUSH_ONE_CHECKED_STACK(p, source);     \
297
393
      }
298
394
# else /* !NEED_FIXUP_POINTER */
306
402
 
307
403
/*
308
404
 * As above, but interior pointer recognition as for
309
 
 * normal for heap pointers.
 
405
 * normal heap pointers.
310
406
 */
311
407
# define GC_PUSH_ONE_HEAP(p,source) \
312
408
    FIXUP_POINTER(p); \
313
 
    if ((ptr_t)(p) >= (ptr_t)GC_least_plausible_heap_addr       \
314
 
         && (ptr_t)(p) < (ptr_t)GC_greatest_plausible_heap_addr) {      \
 
409
    if ((p) >= (ptr_t)GC_least_plausible_heap_addr      \
 
410
         && (p) < (ptr_t)GC_greatest_plausible_heap_addr) {     \
315
411
            GC_mark_stack_top = GC_mark_and_push( \
316
 
                            (GC_PTR)(p), GC_mark_stack_top, \
317
 
                            GC_mark_stack_limit, (GC_PTR *)(source)); \
 
412
                            (void *)(p), GC_mark_stack_top, \
 
413
                            GC_mark_stack_limit, (void * *)(source)); \
318
414
    }
319
415
 
320
416
/* Mark starting at mark stack entry top (incl.) down to        */
321
417
/* mark stack entry bottom (incl.).  Stop after performing      */
322
418
/* about one page worth of work.  Return the new mark stack     */
323
419
/* top entry.                                                   */
324
 
mse * GC_mark_from GC_PROTO((mse * top, mse * bottom, mse *limit));
 
420
mse * GC_mark_from(mse * top, mse * bottom, mse *limit);
325
421
 
326
422
#define MARK_FROM_MARK_STACK() \
327
423
        GC_mark_stack_top = GC_mark_from(GC_mark_stack_top, \
331
427
/*
332
428
 * Mark from one finalizable object using the specified
333
429
 * mark proc. May not mark the object pointed to by 
334
 
 * real_ptr. That is the job of the caller, if appropriate
 
430
 * real_ptr. That is the job of the caller, if appropriate.
 
431
 * Note that this is called with the mutator running, but
 
432
 * with us holding the allocation lock.  This is safe only if the
 
433
 * mutator needs tha allocation lock to reveal hidden pointers.
 
434
 * FIXME: Why do we need the GC_mark_state test below?
335
435
 */
336
436
# define GC_MARK_FO(real_ptr, mark_proc) \
337
437
{ \