ref: 331c5ecbaca705eb8c899e814afe94971b14207b
parent: 8c5f2f24c7d7da0a2fceaf32aaa9e80d0b3b7c86
author: Tor Andersson <[email protected]>
date: Thu May 14 09:42:00 EDT 2020
Issue 133: Eliminate recursion in GC scanning phase. Use a queue instead of recursion to scan reachable objects.
--- a/jsgc.c
+++ b/jsgc.c
@@ -5,8 +5,6 @@
#include "regexp.h"
-static void jsG_markobject(js_State *J, int mark, js_Object *obj);
-
static void jsG_freeenvironment(js_State *J, js_Environment *env)
{js_free(J, env);
@@ -53,6 +51,14 @@
js_free(J, obj);
}
+/* Mark and add object to scan queue */
+static void jsG_markobject(js_State *J, int mark, js_Object *obj)
+{+ obj->gcmark = mark;
+ obj->gcroot = J->gcroot;
+ J->gcroot = obj;
+}
+
static void jsG_markfunction(js_State *J, int mark, js_Function *fun)
{int i;
@@ -87,9 +93,9 @@
jsG_markobject(J, mark, node->setter);
}
-static void jsG_markobject(js_State *J, int mark, js_Object *obj)
+/* Mark everything the object can reach. */
+static void jsG_scanobject(js_State *J, int mark, js_Object *obj)
{- obj->gcmark = mark;
if (obj->properties->level)
jsG_markproperty(J, mark, obj->properties);
if (obj->prototype && obj->prototype->gcmark != mark)
@@ -139,6 +145,8 @@
mark = J->gcmark = J->gcmark == 1 ? 2 : 1;
+ /* Add initial roots. */
+
jsG_markobject(J, mark, J->Object_prototype);
jsG_markobject(J, mark, J->Array_prototype);
jsG_markobject(J, mark, J->Function_prototype);
@@ -165,6 +173,16 @@
jsG_markenvironment(J, mark, J->GE);
for (i = 0; i < J->envtop; ++i)
jsG_markenvironment(J, mark, J->envstack[i]);
+
+ /* Scan objects until none remain. */
+
+ while ((obj = J->gcroot) != NULL) {+ J->gcroot = obj->gcroot;
+ obj->gcroot = NULL;
+ jsG_scanobject(J, mark, obj);
+ }
+
+ /* Free everything not marked. */
prevnextenv = &J->gcenv;
for (env = J->gcenv; env; env = nextenv) {--- a/jsi.h
+++ b/jsi.h
@@ -239,6 +239,8 @@
js_Object *gcobj;
js_String *gcstr;
+ js_Object *gcroot; /* gc scan list */
+
/* environments on the call stack but currently not in scope */
int envtop;
js_Environment *envstack[JS_ENVLIMIT];
--- a/jsvalue.h
+++ b/jsvalue.h
@@ -119,7 +119,8 @@
js_Finalize finalize;
} user;
} u;
- js_Object *gcnext;
+ js_Object *gcnext; /* allocation list */
+ js_Object *gcroot; /* scan list */
int gcmark;
};