linux-kernel - [PATCH 05/13] proc: new and improved way to print decimals

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <20180827231503.26899-5-adobriyan@gmail.com>
Date:   Tue, 28 Aug 2018 02:14:55 +0300
From:   Alexey Dobriyan <adobriyan@...il.com>
To:     akpm@...ux-foundation.org
Cc:     linux-kernel@...r.kernel.org, Alexey Dobriyan <adobriyan@...il.com>
Subject: [PATCH 05/13] proc: new and improved way to print decimals

C lacks a capable preprocess to turn

	snprintf(buf, sizeof(buf), "%u", x);

into

	print_integer_u32(buf, x);

so vsnprintf() is forced to have a million branches.
Benchmark anything which uses /proc and look for format_decode().

This unfortunate situation was partially fixed by seq_put_decimal_ull()
function which skipped "format specifier" part. However, it still does
unnecessary copies internally and even reflects the digits before
putting them into final buffer. It also does strlen() which is done at
runtime.

The following 3 functions

	_print_integer_u32
	_print_integer_u64
	_print_integer_ul

cut all the overhead by printing backwards one character at a time:

	x = 123456789

	|	<====|
	|...123456789|

This is just as fast as current printing by 2 characters at a time,
because pids, fds, uids are small integers so emitting 2 characters
doesn't make much difference. It also generates very small code
(146 bytes total here, not counting the callers).
Current put_dec() and friends are surprisingly large.

All the functions have the following signature:

	char *_print_integer_XXX(char *p, T x);

They are written quite in a very specific way to prevent gcc from
inlining everything and making a mess.

They aren't exported and advertised because idiomatic way of using them
is not something you see every day:
* fixed sized buffer on stack capable of holding the worst case,
* pointer past the end of the buffer (yay 6.5.6 p8!)
* no buffer length checks (wheee),
* no NUL terminator (ha-ha-ha),
* emitting output BACKWARDS (one character at a time!),
* finally one copy to the final buffer (one copy, one!).

	char buf[10 + 1 + 20 + 1], *p = buf + sizeof(buf);

	*--p = '\n';
	p = _print_integer_u64(p, y);
	*--p = ' ';
	p = _print_integer_u32(p, x);

	seq_write(seq, p, buf + sizeof(buf) - p);

As the comment says, do not tell anyone about these functions.

The plan is to use them inside /proc and only inside /proc.

Signed-off-by: Alexey Dobriyan <adobriyan@...il.com>
---
 fs/proc/internal.h | 11 +++++++++++
 fs/proc/util.c     | 47 +++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 58 insertions(+)

diff --git a/fs/proc/internal.h b/fs/proc/internal.h
index 5185d7f6a51e..be4965ef8e48 100644
--- a/fs/proc/internal.h
+++ b/fs/proc/internal.h
@@ -127,6 +127,17 @@ void task_dump_owner(struct task_struct *task, umode_t mode,
 		     kuid_t *ruid, kgid_t *rgid);

 unsigned name_to_int(const struct qstr *qstr);
+
+char *_print_integer_u32(char *, u32);
+char *_print_integer_u64(char *, u64);
+static inline char *_print_integer_ul(char *p, unsigned long x)
+{
+	if (sizeof(unsigned long) == 4)
+		return _print_integer_u32(p, x);
+	else
+		return _print_integer_u64(p, x);
+}
+
 /*
  * Offset of the first process in the /proc root directory..
  */
diff --git a/fs/proc/util.c b/fs/proc/util.c
index b161cfa0f9fa..2d9ceab04289 100644
--- a/fs/proc/util.c
+++ b/fs/proc/util.c
@@ -1,4 +1,5 @@
 #include <linux/dcache.h>
+#include <linux/math64.h>

 unsigned name_to_int(const struct qstr *qstr)
 {
@@ -21,3 +22,49 @@ unsigned name_to_int(const struct qstr *qstr)
 out:
 	return ~0U;
 }
+
+/*
+ * Print an integer in decimal.
+ * "p" initially points PAST THE END OF THE BUFFER!
+ *
+ * DO NOT USE THESE FUNCTIONS!
+ *
+ * Do not copy these functions.
+ * Do not document these functions.
+ * Do not move these functions to lib/ or elsewhere.
+ * Do not export these functions to modules.
+ * Do not tell anyone about these functions.
+ */
+noinline
+char *_print_integer_u32(char *p, u32 x)
+{
+	do {
+		*--p = '0' + (x % 10);
+		x /= 10;
+	} while (x != 0);
+	return p;
+}
+
+static char *__print_integer_u32(char *p, u32 x)
+{
+	/* 0 <= x < 10^8 */
+	char *p0 = p - 8;
+
+	p = _print_integer_u32(p, x);
+	while (p != p0)
+		*--p = '0';
+	return p;
+}
+
+char *_print_integer_u64(char *p, u64 x)
+{
+	while (x >= 100000000) {
+		u64 q;
+		u32 r;
+
+		q = div_u64_rem(x, 100000000, &r);
+		p = __print_integer_u32(p, r);
+		x = q;
+	}
+	return _print_integer_u32(p, x);
+}
-- 
2.16.4