From mboxrd@z Thu Jan 1 00:00:00 1970 From: Patrick McHardy Subject: Re: ctnetlink questions Date: Mon, 20 Oct 2003 05:09:08 +0200 Sender: netfilter-devel-admin@lists.netfilter.org Message-ID: <3F9351D4.3070704@trash.net> References: <3F934FFD.7090700@trash.net> Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Cc: Henrik Nordstrom , Harald Welte , Netfilter Development Mailinglist Return-path: In-Reply-To: <3F934FFD.7090700@trash.net> Errors-To: netfilter-devel-admin@lists.netfilter.org List-Help: List-Post: List-Subscribe: , List-Unsubscribe: , List-Archive: List-Id: netfilter-devel.vger.kernel.org Patrick McHardy wrote: > - we can use some sorting algorithm which benefits from pre-sorted > input. this would > give better average performance. IIRC new conntracks are added at the > head of the > chains, so if we sort and walk backwards through the chains we only > have to resort > after an id counter wrap. Sorting is also pretty easy in that case: > move all entries at > head of list whose id is smaller than the last one's to the tail > while preserving order, > stop at first one thats bigger. This also means we only need the > write lock in a very > very rare case. One small addition, this it not completly correct we need to resort more often, but never before the first counter wrap. Best regards, patrick