All of lore.kernel.org
 help / color / mirror / Atom feed
From: Erik Gabriel Carrillo <erik.g.carrillo@intel.com>
To: rsanford@akamai.com
Cc: dev@dpdk.org, konstantin.ananyev@intel.com,
	stephen@networkplumber.org, keith.wiles@intel.com,
	narender.vangati@intel.com
Subject: [PATCH v3 3/3] doc: update timer lib docs
Date: Wed, 13 Sep 2017 17:05:08 -0500	[thread overview]
Message-ID: <1505340308-86141-4-git-send-email-erik.g.carrillo@intel.com> (raw)
In-Reply-To: <1505340308-86141-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: Erik Gabriel Carrillo <erik.g.carrillo@intel.com>
---
v3
* Updated implementation details section of timer_lib.rst to reflect the 
  addition of the option to use multiple pending timer lists per lcore.
* Updated release notes to reflect the addition of new function in timer
  lib API.

 doc/guides/prog_guide/timer_lib.rst    | 27 +++++++++++++++++----------
 doc/guides/rel_notes/release_17_11.rst |  7 +++++++
 2 files changed, 24 insertions(+), 10 deletions(-)

diff --git a/doc/guides/prog_guide/timer_lib.rst b/doc/guides/prog_guide/timer_lib.rst
index f437417..dfabf24 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 ¼^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 +80,21 @@ 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,
-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,
+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

  parent reply	other threads:[~2017-09-13 22:04 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 ` [PATCH 3/3] doc: update timer lib docs Gabriel Carrillo
2017-08-25 20:27   ` [PATCH v2 " 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     ` Erik Gabriel Carrillo [this message]
2017-09-18 16:19       ` [PATCH v3 3/3] doc: update timer lib docs 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=1505340308-86141-4-git-send-email-erik.g.carrillo@intel.com \
    --to=erik.g.carrillo@intel.com \
    --cc=dev@dpdk.org \
    --cc=keith.wiles@intel.com \
    --cc=konstantin.ananyev@intel.com \
    --cc=narender.vangati@intel.com \
    --cc=rsanford@akamai.com \
    --cc=stephen@networkplumber.org \
    --subject='Re: [PATCH v3 3/3] doc: update timer lib docs' \
    /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

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.