os.walk() consumes a lot of file descriptors

[serhiy-storchaka]

BPO	25995
Nosy	@gvanrossum, @vstinner, @larryhastings, @benhoyt, @vadmium, @serhiy-storchaka
Files	walk_consume_fds_opt1.patch walk_consume_fds_opt2.patch

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/serhiy-storchaka'
closed_at = <Date 2016-02-24.11:05:58.710>
created_at = <Date 2016-01-02.17:57:05.341>
labels = ['library', 'performance']
title = 'os.walk() consumes a lot of file descriptors'
updated_at = <Date 2016-02-24.11:05:58.709>
user = 'https://github.com/serhiy-storchaka'

bugs.python.org fields:

activity = <Date 2016-02-24.11:05:58.709>
actor = 'serhiy.storchaka'
assignee = 'serhiy.storchaka'
closed = True
closed_date = <Date 2016-02-24.11:05:58.710>
closer = 'serhiy.storchaka'
components = ['Library (Lib)']
creation = <Date 2016-01-02.17:57:05.341>
creator = 'serhiy.storchaka'
dependencies = []
files = ['41482', '41483']
hgrepos = []
issue_num = 25995
keywords = ['patch']
message_count = 13.0
messages = ['257352', '257404', '258018', '258022', '258025', '258096', '258116', '258238', '260089', '260095', '260784', '260788', '260789']
nosy_count = 7.0
nosy_names = ['gvanrossum', 'vstinner', 'larry', 'benhoyt', 'python-dev', 'martin.panter', 'serhiy.storchaka']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'resource usage'
url = 'https://bugs.python.org/issue25995'
versions = ['Python 3.5', 'Python 3.6']

[serhiy-storchaka]

Since 3.5 os.walk() consumes a lot of file descriptors. Its number equals to the deep of directories tree. Since the number of file descriptors is limited, this can cause problems.

This was the main reason for rejecting fwalk-based implementation of os.walk() (bpo-15200).

[serhiy-storchaka]

Here are two alternative solutions for this issue.

[gvanrossum]

I don't like the first solution (it just collects all scandir() results in a list, which defeats one of the purposes of using scandir()), but I don't understand the second solution.

Ideally the number of FDs used should be limited by the depth of the tree being walked, right?

[serhiy-storchaka]

Both patches are basically equivalent. The first one collects all scandir() results in a list, the second one collects only directory names in a list. The purpose of using os.scandir() in os.walk() was a speed up (bpo-23605), and both patches preserve it.

Yes, the number of FDs used is equivalent to the depth of the tree which can be very deep (I just created a tree depth of 1000 levels). And what is worse, all these FDs can be effectively leaked if the walking was not finished. This is unwanted behavior change.

[gvanrossum]

I am all for preventing the leaks. But using FDs proportional to the tree
depth seems reasonable to me. (If you are worried about some kind of DoS
attack on the algorithm by someone who can build a tree with depth 1000,
well, if they can do that they can also create a flat folder with a million
files in it.)

Is there a potential hybrid strategy, where for small directories we close
the FD but for large directories we keep it open?

[serhiy-storchaka]

But using FDs proportional to the tree depth seems reasonable to me.

This was the main reason for rejecting bpo-15200. May be we can allow this for globbing, but only explicitly enabled with special parameter or separate functions. The benefit for globbing is starting to yield results without internal caching. The benefit for os.walk() is smaller, because in any case it yields files and directories not one-by-one, but collected into lists.

Is there a potential hybrid strategy, where for small directories we close
the FD but for large directories we keep it open?

May be with more complicated code. I think this needs explicit close() method, so it can go only in 3.6. For now I think we have to commit one of my patches (the difference only stylistic).

[gvanrossum]

I like them both, if I had to choose I'd pick patch 2.

But yes, we need to add a close() method to the scandir iterator object.

In the meantime, I am still worried about what would happen if somehow the loop got interrupted and the frame got kept alive and the iterator wasn't closed by its dealloc until much later. This kind of thing was common in asyncio and we had to resort to similar tricks to break some cycles. Maybe you can add a try/finally that *deletes* scandir_it to force it to close itself (at least in CPython)? That can go into 3.5.

[serhiy-storchaka]

Yes, OSError, MemoryError and KeyboardInterrupt can be raised during iterating scandir object or calling is_dir() or is_symlink() methods of the result. They stop iterating and left file descriptor open. If close file descriptor on error during iteration (bpo-26117), patch 1 becomes more safe, because it minimizes the lifetime of opened descriptor.

[python-dev]

New changeset e951d76f1945 by Serhiy Storchaka in branch '3.5':
Issue bpo-25995: os.walk() no longer uses FDs proportional to the tree depth.
https://hg.python.org/cpython/rev/e951d76f1945

New changeset 6197a09a56b1 by Serhiy Storchaka in branch 'default':
Issue bpo-25995: os.walk() no longer uses FDs proportional to the tree depth.
https://hg.python.org/cpython/rev/6197a09a56b1

[serhiy-storchaka]

walk_consume_fds_opt1.patch is applied in 3.5 (it is more reliable with the absence of close()) and walk_consume_fds_opt2.patch is applied in 3.6.

[vadmium]

The change seems to be causing some Windows buildbot failures <http://buildbot.python.org/all/builders/AMD64%20Windows7%20SP1%203.5/builds/666/steps/test/logs/stdio\>:

======================================================================
ERROR: test_walk_bad_dir (test.test_os.BytesWalkTests)
----------------------------------------------------------------------

Traceback (most recent call last):
  File "C:\buildbot.python.org\3.5.kloth-win64\build\lib\test\test_os.py", line 931, in test_walk_bad_dir
    root, dirs, files = next(walk_it)
  File "C:\buildbot.python.org\3.5.kloth-win64\build\lib\test\test_os.py", line 1027, in walk
    for broot, bdirs, bfiles in os.walk(os.fsencode(top), **kwargs):
  File "C:\buildbot.python.org\3.5.kloth-win64\build\lib\os.py", line 372, in walk
    entries = list(scandir(top))
TypeError: os.scandir() doesn't support bytes path on Windows, use Unicode instead

======================================================================
ERROR: test_walk_bottom_up (test.test_os.BytesWalkTests)
ERROR: test_walk_prune (test.test_os.BytesWalkTests)

Was this line

entries = list(scandir(top))

meant to be

entries = list(scandir_it)