1 /**
2  * [Source](https://raw.githubusercontent.com/schveiguy/iopipe/makesafe/source/iopipe/refc.d).
3  *
4  * Reference counting using the GC.
5  *
6  * The RefCounted struct simply stores the item in a GC block, and also adds a
7  * root to that block. Once all known references to the block are removed
8  * (tracked by a reference count in the block), then the block is removed, and
9  * the destructor run. Since it's a root, it can run the full destructor of the
10  * data underneath, without worrying about GC data being collected underneath
11  * it.
12  *
13  * This depends on the block not being involved in a cycle, which should be
14  * fine for iopipes.
15  *
16  * Note that atomics are used for the reference count because the GC can
17  * destroy things in other threads.
18  */
19 module my.gc.refc;
20 
21 import core.atomic : atomicOp, atomicLoad, atomicStore, cas;
22 import core.memory : GC;
23 import std.algorithm : move, swap;
24 
25 /**
26  * The "use count" is the number of shared_ptr instances pointing to the
27  * object.
28  * The "weak count" is the number of weak_ptr instances pointing to the object,
29  * plus one if the "use count" is still > 0.
30  */
31 private struct ControlBlock(T) {
32     T item;
33     /// Number of RefCounted instances.
34     shared int useCnt = 1;
35     /// Number of weak references. +1 if useCnt isn't zero.
36     shared int weakCnt = 1;
37 
38     this(ref T item_) {
39         item = move(item_);
40     }
41 
42     this(Args...)(auto ref Args args) {
43         item = T(args);
44     }
45 }
46 
47 private void incrUseCnt(T)(ref T cb) nothrow {
48     cb.useCnt.atomicOp!"+="(1);
49 }
50 
51 private void releaseUseCnt(T)(ref T cb)
52 in (cb.useCnt >= 0, "Invalid count detected") {
53     if (cb.useCnt.atomicOp!"-="(1) == 0) {
54         if (!GC.inFinalizer)
55             destroy(cb.item);
56         releaseWeakCnt(cb);
57     }
58 }
59 
60 private void incrWeakCnt(T)(ref T cb) nothrow {
61     cb.weakCnt.atomicOp!"+="(1);
62 }
63 
64 private void releaseWeakCnt(T)(ref T cb) @trusted
65 in (cb.weakCnt >= 0, "Invalid count detected") {
66     if (cb.weakCnt.atomicOp!"-="(1) == 0) {
67         GC.removeRoot(cb);
68     }
69 }
70 
71 /** `RefCounted` is a smart pointer that retains shared ownership of an object
72  * through a pointer. Several `RefCounted` objects may own the same object. The
73  * object is destroyed and its memory deallocated when either of the following
74  * happens:
75  *
76  *  * the last remaining `RefCounted` owning the object is destroyed;
77  *  * the last remaining `RefCounted` owning the object is assigned another
78  *    pointer via `opAssign` or `release()`.
79  *
80  * The object is destroyed using the objects destructor.
81  *
82  * A `RefCounted` may also own no objects, in which case it is called empty and
83  * `isNull()` returns true.
84  *
85  * All member functions can be called by multiple threads on different
86  * instances of shared_ptr without additional synchronization even if these
87  * instances are copies and share ownership of the same object. If multiple
88  * threads of execution access the same shared_ptr without synchronization and
89  * any of those accesses uses a non-const member function of shared_ptr then a
90  * data race will occur; the shared_ptr overloads of atomic functions can be
91  * used to prevent the data race.
92  */
93 struct RefCounted(T) {
94     import std.conv : emplace;
95 
96     alias Impl = ControlBlock!T;
97     private Impl* impl;
98 
99     this(Impl* impl) {
100         this.impl = impl;
101     }
102 
103     this(Args...)(auto ref Args args) {
104         impl = alloc();
105         () @trusted {
106             scope (failure)
107                 GC.removeRoot(impl);
108             emplace(impl, args);
109         }();
110     }
111 
112     this(this) {
113         if (impl)
114             incrUseCnt(impl);
115     }
116 
117     ~this() {
118         if (impl)
119             releaseUseCnt(impl);
120         impl = null;
121     }
122 
123     /// Set impl to an allocated block of data. It is uninitialized.
124     private static Impl* alloc() @trusted {
125         // need to use untyped memory, so we don't get a dtor call by the GC.
126         import std.traits : hasIndirections;
127 
128         static if (hasIndirections!T) {
129             auto rawMem = new void[Impl.sizeof];
130             GC.addRoot(rawMem.ptr);
131         } else {
132             auto rawMem = new ubyte[Impl.sizeof];
133         }
134 
135         auto rval = cast(Impl*) rawMem.ptr;
136         rval.useCnt = 1;
137         rval.weakCnt = 1;
138         return rval;
139     }
140 
141     private inout(T*) item() inout @trusted
142     in (impl !is null, "not initialized") {
143         return cast(inout(T*)) impl;
144     }
145 
146     /// Returns: pointer to the item or null.
147     inout(T*) ptr() inout return {
148         return item;
149     }
150 
151     ref inout(T) get() inout
152     in (item !is null, "Invalid refcounted access") {
153         return *item;
154     }
155 
156     // creates forwarding problem but is convenient.
157     //alias get this;
158 
159     size_t toHash() @safe pure nothrow const @nogc scope {
160         return cast(size_t) impl;
161     }
162 
163     void opAssign(RefCounted other) {
164         swap(impl, other.impl);
165     }
166 
167     void opAssign(T other) {
168         if (empty)
169             impl = alloc;
170         move(other, impl.item);
171     }
172 
173     /// Release the reference.
174     void release() {
175         if (impl) {
176             releaseUseCnt(impl);
177             impl = null;
178         }
179     }
180 
181     /// The number of references.
182     int refCount() @safe pure nothrow const @nogc {
183         if (impl) {
184             return atomicLoad(impl.useCnt);
185         }
186         return 0;
187     }
188 
189     bool empty() @safe pure nothrow const @nogc {
190         return impl is null;
191     }
192 
193     T opCast(T : bool)() @safe pure nothrow const @nogc {
194         return !empty;
195     }
196 
197     WeakRef!T weakRef() {
198         return WeakRef!T(this);
199     }
200 }
201 
202 RefCounted!T refCounted(T)(auto ref T item) {
203     return RefCounted!T(item);
204 }
205 
206 @("shall call the destructor when the last ref is destroyed")
207 @safe unittest {
208     size_t dtorcalled = 0;
209     struct S {
210         int x;
211         @safe ~this() {
212             if (x)
213                 dtorcalled++;
214         }
215 
216         @disable this(this);
217     }
218 
219     {
220         auto destroyme = S(1).refCounted;
221         auto dm2 = destroyme;
222         auto dm3 = destroyme;
223         assert(destroyme.refCount == 3);
224         assert(dm2.refCount == 3);
225         assert(dm3.refCount == 3);
226     }
227 
228     assert(dtorcalled == 1);
229 }
230 
231 /** `WeakRef` is a smart pointer that holds a non-owning ("weak") reference to
232  * an object that is managed by `RefCounted`. It must be converted to a
233  * `RefCounted` via `asRefCounted()` in order to access the referenced object.
234  *
235  * `WeakRef` models temporary ownership: when an object needs to be accessed
236  * only if it exists, and it may be deleted at any time by someone else,
237  * `WeakRef` is used to track the object, and it is converted to `RefCounted`
238  * to assume temporary ownership. If the original `RefCounted` is destroyed at
239  * this time, the object's lifetime is extended until the temporary
240  * `RefCounted` is destroyed as well.
241  *
242  * Another use for `WeakRef` is to break reference cycles formed by objects
243  * managed by `RefCounted`. if such cycle is orphaned (i.e. there are no
244  * outside shared pointers into the cycle), the `RefCounted` reference counts
245  * cannot reach zero and the memory is leaked. To prevent this, one of the
246  * pointers in the cycle can be made weak.
247  */
248 struct WeakRef(T) {
249     alias Impl = ControlBlock!T;
250     private Impl* impl;
251 
252     this(RefCounted!(T) r) {
253         if (r.empty)
254             return;
255 
256         incrWeakCnt(r.impl);
257         impl = r.impl;
258     }
259 
260     this(ref RefCounted!(T) r) {
261         if (r.empty)
262             return;
263 
264         incrWeakCnt(r.impl);
265         impl = r.impl;
266     }
267 
268     this(this) {
269         if (impl)
270             incrWeakCnt(impl);
271     }
272 
273     ~this() @safe {
274         if (impl)
275             releaseWeakCnt(impl);
276         impl = null;
277     }
278 
279     size_t toHash() @safe pure nothrow const @nogc scope {
280         return cast(size_t) impl;
281     }
282 
283     void opAssign(WeakRef other) @safe nothrow {
284         swap(impl, other.impl);
285     }
286 
287     RefCounted!(T) asRefCounted() nothrow {
288         if (impl is null) {
289             return typeof(return).init;
290         }
291 
292         auto useCnt = atomicLoad(impl.useCnt);
293         if (useCnt == 0)
294             return typeof(return).init;
295 
296         cas(&impl.useCnt, useCnt, useCnt + 1);
297         return typeof(return)(impl);
298     }
299 
300     /// Release the reference.
301     void release() @safe nothrow @nogc {
302         if (impl) {
303             releaseWeakCnt(impl);
304             impl = null;
305         }
306     }
307 
308     /** If the `WeakRef` reference a `RefCounted`.
309      *
310      * This only mean that `asRefCounted` can be used to try and get the data.
311      * No guarantee that it will succeed.
312      */
313     bool empty() @safe pure nothrow const @nogc {
314         return impl is null;
315     }
316 
317     T opCast(T : bool)() @safe pure nothrow const @nogc {
318         return !empty;
319     }
320 }
321 
322 @("shall only call the destructor one time")
323 @safe unittest {
324     size_t dtorcalled = 0;
325     struct S {
326         int x;
327         @safe ~this() {
328             if (x)
329                 dtorcalled++;
330         }
331 
332         @disable this(this);
333     }
334 
335     {
336         auto rc1 = S(1).refCounted;
337         assert(rc1.refCount == 1);
338         assert(rc1.impl.weakCnt == 1);
339         auto rc2 = rc1;
340         assert(rc2.refCount == 2);
341         assert(rc2.impl.weakCnt == 1);
342 
343         auto wrc1 = rc1.weakRef;
344         assert(wrc1.impl.useCnt == 2);
345         assert(wrc1.impl.weakCnt == 2);
346     }
347 
348     assert(dtorcalled == 1);
349 }
350 
351 @("shall destroy the object even though there are cycles because they are WeakRef")
352 @safe unittest {
353     size_t dtorcalled = 0;
354     struct S {
355         int x;
356         WeakRef!(typeof(this)) other;
357 
358         @safe ~this() {
359             if (x)
360                 dtorcalled++;
361         }
362 
363         @disable this(this);
364     }
365 
366     {
367         auto rc1 = S(1).refCounted;
368         auto rc2 = S(2).refCounted;
369 
370         rc1.get.other = rc2.weakRef;
371         rc2.get.other = rc1.weakRef;
372 
373         assert(rc1.impl.useCnt == 1);
374         assert(rc1.impl.weakCnt == 2);
375         assert(rc2.impl.useCnt == 1);
376         assert(rc2.impl.weakCnt == 2);
377     }
378 
379     assert(dtorcalled == 2);
380 }
381 
382 @("shall ref count an object stored in a Variant")
383 @system unittest {
384     import std.variant : Variant;
385     import std.typecons : tuple, Tuple;
386 
387     static struct S {
388         int x;
389     }
390 
391     auto rc = S(42).refCounted;
392 
393     {
394         Variant obj;
395 
396         obj = rc;
397         assert(rc.refCount == 2, "count incr when stored");
398 
399         obj = 42;
400         assert(rc.refCount == 1, "count decrease when obj is destroyed");
401 
402         {
403             obj = rc.weakRef;
404             assert(rc.refCount == 1, "the use count did not change");
405             assert(rc.impl.weakCnt == 2, "weak count incr");
406         }
407 
408         { // lets get the object back via the weak ref
409             auto tmpRef = obj.get!(WeakRef!S);
410             assert(rc.impl.weakCnt == 3);
411             auto tmpRc = tmpRef.asRefCounted;
412             assert(tmpRc.get.x == 42);
413         }
414         assert(rc.impl.weakCnt == 2);
415     }
416 
417     assert(rc.refCount == 1,
418             "when last ref of obj disappears the dtor is called. only one ref left");
419     assert(rc.impl.weakCnt == 1);
420 }
421 
422 @("shall ref count an object stored in nested Variant")
423 @system unittest {
424     import std.variant : Variant;
425     import std.typecons : tuple, Tuple;
426 
427     static struct S {
428         int x;
429     }
430 
431     auto rc = S(42).refCounted;
432 
433     {
434         auto obj = Variant(rc.weakRef);
435         assert(rc.refCount == 1, "the use count did not change");
436         assert(rc.impl.weakCnt == 2, "weak count incr");
437 
438         { // nested Variants call ctor/dtor as expected
439             auto obj2 = Variant(tuple(42, obj));
440             assert(rc.refCount == 1);
441             assert(rc.impl.weakCnt == 3);
442         }
443     }
444 
445     assert(rc.refCount == 1,
446             "when last ref of obj disappears the dtor is called. only one ref left");
447 }