From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <systemtap-return-18899-listarch-systemtap=sources.redhat.com@sourceware.org>
Received: (qmail 28960 invoked by alias); 31 Dec 2011 01:33:03 -0000
Received: (qmail 28953 invoked by uid 22791); 31 Dec 2011 01:33:02 -0000
X-SWARE-Spam-Status: No, hits=-2.8 required=5.0	tests=ALL_TRUSTED,AWL,BAYES_00
X-Spam-Check-By: sourceware.org
Received: from localhost (HELO sourceware.org) (127.0.0.1)    by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Sat, 31 Dec 2011 01:32:50 +0000
From: "fche at redhat dot com" <sourceware-bugzilla@sourceware.org>
To: systemtap@sourceware.org
Subject: [Bug runtime/13546] New: improve map hashing
Date: Sat, 31 Dec 2011 01:37:00 -0000
X-Bugzilla-Reason: AssignedTo
X-Bugzilla-Type: new
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: systemtap
X-Bugzilla-Component: runtime
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: fche at redhat dot com
X-Bugzilla-Status: NEW
X-Bugzilla-Priority: P2
X-Bugzilla-Assigned-To: systemtap at sourceware dot org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Changed-Fields:
Message-ID: <bug-13546-6586@http.sourceware.org/bugzilla/>
X-Bugzilla-URL: http://sourceware.org/bugzilla/
Auto-Submitted: auto-generated
Content-Type: text/plain; charset="UTF-8"
MIME-Version: 1.0
Mailing-List: contact systemtap-help@sourceware.org; run by ezmlm
Precedence: bulk
List-Id: <systemtap.sourceware.org>
List-Subscribe: <mailto:systemtap-subscribe@sourceware.org>
List-Post: <mailto:systemtap@sourceware.org>
List-Help: <mailto:systemtap-help@sourceware.org>, <http://sourceware.org/lists.html#faqs>
Sender: systemtap-owner@sourceware.org
X-SW-Source: 2011-q4/txt/msg00432.txt.bz2

http://sourceware.org/bugzilla/show_bug.cgi?id=13546

             Bug #: 13546
           Summary: improve map hashing
           Product: systemtap
           Version: unspecified
            Status: NEW
          Severity: normal
          Priority: P2
         Component: runtime
        AssignedTo: systemtap@sourceware.org
        ReportedBy: fche@redhat.com
    Classification: Unclassified


The runtime/map* functions have several weaknesses w.r.t. hashing
that we should improve.

1) HASH_TABLE_BITS/SIZE should probably be a function of MAXMAPENTRIES.
2) str_hash() should be more hashy.  It looks rather wimpy.
3) With deliberate hash-collision-inducing data conceivably fed to stap,
   we should investigate salting the map FOO_hash functions with some
   runtime-random value, such as a few bytes collected at startup time with
   get_random_bytes(), as in

static unsigned long stap_hash_seed; /* init during module startup */
static unsigned int int64_hash (const int64_t v)
{
        return (unsigned int)hash_long (((unsigned long)v) ^ stap_hash_seed,
                                        HASH_TABLE_BITS);
}
/* and similarly for str_hash */

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug.