From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga01.intel.com (mga01.intel.com [192.55.52.88]) by dpdk.org (Postfix) with ESMTP id 72A281AEE8 for ; Tue, 19 Sep 2017 19:00:57 +0200 (CEST) Received: from fmsmga003.fm.intel.com ([10.253.24.29]) by fmsmga101.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 19 Sep 2017 10:00:54 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.42,418,1500966000"; d="scan'208";a="901901901" Received: from wcpqa1.an.intel.com ([10.123.72.207]) by FMSMGA003.fm.intel.com with ESMTP; 19 Sep 2017 10:00:53 -0700 From: Erik Gabriel Carrillo To: rsanford@akamai.com Cc: dev@dpdk.org, john.mcnamara@intel.com, Erik Carrillo Date: Tue, 19 Sep 2017 12:02:28 -0500 Message-Id: <1505840548-77004-4-git-send-email-erik.g.carrillo@intel.com> X-Mailer: git-send-email 1.7.10 In-Reply-To: <1505840548-77004-1-git-send-email-erik.g.carrillo@intel.com> References: <1505340308-86141-1-git-send-email-erik.g.carrillo@intel.com> <1505840548-77004-1-git-send-email-erik.g.carrillo@intel.com> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Subject: [dpdk-dev] =?utf-8?q?=5BPATCH_v4_3/3=5D_doc=3A_update_timer_lib_d?= =?utf-8?q?ocs?= X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 19 Sep 2017 17:00:58 -0000 From: Erik Carrillo 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 Acked-by: John McNamara --- 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 ` 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