diff options
| author | Christian Brauner <brauner@kernel.org> | 2026-11-01 11:57:21 +0100 |
|---|---|---|
| committer | Christian Brauner <brauner@kernel.org> | 2026-11-05 15:52:39 +0100 |
| commit | 309f7a5585aeaf77d3d7c27304ac97e515447dac (patch) | |
| tree | eb78d4bdf5a4629dc94bfa731fd858ecacc74bca /include/linux/timerqueue.h | |
| parent | e7d73cef9726bea49de97ae1fd76405df4050a75 (diff) | |
libfs: walk offset directories in offset order
offset_iterate_dir() walks d_children from the head and only uses the
maple tree to map ctx->pos back to a dentry when a getdents64() call
resumes. offset_dir_lookup() finds the entry at ctx->pos, or the one
with the next lower offset if it is gone, and the list walk continues
from there.
That only works if list order and offset order agree and quite often
they don't. A rename over an existing name gives the moved dentry the
offset of the name it replaced but __d_move() puts it at the head of
d_children. RENAME_EXCHANGE does the same to both dentries. And once
the cyclic offset allocator wraps new entries get low offsets at the
head of the list.
So if the entry at ctx->pos is unlinked between two getdents64() calls
we resume at the entry with the next lower offset and that one can sit
anywhere in the list:
(1) If it sits further down the list everything in between is skipped.
Create y, t, a, b and rename b over t. The list is now t(4) a(5)
y(3). Stop the listing at t and unlink t. The next call resumes at
y and a is never returned although nobody touched it.
(2) If there is no lower entry we restart at the head and return the
whole directory again. Nickolai reported this for the simple case
of unlinking the oldest entry while a listing is about to reach it.
Ending the walk there instead turns this into (1): create a, b, c,
rename c over a, stop the listing at the renamed entry, unlink it,
and b is lost.
Instead of the list let's walk the maple tree itself in descending
offset order. Then ctx->pos really means that everything above it has
been emitted and resuming at the highest offset at or below it is right
no matter where the dentry sits in d_children. Entries created or
renamed to a new name after the listing started get an offset above
ctx->pos and aren't returned, same as with the list walk which never
went back to the head. So a readdir loop that renames or creates an
entry for each one it reads still terminates.
The maple tree can't change under us as all modifications happen with
the directory's i_rwsem held exclusive and offset_readdir() holds it
shared. That also covers the dentries in the tree. They are all
persistent and only unlink, rmdir and rename remove or rename them. And
since the previous patch i_rwsem is the lock of the tree. So keep a
single ma_state across the walk and emit directly from the dentry
without taking rcu_read_lock(), a reference or d_lock.
This also makes the walk cheaper than the list walk was. With a million
entries on tmpfs a getdents64() listing goes from 146ms to 114ms. With
four processes listing the directory at the same time it goes from
470ms to 113ms per listing as they don't bounce the parent's d_lock and
the dentries' lockrefs between them anymore.
base v2 this
1M entries, getdents64 32k buffer (ms) 146 127 114
1M entries, getdents64 1k buffer (ms) 184 156 141
1M entries, getdents64 128b buffer (ms) 429 364 335
1M entries, ls -f (s) 0.259 0.239 0.228
1M entries, LC_ALL=C ls (s) 0.482 0.467 0.455
1M entries, 4 parallel listers (ms) 470 125 113
18 entries, rewind and list (ns) 4107 3594 3323
250k of 1M left, getdents64 32k (ms) 58.8 57.8 53.8
250k of 1M left, getdents64 128b (ms) 128 114 108
Fixes: b9b588f22a0c ("libfs: Use d_children list to iterate simple_offset directories")
Fixes: f70681e9e606 ("libfs: Fix duplicate directory entry in offset_dir_lookup")
Reported-by: Nickolai Zeldovich <nickolai@csail.mit.edu>
Link: https://patch.msgid.link/20261018024549.798968-1-nickolai@csail.mit.edu
Link: https://patch.msgid.link/20261101-work-libfs-offset_readdir-v2-2-c621125b56d1@kernel.org
Reviewed-by: Chuck Lever <cel@kernel.org>
Signed-off-by: Christian Brauner (Amutable) <brauner@kernel.org>
Diffstat (limited to 'include/linux/timerqueue.h')
0 files changed, 0 insertions, 0 deletions
