2 * Mark-and-sweep garbage collection.
5 #include "duk_internal.h"
7 #ifdef DUK_USE_MARK_AND_SWEEP
9 DUK_LOCAL_DECL
void duk__mark_heaphdr(duk_heap
*heap
, duk_heaphdr
*h
);
10 DUK_LOCAL_DECL
void duk__mark_tval(duk_heap
*heap
, duk_tval
*tv
);
16 /* Select a thread for mark-and-sweep use.
18 * XXX: This needs to change later.
20 DUK_LOCAL duk_hthread
*duk__get_temp_hthread(duk_heap
*heap
) {
21 if (heap
->curr_thread
) {
22 return heap
->curr_thread
;
24 return heap
->heap_thread
; /* may be NULL, too */
28 * Marking functions for heap types: mark children recursively
31 DUK_LOCAL
void duk__mark_hstring(duk_heap
*heap
, duk_hstring
*h
) {
35 DUK_DDD(DUK_DDDPRINT("duk__mark_hstring: %p", (void *) h
));
38 /* nothing to process */
41 DUK_LOCAL
void duk__mark_hobject(duk_heap
*heap
, duk_hobject
*h
) {
44 DUK_DDD(DUK_DDDPRINT("duk__mark_hobject: %p", (void *) h
));
48 /* XXX: use advancing pointers instead of index macros -> faster and smaller? */
50 for (i
= 0; i
< (duk_uint_fast32_t
) DUK_HOBJECT_GET_ENEXT(h
); i
++) {
51 duk_hstring
*key
= DUK_HOBJECT_E_GET_KEY(heap
, h
, i
);
55 duk__mark_heaphdr(heap
, (duk_heaphdr
*) key
);
56 if (DUK_HOBJECT_E_SLOT_IS_ACCESSOR(heap
, h
, i
)) {
57 duk__mark_heaphdr(heap
, (duk_heaphdr
*) DUK_HOBJECT_E_GET_VALUE_PTR(heap
, h
, i
)->a
.get
);
58 duk__mark_heaphdr(heap
, (duk_heaphdr
*) DUK_HOBJECT_E_GET_VALUE_PTR(heap
, h
, i
)->a
.set
);
60 duk__mark_tval(heap
, &DUK_HOBJECT_E_GET_VALUE_PTR(heap
, h
, i
)->v
);
64 for (i
= 0; i
< (duk_uint_fast32_t
) DUK_HOBJECT_GET_ASIZE(h
); i
++) {
65 duk__mark_tval(heap
, DUK_HOBJECT_A_GET_VALUE_PTR(heap
, h
, i
));
68 /* hash part is a 'weak reference' and does not contribute */
70 duk__mark_heaphdr(heap
, (duk_heaphdr
*) DUK_HOBJECT_GET_PROTOTYPE(heap
, h
));
72 if (DUK_HOBJECT_IS_COMPILEDFUNCTION(h
)) {
73 duk_hcompiledfunction
*f
= (duk_hcompiledfunction
*) h
;
74 duk_tval
*tv
, *tv_end
;
75 duk_hobject
**fn
, **fn_end
;
77 /* 'data' is reachable through every compiled function which
78 * contains a reference.
81 duk__mark_heaphdr(heap
, (duk_heaphdr
*) DUK_HCOMPILEDFUNCTION_GET_DATA(heap
, f
));
83 if (DUK_HCOMPILEDFUNCTION_GET_DATA(heap
, f
) != NULL
) {
84 tv
= DUK_HCOMPILEDFUNCTION_GET_CONSTS_BASE(heap
, f
);
85 tv_end
= DUK_HCOMPILEDFUNCTION_GET_CONSTS_END(heap
, f
);
87 duk__mark_tval(heap
, tv
);
91 fn
= DUK_HCOMPILEDFUNCTION_GET_FUNCS_BASE(heap
, f
);
92 fn_end
= DUK_HCOMPILEDFUNCTION_GET_FUNCS_END(heap
, f
);
94 duk__mark_heaphdr(heap
, (duk_heaphdr
*) *fn
);
98 /* May happen in some out-of-memory corner cases. */
99 DUK_D(DUK_DPRINT("duk_hcompiledfunction 'data' is NULL, skipping marking"));
101 } else if (DUK_HOBJECT_IS_NATIVEFUNCTION(h
)) {
102 duk_hnativefunction
*f
= (duk_hnativefunction
*) h
;
104 /* nothing to mark */
105 } else if (DUK_HOBJECT_IS_BUFFEROBJECT(h
)) {
106 duk_hbufferobject
*b
= (duk_hbufferobject
*) h
;
107 duk__mark_heaphdr(heap
, (duk_heaphdr
*) b
->buf
);
108 } else if (DUK_HOBJECT_IS_THREAD(h
)) {
109 duk_hthread
*t
= (duk_hthread
*) h
;
113 while (tv
< t
->valstack_top
) {
114 duk__mark_tval(heap
, tv
);
118 for (i
= 0; i
< (duk_uint_fast32_t
) t
->callstack_top
; i
++) {
119 duk_activation
*act
= t
->callstack
+ i
;
120 duk__mark_heaphdr(heap
, (duk_heaphdr
*) DUK_ACT_GET_FUNC(act
));
121 duk__mark_heaphdr(heap
, (duk_heaphdr
*) act
->var_env
);
122 duk__mark_heaphdr(heap
, (duk_heaphdr
*) act
->lex_env
);
123 #ifdef DUK_USE_NONSTD_FUNC_CALLER_PROPERTY
124 duk__mark_heaphdr(heap
, (duk_heaphdr
*) act
->prev_caller
);
128 #if 0 /* nothing now */
129 for (i
= 0; i
< (duk_uint_fast32_t
) t
->catchstack_top
; i
++) {
130 duk_catcher
*cat
= t
->catchstack
+ i
;
134 duk__mark_heaphdr(heap
, (duk_heaphdr
*) t
->resumer
);
136 /* XXX: duk_small_uint_t would be enough for this loop */
137 for (i
= 0; i
< DUK_NUM_BUILTINS
; i
++) {
138 duk__mark_heaphdr(heap
, (duk_heaphdr
*) t
->builtins
[i
]);
143 /* recursion tracking happens here only */
144 DUK_LOCAL
void duk__mark_heaphdr(duk_heap
*heap
, duk_heaphdr
*h
) {
145 DUK_DDD(DUK_DDDPRINT("duk__mark_heaphdr %p, type %ld",
147 (h
!= NULL
? (long) DUK_HEAPHDR_GET_TYPE(h
) : (long) -1)));
151 #if defined(DUK_USE_ROM_OBJECTS)
152 if (DUK_HEAPHDR_HAS_READONLY(h
)) {
153 DUK_DDD(DUK_DDDPRINT("readonly object %p, skip", (void *) h
));
157 if (DUK_HEAPHDR_HAS_REACHABLE(h
)) {
158 DUK_DDD(DUK_DDDPRINT("already marked reachable, skip"));
161 DUK_HEAPHDR_SET_REACHABLE(h
);
163 if (heap
->mark_and_sweep_recursion_depth
>= DUK_USE_MARK_AND_SWEEP_RECLIMIT
) {
164 /* log this with a normal debug level because this should be relatively rare */
165 DUK_D(DUK_DPRINT("mark-and-sweep recursion limit reached, marking as temproot: %p", (void *) h
));
166 DUK_HEAP_SET_MARKANDSWEEP_RECLIMIT_REACHED(heap
);
167 DUK_HEAPHDR_SET_TEMPROOT(h
);
171 heap
->mark_and_sweep_recursion_depth
++;
173 switch ((int) DUK_HEAPHDR_GET_TYPE(h
)) {
174 case DUK_HTYPE_STRING
:
175 duk__mark_hstring(heap
, (duk_hstring
*) h
);
177 case DUK_HTYPE_OBJECT
:
178 duk__mark_hobject(heap
, (duk_hobject
*) h
);
180 case DUK_HTYPE_BUFFER
:
181 /* nothing to mark */
184 DUK_D(DUK_DPRINT("attempt to mark heaphdr %p with invalid htype %ld", (void *) h
, (long) DUK_HEAPHDR_GET_TYPE(h
)));
188 heap
->mark_and_sweep_recursion_depth
--;
191 DUK_LOCAL
void duk__mark_tval(duk_heap
*heap
, duk_tval
*tv
) {
192 DUK_DDD(DUK_DDDPRINT("duk__mark_tval %p", (void *) tv
));
196 if (DUK_TVAL_IS_HEAP_ALLOCATED(tv
)) {
197 duk__mark_heaphdr(heap
, DUK_TVAL_GET_HEAPHDR(tv
));
205 DUK_LOCAL
void duk__mark_roots_heap(duk_heap
*heap
) {
208 DUK_DD(DUK_DDPRINT("duk__mark_roots_heap: %p", (void *) heap
));
210 duk__mark_heaphdr(heap
, (duk_heaphdr
*) heap
->heap_thread
);
211 duk__mark_heaphdr(heap
, (duk_heaphdr
*) heap
->heap_object
);
213 for (i
= 0; i
< DUK_HEAP_NUM_STRINGS
; i
++) {
214 duk_hstring
*h
= DUK_HEAP_GET_STRING(heap
, i
);
215 duk__mark_heaphdr(heap
, (duk_heaphdr
*) h
);
218 duk__mark_tval(heap
, &heap
->lj
.value1
);
219 duk__mark_tval(heap
, &heap
->lj
.value2
);
221 #if defined(DUK_USE_DEBUGGER_SUPPORT)
222 for (i
= 0; i
< heap
->dbg_breakpoint_count
; i
++) {
223 duk__mark_heaphdr(heap
, (duk_heaphdr
*) heap
->dbg_breakpoints
[i
].filename
);
229 * Mark refzero_list objects.
231 * Objects on the refzero_list have no inbound references. They might have
232 * outbound references to objects that we might free, which would invalidate
233 * any references held by the refzero objects. A refzero object might also
234 * be rescued by refcount finalization. Refzero objects are treated as
235 * reachability roots to ensure they (or anything they point to) are not
236 * freed in mark-and-sweep.
239 #ifdef DUK_USE_REFERENCE_COUNTING
240 DUK_LOCAL
void duk__mark_refzero_list(duk_heap
*heap
) {
243 DUK_DD(DUK_DDPRINT("duk__mark_refzero_list: %p", (void *) heap
));
245 hdr
= heap
->refzero_list
;
247 duk__mark_heaphdr(heap
, hdr
);
248 hdr
= DUK_HEAPHDR_GET_NEXT(heap
, hdr
);
254 * Mark unreachable, finalizable objects.
256 * Such objects will be moved aside and their finalizers run later. They have
257 * to be treated as reachability roots for their properties etc to remain
258 * allocated. This marking is only done for unreachable values which would
259 * be swept later (refzero_list is thus excluded).
261 * Objects are first marked FINALIZABLE and only then marked as reachability
262 * roots; otherwise circular references might be handled inconsistently.
265 DUK_LOCAL
void duk__mark_finalizable(duk_heap
*heap
) {
268 duk_size_t count_finalizable
= 0;
270 DUK_DD(DUK_DDPRINT("duk__mark_finalizable: %p", (void *) heap
));
272 thr
= duk__get_temp_hthread(heap
);
273 DUK_ASSERT(thr
!= NULL
);
275 hdr
= heap
->heap_allocated
;
277 /* A finalizer is looked up from the object and up its prototype chain
278 * (which allows inherited finalizers). A prototype loop must not cause
279 * an error to be thrown here; duk_hobject_hasprop_raw() will ignore a
280 * prototype loop silently and indicate that the property doesn't exist.
283 if (!DUK_HEAPHDR_HAS_REACHABLE(hdr
) &&
284 DUK_HEAPHDR_GET_TYPE(hdr
) == DUK_HTYPE_OBJECT
&&
285 !DUK_HEAPHDR_HAS_FINALIZED(hdr
) &&
286 duk_hobject_hasprop_raw(thr
, (duk_hobject
*) hdr
, DUK_HTHREAD_STRING_INT_FINALIZER(thr
))) {
291 * - is not a finalized object
295 DUK_DD(DUK_DDPRINT("unreachable heap object will be "
296 "finalized -> mark as finalizable "
297 "and treat as a reachability root: %p",
299 DUK_ASSERT(!DUK_HEAPHDR_HAS_READONLY(hdr
));
300 DUK_HEAPHDR_SET_FINALIZABLE(hdr
);
301 count_finalizable
++;
304 hdr
= DUK_HEAPHDR_GET_NEXT(heap
, hdr
);
307 if (count_finalizable
== 0) {
311 DUK_DD(DUK_DDPRINT("marked %ld heap objects as finalizable, now mark them reachable",
312 (long) count_finalizable
));
314 hdr
= heap
->heap_allocated
;
316 if (DUK_HEAPHDR_HAS_FINALIZABLE(hdr
)) {
317 duk__mark_heaphdr(heap
, hdr
);
320 hdr
= DUK_HEAPHDR_GET_NEXT(heap
, hdr
);
323 /* Caller will finish the marking process if we hit a recursion limit. */
327 * Mark objects on finalize_list.
331 DUK_LOCAL
void duk__mark_finalize_list(duk_heap
*heap
) {
334 duk_size_t count_finalize_list
= 0;
337 DUK_DD(DUK_DDPRINT("duk__mark_finalize_list: %p", (void *) heap
));
339 hdr
= heap
->finalize_list
;
341 duk__mark_heaphdr(heap
, hdr
);
342 hdr
= DUK_HEAPHDR_GET_NEXT(heap
, hdr
);
344 count_finalize_list
++;
349 if (count_finalize_list
> 0) {
350 DUK_D(DUK_DPRINT("marked %ld objects on the finalize_list as reachable (previous finalizer run skipped)",
351 (long) count_finalize_list
));
357 * Fallback marking handler if recursion limit is reached.
359 * Iterates 'temproots' until recursion limit is no longer hit. Note
360 * that temproots may reside either in heap allocated list or the
361 * refzero work list. This is a slow scan, but guarantees that we
362 * finish with a bounded C stack.
364 * Note that nodes may have been marked as temproots before this
365 * scan begun, OR they may have been marked during the scan (as
366 * we process nodes recursively also during the scan). This is
371 DUK_LOCAL
void duk__handle_temproot(duk_heap
*heap
, duk_heaphdr
*hdr
, duk_size_t
*count
) {
373 DUK_LOCAL
void duk__handle_temproot(duk_heap
*heap
, duk_heaphdr
*hdr
) {
375 if (!DUK_HEAPHDR_HAS_TEMPROOT(hdr
)) {
376 DUK_DDD(DUK_DDDPRINT("not a temp root: %p", (void *) hdr
));
380 DUK_DDD(DUK_DDDPRINT("found a temp root: %p", (void *) hdr
));
381 DUK_HEAPHDR_CLEAR_TEMPROOT(hdr
);
382 DUK_HEAPHDR_CLEAR_REACHABLE(hdr
); /* done so that duk__mark_heaphdr() works correctly */
383 duk__mark_heaphdr(heap
, hdr
);
390 DUK_LOCAL
void duk__mark_temproots_by_heap_scan(duk_heap
*heap
) {
396 DUK_DD(DUK_DDPRINT("duk__mark_temproots_by_heap_scan: %p", (void *) heap
));
398 while (DUK_HEAP_HAS_MARKANDSWEEP_RECLIMIT_REACHED(heap
)) {
399 DUK_DD(DUK_DDPRINT("recursion limit reached, doing heap scan to continue from temproots"));
404 DUK_HEAP_CLEAR_MARKANDSWEEP_RECLIMIT_REACHED(heap
);
406 hdr
= heap
->heap_allocated
;
409 duk__handle_temproot(heap
, hdr
, &count
);
411 duk__handle_temproot(heap
, hdr
);
413 hdr
= DUK_HEAPHDR_GET_NEXT(heap
, hdr
);
416 /* must also check refzero_list */
417 #ifdef DUK_USE_REFERENCE_COUNTING
418 hdr
= heap
->refzero_list
;
421 duk__handle_temproot(heap
, hdr
, &count
);
423 duk__handle_temproot(heap
, hdr
);
425 hdr
= DUK_HEAPHDR_GET_NEXT(heap
, hdr
);
427 #endif /* DUK_USE_REFERENCE_COUNTING */
430 DUK_DD(DUK_DDPRINT("temproot mark heap scan processed %ld temp roots", (long) count
));
436 * Finalize refcounts for heap elements just about to be freed.
437 * This must be done for all objects before freeing to avoid any
438 * stale pointer dereferences.
440 * Note that this must deduce the set of objects to be freed
441 * identically to duk__sweep_heap().
444 #ifdef DUK_USE_REFERENCE_COUNTING
445 DUK_LOCAL
void duk__finalize_refcounts(duk_heap
*heap
) {
449 thr
= duk__get_temp_hthread(heap
);
450 DUK_ASSERT(thr
!= NULL
);
452 DUK_DD(DUK_DDPRINT("duk__finalize_refcounts: heap=%p, hthread=%p",
453 (void *) heap
, (void *) thr
));
455 hdr
= heap
->heap_allocated
;
457 if (!DUK_HEAPHDR_HAS_REACHABLE(hdr
)) {
459 * Unreachable object about to be swept. Finalize target refcounts
460 * (objects which the unreachable object points to) without doing
461 * refzero processing. Recursive decrefs are also prevented when
462 * refzero processing is disabled.
464 * Value cannot be a finalizable object, as they have been made
465 * temporarily reachable for this round.
468 DUK_DDD(DUK_DDDPRINT("unreachable object, refcount finalize before sweeping: %p", (void *) hdr
));
469 duk_heaphdr_refcount_finalize(thr
, hdr
);
472 hdr
= DUK_HEAPHDR_GET_NEXT(heap
, hdr
);
475 #endif /* DUK_USE_REFERENCE_COUNTING */
478 * Clear (reachable) flags of refzero work list.
481 #ifdef DUK_USE_REFERENCE_COUNTING
482 DUK_LOCAL
void duk__clear_refzero_list_flags(duk_heap
*heap
) {
485 DUK_DD(DUK_DDPRINT("duk__clear_refzero_list_flags: %p", (void *) heap
));
487 hdr
= heap
->refzero_list
;
489 DUK_HEAPHDR_CLEAR_REACHABLE(hdr
);
490 DUK_ASSERT(!DUK_HEAPHDR_HAS_FINALIZABLE(hdr
));
491 DUK_ASSERT(!DUK_HEAPHDR_HAS_FINALIZED(hdr
));
492 DUK_ASSERT(!DUK_HEAPHDR_HAS_TEMPROOT(hdr
));
493 hdr
= DUK_HEAPHDR_GET_NEXT(heap
, hdr
);
496 #endif /* DUK_USE_REFERENCE_COUNTING */
499 * Clear (reachable) flags of finalize_list
501 * We could mostly do in the sweep phase when we move objects from the
502 * heap into the finalize_list. However, if a finalizer run is skipped
503 * during a mark-and-sweep, the objects on the finalize_list will be marked
504 * reachable during the next mark-and-sweep. Since they're already on the
505 * finalize_list, no-one will be clearing their REACHABLE flag so we do it
506 * here. (This now overlaps with the sweep handling in a harmless way.)
509 DUK_LOCAL
void duk__clear_finalize_list_flags(duk_heap
*heap
) {
512 DUK_DD(DUK_DDPRINT("duk__clear_finalize_list_flags: %p", (void *) heap
));
514 hdr
= heap
->finalize_list
;
516 DUK_HEAPHDR_CLEAR_REACHABLE(hdr
);
517 DUK_ASSERT(!DUK_HEAPHDR_HAS_FINALIZABLE(hdr
));
518 DUK_ASSERT(!DUK_HEAPHDR_HAS_FINALIZED(hdr
));
519 DUK_ASSERT(!DUK_HEAPHDR_HAS_TEMPROOT(hdr
));
520 hdr
= DUK_HEAPHDR_GET_NEXT(heap
, hdr
);
528 #if defined(DUK_USE_STRTAB_CHAIN)
530 /* XXX: skip count_free w/o debug? */
531 #if defined(DUK_USE_HEAPPTR16)
532 DUK_LOCAL
void duk__sweep_string_chain16(duk_heap
*heap
, duk_uint16_t
*slot
, duk_size_t
*count_keep
, duk_size_t
*count_free
) {
533 duk_uint16_t h16
= *slot
;
535 duk_uint16_t null16
= heap
->heapptr_null16
;
541 h
= (duk_hstring
*) DUK_USE_HEAPPTR_DEC16(heap
->heap_udata
, h16
);
542 DUK_ASSERT(h
!= NULL
);
544 if (DUK_HEAPHDR_HAS_REACHABLE((duk_heaphdr
*) h
)) {
545 DUK_HEAPHDR_CLEAR_REACHABLE((duk_heaphdr
*) h
);
548 #if defined(DUK_USE_REFERENCE_COUNTING)
549 DUK_ASSERT(DUK_HEAPHDR_GET_REFCOUNT((duk_heaphdr
*) h
) == 0);
551 /* deal with weak references first */
552 duk_heap_strcache_string_remove(heap
, (duk_hstring
*) h
);
555 /* free inner references (these exist e.g. when external
556 * strings are enabled)
558 duk_free_hstring_inner(heap
, h
);
563 #else /* DUK_USE_HEAPPTR16 */
564 DUK_LOCAL
void duk__sweep_string_chain(duk_heap
*heap
, duk_hstring
**slot
, duk_size_t
*count_keep
, duk_size_t
*count_free
) {
565 duk_hstring
*h
= *slot
;
572 if (DUK_HEAPHDR_HAS_REACHABLE((duk_heaphdr
*) h
)) {
573 DUK_HEAPHDR_CLEAR_REACHABLE((duk_heaphdr
*) h
);
576 #if defined(DUK_USE_REFERENCE_COUNTING)
577 DUK_ASSERT(DUK_HEAPHDR_GET_REFCOUNT((duk_heaphdr
*) h
) == 0);
579 /* deal with weak references first */
580 duk_heap_strcache_string_remove(heap
, (duk_hstring
*) h
);
583 /* free inner references (these exist e.g. when external
584 * strings are enabled)
586 duk_free_hstring_inner(heap
, h
);
591 #endif /* DUK_USE_HEAPPTR16 */
593 DUK_LOCAL
void duk__sweep_stringtable_chain(duk_heap
*heap
, duk_size_t
*out_count_keep
) {
596 duk_size_t count_free
= 0;
597 duk_size_t count_keep
= 0;
599 #if defined(DUK_USE_HEAPPTR16)
605 DUK_DD(DUK_DDPRINT("duk__sweep_stringtable: %p", (void *) heap
));
607 /* Non-zero refcounts should not happen for unreachable strings,
608 * because we refcount finalize all unreachable objects which
609 * should have decreased unreachable string refcounts to zero
613 for (i
= 0; i
< DUK_STRTAB_CHAIN_SIZE
; i
++) {
614 e
= heap
->strtable
+ i
;
615 if (e
->listlen
== 0) {
616 #if defined(DUK_USE_HEAPPTR16)
617 duk__sweep_string_chain16(heap
, &e
->u
.str16
, &count_keep
, &count_free
);
619 duk__sweep_string_chain(heap
, &e
->u
.str
, &count_keep
, &count_free
);
622 #if defined(DUK_USE_HEAPPTR16)
623 lst
= (duk_uint16_t
*) DUK_USE_HEAPPTR_DEC16(heap
->heap_udata
, e
->u
.strlist16
);
627 for (j
= 0, n
= e
->listlen
; j
< n
; j
++) {
628 #if defined(DUK_USE_HEAPPTR16)
629 duk__sweep_string_chain16(heap
, lst
+ j
, &count_keep
, &count_free
);
631 duk__sweep_string_chain(heap
, lst
+ j
, &count_keep
, &count_free
);
637 DUK_D(DUK_DPRINT("mark-and-sweep sweep stringtable: %ld freed, %ld kept",
638 (long) count_free
, (long) count_keep
));
639 *out_count_keep
= count_keep
;
641 #endif /* DUK_USE_STRTAB_CHAIN */
643 #if defined(DUK_USE_STRTAB_PROBE)
644 DUK_LOCAL
void duk__sweep_stringtable_probe(duk_heap
*heap
, duk_size_t
*out_count_keep
) {
648 duk_size_t count_free
= 0;
650 duk_size_t count_keep
= 0;
652 DUK_DD(DUK_DDPRINT("duk__sweep_stringtable: %p", (void *) heap
));
654 for (i
= 0; i
< heap
->st_size
; i
++) {
655 #if defined(DUK_USE_HEAPPTR16)
656 h
= (duk_hstring
*) DUK_USE_HEAPPTR_DEC16(heap
->heap_udata
, heap
->strtable16
[i
]);
658 h
= heap
->strtable
[i
];
660 if (h
== NULL
|| h
== DUK_STRTAB_DELETED_MARKER(heap
)) {
662 } else if (DUK_HEAPHDR_HAS_REACHABLE((duk_heaphdr
*) h
)) {
663 DUK_HEAPHDR_CLEAR_REACHABLE((duk_heaphdr
*) h
);
672 #if defined(DUK_USE_REFERENCE_COUNTING)
673 /* Non-zero refcounts should not happen for unreachable strings,
674 * because we refcount finalize all unreachable objects which
675 * should have decreased unreachable string refcounts to zero
678 DUK_ASSERT(DUK_HEAPHDR_GET_REFCOUNT((duk_heaphdr
*) h
) == 0);
681 DUK_DDD(DUK_DDDPRINT("sweep string, not reachable: %p", (void *) h
));
683 /* deal with weak references first */
684 duk_heap_strcache_string_remove(heap
, (duk_hstring
*) h
);
686 /* remove the string (mark DELETED), could also call
687 * duk_heap_string_remove() but that would be slow and
688 * pointless because we already know the slot.
690 #if defined(DUK_USE_HEAPPTR16)
691 heap
->strtable16
[i
] = heap
->heapptr_deleted16
;
693 heap
->strtable
[i
] = DUK_STRTAB_DELETED_MARKER(heap
);
696 /* free inner references (these exist e.g. when external
697 * strings are enabled)
699 duk_free_hstring_inner(heap
, (duk_hstring
*) h
);
701 /* finally free the struct itself */
706 DUK_D(DUK_DPRINT("mark-and-sweep sweep stringtable: %ld freed, %ld kept",
707 (long) count_free
, (long) count_keep
));
709 *out_count_keep
= count_keep
;
711 #endif /* DUK_USE_STRTAB_PROBE */
717 DUK_LOCAL
void duk__sweep_heap(duk_heap
*heap
, duk_int_t flags
, duk_size_t
*out_count_keep
) {
718 duk_heaphdr
*prev
; /* last element that was left in the heap */
722 duk_size_t count_free
= 0;
723 duk_size_t count_finalize
= 0;
724 duk_size_t count_rescue
= 0;
726 duk_size_t count_keep
= 0;
729 DUK_DD(DUK_DDPRINT("duk__sweep_heap: %p", (void *) heap
));
732 curr
= heap
->heap_allocated
;
733 heap
->heap_allocated
= NULL
;
735 /* Strings and ROM objects are never placed on the heap allocated list. */
736 DUK_ASSERT(DUK_HEAPHDR_GET_TYPE(curr
) != DUK_HTYPE_STRING
);
737 DUK_ASSERT(!DUK_HEAPHDR_HAS_READONLY(curr
));
739 next
= DUK_HEAPHDR_GET_NEXT(heap
, curr
);
741 if (DUK_HEAPHDR_HAS_REACHABLE(curr
)) {
743 * Reachable object, keep
746 DUK_DDD(DUK_DDDPRINT("sweep, reachable: %p", (void *) curr
));
748 if (DUK_HEAPHDR_HAS_FINALIZABLE(curr
)) {
750 * If object has been marked finalizable, move it to the
751 * "to be finalized" work list. It will be collected on
752 * the next mark-and-sweep if it is still unreachable
753 * after running the finalizer.
756 DUK_ASSERT(!DUK_HEAPHDR_HAS_FINALIZED(curr
));
757 DUK_ASSERT(DUK_HEAPHDR_GET_TYPE(curr
) == DUK_HTYPE_OBJECT
);
758 DUK_DDD(DUK_DDDPRINT("object has finalizer, move to finalization work list: %p", (void *) curr
));
760 #ifdef DUK_USE_DOUBLE_LINKED_HEAP
761 if (heap
->finalize_list
) {
762 DUK_HEAPHDR_SET_PREV(heap
, heap
->finalize_list
, curr
);
764 DUK_HEAPHDR_SET_PREV(heap
, curr
, NULL
);
766 DUK_HEAPHDR_SET_NEXT(heap
, curr
, heap
->finalize_list
);
767 DUK_ASSERT_HEAPHDR_LINKS(heap
, curr
);
768 heap
->finalize_list
= curr
;
774 * Object will be kept; queue object back to heap_allocated (to tail)
777 if (DUK_HEAPHDR_HAS_FINALIZED(curr
)) {
779 * Object's finalizer was executed on last round, and
780 * object has been happily rescued.
783 DUK_ASSERT(!DUK_HEAPHDR_HAS_FINALIZABLE(curr
));
784 DUK_ASSERT(DUK_HEAPHDR_GET_TYPE(curr
) == DUK_HTYPE_OBJECT
);
785 DUK_DD(DUK_DDPRINT("object rescued during mark-and-sweep finalization: %p", (void *) curr
));
791 * Plain, boring reachable object.
793 DUK_DD(DUK_DDPRINT("keep object: %!iO", curr
));
797 if (!heap
->heap_allocated
) {
798 heap
->heap_allocated
= curr
;
801 DUK_HEAPHDR_SET_NEXT(heap
, prev
, curr
);
803 #ifdef DUK_USE_DOUBLE_LINKED_HEAP
804 DUK_HEAPHDR_SET_PREV(heap
, curr
, prev
);
806 DUK_ASSERT_HEAPHDR_LINKS(heap
, prev
);
807 DUK_ASSERT_HEAPHDR_LINKS(heap
, curr
);
811 DUK_HEAPHDR_CLEAR_REACHABLE(curr
);
812 DUK_HEAPHDR_CLEAR_FINALIZED(curr
);
813 DUK_HEAPHDR_CLEAR_FINALIZABLE(curr
);
815 DUK_ASSERT(!DUK_HEAPHDR_HAS_REACHABLE(curr
));
816 DUK_ASSERT(!DUK_HEAPHDR_HAS_FINALIZED(curr
));
817 DUK_ASSERT(!DUK_HEAPHDR_HAS_FINALIZABLE(curr
));
822 * Unreachable object, free
825 DUK_DDD(DUK_DDDPRINT("sweep, not reachable: %p", (void *) curr
));
827 #if defined(DUK_USE_REFERENCE_COUNTING)
828 /* Non-zero refcounts should not happen because we refcount
829 * finalize all unreachable objects which should cancel out
830 * refcounts (even for cycles).
832 DUK_ASSERT(DUK_HEAPHDR_GET_REFCOUNT(curr
) == 0);
834 DUK_ASSERT(!DUK_HEAPHDR_HAS_FINALIZABLE(curr
));
836 if (DUK_HEAPHDR_HAS_FINALIZED(curr
)) {
837 DUK_DDD(DUK_DDDPRINT("finalized object not rescued: %p", (void *) curr
));
840 /* Note: object cannot be a finalizable unreachable object, as
841 * they have been marked temporarily reachable for this round,
842 * and are handled above.
849 /* weak refs should be handled here, but no weak refs for
850 * any non-string objects exist right now.
853 /* free object and all auxiliary (non-heap) allocs */
854 duk_heap_free_heaphdr_raw(heap
, curr
);
860 DUK_HEAPHDR_SET_NEXT(heap
, prev
, NULL
);
862 DUK_ASSERT_HEAPHDR_LINKS(heap
, prev
);
865 DUK_D(DUK_DPRINT("mark-and-sweep sweep objects (non-string): %ld freed, %ld kept, %ld rescued, %ld queued for finalization",
866 (long) count_free
, (long) count_keep
, (long) count_rescue
, (long) count_finalize
));
868 *out_count_keep
= count_keep
;
872 * Run (object) finalizers in the "to be finalized" work list.
875 DUK_LOCAL
void duk__run_object_finalizers(duk_heap
*heap
, duk_small_uint_t flags
) {
879 duk_size_t count
= 0;
883 DUK_DD(DUK_DDPRINT("duk__run_object_finalizers: %p", (void *) heap
));
885 thr
= duk__get_temp_hthread(heap
);
886 DUK_ASSERT(thr
!= NULL
);
888 curr
= heap
->finalize_list
;
890 DUK_DDD(DUK_DDDPRINT("mark-and-sweep finalize: %p", (void *) curr
));
892 DUK_ASSERT(DUK_HEAPHDR_GET_TYPE(curr
) == DUK_HTYPE_OBJECT
); /* only objects have finalizers */
893 DUK_ASSERT(!DUK_HEAPHDR_HAS_REACHABLE(curr
)); /* flags have been already cleared */
894 DUK_ASSERT(!DUK_HEAPHDR_HAS_TEMPROOT(curr
));
895 DUK_ASSERT(!DUK_HEAPHDR_HAS_FINALIZABLE(curr
));
896 DUK_ASSERT(!DUK_HEAPHDR_HAS_FINALIZED(curr
));
897 DUK_ASSERT(!DUK_HEAPHDR_HAS_READONLY(curr
)); /* No finalizers for ROM objects */
899 if (DUK_LIKELY((flags
& DUK_MS_FLAG_SKIP_FINALIZERS
) == 0)) {
900 /* Run the finalizer, duk_hobject_run_finalizer() sets FINALIZED.
901 * Next mark-and-sweep will collect the object unless it has
902 * become reachable (i.e. rescued). FINALIZED prevents the
903 * finalizer from being executed again before that.
905 duk_hobject_run_finalizer(thr
, (duk_hobject
*) curr
); /* must never longjmp */
906 DUK_ASSERT(DUK_HEAPHDR_HAS_FINALIZED(curr
));
908 /* Used during heap destruction: don't actually run finalizers
909 * because we're heading into forced finalization. Instead,
910 * queue finalizable objects back to the heap_allocated list.
912 DUK_D(DUK_DPRINT("skip finalizers flag set, queue object to heap_allocated without finalizing"));
913 DUK_ASSERT(!DUK_HEAPHDR_HAS_FINALIZED(curr
));
916 /* queue back to heap_allocated */
917 next
= DUK_HEAPHDR_GET_NEXT(heap
, curr
);
918 DUK_HEAP_INSERT_INTO_HEAP_ALLOCATED(heap
, curr
);
926 /* finalize_list will always be processed completely */
927 heap
->finalize_list
= NULL
;
930 DUK_D(DUK_DPRINT("mark-and-sweep finalize objects: %ld finalizers called", (long) count
));
937 * Compaction is assumed to never throw an error.
940 DUK_LOCAL
int duk__protected_compact_object(duk_context
*ctx
) {
941 /* XXX: for threads, compact value stack, call stack, catch stack? */
943 duk_hobject
*obj
= duk_get_hobject(ctx
, -1);
944 DUK_ASSERT(obj
!= NULL
);
945 duk_hobject_compact_props((duk_hthread
*) ctx
, obj
);
950 DUK_LOCAL
void duk__compact_object_list(duk_heap
*heap
, duk_hthread
*thr
, duk_heaphdr
*start
, duk_size_t
*p_count_check
, duk_size_t
*p_count_compact
, duk_size_t
*p_count_bytes_saved
) {
952 DUK_LOCAL
void duk__compact_object_list(duk_heap
*heap
, duk_hthread
*thr
, duk_heaphdr
*start
) {
956 duk_size_t old_size
, new_size
;
964 DUK_DDD(DUK_DDDPRINT("mark-and-sweep compact: %p", (void *) curr
));
966 if (DUK_HEAPHDR_GET_TYPE(curr
) != DUK_HTYPE_OBJECT
) {
969 obj
= (duk_hobject
*) curr
;
972 old_size
= DUK_HOBJECT_P_COMPUTE_SIZE(DUK_HOBJECT_GET_ESIZE(obj
),
973 DUK_HOBJECT_GET_ASIZE(obj
),
974 DUK_HOBJECT_GET_HSIZE(obj
));
977 DUK_DD(DUK_DDPRINT("compact object: %p", (void *) obj
));
978 duk_push_hobject((duk_context
*) thr
, obj
);
979 /* XXX: disable error handlers for duration of compaction? */
980 duk_safe_call((duk_context
*) thr
, duk__protected_compact_object
, 1, 0);
983 new_size
= DUK_HOBJECT_P_COMPUTE_SIZE(DUK_HOBJECT_GET_ESIZE(obj
),
984 DUK_HOBJECT_GET_ASIZE(obj
),
985 DUK_HOBJECT_GET_HSIZE(obj
));
989 (*p_count_compact
)++;
990 (*p_count_bytes_saved
) += (duk_size_t
) (old_size
- new_size
);
994 curr
= DUK_HEAPHDR_GET_NEXT(heap
, curr
);
1001 DUK_LOCAL
void duk__compact_objects(duk_heap
*heap
) {
1002 /* XXX: which lists should participate? to be finalized? */
1003 #ifdef DUK_USE_DEBUG
1004 duk_size_t count_check
= 0;
1005 duk_size_t count_compact
= 0;
1006 duk_size_t count_bytes_saved
= 0;
1010 DUK_DD(DUK_DDPRINT("duk__compact_objects: %p", (void *) heap
));
1012 thr
= duk__get_temp_hthread(heap
);
1013 DUK_ASSERT(thr
!= NULL
);
1015 #ifdef DUK_USE_DEBUG
1016 duk__compact_object_list(heap
, thr
, heap
->heap_allocated
, &count_check
, &count_compact
, &count_bytes_saved
);
1017 duk__compact_object_list(heap
, thr
, heap
->finalize_list
, &count_check
, &count_compact
, &count_bytes_saved
);
1018 #ifdef DUK_USE_REFERENCE_COUNTING
1019 duk__compact_object_list(heap
, thr
, heap
->refzero_list
, &count_check
, &count_compact
, &count_bytes_saved
);
1022 duk__compact_object_list(heap
, thr
, heap
->heap_allocated
);
1023 duk__compact_object_list(heap
, thr
, heap
->finalize_list
);
1024 #ifdef DUK_USE_REFERENCE_COUNTING
1025 duk__compact_object_list(heap
, thr
, heap
->refzero_list
);
1029 #ifdef DUK_USE_DEBUG
1030 DUK_D(DUK_DPRINT("mark-and-sweep compact objects: %ld checked, %ld compaction attempts, %ld bytes saved by compaction",
1031 (long) count_check
, (long) count_compact
, (long) count_bytes_saved
));
1036 * Assertion helpers.
1039 #ifdef DUK_USE_ASSERTIONS
1040 DUK_LOCAL
void duk__assert_heaphdr_flags(duk_heap
*heap
) {
1043 hdr
= heap
->heap_allocated
;
1045 DUK_ASSERT(!DUK_HEAPHDR_HAS_REACHABLE(hdr
));
1046 DUK_ASSERT(!DUK_HEAPHDR_HAS_TEMPROOT(hdr
));
1047 DUK_ASSERT(!DUK_HEAPHDR_HAS_FINALIZABLE(hdr
));
1048 /* may have FINALIZED */
1049 hdr
= DUK_HEAPHDR_GET_NEXT(heap
, hdr
);
1052 #ifdef DUK_USE_REFERENCE_COUNTING
1053 hdr
= heap
->refzero_list
;
1055 DUK_ASSERT(!DUK_HEAPHDR_HAS_REACHABLE(hdr
));
1056 DUK_ASSERT(!DUK_HEAPHDR_HAS_TEMPROOT(hdr
));
1057 DUK_ASSERT(!DUK_HEAPHDR_HAS_FINALIZABLE(hdr
));
1058 DUK_ASSERT(!DUK_HEAPHDR_HAS_FINALIZED(hdr
));
1059 hdr
= DUK_HEAPHDR_GET_NEXT(heap
, hdr
);
1061 #endif /* DUK_USE_REFERENCE_COUNTING */
1064 #ifdef DUK_USE_REFERENCE_COUNTING
1065 DUK_LOCAL
void duk__assert_valid_refcounts(duk_heap
*heap
) {
1066 duk_heaphdr
*hdr
= heap
->heap_allocated
;
1068 if (DUK_HEAPHDR_GET_REFCOUNT(hdr
) == 0 &&
1069 DUK_HEAPHDR_HAS_FINALIZED(hdr
)) {
1070 /* An object may be in heap_allocated list with a zero
1071 * refcount if it has just been finalized and is waiting
1072 * to be collected by the next cycle.
1074 } else if (DUK_HEAPHDR_GET_REFCOUNT(hdr
) == 0) {
1075 /* An object may be in heap_allocated list with a zero
1076 * refcount also if it is a temporary object created by
1077 * a finalizer; because finalization now runs inside
1078 * mark-and-sweep, such objects will not be queued to
1079 * refzero_list and will thus appear here with refcount
1082 #if 0 /* this case can no longer occur because refcount is unsigned */
1083 } else if (DUK_HEAPHDR_GET_REFCOUNT(hdr
) < 0) {
1084 DUK_D(DUK_DPRINT("invalid refcount: %ld, %p -> %!O",
1085 (hdr
!= NULL
? (long) DUK_HEAPHDR_GET_REFCOUNT(hdr
) : (long) 0),
1086 (void *) hdr
, (duk_heaphdr
*) hdr
));
1087 DUK_ASSERT(DUK_HEAPHDR_GET_REFCOUNT(hdr
) > 0);
1090 hdr
= DUK_HEAPHDR_GET_NEXT(heap
, hdr
);
1093 #endif /* DUK_USE_REFERENCE_COUNTING */
1094 #endif /* DUK_USE_ASSERTIONS */
1097 * Finalizer torture. Do one fake finalizer call which causes side effects
1098 * similar to one or more finalizers on actual objects.
1101 #if defined(DUK_USE_MARKANDSWEEP_FINALIZER_TORTURE)
1102 DUK_LOCAL duk_ret_t
duk__markandsweep_fake_finalizer(duk_context
*ctx
) {
1103 DUK_D(DUK_DPRINT("fake mark-and-sweep torture finalizer executed"));
1105 /* Require a lot of stack to force a value stack grow/shrink.
1106 * Recursive mark-and-sweep is prevented by allocation macros
1107 * so this won't trigger another mark-and-sweep.
1109 duk_require_stack(ctx
, 100000);
1111 /* XXX: do something to force a callstack grow/shrink, perhaps
1112 * just a manual forced resize or a forced relocating realloc?
1118 DUK_LOCAL
void duk__markandsweep_torture_finalizer(duk_hthread
*thr
) {
1122 DUK_ASSERT(thr
!= NULL
);
1123 ctx
= (duk_context
*) thr
;
1125 /* Avoid fake finalization when callstack limit has been reached.
1126 * Otherwise a callstack limit error will be created, then refzero'ed.
1128 if (thr
->heap
->call_recursion_depth
>= thr
->heap
->call_recursion_limit
||
1129 thr
->callstack_size
+ 2 * DUK_CALLSTACK_GROW_STEP
>= thr
->callstack_max
/*approximate*/) {
1130 DUK_D(DUK_DPRINT("call recursion depth reached, avoid fake mark-and-sweep torture finalizer"));
1134 /* Run fake finalizer. Avoid creating unnecessary garbage. */
1135 duk_push_c_function(ctx
, duk__markandsweep_fake_finalizer
, 0 /*nargs*/);
1136 rc
= duk_pcall(ctx
, 0 /*nargs*/);
1137 DUK_UNREF(rc
); /* ignored */
1140 #endif /* DUK_USE_MARKANDSWEEP_FINALIZER_TORTURE */
1143 * Main mark-and-sweep function.
1145 * 'flags' represents the features requested by the caller. The current
1146 * heap->mark_and_sweep_base_flags is ORed automatically into the flags;
1147 * the base flags mask typically prevents certain mark-and-sweep operations
1151 DUK_INTERNAL duk_bool_t
duk_heap_mark_and_sweep(duk_heap
*heap
, duk_small_uint_t flags
) {
1153 duk_size_t count_keep_obj
;
1154 duk_size_t count_keep_str
;
1155 #ifdef DUK_USE_VOLUNTARY_GC
1159 /* XXX: thread selection for mark-and-sweep is currently a hack.
1160 * If we don't have a thread, the entire mark-and-sweep is now
1161 * skipped (although we could just skip finalizations).
1164 /* If thr != NULL, the thr may still be in the middle of
1166 * XXX: Improve the thread viability test.
1168 thr
= duk__get_temp_hthread(heap
);
1170 DUK_D(DUK_DPRINT("gc skipped because we don't have a temp thread"));
1172 /* reset voluntary gc trigger count */
1173 #ifdef DUK_USE_VOLUNTARY_GC
1174 heap
->mark_and_sweep_trigger_counter
= DUK_HEAP_MARK_AND_SWEEP_TRIGGER_SKIP
;
1179 /* If debugger is paused, garbage collection is disabled by default. */
1180 /* XXX: will need a force flag if garbage collection is triggered
1181 * explicitly during paused state.
1183 #if defined(DUK_USE_DEBUGGER_SUPPORT)
1184 if (DUK_HEAP_IS_PAUSED(heap
)) {
1185 /* Checking this here rather that in memory alloc primitives
1186 * reduces checking code there but means a failed allocation
1187 * will go through a few retries before giving up. That's
1188 * fine because this only happens during debugging.
1190 DUK_D(DUK_DPRINT("gc skipped because debugger is paused"));
1195 DUK_D(DUK_DPRINT("garbage collect (mark-and-sweep) starting, requested flags: 0x%08lx, effective flags: 0x%08lx",
1196 (unsigned long) flags
, (unsigned long) (flags
| heap
->mark_and_sweep_base_flags
)));
1198 flags
|= heap
->mark_and_sweep_base_flags
;
1204 #ifdef DUK_USE_ASSERTIONS
1205 DUK_ASSERT(!DUK_HEAP_HAS_MARKANDSWEEP_RUNNING(heap
));
1206 DUK_ASSERT(!DUK_HEAP_HAS_MARKANDSWEEP_RECLIMIT_REACHED(heap
));
1207 DUK_ASSERT(heap
->mark_and_sweep_recursion_depth
== 0);
1208 duk__assert_heaphdr_flags(heap
);
1209 #ifdef DUK_USE_REFERENCE_COUNTING
1210 /* Note: DUK_HEAP_HAS_REFZERO_FREE_RUNNING(heap) may be true; a refcount
1211 * finalizer may trigger a mark-and-sweep.
1213 duk__assert_valid_refcounts(heap
);
1214 #endif /* DUK_USE_REFERENCE_COUNTING */
1215 #endif /* DUK_USE_ASSERTIONS */
1221 DUK_HEAP_SET_MARKANDSWEEP_RUNNING(heap
);
1224 * Mark roots, hoping that recursion limit is not normally hit.
1225 * If recursion limit is hit, run additional reachability rounds
1226 * starting from "temproots" until marking is complete.
1228 * Marking happens in two phases: first we mark actual reachability
1229 * roots (and run "temproots" to complete the process). Then we
1230 * check which objects are unreachable and are finalizable; such
1231 * objects are marked as FINALIZABLE and marked as reachability
1232 * (and "temproots" is run again to complete the process).
1234 * The heap finalize_list must also be marked as a reachability root.
1235 * There may be objects on the list from a previous round if the
1236 * previous run had finalizer skip flag.
1239 duk__mark_roots_heap(heap
); /* main reachability roots */
1240 #ifdef DUK_USE_REFERENCE_COUNTING
1241 duk__mark_refzero_list(heap
); /* refzero_list treated as reachability roots */
1243 duk__mark_temproots_by_heap_scan(heap
); /* temproots */
1245 duk__mark_finalizable(heap
); /* mark finalizable as reachability roots */
1246 duk__mark_finalize_list(heap
); /* mark finalizer work list as reachability roots */
1247 duk__mark_temproots_by_heap_scan(heap
); /* temproots */
1250 * Sweep garbage and remove marking flags, and move objects with
1251 * finalizers to the finalizer work list.
1253 * Objects to be swept need to get their refcounts finalized before
1254 * they are swept. In other words, their target object refcounts
1255 * need to be decreased. This has to be done before freeing any
1256 * objects to avoid decref'ing dangling pointers (which may happen
1257 * even without bugs, e.g. with reference loops)
1259 * Because strings don't point to other heap objects, similar
1260 * finalization is not necessary for strings.
1263 /* XXX: more emergency behavior, e.g. find smaller hash sizes etc */
1265 #ifdef DUK_USE_REFERENCE_COUNTING
1266 duk__finalize_refcounts(heap
);
1268 duk__sweep_heap(heap
, flags
, &count_keep_obj
);
1269 #if defined(DUK_USE_STRTAB_CHAIN)
1270 duk__sweep_stringtable_chain(heap
, &count_keep_str
);
1271 #elif defined(DUK_USE_STRTAB_PROBE)
1272 duk__sweep_stringtable_probe(heap
, &count_keep_str
);
1274 #error internal error, invalid strtab options
1276 #ifdef DUK_USE_REFERENCE_COUNTING
1277 duk__clear_refzero_list_flags(heap
);
1279 duk__clear_finalize_list_flags(heap
);
1282 * Object compaction (emergency only).
1284 * Object compaction is a separate step after sweeping, as there is
1285 * more free memory for it to work with. Also, currently compaction
1286 * may insert new objects into the heap allocated list and the string
1287 * table which we don't want to do during a sweep (the reachability
1288 * flags of such objects would be incorrect). The objects inserted
1291 * - a temporary duk_hbuffer for a new properties allocation
1292 * - if array part is abandoned, string keys are interned
1294 * The object insertions go to the front of the list, so they do not
1295 * cause an infinite loop (they are not compacted).
1298 if ((flags
& DUK_MS_FLAG_EMERGENCY
) &&
1299 !(flags
& DUK_MS_FLAG_NO_OBJECT_COMPACTION
)) {
1300 duk__compact_objects(heap
);
1304 * String table resize check.
1306 * Note: this may silently (and safely) fail if GC is caused by an
1307 * allocation call in stringtable resize_hash(). Resize_hash()
1308 * will prevent a recursive call to itself by setting the
1309 * DUK_MS_FLAG_NO_STRINGTABLE_RESIZE in heap->mark_and_sweep_base_flags.
1312 /* XXX: stringtable emergency compaction? */
1314 /* XXX: remove this feature entirely? it would only matter for
1315 * emergency GC. Disable for lowest memory builds.
1317 #if defined(DUK_USE_MS_STRINGTABLE_RESIZE)
1318 if (!(flags
& DUK_MS_FLAG_NO_STRINGTABLE_RESIZE
)) {
1319 DUK_DD(DUK_DDPRINT("resize stringtable: %p", (void *) heap
));
1320 duk_heap_force_strtab_resize(heap
);
1322 DUK_D(DUK_DPRINT("stringtable resize skipped because DUK_MS_FLAG_NO_STRINGTABLE_RESIZE is set"));
1327 * Finalize objects in the finalization work list. Finalized
1328 * objects are queued back to heap_allocated with FINALIZED set.
1330 * Since finalizers may cause arbitrary side effects, they are
1331 * prevented during string table and object property allocation
1332 * resizing using the DUK_MS_FLAG_NO_FINALIZERS flag in
1333 * heap->mark_and_sweep_base_flags. In this case the objects
1334 * remain in the finalization work list after mark-and-sweep
1335 * exits and they may be finalized on the next pass.
1337 * Finalization currently happens inside "MARKANDSWEEP_RUNNING"
1338 * protection (no mark-and-sweep may be triggered by the
1339 * finalizers). As a side effect:
1341 * 1) an out-of-memory error inside a finalizer will not
1342 * cause a mark-and-sweep and may cause the finalizer
1343 * to fail unnecessarily
1345 * 2) any temporary objects whose refcount decreases to zero
1346 * during finalization will not be put into refzero_list;
1347 * they can only be collected by another mark-and-sweep
1349 * This is not optimal, but since the sweep for this phase has
1350 * already happened, this is probably good enough for now.
1353 #if defined(DUK_USE_MARKANDSWEEP_FINALIZER_TORTURE)
1354 /* Cannot simulate individual finalizers because finalize_list only
1355 * contains objects with actual finalizers. But simulate side effects
1356 * from finalization by doing a bogus function call and resizing the
1359 if (flags
& DUK_MS_FLAG_NO_FINALIZERS
) {
1360 DUK_D(DUK_DPRINT("skip mark-and-sweep torture finalizer, DUK_MS_FLAG_NO_FINALIZERS is set"));
1361 } else if (!(thr
->valstack
!= NULL
&& thr
->callstack
!= NULL
&& thr
->catchstack
!= NULL
)) {
1362 DUK_D(DUK_DPRINT("skip mark-and-sweep torture finalizer, thread not yet viable"));
1364 DUK_D(DUK_DPRINT("run mark-and-sweep torture finalizer"));
1365 duk__markandsweep_torture_finalizer(thr
);
1367 #endif /* DUK_USE_MARKANDSWEEP_FINALIZER_TORTURE */
1369 if (flags
& DUK_MS_FLAG_NO_FINALIZERS
) {
1370 DUK_D(DUK_DPRINT("finalizer run skipped because DUK_MS_FLAG_NO_FINALIZERS is set"));
1372 duk__run_object_finalizers(heap
, flags
);
1379 DUK_HEAP_CLEAR_MARKANDSWEEP_RUNNING(heap
);
1385 #ifdef DUK_USE_ASSERTIONS
1386 DUK_ASSERT(!DUK_HEAP_HAS_MARKANDSWEEP_RUNNING(heap
));
1387 DUK_ASSERT(!DUK_HEAP_HAS_MARKANDSWEEP_RECLIMIT_REACHED(heap
));
1388 DUK_ASSERT(heap
->mark_and_sweep_recursion_depth
== 0);
1389 duk__assert_heaphdr_flags(heap
);
1390 #ifdef DUK_USE_REFERENCE_COUNTING
1391 /* Note: DUK_HEAP_HAS_REFZERO_FREE_RUNNING(heap) may be true; a refcount
1392 * finalizer may trigger a mark-and-sweep.
1394 duk__assert_valid_refcounts(heap
);
1395 #endif /* DUK_USE_REFERENCE_COUNTING */
1396 #endif /* DUK_USE_ASSERTIONS */
1399 * Reset trigger counter
1402 #ifdef DUK_USE_VOLUNTARY_GC
1403 tmp
= (count_keep_obj
+ count_keep_str
) / 256;
1404 heap
->mark_and_sweep_trigger_counter
= (duk_int_t
) (
1405 (tmp
* DUK_HEAP_MARK_AND_SWEEP_TRIGGER_MULT
) +
1406 DUK_HEAP_MARK_AND_SWEEP_TRIGGER_ADD
);
1407 DUK_D(DUK_DPRINT("garbage collect (mark-and-sweep) finished: %ld objects kept, %ld strings kept, trigger reset to %ld",
1408 (long) count_keep_obj
, (long) count_keep_str
, (long) heap
->mark_and_sweep_trigger_counter
));
1410 DUK_D(DUK_DPRINT("garbage collect (mark-and-sweep) finished: %ld objects kept, %ld strings kept, no voluntary trigger",
1411 (long) count_keep_obj
, (long) count_keep_str
));
1417 #else /* DUK_USE_MARK_AND_SWEEP */
1419 /* no mark-and-sweep gc */
1421 #endif /* DUK_USE_MARK_AND_SWEEP */