1 //
2 // Copyright (c) ZeroC, Inc. All rights reserved.
3 //
4
5 #include <Ice/GCObject.h>
6
7 #ifndef ICE_CPP11_MAPPING
8
9 #include <set>
10 #include <stack>
11
12 using namespace std;
13 using namespace IceUtil;
14 using namespace IceInternal;
15
16 namespace
17 {
18
19 typedef ::map<GCObject*, int> GCCountMap;
20 Mutex* gcMutex = 0;
21
22 class Init
23 {
24 public:
25
Init()26 Init()
27 {
28 gcMutex = new Mutex();
29 }
30
~Init()31 ~Init()
32 {
33 delete gcMutex;
34 gcMutex = 0;
35 }
36 };
37
38 Init init;
39
40 class ClearMembers : public GCVisitor
41 {
42 public:
43
44 virtual bool visit(GCObject*);
45 };
46 ClearMembers clearMembers;
47
48 class DecreaseRefCounts : public GCVisitor
49 {
50 public:
51
52 DecreaseRefCounts(GCCountMap&);
53
54 virtual bool visit(GCObject*);
55
56 private:
57
58 GCCountMap& _counts;
59 };
60
61 class RestoreRefCountsIfReachable : public GCVisitor
62 {
63 public:
64
65 RestoreRefCountsIfReachable(GCCountMap&);
66
67 virtual bool visit(GCObject*);
68
69 private:
70
71 GCCountMap& _counts;
72 bool _reachable;
73 };
74
75 class MarkCollectable : public GCVisitor
76 {
77 public:
78
79 MarkCollectable();
80
81 virtual bool visit(GCObject*);
82
83 void visitNeighbor(GCObject*);
84
85 private:
86
87 int _counter;
88 map<GCObject*, int> _numbers;
89 stack<GCObject*> _p;
90 stack<GCObject*> _s;
91
92 class VisitNeighbors : public IceInternal::GCVisitor
93 {
94 public:
95
96 void setVisitor(MarkCollectable*);
97 virtual bool visit(GCObject*);
98
99 private:
100
101 MarkCollectable* _visitor;
102 };
103 VisitNeighbors _neighborsVisitor;
104 };
105
106 class ClearCollectable : public GCVisitor
107 {
108 public:
109
110 virtual bool visit(GCObject*);
111 };
112
113 }
114
115 bool
visit(GCObject *)116 ClearMembers::visit(GCObject*)
117 {
118 return true;
119 }
120
DecreaseRefCounts(GCCountMap & counts)121 DecreaseRefCounts::DecreaseRefCounts(GCCountMap& counts) : _counts(counts)
122 {
123 }
124
125 bool
visit(GCObject * obj)126 DecreaseRefCounts::visit(GCObject* obj)
127 {
128 //
129 // Visit the object only once when the object is inserted for
130 // the first time in the counts map. After, we just decrement
131 // its reference count. Decrementing the reference counts of
132 // reachable objects will indicate when a cycle is
133 // collectable. Collectable objects are those with a reference
134 // count of zero and for which there's no "reachable" parent
135 // object (objects with a reference count > 0).
136 //
137 GCCountMap::iterator p = _counts.find(obj);
138 if(p == _counts.end())
139 {
140 _counts.insert(make_pair(obj, obj->_iceGetRefUnsafe() - 1));
141 if(obj->__hasFlag(GCObject::Collectable))
142 {
143 obj->_iceGcVisitMembers(*this);
144 }
145 }
146 else
147 {
148 --p->second;
149 }
150 return false;
151 }
152
RestoreRefCountsIfReachable(GCCountMap & counts)153 RestoreRefCountsIfReachable::RestoreRefCountsIfReachable(GCCountMap& counts) : _counts(counts), _reachable(false)
154 {
155 }
156
157 bool
visit(GCObject * obj)158 RestoreRefCountsIfReachable::visit(GCObject* obj)
159 {
160 GCCountMap::iterator p = _counts.find(obj);
161 if(p == _counts.end())
162 {
163 //
164 // If the object has been removed from the counts map,
165 // it's reachable.
166 //
167 return false;
168 }
169 else if(_reachable)
170 {
171 //
172 // If parent object is reachable, this object is also
173 // reachable. Remove it from the counts map and also make
174 // reachable children.
175 //
176 _counts.erase(p);
177 obj->_iceGcVisitMembers(*this);
178 }
179 else if(p->second == 0)
180 {
181 //
182 // If the object is collectable, set its count to -1 to
183 // indicate that it was already visited prevent it from
184 // being visited again.
185 //
186 p->second = -1;
187 obj->_iceGcVisitMembers(*this);
188 }
189 else if(p->second > 0)
190 {
191 //
192 // Object isn't collectable, remove it from the counts map
193 // and visit its sub-graph to remove children wobjects from
194 // the counts map since they are also reachable.
195 //
196 _counts.erase(p);
197
198 _reachable = true;
199 obj->_iceGcVisitMembers(*this);
200 _reachable = false;
201 }
202 return false;
203 }
204
MarkCollectable()205 MarkCollectable::MarkCollectable() : _counter(0)
206 {
207 _neighborsVisitor.setVisitor(this);
208 }
209
210 bool
visit(GCObject * obj)211 MarkCollectable::visit(GCObject* obj)
212 {
213 //
214 // Set the collectable flag on the object graph. While setting the
215 // flag, we also check if the object graph has cycles and mark all the
216 // objects which are part of a cycle with the CycleMember flag.
217 //
218 // We use the path-based strong component algorithm to detect the
219 // strong components of the graph.
220 //
221
222 if(obj->__hasFlag(GCObject::Collectable))
223 {
224 return false;
225 }
226 obj->__setFlag(GCObject::Collectable);
227
228 _numbers[obj] = ++_counter;
229 _p.push(obj);
230 _s.push(obj);
231
232 obj->_iceGcVisitMembers(_neighborsVisitor);
233
234 if(_p.top() == obj)
235 {
236 GCObject* o;
237 do
238 {
239 o = _s.top();
240 _s.pop();
241 o->__setFlag(GCObject::CycleMember);
242 }
243 while(o != obj);
244 _p.pop();
245 }
246 return false;
247 }
248
249 void
visitNeighbor(GCObject * obj)250 MarkCollectable::visitNeighbor(GCObject* obj)
251 {
252 map<GCObject*, int>::const_iterator p = _numbers.find(obj);
253 if(p == _numbers.end())
254 {
255 visit(obj);
256 }
257 else if(!obj->__hasFlag(GCObject::CycleMember))
258 {
259 while(_numbers[_p.top()] > p->second)
260 {
261 _p.pop();
262 }
263 }
264 }
265
266 void
setVisitor(MarkCollectable * visitor)267 MarkCollectable::VisitNeighbors::setVisitor(MarkCollectable* visitor)
268 {
269 _visitor = visitor;
270 }
271
272 bool
visit(GCObject * obj)273 MarkCollectable::VisitNeighbors::visit(GCObject* obj)
274 {
275 _visitor->visitNeighbor(obj);
276 return false;
277 }
278
279 bool
visit(GCObject * obj)280 ClearCollectable::visit(GCObject* obj)
281 {
282 //
283 // Clear the collectable flag on the object graph.
284 //
285 if(obj->__hasFlag(GCObject::Collectable))
286 {
287 obj->__clearFlag(GCObject::Collectable | GCObject::CycleMember);
288 obj->_iceGcVisitMembers(*this);
289 }
290 return false;
291 }
292
293 //
294 // Flags constant used for collection of graphs.
295 //
296 const unsigned char GCObject::Collectable = 2;
297 const unsigned char GCObject::CycleMember = 4;
298 const unsigned char GCObject::Visiting = 8;
299
300 //
301 // GCObject
302 //
303 void
__incRef()304 IceInternal::GCObject::__incRef()
305 {
306 IceUtilInternal::MutexPtrLock<IceUtil::Mutex> lock(gcMutex);
307 ++_ref;
308 }
309
310 void
__decRef()311 IceInternal::GCObject::__decRef()
312 {
313 IceUtilInternal::MutexPtrLock<IceUtil::Mutex> lock(gcMutex);
314 bool doDelete = false;
315 assert(_ref > 0);
316
317 //
318 // Try to collect the object each time its reference count is
319 // decremented and only if it's part of a cycle.
320 //
321 if(_ref > 1 && __hasFlag(CycleMember) && collect(lock))
322 {
323 return;
324 }
325
326 if(--_ref == 0)
327 {
328 doDelete = !__hasFlag(NoDelete);
329 __setFlag(NoDelete);
330 }
331
332 lock.release();
333 if(doDelete)
334 {
335 delete this;
336 }
337 }
338
339 int
__getRef() const340 IceInternal::GCObject::__getRef() const
341 {
342 IceUtilInternal::MutexPtrLock<IceUtil::Mutex> lock(gcMutex);
343 return _ref;
344 }
345
346 void
__setNoDelete(bool b)347 IceInternal::GCObject::__setNoDelete(bool b)
348 {
349 IceUtilInternal::MutexPtrLock<IceUtil::Mutex> lock(gcMutex);
350 IceUtil::Shared::__setNoDelete(b);
351 }
352
353 bool
_iceGcVisit(GCVisitor & v)354 GCObject::_iceGcVisit(GCVisitor& v)
355 {
356 return v.visit(this);
357 }
358
359 void
ice_collectable(bool enable)360 GCObject::ice_collectable(bool enable)
361 {
362 IceUtilInternal::MutexPtrLock<IceUtil::Mutex> lock(gcMutex);
363 if(enable)
364 {
365 ClearCollectable().visit(this);
366 MarkCollectable().visit(this);
367 }
368 else
369 {
370 ClearCollectable().visit(this);
371 }
372 }
373
374 bool
collect(IceUtilInternal::MutexPtrLock<IceUtil::Mutex> & lock)375 GCObject::collect(IceUtilInternal::MutexPtrLock<IceUtil::Mutex>& lock)
376 {
377 GCCountMap counts;
378
379 //
380 // Go through the object graph and decrease reference counts for
381 // all the objects from the graph. Cycles which can be collected
382 // should lead to objects with a zero reference count.
383 //
384 DecreaseRefCounts(counts).visit(this);
385 assert(counts.find(this) != counts.end());
386 if(counts[this] > 0)
387 {
388 return false; // Object is still reachable, we're done.
389 }
390
391 //
392 // Go the graph again and check for objects which are still
393 // reachable. If there are any, we restore the reference counts
394 // for the sub-graph of the reachable object and we remove the
395 // reachable objects from the counts map. At the end, if the
396 // counts map is empty, it indicates that this object graph isn't
397 // collectable yet.
398 //
399 RestoreRefCountsIfReachable(counts).visit(this);
400 if(counts.empty())
401 {
402 return false;
403 }
404
405 assert(counts.find(this) != counts.end()); // This object must be collectable.
406
407 //
408 // At this point, we can release the lock. The objects from counts
409 // are un-reachable from the user code and clearing the members of
410 // the collectable objects requires acquiring the mutex to
411 // decrement their reference counts.
412 //
413 lock.release();
414
415 //
416 // Break all the cyclic reference counts of objects which are
417 // remaining in the counts map by clearing members.
418 //
419 // We first go through the list to mark all the objects as
420 // non-deletable and we also disable collection for all those
421 // objects since we already know they are collectable.
422 //
423 // After clearing members, we delete all the collectable
424 // objects. We can't just delete the objects since those objects
425 // likely point to each other.
426 //
427 for(GCCountMap::const_iterator p = counts.begin(); p != counts.end(); ++p)
428 {
429 p->first->__setFlag(NoDelete);
430 p->first->__clearFlag(CycleMember); // Disable cycle collection.
431 }
432 for(GCCountMap::const_iterator p = counts.begin(); p != counts.end(); ++p)
433 {
434 p->first->_iceGcVisitMembers(clearMembers);
435 }
436 for(GCCountMap::const_iterator p = counts.begin(); p != counts.end(); ++p)
437 {
438 delete p->first;
439 }
440 return true;
441 }
442 #endif
443