Date: Tue, 21 Dec 2010 20:26:51 +1100
From: Nick Piggin <npiggin@kernel.dk>
To: George Spelvin <linux@horizon.com>
Cc: npiggin@gmail.com, bharrosh@panasas.com, linux-arch@vger.kernel.org,
        linux-fsdevel@vger.kernel.org, linux-kernel@vger.kernel.org
Subject: Re: Big git diff speedup by avoiding x86 "fast string" memcmp
Message-ID: <20101221092651.GA9242@amd>
References: <AANLkTikwUEBd1Ez75pQ7gw7ShZitwQOQcH6CvCdJV2np@mail.gmail.com>
 <20101219170646.482.qmail@science.horizon.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20101219170646.482.qmail@science.horizon.com>
User-Agent: Mutt/1.5.20 (2009-06-14)
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 2544
Lines: 57

On Sun, Dec 19, 2010 at 12:06:46PM -0500, George Spelvin wrote:
> > First, a byte-by-byte strcpy_from_user of the whole name string to
> > kernel space. Then a byte-by-byte chunking and hashing component
> > paths according to '/'. Then a byte-by-byte memcmp against the
> > dentry name.
> 
> Well, you've put your finger on the obvious place to to the aligned copy,
> if you want.

Yes, this would be a nice place to align things and parse '/' compoents,
although in fact it doesn't strictly have to be a byte-by-byte copy
(although doing long loads would put a lot more complexity in fault
handling and parsing).


>  Looking into it, I note that __d_lookup() does a 32-bit
> hash compare before doing a string compare, so the memcmp should almost
> always succeed.  (Failures are due to hash collisions and rename races.)
> 
> > I'd love to do everything with 8 byte loads, do the component
> > separation and hashing at the same time as copy from user, and
> > have the padded and aligned component strings and their hash
> > available... but complexity.
> 
> It actually doesn't seem that difficult to do in fs/namei.c:do_getname
> via a heavily hacked strncpy_from_user.  Call it strhash_from_user, and
> it copies the string, while accumulating the hash and the length,
> until it hits a nul or /.  It has to return the length, the hash,
> and the termination condition: nul, /, or space exhausted.
> 
> Then you could arrange for each component to be padded so that it
> starts aligned.
> 
> (The hash and length can be stored directly in the qstr.  The length is
> only otherwise needed for components that end in /, so you could return
> a magic negative length in those cases.)

Probably, due to bloat caused by the hash for small names, and that
some filesystems do their own hashing, we should still hash in the
same place. However we can do sizeof(long) at a time hashing, which
should be nice and fast too.

 
> The main problem with initializing all the qstr structures early is that
> it can lead to an oddly dynamic PATH_MAX and/or a type of kernel
> DOS by passing in paths with many short directory names that would need
> maximal padding.

If the results are compelling enough, this could be worked around
some way. Simple realloc probably, seeing as it would be a rare case.


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