From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga04.intel.com (mga04.intel.com [192.55.52.120]) by dpdk.org (Postfix) with ESMTP id E67177D1C for ; Fri, 25 Aug 2017 22:27:34 +0200 (CEST) Received: from fmsmga005.fm.intel.com ([10.253.24.32]) by fmsmga104.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 25 Aug 2017 13:27:34 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.41,426,1498546800"; d="scan'208";a="143992179" Received: from wcpqa1.an.intel.com ([10.123.72.207]) by fmsmga005.fm.intel.com with ESMTP; 25 Aug 2017 13:27:33 -0700 From: Gabriel Carrillo To: rsanford@akamai.com Cc: dev@dpdk.org Date: Fri, 25 Aug 2017 15:27:59 -0500 Message-Id: <1503692879-16320-1-git-send-email-erik.g.carrillo@intel.com> X-Mailer: git-send-email 1.7.10 In-Reply-To: <1503499644-29432-4-git-send-email-erik.g.carrillo@intel.com> References: <1503499644-29432-4-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_v2_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: Fri, 25 Aug 2017 20:27:35 -0000 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 --- 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 ` 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