From e7b68776474003337fc6f733983e175952f154f7 Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=A9mie=20Galarneau?= Date: Mon, 23 Nov 2015 18:25:38 -0500 Subject: [PATCH] Docs: Document reference counting scheme implemented by Object MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Signed-off-by: Jérémie Galarneau --- configure.ac | 1 + doc/Makefile.am | 4 +- doc/images/Makefile.am | 4 + doc/images/bt-ref01.svg | 3 + doc/images/bt-ref02.svg | 3 + doc/images/bt-ref03.svg | 3 + doc/images/bt-ref04.svg | 3 + doc/images/bt-ref05.svg | 3 + doc/images/bt-ref06.svg | 3 + doc/images/bt-ref07.svg | 3 + doc/images/bt-ref08.svg | 3 + doc/images/bt-ref09.svg | 3 + doc/images/bt-ref10.svg | 3 + doc/images/bt-ref11.svg | 3 + doc/images/bt-ref12.svg | 3 + doc/images/bt-ref13.svg | 3 + doc/ref-counting.md | 195 ++++++++++++++++++++++++++++++++++++++++ 17 files changed, 241 insertions(+), 2 deletions(-) create mode 100644 doc/images/Makefile.am create mode 100644 doc/images/bt-ref01.svg create mode 100644 doc/images/bt-ref02.svg create mode 100644 doc/images/bt-ref03.svg create mode 100644 doc/images/bt-ref04.svg create mode 100644 doc/images/bt-ref05.svg create mode 100644 doc/images/bt-ref06.svg create mode 100644 doc/images/bt-ref07.svg create mode 100644 doc/images/bt-ref08.svg create mode 100644 doc/images/bt-ref09.svg create mode 100644 doc/images/bt-ref10.svg create mode 100644 doc/images/bt-ref11.svg create mode 100644 doc/images/bt-ref12.svg create mode 100644 doc/images/bt-ref13.svg create mode 100644 doc/ref-counting.md diff --git a/configure.ac b/configure.ac index f23e460b..a6be4783 100644 --- a/configure.ac +++ b/configure.ac @@ -304,6 +304,7 @@ AC_CONFIG_FILES([ doc/Makefile doc/bindings/Makefile doc/bindings/python/Makefile + doc/images/Makefile lib/Makefile lib/prio_heap/Makefile include/Makefile diff --git a/doc/Makefile.am b/doc/Makefile.am index f32a4dd2..0ef5e20e 100644 --- a/doc/Makefile.am +++ b/doc/Makefile.am @@ -1,7 +1,7 @@ -SUBDIRS = bindings +SUBDIRS = bindings images dist_man_MANS = babeltrace.1 babeltrace-log.1 -dist_doc_DATA = API.txt lttng-live.txt +dist_doc_DATA = API.txt lttng-live.txt ref-counting.md EXTRA_DIST = development.txt diff --git a/doc/images/Makefile.am b/doc/images/Makefile.am new file mode 100644 index 00000000..05d138b8 --- /dev/null +++ b/doc/images/Makefile.am @@ -0,0 +1,4 @@ +dist_doc_DATA = bt-ref01.svg bt-ref02.svg bt-ref03.svg bt-ref04.svg \ + bt-ref05.svg bt-ref06.svg bt-ref07.svg bt-ref08.svg \ + bt-ref09.svg bt-ref10.svg bt-ref11.svg bt-ref12.svg \ + bt-ref13.svg diff --git a/doc/images/bt-ref01.svg b/doc/images/bt-ref01.svg new file mode 100644 index 00000000..7291f2c0 --- /dev/null +++ b/doc/images/bt-ref01.svg @@ -0,0 +1,3 @@ + + +
TC1
[Not supported by viewer]
SC1
[Not supported by viewer]
SC2
[Not supported by viewer]
EC1
[Not supported by viewer]
EC2
[Not supported by viewer]
EC3
[Not supported by viewer]
1
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer]
User A
[Not supported by viewer] \ No newline at end of file diff --git a/doc/images/bt-ref02.svg b/doc/images/bt-ref02.svg new file mode 100644 index 00000000..da1eb735 --- /dev/null +++ b/doc/images/bt-ref02.svg @@ -0,0 +1,3 @@ + + +
TC1
[Not supported by viewer]
SC1
[Not supported by viewer]
SC2
[Not supported by viewer]
EC1
[Not supported by viewer]
EC2
[Not supported by viewer]
EC3
[Not supported by viewer]
2
[Not supported by viewer]
1
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer]
User A
[Not supported by viewer] \ No newline at end of file diff --git a/doc/images/bt-ref03.svg b/doc/images/bt-ref03.svg new file mode 100644 index 00000000..12f8a14c --- /dev/null +++ b/doc/images/bt-ref03.svg @@ -0,0 +1,3 @@ + + +
TC1
[Not supported by viewer]
SC1
[Not supported by viewer]
SC2
[Not supported by viewer]
EC1
[Not supported by viewer]
EC2
[Not supported by viewer]
EC3
[Not supported by viewer]
2
[Not supported by viewer]
2
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer]
1
[Not supported by viewer]
User A
[Not supported by viewer] \ No newline at end of file diff --git a/doc/images/bt-ref04.svg b/doc/images/bt-ref04.svg new file mode 100644 index 00000000..10ada1d1 --- /dev/null +++ b/doc/images/bt-ref04.svg @@ -0,0 +1,3 @@ + + +
TC1
[Not supported by viewer]
SC1
[Not supported by viewer]
SC2
[Not supported by viewer]
EC1
[Not supported by viewer]
EC2
[Not supported by viewer]
EC3
[Not supported by viewer]
2
[Not supported by viewer]
1
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer]
1
[Not supported by viewer]
User A
[Not supported by viewer] \ No newline at end of file diff --git a/doc/images/bt-ref05.svg b/doc/images/bt-ref05.svg new file mode 100644 index 00000000..d14a01c5 --- /dev/null +++ b/doc/images/bt-ref05.svg @@ -0,0 +1,3 @@ + + +
TC1
[Not supported by viewer]
SC1
[Not supported by viewer]
SC2
[Not supported by viewer]
EC1
[Not supported by viewer]
EC2
[Not supported by viewer]
EC3
[Not supported by viewer]
1
[Not supported by viewer]
1
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer]
1
[Not supported by viewer]
User A
[Not supported by viewer] \ No newline at end of file diff --git a/doc/images/bt-ref06.svg b/doc/images/bt-ref06.svg new file mode 100644 index 00000000..4f8328f7 --- /dev/null +++ b/doc/images/bt-ref06.svg @@ -0,0 +1,3 @@ + + +
TC1
[Not supported by viewer]
SC1
[Not supported by viewer]
SC2
[Not supported by viewer]
EC1
[Not supported by viewer]
EC2
[Not supported by viewer]
EC3
[Not supported by viewer]
2
[Not supported by viewer]
1
[Not supported by viewer]
1
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer]
1
[Not supported by viewer]
User A
[Not supported by viewer]
User B
[Not supported by viewer] \ No newline at end of file diff --git a/doc/images/bt-ref07.svg b/doc/images/bt-ref07.svg new file mode 100644 index 00000000..e6674a1c --- /dev/null +++ b/doc/images/bt-ref07.svg @@ -0,0 +1,3 @@ + + +
TC1
[Not supported by viewer]
SC1
[Not supported by viewer]
SC2
[Not supported by viewer]
EC1
[Not supported by viewer]
EC2
[Not supported by viewer]
EC3
[Not supported by viewer]
2
[Not supported by viewer]
1
[Not supported by viewer]
2
[Not supported by viewer]
0
[Not supported by viewer]
1
[Not supported by viewer]
1
[Not supported by viewer]
User A
[Not supported by viewer]
User B
[Not supported by viewer]
User C
[Not supported by viewer] \ No newline at end of file diff --git a/doc/images/bt-ref08.svg b/doc/images/bt-ref08.svg new file mode 100644 index 00000000..e813cee6 --- /dev/null +++ b/doc/images/bt-ref08.svg @@ -0,0 +1,3 @@ + + +
TC1
[Not supported by viewer]
SC1
[Not supported by viewer]
SC2
[Not supported by viewer]
EC1
[Not supported by viewer]
EC2
[Not supported by viewer]
EC3
[Not supported by viewer]
1
[Not supported by viewer]
0
[Not supported by viewer]
2
[Not supported by viewer]
0
[Not supported by viewer]
1
[Not supported by viewer]
0
[Not supported by viewer]
User B
[Not supported by viewer]
User C
[Not supported by viewer] \ No newline at end of file diff --git a/doc/images/bt-ref09.svg b/doc/images/bt-ref09.svg new file mode 100644 index 00000000..98a7ad4a --- /dev/null +++ b/doc/images/bt-ref09.svg @@ -0,0 +1,3 @@ + + +
TC1
[Not supported by viewer]
SC1
[Not supported by viewer]
SC2
[Not supported by viewer]
EC1
[Not supported by viewer]
EC2
[Not supported by viewer]
EC3
[Not supported by viewer]
1
[Not supported by viewer]
0
[Not supported by viewer]
1
[Not supported by viewer]
0
[Not supported by viewer]
1
[Not supported by viewer]
0
[Not supported by viewer]
User C
[Not supported by viewer] \ No newline at end of file diff --git a/doc/images/bt-ref10.svg b/doc/images/bt-ref10.svg new file mode 100644 index 00000000..5bad3555 --- /dev/null +++ b/doc/images/bt-ref10.svg @@ -0,0 +1,3 @@ + + +
TC1
[Not supported by viewer]
SC1
[Not supported by viewer]
SC2
[Not supported by viewer]
EC1
[Not supported by viewer]
EC2
[Not supported by viewer]
EC3
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer] \ No newline at end of file diff --git a/doc/images/bt-ref11.svg b/doc/images/bt-ref11.svg new file mode 100644 index 00000000..e10a6e95 --- /dev/null +++ b/doc/images/bt-ref11.svg @@ -0,0 +1,3 @@ + + +
TC1
[Not supported by viewer]
SC1
[Not supported by viewer]
SC2
[Not supported by viewer]
EC1
[Not supported by viewer]
EC2
[Not supported by viewer]
EC3
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer] \ No newline at end of file diff --git a/doc/images/bt-ref12.svg b/doc/images/bt-ref12.svg new file mode 100644 index 00000000..b6f6b89a --- /dev/null +++ b/doc/images/bt-ref12.svg @@ -0,0 +1,3 @@ + + +
TC1
[Not supported by viewer]
SC1
[Not supported by viewer]
SC2
[Not supported by viewer]
EC1
[Not supported by viewer]
EC2
[Not supported by viewer]
EC3
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer] \ No newline at end of file diff --git a/doc/images/bt-ref13.svg b/doc/images/bt-ref13.svg new file mode 100644 index 00000000..de88b298 --- /dev/null +++ b/doc/images/bt-ref13.svg @@ -0,0 +1,3 @@ + + +
TC1
[Not supported by viewer]
SC1
[Not supported by viewer]
SC2
[Not supported by viewer]
EC1
[Not supported by viewer]
EC2
[Not supported by viewer]
EC3
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer]
0
[Not supported by viewer] \ No newline at end of file diff --git a/doc/ref-counting.md b/doc/ref-counting.md new file mode 100644 index 00000000..32b86085 --- /dev/null +++ b/doc/ref-counting.md @@ -0,0 +1,195 @@ +# Babeltrace Object Reference Counting and Lifetime + +This document covers the rationale behind the design of Babeltrace's object +lifetime management. + +Starting from Babeltrace 2.x, all publicly exposed objects inherit a common +base: bt_object. This base provides a number of facilities to all objects, chief +amongst which are lifetime management functions. + +The reference count of all public objects is controlled by invoking +the `bt_get()` and `bt_put()` functions which respectively +increment and decrement an object's reference count. + +As far as lifetime management in concerned, Babeltrace makes a clear +distinction between regular objects, which have a single parent, and root +objects, which don't. + +## The Problem + +Let us consider a problematic case to illustrate the need for this +distinction. + +A user of the CTF Writer library declares a Trace, which *has* a +Stream Class (the declaration of a stream) and that Stream Class, in +turn, *has* an Event Class (the declaration of an event). + +Nothing prevents this user from releasing his reference on any one of +these objects in any order. However, all objects in the "Trace <-> +Stream <-> Event" hierarchy can be retrieved from any other. + +For instance, the user could discard his reference on both the Event +Class and the Stream Class, only keeping a reference on the Trace. +From this Trace reference, Stream Classes can be enumerated, providing +the user with a new reference to the Stream Class he discarded +earlier. Event Classes can also be enumerated from Stream Classes, +providing the user with references to the individual Event Classes. + +Conversely, the user could also hold a reference to an Event Class and +retrieve its parent Stream Class. The Trace, in turn, can then be +retrieved from the Stream Class. + +This example illustrates what could be interpreted as a circular +reference dependency existing between these objects. Of course, if the +objects in such a scenario were to hold references to each other (in +both directions), we would be in presence of a circular ownership +resulting in a leak of both objects as their reference counts would +never reach zero. + +Nonetheless, the API must offer the guarantee that holding a node to any node of +the graph keeps all other reachable nodes alive. + +## The Solution + +The scheme employed in Babeltrace to break this cycle consists in the +"children" holding *Reverse Component References* to their parents. That +is, in the context of CTF-IR, that Event Classes hold a reference to +their Stream Class and Stream Classes hold a reference to their Trace. + +On the other hand, parents hold *Claiming Aggregation References* to +their children. A claiming aggregation reference means that the +object being referenced should not be deleted as long as the reference +still exists. In this respect, it can be said that parents truly hold the +ownership of their children, since they control their lifetime. Conversely, +the reference counting mechanism is leveraged by children to notify parents +that no other child indirectly exposes the parent. + +When a parented object's reference count reaches zero, it invokes +`bt_put()` on its parent and does **not** free itself. However, from that +point, the object depends on its parent to signal the moment when it +can be safely reclaimed. + +The invocation of `bt_put()` by the last children holding a reference to its +parent might trigger a cascade of `bt_put()` from child to parent. Eventually, +a **root** object is reached. At that point, if this orphaned object's +reference count reaches zero, the object will invoke the `destroy()` method +defined by every one of its children as part of their base `struct bt_object`. +The key point here is that the cascade of `destroy()` will necessarily originate +from the root and propagate in pre-order to the children. These children will +propagate the destruction to their own children before reclaiming their own +memory. This ensures that a node's pointer to its parent is *always* valid +since the parent has the responsibility of tearing-down their children before +cleaning themselves-up. + +Assuming a reference to an object is *acquired* by calling `bt_get()` while its +reference count is zero, the object will, in turn, acquire a reference on its +parent using `bt_get()`. At that point, the child can be thought of as having +converted its weak reference to its parent into a regular reference. That is +why this reference is referred to as a *claiming* aggregation reference. + +## Caveats + +This scheme imposes a number of strict rules defining the relation +between objects: + + * Objects may only have one parent, + * Objects, beside the root, are only retrievable from their direct parent or + children. + +## Walking through an example + +The initial situation is rather simple. **User A** is holding a reference to a +trace, **TC1**. As per the rules previously enounced, Stream Classes **SC1** and +**SC2** don't hold a reference to **TC1** since their own reference counts are +zero. The same holds true for **EC1**, **EC2** and **EC3** with respect to +**SC1** and **SC2**. + +![](images/bt-ref01.svg) + +In this second step, we can see that User A has acquired a reference on **SC2** +through the Trace, **TC1**. + +The Stream Class' reference count transitions from zero to one, triggering the +acquisition of a strong reference on **TC1** from **SC2**. + +Hence, at this point, the Trace's ownership is shared by **User A** and +**SC2**. + +![](images/bt-ref02.svg) + +Next, **User A** acquires a reference on the **EC3** Event Class through its +parent Stream Class, **SC2**. Again, the transition of an object's reference +count from 0 to 1 triggers the acquisition of a reference on its parent. + +Note that SC2's reference count was incremented to 2. The Trace's reference +count remains unchanged. + +![](images/bt-ref03.svg) + +**User A** decides to drop its reference on **SC2**. **SC2**'s reference count +returns back to 1, everything else remaining unchanged. + +![](images/bt-ref04.svg) + +**User A** can then decide to drop its reference on the Trace. This results in +a reversal of the initial situation: **User A** now owns an event, **EC3**, +which is keeping everything else alive and reachable. + +![](images/bt-ref05.svg) + +If another object, **User B**, enters the picture and acquires a reference on +the **SC1** Stream Class, we see that **SC1**'s reference count +transitioned from 0 to 1, triggering the acquisition of a reference on **TC1**. + +![](images/bt-ref06.svg) + +**User B** hands off a reference to **EC1**, acquired through **SC1**, to +another object, **User C**. The acquisition of a reference on **EC1**, which +transitions from 0 to 1, triggers the acquisition of a reference on its parent, +**SC1**. + +![](images/bt-ref07.svg) + +At some point, **User A** releases its reference on **EC3**. Since **EC3**'s +reference count transitions to zero, it releases its reference on **SC2**. +**SC2**'s reference count, in turn, reaches zero and it releases its reference +to **TC1**. + +**TC1**'s reference count is now 1 and no further action is taken. + +![](images/bt-ref08.svg) + +**User B** releases its reference on **SC1**. **User C** becomes the sole owner +of the whole hierarchy through his ownership of **EC1**. + +![](images/bt-ref09.svg) + +Finally, **User C** releases his ownership of **EC1**, triggering the release of +the whole hierarchy. We will walk through the reclamation of the whole graph. + +Mirroring what happened when **User A** released its last reference on **EC3**, +the release of **EC1** by **User C** causes its reference count to fall to zero. + +This transition to zero causes **EC1** to release its reference on **SC1**. +**SC1**'s reference count reaching zero causes it to release its reference on +**TC1**. + +![](images/bt-ref10.svg) + +Since the reference count of **TC1**, a root object, has reached zero, it +invokes the `destroy()` method on its children. This method is recursive and +causes the Stream Classes to call the `destroy()` method on their Event Classes. + +The Event Classes are reached and, having no children of their own, are +reclaimed. + +![](images/bt-ref11.svg) + +The Stream Classes having destroyed their children, are then reclaimed by the +Trace. + +![](images/bt-ref12.svg) + +Finally, the Stream Classes having been reclaimed, **TC1** is reclaimed. + +![](images/bt-ref13.svg) -- 2.34.1