From: Artem Savkov <asavkov@redhat.com>
To: Thomas Gleixner <tglx@linutronix.de>,
Josh Poimboeuf <jpoimboe@redhat.com>,
Anna-Maria Behnsen <anna-maria@linutronix.de>,
netdev@vger.kernel.org
Cc: davem@davemloft.net, yoshfuji@linux-ipv6.org, dsahern@kernel.org,
linux-kernel@vger.kernel.org, Artem Savkov <asavkov@redhat.com>
Subject: [PATCH v4 1/2] timer: add a function to adjust timeouts to be upper bound
Date: Thu, 7 Apr 2022 09:52:41 +0200 [thread overview]
Message-ID: <20220407075242.118253-2-asavkov@redhat.com> (raw)
In-Reply-To: <20220407075242.118253-1-asavkov@redhat.com>
Current timer wheel implementation is optimized for performance and
energy usage but lacks in precision. This, normally, is not a problem as
most timers that use timer wheel are used for timeouts and thus rarely
expire, instead they often get canceled or modified before expiration.
Even when they don't, expiring a bit late is not an issue for timeout
timers.
TCP keepalive timer is a special case, it's aim is to prevent timeouts,
so triggering earlier rather than later is desired behavior. In a
reported case the user had a 3600s keepalive timer for preventing firewall
disconnects (on a 3650s interval). They observed keepalive timers coming
in up to four minutes late, causing unexpected disconnects.
This commit adds upper_bound_timeout() function that takes a relative
timeout and adjusts it based on timer wheel granularity so that supplied
value effectively becomes an upper bound for the timer.
This was previously discussed here:
https://lore.kernel.org/all/20210302001054.4qgrvnkltvkgikzr@treble/T/#u
Suggested-by: Josh Poimboeuf <jpoimboe@redhat.com>
Signed-off-by: Artem Savkov <asavkov@redhat.com>
---
include/linux/timer.h | 1 +
kernel/time/timer.c | 68 ++++++++++++++++++++++++++++++++++---------
2 files changed, 56 insertions(+), 13 deletions(-)
diff --git a/include/linux/timer.h b/include/linux/timer.h
index fda13c9d1256c..b209d31d543f0 100644
--- a/include/linux/timer.h
+++ b/include/linux/timer.h
@@ -168,6 +168,7 @@ static inline int timer_pending(const struct timer_list * timer)
return !hlist_unhashed_lockless(&timer->entry);
}
+extern unsigned long upper_bound_timeout(unsigned long timeout);
extern void add_timer_on(struct timer_list *timer, int cpu);
extern int del_timer(struct timer_list * timer);
extern int mod_timer(struct timer_list *timer, unsigned long expires);
diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index 85f1021ad4595..a645b62e257e2 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -507,28 +507,38 @@ static inline unsigned calc_index(unsigned long expires, unsigned lvl,
return LVL_OFFS(lvl) + (expires & LVL_MASK);
}
-static int calc_wheel_index(unsigned long expires, unsigned long clk,
- unsigned long *bucket_expiry)
+static inline int get_wheel_lvl(unsigned long delta)
{
- unsigned long delta = expires - clk;
- unsigned int idx;
-
if (delta < LVL_START(1)) {
- idx = calc_index(expires, 0, bucket_expiry);
+ return 0;
} else if (delta < LVL_START(2)) {
- idx = calc_index(expires, 1, bucket_expiry);
+ return 1;
} else if (delta < LVL_START(3)) {
- idx = calc_index(expires, 2, bucket_expiry);
+ return 2;
} else if (delta < LVL_START(4)) {
- idx = calc_index(expires, 3, bucket_expiry);
+ return 3;
} else if (delta < LVL_START(5)) {
- idx = calc_index(expires, 4, bucket_expiry);
+ return 4;
} else if (delta < LVL_START(6)) {
- idx = calc_index(expires, 5, bucket_expiry);
+ return 5;
} else if (delta < LVL_START(7)) {
- idx = calc_index(expires, 6, bucket_expiry);
+ return 6;
} else if (LVL_DEPTH > 8 && delta < LVL_START(8)) {
- idx = calc_index(expires, 7, bucket_expiry);
+ return 7;
+ }
+
+ return -1;
+}
+
+static int calc_wheel_index(unsigned long expires, unsigned long clk,
+ unsigned long *bucket_expiry)
+{
+ unsigned long delta = expires - clk;
+ unsigned int idx;
+ int lvl = get_wheel_lvl(delta);
+
+ if (lvl >= 0) {
+ idx = calc_index(expires, lvl, bucket_expiry);
} else if ((long) delta < 0) {
idx = clk & LVL_MASK;
*bucket_expiry = clk;
@@ -545,6 +555,38 @@ static int calc_wheel_index(unsigned long expires, unsigned long clk,
return idx;
}
+/**
+ * upper_bound_timeout - return granularity-adjusted timeout
+ * @timeout: timeout value in jiffies
+ *
+ * This function return supplied timeout adjusted based on timer wheel
+ * granularity effectively making supplied value an upper bound at which the
+ * timer will expire. Due to the way timer wheel works timeouts smaller than
+ * LVL_GRAN on their respecrive levels will be _at least_
+ * LVL_GRAN(lvl) - LVL_GRAN(lvl -1)) jiffies early.
+ */
+unsigned long upper_bound_timeout(unsigned long timeout)
+{
+ int lvl = get_wheel_lvl(timeout);
+
+ if (lvl < 0) {
+ if ((long) timeout < 0) {
+ /*
+ * This will expire immediately so no adjustment
+ * needed.
+ */
+ return timeout;
+ } else {
+ if (timeout > WHEEL_TIMEOUT_CUTOFF)
+ timeout = WHEEL_TIMEOUT_CUTOFF;
+ lvl = LVL_DEPTH - 1;
+ }
+ }
+
+ return LVL_GRAN(lvl) > timeout ? 0 : timeout - LVL_GRAN(lvl);
+}
+EXPORT_SYMBOL(upper_bound_timeout);
+
static void
trigger_dyntick_cpu(struct timer_base *base, struct timer_list *timer)
{
--
2.34.1
next prev parent reply other threads:[~2022-04-07 7:53 UTC|newest]
Thread overview: 35+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-03-23 11:16 [PATCH 0/2] Upper bound mode for kernel timers Artem Savkov
2022-03-23 11:16 ` [PATCH 1/2] timer: introduce upper bound timers Artem Savkov
2022-03-23 18:40 ` Josh Poimboeuf
2022-03-24 9:14 ` [PATCH v2 0/2] Upper bound mode for kernel timers Artem Savkov
2022-03-24 9:14 ` [PATCH v2 1/2] timer: introduce upper bound timers Artem Savkov
2022-03-24 9:15 ` [PATCH v2 2/2] net: make tcp keepalive timer upper bound Artem Savkov
2022-03-24 12:28 ` [PATCH 1/2] timer: introduce upper bound timers Thomas Gleixner
2022-03-24 13:54 ` Thomas Gleixner
2022-03-26 21:13 ` Thomas Gleixner
2022-03-30 8:20 ` [PATCH v3 0/2] Upper bound kernel timers Artem Savkov
2022-03-30 8:20 ` [PATCH v3 1/2] timer: add a function to adjust timeouts to be upper bound Artem Savkov
2022-03-30 13:40 ` Anna-Maria Behnsen
2022-04-02 6:55 ` Artem Savkov
2022-04-05 15:33 ` Thomas Gleixner
2022-04-07 7:52 ` [PATCH v4 0/2] Upper bound kernel timers Artem Savkov
2022-04-07 7:52 ` Artem Savkov [this message]
2022-04-08 0:37 ` [PATCH v4 1/2] timer: add a function to adjust timeouts to be upper bound Thomas Gleixner
2022-04-08 5:39 ` Josh Poimboeuf
2022-04-12 13:42 ` Artem Savkov
2022-05-05 13:18 ` [PATCH v5 0/2] Upper bound kernel timers Artem Savkov
2022-05-05 13:18 ` [PATCH v5 1/2] timer: add a function to adjust timeouts to be upper bound Artem Savkov
2022-05-05 13:18 ` [PATCH v5 2/2] net: make tcp keepalive timer " Artem Savkov
2022-05-05 17:56 ` Josh Poimboeuf
2022-05-06 6:39 ` Artem Savkov
2022-05-06 16:24 ` Josh Poimboeuf
2022-07-26 22:42 ` [PATCH v5 0/2] Upper bound kernel timers Josh Poimboeuf
2022-04-07 7:52 ` [PATCH v4 2/2] net: make tcp keepalive timer upper bound Artem Savkov
[not found] ` <Yk1i3WrcVIICAiF0@samus.usersys.redhat.com>
2022-04-07 23:26 ` [PATCH v3 1/2] timer: add a function to adjust timeouts to be " Thomas Gleixner
2022-03-30 8:20 ` [PATCH v3 2/2] net: make tcp keepalive timer " Artem Savkov
2022-04-02 3:09 ` [net] 6ef3f95797: UBSAN:shift-out-of-bounds_in_kernel/time/timer.c kernel test robot
2022-04-02 7:11 ` Artem Savkov
2022-03-30 10:28 ` [PATCH v3 0/2] Upper bound kernel timers David Laight
2022-03-25 7:38 ` [timer] d41e0719d5: UBSAN:shift-out-of-bounds_in_lib/flex_proportions.c kernel test robot
2022-03-25 19:14 ` Thomas Gleixner
2022-03-23 11:16 ` [PATCH 2/2] net: make tcp keepalive timer upper bound Artem Savkov
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=20220407075242.118253-2-asavkov@redhat.com \
--to=asavkov@redhat.com \
--cc=anna-maria@linutronix.de \
--cc=davem@davemloft.net \
--cc=dsahern@kernel.org \
--cc=jpoimboe@redhat.com \
--cc=linux-kernel@vger.kernel.org \
--cc=netdev@vger.kernel.org \
--cc=tglx@linutronix.de \
--cc=yoshfuji@linux-ipv6.org \
/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 a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).