From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from rock.gnat.com (rock.gnat.com [205.232.38.15]) by sourceware.org (Postfix) with ESMTPS id 7C06C383D807; Thu, 23 Jun 2022 01:02:37 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 7C06C383D807 Received: from localhost (localhost.localdomain [127.0.0.1]) by filtered-rock.gnat.com (Postfix) with ESMTP id 02F8C1160E6; Wed, 22 Jun 2022 21:02:37 -0400 (EDT) X-Virus-Scanned: Debian amavisd-new at gnat.com Received: from rock.gnat.com ([127.0.0.1]) by localhost (rock.gnat.com [127.0.0.1]) (amavisd-new, port 10024) with LMTP id HE87eEcJO4X5; Wed, 22 Jun 2022 21:02:36 -0400 (EDT) Received: from free.home (tron.gnat.com [IPv6:2620:20:4000:0:46a8:42ff:fe0e:e294]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by rock.gnat.com (Postfix) with ESMTPS id BB2221160DD; Wed, 22 Jun 2022 21:02:36 -0400 (EDT) Received: from livre (livre.home [172.31.160.2]) by free.home (8.15.2/8.15.2) with ESMTPS id 25N128rk745245 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Wed, 22 Jun 2022 22:02:09 -0300 From: Alexandre Oliva To: Jonathan Wakely Cc: gcc Patches , "libstdc++" Subject: Re: [PATCH] libstdc++: retry removal of dir entries if dir removal fails Organization: Free thinker, does not speak for AdaCore References: Errors-To: aoliva@lxoliva.fsfla.org Date: Wed, 22 Jun 2022 22:02:08 -0300 In-Reply-To: (Jonathan Wakely's message of "Wed, 22 Jun 2022 10:45:13 +0100") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.2 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-Scanned-By: MIMEDefang 2.84 X-Spam-Status: No, score=-6.3 required=5.0 tests=BAYES_00, KAM_DMARC_STATUS, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: libstdc++@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libstdc++ mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 23 Jun 2022 01:02:39 -0000 On Jun 22, 2022, Jonathan Wakely wrote: > It looks like it would be possible for this to livelock. True > The current > implementation will fail with an error in that case, rather than > getting stuck forever in a loop. In the equivalent livelock scenario, newly-added dir entries are added to the end of the directory, and get visited in the same readdir iteration, so you never reach the end as long as the entry-creator runs faster than the remover. > It would be possible to add a __rewind member to directory iterators > too, to call rewinddir after each modification to the directory. That would likely lead to O(n^2) behavior in some implementations, in which remove entries get rescanned over and over, whereas the approach I proposed cuts that down to O(nlogn). Unless you rewind once you hit the end after successful removals, even before trying to remove the dir. That's still a little wasteful on POSIX-compliant targets, because you rewind and rescan a dir that should already be empty. I aimed for minimizing the overhead on compliant targets, but that was before remove_all switched to recursive iterators. With recursive iterators, rewinding might be better done in a custom iterator, tuned for recursive removal, that knows to rewind a dir if there were removals in it or something. Rewinding the entire recursive removal is not something I realized my rewritten patch did. I still had the recursive remove_all implementation in cache. Oops ;-) That said, I'm not sure it makes much of a difference in the end. As long as the recursion and removal doesn't treat symlinks as dirs (which IIUC requires openat and unlinkat, so that's a big if to boot), the rewinding seems to only change the nature of filesystem race conditions that recursive removal enables. E.g., consider that you start removing the entries in a dir, and then the dir you're visiting is moved out of the subtree you're removing, and other dirs are moved into it: the recursive removal with openat and unlinkat will happily attempt to wipe out everything moved in there, even if it wasn't within that subtree at the time of the remove_all request, and even if the newly-moved dirs were never part of the subtree whose removal was requested. To make it clearer: c++::std::filesystem::remove_all foo/bar & mv foo/bar/temp temp mv foo temp wait ls -d temp/foo temp/foo might be removed if you happened to be iterating in temp when the 'mv' commands run. Is that another kind of race that needs to be considered? If a dir is moved while we're visiting it, should we stop visiting it? What about its parent? -- Alexandre Oliva, happy hacker https://FSFLA.org/blogs/lxo/ Free Software Activist GNU Toolchain Engineer Disinformation flourishes because many people care deeply about injustice but very few check the facts. Ask me about