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)