From: Andrei Vagin <avagin@virtuozzo.com>
To: "Eric W. Biederman" <ebiederm@xmission.com>
Cc: Andrei Vagin <avagin@openvz.org>,
Alexander Viro <viro@zeniv.linux.org.uk>,
<containers@lists.linux-foundation.org>,
<linux-fsdevel@vger.kernel.org>, <linux-kernel@vger.kernel.org>
Subject: Re: [PATCH v2] mount: dont execute propagate_umount() many times for same mounts
Date: Mon, 10 Oct 2016 13:42:32 -0700 [thread overview]
Message-ID: <20161010204218.GB31628@outlook.office365.com> (raw)
In-Reply-To: <87twcoahs3.fsf@x220.int.ebiederm.org>
On Thu, Oct 06, 2016 at 11:45:48PM -0500, Eric W. Biederman wrote:
> Andrei Vagin <avagin@virtuozzo.com> writes:
>
> > On Thu, Oct 06, 2016 at 02:46:30PM -0500, Eric W. Biederman wrote:
> >> Andrei Vagin <avagin@openvz.org> writes:
> >>
> >> > The reason of this optimization is that umount() can hold namespace_sem
> >> > for a long time, this semaphore is global, so it affects all users.
> >> > Recently Eric W. Biederman added a per mount namespace limit on the
> >> > number of mounts. The default number of mounts allowed per mount
> >> > namespace at 100,000. Currently this value is allowed to construct a tree
> >> > which requires hours to be umounted.
> >>
> >> I am going to take a hard look at this as this problem sounds very
> >> unfortunate. My memory of going through this code before strongly
> >> suggests that changing the last list_for_each_entry to
> >> list_for_each_entry_reverse is going to impact the correctness of this
> >> change.
> >
> > I have read this code again and you are right, list_for_each_entry can't
> > be changed on list_for_each_entry_reverse here.
> >
> > I tested these changes more carefully and find one more issue, so I am
> > going to send a new patch and would like to get your comments to it.
> >
> > Thank you for your time.
>
> No problem.
>
> A quick question. You have introduced lookup_mnt_cont. Is that a core
> part of your fix or do you truly have problmenatic long hash chains.
Actually I need a slightly modified copy of __lookup_mnt_last() to set
mark for mounts with the MNT_UMOUNT flag.
>
> Simply increasing the hash table size should fix problems long hash
> chains (and there are other solutions like rhashtable that may be more
> appropriate than pre-allocating large hash chains).
>
> If it is not long hash chains introducing lookup_mnt_cont in your patch
> is a distraction to the core of what is going on.
>
> Perhaps I am blind but if the hash chains are not long I don't see mount
> propagation could be more than quadratic in the worst case. As there is
> only a loop within a loop. Or Is the tree walking in propagation_next
> that bad?
I don't think that the hash chains are long here.
The complexity of __lookup_mnt() is O(n). In our case the hash size
(4096) is smaller than a number of elements. If we increase the hash
size, it will be faster but the coplexity in term of O() will be the
same, will it not?
Here are all nested steps where we enumirate mounts:
* Enumirate all mounts in a target tree (propagate_umount)
* Enumirate mounts to find where these changes have to
be propagated (mark_umount_candidates)
* Enumirate mounts to find a requered mount by parent and dentry
(__lookup_mnt_last)
And my measurements proves that it isn't O(n^2):
mounts | (sec) |
------------
1024 | 0.08
2048 | 0.4
4096 | 3.2
8192 | 50.8
16384 | 810
>
> Eric
prev parent reply other threads:[~2016-10-10 22:15 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-10-06 16:49 Andrei Vagin
2016-10-06 19:46 ` Eric W. Biederman
2016-10-06 23:06 ` Andrei Vagin
2016-10-07 4:45 ` Eric W. Biederman
2016-10-10 20:42 ` Andrei Vagin [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20161010204218.GB31628@outlook.office365.com \
--to=avagin@virtuozzo.com \
--cc=avagin@openvz.org \
--cc=containers@lists.linux-foundation.org \
--cc=ebiederm@xmission.com \
--cc=linux-fsdevel@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=viro@zeniv.linux.org.uk \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®