Performance improvement for fanotify merge

In order to improve event merge performance, support sharding the notification queue to several notification lists, hashed by an event merge key.

The fanotify event merge key is the object id reduced to 32bit hash.

At the moment, both inotify and fanotify still use a single notification list.

At the moment, reading events from the hashed queue is not by event insertion order. A non-empty list is read until it is empty.

The max events limit is accounted for total events in all lists.

Signed-off-by Amir Goldstein <[email protected]>

fs/notify/fanotify/fanotify_user.c +1 -1

index 8ff27d92d32c..dee12d927f8d 100644
@@ -635,6 +635,7 @@ static long fanotify_ioctl(struct file *file, unsigned int cmd, unsigned long ar
 {
 	struct fsnotify_group *group;
 	struct fsnotify_event *fsn_event;
+	struct list_head *list;
 	void __user *p;
 	int ret = -ENOTTY;
 	size_t send_len = 0;

@@ -646,8 +647,15 @@ static long fanotify_ioctl(struct file *file, unsigned int cmd, unsigned long ar
 	switch (cmd) {
 	case FIONREAD:
 		spin_lock(&group->notification_lock);
-		list_for_each_entry(fsn_event, &group->notification_list, list)

fs/notify/group.c +1 -1

index ffd723ffe46d..b41ed68f9ff9 100644
@@ -111,12 +116,20 @@ void fsnotify_put_group(struct fsnotify_group *group)
 }
 EXPORT_SYMBOL_GPL(fsnotify_put_group);
 
-static struct fsnotify_group *__fsnotify_alloc_group(
+static struct fsnotify_group *__fsnotify_alloc_group(unsigned int q_hash_bits,
 				const struct fsnotify_ops *ops, gfp_t gfp)

fs/notify/group.c +6 -2

-	group = kzalloc(sizeof(struct fsnotify_group), gfp);
+	group = kzalloc(fsnotify_group_size(q_hash_bits), gfp);
 	if (!group)
 		return ERR_PTR(-ENOMEM);
 

@@ -126,8 +139,12 @@ static struct fsnotify_group *__fsnotify_alloc_group(
 	atomic_set(&group->user_waits, 0);
 
 	spin_lock_init(&group->notification_lock);
-	INIT_LIST_HEAD(&group->notification_list);
 	init_waitqueue_head(&group->notification_waitq);
+	/* Initialize one or more notification lists */
+	group->q_hash_bits = q_hash_bits;
+	group->max_bucket = (1 << q_hash_bits) - 1;
+	for (i = 0; i <= group->max_bucket; i++)
+		INIT_LIST_HEAD(&group->notification_list[i]);
 	group->max_events = UINT_MAX;
 
 	mutex_init(&group->mark_mutex);

fs/notify/group.c +8 -4

+ * Hold a reference for the group returned.
  */
 struct fsnotify_group *fsnotify_alloc_group(const struct fsnotify_ops *ops)
 {
-	return __fsnotify_alloc_group(ops, GFP_KERNEL);
+	return __fsnotify_alloc_group(0, ops, GFP_KERNEL);
 }
 EXPORT_SYMBOL_GPL(fsnotify_alloc_group);
 
 /*
- * Create a new fsnotify_group and hold a reference for the group returned.
+ * Create a new fsnotify_group with an events queue.
+ * If @q_hash_bits > 0, the queue is shareded into several notification lists.
+ * Hold a reference for the group returned.
  */
-struct fsnotify_group *fsnotify_alloc_user_group(const struct fsnotify_ops *ops)
+struct fsnotify_group *fsnotify_alloc_user_group(unsigned int q_hash_bits,
+						 const struct fsnotify_ops *ops)
 {
-	return __fsnotify_alloc_group(ops, GFP_KERNEL_ACCOUNT);
+	return __fsnotify_alloc_group(q_hash_bits, ops, GFP_KERNEL_ACCOUNT);
 }
 EXPORT_SYMBOL_GPL(fsnotify_alloc_user_group);
 

fs/notify/inotify/inotify_user.c +1 -4

index d8830be60a9b..1c476b9485dc 100644
@@ -288,6 +288,7 @@ static long inotify_ioctl(struct file *file, unsigned int cmd,
 {
 	struct fsnotify_group *group;
 	struct fsnotify_event *fsn_event;
+	struct list_head *list;
 	void __user *p;
 	int ret = -ENOTTY;
 	size_t send_len = 0;

@@ -300,10 +301,16 @@ static long inotify_ioctl(struct file *file, unsigned int cmd,
 	switch (cmd) {
 	case FIONREAD:
 		spin_lock(&group->notification_lock);
-		list_for_each_entry(fsn_event, &group->notification_list,
-				    list) {
-			send_len += sizeof(struct inotify_event);
-			send_len += round_event_name_len(fsn_event);

fs/notify/inotify/inotify_user.c +1 -1

 		}
 		spin_unlock(&group->notification_lock);
 		ret = put_user(send_len, (int __user *) p);

@@ -631,7 +638,7 @@ static struct fsnotify_group *inotify_new_group(unsigned int max_events)
 	struct fsnotify_group *group;
 	struct inotify_event_info *oevent;
 
-	group = fsnotify_alloc_user_group(&inotify_fsnotify_ops);
+	group = fsnotify_alloc_user_group(0, &inotify_fsnotify_ops);
 	if (IS_ERR(group))
 		return group;
 

fs/notify/notification.c +0 -0

index fcac2d72cbf5..58c8f6c1be1b 100644

fs/notify/notification.c +28 -0

@@ -74,10 +67,75 @@ void fsnotify_destroy_event(struct fsnotify_group *group,
 	group->ops->free_event(event);
 }
 
+/* Check and fix inconsistencies in hashed queue */
+static void fsnotify_queue_check(struct fsnotify_group *group)
+{
+#ifdef FSNOTIFY_HASHED_QUEUE
+	struct list_head *list;
+	int i, nbuckets = 0;
+	bool first_empty, last_empty;
+
+	assert_spin_locked(&group->notification_lock);
+
+	pr_debug("%s: group=%p events: num=%u max=%u buckets: first=%u last=%u max=%u\n",
+		 __func__, group, group->num_events, group->max_events,
+		 group->first_bucket, group->last_bucket, group->max_bucket);
+
+	if (fsnotify_notify_queue_is_empty(group))
+		return;
+
+	first_empty = list_empty(&group->notification_list[group->first_bucket]);
+	last_empty = list_empty(&group->notification_list[group->last_bucket]);
+
+	list = &group->notification_list[0];
+	for (i = 0; i <= group->max_bucket; i++, list++) {
+		if (list_empty(list))
+			continue;
+		if (nbuckets++)
+			continue;
+		if (first_empty)
+			group->first_bucket = i;

fs/notify/notification.c +1 -1

@@ -147,17 +228,21 @@ void fsnotify_remove_queued_event(struct fsnotify_group *group,
 struct fsnotify_event *fsnotify_remove_first_event(struct fsnotify_group *group)
 {
 	struct fsnotify_event *event;
+	struct list_head *list;
 
 	assert_spin_locked(&group->notification_lock);
 
-	if (fsnotify_notify_queue_is_empty(group))

fs/notify/notification.c +8 -3

 	fsnotify_remove_queued_event(group, event);
+	/*
+	 * TODO: update group->first_bucket to next_bucket in first event.
+	 */
 	return event;
 }
 

@@ -167,13 +252,15 @@ struct fsnotify_event *fsnotify_remove_first_event(struct fsnotify_group *group)
  */
 struct fsnotify_event *fsnotify_peek_first_event(struct fsnotify_group *group)
 {
+	struct list_head *list;
+
 	assert_spin_locked(&group->notification_lock);
 
-	if (fsnotify_notify_queue_is_empty(group))
+	list = fsnotify_first_notification_list(group);
+	if (!list)
 		return NULL;
 
-	return list_first_entry(&group->notification_list,
-				struct fsnotify_event, list);
+	return list_first_entry(list, struct fsnotify_event, list);
 }
 
 /*

include/linux/fsnotify_backend.h +0 -0

index e5409b83e731..b2a80bc00108 100644

Quoted 14 lines · Amir Goldstein

In order to improve event merge performance, support sharding the notification queue to several notification lists, hashed by an event merge key.

The fanotify event merge key is the object id reduced to 32bit hash.

At the moment, both inotify and fanotify still use a single notification list.

At the moment, reading events from the hashed queue is not by event insertion order. A non-empty list is read until it is empty.

The max events limit is accounted for total events in all lists.

Quoted 1 line

Signed-off-by Amir Goldstein <[email protected]>

Style nit: Please try to stay within 80 columns...

Also I think this change would be more comprehensible if it was merged with the following patch 3/8. Having code with TODOs is kind of awkward and makes it more difficult to verify the result is actually correct.

Quoted 25 lines

fs/notify/fanotify/fanotify_user.c +8 -2

index 8ff27d92d32c..dee12d927f8d 100644
@@ -635,6 +635,7 @@ static long fanotify_ioctl(struct file *file, unsigned int cmd, unsigned long ar
 {
      struct fsnotify_group *group;
      struct fsnotify_event *fsn_event;
+     struct list_head *list;
      void __user *p;
      int ret = -ENOTTY;
      size_t send_len = 0;

@@ -646,8 +647,15 @@ static long fanotify_ioctl(struct file *file, unsigned int cmd, unsigned long ar
      switch (cmd) {
      case FIONREAD:
              spin_lock(&group->notification_lock);
-             list_for_each_entry(fsn_event, &group->notification_list, list)
-                     send_len += FAN_EVENT_METADATA_LEN;
+             list = fsnotify_first_notification_list(group);
+             /*
+              * With multi queue, send_len will be a lower bound
+              * on total events size.
+              */
+             if (list) {
+                     list_for_each_entry(fsn_event, list, list)

fs/notify/fanotify/fanotify_user.c static long fanotify_ioctl(struct file *file, unsigned int cmd, unsigned long ar · line 658

Quoted 2 lines

fs/notify/fanotify/fanotify_user.c +2 -0

+                             send_len += FAN_EVENT_METADATA_LEN;
+             }

IMO we should just walk all the lists here. Otherwise reported length would be just odd. That being said the returned value already is odd because we don't properly account for different event sizes (unrelated problem). So if we want to keep it simple for now, we can just return group->num_events * FAN_EVENT_METADATA_LEN, can't we?

Quoted 20 lines

fs/notify/group.c +7 -1

index ffd723ffe46d..b41ed68f9ff9 100644
@@ -111,12 +116,20 @@ void fsnotify_put_group(struct fsnotify_group *group)
 }
 EXPORT_SYMBOL_GPL(fsnotify_put_group);
 
-static struct fsnotify_group *__fsnotify_alloc_group(
+static struct fsnotify_group *__fsnotify_alloc_group(unsigned int q_hash_bits,
                              const struct fsnotify_ops *ops, gfp_t gfp)
 {
      struct fsnotify_group *group;
+     int i;
+
+#ifdef FSNOTIFY_HASHED_QUEUE
+     if (WARN_ON_ONCE(q_hash_bits > FSNOTIFY_HASHED_QUEUE_MAX_BITS))
+             q_hash_bits = FSNOTIFY_HASHED_QUEUE_MAX_BITS;
+#else

fs/notify/group.c void fsnotify_put_group(struct fsnotify_group *group) · line 130

Quoted 2 lines

fs/notify/group.c +2 -0

+     q_hash_bits = 0;
+#endif

Why the check for q_hash_bits? We have in-kernel users only so I would not be that paranoid :) Maybe I'd just let the group specify whether it wants hashed queue or not and for hashed queues always set number of buckets to
128. So far we don't need anything more flexible and if we ever do, it's easy enough to change the in-kernel API...

Also, honestly, I find these ifdefs ugly. I'd just leave hashed queues unconditionally compiled in.

Quoted 22 lines

fs/notify/group.c +6 -2

-     group = kzalloc(sizeof(struct fsnotify_group), gfp);
+     group = kzalloc(fsnotify_group_size(q_hash_bits), gfp);
      if (!group)
              return ERR_PTR(-ENOMEM);
 

@@ -126,8 +139,12 @@ static struct fsnotify_group *__fsnotify_alloc_group(
      atomic_set(&group->user_waits, 0);
 
      spin_lock_init(&group->notification_lock);
-     INIT_LIST_HEAD(&group->notification_list);
      init_waitqueue_head(&group->notification_waitq);
+     /* Initialize one or more notification lists */
+     group->q_hash_bits = q_hash_bits;
+     group->max_bucket = (1 << q_hash_bits) - 1;
+     for (i = 0; i <= group->max_bucket; i++)
+             INIT_LIST_HEAD(&group->notification_list[i]);
      group->max_events = UINT_MAX;
 
      mutex_init(&group->mark_mutex);

@@ -139,20 +156,24 @@ static struct fsnotify_group *__fsnotify_alloc_group(
 }
 

fs/notify/group.c static struct fsnotify_group *__fsnotify_alloc_group( · line 159

Quoted 3 lines

fs/notify/group.c +1 -1

 /*
- * Create a new fsnotify_group and hold a reference for the group returned.
+ * Create a new fsnotify_group with no events queue.

How come "no events queue"? There will be always at least one queue...

Quoted 49 lines

fs/notify/group.c +8 -4

+ * Hold a reference for the group returned.
  */
 struct fsnotify_group *fsnotify_alloc_group(const struct fsnotify_ops *ops)
 {
-     return __fsnotify_alloc_group(ops, GFP_KERNEL);
+     return __fsnotify_alloc_group(0, ops, GFP_KERNEL);
 }
 EXPORT_SYMBOL_GPL(fsnotify_alloc_group);
 
 /*
- * Create a new fsnotify_group and hold a reference for the group returned.
+ * Create a new fsnotify_group with an events queue.
+ * If @q_hash_bits > 0, the queue is shareded into several notification lists.
+ * Hold a reference for the group returned.
  */
-struct fsnotify_group *fsnotify_alloc_user_group(const struct fsnotify_ops *ops)
+struct fsnotify_group *fsnotify_alloc_user_group(unsigned int q_hash_bits,
+                                              const struct fsnotify_ops *ops)
 {
-     return __fsnotify_alloc_group(ops, GFP_KERNEL_ACCOUNT);
+     return __fsnotify_alloc_group(q_hash_bits, ops, GFP_KERNEL_ACCOUNT);
 }
 EXPORT_SYMBOL_GPL(fsnotify_alloc_user_group);
 

fs/notify/inotify/inotify_user.c +6 -4

index d8830be60a9b..1c476b9485dc 100644
@@ -288,6 +288,7 @@ static long inotify_ioctl(struct file *file, unsigned int cmd,
 {
      struct fsnotify_group *group;
      struct fsnotify_event *fsn_event;
+     struct list_head *list;
      void __user *p;
      int ret = -ENOTTY;
      size_t send_len = 0;

@@ -300,10 +301,16 @@ static long inotify_ioctl(struct file *file, unsigned int cmd,
      switch (cmd) {
      case FIONREAD:
              spin_lock(&group->notification_lock);
-             list_for_each_entry(fsn_event, &group->notification_list,
-                                 list) {
-                     send_len += sizeof(struct inotify_event);
-                     send_len += round_event_name_len(fsn_event);
+             list = fsnotify_first_notification_list(group);
+             /*
+              * With multi queue, send_len will be a lower bound
+              * on total events size.
+              */

fs/notify/inotify/inotify_user.c static long inotify_ioctl(struct file *file, unsigned int cmd, · line 313

Quoted 5 lines

fs/notify/inotify/inotify_user.c +5 -0

+             if (list) {
+                     list_for_each_entry(fsn_event, list, list) {
+                             send_len += sizeof(struct inotify_event);
+                             send_len += round_event_name_len(fsn_event);
+                     }

As I write below IMO we should enable hashed queues also for inotify (is there good reason not to?)

and here we should just walk through all the lists.

Quoted 17 lines

fs/notify/inotify/inotify_user.c +1 -1

              }
              spin_unlock(&group->notification_lock);
              ret = put_user(send_len, (int __user *) p);

@@ -631,7 +638,7 @@ static struct fsnotify_group *inotify_new_group(unsigned int max_events)
      struct fsnotify_group *group;
      struct inotify_event_info *oevent;
 
-     group = fsnotify_alloc_user_group(&inotify_fsnotify_ops);
+     group = fsnotify_alloc_user_group(0, &inotify_fsnotify_ops);
      if (IS_ERR(group))
              return group;
 

fs/notify/notification.c +0 -0

index fcac2d72cbf5..58c8f6c1be1b 100644

...

Quoted 32 lines

fs/notify/notification.c +28 -0

@@ -74,10 +67,75 @@ void fsnotify_destroy_event(struct fsnotify_group *group,
      group->ops->free_event(event);
 }
 
+/* Check and fix inconsistencies in hashed queue */
+static void fsnotify_queue_check(struct fsnotify_group *group)
+{
+#ifdef FSNOTIFY_HASHED_QUEUE
+     struct list_head *list;
+     int i, nbuckets = 0;
+     bool first_empty, last_empty;
+
+     assert_spin_locked(&group->notification_lock);
+
+     pr_debug("%s: group=%p events: num=%u max=%u buckets: first=%u last=%u max=%u\n",
+              __func__, group, group->num_events, group->max_events,
+              group->first_bucket, group->last_bucket, group->max_bucket);
+
+     if (fsnotify_notify_queue_is_empty(group))
+             return;
+
+     first_empty = list_empty(&group->notification_list[group->first_bucket]);
+     last_empty = list_empty(&group->notification_list[group->last_bucket]);
+
+     list = &group->notification_list[0];
+     for (i = 0; i <= group->max_bucket; i++, list++) {
+             if (list_empty(list))
+                     continue;
+             if (nbuckets++)
+                     continue;
+             if (first_empty)
+                     group->first_bucket = i;

fs/notify/notification.c void fsnotify_destroy_event(struct fsnotify_group *group, · line 107

Quoted 10 lines

fs/notify/notification.c +10 -0

+             if (last_empty)
+                     group->last_bucket = i;
+     }
+
+     pr_debug("%s: %u non-empty buckets\n", __func__, nbuckets);
+
+     /* All buckets are empty, but non-zero num_events? */
+     if (WARN_ON_ONCE(!nbuckets && group->num_events))
+             group->num_events = 0;
+#endif

Hum, what is this function about? I understand you might want to have this around for debugging when developing the patch but is there are legitimate reason for this in production?

I understand current patch uses this function for searching for next non-empty list but after this patch is merged with the next one, is there still a need for this?

Quoted 10 lines

fs/notify/notification.c +1 -1

@@ -147,17 +228,21 @@ void fsnotify_remove_queued_event(struct fsnotify_group *group,
 struct fsnotify_event *fsnotify_remove_first_event(struct fsnotify_group *group)
 {
      struct fsnotify_event *event;
+     struct list_head *list;
 
      assert_spin_locked(&group->notification_lock);
 
-     if (fsnotify_notify_queue_is_empty(group))

fs/notify/notification.c void fsnotify_remove_queued_event(struct fsnotify_group *group, · line 241

Quoted 10 lines

fs/notify/notification.c +4 -3

+     list = fsnotify_first_notification_list(group);
+     if (!list)
              return NULL;
 
-     pr_debug("%s: group=%p\n", __func__, group);
+     pr_debug("%s: group=%p bucket=%u\n", __func__, group, group->first_bucket);
 
-     event = list_first_entry(&group->notification_list,
-                              struct fsnotify_event, list);
+     event = list_first_entry(list, struct fsnotify_event, list);

Perhaps the above could just reuse fsnotify_peek_first_event()? It is now complex enough to be worth it I guess.

Quoted 34 lines

fs/notify/notification.c +8 -3

      fsnotify_remove_queued_event(group, event);
+     /*
+      * TODO: update group->first_bucket to next_bucket in first event.
+      */
      return event;
 }
 

@@ -167,13 +252,15 @@ struct fsnotify_event *fsnotify_remove_first_event(struct fsnotify_group *group)
  */
 struct fsnotify_event *fsnotify_peek_first_event(struct fsnotify_group *group)
 {
+     struct list_head *list;
+
      assert_spin_locked(&group->notification_lock);
 
-     if (fsnotify_notify_queue_is_empty(group))
+     list = fsnotify_first_notification_list(group);
+     if (!list)
              return NULL;
 
-     return list_first_entry(&group->notification_list,
-                             struct fsnotify_event, list);
+     return list_first_entry(list, struct fsnotify_event, list);
 }
 
 /*

include/linux/fsnotify_backend.h +0 -0

index e5409b83e731..b2a80bc00108 100644
@@ -160,6 +160,11 @@ struct fsnotify_ops {
      void (*free_mark)(struct fsnotify_mark *mark);
 };
 

include/linux/fsnotify_backend.h struct fsnotify_ops { · line 167

Quoted 5 lines

include/linux/fsnotify_backend.h +5 -0

+#ifdef CONFIG_FANOTIFY
+#define FSNOTIFY_HASHED_QUEUE
+#define FSNOTIFY_HASHED_QUEUE_MAX_BITS 8
+#endif
+

Would not inotify benefit from this work as well?

Also I'd just compile in
hashed queues unconditionally. The ifdefs are ugly and IMHO not worth it.

...

include/linux/fsnotify_backend.h struct fsnotify_group { · line 271

Quoted 11 lines

include/linux/fsnotify_backend.h +11 -0

+static inline size_t fsnotify_group_size(unsigned int q_hash_bits)
+{
+     return sizeof(struct fsnotify_group) + (sizeof(struct list_head) << q_hash_bits);
+}
+
+static inline unsigned int fsnotify_event_bucket(struct fsnotify_group *group,
+                                              struct fsnotify_event *event)
+{
+     /* High bits are better for hash */
+     return (event->key >> (32 - group->q_hash_bits)) & group->max_bucket;
+}

Why not use hash_32() here? IMHO better than just stripping bits...

include/linux/fsnotify_backend.h struct fsnotify_group { · line 279

Quoted 9 lines

include/linux/fsnotify_backend.h +8 -0

+
+static inline struct list_head *fsnotify_event_notification_list(
+                                             struct fsnotify_group *group,
+                                             struct fsnotify_event *event)
+{
+     return &group->notification_list[fsnotify_event_bucket(group, event)];
+}
+

Any reason for this to be in a header? Will it ever have other user than fsnotify_add_event()?

Quoted 13 lines · Jan Kara

Quoted 13 lines

fs/notify/inotify/inotify_user.c +5 -4

@@ -300,10 +301,16 @@ static long inotify_ioctl(struct file *file, unsigned int cmd,
      switch (cmd) {
      case FIONREAD:
              spin_lock(&group->notification_lock);
-             list_for_each_entry(fsn_event, &group->notification_list,
-                                 list) {
-                     send_len += sizeof(struct inotify_event);
-                     send_len += round_event_name_len(fsn_event);
+             list = fsnotify_first_notification_list(group);
+             /*
+              * With multi queue, send_len will be a lower bound
+              * on total events size.
+              */

Quoted 8 lines

fs/notify/inotify/inotify_user.c static long inotify_ioctl(struct file *file, unsigned int cmd, · line 313

Quoted 5 lines

fs/notify/inotify/inotify_user.c +5 -0

+             if (list) {
+                     list_for_each_entry(fsn_event, list, list) {
+                             send_len += sizeof(struct inotify_event);
+                             send_len += round_event_name_len(fsn_event);
+                     }

As I write below IMO we should enable hashed queues also for inotify (is there good reason not to?)

I see your perception of inotify_merge() is the same as mine was when I wrote a patch to support hashed queues for inotify. It is only after that I realized that inotify_merge() only ever merges with the last event and I dropped that patch.
I see no reason to change this long time behavior.

Quoted 5 lines

Quoted 5 lines

include/linux/fsnotify_backend.h +5 -0

+static inline size_t fsnotify_group_size(unsigned int q_hash_bits)
+{
+     return sizeof(struct fsnotify_group) + (sizeof(struct list_head) << q_hash_bits);
+}
+

Quoted 8 lines

include/linux/fsnotify_backend.h struct fsnotify_group { · line 271

Quoted 6 lines

include/linux/fsnotify_backend.h +6 -0

+static inline unsigned int fsnotify_event_bucket(struct fsnotify_group *group,
+                                              struct fsnotify_event *event)
+{
+     /* High bits are better for hash */
+     return (event->key >> (32 - group->q_hash_bits)) & group->max_bucket;
+}

Why not use hash_32() here? IMHO better than just stripping bits...

See hash_ptr(). There is a reason to use the highest bits.

Quoted 23 lines · Amir Goldstein

Quoted 13 lines · Jan Kara

Quoted 13 lines

fs/notify/inotify/inotify_user.c +5 -4

@@ -300,10 +301,16 @@ static long inotify_ioctl(struct file *file, unsigned int cmd,
      switch (cmd) {
      case FIONREAD:
              spin_lock(&group->notification_lock);
-             list_for_each_entry(fsn_event, &group->notification_list,
-                                 list) {
-                     send_len += sizeof(struct inotify_event);
-                     send_len += round_event_name_len(fsn_event);
+             list = fsnotify_first_notification_list(group);
+             /*
+              * With multi queue, send_len will be a lower bound
+              * on total events size.
+              */

Quoted 8 lines

fs/notify/inotify/inotify_user.c static long inotify_ioctl(struct file *file, unsigned int cmd, · line 313

Quoted 5 lines

fs/notify/inotify/inotify_user.c +5 -0

+             if (list) {
+                     list_for_each_entry(fsn_event, list, list) {
+                             send_len += sizeof(struct inotify_event);
+                             send_len += round_event_name_len(fsn_event);
+                     }

As I write below IMO we should enable hashed queues also for inotify (is there good reason not to?)

Quoted 5 lines

I see your perception of inotify_merge() is the same as mine was when I wrote a patch to support hashed queues for inotify. It is only after that I realized that inotify_merge() only ever merges with the last event and I dropped that patch.
I see no reason to change this long time behavior.

Ah, I even briefly looked at that code but didn't notice it merges only with the last event. I agree that hashing for inotify doesn't make sense then.

Hum, if the hashing and merging is specific to fanotify and as we decided to keep the event->list for the global event list, we could easily have the hash table just in fanotify private group data and hash->next pointer in fanotify private part of the event? Maybe that would even result in a more compact code?

Quoted 14 lines

Quoted 13 lines

include/linux/fsnotify_backend.h struct fsnotify_group { · line 271

Quoted 11 lines

include/linux/fsnotify_backend.h +11 -0

+static inline size_t fsnotify_group_size(unsigned int q_hash_bits)
+{
+     return sizeof(struct fsnotify_group) + (sizeof(struct list_head) << q_hash_bits);
+}
+
+static inline unsigned int fsnotify_event_bucket(struct fsnotify_group *group,
+                                              struct fsnotify_event *event)
+{
+     /* High bits are better for hash */
+     return (event->key >> (32 - group->q_hash_bits)) & group->max_bucket;
+}

Why not use hash_32() here? IMHO better than just stripping bits...

Quoted 1 line

See hash_ptr(). There is a reason to use the highest bits.

Well, but event->key is just a 32-bit number so I don't follow how high bits used by hash_ptr() matter?

Quoted 16 lines · Jan Kara

Quoted 15 lines

Quoted 5 lines

Quoted 5 lines

include/linux/fsnotify_backend.h +5 -0

+static inline size_t fsnotify_group_size(unsigned int q_hash_bits)
+{
+     return sizeof(struct fsnotify_group) + (sizeof(struct list_head) << q_hash_bits);
+}
+

Quoted 8 lines

include/linux/fsnotify_backend.h struct fsnotify_group { · line 271

Quoted 6 lines

include/linux/fsnotify_backend.h +6 -0

+static inline unsigned int fsnotify_event_bucket(struct fsnotify_group *group,
+                                              struct fsnotify_event *event)
+{
+     /* High bits are better for hash */
+     return (event->key >> (32 - group->q_hash_bits)) & group->max_bucket;
+}

Why not use hash_32() here? IMHO better than just stripping bits...

See hash_ptr(). There is a reason to use the highest bits.

Quoted 2 lines

Well, but event->key is just a 32-bit number so I don't follow how high bits used by hash_ptr() matter?

Of course, you are right.
But that 32-bit number was already generated using a xor of several hash_32() results from hash_ptr() and full_name_hash(), so we do not really need to mix it anymore to get better entropy in the higher 7 bits.

Quoted 35 lines · Jan Kara

Quoted 23 lines · Amir Goldstein

Quoted 13 lines · Jan Kara

Quoted 13 lines

fs/notify/inotify/inotify_user.c +5 -4

@@ -300,10 +301,16 @@ static long inotify_ioctl(struct file *file, unsigned int cmd,
      switch (cmd) {
      case FIONREAD:
              spin_lock(&group->notification_lock);
-             list_for_each_entry(fsn_event, &group->notification_list,
-                                 list) {
-                     send_len += sizeof(struct inotify_event);
-                     send_len += round_event_name_len(fsn_event);
+             list = fsnotify_first_notification_list(group);
+             /*
+              * With multi queue, send_len will be a lower bound
+              * on total events size.
+              */

Quoted 8 lines

fs/notify/inotify/inotify_user.c static long inotify_ioctl(struct file *file, unsigned int cmd, · line 313

Quoted 5 lines

fs/notify/inotify/inotify_user.c +5 -0

+             if (list) {
+                     list_for_each_entry(fsn_event, list, list) {
+                             send_len += sizeof(struct inotify_event);
+                             send_len += round_event_name_len(fsn_event);
+                     }

As I write below IMO we should enable hashed queues also for inotify (is there good reason not to?)

Quoted 5 lines

I see your perception of inotify_merge() is the same as mine was when I wrote a patch to support hashed queues for inotify. It is only after that I realized that inotify_merge() only ever merges with the last event and I dropped that patch.
I see no reason to change this long time behavior.

Ah, I even briefly looked at that code but didn't notice it merges only with the last event. I agree that hashing for inotify doesn't make sense then.

Quoted 6 lines

Hum, if the hashing and merging is specific to fanotify and as we decided to keep the event->list for the global event list, we could easily have the hash table just in fanotify private group data and hash->next pointer in fanotify private part of the event? Maybe that would even result in a more compact code?

Maybe, I am not so sure. I will look into it.

On 64bit arch, use the available 32bit in event for next_bucket field, that is used to chain all events by order of insertion.

The group has a cursor for the bucket containing the first event and every event stores the bucket of the next event to read.

On 32bit arch, hashed notification queue is disabled.

Signed-off-by Amir Goldstein <[email protected]>

---
 fs/notify/notification.c         | 49 ++++++++++++++++++++++++--------
 include/linux/fsnotify_backend.h | 42 +++++++++++++++++++++++++++
 2 files changed, 79 insertions(+), 12 deletions(-)

fs/notify/notification.c +37 -12

index 58c8f6c1be1b..d98f4c8bfb0e 100644
@@ -84,8 +84,8 @@ static void fsnotify_queue_check(struct fsnotify_group *group)
 	if (fsnotify_notify_queue_is_empty(group))
 		return;
 
-	first_empty = list_empty(&group->notification_list[group->first_bucket]);
-	last_empty = list_empty(&group->notification_list[group->last_bucket]);
+	first_empty = WARN_ON_ONCE(list_empty(&group->notification_list[group->first_bucket]));
+	last_empty = WARN_ON_ONCE(list_empty(&group->notification_list[group->last_bucket]));
 
 	list = &group->notification_list[0];
 	for (i = 0; i <= group->max_bucket; i++, list++) {

@@ -121,12 +121,23 @@ static void fsnotify_queue_event(struct fsnotify_group *group,
 
 	pr_debug("%s: group=%p event=%p bucket=%u\n", __func__, group, event, b);
 
-	/*
-	 * TODO: set next_bucket of last event.
-	 */
-	group->last_bucket = b;
-	if (!group->num_events)
-		group->first_bucket = b;
+	if (fsnotify_notify_queue_is_hashed(group)) {
+		/*
+		 * On first insert, set this event's list as the list to read first event.
+		 * Otherwise, point from last event to this event's list.
+		 */
+		struct list_head *last_l = &group->notification_list[group->last_bucket];
+
+		if (!group->num_events) {
+			group->first_bucket = b;
+		} else if (!WARN_ON_ONCE(list_empty(last_l))) {
+			struct fsnotify_event *last_e;
+
+			last_e = list_last_entry(last_l, struct fsnotify_event, list);
+			fsnotify_event_set_next_bucket(last_e, b);
+		}
+		group->last_bucket = b;
+	}
 	group->num_events++;
 	list_add_tail(&event->list, list);
 }

@@ -186,8 +197,8 @@ int fsnotify_add_event(struct fsnotify_group *group,
 	return ret;
 }
 
-void fsnotify_remove_queued_event(struct fsnotify_group *group,
-				  struct fsnotify_event *event)
+static void __fsnotify_remove_queued_event(struct fsnotify_group *group,
+					   struct fsnotify_event *event)
 {
 	assert_spin_locked(&group->notification_lock);
 	/*

@@ -198,6 +209,17 @@ void fsnotify_remove_queued_event(struct fsnotify_group *group,
 	group->num_events--;
 }
 
+void fsnotify_remove_queued_event(struct fsnotify_group *group,
+				  struct fsnotify_event *event)
+{
+	/*
+	 * if called for removal of event in the middle of a hashed queue,
+	 * events may be read not in insertion order.
+	 */
+	WARN_ON_ONCE(fsnotify_notify_queue_is_hashed(group));
+	__fsnotify_remove_queued_event(group, event);
+}
+
 /* Return the notification list of the first event */
 struct list_head *fsnotify_first_notification_list(struct fsnotify_group *group)
 {

@@ -213,6 +235,7 @@ struct list_head *fsnotify_first_notification_list(struct fsnotify_group *group)
 		return list;
 
 	/*
+	 * Oops... first bucket is not supposed to be empty.
 	 * Look for any non-empty bucket.
 	 */
 	fsnotify_queue_check(group);

@@ -239,10 +262,12 @@ struct fsnotify_event *fsnotify_remove_first_event(struct fsnotify_group *group)
 	pr_debug("%s: group=%p bucket=%u\n", __func__, group, group->first_bucket);
 
 	event = list_first_entry(list, struct fsnotify_event, list);
-	fsnotify_remove_queued_event(group, event);
+	__fsnotify_remove_queued_event(group, event);
 	/*
-	 * TODO: update group->first_bucket to next_bucket in first event.
+	 * Removed event points to the next list to read from.
 	 */
+	group->first_bucket = fsnotify_event_next_bucket(event);
+
 	return event;
 }
 

include/linux/fsnotify_backend.h +42 -0

index b2a80bc00108..3fc3c9e4d21c 100644
@@ -161,9 +161,12 @@ struct fsnotify_ops {
 };
 
 #ifdef CONFIG_FANOTIFY
+#if BITS_PER_LONG == 64
+/* Use available 32bit of event for hashed queue support */
 #define FSNOTIFY_HASHED_QUEUE
 #define FSNOTIFY_HASHED_QUEUE_MAX_BITS 8
 #endif
+#endif
 
 /*
  * all of the information about the original object we want to now send to

@@ -173,6 +176,9 @@ struct fsnotify_ops {
 struct fsnotify_event {
 	struct list_head list;
 	unsigned int key;		/* Key for hashed queue add/merge */
+#ifdef FSNOTIFY_HASHED_QUEUE
+	unsigned int next_bucket;	/* Bucket to read next event from */
+#endif
 };
 
 /*

@@ -277,6 +283,41 @@ static inline struct list_head *fsnotify_event_notification_list(
 	return &group->notification_list[fsnotify_event_bucket(group, event)];
 }
 
+#ifdef FSNOTIFY_HASHED_QUEUE
+static inline bool fsnotify_notify_queue_is_hashed(struct fsnotify_group *group)
+{
+	return group->max_bucket > 0;
+}
+
+static inline unsigned int fsnotify_event_next_bucket(struct fsnotify_event *event)
+{
+	return event->next_bucket;
+}
+
+static inline void fsnotify_event_set_next_bucket(struct fsnotify_event *event,
+						  unsigned int b)
+{
+	event->next_bucket = b;
+}
+
+#else
+static inline bool fsnotify_notify_queue_is_hashed(struct fsnotify_group *group)
+{
+	return false;
+}
+
+static inline unsigned int fsnotify_event_next_bucket(struct fsnotify_event *event)
+{
+	return 0;
+}
+
+static inline void fsnotify_event_set_next_bucket(struct fsnotify_event *event,
+						  unsigned int b)
+{
+}
+
+#endif
+
 /* When calling fsnotify tell it if the data is a path or inode */
 enum fsnotify_data_type {
 	FSNOTIFY_EVENT_NONE,

@@ -620,6 +661,7 @@ static inline void fsnotify_init_event(struct fsnotify_event *event,
 {
 	INIT_LIST_HEAD(&event->list);
 	event->key = key;
+	fsnotify_event_set_next_bucket(event, 0);
 }
 
 #else

Signature · 1 line

2.25.1

Event merges are expensive when event queue size is large. Limit the linear search to 128 merge tests.
In combination with 128 hash lists, there is a potential to merge with up to 16K events in the hashed queue.

Signed-off-by Amir Goldstein <[email protected]>

---
 fs/notify/fanotify/fanotify.c | 6 ++++++
 1 file changed, 6 insertions(+)

fs/notify/fanotify/fanotify.c +6 -1

index 12df6957e4d8..6d3807012851 100644
@@ -129,11 +129,15 @@ static bool fanotify_should_merge(struct fsnotify_event *old_fsn,
        return false;
 }
 
+/* Limit event merges to limit CPU overhead per event */
+#define FANOTIFY_MAX_MERGE_EVENTS 128
+
 /* and the list better be locked by something too! */
 static int fanotify_merge(struct list_head *list, struct fsnotify_event *event)
 {
        struct fsnotify_event *test_event;
        struct fanotify_event *new;
+       int i = 0;
 
        pr_debug("%s: list=%p event=%p\n", __func__, list, event);
        new = FANOTIFY_E(event);

@@ -147,6 +151,8 @@ static int fanotify_merge(struct list_head *list, struct fsnotify_event *event)
                return 0;
 
        list_for_each_entry_reverse(test_event, list, list) {
+               if (++i > FANOTIFY_MAX_MERGE_EVENTS)
+                       break;
                if (fanotify_should_merge(test_event, event)) {
                        FANOTIFY_E(test_event)->mask |= new->mask;
                        return 1;
--

2.25.1

Quoted 41 lines · Amir Goldstein

Event merges are expensive when event queue size is large. Limit the linear search to 128 merge tests.
In combination with 128 hash lists, there is a potential to merge with up to 16K events in the hashed queue.

Signed-off-by Amir Goldstein <[email protected]>

---
 fs/notify/fanotify/fanotify.c | 6 ++++++
 1 file changed, 6 insertions(+)

fs/notify/fanotify/fanotify.c +6 -1

index 12df6957e4d8..6d3807012851 100644
@@ -129,11 +129,15 @@ static bool fanotify_should_merge(struct fsnotify_event *old_fsn,
        return false;
 }
 
+/* Limit event merges to limit CPU overhead per event */
+#define FANOTIFY_MAX_MERGE_EVENTS 128
+
 /* and the list better be locked by something too! */
 static int fanotify_merge(struct list_head *list, struct fsnotify_event *event)
 {
        struct fsnotify_event *test_event;
        struct fanotify_event *new;
+       int i = 0;
 
        pr_debug("%s: list=%p event=%p\n", __func__, list, event);
        new = FANOTIFY_E(event);

@@ -147,6 +151,8 @@ static int fanotify_merge(struct list_head *list, struct fsnotify_event *event)
                return 0;
 
        list_for_each_entry_reverse(test_event, list, list) {
+               if (++i > FANOTIFY_MAX_MERGE_EVENTS)
+                       break;
                if (fanotify_should_merge(test_event, event)) {
                        FANOTIFY_E(test_event)->mask |= new->mask;
                        return 1;
--

Quoted 2 lines

2.25.1

Jan,

I was thinking that this patch or a variant thereof should be applied to stable kernels, but not the entire series.

OTOH, I am concerned about regressing existing workloads that depend on merging events on more than 128 inodes.

I thought of this compromise between performance and functional regressions:

/*
* Limit event merges to limit CPU overhead per new event.
* For legacy mode, avoid unlimited CPU overhead, but do not regress the event
* merge ratio in heavy concurrent workloads with default queue size.
* For new FAN_REPORT_FID modes, make sure that CPU overhead is low. */
#define FANOTIFY_MAX_MERGE_OLD_EVENTS 16384
#define FANOTIFY_MAX_MERGE_FID_EVENTS 128

static inline int fanotify_max_merge_events(struct fsnotify_group *group)

{
        if (FAN_GROUP_FLAG(group, FANOTIFY_FID_BITS))
                return FANOTIFY_MAX_MERGE_FID_EVENTS;
        else
                return FANOTIFY_MAX_MERGE_OLD_EVENTS;
}

I can start the series with this patch and change that to:

#define FANOTIFY_MAX_MERGE_FID_EVENTS 128

static inline int fanotify_max_merge_events(struct fsnotify_group *group)

{
               return FANOTIFY_MAX_MERGE_EVENTS;
}

At the end of the series.

What do you think?

Thanks,
Amir.

Quoted 47 lines · Amir Goldstein

Quoted 41 lines · Amir Goldstein

Event merges are expensive when event queue size is large. Limit the linear search to 128 merge tests.
In combination with 128 hash lists, there is a potential to merge with up to 16K events in the hashed queue.

Signed-off-by Amir Goldstein <[email protected]>

---
 fs/notify/fanotify/fanotify.c | 6 ++++++
 1 file changed, 6 insertions(+)

fs/notify/fanotify/fanotify.c +6 -1

index 12df6957e4d8..6d3807012851 100644
@@ -129,11 +129,15 @@ static bool fanotify_should_merge(struct fsnotify_event *old_fsn,
        return false;
 }
 
+/* Limit event merges to limit CPU overhead per event */
+#define FANOTIFY_MAX_MERGE_EVENTS 128
+
 /* and the list better be locked by something too! */
 static int fanotify_merge(struct list_head *list, struct fsnotify_event *event)
 {
        struct fsnotify_event *test_event;
        struct fanotify_event *new;
+       int i = 0;
 
        pr_debug("%s: list=%p event=%p\n", __func__, list, event);
        new = FANOTIFY_E(event);

@@ -147,6 +151,8 @@ static int fanotify_merge(struct list_head *list, struct fsnotify_event *event)
                return 0;
 
        list_for_each_entry_reverse(test_event, list, list) {
+               if (++i > FANOTIFY_MAX_MERGE_EVENTS)
+                       break;
                if (fanotify_should_merge(test_event, event)) {
                        FANOTIFY_E(test_event)->mask |= new->mask;
                        return 1;
--

Quoted 2 lines

2.25.1

Jan,

Quoted 5 lines

I was thinking that this patch or a variant thereof should be applied to stable kernels, but not the entire series.

OTOH, I am concerned about regressing existing workloads that depend on merging events on more than 128 inodes.

Honestly, I don't think pushing anything to stable for this is really worth it.

1) fanotify() is limited to CAP_SYS_ADMIN (in init namespace) so this is hardly a security issue.

2) We have cond_resched() in the merge code now so the kernel doesn't lockup anymore. So this is only about fanotify becoming slow if you have lots of events.

3) I haven't heard any complaints since we've added the cond_resched() patch so the performance issue seems to be really rare.

If I get complaits from real users about this, we can easily reconsider, it is not a big deal. But I just don't think preemptive action is warranted...

Quoted 47 lines · Amir Goldstein

Quoted 41 lines · Amir Goldstein

Event merges are expensive when event queue size is large. Limit the linear search to 128 merge tests.
In combination with 128 hash lists, there is a potential to merge with up to 16K events in the hashed queue.

Signed-off-by Amir Goldstein <[email protected]>

---
 fs/notify/fanotify/fanotify.c | 6 ++++++
 1 file changed, 6 insertions(+)

fs/notify/fanotify/fanotify.c +6 -1

index 12df6957e4d8..6d3807012851 100644
@@ -129,11 +129,15 @@ static bool fanotify_should_merge(struct fsnotify_event *old_fsn,
        return false;
 }
 
+/* Limit event merges to limit CPU overhead per event */
+#define FANOTIFY_MAX_MERGE_EVENTS 128
+
 /* and the list better be locked by something too! */
 static int fanotify_merge(struct list_head *list, struct fsnotify_event *event)
 {
        struct fsnotify_event *test_event;
        struct fanotify_event *new;
+       int i = 0;
 
        pr_debug("%s: list=%p event=%p\n", __func__, list, event);
        new = FANOTIFY_E(event);

@@ -147,6 +151,8 @@ static int fanotify_merge(struct list_head *list, struct fsnotify_event *event)
                return 0;
 
        list_for_each_entry_reverse(test_event, list, list) {
+               if (++i > FANOTIFY_MAX_MERGE_EVENTS)
+                       break;
                if (fanotify_should_merge(test_event, event)) {
                        FANOTIFY_E(test_event)->mask |= new->mask;
                        return 1;
--

Quoted 2 lines

2.25.1

Jan,

Quoted 5 lines

I was thinking that this patch or a variant thereof should be applied to stable kernels, but not the entire series.

OTOH, I am concerned about regressing existing workloads that depend on merging events on more than 128 inodes.

Honestly, I don't think pushing anything to stable for this is really worth it.

1) fanotify() is limited to CAP_SYS_ADMIN (in init namespace) so this is hardly a security issue.

2) We have cond_resched() in the merge code now so the kernel doesn't lockup anymore. So this is only about fanotify becoming slow if you have lots of events.

3) I haven't heard any complaints since we've added the cond_resched() patch so the performance issue seems to be really rare.

If I get complaits from real users about this, we can easily reconsider, it is not a big deal. But I just don't think preemptive action is warranted...

Quoted 65 lines · Jan Kara

Quoted 47 lines · Amir Goldstein

Quoted 41 lines · Amir Goldstein

Event merges are expensive when event queue size is large. Limit the linear search to 128 merge tests.
In combination with 128 hash lists, there is a potential to merge with up to 16K events in the hashed queue.

Signed-off-by Amir Goldstein <[email protected]>

---
 fs/notify/fanotify/fanotify.c | 6 ++++++
 1 file changed, 6 insertions(+)

fs/notify/fanotify/fanotify.c +6 -1

index 12df6957e4d8..6d3807012851 100644
@@ -129,11 +129,15 @@ static bool fanotify_should_merge(struct fsnotify_event *old_fsn,
        return false;
 }
 
+/* Limit event merges to limit CPU overhead per event */
+#define FANOTIFY_MAX_MERGE_EVENTS 128
+
 /* and the list better be locked by something too! */
 static int fanotify_merge(struct list_head *list, struct fsnotify_event *event)
 {
        struct fsnotify_event *test_event;
        struct fanotify_event *new;
+       int i = 0;
 
        pr_debug("%s: list=%p event=%p\n", __func__, list, event);
        new = FANOTIFY_E(event);

@@ -147,6 +151,8 @@ static int fanotify_merge(struct list_head *list, struct fsnotify_event *event)
                return 0;
 
        list_for_each_entry_reverse(test_event, list, list) {
+               if (++i > FANOTIFY_MAX_MERGE_EVENTS)
+                       break;
                if (fanotify_should_merge(test_event, event)) {
                        FANOTIFY_E(test_event)->mask |= new->mask;
                        return 1;
--

Quoted 2 lines

2.25.1

Jan,

Quoted 5 lines

I was thinking that this patch or a variant thereof should be applied to stable kernels, but not the entire series.

OTOH, I am concerned about regressing existing workloads that depend on merging events on more than 128 inodes.

Honestly, I don't think pushing anything to stable for this is really worth it.

1) fanotify() is limited to CAP_SYS_ADMIN (in init namespace) so this is hardly a security issue.

2) We have cond_resched() in the merge code now so the kernel doesn't lockup anymore. So this is only about fanotify becoming slow if you have lots of events.

Quoted 6 lines

3) I haven't heard any complaints since we've added the cond_resched() patch so the performance issue seems to be really rare.

If I get complaits from real users about this, we can easily reconsider, it is not a big deal. But I just don't think preemptive action is warranted...

Hi Jan,

I know you have some catching up to do, but applying this patch to stable has become a priority for me.
It was a mistake on my part not to push harder 6 months ago, so I am trying to rectify this mistake now as soon as possible.

To answer your arguments against preemptive action:
1) My application has CAP_SYS_ADMIN, it is not malicious, but it cannot do its job without taking up more CPU that it needs to, because bursts of events will cause the event queue to grow to thousands of events and fanotify_merge() will become a high CPU consumer
2) It's not only about fanotify becoming slow, it's about fanotify making the entire system slow and as a result it takes a long time for the system to recover from this condition
3) You haven't heard any complains because nobody was using sb mark We have been using sb mark in production for a few years and carry this patch in our kernel, so I can say for certain that sb mark on a fs with heavy workload is disturbing the entire system without this patch.

I don't think that "regressing" the number of merged event is a big issue, as we never guaranteed any specific merge behavior and the behavior was hard enough to predict, so I don't think applications could have relied on it.

So, are you ok with me sending this patch to stable as is?

Improve the balance of hashed queue lists by mixing more event info relevant for merge.

For example, all FAN_CREATE name events in the same dir used to have the same merge key based on the dir inode. With this change the created file name is mixed into the merge key.

Signed-off-by Amir Goldstein <[email protected]>

---
 fs/notify/fanotify/fanotify.c | 33 +++++++++++++++++++++++++++------
 fs/notify/fanotify/fanotify.h | 20 +++++++++++++++++---
 2 files changed, 44 insertions(+), 9 deletions(-)

fs/notify/fanotify/fanotify.c +0 -0

index 6d3807012851..b19fef1c6f64 100644

fs/notify/fanotify/fanotify.c +3 -1

 	pr_debug("%s: ino=%lu size=%u dir_fh_len=%u child_fh_len=%u name_len=%u name='%.*s'\n",
 		 __func__, id->i_ino, size, dir_fh_len, child_fh_len,
 		 info->name_len, info->name_len, fanotify_info_name(info));

@@ -539,6 +554,8 @@ static struct fanotify_event *fanotify_alloc_event(struct fsnotify_group *group,
 	struct mem_cgroup *old_memcg;
 	struct inode *child = NULL;
 	bool name_event = false;
+	unsigned int hash = 0;
+	struct pid *pid;
 
 	if ((fid_mode & FAN_REPORT_DIR_FID) && dirid) {
 		/*

@@ -606,13 +623,17 @@ static struct fanotify_event *fanotify_alloc_event(struct fsnotify_group *group,
 	 * Use the victim inode instead of the watching inode as the id for
 	 * event queue, so event reported on parent is merged with event
 	 * reported on child when both directory and child watches exist.
-	 * Reduce object id to 32bit hash for hashed queue merge.
+	 * Reduce object id and event info to 32bit hash for hashed queue merge.
 	 */

fs/notify/fanotify/fanotify.c +2 -0

+	fanotify_init_event(event, hash, mask);
+	event->pid = pid;
 
 out:
 	set_active_memcg(old_memcg);

fs/notify/fanotify/fanotify.h +5 -0

index 2e856372ffc8..522fb1a68b30 100644
@@ -115,6 +115,11 @@ static inline void fanotify_info_init(struct fanotify_info *info)
 	info->name_len = 0;
 }
 
+static inline unsigned int fanotify_info_len(struct fanotify_info *info)
+{
+	return info->dir_fh_totlen + info->file_fh_totlen + info->name_len;
+}
+
 static inline void fanotify_info_copy_name(struct fanotify_info *info,
 					   const struct qstr *name)
 {

@@ -138,7 +143,10 @@ enum fanotify_event_type {
 };

fs/notify/fanotify/fanotify.h +4 -1

@@ -154,7 +162,10 @@ static inline void fanotify_init_event(struct fanotify_event *event,
 
 struct fanotify_fid_event {
 	struct fanotify_event fae;
-	__kernel_fsid_t fsid;
+	union {
+		__kernel_fsid_t fsid;
+		void *fskey;	/* 64 or 32 bits of fsid used for salt */
+	};
 	struct fanotify_fh object_fh;
 	/* Reserve space in object_fh.buf[] - access with fanotify_fh_buf() */
 	unsigned char _inline_fh_buf[FANOTIFY_INLINE_FH_LEN];

Quoted 17 lines · Amir Goldstein

Improve the balance of hashed queue lists by mixing more event info relevant for merge.

For example, all FAN_CREATE name events in the same dir used to have the same merge key based on the dir inode. With this change the created file name is mixed into the merge key.

Signed-off-by Amir Goldstein <[email protected]>

---
 fs/notify/fanotify/fanotify.c | 33 +++++++++++++++++++++++++++------
 fs/notify/fanotify/fanotify.h | 20 +++++++++++++++++---
 2 files changed, 44 insertions(+), 9 deletions(-)

fs/notify/fanotify/fanotify.c +0 -0

index 6d3807012851..b19fef1c6f64 100644

...

Quoted 2 lines

fs/notify/fanotify/fanotify.c +0 -0

@@ -476,8 +485,11 @@ static struct fanotify_event *fanotify_alloc_fid_event(struct inode *id,
 

fs/notify/fanotify/fanotify.c static struct fanotify_event *fanotify_alloc_fid_event(struct inode *id, · line 492

Quoted 9 lines

fs/notify/fanotify/fanotify.c +5 -2

      ffe->fae.type = FANOTIFY_EVENT_TYPE_FID;
      ffe->fsid = *fsid;
-     fanotify_encode_fh(&ffe->object_fh, id, fanotify_encode_fh_len(id),
-                        gfp);
+     fh = &ffe->object_fh;
+     fanotify_encode_fh(fh, id, fanotify_encode_fh_len(id), gfp);
+
+     /* Mix fsid+fid info into event merge key */
+     ffe->fae.info_hash = full_name_hash(ffe->fskey, fanotify_fh_buf(fh), fh->len);

Is it really sensible to hash FID with full_name_hash()? It would make more sense to treat it as binary data, not strings...

fs/notify/fanotify/fanotify.c static struct fanotify_event *fanotify_alloc_name_event(struct inode *id, · line 534

Quoted 10 lines

fs/notify/fanotify/fanotify.c +3 -0

      return &ffe->fae;
 }

@@ -517,6 +529,9 @@ static struct fanotify_event *fanotify_alloc_name_event(struct inode *id,
      if (file_name)
              fanotify_info_copy_name(info, file_name);
 
+     /* Mix fsid+dfid+name+fid info into event merge key */
+     fne->fae.info_hash = full_name_hash(fne->fskey, info->buf, fanotify_info_len(info));
+

Similarly here...

Quoted 23 lines

fs/notify/fanotify/fanotify.c +4 -3

      pr_debug("%s: ino=%lu size=%u dir_fh_len=%u child_fh_len=%u name_len=%u name='%.*s'\n",
               __func__, id->i_ino, size, dir_fh_len, child_fh_len,
               info->name_len, info->name_len, fanotify_info_name(info));

@@ -539,6 +554,8 @@ static struct fanotify_event *fanotify_alloc_event(struct fsnotify_group *group,
      struct mem_cgroup *old_memcg;
      struct inode *child = NULL;
      bool name_event = false;
+     unsigned int hash = 0;
+     struct pid *pid;
 
      if ((fid_mode & FAN_REPORT_DIR_FID) && dirid) {
              /*

@@ -606,13 +623,17 @@ static struct fanotify_event *fanotify_alloc_event(struct fsnotify_group *group,
       * Use the victim inode instead of the watching inode as the id for
       * event queue, so event reported on parent is merged with event
       * reported on child when both directory and child watches exist.
-      * Reduce object id to 32bit hash for hashed queue merge.
+      * Reduce object id and event info to 32bit hash for hashed queue merge.
       */
-     fanotify_init_event(event, hash_ptr(id, 32), mask);
+     hash = event->info_hash ^ hash_ptr(id, 32);
      if (FAN_GROUP_FLAG(group, FAN_REPORT_TID))
-             event->pid = get_pid(task_pid(current));

fs/notify/fanotify/fanotify.c static struct fanotify_event *fanotify_alloc_event(struct fsnotify_group *group, · line 634

Quoted 6 lines

fs/notify/fanotify/fanotify.c +4 -1

+             pid = get_pid(task_pid(current));
      else
-             event->pid = get_pid(task_tgid(current));
+             pid = get_pid(task_tgid(current));
+     /* Mix pid info into event merge key */
+     hash ^= hash_ptr(pid, 32);

hash_32() here?

Quoted 25 lines

fs/notify/fanotify/fanotify.c +2 -0

+     fanotify_init_event(event, hash, mask);
+     event->pid = pid;
 
 out:
      set_active_memcg(old_memcg);

fs/notify/fanotify/fanotify.h +5 -0

index 2e856372ffc8..522fb1a68b30 100644
@@ -115,6 +115,11 @@ static inline void fanotify_info_init(struct fanotify_info *info)
      info->name_len = 0;
 }
 
+static inline unsigned int fanotify_info_len(struct fanotify_info *info)
+{
+     return info->dir_fh_totlen + info->file_fh_totlen + info->name_len;
+}
+
 static inline void fanotify_info_copy_name(struct fanotify_info *info,
                                         const struct qstr *name)
 {

@@ -138,7 +143,10 @@ enum fanotify_event_type {
 };
 

fs/notify/fanotify/fanotify.h enum fanotify_event_type { · line 152

Quoted 9 lines

fs/notify/fanotify/fanotify.h +4 -1

 struct fanotify_event {
-     struct fsnotify_event fse;
+     union {
+             struct fsnotify_event fse;
+             unsigned int info_hash;
+     };
      u32 mask;
      enum fanotify_event_type type;
      struct pid *pid;

How is this ever safe? info_hash will likely overlay with 'list' in fsnotify_event.

Quoted 15 lines

fs/notify/fanotify/fanotify.h +4 -1

@@ -154,7 +162,10 @@ static inline void fanotify_init_event(struct fanotify_event *event,
 
 struct fanotify_fid_event {
      struct fanotify_event fae;
-     __kernel_fsid_t fsid;
+     union {
+             __kernel_fsid_t fsid;
+             void *fskey;    /* 64 or 32 bits of fsid used for salt */
+     };
      struct fanotify_fh object_fh;
      /* Reserve space in object_fh.buf[] - access with fanotify_fh_buf() */
      unsigned char _inline_fh_buf[FANOTIFY_INLINE_FH_LEN];

@@ -168,7 +179,10 @@ FANOTIFY_FE(struct fanotify_event *event)
 

fs/notify/fanotify/fanotify.h FANOTIFY_FE(struct fanotify_event *event) · line 187

Quoted 9 lines

fs/notify/fanotify/fanotify.h +4 -1

 struct fanotify_name_event {
      struct fanotify_event fae;
-     __kernel_fsid_t fsid;
+     union {
+             __kernel_fsid_t fsid;
+             void *fskey;    /* 64 or 32 bits of fsid used for salt */
+     };
      struct fanotify_info info;
 };

What games are you playing here with the unions? I presume you can remove these 'fskey' unions and just use (void *)(event->fsid) at appropriate places? IMO much more comprehensible...

Quoted 22 lines · Jan Kara

Quoted 17 lines · Amir Goldstein

Improve the balance of hashed queue lists by mixing more event info relevant for merge.

For example, all FAN_CREATE name events in the same dir used to have the same merge key based on the dir inode. With this change the created file name is mixed into the merge key.

Signed-off-by Amir Goldstein <[email protected]>

---
 fs/notify/fanotify/fanotify.c | 33 +++++++++++++++++++++++++++------
 fs/notify/fanotify/fanotify.h | 20 +++++++++++++++++---
 2 files changed, 44 insertions(+), 9 deletions(-)

fs/notify/fanotify/fanotify.c +0 -0

index 6d3807012851..b19fef1c6f64 100644

...

Quoted 2 lines

fs/notify/fanotify/fanotify.c +0 -0

@@ -476,8 +485,11 @@ static struct fanotify_event *fanotify_alloc_fid_event(struct inode *id,
 

Quoted 12 lines

fs/notify/fanotify/fanotify.c static struct fanotify_event *fanotify_alloc_fid_event(struct inode *id, · line 492

Quoted 9 lines

fs/notify/fanotify/fanotify.c +5 -2

      ffe->fae.type = FANOTIFY_EVENT_TYPE_FID;
      ffe->fsid = *fsid;
-     fanotify_encode_fh(&ffe->object_fh, id, fanotify_encode_fh_len(id),
-                        gfp);
+     fh = &ffe->object_fh;
+     fanotify_encode_fh(fh, id, fanotify_encode_fh_len(id), gfp);
+
+     /* Mix fsid+fid info into event merge key */
+     ffe->fae.info_hash = full_name_hash(ffe->fskey, fanotify_fh_buf(fh), fh->len);

Is it really sensible to hash FID with full_name_hash()? It would make more sense to treat it as binary data, not strings...

See the actual implementation of full_name_hash() for 64bit. it treats the string as an array of ulong, which is quite perfect for FID.

Quoted 36 lines

fs/notify/fanotify/fanotify.c static struct fanotify_event *fanotify_alloc_name_event(struct inode *id, · line 534

Quoted 10 lines

fs/notify/fanotify/fanotify.c +3 -0

      return &ffe->fae;
 }

@@ -517,6 +529,9 @@ static struct fanotify_event *fanotify_alloc_name_event(struct inode *id,
      if (file_name)
              fanotify_info_copy_name(info, file_name);
 
+     /* Mix fsid+dfid+name+fid info into event merge key */
+     fne->fae.info_hash = full_name_hash(fne->fskey, info->buf, fanotify_info_len(info));
+

Similarly here...

Quoted 23 lines

fs/notify/fanotify/fanotify.c +4 -3

      pr_debug("%s: ino=%lu size=%u dir_fh_len=%u child_fh_len=%u name_len=%u name='%.*s'\n",
               __func__, id->i_ino, size, dir_fh_len, child_fh_len,
               info->name_len, info->name_len, fanotify_info_name(info));

@@ -539,6 +554,8 @@ static struct fanotify_event *fanotify_alloc_event(struct fsnotify_group *group,
      struct mem_cgroup *old_memcg;
      struct inode *child = NULL;
      bool name_event = false;
+     unsigned int hash = 0;
+     struct pid *pid;
 
      if ((fid_mode & FAN_REPORT_DIR_FID) && dirid) {
              /*

@@ -606,13 +623,17 @@ static struct fanotify_event *fanotify_alloc_event(struct fsnotify_group *group,
       * Use the victim inode instead of the watching inode as the id for
       * event queue, so event reported on parent is merged with event
       * reported on child when both directory and child watches exist.
-      * Reduce object id to 32bit hash for hashed queue merge.
+      * Reduce object id and event info to 32bit hash for hashed queue merge.
       */
-     fanotify_init_event(event, hash_ptr(id, 32), mask);
+     hash = event->info_hash ^ hash_ptr(id, 32);
      if (FAN_GROUP_FLAG(group, FAN_REPORT_TID))
-             event->pid = get_pid(task_pid(current));

Quoted 8 lines

fs/notify/fanotify/fanotify.c static struct fanotify_event *fanotify_alloc_event(struct fsnotify_group *group, · line 634

Quoted 6 lines

fs/notify/fanotify/fanotify.c +4 -1

+             pid = get_pid(task_pid(current));
      else
-             event->pid = get_pid(task_tgid(current));
+             pid = get_pid(task_tgid(current));
+     /* Mix pid info into event merge key */
+     hash ^= hash_ptr(pid, 32);

hash_32() here?

I don't think so.
hash_32() looses the high bits of ptr before mixing them. hash_ptr(pid, 32) looses the *low* bits which contain less entropy after mixing all 64bits of ptr.

Quoted 25 lines

Quoted 25 lines

fs/notify/fanotify/fanotify.c +2 -0

+     fanotify_init_event(event, hash, mask);
+     event->pid = pid;
 
 out:
      set_active_memcg(old_memcg);

fs/notify/fanotify/fanotify.h +5 -0

index 2e856372ffc8..522fb1a68b30 100644
@@ -115,6 +115,11 @@ static inline void fanotify_info_init(struct fanotify_info *info)
      info->name_len = 0;
 }
 
+static inline unsigned int fanotify_info_len(struct fanotify_info *info)
+{
+     return info->dir_fh_totlen + info->file_fh_totlen + info->name_len;
+}
+
 static inline void fanotify_info_copy_name(struct fanotify_info *info,
                                         const struct qstr *name)
 {

@@ -138,7 +143,10 @@ enum fanotify_event_type {
 };
 

Quoted 12 lines

fs/notify/fanotify/fanotify.h enum fanotify_event_type { · line 152

Quoted 9 lines

fs/notify/fanotify/fanotify.h +4 -1

 struct fanotify_event {
-     struct fsnotify_event fse;
+     union {
+             struct fsnotify_event fse;
+             unsigned int info_hash;
+     };
      u32 mask;
      enum fanotify_event_type type;
      struct pid *pid;

How is this ever safe? info_hash will likely overlay with 'list' in fsnotify_event.

Oh yeh. That's an ugly hack. Sorry for that.
I wanted to avoid adding an arg unsigned int *info_hash to all fanotify_alloc_*_event() helpers, so I used this uninitialized space in event instead.
I'll do it the proper way.

Quoted 28 lines

Quoted 14 lines

fs/notify/fanotify/fanotify.h +4 -1

@@ -154,7 +162,10 @@ static inline void fanotify_init_event(struct fanotify_event *event,
 
 struct fanotify_fid_event {
      struct fanotify_event fae;
-     __kernel_fsid_t fsid;
+     union {
+             __kernel_fsid_t fsid;
+             void *fskey;    /* 64 or 32 bits of fsid used for salt */
+     };
      struct fanotify_fh object_fh;
      /* Reserve space in object_fh.buf[] - access with fanotify_fh_buf() */
      unsigned char _inline_fh_buf[FANOTIFY_INLINE_FH_LEN];

fs/notify/fanotify/fanotify.h FANOTIFY_FE(struct fanotify_event *event) · line 187

Quoted 10 lines

fs/notify/fanotify/fanotify.h +4 -1

@@ -168,7 +179,10 @@ FANOTIFY_FE(struct fanotify_event *event)
 
 struct fanotify_name_event {
      struct fanotify_event fae;
-     __kernel_fsid_t fsid;
+     union {
+             __kernel_fsid_t fsid;
+             void *fskey;    /* 64 or 32 bits of fsid used for salt */
+     };
      struct fanotify_info info;
 };

What games are you playing here with the unions? I presume you can remove these 'fskey' unions and just use (void *)(event->fsid) at appropriate places? IMO much more comprehensible...

Quoted 14 lines · Amir Goldstein

Quoted 14 lines

Quoted 14 lines

fs/notify/fanotify/fanotify.h +4 -1

@@ -154,7 +162,10 @@ static inline void fanotify_init_event(struct fanotify_event *event,
 
 struct fanotify_fid_event {
      struct fanotify_event fae;
-     __kernel_fsid_t fsid;
+     union {
+             __kernel_fsid_t fsid;
+             void *fskey;    /* 64 or 32 bits of fsid used for salt */
+     };
      struct fanotify_fh object_fh;
      /* Reserve space in object_fh.buf[] - access with fanotify_fh_buf() */
      unsigned char _inline_fh_buf[FANOTIFY_INLINE_FH_LEN];

@@ -168,7 +179,10 @@ FANOTIFY_FE(struct fanotify_event *event)
 

Quoted 14 lines

Quoted 10 lines

fs/notify/fanotify/fanotify.h FANOTIFY_FE(struct fanotify_event *event) · line 187

Quoted 9 lines

fs/notify/fanotify/fanotify.h +4 -1

 struct fanotify_name_event {
      struct fanotify_event fae;
-     __kernel_fsid_t fsid;
+     union {
+             __kernel_fsid_t fsid;
+             void *fskey;    /* 64 or 32 bits of fsid used for salt */
+     };
      struct fanotify_info info;
 };

Quoted 3 lines

What games are you playing here with the unions? I presume you can remove these 'fskey' unions and just use (void *)(event->fsid) at appropriate places? IMO much more comprehensible...

FYI, this is what the open coded conversion looks like:

(void *)*(long *)event->fsid.val

Quoted 30 lines · Amir Goldstein

Quoted 14 lines · Amir Goldstein

Quoted 14 lines

Quoted 14 lines

fs/notify/fanotify/fanotify.h +4 -1

@@ -154,7 +162,10 @@ static inline void fanotify_init_event(struct fanotify_event *event,
 
 struct fanotify_fid_event {
      struct fanotify_event fae;
-     __kernel_fsid_t fsid;
+     union {
+             __kernel_fsid_t fsid;
+             void *fskey;    /* 64 or 32 bits of fsid used for salt */
+     };
      struct fanotify_fh object_fh;
      /* Reserve space in object_fh.buf[] - access with fanotify_fh_buf() */
      unsigned char _inline_fh_buf[FANOTIFY_INLINE_FH_LEN];

@@ -168,7 +179,10 @@ FANOTIFY_FE(struct fanotify_event *event)
 

Quoted 14 lines

Quoted 10 lines

fs/notify/fanotify/fanotify.h FANOTIFY_FE(struct fanotify_event *event) · line 187

Quoted 9 lines

fs/notify/fanotify/fanotify.h +4 -1

 struct fanotify_name_event {
      struct fanotify_event fae;
-     __kernel_fsid_t fsid;
+     union {
+             __kernel_fsid_t fsid;
+             void *fskey;    /* 64 or 32 bits of fsid used for salt */
+     };
      struct fanotify_info info;
 };

Quoted 3 lines

What games are you playing here with the unions? I presume you can remove these 'fskey' unions and just use (void *)(event->fsid) at appropriate places? IMO much more comprehensible...

Quoted 3 lines

FYI, this is what the open coded conversion looks like:

(void *)*(long *)event->fsid.val

Not great but at least fairly localized. I'd just note that this doesn't quite work on 32-bit archs (sizeof(long) != sizeof(__kernel_fsid_t) there). Maybe we could just use

hash_32(event->fsid.val[0]) ^ hash_32(event->fsid.val[1])

for mixing into the 'key' value and thus avoid all these games?

Jan,

fanotify_merge() has been observed [1] to consume a lot of CPU. This is not surprising considering that it is implemented as a linear search on a practically unbounded size list.

The following series improves the linear search for an event to merge in three different ways:
1. Hash events into as much as to 128 lists
2. Limit linear search to 128 last list elements
3. Use a better key - instead of victim inode ptr, use a hash of all the compared fields

The end result can be observed in the test run times below. The test is an extension of your queue overflow LTP test [2]. The timing results use are from the 2nd run of -i 2, where files are already existing in the test fs.

With an unlimited queue, queueing of 16385 events on unique objects is ~3 times faster than before the change.

In fact, the run time of queueing 16385 events (~600ms) is almost the same as the run time of rejecting 16385 events (~550ms) due to full queue, which suggest a very low overhead for merging events.

The test runs two passes to test event merge, the "create" pass and the "open" pass.

Before the change (v5.11-rc2) 100% of the events of the "open" pass are merged (16385 files and 16385 events).

After the change, only %50 of the events of the "open" pass are merged (16385 files and 25462 events).

This is because 16384 is the maximum number of events that we can merge when hash table is fully balanced.
When reducing the number of unique objects to 8192, all events on the "open" pass are merged.

Thanks,
Amir.

v5.11-rc2, run #2 of ./fanotify05 -i 2:

fanotify05.c:109: TINFO: Test #0: Limited queue fanotify05.c:98: TINFO: Created 16385 files in 1653ms fanotify05.c:98: TINFO: Opened 16385 files in 543ms fanotify05.c:77: TINFO: Got event #0 filename=fname_0 fanotify05.c:176: TPASS: Got an overflow event: pid=0 fd=-1 fanotify05.c:182: TINFO: Got 16385 events

fanotify05.c:109: TINFO: Test #1: Unlimited queue fanotify05.c:98: TINFO: Created 16385 files in 1683ms fanotify05.c:98: TINFO: Opened 16385 files in 1647ms fanotify05.c:77: TINFO: Got event #0 filename=fname_0 fanotify05.c:138: TPASS: Overflow event not generated! fanotify05.c:182: TINFO: Got 16385 events

fanotify_merge branch, run #2 of ./fanotify05 -i 2:

fanotify05.c:109: TINFO: Test #0: Limited queue fanotify05.c:98: TINFO: Created 16385 files in 616ms fanotify05.c:98: TINFO: Opened 16385 files in 549ms fanotify05.c:77: TINFO: Got event #0 filename=fname_0 fanotify05.c:176: TPASS: Got an overflow event: pid=0 fd=-1 fanotify05.c:182: TINFO: Got 16385 events

fanotify05.c:109: TINFO: Test #1: Unlimited queue fanotify05.c:98: TINFO: Created 16385 files in 614ms fanotify05.c:98: TINFO: Opened 16385 files in 599ms fanotify05.c:77: TINFO: Got event #0 filename=fname_0 fanotify05.c:138: TPASS: Overflow event not generated! fanotify05.c:182: TINFO: Got 25462 events

[1] https://lore.kernel.org/linux-fsdevel/[email protected]/
[2] https://github.com/amir73il/ltp/commits/fanotify_merge

Amir Goldstein (7):
fsnotify: allow fsnotify_{peek,remove}_first_event with empty queue
fsnotify: support hashed notification queue
fsnotify: read events from hashed notification queue by order of
insertion
fanotify: enable hashed notification queue for FAN_CLASS_NOTIF groups
fanotify: limit number of event merge attempts
fanotify: mix event info into merge key hash
fsnotify: print some debug stats on hashed queue overflow

 fs/notify/fanotify/fanotify.c      |  40 ++++++-
 fs/notify/fanotify/fanotify.h      |  24 +++-
 fs/notify/fanotify/fanotify_user.c |  55 ++++++---
 fs/notify/group.c                  |  37 ++++--
 fs/notify/inotify/inotify_user.c   |  22 ++--
 fs/notify/notification.c           | 175 +++++++++++++++++++++++++----
 include/linux/fsnotify_backend.h   | 105 +++++++++++++++--
 7 files changed, 383 insertions(+), 75 deletions(-)

Signature · 1 line

2.25.1

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,

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).

The disadvantage is increase of
event size by one pointer on 64-bit but I think we can live with that. What do you think?

Quoted 23 lines · Jan Kara

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;
};

Quoted 4 lines

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.

Quoted 3 lines

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.

Quoted 3 lines

The disadvantage is increase of
event size by one pointer on 64-bit but I think we can live with that. What do you think?

Given the round size of fixes size events in v5.10, that would be a shame:

ls -l /sys/kernel/slab/*notify*event
lrwxrwxrwx 1 root root 0 Feb 17 12:23
/sys/kernel/slab/fanotify_fid_event -> :0000064
lrwxrwxrwx 1 root root 0 Feb 17 12:23
/sys/kernel/slab/fanotify_path_event -> :0000056
lrwxrwxrwx 1 root root 0 Feb 17 12:23
/sys/kernel/slab/fanotify_perm_event -> :0000064

Counter proposal:

struct fsnotify_event {
        struct list_head list;
        struct fsnotify_event *hash_next;
        unsigned int key;
        u32 mask;
};

It is quite strange that mask is a member of struct fanotify_event and struct inotify_event_info to begin with.

Moving the mask member to struct fsnotify_event like that is not going to change the resulting inotify/fanotify event size.

We can actually squeeze fanotify_event_type into 2 low bits of pid pointer, and reduce the size of all fanotify events by one pointer, because FANOTIFY_EVENT_TYPE_OVERFLOW is nice to have. The overflow event can use FANOTIFY_EVENT_TYPE_PATH with a NULL path values (as early versions of the patch did).

This is not worth doing with current round event size, IMO.

Quoted 35 lines · Amir Goldstein

Quoted 23 lines · Jan Kara

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;
};

Quoted 4 lines

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.

Quoted 3 lines

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).

Quoted 2 lines

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...

Quoted 37 lines · Jan Kara

Quoted 35 lines · Amir Goldstein

Quoted 23 lines · Jan Kara

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;
};

Quoted 4 lines

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.

Quoted 3 lines

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).

Quoted 9 lines

Quoted 2 lines

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 I stayed with hashed queue only for group priority 0.

Pushed partly tested result to fanotify_merge branch.

Will post after testing unless you have reservations.

Quoted 48 lines · Amir Goldstein

Quoted 37 lines · Jan Kara

Quoted 35 lines · Amir Goldstein

Quoted 23 lines · Jan Kara

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;
};

Quoted 4 lines

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.

Quoted 3 lines

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).

Quoted 9 lines

Quoted 2 lines

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...

Quoted 5 lines

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.

Quoted 56 lines · Jan Kara

Quoted 53 lines · Amir Goldstein

Quoted 37 lines · Jan Kara

Quoted 35 lines · Amir Goldstein

Quoted 23 lines · Jan Kara

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;
};

Quoted 4 lines

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.

Quoted 3 lines

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).

Quoted 9 lines

Quoted 2 lines

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.

Quoted 4 lines

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.

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?

Quoted 57 lines · Amir Goldstein

Quoted 56 lines · Jan Kara

Quoted 53 lines · Amir Goldstein

Quoted 37 lines · Jan Kara

Quoted 35 lines · Amir Goldstein

Quoted 23 lines · Jan Kara

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;
};

Quoted 4 lines

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.

Quoted 3 lines

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).

Quoted 9 lines

Quoted 2 lines

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.

Quoted 6 lines

Quoted 4 lines

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 :).

Quoted 11 lines

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

Signature · 2 lines

Jan Kara <[email protected]>
SUSE Labs, CR

Quoted 103 lines · Jan Kara

Quoted 57 lines · Amir Goldstein

Quoted 56 lines · Jan Kara

Quoted 53 lines · Amir Goldstein

Quoted 37 lines · Jan Kara

Quoted 35 lines · Amir Goldstein

Quoted 23 lines · Jan Kara

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;
};

Quoted 4 lines

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.

Quoted 3 lines

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).

Quoted 9 lines

Quoted 2 lines

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.

Quoted 6 lines

Quoted 4 lines

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 :).

Quoted 11 lines

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:

Quoted 3 lines

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

Quoted 7 lines

if (!event->next_hash) {
      group->merge_hash[hash(event->key)]->lastp =
              &(group->merge_hash[hash(event->key)]->first);
}

Clearer now?

Quoted 109 lines · Jan Kara

Quoted 103 lines · Jan Kara

Quoted 57 lines · Amir Goldstein

Quoted 56 lines · Jan Kara

Quoted 53 lines · Amir Goldstein

Quoted 37 lines · Jan Kara

Quoted 35 lines · Amir Goldstein

Quoted 23 lines · Jan Kara

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;
};

Quoted 4 lines

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.

Quoted 3 lines

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).

Quoted 9 lines

Quoted 2 lines

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.

Quoted 6 lines

Quoted 4 lines

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 :).

Quoted 11 lines

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:

Quoted 3 lines

list_del_init(&event->list);
group->q_len--; group->merge_hash[hash(event->key)]->first = event->next_hash;

Quoted 6 lines

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.

Quoted 1 line

Quoted 6 lines

Quoted 6 lines

if (!event->next_hash) {
      group->merge_hash[hash(event->key)]->lastp =
              &(group->merge_hash[hash(event->key)]->first);
}

Clearer now?

Yes, and much simpler.

Quoted 139 lines · Amir Goldstein

Quoted 109 lines · Jan Kara

Quoted 103 lines · Jan Kara

Quoted 57 lines · Amir Goldstein

Quoted 56 lines · Jan Kara

Quoted 53 lines · Amir Goldstein

Quoted 37 lines · Jan Kara

Quoted 35 lines · Amir Goldstein

Quoted 23 lines · Jan Kara

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;
};

Quoted 4 lines

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.

Quoted 3 lines

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).

Quoted 9 lines

Quoted 2 lines

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.

Quoted 6 lines

Quoted 4 lines

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 :).

Quoted 11 lines

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:

Quoted 3 lines

list_del_init(&event->list);
group->q_len--; group->merge_hash[hash(event->key)]->first = event->next_hash;

Quoted 6 lines

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.

Quoted 6 lines

Quoted 6 lines

if (!event->next_hash) {
      group->merge_hash[hash(event->key)]->lastp =
              &(group->merge_hash[hash(event->key)]->first);
}

Quoted 4 lines

Quoted 1 line

Quoted 1 line

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