bug#81616: [PATCH] tail: hash follow-by-name directory events
Iván Ezequiel Rodriguez <[email protected]>
| Newsgroups | gmane.comp.gnu.core-utils.bugs |
|---|---|
| Message-ID | <[email protected]> |
Replace the O(N) scan of watched names on each directory inotify event with a Hash_table keyed by (parent_wd, basename), addressing the long-standing FIXME in tail_forever_inotify. Keep ownership consistent with wd_to_name: parent_by_name is created only for Follow_name and returned to the caller, so fallback paths can return without local hash cleanup. Matching cost for N directory events that each compare against N names (illustrative host timings of the scan vs hash lookup alone): N=1000: ~0.018s -> ~0.000s N=5000: ~0.39s -> ~0.000s N=10000: ~1.5s -> ~0.000s End-to-end recreate storms remain largely file-system bound on this host; the hash removes the quadratic name-matching CPU from that path. * src/tail.c (parent_name_hasher, parent_name_comparator): New. (tail_forever_inotify): Build and use parent_by_name; return it to the caller. (main): Free parent_ht when non-NULL. * tests/tail/inotify-parent-hash.sh: Require notification mode; cover multiple names in one directory and the same basename in two directories. * tests/local.mk: Reference the new test. * NEWS: Mention the improvement. Signed-off-by: Iván Ezequiel Rodriguez <[email protected]> --- NEWS | 4 ++ src/tail.c | 84 +++++++++++++++++----- tests/local.mk | 1 + tests/tail/inotify-parent-hash.sh | 116 ++++++++++++++++++++++++++++++ 4 files changed, 188 insertions(+), 17 deletions(-) create mode 100755 tests/tail/inotify-parent-hash.sh diff --git a/NEWS b/NEWS index 17a6333d3..2e3f1dbd6 100644 --- a/NEWS +++ b/NEWS @@ -95,6 +95,10 @@ GNU coreutils NEWS -*- outline -*- ** Improvements + 'tail -F' now matches directory inotify events with a hash keyed by + (parent watch descriptor, basename), avoiding an O(N) scan per event when + following many files by name. + When built with the configure option '--with-wtmpdb', invocations of 'who /var/log/wtmp' and 'users /var/log/wtmp' use the wtmpdb database instead of the file /var/log/wtmp. This makes them Y2038-safe. diff --git a/src/tail.c b/src/tail.c index 2ca27e835..efeb8bfb4 100644 --- a/src/tail.c +++ b/src/tail.c @@ -1428,6 +1428,30 @@ wd_comparator (const void *e1, const void *e2) return spec1->wd == spec2->wd; } +/* Hash Follow_name watches by parent directory wd + basename so directory + inotify events can be matched in expected O(1) instead of scanning all + files. */ +static size_t +parent_name_hasher (const void *entry, size_t tabsize) +{ + const struct File_spec *spec = entry; + char const *name = spec->name + spec->basename_start; + size_t value = spec->parent_wd; + for (unsigned char c; (c = *name); name++) + value = value * 31 + c; + return value % tabsize; +} + +static bool +parent_name_comparator (const void *e1, const void *e2) +{ + const struct File_spec *a = e1; + const struct File_spec *b = e2; + return (a->parent_wd == b->parent_wd + && streq (a->name + a->basename_start, + b->name + b->basename_start)); +} + /* Output (new) data for FSPEC->fd. PREV_FSPEC records the last File_spec for which we output. */ static void @@ -1476,10 +1500,17 @@ check_fspec (struct File_spec *fspec, struct File_spec **prev_fspec) /* Attempt to tail N_FILES files forever, or until killed. Check modifications using the inotify events system. - Exit if finished or on fatal error; return to revert to polling. */ + Exit if finished or on fatal error; return to revert to polling. + + On return (to revert to polling), *WD_TO_NAMEP and *PARENT_BY_NAMEP + hold hash tables the caller must free. *PARENT_BY_NAMEP is non-NULL + only when follow_mode == Follow_name; otherwise it is set to NULL. + Like WD_TO_NAME, PARENT_BY_NAME is owned by the caller so return + paths need not free it (and must not call hash_free (NULL)). */ static void tail_forever_inotify (int wd, struct File_spec *f, int n_files, - double sleep_interval, Hash_table **wd_to_namep) + double sleep_interval, Hash_table **wd_to_namep, + Hash_table **parent_by_namep) { # if TAIL_TEST_SLEEP /* Delay between open() and inotify_add_watch() @@ -1491,6 +1522,9 @@ tail_forever_inotify (int wd, struct File_spec *f, int n_files, /* Map an inotify watch descriptor to the name of the file it's watching. */ Hash_table *wd_to_name; + /* Map (parent_wd, basename) -> File_spec for Follow_name directory events. */ + Hash_table *parent_by_name = NULL; + bool found_watchable_file = false; bool tailed_but_unwatchable = false; bool found_unwatchable_dir = false; @@ -1500,12 +1534,23 @@ tail_forever_inotify (int wd, struct File_spec *f, int n_files, char *evbuf; idx_t evbuf_off = 0; + *parent_by_namep = NULL; + wd_to_name = hash_initialize (n_files, NULL, wd_hasher, wd_comparator, NULL); if (! wd_to_name) xalloc_die (); *wd_to_namep = wd_to_name; + if (follow_mode == Follow_name) + { + parent_by_name = hash_initialize (n_files, NULL, parent_name_hasher, + parent_name_comparator, NULL); + if (! parent_by_name) + xalloc_die (); + *parent_by_namep = parent_by_name; + } + /* The events mask used with inotify on files (not directories). */ uint32_t inotify_wd_mask = IN_MODIFY; /* TODO: Perhaps monitor these events in Follow_descriptor mode also, @@ -1555,6 +1600,9 @@ tail_forever_inotify (int wd, struct File_spec *f, int n_files, of the inotify API will still be diagnosed. */ break; } + + if (hash_insert (parent_by_name, &(f[i])) == NULL) + xalloc_die (); } f[i].wd = inotify_add_watch (wd, f[i].name, inotify_wd_mask); @@ -1733,29 +1781,27 @@ tail_forever_inotify (int wd, struct File_spec *f, int n_files, if (ev->len) /* event on ev->name in watched directory. */ { - int j; - for (j = 0; j < n_files; j++) - { - /* With N=hundreds of frequently-changing files, this O(N^2) - process might be a problem. FIXME: use a hash table? */ - if (f[j].parent_wd == ev->wd - && streq (ev->name, f[j].name + f[j].basename_start)) - break; - } + struct File_spec key; + if (! parent_by_name) + continue; + + /* Probe key: basename is the whole string at KEY.NAME. */ + key.parent_wd = ev->wd; + key.name = ev->name; + key.basename_start = 0; + fspec = hash_lookup (parent_by_name, &key); /* It is not a watched file. */ - if (j == n_files) + if (! fspec) continue; - fspec = &(f[j]); - int new_wd = -1; bool deleting = !! (ev->mask & IN_DELETE); if (! deleting) { /* Adding the same inode again will look up any existing wd. */ - new_wd = inotify_add_watch (wd, f[j].name, inotify_wd_mask); + new_wd = inotify_add_watch (wd, fspec->name, inotify_wd_mask); } if (! deleting && new_wd < 0) @@ -1768,7 +1814,7 @@ tail_forever_inotify (int wd, struct File_spec *f, int n_files, else { /* Can get ENOENT for a dangling symlink for example. */ - error (0, errno, _("cannot watch %s"), quoteaf (f[j].name)); + error (0, errno, _("cannot watch %s"), quoteaf (fspec->name)); } /* We'll continue below after removing the existing watch. */ } @@ -2517,8 +2563,12 @@ main (int argc, char **argv) write_error (); Hash_table *ht; - tail_forever_inotify (wd, F, n_files, sleep_interval, &ht); + Hash_table *parent_ht = NULL; + tail_forever_inotify (wd, F, n_files, sleep_interval, + &ht, &parent_ht); hash_free (ht); + if (parent_ht) + hash_free (parent_ht); close (wd); errno = 0; } diff --git a/tests/local.mk b/tests/local.mk index 33abb9d72..7ad6b852d 100644 --- a/tests/local.mk +++ b/tests/local.mk @@ -193,6 +193,7 @@ all_tests = \ tests/tail/basic-seek.sh \ tests/tail/inotify-hash-abuse.sh \ tests/tail/inotify-hash-abuse2.sh \ + tests/tail/inotify-parent-hash.sh \ tests/tail/F-vs-missing.sh \ tests/tail/F-vs-rename.sh \ tests/tail/F-headers.sh \ diff --git a/tests/tail/inotify-parent-hash.sh b/tests/tail/inotify-parent-hash.sh new file mode 100755 index 000000000..0f430dd84 --- /dev/null +++ b/tests/tail/inotify-parent-hash.sh @@ -0,0 +1,116 @@ +#!/bin/sh +# Exercise Follow_name directory-event lookup keyed by (parent_wd, basename). +# Covers several names in one directory and the same basename in two dirs. + +# Copyright (C) 2026 Free Software Foundation, Inc. + +# This program is free software: you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation, either version 3 of the License, or +# (at your option) any later version. + +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. + +# You should have received a copy of the GNU General Public License +# along with this program. If not, see <https://www.gnu.org/licenses/>. + +. "${srcdir=.}/tests/init.sh"; path_prepend_ ./src +print_ver_ tail +require_inotify_supported_ + +check_tail_output() +{ + local delay="$1" + grep "$tail_re" out > /dev/null || + { sleep $delay; return 1; } +} + +cleanup_() { kill $pid 2>/dev/null && wait $pid; } + +cleanup_fail() +{ + cat out + warn_ "$1" + cleanup_ + fail=1 +} + +# Ensure this run actually uses inotify (not a silent fallback to polling). +assert_notification_mode_() +{ + inotify_failed_re='inotify (resources exhausted|cannot be used)' + grep -E "$inotify_failed_re" out && + skip_ "inotify can't be used" + tail_re='using notification mode' retry_delay_ check_tail_output .1 7 || + cleanup_fail 'tail did not use notification mode' +} + +# --- Several basenames in the same parent directory. --- +mkdir d || framework_failure_ +touch d/a d/b d/c || framework_failure_ + +rm -f out +timeout 60 tail --debug -qF d/a d/b d/c > out 2>&1 & pid=$! + +assert_notification_mode_ + +echo a1 > d/a || framework_failure_ +tail_re='^a1$' retry_delay_ check_tail_output .1 7 || + cleanup_fail 'missing a1' + +echo b1 > d/b || framework_failure_ +tail_re='^b1$' retry_delay_ check_tail_output .1 7 || + cleanup_fail 'missing b1' + +echo c1 > d/c || framework_failure_ +tail_re='^c1$' retry_delay_ check_tail_output .1 7 || + cleanup_fail 'missing c1' + +# Recreate each name so directory CREATE events must resolve the right +# File_spec via (parent_wd, basename), not a linear scan of the wrong peer. +rm -f d/a d/b d/c || framework_failure_ +echo a2 > d/a || framework_failure_ +tail_re='^a2$' retry_delay_ check_tail_output .1 7 || + cleanup_fail 'missing a2' +echo b2 > d/b || framework_failure_ +tail_re='^b2$' retry_delay_ check_tail_output .1 7 || + cleanup_fail 'missing b2' +echo c2 > d/c || framework_failure_ +tail_re='^c2$' retry_delay_ check_tail_output .1 7 || + cleanup_fail 'missing c2' + +kill -0 $pid || fail=1 +cleanup_ + +# --- Same basename in two different parent directories. --- +mkdir e1 e2 || framework_failure_ +touch e1/log e2/log || framework_failure_ + +rm -f out +timeout 60 tail --debug -qF e1/log e2/log > out 2>&1 & pid=$! + +assert_notification_mode_ + +echo e1x > e1/log || framework_failure_ +tail_re='^e1x$' retry_delay_ check_tail_output .1 7 || + cleanup_fail 'missing e1x' + +echo e2x > e2/log || framework_failure_ +tail_re='^e2x$' retry_delay_ check_tail_output .1 7 || + cleanup_fail 'missing e2x' + +rm -f e1/log e2/log || framework_failure_ +echo e1y > e1/log || framework_failure_ +tail_re='^e1y$' retry_delay_ check_tail_output .1 7 || + cleanup_fail 'missing e1y' +echo e2y > e2/log || framework_failure_ +tail_re='^e2y$' retry_delay_ check_tail_output .1 7 || + cleanup_fail 'missing e2y' + +kill -0 $pid || fail=1 +cleanup_ + +Exit $fail -- 2.43.0