From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752977AbcKIJhC (ORCPT ); Wed, 9 Nov 2016 04:37:02 -0500 Received: from smtp.codeaurora.org ([198.145.29.96]:35838 "EHLO smtp.codeaurora.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751564AbcKIJg6 (ORCPT ); Wed, 9 Nov 2016 04:36:58 -0500 DMARC-Filter: OpenDMARC Filter v1.3.1 smtp.codeaurora.org 0B139601A3 Authentication-Results: pdx-caf-mail.web.codeaurora.org; dmarc=none header.from=codeaurora.org Authentication-Results: pdx-caf-mail.web.codeaurora.org; spf=pass smtp.mailfrom=joonwoop@codeaurora.org From: Joonwoo Park To: Thomas Gleixner Cc: Joonwoo Park , John Stultz , Eric Dumazet , Frederic Weisbecker , Linus Torvalds , "Paul E. McKenney" , Peter Zijlstra , linux-kernel@vger.kernel.org Subject: [PATCH] timers: Fix timer inaccuracy Date: Wed, 9 Nov 2016 01:36:43 -0800 Message-Id: <1478684203-11966-1-git-send-email-joonwoop@codeaurora.org> X-Mailer: git-send-email 1.9.1 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org When a new timer list enqueued into the time wheel, array index for the given expiry time is: expires = (expires + LVL_GRAN(lvl)) >> LVL_SHIFT(lvl); idx = LVL_OFFS(lvl) + (expires & LVL_MASK); The granularity of the expiry time level is being added to the index in order to fire the timer after its expiry time for the case when the timer cannot fire at the exact time because of each level's granularity. However current index calculation also increases index of timer list even if the timer can fire at exact time. Consequently timers which can fire at exact time including all in the first level of bucket fire with one jiffy delay at present. Fix such inaccuracy by adding granularity of expiry time level only when a given timer cannot fire at exact time. With CONFIG_HZ_100=y Before: 225.768008: timer_start: timer=ffffffffa00042c0 function=timer_func [timer] expires=4294959868 [timeout=2] flags=0x0e800000 225.797961: timer_expire_entry: timer=ffffffffa00042c0 function=timer_func [timer] now=4294959869 After: 54.424805: timer_start: timer=ffffffffa00042c0 function=timer_func [timer] expires=4294942730 [timeout=2] flags=0x10400000 54.444764: timer_expire_entry: timer=ffffffffa00042c0 function=timer_func [timer] now=4294942730 Fixes: 500462a9de65 "timers: Switch to a non-cascading wheel" Cc: Thomas Gleixner Cc: John Stultz Cc: Eric Dumazet Cc: Frederic Weisbecker Cc: Linus Torvalds Cc: Paul E. McKenney Cc: Peter Zijlstra Cc: linux-kernel@vger.kernel.org Signed-off-by: Joonwoo Park --- kernel/time/timer.c | 16 ++++++++++++++-- 1 file changed, 14 insertions(+), 2 deletions(-) diff --git a/kernel/time/timer.c b/kernel/time/timer.c index c611c47..f6ad4e9 100644 --- a/kernel/time/timer.c +++ b/kernel/time/timer.c @@ -467,17 +467,29 @@ static inline void timer_set_idx(struct timer_list *timer, unsigned int idx) */ static inline unsigned calc_index(unsigned expires, unsigned lvl) { - expires = (expires + LVL_GRAN(lvl)) >> LVL_SHIFT(lvl); + if (expires & ~(UINT_MAX << LVL_SHIFT(lvl))) + expires = (expires + LVL_GRAN(lvl)) >> LVL_SHIFT(lvl); + else + expires = expires >> LVL_SHIFT(lvl); return LVL_OFFS(lvl) + (expires & LVL_MASK); } +static inline unsigned calc_index_min_granularity(unsigned expires) +{ + return LVL_OFFS(0) + ((expires >> LVL_SHIFT(0)) & LVL_MASK); +} + static int calc_wheel_index(unsigned long expires, unsigned long clk) { unsigned long delta = expires - clk; unsigned int idx; if (delta < LVL_START(1)) { - idx = calc_index(expires, 0); + /* + * calc_index(expires, 0) should still work but we can + * optimize as LVL_SHIFT(0) is always 0. + */ + idx = calc_index_min_granularity(expires); } else if (delta < LVL_START(2)) { idx = calc_index(expires, 1); } else if (delta < LVL_START(3)) { -- 2.9.3