From patchwork Mon Oct 6 10:49:33 2008 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eric Dumazet X-Patchwork-Id: 2896 X-Patchwork-Delegate: davem@davemloft.net Return-Path: X-Original-To: patchwork-incoming@ozlabs.org Delivered-To: patchwork-incoming@ozlabs.org Received: from vger.kernel.org (vger.kernel.org [209.132.176.167]) by ozlabs.org (Postfix) with ESMTP id EDF6DDDDED for ; Mon, 6 Oct 2008 22:29:51 +1100 (EST) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752393AbYJFL3q (ORCPT ); Mon, 6 Oct 2008 07:29:46 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id S1752643AbYJFL3q (ORCPT ); Mon, 6 Oct 2008 07:29:46 -0400 Received: from smtp2e.orange.fr ([80.12.242.111]:4670 "EHLO smtp2e.orange.fr" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752295AbYJFL3p (ORCPT ); Mon, 6 Oct 2008 07:29:45 -0400 Received: from me-wanadoo.net (localhost [127.0.0.1]) by mwinf2e04.orange.fr (SMTP Server) with ESMTP id E05D27000131; Mon, 6 Oct 2008 13:29:40 +0200 (CEST) Received: from dniepr.adsl.jetmultimedia.fr (LNeuilly-152-23-22-3.w193-252.abo.wanadoo.fr [193.252.36.3]) by mwinf2e04.orange.fr (SMTP Server) with SMTP id 4829A70004D9; Mon, 6 Oct 2008 12:53:36 +0200 (CEST) X-ME-UUID: 20081006105338295.4829A70004D9@mwinf2e04.orange.fr Received: from [127.0.0.1] ([192.168.4.161]) by dniepr.adsl.jetmultimedia.fr (8.11.7+Sun/8.11.7) with SMTP id m96AnmN10137; Mon, 6 Oct 2008 12:49:48 +0200 (MEST) Message-ID: <48E9ED3D.2020005@cosmosbay.com> Date: Mon, 06 Oct 2008 12:49:33 +0200 From: Eric Dumazet User-Agent: Thunderbird 2.0.0.17 (Windows/20080914) MIME-Version: 1.0 To: Neil Horman Cc: Bill Fink , David Miller , netdev@vger.kernel.org, kuznet@ms2.inr.ac.ru, pekkas@netcore.fi, jmorris@namei.org, yoshfuji@linux-ipv6.org, kaber@trash.net, Evgeniy Polyakov Subject: Re: [PATCH] net: implement emergency route cache rebulds when gc_elasticity is exceeded References: <48E141F3.9000903@cosmosbay.com> <20080929223801.GA3157@hmsreliant.think-freely.org> <48E1C104.2080801@cosmosbay.com> <20080930.071023.07946874.davem@davemloft.net> <48E25F02.8030303@cosmosbay.com> <20081001180846.GB3566@hmsreliant.think-freely.org> <20081002010101.6f0a1fa5.billfink@mindspring.com> <48E470AC.10305@cosmosbay.com> <48E4832A.3070804@cosmosbay.com> <20081003003158.GA19230@localhost.localdomain> <20081003203640.GA13354@hmsreliant.think-freely.org> In-Reply-To: <20081003203640.GA13354@hmsreliant.think-freely.org> Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org diff --git a/net/ipv4/route.c b/net/ipv4/route.c index 6ee5354..85182d9 100644 --- a/net/ipv4/route.c +++ b/net/ipv4/route.c @@ -125,6 +125,7 @@ static int ip_rt_redirect_silence __read_mostly = ((HZ / 50) << (9 + 1)); static int ip_rt_error_cost __read_mostly = HZ; static int ip_rt_error_burst __read_mostly = 5 * HZ; static int ip_rt_gc_elasticity __read_mostly = 8; +static int rt_chain_length_max __read_mostly = 32; static int ip_rt_mtu_expires __read_mostly = 10 * 60 * HZ; static int ip_rt_min_pmtu __read_mostly = 512 + 20 + 20; static int ip_rt_min_advmss __read_mostly = 256; @@ -748,11 +749,24 @@ static void rt_do_flush(int process_context) } } +/* + * While freeing expired entries, we compute average chain length + * and standard deviation, using fixed-point arithmetic. + * This to have an estimation of rt_chain_length_max + * rt_chain_length_max = max(elasticity, AVG + 4*SD) + * We use 3 bits for frational part, and 29 (or 61) for magnitude. + */ + +#define FRACT_BITS 3 +#define ONE (1UL << FRACT_BITS) + static void rt_check_expire(void) { static unsigned int rover; unsigned int i = rover, goal; struct rtable *rth, **rthp; + unsigned long sum = 0, sum2 = 0; + unsigned long length, samples = 0; u64 mult; mult = ((u64)ip_rt_gc_interval) << rt_hash_log; @@ -770,8 +784,10 @@ static void rt_check_expire(void) if (need_resched()) cond_resched(); + samples++; if (*rthp == NULL) continue; + length = 0; spin_lock_bh(rt_hash_lock_addr(i)); while ((rth = *rthp) != NULL) { if (rt_is_expired(rth)) { @@ -784,11 +800,13 @@ static void rt_check_expire(void) if (time_before_eq(jiffies, rth->u.dst.expires)) { tmo >>= 1; rthp = &rth->u.dst.rt_next; + length += ONE; continue; } } else if (!rt_may_expire(rth, tmo, ip_rt_gc_timeout)) { tmo >>= 1; rthp = &rth->u.dst.rt_next; + length += ONE; continue; } @@ -797,6 +815,15 @@ static void rt_check_expire(void) rt_free(rth); } spin_unlock_bh(rt_hash_lock_addr(i)); + sum += length; + sum2 += length*length; + } + if (samples) { + unsigned long avg = sum / samples; + unsigned long sd = int_sqrt(sum2 / samples - avg*avg); + rt_chain_length_max = max_t(unsigned long, + ip_rt_gc_elasticity, + (avg + 4*sd) >> FRACT_BITS); } rover = i; }