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@xxxxxxxxxxxxxxxxxxxxxxxxxxxx/ [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
