NotificationsYou must be signed in to change notification settings
Fork32.2k
Star67.7k

gh-89727: Fix os.fwalk RecursionError on deep trees#100347

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Jump to bottom

Closed

jonburdo wants to merge31 commits intopython:mainfromjonburdo:iterative-os-fwalk

Closed

gh-89727: Fix os.fwalk RecursionError on deep trees#100347

jonburdo wants to merge31 commits intopython:mainfromjonburdo:iterative-os-fwalk

Conversation

Copy link

Contributor

jonburdo commentedDec 19, 2022•
edited by bedevere-bot
Loading

Use a stack to implement os.fwalk iteratively instead of recursively to avoid hitting recursion limits on deeply nested trees.

Similar to how this is done foros.walk in#99803

Issue:Change shutil.rmtree and os.walk to support very deep hierarchies #89727

jonburdo added2 commits

December 19, 2022 09:40

fix os.walk RecursionError on deep trees

d9f6f44

use _WalkAction enum

61b8078

bedevere-bot mentioned this pull request

Dec 19, 2022

Change shutil.rmtree and os.walk to support very deep hierarchies#89727

Open

bedevere-bot added the awaiting review label

Dec 19, 2022

Copy link

bedevere-bot commentedDec 19, 2022

Most changes to Pythonrequire a NEWS entry.

Please add it using theblurb_it web app or theblurb command-line tool.

Merge branch 'main' into iterative-os-fwalk

d5e2042

Copy link

bedevere-bot commentedDec 19, 2022

Most changes to Pythonrequire a NEWS entry.

Please add it using theblurb_it web app or theblurb command-line tool.

Copy link

ContributorAuthor

jonburdo commentedDec 19, 2022•
edited
Loading

TODO:

Oncegh-89727: Fix os.walk RecursionError on deep trees #99803 is merged,this line can be removed so thatFwalkTests will runtest_walk_above_recursion_limit to prevent a regression

AlexWaygood reviewed

Dec 19, 2022

View reviewed changes

Lib/os.py OutdatedShow resolvedHide resolved

jonburdoand others added13 commits

December 20, 2022 10:05

fix formatting

90c123b

remove enum from os

570818b

add blurb

30aeed7

pythongh-89727: Fix os.walk RecursionError on deep trees (python#99803)

55e17b8

Use a stack to implement os.walk iteratively instead of recursively toavoid hitting recursion limits on deeply nested trees.

pythongh-69929: re docs: Add more specific definition of \w (python#9…

f41cef6

…2015)Co-authored-by: Jelle Zijlstra <jelle.zijlstra@gmail.com>

pythongh-89051: Add ssl.OP_LEGACY_SERVER_CONNECT (python#93927)

33ba6a5

Co-authored-by: blurb-it[bot] <43283697+blurb-it[bot]@users.noreply.github.com>Co-authored-by: Christian Heimes <christian@python.org>Co-authored-by: Hugo van Kemenade <hugovk@users.noreply.github.com>Fixespython#89051

pythongh-88211: Change lower-case and upper-case to match recommendat…

f9b6796

…ions in imaplib docs (python#99625)

pythongh-100348: Fix ref cycle inasyncio._SelectorSocketTransport…

77d160f

…with `_read_ready_cb` (python#100349)

pythongh-99925: Fix inconsistency injson.dumps()error messages (p…

db820a2

…ythonGH-99926)

Clarify that every thread has its own default context in contextvars (p…

c39ce63

…ython#99246)

run test_walk_above_recursion_limit for fwalk

8d2befb

set stack outside try-except in fwalk

d29188e

fix comments

2cf7550

jonburdo requested review froma team,1st1,asvetlov,gvanrossum andkumaraditya303 ascode owners

December 20, 2022 15:08

Merge branch 'main' into iterative-os-fwalk

f2cca94

AlexWaygood removed request fora team and1st1

December 20, 2022 15:13

gpshead self-requested a review

December 24, 2022 02:45

jonburdo marked this pull request as draft

January 4, 2023 22:56

jonburdo added5 commits

March 23, 2023 09:03

Merge branch 'main' into iterative-os-fwalk

9eedf9a

add more reliable file descriptor closing logic in os.fwalk

5ee50c6

Make sure file descriptors get closed if an exception occurs right after the file descriptor was popped from the stack. Also catch exceptions thrown by calling os.close on an already-closed file-descriptor when doing file descriptor cleanup.

use a separate fd_stack for simpler cleanup and error handling

f0f9330

Merge branch 'main' into iterative-os-fwalk

ccfb955

run test_walk_above_recursion_limit with fwalk tests

598bdf9

arhadthedev added the stdlibPython modules in the Lib dir label

Mar 23, 2023

Copy link

ContributorAuthor

jonburdo commentedMar 23, 2023•
edited
Loading

Note that handling of a single exception should function the same, but repeated errors will interrupt the file descriptor cleanup (closing).

Imagine a user holds downctrl-c sending a burst ofKeyboardExceptions. Previously in the recursive version there were nested try-finally statements making sureclose(fd) gets called. I believe each exception might cause one of theseclose(fd) calls to be missed (if it occurs in the finally beforeclose(fd) is executed), but after the burst of exceptions is over, the remaining calls would be made. Now the cleanup is handled in a loop, so a single exception would end the fd cleanup:

try:            ...except:forfdinreversed(fd_stack):try:close(fd)exceptOSError:passraise

I'm not sure this is a problem. If I understand correctly, neither versions handles this perfectly. It seemed worth mentioning though.

I thought about changing theexcept OSError: is this cleanup loop to a bareexcept:, but then you get kind of a weird, inconsistent behavior where aKeyboardInterrupt that happens to fall just before the try-except starts will end the loop, but one that falls in the try-except won't.

jonburdo marked this pull request as ready for review

March 23, 2023 15:16

jonburdo requested review fromAlexWaygood and removed request forgpshead

March 24, 2023 00:35

Copy link

ContributorAuthor

jonburdo commentedMar 24, 2023

Opening this up for review in response to#89727 (comment)

barneygale reviewed

Mar 24, 2023

View reviewed changes

Lib/os.py OutdatedShow resolvedHide resolved

jonburdo added4 commits

March 24, 2023 17:08

Merge branch 'main' into iterative-os-fwalk

c158be3

make sure we don't close the same fd twice

6608a6a

If an exception occurred between `close(fd_stack[-1])` and `fd_stack.pop()`, then we would close the fd a second time in the except clause. It would be better to risk leaving the fd open, as the previous implementation of fwalk could

revert to using a single stack instead of a separate ffd stack

d026146

remove unused variable

762c03a

barneygale approved these changes

Mar 30, 2023

View reviewed changes

Copy link

Contributor

barneygale left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

LGTM, nice work!

bedevere-bot added awaiting merge and removed awaiting review labels

Mar 30, 2023

Copy link

Contributor

barneygale commentedMar 31, 2023•
edited
Loading

A thought: could you merge_fwalk() intofwalk()? As we're no longer calling_fwalk() recursively, the separation appears pointless, and theyield from indirection will have a small performance cost.

barneygale reviewed

Mar 31, 2023

View reviewed changes

Lib/os.py Outdated

Comment on lines 563 to 570

		except:
		for action, value in reversed(stack):
		if action is _WalkAction.CLOSE:
		try:
		close(value)
		except OSError:
		pass
		raise

Copy link

Contributor

barneygaleMar 31, 2023

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

Could this be afinally: block?

Copy link

ContributorAuthor

jonburdoMar 31, 2023

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

Sure, would you consider that more readable or explicit? I just didn't see any benefit, since this is only needed if an exception occurs. The only functional difference would be that we'd iterate over an empty list if no exceptions occur right?

Copy link

Contributor

barneygaleApr 1, 2023

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

I think I'd consider it more explicit, though feel free to wait for another opinion if you'd like.

Copy link

Member

AlexWaygoodApr 1, 2023

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

I'd also preferfinally here. Not sure if it actually delivers any functional benefit here (can't remember the exact semantics off the top of my head...), but it does feel at least more readable to me.

Copy link

ContributorAuthor

jonburdoApr 1, 2023

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

Makes sense, thanks for clarifying. I'll change it tofinally. Functionally, I thinkfinally is slightly worse but it's negligible.

In this case, changing tofinally is functionally equivalent to adding anelse clause with the same for-loop:

try:            ...except:foraction,valueinreversed(stack): ...raiseelse:foraction,valueinreversed(stack): ...

If no exception occurs in thetry, thenstack will be empty and all of the fds will have been closed already. So changing tofinally means we're adding a step where we simply iterate over an empty list - unnecessary, but costs almost nothing.

To me, a bareexcept indicates a cleanup step, butfinally is even more explicit, so it probably makes sense here.

jonburdoand others added4 commits

April 1, 2023 11:16

get rid of unnecessary os._fwalk

045fd88

change except clause to finally clause in os.fwalk

f3f793a

Merge branch 'main' into iterative-os-fwalk

dfb9685

Merge branch 'main' into iterative-os-fwalk

0ebc475

Copy link

Contributor

barneygale commentedJun 1, 2024

@jonburdo I've fixed this in another PR -#119638. Shamefully I forgot about this PR :(.

Comparing our code, I think we arrived at similar solutions, the main difference being that I moved thelstat() of directory entries our of thescandir() loop. If there's anything you think I've missed in my implementation please let me know or log another PR and I'll review. Thanks and sorry.