From owner-freebsd-bugs@freebsd.org Tue Mar 7 21:02:37 2017 Return-Path: Delivered-To: freebsd-bugs@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 8FE28D02CEA for ; Tue, 7 Mar 2017 21:02:37 +0000 (UTC) (envelope-from bugzilla-noreply@freebsd.org) Received: from kenobi.freebsd.org (kenobi.freebsd.org [IPv6:2001:1900:2254:206a::16:76]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 65F0B11AE for ; Tue, 7 Mar 2017 21:02:37 +0000 (UTC) (envelope-from bugzilla-noreply@freebsd.org) Received: from bugs.freebsd.org ([127.0.1.118]) by kenobi.freebsd.org (8.15.2/8.15.2) with ESMTP id v27L2baA095126 for ; Tue, 7 Mar 2017 21:02:37 GMT (envelope-from bugzilla-noreply@freebsd.org) From: bugzilla-noreply@freebsd.org To: freebsd-bugs@FreeBSD.org Subject: [Bug 217618] Enhance hash function in ip_fw_table_algo.c for flow:hash Date: Tue, 07 Mar 2017 21:02:37 +0000 X-Bugzilla-Reason: AssignedTo X-Bugzilla-Type: new X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: Base System X-Bugzilla-Component: kern X-Bugzilla-Version: 11.0-STABLE X-Bugzilla-Keywords: X-Bugzilla-Severity: Affects Some People X-Bugzilla-Who: lutz@donnerhacke.de X-Bugzilla-Status: New X-Bugzilla-Resolution: X-Bugzilla-Priority: --- X-Bugzilla-Assigned-To: freebsd-bugs@FreeBSD.org X-Bugzilla-Flags: X-Bugzilla-Changed-Fields: bug_id short_desc product version rep_platform op_sys bug_status bug_severity priority component assigned_to reporter Message-ID: Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Bugzilla-URL: https://bugs.freebsd.org/bugzilla/ Auto-Submitted: auto-generated MIME-Version: 1.0 X-BeenThere: freebsd-bugs@freebsd.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: Bug reports List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 07 Mar 2017 21:02:37 -0000 https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=3D217618 Bug ID: 217618 Summary: Enhance hash function in ip_fw_table_algo.c for flow:hash Product: Base System Version: 11.0-STABLE Hardware: Any OS: Any Status: New Severity: Affects Some People Priority: --- Component: kern Assignee: freebsd-bugs@FreeBSD.org Reporter: lutz@donnerhacke.de While experimenting with some extentions for flow tables, I noticed, that t= he hash function does not separate distinct entries clearly enough. Larger flo= ws tables do reflect external structures and tend to heavily cluster the entri= es on a few hash values (i.e. src-ip and dst-ip are varied both within a netwo= rk). Current code does not even include the protocol number. So I propose to reuse the existing crc32 function for this small amount of data. The probability to have a uniform distributed hash key increases dramatically and overall the lookup is faster than step through a list of entries having the same key. Note: This code depends on a zeroed struct fhashentry*, because it does not select the individual fields. All functions despite ta_prepare_del_fhash do clean the structure. I'm not sure, if this is can cause a problem. --- sys/netpfil/ipfw/ip_fw_table_algo.c (revision 314807) +++ sys/netpfil/ipfw/ip_fw_table_algo.c (working copy) @@ -3163,7 +3176,7 @@ { uint32_t i; - i =3D (f->dip.s_addr) ^ (f->sip.s_addr) ^ (f->e.dport) ^ (f->e.spor= t); + i =3D crc32(f, sizeof(*f)); return (i % (hsize - 1)); } @@ -3173,11 +3186,7 @@ { uint32_t i; - i =3D (f->dip6.__u6_addr.__u6_addr32[2]) ^ - (f->dip6.__u6_addr.__u6_addr32[3]) ^ - (f->sip6.__u6_addr.__u6_addr32[2]) ^ - (f->sip6.__u6_addr.__u6_addr32[3]) ^ - (f->e.dport) ^ (f->e.sport); + i =3D crc32(f, sizeof(*f)); return (i % (hsize - 1)); } --=20 You are receiving this mail because: You are the assignee for the bug.=