From owner-freebsd-stable@FreeBSD.ORG  Fri May 16 04:33:18 2008
Return-Path: <owner-freebsd-stable@FreeBSD.ORG>
Delivered-To: freebsd-stable@freebsd.org
Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34])
	by hub.freebsd.org (Postfix) with ESMTP id 54CFF1065670;
	Fri, 16 May 2008 04:33:18 +0000 (UTC)
	(envelope-from bu7cher@yandex.ru)
Received: from smtp6.yandex.ru (smtp6.yandex.ru [213.180.200.197])
	by mx1.freebsd.org (Postfix) with ESMTP id 30F468FC2E;
	Fri, 16 May 2008 04:33:16 +0000 (UTC)
	(envelope-from bu7cher@yandex.ru)
Received: from ns.kirov.so-cdu.ru ([77.72.136.145]:47811 "EHLO [127.0.0.1]"
	smtp-auth: "bu7cher" TLS-CIPHER: "DHE-RSA-AES256-SHA keybits 256/256
	version TLSv1/SSLv3" TLS-PEER-CN1: <none>) by mail.yandex.ru
	with ESMTP id S5473464AbYEPEdO (ORCPT
	<rfc822;freebsd-ipfw@freebsd.org> + 2 others);
	Fri, 16 May 2008 08:33:14 +0400
X-Yandex-Spam: 1 
X-Yandex-Front: smtp6
X-Yandex-TimeMark: 1210912394
X-MsgDayCount: 5
X-Comment: RFC 2476 MSA function at smtp6.yandex.ru logged sender identity as:
	bu7cher
Message-ID: <482D0E87.6000003@yandex.ru>
Date: Fri, 16 May 2008 08:33:11 +0400
From: "Andrey V. Elsukov" <bu7cher@yandex.ru>
User-Agent: Mozilla Thunderbird 1.5 (FreeBSD/20051231)
MIME-Version: 1.0
To: "Bruce M. Simpson" <bms@FreeBSD.org>
References: <04EA1C34-AB7D-4A85-8A91-DED03E987706@khera.org>
	<482C07DE.3090504@yandex.ru> <482C0A89.104@FreeBSD.org>
In-Reply-To: <482C0A89.104@FreeBSD.org>
Content-Type: text/plain; charset=KOI8-R; format=flowed
Content-Transfer-Encoding: 7bit
Cc: Vadim Goncharov <vadim_nuclight@mail.ru>, Vivek Khera <vivek@khera.org>,
	FreeBSD Stable <freebsd-stable@freebsd.org>, freebsd-ipfw@freebsd.org
Subject: Re: how much memory does increasing max rules for IPFW take up?
X-BeenThere: freebsd-stable@freebsd.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: Production branch of FreeBSD source code <freebsd-stable.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-stable>, 
	<mailto:freebsd-stable-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-stable>
List-Post: <mailto:freebsd-stable@freebsd.org>
List-Help: <mailto:freebsd-stable-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-stable>,
	<mailto:freebsd-stable-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Fri, 16 May 2008 04:33:18 -0000

Bruce M. Simpson wrote:
> Got any figures for this? I took a quick glance and it looks like it 
> just uses a hash over dst/src/dport/sport. If there are a lot of raw IP 
> or ICMP flows then that's going to result in hash collisions.

It's my guess, i haven't any figures..
Yes, hash collisions will trigger many searching in buckets lists.
And increasing only dyn_max without increasing dyn_buckets will
grow collisions.

> It might be a good project for someone to optimize if it isn't scaling 
> for folk. "Bloomier" filters are probably worth a look -- bloom filters 
> are a class of probabilistic hash which may return a false positive, 
> "bloomier" filters are a refinement which tries to limit the false 
> positives.

There were some ideas from Vadim Goncharov about rewriting dynamic
rules implementation..

-- 
WBR, Andrey V. Elsukov