On Tue 26-01-21 18:21:26, Amir Goldstein wrote:

On Mon, Jan 25, 2021 at 3:01 PM Jan Kara [off-list ref] wrote:

quoted

On Sat 23-01-21 15:30:59, Amir Goldstein wrote:

quoted

On Fri, Jan 22, 2021 at 3:59 PM Amir Goldstein [off-list ref] wrote:

quoted

quoted

quoted

quoted

Hum, now thinking about this, maybe we could clean this up even a bit more.
event->inode is currently used only by inotify and fanotify for merging
purposes. Now inotify could use its 'wd' instead of inode with exactly the
same results, fanotify path or fid check is at least as strong as the inode
check. So only for the case of pure "inode" events, we need to store inode
identifier in struct fanotify_event - and we can do that in the union with
struct path and completely remove the 'inode' member from fsnotify_event.
Am I missing something?

That generally sounds good and I did notice it is strange that wd is not
being compared.  However, I think I was worried that comparing fid+name
(in following patches) would be more expensive than comparing dentry (or
object inode) as a "rule out first" in merge, so I preferred to keep the
tag/dentry/id comparison for fanotify_fid case.

Yes, that could be a concern.

quoted

Given this analysis (and assuming it is correct), would you like me to
just go a head with the change suggested above? or anything beyond that?

Let's go just with the change suggested above for now. We can work on this
later (probably with optimizing of the fanotify merging code).

Hi Jan,

Recap:
- fanotify_merge is very inefficient and uses extensive CPU if queue contains
  many events, so it is rather easy for a poorly written listener to
cripple the system
- You had an idea to store in event->objectid a hash of all the compared
  fields (e.g. fid+name)
- I think you had an idea to keep a hash table of events in the queue
to find the
  merge candidates faster
- For internal uses, I carry a patch that limits the linear search for
last 128 events
  which is enough to relieve the CPU overuse in case of unattended long queues

I tried looking into implementing the hash table idea, assuming I understood you
correctly and I struggled to choose appropriate table sizes. It seemed to make
sense to use a global hash table, such as inode/dentry cache for all the groups
but that would add complexity to locking rules of queue/dequeue and
group cleanup.

A simpler solution I considered, similar to my 128 events limit patch,
is to limit
the linear search to events queued in the last X seconds.
The rationale is that event merging is not supposed to be long term at all.
If a listener fails to perform read from the queue, it is not fsnotify's job to
try and keep the queue compact. I think merging events mechanism was
mainly meant to merge short bursts of events on objects, which are quite
common and surely can happen concurrently on several objects.

My intuition is that making event->objectid into event->hash in addition
to limiting the age of events to merge would address the real life workloads.
One question if we do choose this approach is what should the age limit be?
Should it be configurable? Default to infinity and let distro cap the age or
provide a sane default by kernel while slightly changing behavior (yes please).

What are your thoughts about this?

Aha! found it:
https://lore.kernel.org/linux-fsdevel/20200227112755.GZ10728@quack2.suse.cz/ (local)
You suggested a small hash table per group (128 slots).

My intuition is that this will not be good enough for the worst case, which is
not that hard to hit is real life:
1. Listener sets FAN_UNLIMITED_QUEUE
2. Listener adds a FAN_MARK_FILESYSTEM watch
3. Many thousands of events are queued
4. Listener lingers (due to bad implementation?) in reading events
5. Every single event now incurs a huge fanotify_merge() cost

Reducing the cost of merge from O(N) to O(N/128) doesn't really fix the
problem.

So my thought was that indeed reducing the overhead of merging by a factor
of 128 should be enough for any practical case as much as I agree that in
principle the computational complexity remains the same. And I've picked
per-group hash table to avoid interferences among notification groups and
to keep locking simple. That being said I'm not opposed to combining this
with a limit on the number of elements traversed in a hash chain (e.g.
those 128 you use yourself) - it will be naturally ordered by queue order
if we are a bit careful. This will provide efficient and effective merging
for ~8k queued events which seems enough to me. I find time based limits
not really worth it. Yes, they provide more predictable behavior but less
predictable runtime and overall I don't find the complexity worth the
benefit.

Sounds reasonable.
If you have time, please take a look at this WIP branch:
https://github.com/amir73il/linux/commits/fanotify_merge
and let me know if you like the direction it is taking.

This branch is only compile tested, but I am asking w.r.t to the chosen
data structures.  So far it is just an array of queues selected by (yet
unmodified) objectid.  Reading is just from any available queue.

My goal was to avoid having to hang the event on multiple list/hlist and
the idea is to implement read by order of events as follows:

As a side note, since we use notification_list as a strict queue, we could
actually use a singly linked list for linking all the events (implemented
in include/linux/llist.h). That way we can save one pointer in
fsnotify_event if we wish without too much complication AFAICT. But I'm not
sure we really care.

- With multi queue, high bit of obejctid will be masked for merge compare.
- Instead, they will be used to store the next_qid to read from

For example:
- event #1 is added to queue 6
- set group->last_qid = 6
- set group->next_qid = 6 (because group->num_events == 1)
- event #2 is added to queue 13
- the next_qid bits of the last event in last_qid (6) queue are set to 13
- set group->last_qid = 13

- read() checks value of group->next_qid and reads the first event
from queue 6 (event #1)
- event #1 has 13 stored in next_qid bits so set group->next_qid = 13
- read() reads first event from queue 13 (event #2)

That's an interesting idea. I like it and I think it would work. Just
instead of masking, I'd use bitfields. Or we could just restrict objectid
to 32-bits and use remaining 32-bits for the next_qid pointer. I know it
will waste some bits but 32-bits of objectid should provide us with enough
space to avoid doing full event comparison in most cases - BTW WRT naming I
find 'qid' somewhat confusing. Can we call it say 'next_bucket' or
something like that?

Permission events require special care, but that is the idea of a simple
singly linked list using qid's for reading events by insert order and
merging by hashed queue.

Why are permission events special in this regard?

								Honza
-- 
Jan Kara [off-list ref]
SUSE Labs, CR