From patchwork Fri Oct 15 06:53:04 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eric Dumazet X-Patchwork-Id: 67889 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.180.67]) by ozlabs.org (Postfix) with ESMTP id A03C9B70E2 for ; Fri, 15 Oct 2010 18:01:46 +1100 (EST) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1756217Ab0JOHBm (ORCPT ); Fri, 15 Oct 2010 03:01:42 -0400 Received: from mail-wy0-f174.google.com ([74.125.82.174]:45420 "EHLO mail-wy0-f174.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755977Ab0JOHBl (ORCPT ); Fri, 15 Oct 2010 03:01:41 -0400 Received: by wyb28 with SMTP id 28so357968wyb.19 for ; Fri, 15 Oct 2010 00:01:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:subject:from:to:cc :in-reply-to:references:content-type:date:message-id:mime-version :x-mailer:content-transfer-encoding; bh=vNEn6vLcWmZ5G8li65ktxswXSp2VIw3aNqk3ZoWZnco=; b=hwNGCsl5sHt7hs0NECnYGUgxZtkzxXDy6E1jV+2rCztA5Ee3zHre8bH8qkX55ymUJi NCRXLEXBa8hjL9elUvFBrREVUGKgTnt4ALAJ1i+c0DPcFv08jiXvGoL3Iq8nB+Yt97rc dp5GM+bWNckt2c0MOm8aK6GH3pBdl4tVWSHxs= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=subject:from:to:cc:in-reply-to:references:content-type:date :message-id:mime-version:x-mailer:content-transfer-encoding; b=htc9v9n6+fN04+Gshh3QRskoQVETi4R3eIj9o8Yvd4t40cNDwcab7zb+7n77S4vHmw tCJeG6PJvyzhja9JG8qlGDJ1HFEX1aVa11zOEM6k+90yioVrULmZp+goE3WyPGVTjibY dSrS2+zlXqkkyZRY97orIZOCaCwcWYH3ztXNE= Received: by 10.227.127.82 with SMTP id f18mr392415wbs.185.1287125605061; Thu, 14 Oct 2010 23:53:25 -0700 (PDT) Received: from [192.168.1.21] ([86.72.144.167]) by mx.google.com with ESMTPS id x12sm3694543weq.18.2010.10.14.23.53.23 (version=SSLv3 cipher=RC4-MD5); Thu, 14 Oct 2010 23:53:24 -0700 (PDT) Subject: [PATCH net-next 1/3] fib_hash: embed initial hash table in fn_zone From: Eric Dumazet To: David Miller Cc: netdev In-Reply-To: <1287084159.2659.0.camel@edumazet-laptop> References: <1287073458.2712.100.camel@edumazet-laptop> <1287084159.2659.0.camel@edumazet-laptop> Date: Fri, 15 Oct 2010 08:53:04 +0200 Message-ID: <1287125584.2659.1840.camel@edumazet-laptop> Mime-Version: 1.0 X-Mailer: Evolution 2.30.3 Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org While looking for false sharing problems, I noticed sizeof(struct fn_zone) was small (28 bytes) and possibly sharing a cache line with an often written kernel structure. Most of the time, fn_zone uses its initial hash table of 16 slots. We can avoid the false sharing problem by embedding this initial hash table in fn_zone itself, so that sizeof(fn_zone) > L1_CACHE_BYTES We did a similar optimization in commit a6501e080c (Reduce memory needs and speedup lookups) Add a fz_revorder field to speedup fn_hash() a bit. Signed-off-by: Eric Dumazet --- net/ipv4/fib_hash.c | 52 ++++++++++++++++++------------------------ 1 file changed, 23 insertions(+), 29 deletions(-) -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html diff --git a/net/ipv4/fib_hash.c b/net/ipv4/fib_hash.c index 83cca68..10001aa 100644 --- a/net/ipv4/fib_hash.c +++ b/net/ipv4/fib_hash.c @@ -54,23 +54,23 @@ struct fib_node { struct fib_alias fn_embedded_alias; }; +#define EMBEDDED_HASH_SIZE (L1_CACHE_BYTES / sizeof(struct hlist_head)) + struct fn_zone { struct fn_zone *fz_next; /* Next not empty zone */ struct hlist_head *fz_hash; /* Hash table pointer */ - int fz_nent; /* Number of entries */ - - int fz_divisor; /* Hash divisor */ u32 fz_hashmask; /* (fz_divisor - 1) */ -#define FZ_HASHMASK(fz) ((fz)->fz_hashmask) - int fz_order; /* Zone order */ - __be32 fz_mask; + u8 fz_order; /* Zone order (0..32) */ + u8 fz_revorder; /* 32 - fz_order */ + __be32 fz_mask; /* inet_make_mask(order) */ #define FZ_MASK(fz) ((fz)->fz_mask) -}; -/* NOTE. On fast computers evaluation of fz_hashmask and fz_mask - * can be cheaper than memory lookup, so that FZ_* macros are used. - */ + struct hlist_head fz_embedded_hash[EMBEDDED_HASH_SIZE]; + + int fz_nent; /* Number of entries */ + int fz_divisor; /* Hash size (mask+1) */ +}; struct fn_hash { struct fn_zone *fn_zones[33]; @@ -79,11 +79,11 @@ struct fn_hash { static inline u32 fn_hash(__be32 key, struct fn_zone *fz) { - u32 h = ntohl(key)>>(32 - fz->fz_order); + u32 h = ntohl(key) >> fz->fz_revorder; h ^= (h>>20); h ^= (h>>10); h ^= (h>>5); - h &= FZ_HASHMASK(fz); + h &= fz->fz_hashmask; return h; } @@ -147,14 +147,14 @@ static void fn_rehash_zone(struct fn_zone *fz) int old_divisor, new_divisor; u32 new_hashmask; - old_divisor = fz->fz_divisor; + new_divisor = old_divisor = fz->fz_divisor; switch (old_divisor) { - case 16: - new_divisor = 256; + case EMBEDDED_HASH_SIZE: + new_divisor *= EMBEDDED_HASH_SIZE; break; - case 256: - new_divisor = 1024; + case EMBEDDED_HASH_SIZE*EMBEDDED_HASH_SIZE: + new_divisor *= (EMBEDDED_HASH_SIZE/2); break; default: if ((old_divisor << 1) > FZ_MAX_DIVISOR) { @@ -184,7 +184,8 @@ static void fn_rehash_zone(struct fn_zone *fz) fib_hash_genid++; write_unlock_bh(&fib_hash_lock); - fz_hash_free(old_ht, old_divisor); + if (old_ht != fz->fz_embedded_hash) + fz_hash_free(old_ht, old_divisor); } } @@ -210,18 +211,11 @@ fn_new_zone(struct fn_hash *table, int z) if (!fz) return NULL; - if (z) { - fz->fz_divisor = 16; - } else { - fz->fz_divisor = 1; - } - fz->fz_hashmask = (fz->fz_divisor - 1); - fz->fz_hash = fz_hash_alloc(fz->fz_divisor); - if (!fz->fz_hash) { - kfree(fz); - return NULL; - } + fz->fz_divisor = z ? EMBEDDED_HASH_SIZE : 1; + fz->fz_hashmask = fz->fz_divisor - 1; + fz->fz_hash = fz->fz_embedded_hash; fz->fz_order = z; + fz->fz_revorder = 32 - z; fz->fz_mask = inet_make_mask(z); /* Find the first not empty zone with more specific mask */