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
Honza
> if (!event->next_hash) {
> group->merge_hash[hash(event->key)]->lastp =
> &(group->merge_hash[hash(event->key)]->first);
> }
>
> Clearer now?
> Honza
> --
> Jan Kara <jack@xxxxxxxx>
> SUSE Labs, CR
--
Jan Kara <jack@xxxxxxxx>
SUSE Labs, CR
