docs/design/part-relations.txt

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