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

Annotation of OpenXM_contrib2/asir2000/gc5.3/mark.c, Revision 1.1.1.1

1.1       noro        1:
                      2: /*
                      3:  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
                      4:  * Copyright (c) 1991-1995 by Xerox Corporation.  All rights reserved.
                      5:  *
                      6:  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
                      7:  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
                      8:  *
                      9:  * Permission is hereby granted to use or copy this program
                     10:  * for any purpose,  provided the above notices are retained on all copies.
                     11:  * Permission to modify the code and to distribute modified code is granted,
                     12:  * provided the above notices are retained, and a notice that the code was
                     13:  * modified is included with the above copyright notice.
                     14:  *
                     15:  */
                     16:
                     17:
                     18: # include <stdio.h>
                     19: # include "gc_priv.h"
                     20: # include "gc_mark.h"
                     21:
                     22: /* We put this here to minimize the risk of inlining. */
                     23: /*VARARGS*/
                     24: #ifdef __WATCOMC__
                     25:   void GC_noop(void *p, ...) {}
                     26: #else
                     27:   void GC_noop() {}
                     28: #endif
                     29:
                     30: /* Single argument version, robust against whole program analysis. */
                     31: void GC_noop1(x)
                     32: word x;
                     33: {
                     34:     static VOLATILE word sink;
                     35:
                     36:     sink = x;
                     37: }
                     38:
                     39: /* mark_proc GC_mark_procs[MAX_MARK_PROCS] = {0} -- declared in gc_priv.h */
                     40:
                     41: word GC_n_mark_procs = GC_RESERVED_MARK_PROCS;
                     42:
                     43: /* Initialize GC_obj_kinds properly and standard free lists properly.          */
                     44: /* This must be done statically since they may be accessed before      */
                     45: /* GC_init is called.                                                  */
                     46: /* It's done here, since we need to deal with mark descriptors.                */
                     47: struct obj_kind GC_obj_kinds[MAXOBJKINDS] = {
                     48: /* PTRFREE */ { &GC_aobjfreelist[0], 0 /* filled in dynamically */,
                     49:                0 | DS_LENGTH, FALSE, FALSE },
                     50: /* NORMAL  */ { &GC_objfreelist[0], 0,
                     51: #              if defined(ADD_BYTE_AT_END) && ALIGNMENT > DS_TAGS
                     52:                (word)(-ALIGNMENT) | DS_LENGTH,
                     53: #              else
                     54:                0 | DS_LENGTH,
                     55: #              endif
                     56:                TRUE /* add length to descr */, TRUE },
                     57: /* UNCOLLECTABLE */
                     58:              { &GC_uobjfreelist[0], 0,
                     59:                0 | DS_LENGTH, TRUE /* add length to descr */, TRUE },
                     60: # ifdef ATOMIC_UNCOLLECTABLE
                     61:    /* AUNCOLLECTABLE */
                     62:              { &GC_auobjfreelist[0], 0,
                     63:                0 | DS_LENGTH, FALSE /* add length to descr */, FALSE },
                     64: # endif
                     65: # ifdef STUBBORN_ALLOC
                     66: /*STUBBORN*/ { &GC_sobjfreelist[0], 0,
                     67:                0 | DS_LENGTH, TRUE /* add length to descr */, TRUE },
                     68: # endif
                     69: };
                     70:
                     71: # ifdef ATOMIC_UNCOLLECTABLE
                     72: #   ifdef STUBBORN_ALLOC
                     73:       int GC_n_kinds = 5;
                     74: #   else
                     75:       int GC_n_kinds = 4;
                     76: #   endif
                     77: # else
                     78: #   ifdef STUBBORN_ALLOC
                     79:       int GC_n_kinds = 4;
                     80: #   else
                     81:       int GC_n_kinds = 3;
                     82: #   endif
                     83: # endif
                     84:
                     85:
                     86: # ifndef INITIAL_MARK_STACK_SIZE
                     87: #   define INITIAL_MARK_STACK_SIZE (1*HBLKSIZE)
                     88:                /* INITIAL_MARK_STACK_SIZE * sizeof(mse) should be a    */
                     89:                /* multiple of HBLKSIZE.                                */
                     90:                /* The incremental collector actually likes a larger    */
                     91:                /* size, since it want to push all marked dirty objs    */
                     92:                /* before marking anything new.  Currently we let it    */
                     93:                /* grow dynamically.                                    */
                     94: # endif
                     95:
                     96: /*
                     97:  * Limits of stack for GC_mark routine.
                     98:  * All ranges between GC_mark_stack(incl.) and GC_mark_stack_top(incl.) still
                     99:  * need to be marked from.
                    100:  */
                    101:
                    102: word GC_n_rescuing_pages;      /* Number of dirty pages we marked from */
                    103:                                /* excludes ptrfree pages, etc.         */
                    104:
                    105: mse * GC_mark_stack;
                    106:
                    107: word GC_mark_stack_size = 0;
                    108:
                    109: mse * GC_mark_stack_top;
                    110:
                    111: static struct hblk * scan_ptr;
                    112:
                    113: mark_state_t GC_mark_state = MS_NONE;
                    114:
                    115: GC_bool GC_mark_stack_too_small = FALSE;
                    116:
                    117: GC_bool GC_objects_are_marked = FALSE; /* Are there collectable marked */
                    118:                                        /* objects in the heap?         */
                    119:
                    120: /* Is a collection in progress?  Note that this can return true in the */
                    121: /* nonincremental case, if a collection has been abandoned and the     */
                    122: /* mark state is now MS_INVALID.                                       */
                    123: GC_bool GC_collection_in_progress()
                    124: {
                    125:     return(GC_mark_state != MS_NONE);
                    126: }
                    127:
                    128: /* clear all mark bits in the header */
                    129: void GC_clear_hdr_marks(hhdr)
                    130: register hdr * hhdr;
                    131: {
                    132:     BZERO(hhdr -> hb_marks, MARK_BITS_SZ*sizeof(word));
                    133: }
                    134:
                    135: /* Set all mark bits in the header.  Used for uncollectable blocks. */
                    136: void GC_set_hdr_marks(hhdr)
                    137: register hdr * hhdr;
                    138: {
                    139:     register int i;
                    140:
                    141:     for (i = 0; i < MARK_BITS_SZ; ++i) {
                    142:        hhdr -> hb_marks[i] = ONES;
                    143:     }
                    144: }
                    145:
                    146: /*
                    147:  * Clear all mark bits associated with block h.
                    148:  */
                    149: /*ARGSUSED*/
                    150: static void clear_marks_for_block(h, dummy)
                    151: struct hblk *h;
                    152: word dummy;
                    153: {
                    154:     register hdr * hhdr = HDR(h);
                    155:
                    156:     if (IS_UNCOLLECTABLE(hhdr -> hb_obj_kind)) return;
                    157:         /* Mark bit for these is cleared only once the object is       */
                    158:         /* explicitly deallocated.  This either frees the block, or    */
                    159:         /* the bit is cleared once the object is on the free list.     */
                    160:     GC_clear_hdr_marks(hhdr);
                    161: }
                    162:
                    163: /* Slow but general routines for setting/clearing/asking about mark bits */
                    164: void GC_set_mark_bit(p)
                    165: ptr_t p;
                    166: {
                    167:     register struct hblk *h = HBLKPTR(p);
                    168:     register hdr * hhdr = HDR(h);
                    169:     register int word_no = (word *)p - (word *)h;
                    170:
                    171:     set_mark_bit_from_hdr(hhdr, word_no);
                    172: }
                    173:
                    174: void GC_clear_mark_bit(p)
                    175: ptr_t p;
                    176: {
                    177:     register struct hblk *h = HBLKPTR(p);
                    178:     register hdr * hhdr = HDR(h);
                    179:     register int word_no = (word *)p - (word *)h;
                    180:
                    181:     clear_mark_bit_from_hdr(hhdr, word_no);
                    182: }
                    183:
                    184: GC_bool GC_is_marked(p)
                    185: ptr_t p;
                    186: {
                    187:     register struct hblk *h = HBLKPTR(p);
                    188:     register hdr * hhdr = HDR(h);
                    189:     register int word_no = (word *)p - (word *)h;
                    190:
                    191:     return(mark_bit_from_hdr(hhdr, word_no));
                    192: }
                    193:
                    194:
                    195: /*
                    196:  * Clear mark bits in all allocated heap blocks.  This invalidates
                    197:  * the marker invariant, and sets GC_mark_state to reflect this.
                    198:  * (This implicitly starts marking to reestablish the invariant.)
                    199:  */
                    200: void GC_clear_marks()
                    201: {
                    202:     GC_apply_to_all_blocks(clear_marks_for_block, (word)0);
                    203:     GC_objects_are_marked = FALSE;
                    204:     GC_mark_state = MS_INVALID;
                    205:     scan_ptr = 0;
                    206: #   ifdef GATHERSTATS
                    207:        /* Counters reflect currently marked objects: reset here */
                    208:         GC_composite_in_use = 0;
                    209:         GC_atomic_in_use = 0;
                    210: #   endif
                    211:
                    212: }
                    213:
                    214: /* Initiate a garbage collection.  Initiates a full collection if the  */
                    215: /* mark        state is invalid.                                               */
                    216: /*ARGSUSED*/
                    217: void GC_initiate_gc()
                    218: {
                    219:     if (GC_dirty_maintained) GC_read_dirty();
                    220: #   ifdef STUBBORN_ALLOC
                    221:        GC_read_changed();
                    222: #   endif
                    223: #   ifdef CHECKSUMS
                    224:        {
                    225:            extern void GC_check_dirty();
                    226:
                    227:            if (GC_dirty_maintained) GC_check_dirty();
                    228:        }
                    229: #   endif
                    230: #   ifdef GATHERSTATS
                    231:        GC_n_rescuing_pages = 0;
                    232: #   endif
                    233:     if (GC_mark_state == MS_NONE) {
                    234:         GC_mark_state = MS_PUSH_RESCUERS;
                    235:     } else if (GC_mark_state != MS_INVALID) {
                    236:        ABORT("unexpected state");
                    237:     } /* else this is really a full collection, and mark       */
                    238:       /* bits are invalid.                                     */
                    239:     scan_ptr = 0;
                    240: }
                    241:
                    242:
                    243: static void alloc_mark_stack();
                    244:
                    245: /* Perform a small amount of marking.                  */
                    246: /* We try to touch roughly a page of memory.           */
                    247: /* Return TRUE if we just finished a mark phase.       */
                    248: /* Cold_gc_frame is an address inside a GC frame that  */
                    249: /* remains valid until all marking is complete.                */
                    250: /* A zero value indicates that it's OK to miss some    */
                    251: /* register values.                                    */
                    252: GC_bool GC_mark_some(cold_gc_frame)
                    253: ptr_t cold_gc_frame;
                    254: {
                    255: #ifdef MSWIN32
                    256:   /* Windows 98 appears to asynchronously create and remove writable   */
                    257:   /* memory mappings, for reasons we haven't yet understood.  Since    */
                    258:   /* we look for writable regions to determine the root set, we may    */
                    259:   /* try to mark from an address range that disappeared since we       */
                    260:   /* started the collection.  Thus we have to recover from faults here. */
                    261:   /* This code does not appear to be necessary for Windows 95/NT/2000. */
                    262:   /* Note that this code should never generate an incremental GC write */
                    263:   /* fault.                                                            */
                    264:   __try {
                    265: #endif
                    266:     switch(GC_mark_state) {
                    267:        case MS_NONE:
                    268:            return(FALSE);
                    269:
                    270:        case MS_PUSH_RESCUERS:
                    271:            if (GC_mark_stack_top
                    272:                >= GC_mark_stack + GC_mark_stack_size
                    273:                   - INITIAL_MARK_STACK_SIZE/2) {
                    274:                /* Go ahead and mark, even though that might cause us to */
                    275:                /* see more marked dirty objects later on.  Avoid this   */
                    276:                /* in the future.                                        */
                    277:                GC_mark_stack_too_small = TRUE;
                    278:                GC_mark_from_mark_stack();
                    279:                return(FALSE);
                    280:            } else {
                    281:                scan_ptr = GC_push_next_marked_dirty(scan_ptr);
                    282:                if (scan_ptr == 0) {
                    283: #                  ifdef PRINTSTATS
                    284:                        GC_printf1("Marked from %lu dirty pages\n",
                    285:                                   (unsigned long)GC_n_rescuing_pages);
                    286: #                  endif
                    287:                    GC_push_roots(FALSE, cold_gc_frame);
                    288:                    GC_objects_are_marked = TRUE;
                    289:                    if (GC_mark_state != MS_INVALID) {
                    290:                        GC_mark_state = MS_ROOTS_PUSHED;
                    291:                    }
                    292:                }
                    293:            }
                    294:            return(FALSE);
                    295:
                    296:        case MS_PUSH_UNCOLLECTABLE:
                    297:            if (GC_mark_stack_top
                    298:                >= GC_mark_stack + INITIAL_MARK_STACK_SIZE/4) {
                    299:                GC_mark_from_mark_stack();
                    300:                return(FALSE);
                    301:            } else {
                    302:                scan_ptr = GC_push_next_marked_uncollectable(scan_ptr);
                    303:                if (scan_ptr == 0) {
                    304:                    GC_push_roots(TRUE, cold_gc_frame);
                    305:                    GC_objects_are_marked = TRUE;
                    306:                    if (GC_mark_state != MS_INVALID) {
                    307:                        GC_mark_state = MS_ROOTS_PUSHED;
                    308:                    }
                    309:                }
                    310:            }
                    311:            return(FALSE);
                    312:
                    313:        case MS_ROOTS_PUSHED:
                    314:            if (GC_mark_stack_top >= GC_mark_stack) {
                    315:                GC_mark_from_mark_stack();
                    316:                return(FALSE);
                    317:            } else {
                    318:                GC_mark_state = MS_NONE;
                    319:                if (GC_mark_stack_too_small) {
                    320:                    alloc_mark_stack(2*GC_mark_stack_size);
                    321:                }
                    322:                return(TRUE);
                    323:            }
                    324:
                    325:        case MS_INVALID:
                    326:        case MS_PARTIALLY_INVALID:
                    327:            if (!GC_objects_are_marked) {
                    328:                GC_mark_state = MS_PUSH_UNCOLLECTABLE;
                    329:                return(FALSE);
                    330:            }
                    331:            if (GC_mark_stack_top >= GC_mark_stack) {
                    332:                GC_mark_from_mark_stack();
                    333:                return(FALSE);
                    334:            }
                    335:            if (scan_ptr == 0 && GC_mark_state == MS_INVALID) {
                    336:                /* About to start a heap scan for marked objects. */
                    337:                /* Mark stack is empty.  OK to reallocate.        */
                    338:                if (GC_mark_stack_too_small) {
                    339:                    alloc_mark_stack(2*GC_mark_stack_size);
                    340:                }
                    341:                GC_mark_state = MS_PARTIALLY_INVALID;
                    342:            }
                    343:            scan_ptr = GC_push_next_marked(scan_ptr);
                    344:            if (scan_ptr == 0 && GC_mark_state == MS_PARTIALLY_INVALID) {
                    345:                GC_push_roots(TRUE, cold_gc_frame);
                    346:                GC_objects_are_marked = TRUE;
                    347:                if (GC_mark_state != MS_INVALID) {
                    348:                    GC_mark_state = MS_ROOTS_PUSHED;
                    349:                }
                    350:            }
                    351:            return(FALSE);
                    352:        default:
                    353:            ABORT("GC_mark_some: bad state");
                    354:            return(FALSE);
                    355:     }
                    356: #ifdef MSWIN32
                    357:   } __except (GetExceptionCode() == EXCEPTION_ACCESS_VIOLATION ?
                    358:            EXCEPTION_EXECUTE_HANDLER : EXCEPTION_CONTINUE_SEARCH) {
                    359: #   ifdef PRINTSTATS
                    360:        GC_printf0("Caught ACCESS_VIOLATION in marker. "
                    361:                   "Memory mapping disappeared.\n");
                    362: #   endif /* PRINTSTATS */
                    363:     /* We have bad roots on the stack.  Discard mark stack.    */
                    364:     /* Rescan from marked objects.  Redetermine roots.         */
                    365:     GC_invalidate_mark_state();
                    366:     scan_ptr = 0;
                    367:     return FALSE;
                    368:   }
                    369: #endif /* MSWIN32 */
                    370: }
                    371:
                    372:
                    373: GC_bool GC_mark_stack_empty()
                    374: {
                    375:     return(GC_mark_stack_top < GC_mark_stack);
                    376: }
                    377:
                    378: #ifdef PROF_MARKER
                    379:     word GC_prof_array[10];
                    380: #   define PROF(n) GC_prof_array[n]++
                    381: #else
                    382: #   define PROF(n)
                    383: #endif
                    384:
                    385: /* Given a pointer to someplace other than a small object page or the  */
                    386: /* first page of a large object, return a pointer either to the                */
                    387: /* start of the large object or NIL.                                   */
                    388: /* In the latter case black list the address current.                  */
                    389: /* Returns NIL without black listing if current points to a block      */
                    390: /* with IGNORE_OFF_PAGE set.                                           */
                    391: /*ARGSUSED*/
                    392: # ifdef PRINT_BLACK_LIST
                    393:   ptr_t GC_find_start(current, hhdr, source)
                    394:   word source;
                    395: # else
                    396:   ptr_t GC_find_start(current, hhdr)
                    397: # define source 0
                    398: # endif
                    399: register ptr_t current;
                    400: register hdr * hhdr;
                    401: {
                    402: #   ifdef ALL_INTERIOR_POINTERS
                    403:        if (hhdr != 0) {
                    404:            register ptr_t orig = current;
                    405:
                    406:            current = (ptr_t)HBLKPTR(current) + HDR_BYTES;
                    407:            do {
                    408:              current = current - HBLKSIZE*(word)hhdr;
                    409:              hhdr = HDR(current);
                    410:            } while(IS_FORWARDING_ADDR_OR_NIL(hhdr));
                    411:            /* current points to the start of the large object */
                    412:            if (hhdr -> hb_flags & IGNORE_OFF_PAGE) return(0);
                    413:            if ((word *)orig - (word *)current
                    414:                 >= (ptrdiff_t)(hhdr->hb_sz)) {
                    415:                /* Pointer past the end of the block */
                    416:                GC_ADD_TO_BLACK_LIST_NORMAL(orig, source);
                    417:                return(0);
                    418:            }
                    419:            return(current);
                    420:        } else {
                    421:            GC_ADD_TO_BLACK_LIST_NORMAL(current, source);
                    422:            return(0);
                    423:         }
                    424: #   else
                    425:         GC_ADD_TO_BLACK_LIST_NORMAL(current, source);
                    426:         return(0);
                    427: #   endif
                    428: #   undef source
                    429: }
                    430:
                    431: void GC_invalidate_mark_state()
                    432: {
                    433:     GC_mark_state = MS_INVALID;
                    434:     GC_mark_stack_top = GC_mark_stack-1;
                    435: }
                    436:
                    437: mse * GC_signal_mark_stack_overflow(msp)
                    438: mse * msp;
                    439: {
                    440:     GC_mark_state = MS_INVALID;
                    441:     GC_mark_stack_too_small = TRUE;
                    442: #   ifdef PRINTSTATS
                    443:        GC_printf1("Mark stack overflow; current size = %lu entries\n",
                    444:                    GC_mark_stack_size);
                    445: #    endif
                    446:      return(msp-INITIAL_MARK_STACK_SIZE/8);
                    447: }
                    448:
                    449:
                    450: /*
                    451:  * Mark objects pointed to by the regions described by
                    452:  * mark stack entries between GC_mark_stack and GC_mark_stack_top,
                    453:  * inclusive.  Assumes the upper limit of a mark stack entry
                    454:  * is never 0.  A mark stack entry never has size 0.
                    455:  * We try to traverse on the order of a hblk of memory before we return.
                    456:  * Caller is responsible for calling this until the mark stack is empty.
                    457:  * Note that this is the most performance critical routine in the
                    458:  * collector.  Hence it contains all sorts of ugly hacks to speed
                    459:  * things up.  In particular, we avoid procedure calls on the common
                    460:  * path, we take advantage of peculiarities of the mark descriptor
                    461:  * encoding, we optionally maintain a cache for the block address to
                    462:  * header mapping, we prefetch when an object is "grayed", etc.
                    463:  */
                    464: void GC_mark_from_mark_stack()
                    465: {
                    466:   mse * GC_mark_stack_reg = GC_mark_stack;
                    467:   mse * GC_mark_stack_top_reg = GC_mark_stack_top;
                    468:   mse * mark_stack_limit = &(GC_mark_stack[GC_mark_stack_size]);
                    469:   int credit = HBLKSIZE;       /* Remaining credit for marking work    */
                    470:   register word * current_p;   /* Pointer to current candidate ptr.    */
                    471:   register word current;       /* Candidate pointer.                   */
                    472:   register word * limit;       /* (Incl) limit of current candidate    */
                    473:                                /* range                                */
                    474:   register word descr;
                    475:   register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
                    476:   register ptr_t least_ha = GC_least_plausible_heap_addr;
                    477:   DECLARE_HDR_CACHE;
                    478:
                    479: # define SPLIT_RANGE_WORDS 128  /* Must be power of 2.         */
                    480:
                    481:   GC_objects_are_marked = TRUE;
                    482:   INIT_HDR_CACHE;
                    483: # ifdef OS2 /* Use untweaked version to circumvent compiler problem */
                    484:   while (GC_mark_stack_top_reg >= GC_mark_stack_reg && credit >= 0) {
                    485: # else
                    486:   while ((((ptr_t)GC_mark_stack_top_reg - (ptr_t)GC_mark_stack_reg) | credit)
                    487:        >= 0) {
                    488: # endif
                    489:     current_p = GC_mark_stack_top_reg -> mse_start;
                    490:     descr = GC_mark_stack_top_reg -> mse_descr;
                    491:   retry:
                    492:     /* current_p and descr describe the current object.                */
                    493:     /* *GC_mark_stack_top_reg is vacant.                       */
                    494:     /* The following is 0 only for small objects described by a simple */
                    495:     /* length descriptor.  For many applications this is the common    */
                    496:     /* case, so we try to detect it quickly.                           */
                    497:     if (descr & ((~(WORDS_TO_BYTES(SPLIT_RANGE_WORDS) - 1)) | DS_TAGS)) {
                    498:       word tag = descr & DS_TAGS;
                    499:
                    500:       switch(tag) {
                    501:         case DS_LENGTH:
                    502:           /* Large length.                                             */
                    503:           /* Process part of the range to avoid pushing too much on the        */
                    504:           /* stack.                                                    */
                    505:           GC_mark_stack_top_reg -> mse_start =
                    506:                limit = current_p + SPLIT_RANGE_WORDS-1;
                    507:           GC_mark_stack_top_reg -> mse_descr =
                    508:                        descr - WORDS_TO_BYTES(SPLIT_RANGE_WORDS-1);
                    509:           /* Make sure that pointers overlapping the two ranges are    */
                    510:           /* considered.                                               */
                    511:           limit = (word *)((char *)limit + sizeof(word) - ALIGNMENT);
                    512:           break;
                    513:         case DS_BITMAP:
                    514:           GC_mark_stack_top_reg--;
                    515:           descr &= ~DS_TAGS;
                    516:           credit -= WORDS_TO_BYTES(WORDSZ/2); /* guess */
                    517:           while (descr != 0) {
                    518:             if ((signed_word)descr < 0) {
                    519:               current = *current_p;
                    520:              if ((ptr_t)current >= least_ha && (ptr_t)current < greatest_ha) {
                    521:                PREFETCH(current);
                    522:                 HC_PUSH_CONTENTS((ptr_t)current, GC_mark_stack_top_reg,
                    523:                              mark_stack_limit, current_p, exit1);
                    524:              }
                    525:             }
                    526:            descr <<= 1;
                    527:            ++ current_p;
                    528:           }
                    529:           continue;
                    530:         case DS_PROC:
                    531:           GC_mark_stack_top_reg--;
                    532:           credit -= PROC_BYTES;
                    533:           GC_mark_stack_top_reg =
                    534:               (*PROC(descr))
                    535:                    (current_p, GC_mark_stack_top_reg,
                    536:                    mark_stack_limit, ENV(descr));
                    537:           continue;
                    538:         case DS_PER_OBJECT:
                    539:          if ((signed_word)descr >= 0) {
                    540:            /* Descriptor is in the object.     */
                    541:             descr = *(word *)((ptr_t)current_p + descr - DS_PER_OBJECT);
                    542:          } else {
                    543:            /* Descriptor is in type descriptor pointed to by first     */
                    544:            /* word in object.                                          */
                    545:            ptr_t type_descr = *(ptr_t *)current_p;
                    546:            /* type_descr is either a valid pointer to the descriptor   */
                    547:            /* structure, or this object was on a free list.  If it     */
                    548:            /* it was anything but the last object on the free list,    */
                    549:            /* we will misinterpret the next object on the free list as */
                    550:            /* the type descriptor, and get a 0 GC descriptor, which    */
                    551:            /* is ideal.  Unfortunately, we need to check for the last  */
                    552:            /* object case explicitly.                                  */
                    553:            if (0 == type_descr) {
                    554:                /* Rarely executed.     */
                    555:                GC_mark_stack_top_reg--;
                    556:                continue;
                    557:            }
                    558:             descr = *(word *)(type_descr
                    559:                              - (descr - (DS_PER_OBJECT - INDIR_PER_OBJ_BIAS)));
                    560:          }
                    561:          if (0 == descr) {
                    562:            GC_mark_stack_top_reg--;
                    563:            continue;
                    564:          }
                    565:           goto retry;
                    566:       }
                    567:     } else /* Small object with length descriptor */ {
                    568:       GC_mark_stack_top_reg--;
                    569:       limit = (word *)(((ptr_t)current_p) + (word)descr);
                    570:     }
                    571:     /* The simple case in which we're scanning a range.        */
                    572:     credit -= (ptr_t)limit - (ptr_t)current_p;
                    573:     limit -= 1;
                    574:     {
                    575: #     define PREF_DIST 4
                    576:
                    577: #     ifndef SMALL_CONFIG
                    578:         word deferred;
                    579:
                    580:        /* Try to prefetch the next pointer to be examined asap.        */
                    581:        /* Empirically, this also seems to help slightly without        */
                    582:        /* prefetches, at least on linux/X86.  Presumably this loop     */
                    583:        /* ends up with less register pressure, and gcc thus ends up    */
                    584:        /* generating slightly better code.  Overall gcc code quality   */
                    585:        /* for this loop is still not great.                            */
                    586:        for(;;) {
                    587:          PREFETCH((ptr_t)limit - PREF_DIST*CACHE_LINE_SIZE);
                    588:          deferred = *limit;
                    589:          limit = (word *)((char *)limit - ALIGNMENT);
                    590:          if ((ptr_t)deferred >= least_ha && (ptr_t)deferred <  greatest_ha) {
                    591:            PREFETCH(deferred);
                    592:            break;
                    593:          }
                    594:          if (current_p > limit) goto next_object;
                    595:          /* Unroll once, so we don't do too many of the prefetches     */
                    596:          /* based on limit.                                            */
                    597:          deferred = *limit;
                    598:          limit = (word *)((char *)limit - ALIGNMENT);
                    599:          if ((ptr_t)deferred >= least_ha && (ptr_t)deferred <  greatest_ha) {
                    600:            PREFETCH(deferred);
                    601:            break;
                    602:          }
                    603:          if (current_p > limit) goto next_object;
                    604:        }
                    605: #     endif
                    606:
                    607:       while (current_p <= limit) {
                    608:        /* Empirically, unrolling this loop doesn't help a lot. */
                    609:        /* Since HC_PUSH_CONTENTS expands to a lot of code,     */
                    610:        /* we don't.                                            */
                    611:         current = *current_p;
                    612:         PREFETCH((ptr_t)current_p + PREF_DIST*CACHE_LINE_SIZE);
                    613:         if ((ptr_t)current >= least_ha && (ptr_t)current <  greatest_ha) {
                    614:          /* Prefetch the contents of the object we just pushed.  It's  */
                    615:          /* likely we will need them soon.                             */
                    616:          PREFETCH(current);
                    617:           HC_PUSH_CONTENTS((ptr_t)current, GC_mark_stack_top_reg,
                    618:                           mark_stack_limit, current_p, exit2);
                    619:         }
                    620:         current_p = (word *)((char *)current_p + ALIGNMENT);
                    621:       }
                    622:
                    623: #     ifndef SMALL_CONFIG
                    624:        /* We still need to mark the entry we previously prefetched.    */
                    625:        /* We alrady know that it passes the preliminary pointer        */
                    626:        /* validity test.                                               */
                    627:         HC_PUSH_CONTENTS((ptr_t)deferred, GC_mark_stack_top_reg,
                    628:                         mark_stack_limit, current_p, exit4);
                    629:        next_object:;
                    630: #     endif
                    631:     }
                    632:   }
                    633:   GC_mark_stack_top = GC_mark_stack_top_reg;
                    634: }
                    635:
                    636: /* Allocate or reallocate space for mark stack of size s words  */
                    637: /* May silently fail.                                          */
                    638: static void alloc_mark_stack(n)
                    639: word n;
                    640: {
                    641:     mse * new_stack = (mse *)GC_scratch_alloc(n * sizeof(struct ms_entry));
                    642:
                    643:     GC_mark_stack_too_small = FALSE;
                    644:     if (GC_mark_stack_size != 0) {
                    645:         if (new_stack != 0) {
                    646:           word displ = (word)GC_mark_stack & (GC_page_size - 1);
                    647:           signed_word size = GC_mark_stack_size * sizeof(struct ms_entry);
                    648:
                    649:           /* Recycle old space */
                    650:              if (0 != displ) displ = GC_page_size - displ;
                    651:              size = (size - displ) & ~(GC_page_size - 1);
                    652:              if (size > 0) {
                    653:                GC_add_to_heap((struct hblk *)
                    654:                                ((word)GC_mark_stack + displ), (word)size);
                    655:              }
                    656:           GC_mark_stack = new_stack;
                    657:           GC_mark_stack_size = n;
                    658: #        ifdef PRINTSTATS
                    659:              GC_printf1("Grew mark stack to %lu frames\n",
                    660:                         (unsigned long) GC_mark_stack_size);
                    661: #        endif
                    662:         } else {
                    663: #        ifdef PRINTSTATS
                    664:              GC_printf1("Failed to grow mark stack to %lu frames\n",
                    665:                         (unsigned long) n);
                    666: #        endif
                    667:         }
                    668:     } else {
                    669:         if (new_stack == 0) {
                    670:             GC_err_printf0("No space for mark stack\n");
                    671:             EXIT();
                    672:         }
                    673:         GC_mark_stack = new_stack;
                    674:         GC_mark_stack_size = n;
                    675:     }
                    676:     GC_mark_stack_top = GC_mark_stack-1;
                    677: }
                    678:
                    679: void GC_mark_init()
                    680: {
                    681:     alloc_mark_stack(INITIAL_MARK_STACK_SIZE);
                    682: }
                    683:
                    684: /*
                    685:  * Push all locations between b and t onto the mark stack.
                    686:  * b is the first location to be checked. t is one past the last
                    687:  * location to be checked.
                    688:  * Should only be used if there is no possibility of mark stack
                    689:  * overflow.
                    690:  */
                    691: void GC_push_all(bottom, top)
                    692: ptr_t bottom;
                    693: ptr_t top;
                    694: {
                    695:     register word length;
                    696:
                    697:     bottom = (ptr_t)(((word) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
                    698:     top = (ptr_t)(((word) top) & ~(ALIGNMENT-1));
                    699:     if (top == 0 || bottom == top) return;
                    700:     GC_mark_stack_top++;
                    701:     if (GC_mark_stack_top >= GC_mark_stack + GC_mark_stack_size) {
                    702:        ABORT("unexpected mark stack overflow");
                    703:     }
                    704:     length = top - bottom;
                    705: #   if DS_TAGS > ALIGNMENT - 1
                    706:        length += DS_TAGS;
                    707:        length &= ~DS_TAGS;
                    708: #   endif
                    709:     GC_mark_stack_top -> mse_start = (word *)bottom;
                    710:     GC_mark_stack_top -> mse_descr = length;
                    711: }
                    712:
                    713: /*
                    714:  * Analogous to the above, but push only those pages that may have been
                    715:  * dirtied.  A block h is assumed dirty if dirty_fn(h) != 0.
                    716:  * We use push_fn to actually push the block.
                    717:  * Will not overflow mark stack if push_fn pushes a small fixed number
                    718:  * of entries.  (This is invoked only if push_fn pushes a single entry,
                    719:  * or if it marks each object before pushing it, thus ensuring progress
                    720:  * in the event of a stack overflow.)
                    721:  */
                    722: void GC_push_dirty(bottom, top, dirty_fn, push_fn)
                    723: ptr_t bottom;
                    724: ptr_t top;
                    725: int (*dirty_fn)(/* struct hblk * h */);
                    726: void (*push_fn)(/* ptr_t bottom, ptr_t top */);
                    727: {
                    728:     register struct hblk * h;
                    729:
                    730:     bottom = (ptr_t)(((long) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
                    731:     top = (ptr_t)(((long) top) & ~(ALIGNMENT-1));
                    732:
                    733:     if (top == 0 || bottom == top) return;
                    734:     h = HBLKPTR(bottom + HBLKSIZE);
                    735:     if (top <= (ptr_t) h) {
                    736:        if ((*dirty_fn)(h-1)) {
                    737:            (*push_fn)(bottom, top);
                    738:        }
                    739:        return;
                    740:     }
                    741:     if ((*dirty_fn)(h-1)) {
                    742:         (*push_fn)(bottom, (ptr_t)h);
                    743:     }
                    744:     while ((ptr_t)(h+1) <= top) {
                    745:        if ((*dirty_fn)(h)) {
                    746:            if ((word)(GC_mark_stack_top - GC_mark_stack)
                    747:                > 3 * GC_mark_stack_size / 4) {
                    748:                /* Danger of mark stack overflow */
                    749:                (*push_fn)((ptr_t)h, top);
                    750:                return;
                    751:            } else {
                    752:                (*push_fn)((ptr_t)h, (ptr_t)(h+1));
                    753:            }
                    754:        }
                    755:        h++;
                    756:     }
                    757:     if ((ptr_t)h != top) {
                    758:        if ((*dirty_fn)(h)) {
                    759:             (*push_fn)((ptr_t)h, top);
                    760:         }
                    761:     }
                    762:     if (GC_mark_stack_top >= GC_mark_stack + GC_mark_stack_size) {
                    763:         ABORT("unexpected mark stack overflow");
                    764:     }
                    765: }
                    766:
                    767: # ifndef SMALL_CONFIG
                    768: void GC_push_conditional(bottom, top, all)
                    769: ptr_t bottom;
                    770: ptr_t top;
                    771: int all;
                    772: {
                    773:     if (all) {
                    774:       if (GC_dirty_maintained) {
                    775: #      ifdef PROC_VDB
                    776:            /* Pages that were never dirtied cannot contain pointers    */
                    777:            GC_push_dirty(bottom, top, GC_page_was_ever_dirty, GC_push_all);
                    778: #      else
                    779:            GC_push_all(bottom, top);
                    780: #      endif
                    781:       } else {
                    782:        GC_push_all(bottom, top);
                    783:       }
                    784:     } else {
                    785:        GC_push_dirty(bottom, top, GC_page_was_dirty, GC_push_all);
                    786:     }
                    787: }
                    788: #endif
                    789:
                    790: # ifdef MSWIN32
                    791:   void __cdecl GC_push_one(p)
                    792: # else
                    793:   void GC_push_one(p)
                    794: # endif
                    795: word p;
                    796: {
                    797: #   ifdef NURSERY
                    798:       if (0 != GC_push_proc) {
                    799:        GC_push_proc(p);
                    800:        return;
                    801:       }
                    802: #   endif
                    803:     GC_PUSH_ONE_STACK(p, MARKED_FROM_REGISTER);
                    804: }
                    805:
                    806: # ifdef __STDC__
                    807: #   define BASE(p) (word)GC_base((void *)(p))
                    808: # else
                    809: #   define BASE(p) (word)GC_base((char *)(p))
                    810: # endif
                    811:
                    812: /* As above, but argument passed preliminary test. */
                    813: # if defined(PRINT_BLACK_LIST) || defined(KEEP_BACK_PTRS)
                    814:     void GC_push_one_checked(p, interior_ptrs, source)
                    815:     ptr_t source;
                    816: # else
                    817:     void GC_push_one_checked(p, interior_ptrs)
                    818: #   define source 0
                    819: # endif
                    820: register word p;
                    821: register GC_bool interior_ptrs;
                    822: {
                    823:     register word r;
                    824:     register hdr * hhdr;
                    825:     register int displ;
                    826:
                    827:     GET_HDR(p, hhdr);
                    828:     if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) {
                    829:         if (hhdr != 0 && interior_ptrs) {
                    830:           r = BASE(p);
                    831:          hhdr = HDR(r);
                    832:          displ = BYTES_TO_WORDS(HBLKDISPL(r));
                    833:        } else {
                    834:          hhdr = 0;
                    835:        }
                    836:     } else {
                    837:         register map_entry_type map_entry;
                    838:
                    839:         displ = HBLKDISPL(p);
                    840:         map_entry = MAP_ENTRY((hhdr -> hb_map), displ);
                    841:         if (map_entry == OBJ_INVALID) {
                    842: #        ifndef ALL_INTERIOR_POINTERS
                    843:             if (interior_ptrs) {
                    844:               r = BASE(p);
                    845:              displ = BYTES_TO_WORDS(HBLKDISPL(r));
                    846:              if (r == 0) hhdr = 0;
                    847:             } else {
                    848:               hhdr = 0;
                    849:             }
                    850: #        else
                    851:            /* map already reflects interior pointers */
                    852:            hhdr = 0;
                    853: #        endif
                    854:         } else {
                    855:           displ = BYTES_TO_WORDS(displ);
                    856:           displ -= map_entry;
                    857:           r = (word)((word *)(HBLKPTR(p)) + displ);
                    858:         }
                    859:     }
                    860:     /* If hhdr != 0 then r == GC_base(p), only we did it faster. */
                    861:     /* displ is the word index within the block.                */
                    862:     if (hhdr == 0) {
                    863:        if (interior_ptrs) {
                    864: #          ifdef PRINT_BLACK_LIST
                    865:              GC_add_to_black_list_stack(p, source);
                    866: #          else
                    867:              GC_add_to_black_list_stack(p);
                    868: #          endif
                    869:        } else {
                    870:            GC_ADD_TO_BLACK_LIST_NORMAL(p, source);
                    871: #          undef source  /* In case we had to define it. */
                    872:        }
                    873:     } else {
                    874:        if (!mark_bit_from_hdr(hhdr, displ)) {
                    875:            set_mark_bit_from_hdr(hhdr, displ);
                    876:            GC_STORE_BACK_PTR(source, (ptr_t)r);
                    877:            PUSH_OBJ((word *)r, hhdr, GC_mark_stack_top,
                    878:                     &(GC_mark_stack[GC_mark_stack_size]));
                    879:        }
                    880:     }
                    881: }
                    882:
                    883: # ifdef TRACE_BUF
                    884:
                    885: # define TRACE_ENTRIES 1000
                    886:
                    887: struct trace_entry {
                    888:     char * kind;
                    889:     word gc_no;
                    890:     word words_allocd;
                    891:     word arg1;
                    892:     word arg2;
                    893: } GC_trace_buf[TRACE_ENTRIES];
                    894:
                    895: int GC_trace_buf_ptr = 0;
                    896:
                    897: void GC_add_trace_entry(char *kind, word arg1, word arg2)
                    898: {
                    899:     GC_trace_buf[GC_trace_buf_ptr].kind = kind;
                    900:     GC_trace_buf[GC_trace_buf_ptr].gc_no = GC_gc_no;
                    901:     GC_trace_buf[GC_trace_buf_ptr].words_allocd = GC_words_allocd;
                    902:     GC_trace_buf[GC_trace_buf_ptr].arg1 = arg1 ^ 0x80000000;
                    903:     GC_trace_buf[GC_trace_buf_ptr].arg2 = arg2 ^ 0x80000000;
                    904:     GC_trace_buf_ptr++;
                    905:     if (GC_trace_buf_ptr >= TRACE_ENTRIES) GC_trace_buf_ptr = 0;
                    906: }
                    907:
                    908: void GC_print_trace(word gc_no, GC_bool lock)
                    909: {
                    910:     int i;
                    911:     struct trace_entry *p;
                    912:
                    913:     if (lock) LOCK();
                    914:     for (i = GC_trace_buf_ptr-1; i != GC_trace_buf_ptr; i--) {
                    915:        if (i < 0) i = TRACE_ENTRIES-1;
                    916:        p = GC_trace_buf + i;
                    917:        if (p -> gc_no < gc_no || p -> kind == 0) return;
                    918:        printf("Trace:%s (gc:%d,words:%d) 0x%X, 0x%X\n",
                    919:                p -> kind, p -> gc_no, p -> words_allocd,
                    920:                (p -> arg1) ^ 0x80000000, (p -> arg2) ^ 0x80000000);
                    921:     }
                    922:     printf("Trace incomplete\n");
                    923:     if (lock) UNLOCK();
                    924: }
                    925:
                    926: # endif /* TRACE_BUF */
                    927:
                    928: /*
                    929:  * A version of GC_push_all that treats all interior pointers as valid
                    930:  * and scans the entire region immediately, in case the contents
                    931:  * change.
                    932:  */
                    933: void GC_push_all_eager(bottom, top)
                    934: ptr_t bottom;
                    935: ptr_t top;
                    936: {
                    937:     word * b = (word *)(((long) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
                    938:     word * t = (word *)(((long) top) & ~(ALIGNMENT-1));
                    939:     register word *p;
                    940:     register word q;
                    941:     register word *lim;
                    942:     register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
                    943:     register ptr_t least_ha = GC_least_plausible_heap_addr;
                    944: #   define GC_greatest_plausible_heap_addr greatest_ha
                    945: #   define GC_least_plausible_heap_addr least_ha
                    946:
                    947:     if (top == 0) return;
                    948:     /* check all pointers in range and put in push if they appear */
                    949:     /* to be valid.                                              */
                    950:       lim = t - 1 /* longword */;
                    951:       for (p = b; p <= lim; p = (word *)(((char *)p) + ALIGNMENT)) {
                    952:        q = *p;
                    953:        GC_PUSH_ONE_STACK(q, p);
                    954:       }
                    955: #   undef GC_greatest_plausible_heap_addr
                    956: #   undef GC_least_plausible_heap_addr
                    957: }
                    958:
                    959: #ifndef THREADS
                    960: /*
                    961:  * A version of GC_push_all that treats all interior pointers as valid
                    962:  * and scans part of the area immediately, to make sure that saved
                    963:  * register values are not lost.
                    964:  * Cold_gc_frame delimits the stack section that must be scanned
                    965:  * eagerly.  A zero value indicates that no eager scanning is needed.
                    966:  */
                    967: void GC_push_all_stack_partially_eager(bottom, top, cold_gc_frame)
                    968: ptr_t bottom;
                    969: ptr_t top;
                    970: ptr_t cold_gc_frame;
                    971: {
                    972: # ifdef ALL_INTERIOR_POINTERS
                    973: #   define EAGER_BYTES 1024
                    974:     /* Push the hot end of the stack eagerly, so that register values   */
                    975:     /* saved inside GC frames are marked before they disappear.                */
                    976:     /* The rest of the marking can be deferred until later.            */
                    977:     if (0 == cold_gc_frame) {
                    978:        GC_push_all_stack(bottom, top);
                    979:        return;
                    980:     }
                    981: #   ifdef STACK_GROWS_DOWN
                    982:        GC_push_all_eager(bottom, cold_gc_frame);
                    983:        GC_push_all(cold_gc_frame - sizeof(ptr_t), top);
                    984: #   else /* STACK_GROWS_UP */
                    985:        GC_push_all_eager(cold_gc_frame, top);
                    986:        GC_push_all(bottom, cold_gc_frame + sizeof(ptr_t));
                    987: #   endif /* STACK_GROWS_UP */
                    988: # else
                    989:     GC_push_all_eager(bottom, top);
                    990: # endif
                    991: # ifdef TRACE_BUF
                    992:       GC_add_trace_entry("GC_push_all_stack", bottom, top);
                    993: # endif
                    994: }
                    995: #endif /* !THREADS */
                    996:
                    997: void GC_push_all_stack(bottom, top)
                    998: ptr_t bottom;
                    999: ptr_t top;
                   1000: {
                   1001: # ifdef ALL_INTERIOR_POINTERS
                   1002:     GC_push_all(bottom, top);
                   1003: # else
                   1004:     GC_push_all_eager(bottom, top);
                   1005: # endif
                   1006: }
                   1007:
                   1008: #ifndef SMALL_CONFIG
                   1009: /* Push all objects reachable from marked objects in the given block */
                   1010: /* of size 1 objects.                                               */
                   1011: void GC_push_marked1(h, hhdr)
                   1012: struct hblk *h;
                   1013: register hdr * hhdr;
                   1014: {
                   1015:     word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
                   1016:     register word *p;
                   1017:     word *plim;
                   1018:     register int i;
                   1019:     register word q;
                   1020:     register word mark_word;
                   1021:     register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
                   1022:     register ptr_t least_ha = GC_least_plausible_heap_addr;
                   1023: #   define GC_greatest_plausible_heap_addr greatest_ha
                   1024: #   define GC_least_plausible_heap_addr least_ha
                   1025:
                   1026:     p = (word *)(h->hb_body);
                   1027:     plim = (word *)(((word)h) + HBLKSIZE);
                   1028:
                   1029:     /* go through all words in block */
                   1030:        while( p < plim )  {
                   1031:            mark_word = *mark_word_addr++;
                   1032:            i = 0;
                   1033:            while(mark_word != 0) {
                   1034:              if (mark_word & 1) {
                   1035:                  q = p[i];
                   1036:                  GC_PUSH_ONE_HEAP(q, p + i);
                   1037:              }
                   1038:              i++;
                   1039:              mark_word >>= 1;
                   1040:            }
                   1041:            p += WORDSZ;
                   1042:        }
                   1043: #   undef GC_greatest_plausible_heap_addr
                   1044: #   undef GC_least_plausible_heap_addr
                   1045: }
                   1046:
                   1047:
                   1048: #ifndef UNALIGNED
                   1049:
                   1050: /* Push all objects reachable from marked objects in the given block */
                   1051: /* of size 2 objects.                                               */
                   1052: void GC_push_marked2(h, hhdr)
                   1053: struct hblk *h;
                   1054: register hdr * hhdr;
                   1055: {
                   1056:     word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
                   1057:     register word *p;
                   1058:     word *plim;
                   1059:     register int i;
                   1060:     register word q;
                   1061:     register word mark_word;
                   1062:     register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
                   1063:     register ptr_t least_ha = GC_least_plausible_heap_addr;
                   1064: #   define GC_greatest_plausible_heap_addr greatest_ha
                   1065: #   define GC_least_plausible_heap_addr least_ha
                   1066:
                   1067:     p = (word *)(h->hb_body);
                   1068:     plim = (word *)(((word)h) + HBLKSIZE);
                   1069:
                   1070:     /* go through all words in block */
                   1071:        while( p < plim )  {
                   1072:            mark_word = *mark_word_addr++;
                   1073:            i = 0;
                   1074:            while(mark_word != 0) {
                   1075:              if (mark_word & 1) {
                   1076:                  q = p[i];
                   1077:                  GC_PUSH_ONE_HEAP(q, p + i);
                   1078:                  q = p[i+1];
                   1079:                  GC_PUSH_ONE_HEAP(q, p + i);
                   1080:              }
                   1081:              i += 2;
                   1082:              mark_word >>= 2;
                   1083:            }
                   1084:            p += WORDSZ;
                   1085:        }
                   1086: #   undef GC_greatest_plausible_heap_addr
                   1087: #   undef GC_least_plausible_heap_addr
                   1088: }
                   1089:
                   1090: /* Push all objects reachable from marked objects in the given block */
                   1091: /* of size 4 objects.                                               */
                   1092: /* There is a risk of mark stack overflow here.  But we handle that. */
                   1093: /* And only unmarked objects get pushed, so it's not very likely.    */
                   1094: void GC_push_marked4(h, hhdr)
                   1095: struct hblk *h;
                   1096: register hdr * hhdr;
                   1097: {
                   1098:     word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
                   1099:     register word *p;
                   1100:     word *plim;
                   1101:     register int i;
                   1102:     register word q;
                   1103:     register word mark_word;
                   1104:     register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
                   1105:     register ptr_t least_ha = GC_least_plausible_heap_addr;
                   1106: #   define GC_greatest_plausible_heap_addr greatest_ha
                   1107: #   define GC_least_plausible_heap_addr least_ha
                   1108:
                   1109:     p = (word *)(h->hb_body);
                   1110:     plim = (word *)(((word)h) + HBLKSIZE);
                   1111:
                   1112:     /* go through all words in block */
                   1113:        while( p < plim )  {
                   1114:            mark_word = *mark_word_addr++;
                   1115:            i = 0;
                   1116:            while(mark_word != 0) {
                   1117:              if (mark_word & 1) {
                   1118:                  q = p[i];
                   1119:                  GC_PUSH_ONE_HEAP(q, p + i);
                   1120:                  q = p[i+1];
                   1121:                  GC_PUSH_ONE_HEAP(q, p + i + 1);
                   1122:                  q = p[i+2];
                   1123:                  GC_PUSH_ONE_HEAP(q, p + i + 2);
                   1124:                  q = p[i+3];
                   1125:                  GC_PUSH_ONE_HEAP(q, p + i + 3);
                   1126:              }
                   1127:              i += 4;
                   1128:              mark_word >>= 4;
                   1129:            }
                   1130:            p += WORDSZ;
                   1131:        }
                   1132: #   undef GC_greatest_plausible_heap_addr
                   1133: #   undef GC_least_plausible_heap_addr
                   1134: }
                   1135:
                   1136: #endif /* UNALIGNED */
                   1137:
                   1138: #endif /* SMALL_CONFIG */
                   1139:
                   1140: /* Push all objects reachable from marked objects in the given block */
                   1141: void GC_push_marked(h, hhdr)
                   1142: struct hblk *h;
                   1143: register hdr * hhdr;
                   1144: {
                   1145:     register int sz = hhdr -> hb_sz;
                   1146:     register int descr = hhdr -> hb_descr;
                   1147:     register word * p;
                   1148:     register int word_no;
                   1149:     register word * lim;
                   1150:     register mse * GC_mark_stack_top_reg;
                   1151:     register mse * mark_stack_limit = &(GC_mark_stack[GC_mark_stack_size]);
                   1152:
                   1153:     /* Some quick shortcuts: */
                   1154:        if ((0 | DS_LENGTH) == descr) return;
                   1155:         if (GC_block_empty(hhdr)/* nothing marked */) return;
                   1156: #   ifdef GATHERSTATS
                   1157:         GC_n_rescuing_pages++;
                   1158: #   endif
                   1159:     GC_objects_are_marked = TRUE;
                   1160:     if (sz > MAXOBJSZ) {
                   1161:         lim = (word *)h + HDR_WORDS;
                   1162:     } else {
                   1163:         lim = (word *)(h + 1) - sz;
                   1164:     }
                   1165:
                   1166:     switch(sz) {
                   1167: #   if !defined(SMALL_CONFIG)
                   1168:      case 1:
                   1169:        GC_push_marked1(h, hhdr);
                   1170:        break;
                   1171: #   endif
                   1172: #   if !defined(SMALL_CONFIG) && !defined(UNALIGNED)
                   1173:      case 2:
                   1174:        GC_push_marked2(h, hhdr);
                   1175:        break;
                   1176:      case 4:
                   1177:        GC_push_marked4(h, hhdr);
                   1178:        break;
                   1179: #   endif
                   1180:      default:
                   1181:       GC_mark_stack_top_reg = GC_mark_stack_top;
                   1182:       for (p = (word *)h + HDR_WORDS, word_no = HDR_WORDS; p <= lim;
                   1183:          p += sz, word_no += sz) {
                   1184:          if (mark_bit_from_hdr(hhdr, word_no)) {
                   1185:            /* Mark from fields inside the object */
                   1186:              PUSH_OBJ((word *)p, hhdr, GC_mark_stack_top_reg, mark_stack_limit);
                   1187: #           ifdef GATHERSTATS
                   1188:                /* Subtract this object from total, since it was        */
                   1189:                /* added in twice.                                      */
                   1190:                GC_composite_in_use -= sz;
                   1191: #           endif
                   1192:          }
                   1193:       }
                   1194:       GC_mark_stack_top = GC_mark_stack_top_reg;
                   1195:     }
                   1196: }
                   1197:
                   1198: #ifndef SMALL_CONFIG
                   1199: /* Test whether any page in the given block is dirty   */
                   1200: GC_bool GC_block_was_dirty(h, hhdr)
                   1201: struct hblk *h;
                   1202: register hdr * hhdr;
                   1203: {
                   1204:     register int sz = hhdr -> hb_sz;
                   1205:
                   1206:     if (sz < MAXOBJSZ) {
                   1207:          return(GC_page_was_dirty(h));
                   1208:     } else {
                   1209:         register ptr_t p = (ptr_t)h;
                   1210:          sz += HDR_WORDS;
                   1211:          sz = WORDS_TO_BYTES(sz);
                   1212:          while (p < (ptr_t)h + sz) {
                   1213:              if (GC_page_was_dirty((struct hblk *)p)) return(TRUE);
                   1214:              p += HBLKSIZE;
                   1215:          }
                   1216:          return(FALSE);
                   1217:     }
                   1218: }
                   1219: #endif /* SMALL_CONFIG */
                   1220:
                   1221: /* Similar to GC_push_next_marked, but return address of next block    */
                   1222: struct hblk * GC_push_next_marked(h)
                   1223: struct hblk *h;
                   1224: {
                   1225:     register hdr * hhdr;
                   1226:
                   1227:     h = GC_next_used_block(h);
                   1228:     if (h == 0) return(0);
                   1229:     hhdr = HDR(h);
                   1230:     GC_push_marked(h, hhdr);
                   1231:     return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
                   1232: }
                   1233:
                   1234: #ifndef SMALL_CONFIG
                   1235: /* Identical to above, but mark only from dirty pages  */
                   1236: struct hblk * GC_push_next_marked_dirty(h)
                   1237: struct hblk *h;
                   1238: {
                   1239:     register hdr * hhdr;
                   1240:
                   1241:     if (!GC_dirty_maintained) { ABORT("dirty bits not set up"); }
                   1242:     for (;;) {
                   1243:         h = GC_next_used_block(h);
                   1244:         if (h == 0) return(0);
                   1245:         hhdr = HDR(h);
                   1246: #      ifdef STUBBORN_ALLOC
                   1247:           if (hhdr -> hb_obj_kind == STUBBORN) {
                   1248:             if (GC_page_was_changed(h) && GC_block_was_dirty(h, hhdr)) {
                   1249:                 break;
                   1250:             }
                   1251:           } else {
                   1252:             if (GC_block_was_dirty(h, hhdr)) break;
                   1253:           }
                   1254: #      else
                   1255:          if (GC_block_was_dirty(h, hhdr)) break;
                   1256: #      endif
                   1257:         h += OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
                   1258:     }
                   1259:     GC_push_marked(h, hhdr);
                   1260:     return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
                   1261: }
                   1262: #endif
                   1263:
                   1264: /* Similar to above, but for uncollectable pages.  Needed since we     */
                   1265: /* do not clear marks for such pages, even for full collections.       */
                   1266: struct hblk * GC_push_next_marked_uncollectable(h)
                   1267: struct hblk *h;
                   1268: {
                   1269:     register hdr * hhdr = HDR(h);
                   1270:
                   1271:     for (;;) {
                   1272:         h = GC_next_used_block(h);
                   1273:         if (h == 0) return(0);
                   1274:         hhdr = HDR(h);
                   1275:        if (hhdr -> hb_obj_kind == UNCOLLECTABLE) break;
                   1276:         h += OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
                   1277:     }
                   1278:     GC_push_marked(h, hhdr);
                   1279:     return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
                   1280: }
                   1281:
                   1282:

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