diff mbox

[11/12,RFC] ipv4: avoid timespec in timestamp computation

Message ID 1443612402-3000775-12-git-send-email-arnd@arndb.de
State RFC, archived
Delegated to: David Miller
Headers show

Commit Message

Arnd Bergmann Sept. 30, 2015, 11:26 a.m. UTC
This is an attempt to avoid the use of timespec in ipv4, where
getnstimeofday() used to be used for computing the number of
milliseconds since midnight, in three places.

That computation would overflow in 2038 on 32-bit machines,
and the normal workaround for this is to use timespec64, which
in turn requires an expensive div_s64_mod() function call
for calculating the seconds modulo 86400.

Instead, this approach introduces a new generic helper function
that does this more efficiently, by using only a 32-bit modulo
(which the compiler can turn into two multiplications), relying
on 39 bits to be sufficient for the current time of day. This
is roughly 100 times faster than a full divmod operation on ARM.

As a further optimization, this does not use the exact nanosecond
value but instead relies tk_xtime() to report the time of the
last jiffy, which is slightly less accurate, depending on the
value of HZ.

Signed-off-by: Arnd Bergmann <arnd@arndb.de>
Cc: Alexey Kuznetsov <kuznet@ms2.inr.ac.ru>
Cc: James Morris <jmorris@namei.org>
Cc: Hideaki YOSHIFUJI <yoshfuji@linux-ipv6.org>
Cc: Patrick McHardy <kaber@trash.net>
Cc: John Stultz <john.stultz@linaro.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
---
 include/linux/timekeeping.h |  2 ++
 kernel/time/timekeeping.c   | 34 ++++++++++++++++++++++++++++++++++
 net/ipv4/icmp.c             |  8 +++-----
 net/ipv4/ip_options.c       |  9 ++-------
 4 files changed, 41 insertions(+), 12 deletions(-)

Comments

kernel test robot Sept. 30, 2015, 11:55 a.m. UTC | #1
Hi Arnd,

[auto build test results on v4.3-rc3 -- if it's inappropriate base, please ignore]

config: mn10300-asb2364_defconfig (attached as .config)
reproduce:
  wget https://git.kernel.org/cgit/linux/kernel/git/wfg/lkp-tests.git/plain/sbin/make.cross -O ~/bin/make.cross
  chmod +x ~/bin/make.cross
  git checkout e1358094d427405462a47d6d2650458b689e55d9
  # save the attached .config to linux build tree
  make.cross ARCH=mn10300 

All error/warnings (new ones prefixed by >>):

   am33_2.0-linux-ld: Dwarf Error: mangled line number section.
   am33_2.0-linux-ld: Dwarf Error: mangled line number section.
   kernel/built-in.o: In function `current_thread_info':
   (___ksymtab_gpl+ktime_get_ms_since_midnight+0x0): undefined reference to `ktime_get_ms_since_midnight'
   am33_2.0-linux-ld: Dwarf Error: mangled line number section.
   am33_2.0-linux-ld: Dwarf Error: mangled line number section.
   am33_2.0-linux-ld: Dwarf Error: mangled line number section.
   am33_2.0-linux-ld: Dwarf Error: mangled line number section.
   am33_2.0-linux-ld: Dwarf Error: mangled line number section.
   am33_2.0-linux-ld: Dwarf Error: mangled line number section.
   am33_2.0-linux-ld: Dwarf Error: mangled line number section.
   am33_2.0-linux-ld: Dwarf Error: mangled line number section.
   am33_2.0-linux-ld: Dwarf Error: mangled line number section.
   net/built-in.o: In function `register_netevent_notifier':
>> net/core/netevent.c:29: undefined reference to `ktime_get_ms_since_midnight'
>> net/core/netevent.c:29: undefined reference to `ktime_get_ms_since_midnight'
   net/core/netevent.c:17: undefined reference to `ktime_get_ms_since_midnight'

vim +29 net/core/netevent.c

792d1932 Tom Tucker 2006-07-30  23  /**
792d1932 Tom Tucker 2006-07-30  24   *	register_netevent_notifier - register a netevent notifier block
792d1932 Tom Tucker 2006-07-30  25   *	@nb: notifier
792d1932 Tom Tucker 2006-07-30  26   *
792d1932 Tom Tucker 2006-07-30  27   *	Register a notifier to be called when a netevent occurs.
792d1932 Tom Tucker 2006-07-30  28   *	The notifier passed is linked into the kernel structures and must
792d1932 Tom Tucker 2006-07-30 @29   *	not be reused until it has been unregistered. A negative errno code
792d1932 Tom Tucker 2006-07-30  30   *	is returned on a failure.
792d1932 Tom Tucker 2006-07-30  31   */
792d1932 Tom Tucker 2006-07-30  32  int register_netevent_notifier(struct notifier_block *nb)

:::::: The code at line 29 was first introduced by commit
:::::: 792d1932e319ff8ba01361e7d151b1794c55c31f [NET]: Network Event Notifier Mechanism.

:::::: TO: Tom Tucker <tom@opengridcomputing.com>
:::::: CC: David S. Miller <davem@sunset.davemloft.net>

---
0-DAY kernel test infrastructure                Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all                   Intel Corporation
kernel test robot Sept. 30, 2015, 12:15 p.m. UTC | #2
Hi Arnd,

[auto build test results on v4.3-rc3 -- if it's inappropriate base, please ignore]

reproduce:
  # apt-get install sparse
  make ARCH=x86_64 allmodconfig
  make C=1 CF=-D__CHECK_ENDIAN__


sparse warnings: (new ones prefixed by >>)

>> kernel/time/timekeeping.c:850:5: sparse: symbol 'ktime_get_ms_of_day' was not declared. Should it be static?

Please review and possibly fold the followup patch.

---
0-DAY kernel test infrastructure                Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all                   Intel Corporation
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Arnd Bergmann Sept. 30, 2015, 12:39 p.m. UTC | #3
On Wednesday 30 September 2015 19:55:43 kbuild test robot wrote:
> Hi Arnd,
> 
> [auto build test results on v4.3-rc3 -- if it's inappropriate base, please ignore]
> 
> config: mn10300-asb2364_defconfig (attached as .config)
> reproduce:
>   wget https://git.kernel.org/cgit/linux/kernel/git/wfg/lkp-tests.git/plain/sbin/make.cross -O ~/bin/make.cross
>   chmod +x ~/bin/make.cross
>   git checkout e1358094d427405462a47d6d2650458b689e55d9
>   # save the attached .config to linux build tree
>   make.cross ARCH=mn10300 
> 
> All error/warnings (new ones prefixed by >>):
> 
>    am33_2.0-linux-ld: Dwarf Error: mangled line number section.
>    am33_2.0-linux-ld: Dwarf Error: mangled line number section.
>    kernel/built-in.o: In function `current_thread_info':
>    (___ksymtab_gpl+ktime_get_ms_since_midnight+0x0): undefined reference to `ktime_get_ms_since_midnight'
>    am33_2.0-linux-ld: Dwarf Error: mangled line number section.
>    am33_2.0-linux-ld: Dwarf Error: mangled line number section.
>    am33_2.0-linux-ld: Dwarf Error: mangled line number section.
>    am33_2.0-linux-ld: Dwarf Error: mangled line number section.
>    am33_2.0-linux-ld: Dwarf Error: mangled line number section.
>    am33_2.0-linux-ld: Dwarf Error: mangled line number section.
>    am33_2.0-linux-ld: Dwarf Error: mangled line number section.
>    am33_2.0-linux-ld: Dwarf Error: mangled line number section.
>    am33_2.0-linux-ld: Dwarf Error: mangled line number section.
>    net/built-in.o: In function `register_netevent_notifier':
> >> net/core/netevent.c:29: undefined reference to `ktime_get_ms_since_midnight'
> >> net/core/netevent.c:29: undefined reference to `ktime_get_ms_since_midnight'
>    net/core/netevent.c:17: undefined reference to `ktime_get_ms_since_midnight'

Thanks for the helpful report, I love the new feature of grabbing the patches
from the list.

Moreover, sorry for screwing up here, I changed the function name before
sending it out and only compiled the files individually but did not notice
that I only changed it in three out of four places because I did not
try to relink the kernel.

I'll send an updated version.

	Arnd
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
diff mbox

Patch

diff --git a/include/linux/timekeeping.h b/include/linux/timekeeping.h
index ca2eaa9077eb..3e126f8c2876 100644
--- a/include/linux/timekeeping.h
+++ b/include/linux/timekeeping.h
@@ -44,6 +44,8 @@  extern void ktime_get_ts64(struct timespec64 *ts);
 extern time64_t ktime_get_seconds(void);
 extern time64_t ktime_get_real_seconds(void);
 
+extern u32 ktime_get_ms_since_midnight(void);
+
 extern int __getnstimeofday64(struct timespec64 *tv);
 extern void getnstimeofday64(struct timespec64 *tv);
 extern void getboottime64(struct timespec64 *ts);
diff --git a/kernel/time/timekeeping.c b/kernel/time/timekeeping.c
index ed5049ff94c5..3a1e030fa969 100644
--- a/kernel/time/timekeeping.c
+++ b/kernel/time/timekeeping.c
@@ -846,6 +846,40 @@  time64_t ktime_get_real_seconds(void)
 }
 EXPORT_SYMBOL_GPL(ktime_get_real_seconds);
 
+#if IS_ENABLED(CONFIG_INET)
+u32 ktime_get_ms_of_day(void)
+{
+	struct timekeeper *tk = &tk_core.timekeeper;
+	struct timespec64 now;
+	unsigned long seq;
+	u32 ms;
+
+	/* we assume that the coarse time is good enough here */
+	do {
+		seq = read_seqcount_begin(&tk_core.seq);
+
+		now = tk_xtime(tk);
+	} while (read_seqcount_retry(&tk_core.seq, seq));
+
+	/*
+	 * efficiently calculate the milliseconds since midnight:
+	 * 86400 seconds per day == 2^7 * 675, which helps us
+	 * replace an expensive div_s64_rem() with a hand-written
+	 * 39-bit modulo on 32-bit architectures.
+	 */
+	if (!IS_ENABLED(CONFIG_64BIT))
+		ms = (now.tv_sec & 0x7f) * MSEC_PER_SEC +
+		     ((u32)(now.tv_sec >> 7) % 675) * 0x80 * MSEC_PER_SEC;
+	else
+		ms = (now.tv_sec % 86400) * MSEC_PER_SEC;
+
+	ms += now.tv_nsec / NSEC_PER_MSEC;
+
+	return ms;
+}
+EXPORT_SYMBOL_GPL(ktime_get_ms_since_midnight);
+#endif
+
 #ifdef CONFIG_NTP_PPS
 
 /**
diff --git a/net/ipv4/icmp.c b/net/ipv4/icmp.c
index e5eb8ac4089d..b1c53f2f7bd5 100644
--- a/net/ipv4/icmp.c
+++ b/net/ipv4/icmp.c
@@ -914,7 +914,6 @@  static bool icmp_echo(struct sk_buff *skb)
  */
 static bool icmp_timestamp(struct sk_buff *skb)
 {
-	struct timespec tv;
 	struct icmp_bxm icmp_param;
 	/*
 	 *	Too short.
@@ -923,11 +922,10 @@  static bool icmp_timestamp(struct sk_buff *skb)
 		goto out_err;
 
 	/*
-	 *	Fill in the current time as ms since midnight UT:
+	 *	Fill in the current time as ms since midnight UT,
+	 *	this could probably be done faster.
 	 */
-	getnstimeofday(&tv);
-	icmp_param.data.times[1] = htonl((tv.tv_sec % 86400) * MSEC_PER_SEC +
-					 tv.tv_nsec / NSEC_PER_MSEC);
+	icmp_param.data.times[1] = htonl(ktime_get_ms_since_midnight());
 	icmp_param.data.times[2] = icmp_param.data.times[1];
 	if (skb_copy_bits(skb, 0, &icmp_param.data.times[0], 4))
 		BUG();
diff --git a/net/ipv4/ip_options.c b/net/ipv4/ip_options.c
index bd246792360b..339ce528ecae 100644
--- a/net/ipv4/ip_options.c
+++ b/net/ipv4/ip_options.c
@@ -58,10 +58,8 @@  void ip_options_build(struct sk_buff *skb, struct ip_options *opt,
 		if (opt->ts_needaddr)
 			ip_rt_get_source(iph+opt->ts+iph[opt->ts+2]-9, skb, rt);
 		if (opt->ts_needtime) {
-			struct timespec tv;
 			__be32 midtime;
-			getnstimeofday(&tv);
-			midtime = htonl((tv.tv_sec % 86400) * MSEC_PER_SEC + tv.tv_nsec / NSEC_PER_MSEC);
+			midtime = htonl(ktime_get_ms_since_midnight());
 			memcpy(iph+opt->ts+iph[opt->ts+2]-5, &midtime, 4);
 		}
 		return;
@@ -415,10 +413,7 @@  int ip_options_compile(struct net *net,
 					break;
 				}
 				if (timeptr) {
-					struct timespec tv;
-					u32  midtime;
-					getnstimeofday(&tv);
-					midtime = (tv.tv_sec % 86400) * MSEC_PER_SEC + tv.tv_nsec / NSEC_PER_MSEC;
+					u32 midtime = ktime_get_ms_since_midnight();
 					put_unaligned_be32(midtime, timeptr);
 					opt->is_changed = 1;
 				}