doc/guides/prog_guide/timer_lib.rst

   1 ..  BSD LICENSE
   2     Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
   3     All rights reserved.
   4
   5     Redistribution and use in source and binary forms, with or without
   6     modification, are permitted provided that the following conditions
   7     are met:
   8
   9     * Redistributions of source code must retain the above copyright
  10     notice, this list of conditions and the following disclaimer.
  11     * Redistributions in binary form must reproduce the above copyright
  12     notice, this list of conditions and the following disclaimer in
  13     the documentation and/or other materials provided with the
  14     distribution.
  15     * Neither the name of Intel Corporation nor the names of its
  16     contributors may be used to endorse or promote products derived
  17     from this software without specific prior written permission.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  20     "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  21     LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  22     A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  23     OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  24     SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  25     LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  26     DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  27     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  28     (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  29     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  30
  31 .. _Timer_Library:
  32
  33 Timer Library
  34 =============
  35
  36 The Timer library provides a timer service to DPDK execution units to enable execution of callback functions asynchronously.
  37 Features of the library are:
  38
  39 *   Timers can be periodic (multi-shot) or single (one-shot).
  40
  41 *   Timers can be loaded from one core and executed on another. It has to be specified in the call to rte_timer_reset().
  42
  43 *   Timers provide high precision (depends on the call frequency to rte_timer_manage() that checks timer expiration for the local core).
  44
  45 *   If not required in the application, timers can be disabled at compilation time by not calling the rte_timer_manage() to increase performance.
  46
  47 The timer library uses the rte_get_timer_cycles() function that uses the High Precision Event Timer (HPET)
  48 or the CPUs Time Stamp Counter (TSC) to provide a reliable time reference.
  49
  50 This library provides an interface to add, delete and restart a timer. The API is based on BSD callout() with a few differences.
  51 Refer to the `callout manual <http://www.daemon-systems.org/man/callout.9.html>`_.
  52
  53 Implementation Details
  54 ----------------------
  55
  56 Timers are tracked on a per-lcore basis,
  57 with all pending timers for a core being maintained in order of timer expiry in a skiplist data structure.
  58 The skiplist used has ten levels and each entry in the table appears in each level with probability ¼^level.
  59 This means that all entries are present in level 0, 1 in every 4 entries is present at level 1,
  60 one in every 16 at level 2 and so on up to level 9.
  61 This means that adding and removing entries from the timer list for a core can be done in log(n) time,
  62 up to 4^10 entries, that is, approximately 1,000,000 timers per lcore.
  63
  64 A timer structure contains a special field called status,
  65 which is a union of a timer state (stopped, pending, running, config) and an owner (lcore id).
  66 Depending on the timer state, we know if a timer is present in a list or not:
  67
  68 *   STOPPED: no owner, not in a list
  69
  70 *   CONFIG: owned by a core, must not be modified by another core, maybe in a list or not, depending on previous state
  71
  72 *   PENDING: owned by a core, present in a list
  73
  74 *   RUNNING: owned by a core, must not be modified by another core, present in a list
  75
  76 Resetting or stopping a timer while it is in a CONFIG or RUNNING state is not allowed.
  77 When modifying the state of a timer,
  78 a Compare And Swap instruction should be used to guarantee that the status (state+owner) is modified atomically.
  79
  80 Inside the rte_timer_manage() function,
  81 the skiplist is used as a regular list by iterating along the level 0 list, which contains all timer entries,
  82 until an entry which has not yet expired has been encountered.
  83 To improve performance in the case where there are entries in the timer list but none of those timers have yet expired,
  84 the expiry time of the first list entry is maintained within the per-core timer list structure itself.
  85 On 64-bit platforms, this value can be checked without the need to take a lock on the overall structure.
  86 (Since expiry times are maintained as 64-bit values,
  87 a check on the value cannot be done on 32-bit platforms without using either a compare-and-swap (CAS) instruction or using a lock,
  88 so this additional check is skipped in favor of checking as normal once the lock has been taken.)
  89 On both 64-bit and 32-bit platforms,
  90 a call to rte_timer_manage() returns without taking a lock in the case where the timer list for the calling core is empty.
  91
  92 Use Cases
  93 ---------
  94
  95 The timer library is used for periodic calls, such as garbage collectors, or some state machines (ARP, bridging, and so on).
  96
  97 References
  98 ----------
  99
 100 *   `callout manual <http://www.daemon-systems.org/man/callout.9.html>`_
 101     - The callout facility that provides timers with a mechanism to execute a function at a given time.
 102
 103 *   `HPET <http://en.wikipedia.org/wiki/HPET>`_
 104     - Information about the High Precision Event Timer (HPET).