| 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) |