}
/* and the list better be locked by something too! */
-static int fanotify_merge(struct list_head *list, struct fsnotify_event *event)
+static int fanotify_merge(struct fsnotify_group *group,
+ struct fsnotify_event *event)
{
- struct fsnotify_event *test_event;
struct fanotify_event *old, *new = FANOTIFY_E(event);
+ unsigned int bucket = fanotify_event_hash_bucket(group, new);
+ struct hlist_head *hlist = &group->fanotify_data.merge_hash[bucket];
- pr_debug("%s: list=%p event=%p\n", __func__, list, event);
+ pr_debug("%s: group=%p event=%p bucket=%u\n", __func__,
+ group, event, bucket);
/*
* Don't merge a permission event with any other event so that we know
if (fanotify_is_perm_event(new->mask))
return 0;
- list_for_each_entry_reverse(test_event, list, list) {
- old = FANOTIFY_E(test_event);
+ hlist_for_each_entry(old, hlist, merge_list) {
if (fanotify_should_merge(old, new)) {
old->mask |= new->mask;
return 1;
return ret;
}
/* Event not yet reported? Just remove it. */
- if (event->state == FAN_EVENT_INIT)
+ if (event->state == FAN_EVENT_INIT) {
fsnotify_remove_queued_event(group, &event->fae.fse);
+ /* Permission events are not supposed to be hashed */
+ WARN_ON_ONCE(!hlist_unhashed(&event->fae.merge_list));
+ }
/*
* Event may be also answered in case signal delivery raced
* with wakeup. In that case we have nothing to do besides
return fsid;
}
+/*
+ * Add an event to hash table for faster merge.
+ */
+static void fanotify_insert_event(struct fsnotify_group *group,
+ struct fsnotify_event *fsn_event)
+{
+ struct fanotify_event *event = FANOTIFY_E(fsn_event);
+ unsigned int bucket = fanotify_event_hash_bucket(group, event);
+ struct hlist_head *hlist = &group->fanotify_data.merge_hash[bucket];
+
+ assert_spin_locked(&group->notification_lock);
+
+ pr_debug("%s: group=%p event=%p bucket=%u\n", __func__,
+ group, event, bucket);
+
+ hlist_add_head(&event->merge_list, hlist);
+}
+
static int fanotify_handle_event(struct fsnotify_group *group, u32 mask,
const void *data, int data_type,
struct inode *dir,
}
fsn_event = &event->fse;
- ret = fsnotify_add_event(group, fsn_event, fanotify_merge);
+ ret = fsnotify_add_event(group, fsn_event, fanotify_merge,
+ fanotify_is_hashed_event(mask) ?
+ fanotify_insert_event : NULL);
if (ret) {
/* Permission events shouldn't be merged */
BUG_ON(ret == 1 && mask & FANOTIFY_PERM_EVENTS);
{
struct user_struct *user;
+ kfree(group->fanotify_data.merge_hash);
user = group->fanotify_data.user;
atomic_dec(&user->fanotify_listeners);
free_uid(user);
#include <linux/path.h>
#include <linux/slab.h>
#include <linux/exportfs.h>
+#include <linux/hashtable.h>
extern struct kmem_cache *fanotify_mark_cache;
extern struct kmem_cache *fanotify_fid_event_cachep;
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, u32 mask)
{
fsnotify_init_event(&event->fse);
+ INIT_HLIST_NODE(&event->merge_list);
event->hash = hash;
event->mask = mask;
event->pid = NULL;
else
return NULL;
}
+
+/*
+ * Use 128 size hash table to speed up events merge.
+ */
+#define FANOTIFY_HTABLE_BITS (7)
+#define FANOTIFY_HTABLE_SIZE (1 << FANOTIFY_HTABLE_BITS)
+#define FANOTIFY_HTABLE_MASK (FANOTIFY_HTABLE_SIZE - 1)
+
+/*
+ * Permission events and overflow event do not get merged - don't hash them.
+ */
+static inline bool fanotify_is_hashed_event(u32 mask)
+{
+ return !fanotify_is_perm_event(mask) && !(mask & FS_Q_OVERFLOW);
+}
+
+static inline unsigned int fanotify_event_hash_bucket(
+ struct fsnotify_group *group,
+ struct fanotify_event *event)
+{
+ return event->hash & FANOTIFY_HTABLE_MASK;
+}
return info_len;
}
+/*
+ * Remove an hashed event from merge hash table.
+ */
+static void fanotify_unhash_event(struct fsnotify_group *group,
+ struct fanotify_event *event)
+{
+ assert_spin_locked(&group->notification_lock);
+
+ pr_debug("%s: group=%p event=%p bucket=%u\n", __func__,
+ group, event, fanotify_event_hash_bucket(group, event));
+
+ if (WARN_ON_ONCE(hlist_unhashed(&event->merge_list)))
+ return;
+
+ hlist_del_init(&event->merge_list);
+}
+
/*
* Get an fanotify notification event if one exists and is small
* enough to fit in "count". Return an error pointer if the count
fsnotify_remove_first_event(group);
if (fanotify_is_perm_event(event->mask))
FANOTIFY_PERM(event)->state = FAN_EVENT_REPORTED;
+ if (fanotify_is_hashed_event(event->mask))
+ fanotify_unhash_event(group, event);
out:
spin_unlock(&group->notification_lock);
return event;
return &oevent->fse;
}
+static struct hlist_head *fanotify_alloc_merge_hash(void)
+{
+ struct hlist_head *hash;
+
+ hash = kmalloc(sizeof(struct hlist_head) << FANOTIFY_HTABLE_BITS,
+ GFP_KERNEL_ACCOUNT);
+ if (!hash)
+ return NULL;
+
+ __hash_init(hash, FANOTIFY_HTABLE_SIZE);
+
+ return hash;
+}
+
/* fanotify syscalls */
SYSCALL_DEFINE2(fanotify_init, unsigned int, flags, unsigned int, event_f_flags)
{
atomic_inc(&user->fanotify_listeners);
group->memcg = get_mem_cgroup_from_mm(current->mm);
+ group->fanotify_data.merge_hash = fanotify_alloc_merge_hash();
+ if (!group->fanotify_data.merge_hash) {
+ fd = -ENOMEM;
+ goto out_destroy_group;
+ }
+
group->overflow_event = fanotify_alloc_overflow_event();
if (unlikely(!group->overflow_event)) {
fd = -ENOMEM;
return false;
}
-static int inotify_merge(struct list_head *list,
- struct fsnotify_event *event)
+static int inotify_merge(struct fsnotify_group *group,
+ struct fsnotify_event *event)
{
+ struct list_head *list = &group->notification_list;
struct fsnotify_event *last_event;
last_event = list_entry(list->prev, struct fsnotify_event, list);
if (len)
strcpy(event->name, name->name);
- ret = fsnotify_add_event(group, fsn_event, inotify_merge);
+ ret = fsnotify_add_event(group, fsn_event, inotify_merge, NULL);
if (ret) {
/* Our event wasn't used in the end. Free it. */
fsnotify_destroy_event(group, fsn_event);
}
/*
- * Add an event to the group notification queue. The group can later pull this
- * event off the queue to deal with. The function returns 0 if the event was
- * added to the queue, 1 if the event was merged with some other queued event,
+ * Try to add an event to the notification queue.
+ * The group can later pull this event off the queue to deal with.
+ * The group can use the @merge hook to merge the event with a queued event.
+ * The group can use the @insert hook to insert the event into hash table.
+ * The function returns:
+ * 0 if the event was added to a queue
+ * 1 if the event was merged with some other queued event
* 2 if the event was not queued - either the queue of events has overflown
- * or the group is shutting down.
+ * or the group is shutting down.
*/
int fsnotify_add_event(struct fsnotify_group *group,
struct fsnotify_event *event,
- int (*merge)(struct list_head *,
- struct fsnotify_event *))
+ int (*merge)(struct fsnotify_group *,
+ struct fsnotify_event *),
+ void (*insert)(struct fsnotify_group *,
+ struct fsnotify_event *))
{
int ret = 0;
struct list_head *list = &group->notification_list;
}
if (!list_empty(list) && merge) {
- ret = merge(list, event);
+ ret = merge(group, event);
if (ret) {
spin_unlock(&group->notification_lock);
return ret;
queue:
group->q_len++;
list_add_tail(&event->list, list);
+ if (insert)
+ insert(group, event);
spin_unlock(&group->notification_lock);
wake_up(&group->notification_waitq);
#endif
#ifdef CONFIG_FANOTIFY
struct fanotify_group_private_data {
+ /* Hash table of events for merge */
+ struct hlist_head *merge_hash;
/* allows a group to block waiting for a userspace response */
struct list_head access_list;
wait_queue_head_t access_waitq;
/* attach the event to the group notification queue */
extern int fsnotify_add_event(struct fsnotify_group *group,
struct fsnotify_event *event,
- int (*merge)(struct list_head *,
- struct fsnotify_event *));
+ int (*merge)(struct fsnotify_group *,
+ struct fsnotify_event *),
+ void (*insert)(struct fsnotify_group *,
+ struct fsnotify_event *));
/* Queue overflow event to a notification group */
static inline void fsnotify_queue_overflow(struct fsnotify_group *group)
{
- fsnotify_add_event(group, group->overflow_event, NULL);
+ fsnotify_add_event(group, group->overflow_event, NULL, NULL);
}
static inline bool fsnotify_notify_queue_is_empty(struct fsnotify_group *group)