summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorRubidium <rubidium@openttd.org>2021-04-15 18:47:41 +0200
committerCharles Pigott <charlespigott@googlemail.com>2021-04-17 19:18:51 +0100
commit47a99bb67632b6c05b70024f0639c767d057c6ae (patch)
tree9b31843a7dfc6fbf447f649c8a3eb0fac2dbffce
parent6c49ae9cd7612a0e7a4542cc49d7361889d0f345 (diff)
downloadopenttd-47a99bb67632b6c05b70024f0639c767d057c6ae.tar.xz
Fix #7513: recursive garbage collection caused stack overflow
-rw-r--r--src/3rdparty/squirrel/squirrel/sqarray.h2
-rw-r--r--src/3rdparty/squirrel/squirrel/sqclass.h4
-rw-r--r--src/3rdparty/squirrel/squirrel/sqclosure.h6
-rw-r--r--src/3rdparty/squirrel/squirrel/sqobject.cpp131
-rw-r--r--src/3rdparty/squirrel/squirrel/sqobject.h38
-rw-r--r--src/3rdparty/squirrel/squirrel/sqstate.cpp65
-rw-r--r--src/3rdparty/squirrel/squirrel/sqstate.h4
-rw-r--r--src/3rdparty/squirrel/squirrel/sqtable.h2
-rw-r--r--src/3rdparty/squirrel/squirrel/squserdata.h2
-rw-r--r--src/3rdparty/squirrel/squirrel/sqvm.h2
10 files changed, 139 insertions, 117 deletions
diff --git a/src/3rdparty/squirrel/squirrel/sqarray.h b/src/3rdparty/squirrel/squirrel/sqarray.h
index 5c2635207..37d91bc4e 100644
--- a/src/3rdparty/squirrel/squirrel/sqarray.h
+++ b/src/3rdparty/squirrel/squirrel/sqarray.h
@@ -17,7 +17,7 @@ public:
return newarray;
}
#ifndef NO_GARBAGE_COLLECTOR
- void Mark(SQCollectable **chain);
+ void EnqueueMarkObjectForChildren(SQGCMarkerQueue &queue);
#endif
void Finalize(){
_values.resize(0);
diff --git a/src/3rdparty/squirrel/squirrel/sqclass.h b/src/3rdparty/squirrel/squirrel/sqclass.h
index 895c053c2..cb0973bbe 100644
--- a/src/3rdparty/squirrel/squirrel/sqclass.h
+++ b/src/3rdparty/squirrel/squirrel/sqclass.h
@@ -59,7 +59,7 @@ public:
}
void Finalize();
#ifndef NO_GARBAGE_COLLECTOR
- void Mark(SQCollectable ** );
+ void EnqueueMarkObjectForChildren(SQGCMarkerQueue &queue);
#endif
SQInteger Next(const SQObjectPtr &refpos, SQObjectPtr &outkey, SQObjectPtr &outval);
SQInstance *CreateInstance();
@@ -147,7 +147,7 @@ public:
}
void Finalize();
#ifndef NO_GARBAGE_COLLECTOR
- void Mark(SQCollectable ** );
+ void EnqueueMarkObjectForChildren(SQGCMarkerQueue &queue);
#endif
bool InstanceOf(SQClass *trg);
bool GetMetaMethod(SQVM *v,SQMetaMethod mm,SQObjectPtr &res);
diff --git a/src/3rdparty/squirrel/squirrel/sqclosure.h b/src/3rdparty/squirrel/squirrel/sqclosure.h
index a42dcd575..8480fb8af 100644
--- a/src/3rdparty/squirrel/squirrel/sqclosure.h
+++ b/src/3rdparty/squirrel/squirrel/sqclosure.h
@@ -32,7 +32,7 @@ public:
bool Save(SQVM *v,SQUserPointer up,SQWRITEFUNC write);
static bool Load(SQVM *v,SQUserPointer up,SQREADFUNC read,SQObjectPtr &ret);
#ifndef NO_GARBAGE_COLLECTOR
- void Mark(SQCollectable **chain);
+ void EnqueueMarkObjectForChildren(SQGCMarkerQueue &queue);
void Finalize(){_outervalues.resize(0); }
#endif
SQObjectPtr _env;
@@ -66,7 +66,7 @@ public:
bool Yield(SQVM *v);
bool Resume(SQVM *v,SQInteger target);
#ifndef NO_GARBAGE_COLLECTOR
- void Mark(SQCollectable **chain);
+ void EnqueueMarkObjectForChildren(SQGCMarkerQueue &queue);
void Finalize(){_stack.resize(0);_closure=_null_;}
#endif
SQObjectPtr _closure;
@@ -106,7 +106,7 @@ public:
sq_delete(this,SQNativeClosure);
}
#ifndef NO_GARBAGE_COLLECTOR
- void Mark(SQCollectable **chain);
+ void EnqueueMarkObjectForChildren(SQGCMarkerQueue &queue);
void Finalize(){_outervalues.resize(0);}
#endif
SQInteger _nparamscheck;
diff --git a/src/3rdparty/squirrel/squirrel/sqobject.cpp b/src/3rdparty/squirrel/squirrel/sqobject.cpp
index d48baca1e..a113f316d 100644
--- a/src/3rdparty/squirrel/squirrel/sqobject.cpp
+++ b/src/3rdparty/squirrel/squirrel/sqobject.cpp
@@ -486,104 +486,81 @@ bool SQFunctionProto::Load(SQVM *v,SQUserPointer up,SQREADFUNC read,SQObjectPtr
#ifndef NO_GARBAGE_COLLECTOR
-#define START_MARK() if(!(_uiRef&MARK_FLAG)){ \
- _uiRef|=MARK_FLAG;
-
-#define END_MARK() RemoveFromChain(&_sharedstate->_gc_chain, this); \
- AddToChain(chain, this); }
-
-void SQVM::Mark(SQCollectable **chain)
+void SQVM::EnqueueMarkObjectForChildren(SQGCMarkerQueue &queue)
{
- START_MARK()
- SQSharedState::MarkObject(_lasterror,chain);
- SQSharedState::MarkObject(_errorhandler,chain);
- SQSharedState::MarkObject(_debughook,chain);
- SQSharedState::MarkObject(_roottable, chain);
- SQSharedState::MarkObject(temp_reg, chain);
- for(SQUnsignedInteger i = 0; i < _stack.size(); i++) SQSharedState::MarkObject(_stack[i], chain);
- for(SQUnsignedInteger j = 0; j < _vargsstack.size(); j++) SQSharedState::MarkObject(_vargsstack[j], chain);
- for(SQInteger k = 0; k < _callsstacksize; k++) SQSharedState::MarkObject(_callsstack[k]._closure, chain);
- END_MARK()
-}
-
-void SQArray::Mark(SQCollectable **chain)
+ SQSharedState::EnqueueMarkObject(_lasterror,queue);
+ SQSharedState::EnqueueMarkObject(_errorhandler,queue);
+ SQSharedState::EnqueueMarkObject(_debughook,queue);
+ SQSharedState::EnqueueMarkObject(_roottable, queue);
+ SQSharedState::EnqueueMarkObject(temp_reg, queue);
+ for(SQUnsignedInteger i = 0; i < _stack.size(); i++) SQSharedState::EnqueueMarkObject(_stack[i], queue);
+ for(SQUnsignedInteger j = 0; j < _vargsstack.size(); j++) SQSharedState::EnqueueMarkObject(_vargsstack[j], queue);
+ for(SQInteger k = 0; k < _callsstacksize; k++) SQSharedState::EnqueueMarkObject(_callsstack[k]._closure, queue);
+}
+
+void SQArray::EnqueueMarkObjectForChildren(SQGCMarkerQueue &queue)
{
- START_MARK()
- SQInteger len = _values.size();
- for(SQInteger i = 0;i < len; i++) SQSharedState::MarkObject(_values[i], chain);
- END_MARK()
+ SQInteger len = _values.size();
+ for(SQInteger i = 0;i < len; i++) SQSharedState::EnqueueMarkObject(_values[i], queue);
}
-void SQTable::Mark(SQCollectable **chain)
+
+void SQTable::EnqueueMarkObjectForChildren(SQGCMarkerQueue &queue)
{
- START_MARK()
- if(_delegate) _delegate->Mark(chain);
- SQInteger len = _numofnodes;
- for(SQInteger i = 0; i < len; i++){
- SQSharedState::MarkObject(_nodes[i].key, chain);
- SQSharedState::MarkObject(_nodes[i].val, chain);
- }
- END_MARK()
+ if(_delegate) queue.Enqueue(_delegate);
+ SQInteger len = _numofnodes;
+ for(SQInteger i = 0; i < len; i++){
+ SQSharedState::EnqueueMarkObject(_nodes[i].key, queue);
+ SQSharedState::EnqueueMarkObject(_nodes[i].val, queue);
+ }
}
-void SQClass::Mark(SQCollectable **chain)
+void SQClass::EnqueueMarkObjectForChildren(SQGCMarkerQueue &queue)
{
- START_MARK()
- _members->Mark(chain);
- if(_base) _base->Mark(chain);
- SQSharedState::MarkObject(_attributes, chain);
- for(SQUnsignedInteger i =0; i< _defaultvalues.size(); i++) {
- SQSharedState::MarkObject(_defaultvalues[i].val, chain);
- SQSharedState::MarkObject(_defaultvalues[i].attrs, chain);
- }
- for(SQUnsignedInteger j =0; j< _methods.size(); j++) {
- SQSharedState::MarkObject(_methods[j].val, chain);
- SQSharedState::MarkObject(_methods[j].attrs, chain);
- }
- for(SQUnsignedInteger k =0; k< _metamethods.size(); k++) {
- SQSharedState::MarkObject(_metamethods[k], chain);
- }
- END_MARK()
+ queue.Enqueue(_members);
+ if(_base) queue.Enqueue(_base);
+ SQSharedState::EnqueueMarkObject(_attributes, queue);
+ for(SQUnsignedInteger i =0; i< _defaultvalues.size(); i++) {
+ SQSharedState::EnqueueMarkObject(_defaultvalues[i].val, queue);
+ SQSharedState::EnqueueMarkObject(_defaultvalues[i].attrs, queue);
+ }
+ for(SQUnsignedInteger j =0; j< _methods.size(); j++) {
+ SQSharedState::EnqueueMarkObject(_methods[j].val, queue);
+ SQSharedState::EnqueueMarkObject(_methods[j].attrs, queue);
+ }
+ for(SQUnsignedInteger k =0; k< _metamethods.size(); k++) {
+ SQSharedState::EnqueueMarkObject(_metamethods[k], queue);
+ }
}
-void SQInstance::Mark(SQCollectable **chain)
+void SQInstance::EnqueueMarkObjectForChildren(SQGCMarkerQueue &queue)
{
- START_MARK()
- _class->Mark(chain);
- SQUnsignedInteger nvalues = _class->_defaultvalues.size();
- for(SQUnsignedInteger i =0; i< nvalues; i++) {
- SQSharedState::MarkObject(_values[i], chain);
- }
- END_MARK()
+ queue.Enqueue(_class);
+ SQUnsignedInteger nvalues = _class->_defaultvalues.size();
+ for(SQUnsignedInteger i =0; i< nvalues; i++) {
+ SQSharedState::EnqueueMarkObject(_values[i], queue);
+ }
}
-void SQGenerator::Mark(SQCollectable **chain)
+void SQGenerator::EnqueueMarkObjectForChildren(SQGCMarkerQueue &queue)
{
- START_MARK()
- for(SQUnsignedInteger i = 0; i < _stack.size(); i++) SQSharedState::MarkObject(_stack[i], chain);
- for(SQUnsignedInteger j = 0; j < _vargsstack.size(); j++) SQSharedState::MarkObject(_vargsstack[j], chain);
- SQSharedState::MarkObject(_closure, chain);
- END_MARK()
+ for(SQUnsignedInteger i = 0; i < _stack.size(); i++) SQSharedState::EnqueueMarkObject(_stack[i], queue);
+ for(SQUnsignedInteger j = 0; j < _vargsstack.size(); j++) SQSharedState::EnqueueMarkObject(_vargsstack[j], queue);
+ SQSharedState::EnqueueMarkObject(_closure, queue);
}
-void SQClosure::Mark(SQCollectable **chain)
+void SQClosure::EnqueueMarkObjectForChildren(SQGCMarkerQueue &queue)
{
- START_MARK()
- for(SQUnsignedInteger i = 0; i < _outervalues.size(); i++) SQSharedState::MarkObject(_outervalues[i], chain);
- for(SQUnsignedInteger i = 0; i < _defaultparams.size(); i++) SQSharedState::MarkObject(_defaultparams[i], chain);
- END_MARK()
+ for(SQUnsignedInteger i = 0; i < _outervalues.size(); i++) SQSharedState::EnqueueMarkObject(_outervalues[i], queue);
+ for(SQUnsignedInteger i = 0; i < _defaultparams.size(); i++) SQSharedState::EnqueueMarkObject(_defaultparams[i], queue);
}
-void SQNativeClosure::Mark(SQCollectable **chain)
+void SQNativeClosure::EnqueueMarkObjectForChildren(SQGCMarkerQueue &queue)
{
- START_MARK()
- for(SQUnsignedInteger i = 0; i < _outervalues.size(); i++) SQSharedState::MarkObject(_outervalues[i], chain);
- END_MARK()
+ for(SQUnsignedInteger i = 0; i < _outervalues.size(); i++) SQSharedState::EnqueueMarkObject(_outervalues[i], queue);
}
-void SQUserData::Mark(SQCollectable **chain){
- START_MARK()
- if(_delegate) _delegate->Mark(chain);
- END_MARK()
+void SQUserData::EnqueueMarkObjectForChildren(SQGCMarkerQueue &queue){
+ if(_delegate) queue.Enqueue(_delegate);
}
void SQCollectable::UnMark() { _uiRef&=~MARK_FLAG; }
diff --git a/src/3rdparty/squirrel/squirrel/sqobject.h b/src/3rdparty/squirrel/squirrel/sqobject.h
index d71e515a8..ed4f31fcb 100644
--- a/src/3rdparty/squirrel/squirrel/sqobject.h
+++ b/src/3rdparty/squirrel/squirrel/sqobject.h
@@ -2,6 +2,7 @@
#ifndef _SQOBJECT_H_
#define _SQOBJECT_H_
+#include <forward_list>
#include "squtils.h"
#define SQ_CLOSURESTREAM_HEAD (('S'<<24)|('Q'<<16)|('I'<<8)|('R'))
@@ -344,13 +345,48 @@ struct SQCollectable : public SQRefCounted {
SQCollectable *_prev;
SQSharedState *_sharedstate;
virtual void Release()=0;
- virtual void Mark(SQCollectable **chain)=0;
+ virtual void EnqueueMarkObjectForChildren(class SQGCMarkerQueue &queue)=0;
void UnMark();
virtual void Finalize()=0;
static void AddToChain(SQCollectable **chain,SQCollectable *c);
static void RemoveFromChain(SQCollectable **chain,SQCollectable *c);
};
+/**
+ * Helper container for state to change the garbage collection from a recursive to an iterative approach.
+ * The iterative approach provides effectively a depth first search approach.
+ */
+class SQGCMarkerQueue {
+ std::forward_list<SQCollectable*> queue; ///< The queue of elements to still process.
+public:
+ /** Whether there are any elements left to process. */
+ bool IsEmpty() { return this->queue.empty(); }
+
+ /**
+ * Remove the first element from the queue.
+ * Removal when the queue is empty results in undefined behaviour.
+ */
+ SQCollectable *Pop()
+ {
+ SQCollectable *collectable = this->queue.front();
+ this->queue.pop_front();
+ return collectable;
+ }
+
+ /**
+ * Add a collectable to the queue, but only when it has not been marked yet.
+ * When adding it to the queue, the collectable will be marked, so subsequent calls
+ * will not add it again.
+ */
+ void Enqueue(SQCollectable *collectable)
+ {
+ if ((collectable->_uiRef & MARK_FLAG) == 0) {
+ collectable->_uiRef |= MARK_FLAG;
+ this->queue.push_front(collectable);
+ }
+ }
+};
+
#define ADD_TO_CHAIN(chain,obj) AddToChain(chain,obj)
#define REMOVE_FROM_CHAIN(chain,obj) {if(!(_uiRef&MARK_FLAG))RemoveFromChain(chain,obj);}
diff --git a/src/3rdparty/squirrel/squirrel/sqstate.cpp b/src/3rdparty/squirrel/squirrel/sqstate.cpp
index 8233ad178..9d91c7899 100644
--- a/src/3rdparty/squirrel/squirrel/sqstate.cpp
+++ b/src/3rdparty/squirrel/squirrel/sqstate.cpp
@@ -228,18 +228,18 @@ SQInteger SQSharedState::GetMetaMethodIdxByName(const SQObjectPtr &name)
#ifndef NO_GARBAGE_COLLECTOR
-void SQSharedState::MarkObject(SQObjectPtr &o,SQCollectable **chain)
+void SQSharedState::EnqueueMarkObject(SQObjectPtr &o,SQGCMarkerQueue &queue)
{
switch(type(o)){
- case OT_TABLE:_table(o)->Mark(chain);break;
- case OT_ARRAY:_array(o)->Mark(chain);break;
- case OT_USERDATA:_userdata(o)->Mark(chain);break;
- case OT_CLOSURE:_closure(o)->Mark(chain);break;
- case OT_NATIVECLOSURE:_nativeclosure(o)->Mark(chain);break;
- case OT_GENERATOR:_generator(o)->Mark(chain);break;
- case OT_THREAD:_thread(o)->Mark(chain);break;
- case OT_CLASS:_class(o)->Mark(chain);break;
- case OT_INSTANCE:_instance(o)->Mark(chain);break;
+ case OT_TABLE:queue.Enqueue(_table(o));break;
+ case OT_ARRAY:queue.Enqueue(_array(o));break;
+ case OT_USERDATA:queue.Enqueue(_userdata(o));break;
+ case OT_CLOSURE:queue.Enqueue(_closure(o));break;
+ case OT_NATIVECLOSURE:queue.Enqueue(_nativeclosure(o));break;
+ case OT_GENERATOR:queue.Enqueue(_generator(o));break;
+ case OT_THREAD:queue.Enqueue(_thread(o));break;
+ case OT_CLASS:queue.Enqueue(_class(o));break;
+ case OT_INSTANCE:queue.Enqueue(_instance(o));break;
default: break; //shutup compiler
}
}
@@ -248,27 +248,36 @@ void SQSharedState::MarkObject(SQObjectPtr &o,SQCollectable **chain)
SQInteger SQSharedState::CollectGarbage(SQVM *vm)
{
SQInteger n=0;
- SQCollectable *tchain=NULL;
SQVM *vms = _thread(_root_vm);
- vms->Mark(&tchain);
+ SQGCMarkerQueue queue;
+ queue.Enqueue(vms);
#ifdef WITH_ASSERT
SQInteger x = _table(_thread(_root_vm)->_roottable)->CountUsed();
#endif
- _refs_table.Mark(&tchain);
- MarkObject(_registry,&tchain);
- MarkObject(_consts,&tchain);
- MarkObject(_metamethodsmap,&tchain);
- MarkObject(_table_default_delegate,&tchain);
- MarkObject(_array_default_delegate,&tchain);
- MarkObject(_string_default_delegate,&tchain);
- MarkObject(_number_default_delegate,&tchain);
- MarkObject(_generator_default_delegate,&tchain);
- MarkObject(_thread_default_delegate,&tchain);
- MarkObject(_closure_default_delegate,&tchain);
- MarkObject(_class_default_delegate,&tchain);
- MarkObject(_instance_default_delegate,&tchain);
- MarkObject(_weakref_default_delegate,&tchain);
+ _refs_table.EnqueueMarkObject(queue);
+ EnqueueMarkObject(_registry,queue);
+ EnqueueMarkObject(_consts,queue);
+ EnqueueMarkObject(_metamethodsmap,queue);
+ EnqueueMarkObject(_table_default_delegate,queue);
+ EnqueueMarkObject(_array_default_delegate,queue);
+ EnqueueMarkObject(_string_default_delegate,queue);
+ EnqueueMarkObject(_number_default_delegate,queue);
+ EnqueueMarkObject(_generator_default_delegate,queue);
+ EnqueueMarkObject(_thread_default_delegate,queue);
+ EnqueueMarkObject(_closure_default_delegate,queue);
+ EnqueueMarkObject(_class_default_delegate,queue);
+ EnqueueMarkObject(_instance_default_delegate,queue);
+ EnqueueMarkObject(_weakref_default_delegate,queue);
+
+ SQCollectable *tchain=NULL;
+
+ while (!queue.IsEmpty()) {
+ SQCollectable *q = queue.Pop();
+ q->EnqueueMarkObjectForChildren(queue);
+ SQCollectable::RemoveFromChain(&_gc_chain, q);
+ SQCollectable::AddToChain(&tchain, q);
+ }
SQCollectable *t = _gc_chain;
SQCollectable *nx = NULL;
@@ -357,12 +366,12 @@ RefTable::~RefTable()
}
#ifndef NO_GARBAGE_COLLECTOR
-void RefTable::Mark(SQCollectable **chain)
+void RefTable::EnqueueMarkObject(SQGCMarkerQueue &queue)
{
RefNode *nodes = (RefNode *)_nodes;
for(SQUnsignedInteger n = 0; n < _numofslots; n++) {
if(type(nodes->obj) != OT_NULL) {
- SQSharedState::MarkObject(nodes->obj,chain);
+ SQSharedState::EnqueueMarkObject(nodes->obj,queue);
}
nodes++;
}
diff --git a/src/3rdparty/squirrel/squirrel/sqstate.h b/src/3rdparty/squirrel/squirrel/sqstate.h
index da6bf9ae6..d1a1f8dd6 100644
--- a/src/3rdparty/squirrel/squirrel/sqstate.h
+++ b/src/3rdparty/squirrel/squirrel/sqstate.h
@@ -34,7 +34,7 @@ struct RefTable {
void AddRef(SQObject &obj);
SQBool Release(SQObject &obj);
#ifndef NO_GARBAGE_COLLECTOR
- void Mark(SQCollectable **chain);
+ void EnqueueMarkObject(SQGCMarkerQueue &queue);
#endif
void Finalize();
private:
@@ -63,7 +63,7 @@ public:
SQInteger GetMetaMethodIdxByName(const SQObjectPtr &name);
#ifndef NO_GARBAGE_COLLECTOR
SQInteger CollectGarbage(SQVM *vm);
- static void MarkObject(SQObjectPtr &o,SQCollectable **chain);
+ static void EnqueueMarkObject(SQObjectPtr &o,SQGCMarkerQueue &queue);
#endif
SQObjectPtrVec *_metamethods;
SQObjectPtr _metamethodsmap;
diff --git a/src/3rdparty/squirrel/squirrel/sqtable.h b/src/3rdparty/squirrel/squirrel/sqtable.h
index 52d9ba41a..0083a90a9 100644
--- a/src/3rdparty/squirrel/squirrel/sqtable.h
+++ b/src/3rdparty/squirrel/squirrel/sqtable.h
@@ -60,7 +60,7 @@ public:
SQ_FREE(_nodes, _numofnodes * sizeof(_HashNode));
}
#ifndef NO_GARBAGE_COLLECTOR
- void Mark(SQCollectable **chain);
+ void EnqueueMarkObjectForChildren(SQGCMarkerQueue &queue);
#endif
inline _HashNode *_Get(const SQObjectPtr &key,SQHash hash)
{
diff --git a/src/3rdparty/squirrel/squirrel/squserdata.h b/src/3rdparty/squirrel/squirrel/squserdata.h
index 3bf1a9dba..ca4933de2 100644
--- a/src/3rdparty/squirrel/squirrel/squserdata.h
+++ b/src/3rdparty/squirrel/squirrel/squserdata.h
@@ -18,7 +18,7 @@ struct SQUserData : SQDelegable
return ud;
}
#ifndef NO_GARBAGE_COLLECTOR
- void Mark(SQCollectable **chain);
+ void EnqueueMarkObjectForChildren(SQGCMarkerQueue &queue);
void Finalize(){SetDelegate(NULL);}
#endif
void Release() {
diff --git a/src/3rdparty/squirrel/squirrel/sqvm.h b/src/3rdparty/squirrel/squirrel/sqvm.h
index 9c8e986fb..dbfe2309c 100644
--- a/src/3rdparty/squirrel/squirrel/sqvm.h
+++ b/src/3rdparty/squirrel/squirrel/sqvm.h
@@ -113,7 +113,7 @@ public:
#endif
#ifndef NO_GARBAGE_COLLECTOR
- void Mark(SQCollectable **chain);
+ void EnqueueMarkObjectForChildren(SQGCMarkerQueue &queue);
#endif
void Finalize();
void GrowCallStack() {