docs/random/wtay/scheduling_ideas

   1 Element types
   2 -------------
   3
   4 SOURCES
   5 -------
   6
   7 * never chain-based
   8 * have no sinkpads
   9
  10 1) get based src
  11
  12    (----------)
  13    ! fakesrc  !
  14    !         src-   (get based)
  15    (----------)
  16
  17   * no sinkpads
  18   * srcpad(s) that are get-based
  19
  20 2) loop based src
  21
  22    (----------)
  23    ! fakesrc  !
  24    !         src-   (loop based)
  25    (----------)
  26
  27   * no sinkpads
  28   * element is loop-based
  29   * data is pushed on the srcpad(s)
  30
  31 FILTERS
  32 -------
  33
  34 3) chain based filter
  35
  36    (----------)
  37    ! identity !
  38  -sink       src-
  39    (----------)
  40
  41   * sinkpad(s) have a chain function
  42   * srcpad(s) push data
  43
  44 4) loop-based filter
  45
  46    (----------)
  47    ! identity !
  48  -sink       src-
  49    (----------)
  50
  51   * element is loop-based
  52   * data is pushed on the srcpads
  53   * data is pulled from sinkpad(s)
  54
  55
  56 SINKS
  57 -----
  58
  59 5) chain based sink
  60
  61    (----------)
  62    ! fakesink !
  63  -sink        !
  64    (----------)
  65
  66   * sinkpad(s) have a chain function
  67   * no srcpads
  68
  69 6) loop-based sink
  70
  71    (----------)
  72    ! fakesink !
  73  -sink        !
  74    (----------)
  75
  76   * element is loop-based
  77   * data is pulled from sinkpad(s)
  78
  79
  80 DECOUPLED
  81 ---------
  82
  83 7) decoupled element
  84
  85
  86    (----------)
  87    ! queue    !
  88  -sink       src-
  89    (----------)
  90
  91   * sinkpad(s) have chain function
  92   * srcpad(s) have get function
  93   * never loop-based
  94   * always acts like a chain-based sink for upstream elements
  95   * always acts like a get-based src for downstream elements
  96   * are not added to a group, but marked as an entry point in
  97     case it acts as a src element
  98
  99
 100 Connection types
 101 ----------------
 102
 103 1) get based src
 104 2) loop based src
 105 3) chain based filter
 106 4) loop-based filter
 107 5) chain based sink
 108 6) loop-based sink
 109 7) decoupled element
 110
 111
 112    !  1  !  2  !  3  !  4  !  5  !  6  !  7  !
 113 ---+-----+-----+-----+-----+-----+-----+-----+
 114  1 !  X  !  X  !  A  !  C  !  A  !  C  !  A  !
 115    !     !     !     !     !     !     !     !
 116  2 !  X  !  X  !  B  !  F  !  B  !  F  !  B  !
 117    !     !     !     !     !     !     !     !
 118  3 !  X  !  X  !  D  !  E  !  D  !  E  !  D  !
 119    !     !     !     !     !     !     !     !
 120  4 !  X  !  X  !  B  !  F  !  B  !  F  !  B  !
 121    !     !     !     !     !     !     !     !
 122  5 !  X  !  X  !  X  !  X  !  X  !  X  !  X  !
 123    !     !     !     !     !     !     !     !
 124  6 !  X  !  X  !  X  !  X  !  X  !  X  !  X  !
 125    !     !     !     !     !     !     !     !
 126  7 !  X  !  X  !  A  !  C  !  A  !  C  !  X  !
 127    !     !     !     !     !     !     !     !
 128
 129
 130 A)
 131
 132   src       -> sink
 133   src       -> filter
 134   src       -> decoupled
 135   decoupled -> sink
 136   decoupled -> filter
 137
 138  - get based source
 139  - chain based sink
 140
 141   * one group
 142   * src at start of group and entry point
 143   * _get from src, push to sink
 144
 145   (-group1---------------)
 146   !                      !
 147   ! *fakesrc -> fakesink !
 148   (----------------------)
 149
 150
 151 B)
 152
 153   src    -> sink
 154   src    -> filter
 155   src    -> decoupled
 156   filter -> sink
 157   filter -> filter
 158   filter -> decoupled
 159
 160  - loop based source/filter
 161  - chain based sink/filter/decoupled
 162
 163  * one group
 164  * src/filter at start of group and entry point
 165  * loop on src, chainhandler set to chain function
 166
 167   (-group1----------------)
 168   !                       !
 169   ! %*fakesrc -> fakesink !
 170   (-----------------------)
 171
 172
 173 C)
 174
 175   src       -> sink
 176   src       -> filter
 177   decoupled -> sink
 178   decoupled -> filter
 179
 180  - get based source/decoupled
 181  - loop based sink/filter
 182
 183  * one group
 184  * loop based element is entry point
 185  * loop on sink/filter, gethandler set to getfunction
 186
 187   (-group1----------------)
 188   !                       !
 189   ! fakesrc -> %*fakesink !
 190   (-----------------------)
 191
 192 D)
 193
 194   filter -> filter
 195   filter -> sink
 196   filter -> decoupled
 197
 198   - chain based filter
 199   - chain based filter/sink/decoupled
 200
 201   * one group is created to hold the two elements
 202   * no entry point
 203   * chainhandler set to peer chainfunction
 204
 205   (-group1----------------)
 206   !                       !
 207   ! identity -> identity  !
 208   (-----------------------)
 209
 210 E)
 211
 212   filter  -> filter
 213   filter  -> sink
 214
 215   - chain based filter
 216   - loop based filter/sink
 217
 218   * two groups
 219   * group is created for src element if needed
 220   * chainhandler of loop based element set to loop wrapper, control is
 221     handed to the peer group
 222   * gethandler of loop based element set to get wrapper
 223
 224   (-group1---)  (-group2------)
 225   !          !  !             !
 226   ! identity ---> %*identity  !
 227   (----------)  (-------------)
 228
 229
 230 F)
 231
 232   src     -> filter
 233   src     -> sink
 234   filter  -> filter
 235   filter  -> sink
 236
 237   - loop based filter/src
 238   - loop based filter/sink
 239
 240   * two groups
 241   * two entry points
 242   * chainhandler set to loop wrapper
 243   * gethandler set to get wrapper
 244
 245   (-group1-----)  (-group2------)
 246   !            !  !             !
 247   ! %*identity ---> %*identity  !
 248   (------------)  (-------------)
 249
 250
 251 Grouping
 252 --------
 253
 254  * a group has at most one loop based element
 255  * elements in a group are sorted, src elements first (not mandatory)
 256  * a group has one cothread
 257  * a group is created immediatly for loop based elements, all other elements
 258    are added to a group when a pad connection is made
 259  * get-based plugins are put in the same group as a peer loop based element
 260  * chain based elements are put in the same group as sink peer elements
 261  * entry point in the group is:
 262    - loopbased element
 263    - first src element if no loopbased element exists in the group
 264
 265 Result: you end up with a group of connected elements with either:
 266     - a loop based plugin as the entry point
 267     - a get based plugin as the entry point
 268
 269 Scheduling the group is a matter of starting the cothread and calling
 270 the loop function or doing a _get/_push on a srcpad.
 271
 272
 273 other examples of groups:
 274 -------------------------
 275
 276  % = loop based
 277  * = entry point of group
 278
 279 .
 280   (-group1---------------)
 281   !                      !
 282   ! *fakesrc -> fakesink !
 283   (----------------------)
 284
 285 .
 286   (-group1---------------------------------------)
 287   !                                              !
 288   ! *fakesrc -> identity -> identity -> fakesink !
 289   (----------------------------------------------)
 290
 291 .
 292   (-group1-----------------------------------------)
 293   !                                                !
 294   ! fakesrc -> %*identity -> identity -> fakesink  !
 295   (------------------------------------------------)
 296
 297 .
 298   (-group1---------------) (-group2-----------------)
 299   !                      ! !                        !
 300   ! *fakesrc -> identity --> *%identity -> fakesink !
 301   (----------------------) (------------------------)
 302
 303 .
 304   (-group1------------------------------------)
 305   !                                           !
 306   ! *fakesrc -> tee  --> identity -> fakesink !
 307   !                  --> identity -> fakesink !
 308   (-------------------------------------------)
 309
 310 .
 311   (-group1------------------------------------)
 312   !                                           !
 313   ! *fakesrc -> tee  --> identity -> fakesink !
 314   (--------------!----------------------------)
 315                  v
 316               (-group2-----------------)
 317               !                        !
 318               ! *%identity -> fakesink !
 319               (------------------------)
 320
 321 .
 322   (-group1----------) (-group2-----------------)
 323   !                 ! !                        !
 324   ! *fakesrc -> tee --> *%identity -> fakesink !
 325   (--------------!--) (------------------------)
 326                  v
 327               (-group3-----------------)
 328               !                        !
 329               ! *%identity -> fakesink !
 330               (------------------------)
 331
 332 .
 333   (-group1-----------------------) (-group2----------------------)
 334   !                              ! !                             !
 335   ! filesrc -> *%mpegdemux  --> queue* -> mpeg2dec -> xvideosink !
 336   !                              ! (-----------------------------)
 337   !                              ! (-group3----------------------)
 338   !                              ! !                             !
 339   !                         --> queue* -> mad -> osssink         !
 340   (------------------------------) (-----------------------------)
 341
 342
 343 Chaining
 344 --------
 345
 346  * groups that are connected end up in the same chain
 347  * a group always belongs to a chain
 348  * updating the chain is only needed when two groups are
 349    connected with a connection of type E/F. for other
 350    connection types, the group itself is updated.
 351  * a chain is scheduled by scheduling a random group in the chain.
 352
 353
 354 Wrapper functions
 355 -----------------
 356
 357
 358
 359 iterating without cothreads
 360 ---------------------------
 361
 362 A cothread for each group is the easiest way to schedule most of
 363 the pipelines. Some pipelines are however schedulable without
 364 any cothreads.
 365
 366 Each group is schedulable without cothreads, one can call the
 367 group schedule function and be done with it. Problems arise
 368 one the group boundaries of connected elements, which are always
 369 of type E and F (chain->loop, loop->loop)
 370
 371 We always have a producer group and a provider group in this case.
 372
 373 chain->loop
 374 -----------
 375
 376
 377
 378 Scheduler algorithm
 379 -------------------
 380
 381 1: select (random?) group in chain
 382 2: schedule group
 383 3: on E/F connections, the get/chain wrapper is called
 384    - get wrapper puts the peer element on the runqueue and
 385      recursively invokes the scheduler.
 386    - chain wrapper puts the buffer in the bufpen and puts
 387      the peer element in the runqueue
 388 4: when the group is scheduled, take group from the runqueue
 389    and goto 2:
 390 5: no more groups on the runqueue, iteration ends
 391
 392
 393 NOTES:
 394
 395 - We need a GList instead of a single bufpen to hold buffers
 396   for multi-out elements.
 397
 398 - We probably need to set a limit on the maximum number of
 399   recursions and size of the bufpen list.
 400
 401 - elements run non-preemptively, a group is done scheduling when all
 402   elements in that group complete their chain/loop function.
 403
 404 - can we only have a stack overflow when there is a loop in the
 405   pipeline? I think so.
 406
 407 - putting groups twice on the runqueue is not a good idea, we
 408   need to check a flag or something, maybe give the group a
 409   higher priority?
 410
 411 - what about starvation? We'll probably have to put the group
 412   at the end of the runqueue.
 413
 414 - multi-out elements can introduce significant latency. consider:
 415
 416   (-group1----------) (-group2-----------------)
 417   !                 ! !                        !
 418   ! *filesrc -> mad --> *%identity -> osssink  !
 419   (-----------------) (------------------------)
 420
 421   mad produces N output buffers, they are queued in the bufpen, when
 422   group1 is done, group2 is scheduled to empty the bufpen queue.
 423
 424   The time it takes for the first buffer to arrive at osssink equals
 425   the time needed to decode the N-1 other buffers.
 426
 427   Of course, given the right buffersize for filesrc, N can be reduced
 428   to 1. mad can also suggest a buffersize to filesrc with the
 429   BUFFER_SIZE event.
 430
 431
 432
 433 Ungrouping
 434 ----------
 435
 436 Ungrouping might be the hardest part. especially in the case where
 437 an element is still running (state changes and pipeline modifications
 438 in element callbacks).
 439
 440 Ungrouping involves two tasks:
 441
 442  - breaking up groups. This can happen when a pad connection is broken
 443    so that the group contains two clusters of unconnected elements.
 444  - breaking up chains. This happens when a pad connection is broken
 445    so that the chains contains two clusters of unconnected groups.
 446
 447
 448 case1
 449 -----
 450
 451 The most simple case is where two elements are disconnected and one
 452 of the elements does not belong to a group. In this case, we don't need
 453 to do anything at all.
 454
 455 case2
 456 -----
 457
 458 if the elements are part of different groups, we need to check if the
 459 chain needs to be broken. A chain is broken if it contains two sets
 460 of unconnected groups.
 461
 462 To test this case, we will create a new chain and recursively move
 463 one of the groups with all of its connected groups to it. If the
 464 origial chain is empty after this operation, there was still a connection
 465 and the new chain replaces the old one, else we end up with two chains.
 466
 467 case3
 468 -----
 469
 470 When the elements are part of the same group we check if both elements
 471 still have a connection to some other element in that group. The elements
 472 without connections are removed from the group.
 473
 474 It is possible that when an element still has a connection with some other
 475 element in the group, the group has to be split up anyway. This can happen
 476 in fakesrc ! indentity ! identity ! fakesink when we break the connection
 477 between the two identity elements. We have to be careful here in the cothread
 478 case that we don't take away the running cothread from under the elements.
 479 In the non-cothread case we can just move the elements to another new group.
 480
 481
 482 Interrupt with cothreadless optimal scheduler
 483 ---------------------------------------------
 484
 485 Interrupts are usually performed when a blocking _get based source or
 486 decoupled element is unlocked for a state change. The idea of the
 487 interrupt scheduler call is to return to the main execution stack frame
 488 ASAP so that the state change can take place. For cothread based
 489 implementations of the scheduler this is not a problem as one can jump
 490 to the main cothread context without problems. For non cothread based
 491 schedulers we need to follow this scheme:
 492
 493 get <-> chain based connection.
 494
 495  - enter get group scheduler
 496    - call _get function on source, this can block internally
 497    - app performs state change, element is told to unlock itself
 498    - lock inside the get based function unlocks and _get function
 499      return GST_EVENT_INTERRUPT
 500    - group scheduler notices the event, unrefs it and jumps out of the
 501      get_group_scheduler function, a scheduler INTERRUPTED flag is set.
 502
 503 get <-> loop based connection
 504
 505   - enter loop group scheduler
 506     - loop based element does pull on sinkpad
 507     - _get blocks
 508     - app performs state change, _get is unlocked and returns
 509       GST_EVENT_INTERRUPT.
 510     - loop based function receives INTERRUPT event and exits its loop
 511       ASAP using gst_element_interrupt.
 512
 513 loop/chain <-> loop based connection
 514
 515   - when returning from the recursive call to the scheduler, the state
 516     of the scheduler is checked, if it was interrupted, a
 517     GST_EVENT_INTERRUPTED event is returned to the loop based element.
 518   - the loop based element exits its loop ASAP.
 519
 520
 521 This technique will unwind the stack of scheduled groups ASAP and returns
 522 to the main execution stack frame where the iterate() function can return
 523 and the state change can take place.
 524
 525 Another alternative could be implemented when the _push and _pull functions
 526 would return a result code...
 527
 528
 529
 530
 531
 532
 533
 534
 535
 536
 537