summaryrefslogtreecommitdiff
path: root/include/linux/timerqueue.h
diff options
context:
space:
mode:
authorChristian Brauner <brauner@kernel.org>2026-11-01 11:57:21 +0100
committerChristian Brauner <brauner@kernel.org>2026-11-05 15:52:39 +0100
commit309f7a5585aeaf77d3d7c27304ac97e515447dac (patch)
treeeb78d4bdf5a4629dc94bfa731fd858ecacc74bca /include/linux/timerqueue.h
parente7d73cef9726bea49de97ae1fd76405df4050a75 (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