[PATCH review 6/6] vfs: Cache the results of path_connected

Eric W. Biederman ebiederm at xmission.com
Tue Aug 4 22:58:59 UTC 2015


"J. Bruce Fields" <bfields at fieldses.org> writes:

> On Tue, Aug 04, 2015 at 12:41:32PM -0500, Eric W. Biederman wrote:
>> A pathname lookup taking 16 seconds seems absurd.  But perhaps in the
>> worst case.
>> 
>> The maximum length of a path that can be passed into path_lookup is
>> 4096.  For a lookup to be problematic there must be at least as many
>> instances of .. as there are of any other path component.  So each pair
>> of a minium length path element and a .. element must take at least 5
>> bytes. Which in 4096 bytes leaves room for 819 path elements.  If every
>> one of those 819 path components triggered a disk seek at 100 seeks per
>> second I could see a path name lookup potentially taking 8 seconds.
>
> A lookup on NFS while a server's rebooting or the network's flaky could
> take arbitrary long.  Other network filesystems and fuse can have
> similar problems.  Depending on threat model an attacker might have
> quite precise control over that timing.  Disk filesystems could have all
> the same problems since there's no guarantee the underlying block device
> is really local.  Even ignoring that, hardware can be slow or flaky.
> And couldn't an allocation in theory block for an arbitrary long time?
>
> Apologies for just dropping into the middle here!  I haven't read the
> rest and don't have the context to know whether any of that's relevant.

No problem.  The basic question is: can 2Billion renames be performed on
the same filesystem in less time than a single path lookup?  Allowing
the use of a 32bit counter.

Most of the issues that slow up lookup also slow up rename so I have
not been focusing on them.

If you could look up thread and tell me what you think of the issue with
file handle to dentry conversion and bind mounts I would be appreciate.

I have been testing a little more on my system and it appears that it
takes an 60minutes give or take to perform 2 Billino renames on ramfs.
A faster cpu (5Ghz?) could perhaps get that down to 30 minutes.

With no slow downs and no weirdness I have been able to get a single
pathname lookup to take just over 2 minutes, and I expect I could get
that to take another minute more.

Those numbers are within a factor of 10 of each other, and I expect
someone clever could finagle something to overcome the rest.  So sigh.

There just is not enough margin in there to be certain of things.  Now
with the small change to make that counter 64bit and that 30 minutes to
wrap the counter becomes 240,000+ years.  I think I can safely not worry
about the issue.  I just need to come up with a good 32bit implemenation.

Eric



More information about the Containers mailing list