Commit | Line | Data |
---|---|---|
e7b68776 JG |
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) |