Clean up and shrink uuid input & output

Okay, here's a more formal submission.

Net code size changes for both patches:

	uuid_string()			__uuid_to_bin()
	Before  After   Delta   Percent	Before  After   Delta   Percent

x86-32 245 196 -49 -20.0% 122 90 -32 -26.2%
x86-64 246 162 -84 -34.1% 127 90 -37 -29.1%
arm 292 216 -76 -26.0% 116 92 -24 -20.7%
thumb 220 136 -84 -38.2% 100 50 -50 -50.0%
arm64 296 188 -108 -36.5% 148 116 -32 -21.6%

I haven't measured the speedup because, although it's obviously faster, speed is not particularly important. (I wouldn't be using out-of-line hex2bin() if it were.)

Andy Shevchenko wrote

No, my original patch didn't increase rodata at all, because it replaced tables of the same size.

Bringing that patch forward in the simplest way (the first copy, which I sent you privately) broke the sharing of the arrays with lib/uuid.c and thereby increased rodata by 32 bytes.

But patching lib/uuid.c to share the new tables as is done in this patch series ends up with a net 16-byte reduction in rodata.

Mea culpa. I manually copied the e-mail addresses and managed to typo "bjorn" into "bbjorn".

It's truly marginal, deleted.

hex2bin is better than hex_to_bin because it's does more of what we want in one call rather than needing two.

As for checking the return value, it's a longish story. However, at your prompting, I've deleted it (more size savings!).

Now, the story...

Originally, I had eliminated the uuid_is_valid() call entirely, and just checked that the hyphens were in the right place and the digits all converted:

static int __uuid_to_bin(const char *uuid, __u8 b[16], const u8 si[16])

{
	unsigned int i;
 
	if (uuid[ 8] != '-' || uuid[13] != '-' ||
	    uuid[18] != '-' || uuid[23] != '-')
		return -EINVAL;
 
	for (i = 0; i < 16; i++)
		if (hex2bin(b + i, uuid + si[i], 1) < 0)
			return -EINVAL;
 
	return 0;
}

... but I was worried that some callers might be passing in an arbitrary null-terminated string, and reading uuid[23] before checking that the preceding characters were all non-null might be a bad thing.

So I put the uuid_is_valid() call back.

However, I left the second return value check, on general principles, because it was cheap and I wasn't sure it wasn't useful.

i was thinking about about time-of-check to time-of-use race conditions. I had just determined that I didn't know the callers and what they were doing, so I wasn't sure the source uuid would be stable for the duration of the call.

However, this isn't a real TOCTTOU security bug. The only thing that corrupting the buffer can do is insert a 0xff byte in the uuid. Which is nothing that couldn't be done with a static input.

So it's unnecessary.

George Spelvin (2):
lib/vsprintf.c: Simplify uuid_string()
lib/uuid.c: eliminate uuid_[bl]e_index arrays

 include/linux/uuid.h |  6 ++++--
 lib/uuid.c           | 24 ++++++++++--------------
 lib/vsprintf.c       | 40 +++++++++++++++++-----------------------
 3 files changed, 31 insertions(+), 39 deletions(-)

2.8.1

Rather than have a second pass to upcase the buffer, just make the hex lookup table a variable.

Removing the conditional branch from the inner loop is also a speedup, but since this is not hot code, the important factor it shrinks both source and compiled forms:

Before After Delta Percentage
x86-32 245 199 -46 -18.8%
x86-64 246 186 -60 -24.4%
arm 292 264 -28 -9.6%
thumb 220 160 -60 -27.3%
arm64 296 244 -52 -17.6%

---
 lib/vsprintf.c | 16 ++++++++--------
 1 file changed, 8 insertions(+), 8 deletions(-)

index 7332a5d7..4ee07e89 100644
@@ -1316,24 +1316,24 @@ char *uuid_string(char *buf, char *end, const u8 *addr,
 	char *p = uuid;
 	int i;
 	const u8 *index = uuid_be_index;
-	bool uc = false;
+	const char *hex = hex_asc;
 
-	switch (*(++fmt)) {
+	switch (fmt[1]) {
 	case 'L':
-		uc = true;		/* fall-through */
+		hex = hex_asc_upper;	/* fall-through */
 	case 'l':
 		index = uuid_le_index;
 		break;
 	case 'B':
-		uc = true;
+		hex = hex_asc_upper;
 		break;
 	}
 
 	for (i = 0; i < 16; i++) {
-		if (uc)
-			p = hex_byte_pack_upper(p, addr[index[i]]);
-		else
-			p = hex_byte_pack(p, addr[index[i]]);
+		u8 byte = addr[index[i]];
+
+		*p++ = hex[byte >> 4];
+		*p++ = hex[byte & 0x0f];
 		switch (i) {
 		case 3:
 		case 5:

2.8.1

r

X-ExtLoop1: 1
X-IronPort-AV: E=Sophos;i="5.26,421,1459839600";
d="scan'208";a="969274163"
Subject: Re: [PATCH v2 1/2] lib/vsprintf.c: Simplify uuid_string()
From: Andy Shevchenko <[email protected]>
To: George Spelvin <[email protected]>
Cc: [email protected], [email protected], [email protected],
[email protected]
Date: Sun, 05 Jun 2016 17:22:56 +0300
In-Reply-To: <[email protected]>
References: <[email protected]>
Organization: Intel Finland Oy
Content-Type: text/plain; charset="UTF-8"
X-Mailer: Evolution 3.20.2-2
Mime-Version: 1.0
Content-Transfer-Encoding: 8bit

Because they're inline functions, so there's no compiled copy to take the address of.

Since they're delcared "static", if you take their addresses anyway, gcc will helpfully compile private versions for the use of this source file, which will be bigger and slower than the simple inline expansion I used here.

It's not even any *simpler*. Remembering what "hex_byte_pack()" means is as much mental effort as interpreting those two very simple lines.

There's no strong reason to *avoid* using the hex_asc[] arrays directly. It's done in several other places in the kernel, including earlier in lib/vsprintf.c (search for "hex_asc_upper" in number()).

If they were intended to be "off limits", they would have been given _-prefixed names.

Both input and output code is simplified if we use a mapping from binary UUID index to ASCII UUID position. This lets us combine hyphen-skipping and endian-swapping into one table.

This significantly simplifies __uuid_to_bin(), which was using *two* lookup tables.

uuid_[bl]e_index were EXPORT_SYMBOLed for no obvious reason; all users are compiled unconditionally into the kernel. The replacement uuid_[bl]e_pos arrays are not exported until a need appears.

Benefits:
* The source code is shorter and simpler,
* it executes faster,
* initialized data is 16 bytes smaller, and
* compiled code is smaller.

Since this is not hot code, the important benchmark is not run time but code size:

	uuid_string()			__uuid_to_bin()
	Before  After   Delta   Percent	Before  After   Delta   Percent

x86-32 199 196 -3 -1.5% 122 90 -32 -26.2%
x86-64 186 162 -24 -12.9% 127 90 -37 -29.1%
arm 264 216 -48 -18.2% 116 92 -24 -20.7%
thumb 160 136 -24 -15.0% 100 50 -50 -50.0%
arm64 244 188 -56 -23.0% 148 116 -32 -21.6%

---
 include/linux/uuid.h |  5 +++--
 lib/uuid.c           | 24 +++++++++---------------
 lib/vsprintf.c       | 26 ++++++++++----------------
 3 files changed, 22 insertions(+), 33 deletions(-)

index 2d095fc6..238f16f7 100644
@@ -41,8 +41,9 @@ extern void uuid_be_gen(uuid_be *u);
 
 bool __must_check uuid_is_valid(const char *uuid);
 
-extern const u8 uuid_le_index[16];
-extern const u8 uuid_be_index[16];
+/* For each binary byte, string offset in ASCII UUID where it appears */
+extern const u8 uuid_be_pos[16];
+extern const u8 uuid_le_pos[16];
 
 int uuid_le_to_bin(const char *uuid, uuid_le *u);
 int uuid_be_to_bin(const char *uuid, uuid_be *u);

index e116ae5f..93945915 100644
@@ -21,11 +21,6 @@
 #include <linux/uuid.h>
 #include <linux/random.h>
 
-const u8 uuid_le_index[16] = {3,2,1,0,5,4,7,6,8,9,10,11,12,13,14,15};
-EXPORT_SYMBOL(uuid_le_index);
-const u8 uuid_be_index[16] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
-EXPORT_SYMBOL(uuid_be_index);
-
 /***************************************************************
  * Random UUID interface
  *

@@ -97,32 +92,31 @@ bool uuid_is_valid(const char *uuid)
 }
 EXPORT_SYMBOL(uuid_is_valid);
 
-static int __uuid_to_bin(const char *uuid, __u8 b[16], const u8 ei[16])
+/* For each binary byte, string offset in ASCII UUID where it appears */
+const u8 uuid_be_pos[16] = {0,2,4,6,9,11,14,16,19,21,24,26,28,30,32,34};
+const u8 uuid_le_pos[16] = {6,4,2,0,11,9,16,14,19,21,24,26,28,30,32,34};
+
+static int __uuid_to_bin(const char uuid[36], __u8 b[16], const u8 pos[16])
 {
-	static const u8 si[16] = {0,2,4,6,9,11,14,16,19,21,24,26,28,30,32,34};
 	unsigned int i;
 
 	if (!uuid_is_valid(uuid))
 		return -EINVAL;
 
-	for (i = 0; i < 16; i++) {
-		int hi = hex_to_bin(uuid[si[i]] + 0);
-		int lo = hex_to_bin(uuid[si[i]] + 1);
-
-		b[ei[i]] = (hi << 4) | lo;
-	}
+	for (i = 0; i < 16; i++)
+		hex2bin(b + i, uuid + pos[i], 1);
 
 	return 0;
 }
 
 int uuid_le_to_bin(const char *uuid, uuid_le *u)
 {
-	return __uuid_to_bin(uuid, u->b, uuid_le_index);
+	return __uuid_to_bin(uuid, u->b, uuid_le_pos);
 }
 EXPORT_SYMBOL(uuid_le_to_bin);
 
 int uuid_be_to_bin(const char *uuid, uuid_be *u)
 {
-	return __uuid_to_bin(uuid, u->b, uuid_be_index);
+	return __uuid_to_bin(uuid, u->b, uuid_be_pos);
 }
 EXPORT_SYMBOL(uuid_be_to_bin);

index 4ee07e89..f02cfd9f 100644
@@ -1313,38 +1313,32 @@ char *uuid_string(char *buf, char *end, const u8 *addr,
 		  struct printf_spec spec, const char *fmt)
 {
 	char uuid[UUID_STRING_LEN + 1];
-	char *p = uuid;
 	int i;
-	const u8 *index = uuid_be_index;
+	const u8 *pos = uuid_be_pos;
 	const char *hex = hex_asc;
 
 	switch (fmt[1]) {
 	case 'L':
 		hex = hex_asc_upper;	/* fall-through */
 	case 'l':
-		index = uuid_le_index;
+		pos = uuid_le_pos;
 		break;
 	case 'B':
 		hex = hex_asc_upper;
 		break;
 	}
 
+	/* Format each byte of the raw uuid into the buffer */
 	for (i = 0; i < 16; i++) {
-		u8 byte = addr[index[i]];
+		u8 byte = addr[i];
+		char *p = uuid + pos[i];
 
-		*p++ = hex[byte >> 4];
-		*p++ = hex[byte & 0x0f];
-		switch (i) {
-		case 3:
-		case 5:
-		case 7:
-		case 9:
-			*p++ = '-';
-			break;
-		}
+		p[0] = hex[byte >> 4];
+		p[1] = hex[byte & 0x0f];
 	}
-
-	*p = 0;
+	/* Insert the fixed punctuation */
+	uuid[23] = uuid[18] = uuid[13] = uuid[8] = '-';
+	uuid[UUID_STRING_LEN] = '\0';
 
 	return string(buf, end, uuid, spec);
 }

2.8.1

(adding acpi folks)

Seems sensible, thanks.

Trivially, acpi defines this but doesn't seem to use it.

include/acpi/acconfig.h:#define UUID_STRING_LENGTH          36  /* Total length of a UUID string */

And Ingo commented last month:
https://lkml.org/lkml/2016/4/29/69

Maybe this __uuid_to_bin function should be made public and the acpi version in drivers/acpi/acpica/utuuid.c should be removed.

I agree with the second part, but not the first; the uuid_le_to_bin() wrapper is better for the job, and already public.

Looks like you missed my first version of (other) series.
http://www.spinics.net/lists/linux-api/msg17518.html

Andy Shevchenko <[email protected]>
Intel Finland Oy
--
To unsubscribe from this list: send the line "unsubscribe linux-acpi" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

More like if a patch isn't applied after several months, it's likely not going to be applied unless it is resent.
--
To unsubscribe from this list: send the line "unsubscribe linux-acpi" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

The discussion was about how to proceed with uuid_*_cmp() functions that have prototypes like uuid_le x1, x2. Any ideas come to mind?

Andy Shevchenko <[email protected]>
Intel Finland Oy
--
To unsubscribe from this list: send the line "unsubscribe linux-acpi" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Andy Shevchenko pointed out that __uuid_to_bin doesn't need to check the return value from hex2bin(), because the preceding uuid_is_valid() check already took care of that.

But hex2bin() is declared __must_check, so checking anyway is the simplest way to silence the warning.

This cancels a small fraction of the the space savings, but not all:

vs. previous patch vs. before patch series
Before After Delta Percent Orig. Delta Percent
x86-32 90 96 +6 6.7% 122 -26 -21.3%
x86-64 90 96 +6 6.7% 127 -31 -24.4%
arm 92 104 +12 13.0% 116 -12 -10.3%
thumb 50 62 +12 24.0% 100 -38 -38.0%
arm64 116 124 +8 6.9% 148 -24 -16.2%

---
 lib/uuid.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

index 93945915..1a6dbbd2 100644
@@ -104,7 +104,8 @@ static int __uuid_to_bin(const char uuid[36], __u8 b[16], const u8 pos[16])
 		return -EINVAL;
 
 	for (i = 0; i < 16; i++)
-		hex2bin(b + i, uuid + pos[i], 1);
+		if (hex2bin(b + i, uuid + pos[i], 1) < 0)
+			return -EINVAL;
 
 	return 0;
 }

2.8.1

X-ExtLoop1: 1
X-IronPort-AV: E=Sophos;i="5.26,421,1459839600";
d="scan'208";a="995605979"
Subject: Re: [PATCH v2 3/2] lib/uuid.c: Silence an unchecked return value
warning
From: Andy Shevchenko <[email protected]>
To: George Spelvin <[email protected]>
Cc: [email protected], [email protected], [email protected],
[email protected]
Date: Sun, 05 Jun 2016 17:21:04 +0300
In-Reply-To: <[email protected]>
References: <[email protected]>
Organization: Intel Finland Oy
Content-Type: text/plain; charset="UTF-8"
X-Mailer: Evolution 3.20.2-2
Mime-Version: 1.0
Content-Transfer-Encoding: 8bit

Andy Shevchenko worte:

Um... huh? Neither hex_to_bin() nor hex2bin() are inline functions. They're declared as extern in <linux/kernel.h> and defined in lib/hexdump.c.

One call is smaller than two calls, which is why I did that.

It's also faster, as hex_to_bin() *is* inlined within hex2bin() (if you compile with -O).

Is your request based on a false premise?

^^^^ Something wrong with mail configuration?

To be sure it faster we need the measurements. Sometimes it's not obvious.

Yeah, you are right, I looked at hex2bin() which is in the same module.

Andy Shevchenko <[email protected]>
Intel Finland Oy

Oops, sorry, I forgot to delete the header.

You're right that sometimes measurements show surprising results. But do you want to bet on it? :-)

If speed were a primary goal, I'd want to be sure.

But as you pointed out, this is not hot-path code and speed is *not* a primary goal. Being off the hot path also makes benchmarking more annoying, as it's hard to define realistic test conditions. (Code resident in L2 but not in L1?)

So I think it's reasonable in this case to estimate rather than waste effort striving for certainty. Performing the same basic operations in the same order, but with shorter code and fewer jumps, it's hard not to be faster.

It might be measurably faster, or it might be an insignificant change that's not measurable, but barring some bizarre alignment or cache aliasing effect, the chance of it being *slower* is negligible.

Speaking pedantically, you're right. But as a practical matter, it's very unlikely, and what makes it truly insignificant is that it's not really a problem even if I'm wrong and the code *is* slower.

As you said, size is more important than speed, and I did, at your request, benchmark that. I'm just trying to make the sort of changes that improve *both*.

If you have a realistic concern that the patches degrade speed, I can put in a few hours of work to put the different versions into a test harness and measure it accurately.

But if this is just a pro forma observation that estimates aren't perfectly reliable, it's not worth the effort.

[]

Readability and correctness are probably more important than runtime performance here.