OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [boehm-gc/] [reclaim.c] - Blame information for rev 721

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 721 jeremybenn
/*
2
 * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
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.
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 "private/gc_priv.h"
19
 
20
signed_word GC_mem_found = 0;
21
                        /* Number of words of memory reclaimed     */
22
 
23
#if defined(PARALLEL_MARK) || defined(THREAD_LOCAL_ALLOC)
24
  word GC_fl_builder_count = 0;
25
        /* Number of threads currently building free lists without      */
26
        /* holding GC lock.  It is not safe to collect if this is       */
27
        /* nonzero.                                                     */
28
#endif /* PARALLEL_MARK */
29
 
30
/* We defer printing of leaked objects until we're done with the GC     */
31
/* cycle, since the routine for printing objects needs to run outside   */
32
/* the collector, e.g. without the allocation lock.                     */
33
#define MAX_LEAKED 40
34
ptr_t GC_leaked[MAX_LEAKED];
35
unsigned GC_n_leaked = 0;
36
 
37
GC_bool GC_have_errors = FALSE;
38
 
39
void GC_add_leaked(leaked)
40
ptr_t leaked;
41
{
42
    if (GC_n_leaked < MAX_LEAKED) {
43
      GC_have_errors = TRUE;
44
      GC_leaked[GC_n_leaked++] = leaked;
45
      /* Make sure it's not reclaimed this cycle */
46
        GC_set_mark_bit(leaked);
47
    }
48
}
49
 
50
static GC_bool printing_errors = FALSE;
51
/* Print all objects on the list after printing any smashed objs.       */
52
/* Clear both lists.                                                    */
53
void GC_print_all_errors ()
54
{
55
    unsigned i;
56
 
57
    LOCK();
58
    if (printing_errors) {
59
        UNLOCK();
60
        return;
61
    }
62
    printing_errors = TRUE;
63
    UNLOCK();
64
    if (GC_debugging_started) GC_print_all_smashed();
65
    for (i = 0; i < GC_n_leaked; ++i) {
66
        ptr_t p = GC_leaked[i];
67
        if (HDR(p) -> hb_obj_kind == PTRFREE) {
68
            GC_err_printf0("Leaked atomic object at ");
69
        } else {
70
            GC_err_printf0("Leaked composite object at ");
71
        }
72
        GC_print_heap_obj(p);
73
        GC_err_printf0("\n");
74
        GC_free(p);
75
        GC_leaked[i] = 0;
76
    }
77
    GC_n_leaked = 0;
78
    printing_errors = FALSE;
79
}
80
 
81
 
82
#   define FOUND_FREE(hblk, word_no) \
83
      { \
84
         GC_add_leaked((ptr_t)hblk + WORDS_TO_BYTES(word_no)); \
85
      }
86
 
87
/*
88
 * reclaim phase
89
 *
90
 */
91
 
92
 
93
/*
94
 * Test whether a block is completely empty, i.e. contains no marked
95
 * objects.  This does not require the block to be in physical
96
 * memory.
97
 */
98
 
99
GC_bool GC_block_empty(hhdr)
100
register hdr * hhdr;
101
{
102
    /* We treat hb_marks as an array of words here, even if it is       */
103
    /* actually an array of bytes.  Since we only check for zero, there */
104
    /* are no endian-ness issues.                                       */
105
    register word *p = (word *)(&(hhdr -> hb_marks[0]));
106
    register word * plim =
107
            (word *)(&(hhdr -> hb_marks[MARK_BITS_SZ]));
108
    while (p < plim) {
109
        if (*p++) return(FALSE);
110
    }
111
    return(TRUE);
112
}
113
 
114
/* The following functions sometimes return a DONT_KNOW value. */
115
#define DONT_KNOW  2
116
 
117
#ifdef SMALL_CONFIG
118
# define GC_block_nearly_full1(hhdr, pat1) DONT_KNOW
119
# define GC_block_nearly_full3(hhdr, pat1, pat2) DONT_KNOW
120
# define GC_block_nearly_full(hhdr) DONT_KNOW
121
#endif
122
 
123
#if !defined(SMALL_CONFIG) && defined(USE_MARK_BYTES)
124
 
125
# define GC_block_nearly_full1(hhdr, pat1) GC_block_nearly_full(hhdr)
126
# define GC_block_nearly_full3(hhdr, pat1, pat2) GC_block_nearly_full(hhdr)
127
 
128
 
129
GC_bool GC_block_nearly_full(hhdr)
130
register hdr * hhdr;
131
{
132
    /* We again treat hb_marks as an array of words, even though it     */
133
    /* isn't.  We first sum up all the words, resulting in a word       */
134
    /* containing 4 or 8 separate partial sums.                         */
135
    /* We then sum the bytes in the word of partial sums.               */
136
    /* This is still endian independant.  This fails if the partial     */
137
    /* sums can overflow.                                               */
138
#   if (BYTES_TO_WORDS(MARK_BITS_SZ)) >= 256
139
        --> potential overflow; fix the code
140
#   endif
141
    register word *p = (word *)(&(hhdr -> hb_marks[0]));
142
    register word * plim =
143
            (word *)(&(hhdr -> hb_marks[MARK_BITS_SZ]));
144
    word sum_vector = 0;
145
    unsigned sum;
146
    while (p < plim) {
147
        sum_vector += *p;
148
        ++p;
149
    }
150
    sum = 0;
151
    while (sum_vector > 0) {
152
        sum += sum_vector & 0xff;
153
        sum_vector >>= 8;
154
    }
155
    return (sum > BYTES_TO_WORDS(7*HBLKSIZE/8)/(hhdr -> hb_sz));
156
}
157
#endif  /* USE_MARK_BYTES */
158
 
159
#if !defined(SMALL_CONFIG) && !defined(USE_MARK_BYTES)
160
 
161
/*
162
 * Test whether nearly all of the mark words consist of the same
163
 * repeating pattern.
164
 */
165
#define FULL_THRESHOLD (MARK_BITS_SZ/16)
166
 
167
GC_bool GC_block_nearly_full1(hhdr, pat1)
168
hdr *hhdr;
169
word pat1;
170
{
171
    unsigned i;
172
    unsigned misses = 0;
173
    GC_ASSERT((MARK_BITS_SZ & 1) == 0);
174
    for (i = 0; i < MARK_BITS_SZ; ++i) {
175
        if ((hhdr -> hb_marks[i] | ~pat1) != ONES) {
176
            if (++misses > FULL_THRESHOLD) return FALSE;
177
        }
178
    }
179
    return TRUE;
180
}
181
 
182
/*
183
 * Test whether the same repeating 3 word pattern occurs in nearly
184
 * all the mark bit slots.
185
 * This is used as a heuristic, so we're a bit sloppy and ignore
186
 * the last one or two words.
187
 */
188
GC_bool GC_block_nearly_full3(hhdr, pat1, pat2, pat3)
189
hdr *hhdr;
190
word pat1, pat2, pat3;
191
{
192
    unsigned i;
193
    unsigned misses = 0;
194
 
195
    if (MARK_BITS_SZ < 4) {
196
      return DONT_KNOW;
197
    }
198
    for (i = 0; i < MARK_BITS_SZ - 2; i += 3) {
199
        if ((hhdr -> hb_marks[i] | ~pat1) != ONES) {
200
            if (++misses > FULL_THRESHOLD) return FALSE;
201
        }
202
        if ((hhdr -> hb_marks[i+1] | ~pat2) != ONES) {
203
            if (++misses > FULL_THRESHOLD) return FALSE;
204
        }
205
        if ((hhdr -> hb_marks[i+2] | ~pat3) != ONES) {
206
            if (++misses > FULL_THRESHOLD) return FALSE;
207
        }
208
    }
209
    return TRUE;
210
}
211
 
212
/* Check whether a small object block is nearly full by looking at only */
213
/* the mark bits.                                                       */
214
/* We manually precomputed the mark bit patterns that need to be        */
215
/* checked for, and we give up on the ones that are unlikely to occur,  */
216
/* or have period > 3.                                                  */
217
/* This would be a lot easier with a mark bit per object instead of per */
218
/* word, but that would rewuire computing object numbers in the mark    */
219
/* loop, which would require different data structures ...              */
220
GC_bool GC_block_nearly_full(hhdr)
221
hdr *hhdr;
222
{
223
    int sz = hhdr -> hb_sz;
224
 
225
#   if CPP_WORDSZ != 32 && CPP_WORDSZ != 64
226
      return DONT_KNOW; /* Shouldn't be used in any standard config.    */
227
#   endif
228
#   if CPP_WORDSZ == 32
229
      switch(sz) {
230
        case 1:
231
          return GC_block_nearly_full1(hhdr, 0xffffffffl);
232
        case 2:
233
          return GC_block_nearly_full1(hhdr, 0x55555555l);
234
        case 4:
235
          return GC_block_nearly_full1(hhdr, 0x11111111l);
236
        case 6:
237
          return GC_block_nearly_full3(hhdr, 0x41041041l,
238
                                              0x10410410l,
239
                                               0x04104104l);
240
        case 8:
241
          return GC_block_nearly_full1(hhdr, 0x01010101l);
242
        case 12:
243
          return GC_block_nearly_full3(hhdr, 0x01001001l,
244
                                              0x10010010l,
245
                                               0x00100100l);
246
        case 16:
247
          return GC_block_nearly_full1(hhdr, 0x00010001l);
248
        case 32:
249
          return GC_block_nearly_full1(hhdr, 0x00000001l);
250
        default:
251
          return DONT_KNOW;
252
      }
253
#   endif
254
#   if CPP_WORDSZ == 64
255
      switch(sz) {
256
        case 1:
257
          return GC_block_nearly_full1(hhdr, 0xffffffffffffffffl);
258
        case 2:
259
          return GC_block_nearly_full1(hhdr, 0x5555555555555555l);
260
        case 4:
261
          return GC_block_nearly_full1(hhdr, 0x1111111111111111l);
262
        case 6:
263
          return GC_block_nearly_full3(hhdr, 0x1041041041041041l,
264
                                               0x4104104104104104l,
265
                                                 0x0410410410410410l);
266
        case 8:
267
          return GC_block_nearly_full1(hhdr, 0x0101010101010101l);
268
        case 12:
269
          return GC_block_nearly_full3(hhdr, 0x1001001001001001l,
270
                                               0x0100100100100100l,
271
                                                 0x0010010010010010l);
272
        case 16:
273
          return GC_block_nearly_full1(hhdr, 0x0001000100010001l);
274
        case 32:
275
          return GC_block_nearly_full1(hhdr, 0x0000000100000001l);
276
        default:
277
          return DONT_KNOW;
278
      }
279
#   endif
280
}
281
#endif /* !SMALL_CONFIG  && !USE_MARK_BYTES */
282
 
283
/* We keep track of reclaimed memory if we are either asked to, or      */
284
/* we are using the parallel marker.  In the latter case, we assume     */
285
/* that most allocation goes through GC_malloc_many for scalability.    */
286
/* GC_malloc_many needs the count anyway.                               */
287
# if defined(GATHERSTATS) || defined(PARALLEL_MARK)
288
#   define INCR_WORDS(sz) n_words_found += (sz)
289
#   define COUNT_PARAM , count
290
#   define COUNT_ARG , count
291
#   define COUNT_DECL signed_word * count;
292
#   define NWORDS_DECL signed_word n_words_found = 0;
293
#   define COUNT_UPDATE *count += n_words_found;
294
#   define MEM_FOUND_ADDR , &GC_mem_found
295
# else
296
#   define INCR_WORDS(sz)
297
#   define COUNT_PARAM
298
#   define COUNT_ARG
299
#   define COUNT_DECL
300
#   define NWORDS_DECL
301
#   define COUNT_UPDATE
302
#   define MEM_FOUND_ADDR
303
# endif
304
/*
305
 * Restore unmarked small objects in h of size sz to the object
306
 * free list.  Returns the new list.
307
 * Clears unmarked objects.
308
 */
309
/*ARGSUSED*/
310
ptr_t GC_reclaim_clear(hbp, hhdr, sz, list COUNT_PARAM)
311
register struct hblk *hbp;      /* ptr to current heap block            */
312
register hdr * hhdr;
313
register ptr_t list;
314
register word sz;
315
COUNT_DECL
316
{
317
    register int word_no;
318
    register word *p, *q, *plim;
319
    NWORDS_DECL
320
 
321
    GC_ASSERT(hhdr == GC_find_header((ptr_t)hbp));
322
    p = (word *)(hbp->hb_body);
323
    word_no = 0;
324
    plim = (word *)((((word)hbp) + HBLKSIZE)
325
                   - WORDS_TO_BYTES(sz));
326
 
327
    /* go through all words in block */
328
        while( p <= plim )  {
329
            if( mark_bit_from_hdr(hhdr, word_no) ) {
330
                p += sz;
331
            } else {
332
                INCR_WORDS(sz);
333
                /* object is available - put on list */
334
                    obj_link(p) = list;
335
                    list = ((ptr_t)p);
336
                /* Clear object, advance p to next object in the process */
337
                    q = p + sz;
338
#                   ifdef USE_MARK_BYTES
339
                      GC_ASSERT(!(sz & 1)
340
                                && !((word)p & (2 * sizeof(word) - 1)));
341
                      p[1] = 0;
342
                      p += 2;
343
                      while (p < q) {
344
                        CLEAR_DOUBLE(p);
345
                        p += 2;
346
                      }
347
#                   else
348
                      p++; /* Skip link field */
349
                      while (p < q) {
350
                        *p++ = 0;
351
                      }
352
#                   endif
353
            }
354
            word_no += sz;
355
        }
356
    COUNT_UPDATE
357
    return(list);
358
}
359
 
360
#if !defined(SMALL_CONFIG) && !defined(USE_MARK_BYTES)
361
 
362
/*
363
 * A special case for 2 word composite objects (e.g. cons cells):
364
 */
365
/*ARGSUSED*/
366
ptr_t GC_reclaim_clear2(hbp, hhdr, list COUNT_PARAM)
367
register struct hblk *hbp;      /* ptr to current heap block            */
368
hdr * hhdr;
369
register ptr_t list;
370
COUNT_DECL
371
{
372
    register word * mark_word_addr = &(hhdr->hb_marks[0]);
373
    register word *p, *plim;
374
    register word mark_word;
375
    register int i;
376
    NWORDS_DECL
377
#   define DO_OBJ(start_displ) \
378
        if (!(mark_word & ((word)1 << start_displ))) { \
379
            p[start_displ] = (word)list; \
380
            list = (ptr_t)(p+start_displ); \
381
            p[start_displ+1] = 0; \
382
            INCR_WORDS(2); \
383
        }
384
 
385
    p = (word *)(hbp->hb_body);
386
    plim = (word *)(((word)hbp) + HBLKSIZE);
387
 
388
    /* go through all words in block */
389
        while( p < plim )  {
390
            mark_word = *mark_word_addr++;
391
            for (i = 0; i < WORDSZ; i += 8) {
392
                DO_OBJ(0);
393
                DO_OBJ(2);
394
                DO_OBJ(4);
395
                DO_OBJ(6);
396
                p += 8;
397
                mark_word >>= 8;
398
            }
399
        }
400
    COUNT_UPDATE
401
    return(list);
402
#   undef DO_OBJ
403
}
404
 
405
/*
406
 * Another special case for 4 word composite objects:
407
 */
408
/*ARGSUSED*/
409
ptr_t GC_reclaim_clear4(hbp, hhdr, list COUNT_PARAM)
410
register struct hblk *hbp;      /* ptr to current heap block            */
411
hdr * hhdr;
412
register ptr_t list;
413
COUNT_DECL
414
{
415
    register word * mark_word_addr = &(hhdr->hb_marks[0]);
416
    register word *p, *plim;
417
    register word mark_word;
418
    NWORDS_DECL
419
#   define DO_OBJ(start_displ) \
420
        if (!(mark_word & ((word)1 << start_displ))) { \
421
            p[start_displ] = (word)list; \
422
            list = (ptr_t)(p+start_displ); \
423
            p[start_displ+1] = 0; \
424
            CLEAR_DOUBLE(p + start_displ + 2); \
425
            INCR_WORDS(4); \
426
        }
427
 
428
    p = (word *)(hbp->hb_body);
429
    plim = (word *)(((word)hbp) + HBLKSIZE);
430
 
431
    /* go through all words in block */
432
        while( p < plim )  {
433
            mark_word = *mark_word_addr++;
434
            DO_OBJ(0);
435
            DO_OBJ(4);
436
            DO_OBJ(8);
437
            DO_OBJ(12);
438
            DO_OBJ(16);
439
            DO_OBJ(20);
440
            DO_OBJ(24);
441
            DO_OBJ(28);
442
#           if CPP_WORDSZ == 64
443
              DO_OBJ(32);
444
              DO_OBJ(36);
445
              DO_OBJ(40);
446
              DO_OBJ(44);
447
              DO_OBJ(48);
448
              DO_OBJ(52);
449
              DO_OBJ(56);
450
              DO_OBJ(60);
451
#           endif
452
            p += WORDSZ;
453
        }
454
    COUNT_UPDATE
455
    return(list);
456
#   undef DO_OBJ
457
}
458
 
459
#endif /* !SMALL_CONFIG && !USE_MARK_BYTES */
460
 
461
/* The same thing, but don't clear objects: */
462
/*ARGSUSED*/
463
ptr_t GC_reclaim_uninit(hbp, hhdr, sz, list COUNT_PARAM)
464
register struct hblk *hbp;      /* ptr to current heap block            */
465
register hdr * hhdr;
466
register ptr_t list;
467
register word sz;
468
COUNT_DECL
469
{
470
    register int word_no = 0;
471
    register word *p, *plim;
472
    NWORDS_DECL
473
 
474
    p = (word *)(hbp->hb_body);
475
    plim = (word *)((((word)hbp) + HBLKSIZE)
476
                   - WORDS_TO_BYTES(sz));
477
 
478
    /* go through all words in block */
479
        while( p <= plim )  {
480
            if( !mark_bit_from_hdr(hhdr, word_no) ) {
481
                INCR_WORDS(sz);
482
                /* object is available - put on list */
483
                    obj_link(p) = list;
484
                    list = ((ptr_t)p);
485
            }
486
            p += sz;
487
            word_no += sz;
488
        }
489
    COUNT_UPDATE
490
    return(list);
491
}
492
 
493
/* Don't really reclaim objects, just check for unmarked ones: */
494
/*ARGSUSED*/
495
void GC_reclaim_check(hbp, hhdr, sz)
496
register struct hblk *hbp;      /* ptr to current heap block            */
497
register hdr * hhdr;
498
register word sz;
499
{
500
    register int word_no = 0;
501
    register word *p, *plim;
502
#   ifdef GATHERSTATS
503
        register int n_words_found = 0;
504
#   endif
505
 
506
    p = (word *)(hbp->hb_body);
507
    plim = (word *)((((word)hbp) + HBLKSIZE)
508
                   - WORDS_TO_BYTES(sz));
509
 
510
    /* go through all words in block */
511
        while( p <= plim )  {
512
            if( !mark_bit_from_hdr(hhdr, word_no) ) {
513
                FOUND_FREE(hbp, word_no);
514
            }
515
            p += sz;
516
            word_no += sz;
517
        }
518
}
519
 
520
#if !defined(SMALL_CONFIG) && !defined(USE_MARK_BYTES)
521
/*
522
 * Another special case for 2 word atomic objects:
523
 */
524
/*ARGSUSED*/
525
ptr_t GC_reclaim_uninit2(hbp, hhdr, list COUNT_PARAM)
526
register struct hblk *hbp;      /* ptr to current heap block            */
527
hdr * hhdr;
528
register ptr_t list;
529
COUNT_DECL
530
{
531
    register word * mark_word_addr = &(hhdr->hb_marks[0]);
532
    register word *p, *plim;
533
    register word mark_word;
534
    register int i;
535
    NWORDS_DECL
536
#   define DO_OBJ(start_displ) \
537
        if (!(mark_word & ((word)1 << start_displ))) { \
538
            p[start_displ] = (word)list; \
539
            list = (ptr_t)(p+start_displ); \
540
            INCR_WORDS(2); \
541
        }
542
 
543
    p = (word *)(hbp->hb_body);
544
    plim = (word *)(((word)hbp) + HBLKSIZE);
545
 
546
    /* go through all words in block */
547
        while( p < plim )  {
548
            mark_word = *mark_word_addr++;
549
            for (i = 0; i < WORDSZ; i += 8) {
550
                DO_OBJ(0);
551
                DO_OBJ(2);
552
                DO_OBJ(4);
553
                DO_OBJ(6);
554
                p += 8;
555
                mark_word >>= 8;
556
            }
557
        }
558
    COUNT_UPDATE
559
    return(list);
560
#   undef DO_OBJ
561
}
562
 
563
/*
564
 * Another special case for 4 word atomic objects:
565
 */
566
/*ARGSUSED*/
567
ptr_t GC_reclaim_uninit4(hbp, hhdr, list COUNT_PARAM)
568
register struct hblk *hbp;      /* ptr to current heap block            */
569
hdr * hhdr;
570
register ptr_t list;
571
COUNT_DECL
572
{
573
    register word * mark_word_addr = &(hhdr->hb_marks[0]);
574
    register word *p, *plim;
575
    register word mark_word;
576
    NWORDS_DECL
577
#   define DO_OBJ(start_displ) \
578
        if (!(mark_word & ((word)1 << start_displ))) { \
579
            p[start_displ] = (word)list; \
580
            list = (ptr_t)(p+start_displ); \
581
            INCR_WORDS(4); \
582
        }
583
 
584
    p = (word *)(hbp->hb_body);
585
    plim = (word *)(((word)hbp) + HBLKSIZE);
586
 
587
    /* go through all words in block */
588
        while( p < plim )  {
589
            mark_word = *mark_word_addr++;
590
            DO_OBJ(0);
591
            DO_OBJ(4);
592
            DO_OBJ(8);
593
            DO_OBJ(12);
594
            DO_OBJ(16);
595
            DO_OBJ(20);
596
            DO_OBJ(24);
597
            DO_OBJ(28);
598
#           if CPP_WORDSZ == 64
599
              DO_OBJ(32);
600
              DO_OBJ(36);
601
              DO_OBJ(40);
602
              DO_OBJ(44);
603
              DO_OBJ(48);
604
              DO_OBJ(52);
605
              DO_OBJ(56);
606
              DO_OBJ(60);
607
#           endif
608
            p += WORDSZ;
609
        }
610
    COUNT_UPDATE
611
    return(list);
612
#   undef DO_OBJ
613
}
614
 
615
/* Finally the one word case, which never requires any clearing: */
616
/*ARGSUSED*/
617
ptr_t GC_reclaim1(hbp, hhdr, list COUNT_PARAM)
618
register struct hblk *hbp;      /* ptr to current heap block            */
619
hdr * hhdr;
620
register ptr_t list;
621
COUNT_DECL
622
{
623
    register word * mark_word_addr = &(hhdr->hb_marks[0]);
624
    register word *p, *plim;
625
    register word mark_word;
626
    register int i;
627
    NWORDS_DECL
628
#   define DO_OBJ(start_displ) \
629
        if (!(mark_word & ((word)1 << start_displ))) { \
630
            p[start_displ] = (word)list; \
631
            list = (ptr_t)(p+start_displ); \
632
            INCR_WORDS(1); \
633
        }
634
 
635
    p = (word *)(hbp->hb_body);
636
    plim = (word *)(((word)hbp) + HBLKSIZE);
637
 
638
    /* go through all words in block */
639
        while( p < plim )  {
640
            mark_word = *mark_word_addr++;
641
            for (i = 0; i < WORDSZ; i += 4) {
642
                DO_OBJ(0);
643
                DO_OBJ(1);
644
                DO_OBJ(2);
645
                DO_OBJ(3);
646
                p += 4;
647
                mark_word >>= 4;
648
            }
649
        }
650
    COUNT_UPDATE
651
    return(list);
652
#   undef DO_OBJ
653
}
654
 
655
#endif /* !SMALL_CONFIG && !USE_MARK_BYTES */
656
 
657
/*
658
 * Generic procedure to rebuild a free list in hbp.
659
 * Also called directly from GC_malloc_many.
660
 */
661
ptr_t GC_reclaim_generic(hbp, hhdr, sz, init, list COUNT_PARAM)
662
struct hblk *hbp;       /* ptr to current heap block            */
663
hdr * hhdr;
664
GC_bool init;
665
ptr_t list;
666
word sz;
667
COUNT_DECL
668
{
669
    ptr_t result = list;
670
 
671
    GC_ASSERT(GC_find_header((ptr_t)hbp) == hhdr);
672
    GC_remove_protection(hbp, 1, (hhdr)->hb_descr == 0 /* Pointer-free? */);
673
    if (init) {
674
      switch(sz) {
675
#      if !defined(SMALL_CONFIG) && !defined(USE_MARK_BYTES)
676
        case 1:
677
            /* We now issue the hint even if GC_nearly_full returned    */
678
            /* DONT_KNOW.                                               */
679
            result = GC_reclaim1(hbp, hhdr, list COUNT_ARG);
680
            break;
681
        case 2:
682
            result = GC_reclaim_clear2(hbp, hhdr, list COUNT_ARG);
683
            break;
684
        case 4:
685
            result = GC_reclaim_clear4(hbp, hhdr, list COUNT_ARG);
686
            break;
687
#      endif /* !SMALL_CONFIG && !USE_MARK_BYTES */
688
        default:
689
            result = GC_reclaim_clear(hbp, hhdr, sz, list COUNT_ARG);
690
            break;
691
      }
692
    } else {
693
      GC_ASSERT((hhdr)->hb_descr == 0 /* Pointer-free block */);
694
      switch(sz) {
695
#      if !defined(SMALL_CONFIG) && !defined(USE_MARK_BYTES)
696
        case 1:
697
            result = GC_reclaim1(hbp, hhdr, list COUNT_ARG);
698
            break;
699
        case 2:
700
            result = GC_reclaim_uninit2(hbp, hhdr, list COUNT_ARG);
701
            break;
702
        case 4:
703
            result = GC_reclaim_uninit4(hbp, hhdr, list COUNT_ARG);
704
            break;
705
#      endif /* !SMALL_CONFIG && !USE_MARK_BYTES */
706
        default:
707
            result = GC_reclaim_uninit(hbp, hhdr, sz, list COUNT_ARG);
708
            break;
709
      }
710
    }
711
    if (IS_UNCOLLECTABLE(hhdr -> hb_obj_kind)) GC_set_hdr_marks(hhdr);
712
    return result;
713
}
714
 
715
/*
716
 * Restore unmarked small objects in the block pointed to by hbp
717
 * to the appropriate object free list.
718
 * If entirely empty blocks are to be completely deallocated, then
719
 * caller should perform that check.
720
 */
721
void GC_reclaim_small_nonempty_block(hbp, report_if_found COUNT_PARAM)
722
register struct hblk *hbp;      /* ptr to current heap block            */
723
int report_if_found;            /* Abort if a reclaimable object is found */
724
COUNT_DECL
725
{
726
    hdr *hhdr = HDR(hbp);
727
    word sz = hhdr -> hb_sz;
728
    int kind = hhdr -> hb_obj_kind;
729
    struct obj_kind * ok = &GC_obj_kinds[kind];
730
    ptr_t * flh = &(ok -> ok_freelist[sz]);
731
 
732
    hhdr -> hb_last_reclaimed = (unsigned short) GC_gc_no;
733
 
734
    if (report_if_found) {
735
        GC_reclaim_check(hbp, hhdr, sz);
736
    } else {
737
        *flh = GC_reclaim_generic(hbp, hhdr, sz,
738
                                  (ok -> ok_init || GC_debugging_started),
739
                                  *flh MEM_FOUND_ADDR);
740
    }
741
}
742
 
743
/*
744
 * Restore an unmarked large object or an entirely empty blocks of small objects
745
 * to the heap block free list.
746
 * Otherwise enqueue the block for later processing
747
 * by GC_reclaim_small_nonempty_block.
748
 * If report_if_found is TRUE, then process any block immediately, and
749
 * simply report free objects; do not actually reclaim them.
750
 */
751
# if defined(__STDC__) || defined(__cplusplus)
752
    void GC_reclaim_block(register struct hblk *hbp, word report_if_found)
753
# else
754
    void GC_reclaim_block(hbp, report_if_found)
755
    register struct hblk *hbp;  /* ptr to current heap block            */
756
    word report_if_found;       /* Abort if a reclaimable object is found */
757
# endif
758
{
759
    register hdr * hhdr;
760
    register word sz;           /* size of objects in current block     */
761
    register struct obj_kind * ok;
762
    struct hblk ** rlh;
763
 
764
    hhdr = HDR(hbp);
765
    sz = hhdr -> hb_sz;
766
    ok = &GC_obj_kinds[hhdr -> hb_obj_kind];
767
 
768
    if( sz > MAXOBJSZ ) {  /* 1 big object */
769
        if( !mark_bit_from_hdr(hhdr, 0) ) {
770
            if (report_if_found) {
771
              FOUND_FREE(hbp, 0);
772
            } else {
773
              word blocks = OBJ_SZ_TO_BLOCKS(sz);
774
              if (blocks > 1) {
775
                GC_large_allocd_bytes -= blocks * HBLKSIZE;
776
              }
777
#             ifdef GATHERSTATS
778
                GC_mem_found += sz;
779
#             endif
780
              GC_freehblk(hbp);
781
            }
782
        }
783
    } else {
784
        GC_bool empty = GC_block_empty(hhdr);
785
        if (report_if_found) {
786
          GC_reclaim_small_nonempty_block(hbp, (int)report_if_found
787
                                          MEM_FOUND_ADDR);
788
        } else if (empty) {
789
#         ifdef GATHERSTATS
790
            GC_mem_found += BYTES_TO_WORDS(HBLKSIZE);
791
#         endif
792
          GC_freehblk(hbp);
793
        } else if (TRUE != GC_block_nearly_full(hhdr)){
794
          /* group of smaller objects, enqueue the real work */
795
          rlh = &(ok -> ok_reclaim_list[sz]);
796
          hhdr -> hb_next = *rlh;
797
          *rlh = hbp;
798
        } /* else not worth salvaging. */
799
        /* We used to do the nearly_full check later, but we    */
800
        /* already have the right cache context here.  Also     */
801
        /* doing it here avoids some silly lock contention in   */
802
        /* GC_malloc_many.                                      */
803
    }
804
}
805
 
806
#if !defined(NO_DEBUGGING)
807
/* Routines to gather and print heap block info         */
808
/* intended for debugging.  Otherwise should be called  */
809
/* with lock.                                           */
810
 
811
struct Print_stats
812
{
813
        size_t number_of_blocks;
814
        size_t total_bytes;
815
};
816
 
817
#ifdef USE_MARK_BYTES
818
 
819
/* Return the number of set mark bits in the given header       */
820
int GC_n_set_marks(hhdr)
821
hdr * hhdr;
822
{
823
    register int result = 0;
824
    register int i;
825
 
826
    for (i = 0; i < MARK_BITS_SZ; i++) {
827
        result += hhdr -> hb_marks[i];
828
    }
829
    return(result);
830
}
831
 
832
#else
833
 
834
/* Number of set bits in a word.  Not performance critical.     */
835
static int set_bits(n)
836
word n;
837
{
838
    register word m = n;
839
    register int result = 0;
840
 
841
    while (m > 0) {
842
        if (m & 1) result++;
843
        m >>= 1;
844
    }
845
    return(result);
846
}
847
 
848
/* Return the number of set mark bits in the given header       */
849
int GC_n_set_marks(hhdr)
850
hdr * hhdr;
851
{
852
    register int result = 0;
853
    register int i;
854
 
855
    for (i = 0; i < MARK_BITS_SZ; i++) {
856
        result += set_bits(hhdr -> hb_marks[i]);
857
    }
858
    return(result);
859
}
860
 
861
#endif /* !USE_MARK_BYTES  */
862
 
863
/*ARGSUSED*/
864
# if defined(__STDC__) || defined(__cplusplus)
865
    void GC_print_block_descr(struct hblk *h, word dummy)
866
# else
867
    void GC_print_block_descr(h, dummy)
868
    struct hblk *h;
869
    word dummy;
870
# endif
871
{
872
    register hdr * hhdr = HDR(h);
873
    register size_t bytes = WORDS_TO_BYTES(hhdr -> hb_sz);
874
    struct Print_stats *ps;
875
 
876
    GC_printf3("(%lu:%lu,%lu)", (unsigned long)(hhdr -> hb_obj_kind),
877
                                (unsigned long)bytes,
878
                                (unsigned long)(GC_n_set_marks(hhdr)));
879
    bytes += HBLKSIZE-1;
880
    bytes &= ~(HBLKSIZE-1);
881
 
882
    ps = (struct Print_stats *)dummy;
883
    ps->total_bytes += bytes;
884
    ps->number_of_blocks++;
885
}
886
 
887
void GC_print_block_list()
888
{
889
    struct Print_stats pstats;
890
 
891
    GC_printf1("(kind(0=ptrfree,1=normal,2=unc.,%lu=stubborn):size_in_bytes, #_marks_set)\n", STUBBORN);
892
    pstats.number_of_blocks = 0;
893
    pstats.total_bytes = 0;
894
    GC_apply_to_all_blocks(GC_print_block_descr, (word)&pstats);
895
    GC_printf2("\nblocks = %lu, bytes = %lu\n",
896
               (unsigned long)pstats.number_of_blocks,
897
               (unsigned long)pstats.total_bytes);
898
}
899
 
900
#endif /* NO_DEBUGGING */
901
 
902
/*
903
 * Clear all obj_link pointers in the list of free objects *flp.
904
 * Clear *flp.
905
 * This must be done before dropping a list of free gcj-style objects,
906
 * since may otherwise end up with dangling "descriptor" pointers.
907
 * It may help for other pointer-containing objects.
908
 */
909
void GC_clear_fl_links(flp)
910
ptr_t *flp;
911
{
912
    ptr_t next = *flp;
913
 
914
    while (0 != next) {
915
       *flp = 0;
916
       flp = &(obj_link(next));
917
       next = *flp;
918
    }
919
}
920
 
921
/*
922
 * Perform GC_reclaim_block on the entire heap, after first clearing
923
 * small object free lists (if we are not just looking for leaks).
924
 */
925
void GC_start_reclaim(report_if_found)
926
int report_if_found;            /* Abort if a GC_reclaimable object is found */
927
{
928
    int kind;
929
 
930
#   if defined(PARALLEL_MARK) || defined(THREAD_LOCAL_ALLOC)
931
      GC_ASSERT(0 == GC_fl_builder_count);
932
#   endif
933
    /* Clear reclaim- and free-lists */
934
      for (kind = 0; kind < GC_n_kinds; kind++) {
935
        ptr_t *fop;
936
        ptr_t *lim;
937
        struct hblk ** rlp;
938
        struct hblk ** rlim;
939
        struct hblk ** rlist = GC_obj_kinds[kind].ok_reclaim_list;
940
        GC_bool should_clobber = (GC_obj_kinds[kind].ok_descriptor != 0);
941
 
942
        if (rlist == 0) continue;        /* This kind not used.  */
943
        if (!report_if_found) {
944
            lim = &(GC_obj_kinds[kind].ok_freelist[MAXOBJSZ+1]);
945
            for( fop = GC_obj_kinds[kind].ok_freelist; fop < lim; fop++ ) {
946
              if (*fop != 0) {
947
                if (should_clobber) {
948
                  GC_clear_fl_links(fop);
949
                } else {
950
                  *fop = 0;
951
                }
952
              }
953
            }
954
        } /* otherwise free list objects are marked,    */
955
          /* and its safe to leave them                 */
956
        rlim = rlist + MAXOBJSZ+1;
957
        for( rlp = rlist; rlp < rlim; rlp++ ) {
958
            *rlp = 0;
959
        }
960
      }
961
 
962
#   ifdef PRINTBLOCKS
963
        GC_printf0("GC_reclaim: current block sizes:\n");
964
        GC_print_block_list();
965
#   endif
966
 
967
  /* Go through all heap blocks (in hblklist) and reclaim unmarked objects */
968
  /* or enqueue the block for later processing.                            */
969
    GC_apply_to_all_blocks(GC_reclaim_block, (word)report_if_found);
970
 
971
# ifdef EAGER_SWEEP
972
    /* This is a very stupid thing to do.  We make it possible anyway,  */
973
    /* so that you can convince yourself that it really is very stupid. */
974
    GC_reclaim_all((GC_stop_func)0, FALSE);
975
# endif
976
# if defined(PARALLEL_MARK) || defined(THREAD_LOCAL_ALLOC)
977
    GC_ASSERT(0 == GC_fl_builder_count);
978
# endif
979
 
980
}
981
 
982
/*
983
 * Sweep blocks of the indicated object size and kind until either the
984
 * appropriate free list is nonempty, or there are no more blocks to
985
 * sweep.
986
 */
987
void GC_continue_reclaim(sz, kind)
988
word sz;        /* words */
989
int kind;
990
{
991
    register hdr * hhdr;
992
    register struct hblk * hbp;
993
    register struct obj_kind * ok = &(GC_obj_kinds[kind]);
994
    struct hblk ** rlh = ok -> ok_reclaim_list;
995
    ptr_t *flh = &(ok -> ok_freelist[sz]);
996
 
997
    if (rlh == 0) return;        /* No blocks of this kind.      */
998
    rlh += sz;
999
    while ((hbp = *rlh) != 0) {
1000
        hhdr = HDR(hbp);
1001
        *rlh = hhdr -> hb_next;
1002
        GC_reclaim_small_nonempty_block(hbp, FALSE MEM_FOUND_ADDR);
1003
        if (*flh != 0) break;
1004
    }
1005
}
1006
 
1007
/*
1008
 * Reclaim all small blocks waiting to be reclaimed.
1009
 * Abort and return FALSE when/if (*stop_func)() returns TRUE.
1010
 * If this returns TRUE, then it's safe to restart the world
1011
 * with incorrectly cleared mark bits.
1012
 * If ignore_old is TRUE, then reclaim only blocks that have been
1013
 * recently reclaimed, and discard the rest.
1014
 * Stop_func may be 0.
1015
 */
1016
GC_bool GC_reclaim_all(stop_func, ignore_old)
1017
GC_stop_func stop_func;
1018
GC_bool ignore_old;
1019
{
1020
    register word sz;
1021
    register int kind;
1022
    register hdr * hhdr;
1023
    register struct hblk * hbp;
1024
    register struct obj_kind * ok;
1025
    struct hblk ** rlp;
1026
    struct hblk ** rlh;
1027
#   ifdef PRINTTIMES
1028
        CLOCK_TYPE start_time;
1029
        CLOCK_TYPE done_time;
1030
 
1031
        GET_TIME(start_time);
1032
#   endif
1033
 
1034
    for (kind = 0; kind < GC_n_kinds; kind++) {
1035
        ok = &(GC_obj_kinds[kind]);
1036
        rlp = ok -> ok_reclaim_list;
1037
        if (rlp == 0) continue;
1038
        for (sz = 1; sz <= MAXOBJSZ; sz++) {
1039
            rlh = rlp + sz;
1040
            while ((hbp = *rlh) != 0) {
1041
                if (stop_func != (GC_stop_func)0 && (*stop_func)()) {
1042
                    return(FALSE);
1043
                }
1044
                hhdr = HDR(hbp);
1045
                *rlh = hhdr -> hb_next;
1046
                if (!ignore_old || hhdr -> hb_last_reclaimed == GC_gc_no - 1) {
1047
                    /* It's likely we'll need it this time, too */
1048
                    /* It's been touched recently, so this      */
1049
                    /* shouldn't trigger paging.                */
1050
                    GC_reclaim_small_nonempty_block(hbp, FALSE MEM_FOUND_ADDR);
1051
                }
1052
            }
1053
        }
1054
    }
1055
#   ifdef PRINTTIMES
1056
        GET_TIME(done_time);
1057
        GC_printf1("Disposing of reclaim lists took %lu msecs\n",
1058
                   MS_TIME_DIFF(done_time,start_time));
1059
#   endif
1060
    return(TRUE);
1061
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.