This change updates the timer library documentation to
reflect a change to the organization of the skiplists
in the implementation.
Signed-off-by: Gabriel Carrillo <erik.g.carri...@intel.com>
---
doc/guides/prog_guide/timer_lib.rst | 19 ++++++++++---------
1 file changed, 10 insertions(+), 9 deletions(-)
diff --git a/doc/guides/prog_guide/timer_lib.rst
b/doc/guides/prog_guide/timer_lib.rst
index f437417..f94ffaa 100644
--- a/doc/guides/prog_guide/timer_lib.rst
+++ b/doc/guides/prog_guide/timer_lib.rst
@@ -1,5 +1,5 @@
.. BSD LICENSE
- Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
+ Copyright(c) 2010-2017 Intel Corporation. All rights reserved.
All rights reserved.
Redistribution and use in source and binary forms, with or without
@@ -53,16 +53,17 @@ Refer to the `callout manual
<http://www.daemon-systems.org/man/callout.9.html>`
Implementation Details
----------------------
-Timers are tracked on a per-lcore basis,
-with all pending timers for a core being maintained in order of timer expiry
in a skiplist data structure.
-The skiplist used has ten levels and each entry in the table appears in each
level with probability ¼^level.
+Timers are tracked in a per-lcore array of skiplist data structures; each
+lcore has one skiplist corresponding to each other lcore that could load a
timer on it. All pending
+timers in each skiplist are maintained in order of timer expiry.
+Each skiplist has ten levels and each entry in the table appears in each level
with probability ¼^level.
This means that all entries are present in level 0, 1 in every 4 entries is
present at level 1,
one in every 16 at level 2 and so on up to level 9.
This means that adding and removing entries from the timer list for a core can
be done in log(n) time,
up to 4^10 entries, that is, approximately 1,000,000 timers per lcore.
A timer structure contains a special field called status,
-which is a union of a timer state (stopped, pending, running, config) and an
owner (lcore id).
+which is a union of a timer state (stopped, pending, running, config), an
installer (lcore id), and an owner (lcore id).
Depending on the timer state, we know if a timer is present in a list or not:
* STOPPED: no owner, not in a list
@@ -77,17 +78,17 @@ Resetting or stopping a timer while it is in a CONFIG or
RUNNING state is not al
When modifying the state of a timer,
a Compare And Swap instruction should be used to guarantee that the status
(state+owner) is modified atomically.
-Inside the rte_timer_manage() function,
-the skiplist is used as a regular list by iterating along the level 0 list,
which contains all timer entries,
+Inside the rte_timer_manage() function, each of an lcore's skiplists is
traversed in sequence.
+Each skiplist is used as a regular list by iterating along the level 0 list,
which contains all timer entries,
until an entry which has not yet expired has been encountered.
-To improve performance in the case where there are entries in the timer list
but none of those timers have yet expired,
+To improve performance in the case where there are entries in a skiplist but
none of those timers have yet expired,
the expiry time of the first list entry is maintained within the per-core
timer list structure itself.
On 64-bit platforms, this value can be checked without the need to take a lock
on the overall structure.
(Since expiry times are maintained as 64-bit values,
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,
so this additional check is skipped in favor of checking as normal once the
lock has been taken.)
On both 64-bit and 32-bit platforms,
-a call to rte_timer_manage() returns without taking a lock in the case where
the timer list for the calling core is empty.
+rte_timer_manage() can continue on to an lcore's next skiplist without taking
a lock in the case where a timer list is empty.
Use Cases
---------
--
2.6.4
