Re: [PATCH] lib/uuid.c: eliminate uuid_[bl]e_index arrays

[Andy Shevchenko]

On Tue, 2016-05-31 at 16:31 -0400, George Spelvin wrote:
> From a0d084b1225f2efcf4b5c81871c9c446155b9b13 Mon Sep 17 00:00:00 2001
> From: George Spelvin <linux@xxxxxxxxxxxxxxxxxxx>
> Date: Tue, 31 May 2016 16:00:22 -0400
> Subject: [PATCH] lib/uuid.c: eliminate uuid_[bl]e_index arrays

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.

> 
> 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().

Oh, it makes readability worse.

> ÂÂ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

x86_32? arm?

> 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.
> 

--- a/include/linux/uuid.h
> +++ b/include/linux/uuid.h
> @@ -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);
> diff --git a/lib/uuid.c b/lib/uuid.c
> index e116ae5f..8a439caf 100644
> --- a/lib/uuid.c
> +++ b/lib/uuid.c
> @@ -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 */
> +};

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

> Â
> Â/***************************************************************
> Â * 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])

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

> Â{
> -	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;

How hex2bin is better here? We have validation done, no need to repeat.
So, I suggest not to touch this piece of code.

> --- a/lib/vsprintf.c
> +++ b/lib/vsprintf.c
> @@ -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];

If you wish you may convert this to hex_byte_pack{,upper}().


-- 
Andy Shevchenko <andriy.shevchenko@xxxxxxxxxxxxxxx>
Intel Finland Oy