← Back to branch summary

~ubuntu-branches/ubuntu/precise/kompozer/precise

« back to all changes in this revision

Viewing changes to mozilla/gc/boehm/alloc.c

  • Committer: Bazaar Package Importer
  • Author(s): Anthony Yarusso
  • Date: 2007-08-27 01:11:03 UTC
  • Revision ID: james.westby@ubuntu.com-20070827011103-2jgf4s6532gqu2ka
Tags: upstream-0.7.10
Import upstream version 0.7.10

Show diffs side-by-side

added added

removed removed

Lines of Context:
mozilla/gc/boehm/alloc.c
 
1
/*
 
2
 * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
 
3
 * Copyright (c) 1991-1994 by Xerox Corporation.  All rights reserved.
 
4
 * Copyright (c) 1998 by Silicon Graphics.  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 "gc_priv.h"
 
19
 
 
20
# include <stdio.h>
 
21
# ifndef MACOS
 
22
#   include <signal.h>
 
23
#   include <sys/types.h>
 
24
# endif
 
25
 
 
26
/*
 
27
 * Separate free lists are maintained for different sized objects
 
28
 * up to MAXOBJSZ.
 
29
 * The call GC_allocobj(i,k) ensures that the freelist for
 
30
 * kind k objects of size i points to a non-empty
 
31
 * free list. It returns a pointer to the first entry on the free list.
 
32
 * In a single-threaded world, GC_allocobj may be called to allocate
 
33
 * an object of (small) size i as follows:
 
34
 *
 
35
 *            opp = &(GC_objfreelist[i]);
 
36
 *            if (*opp == 0) GC_allocobj(i, NORMAL);
 
37
 *            ptr = *opp;
 
38
 *            *opp = obj_link(ptr);
 
39
 *
 
40
 * Note that this is very fast if the free list is non-empty; it should
 
41
 * only involve the execution of 4 or 5 simple instructions.
 
42
 * All composite objects on freelists are cleared, except for
 
43
 * their first word.
 
44
 */
 
45
 
 
46
/*
 
47
 *  The allocator uses GC_allochblk to allocate large chunks of objects.
 
48
 * These chunks all start on addresses which are multiples of
 
49
 * HBLKSZ.   Each allocated chunk has an associated header,
 
50
 * which can be located quickly based on the address of the chunk.
 
51
 * (See headers.c for details.) 
 
52
 * This makes it possible to check quickly whether an
 
53
 * arbitrary address corresponds to an object administered by the
 
54
 * allocator.
 
55
 */
 
56
 
 
57
word GC_non_gc_bytes = 0;  /* Number of bytes not intended to be collected */
 
58
 
 
59
word GC_gc_no = 0;
 
60
 
 
61
#ifndef SMALL_CONFIG
 
62
  int GC_incremental = 0;    /* By default, stop the world.     */
 
63
#endif
 
64
 
 
65
int GC_full_freq = 4;      /* Every 5th collection is a full    */
 
66
                           /* collection.                       */
 
67
 
 
68
char * GC_copyright[] =
 
69
{"Copyright 1988,1989 Hans-J. Boehm and Alan J. Demers ",
 
70
"Copyright (c) 1991-1995 by Xerox Corporation.  All rights reserved. ",
 
71
"Copyright (c) 1996-1998 by Silicon Graphics.  All rights reserved. ",
 
72
"THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY",
 
73
" EXPRESSED OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.",
 
74
"See source code for details." };
 
75
 
 
76
# include "version.h"
 
77
 
 
78
/* some more variables */
 
79
 
 
80
extern signed_word GC_mem_found;  /* Number of reclaimed longwords      */
 
81
                                  /* after garbage collection           */
 
82
 
 
83
GC_bool GC_dont_expand = 0;
 
84
 
 
85
word GC_free_space_divisor = 4;
 
86
 
 
87
extern GC_bool GC_collection_in_progress();
 
88
                /* Collection is in progress, or was abandoned. */
 
89
 
 
90
int GC_never_stop_func GC_PROTO((void)) { return(0); }
 
91
 
 
92
CLOCK_TYPE GC_start_time;       /* Time at which we stopped world.      */
 
93
                                /* used only in GC_timeout_stop_func.   */
 
94
 
 
95
int GC_n_attempts = 0;          /* Number of attempts at finishing      */
 
96
                                /* collection within TIME_LIMIT         */
 
97
 
 
98
#ifdef SMALL_CONFIG
 
99
#   define GC_timeout_stop_func GC_never_stop_func
 
100
#else
 
101
  int GC_timeout_stop_func GC_PROTO((void))
 
102
  {
 
103
    CLOCK_TYPE current_time;
 
104
    static unsigned count = 0;
 
105
    unsigned long time_diff;
 
106
    
 
107
    if ((count++ & 3) != 0) return(0);
 
108
    GET_TIME(current_time);
 
109
    time_diff = MS_TIME_DIFF(current_time,GC_start_time);
 
110
    if (time_diff >= TIME_LIMIT) {
 
111
#       ifdef PRINTSTATS
 
112
            GC_printf0("Abandoning stopped marking after ");
 
113
            GC_printf1("%lu msecs", (unsigned long)time_diff);
 
114
            GC_printf1("(attempt %d)\n", (unsigned long) GC_n_attempts);
 
115
#       endif
 
116
        return(1);
 
117
    }
 
118
    return(0);
 
119
  }
 
120
#endif /* !SMALL_CONFIG */
 
121
 
 
122
/* Return the minimum number of words that must be allocated between    */
 
123
/* collections to amortize the collection cost.                         */
 
124
static word min_words_allocd()
 
125
{
 
126
#   ifdef THREADS
 
127
        /* We punt, for now. */
 
128
        register signed_word stack_size = 10000;
 
129
#   else
 
130
        int dummy;
 
131
        register signed_word stack_size = (ptr_t)(&dummy) - GC_stackbottom;
 
132
#   endif
 
133
    register word total_root_size;  /* includes double stack size,      */
 
134
                                    /* since the stack is expensive     */
 
135
                                    /* to scan.                         */
 
136
    
 
137
    if (stack_size < 0) stack_size = -stack_size;
 
138
    total_root_size = 2 * stack_size + GC_root_size;
 
139
    if (GC_incremental) {
 
140
        return(BYTES_TO_WORDS(GC_heapsize + total_root_size)
 
141
               / (2 * GC_free_space_divisor));
 
142
    } else {
 
143
        return(BYTES_TO_WORDS(GC_heapsize + total_root_size)
 
144
               / GC_free_space_divisor);
 
145
    }
 
146
}
 
147
 
 
148
/* Return the number of words allocated, adjusted for explicit storage  */
 
149
/* management, etc..  This number is used in deciding when to trigger   */
 
150
/* collections.                                                         */
 
151
word GC_adj_words_allocd()
 
152
{
 
153
    register signed_word result;
 
154
    register signed_word expl_managed =
 
155
                BYTES_TO_WORDS((long)GC_non_gc_bytes
 
156
                                - (long)GC_non_gc_bytes_at_gc);
 
157
    
 
158
    /* Don't count what was explicitly freed, or newly allocated for    */
 
159
    /* explicit management.  Note that deallocating an explicitly       */
 
160
    /* managed object should not alter result, assuming the client      */
 
161
    /* is playing by the rules.                                         */
 
162
    result = (signed_word)GC_words_allocd
 
163
             - (signed_word)GC_mem_freed - expl_managed;
 
164
    if (result > (signed_word)GC_words_allocd) {
 
165
        result = GC_words_allocd;
 
166
        /* probably client bug or unfortunate scheduling */
 
167
    }
 
168
    result += GC_words_finalized;
 
169
        /* We count objects enqueued for finalization as though they    */
 
170
        /* had been reallocated this round. Finalization is user        */
 
171
        /* visible progress.  And if we don't count this, we have       */
 
172
        /* stability problems for programs that finalize all objects.   */
 
173
    result += GC_words_wasted;
 
174
        /* This doesn't reflect useful work.  But if there is lots of   */
 
175
        /* new fragmentation, the same is probably true of the heap,    */
 
176
        /* and the collection will be correspondingly cheaper.          */
 
177
    if (result < (signed_word)(GC_words_allocd >> 3)) {
 
178
        /* Always count at least 1/8 of the allocations.  We don't want */
 
179
        /* to collect too infrequently, since that would inhibit        */
 
180
        /* coalescing of free storage blocks.                           */
 
181
        /* This also makes us partially robust against client bugs.     */
 
182
        return(GC_words_allocd >> 3);
 
183
    } else {
 
184
        return(result);
 
185
    }
 
186
}
 
187
 
 
188
 
 
189
/* Clear up a few frames worth of garbage left at the top of the stack. */
 
190
/* This is used to prevent us from accidentally treating garbade left   */
 
191
/* on the stack by other parts of the collector as roots.  This         */
 
192
/* differs from the code in misc.c, which actually tries to keep the    */
 
193
/* stack clear of long-lived, client-generated garbage.                 */
 
194
void GC_clear_a_few_frames()
 
195
{
 
196
#   define NWORDS 64
 
197
    word frames[NWORDS];
 
198
    register int i;
 
199
    
 
200
    for (i = 0; i < NWORDS; i++) frames[i] = 0;
 
201
}
 
202
 
 
203
/* Have we allocated enough to amortize a collection? */
 
204
GC_bool GC_should_collect()
 
205
{
 
206
    return(GC_adj_words_allocd() >= min_words_allocd());
 
207
}
 
208
 
 
209
void GC_notify_full_gc()
 
210
{
 
211
    if (GC_start_call_back != (void (*)())0) {
 
212
        (*GC_start_call_back)();
 
213
    }
 
214
}
 
215
 
 
216
/* 
 
217
 * Initiate a garbage collection if appropriate.
 
218
 * Choose judiciously
 
219
 * between partial, full, and stop-world collections.
 
220
 * Assumes lock held, signals disabled.
 
221
 */
 
222
void GC_maybe_gc()
 
223
{
 
224
    static int n_partial_gcs = 0;
 
225
    GC_bool is_full_gc = FALSE;
 
226
 
 
227
    if (GC_should_collect()) {
 
228
        if (!GC_incremental) {
 
229
            GC_notify_full_gc();
 
230
            GC_gcollect_inner();
 
231
            n_partial_gcs = 0;
 
232
            return;
 
233
        } else if (n_partial_gcs >= GC_full_freq) {
 
234
#           ifdef PRINTSTATS
 
235
              GC_printf2(
 
236
                "***>Full mark for collection %lu after %ld allocd bytes\n",
 
237
                (unsigned long) GC_gc_no+1,
 
238
                (long)WORDS_TO_BYTES(GC_words_allocd));
 
239
#           endif
 
240
            GC_promote_black_lists();
 
241
            (void)GC_reclaim_all((GC_stop_func)0, TRUE);
 
242
            GC_clear_marks();
 
243
            n_partial_gcs = 0;
 
244
            GC_notify_full_gc();
 
245
            is_full_gc = TRUE;
 
246
        } else {
 
247
            n_partial_gcs++;
 
248
        }
 
249
        /* We try to mark with the world stopped.       */
 
250
        /* If we run out of time, this turns into       */
 
251
        /* incremental marking.                 */
 
252
        GET_TIME(GC_start_time);
 
253
        if (GC_stopped_mark(GC_timeout_stop_func)) {
 
254
#           ifdef SAVE_CALL_CHAIN
 
255
                GC_save_callers(GC_last_stack);
 
256
#           endif
 
257
            GC_finish_collection();
 
258
        } else {
 
259
            if (!is_full_gc) {
 
260
                /* Count this as the first attempt */
 
261
                GC_n_attempts++;
 
262
            }
 
263
        }
 
264
    }
 
265
}
 
266
 
 
267
 
 
268
/*
 
269
 * Stop the world garbage collection.  Assumes lock held, signals disabled.
 
270
 * If stop_func is not GC_never_stop_func, then abort if stop_func returns TRUE.
 
271
 */
 
272
GC_bool GC_try_to_collect_inner(stop_func)
 
273
GC_stop_func stop_func;
 
274
{
 
275
    if (GC_incremental && GC_collection_in_progress()) {
 
276
#   ifdef PRINTSTATS
 
277
        GC_printf0(
 
278
            "GC_try_to_collect_inner: finishing collection in progress\n");
 
279
#    endif /* PRINTSTATS */
 
280
      /* Just finish collection already in progress.    */
 
281
        while(GC_collection_in_progress()) {
 
282
            if (stop_func()) return(FALSE);
 
283
            GC_collect_a_little_inner(1);
 
284
        }
 
285
    }
 
286
#   ifdef PRINTSTATS
 
287
        GC_printf2(
 
288
           "Initiating full world-stop collection %lu after %ld allocd bytes\n",
 
289
           (unsigned long) GC_gc_no+1,
 
290
           (long)WORDS_TO_BYTES(GC_words_allocd));
 
291
#   endif
 
292
    GC_promote_black_lists();
 
293
    /* Make sure all blocks have been reclaimed, so sweep routines      */
 
294
    /* don't see cleared mark bits.                                     */
 
295
    /* If we're guaranteed to finish, then this is unnecessary.         */
 
296
        if (stop_func != GC_never_stop_func
 
297
            && !GC_reclaim_all(stop_func, FALSE)) {
 
298
            /* Aborted.  So far everything is still consistent. */
 
299
            return(FALSE);
 
300
        }
 
301
    GC_invalidate_mark_state();  /* Flush mark stack.   */
 
302
    GC_clear_marks();
 
303
#   ifdef SAVE_CALL_CHAIN
 
304
        GC_save_callers(GC_last_stack);
 
305
#   endif
 
306
    if (!GC_stopped_mark(stop_func)) {
 
307
      if (!GC_incremental) {
 
308
        /* We're partially done and have no way to complete or use      */
 
309
        /* current work.  Reestablish invariants as cheaply as          */
 
310
        /* possible.                                                    */
 
311
        GC_invalidate_mark_state();
 
312
        GC_unpromote_black_lists();
 
313
      } /* else we claim the world is already still consistent.  We'll  */
 
314
        /* finish incrementally.                                        */
 
315
      return(FALSE);
 
316
    }
 
317
    GC_finish_collection();
 
318
    return(TRUE);
 
319
}
 
320
 
 
321
 
 
322
 
 
323
/*
 
324
 * Perform n units of garbage collection work.  A unit is intended to touch
 
325
 * roughly GC_RATE pages.  Every once in a while, we do more than that.
 
326
 * This needa to be a fairly large number with our current incremental
 
327
 * GC strategy, since otherwise we allocate too much during GC, and the
 
328
 * cleanup gets expensive.
 
329
 */
 
330
# define GC_RATE 10 
 
331
# define MAX_PRIOR_ATTEMPTS 1
 
332
        /* Maximum number of prior attempts at world stop marking       */
 
333
        /* A value of 1 means that we finish the seconf time, no matter */
 
334
        /* how long it takes.  Doesn't count the initial root scan      */
 
335
        /* for a full GC.                                               */
 
336
 
 
337
int GC_deficit = 0;     /* The number of extra calls to GC_mark_some    */
 
338
                        /* that we have made.                           */
 
339
 
 
340
void GC_collect_a_little_inner(n)
 
341
int n;
 
342
{
 
343
    register int i;
 
344
    
 
345
    if (GC_incremental && GC_collection_in_progress()) {
 
346
        for (i = GC_deficit; i < GC_RATE*n; i++) {
 
347
            if (GC_mark_some((ptr_t)0)) {
 
348
                /* Need to finish a collection */
 
349
#               ifdef SAVE_CALL_CHAIN
 
350
                    GC_save_callers(GC_last_stack);
 
351
#               endif
 
352
                if (GC_n_attempts < MAX_PRIOR_ATTEMPTS) {
 
353
                  GET_TIME(GC_start_time);
 
354
                  if (!GC_stopped_mark(GC_timeout_stop_func)) {
 
355
                    GC_n_attempts++;
 
356
                    break;
 
357
                  }
 
358
                } else {
 
359
                  (void)GC_stopped_mark(GC_never_stop_func);
 
360
                }
 
361
                GC_finish_collection();
 
362
                break;
 
363
            }
 
364
        }
 
365
        if (GC_deficit > 0) GC_deficit -= GC_RATE*n;
 
366
        if (GC_deficit < 0) GC_deficit = 0;
 
367
    } else {
 
368
        GC_maybe_gc();
 
369
    }
 
370
}
 
371
 
 
372
int GC_collect_a_little GC_PROTO(())
 
373
{
 
374
    int result;
 
375
    DCL_LOCK_STATE;
 
376
 
 
377
    DISABLE_SIGNALS();
 
378
    LOCK();
 
379
    GC_collect_a_little_inner(1);
 
380
    result = (int)GC_collection_in_progress();
 
381
    UNLOCK();
 
382
    ENABLE_SIGNALS();
 
383
    return(result);
 
384
}
 
385
 
 
386
/*
 
387
 * Assumes lock is held, signals are disabled.
 
388
 * We stop the world.
 
389
 * If stop_func() ever returns TRUE, we may fail and return FALSE.
 
390
 * Increment GC_gc_no if we succeed.
 
391
 */
 
392
GC_bool GC_stopped_mark(stop_func)
 
393
GC_stop_func stop_func;
 
394
{
 
395
    register int i;
 
396
    int dummy;
 
397
#   ifdef PRINTSTATS
 
398
        CLOCK_TYPE start_time, current_time;
 
399
#   endif
 
400
        
 
401
    STOP_WORLD();
 
402
#   ifdef PRINTSTATS
 
403
        GET_TIME(start_time);
 
404
        GC_printf1("--> Marking for collection %lu ",
 
405
                   (unsigned long) GC_gc_no + 1);
 
406
        GC_printf2("after %lu allocd bytes + %lu wasted bytes\n",
 
407
                   (unsigned long) WORDS_TO_BYTES(GC_words_allocd),
 
408
                   (unsigned long) WORDS_TO_BYTES(GC_words_wasted));
 
409
#   endif
 
410
 
 
411
    /* Mark from all roots.  */
 
412
        /* Minimize junk left in my registers and on the stack */
 
413
            GC_clear_a_few_frames();
 
414
            GC_noop(0,0,0,0,0,0);
 
415
        GC_initiate_gc();
 
416
        for(i = 0;;i++) {
 
417
            if ((*stop_func)()) {
 
418
#                   ifdef PRINTSTATS
 
419
                        GC_printf0("Abandoned stopped marking after ");
 
420
                        GC_printf1("%lu iterations\n",
 
421
                                   (unsigned long)i);
 
422
#                   endif
 
423
                    GC_deficit = i; /* Give the mutator a chance. */
 
424
                    START_WORLD();
 
425
                    return(FALSE);
 
426
            }
 
427
            if (GC_mark_some((ptr_t)(&dummy))) break;
 
428
        }
 
429
        
 
430
    GC_gc_no++;
 
431
#   ifdef PRINTSTATS
 
432
      GC_printf2("Collection %lu reclaimed %ld bytes",
 
433
                  (unsigned long) GC_gc_no - 1,
 
434
                  (long)WORDS_TO_BYTES(GC_mem_found));
 
435
      GC_printf1(" ---> heapsize = %lu bytes\n",
 
436
                (unsigned long) GC_heapsize);
 
437
      /* Printf arguments may be pushed in funny places.  Clear the     */
 
438
      /* space.                                                         */
 
439
      GC_printf0("");
 
440
#   endif      
 
441
 
 
442
    /* Check all debugged objects for consistency */
 
443
        if (GC_debugging_started) {
 
444
            (*GC_check_heap)();
 
445
        }
 
446
    
 
447
#   ifdef PRINTTIMES
 
448
        GET_TIME(current_time);
 
449
        GC_printf1("World-stopped marking took %lu msecs\n",
 
450
                   MS_TIME_DIFF(current_time,start_time));
 
451
#   endif
 
452
    START_WORLD();
 
453
    return(TRUE);
 
454
}
 
455
 
 
456
 
 
457
/* Finish up a collection.  Assumes lock is held, signals are disabled, */
 
458
/* but the world is otherwise running.                                  */
 
459
void GC_finish_collection()
 
460
{
 
461
#   ifdef PRINTTIMES
 
462
        CLOCK_TYPE start_time;
 
463
        CLOCK_TYPE finalize_time;
 
464
        CLOCK_TYPE done_time;
 
465
        
 
466
        GET_TIME(start_time);
 
467
        finalize_time = start_time;
 
468
#   endif
 
469
 
 
470
#   ifdef GATHERSTATS
 
471
        GC_mem_found = 0;
 
472
#   endif
 
473
#   ifdef FIND_LEAK
 
474
      /* Mark all objects on the free list.  All objects should be */
 
475
      /* marked when we're done.                                   */
 
476
        {
 
477
          register word size;           /* current object size          */
 
478
          register ptr_t p;     /* pointer to current object    */
 
479
          register struct hblk * h;     /* pointer to block containing *p */
 
480
          register hdr * hhdr;
 
481
          register int word_no;           /* "index" of *p in *q          */
 
482
          int kind;
 
483
 
 
484
          for (kind = 0; kind < GC_n_kinds; kind++) {
 
485
            for (size = 1; size <= MAXOBJSZ; size++) {
 
486
              for (p= GC_obj_kinds[kind].ok_freelist[size];
 
487
                   p != 0; p=obj_link(p)){
 
488
                h = HBLKPTR(p);
 
489
                hhdr = HDR(h);
 
490
                word_no = (((word *)p) - ((word *)h));
 
491
                set_mark_bit_from_hdr(hhdr, word_no);
 
492
              }
 
493
            }
 
494
          }
 
495
        }
 
496
      /* Check that everything is marked */
 
497
        GC_start_reclaim(TRUE);
 
498
#   else
 
499
 
 
500
      GC_finalize();
 
501
#     ifdef STUBBORN_ALLOC
 
502
        GC_clean_changing_list();
 
503
#     endif
 
504
 
 
505
#     ifdef PRINTTIMES
 
506
        GET_TIME(finalize_time);
 
507
#     endif
 
508
 
 
509
      /* Clear free list mark bits, in case they got accidentally marked   */
 
510
      /* Note: HBLKPTR(p) == pointer to head of block containing *p        */
 
511
      /* Also subtract memory remaining from GC_mem_found count.           */
 
512
      /* Note that composite objects on free list are cleared.             */
 
513
      /* Thus accidentally marking a free list is not a problem;  only     */
 
514
      /* objects on the list itself will be marked, and that's fixed here. */
 
515
      {
 
516
        register word size;             /* current object size          */
 
517
        register ptr_t p;       /* pointer to current object    */
 
518
        register struct hblk * h;       /* pointer to block containing *p */
 
519
        register hdr * hhdr;
 
520
        register int word_no;           /* "index" of *p in *q          */
 
521
        int kind;
 
522
 
 
523
        for (kind = 0; kind < GC_n_kinds; kind++) {
 
524
          for (size = 1; size <= MAXOBJSZ; size++) {
 
525
            for (p= GC_obj_kinds[kind].ok_freelist[size];
 
526
                 p != 0; p=obj_link(p)){
 
527
                h = HBLKPTR(p);
 
528
                hhdr = HDR(h);
 
529
                word_no = (((word *)p) - ((word *)h));
 
530
                clear_mark_bit_from_hdr(hhdr, word_no);
 
531
#               ifdef GATHERSTATS
 
532
                    GC_mem_found -= size;
 
533
#               endif
 
534
            }
 
535
          }
 
536
        }
 
537
      }
 
538
 
 
539
 
 
540
#     ifdef PRINTSTATS
 
541
        GC_printf1("Bytes recovered before sweep - f.l. count = %ld\n",
 
542
                  (long)WORDS_TO_BYTES(GC_mem_found));
 
543
#     endif
 
544
 
 
545
    /* Reconstruct free lists to contain everything not marked */
 
546
      GC_start_reclaim(FALSE);
 
547
    
 
548
#   endif /* !FIND_LEAK */
 
549
 
 
550
#   ifdef PRINTSTATS
 
551
        GC_printf2(
 
552
                  "Immediately reclaimed %ld bytes in heap of size %lu bytes\n",
 
553
                  (long)WORDS_TO_BYTES(GC_mem_found),
 
554
                  (unsigned long)GC_heapsize);
 
555
        GC_printf2("%lu (atomic) + %lu (composite) collectable bytes in use\n",
 
556
                   (unsigned long)WORDS_TO_BYTES(GC_atomic_in_use),
 
557
                   (unsigned long)WORDS_TO_BYTES(GC_composite_in_use));
 
558
#   endif
 
559
 
 
560
      GC_n_attempts = 0;
 
561
    /* Reset or increment counters for next cycle */
 
562
      GC_words_allocd_before_gc += GC_words_allocd;
 
563
      GC_non_gc_bytes_at_gc = GC_non_gc_bytes;
 
564
      GC_words_allocd = 0;
 
565
      GC_words_wasted = 0;
 
566
      GC_mem_freed = 0;
 
567
      
 
568
#   ifdef PRINTTIMES
 
569
        GET_TIME(done_time);
 
570
        GC_printf2("Finalize + initiate sweep took %lu + %lu msecs\n",
 
571
                   MS_TIME_DIFF(finalize_time,start_time),
 
572
                   MS_TIME_DIFF(done_time,finalize_time));
 
573
#   endif
 
574
}
 
575
 
 
576
/* Externally callable routine to invoke full, stop-world collection */
 
577
# if defined(__STDC__) || defined(__cplusplus)
 
578
    int GC_try_to_collect(GC_stop_func stop_func)
 
579
# else
 
580
    int GC_try_to_collect(stop_func)
 
581
    GC_stop_func stop_func;
 
582
# endif
 
583
{
 
584
    int result;
 
585
    DCL_LOCK_STATE;
 
586
    
 
587
    GC_INVOKE_FINALIZERS();
 
588
    DISABLE_SIGNALS();
 
589
    LOCK();
 
590
    ENTER_GC();
 
591
    if (!GC_is_initialized) GC_init_inner();
 
592
    /* Minimize junk left in my registers */
 
593
      GC_noop(0,0,0,0,0,0);
 
594
    result = (int)GC_try_to_collect_inner(stop_func);
 
595
    EXIT_GC();
 
596
    UNLOCK();
 
597
    ENABLE_SIGNALS();
 
598
    if(result) GC_INVOKE_FINALIZERS();
 
599
    return(result);
 
600
}
 
601
 
 
602
void GC_gcollect GC_PROTO(())
 
603
{
 
604
    GC_notify_full_gc();
 
605
    (void)GC_try_to_collect(GC_never_stop_func);
 
606
}
 
607
 
 
608
word GC_n_heap_sects = 0;       /* Number of sections currently in heap. */
 
609
 
 
610
/*
 
611
 * Use the chunk of memory starting at p of syze bytes as part of the heap.
 
612
 * Assumes p is HBLKSIZE aligned, and bytes is a multiple of HBLKSIZE.
 
613
 */
 
614
void GC_add_to_heap(p, bytes)
 
615
struct hblk *p;
 
616
word bytes;
 
617
{
 
618
    word words;
 
619
    
 
620
    if (GC_n_heap_sects >= MAX_HEAP_SECTS) {
 
621
        ABORT("Too many heap sections: Increase MAXHINCR or MAX_HEAP_SECTS");
 
622
    }
 
623
    if (!GC_install_header(p)) {
 
624
        /* This is extremely unlikely. Can't add it.  This will         */
 
625
        /* almost certainly result in a 0 return from the allocator,    */
 
626
        /* which is entirely appropriate.                               */
 
627
        return;
 
628
    }
 
629
    GC_heap_sects[GC_n_heap_sects].hs_start = (ptr_t)p;
 
630
    GC_heap_sects[GC_n_heap_sects].hs_bytes = bytes;
 
631
    GC_n_heap_sects++;
 
632
    words = BYTES_TO_WORDS(bytes - HDR_BYTES);
 
633
    HDR(p) -> hb_sz = words;
 
634
    GC_freehblk(p);
 
635
    GC_heapsize += bytes;
 
636
    if ((ptr_t)p <= GC_least_plausible_heap_addr
 
637
        || GC_least_plausible_heap_addr == 0) {
 
638
        GC_least_plausible_heap_addr = (ptr_t)p - sizeof(word);
 
639
                /* Making it a little smaller than necessary prevents   */
 
640
                /* us from getting a false hit from the variable        */
 
641
                /* itself.  There's some unintentional reflection       */
 
642
                /* here.                                                */
 
643
    }
 
644
    if ((ptr_t)p + bytes >= GC_greatest_plausible_heap_addr) {
 
645
        GC_greatest_plausible_heap_addr = (ptr_t)p + bytes;
 
646
    }
 
647
}
 
648
 
 
649
#ifdef PRESERVE_LAST
 
650
 
 
651
GC_bool GC_protect_last_block = FALSE;
 
652
 
 
653
GC_bool GC_in_last_heap_sect(p)
 
654
ptr_t p;
 
655
{
 
656
    struct HeapSect * last_heap_sect;
 
657
    ptr_t start;
 
658
    ptr_t end;
 
659
 
 
660
    if (!GC_protect_last_block) return FALSE;
 
661
    last_heap_sect = &(GC_heap_sects[GC_n_heap_sects-1]);
 
662
    start = last_heap_sect -> hs_start;
 
663
    if (p < start) return FALSE;
 
664
    end = start + last_heap_sect -> hs_bytes;
 
665
    if (p >= end) return FALSE;
 
666
    return TRUE;
 
667
}
 
668
#endif
 
669
 
 
670
# if !defined(NO_DEBUGGING)
 
671
void GC_print_heap_sects()
 
672
{
 
673
    register unsigned i;
 
674
    
 
675
    GC_printf1("Total heap size: %lu\n", (unsigned long) GC_heapsize);
 
676
    for (i = 0; i < GC_n_heap_sects; i++) {
 
677
        unsigned long start = (unsigned long) GC_heap_sects[i].hs_start;
 
678
        unsigned long len = (unsigned long) GC_heap_sects[i].hs_bytes;
 
679
        struct hblk *h;
 
680
        unsigned nbl = 0;
 
681
        
 
682
        GC_printf3("Section %ld from 0x%lx to 0x%lx ", (unsigned long)i,
 
683
                   start, (unsigned long)(start + len));
 
684
        for (h = (struct hblk *)start; h < (struct hblk *)(start + len); h++) {
 
685
            if (GC_is_black_listed(h, HBLKSIZE)) nbl++;
 
686
        }
 
687
        GC_printf2("%lu/%lu blacklisted\n", (unsigned long)nbl,
 
688
                   (unsigned long)(len/HBLKSIZE));
 
689
    }
 
690
}
 
691
# endif
 
692
 
 
693
ptr_t GC_least_plausible_heap_addr = (ptr_t)ONES;
 
694
ptr_t GC_greatest_plausible_heap_addr = 0;
 
695
 
 
696
ptr_t GC_max(x,y)
 
697
ptr_t x, y;
 
698
{
 
699
    return(x > y? x : y);
 
700
}
 
701
 
 
702
ptr_t GC_min(x,y)
 
703
ptr_t x, y;
 
704
{
 
705
    return(x < y? x : y);
 
706
}
 
707
 
 
708
# if defined(__STDC__) || defined(__cplusplus)
 
709
    void GC_set_max_heap_size(GC_word n)
 
710
# else
 
711
    void GC_set_max_heap_size(n)
 
712
    GC_word n;
 
713
# endif
 
714
{
 
715
    GC_max_heapsize = n;
 
716
}
 
717
 
 
718
GC_word GC_max_retries = 0;
 
719
 
 
720
/*
 
721
 * this explicitly increases the size of the heap.  It is used
 
722
 * internally, but may also be invoked from GC_expand_hp by the user.
 
723
 * The argument is in units of HBLKSIZE.
 
724
 * Tiny values of n are rounded up.
 
725
 * Returns FALSE on failure.
 
726
 */
 
727
GC_bool GC_expand_hp_inner(n)
 
728
word n;
 
729
{
 
730
    word bytes;
 
731
    struct hblk * space;
 
732
    word expansion_slop;        /* Number of bytes by which we expect the */
 
733
                                /* heap to expand soon.                   */
 
734
 
 
735
    if (n < MINHINCR) n = MINHINCR;
 
736
    bytes = n * HBLKSIZE;
 
737
    /* Make sure bytes is a multiple of GC_page_size */
 
738
      {
 
739
        word mask = GC_page_size - 1;
 
740
        bytes += mask;
 
741
        bytes &= ~mask;
 
742
      }
 
743
    
 
744
    if (GC_max_heapsize != 0 && GC_heapsize + bytes > GC_max_heapsize) {
 
745
        /* Exceeded self-imposed limit */
 
746
        return(FALSE);
 
747
    }
 
748
    space = GET_MEM(bytes);
 
749
    if( space == 0 ) {
 
750
        return(FALSE);
 
751
    }
 
752
#   ifdef PRINTSTATS
 
753
        GC_printf2("Increasing heap size by %lu after %lu allocated bytes\n",
 
754
                   (unsigned long)bytes,
 
755
                   (unsigned long)WORDS_TO_BYTES(GC_words_allocd));
 
756
#       ifdef UNDEFINED
 
757
          GC_printf1("Root size = %lu\n", GC_root_size);
 
758
          GC_print_block_list(); GC_print_hblkfreelist();
 
759
          GC_printf0("\n");
 
760
#       endif
 
761
#   endif
 
762
    expansion_slop = 8 * WORDS_TO_BYTES(min_words_allocd());
 
763
    if (5 * HBLKSIZE * MAXHINCR > expansion_slop) {
 
764
        expansion_slop = 5 * HBLKSIZE * MAXHINCR;
 
765
    }
 
766
    if (GC_last_heap_addr == 0 && !((word)space & SIGNB)
 
767
        || GC_last_heap_addr != 0 && GC_last_heap_addr < (ptr_t)space) {
 
768
        /* Assume the heap is growing up */
 
769
        GC_greatest_plausible_heap_addr =
 
770
            GC_max(GC_greatest_plausible_heap_addr,
 
771
                   (ptr_t)space + bytes + expansion_slop);
 
772
    } else {
 
773
        /* Heap is growing down */
 
774
        GC_least_plausible_heap_addr =
 
775
            GC_min(GC_least_plausible_heap_addr,
 
776
                   (ptr_t)space - expansion_slop);
 
777
    }
 
778
    GC_prev_heap_addr = GC_last_heap_addr;
 
779
    GC_last_heap_addr = (ptr_t)space;
 
780
    GC_add_to_heap(space, bytes);
 
781
    return(TRUE);
 
782
}
 
783
 
 
784
/* Really returns a bool, but it's externally visible, so that's clumsy. */
 
785
/* Arguments is in bytes.                                               */
 
786
# if defined(__STDC__) || defined(__cplusplus)
 
787
  int GC_expand_hp(size_t bytes)
 
788
# else
 
789
  int GC_expand_hp(bytes)
 
790
  size_t bytes;
 
791
# endif
 
792
{
 
793
    int result;
 
794
    DCL_LOCK_STATE;
 
795
    
 
796
    DISABLE_SIGNALS();
 
797
    LOCK();
 
798
    if (!GC_is_initialized) GC_init_inner();
 
799
    result = (int)GC_expand_hp_inner(divHBLKSZ((word)bytes));
 
800
#   ifdef PRESERVE_LAST
 
801
        if (result) GC_protect_last_block = FALSE;
 
802
#   endif
 
803
    UNLOCK();
 
804
    ENABLE_SIGNALS();
 
805
    return(result);
 
806
}
 
807
 
 
808
unsigned GC_fail_count = 0;  
 
809
                        /* How many consecutive GC/expansion failures?  */
 
810
                        /* Reset by GC_allochblk.                       */
 
811
 
 
812
GC_bool GC_collect_or_expand(needed_blocks, ignore_off_page)
 
813
word needed_blocks;
 
814
GC_bool ignore_off_page;
 
815
{
 
816
    
 
817
    if (!GC_incremental && !GC_dont_gc && GC_should_collect()) {
 
818
      GC_notify_full_gc();
 
819
      GC_gcollect_inner();
 
820
    } else {
 
821
      word blocks_to_get = GC_heapsize/(HBLKSIZE*GC_free_space_divisor)
 
822
                           + needed_blocks;
 
823
      
 
824
      if (blocks_to_get > MAXHINCR) {
 
825
          word slop;
 
826
          
 
827
          if (ignore_off_page) {
 
828
              slop = 4;
 
829
          } else {
 
830
              slop = 2*divHBLKSZ(BL_LIMIT);
 
831
              if (slop > needed_blocks) slop = needed_blocks;
 
832
          }
 
833
          if (needed_blocks + slop > MAXHINCR) {
 
834
              blocks_to_get = needed_blocks + slop;
 
835
          } else {
 
836
              blocks_to_get = MAXHINCR;
 
837
          }
 
838
      }
 
839
      if (!GC_expand_hp_inner(blocks_to_get)
 
840
        && !GC_expand_hp_inner(needed_blocks)) {
 
841
        if (GC_fail_count++ < GC_max_retries) {
 
842
            WARN("Out of Memory!  Trying to continue ...\n", 0);
 
843
            GC_notify_full_gc();
 
844
            GC_gcollect_inner();
 
845
        } else {
 
846
            WARN("Out of Memory!  Returning NIL!\n", 0);
 
847
            return(FALSE);
 
848
        }
 
849
      } else {
 
850
#         ifdef PRINTSTATS
 
851
            if (GC_fail_count) {
 
852
              GC_printf0("Memory available again ...\n");
 
853
            }
 
854
#         endif
 
855
#         ifdef PRESERVE_LAST
 
856
            if (needed_blocks > 1) GC_protect_last_block = TRUE;
 
857
                /* We were forced to expand the heap as the result      */
 
858
                /* of a large block allocation.  Avoid breaking up      */
 
859
                /* new block into small pieces.                         */
 
860
#         endif
 
861
      }
 
862
    }
 
863
    return(TRUE);
 
864
}
 
865
 
 
866
/*
 
867
 * Make sure the object free list for sz is not empty.
 
868
 * Return a pointer to the first object on the free list.
 
869
 * The object MUST BE REMOVED FROM THE FREE LIST BY THE CALLER.
 
870
 * Assumes we hold the allocator lock and signals are disabled.
 
871
 *
 
872
 */
 
873
ptr_t GC_allocobj(sz, kind)
 
874
word sz;
 
875
int kind;
 
876
{
 
877
    register ptr_t * flh = &(GC_obj_kinds[kind].ok_freelist[sz]);
 
878
    
 
879
    if (sz == 0) return(0);
 
880
 
 
881
    while (*flh == 0) {
 
882
      ENTER_GC();
 
883
      /* Do our share of marking work */
 
884
        if(GC_incremental && !GC_dont_gc) GC_collect_a_little_inner(1);
 
885
      /* Sweep blocks for objects of this size */
 
886
          GC_continue_reclaim(sz, kind);
 
887
      EXIT_GC();
 
888
      if (*flh == 0) {
 
889
        GC_new_hblk(sz, kind);
 
890
      }
 
891
      if (*flh == 0) {
 
892
        ENTER_GC();
 
893
        if (!GC_collect_or_expand((word)1,FALSE)) {
 
894
            EXIT_GC();
 
895
            return(0);
 
896
        }
 
897
        EXIT_GC();
 
898
      }
 
899
    }
 
900
    
 
901
    return(*flh);
 
902
}