[BACK]Return to reclaim.c CVS log [TXT][DIR] Up to [local] / OpenXM_contrib2 / asir2000 / gc

Annotation of OpenXM_contrib2/asir2000/gc/reclaim.c, Revision 1.3

1.1       noro        1: /*
                      2:  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
1.2       noro        3:  * Copyright (c) 1991-1996 by Xerox Corporation.  All rights reserved.
                      4:  * Copyright (c) 1996-1999 by Silicon Graphics.  All rights reserved.
                      5:  * Copyright (c) 1999 by Hewlett-Packard Company. All rights reserved.
1.1       noro        6:  *
                      7:  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
                      8:  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
                      9:  *
                     10:  * Permission is hereby granted to use or copy this program
                     11:  * for any purpose,  provided the above notices are retained on all copies.
                     12:  * Permission to modify the code and to distribute modified code is granted,
                     13:  * provided the above notices are retained, and a notice that the code was
                     14:  * modified is included with the above copyright notice.
                     15:  */
                     16:
                     17: #include <stdio.h>
                     18: #include "gc_priv.h"
                     19:
                     20: void GC_timerstart(), GC_timerstop();
                     21:
                     22: signed_word GC_mem_found = 0;
                     23:                        /* Number of words of memory reclaimed     */
                     24:
                     25: static void report_leak(p, sz)
                     26: ptr_t p;
                     27: word sz;
                     28: {
                     29:     if (HDR(p) -> hb_obj_kind == PTRFREE) {
                     30:         GC_err_printf0("Leaked atomic object at ");
                     31:     } else {
                     32:         GC_err_printf0("Leaked composite object at ");
                     33:     }
                     34:     if (GC_debugging_started && GC_has_debug_info(p)) {
                     35:         GC_print_obj(p);
                     36:     } else {
                     37:         GC_err_printf2("0x%lx (appr. size = %ld)\n",
                     38:                              (unsigned long)p,
                     39:                              (unsigned long)WORDS_TO_BYTES(sz));
                     40:     }
                     41: }
                     42:
                     43: #   define FOUND_FREE(hblk, word_no) \
1.2       noro       44:       { \
1.1       noro       45:          report_leak((ptr_t)hblk + WORDS_TO_BYTES(word_no), \
                     46:                     HDR(hblk) -> hb_sz); \
                     47:       }
                     48:
                     49: /*
                     50:  * reclaim phase
                     51:  *
                     52:  */
                     53:
                     54:
                     55: /*
                     56:  * Test whether a block is completely empty, i.e. contains no marked
                     57:  * objects.  This does not require the block to be in physical
                     58:  * memory.
                     59:  */
                     60:
                     61: GC_bool GC_block_empty(hhdr)
                     62: register hdr * hhdr;
                     63: {
                     64:     register word *p = (word *)(&(hhdr -> hb_marks[0]));
                     65:     register word * plim =
                     66:                        (word *)(&(hhdr -> hb_marks[MARK_BITS_SZ]));
                     67:     while (p < plim) {
                     68:        if (*p++) return(FALSE);
                     69:     }
                     70:     return(TRUE);
                     71: }
                     72:
1.2       noro       73: /* The following functions sometimes return a DONT_KNOW value. */
                     74: #define DONT_KNOW  2
                     75:
                     76: #ifdef SMALL_CONFIG
                     77: # define GC_block_nearly_full1(hhdr, pat1) DONT_KNOW
                     78: # define GC_block_nearly_full3(hhdr, pat1, pat2) DONT_KNOW
                     79: # define GC_block_nearly_full(hhdr) DONT_KNOW
                     80: #else
                     81:
                     82: /*
                     83:  * Test whether nearly all of the mark words consist of the same
                     84:  * repeating pattern.
                     85:  */
                     86: #define FULL_THRESHOLD (MARK_BITS_SZ/16)
                     87:
                     88: GC_bool GC_block_nearly_full1(hhdr, pat1)
                     89: hdr *hhdr;
                     90: word pat1;
                     91: {
                     92:     unsigned i;
                     93:     unsigned misses = 0;
                     94:     GC_ASSERT((MARK_BITS_SZ & 1) == 0);
                     95:     for (i = 0; i < MARK_BITS_SZ; ++i) {
                     96:        if ((hhdr -> hb_marks[i] | ~pat1) != ONES) {
                     97:            if (++misses > FULL_THRESHOLD) return FALSE;
                     98:        }
                     99:     }
                    100:     return TRUE;
                    101: }
                    102:
                    103: /*
                    104:  * Test whether the same repeating 3 word pattern occurs in nearly
                    105:  * all the mark bit slots.
                    106:  * This is used as a heuristic, so we're a bit sloppy and ignore
                    107:  * the last one or two words.
                    108:  */
                    109: GC_bool GC_block_nearly_full3(hhdr, pat1, pat2, pat3)
                    110: hdr *hhdr;
                    111: word pat1, pat2, pat3;
                    112: {
                    113:     unsigned i;
                    114:     unsigned misses = 0;
                    115:
                    116:     if (MARK_BITS_SZ < 4) {
                    117:       return DONT_KNOW;
                    118:     }
                    119:     for (i = 0; i < MARK_BITS_SZ - 2; i += 3) {
                    120:        if ((hhdr -> hb_marks[i] | ~pat1) != ONES) {
                    121:            if (++misses > FULL_THRESHOLD) return FALSE;
                    122:        }
                    123:        if ((hhdr -> hb_marks[i+1] | ~pat2) != ONES) {
                    124:            if (++misses > FULL_THRESHOLD) return FALSE;
                    125:        }
                    126:        if ((hhdr -> hb_marks[i+2] | ~pat3) != ONES) {
                    127:            if (++misses > FULL_THRESHOLD) return FALSE;
                    128:        }
                    129:     }
                    130:     return TRUE;
                    131: }
                    132:
                    133: /* Check whether a small object block is nearly full by looking at only */
                    134: /* the mark bits.                                                      */
                    135: /* We manually precomputed the mark bit patterns that need to be       */
                    136: /* checked for, and we give up on the ones that are unlikely to occur, */
                    137: /* or have period > 3.                                                 */
                    138: /* This would be a lot easier with a mark bit per object instead of per        */
                    139: /* word, but that would rewuire computing object numbers in the mark   */
                    140: /* loop, which would require different data structures ...             */
                    141: GC_bool GC_block_nearly_full(hhdr)
                    142: hdr *hhdr;
                    143: {
                    144:     int sz = hhdr -> hb_sz;
                    145:
                    146: #   if CPP_WORDSZ != 32 && CPP_WORDSZ != 64
                    147:       return DONT_KNOW;        /* Shouldn't be used in any standard config.    */
                    148: #   endif
                    149:     if (0 != HDR_WORDS) return DONT_KNOW;
                    150:        /* Also shouldn't happen */
                    151: #   if CPP_WORDSZ == 32
                    152:       switch(sz) {
                    153:         case 1:
                    154:          return GC_block_nearly_full1(hhdr, 0xffffffffl);
                    155:        case 2:
                    156:          return GC_block_nearly_full1(hhdr, 0x55555555l);
                    157:        case 4:
                    158:          return GC_block_nearly_full1(hhdr, 0x11111111l);
                    159:        case 6:
                    160:          return GC_block_nearly_full3(hhdr, 0x41041041l,
                    161:                                              0x10410410l,
                    162:                                               0x04104104l);
                    163:        case 8:
                    164:          return GC_block_nearly_full1(hhdr, 0x01010101l);
                    165:        case 12:
                    166:          return GC_block_nearly_full3(hhdr, 0x01001001l,
                    167:                                              0x10010010l,
                    168:                                               0x00100100l);
                    169:        case 16:
                    170:          return GC_block_nearly_full1(hhdr, 0x00010001l);
                    171:        case 32:
                    172:          return GC_block_nearly_full1(hhdr, 0x00000001l);
                    173:        default:
                    174:          return DONT_KNOW;
                    175:       }
                    176: #   endif
                    177: #   if CPP_WORDSZ == 64
                    178:       switch(sz) {
                    179:         case 1:
                    180:          return GC_block_nearly_full1(hhdr, 0xffffffffffffffffl);
                    181:        case 2:
                    182:          return GC_block_nearly_full1(hhdr, 0x5555555555555555l);
                    183:        case 4:
                    184:          return GC_block_nearly_full1(hhdr, 0x1111111111111111l);
                    185:        case 6:
                    186:          return GC_block_nearly_full3(hhdr, 0x1041041041041041l,
                    187:                                               0x4104104104104104l,
                    188:                                                 0x0410410410410410l);
                    189:        case 8:
                    190:          return GC_block_nearly_full1(hhdr, 0x0101010101010101l);
                    191:        case 12:
                    192:          return GC_block_nearly_full3(hhdr, 0x1001001001001001l,
                    193:                                               0x0100100100100100l,
                    194:                                                 0x0010010010010010l);
                    195:        case 16:
                    196:          return GC_block_nearly_full1(hhdr, 0x0001000100010001l);
                    197:        case 32:
                    198:          return GC_block_nearly_full1(hhdr, 0x0000000100000001l);
                    199:        default:
                    200:          return DONT_KNOW;
                    201:       }
                    202: #   endif
                    203: }
                    204: #endif /* !SMALL_CONFIG */
                    205:
1.1       noro      206: # ifdef GATHERSTATS
                    207: #   define INCR_WORDS(sz) n_words_found += (sz)
                    208: # else
                    209: #   define INCR_WORDS(sz)
                    210: # endif
                    211: /*
                    212:  * Restore unmarked small objects in h of size sz to the object
                    213:  * free list.  Returns the new list.
                    214:  * Clears unmarked objects.
                    215:  */
                    216: /*ARGSUSED*/
1.2       noro      217: ptr_t GC_reclaim_clear(hbp, hhdr, sz, list)
1.1       noro      218: register struct hblk *hbp;     /* ptr to current heap block            */
                    219: register hdr * hhdr;
                    220: register ptr_t list;
                    221: register word sz;
                    222: {
                    223:     register int word_no;
                    224:     register word *p, *q, *plim;
                    225: #   ifdef GATHERSTATS
                    226:         register int n_words_found = 0;
                    227: #   endif
                    228:
                    229:     p = (word *)(hbp->hb_body);
                    230:     word_no = HDR_WORDS;
                    231:     plim = (word *)((((word)hbp) + HBLKSIZE)
                    232:                   - WORDS_TO_BYTES(sz));
                    233:
                    234:     /* go through all words in block */
                    235:        while( p <= plim )  {
                    236:            if( mark_bit_from_hdr(hhdr, word_no) ) {
                    237:                p += sz;
                    238:            } else {
                    239:                INCR_WORDS(sz);
                    240:                /* object is available - put on list */
                    241:                    obj_link(p) = list;
                    242:                    list = ((ptr_t)p);
                    243:                /* Clear object, advance p to next object in the process */
                    244:                    q = p + sz;
                    245:                     p++; /* Skip link field */
                    246:                     while (p < q) {
                    247:                        *p++ = 0;
                    248:                    }
                    249:            }
                    250:            word_no += sz;
                    251:        }
                    252: #   ifdef GATHERSTATS
                    253:        GC_mem_found += n_words_found;
                    254: #   endif
                    255:     return(list);
                    256: }
                    257:
                    258: #ifndef SMALL_CONFIG
                    259:
                    260: /*
                    261:  * A special case for 2 word composite objects (e.g. cons cells):
                    262:  */
                    263: /*ARGSUSED*/
1.2       noro      264: ptr_t GC_reclaim_clear2(hbp, hhdr, list)
1.1       noro      265: register struct hblk *hbp;     /* ptr to current heap block            */
                    266: hdr * hhdr;
                    267: register ptr_t list;
                    268: {
                    269:     register word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
                    270:     register word *p, *plim;
                    271: #   ifdef GATHERSTATS
                    272:         register int n_words_found = 0;
                    273: #   endif
                    274:     register word mark_word;
                    275:     register int i;
                    276: #   define DO_OBJ(start_displ) \
                    277:        if (!(mark_word & ((word)1 << start_displ))) { \
                    278:            p[start_displ] = (word)list; \
                    279:            list = (ptr_t)(p+start_displ); \
                    280:            p[start_displ+1] = 0; \
                    281:            INCR_WORDS(2); \
                    282:        }
                    283:
                    284:     p = (word *)(hbp->hb_body);
                    285:     plim = (word *)(((word)hbp) + HBLKSIZE);
                    286:
                    287:     /* go through all words in block */
                    288:        while( p < plim )  {
                    289:            mark_word = *mark_word_addr++;
                    290:            for (i = 0; i < WORDSZ; i += 8) {
                    291:                DO_OBJ(0);
                    292:                DO_OBJ(2);
                    293:                DO_OBJ(4);
                    294:                DO_OBJ(6);
                    295:                p += 8;
                    296:                mark_word >>= 8;
                    297:            }
                    298:        }
                    299: #   ifdef GATHERSTATS
                    300:        GC_mem_found += n_words_found;
                    301: #   endif
                    302:     return(list);
                    303: #   undef DO_OBJ
                    304: }
                    305:
                    306: /*
                    307:  * Another special case for 4 word composite objects:
                    308:  */
                    309: /*ARGSUSED*/
1.2       noro      310: ptr_t GC_reclaim_clear4(hbp, hhdr, list)
1.1       noro      311: register struct hblk *hbp;     /* ptr to current heap block            */
                    312: hdr * hhdr;
                    313: register ptr_t list;
                    314: {
                    315:     register word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
                    316:     register word *p, *plim;
                    317: #   ifdef GATHERSTATS
                    318:         register int n_words_found = 0;
                    319: #   endif
                    320:     register word mark_word;
                    321: #   define DO_OBJ(start_displ) \
                    322:        if (!(mark_word & ((word)1 << start_displ))) { \
                    323:            p[start_displ] = (word)list; \
                    324:            list = (ptr_t)(p+start_displ); \
                    325:            p[start_displ+1] = 0; \
                    326:            p[start_displ+2] = 0; \
                    327:            p[start_displ+3] = 0; \
                    328:            INCR_WORDS(4); \
                    329:        }
                    330:
                    331:     p = (word *)(hbp->hb_body);
                    332:     plim = (word *)(((word)hbp) + HBLKSIZE);
                    333:
                    334:     /* go through all words in block */
                    335:        while( p < plim )  {
                    336:            mark_word = *mark_word_addr++;
                    337:            DO_OBJ(0);
                    338:            DO_OBJ(4);
                    339:            DO_OBJ(8);
                    340:            DO_OBJ(12);
                    341:            DO_OBJ(16);
                    342:            DO_OBJ(20);
                    343:            DO_OBJ(24);
                    344:            DO_OBJ(28);
                    345: #          if CPP_WORDSZ == 64
                    346:              DO_OBJ(32);
                    347:              DO_OBJ(36);
                    348:              DO_OBJ(40);
                    349:              DO_OBJ(44);
                    350:              DO_OBJ(48);
                    351:              DO_OBJ(52);
                    352:              DO_OBJ(56);
                    353:              DO_OBJ(60);
                    354: #          endif
                    355:            p += WORDSZ;
                    356:        }
                    357: #   ifdef GATHERSTATS
                    358:        GC_mem_found += n_words_found;
                    359: #   endif
                    360:     return(list);
                    361: #   undef DO_OBJ
                    362: }
                    363:
                    364: #endif /* !SMALL_CONFIG */
                    365:
                    366: /* The same thing, but don't clear objects: */
                    367: /*ARGSUSED*/
1.2       noro      368: ptr_t GC_reclaim_uninit(hbp, hhdr, sz, list)
1.1       noro      369: register struct hblk *hbp;     /* ptr to current heap block            */
                    370: register hdr * hhdr;
                    371: register ptr_t list;
                    372: register word sz;
                    373: {
                    374:     register int word_no;
                    375:     register word *p, *plim;
                    376: #   ifdef GATHERSTATS
                    377:         register int n_words_found = 0;
                    378: #   endif
                    379:
                    380:     p = (word *)(hbp->hb_body);
                    381:     word_no = HDR_WORDS;
                    382:     plim = (word *)((((word)hbp) + HBLKSIZE)
                    383:                   - WORDS_TO_BYTES(sz));
                    384:
                    385:     /* go through all words in block */
                    386:        while( p <= plim )  {
                    387:            if( !mark_bit_from_hdr(hhdr, word_no) ) {
                    388:                INCR_WORDS(sz);
                    389:                /* object is available - put on list */
                    390:                    obj_link(p) = list;
                    391:                    list = ((ptr_t)p);
                    392:            }
                    393:            p += sz;
                    394:            word_no += sz;
                    395:        }
                    396: #   ifdef GATHERSTATS
                    397:        GC_mem_found += n_words_found;
                    398: #   endif
                    399:     return(list);
                    400: }
                    401:
1.2       noro      402: /* Don't really reclaim objects, just check for unmarked ones: */
                    403: /*ARGSUSED*/
                    404: void GC_reclaim_check(hbp, hhdr, sz)
                    405: register struct hblk *hbp;     /* ptr to current heap block            */
                    406: register hdr * hhdr;
                    407: register word sz;
                    408: {
                    409:     register int word_no;
                    410:     register word *p, *plim;
                    411: #   ifdef GATHERSTATS
                    412:         register int n_words_found = 0;
                    413: #   endif
                    414:
                    415:     p = (word *)(hbp->hb_body);
                    416:     word_no = HDR_WORDS;
                    417:     plim = (word *)((((word)hbp) + HBLKSIZE)
                    418:                   - WORDS_TO_BYTES(sz));
                    419:
                    420:     /* go through all words in block */
                    421:        while( p <= plim )  {
                    422:            if( !mark_bit_from_hdr(hhdr, word_no) ) {
                    423:                FOUND_FREE(hbp, word_no);
                    424:            }
                    425:            p += sz;
                    426:            word_no += sz;
                    427:        }
                    428: }
                    429:
1.1       noro      430: #ifndef SMALL_CONFIG
                    431: /*
                    432:  * Another special case for 2 word atomic objects:
                    433:  */
                    434: /*ARGSUSED*/
1.2       noro      435: ptr_t GC_reclaim_uninit2(hbp, hhdr, list)
1.1       noro      436: register struct hblk *hbp;     /* ptr to current heap block            */
                    437: hdr * hhdr;
                    438: register ptr_t list;
                    439: {
                    440:     register word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
                    441:     register word *p, *plim;
                    442: #   ifdef GATHERSTATS
                    443:         register int n_words_found = 0;
                    444: #   endif
                    445:     register word mark_word;
                    446:     register int i;
                    447: #   define DO_OBJ(start_displ) \
                    448:        if (!(mark_word & ((word)1 << start_displ))) { \
                    449:            p[start_displ] = (word)list; \
                    450:            list = (ptr_t)(p+start_displ); \
                    451:            INCR_WORDS(2); \
                    452:        }
                    453:
                    454:     p = (word *)(hbp->hb_body);
                    455:     plim = (word *)(((word)hbp) + HBLKSIZE);
                    456:
                    457:     /* go through all words in block */
                    458:        while( p < plim )  {
                    459:            mark_word = *mark_word_addr++;
                    460:            for (i = 0; i < WORDSZ; i += 8) {
                    461:                DO_OBJ(0);
                    462:                DO_OBJ(2);
                    463:                DO_OBJ(4);
                    464:                DO_OBJ(6);
                    465:                p += 8;
                    466:                mark_word >>= 8;
                    467:            }
                    468:        }
                    469: #   ifdef GATHERSTATS
                    470:        GC_mem_found += n_words_found;
                    471: #   endif
                    472:     return(list);
                    473: #   undef DO_OBJ
                    474: }
                    475:
                    476: /*
                    477:  * Another special case for 4 word atomic objects:
                    478:  */
                    479: /*ARGSUSED*/
1.2       noro      480: ptr_t GC_reclaim_uninit4(hbp, hhdr, list)
1.1       noro      481: register struct hblk *hbp;     /* ptr to current heap block            */
                    482: hdr * hhdr;
                    483: register ptr_t list;
                    484: {
                    485:     register word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
                    486:     register word *p, *plim;
                    487: #   ifdef GATHERSTATS
                    488:         register int n_words_found = 0;
                    489: #   endif
                    490:     register word mark_word;
                    491: #   define DO_OBJ(start_displ) \
                    492:        if (!(mark_word & ((word)1 << start_displ))) { \
                    493:            p[start_displ] = (word)list; \
                    494:            list = (ptr_t)(p+start_displ); \
                    495:            INCR_WORDS(4); \
                    496:        }
                    497:
                    498:     p = (word *)(hbp->hb_body);
                    499:     plim = (word *)(((word)hbp) + HBLKSIZE);
                    500:
                    501:     /* go through all words in block */
                    502:        while( p < plim )  {
                    503:            mark_word = *mark_word_addr++;
                    504:            DO_OBJ(0);
                    505:            DO_OBJ(4);
                    506:            DO_OBJ(8);
                    507:            DO_OBJ(12);
                    508:            DO_OBJ(16);
                    509:            DO_OBJ(20);
                    510:            DO_OBJ(24);
                    511:            DO_OBJ(28);
                    512: #          if CPP_WORDSZ == 64
                    513:              DO_OBJ(32);
                    514:              DO_OBJ(36);
                    515:              DO_OBJ(40);
                    516:              DO_OBJ(44);
                    517:              DO_OBJ(48);
                    518:              DO_OBJ(52);
                    519:              DO_OBJ(56);
                    520:              DO_OBJ(60);
                    521: #          endif
                    522:            p += WORDSZ;
                    523:        }
                    524: #   ifdef GATHERSTATS
                    525:        GC_mem_found += n_words_found;
                    526: #   endif
                    527:     return(list);
                    528: #   undef DO_OBJ
                    529: }
                    530:
                    531: /* Finally the one word case, which never requires any clearing: */
                    532: /*ARGSUSED*/
1.2       noro      533: ptr_t GC_reclaim1(hbp, hhdr, list)
1.1       noro      534: register struct hblk *hbp;     /* ptr to current heap block            */
                    535: hdr * hhdr;
                    536: register ptr_t list;
                    537: {
                    538:     register word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
                    539:     register word *p, *plim;
                    540: #   ifdef GATHERSTATS
                    541:         register int n_words_found = 0;
                    542: #   endif
                    543:     register word mark_word;
                    544:     register int i;
                    545: #   define DO_OBJ(start_displ) \
                    546:        if (!(mark_word & ((word)1 << start_displ))) { \
                    547:            p[start_displ] = (word)list; \
                    548:            list = (ptr_t)(p+start_displ); \
                    549:            INCR_WORDS(1); \
                    550:        }
                    551:
                    552:     p = (word *)(hbp->hb_body);
                    553:     plim = (word *)(((word)hbp) + HBLKSIZE);
                    554:
                    555:     /* go through all words in block */
                    556:        while( p < plim )  {
                    557:            mark_word = *mark_word_addr++;
                    558:            for (i = 0; i < WORDSZ; i += 4) {
                    559:                DO_OBJ(0);
                    560:                DO_OBJ(1);
                    561:                DO_OBJ(2);
                    562:                DO_OBJ(3);
                    563:                p += 4;
                    564:                mark_word >>= 4;
                    565:            }
                    566:        }
                    567: #   ifdef GATHERSTATS
                    568:        GC_mem_found += n_words_found;
                    569: #   endif
                    570:     return(list);
                    571: #   undef DO_OBJ
                    572: }
                    573:
                    574: #endif /* !SMALL_CONFIG */
                    575:
                    576: /*
                    577:  * Restore unmarked small objects in the block pointed to by hbp
                    578:  * to the appropriate object free list.
                    579:  * If entirely empty blocks are to be completely deallocated, then
                    580:  * caller should perform that check.
                    581:  */
1.2       noro      582: void GC_reclaim_small_nonempty_block(hbp, report_if_found)
1.1       noro      583: register struct hblk *hbp;     /* ptr to current heap block            */
1.2       noro      584: int report_if_found;           /* Abort if a reclaimable object is found */
1.1       noro      585: {
                    586:     hdr * hhdr;
1.2       noro      587:     word sz;           /* size of objects in current block     */
                    588:     struct obj_kind * ok;
                    589:     ptr_t * flh;
                    590:     int kind;
                    591:     GC_bool full;
1.1       noro      592:
                    593:     hhdr = HDR(hbp);
                    594:     sz = hhdr -> hb_sz;
                    595:     hhdr -> hb_last_reclaimed = (unsigned short) GC_gc_no;
                    596:     kind = hhdr -> hb_obj_kind;
                    597:     ok = &GC_obj_kinds[kind];
                    598:     flh = &(ok -> ok_freelist[sz]);
                    599:
1.2       noro      600:     if (report_if_found) {
                    601:        GC_reclaim_check(hbp, hhdr, sz);
                    602:     } else if (ok -> ok_init) {
1.1       noro      603:       switch(sz) {
                    604: #      ifndef SMALL_CONFIG
                    605:         case 1:
1.2       noro      606:            full = GC_block_nearly_full1(hhdr, 0xffffffffl);
                    607:            if (TRUE == full) goto out;
                    608:            if (FALSE == full) GC_write_hint(hbp);
                    609:            /* In the DONT_KNOW case, we let reclaim fault.     */
                    610:             *flh = GC_reclaim1(hbp, hhdr, *flh);
1.1       noro      611:             break;
                    612:         case 2:
1.2       noro      613:            full = GC_block_nearly_full1(hhdr, 0x55555555l);
                    614:            if (TRUE == full) goto out;
                    615:            if (FALSE == full) GC_write_hint(hbp);
                    616:             *flh = GC_reclaim_clear2(hbp, hhdr, *flh);
1.1       noro      617:             break;
                    618:         case 4:
1.2       noro      619:            full = GC_block_nearly_full1(hhdr, 0x11111111l);
                    620:            if (TRUE == full) goto out;
                    621:            if (FALSE == full) GC_write_hint(hbp);
                    622:             *flh = GC_reclaim_clear4(hbp, hhdr, *flh);
1.1       noro      623:             break;
                    624: #      endif
                    625:         default:
1.2       noro      626:            full = GC_block_nearly_full(hhdr);
                    627:            if (TRUE == full) goto out;
                    628:            if (FALSE == full) GC_write_hint(hbp);
                    629:             *flh = GC_reclaim_clear(hbp, hhdr, sz, *flh);
1.1       noro      630:             break;
                    631:       }
                    632:     } else {
                    633:       switch(sz) {
                    634: #      ifndef SMALL_CONFIG
                    635:         case 1:
1.2       noro      636:            full = GC_block_nearly_full1(hhdr, 0xffffffffl);
                    637:            if (TRUE == full) goto out;
                    638:            if (FALSE == full) GC_write_hint(hbp);
                    639:             *flh = GC_reclaim1(hbp, hhdr, *flh);
1.1       noro      640:             break;
                    641:         case 2:
1.2       noro      642:            full = GC_block_nearly_full1(hhdr, 0x55555555l);
                    643:            if (TRUE == full) goto out;
                    644:            if (FALSE == full) GC_write_hint(hbp);
                    645:             *flh = GC_reclaim_uninit2(hbp, hhdr, *flh);
1.1       noro      646:             break;
                    647:         case 4:
1.2       noro      648:            full = GC_block_nearly_full1(hhdr, 0x11111111l);
                    649:            if (TRUE == full) goto out;
                    650:            if (FALSE == full) GC_write_hint(hbp);
                    651:             *flh = GC_reclaim_uninit4(hbp, hhdr, *flh);
1.1       noro      652:             break;
                    653: #      endif
                    654:         default:
1.2       noro      655:            full = GC_block_nearly_full(hhdr);
                    656:            if (TRUE == full) goto out;
                    657:            if (FALSE == full) GC_write_hint(hbp);
                    658:             *flh = GC_reclaim_uninit(hbp, hhdr, sz, *flh);
1.1       noro      659:             break;
                    660:       }
                    661:     }
1.2       noro      662: out:
1.1       noro      663:     if (IS_UNCOLLECTABLE(kind)) GC_set_hdr_marks(hhdr);
                    664: }
                    665:
                    666: /*
                    667:  * Restore an unmarked large object or an entirely empty blocks of small objects
                    668:  * to the heap block free list.
                    669:  * Otherwise enqueue the block for later processing
                    670:  * by GC_reclaim_small_nonempty_block.
1.2       noro      671:  * If report_if_found is TRUE, then process any block immediately, and
                    672:  * simply report free objects; do not actually reclaim them.
1.1       noro      673:  */
1.2       noro      674: void GC_reclaim_block(hbp, report_if_found)
1.1       noro      675: register struct hblk *hbp;     /* ptr to current heap block            */
1.2       noro      676: word report_if_found;          /* Abort if a reclaimable object is found */
1.1       noro      677: {
                    678:     register hdr * hhdr;
                    679:     register word sz;          /* size of objects in current block     */
                    680:     register struct obj_kind * ok;
                    681:     struct hblk ** rlh;
                    682:
                    683:     hhdr = HDR(hbp);
                    684:     sz = hhdr -> hb_sz;
                    685:     ok = &GC_obj_kinds[hhdr -> hb_obj_kind];
                    686:
                    687:     if( sz > MAXOBJSZ ) {  /* 1 big object */
                    688:         if( !mark_bit_from_hdr(hhdr, HDR_WORDS) ) {
1.2       noro      689:            if (report_if_found) {
                    690:              FOUND_FREE(hbp, HDR_WORDS);
                    691:            } else {
                    692: #            ifdef GATHERSTATS
1.1       noro      693:                GC_mem_found += sz;
1.2       noro      694: #            endif
                    695:              GC_freehblk(hbp);
                    696:            }
1.1       noro      697:        }
                    698:     } else {
                    699:         GC_bool empty = GC_block_empty(hhdr);
1.2       noro      700:         if (report_if_found) {
                    701:          GC_reclaim_small_nonempty_block(hbp, (int)report_if_found);
1.1       noro      702:         } else if (empty) {
                    703: #        ifdef GATHERSTATS
                    704:             GC_mem_found += BYTES_TO_WORDS(HBLKSIZE);
                    705: #        endif
                    706:           GC_freehblk(hbp);
                    707:         } else {
                    708:           /* group of smaller objects, enqueue the real work */
                    709:           rlh = &(ok -> ok_reclaim_list[sz]);
                    710:           hhdr -> hb_next = *rlh;
                    711:           *rlh = hbp;
                    712:         }
                    713:     }
                    714: }
                    715:
                    716: #if !defined(NO_DEBUGGING)
                    717: /* Routines to gather and print heap block info        */
                    718: /* intended for debugging.  Otherwise should be called */
                    719: /* with lock.                                          */
                    720: static size_t number_of_blocks;
                    721: static size_t total_bytes;
                    722:
                    723: /* Number of set bits in a word.  Not performance critical.    */
                    724: static int set_bits(n)
                    725: word n;
                    726: {
                    727:     register word m = n;
                    728:     register int result = 0;
                    729:
                    730:     while (m > 0) {
                    731:        if (m & 1) result++;
                    732:        m >>= 1;
                    733:     }
                    734:     return(result);
                    735: }
                    736:
                    737: /* Return the number of set mark bits in the given header      */
                    738: int GC_n_set_marks(hhdr)
                    739: hdr * hhdr;
                    740: {
                    741:     register int result = 0;
                    742:     register int i;
                    743:
                    744:     for (i = 0; i < MARK_BITS_SZ; i++) {
                    745:         result += set_bits(hhdr -> hb_marks[i]);
                    746:     }
                    747:     return(result);
                    748: }
                    749:
                    750: /*ARGSUSED*/
                    751: void GC_print_block_descr(h, dummy)
                    752: struct hblk *h;
                    753: word dummy;
                    754: {
                    755:     register hdr * hhdr = HDR(h);
                    756:     register size_t bytes = WORDS_TO_BYTES(hhdr -> hb_sz);
                    757:
                    758:     GC_printf3("(%lu:%lu,%lu)", (unsigned long)(hhdr -> hb_obj_kind),
                    759:                                (unsigned long)bytes,
                    760:                                (unsigned long)(GC_n_set_marks(hhdr)));
                    761:     bytes += HDR_BYTES + HBLKSIZE-1;
                    762:     bytes &= ~(HBLKSIZE-1);
                    763:     total_bytes += bytes;
                    764:     number_of_blocks++;
                    765: }
                    766:
                    767: void GC_print_block_list()
                    768: {
                    769:     GC_printf0("(kind(0=ptrfree,1=normal,2=unc.,3=stubborn):size_in_bytes, #_marks_set)\n");
                    770:     number_of_blocks = 0;
                    771:     total_bytes = 0;
                    772:     GC_apply_to_all_blocks(GC_print_block_descr, (word)0);
                    773:     GC_printf2("\nblocks = %lu, bytes = %lu\n",
                    774:               (unsigned long)number_of_blocks,
                    775:               (unsigned long)total_bytes);
                    776: }
                    777:
                    778: #endif /* NO_DEBUGGING */
                    779:
                    780: /*
1.2       noro      781:  * Perform GC_reclaim_block on the entire heap, after first clearing
                    782:  * small object free lists (if we are not just looking for leaks).
1.1       noro      783:  */
1.2       noro      784: void GC_start_reclaim(report_if_found)
                    785: int report_if_found;           /* Abort if a GC_reclaimable object is found */
1.1       noro      786: {
                    787:     int kind;
                    788:
                    789:     /* Clear reclaim- and free-lists */
                    790:       for (kind = 0; kind < GC_n_kinds; kind++) {
                    791:         register ptr_t *fop;
                    792:         register ptr_t *lim;
                    793:         register struct hblk ** rlp;
                    794:         register struct hblk ** rlim;
                    795:         register struct hblk ** rlist = GC_obj_kinds[kind].ok_reclaim_list;
                    796:
                    797:         if (rlist == 0) continue;      /* This kind not used.  */
1.2       noro      798:         if (!report_if_found) {
1.1       noro      799:             lim = &(GC_obj_kinds[kind].ok_freelist[MAXOBJSZ+1]);
                    800:            for( fop = GC_obj_kinds[kind].ok_freelist; fop < lim; fop++ ) {
                    801:              *fop = 0;
                    802:            }
                    803:        } /* otherwise free list objects are marked,    */
                    804:          /* and its safe to leave them                 */
                    805:        rlim = rlist + MAXOBJSZ+1;
                    806:        for( rlp = rlist; rlp < rlim; rlp++ ) {
                    807:            *rlp = 0;
                    808:        }
                    809:       }
                    810:
                    811: #   ifdef PRINTBLOCKS
                    812:         GC_printf0("GC_reclaim: current block sizes:\n");
                    813:         GC_print_block_list();
                    814: #   endif
                    815:
                    816:   /* Go through all heap blocks (in hblklist) and reclaim unmarked objects */
                    817:   /* or enqueue the block for later processing.                                   */
1.2       noro      818:     GC_apply_to_all_blocks(GC_reclaim_block, (word)report_if_found);
1.1       noro      819:
                    820: }
                    821:
                    822: /*
                    823:  * Sweep blocks of the indicated object size and kind until either the
                    824:  * appropriate free list is nonempty, or there are no more blocks to
                    825:  * sweep.
                    826:  */
                    827: void GC_continue_reclaim(sz, kind)
                    828: word sz;       /* words */
                    829: int kind;
                    830: {
                    831:     register hdr * hhdr;
                    832:     register struct hblk * hbp;
                    833:     register struct obj_kind * ok = &(GC_obj_kinds[kind]);
                    834:     struct hblk ** rlh = ok -> ok_reclaim_list;
                    835:     ptr_t *flh = &(ok -> ok_freelist[sz]);
                    836:
                    837:     if (rlh == 0) return;      /* No blocks of this kind.      */
                    838:     rlh += sz;
1.3     ! noro      839: #if 0
1.1       noro      840:        GC_timerstart();
1.3     ! noro      841: #endif
1.1       noro      842:     while ((hbp = *rlh) != 0) {
                    843:         hhdr = HDR(hbp);
                    844:         *rlh = hhdr -> hb_next;
                    845:         GC_reclaim_small_nonempty_block(hbp, FALSE);
                    846:         if (*flh != 0) break;
                    847:     }
1.3     ! noro      848: #if 0
1.1       noro      849:        GC_timerstop();
1.3     ! noro      850: #endif
1.1       noro      851: }
                    852:
                    853: /*
                    854:  * Reclaim all small blocks waiting to be reclaimed.
                    855:  * Abort and return FALSE when/if (*stop_func)() returns TRUE.
                    856:  * If this returns TRUE, then it's safe to restart the world
                    857:  * with incorrectly cleared mark bits.
                    858:  * If ignore_old is TRUE, then reclain only blocks that have been
                    859:  * recently reclaimed, and discard the rest.
                    860:  * Stop_func may be 0.
                    861:  */
                    862: GC_bool GC_reclaim_all(stop_func, ignore_old)
                    863: GC_stop_func stop_func;
                    864: GC_bool ignore_old;
                    865: {
                    866:     register word sz;
                    867:     register int kind;
                    868:     register hdr * hhdr;
                    869:     register struct hblk * hbp;
                    870:     register struct obj_kind * ok;
                    871:     struct hblk ** rlp;
                    872:     struct hblk ** rlh;
                    873: #   ifdef PRINTTIMES
                    874:        CLOCK_TYPE start_time;
                    875:        CLOCK_TYPE done_time;
                    876:
                    877:        GET_TIME(start_time);
                    878: #   endif
                    879:
                    880:        GC_timerstart();
                    881:     for (kind = 0; kind < GC_n_kinds; kind++) {
                    882:        ok = &(GC_obj_kinds[kind]);
                    883:        rlp = ok -> ok_reclaim_list;
                    884:        if (rlp == 0) continue;
                    885:        for (sz = 1; sz <= MAXOBJSZ; sz++) {
                    886:            rlh = rlp + sz;
                    887:            while ((hbp = *rlh) != 0) {
                    888:                if (stop_func != (GC_stop_func)0 && (*stop_func)()) {
                    889:                    return(FALSE);
                    890:                }
                    891:                hhdr = HDR(hbp);
                    892:                *rlh = hhdr -> hb_next;
                    893:                if (!ignore_old || hhdr -> hb_last_reclaimed == GC_gc_no - 1) {
                    894:                    /* It's likely we'll need it this time, too */
                    895:                    /* It's been touched recently, so this      */
                    896:                    /* shouldn't trigger paging.                */
                    897:                    GC_reclaim_small_nonempty_block(hbp, FALSE);
                    898:                }
                    899:             }
                    900:         }
                    901:     }
                    902:        GC_timerstop();
                    903: #   ifdef PRINTTIMES
                    904:        GET_TIME(done_time);
                    905:        GC_printf1("Disposing of reclaim lists took %lu msecs\n",
                    906:                   MS_TIME_DIFF(done_time,start_time));
                    907: #   endif
                    908:     return(TRUE);
                    909: }

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