linux-kernel - Re: If not readdir() then what?

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: <20070412093310.GC8175@lazybastard.org>
Date:	Thu, 12 Apr 2007 11:33:11 +0200
From:	Jörn Engel <joern@...ybastard.org>
To:	Neil Brown <neilb@...e.de>
Cc:	Theodore Tso <tytso@....edu>, "H. Peter Anvin" <hpa@...or.com>,
	Christoph Hellwig <hch@...radead.org>,
	Ulrich Drepper <drepper@...il.com>,
	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>
Subject: Re: If not readdir() then what?

On Thu, 12 April 2007 15:57:41 +1000, Neil Brown wrote:
> 
> > However, the collision chain gives me quite a bit of headache.  One
> > would have to store each entry's position on the chain, deal with older
> > entries getting deleted, newer entries getting removed, etc.  All this
> > requires a lot of complicated code that basically never gets tested in
> > the wild.
> 
> This is a simple consequence of the design decision to use hashes as
> the search key.  They aren't dense and they will collide.  So the
> solution will be a bit fuzzy around the edges.  And maybe that is an
> acceptable tradeoff.  But the filesystem should take full
> responsibility for it, whether in performance or correctness :-)

Sure.  And seeing that not using hashes would kill performance long
before 4 billion dentries are reached, there don't seem to be many
downsides to hashing in principle.

> > Just settling for a 64bit hash and returning -EEXIST when someone causes
> > a collision an creat() sounds more appealing.  Directories with 4
> > billion entries will cause problems, but that is hardly news to anyone.
> 
> I think you want -EFBIG or -ENOSPC.  -EEXIST sounds just wrong.

None of them are 100% correct.  But you are right, -ENOSPC seems to do
less harm.

> But there are alternatives.  e.g. internal chaining.
> Insist on a unique 64bit hash for every file.  If the hash is in use,
> increment and try again.  On lookup, if the hash leads you to a file
> with the wrong name, increment and try again until you find a hole
> (hash value that is not stored).  When you delete an entry, leave a
> place holder if the next hash is in use.  Conversely if the next hash
> is not in use, delete the entry and delete the previous one if it is a
> place holder.

That would work and is limited to reasonable complexity.  It still
suffers from getting virtually no testing in the wild and therefore
being one of the dark corners little critters thrive in.  But one can at
least add a config option to fold the hash to 16bit or so.  And cross
fingers that at least one person will occasionally test with that
option.

> You have to require 64bit cookies/fpos, but I think that today, that
> is a reasonable thing to require (5 years ago it might not have been).

Which brings us back to the start of this thread.

Jörn

-- 
Why do musicians compose symphonies and poets write poems?
They do it because life wouldn't have any meaning for them if they didn't.
That's why I draw cartoons.  It's my life.
-- Charles Shultz
-
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/