linux-kernel - Re: [PATCH 3/3] fs: rcu protect inode hash lookups

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: <20101102000152.GO2715@dastard>
Date:	Tue, 2 Nov 2010 11:01:52 +1100
From:	Dave Chinner <david@...morbit.com>
To:	Eric Dumazet <eric.dumazet@...il.com>
Cc:	viro@...IV.linux.org.uk, linux-fsdevel@...r.kernel.org,
	linux-kernel@...r.kernel.org,
	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
Subject: Re: [PATCH 3/3] fs: rcu protect inode hash lookups

On Mon, Nov 01, 2010 at 04:29:22PM +0100, Eric Dumazet wrote:
> Le mardi 02 novembre 2010 à 00:44 +1100, Dave Chinner a écrit :
> 
> > Perhaps you should rename that file "slab_destroy_by_rcu-tips.txt",
> > because the current name seems unrelated to the contents. :/
> > 
> 
> Hmm, I dont know, this doc really is about the nulls thing.

Ok, now I understand - there's a new list type that I didn't know
about called hlist_nulls. not surprising - it's not documented
anywhere.

Maybe explicitly describing what the list_null pattern іs or a
pointer to linux/include/list_nulls.h might be appropriate, because
I managed to read that documentation and not realise that it was
refering to a specific type of list that was already implemented
rather than a simple marker technique.

> This stuff also addressed one problem I forgot to tell you about: During
> a lookup, you might find an item that is moved to another chain by
> another cpu, so your lookup is redirected to another chain. You can miss
> your target.

<groan>

So, to go to per-chain locks as per the proposed bit-lock-on-the-
low-bit-of-the-head-pointer infrastructure, we'll have to cross that
with the hlist_null code that plays low-bit pointer games for
detecting the end of the chain.

That's just messy - another hash chain specific scalability hackup.
My dislike of using hash tables for unbounded caches is not
improved by this....

> You must find a way to detect such thing to restart the lookup at
> the beginning (of the right chain).  Either you stick the chain
> number in a new inode field (that costs extra memory), or you use
> the 'nulls' value that can let you know if you ended your lookup
> in the right chain.

The chain is determined by hashing the inode number. Perhaps a
simple enough test is to hash the last inode number on a cache miss
and if that doesn't match the hash of the lookup key we redo the
search. That seems to me like it will avoid needing to play games
with termination markers - does that sound reasonable?

Cheers,

Dave.
-- 
Dave Chinner
david@...morbit.com
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/