linux-ext4 - Re: [RFC] Optimizing readdir()

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: <20130114045152.GF29329@thunk.org>
Date:	Sun, 13 Jan 2013 23:51:52 -0500
From:	Theodore Ts'o <tytso@....edu>
To:	Radek Pazdera <rpazdera@...hat.com>
Cc:	linux-ext4@...r.kernel.org,
	Lukáš Czerner <lczerner@...hat.com>
Subject: Re: [RFC] Optimizing readdir()

On Sun, Jan 13, 2013 at 04:22:04PM +0100, Radek Pazdera wrote:
> 
> My idea was to try to add a second tree to the current index that would
> be used to retrieve entries in inode-order. Its structure could be very
> similar to the current HTree (the hash is 32bits and so are inode
> numbers).

Something to think about what the backwards compatibility impacts of
this would be.  The current directory entries are indexed using
*logical* block numbers, which means that if we ignore the directory
htree blocks (which were deliberately crafted to look like deleted
directory entries that were the size of the entire directory block),
an htree-oblivious kernel (or the ext2 file system driver) would be
able to interpret the directory entries as a traditional ext2
directory.

When you add this feature, you will almost certainly break this, at
least for read/write forward compatibility.

What I would suggest, if we do go down this path, is to store the
secondary directory tree using physical block numbers, so the
directory blocks are stored outside of the directory entirely.  That
means you'll need to have a 64-bit block number, but it means that you
won't have to do a lookup to translate the logical block number ot the
physical block number.  It also means that there won't be any
confusion about whether a particular directory entry block belongs to
the htree-indexed tree or the inode-number-indexed tree.

If we want to make the file system be backwards compatible, this gets
a bit more difficult, since the current code is not set up to handle
the info_length to be anything other than 8.  This won't be a problem
if you want to make the feature be completely backwards incompatible,
but if you want to allow at least read/only compatibility, you might
want to stick 64-bit block number at the end of the dx_root block
(this is why the directory checksum is in the dx_tail structure).

I wonder if the better approach is to just simply have some
easy-to-use library routines that do a readdir/sort in userspace.  The
spd_readdir does basically this, and as we can see it's good enough
for most purposes.  The problem is danger when using this in threaded
programs, or if you have programs doing really strange things with
telldir/seekdir, etc.

But it wouldn't be that hard to write a generic library function which
if it were used for find, ls, tar, and a few other key programs, would
solve the problem for most use cases.

Cheers,

						- Ted
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html