netdev - Re: [PATCH] NET : change layout of ehash table

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <20070208.145632.74749802.davem@davemloft.net>
Date:	Thu, 08 Feb 2007 14:56:32 -0800 (PST)
From:	David Miller <davem@...emloft.net>
To:	dada1@...mosbay.com
Cc:	linux@...izon.com, akepner@....com, netdev@...r.kernel.org
Subject: Re: [PATCH] NET : change layout of ehash table

From: Eric Dumazet <dada1@...mosbay.com>
Date: Wed, 7 Feb 2007 11:59:34 +0100

> ehash table layout is currently this one :
> 
> First half of this table is used by sockets not in TIME_WAIT state
> Second half of it is used by sockets in TIME_WAIT state.
> 
> This is non optimal because of for a given hash or socket, the two chain heads 
> are located in separate cache lines.
> Moreover the locks of the second half are never used.
> 
> If instead of this halving, we use two list heads in inet_ehash_bucket instead 
> of only one, we probably can avoid one cache miss, and reduce ram usage, 
> particularly if sizeof(rwlock_t) is big (various CONFIG_DEBUG_SPINLOCK, 
> CONFIG_DEBUG_LOCK_ALLOC settings). So we still halves the table but we keep 
> together related chains to speedup lookups and socket state change.
> 
> In this patch I did not try to align struct inet_ehash_bucket, but a future 
> patch could try to make this structure have a convenient size (a power of two 
> or a multiple of L1_CACHE_SIZE).
> I guess rwlock will just vanish as soon as RCU is plugged into ehash :) , so 
> maybe we dont need to scratch our heads to align the bucket...
> 
> Note : In case struct inet_ehash_bucket is not a power of two, we could 
> probably change alloc_large_system_hash() (in case it use __get_free_pages()) 
> to free the unused space. It currently allocates a big zone, but the last 
> quarter of it could be freed. Again, this should be a temporary 'problem'.
> 
> Patch tested on ipv4 tcp only, but should be OK for IPV6 and DCCP.
> 
> Signed-off-by: Eric Dumazet <dada1@...mosbay.com>

I've applied this, but I _REALLY_ don't like the new multiply
instructions that are used now in the hash indexing paths when
CONFIG_SMP is set.

I think that's a higher cost than the memory waste.
-
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html