[PATCH 0/7] Performance improvement for fanotify merge

[Amir Goldstein <amir73il@gmail.com>]

Jan,

fanotify_merge() has been observed [1] to consume a lot of CPU.
This is not surprising considering that it is implemented as a linear
search on a practically unbounded size list.

The following series improves the linear search for an event to merge
in three different ways:
1. Hash events into as much as to 128 lists
2. Limit linear search to 128 last list elements
3. Use a better key - instead of victim inode ptr, use a hash of all
   the compared fields

The end result can be observed in the test run times below.
The test is an extension of your queue overflow LTP test [2].
The timing results use are from the 2nd run of -i 2, where files
are already existing in the test fs.

With an unlimited queue, queueing of 16385 events on unique objects
is ~3 times faster than before the change.

In fact, the run time of queueing 16385 events (~600ms) is almost the
same as the run time of rejecting 16385 events (~550ms) due to full
queue, which suggest a very low overhead for merging events.

The test runs two passes to test event merge, the "create" pass and
the "open" pass.

Before the change (v5.11-rc2) 100% of the events of the "open" pass
are merged (16385 files and 16385 events).

After the change, only %50 of the events of the "open" pass are
merged (16385 files and 25462 events).

This is because 16384 is the maximum number of events that we can
merge when hash table is fully balanced.
When reducing the number of unique objects to 8192, all events
on the "open" pass are merged.

Thanks,
Amir.

v5.11-rc2, run #2 of ./fanotify05 -i 2:

fanotify05.c:109: TINFO: Test #0: Limited queue
fanotify05.c:98: TINFO: Created 16385 files in 1653ms
fanotify05.c:98: TINFO: Opened 16385 files in 543ms
fanotify05.c:77: TINFO: Got event #0 filename=fname_0
fanotify05.c:176: TPASS: Got an overflow event: pid=0 fd=-1
fanotify05.c:182: TINFO: Got 16385 events

fanotify05.c:109: TINFO: Test #1: Unlimited queue
fanotify05.c:98: TINFO: Created 16385 files in 1683ms
fanotify05.c:98: TINFO: Opened 16385 files in 1647ms
fanotify05.c:77: TINFO: Got event #0 filename=fname_0
fanotify05.c:138: TPASS: Overflow event not generated!
fanotify05.c:182: TINFO: Got 16385 events

fanotify_merge branch, run #2 of ./fanotify05 -i 2:

fanotify05.c:109: TINFO: Test #0: Limited queue
fanotify05.c:98: TINFO: Created 16385 files in 616ms
fanotify05.c:98: TINFO: Opened 16385 files in 549ms
fanotify05.c:77: TINFO: Got event #0 filename=fname_0
fanotify05.c:176: TPASS: Got an overflow event: pid=0 fd=-1
fanotify05.c:182: TINFO: Got 16385 events

fanotify05.c:109: TINFO: Test #1: Unlimited queue
fanotify05.c:98: TINFO: Created 16385 files in 614ms
fanotify05.c:98: TINFO: Opened 16385 files in 599ms
fanotify05.c:77: TINFO: Got event #0 filename=fname_0
fanotify05.c:138: TPASS: Overflow event not generated!
fanotify05.c:182: TINFO: Got 25462 events

[1] https://lore.kernel.org/linux-fsdevel/20200714025417.A25EB95C0339@us180.sjc.aristanetworks.com/
[2] https://github.com/amir73il/ltp/commits/fanotify_merge

Amir Goldstein (7):
  fsnotify: allow fsnotify_{peek,remove}_first_event with empty queue
  fsnotify: support hashed notification queue
  fsnotify: read events from hashed notification queue by order of
    insertion
  fanotify: enable hashed notification queue for FAN_CLASS_NOTIF groups
  fanotify: limit number of event merge attempts
  fanotify: mix event info into merge key hash
  fsnotify: print some debug stats on hashed queue overflow

 fs/notify/fanotify/fanotify.c      |  40 ++++++-
 fs/notify/fanotify/fanotify.h      |  24 +++-
 fs/notify/fanotify/fanotify_user.c |  55 ++++++---
 fs/notify/group.c                  |  37 ++++--
 fs/notify/inotify/inotify_user.c   |  22 ++--
 fs/notify/notification.c           | 175 +++++++++++++++++++++++++----
 include/linux/fsnotify_backend.h   | 105 +++++++++++++++--
 7 files changed, 383 insertions(+), 75 deletions(-)

-- 
2.25.1