[PATCH] Fix hashing of vectors to run in bounded time

[PATCH] Fix hashing of vectors to run in bounded time

[Mark H Weaver]

[-- Attachment #1: Type: text/plain, Size: 443 bytes --]

Hello all,

The 'equal?' hash function in Guile 2.0 uses unbound amounts of runtime
in many cases involving nested vectors, and can go into an infinite loop
for cyclic data structures involving vectors.  For example, it will
always do a complete traversal of a nested tree of vectors of length 5
or less.

To fix this, I'd like to apply this patch to stable-2.0.
What do you think?

Comments and suggestions welcome.

    Thanks,
      Mark



[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: [PATCH] Fix hashing of vectors to run in bounded time --]
[-- Type: text/x-patch, Size: 2446 bytes --]

From 0f1debcb9ac9f350c6bab8fea91e4c7dca0fdd68 Mon Sep 17 00:00:00 2001
From: Mark H Weaver <mhw@netris.org>
Date: Sat, 11 Jan 2014 10:18:40 -0500
Subject: [PATCH] Fix hashing of vectors to run in bounded time.

* libguile/hash.c (scm_hasher): In vector case, do nothing if d is 0.
  Make sure to recurse with a reduced d.  Move the loop out of the 'if'.
---
 libguile/hash.c |   55 +++++++++++++++++++++++++++++--------------------------
 1 files changed, 29 insertions(+), 26 deletions(-)

diff --git a/libguile/hash.c b/libguile/hash.c
index 8b00a0c..39766b6 100644
--- a/libguile/hash.c
+++ b/libguile/hash.c
@@ -1,5 +1,5 @@
 /* Copyright (C) 1995, 1996, 1997, 2000, 2001, 2003, 2004, 2006, 2008,
- *   2009, 2010, 2011, 2012 Free Software Foundation, Inc.
+ *   2009, 2010, 2011, 2012, 2014 Free Software Foundation, Inc.
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public License
@@ -228,31 +228,34 @@ scm_hasher(SCM obj, unsigned long n, size_t d)
       return scm_i_struct_hash (obj, n, d);
     case scm_tc7_wvect:
     case scm_tc7_vector:
-      {
-	size_t len = SCM_SIMPLE_VECTOR_LENGTH (obj);
-	if (len > 5)
-	  {
-	    size_t i = d/2;
-	    unsigned long h = 1;
-	    while (i--)
-	      {
-		SCM elt = SCM_SIMPLE_VECTOR_REF (obj, h % len);
-		h = ((h << 8) + (scm_hasher (elt, n, 2))) % n;
-	      }
-	    return h;
-	  }
-	else
-	  {
-	    size_t i = len;
-	    unsigned long h = (n)-1;
-	    while (i--)
-	      {
-		SCM elt = SCM_SIMPLE_VECTOR_REF (obj, h % len);
-		h = ((h << 8) + (scm_hasher (elt, n, d/len))) % n;
-	      }
-	    return h;
-	  }
-      }
+      if (d > 0)
+        {
+          size_t len, i, d2;
+          unsigned long h;
+
+          len = SCM_SIMPLE_VECTOR_LENGTH (obj);
+          if (len > 5)
+            {
+              i = d / 2;
+              h = 1;
+              d2 = SCM_MAX (2, d - 1);
+            }
+          else
+            {
+              i = len;
+              h = n - 1;
+              d2 = (d - 1) / len;
+            }
+
+          while (i--)
+            {
+              SCM elt = SCM_SIMPLE_VECTOR_REF (obj, h % len);
+              h = ((h << 8) + (scm_hasher (elt, n, d2))) % n;
+            }
+          return h;
+        }
+      else
+        return 1;
     case scm_tcs_cons_imcar: 
     case scm_tcs_cons_nimcar:
       if (d) return (scm_hasher (SCM_CAR (obj), n, d/2)
-- 
1.7.5.4

Re: [PATCH] Fix hashing of vectors to run in bounded time

[Ludovic Courtès]

Mark H Weaver <mhw@netris.org> skribis:

> The 'equal?' hash function in Guile 2.0 uses unbound amounts of runtime
> in many cases involving nested vectors, and can go into an infinite loop
> for cyclic data structures involving vectors.  For example, it will
> always do a complete traversal of a nested tree of vectors of length 5
> or less.

Good catch!

> From 0f1debcb9ac9f350c6bab8fea91e4c7dca0fdd68 Mon Sep 17 00:00:00 2001
> From: Mark H Weaver <mhw@netris.org>
> Date: Sat, 11 Jan 2014 10:18:40 -0500
> Subject: [PATCH] Fix hashing of vectors to run in bounded time.
>
> * libguile/hash.c (scm_hasher): In vector case, do nothing if d is 0.
>   Make sure to recurse with a reduced d.  Move the loop out of the 'if'.

Looks good to me.

Thanks,
Ludo’.