From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Mark H Weaver Newsgroups: gmane.lisp.guile.devel Subject: [PATCH] Fix hashing of vectors to run in bounded time Date: Sat, 11 Jan 2014 10:30:54 -0500 Message-ID: <87vbxqv8lt.fsf@netris.org> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" X-Trace: ger.gmane.org 1389454424 25880 80.91.229.3 (11 Jan 2014 15:33:44 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sat, 11 Jan 2014 15:33:44 +0000 (UTC) To: guile-devel@gnu.org Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Sat Jan 11 16:33:48 2014 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1W20ZG-0005RY-DL for guile-devel@m.gmane.org; Sat, 11 Jan 2014 16:33:46 +0100 Original-Received: from localhost ([::1]:34440 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1W20ZG-0003EN-0f for guile-devel@m.gmane.org; Sat, 11 Jan 2014 10:33:46 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:60190) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1W20Z8-0003EA-C8 for guile-devel@gnu.org; Sat, 11 Jan 2014 10:33:44 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1W20Z2-0002b6-4B for guile-devel@gnu.org; Sat, 11 Jan 2014 10:33:38 -0500 Original-Received: from world.peace.net ([96.39.62.75]:43924) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1W20Z2-0002ZC-0L for guile-devel@gnu.org; Sat, 11 Jan 2014 10:33:32 -0500 Original-Received: from c-98-217-64-74.hsd1.ma.comcast.net ([98.217.64.74] helo=yeeloong) by world.peace.net with esmtpsa (TLS1.0:DHE_RSA_AES_128_CBC_SHA1:16) (Exim 4.72) (envelope-from ) id 1W20YV-0007wa-UY; Sat, 11 Jan 2014 10:33:00 -0500 X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-Received-From: 96.39.62.75 X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:16799 Archived-At: --=-=-= Content-Type: text/plain 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 --=-=-= Content-Type: text/x-patch Content-Disposition: inline; filename=0001-Fix-hashing-of-vectors-to-run-in-bounded-time.patch Content-Description: [PATCH] Fix hashing of vectors to run in bounded time >From 0f1debcb9ac9f350c6bab8fea91e4c7dca0fdd68 Mon Sep 17 00:00:00 2001 From: Mark H Weaver 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 --=-=-=--