GNU bug report logs - #29132
[PATCH] system: vm: Use 2^32 - 1 as hash size.

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 29132 in the body.
You can then email your comments to 29132 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Mathieu Othacehe <m.othacehe <at> gmail.com>
To: guix-patches <at> gnu.org
Cc: Mathieu Othacehe <m.othacehe <at> gmail.com>
Subject: [PATCH] system: vm: Use 2^32 - 1 as hash size.
Date: Fri,  3 Nov 2017 13:49:04 +0100

* gnu/system/vm.scm (operating-system-uuid): Use 2^32 - 1 instead of
  2^32 as hash size.

On some 32 bit system (ARM for example), 2^32 exceeds hash max
size (ULONG_MAX = 2^32 - 1).
---
 gnu/system/vm.scm | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/gnu/system/vm.scm b/gnu/system/vm.scm
index 3127b30..4424608 100644
--- a/gnu/system/vm.scm
+++ b/gnu/system/vm.scm
@@ -372,13 +372,13 @@ TYPE (one of 'iso9660 or 'dce).  Return a UUID object."
       (bytevector->uuid
        (uint-list->bytevector
         (list (hash file-system-type
-                    (expt 2 32))
+                    (- (expt 2 32) 1))
               (hash (operating-system-host-name os)
-                    (expt 2 32))
+                    (- (expt 2 32) 1))
               (hash (operating-system-services os)
-                    (expt 2 32))
+                    (- (expt 2 32) 1))
               (hash (operating-system-file-systems os)
-                    (expt 2 32)))
+                    (- (expt 2 32) 1)))
         (endianness little)
         4)
        type)))
-- 
2.7.4

Message #8 received at 29132 <at> debbugs.gnu.org (full text, mbox):

From: ludo <at> gnu.org (Ludovic Courtès)
To: Mathieu Othacehe <m.othacehe <at> gmail.com>
Cc: 29132 <at> debbugs.gnu.org
Subject: Re: [bug#29132] [PATCH] system: vm: Use 2^32 - 1 as hash size.
Date: Sun, 05 Nov 2017 21:48:52 +0100

Hello!

Mathieu Othacehe <m.othacehe <at> gmail.com> skribis:

> * gnu/system/vm.scm (operating-system-uuid): Use 2^32 - 1 instead of
>   2^32 as hash size.
>
> On some 32 bit system (ARM for example), 2^32 exceeds hash max
> size (ULONG_MAX = 2^32 - 1).
> ---
>  gnu/system/vm.scm | 8 ++++----
>  1 file changed, 4 insertions(+), 4 deletions(-)
>
> diff --git a/gnu/system/vm.scm b/gnu/system/vm.scm
> index 3127b30..4424608 100644
> --- a/gnu/system/vm.scm
> +++ b/gnu/system/vm.scm
> @@ -372,13 +372,13 @@ TYPE (one of 'iso9660 or 'dce).  Return a UUID object."
>        (bytevector->uuid
>         (uint-list->bytevector
>          (list (hash file-system-type
> -                    (expt 2 32))
> +                    (- (expt 2 32) 1))

‘hash’ is documented like this:

  -- Scheme Procedure: hash key size
  -- Scheme Procedure: hashq key size
  -- Scheme Procedure: hashv key size
  -- C Function: scm_hash (key, size)
  -- C Function: scm_hashq (key, size)
  -- C Function: scm_hashv (key, size)
      Return a hash value for KEY.  This is a number in the range 0 to
      SIZE-1, which is suitable for use in a hash table of the given
      SIZE.

So I take it that you always get something in the range 0–2³²-1, no?

Ludo’.

Message #11 received at 29132 <at> debbugs.gnu.org (full text, mbox):

From: Mathieu Othacehe <m.othacehe <at> gmail.com>
To: Ludovic Courtès <ludo <at> gnu.org>
Cc: 29132 <at> debbugs.gnu.org
Subject: Re: [bug#29132] [PATCH] system: vm: Use 2^32 - 1 as hash size.
Date: Sun, 05 Nov 2017 21:56:13 +0100

Hey Ludo,

> So I take it that you always get something in the range 0–2³²-1, no?

Well I agree, but looking to hash code, we have :

--8<---------------cut here---------------start------------->8---
#define FUNC_NAME s_scm_hash
{
  unsigned long sz = scm_to_unsigned_integer (size, 1, ULONG_MAX);
--8<---------------cut here---------------end--------------->8---

And 2^32 > ULONG_MAX == 2^32 - 1 on ARM.

This results in this exception :

--8<---------------cut here---------------start------------->8---
scheme@(guile-user)> (hash 'test (expt 2 32))
ERROR: In procedure hash:
ERROR: Value out of range 1 to 4294967295: 4294967296
--8<---------------cut here---------------end--------------->8---

Mathieu

Message #14 received at 29132 <at> debbugs.gnu.org (full text, mbox):

From: ludo <at> gnu.org (Ludovic Courtès)
To: Mathieu Othacehe <m.othacehe <at> gmail.com>
Cc: 29132 <at> debbugs.gnu.org
Subject: Re: [bug#29132] [PATCH] system: vm: Use 2^32 - 1 as hash size.
Date: Mon, 06 Nov 2017 09:41:09 +0100

Mathieu Othacehe <m.othacehe <at> gmail.com> skribis:

> Hey Ludo,
>
>> So I take it that you always get something in the range 0–2³²-1, no?
>
> Well I agree, but looking to hash code, we have :
>
> #define FUNC_NAME s_scm_hash
> {
>   unsigned long sz = scm_to_unsigned_integer (size, 1, ULONG_MAX);

Oh, got it.  Well, OK for the patch!

Thank you,
Ludo’.

Message #17 received at 29132 <at> debbugs.gnu.org (full text, mbox):

From: Mathieu Othacehe <m.othacehe <at> gmail.com>
To: Ludovic Courtès <ludo <at> gnu.org>
Cc: 29132 <at> debbugs.gnu.org
Subject: Re: [bug#29132] [PATCH] system: vm: Use 2^32 - 1 as hash size.
Date: Mon, 06 Nov 2017 20:04:16 +0100

> Oh, got it.  Well, OK for the patch!

Thanks, pushed as b1a30793477c705a136546798d8e1d27802dd4b7.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.