docs/design/part-relations.txt

   1 Object relation types
   2 ---------------------
   3
   4 This document describes the relations between objects that exist in GStreamer.
   5 It will also describe the way of handling the relation wrt locking and
   6 refcounting.
   7
   8 parent-child relation
   9 ~~~~~~~~~~~~~~~~~~~~~
  10
  11       +---------+    +-------+
  12       | parent  |    | child |
  13  *--->|       *----->|       |
  14       |       F1|<-----*    1|
  15       +---------+    +-------+
  16
  17  - properties
  18
  19    - parent has references to multiple children
  20    - child has reference to parent
  21    - reference fields protected with LOCK
  22    - the reference held by each child to the parent is
  23      NOT reflected in the refcount of the parent.
  24    - the parent removes the floating flag of the child when taking
  25      ownership.
  26    - the application has valid reference to parent
  27    - creation/destruction requires two unnested locks and 1 refcount.
  28
  29  - usage in GStreamer
  30
  31     GstBin -> GstElement
  32     GstElement -> GstRealPad
  33
  34  - lifecycle
  35
  36  a) object creation
  37
  38     The application creates two object and holds a pointer
  39     to them. The objects are initially FLOATING with a refcount
  40     of 1.
  41
  42          +---------+              +-------+
  43     *--->| parent  |         *--->| child |
  44          |       * |              |       |
  45          |       F1|              | *   F1|
  46          +---------+              +-------+
  47
  48  b) establishing the parent-child relationship
  49
  50     The application then calls a method on the parent object to take
  51     ownership of the child object. The parent performs the following
  52     actions:
  53
  54       result = _set_parent (child, parent);
  55       if (result) {
  56         LOCK (parent);
  57         ref_pointer = child;
  58
  59         .. update other data structures ..
  60         UNLOCK (parent);
  61       }
  62       else {
  63         .. child had parent ..
  64       }
  65
  66     The _set_parent() method performs the following actions:
  67
  68       LOCK (child);
  69       if (child->parent != NULL) {
  70         UNLOCK (child);
  71         return FALSE;
  72       }
  73       if (IS_FLOATING (child)) {
  74         UNSET (child, FLOATING);
  75       }
  76       else {
  77         _ref (child);
  78       }
  79       child->parent = parent;
  80       UNLOCK (child);
  81       _signal (PARENT_SET, child, parent);
  82       return TRUE;
  83
  84     The function atomically checks if the child has no parent yet
  85     and will set the parent if not. It will also sink the child, meaning
  86     all floating references to the child are invalid now as it takes
  87     over the refcount of the object.
  88
  89     Visually:
  90
  91       after _set_parent() returns TRUE:
  92
  93           +---------+            +-------+
  94     *---->| parent  |      *-//->| child |
  95           |       * |            |       |
  96           |       F1|<-------------*    1|
  97           +---------+            +-------+
  98
  99       after parent updates ref_pointer to child.
 100
 101           +---------+        +-------+
 102     *---->| parent  |  *-//->| child |
 103           |       *--------->|       |
 104           |       F1|<---------*    1|
 105           +---------+        +-------+
 106
 107    - only one parent is able to _sink the same object because the
 108      _set_parent() method is atomic.
 109    - since only one parent is able to _set_parent() the object, only
 110      one will add a reference to the object.
 111    - since the parent can hold multiple references to children, we don't
 112      need to lock the parent when locking the child. Many threads can
 113      call _set_parent() on the children with the same parent, the parent
 114      can then add all those to its lists.
 115
 116    Note: that the signal is emited before the parent has added the
 117    element to its internal data structures. This is not a problem
 118    since the parent usually has his own signal to inform the app that
 119    the child was reffed. One possible solution would be to update the
 120    internal structure first and then perform a rollback if the _set_parent()
 121    failed. This is not a good solution as iterators might grab the
 122    'half-added' child too soon.
 123
 124  c) using the parent-child relationship
 125
 126     - since the initial floating reference to the child object became
 127       invalid after giving it to the parent, any reference to a child
 128       has at least a refcount > 1.
 129
 130     - this means that unreffing a child object cannot decrease the refcount
 131       to 0. In fact, only the parent can destroy and dispose the child
 132       object.
 133
 134     - given a reference to the child object, the parent pointer is only
 135       valid when holding the child LOCK. Indeed, after unlocking the child
 136       LOCK, the parent can unparent the child or the parent could even become
 137       disposed. To avoid the parent dispose problem, when obtaining the
 138       parent pointer, if should be reffed before releasing the child LOCK.
 139
 140     1) getting a reference to the parent.
 141
 142        - a referece is held to the child, so it cannot be disposed.
 143
 144        LOCK (child);
 145        parent = _ref (child->parent);
 146        UNLOCK (child);
 147
 148        .. use parent ..
 149
 150        _unref (parent);
 151
 152     2) getting a reference to a child
 153
 154        - a reference to a child can be obtained by reffing it before
 155          adding it to the parent or by querying the parent.
 156
 157        - when requesting a child from the parent, a reference is held to
 158          the parent so it cannot be disposed. The parent will use its
 159          internal data structures to locate the child element and will
 160          return a reference to it with an incremented refcount. The
 161          requester should _unref() the child after usage.
 162
 163
 164  d) destroying the parent-child relationship
 165
 166     - only the parent can actively destroy the parent-child relationship
 167       this typically happens when a method is called on the parent to release
 168       ownership of the child.
 169
 170     - a child shall never remove itself from the parent.
 171
 172     - since calling a method on the parent with the child as an argument
 173       requires the caller to obtain a valid reference to the child, the child
 174       refcount is at least > 1.
 175
 176     - the parent will perform the folowing actions:
 177
 178         LOCK (parent);
 179         if (ref_pointer == child) {
 180           ref_pointer = NULL;
 181
 182           .. update other data structures ..
 183           UNLOCK (parent);
 184
 185           _unparent (child);
 186         }
 187         else {
 188           UNLOCK (parent);
 189           .. not our child ..
 190         }
 191
 192     The _unparent() method performs the following actions:
 193
 194       LOCK (child);
 195       if (child->parent != NULL) {
 196         child->parent = NULL;
 197         UNLOCK (child);
 198         _signal (PARENT_UNSET, child, parent);
 199
 200         _unref (child);
 201       }
 202       else {
 203         UNLOCK (child);
 204       }
 205
 206     Since the _unparent() method unrefs the child object, it is possible that
 207     the child pointer is invalid after this function. If the parent wants to
 208     perform other actions on the child (such as signal emmision) it should
 209     _ref() the child first.
 210
 211
 212 single-reffed relation
 213 ~~~~~~~~~~~~~~~~~~~~~~
 214
 215       +---------+        +---------+
 216  *--->| object1 |   *--->| object2 |
 217       |       *--------->|         |
 218       |        1|        |        2|
 219       +---------+        +---------+
 220
 221  - properties
 222
 223    - one object has a reference to another
 224    - reference field protected with LOCK
 225    - the reference held by the object is reflected in the
 226      refcount of the other object.
 227    - typically the other object can be shared among multiple
 228      other objects where each ref is counted for in the
 229      refcount.
 230    - no object has ownership of the other.
 231    - either shared state or copy-on-write.
 232    - creation/destruction requires one lock and one refcount.
 233
 234  - usage
 235
 236     GstRealPad -> GstCaps
 237     GstBuffer -> GstCaps
 238     GstEvent -> GstCaps
 239     GstEvent -> GstObject
 240     GstMessage -> GstCaps
 241     GstMessage -> GstObject
 242
 243  - lifecycle
 244
 245  a) Two objects exist unlinked.
 246
 247       +---------+        +---------+
 248  *--->| object1 |   *--->| object2 |
 249       |      *  |        |         |
 250       |        1|        |        1|
 251       +---------+        +---------+
 252
 253  b) establishing the single-reffed relationship
 254
 255    The second object is attached to the first one using a method
 256    on the first object. The second object is reffed and a pointer
 257    is updated in the first object using the following algorithm:
 258
 259      LOCK (object1);
 260      if (object1->pointer)
 261        _unref (object1->pointer);
 262      object1->pointer = _ref (object2);
 263      UNLOCK (object1);
 264
 265    After releasing the lock on the first object is is not sure that
 266    object2 is still reffed from object1.
 267
 268       +---------+        +---------+
 269  *--->| object1 |   *--->| object2 |
 270       |       *--------->|         |
 271       |        1|        |        2|
 272       +---------+        +---------+
 273
 274  c) using the single-reffed relationship
 275
 276    The only way to access object2 is by holding a ref to it or by
 277    getting the reference from object1.
 278    Reading the object pointed to by object1 can be done like this:
 279
 280      LOCK (object1);
 281      object2 = object1->pointer;
 282      _ref (object2);
 283      UNLOCK (object1);
 284
 285      .. use object2 ...
 286      _unref (object2);
 287
 288    Depending on the type of the object, modifications can be done either
 289    with copy-on-write or directly into the object.
 290
 291    Copy on write can practically only be done like this:
 292
 293      LOCK (object1);
 294      object2 = object1->pointer;
 295      object2 = _copy_on_write (object2);
 296      ... make modifications to object2 ...
 297      UNLOCK (object1);
 298
 299    Releasing the lock has only a very small window where the copy_on_write
 300    actually does not perform a copy:
 301
 302      LOCK (object1);
 303      object2 = object1->pointer;
 304      _ref (object2);
 305      UNLOCK (object1);
 306
 307      .. object2 now has at least 2 refcounts making the next
 308         copy-on-write make a real copy, unless some other thread
 309         writes another object2 to object1 here ...
 310
 311      object2 = _copy_on_write (object2);
 312
 313      .. make modifications to object2 ...
 314
 315      LOCK (object1);
 316      if (object1->pointer != object2) {
 317        if (object1->pointer)
 318          _unref (object1->pointer);
 319        object1->pointer = gst_object_ref (object2);
 320      }
 321      UNLOCK (object1);
 322
 323  d) destroying the single-reffed relationship
 324
 325    The folowing algorithm removes the single-reffed link between
 326    object1 and object2.
 327
 328      LOCK (object1);
 329      _unref (object1->pointer);
 330      object1->pointer = NULL;
 331      UNLOCK (object1);
 332
 333    Which yields the following initial state again:
 334
 335       +---------+        +---------+
 336  *--->| object1 |   *--->| object2 |
 337       |      *  |        |         |
 338       |        1|        |        1|
 339       +---------+        +---------+
 340
 341
 342 unreffed relation
 343 ~~~~~~~~~~~~~~~~~
 344
 345       +---------+        +---------+
 346  *--->| object1 |   *--->| object2 |
 347       |       *--------->|         |
 348       |        1|<---------*      1|
 349       +---------+        +---------+
 350
 351  - properties
 352
 353    - two objects have references to eachother
 354    - both objects can only have 1 reference to another object.
 355    - reference fields protected with LOCK
 356    - the references held by each object are NOT reflected in the
 357      refcount of the other object.
 358    - no object has ownership of the other.
 359    - typically each object is owned by a different parent.
 360    - creation/destruction requires two nested locks and no refcounts.
 361
 362  - usage
 363
 364    - This type of link is used when the link is less important than
 365      the existance of the objects, If one of the objects is disposed, so
 366      is the link.
 367
 368    GstRealPad <-> GstRealPad (srcpad lock taken first)
 369
 370  - lifecycle
 371
 372  a) Two objects exist unlinked.
 373
 374       +---------+        +---------+
 375  *--->| object1 |   *--->| object2 |
 376       |       * |        |         |
 377       |        1|        | *      1|
 378       +---------+        +---------+
 379
 380  b) establishing the unreffed relationship
 381
 382     Since we need to take two locks, the order in which these locks are
 383     taken is very important or we might cause deadlocks. This lock order
 384     must be defined for all unreffed relations. In these examples we always
 385     lock object1 first and then object2.
 386
 387       LOCK (object1);
 388       LOCK (object2);
 389       object2->refpointer = object1;
 390       object1->refpointer = object2;
 391       UNLOCK (object2);
 392       UNLOCK (object1);
 393
 394  c) using the unreffed relationship
 395
 396     Reading requires taking one of the locks and reading the corresponing
 397     object. Again we need to ref the object before releasing the lock.
 398
 399       LOCK (object1);
 400       object2 = _ref (object1->refpointer);
 401       UNLOCK (object1);
 402
 403       .. use object2 ..
 404       _unref (object2);
 405
 406  d) destroying the unreffed relationship
 407
 408     Because of the lock order we need to be careful when destroying this
 409     Relation.
 410
 411     When only a reference to object1 is held:
 412
 413       LOCK (object1);
 414       LOCK (object2);
 415       object1->refpointer->refpointer = NULL;
 416       object1->refpointer = NULL;
 417       UNLOCK (object2);
 418       UNLOCK (object1);
 419
 420     When only a reference to object2 is held we need to get a handle to the
 421     other object fist so that we can lock it first. There is a window where
 422     we need to release all locks and the relation could be invalid. To solve
 423     this we check the relation after grabbing both locks and retry if the
 424     relation changed.
 425
 426     retry:
 427       LOCK (object2);
 428       object1 = _ref (object2->refpointer);
 429       UNLOCK (object2);
 430       .. things can change here ..
 431       LOCK (object1);
 432       LOCK (object2);
 433       if (object1 == object2->refpointer) {
 434         /* relation unchanged */
 435         object1->refpointer->refpointer = NULL;
 436         object1->refpointer = NULL;
 437       }
 438       else {
 439         /* relation changed.. retry */
 440         UNLOCK (object2);
 441         UNLOCK (object1);
 442         _unref (object1);
 443         goto retry;
 444       }
 445       UNLOCK (object2);
 446       UNLOCK (object1);
 447       _unref (object1);
 448
 449     When references are held to both objects. Note that it is not possible to
 450     get references to both objects with the locks released since when the
 451     references are taken and the locks are released, a concurrent update might
 452     have changed the link, making the references not point to linked objects.
 453
 454       LOCK (object1);
 455       LOCK (object2);
 456       if (object1->refpointer == object2) {
 457         object2->refpointer = NULL;
 458         object1->refpointer = NULL;
 459       }
 460       else {
 461         .. objects are not linked ..
 462       }
 463       UNLOCK (object2);
 464       UNLOCK (object1);
 465
 466
 467 double-reffed relation
 468 ~~~~~~~~~~~~~~~~~~~~~~
 469
 470       +---------+        +---------+
 471  *--->| object1 |   *--->| object2 |
 472       |       *--------->|         |
 473       |        2|<---------*      2|
 474       +---------+        +---------+
 475
 476  - properties
 477
 478    - two objects have references to eachother
 479    - reference fields protected with LOCK
 480    - the references held by each object are reflected in the
 481      refcount of the other object.
 482    - no object has ownership of the other.
 483    - typically each object is owned by a different parent.
 484    - creation/destruction requires two locks and two refcounts.
 485
 486  - usage
 487
 488    Not used in GStreamer.
 489
 490  - lifecycle
 491