Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1410607 > unrolled thread

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

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  [PATCH] lib/uuid.c: eliminate uuid_[bl]e_index arrays "George Spelvin" <linux@sciencehorizons.net> - 2016-05-31 22:40 +0200
    Re: [PATCH] lib/uuid.c: eliminate uuid_[bl]e_index arrays Joe Perches <joe@perches.com> - 2016-05-31 23:40 +0200
      Re: [PATCH] lib/uuid.c: eliminate uuid_[bl]e_index arrays "George Spelvin" <linux@sciencehorizons.net> - 2016-06-01 00:10 +0200
      Re: [PATCH] lib/uuid.c: eliminate uuid_[bl]e_index arrays Andy Shevchenko <andriy.shevchenko@linux.intel.com> - 2016-06-01 14:40 +0200
        Re: [PATCH] lib/uuid.c: eliminate uuid_[bl]e_index arrays "George Spelvin" <linux@sciencehorizons.net> - 2016-06-01 17:10 +0200
          Re: [PATCH] lib/uuid.c: eliminate uuid_[bl]e_index arrays Joe Perches <joe@perches.com> - 2016-06-02 18:50 +0200
    Re: [PATCH] lib/uuid.c: eliminate uuid_[bl]e_index arrays Andrew Morton <akpm@linux-foundation.org> - 2016-06-01 22:00 +0200
      Re: [PATCH] lib/uuid.c: eliminate uuid_[bl]e_index arrays Andy Shevchenko <andriy.shevchenko@linux.intel.com> - 2016-06-01 22:20 +0200
    Re: [PATCH] lib/uuid.c: eliminate uuid_[bl]e_index arrays Andy Shevchenko <andriy.shevchenko@linux.intel.com> - 2016-06-03 13:20 +0200

#1410607 — [PATCH] lib/uuid.c: eliminate uuid_[bl]e_index arrays

From a0d084b1225f2efcf4b5c81871c9c446155b9b13 Mon Sep 17 00:00:00 2001
From: George Spelvin <linux@sciencehorizons.net>
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.

Signed-off-by: George Spelvin <linux@horizon.com>
---
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(-)

diff --git a/include/linux/uuid.h b/include/linux/uuid.h
index 2d095fc6..882d9ada 100644
--- 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 */
+};
 
 /***************************************************************
  * 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);
diff --git a/lib/vsprintf.c b/lib/vsprintf.c
index 4ee07e89..44faddb1 100644
--- 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];
 	}
-
-	*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

[toc] | [next] | [standalone]

#1410646

On Tue, 2016-05-31 at 16:31 -0400, George Spelvin wrote:
> 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.
[]
> diff --git a/lib/uuid.c b/lib/uuid.c
[]
> @@ -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])

Functions with sized array arguments are generally undesired.

Linus once wrote: (http://comments.gmane.org/gmane.linux.kernel/2031400)

    array arguments in C don't
    actually exist. Sadly, compilers accept it for various bad historical
    reasons, and silently turn it into just a pointer argument. There are
    arguments for them, but they are from weak minds.

Perhaps this would be better using simple pointers and without the __

static int __uuid_to_bin(const char *uuid, u8 *b, const u8 *si)

[toc] | [prev] | [next] | [standalone]

#1410661

> Functions with sized array arguments are generally undesired.
> 
> Linus once wrote: (http://comments.gmane.org/gmane.linux.kernel/2031400)
> 
>     array arguments in C don't
>    actually exist. Sadly, compilers accept it for various bad historical
>    reasons, and silently turn it into just a pointer argument. There are
>    arguments for them, but they are from weak minds.
>
> Perhaps this would be better using simple pointers and without the __
>
> static int __uuid_to_bin(const char *uuid, u8 *b, const u8 *si)

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

[toc] | [prev] | [next] | [standalone]

#1411158

On Tue, 2016-05-31 at 14:36 -0700, Joe Perches wrote:
> On Tue, 2016-05-31 at 16:31 -0400, George Spelvin wrote:
> > 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.
> []
> > diff --git a/lib/uuid.c b/lib/uuid.c
> []
> > @@ -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])
> 
> Functions with sized array arguments are generally undesired.

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

> 
> Linus once wrote: (http://comments.gmane.org/gmane.linux.kernel/203140
> 0)
> 
>     array arguments in C don't
>     actually exist. Sadly, compilers accept it for various bad
> historical
>     reasons, and silently turn it into just a pointer argument. There
> are
>     arguments for them, but they are from weak minds.
> 
> Perhaps this would be better using simple pointers and without the __
> 
> static int __uuid_to_bin(const char *uuid, u8 *b, const u8 *si)
> 

-- 
Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Intel Finland Oy

[toc] | [prev] | [next] | [standalone]

#1411303

On Wed, 01 Jun 2016 at 15:32:47, Andy Shevchenko wrote:
> On Tue, 2016-05-31 at 14:36 -0700, Joe Perches wrote:
>> On Tue, 2016-05-31 at 16:31 -0400, George Spelvin wrote:
>>> -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])
>> 
>> Functions with sized array arguments are generally undesired.
> 
> That function follows existing UUID API. Since we have now it
> consolidated in one place someone may fix it eventually.

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.

[toc] | [prev] | [next] | [standalone]

#1412426

On Wed, 2016-06-01 at 11:07 -0400, George Spelvin wrote:
> On Wed, 01 Jun 2016 at 15:32:47, Andy Shevchenko wrote:
> > On Tue, 2016-05-31 at 14:36 -0700, Joe Perches wrote:
> > > On Tue, 2016-05-31 at 16:31 -0400, George Spelvin wrote:
> > > > -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])
> > > Functions with sized array arguments are generally undesired.
> > That function follows existing UUID API. Since we have now it
> > consolidated in one place someone may fix it eventually.
> 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(*).

[toc] | [prev] | [next] | [standalone]

#1411509

On 31 May 2016 16:31:22 -0400 "George Spelvin" <linux@sciencehorizons.net> wrote:

> This patch is on top of the upper/lower case hex optimization for
> lib/vsprintf.c I sent earlier.

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

[toc] | [prev] | [next] | [standalone]

#1411525

On Wed, 2016-06-01 at 12:58 -0700, Andrew Morton wrote:
> On 31 May 2016 16:31:22 -0400 "George Spelvin" <linux@sciencehorizons.
> net> wrote:
> 
> > This patch is on top of the upper/lower case hex optimization for
> > lib/vsprintf.c I sent earlier.
> 
> 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 <andriy.shevchenko@linux.intel.com>
Intel Finland Oy

[toc] | [prev] | [next] | [standalone]

#1413136

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@sciencehorizons.net>
> 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@linux.intel.com>
Intel Finland Oy

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web