All of lore.kernel.org
 help / color / mirror / Atom feed
From: Gabriel Carrillo <erik.g.carrillo@intel.com>
To: rsanford@akamai.com
Cc: dev@dpdk.org
Subject: [PATCH 3/3] doc: update timer lib docs
Date: Wed, 23 Aug 2017 09:47:24 -0500	[thread overview]
Message-ID: <1503499644-29432-4-git-send-email-erik.g.carrillo@intel.com> (raw)
In-Reply-To: <1503499644-29432-1-git-send-email-erik.g.carrillo@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: Gabriel Carrillo <erik.g.carrillo@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

  parent reply	other threads:[~2017-08-23 14:48 UTC|newest]

Thread overview: 30+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2017-08-23 14:47 [PATCH 0/3] *** timer library enhancements *** Gabriel Carrillo
2017-08-23 14:47 ` [PATCH 1/3] timer: add per-installer pending lists for each lcore Gabriel Carrillo
2017-08-25 20:27   ` [PATCH v2 " Gabriel Carrillo
2017-08-29 10:57     ` Ananyev, Konstantin
2017-08-29 16:13       ` Carrillo, Erik G
2017-08-29 15:11   ` [PATCH " Stephen Hemminger
2017-08-23 14:47 ` [PATCH 2/3] timer: handle timers installed from non-EAL threads Gabriel Carrillo
2017-08-25 20:27   ` [PATCH v2 " Gabriel Carrillo
2017-08-23 14:47 ` Gabriel Carrillo [this message]
2017-08-25 20:27   ` [PATCH v2 3/3] doc: update timer lib docs Gabriel Carrillo
2017-08-23 15:02 ` [PATCH 0/3] *** timer library enhancements *** Wiles, Keith
2017-08-23 16:19   ` Carrillo, Erik G
2017-08-23 16:50     ` Wiles, Keith
2017-08-23 19:28       ` Carrillo, Erik G
2017-08-23 21:04         ` Wiles, Keith
2017-08-24 14:08           ` Carrillo, Erik G
2017-08-25 20:26 ` [PATCH v2 " Gabriel Carrillo
2017-09-13 22:05   ` [PATCH v3 0/3] timer library enhancement Erik Gabriel Carrillo
2017-09-13 22:05     ` [PATCH v3 1/3] timer: add multiple pending lists option for each lcore Erik Gabriel Carrillo
2017-09-13 22:05     ` [PATCH v3 2/3] timer: handle timers installed from non-EAL threads Erik Gabriel Carrillo
2017-09-13 22:05     ` [PATCH v3 3/3] doc: update timer lib docs Erik Gabriel Carrillo
2017-09-18 16:19       ` Mcnamara, John
2017-09-19 17:04         ` Carrillo, Erik G
2017-09-19 17:02     ` [PATCH v4 0/3] timer library enhancement Erik Gabriel Carrillo
2017-09-19 17:02       ` [PATCH v4 1/3] timer: add multiple pending lists option for each lcore Erik Gabriel Carrillo
2017-09-19 17:02       ` [PATCH v4 2/3] timer: handle timers installed from non-EAL threads Erik Gabriel Carrillo
2017-09-19 17:02       ` [PATCH v4 3/3] doc: update timer lib docs Erik Gabriel Carrillo
2017-10-11 20:42       ` [PATCH v4 0/3] timer library enhancement Thomas Monjalon
2018-04-04 22:42         ` Thomas Monjalon
2018-04-05 21:53           ` Carrillo, Erik G

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=1503499644-29432-4-git-send-email-erik.g.carrillo@intel.com \
    --to=erik.g.carrillo@intel.com \
    --cc=dev@dpdk.org \
    --cc=rsanford@akamai.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.