netdev - RE: [PATCH 7/9] rhashtable: Per bucket locks & deferred expansion/shrinking

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: <063D6719AE5E284EB5DD2968C1650D6D1CACADAF@AcuExch.aculab.com>
Date:	Fri, 16 Jan 2015 16:43:02 +0000
From:	David Laight <David.Laight@...LAB.COM>
To:	'Patrick McHardy' <kaber@...sh.net>, Thomas Graf <tgraf@...g.ch>
CC:	"davem@...emloft.net" <davem@...emloft.net>,
	"netdev@...r.kernel.org" <netdev@...r.kernel.org>,
	"kernel@...r.kernel.org" <kernel@...r.kernel.org>,
	"herbert@...dor.apana.org.au" <herbert@...dor.apana.org.au>,
	"paulmck@...ux.vnet.ibm.com" <paulmck@...ux.vnet.ibm.com>,
	"edumazet@...gle.com" <edumazet@...gle.com>,
	"john.r.fastabend@...el.com" <john.r.fastabend@...el.com>,
	"josh@...htriplett.org" <josh@...htriplett.org>,
	"netfilter-devel@...r.kernel.org" <netfilter-devel@...r.kernel.org>
Subject: RE: [PATCH 7/9] rhashtable: Per bucket locks & deferred
 expansion/shrinking

From: Patrick McHardy
> On 16.01, Thomas Graf wrote:
> > On 01/16/15 at 04:03pm, Patrick McHardy wrote:
> > > On 16.01, Thomas Graf wrote:
> > > > A walker may not see insertions that occur after the walker was started
> > > > if resizing is enabled. Is that a problem for nftables?
> > >
> > > No, that would be Ok. The case I'm wondering about is:
> > >
> > > - insertion
> > > - resize starts
> > > - another insertion
> > > - walker, resize not finished yet
> >
> > Correct, walker may not see "another insertion". The window for this
> > behavior to occur is not the full resize operation, just the linking
> > period, but it may occur. The length of the window is typically
> > equal to a grace period.
> >
> > We can provide a synchronization function to block the dumper or the
> > insertion/removal until the linking is complete. The latter would
> > give the old runtime behaviour back (variable runtime of insert),
> > the blocked dumper might be preferred. What do you think?
> 
> If we have to block, the dumper if of course preferred. Taking the
> mutex should do fine I guess?
> 
> I suppose walking both tables without any races would be rather
> complicated.

The walker is unlikely to see items that get inserted early in the hash
table even without a resize.

I'd be more worried about the walker missing big blocks of entries or
getting duplicate entries during a resize.
This might be a problem if the walker is a user-process table dump,
in which case you can't assume it will finish in any finite time.

	David

--
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