From: Erik Carrillo <erik.g.carri...@intel.com> This change updates the timer library documentation to reflect a change to the organization of the skiplists in the implementation.
Signed-off-by: Erik Gabriel Carrillo <erik.g.carri...@intel.com> Acked-by: John McNamara <john.mcnam...@intel.com> --- v4: * Made changes suggested by John Mcnamara[1]. [1] http://dpdk.org/ml/archives/dev/2017-September/075819.html doc/guides/prog_guide/timer_lib.rst | 31 +++++++++++++++++++------------ doc/guides/rel_notes/release_17_11.rst | 7 +++++++ 2 files changed, 26 insertions(+), 12 deletions(-) diff --git a/doc/guides/prog_guide/timer_lib.rst b/doc/guides/prog_guide/timer_lib.rst index f437417..e1f64ac 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,19 @@ 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 on a per-lcore basis, with all pending timers for a core being maintained in order of timer +expiry in either a single skiplist data structure or an array of skiplists, depending on whether +the lcore has been configured for multiple pending lists. Multiple pending lists can be enabled when an +application experiences contention for a single list for that lcore; skiplists corresponding to every other +enabled lcore will be created. +Each skiplist data structure has ten levels and each entry in the table appears in each level with probability 0.25^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 index (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 @@ -75,19 +78,23 @@ Depending on the timer state, we know if a timer is present in a list or not: Resetting or stopping a timer while it is in a CONFIG or RUNNING state is not allowed. 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, -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, +a Compare And Swap instruction should be used to guarantee that the status (state+index+owner) is modified atomically. + +Inside the rte_timer_manage() function, the timer lists are processed. +If multiple pending lists have been enabled for an lcore, then each skiplist will +be traversed sequentially, and run lists will be broken out and then processed. +If multiple pending lists are not enabled for an lcore, then only a single skiplist will be traversed. +A 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 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 either return or continue on to an lcore's next skiplist without taking a lock in the case where a timer list is empty, +depending on whether or not the lcore has multiple pending lists. Use Cases --------- diff --git a/doc/guides/rel_notes/release_17_11.rst b/doc/guides/rel_notes/release_17_11.rst index 170f4f9..4683cbe 100644 --- a/doc/guides/rel_notes/release_17_11.rst +++ b/doc/guides/rel_notes/release_17_11.rst @@ -110,6 +110,13 @@ API Changes Also, make sure to start the actual text at the margin. ========================================================= +* **Updated timer library.** + + The timer library has been updated; it can now support multiple timer lists + per lcore where it previously only had one. This functionality is off by + default but can be enabled in cases where contention for a single list is + an issue with the new function ``rte_timer_subsystem_set_multi_pendlists()``. + ABI Changes ----------- -- 2.6.4
