1.. _Reference_Counting:
2
3Reference Counting
4==================
5
6
7.. container:: section
8
9
10   .. rubric:: Problem
11      :class: sectiontitle
12
13   Destroy an object when it will no longer be used.
14
15
16.. container:: section
17
18
19   .. rubric:: Context
20      :class: sectiontitle
21
22   Often it is desirable to destroy an object when it is known that it
23   will not be used in the future. Reference counting is a common serial
24   solution that extends to parallel programming if done carefully.
25
26
27.. container:: section
28
29
30   .. rubric:: Forces
31      :class: sectiontitle
32
33   -  If there are cycles of references, basic reference counting is
34      insufficient unless the cycle is explicitly broken.
35
36
37   -  Atomic counting is relatively expensive in hardware.
38
39
40.. container:: section
41
42
43   .. rubric:: Solution
44      :class: sectiontitle
45
46   Thread-safe reference counting is like serial reference counting,
47   except that the increment/decrement is done atomically, and the
48   decrement and test "count is zero?" must act as a single atomic
49   operation. The following example uses ``std::atomic<int>`` to achieve
50   this.
51
52
53   ::
54
55
56      template<typename T>
57      class counted {
58         std::atomic<int> my_count;
59         T value;
60      public:
61         // Construct object with a single reference to it.
62         counted() {my_count=1;}
63         // Add reference
64         void add_ref() {++my_count;}
65         // Remove reference. Return true if it was the last reference.
66         bool remove_ref() {return --my_count==0;}
67         // Get reference to underlying object
68         T& get() {
69             assert(my_count>0);
70             return my_value;
71         }
72      };
73
74
75   It is incorrect to use a separate read for testing if the count is
76   zero. The following code would be an incorrect implementation of
77   method ``remove_ref``\ () because two threads might both execute the
78   decrement, and then both read ``my_count`` as zero. Hence two callers
79   would both be told incorrectly that they had removed the last
80   reference.
81
82
83   ::
84
85
86            --my_count;
87            return my_count==0. // WRONG!
88
89
90   The decrement may need to have a *release* fence so that any pending
91   writes complete before the object is deleted.
92
93
94   There is no simple way to atomically copy a pointer and increment its
95   reference count, because there will be a timing hole between the
96   copying and the increment where the reference count is too low, and
97   thus another thread might decrement the count to zero and delete the
98   object. Two ways to address the problem are "hazard pointers" and
99   "pass the buck". See the references below for details.
100
101
102.. container:: section
103
104
105   .. rubric:: Variations
106      :class: sectiontitle
107
108   Atomic increment/decrement can be more than an order of magnitude
109   more expensive than ordinary increment/decrement. The serial
110   optimization of eliminating redundant increment/decrement operations
111   becomes more important with atomic reference counts.
112
113
114   Weighted reference counting can be used to reduce costs if the
115   pointers are unshared but the referent is shared. Associate a
116   *weight* with each pointer. The reference count is the sum of the
117   weights. A pointer ``x`` can be copied as a pointer ``x'`` without
118   updating the reference count by splitting the original weight between
119   ``x`` and ``x'``. If the weight of ``x`` is too low to split, then first add a
120   constant W to the reference count and weight of ``x``.
121
122
123.. container:: section
124
125
126   .. rubric:: References
127      :class: sectiontitle
128
129   D. Bacon and V.T. Rajan, "Concurrent Cycle Collection in Reference
130   Counted Systems" in Proc. European Conf. on Object-Oriented
131   Programming (June 2001). Describes a garbage collector based on
132   reference counting that does collect cycles.
133
134
135   M. Michael, "Hazard Pointers: Safe Memory Reclamation for Lock-Free
136   Objects" in IEEE Transactions on Parallel and Distributed Systems
137   (June 2004). Describes the "hazard pointer" technique.
138
139
140   M. Herlihy, V. Luchangco, and M. Moir, "The Repeat Offender Problem:
141   A Mechanism for Supporting Dynamic-Sized, Lock-Free Data Structures"
142   in Proceedings of the 16th International Symposium on Distributed
143   Computing (Oct. 2002). Describes the "pass the buck" technique.
144
145