--- /dev/null
+/*
+ * Mark-and-sweep garbage collection.
+ */
+
+#include "duk_internal.h"
+
+#ifdef DUK_USE_MARK_AND_SWEEP
+
+DUK_LOCAL_DECL void duk__mark_heaphdr(duk_heap *heap, duk_heaphdr *h);
+DUK_LOCAL_DECL void duk__mark_tval(duk_heap *heap, duk_tval *tv);
+
+/*
+ * Misc
+ */
+
+/* Select a thread for mark-and-sweep use.
+ *
+ * XXX: This needs to change later.
+ */
+DUK_LOCAL duk_hthread *duk__get_temp_hthread(duk_heap *heap) {
+ if (heap->curr_thread) {
+ return heap->curr_thread;
+ }
+ return heap->heap_thread; /* may be NULL, too */
+}
+
+/*
+ * Marking functions for heap types: mark children recursively
+ */
+
+DUK_LOCAL void duk__mark_hstring(duk_heap *heap, duk_hstring *h) {
+ DUK_UNREF(heap);
+ DUK_UNREF(h);
+
+ DUK_DDD(DUK_DDDPRINT("duk__mark_hstring: %p", (void *) h));
+ DUK_ASSERT(h);
+
+ /* nothing to process */
+}
+
+DUK_LOCAL void duk__mark_hobject(duk_heap *heap, duk_hobject *h) {
+ duk_uint_fast32_t i;
+
+ DUK_DDD(DUK_DDDPRINT("duk__mark_hobject: %p", (void *) h));
+
+ DUK_ASSERT(h);
+
+ /* XXX: use advancing pointers instead of index macros -> faster and smaller? */
+
+ for (i = 0; i < (duk_uint_fast32_t) DUK_HOBJECT_GET_ENEXT(h); i++) {
+ duk_hstring *key = DUK_HOBJECT_E_GET_KEY(heap, h, i);
+ if (!key) {
+ continue;
+ }
+ duk__mark_heaphdr(heap, (duk_heaphdr *) key);
+ if (DUK_HOBJECT_E_SLOT_IS_ACCESSOR(heap, h, i)) {
+ duk__mark_heaphdr(heap, (duk_heaphdr *) DUK_HOBJECT_E_GET_VALUE_PTR(heap, h, i)->a.get);
+ duk__mark_heaphdr(heap, (duk_heaphdr *) DUK_HOBJECT_E_GET_VALUE_PTR(heap, h, i)->a.set);
+ } else {
+ duk__mark_tval(heap, &DUK_HOBJECT_E_GET_VALUE_PTR(heap, h, i)->v);
+ }
+ }
+
+ for (i = 0; i < (duk_uint_fast32_t) DUK_HOBJECT_GET_ASIZE(h); i++) {
+ duk__mark_tval(heap, DUK_HOBJECT_A_GET_VALUE_PTR(heap, h, i));
+ }
+
+ /* hash part is a 'weak reference' and does not contribute */
+
+ duk__mark_heaphdr(heap, (duk_heaphdr *) DUK_HOBJECT_GET_PROTOTYPE(heap, h));
+
+ if (DUK_HOBJECT_IS_COMPILEDFUNCTION(h)) {
+ duk_hcompiledfunction *f = (duk_hcompiledfunction *) h;
+ duk_tval *tv, *tv_end;
+ duk_hobject **fn, **fn_end;
+
+ /* 'data' is reachable through every compiled function which
+ * contains a reference.
+ */
+
+ duk__mark_heaphdr(heap, (duk_heaphdr *) DUK_HCOMPILEDFUNCTION_GET_DATA(heap, f));
+
+ if (DUK_HCOMPILEDFUNCTION_GET_DATA(heap, f) != NULL) {
+ tv = DUK_HCOMPILEDFUNCTION_GET_CONSTS_BASE(heap, f);
+ tv_end = DUK_HCOMPILEDFUNCTION_GET_CONSTS_END(heap, f);
+ while (tv < tv_end) {
+ duk__mark_tval(heap, tv);
+ tv++;
+ }
+
+ fn = DUK_HCOMPILEDFUNCTION_GET_FUNCS_BASE(heap, f);
+ fn_end = DUK_HCOMPILEDFUNCTION_GET_FUNCS_END(heap, f);
+ while (fn < fn_end) {
+ duk__mark_heaphdr(heap, (duk_heaphdr *) *fn);
+ fn++;
+ }
+ } else {
+ /* May happen in some out-of-memory corner cases. */
+ DUK_D(DUK_DPRINT("duk_hcompiledfunction 'data' is NULL, skipping marking"));
+ }
+ } else if (DUK_HOBJECT_IS_NATIVEFUNCTION(h)) {
+ duk_hnativefunction *f = (duk_hnativefunction *) h;
+ DUK_UNREF(f);
+ /* nothing to mark */
+ } else if (DUK_HOBJECT_IS_BUFFEROBJECT(h)) {
+ duk_hbufferobject *b = (duk_hbufferobject *) h;
+ duk__mark_heaphdr(heap, (duk_heaphdr *) b->buf);
+ } else if (DUK_HOBJECT_IS_THREAD(h)) {
+ duk_hthread *t = (duk_hthread *) h;
+ duk_tval *tv;
+
+ tv = t->valstack;
+ while (tv < t->valstack_top) {
+ duk__mark_tval(heap, tv);
+ tv++;
+ }
+
+ for (i = 0; i < (duk_uint_fast32_t) t->callstack_top; i++) {
+ duk_activation *act = t->callstack + i;
+ duk__mark_heaphdr(heap, (duk_heaphdr *) DUK_ACT_GET_FUNC(act));
+ duk__mark_heaphdr(heap, (duk_heaphdr *) act->var_env);
+ duk__mark_heaphdr(heap, (duk_heaphdr *) act->lex_env);
+#ifdef DUK_USE_NONSTD_FUNC_CALLER_PROPERTY
+ duk__mark_heaphdr(heap, (duk_heaphdr *) act->prev_caller);
+#endif
+ }
+
+#if 0 /* nothing now */
+ for (i = 0; i < (duk_uint_fast32_t) t->catchstack_top; i++) {
+ duk_catcher *cat = t->catchstack + i;
+ }
+#endif
+
+ duk__mark_heaphdr(heap, (duk_heaphdr *) t->resumer);
+
+ /* XXX: duk_small_uint_t would be enough for this loop */
+ for (i = 0; i < DUK_NUM_BUILTINS; i++) {
+ duk__mark_heaphdr(heap, (duk_heaphdr *) t->builtins[i]);
+ }
+ }
+}
+
+/* recursion tracking happens here only */
+DUK_LOCAL void duk__mark_heaphdr(duk_heap *heap, duk_heaphdr *h) {
+ DUK_DDD(DUK_DDDPRINT("duk__mark_heaphdr %p, type %ld",
+ (void *) h,
+ (h != NULL ? (long) DUK_HEAPHDR_GET_TYPE(h) : (long) -1)));
+ if (!h) {
+ return;
+ }
+#if defined(DUK_USE_ROM_OBJECTS)
+ if (DUK_HEAPHDR_HAS_READONLY(h)) {
+ DUK_DDD(DUK_DDDPRINT("readonly object %p, skip", (void *) h));
+ return;
+ }
+#endif
+ if (DUK_HEAPHDR_HAS_REACHABLE(h)) {
+ DUK_DDD(DUK_DDDPRINT("already marked reachable, skip"));
+ return;
+ }
+ DUK_HEAPHDR_SET_REACHABLE(h);
+
+ if (heap->mark_and_sweep_recursion_depth >= DUK_USE_MARK_AND_SWEEP_RECLIMIT) {
+ /* log this with a normal debug level because this should be relatively rare */
+ DUK_D(DUK_DPRINT("mark-and-sweep recursion limit reached, marking as temproot: %p", (void *) h));
+ DUK_HEAP_SET_MARKANDSWEEP_RECLIMIT_REACHED(heap);
+ DUK_HEAPHDR_SET_TEMPROOT(h);
+ return;
+ }
+
+ heap->mark_and_sweep_recursion_depth++;
+
+ switch ((int) DUK_HEAPHDR_GET_TYPE(h)) {
+ case DUK_HTYPE_STRING:
+ duk__mark_hstring(heap, (duk_hstring *) h);
+ break;
+ case DUK_HTYPE_OBJECT:
+ duk__mark_hobject(heap, (duk_hobject *) h);
+ break;
+ case DUK_HTYPE_BUFFER:
+ /* nothing to mark */
+ break;
+ default:
+ DUK_D(DUK_DPRINT("attempt to mark heaphdr %p with invalid htype %ld", (void *) h, (long) DUK_HEAPHDR_GET_TYPE(h)));
+ DUK_UNREACHABLE();
+ }
+
+ heap->mark_and_sweep_recursion_depth--;
+}
+
+DUK_LOCAL void duk__mark_tval(duk_heap *heap, duk_tval *tv) {
+ DUK_DDD(DUK_DDDPRINT("duk__mark_tval %p", (void *) tv));
+ if (!tv) {
+ return;
+ }
+ if (DUK_TVAL_IS_HEAP_ALLOCATED(tv)) {
+ duk__mark_heaphdr(heap, DUK_TVAL_GET_HEAPHDR(tv));
+ }
+}
+
+/*
+ * Mark the heap.
+ */
+
+DUK_LOCAL void duk__mark_roots_heap(duk_heap *heap) {
+ duk_small_uint_t i;
+
+ DUK_DD(DUK_DDPRINT("duk__mark_roots_heap: %p", (void *) heap));
+
+ duk__mark_heaphdr(heap, (duk_heaphdr *) heap->heap_thread);
+ duk__mark_heaphdr(heap, (duk_heaphdr *) heap->heap_object);
+
+ for (i = 0; i < DUK_HEAP_NUM_STRINGS; i++) {
+ duk_hstring *h = DUK_HEAP_GET_STRING(heap, i);
+ duk__mark_heaphdr(heap, (duk_heaphdr *) h);
+ }
+
+ duk__mark_tval(heap, &heap->lj.value1);
+ duk__mark_tval(heap, &heap->lj.value2);
+
+#if defined(DUK_USE_DEBUGGER_SUPPORT)
+ for (i = 0; i < heap->dbg_breakpoint_count; i++) {
+ duk__mark_heaphdr(heap, (duk_heaphdr *) heap->dbg_breakpoints[i].filename);
+ }
+#endif
+}
+
+/*
+ * Mark refzero_list objects.
+ *
+ * Objects on the refzero_list have no inbound references. They might have
+ * outbound references to objects that we might free, which would invalidate
+ * any references held by the refzero objects. A refzero object might also
+ * be rescued by refcount finalization. Refzero objects are treated as
+ * reachability roots to ensure they (or anything they point to) are not
+ * freed in mark-and-sweep.
+ */
+
+#ifdef DUK_USE_REFERENCE_COUNTING
+DUK_LOCAL void duk__mark_refzero_list(duk_heap *heap) {
+ duk_heaphdr *hdr;
+
+ DUK_DD(DUK_DDPRINT("duk__mark_refzero_list: %p", (void *) heap));
+
+ hdr = heap->refzero_list;
+ while (hdr) {
+ duk__mark_heaphdr(heap, hdr);
+ hdr = DUK_HEAPHDR_GET_NEXT(heap, hdr);
+ }
+}
+#endif
+
+/*
+ * Mark unreachable, finalizable objects.
+ *
+ * Such objects will be moved aside and their finalizers run later. They have
+ * to be treated as reachability roots for their properties etc to remain
+ * allocated. This marking is only done for unreachable values which would
+ * be swept later (refzero_list is thus excluded).
+ *
+ * Objects are first marked FINALIZABLE and only then marked as reachability
+ * roots; otherwise circular references might be handled inconsistently.
+ */
+
+DUK_LOCAL void duk__mark_finalizable(duk_heap *heap) {
+ duk_hthread *thr;
+ duk_heaphdr *hdr;
+ duk_size_t count_finalizable = 0;
+
+ DUK_DD(DUK_DDPRINT("duk__mark_finalizable: %p", (void *) heap));
+
+ thr = duk__get_temp_hthread(heap);
+ DUK_ASSERT(thr != NULL);
+
+ hdr = heap->heap_allocated;
+ while (hdr) {
+ /* A finalizer is looked up from the object and up its prototype chain
+ * (which allows inherited finalizers). A prototype loop must not cause
+ * an error to be thrown here; duk_hobject_hasprop_raw() will ignore a
+ * prototype loop silently and indicate that the property doesn't exist.
+ */
+
+ if (!DUK_HEAPHDR_HAS_REACHABLE(hdr) &&
+ DUK_HEAPHDR_GET_TYPE(hdr) == DUK_HTYPE_OBJECT &&
+ !DUK_HEAPHDR_HAS_FINALIZED(hdr) &&
+ duk_hobject_hasprop_raw(thr, (duk_hobject *) hdr, DUK_HTHREAD_STRING_INT_FINALIZER(thr))) {
+
+ /* heaphdr:
+ * - is not reachable
+ * - is an object
+ * - is not a finalized object
+ * - has a finalizer
+ */
+
+ DUK_DD(DUK_DDPRINT("unreachable heap object will be "
+ "finalized -> mark as finalizable "
+ "and treat as a reachability root: %p",
+ (void *) hdr));
+ DUK_ASSERT(!DUK_HEAPHDR_HAS_READONLY(hdr));
+ DUK_HEAPHDR_SET_FINALIZABLE(hdr);
+ count_finalizable ++;
+ }
+
+ hdr = DUK_HEAPHDR_GET_NEXT(heap, hdr);
+ }
+
+ if (count_finalizable == 0) {
+ return;
+ }
+
+ DUK_DD(DUK_DDPRINT("marked %ld heap objects as finalizable, now mark them reachable",
+ (long) count_finalizable));
+
+ hdr = heap->heap_allocated;
+ while (hdr) {
+ if (DUK_HEAPHDR_HAS_FINALIZABLE(hdr)) {
+ duk__mark_heaphdr(heap, hdr);
+ }
+
+ hdr = DUK_HEAPHDR_GET_NEXT(heap, hdr);
+ }
+
+ /* Caller will finish the marking process if we hit a recursion limit. */
+}
+
+/*
+ * Mark objects on finalize_list.
+ *
+ */
+
+DUK_LOCAL void duk__mark_finalize_list(duk_heap *heap) {
+ duk_heaphdr *hdr;
+#ifdef DUK_USE_DEBUG
+ duk_size_t count_finalize_list = 0;
+#endif
+
+ DUK_DD(DUK_DDPRINT("duk__mark_finalize_list: %p", (void *) heap));
+
+ hdr = heap->finalize_list;
+ while (hdr) {
+ duk__mark_heaphdr(heap, hdr);
+ hdr = DUK_HEAPHDR_GET_NEXT(heap, hdr);
+#ifdef DUK_USE_DEBUG
+ count_finalize_list++;
+#endif
+ }
+
+#ifdef DUK_USE_DEBUG
+ if (count_finalize_list > 0) {
+ DUK_D(DUK_DPRINT("marked %ld objects on the finalize_list as reachable (previous finalizer run skipped)",
+ (long) count_finalize_list));
+ }
+#endif
+}
+
+/*
+ * Fallback marking handler if recursion limit is reached.
+ *
+ * Iterates 'temproots' until recursion limit is no longer hit. Note
+ * that temproots may reside either in heap allocated list or the
+ * refzero work list. This is a slow scan, but guarantees that we
+ * finish with a bounded C stack.
+ *
+ * Note that nodes may have been marked as temproots before this
+ * scan begun, OR they may have been marked during the scan (as
+ * we process nodes recursively also during the scan). This is
+ * intended behavior.
+ */
+
+#ifdef DUK_USE_DEBUG
+DUK_LOCAL void duk__handle_temproot(duk_heap *heap, duk_heaphdr *hdr, duk_size_t *count) {
+#else
+DUK_LOCAL void duk__handle_temproot(duk_heap *heap, duk_heaphdr *hdr) {
+#endif
+ if (!DUK_HEAPHDR_HAS_TEMPROOT(hdr)) {
+ DUK_DDD(DUK_DDDPRINT("not a temp root: %p", (void *) hdr));
+ return;
+ }
+
+ DUK_DDD(DUK_DDDPRINT("found a temp root: %p", (void *) hdr));
+ DUK_HEAPHDR_CLEAR_TEMPROOT(hdr);
+ DUK_HEAPHDR_CLEAR_REACHABLE(hdr); /* done so that duk__mark_heaphdr() works correctly */
+ duk__mark_heaphdr(heap, hdr);
+
+#ifdef DUK_USE_DEBUG
+ (*count)++;
+#endif
+}
+
+DUK_LOCAL void duk__mark_temproots_by_heap_scan(duk_heap *heap) {
+ duk_heaphdr *hdr;
+#ifdef DUK_USE_DEBUG
+ duk_size_t count;
+#endif
+
+ DUK_DD(DUK_DDPRINT("duk__mark_temproots_by_heap_scan: %p", (void *) heap));
+
+ while (DUK_HEAP_HAS_MARKANDSWEEP_RECLIMIT_REACHED(heap)) {
+ DUK_DD(DUK_DDPRINT("recursion limit reached, doing heap scan to continue from temproots"));
+
+#ifdef DUK_USE_DEBUG
+ count = 0;
+#endif
+ DUK_HEAP_CLEAR_MARKANDSWEEP_RECLIMIT_REACHED(heap);
+
+ hdr = heap->heap_allocated;
+ while (hdr) {
+#ifdef DUK_USE_DEBUG
+ duk__handle_temproot(heap, hdr, &count);
+#else
+ duk__handle_temproot(heap, hdr);
+#endif
+ hdr = DUK_HEAPHDR_GET_NEXT(heap, hdr);
+ }
+
+ /* must also check refzero_list */
+#ifdef DUK_USE_REFERENCE_COUNTING
+ hdr = heap->refzero_list;
+ while (hdr) {
+#ifdef DUK_USE_DEBUG
+ duk__handle_temproot(heap, hdr, &count);
+#else
+ duk__handle_temproot(heap, hdr);
+#endif
+ hdr = DUK_HEAPHDR_GET_NEXT(heap, hdr);
+ }
+#endif /* DUK_USE_REFERENCE_COUNTING */
+
+#ifdef DUK_USE_DEBUG
+ DUK_DD(DUK_DDPRINT("temproot mark heap scan processed %ld temp roots", (long) count));
+#endif
+ }
+}
+
+/*
+ * Finalize refcounts for heap elements just about to be freed.
+ * This must be done for all objects before freeing to avoid any
+ * stale pointer dereferences.
+ *
+ * Note that this must deduce the set of objects to be freed
+ * identically to duk__sweep_heap().
+ */
+
+#ifdef DUK_USE_REFERENCE_COUNTING
+DUK_LOCAL void duk__finalize_refcounts(duk_heap *heap) {
+ duk_hthread *thr;
+ duk_heaphdr *hdr;
+
+ thr = duk__get_temp_hthread(heap);
+ DUK_ASSERT(thr != NULL);
+
+ DUK_DD(DUK_DDPRINT("duk__finalize_refcounts: heap=%p, hthread=%p",
+ (void *) heap, (void *) thr));
+
+ hdr = heap->heap_allocated;
+ while (hdr) {
+ if (!DUK_HEAPHDR_HAS_REACHABLE(hdr)) {
+ /*
+ * Unreachable object about to be swept. Finalize target refcounts
+ * (objects which the unreachable object points to) without doing
+ * refzero processing. Recursive decrefs are also prevented when
+ * refzero processing is disabled.
+ *
+ * Value cannot be a finalizable object, as they have been made
+ * temporarily reachable for this round.
+ */
+
+ DUK_DDD(DUK_DDDPRINT("unreachable object, refcount finalize before sweeping: %p", (void *) hdr));
+ duk_heaphdr_refcount_finalize(thr, hdr);
+ }
+
+ hdr = DUK_HEAPHDR_GET_NEXT(heap, hdr);
+ }
+}
+#endif /* DUK_USE_REFERENCE_COUNTING */
+
+/*
+ * Clear (reachable) flags of refzero work list.
+ */
+
+#ifdef DUK_USE_REFERENCE_COUNTING
+DUK_LOCAL void duk__clear_refzero_list_flags(duk_heap *heap) {
+ duk_heaphdr *hdr;
+
+ DUK_DD(DUK_DDPRINT("duk__clear_refzero_list_flags: %p", (void *) heap));
+
+ hdr = heap->refzero_list;
+ while (hdr) {
+ DUK_HEAPHDR_CLEAR_REACHABLE(hdr);
+ DUK_ASSERT(!DUK_HEAPHDR_HAS_FINALIZABLE(hdr));
+ DUK_ASSERT(!DUK_HEAPHDR_HAS_FINALIZED(hdr));
+ DUK_ASSERT(!DUK_HEAPHDR_HAS_TEMPROOT(hdr));
+ hdr = DUK_HEAPHDR_GET_NEXT(heap, hdr);
+ }
+}
+#endif /* DUK_USE_REFERENCE_COUNTING */
+
+/*
+ * Clear (reachable) flags of finalize_list
+ *
+ * We could mostly do in the sweep phase when we move objects from the
+ * heap into the finalize_list. However, if a finalizer run is skipped
+ * during a mark-and-sweep, the objects on the finalize_list will be marked
+ * reachable during the next mark-and-sweep. Since they're already on the
+ * finalize_list, no-one will be clearing their REACHABLE flag so we do it
+ * here. (This now overlaps with the sweep handling in a harmless way.)
+ */
+
+DUK_LOCAL void duk__clear_finalize_list_flags(duk_heap *heap) {
+ duk_heaphdr *hdr;
+
+ DUK_DD(DUK_DDPRINT("duk__clear_finalize_list_flags: %p", (void *) heap));
+
+ hdr = heap->finalize_list;
+ while (hdr) {
+ DUK_HEAPHDR_CLEAR_REACHABLE(hdr);
+ DUK_ASSERT(!DUK_HEAPHDR_HAS_FINALIZABLE(hdr));
+ DUK_ASSERT(!DUK_HEAPHDR_HAS_FINALIZED(hdr));
+ DUK_ASSERT(!DUK_HEAPHDR_HAS_TEMPROOT(hdr));
+ hdr = DUK_HEAPHDR_GET_NEXT(heap, hdr);
+ }
+}
+
+/*
+ * Sweep stringtable
+ */
+
+#if defined(DUK_USE_STRTAB_CHAIN)
+
+/* XXX: skip count_free w/o debug? */
+#if defined(DUK_USE_HEAPPTR16)
+DUK_LOCAL void duk__sweep_string_chain16(duk_heap *heap, duk_uint16_t *slot, duk_size_t *count_keep, duk_size_t *count_free) {
+ duk_uint16_t h16 = *slot;
+ duk_hstring *h;
+ duk_uint16_t null16 = heap->heapptr_null16;
+
+ if (h16 == null16) {
+ /* nop */
+ return;
+ }
+ h = (duk_hstring *) DUK_USE_HEAPPTR_DEC16(heap->heap_udata, h16);
+ DUK_ASSERT(h != NULL);
+
+ if (DUK_HEAPHDR_HAS_REACHABLE((duk_heaphdr *) h)) {
+ DUK_HEAPHDR_CLEAR_REACHABLE((duk_heaphdr *) h);
+ (*count_keep)++;
+ } else {
+#if defined(DUK_USE_REFERENCE_COUNTING)
+ DUK_ASSERT(DUK_HEAPHDR_GET_REFCOUNT((duk_heaphdr *) h) == 0);
+#endif
+ /* deal with weak references first */
+ duk_heap_strcache_string_remove(heap, (duk_hstring *) h);
+ *slot = null16;
+
+ /* free inner references (these exist e.g. when external
+ * strings are enabled)
+ */
+ duk_free_hstring_inner(heap, h);
+ DUK_FREE(heap, h);
+ (*count_free)++;
+ }
+}
+#else /* DUK_USE_HEAPPTR16 */
+DUK_LOCAL void duk__sweep_string_chain(duk_heap *heap, duk_hstring **slot, duk_size_t *count_keep, duk_size_t *count_free) {
+ duk_hstring *h = *slot;
+
+ if (h == NULL) {
+ /* nop */
+ return;
+ }
+
+ if (DUK_HEAPHDR_HAS_REACHABLE((duk_heaphdr *) h)) {
+ DUK_HEAPHDR_CLEAR_REACHABLE((duk_heaphdr *) h);
+ (*count_keep)++;
+ } else {
+#if defined(DUK_USE_REFERENCE_COUNTING)
+ DUK_ASSERT(DUK_HEAPHDR_GET_REFCOUNT((duk_heaphdr *) h) == 0);
+#endif
+ /* deal with weak references first */
+ duk_heap_strcache_string_remove(heap, (duk_hstring *) h);
+ *slot = NULL;
+
+ /* free inner references (these exist e.g. when external
+ * strings are enabled)
+ */
+ duk_free_hstring_inner(heap, h);
+ DUK_FREE(heap, h);
+ (*count_free)++;
+ }
+}
+#endif /* DUK_USE_HEAPPTR16 */
+
+DUK_LOCAL void duk__sweep_stringtable_chain(duk_heap *heap, duk_size_t *out_count_keep) {
+ duk_strtab_entry *e;
+ duk_uint_fast32_t i;
+ duk_size_t count_free = 0;
+ duk_size_t count_keep = 0;
+ duk_size_t j, n;
+#if defined(DUK_USE_HEAPPTR16)
+ duk_uint16_t *lst;
+#else
+ duk_hstring **lst;
+#endif
+
+ DUK_DD(DUK_DDPRINT("duk__sweep_stringtable: %p", (void *) heap));
+
+ /* Non-zero refcounts should not happen for unreachable strings,
+ * because we refcount finalize all unreachable objects which
+ * should have decreased unreachable string refcounts to zero
+ * (even for cycles).
+ */
+
+ for (i = 0; i < DUK_STRTAB_CHAIN_SIZE; i++) {
+ e = heap->strtable + i;
+ if (e->listlen == 0) {
+#if defined(DUK_USE_HEAPPTR16)
+ duk__sweep_string_chain16(heap, &e->u.str16, &count_keep, &count_free);
+#else
+ duk__sweep_string_chain(heap, &e->u.str, &count_keep, &count_free);
+#endif
+ } else {
+#if defined(DUK_USE_HEAPPTR16)
+ lst = (duk_uint16_t *) DUK_USE_HEAPPTR_DEC16(heap->heap_udata, e->u.strlist16);
+#else
+ lst = e->u.strlist;
+#endif
+ for (j = 0, n = e->listlen; j < n; j++) {
+#if defined(DUK_USE_HEAPPTR16)
+ duk__sweep_string_chain16(heap, lst + j, &count_keep, &count_free);
+#else
+ duk__sweep_string_chain(heap, lst + j, &count_keep, &count_free);
+#endif
+ }
+ }
+ }
+
+ DUK_D(DUK_DPRINT("mark-and-sweep sweep stringtable: %ld freed, %ld kept",
+ (long) count_free, (long) count_keep));
+ *out_count_keep = count_keep;
+}
+#endif /* DUK_USE_STRTAB_CHAIN */
+
+#if defined(DUK_USE_STRTAB_PROBE)
+DUK_LOCAL void duk__sweep_stringtable_probe(duk_heap *heap, duk_size_t *out_count_keep) {
+ duk_hstring *h;
+ duk_uint_fast32_t i;
+#ifdef DUK_USE_DEBUG
+ duk_size_t count_free = 0;
+#endif
+ duk_size_t count_keep = 0;
+
+ DUK_DD(DUK_DDPRINT("duk__sweep_stringtable: %p", (void *) heap));
+
+ for (i = 0; i < heap->st_size; i++) {
+#if defined(DUK_USE_HEAPPTR16)
+ h = (duk_hstring *) DUK_USE_HEAPPTR_DEC16(heap->heap_udata, heap->strtable16[i]);
+#else
+ h = heap->strtable[i];
+#endif
+ if (h == NULL || h == DUK_STRTAB_DELETED_MARKER(heap)) {
+ continue;
+ } else if (DUK_HEAPHDR_HAS_REACHABLE((duk_heaphdr *) h)) {
+ DUK_HEAPHDR_CLEAR_REACHABLE((duk_heaphdr *) h);
+ count_keep++;
+ continue;
+ }
+
+#ifdef DUK_USE_DEBUG
+ count_free++;
+#endif
+
+#if defined(DUK_USE_REFERENCE_COUNTING)
+ /* Non-zero refcounts should not happen for unreachable strings,
+ * because we refcount finalize all unreachable objects which
+ * should have decreased unreachable string refcounts to zero
+ * (even for cycles).
+ */
+ DUK_ASSERT(DUK_HEAPHDR_GET_REFCOUNT((duk_heaphdr *) h) == 0);
+#endif
+
+ DUK_DDD(DUK_DDDPRINT("sweep string, not reachable: %p", (void *) h));
+
+ /* deal with weak references first */
+ duk_heap_strcache_string_remove(heap, (duk_hstring *) h);
+
+ /* remove the string (mark DELETED), could also call
+ * duk_heap_string_remove() but that would be slow and
+ * pointless because we already know the slot.
+ */
+#if defined(DUK_USE_HEAPPTR16)
+ heap->strtable16[i] = heap->heapptr_deleted16;
+#else
+ heap->strtable[i] = DUK_STRTAB_DELETED_MARKER(heap);
+#endif
+
+ /* free inner references (these exist e.g. when external
+ * strings are enabled)
+ */
+ duk_free_hstring_inner(heap, (duk_hstring *) h);
+
+ /* finally free the struct itself */
+ DUK_FREE(heap, h);
+ }
+
+#ifdef DUK_USE_DEBUG
+ DUK_D(DUK_DPRINT("mark-and-sweep sweep stringtable: %ld freed, %ld kept",
+ (long) count_free, (long) count_keep));
+#endif
+ *out_count_keep = count_keep;
+}
+#endif /* DUK_USE_STRTAB_PROBE */
+
+/*
+ * Sweep heap
+ */
+
+DUK_LOCAL void duk__sweep_heap(duk_heap *heap, duk_int_t flags, duk_size_t *out_count_keep) {
+ duk_heaphdr *prev; /* last element that was left in the heap */
+ duk_heaphdr *curr;
+ duk_heaphdr *next;
+#ifdef DUK_USE_DEBUG
+ duk_size_t count_free = 0;
+ duk_size_t count_finalize = 0;
+ duk_size_t count_rescue = 0;
+#endif
+ duk_size_t count_keep = 0;
+
+ DUK_UNREF(flags);
+ DUK_DD(DUK_DDPRINT("duk__sweep_heap: %p", (void *) heap));
+
+ prev = NULL;
+ curr = heap->heap_allocated;
+ heap->heap_allocated = NULL;
+ while (curr) {
+ /* Strings and ROM objects are never placed on the heap allocated list. */
+ DUK_ASSERT(DUK_HEAPHDR_GET_TYPE(curr) != DUK_HTYPE_STRING);
+ DUK_ASSERT(!DUK_HEAPHDR_HAS_READONLY(curr));
+
+ next = DUK_HEAPHDR_GET_NEXT(heap, curr);
+
+ if (DUK_HEAPHDR_HAS_REACHABLE(curr)) {
+ /*
+ * Reachable object, keep
+ */
+
+ DUK_DDD(DUK_DDDPRINT("sweep, reachable: %p", (void *) curr));
+
+ if (DUK_HEAPHDR_HAS_FINALIZABLE(curr)) {
+ /*
+ * If object has been marked finalizable, move it to the
+ * "to be finalized" work list. It will be collected on
+ * the next mark-and-sweep if it is still unreachable
+ * after running the finalizer.
+ */
+
+ DUK_ASSERT(!DUK_HEAPHDR_HAS_FINALIZED(curr));
+ DUK_ASSERT(DUK_HEAPHDR_GET_TYPE(curr) == DUK_HTYPE_OBJECT);
+ DUK_DDD(DUK_DDDPRINT("object has finalizer, move to finalization work list: %p", (void *) curr));
+
+#ifdef DUK_USE_DOUBLE_LINKED_HEAP
+ if (heap->finalize_list) {
+ DUK_HEAPHDR_SET_PREV(heap, heap->finalize_list, curr);
+ }
+ DUK_HEAPHDR_SET_PREV(heap, curr, NULL);
+#endif
+ DUK_HEAPHDR_SET_NEXT(heap, curr, heap->finalize_list);
+ DUK_ASSERT_HEAPHDR_LINKS(heap, curr);
+ heap->finalize_list = curr;
+#ifdef DUK_USE_DEBUG
+ count_finalize++;
+#endif
+ } else {
+ /*
+ * Object will be kept; queue object back to heap_allocated (to tail)
+ */
+
+ if (DUK_HEAPHDR_HAS_FINALIZED(curr)) {
+ /*
+ * Object's finalizer was executed on last round, and
+ * object has been happily rescued.
+ */
+
+ DUK_ASSERT(!DUK_HEAPHDR_HAS_FINALIZABLE(curr));
+ DUK_ASSERT(DUK_HEAPHDR_GET_TYPE(curr) == DUK_HTYPE_OBJECT);
+ DUK_DD(DUK_DDPRINT("object rescued during mark-and-sweep finalization: %p", (void *) curr));
+#ifdef DUK_USE_DEBUG
+ count_rescue++;
+#endif
+ } else {
+ /*
+ * Plain, boring reachable object.
+ */
+ DUK_DD(DUK_DDPRINT("keep object: %!iO", curr));
+ count_keep++;
+ }
+
+ if (!heap->heap_allocated) {
+ heap->heap_allocated = curr;
+ }
+ if (prev) {
+ DUK_HEAPHDR_SET_NEXT(heap, prev, curr);
+ }
+#ifdef DUK_USE_DOUBLE_LINKED_HEAP
+ DUK_HEAPHDR_SET_PREV(heap, curr, prev);
+#endif
+ DUK_ASSERT_HEAPHDR_LINKS(heap, prev);
+ DUK_ASSERT_HEAPHDR_LINKS(heap, curr);
+ prev = curr;
+ }
+
+ DUK_HEAPHDR_CLEAR_REACHABLE(curr);
+ DUK_HEAPHDR_CLEAR_FINALIZED(curr);
+ DUK_HEAPHDR_CLEAR_FINALIZABLE(curr);
+
+ DUK_ASSERT(!DUK_HEAPHDR_HAS_REACHABLE(curr));
+ DUK_ASSERT(!DUK_HEAPHDR_HAS_FINALIZED(curr));
+ DUK_ASSERT(!DUK_HEAPHDR_HAS_FINALIZABLE(curr));
+
+ curr = next;
+ } else {
+ /*
+ * Unreachable object, free
+ */
+
+ DUK_DDD(DUK_DDDPRINT("sweep, not reachable: %p", (void *) curr));
+
+#if defined(DUK_USE_REFERENCE_COUNTING)
+ /* Non-zero refcounts should not happen because we refcount
+ * finalize all unreachable objects which should cancel out
+ * refcounts (even for cycles).
+ */
+ DUK_ASSERT(DUK_HEAPHDR_GET_REFCOUNT(curr) == 0);
+#endif
+ DUK_ASSERT(!DUK_HEAPHDR_HAS_FINALIZABLE(curr));
+
+ if (DUK_HEAPHDR_HAS_FINALIZED(curr)) {
+ DUK_DDD(DUK_DDDPRINT("finalized object not rescued: %p", (void *) curr));
+ }
+
+ /* Note: object cannot be a finalizable unreachable object, as
+ * they have been marked temporarily reachable for this round,
+ * and are handled above.
+ */
+
+#ifdef DUK_USE_DEBUG
+ count_free++;
+#endif
+
+ /* weak refs should be handled here, but no weak refs for
+ * any non-string objects exist right now.
+ */
+
+ /* free object and all auxiliary (non-heap) allocs */
+ duk_heap_free_heaphdr_raw(heap, curr);
+
+ curr = next;
+ }
+ }
+ if (prev) {
+ DUK_HEAPHDR_SET_NEXT(heap, prev, NULL);
+ }
+ DUK_ASSERT_HEAPHDR_LINKS(heap, prev);
+
+#ifdef DUK_USE_DEBUG
+ DUK_D(DUK_DPRINT("mark-and-sweep sweep objects (non-string): %ld freed, %ld kept, %ld rescued, %ld queued for finalization",
+ (long) count_free, (long) count_keep, (long) count_rescue, (long) count_finalize));
+#endif
+ *out_count_keep = count_keep;
+}
+
+/*
+ * Run (object) finalizers in the "to be finalized" work list.
+ */
+
+DUK_LOCAL void duk__run_object_finalizers(duk_heap *heap, duk_small_uint_t flags) {
+ duk_heaphdr *curr;
+ duk_heaphdr *next;
+#ifdef DUK_USE_DEBUG
+ duk_size_t count = 0;
+#endif
+ duk_hthread *thr;
+
+ DUK_DD(DUK_DDPRINT("duk__run_object_finalizers: %p", (void *) heap));
+
+ thr = duk__get_temp_hthread(heap);
+ DUK_ASSERT(thr != NULL);
+
+ curr = heap->finalize_list;
+ while (curr) {
+ DUK_DDD(DUK_DDDPRINT("mark-and-sweep finalize: %p", (void *) curr));
+
+ DUK_ASSERT(DUK_HEAPHDR_GET_TYPE(curr) == DUK_HTYPE_OBJECT); /* only objects have finalizers */
+ DUK_ASSERT(!DUK_HEAPHDR_HAS_REACHABLE(curr)); /* flags have been already cleared */
+ DUK_ASSERT(!DUK_HEAPHDR_HAS_TEMPROOT(curr));
+ DUK_ASSERT(!DUK_HEAPHDR_HAS_FINALIZABLE(curr));
+ DUK_ASSERT(!DUK_HEAPHDR_HAS_FINALIZED(curr));
+ DUK_ASSERT(!DUK_HEAPHDR_HAS_READONLY(curr)); /* No finalizers for ROM objects */
+
+ if (DUK_LIKELY((flags & DUK_MS_FLAG_SKIP_FINALIZERS) == 0)) {
+ /* Run the finalizer, duk_hobject_run_finalizer() sets FINALIZED.
+ * Next mark-and-sweep will collect the object unless it has
+ * become reachable (i.e. rescued). FINALIZED prevents the
+ * finalizer from being executed again before that.
+ */
+ duk_hobject_run_finalizer(thr, (duk_hobject *) curr); /* must never longjmp */
+ DUK_ASSERT(DUK_HEAPHDR_HAS_FINALIZED(curr));
+ } else {
+ /* Used during heap destruction: don't actually run finalizers
+ * because we're heading into forced finalization. Instead,
+ * queue finalizable objects back to the heap_allocated list.
+ */
+ DUK_D(DUK_DPRINT("skip finalizers flag set, queue object to heap_allocated without finalizing"));
+ DUK_ASSERT(!DUK_HEAPHDR_HAS_FINALIZED(curr));
+ }
+
+ /* queue back to heap_allocated */
+ next = DUK_HEAPHDR_GET_NEXT(heap, curr);
+ DUK_HEAP_INSERT_INTO_HEAP_ALLOCATED(heap, curr);
+
+ curr = next;
+#ifdef DUK_USE_DEBUG
+ count++;
+#endif
+ }
+
+ /* finalize_list will always be processed completely */
+ heap->finalize_list = NULL;
+
+#ifdef DUK_USE_DEBUG
+ DUK_D(DUK_DPRINT("mark-and-sweep finalize objects: %ld finalizers called", (long) count));
+#endif
+}
+
+/*
+ * Object compaction.
+ *
+ * Compaction is assumed to never throw an error.
+ */
+
+DUK_LOCAL int duk__protected_compact_object(duk_context *ctx) {
+ /* XXX: for threads, compact value stack, call stack, catch stack? */
+
+ duk_hobject *obj = duk_get_hobject(ctx, -1);
+ DUK_ASSERT(obj != NULL);
+ duk_hobject_compact_props((duk_hthread *) ctx, obj);
+ return 0;
+}
+
+#ifdef DUK_USE_DEBUG
+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) {
+#else
+DUK_LOCAL void duk__compact_object_list(duk_heap *heap, duk_hthread *thr, duk_heaphdr *start) {
+#endif
+ duk_heaphdr *curr;
+#ifdef DUK_USE_DEBUG
+ duk_size_t old_size, new_size;
+#endif
+ duk_hobject *obj;
+
+ DUK_UNREF(heap);
+
+ curr = start;
+ while (curr) {
+ DUK_DDD(DUK_DDDPRINT("mark-and-sweep compact: %p", (void *) curr));
+
+ if (DUK_HEAPHDR_GET_TYPE(curr) != DUK_HTYPE_OBJECT) {
+ goto next;
+ }
+ obj = (duk_hobject *) curr;
+
+#ifdef DUK_USE_DEBUG
+ old_size = DUK_HOBJECT_P_COMPUTE_SIZE(DUK_HOBJECT_GET_ESIZE(obj),
+ DUK_HOBJECT_GET_ASIZE(obj),
+ DUK_HOBJECT_GET_HSIZE(obj));
+#endif
+
+ DUK_DD(DUK_DDPRINT("compact object: %p", (void *) obj));
+ duk_push_hobject((duk_context *) thr, obj);
+ /* XXX: disable error handlers for duration of compaction? */
+ duk_safe_call((duk_context *) thr, duk__protected_compact_object, 1, 0);
+
+#ifdef DUK_USE_DEBUG
+ new_size = DUK_HOBJECT_P_COMPUTE_SIZE(DUK_HOBJECT_GET_ESIZE(obj),
+ DUK_HOBJECT_GET_ASIZE(obj),
+ DUK_HOBJECT_GET_HSIZE(obj));
+#endif
+
+#ifdef DUK_USE_DEBUG
+ (*p_count_compact)++;
+ (*p_count_bytes_saved) += (duk_size_t) (old_size - new_size);
+#endif
+
+ next:
+ curr = DUK_HEAPHDR_GET_NEXT(heap, curr);
+#ifdef DUK_USE_DEBUG
+ (*p_count_check)++;
+#endif
+ }
+}
+
+DUK_LOCAL void duk__compact_objects(duk_heap *heap) {
+ /* XXX: which lists should participate? to be finalized? */
+#ifdef DUK_USE_DEBUG
+ duk_size_t count_check = 0;
+ duk_size_t count_compact = 0;
+ duk_size_t count_bytes_saved = 0;
+#endif
+ duk_hthread *thr;
+
+ DUK_DD(DUK_DDPRINT("duk__compact_objects: %p", (void *) heap));
+
+ thr = duk__get_temp_hthread(heap);
+ DUK_ASSERT(thr != NULL);
+
+#ifdef DUK_USE_DEBUG
+ duk__compact_object_list(heap, thr, heap->heap_allocated, &count_check, &count_compact, &count_bytes_saved);
+ duk__compact_object_list(heap, thr, heap->finalize_list, &count_check, &count_compact, &count_bytes_saved);
+#ifdef DUK_USE_REFERENCE_COUNTING
+ duk__compact_object_list(heap, thr, heap->refzero_list, &count_check, &count_compact, &count_bytes_saved);
+#endif
+#else
+ duk__compact_object_list(heap, thr, heap->heap_allocated);
+ duk__compact_object_list(heap, thr, heap->finalize_list);
+#ifdef DUK_USE_REFERENCE_COUNTING
+ duk__compact_object_list(heap, thr, heap->refzero_list);
+#endif
+#endif
+
+#ifdef DUK_USE_DEBUG
+ DUK_D(DUK_DPRINT("mark-and-sweep compact objects: %ld checked, %ld compaction attempts, %ld bytes saved by compaction",
+ (long) count_check, (long) count_compact, (long) count_bytes_saved));
+#endif
+}
+
+/*
+ * Assertion helpers.
+ */
+
+#ifdef DUK_USE_ASSERTIONS
+DUK_LOCAL void duk__assert_heaphdr_flags(duk_heap *heap) {
+ duk_heaphdr *hdr;
+
+ hdr = heap->heap_allocated;
+ while (hdr) {
+ DUK_ASSERT(!DUK_HEAPHDR_HAS_REACHABLE(hdr));
+ DUK_ASSERT(!DUK_HEAPHDR_HAS_TEMPROOT(hdr));
+ DUK_ASSERT(!DUK_HEAPHDR_HAS_FINALIZABLE(hdr));
+ /* may have FINALIZED */
+ hdr = DUK_HEAPHDR_GET_NEXT(heap, hdr);
+ }
+
+#ifdef DUK_USE_REFERENCE_COUNTING
+ hdr = heap->refzero_list;
+ while (hdr) {
+ DUK_ASSERT(!DUK_HEAPHDR_HAS_REACHABLE(hdr));
+ DUK_ASSERT(!DUK_HEAPHDR_HAS_TEMPROOT(hdr));
+ DUK_ASSERT(!DUK_HEAPHDR_HAS_FINALIZABLE(hdr));
+ DUK_ASSERT(!DUK_HEAPHDR_HAS_FINALIZED(hdr));
+ hdr = DUK_HEAPHDR_GET_NEXT(heap, hdr);
+ }
+#endif /* DUK_USE_REFERENCE_COUNTING */
+}
+
+#ifdef DUK_USE_REFERENCE_COUNTING
+DUK_LOCAL void duk__assert_valid_refcounts(duk_heap *heap) {
+ duk_heaphdr *hdr = heap->heap_allocated;
+ while (hdr) {
+ if (DUK_HEAPHDR_GET_REFCOUNT(hdr) == 0 &&
+ DUK_HEAPHDR_HAS_FINALIZED(hdr)) {
+ /* An object may be in heap_allocated list with a zero
+ * refcount if it has just been finalized and is waiting
+ * to be collected by the next cycle.
+ */
+ } else if (DUK_HEAPHDR_GET_REFCOUNT(hdr) == 0) {
+ /* An object may be in heap_allocated list with a zero
+ * refcount also if it is a temporary object created by
+ * a finalizer; because finalization now runs inside
+ * mark-and-sweep, such objects will not be queued to
+ * refzero_list and will thus appear here with refcount
+ * zero.
+ */
+#if 0 /* this case can no longer occur because refcount is unsigned */
+ } else if (DUK_HEAPHDR_GET_REFCOUNT(hdr) < 0) {
+ DUK_D(DUK_DPRINT("invalid refcount: %ld, %p -> %!O",
+ (hdr != NULL ? (long) DUK_HEAPHDR_GET_REFCOUNT(hdr) : (long) 0),
+ (void *) hdr, (duk_heaphdr *) hdr));
+ DUK_ASSERT(DUK_HEAPHDR_GET_REFCOUNT(hdr) > 0);
+#endif
+ }
+ hdr = DUK_HEAPHDR_GET_NEXT(heap, hdr);
+ }
+}
+#endif /* DUK_USE_REFERENCE_COUNTING */
+#endif /* DUK_USE_ASSERTIONS */
+
+/*
+ * Finalizer torture. Do one fake finalizer call which causes side effects
+ * similar to one or more finalizers on actual objects.
+ */
+
+#if defined(DUK_USE_MARKANDSWEEP_FINALIZER_TORTURE)
+DUK_LOCAL duk_ret_t duk__markandsweep_fake_finalizer(duk_context *ctx) {
+ DUK_D(DUK_DPRINT("fake mark-and-sweep torture finalizer executed"));
+
+ /* Require a lot of stack to force a value stack grow/shrink.
+ * Recursive mark-and-sweep is prevented by allocation macros
+ * so this won't trigger another mark-and-sweep.
+ */
+ duk_require_stack(ctx, 100000);
+
+ /* XXX: do something to force a callstack grow/shrink, perhaps
+ * just a manual forced resize or a forced relocating realloc?
+ */
+
+ return 0;
+}
+
+DUK_LOCAL void duk__markandsweep_torture_finalizer(duk_hthread *thr) {
+ duk_context *ctx;
+ duk_int_t rc;
+
+ DUK_ASSERT(thr != NULL);
+ ctx = (duk_context *) thr;
+
+ /* Avoid fake finalization when callstack limit has been reached.
+ * Otherwise a callstack limit error will be created, then refzero'ed.
+ */
+ if (thr->heap->call_recursion_depth >= thr->heap->call_recursion_limit ||
+ thr->callstack_size + 2 * DUK_CALLSTACK_GROW_STEP >= thr->callstack_max /*approximate*/) {
+ DUK_D(DUK_DPRINT("call recursion depth reached, avoid fake mark-and-sweep torture finalizer"));
+ return;
+ }
+
+ /* Run fake finalizer. Avoid creating unnecessary garbage. */
+ duk_push_c_function(ctx, duk__markandsweep_fake_finalizer, 0 /*nargs*/);
+ rc = duk_pcall(ctx, 0 /*nargs*/);
+ DUK_UNREF(rc); /* ignored */
+ duk_pop(ctx);
+}
+#endif /* DUK_USE_MARKANDSWEEP_FINALIZER_TORTURE */
+
+/*
+ * Main mark-and-sweep function.
+ *
+ * 'flags' represents the features requested by the caller. The current
+ * heap->mark_and_sweep_base_flags is ORed automatically into the flags;
+ * the base flags mask typically prevents certain mark-and-sweep operations
+ * to avoid trouble.
+ */
+
+DUK_INTERNAL duk_bool_t duk_heap_mark_and_sweep(duk_heap *heap, duk_small_uint_t flags) {
+ duk_hthread *thr;
+ duk_size_t count_keep_obj;
+ duk_size_t count_keep_str;
+#ifdef DUK_USE_VOLUNTARY_GC
+ duk_size_t tmp;
+#endif
+
+ /* XXX: thread selection for mark-and-sweep is currently a hack.
+ * If we don't have a thread, the entire mark-and-sweep is now
+ * skipped (although we could just skip finalizations).
+ */
+
+ /* If thr != NULL, the thr may still be in the middle of
+ * initialization.
+ * XXX: Improve the thread viability test.
+ */
+ thr = duk__get_temp_hthread(heap);
+ if (thr == NULL) {
+ DUK_D(DUK_DPRINT("gc skipped because we don't have a temp thread"));
+
+ /* reset voluntary gc trigger count */
+#ifdef DUK_USE_VOLUNTARY_GC
+ heap->mark_and_sweep_trigger_counter = DUK_HEAP_MARK_AND_SWEEP_TRIGGER_SKIP;
+#endif
+ return 0; /* OK */
+ }
+
+ /* If debugger is paused, garbage collection is disabled by default. */
+ /* XXX: will need a force flag if garbage collection is triggered
+ * explicitly during paused state.
+ */
+#if defined(DUK_USE_DEBUGGER_SUPPORT)
+ if (DUK_HEAP_IS_PAUSED(heap)) {
+ /* Checking this here rather that in memory alloc primitives
+ * reduces checking code there but means a failed allocation
+ * will go through a few retries before giving up. That's
+ * fine because this only happens during debugging.
+ */
+ DUK_D(DUK_DPRINT("gc skipped because debugger is paused"));
+ return 0;
+ }
+#endif
+
+ DUK_D(DUK_DPRINT("garbage collect (mark-and-sweep) starting, requested flags: 0x%08lx, effective flags: 0x%08lx",
+ (unsigned long) flags, (unsigned long) (flags | heap->mark_and_sweep_base_flags)));
+
+ flags |= heap->mark_and_sweep_base_flags;
+
+ /*
+ * Assertions before
+ */
+
+#ifdef DUK_USE_ASSERTIONS
+ DUK_ASSERT(!DUK_HEAP_HAS_MARKANDSWEEP_RUNNING(heap));
+ DUK_ASSERT(!DUK_HEAP_HAS_MARKANDSWEEP_RECLIMIT_REACHED(heap));
+ DUK_ASSERT(heap->mark_and_sweep_recursion_depth == 0);
+ duk__assert_heaphdr_flags(heap);
+#ifdef DUK_USE_REFERENCE_COUNTING
+ /* Note: DUK_HEAP_HAS_REFZERO_FREE_RUNNING(heap) may be true; a refcount
+ * finalizer may trigger a mark-and-sweep.
+ */
+ duk__assert_valid_refcounts(heap);
+#endif /* DUK_USE_REFERENCE_COUNTING */
+#endif /* DUK_USE_ASSERTIONS */
+
+ /*
+ * Begin
+ */
+
+ DUK_HEAP_SET_MARKANDSWEEP_RUNNING(heap);
+
+ /*
+ * Mark roots, hoping that recursion limit is not normally hit.
+ * If recursion limit is hit, run additional reachability rounds
+ * starting from "temproots" until marking is complete.
+ *
+ * Marking happens in two phases: first we mark actual reachability
+ * roots (and run "temproots" to complete the process). Then we
+ * check which objects are unreachable and are finalizable; such
+ * objects are marked as FINALIZABLE and marked as reachability
+ * (and "temproots" is run again to complete the process).
+ *
+ * The heap finalize_list must also be marked as a reachability root.
+ * There may be objects on the list from a previous round if the
+ * previous run had finalizer skip flag.
+ */
+
+ duk__mark_roots_heap(heap); /* main reachability roots */
+#ifdef DUK_USE_REFERENCE_COUNTING
+ duk__mark_refzero_list(heap); /* refzero_list treated as reachability roots */
+#endif
+ duk__mark_temproots_by_heap_scan(heap); /* temproots */
+
+ duk__mark_finalizable(heap); /* mark finalizable as reachability roots */
+ duk__mark_finalize_list(heap); /* mark finalizer work list as reachability roots */
+ duk__mark_temproots_by_heap_scan(heap); /* temproots */
+
+ /*
+ * Sweep garbage and remove marking flags, and move objects with
+ * finalizers to the finalizer work list.
+ *
+ * Objects to be swept need to get their refcounts finalized before
+ * they are swept. In other words, their target object refcounts
+ * need to be decreased. This has to be done before freeing any
+ * objects to avoid decref'ing dangling pointers (which may happen
+ * even without bugs, e.g. with reference loops)
+ *
+ * Because strings don't point to other heap objects, similar
+ * finalization is not necessary for strings.
+ */
+
+ /* XXX: more emergency behavior, e.g. find smaller hash sizes etc */
+
+#ifdef DUK_USE_REFERENCE_COUNTING
+ duk__finalize_refcounts(heap);
+#endif
+ duk__sweep_heap(heap, flags, &count_keep_obj);
+#if defined(DUK_USE_STRTAB_CHAIN)
+ duk__sweep_stringtable_chain(heap, &count_keep_str);
+#elif defined(DUK_USE_STRTAB_PROBE)
+ duk__sweep_stringtable_probe(heap, &count_keep_str);
+#else
+#error internal error, invalid strtab options
+#endif
+#ifdef DUK_USE_REFERENCE_COUNTING
+ duk__clear_refzero_list_flags(heap);
+#endif
+ duk__clear_finalize_list_flags(heap);
+
+ /*
+ * Object compaction (emergency only).
+ *
+ * Object compaction is a separate step after sweeping, as there is
+ * more free memory for it to work with. Also, currently compaction
+ * may insert new objects into the heap allocated list and the string
+ * table which we don't want to do during a sweep (the reachability
+ * flags of such objects would be incorrect). The objects inserted
+ * are currently:
+ *
+ * - a temporary duk_hbuffer for a new properties allocation
+ * - if array part is abandoned, string keys are interned
+ *
+ * The object insertions go to the front of the list, so they do not
+ * cause an infinite loop (they are not compacted).
+ */
+
+ if ((flags & DUK_MS_FLAG_EMERGENCY) &&
+ !(flags & DUK_MS_FLAG_NO_OBJECT_COMPACTION)) {
+ duk__compact_objects(heap);
+ }
+
+ /*
+ * String table resize check.
+ *
+ * Note: this may silently (and safely) fail if GC is caused by an
+ * allocation call in stringtable resize_hash(). Resize_hash()
+ * will prevent a recursive call to itself by setting the
+ * DUK_MS_FLAG_NO_STRINGTABLE_RESIZE in heap->mark_and_sweep_base_flags.
+ */
+
+ /* XXX: stringtable emergency compaction? */
+
+ /* XXX: remove this feature entirely? it would only matter for
+ * emergency GC. Disable for lowest memory builds.
+ */
+#if defined(DUK_USE_MS_STRINGTABLE_RESIZE)
+ if (!(flags & DUK_MS_FLAG_NO_STRINGTABLE_RESIZE)) {
+ DUK_DD(DUK_DDPRINT("resize stringtable: %p", (void *) heap));
+ duk_heap_force_strtab_resize(heap);
+ } else {
+ DUK_D(DUK_DPRINT("stringtable resize skipped because DUK_MS_FLAG_NO_STRINGTABLE_RESIZE is set"));
+ }
+#endif
+
+ /*
+ * Finalize objects in the finalization work list. Finalized
+ * objects are queued back to heap_allocated with FINALIZED set.
+ *
+ * Since finalizers may cause arbitrary side effects, they are
+ * prevented during string table and object property allocation
+ * resizing using the DUK_MS_FLAG_NO_FINALIZERS flag in
+ * heap->mark_and_sweep_base_flags. In this case the objects
+ * remain in the finalization work list after mark-and-sweep
+ * exits and they may be finalized on the next pass.
+ *
+ * Finalization currently happens inside "MARKANDSWEEP_RUNNING"
+ * protection (no mark-and-sweep may be triggered by the
+ * finalizers). As a side effect:
+ *
+ * 1) an out-of-memory error inside a finalizer will not
+ * cause a mark-and-sweep and may cause the finalizer
+ * to fail unnecessarily
+ *
+ * 2) any temporary objects whose refcount decreases to zero
+ * during finalization will not be put into refzero_list;
+ * they can only be collected by another mark-and-sweep
+ *
+ * This is not optimal, but since the sweep for this phase has
+ * already happened, this is probably good enough for now.
+ */
+
+#if defined(DUK_USE_MARKANDSWEEP_FINALIZER_TORTURE)
+ /* Cannot simulate individual finalizers because finalize_list only
+ * contains objects with actual finalizers. But simulate side effects
+ * from finalization by doing a bogus function call and resizing the
+ * stacks.
+ */
+ if (flags & DUK_MS_FLAG_NO_FINALIZERS) {
+ DUK_D(DUK_DPRINT("skip mark-and-sweep torture finalizer, DUK_MS_FLAG_NO_FINALIZERS is set"));
+ } else if (!(thr->valstack != NULL && thr->callstack != NULL && thr->catchstack != NULL)) {
+ DUK_D(DUK_DPRINT("skip mark-and-sweep torture finalizer, thread not yet viable"));
+ } else {
+ DUK_D(DUK_DPRINT("run mark-and-sweep torture finalizer"));
+ duk__markandsweep_torture_finalizer(thr);
+ }
+#endif /* DUK_USE_MARKANDSWEEP_FINALIZER_TORTURE */
+
+ if (flags & DUK_MS_FLAG_NO_FINALIZERS) {
+ DUK_D(DUK_DPRINT("finalizer run skipped because DUK_MS_FLAG_NO_FINALIZERS is set"));
+ } else {
+ duk__run_object_finalizers(heap, flags);
+ }
+
+ /*
+ * Finish
+ */
+
+ DUK_HEAP_CLEAR_MARKANDSWEEP_RUNNING(heap);
+
+ /*
+ * Assertions after
+ */
+
+#ifdef DUK_USE_ASSERTIONS
+ DUK_ASSERT(!DUK_HEAP_HAS_MARKANDSWEEP_RUNNING(heap));
+ DUK_ASSERT(!DUK_HEAP_HAS_MARKANDSWEEP_RECLIMIT_REACHED(heap));
+ DUK_ASSERT(heap->mark_and_sweep_recursion_depth == 0);
+ duk__assert_heaphdr_flags(heap);
+#ifdef DUK_USE_REFERENCE_COUNTING
+ /* Note: DUK_HEAP_HAS_REFZERO_FREE_RUNNING(heap) may be true; a refcount
+ * finalizer may trigger a mark-and-sweep.
+ */
+ duk__assert_valid_refcounts(heap);
+#endif /* DUK_USE_REFERENCE_COUNTING */
+#endif /* DUK_USE_ASSERTIONS */
+
+ /*
+ * Reset trigger counter
+ */
+
+#ifdef DUK_USE_VOLUNTARY_GC
+ tmp = (count_keep_obj + count_keep_str) / 256;
+ heap->mark_and_sweep_trigger_counter = (duk_int_t) (
+ (tmp * DUK_HEAP_MARK_AND_SWEEP_TRIGGER_MULT) +
+ DUK_HEAP_MARK_AND_SWEEP_TRIGGER_ADD);
+ DUK_D(DUK_DPRINT("garbage collect (mark-and-sweep) finished: %ld objects kept, %ld strings kept, trigger reset to %ld",
+ (long) count_keep_obj, (long) count_keep_str, (long) heap->mark_and_sweep_trigger_counter));
+#else
+ DUK_D(DUK_DPRINT("garbage collect (mark-and-sweep) finished: %ld objects kept, %ld strings kept, no voluntary trigger",
+ (long) count_keep_obj, (long) count_keep_str));
+#endif
+
+ return 0; /* OK */
+}
+
+#else /* DUK_USE_MARK_AND_SWEEP */
+
+/* no mark-and-sweep gc */
+
+#endif /* DUK_USE_MARK_AND_SWEEP */
projects / ceph.git / blobdiff