Re: [PATCH 0/7] Performance improvement for fanotify merge

[Amir Goldstein <amir73il@gmail.com>]

On Fri, Feb 19, 2021 at 3:38 PM Amir Goldstein <amir73il@gmail.com> wrote:
>
> On Fri, Feb 19, 2021 at 12:21 PM Jan Kara <jack@suse.cz> wrote:
> >
> > On Fri 19-02-21 11:15:56, Jan Kara wrote:
> > > On Thu 18-02-21 14:35:39, Amir Goldstein wrote:
> > > > On Thu, Feb 18, 2021 at 1:15 PM Jan Kara <jack@suse.cz> wrote:
> > > > >
> > > > > On Thu 18-02-21 12:56:18, Amir Goldstein wrote:
> > > > > > On Wed, Feb 17, 2021 at 1:25 PM Jan Kara <jack@suse.cz> wrote:
> > > > > > >
> > > > > > > On Wed 17-02-21 12:52:21, Amir Goldstein wrote:
> > > > > > > > On Tue, Feb 16, 2021 at 6:02 PM Jan Kara <jack@suse.cz> wrote:
> > > > > > > > >
> > > > > > > > > Hi Amir!
> > > > > > > > >
> > > > > > > > > Looking at the patches I've got one idea:
> > > > > > > > >
> > > > > > > > > Currently you have fsnotify_event like:
> > > > > > > > >
> > > > > > > > > struct fsnotify_event {
> > > > > > > > >         struct list_head list;
> > > > > > > > >         unsigned int key;
> > > > > > > > >         unsigned int next_bucket;
> > > > > > > > > };
> > > > > > > > >
> > > > > > > > > And 'list' is used for hashed queue list, next_bucket is used to simulate
> > > > > > > > > single queue out of all the individual lists. The option I'm considering
> > > > > > > > > is:
> > > > > > > > >
> > > > > > > > > struct fsnotify_event {
> > > > > > > > >         struct list_head list;
> > > > > > > > >         struct fsnotify_event *hash_next;
> > > > > > > > >         unsigned int key;
> > > > > > > > > };
> > > > > > > > >
> > > > > > > > > So 'list' would stay to be used for the single queue of events like it was
> > > > > > > > > before your patches. 'hash_next' would be used for list of events in the
> > > > > > > > > hash chain. The advantage of this scheme would be somewhat more obvious
> > > > > > > > > handling,
> > > > > > > >
> > > > > > > > I can agree to that.
> > > > > > > >
> > > > > > > > > also we can handle removal of permission events (they won't be
> > > > > > > > > hashed so there's no risk of breaking hash-chain in the middle, removal
> > > > > > > > > from global queue is easy as currently).
> > > > > > > >
> > > > > > > > Ok. but I do not really see a value in hashing non-permission events
> > > > > > > > for high priority groups, so this is not a strong argument.
> > > > > > >
> > > > > > > The reason why I thought it is somewhat beneficial is that someone might be
> > > > > > > using higher priority fanotify group just for watching non-permission
> > > > > > > events because so far the group priority makes little difference. And
> > > > > > > conceptually it isn't obvious (from userspace POV) why higher priority
> > > > > > > groups should be merging events less efficiently...
> > > > > > >
> > > > > >
> > > > > > So I implemented your suggestion with ->next_event, but it did not
> > > > > > end up with being able to remove from the middle of the queue.
> > > > > > The thing is we know that permission events are on list #0, but what
> > > > > > we need to find out when removing a permission event is the previous
> > > > > > event in timeline order and we do not have that information.
> > > > >
> > > > > So my idea was that if 'list' is the time ordered list and permission
> > > > > events are *never inserted into the hash* (we don't need them there as
> > > > > hashed lists are used only for merging), then removal of permission events
> > > > > is no problem.
> > > >
> > > > We are still not talking in the same language.
> > >
> > > Yes, I think so :).
> > >
> > > > I think what you mean is use a dedicated list only for permission events
> > > > which is not any one of the hash lists.
> > > >
> > > > In that case, get_one_event() will have to look at both the high
> > > > priority queue and the hash queue if we want to allow mixing hashed
> > > > event with permission events.
> > > >
> > > > It will also mean that permission events always get priority over non-permission
> > > > events. While this makes a lot of sense, this is not the current behavior.
> > > >
> > > > So what am I missing?
> > >
> > > Let me explain with the pseudocode. fsnotify_add_event() will do:
> > >
> > > spin_lock(&group->notification_lock);
> > > ...
> > > if (!list_empty(list) && merge) {
> > >       ret = merge(list, event);
> > >       if (ret)
> > >               bail
> > > }
> > > group->q_len++;
> > > list_add_tail(&event->list, &group->notification_list);
> > > if (add_hash) {
> > >       /* Add to merge hash */
> > >       *(group->merge_hash[hash(event->key)]->lastp) = event;
> > >       group->merge_hash[hash(event->key)]->lastp = &(event->hash_next);
> > > }
> > > spin_unlock(&group->notification_lock);
> > >
> > > And we set 'add_hash' to true only for non-permission events. The merge()
> > > function can use merge_hash[] to speedup the search for merge candidates.
> > > There will be no changes to fsnotify_peek_first_event() (modulo cleanups)
> > > compared to current upstream. fsnotify_remove_queued_event() needs to
> > > update ->first and ->lastp pointers in merge_hash[]. So something like:
> > >
> > > list_del_init(&event->list);
> > > group->q_len--;
> > > group->merge_hash[hash(event->key)]->first = event->next_hash;
> >
> > Actually we must do hash handling only if the event was added to the hash.
> > So either fsnotify_remove_queued_event() needs to take an argument whether
> > it should add event to a hash or we need to somehow identify that based on
> > ->key having special value or checking
> >   group->merge_hash[hash(event->key)]->first == event
> >
>
> Not a problem.
> Permission events and the overflow event already have zero key.
> In the very unlikely event of a random zero hash, that unicorn event
> won't get merged - so what.
>
> But anyway, I think we can keep the hash handling confined in fanotify.
> With your suggestion, there can be no hashing code left in fsnotify core
> and the only hash handling will remain in the fanotify insert() hook as in
> current fanotify_merge branch.
>
> Because the only case we care about the hash is actually when removing
> the first event, fanotify already knows to identify if the event is hashed.
> The other cases where event is removed on group cleanup the hash
> chains are not relevant so fsnotify core doesn't need to care about it.
>
> >
> > > if (!event->next_hash) {
> > >       group->merge_hash[hash(event->key)]->lastp =
> > >               &(group->merge_hash[hash(event->key)]->first);
> > > }
> > >
> > > Clearer now?
>
> Yes, and much simpler.
>

Much simpler but doesn't work.
The merge list needs to be ordered from the most recent event for merging,
not from the oldest event.

Anyway, enough with those games. I implemented the hash table using
hlist's and obviously the result is much simpler.

The space we lost for the pprev pointer of hlist_node I won us back
by cramming the hash together with the type:

struct fanotify_event {
        struct fsnotify_event fse;
        struct hlist_node merge_list;   /* List for hashed merge */
        u32 mask;
        struct {
                unsigned int type : FANOTIFY_EVENT_TYPE_BITS;
                unsigned int hash : FANOTIFY_EVENT_HASH_BITS;
        };
        struct pid *pid;
};

Anyway, pushed the following branches to my github linux and ltp trees:
* fanotify_merge
* fanotify_limits
* fanotify_unpriv

Thanks,
Amir.