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

[Jan Kara <jack@suse.cz>]

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;
if (!event->next_hash) {
	group->merge_hash[hash(event->key)]->lastp =
		&(group->merge_hash[hash(event->key)]->first);
}

Clearer now?
								Honza
-- 
Jan Kara <jack@suse.com>
SUSE Labs, CR