aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorTeddy <ted.sybil@gmail.com>2013-08-13 22:07:31 +0800
committerTeddy <ted.sybil@gmail.com>2013-08-13 22:07:31 +0800
commitfcb069b98bb6a2f59e5ebfd2ad0ab5ee82a1bdb8 (patch)
tree72ee9cea7cc35bef2971eb5de85806eb07f20fb8
parent9982fba5f471944a2e5ab1edac97c971eb557416 (diff)
add cycle detect for `Pair`, `ProcObj`, `Envt` and `Cont`
-rw-r--r--Makefile6
-rw-r--r--eval.cpp1
-rw-r--r--gc.cpp45
-rw-r--r--gc.h17
-rw-r--r--main.cpp1
-rw-r--r--model.h7
-rw-r--r--types.cpp58
-rw-r--r--types.h20
8 files changed, 133 insertions, 22 deletions
diff --git a/Makefile b/Makefile
index 50b7f45..1f44815 100644
--- a/Makefile
+++ b/Makefile
@@ -1,8 +1,8 @@
CXX = g++ -DGMP_SUPPORT
BUILD_DIR = build
-all: release
-debug: CXX += -g -pg
+all: gc_debug
+debug: CXX += -DGC_INFO -g -pg
gc_debug: CXX += -DGC_INFO -DGC_DEBUG -g -pg
release: $(BUILD_DIR) $(BUILD_DIR)/sonsi
@@ -24,7 +24,7 @@ $(BUILD_DIR):
mkdir -p $(BUILD_DIR)
$(BUILD_DIR)/%.o : %.cpp
- $(CXX) -o $@ -c $< -Wall -O2
+ $(CXX) -o $@ -c $< -Wall
clean:
rm -rf $(BUILD_DIR)
diff --git a/eval.cpp b/eval.cpp
index bf61b3e..9e0510f 100644
--- a/eval.cpp
+++ b/eval.cpp
@@ -205,6 +205,7 @@ EvalObj *Evaluator::run_expr(Pair *prog) {
else
throw TokenError(opt->ext_repr(), SYN_ERR_CAN_NOT_APPLY);
gc.force();
+ gc.cycle_resolve();
}
}
}
diff --git a/gc.cpp b/gc.cpp
index 13dfb3c..e6937c2 100644
--- a/gc.cpp
+++ b/gc.cpp
@@ -1,6 +1,7 @@
#include "gc.h"
#include "exc.h"
#include "consts.h"
+#include <vector>
#if defined(GC_DEBUG) || defined (GC_INFO)
#include <cstdio>
@@ -8,10 +9,10 @@ typedef unsigned long long ull;
#endif
static EvalObj *gcq[GC_QUEUE_SIZE];
+static Container *cyc_list[GC_QUEUE_SIZE];
GarbageCollector::GarbageCollector() {
mapping.clear();
- pend_cnt = 0;
pending_list = NULL;
}
@@ -42,7 +43,7 @@ void GarbageCollector::force() {
for (PendingEntry *p = pending_list, *np; p; p = np)
{
np = p->next;
- if (mapping[p->obj] == 0)
+ if (mapping.count(p->obj) && mapping[p->obj] == 0)
*r++ = p->obj;
delete p;
} // fetch the pending pointers in the list
@@ -111,3 +112,43 @@ EvalObj *GarbageCollector::attach(EvalObj *ptr) {
return ptr; // passing through
}
+void GarbageCollector::cycle_resolve() {
+ if (mapping.size() < GC_CYC_THRESHOLD)
+ return;
+ EvalObjSet visited;
+ Container **clptr = cyc_list;
+ for (EvalObj2Int::iterator it = mapping.begin();
+ it != mapping.end(); it++)
+ if (it->first->is_container())
+ {
+ Container *p = static_cast<Container*>(it->first);
+ (*clptr++ = p)->gc_refs = it->second; // init the count
+ p->keep = false;
+ }
+
+ EvalObj **l = gcq, **r = l;
+ for (Container **p = cyc_list; p < clptr; p++)
+ (*p)->gc_decrement();
+ for (Container **p = cyc_list; p < clptr; p++)
+ if ((*p)->gc_refs)
+ {
+ *r++ = *p;
+ visited.insert(*p);
+ }
+ for (; l != r; l++)
+ {
+ Container *p = static_cast<Container*>(*l);
+ p->keep = true;
+ p->gc_trigger(r, visited);
+ }
+ for (Container **p = cyc_list; p < clptr; p++)
+ if (!(*p)->keep)
+ {
+ delete *p;
+ mapping.erase(*p);
+ }
+#ifdef GC_INFO
+ fprintf(stderr, "GC: cycle resolved.\n");
+#endif
+ force();
+}
diff --git a/gc.h b/gc.h
index e807048..d116a18 100644
--- a/gc.h
+++ b/gc.h
@@ -5,8 +5,23 @@
#include <map>
const int GC_QUEUE_SIZE = 262144;
+const size_t GC_CYC_THRESHOLD = 1000;
typedef std::map<EvalObj*, size_t> EvalObj2Int;
+typedef std::set<EvalObj*> EvalObjSet;
+
+#define GC_CYC_TRIGGER(ptr) \
+do { \
+ if ((ptr) && (ptr)->is_container() && !visited.count(ptr)) \
+ visited.insert(*tail++ = (ptr)); \
+} while (0)
+
+#define GC_CYC_DEC(ptr) \
+do { \
+ if ((ptr) && (ptr)->is_container()) \
+ static_cast<Container*>(ptr)->gc_refs--; \
+} while (0)
+
class GarbageCollector {
@@ -17,11 +32,11 @@ class GarbageCollector {
};
EvalObj2Int mapping;
- size_t pend_cnt;
PendingEntry *pending_list;
public:
GarbageCollector();
+ void cycle_resolve();
void force();
void expose(EvalObj *ptr);
EvalObj *attach(EvalObj *ptr);
diff --git a/main.cpp b/main.cpp
index 15a877e..54fa7d2 100644
--- a/main.cpp
+++ b/main.cpp
@@ -35,6 +35,7 @@ void load_file(const char *fname) {
fprintf(stderr, "An error occured: %s\n", e.get_msg().c_str());
}
gc.force();
+ gc.cycle_resolve();
}
}
diff --git a/model.h b/model.h
index 9ccdf20..3260fe7 100644
--- a/model.h
+++ b/model.h
@@ -2,6 +2,7 @@
#define MODEL_H
#include <string>
+#include <set>
using std::string;
@@ -103,12 +104,14 @@ class EvalObj : public FrameObj {
virtual ReprCons *get_repr_cons() = 0;
};
+typedef std::set<EvalObj*> EvalObjSet;
class Container: public EvalObj {
public:
+ bool keep;
size_t gc_refs;
- Container(int otype);
+ Container(int otype = 0);
virtual void gc_decrement() = 0;
- virtual void gc_trigger(EvalObj ** &tail) = 0;
+ virtual void gc_trigger(EvalObj ** &tail, EvalObjSet &visited) = 0;
};
/** @class RetAddr
diff --git a/types.cpp b/types.cpp
index edeeb99..8ae25fc 100644
--- a/types.cpp
+++ b/types.cpp
@@ -28,15 +28,13 @@ Pair::~Pair() {
}
void Pair::gc_decrement() {
- if (car->is_container())
- static_cast<Container*>(car)->gc_refs--;
- if (cdr->is_container())
- static_cast<Container*>(cdr)->gc_refs--;
+ GC_CYC_DEC(car);
+ GC_CYC_DEC(cdr);
}
-void Pair::gc_trigger(EvalObj ** &tail) {
- *tail++ = car;
- *tail++ = cdr;
+void Pair::gc_trigger(EvalObj ** &tail, EvalObjSet &visited) {
+ GC_CYC_TRIGGER(car);
+ GC_CYC_TRIGGER(cdr);
}
ReprCons *Pair::get_repr_cons() {
@@ -59,7 +57,10 @@ SymObj::SymObj(const string &str) :
return new ReprStr(val);
}
-OptObj::OptObj() : EvalObj(CLS_SIM_OBJ | CLS_OPT_OBJ) {}
+OptObj::OptObj() : Container(CLS_SIM_OBJ | CLS_OPT_OBJ) {}
+
+void OptObj::gc_decrement() {}
+void OptObj::gc_trigger(EvalObj ** &tail, EvalObjSet &visited) {}
ProcObj::ProcObj(Pair *_body, Environment *_envt, EvalObj *_params) :
OptObj(), body(_body), params(_params), envt(_envt) {
@@ -114,6 +115,18 @@ Pair *ProcObj::call(Pair *_args, Environment * &genvt,
return body; // Move pc to the proc entry point
}
+void ProcObj::gc_decrement() {
+ GC_CYC_DEC(body);
+ GC_CYC_DEC(params);
+ GC_CYC_DEC(envt);
+}
+
+void ProcObj::gc_trigger(EvalObj ** &tail, EvalObjSet &visited) {
+ GC_CYC_TRIGGER(body);
+ GC_CYC_TRIGGER(params);
+ GC_CYC_TRIGGER(envt);
+}
+
ReprCons *ProcObj::get_repr_cons() {
return new ReprStr("#<Procedure>");
}
@@ -268,7 +281,8 @@ ReprCons *BuiltinProcObj::get_repr_cons() {
return new ReprStr("#<Builtin Procedure: " + name + ">");
}
-Environment::Environment(Environment *_prev_envt) : prev_envt(_prev_envt) {
+Environment::Environment(Environment *_prev_envt) :
+ Container(), prev_envt(_prev_envt) {
gc.attach(prev_envt);
}
@@ -283,6 +297,20 @@ ReprCons *Environment::get_repr_cons() {
return new ReprStr("#<Environment>");
}
+void Environment::gc_decrement() {
+ GC_CYC_DEC(prev_envt);
+ for (Str2EvalObj::iterator it = binding.begin();
+ it != binding.end(); it++)
+ GC_CYC_DEC(it->second);
+}
+
+void Environment::gc_trigger(EvalObj ** &tail, EvalObjSet &visited) {
+ GC_CYC_TRIGGER(prev_envt);
+ for (Str2EvalObj::iterator it = binding.begin();
+ it != binding.end(); it++)
+ GC_CYC_TRIGGER(it->second);
+}
+
bool Environment::add_binding(SymObj *sym_obj, EvalObj *eval_obj, bool def) {
bool found = false;
string name(sym_obj->val);
@@ -337,7 +365,7 @@ EvalObj *Environment::get_obj(EvalObj *obj) {
Continuation::Continuation(Environment *_envt, Pair *_pc,
Continuation *_prev_cont, Pair *_proc_body) :
- prev_cont(_prev_cont), envt(_envt), pc(_pc), proc_body(_proc_body) {
+ Container(), prev_cont(_prev_cont), envt(_envt), pc(_pc), proc_body(_proc_body) {
gc.attach(prev_cont);
gc.attach(envt);
}
@@ -347,6 +375,16 @@ Continuation::~Continuation() {
gc.expose(envt);
}
+void Continuation::gc_decrement() {
+ GC_CYC_DEC(prev_cont);
+ GC_CYC_DEC(envt);
+}
+
+void Continuation::gc_trigger(EvalObj ** &tail, EvalObjSet &visited) {
+ GC_CYC_TRIGGER(prev_cont);
+ GC_CYC_TRIGGER(envt);
+}
+
ReprCons *Continuation::get_repr_cons() {
return new ReprStr("#<Continuation>");
}
diff --git a/types.h b/types.h
index f76a0cc..0633da1 100644
--- a/types.h
+++ b/types.h
@@ -54,7 +54,7 @@ class Pair : public Container {/*{{{*/
~Pair();
ReprCons *get_repr_cons();
void gc_decrement();
- void gc_trigger(EvalObj ** &tail);
+ void gc_trigger(EvalObj ** &tail, EvalObjSet &visited);
};/*}}}*/
/** @class EmptyList
@@ -137,7 +137,7 @@ class Continuation;
/** @class OptObj
* "Operators" in general sense
*/
-class OptObj: public EvalObj {/*{{{*/
+class OptObj: public Container {/*{{{*/
public:
OptObj();
/**
@@ -150,6 +150,9 @@ class OptObj: public EvalObj {/*{{{*/
*/
virtual Pair *call(Pair *args, Environment * &envt,
Continuation * &cont, FrameObj ** &top_ptr) = 0;
+ virtual void gc_decrement();
+ virtual void gc_trigger(EvalObj ** &tail, EvalObjSet &visited);
+
};/*}}}*/
/** @class ProcObj
@@ -170,6 +173,9 @@ class ProcObj: public OptObj {/*{{{*/
Pair *call(Pair *args, Environment * &envt,
Continuation * &cont, FrameObj ** &top_ptr);
ReprCons *get_repr_cons();
+
+ void gc_decrement();
+ void gc_trigger(EvalObj ** &tail, EvalObjSet &visited);
};/*}}}*/
/** @class SpecialOptObj
@@ -331,7 +337,7 @@ class PromObj: public EvalObj {/*{{{*/
/** @class Environment
* The environment of current evaluation, i.e. the local variable binding
*/
-class Environment : public EvalObj{/*{{{*/
+class Environment : public Container{/*{{{*/
private:
Environment *prev_envt; /**< Pointer to the upper-level environment */
Str2EvalObj binding; /**< Store all pairs of identifier and its
@@ -354,6 +360,9 @@ class Environment : public EvalObj{/*{{{*/
* */
EvalObj *get_obj(EvalObj *obj);
ReprCons *get_repr_cons();
+
+ void gc_decrement();
+ void gc_trigger(EvalObj ** &tail, EvalObjSet &visited);
};/*}}}*/
/** @class Continuation
@@ -361,7 +370,7 @@ class Environment : public EvalObj{/*{{{*/
* being made (Behave like a stack frame in C). When the call has accomplished,
* the system will restore all the registers according to the continuation.
*/
-class Continuation : public EvalObj {/*{{{*/
+class Continuation : public Container {/*{{{*/
public:
/** Linking the previous continuation on the chain */
Continuation *prev_cont;
@@ -377,6 +386,9 @@ class Continuation : public EvalObj {/*{{{*/
Pair *proc_body);
~Continuation();
ReprCons *get_repr_cons();
+
+ void gc_decrement();
+ void gc_trigger(EvalObj ** &tail, EvalObjSet &visited);
};/*}}}*/
/** @class InexactNumObj