Allow a component to remove a port and any user to disconnect one
[babeltrace.git] / doc / ref-counting.md
1 # Babeltrace Object Reference Counting and Lifetime
2
3 This document covers the rationale behind the design of Babeltrace's object
4 lifetime management.
5
6 Starting from Babeltrace 2.x, all publicly exposed objects inherit a common
7 base: bt_object. This base provides a number of facilities to all objects, chief
8 amongst which are lifetime management functions.
9
10 The reference count of all public objects is controlled by invoking
11 the `bt_get()` and `bt_put()` functions which respectively
12 increment and decrement an object's reference count.
13
14 As far as lifetime management in concerned, Babeltrace makes a clear
15 distinction between regular objects, which have a single parent, and root
16 objects, which don't.
17
18 ## The Problem
19
20 Let us consider a problematic case to illustrate the need for this
21 distinction.
22
23 A user of the CTF Writer library declares a Trace, which *has* a
24 Stream Class (the declaration of a stream) and that Stream Class, in
25 turn, *has* an Event Class (the declaration of an event).
26
27 Nothing prevents this user from releasing his reference on any one of
28 these objects in any order. However, all objects in the "Trace <->
29 Stream <-> Event" hierarchy can be retrieved from any other.
30
31 For instance, the user could discard his reference on both the Event
32 Class and the Stream Class, only keeping a reference on the Trace.
33 From this Trace reference, Stream Classes can be enumerated, providing
34 the user with a new reference to the Stream Class he discarded
35 earlier. Event Classes can also be enumerated from Stream Classes,
36 providing the user with references to the individual Event Classes.
37
38 Conversely, the user could also hold a reference to an Event Class and
39 retrieve its parent Stream Class. The Trace, in turn, can then be
40 retrieved from the Stream Class.
41
42 This example illustrates what could be interpreted as a circular
43 reference dependency existing between these objects. Of course, if the
44 objects in such a scenario were to hold references to each other (in
45 both directions), we would be in presence of a circular ownership
46 resulting in a leak of both objects as their reference counts would
47 never reach zero.
48
49 Nonetheless, the API must offer the guarantee that holding a node to any node of
50 the graph keeps all other reachable nodes alive.
51
52 ## The Solution
53
54 The scheme employed in Babeltrace to break this cycle consists in the
55 "children" holding *Reverse Component References* to their parents. That
56 is, in the context of CTF-IR, that Event Classes hold a reference to
57 their Stream Class and Stream Classes hold a reference to their Trace.
58
59 On the other hand, parents hold *Claiming Aggregation References* to
60 their children. A claiming aggregation reference means that the
61 object being referenced should not be deleted as long as the reference
62 still exists. In this respect, it can be said that parents truly hold the
63 ownership of their children, since they control their lifetime. Conversely,
64 the reference counting mechanism is leveraged by children to notify parents
65 that no other child indirectly exposes the parent.
66
67 When a parented object's reference count reaches zero, it invokes
68 `bt_put()` on its parent and does **not** free itself. However, from that
69 point, the object depends on its parent to signal the moment when it
70 can be safely reclaimed.
71
72 The invocation of `bt_put()` by the last children holding a reference to its
73 parent might trigger a cascade of `bt_put()` from child to parent. Eventually,
74 a **root** object is reached. At that point, if this orphaned object's
75 reference count reaches zero, the object will invoke the `destroy()` method
76 defined by every one of its children as part of their base `struct bt_object`.
77 The key point here is that the cascade of `destroy()` will necessarily originate
78 from the root and propagate in pre-order to the children. These children will
79 propagate the destruction to their own children before reclaiming their own
80 memory. This ensures that a node's pointer to its parent is *always* valid
81 since the parent has the responsibility of tearing-down their children before
82 cleaning themselves-up.
83
84 Assuming a reference to an object is *acquired* by calling `bt_get()` while its
85 reference count is zero, the object will, in turn, acquire a reference on its
86 parent using `bt_get()`. At that point, the child can be thought of as having
87 converted its weak reference to its parent into a regular reference. That is
88 why this reference is referred to as a *claiming* aggregation reference.
89
90 ## Caveats
91
92 This scheme imposes a number of strict rules defining the relation
93 between objects:
94
95 * Objects may only have one parent,
96 * Objects, beside the root, are only retrievable from their direct parent or
97 children.
98
99 ## Walking through an example
100
101 The initial situation is rather simple. **User A** is holding a reference to a
102 trace, **TC1**. As per the rules previously enounced, Stream Classes **SC1** and
103 **SC2** don't hold a reference to **TC1** since their own reference counts are
104 zero. The same holds true for **EC1**, **EC2** and **EC3** with respect to
105 **SC1** and **SC2**.
106
107 ![](images/bt-ref01.svg)
108
109 In this second step, we can see that User A has acquired a reference on **SC2**
110 through the Trace, **TC1**.
111
112 The Stream Class' reference count transitions from zero to one, triggering the
113 acquisition of a strong reference on **TC1** from **SC2**.
114
115 Hence, at this point, the Trace's ownership is shared by **User A** and
116 **SC2**.
117
118 ![](images/bt-ref02.svg)
119
120 Next, **User A** acquires a reference on the **EC3** Event Class through its
121 parent Stream Class, **SC2**. Again, the transition of an object's reference
122 count from 0 to 1 triggers the acquisition of a reference on its parent.
123
124 Note that SC2's reference count was incremented to 2. The Trace's reference
125 count remains unchanged.
126
127 ![](images/bt-ref03.svg)
128
129 **User A** decides to drop its reference on **SC2**. **SC2**'s reference count
130 returns back to 1, everything else remaining unchanged.
131
132 ![](images/bt-ref04.svg)
133
134 **User A** can then decide to drop its reference on the Trace. This results in
135 a reversal of the initial situation: **User A** now owns an event, **EC3**,
136 which is keeping everything else alive and reachable.
137
138 ![](images/bt-ref05.svg)
139
140 If another object, **User B**, enters the picture and acquires a reference on
141 the **SC1** Stream Class, we see that **SC1**'s reference count
142 transitioned from 0 to 1, triggering the acquisition of a reference on **TC1**.
143
144 ![](images/bt-ref06.svg)
145
146 **User B** hands off a reference to **EC1**, acquired through **SC1**, to
147 another object, **User C**. The acquisition of a reference on **EC1**, which
148 transitions from 0 to 1, triggers the acquisition of a reference on its parent,
149 **SC1**.
150
151 ![](images/bt-ref07.svg)
152
153 At some point, **User A** releases its reference on **EC3**. Since **EC3**'s
154 reference count transitions to zero, it releases its reference on **SC2**.
155 **SC2**'s reference count, in turn, reaches zero and it releases its reference
156 to **TC1**.
157
158 **TC1**'s reference count is now 1 and no further action is taken.
159
160 ![](images/bt-ref08.svg)
161
162 **User B** releases its reference on **SC1**. **User C** becomes the sole owner
163 of the whole hierarchy through his ownership of **EC1**.
164
165 ![](images/bt-ref09.svg)
166
167 Finally, **User C** releases his ownership of **EC1**, triggering the release of
168 the whole hierarchy. We will walk through the reclamation of the whole graph.
169
170 Mirroring what happened when **User A** released its last reference on **EC3**,
171 the release of **EC1** by **User C** causes its reference count to fall to zero.
172
173 This transition to zero causes **EC1** to release its reference on **SC1**.
174 **SC1**'s reference count reaching zero causes it to release its reference on
175 **TC1**.
176
177 ![](images/bt-ref10.svg)
178
179 Since the reference count of **TC1**, a root object, has reached zero, it
180 invokes the `destroy()` method on its children. This method is recursive and
181 causes the Stream Classes to call the `destroy()` method on their Event Classes.
182
183 The Event Classes are reached and, having no children of their own, are
184 reclaimed.
185
186 ![](images/bt-ref11.svg)
187
188 The Stream Classes having destroyed their children, are then reclaimed by the
189 Trace.
190
191 ![](images/bt-ref12.svg)
192
193 Finally, the Stream Classes having been reclaimed, **TC1** is reclaimed.
194
195 ![](images/bt-ref13.svg)
This page took 0.051072 seconds and 4 git commands to generate.