lib/vsprintf.c: Further simplify uuid_string()

Okay. lkml and commenters on recent patches added to Cc:.

To those just joining, I had a couple of local patches I had made to lib/vsprintf.c:uuid_string() which had been sitting around ignored due to not knowing who to submit them to.

Then I noticed (merge conflicts while rebasing my local patches) that Andy was working on the area and sent them to him.

[Aside: Ted, I agree that whoever decided to make UUIDs non-universal by introducing an ambiguous parse is richly deserving of scorn.]

Wow, I didn't expect that! I thought the improvement was obvious in pretty much every possible way, which is why I didn't include much explanation. I'll explain my thinking in more detail here; could you tell me where you disagree?

I agree with you that such "support" code shouldn't try to micro-optimize its own performance at the expense of static resources (code size, large tables), because CPU resources like L1 cache, TLB, and branch predictor slots should be reserved for the hot code.

It's not that we don't care about speed, but given its infrequent use we care even more about slowing down the *rest* of the kernel.

That's exactly why I headlined the space savings rather than the performance gains.

As an example of a less useful "optimization", it's possible to unroll the loop twice and print 16 bits per iteration. You could even shrink the tables to 8 bytes each, since since odd entries can be derived from even entries by complementing the low-order bit:

 	for (i = 0; i < 8; i++) {
		p = hex_byte_pack(p, addr[index[i]]);
		p = hex_byte_pack(p, addr[index[i]^1]);
		if ((unsigned)i - 1 < 4)
			*p++ = '-';
	}

There are two optimzations here:

1) Replacing the "uc" boolean with a pointer.

index 7332a5d7..231cf6d3 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)) {
 	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:

This seems like an obvious win. It's performing exactly the same data memory accesses as the conditional form (the tables it uses are the tables which the hex_byte_pack() macros use internally), while reducing the code size both statically and dynamically.

Dynamically, it eliminates 16 conditional branches. The only extra reesource consumed is the "hex" pointer variable which is larger than the "uc" boolean, but as it's one register either way, that's nothing.

So it's saving L1I space and a branch predictor entry as well as being faster, all without making the code any harder to understand.

I really don't see any downside at all.

2) Inverting the order of formatting.

This is a more complex change. Rather than format the UUID in output order, and use a table to get the permuted input byte order, I invert the table to list the output position for each input byte.

Thus, the input is read in order and the output is written out of order.

index 231cf6d3..aa6135cd 100644
@@ -1313,38 +1313,35 @@ 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;
+	/* Offset in uuid[] where each byte is printed, two cases. */
+	static const u8 be[16] = {0,2,4,6,9,11,14,16,19,21,24,26,28,30,32,34};
+	static const u8 le[16] = {6,4,2,0,11,9,16,14,19,21,24,26,28,30,32,34};
+	const u8 *index = be;
 	const char *hex = hex_asc;
 
 	switch (*(++fmt)) {
 	case 'L':
 		hex = hex_asc_upper;	/* fall-through */
 	case 'l':
-		index = uuid_le_index;
+		index = le;
 		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 + index[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);
 }

When I first wrote it, it didn't increase table size at all, since it was just swapping one set of tables for another.

Now that you're sharing the tables, it's possible to *reduce* table size. My be[] table is identical to your si[] table in __uuid_to_bin(), and using my le[] table there would let you eliminate uuid_le_index[] and uuid_be_index[] completely, for a net 16 byte saving.

More significantly, it decreases both static and dynamic code size by trading the switch() for the four explicit stores of the '-' punctuation.

Most of the work done by the switch() is folded into the table showing which output positions to reserve for punctuation.

Again, the change is not only a speed boost, but speeds up the rest of the kernel by reducing cache and branch predictor use.

I agree it's harder to understand, precisely because the table does two things at once, but not hugely so; the comments resolve any questions the reader might have. In general, subtlety is a problem when it affects a large area of code (RCU being the poster child); this is a self-contained micro-optimization which doesn't affect the understandability or maintainability of the kernel as a whole, and someone who does care about this particular fucntion doesn't have to read very much to figure it out.

From: George Spelvin <[email protected]>
Date: Tue, 31 May 2016 16:00:22 -0400
Subject: [PATCH] lib/uuid.c: eliminate uuid_[bl]e_index arrays

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

uuid_[bl]e_index were EXPORT_SYMBOLed for no obvious reason; there are no users outside of lib/. The replacement uuid_[bl]e_pos arrays are not exported pending finding a need.

The arrays are combined in one contiguous uuid_byte_pos[2][16] array as a micro-optimization for uuid_string(). Choosing between the two can be done by adding 16 rather than loading a second full-word address.

x86-64 code size reductions:
uuid_string: was 228 bytes, now 134
__uuid_to_bin: was 119 bytes, now 85

Initialized data is also reduced by 16 bytes.

---
Here's a patch implementing the suggestion I made earlier. This reduces code size, data size, and run time for input and output of UUIDs.

This patch is on top of the upper/lower case hex optimization for lib/vsprintf.c I sent earlier. If you don't have it, just ignore the merge conflicts in uuid_string() and take the "after" version.

 include/linux/uuid.h |  6 ++++--
 lib/uuid.c           | 24 ++++++++++--------------
 lib/vsprintf.c       | 32 +++++++++++++-------------------
 3 files changed, 27 insertions(+), 35 deletions(-)

index 2d095fc6..882d9ada 100644
@@ -41,8 +41,10 @@ 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_byte_pos[2][16];
+#define uuid_be_pos (uuid_byte_pos[0])
+#define uuid_le_pos (uuid_byte_pos[1])
 
 int uuid_le_to_bin(const char *uuid, uuid_le *u);
 int uuid_be_to_bin(const char *uuid, uuid_be *u);

index e116ae5f..8a439caf 100644
@@ -21,10 +21,10 @@
 #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);
+const u8 uuid_byte_pos[2][16] = {
+	{0,2,4,6,9,11,14,16,19,21,24,26,28,30,32,34},	/* uuid_be_pos */
+	{6,4,2,0,11,9,16,14,19,21,24,26,28,30,32,34}	/* uuid_le_pos */
+};
 
 /***************************************************************
  * Random UUID interface

@@ -97,32 +97,28 @@ 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])
+static int __uuid_to_bin(const char uuid[36], __u8 b[16], const u8 si[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++)
+		if (hex2bin(b + i, uuid + si[i], 1) < 0)
+			return -EINVAL;
 
 	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..44faddb1 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':
+		pos = uuid_le_pos;
+		break;
 	case 'L':
-		hex = hex_asc_upper;	/* fall-through */
-	case 'l':
-		index = uuid_le_index;
-		break;
+		pos = uuid_le_pos;	/* Fall-through */
 	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

[]

I haven't looked up the full original discussion to see if this is a point on which I disagree with Linus, but I find it useful for documentation:
this is not just a pointer to "some" bytes, this is a pointer to [LENGTH] bytes. It's a reminder to the caller that they'd better pass in a buffer of the required size.

Obviosuly, it makes no actual difference to the compiler.

C99 actually has a way to say this explicitly to the compiler, but the syntax is ugly:

static int __uuid_to_bin(const char uuid[static 36], __u8 b[static 16],

	const u8 si[static 16])

(This includes the effect of __attribute__((nonnull)).)

Further discussion at
https://hamberg.no/erlend/posts/2013-02-18-static-array-indices.html
https://stackoverflow.com/questions/3430315/what-is-the-purpose-of-static-keyword-in-array-parameter-of-function-like-char

(FWIW, another two style points which I disagre with Linus about are that I don't mind "sizeof variable" without parens, and that I don't mind using a bare "0" for a null pointer. More substantially, I like "bool" a lot more than Linus does.)

That function follows existing UUID API. Since we have now it consolidated in one place someone may fix it eventually.

Refer to this discussion as well:
http://www.spinics.net/lists/linux-efi/msg08105.html

Andy Shevchenko <[email protected]>
Intel Finland Oy

Just to clarify:

int foo(char *);
int foo(char *floccinaucinihilipilifcation);
int foo(char *p);
int foo(char p[]);
int foo(char []);
int foo(char p[1]);
int foo(char p[999999999]);

are all the exact same declaration. There is no API change; the only difference is stylistic. (Try it! Copy them to a .c file and compile it. Observe the lack of conflicting declaration warnings.)

Although the compiler doesn't care, I happen to prefer to include parameter names for the benefit of someone reading the header files.

For the same reason, if the pointer is to the start of an array with definite length (that's not 1), I prefer to use the array form showing that length.

But it's a matter of style, not substance, either way.

I believe the substantive bit of the argument is the ability to misunderstand that sizeof(argument with size char[999]) is not 999 but is sizeof(*).

I can't find it. Please take more care when referring to patches, to prevent mistakes from being made.

In any case I would to hear from people before going with them. Rasmus, perhaps you can comment on the subject?

Andy Shevchenko <[email protected]>
Intel Finland Oy

There is a tool called git send-email. It would be better to use it directly.

Also, please fix Cc list (I got bounce response) and add some key people like Rasmus.

Oh, it makes readability worse.

x86_32? arm?

--- a/include/linux/uuid.h

And what prevent you to use two arrays? Above looks not good for reading and error prone for users.

This one... Let's keep a prototype as is for now.

Andy Shevchenko <[email protected]>
Intel Finland Oy