On Fri, Feb 19, 2021 at 12:21 PM Jan Kara <jack@xxxxxxx> 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@xxxxxxx> wrote:
> > > >
> > > > On Thu 18-02-21 12:56:18, Amir Goldstein wrote:
> > > > > On Wed, Feb 17, 2021 at 1:25 PM Jan Kara <jack@xxxxxxx> wrote:
> > > > > >
> > > > > > On Wed 17-02-21 12:52:21, Amir Goldstein wrote:
> > > > > > > On Tue, Feb 16, 2021 at 6:02 PM Jan Kara <jack@xxxxxxx> 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.
Good idea!
Thanks,
Amir.
