Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752510AbcJJWPz (ORCPT ); Mon, 10 Oct 2016 18:15:55 -0400 Received: from mail-db5eur01on0099.outbound.protection.outlook.com ([104.47.2.99]:59744 "EHLO EUR01-DB5-obe.outbound.protection.outlook.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1752183AbcJJWPx (ORCPT ); Mon, 10 Oct 2016 18:15:53 -0400 Authentication-Results: spf=none (sender IP is ) smtp.mailfrom=avagin@virtuozzo.com; Date: Mon, 10 Oct 2016 13:42:32 -0700 From: Andrei Vagin To: "Eric W. Biederman" CC: Andrei Vagin , Alexander Viro , , , Subject: Re: [PATCH v2] mount: dont execute propagate_umount() many times for same mounts Message-ID: <20161010204218.GB31628@outlook.office365.com> References: <1475772564-25627-1-git-send-email-avagin@openvz.org> <87eg3tclbd.fsf@x220.int.ebiederm.org> <20161006230616.GA2296@outlook.office365.com> <87twcoahs3.fsf@x220.int.ebiederm.org> MIME-Version: 1.0 Content-Type: text/plain; charset="koi8-r" Content-Disposition: inline In-Reply-To: <87twcoahs3.fsf@x220.int.ebiederm.org> User-Agent: Mutt/1.7.0 (2016-08-17) X-Originating-IP: [162.246.95.100] X-ClientProxiedBy: CY1PR21CA0023.namprd21.prod.outlook.com (10.161.247.33) To VI1PR0801MB1983.eurprd08.prod.outlook.com (10.173.74.16) X-MS-Office365-Filtering-Correlation-Id: 112aa1df-d468-47af-2797-08d3f14e006d X-Microsoft-Exchange-Diagnostics: 1;VI1PR0801MB1983;2:Q3LucMbZeuH/0fb5mAAvlz7F+LlKc7PZL74QPDJLeE8ycl+s73b8JbMluWkbJ+PDEbc+PsNALLLdHcvc7UNocTzubHmU/QEpUWfe04NUfsgzYSoB+HDS9JXAVrcT5GpXZQ8/d7LYRjcB0Ewhhaau6sF4eUu2E0mgapLtePjsdrOIcX1OP7CM7RIAyWzzcrul;3:u1ThYrKzGVbQwRvstcouhoMk3uM9JvGfqUd5CRWSzLg6bJZLlywEXppOpvxDyZTfGKPbAis8/0Bxw54EAUW5UJgNx/uIONfwycQgJ1h/TMJyYqnOa+F8dZg71sMOOC0d X-Microsoft-Antispam: UriScan:;BCL:0;PCL:0;RULEID:;SRVR:VI1PR0801MB1983; X-Microsoft-Exchange-Diagnostics: 1;VI1PR0801MB1983;25:ABIThCwPcOLyoyPkIaoNMRxmkOE9Of3NFDbQp9isr42DqNXItrzm4NmynTMqcVjANXnf6PsUAyWKtF4MqHfNfUKzBz2aTGA+mQutd7+IzWZY+5A/0ttuNSoPUNvLS3gIL8SlmyXd3KAysHjG+JVq6X9EGG/e+fy+L540m/DNg3Vv+/cyQ8t22xXbYrcZuyovhpAYEjyraUEMgSMvmc0y75vVMldCmH4iHQ3wja7kHBKsYTBKJ6IsbrmKQhhHAh6JHG4YtPMG07TpSfPNMLnxcNXQbnjl6hgulaWrLB8guUWfBLfOIP0XKvCp4GxSegAFZOInQuAtHq7HWDoLB3cV+Kaa6CYi/cOupaa++giOR3IwIuz6mr65znXIj/Ai/7/AI8pLRRwcuJUeubyIw/fMsOqIH908ELMuX6+DMdELOuqAx6P5iLXlG64bbQktBP2fS/5klnYnzxJeCYV3CT7VGGs4FUGfrmVwoI6zOZe8mhbXmoBnH5r5yoRq8p6MF3v2aQtmIs2qmr9dumPhn2h9mYB2Wp6OziMEe2cFI1XgTonMEr1Cra/fuqv7A5Mm/S5rYXsaClIzmcE6E1RZEWqaDrv6sJA0tbaMEHvmFSztGcaiwammpahnwnv4plzrVyhpEVAE6RQbgKOuJFzoIEL1/YM4mbkYg54Rc/a8FjGXVeSZ9IBou3Veu4iA9n7A2BBlmulYa396mg8EjY2sndu1pzciDb/ARRxwG23UyfrNmUw= X-Microsoft-Exchange-Diagnostics: 1;VI1PR0801MB1983;31:/DNRo0syf7beuo2Ni1mu2AB2JlFAjRdIeJVEuiWrlV36WuConvHTpeHsuE7WhOlz49PdILurBeYUiDpD4wi+avmfX0+t3S6v+9lMlLoXV8lpgIZQ+MzuEr51BRMW/CyxBRY5v7X6PSN593GKp0R7q6hpjSIbD0OKpLCXNa6b/jyVa/Rbb5SezB/JFklER6c5hkiLO5e9d8STpf4b9FAVOujrW/JRw/XacJc2VXScXSguTBOuS2JlM8a5FwXN6PlY;4:raxOkd+IYgrsM0BKalnI0vwhDxOC2FfGybj+1hlOVCMh8TjWiF0hcunDx6nCaKMvOKHBiaLBMzWCR/pOhwXcf7IETBXORVLnmObwRcIm9fcCTwCH0aQjxI+LYRMjZC5XTDNKqwJ+dfN9BQmRmEhVagsuqHlRiFqCwtGoUOv28+4zM1lv/EpbCmFd5tBFRpi0Di8pXh1eMUneisLC7pITceKM21uH47h3dogLM/w4PpiFtDPudZThOdmaelG7IO6NdmvXttPCsKFxUanM/rg4+sb8l+EB93+foi/dEuKtom6PmVZhFu6Rn/AGWRUhLPFCJ/ltkErGBPg1fEQjXzjTGdytQcpiRIGvKPjqo/gNX0T2EEvZMDcGOy0wie4z2nlux1VFgjCCKrR58HlAiTs/Ok4iiRi5dhwbALNnJnG84fY= X-Microsoft-Antispam-PRVS: X-Exchange-Antispam-Report-Test: UriScan:; X-Exchange-Antispam-Report-CFA-Test: BCL:0;PCL:0;RULEID:(6040176)(601004)(2401047)(8121501046)(5005006)(10201501046)(3002001)(6043046)(6042046);SRVR:VI1PR0801MB1983;BCL:0;PCL:0;RULEID:;SRVR:VI1PR0801MB1983; X-Forefront-PRVS: 0091C8F1EB X-Forefront-Antispam-Report: SFV:NSPM;SFS:(10019020)(4630300001)(6009001)(7916002)(199003)(51744003)(24454002)(189002)(110136003)(33656002)(101416001)(53416004)(86362001)(42186005)(97736004)(7736002)(4001350100001)(305945005)(3846002)(189998001)(54356999)(76176999)(7846002)(6116002)(69596002)(50986999)(77096005)(1076002)(2950100002)(6916009)(92566002)(5660300001)(83506001)(68736007)(23686003)(9686002)(19580395003)(47776003)(50466002)(81156014)(66066001)(6666003)(4326007)(2906002)(105586002)(19580405001)(345774005)(8676002)(81166006)(93886004)(106356001)(586003)(7099028)(18370500001)(26326002)(192303002);DIR:OUT;SFP:1102;SCL:1;SRVR:VI1PR0801MB1983;H:outlook.office365.com;FPR:;SPF:None;PTR:InfoNoRecords;A:1;MX:1;LANG:en; X-Microsoft-Exchange-Diagnostics: =?koi8-r?Q?1;VI1PR0801MB1983;23:N9m4t2Ei2XXEePe/zZSn/bOvk7CQbxORP9B+E0H5U?= =?koi8-r?Q?/DRD8RzX7phwqMQjeRypmvU3+DrePBgNMhxkK3/i4fy5JAXpbSFnhG+zBtzY/3?= =?koi8-r?Q?A6t4SZn2olz5Otx+rsWtNw9qyfBhrOGBXZQkwqhAPbqfzKKYRoABHgr+gLL70Y?= =?koi8-r?Q?PsZDj+Sn8vMdBBj5l5wS69S+QVDk7JNvDBA86vD+ZQl7KrwHA267hLWcSdKSmN?= =?koi8-r?Q?B/OwWEwDG2YSn/rC0x+PeftissUdECba53kAE8jL2s2/wHDQj54BEtaL7v7tzQ?= =?koi8-r?Q?0K7ji9cTa5lLQrGdDA7wMN778y3Yn+p5vihz4tAYlCxiJ0Mg7nIZuAcWQs9EPx?= =?koi8-r?Q?cnxQs2oGrtOAu3IOIfNCgREi71bsK27KV3BeCQUKqYthwpcJEgh5Qfp2umFcpW?= =?koi8-r?Q?XzgEDEcOPVqAK9hMdJfjWK2m5uam2Pe5EZALaTLhQHqQQHHQ59OCz7qKwZjBUa?= =?koi8-r?Q?f7RiVo3uPc/71YGLocmIfIKGg1lCeJ2DMDvvNf54p3aSGowySbveE62VtQwWQG?= =?koi8-r?Q?iEWlbSpml1skWuUVkSGPCWUAoghgmOCgeLd23yZx5BVKuBT/P62uzn9piNMPz3?= =?koi8-r?Q?TiWvNf/Hn62OMtQwlzVN41xoERaKj+s738Jo/7Li5rD45AUYsWOm9RXmSTUG7E?= =?koi8-r?Q?cFjaMlfszNzm7gkdz5YjmxN0VIHy3bW+cXKT1WpIlDkYC7r251G5jo2BZMUgOv?= =?koi8-r?Q?dveblGH8lRvU4OsHRMeEL49csvP8f7OovbWOkM3Oe3Vs+Wi/xWVQu3VgEMo3+8?= =?koi8-r?Q?y+EpNn3dk21AAkw6A4YH/Lo5ksvagQB+BMDSErsDk8XxUf2rVqKSFQCIh9Qp/i?= =?koi8-r?Q?7j6D1PqCZK44pSkc2sq/6iDIxvNiRI5mhrTSOME2dv9/jDeY+Q7yBxrSNwRBWR?= =?koi8-r?Q?LR9ZdkMb6AgCVqbe1L5nERthzwOg4w6z6PB2kGSFtSZU9TXgUvhEC92vMBGKCy?= =?koi8-r?Q?nAf/P25iERmkAgJAZuvLKHl6URj5Y2K5I1xnuBkJC54aVN1+4SFg/NU9jxRCSW?= =?koi8-r?Q?wyOcUYL5AwtSR3+AvC4sMof4GdCAZBKsVLD2uA427NA5hW9LX+qbxS6FfyacaG?= =?koi8-r?Q?sld5cPeZZ8QN1ko1U0GKfoSYomL0dRIoqBSKNIyrN/6yK42CnugYtHlvB7KMQG?= =?koi8-r?Q?3CKrZ/GaybpwC1fwqKZ38hJhJqtiL4OEq8c4ryEnegbrxjeu5vNOy8cuZPOVoz?= =?koi8-r?Q?j5ere5gbyXxGogzAsILGxzIBObJidDm2Jvrlu1RORrELzLLE9PJbUifnC6kRuT?= =?koi8-r?Q?aiDFNpoOkUPwZJ1/QPuETK9GsbaPVvv3qf7OyndwjEq6x88XfA6sgc5tSLMGMk?= =?koi8-r?Q?daB8D7RQXfjozYoaSDRtBQw=3D=3D?= X-Microsoft-Exchange-Diagnostics: 1;VI1PR0801MB1983;6:FYvyjIXfmQF6OCrBLT8ybAitirrnzBn+OUI06SVMD4RQvmXZTMzoRMNZ4raKFC4AP6Orve//NbR3DvNKWmIT8JXH08Si5fMtZoZpaEJGricVNLyzwQ0VyLOoC/wEkRQYxHHPR3ZsQ5epKCnF5be0iabEQZLbHJBTYzdp7eKu47A7+9KqKcZV1lh+EJr++fehW7u1S1LJuYMMTYimyDxd/ap37SFJnX7A7wzdsq7tcyFJ3MxmMZs0toxd4nFxr4oT7gYFd/TxCc0zeXCheug0UYtGNgRpTalE3CvYc3LOxo85guZORh5UJKA2KDmppCHa;5:ltbJYJRSf9AqGE4eKULMQ0gF+dGue8yWrl+VSGs097dQ1c5Q4uMT3ytgqQRlC5hy6QeWPEMTMxM0LXsBp1gSRJVF6hQ6vY4oSKDOa9if/3YYOZkC8qj2tVHuUcoVItoXxbSjwBmxf8bk/uvdLRaT4A==;24:rznlPG+Fpd8AckuuzDuEB7fBLcyaYnYDy1o7AWT6G14D0Y9P/f83HHWesdGlw60nTuiAPVclC77b7K57NQfza2wO5tE3DG8Vk0+y1rx98ec=;7:6EL4JpAByxpmRI8ENLYBHYWfdLB9EE41D5pLtQf+ndOJyREFCwcEFA2t79VwiPlOLc4RnIKavYWW5b7xxCdBfrOEuvjabcJaILkbiKuDjCKJhRz2p5ffJrA7iKxRSFKytHLqwyttD2TiyNi+jGrEzLeCISVURe5771DRDOpJwUZy9lldEH6Z2F2Ni50o+arjjAWy7zZ6Y6kWmtAmBRekM8mxjeYY/5XqN+2vIDSB1LvSxdXdhjeGn/+6von/xbcnCM51fNXqGctICJTQl56Px4dCIeZ9barIxjL+Ifl6U3A9q2m+tTLUJEaaRv/A5DTIYntQ1xByo476CvSej9sW8Q== SpamDiagnosticOutput: 1:99 SpamDiagnosticMetadata: NSPM X-Microsoft-Exchange-Diagnostics: 1;VI1PR0801MB1983;20:mtDCd3qAFcUFnqv6C+e+7XI0sIzGylZBaV0OQMEJfDwng8AWNq1BpDtERZNlE0M8LE7nCj+g7FVUQh1cyNqaTcqdCqOn7Nrz0vgy30PNv4z2AuScqa1rNHAT4Lh5v0Yh6QoWwQfVeiIm+hGRr/ewF04P3+M2weOgdOjTyKW7C60= X-OriginatorOrg: virtuozzo.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 10 Oct 2016 20:42:49.2867 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-Transport-CrossTenantHeadersStamped: VI1PR0801MB1983 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 2910 Lines: 73 On Thu, Oct 06, 2016 at 11:45:48PM -0500, Eric W. Biederman wrote: > Andrei Vagin writes: > > > On Thu, Oct 06, 2016 at 02:46:30PM -0500, Eric W. Biederman wrote: > >> Andrei Vagin 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