fsnotify: Remove indirection from mark list addition
[sfrench/cifs-2.6.git] / fs / notify / mark.c
1 /*
2  *  Copyright (C) 2008 Red Hat, Inc., Eric Paris <eparis@redhat.com>
3  *
4  *  This program is free software; you can redistribute it and/or modify
5  *  it under the terms of the GNU General Public License as published by
6  *  the Free Software Foundation; either version 2, or (at your option)
7  *  any later version.
8  *
9  *  This program is distributed in the hope that it will be useful,
10  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
11  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  *  GNU General Public License for more details.
13  *
14  *  You should have received a copy of the GNU General Public License
15  *  along with this program; see the file COPYING.  If not, write to
16  *  the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
17  */
18
19 /*
20  * fsnotify inode mark locking/lifetime/and refcnting
21  *
22  * REFCNT:
23  * The group->recnt and mark->refcnt tell how many "things" in the kernel
24  * currently are referencing the objects. Both kind of objects typically will
25  * live inside the kernel with a refcnt of 2, one for its creation and one for
26  * the reference a group and a mark hold to each other.
27  * If you are holding the appropriate locks, you can take a reference and the
28  * object itself is guaranteed to survive until the reference is dropped.
29  *
30  * LOCKING:
31  * There are 3 locks involved with fsnotify inode marks and they MUST be taken
32  * in order as follows:
33  *
34  * group->mark_mutex
35  * mark->lock
36  * inode->i_lock
37  *
38  * group->mark_mutex protects the marks_list anchored inside a given group and
39  * each mark is hooked via the g_list.  It also protects the groups private
40  * data (i.e group limits).
41
42  * mark->lock protects the marks attributes like its masks and flags.
43  * Furthermore it protects the access to a reference of the group that the mark
44  * is assigned to as well as the access to a reference of the inode/vfsmount
45  * that is being watched by the mark.
46  *
47  * inode->i_lock protects the i_fsnotify_marks list anchored inside a
48  * given inode and each mark is hooked via the i_list. (and sorta the
49  * free_i_list)
50  *
51  *
52  * LIFETIME:
53  * Inode marks survive between when they are added to an inode and when their
54  * refcnt==0. Marks are also protected by fsnotify_mark_srcu.
55  *
56  * The inode mark can be cleared for a number of different reasons including:
57  * - The inode is unlinked for the last time.  (fsnotify_inode_remove)
58  * - The inode is being evicted from cache. (fsnotify_inode_delete)
59  * - The fs the inode is on is unmounted.  (fsnotify_inode_delete/fsnotify_unmount_inodes)
60  * - Something explicitly requests that it be removed.  (fsnotify_destroy_mark)
61  * - The fsnotify_group associated with the mark is going away and all such marks
62  *   need to be cleaned up. (fsnotify_clear_marks_by_group)
63  *
64  * This has the very interesting property of being able to run concurrently with
65  * any (or all) other directions.
66  */
67
68 #include <linux/fs.h>
69 #include <linux/init.h>
70 #include <linux/kernel.h>
71 #include <linux/kthread.h>
72 #include <linux/module.h>
73 #include <linux/mutex.h>
74 #include <linux/slab.h>
75 #include <linux/spinlock.h>
76 #include <linux/srcu.h>
77
78 #include <linux/atomic.h>
79
80 #include <linux/fsnotify_backend.h>
81 #include "fsnotify.h"
82
83 #define FSNOTIFY_REAPER_DELAY   (1)     /* 1 jiffy */
84
85 struct srcu_struct fsnotify_mark_srcu;
86 struct kmem_cache *fsnotify_mark_connector_cachep;
87
88 static DEFINE_SPINLOCK(destroy_lock);
89 static LIST_HEAD(destroy_list);
90
91 static void fsnotify_mark_destroy_workfn(struct work_struct *work);
92 static DECLARE_DELAYED_WORK(reaper_work, fsnotify_mark_destroy_workfn);
93
94 void fsnotify_get_mark(struct fsnotify_mark *mark)
95 {
96         atomic_inc(&mark->refcnt);
97 }
98
99 void fsnotify_put_mark(struct fsnotify_mark *mark)
100 {
101         if (atomic_dec_and_test(&mark->refcnt)) {
102                 if (mark->group)
103                         fsnotify_put_group(mark->group);
104                 mark->free_mark(mark);
105         }
106 }
107
108 /* Calculate mask of events for a list of marks */
109 u32 fsnotify_recalc_mask(struct fsnotify_mark_connector *conn)
110 {
111         u32 new_mask = 0;
112         struct fsnotify_mark *mark;
113
114         if (!conn)
115                 return 0;
116
117         hlist_for_each_entry(mark, &conn->list, obj_list)
118                 new_mask |= mark->mask;
119         return new_mask;
120 }
121
122 /*
123  * Remove mark from inode / vfsmount list, group list, drop inode reference
124  * if we got one.
125  *
126  * Must be called with group->mark_mutex held.
127  */
128 void fsnotify_detach_mark(struct fsnotify_mark *mark)
129 {
130         struct inode *inode = NULL;
131         struct fsnotify_group *group = mark->group;
132
133         BUG_ON(!mutex_is_locked(&group->mark_mutex));
134
135         spin_lock(&mark->lock);
136
137         /* something else already called this function on this mark */
138         if (!(mark->flags & FSNOTIFY_MARK_FLAG_ATTACHED)) {
139                 spin_unlock(&mark->lock);
140                 return;
141         }
142
143         mark->flags &= ~FSNOTIFY_MARK_FLAG_ATTACHED;
144
145         if (mark->connector->flags & FSNOTIFY_OBJ_TYPE_INODE)
146                 inode = fsnotify_destroy_inode_mark(mark);
147         else if (mark->connector->flags & FSNOTIFY_OBJ_TYPE_VFSMOUNT)
148                 fsnotify_destroy_vfsmount_mark(mark);
149         else
150                 BUG();
151         /*
152          * Note that we didn't update flags telling whether inode cares about
153          * what's happening with children. We update these flags from
154          * __fsnotify_parent() lazily when next event happens on one of our
155          * children.
156          */
157
158         list_del_init(&mark->g_list);
159
160         spin_unlock(&mark->lock);
161
162         if (inode)
163                 iput(inode);
164
165         atomic_dec(&group->num_marks);
166 }
167
168 /*
169  * Prepare mark for freeing and add it to the list of marks prepared for
170  * freeing. The actual freeing must happen after SRCU period ends and the
171  * caller is responsible for this.
172  *
173  * The function returns true if the mark was added to the list of marks for
174  * freeing. The function returns false if someone else has already called
175  * __fsnotify_free_mark() for the mark.
176  */
177 static bool __fsnotify_free_mark(struct fsnotify_mark *mark)
178 {
179         struct fsnotify_group *group = mark->group;
180
181         spin_lock(&mark->lock);
182         /* something else already called this function on this mark */
183         if (!(mark->flags & FSNOTIFY_MARK_FLAG_ALIVE)) {
184                 spin_unlock(&mark->lock);
185                 return false;
186         }
187         mark->flags &= ~FSNOTIFY_MARK_FLAG_ALIVE;
188         spin_unlock(&mark->lock);
189
190         /*
191          * Some groups like to know that marks are being freed.  This is a
192          * callback to the group function to let it know that this mark
193          * is being freed.
194          */
195         if (group->ops->freeing_mark)
196                 group->ops->freeing_mark(mark, group);
197
198         spin_lock(&destroy_lock);
199         list_add(&mark->g_list, &destroy_list);
200         spin_unlock(&destroy_lock);
201
202         return true;
203 }
204
205 /*
206  * Free fsnotify mark. The freeing is actually happening from a workqueue which
207  * first waits for srcu period end. Caller must have a reference to the mark
208  * or be protected by fsnotify_mark_srcu.
209  */
210 void fsnotify_free_mark(struct fsnotify_mark *mark)
211 {
212         if (__fsnotify_free_mark(mark)) {
213                 queue_delayed_work(system_unbound_wq, &reaper_work,
214                                    FSNOTIFY_REAPER_DELAY);
215         }
216 }
217
218 void fsnotify_destroy_mark(struct fsnotify_mark *mark,
219                            struct fsnotify_group *group)
220 {
221         mutex_lock_nested(&group->mark_mutex, SINGLE_DEPTH_NESTING);
222         fsnotify_detach_mark(mark);
223         mutex_unlock(&group->mark_mutex);
224         fsnotify_free_mark(mark);
225 }
226
227 void fsnotify_destroy_marks(struct fsnotify_mark_connector *conn,
228                             spinlock_t *lock)
229 {
230         struct fsnotify_mark *mark;
231
232         if (!conn)
233                 return;
234
235         while (1) {
236                 /*
237                  * We have to be careful since we can race with e.g.
238                  * fsnotify_clear_marks_by_group() and once we drop 'lock',
239                  * mark can get removed from the obj_list and destroyed. But
240                  * we are holding mark reference so mark cannot be freed and
241                  * calling fsnotify_destroy_mark() more than once is fine.
242                  */
243                 spin_lock(lock);
244                 if (hlist_empty(&conn->list)) {
245                         spin_unlock(lock);
246                         break;
247                 }
248                 mark = hlist_entry(conn->list.first, struct fsnotify_mark,
249                                    obj_list);
250                 /*
251                  * We don't update i_fsnotify_mask / mnt_fsnotify_mask here
252                  * since inode / mount is going away anyway. So just remove
253                  * mark from the list.
254                  */
255                 hlist_del_init_rcu(&mark->obj_list);
256                 fsnotify_get_mark(mark);
257                 spin_unlock(lock);
258                 fsnotify_destroy_mark(mark, mark->group);
259                 fsnotify_put_mark(mark);
260         }
261 }
262
263 void fsnotify_connector_free(struct fsnotify_mark_connector **connp)
264 {
265         if (*connp) {
266                 kmem_cache_free(fsnotify_mark_connector_cachep, *connp);
267                 *connp = NULL;
268         }
269 }
270
271 void fsnotify_set_mark_mask_locked(struct fsnotify_mark *mark, __u32 mask)
272 {
273         assert_spin_locked(&mark->lock);
274
275         mark->mask = mask;
276 }
277
278 void fsnotify_set_mark_ignored_mask_locked(struct fsnotify_mark *mark, __u32 mask)
279 {
280         assert_spin_locked(&mark->lock);
281
282         mark->ignored_mask = mask;
283 }
284
285 /*
286  * Sorting function for lists of fsnotify marks.
287  *
288  * Fanotify supports different notification classes (reflected as priority of
289  * notification group). Events shall be passed to notification groups in
290  * decreasing priority order. To achieve this marks in notification lists for
291  * inodes and vfsmounts are sorted so that priorities of corresponding groups
292  * are descending.
293  *
294  * Furthermore correct handling of the ignore mask requires processing inode
295  * and vfsmount marks of each group together. Using the group address as
296  * further sort criterion provides a unique sorting order and thus we can
297  * merge inode and vfsmount lists of marks in linear time and find groups
298  * present in both lists.
299  *
300  * A return value of 1 signifies that b has priority over a.
301  * A return value of 0 signifies that the two marks have to be handled together.
302  * A return value of -1 signifies that a has priority over b.
303  */
304 int fsnotify_compare_groups(struct fsnotify_group *a, struct fsnotify_group *b)
305 {
306         if (a == b)
307                 return 0;
308         if (!a)
309                 return 1;
310         if (!b)
311                 return -1;
312         if (a->priority < b->priority)
313                 return 1;
314         if (a->priority > b->priority)
315                 return -1;
316         if (a < b)
317                 return 1;
318         return -1;
319 }
320
321 static int fsnotify_attach_connector_to_object(
322                                         struct fsnotify_mark_connector **connp,
323                                         spinlock_t *lock,
324                                         struct inode *inode,
325                                         struct vfsmount *mnt)
326 {
327         struct fsnotify_mark_connector *conn;
328
329         conn = kmem_cache_alloc(fsnotify_mark_connector_cachep, GFP_KERNEL);
330         if (!conn)
331                 return -ENOMEM;
332         INIT_HLIST_HEAD(&conn->list);
333         if (inode) {
334                 conn->flags = FSNOTIFY_OBJ_TYPE_INODE;
335                 conn->inode = inode;
336         } else {
337                 conn->flags = FSNOTIFY_OBJ_TYPE_VFSMOUNT;
338                 conn->mnt = mnt;
339         }
340         /*
341          * Make sure 'conn' initialization is visible. Matches
342          * lockless_dereference() in fsnotify().
343          */
344         smp_wmb();
345         spin_lock(lock);
346         if (!*connp)
347                 *connp = conn;
348         else
349                 kmem_cache_free(fsnotify_mark_connector_cachep, conn);
350         spin_unlock(lock);
351
352         return 0;
353 }
354
355 /*
356  * Add mark into proper place in given list of marks. These marks may be used
357  * for the fsnotify backend to determine which event types should be delivered
358  * to which group and for which inodes. These marks are ordered according to
359  * priority, highest number first, and then by the group's location in memory.
360  */
361 static int fsnotify_add_mark_list(struct fsnotify_mark *mark,
362                                   struct inode *inode, struct vfsmount *mnt,
363                                   int allow_dups)
364 {
365         struct fsnotify_mark *lmark, *last = NULL;
366         struct fsnotify_mark_connector *conn;
367         struct fsnotify_mark_connector **connp;
368         spinlock_t *lock;
369         int cmp;
370         int err = 0;
371
372         if (WARN_ON(!inode && !mnt))
373                 return -EINVAL;
374         if (inode) {
375                 connp = &inode->i_fsnotify_marks;
376                 lock = &inode->i_lock;
377         } else {
378                 connp = &real_mount(mnt)->mnt_fsnotify_marks;
379                 lock = &mnt->mnt_root->d_lock;
380         }
381
382         if (!*connp) {
383                 err = fsnotify_attach_connector_to_object(connp, lock,
384                                                           inode, mnt);
385                 if (err)
386                         return err;
387         }
388         spin_lock(&mark->lock);
389         spin_lock(lock);
390         conn = *connp;
391
392         /* is mark the first mark? */
393         if (hlist_empty(&conn->list)) {
394                 hlist_add_head_rcu(&mark->obj_list, &conn->list);
395                 if (inode)
396                         __iget(inode);
397                 goto added;
398         }
399
400         /* should mark be in the middle of the current list? */
401         hlist_for_each_entry(lmark, &conn->list, obj_list) {
402                 last = lmark;
403
404                 if ((lmark->group == mark->group) && !allow_dups) {
405                         err = -EEXIST;
406                         goto out_err;
407                 }
408
409                 cmp = fsnotify_compare_groups(lmark->group, mark->group);
410                 if (cmp >= 0) {
411                         hlist_add_before_rcu(&mark->obj_list, &lmark->obj_list);
412                         goto added;
413                 }
414         }
415
416         BUG_ON(last == NULL);
417         /* mark should be the last entry.  last is the current last entry */
418         hlist_add_behind_rcu(&mark->obj_list, &last->obj_list);
419 added:
420         mark->connector = conn;
421 out_err:
422         spin_unlock(lock);
423         spin_unlock(&mark->lock);
424         return err;
425 }
426
427 /*
428  * Attach an initialized mark to a given group and fs object.
429  * These marks may be used for the fsnotify backend to determine which
430  * event types should be delivered to which group.
431  */
432 int fsnotify_add_mark_locked(struct fsnotify_mark *mark,
433                              struct fsnotify_group *group, struct inode *inode,
434                              struct vfsmount *mnt, int allow_dups)
435 {
436         int ret = 0;
437
438         BUG_ON(inode && mnt);
439         BUG_ON(!inode && !mnt);
440         BUG_ON(!mutex_is_locked(&group->mark_mutex));
441
442         /*
443          * LOCKING ORDER!!!!
444          * group->mark_mutex
445          * mark->lock
446          * inode->i_lock
447          */
448         spin_lock(&mark->lock);
449         mark->flags |= FSNOTIFY_MARK_FLAG_ALIVE | FSNOTIFY_MARK_FLAG_ATTACHED;
450
451         fsnotify_get_group(group);
452         mark->group = group;
453         list_add(&mark->g_list, &group->marks_list);
454         atomic_inc(&group->num_marks);
455         fsnotify_get_mark(mark); /* for i_list and g_list */
456         spin_unlock(&mark->lock);
457
458         ret = fsnotify_add_mark_list(mark, inode, mnt, allow_dups);
459         if (ret)
460                 goto err;
461
462         if (inode)
463                 fsnotify_recalc_inode_mask(inode);
464         else
465                 fsnotify_recalc_vfsmount_mask(mnt);
466
467         return ret;
468 err:
469         mark->flags &= ~FSNOTIFY_MARK_FLAG_ALIVE;
470         list_del_init(&mark->g_list);
471         fsnotify_put_group(group);
472         mark->group = NULL;
473         atomic_dec(&group->num_marks);
474
475         spin_unlock(&mark->lock);
476
477         spin_lock(&destroy_lock);
478         list_add(&mark->g_list, &destroy_list);
479         spin_unlock(&destroy_lock);
480         queue_delayed_work(system_unbound_wq, &reaper_work,
481                                 FSNOTIFY_REAPER_DELAY);
482
483         return ret;
484 }
485
486 int fsnotify_add_mark(struct fsnotify_mark *mark, struct fsnotify_group *group,
487                       struct inode *inode, struct vfsmount *mnt, int allow_dups)
488 {
489         int ret;
490         mutex_lock(&group->mark_mutex);
491         ret = fsnotify_add_mark_locked(mark, group, inode, mnt, allow_dups);
492         mutex_unlock(&group->mark_mutex);
493         return ret;
494 }
495
496 /*
497  * Given a list of marks, find the mark associated with given group. If found
498  * take a reference to that mark and return it, else return NULL.
499  */
500 struct fsnotify_mark *fsnotify_find_mark(struct fsnotify_mark_connector *conn,
501                                          struct fsnotify_group *group)
502 {
503         struct fsnotify_mark *mark;
504
505         if (!conn)
506                 return NULL;
507
508         hlist_for_each_entry(mark, &conn->list, obj_list) {
509                 if (mark->group == group) {
510                         fsnotify_get_mark(mark);
511                         return mark;
512                 }
513         }
514         return NULL;
515 }
516
517 /*
518  * clear any marks in a group in which mark->flags & flags is true
519  */
520 void fsnotify_clear_marks_by_group_flags(struct fsnotify_group *group,
521                                          unsigned int flags)
522 {
523         struct fsnotify_mark *lmark, *mark;
524         LIST_HEAD(to_free);
525
526         /*
527          * We have to be really careful here. Anytime we drop mark_mutex, e.g.
528          * fsnotify_clear_marks_by_inode() can come and free marks. Even in our
529          * to_free list so we have to use mark_mutex even when accessing that
530          * list. And freeing mark requires us to drop mark_mutex. So we can
531          * reliably free only the first mark in the list. That's why we first
532          * move marks to free to to_free list in one go and then free marks in
533          * to_free list one by one.
534          */
535         mutex_lock_nested(&group->mark_mutex, SINGLE_DEPTH_NESTING);
536         list_for_each_entry_safe(mark, lmark, &group->marks_list, g_list) {
537                 if (mark->connector->flags & flags)
538                         list_move(&mark->g_list, &to_free);
539         }
540         mutex_unlock(&group->mark_mutex);
541
542         while (1) {
543                 mutex_lock_nested(&group->mark_mutex, SINGLE_DEPTH_NESTING);
544                 if (list_empty(&to_free)) {
545                         mutex_unlock(&group->mark_mutex);
546                         break;
547                 }
548                 mark = list_first_entry(&to_free, struct fsnotify_mark, g_list);
549                 fsnotify_get_mark(mark);
550                 fsnotify_detach_mark(mark);
551                 mutex_unlock(&group->mark_mutex);
552                 fsnotify_free_mark(mark);
553                 fsnotify_put_mark(mark);
554         }
555 }
556
557 /*
558  * Given a group, prepare for freeing all the marks associated with that group.
559  * The marks are attached to the list of marks prepared for destruction, the
560  * caller is responsible for freeing marks in that list after SRCU period has
561  * ended.
562  */
563 void fsnotify_detach_group_marks(struct fsnotify_group *group)
564 {
565         struct fsnotify_mark *mark;
566
567         while (1) {
568                 mutex_lock_nested(&group->mark_mutex, SINGLE_DEPTH_NESTING);
569                 if (list_empty(&group->marks_list)) {
570                         mutex_unlock(&group->mark_mutex);
571                         break;
572                 }
573                 mark = list_first_entry(&group->marks_list,
574                                         struct fsnotify_mark, g_list);
575                 fsnotify_get_mark(mark);
576                 fsnotify_detach_mark(mark);
577                 mutex_unlock(&group->mark_mutex);
578                 __fsnotify_free_mark(mark);
579                 fsnotify_put_mark(mark);
580         }
581 }
582
583 /*
584  * Nothing fancy, just initialize lists and locks and counters.
585  */
586 void fsnotify_init_mark(struct fsnotify_mark *mark,
587                         void (*free_mark)(struct fsnotify_mark *mark))
588 {
589         memset(mark, 0, sizeof(*mark));
590         spin_lock_init(&mark->lock);
591         atomic_set(&mark->refcnt, 1);
592         mark->free_mark = free_mark;
593 }
594
595 /*
596  * Destroy all marks in destroy_list, waits for SRCU period to finish before
597  * actually freeing marks.
598  */
599 void fsnotify_mark_destroy_list(void)
600 {
601         struct fsnotify_mark *mark, *next;
602         struct list_head private_destroy_list;
603
604         spin_lock(&destroy_lock);
605         /* exchange the list head */
606         list_replace_init(&destroy_list, &private_destroy_list);
607         spin_unlock(&destroy_lock);
608
609         synchronize_srcu(&fsnotify_mark_srcu);
610
611         list_for_each_entry_safe(mark, next, &private_destroy_list, g_list) {
612                 list_del_init(&mark->g_list);
613                 fsnotify_put_mark(mark);
614         }
615 }
616
617 static void fsnotify_mark_destroy_workfn(struct work_struct *work)
618 {
619         fsnotify_mark_destroy_list();
620 }