linux-kernel - Re: .. anybody know of any filesystems that depend on the exact VFS 'namehash' implementation?

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]

Date:	Thu, 01 Mar 2012 10:13:59 +0000
From:	Steven Whitehouse <swhiteho@...hat.com>
To:	Linus Torvalds <torvalds@...ux-foundation.org>
Cc:	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
	linux-fsdevel <linux-fsdevel@...r.kernel.org>,
	Al Viro <viro@...iv.linux.org.uk>
Subject: Re: .. anybody know of any filesystems that depend on the exact
 VFS 'namehash' implementation?

Hi,

On Wed, 2012-02-29 at 15:36 -0800, Linus Torvalds wrote:
> So I'm doing my normal profiling ("empty kernel build" is my favorite
> one), and link_path_walk() and __d_lookup_rcu() remain some of the
> hottest kernel functions due to their per-character loops.
> 
> I can improve __d_lookup_rcu() on my machine by what appears to be
> around 15% by doing things a "unsigned long" at a time (it would be an
> option that only works on little-endian and with cheap unaligned
> accesses, although the big-endian modifications should be pretty
> trivial).
> 
> Sure, that optimization would have to be disabled if you do
> DEBUG_PAGEALLOC, because it might opportunistically access bytes past
> the end of the string, but it does seem to be a very reasonable and
> easy thing to do apart from that small detail, and the numbers do look
> good.
> 
> Basically, dentry_cmp() just becomes
> 
>         /* Little-endian with fast unaligned accesses? */
>         unsigned long a,b,mask;
> 
>         if (scount != tcount)
>                 return 1;
> 
>         for (;;) {
>                 a = *(unsigned long *)cs;
>                 b = *(unsigned long *)ct;
>                 if (tcount < sizeof(unsigned long))
>                         break;
>                 if (a != b)
>                         return 1;
>                 cs += sizeof(unsigned long);
>                 ct += sizeof(unsigned long);
>                 tcount -= sizeof(unsigned long);
>                 if (!tcount)
>                         return 0;
>         }
>         mask = ~(~0ul << tcount*8);
>         return !!((a ^ b) & mask);
> 
> for that case, and gcc generates good code for it.
> 
> However, doing the same thing for link_path_walk() would require that
> we actually change the hash function we use internally in the VFS
> layer, and while I think that shouldn't really be a problem, I worry
> that some filesystem might actually use the hash we generate and save
> it somewhere on disk (rather than only use it for the hashed lookup
> itself).
> 
GFS2 is guilty as charged, m'lud! (but see below...)

from fs/gfs2/dentry.c:

static int gfs2_dhash(const struct dentry *dentry, const struct inode *inode,
                struct qstr *str)
{
        str->hash = gfs2_disk_hash(str->name, str->len);
        return 0;
}
[snip]
const struct dentry_operations gfs2_dops = {
        .d_revalidate = gfs2_drevalidate,
        .d_hash = gfs2_dhash,
        .d_delete = gfs2_dentry_delete,
};

and in fs/gfs2/dir.h:

static inline u32 gfs2_disk_hash(const char *data, int len)
{
        return crc32_le((u32)~0, data, len) ^ (u32)~0;
}


This was something that was added to GFS2 right back at the beginning,
to avoid having to compute two hash functions for each directory entry.
The hash function itself was taken from the original GFS, so it was
designed to be backward compatible. We assume that the 32 bit on disk
hash function of GFS2 will always fit in the "unsigned int" of the qstr.

I wasn't quite sure whether from your description, the issue applies to
filesystems which actually have their own hash functions, or only to
filesystems which might write the VFS's internal hash function to disk?
Maybe the former is a simple solution for the latter, if a filesystem
specific hash function is a suitable solution,

Steve.


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