split the slow part of lock_parent() off
[muen/linux.git] / fs / dcache.c
1 /*
2  * fs/dcache.c
3  *
4  * Complete reimplementation
5  * (C) 1997 Thomas Schoebel-Theuer,
6  * with heavy changes by Linus Torvalds
7  */
8
9 /*
10  * Notes on the allocation strategy:
11  *
12  * The dcache is a master of the icache - whenever a dcache entry
13  * exists, the inode will always exist. "iput()" is done either when
14  * the dcache entry is deleted or garbage collected.
15  */
16
17 #include <linux/syscalls.h>
18 #include <linux/string.h>
19 #include <linux/mm.h>
20 #include <linux/fs.h>
21 #include <linux/fsnotify.h>
22 #include <linux/slab.h>
23 #include <linux/init.h>
24 #include <linux/hash.h>
25 #include <linux/cache.h>
26 #include <linux/export.h>
27 #include <linux/mount.h>
28 #include <linux/file.h>
29 #include <linux/uaccess.h>
30 #include <linux/security.h>
31 #include <linux/seqlock.h>
32 #include <linux/swap.h>
33 #include <linux/bootmem.h>
34 #include <linux/fs_struct.h>
35 #include <linux/bit_spinlock.h>
36 #include <linux/rculist_bl.h>
37 #include <linux/prefetch.h>
38 #include <linux/ratelimit.h>
39 #include <linux/list_lru.h>
40 #include "internal.h"
41 #include "mount.h"
42
43 /*
44  * Usage:
45  * dcache->d_inode->i_lock protects:
46  *   - i_dentry, d_u.d_alias, d_inode of aliases
47  * dcache_hash_bucket lock protects:
48  *   - the dcache hash table
49  * s_roots bl list spinlock protects:
50  *   - the s_roots list (see __d_drop)
51  * dentry->d_sb->s_dentry_lru_lock protects:
52  *   - the dcache lru lists and counters
53  * d_lock protects:
54  *   - d_flags
55  *   - d_name
56  *   - d_lru
57  *   - d_count
58  *   - d_unhashed()
59  *   - d_parent and d_subdirs
60  *   - childrens' d_child and d_parent
61  *   - d_u.d_alias, d_inode
62  *
63  * Ordering:
64  * dentry->d_inode->i_lock
65  *   dentry->d_lock
66  *     dentry->d_sb->s_dentry_lru_lock
67  *     dcache_hash_bucket lock
68  *     s_roots lock
69  *
70  * If there is an ancestor relationship:
71  * dentry->d_parent->...->d_parent->d_lock
72  *   ...
73  *     dentry->d_parent->d_lock
74  *       dentry->d_lock
75  *
76  * If no ancestor relationship:
77  * if (dentry1 < dentry2)
78  *   dentry1->d_lock
79  *     dentry2->d_lock
80  */
81 int sysctl_vfs_cache_pressure __read_mostly = 100;
82 EXPORT_SYMBOL_GPL(sysctl_vfs_cache_pressure);
83
84 __cacheline_aligned_in_smp DEFINE_SEQLOCK(rename_lock);
85
86 EXPORT_SYMBOL(rename_lock);
87
88 static struct kmem_cache *dentry_cache __read_mostly;
89
90 const struct qstr empty_name = QSTR_INIT("", 0);
91 EXPORT_SYMBOL(empty_name);
92 const struct qstr slash_name = QSTR_INIT("/", 1);
93 EXPORT_SYMBOL(slash_name);
94
95 /*
96  * This is the single most critical data structure when it comes
97  * to the dcache: the hashtable for lookups. Somebody should try
98  * to make this good - I've just made it work.
99  *
100  * This hash-function tries to avoid losing too many bits of hash
101  * information, yet avoid using a prime hash-size or similar.
102  */
103
104 static unsigned int d_hash_shift __read_mostly;
105
106 static struct hlist_bl_head *dentry_hashtable __read_mostly;
107
108 static inline struct hlist_bl_head *d_hash(unsigned int hash)
109 {
110         return dentry_hashtable + (hash >> d_hash_shift);
111 }
112
113 #define IN_LOOKUP_SHIFT 10
114 static struct hlist_bl_head in_lookup_hashtable[1 << IN_LOOKUP_SHIFT];
115
116 static inline struct hlist_bl_head *in_lookup_hash(const struct dentry *parent,
117                                         unsigned int hash)
118 {
119         hash += (unsigned long) parent / L1_CACHE_BYTES;
120         return in_lookup_hashtable + hash_32(hash, IN_LOOKUP_SHIFT);
121 }
122
123
124 /* Statistics gathering. */
125 struct dentry_stat_t dentry_stat = {
126         .age_limit = 45,
127 };
128
129 static DEFINE_PER_CPU(long, nr_dentry);
130 static DEFINE_PER_CPU(long, nr_dentry_unused);
131
132 #if defined(CONFIG_SYSCTL) && defined(CONFIG_PROC_FS)
133
134 /*
135  * Here we resort to our own counters instead of using generic per-cpu counters
136  * for consistency with what the vfs inode code does. We are expected to harvest
137  * better code and performance by having our own specialized counters.
138  *
139  * Please note that the loop is done over all possible CPUs, not over all online
140  * CPUs. The reason for this is that we don't want to play games with CPUs going
141  * on and off. If one of them goes off, we will just keep their counters.
142  *
143  * glommer: See cffbc8a for details, and if you ever intend to change this,
144  * please update all vfs counters to match.
145  */
146 static long get_nr_dentry(void)
147 {
148         int i;
149         long sum = 0;
150         for_each_possible_cpu(i)
151                 sum += per_cpu(nr_dentry, i);
152         return sum < 0 ? 0 : sum;
153 }
154
155 static long get_nr_dentry_unused(void)
156 {
157         int i;
158         long sum = 0;
159         for_each_possible_cpu(i)
160                 sum += per_cpu(nr_dentry_unused, i);
161         return sum < 0 ? 0 : sum;
162 }
163
164 int proc_nr_dentry(struct ctl_table *table, int write, void __user *buffer,
165                    size_t *lenp, loff_t *ppos)
166 {
167         dentry_stat.nr_dentry = get_nr_dentry();
168         dentry_stat.nr_unused = get_nr_dentry_unused();
169         return proc_doulongvec_minmax(table, write, buffer, lenp, ppos);
170 }
171 #endif
172
173 /*
174  * Compare 2 name strings, return 0 if they match, otherwise non-zero.
175  * The strings are both count bytes long, and count is non-zero.
176  */
177 #ifdef CONFIG_DCACHE_WORD_ACCESS
178
179 #include <asm/word-at-a-time.h>
180 /*
181  * NOTE! 'cs' and 'scount' come from a dentry, so it has a
182  * aligned allocation for this particular component. We don't
183  * strictly need the load_unaligned_zeropad() safety, but it
184  * doesn't hurt either.
185  *
186  * In contrast, 'ct' and 'tcount' can be from a pathname, and do
187  * need the careful unaligned handling.
188  */
189 static inline int dentry_string_cmp(const unsigned char *cs, const unsigned char *ct, unsigned tcount)
190 {
191         unsigned long a,b,mask;
192
193         for (;;) {
194                 a = read_word_at_a_time(cs);
195                 b = load_unaligned_zeropad(ct);
196                 if (tcount < sizeof(unsigned long))
197                         break;
198                 if (unlikely(a != b))
199                         return 1;
200                 cs += sizeof(unsigned long);
201                 ct += sizeof(unsigned long);
202                 tcount -= sizeof(unsigned long);
203                 if (!tcount)
204                         return 0;
205         }
206         mask = bytemask_from_count(tcount);
207         return unlikely(!!((a ^ b) & mask));
208 }
209
210 #else
211
212 static inline int dentry_string_cmp(const unsigned char *cs, const unsigned char *ct, unsigned tcount)
213 {
214         do {
215                 if (*cs != *ct)
216                         return 1;
217                 cs++;
218                 ct++;
219                 tcount--;
220         } while (tcount);
221         return 0;
222 }
223
224 #endif
225
226 static inline int dentry_cmp(const struct dentry *dentry, const unsigned char *ct, unsigned tcount)
227 {
228         /*
229          * Be careful about RCU walk racing with rename:
230          * use 'READ_ONCE' to fetch the name pointer.
231          *
232          * NOTE! Even if a rename will mean that the length
233          * was not loaded atomically, we don't care. The
234          * RCU walk will check the sequence count eventually,
235          * and catch it. And we won't overrun the buffer,
236          * because we're reading the name pointer atomically,
237          * and a dentry name is guaranteed to be properly
238          * terminated with a NUL byte.
239          *
240          * End result: even if 'len' is wrong, we'll exit
241          * early because the data cannot match (there can
242          * be no NUL in the ct/tcount data)
243          */
244         const unsigned char *cs = READ_ONCE(dentry->d_name.name);
245
246         return dentry_string_cmp(cs, ct, tcount);
247 }
248
249 struct external_name {
250         union {
251                 atomic_t count;
252                 struct rcu_head head;
253         } u;
254         unsigned char name[];
255 };
256
257 static inline struct external_name *external_name(struct dentry *dentry)
258 {
259         return container_of(dentry->d_name.name, struct external_name, name[0]);
260 }
261
262 static void __d_free(struct rcu_head *head)
263 {
264         struct dentry *dentry = container_of(head, struct dentry, d_u.d_rcu);
265
266         kmem_cache_free(dentry_cache, dentry); 
267 }
268
269 static void __d_free_external(struct rcu_head *head)
270 {
271         struct dentry *dentry = container_of(head, struct dentry, d_u.d_rcu);
272         kfree(external_name(dentry));
273         kmem_cache_free(dentry_cache, dentry); 
274 }
275
276 static inline int dname_external(const struct dentry *dentry)
277 {
278         return dentry->d_name.name != dentry->d_iname;
279 }
280
281 void take_dentry_name_snapshot(struct name_snapshot *name, struct dentry *dentry)
282 {
283         spin_lock(&dentry->d_lock);
284         if (unlikely(dname_external(dentry))) {
285                 struct external_name *p = external_name(dentry);
286                 atomic_inc(&p->u.count);
287                 spin_unlock(&dentry->d_lock);
288                 name->name = p->name;
289         } else {
290                 memcpy(name->inline_name, dentry->d_iname, DNAME_INLINE_LEN);
291                 spin_unlock(&dentry->d_lock);
292                 name->name = name->inline_name;
293         }
294 }
295 EXPORT_SYMBOL(take_dentry_name_snapshot);
296
297 void release_dentry_name_snapshot(struct name_snapshot *name)
298 {
299         if (unlikely(name->name != name->inline_name)) {
300                 struct external_name *p;
301                 p = container_of(name->name, struct external_name, name[0]);
302                 if (unlikely(atomic_dec_and_test(&p->u.count)))
303                         kfree_rcu(p, u.head);
304         }
305 }
306 EXPORT_SYMBOL(release_dentry_name_snapshot);
307
308 static inline void __d_set_inode_and_type(struct dentry *dentry,
309                                           struct inode *inode,
310                                           unsigned type_flags)
311 {
312         unsigned flags;
313
314         dentry->d_inode = inode;
315         flags = READ_ONCE(dentry->d_flags);
316         flags &= ~(DCACHE_ENTRY_TYPE | DCACHE_FALLTHRU);
317         flags |= type_flags;
318         WRITE_ONCE(dentry->d_flags, flags);
319 }
320
321 static inline void __d_clear_type_and_inode(struct dentry *dentry)
322 {
323         unsigned flags = READ_ONCE(dentry->d_flags);
324
325         flags &= ~(DCACHE_ENTRY_TYPE | DCACHE_FALLTHRU);
326         WRITE_ONCE(dentry->d_flags, flags);
327         dentry->d_inode = NULL;
328 }
329
330 static void dentry_free(struct dentry *dentry)
331 {
332         WARN_ON(!hlist_unhashed(&dentry->d_u.d_alias));
333         if (unlikely(dname_external(dentry))) {
334                 struct external_name *p = external_name(dentry);
335                 if (likely(atomic_dec_and_test(&p->u.count))) {
336                         call_rcu(&dentry->d_u.d_rcu, __d_free_external);
337                         return;
338                 }
339         }
340         /* if dentry was never visible to RCU, immediate free is OK */
341         if (!(dentry->d_flags & DCACHE_RCUACCESS))
342                 __d_free(&dentry->d_u.d_rcu);
343         else
344                 call_rcu(&dentry->d_u.d_rcu, __d_free);
345 }
346
347 /*
348  * Release the dentry's inode, using the filesystem
349  * d_iput() operation if defined.
350  */
351 static void dentry_unlink_inode(struct dentry * dentry)
352         __releases(dentry->d_lock)
353         __releases(dentry->d_inode->i_lock)
354 {
355         struct inode *inode = dentry->d_inode;
356         bool hashed = !d_unhashed(dentry);
357
358         if (hashed)
359                 raw_write_seqcount_begin(&dentry->d_seq);
360         __d_clear_type_and_inode(dentry);
361         hlist_del_init(&dentry->d_u.d_alias);
362         if (hashed)
363                 raw_write_seqcount_end(&dentry->d_seq);
364         spin_unlock(&dentry->d_lock);
365         spin_unlock(&inode->i_lock);
366         if (!inode->i_nlink)
367                 fsnotify_inoderemove(inode);
368         if (dentry->d_op && dentry->d_op->d_iput)
369                 dentry->d_op->d_iput(dentry, inode);
370         else
371                 iput(inode);
372 }
373
374 /*
375  * The DCACHE_LRU_LIST bit is set whenever the 'd_lru' entry
376  * is in use - which includes both the "real" per-superblock
377  * LRU list _and_ the DCACHE_SHRINK_LIST use.
378  *
379  * The DCACHE_SHRINK_LIST bit is set whenever the dentry is
380  * on the shrink list (ie not on the superblock LRU list).
381  *
382  * The per-cpu "nr_dentry_unused" counters are updated with
383  * the DCACHE_LRU_LIST bit.
384  *
385  * These helper functions make sure we always follow the
386  * rules. d_lock must be held by the caller.
387  */
388 #define D_FLAG_VERIFY(dentry,x) WARN_ON_ONCE(((dentry)->d_flags & (DCACHE_LRU_LIST | DCACHE_SHRINK_LIST)) != (x))
389 static void d_lru_add(struct dentry *dentry)
390 {
391         D_FLAG_VERIFY(dentry, 0);
392         dentry->d_flags |= DCACHE_LRU_LIST;
393         this_cpu_inc(nr_dentry_unused);
394         WARN_ON_ONCE(!list_lru_add(&dentry->d_sb->s_dentry_lru, &dentry->d_lru));
395 }
396
397 static void d_lru_del(struct dentry *dentry)
398 {
399         D_FLAG_VERIFY(dentry, DCACHE_LRU_LIST);
400         dentry->d_flags &= ~DCACHE_LRU_LIST;
401         this_cpu_dec(nr_dentry_unused);
402         WARN_ON_ONCE(!list_lru_del(&dentry->d_sb->s_dentry_lru, &dentry->d_lru));
403 }
404
405 static void d_shrink_del(struct dentry *dentry)
406 {
407         D_FLAG_VERIFY(dentry, DCACHE_SHRINK_LIST | DCACHE_LRU_LIST);
408         list_del_init(&dentry->d_lru);
409         dentry->d_flags &= ~(DCACHE_SHRINK_LIST | DCACHE_LRU_LIST);
410         this_cpu_dec(nr_dentry_unused);
411 }
412
413 static void d_shrink_add(struct dentry *dentry, struct list_head *list)
414 {
415         D_FLAG_VERIFY(dentry, 0);
416         list_add(&dentry->d_lru, list);
417         dentry->d_flags |= DCACHE_SHRINK_LIST | DCACHE_LRU_LIST;
418         this_cpu_inc(nr_dentry_unused);
419 }
420
421 /*
422  * These can only be called under the global LRU lock, ie during the
423  * callback for freeing the LRU list. "isolate" removes it from the
424  * LRU lists entirely, while shrink_move moves it to the indicated
425  * private list.
426  */
427 static void d_lru_isolate(struct list_lru_one *lru, struct dentry *dentry)
428 {
429         D_FLAG_VERIFY(dentry, DCACHE_LRU_LIST);
430         dentry->d_flags &= ~DCACHE_LRU_LIST;
431         this_cpu_dec(nr_dentry_unused);
432         list_lru_isolate(lru, &dentry->d_lru);
433 }
434
435 static void d_lru_shrink_move(struct list_lru_one *lru, struct dentry *dentry,
436                               struct list_head *list)
437 {
438         D_FLAG_VERIFY(dentry, DCACHE_LRU_LIST);
439         dentry->d_flags |= DCACHE_SHRINK_LIST;
440         list_lru_isolate_move(lru, &dentry->d_lru, list);
441 }
442
443 /*
444  * dentry_lru_(add|del)_list) must be called with d_lock held.
445  */
446 static void dentry_lru_add(struct dentry *dentry)
447 {
448         if (unlikely(!(dentry->d_flags & DCACHE_LRU_LIST)))
449                 d_lru_add(dentry);
450         else if (unlikely(!(dentry->d_flags & DCACHE_REFERENCED)))
451                 dentry->d_flags |= DCACHE_REFERENCED;
452 }
453
454 /**
455  * d_drop - drop a dentry
456  * @dentry: dentry to drop
457  *
458  * d_drop() unhashes the entry from the parent dentry hashes, so that it won't
459  * be found through a VFS lookup any more. Note that this is different from
460  * deleting the dentry - d_delete will try to mark the dentry negative if
461  * possible, giving a successful _negative_ lookup, while d_drop will
462  * just make the cache lookup fail.
463  *
464  * d_drop() is used mainly for stuff that wants to invalidate a dentry for some
465  * reason (NFS timeouts or autofs deletes).
466  *
467  * __d_drop requires dentry->d_lock
468  * ___d_drop doesn't mark dentry as "unhashed"
469  *   (dentry->d_hash.pprev will be LIST_POISON2, not NULL).
470  */
471 static void ___d_drop(struct dentry *dentry)
472 {
473         struct hlist_bl_head *b;
474         /*
475          * Hashed dentries are normally on the dentry hashtable,
476          * with the exception of those newly allocated by
477          * d_obtain_root, which are always IS_ROOT:
478          */
479         if (unlikely(IS_ROOT(dentry)))
480                 b = &dentry->d_sb->s_roots;
481         else
482                 b = d_hash(dentry->d_name.hash);
483
484         hlist_bl_lock(b);
485         __hlist_bl_del(&dentry->d_hash);
486         hlist_bl_unlock(b);
487 }
488
489 void __d_drop(struct dentry *dentry)
490 {
491         if (!d_unhashed(dentry)) {
492                 ___d_drop(dentry);
493                 dentry->d_hash.pprev = NULL;
494                 write_seqcount_invalidate(&dentry->d_seq);
495         }
496 }
497 EXPORT_SYMBOL(__d_drop);
498
499 void d_drop(struct dentry *dentry)
500 {
501         spin_lock(&dentry->d_lock);
502         __d_drop(dentry);
503         spin_unlock(&dentry->d_lock);
504 }
505 EXPORT_SYMBOL(d_drop);
506
507 static inline void dentry_unlist(struct dentry *dentry, struct dentry *parent)
508 {
509         struct dentry *next;
510         /*
511          * Inform d_walk() and shrink_dentry_list() that we are no longer
512          * attached to the dentry tree
513          */
514         dentry->d_flags |= DCACHE_DENTRY_KILLED;
515         if (unlikely(list_empty(&dentry->d_child)))
516                 return;
517         __list_del_entry(&dentry->d_child);
518         /*
519          * Cursors can move around the list of children.  While we'd been
520          * a normal list member, it didn't matter - ->d_child.next would've
521          * been updated.  However, from now on it won't be and for the
522          * things like d_walk() it might end up with a nasty surprise.
523          * Normally d_walk() doesn't care about cursors moving around -
524          * ->d_lock on parent prevents that and since a cursor has no children
525          * of its own, we get through it without ever unlocking the parent.
526          * There is one exception, though - if we ascend from a child that
527          * gets killed as soon as we unlock it, the next sibling is found
528          * using the value left in its ->d_child.next.  And if _that_
529          * pointed to a cursor, and cursor got moved (e.g. by lseek())
530          * before d_walk() regains parent->d_lock, we'll end up skipping
531          * everything the cursor had been moved past.
532          *
533          * Solution: make sure that the pointer left behind in ->d_child.next
534          * points to something that won't be moving around.  I.e. skip the
535          * cursors.
536          */
537         while (dentry->d_child.next != &parent->d_subdirs) {
538                 next = list_entry(dentry->d_child.next, struct dentry, d_child);
539                 if (likely(!(next->d_flags & DCACHE_DENTRY_CURSOR)))
540                         break;
541                 dentry->d_child.next = next->d_child.next;
542         }
543 }
544
545 static void __dentry_kill(struct dentry *dentry)
546 {
547         struct dentry *parent = NULL;
548         bool can_free = true;
549         if (!IS_ROOT(dentry))
550                 parent = dentry->d_parent;
551
552         /*
553          * The dentry is now unrecoverably dead to the world.
554          */
555         lockref_mark_dead(&dentry->d_lockref);
556
557         /*
558          * inform the fs via d_prune that this dentry is about to be
559          * unhashed and destroyed.
560          */
561         if (dentry->d_flags & DCACHE_OP_PRUNE)
562                 dentry->d_op->d_prune(dentry);
563
564         if (dentry->d_flags & DCACHE_LRU_LIST) {
565                 if (!(dentry->d_flags & DCACHE_SHRINK_LIST))
566                         d_lru_del(dentry);
567         }
568         /* if it was on the hash then remove it */
569         __d_drop(dentry);
570         dentry_unlist(dentry, parent);
571         if (parent)
572                 spin_unlock(&parent->d_lock);
573         if (dentry->d_inode)
574                 dentry_unlink_inode(dentry);
575         else
576                 spin_unlock(&dentry->d_lock);
577         this_cpu_dec(nr_dentry);
578         if (dentry->d_op && dentry->d_op->d_release)
579                 dentry->d_op->d_release(dentry);
580
581         spin_lock(&dentry->d_lock);
582         if (dentry->d_flags & DCACHE_SHRINK_LIST) {
583                 dentry->d_flags |= DCACHE_MAY_FREE;
584                 can_free = false;
585         }
586         spin_unlock(&dentry->d_lock);
587         if (likely(can_free))
588                 dentry_free(dentry);
589 }
590
591 static struct dentry *__lock_parent(struct dentry *dentry)
592 {
593         struct dentry *parent;
594         rcu_read_lock();
595         spin_unlock(&dentry->d_lock);
596 again:
597         parent = READ_ONCE(dentry->d_parent);
598         spin_lock(&parent->d_lock);
599         /*
600          * We can't blindly lock dentry until we are sure
601          * that we won't violate the locking order.
602          * Any changes of dentry->d_parent must have
603          * been done with parent->d_lock held, so
604          * spin_lock() above is enough of a barrier
605          * for checking if it's still our child.
606          */
607         if (unlikely(parent != dentry->d_parent)) {
608                 spin_unlock(&parent->d_lock);
609                 goto again;
610         }
611         rcu_read_unlock();
612         if (parent != dentry)
613                 spin_lock_nested(&dentry->d_lock, DENTRY_D_LOCK_NESTED);
614         else
615                 parent = NULL;
616         return parent;
617 }
618
619 static inline struct dentry *lock_parent(struct dentry *dentry)
620 {
621         struct dentry *parent = dentry->d_parent;
622         if (IS_ROOT(dentry))
623                 return NULL;
624         if (likely(spin_trylock(&parent->d_lock)))
625                 return parent;
626         return __lock_parent(dentry);
627 }
628
629 /*
630  * Finish off a dentry we've decided to kill.
631  * dentry->d_lock must be held, returns with it unlocked.
632  * Returns dentry requiring refcount drop, or NULL if we're done.
633  */
634 static struct dentry *dentry_kill(struct dentry *dentry)
635         __releases(dentry->d_lock)
636 {
637         struct inode *inode = dentry->d_inode;
638         struct dentry *parent = NULL;
639
640         if (inode && unlikely(!spin_trylock(&inode->i_lock)))
641                 goto failed;
642
643         if (!IS_ROOT(dentry)) {
644                 parent = dentry->d_parent;
645                 if (unlikely(!spin_trylock(&parent->d_lock))) {
646                         if (inode)
647                                 spin_unlock(&inode->i_lock);
648                         goto failed;
649                 }
650         }
651
652         __dentry_kill(dentry);
653         return parent;
654
655 failed:
656         spin_unlock(&dentry->d_lock);
657         return dentry; /* try again with same dentry */
658 }
659
660 /*
661  * Try to do a lockless dput(), and return whether that was successful.
662  *
663  * If unsuccessful, we return false, having already taken the dentry lock.
664  *
665  * The caller needs to hold the RCU read lock, so that the dentry is
666  * guaranteed to stay around even if the refcount goes down to zero!
667  */
668 static inline bool fast_dput(struct dentry *dentry)
669 {
670         int ret;
671         unsigned int d_flags;
672
673         /*
674          * If we have a d_op->d_delete() operation, we sould not
675          * let the dentry count go to zero, so use "put_or_lock".
676          */
677         if (unlikely(dentry->d_flags & DCACHE_OP_DELETE))
678                 return lockref_put_or_lock(&dentry->d_lockref);
679
680         /*
681          * .. otherwise, we can try to just decrement the
682          * lockref optimistically.
683          */
684         ret = lockref_put_return(&dentry->d_lockref);
685
686         /*
687          * If the lockref_put_return() failed due to the lock being held
688          * by somebody else, the fast path has failed. We will need to
689          * get the lock, and then check the count again.
690          */
691         if (unlikely(ret < 0)) {
692                 spin_lock(&dentry->d_lock);
693                 if (dentry->d_lockref.count > 1) {
694                         dentry->d_lockref.count--;
695                         spin_unlock(&dentry->d_lock);
696                         return 1;
697                 }
698                 return 0;
699         }
700
701         /*
702          * If we weren't the last ref, we're done.
703          */
704         if (ret)
705                 return 1;
706
707         /*
708          * Careful, careful. The reference count went down
709          * to zero, but we don't hold the dentry lock, so
710          * somebody else could get it again, and do another
711          * dput(), and we need to not race with that.
712          *
713          * However, there is a very special and common case
714          * where we don't care, because there is nothing to
715          * do: the dentry is still hashed, it does not have
716          * a 'delete' op, and it's referenced and already on
717          * the LRU list.
718          *
719          * NOTE! Since we aren't locked, these values are
720          * not "stable". However, it is sufficient that at
721          * some point after we dropped the reference the
722          * dentry was hashed and the flags had the proper
723          * value. Other dentry users may have re-gotten
724          * a reference to the dentry and change that, but
725          * our work is done - we can leave the dentry
726          * around with a zero refcount.
727          */
728         smp_rmb();
729         d_flags = READ_ONCE(dentry->d_flags);
730         d_flags &= DCACHE_REFERENCED | DCACHE_LRU_LIST | DCACHE_DISCONNECTED;
731
732         /* Nothing to do? Dropping the reference was all we needed? */
733         if (d_flags == (DCACHE_REFERENCED | DCACHE_LRU_LIST) && !d_unhashed(dentry))
734                 return 1;
735
736         /*
737          * Not the fast normal case? Get the lock. We've already decremented
738          * the refcount, but we'll need to re-check the situation after
739          * getting the lock.
740          */
741         spin_lock(&dentry->d_lock);
742
743         /*
744          * Did somebody else grab a reference to it in the meantime, and
745          * we're no longer the last user after all? Alternatively, somebody
746          * else could have killed it and marked it dead. Either way, we
747          * don't need to do anything else.
748          */
749         if (dentry->d_lockref.count) {
750                 spin_unlock(&dentry->d_lock);
751                 return 1;
752         }
753
754         /*
755          * Re-get the reference we optimistically dropped. We hold the
756          * lock, and we just tested that it was zero, so we can just
757          * set it to 1.
758          */
759         dentry->d_lockref.count = 1;
760         return 0;
761 }
762
763
764 /* 
765  * This is dput
766  *
767  * This is complicated by the fact that we do not want to put
768  * dentries that are no longer on any hash chain on the unused
769  * list: we'd much rather just get rid of them immediately.
770  *
771  * However, that implies that we have to traverse the dentry
772  * tree upwards to the parents which might _also_ now be
773  * scheduled for deletion (it may have been only waiting for
774  * its last child to go away).
775  *
776  * This tail recursion is done by hand as we don't want to depend
777  * on the compiler to always get this right (gcc generally doesn't).
778  * Real recursion would eat up our stack space.
779  */
780
781 /*
782  * dput - release a dentry
783  * @dentry: dentry to release 
784  *
785  * Release a dentry. This will drop the usage count and if appropriate
786  * call the dentry unlink method as well as removing it from the queues and
787  * releasing its resources. If the parent dentries were scheduled for release
788  * they too may now get deleted.
789  */
790 void dput(struct dentry *dentry)
791 {
792         if (unlikely(!dentry))
793                 return;
794
795 repeat:
796         might_sleep();
797
798         rcu_read_lock();
799         if (likely(fast_dput(dentry))) {
800                 rcu_read_unlock();
801                 return;
802         }
803
804         /* Slow case: now with the dentry lock held */
805         rcu_read_unlock();
806
807         WARN_ON(d_in_lookup(dentry));
808
809         /* Unreachable? Get rid of it */
810         if (unlikely(d_unhashed(dentry)))
811                 goto kill_it;
812
813         if (unlikely(dentry->d_flags & DCACHE_DISCONNECTED))
814                 goto kill_it;
815
816         if (unlikely(dentry->d_flags & DCACHE_OP_DELETE)) {
817                 if (dentry->d_op->d_delete(dentry))
818                         goto kill_it;
819         }
820
821         dentry_lru_add(dentry);
822
823         dentry->d_lockref.count--;
824         spin_unlock(&dentry->d_lock);
825         return;
826
827 kill_it:
828         dentry = dentry_kill(dentry);
829         if (dentry) {
830                 cond_resched();
831                 goto repeat;
832         }
833 }
834 EXPORT_SYMBOL(dput);
835
836
837 /* This must be called with d_lock held */
838 static inline void __dget_dlock(struct dentry *dentry)
839 {
840         dentry->d_lockref.count++;
841 }
842
843 static inline void __dget(struct dentry *dentry)
844 {
845         lockref_get(&dentry->d_lockref);
846 }
847
848 struct dentry *dget_parent(struct dentry *dentry)
849 {
850         int gotref;
851         struct dentry *ret;
852
853         /*
854          * Do optimistic parent lookup without any
855          * locking.
856          */
857         rcu_read_lock();
858         ret = READ_ONCE(dentry->d_parent);
859         gotref = lockref_get_not_zero(&ret->d_lockref);
860         rcu_read_unlock();
861         if (likely(gotref)) {
862                 if (likely(ret == READ_ONCE(dentry->d_parent)))
863                         return ret;
864                 dput(ret);
865         }
866
867 repeat:
868         /*
869          * Don't need rcu_dereference because we re-check it was correct under
870          * the lock.
871          */
872         rcu_read_lock();
873         ret = dentry->d_parent;
874         spin_lock(&ret->d_lock);
875         if (unlikely(ret != dentry->d_parent)) {
876                 spin_unlock(&ret->d_lock);
877                 rcu_read_unlock();
878                 goto repeat;
879         }
880         rcu_read_unlock();
881         BUG_ON(!ret->d_lockref.count);
882         ret->d_lockref.count++;
883         spin_unlock(&ret->d_lock);
884         return ret;
885 }
886 EXPORT_SYMBOL(dget_parent);
887
888 /**
889  * d_find_alias - grab a hashed alias of inode
890  * @inode: inode in question
891  *
892  * If inode has a hashed alias, or is a directory and has any alias,
893  * acquire the reference to alias and return it. Otherwise return NULL.
894  * Notice that if inode is a directory there can be only one alias and
895  * it can be unhashed only if it has no children, or if it is the root
896  * of a filesystem, or if the directory was renamed and d_revalidate
897  * was the first vfs operation to notice.
898  *
899  * If the inode has an IS_ROOT, DCACHE_DISCONNECTED alias, then prefer
900  * any other hashed alias over that one.
901  */
902 static struct dentry *__d_find_alias(struct inode *inode)
903 {
904         struct dentry *alias, *discon_alias;
905
906 again:
907         discon_alias = NULL;
908         hlist_for_each_entry(alias, &inode->i_dentry, d_u.d_alias) {
909                 spin_lock(&alias->d_lock);
910                 if (S_ISDIR(inode->i_mode) || !d_unhashed(alias)) {
911                         if (IS_ROOT(alias) &&
912                             (alias->d_flags & DCACHE_DISCONNECTED)) {
913                                 discon_alias = alias;
914                         } else {
915                                 __dget_dlock(alias);
916                                 spin_unlock(&alias->d_lock);
917                                 return alias;
918                         }
919                 }
920                 spin_unlock(&alias->d_lock);
921         }
922         if (discon_alias) {
923                 alias = discon_alias;
924                 spin_lock(&alias->d_lock);
925                 if (S_ISDIR(inode->i_mode) || !d_unhashed(alias)) {
926                         __dget_dlock(alias);
927                         spin_unlock(&alias->d_lock);
928                         return alias;
929                 }
930                 spin_unlock(&alias->d_lock);
931                 goto again;
932         }
933         return NULL;
934 }
935
936 struct dentry *d_find_alias(struct inode *inode)
937 {
938         struct dentry *de = NULL;
939
940         if (!hlist_empty(&inode->i_dentry)) {
941                 spin_lock(&inode->i_lock);
942                 de = __d_find_alias(inode);
943                 spin_unlock(&inode->i_lock);
944         }
945         return de;
946 }
947 EXPORT_SYMBOL(d_find_alias);
948
949 /*
950  *      Try to kill dentries associated with this inode.
951  * WARNING: you must own a reference to inode.
952  */
953 void d_prune_aliases(struct inode *inode)
954 {
955         struct dentry *dentry;
956 restart:
957         spin_lock(&inode->i_lock);
958         hlist_for_each_entry(dentry, &inode->i_dentry, d_u.d_alias) {
959                 spin_lock(&dentry->d_lock);
960                 if (!dentry->d_lockref.count) {
961                         struct dentry *parent = lock_parent(dentry);
962                         if (likely(!dentry->d_lockref.count)) {
963                                 __dentry_kill(dentry);
964                                 dput(parent);
965                                 goto restart;
966                         }
967                         if (parent)
968                                 spin_unlock(&parent->d_lock);
969                 }
970                 spin_unlock(&dentry->d_lock);
971         }
972         spin_unlock(&inode->i_lock);
973 }
974 EXPORT_SYMBOL(d_prune_aliases);
975
976 /*
977  * Lock a dentry from shrink list.
978  * Note that dentry is *not* protected from concurrent dentry_kill(),
979  * d_delete(), etc.  It is protected from freeing (by the fact of
980  * being on a shrink list), but everything else is fair game.
981  * Return false if dentry has been disrupted or grabbed, leaving
982  * the caller to kick it off-list.  Otherwise, return true and have
983  * that dentry's inode and parent both locked.
984  */
985 static bool shrink_lock_dentry(struct dentry *dentry)
986 {
987         struct inode *inode;
988         struct dentry *parent;
989
990         if (dentry->d_lockref.count)
991                 return false;
992
993         inode = dentry->d_inode;
994         if (inode && unlikely(!spin_trylock(&inode->i_lock))) {
995                 rcu_read_lock();        /* to protect inode */
996                 spin_unlock(&dentry->d_lock);
997                 spin_lock(&inode->i_lock);
998                 spin_lock(&dentry->d_lock);
999                 if (unlikely(dentry->d_lockref.count))
1000                         goto out;
1001                 /* changed inode means that somebody had grabbed it */
1002                 if (unlikely(inode != dentry->d_inode))
1003                         goto out;
1004                 rcu_read_unlock();
1005         }
1006
1007         parent = dentry->d_parent;
1008         if (IS_ROOT(dentry) || likely(spin_trylock(&parent->d_lock)))
1009                 return true;
1010
1011         rcu_read_lock();                /* to protect parent */
1012         spin_unlock(&dentry->d_lock);
1013         parent = READ_ONCE(dentry->d_parent);
1014         spin_lock(&parent->d_lock);
1015         if (unlikely(parent != dentry->d_parent)) {
1016                 spin_unlock(&parent->d_lock);
1017                 spin_lock(&dentry->d_lock);
1018                 goto out;
1019         }
1020         spin_lock_nested(&dentry->d_lock, DENTRY_D_LOCK_NESTED);
1021         if (likely(!dentry->d_lockref.count)) {
1022                 rcu_read_unlock();
1023                 return true;
1024         }
1025         spin_unlock(&parent->d_lock);
1026 out:
1027         if (inode)
1028                 spin_unlock(&inode->i_lock);
1029         rcu_read_unlock();
1030         return false;
1031 }
1032
1033 static void shrink_dentry_list(struct list_head *list)
1034 {
1035         while (!list_empty(list)) {
1036                 struct dentry *dentry, *parent;
1037                 struct inode *inode;
1038
1039                 dentry = list_entry(list->prev, struct dentry, d_lru);
1040                 spin_lock(&dentry->d_lock);
1041                 if (!shrink_lock_dentry(dentry)) {
1042                         bool can_free = false;
1043                         d_shrink_del(dentry);
1044                         if (dentry->d_lockref.count < 0)
1045                                 can_free = dentry->d_flags & DCACHE_MAY_FREE;
1046                         spin_unlock(&dentry->d_lock);
1047                         if (can_free)
1048                                 dentry_free(dentry);
1049                         continue;
1050                 }
1051                 d_shrink_del(dentry);
1052                 parent = dentry->d_parent;
1053                 __dentry_kill(dentry);
1054                 if (parent == dentry)
1055                         continue;
1056                 /*
1057                  * We need to prune ancestors too. This is necessary to prevent
1058                  * quadratic behavior of shrink_dcache_parent(), but is also
1059                  * expected to be beneficial in reducing dentry cache
1060                  * fragmentation.
1061                  */
1062                 dentry = parent;
1063                 while (dentry && !lockref_put_or_lock(&dentry->d_lockref)) {
1064                         parent = lock_parent(dentry);
1065                         if (dentry->d_lockref.count != 1) {
1066                                 dentry->d_lockref.count--;
1067                                 spin_unlock(&dentry->d_lock);
1068                                 if (parent)
1069                                         spin_unlock(&parent->d_lock);
1070                                 break;
1071                         }
1072                         inode = dentry->d_inode;        /* can't be NULL */
1073                         if (unlikely(!spin_trylock(&inode->i_lock))) {
1074                                 spin_unlock(&dentry->d_lock);
1075                                 if (parent)
1076                                         spin_unlock(&parent->d_lock);
1077                                 cpu_relax();
1078                                 continue;
1079                         }
1080                         __dentry_kill(dentry);
1081                         dentry = parent;
1082                 }
1083         }
1084 }
1085
1086 static enum lru_status dentry_lru_isolate(struct list_head *item,
1087                 struct list_lru_one *lru, spinlock_t *lru_lock, void *arg)
1088 {
1089         struct list_head *freeable = arg;
1090         struct dentry   *dentry = container_of(item, struct dentry, d_lru);
1091
1092
1093         /*
1094          * we are inverting the lru lock/dentry->d_lock here,
1095          * so use a trylock. If we fail to get the lock, just skip
1096          * it
1097          */
1098         if (!spin_trylock(&dentry->d_lock))
1099                 return LRU_SKIP;
1100
1101         /*
1102          * Referenced dentries are still in use. If they have active
1103          * counts, just remove them from the LRU. Otherwise give them
1104          * another pass through the LRU.
1105          */
1106         if (dentry->d_lockref.count) {
1107                 d_lru_isolate(lru, dentry);
1108                 spin_unlock(&dentry->d_lock);
1109                 return LRU_REMOVED;
1110         }
1111
1112         if (dentry->d_flags & DCACHE_REFERENCED) {
1113                 dentry->d_flags &= ~DCACHE_REFERENCED;
1114                 spin_unlock(&dentry->d_lock);
1115
1116                 /*
1117                  * The list move itself will be made by the common LRU code. At
1118                  * this point, we've dropped the dentry->d_lock but keep the
1119                  * lru lock. This is safe to do, since every list movement is
1120                  * protected by the lru lock even if both locks are held.
1121                  *
1122                  * This is guaranteed by the fact that all LRU management
1123                  * functions are intermediated by the LRU API calls like
1124                  * list_lru_add and list_lru_del. List movement in this file
1125                  * only ever occur through this functions or through callbacks
1126                  * like this one, that are called from the LRU API.
1127                  *
1128                  * The only exceptions to this are functions like
1129                  * shrink_dentry_list, and code that first checks for the
1130                  * DCACHE_SHRINK_LIST flag.  Those are guaranteed to be
1131                  * operating only with stack provided lists after they are
1132                  * properly isolated from the main list.  It is thus, always a
1133                  * local access.
1134                  */
1135                 return LRU_ROTATE;
1136         }
1137
1138         d_lru_shrink_move(lru, dentry, freeable);
1139         spin_unlock(&dentry->d_lock);
1140
1141         return LRU_REMOVED;
1142 }
1143
1144 /**
1145  * prune_dcache_sb - shrink the dcache
1146  * @sb: superblock
1147  * @sc: shrink control, passed to list_lru_shrink_walk()
1148  *
1149  * Attempt to shrink the superblock dcache LRU by @sc->nr_to_scan entries. This
1150  * is done when we need more memory and called from the superblock shrinker
1151  * function.
1152  *
1153  * This function may fail to free any resources if all the dentries are in
1154  * use.
1155  */
1156 long prune_dcache_sb(struct super_block *sb, struct shrink_control *sc)
1157 {
1158         LIST_HEAD(dispose);
1159         long freed;
1160
1161         freed = list_lru_shrink_walk(&sb->s_dentry_lru, sc,
1162                                      dentry_lru_isolate, &dispose);
1163         shrink_dentry_list(&dispose);
1164         return freed;
1165 }
1166
1167 static enum lru_status dentry_lru_isolate_shrink(struct list_head *item,
1168                 struct list_lru_one *lru, spinlock_t *lru_lock, void *arg)
1169 {
1170         struct list_head *freeable = arg;
1171         struct dentry   *dentry = container_of(item, struct dentry, d_lru);
1172
1173         /*
1174          * we are inverting the lru lock/dentry->d_lock here,
1175          * so use a trylock. If we fail to get the lock, just skip
1176          * it
1177          */
1178         if (!spin_trylock(&dentry->d_lock))
1179                 return LRU_SKIP;
1180
1181         d_lru_shrink_move(lru, dentry, freeable);
1182         spin_unlock(&dentry->d_lock);
1183
1184         return LRU_REMOVED;
1185 }
1186
1187
1188 /**
1189  * shrink_dcache_sb - shrink dcache for a superblock
1190  * @sb: superblock
1191  *
1192  * Shrink the dcache for the specified super block. This is used to free
1193  * the dcache before unmounting a file system.
1194  */
1195 void shrink_dcache_sb(struct super_block *sb)
1196 {
1197         long freed;
1198
1199         do {
1200                 LIST_HEAD(dispose);
1201
1202                 freed = list_lru_walk(&sb->s_dentry_lru,
1203                         dentry_lru_isolate_shrink, &dispose, 1024);
1204
1205                 this_cpu_sub(nr_dentry_unused, freed);
1206                 shrink_dentry_list(&dispose);
1207                 cond_resched();
1208         } while (list_lru_count(&sb->s_dentry_lru) > 0);
1209 }
1210 EXPORT_SYMBOL(shrink_dcache_sb);
1211
1212 /**
1213  * enum d_walk_ret - action to talke during tree walk
1214  * @D_WALK_CONTINUE:    contrinue walk
1215  * @D_WALK_QUIT:        quit walk
1216  * @D_WALK_NORETRY:     quit when retry is needed
1217  * @D_WALK_SKIP:        skip this dentry and its children
1218  */
1219 enum d_walk_ret {
1220         D_WALK_CONTINUE,
1221         D_WALK_QUIT,
1222         D_WALK_NORETRY,
1223         D_WALK_SKIP,
1224 };
1225
1226 /**
1227  * d_walk - walk the dentry tree
1228  * @parent:     start of walk
1229  * @data:       data passed to @enter() and @finish()
1230  * @enter:      callback when first entering the dentry
1231  * @finish:     callback when successfully finished the walk
1232  *
1233  * The @enter() and @finish() callbacks are called with d_lock held.
1234  */
1235 static void d_walk(struct dentry *parent, void *data,
1236                    enum d_walk_ret (*enter)(void *, struct dentry *),
1237                    void (*finish)(void *))
1238 {
1239         struct dentry *this_parent;
1240         struct list_head *next;
1241         unsigned seq = 0;
1242         enum d_walk_ret ret;
1243         bool retry = true;
1244
1245 again:
1246         read_seqbegin_or_lock(&rename_lock, &seq);
1247         this_parent = parent;
1248         spin_lock(&this_parent->d_lock);
1249
1250         ret = enter(data, this_parent);
1251         switch (ret) {
1252         case D_WALK_CONTINUE:
1253                 break;
1254         case D_WALK_QUIT:
1255         case D_WALK_SKIP:
1256                 goto out_unlock;
1257         case D_WALK_NORETRY:
1258                 retry = false;
1259                 break;
1260         }
1261 repeat:
1262         next = this_parent->d_subdirs.next;
1263 resume:
1264         while (next != &this_parent->d_subdirs) {
1265                 struct list_head *tmp = next;
1266                 struct dentry *dentry = list_entry(tmp, struct dentry, d_child);
1267                 next = tmp->next;
1268
1269                 if (unlikely(dentry->d_flags & DCACHE_DENTRY_CURSOR))
1270                         continue;
1271
1272                 spin_lock_nested(&dentry->d_lock, DENTRY_D_LOCK_NESTED);
1273
1274                 ret = enter(data, dentry);
1275                 switch (ret) {
1276                 case D_WALK_CONTINUE:
1277                         break;
1278                 case D_WALK_QUIT:
1279                         spin_unlock(&dentry->d_lock);
1280                         goto out_unlock;
1281                 case D_WALK_NORETRY:
1282                         retry = false;
1283                         break;
1284                 case D_WALK_SKIP:
1285                         spin_unlock(&dentry->d_lock);
1286                         continue;
1287                 }
1288
1289                 if (!list_empty(&dentry->d_subdirs)) {
1290                         spin_unlock(&this_parent->d_lock);
1291                         spin_release(&dentry->d_lock.dep_map, 1, _RET_IP_);
1292                         this_parent = dentry;
1293                         spin_acquire(&this_parent->d_lock.dep_map, 0, 1, _RET_IP_);
1294                         goto repeat;
1295                 }
1296                 spin_unlock(&dentry->d_lock);
1297         }
1298         /*
1299          * All done at this level ... ascend and resume the search.
1300          */
1301         rcu_read_lock();
1302 ascend:
1303         if (this_parent != parent) {
1304                 struct dentry *child = this_parent;
1305                 this_parent = child->d_parent;
1306
1307                 spin_unlock(&child->d_lock);
1308                 spin_lock(&this_parent->d_lock);
1309
1310                 /* might go back up the wrong parent if we have had a rename. */
1311                 if (need_seqretry(&rename_lock, seq))
1312                         goto rename_retry;
1313                 /* go into the first sibling still alive */
1314                 do {
1315                         next = child->d_child.next;
1316                         if (next == &this_parent->d_subdirs)
1317                                 goto ascend;
1318                         child = list_entry(next, struct dentry, d_child);
1319                 } while (unlikely(child->d_flags & DCACHE_DENTRY_KILLED));
1320                 rcu_read_unlock();
1321                 goto resume;
1322         }
1323         if (need_seqretry(&rename_lock, seq))
1324                 goto rename_retry;
1325         rcu_read_unlock();
1326         if (finish)
1327                 finish(data);
1328
1329 out_unlock:
1330         spin_unlock(&this_parent->d_lock);
1331         done_seqretry(&rename_lock, seq);
1332         return;
1333
1334 rename_retry:
1335         spin_unlock(&this_parent->d_lock);
1336         rcu_read_unlock();
1337         BUG_ON(seq & 1);
1338         if (!retry)
1339                 return;
1340         seq = 1;
1341         goto again;
1342 }
1343
1344 struct check_mount {
1345         struct vfsmount *mnt;
1346         unsigned int mounted;
1347 };
1348
1349 static enum d_walk_ret path_check_mount(void *data, struct dentry *dentry)
1350 {
1351         struct check_mount *info = data;
1352         struct path path = { .mnt = info->mnt, .dentry = dentry };
1353
1354         if (likely(!d_mountpoint(dentry)))
1355                 return D_WALK_CONTINUE;
1356         if (__path_is_mountpoint(&path)) {
1357                 info->mounted = 1;
1358                 return D_WALK_QUIT;
1359         }
1360         return D_WALK_CONTINUE;
1361 }
1362
1363 /**
1364  * path_has_submounts - check for mounts over a dentry in the
1365  *                      current namespace.
1366  * @parent: path to check.
1367  *
1368  * Return true if the parent or its subdirectories contain
1369  * a mount point in the current namespace.
1370  */
1371 int path_has_submounts(const struct path *parent)
1372 {
1373         struct check_mount data = { .mnt = parent->mnt, .mounted = 0 };
1374
1375         read_seqlock_excl(&mount_lock);
1376         d_walk(parent->dentry, &data, path_check_mount, NULL);
1377         read_sequnlock_excl(&mount_lock);
1378
1379         return data.mounted;
1380 }
1381 EXPORT_SYMBOL(path_has_submounts);
1382
1383 /*
1384  * Called by mount code to set a mountpoint and check if the mountpoint is
1385  * reachable (e.g. NFS can unhash a directory dentry and then the complete
1386  * subtree can become unreachable).
1387  *
1388  * Only one of d_invalidate() and d_set_mounted() must succeed.  For
1389  * this reason take rename_lock and d_lock on dentry and ancestors.
1390  */
1391 int d_set_mounted(struct dentry *dentry)
1392 {
1393         struct dentry *p;
1394         int ret = -ENOENT;
1395         write_seqlock(&rename_lock);
1396         for (p = dentry->d_parent; !IS_ROOT(p); p = p->d_parent) {
1397                 /* Need exclusion wrt. d_invalidate() */
1398                 spin_lock(&p->d_lock);
1399                 if (unlikely(d_unhashed(p))) {
1400                         spin_unlock(&p->d_lock);
1401                         goto out;
1402                 }
1403                 spin_unlock(&p->d_lock);
1404         }
1405         spin_lock(&dentry->d_lock);
1406         if (!d_unlinked(dentry)) {
1407                 ret = -EBUSY;
1408                 if (!d_mountpoint(dentry)) {
1409                         dentry->d_flags |= DCACHE_MOUNTED;
1410                         ret = 0;
1411                 }
1412         }
1413         spin_unlock(&dentry->d_lock);
1414 out:
1415         write_sequnlock(&rename_lock);
1416         return ret;
1417 }
1418
1419 /*
1420  * Search the dentry child list of the specified parent,
1421  * and move any unused dentries to the end of the unused
1422  * list for prune_dcache(). We descend to the next level
1423  * whenever the d_subdirs list is non-empty and continue
1424  * searching.
1425  *
1426  * It returns zero iff there are no unused children,
1427  * otherwise  it returns the number of children moved to
1428  * the end of the unused list. This may not be the total
1429  * number of unused children, because select_parent can
1430  * drop the lock and return early due to latency
1431  * constraints.
1432  */
1433
1434 struct select_data {
1435         struct dentry *start;
1436         struct list_head dispose;
1437         int found;
1438 };
1439
1440 static enum d_walk_ret select_collect(void *_data, struct dentry *dentry)
1441 {
1442         struct select_data *data = _data;
1443         enum d_walk_ret ret = D_WALK_CONTINUE;
1444
1445         if (data->start == dentry)
1446                 goto out;
1447
1448         if (dentry->d_flags & DCACHE_SHRINK_LIST) {
1449                 data->found++;
1450         } else {
1451                 if (dentry->d_flags & DCACHE_LRU_LIST)
1452                         d_lru_del(dentry);
1453                 if (!dentry->d_lockref.count) {
1454                         d_shrink_add(dentry, &data->dispose);
1455                         data->found++;
1456                 }
1457         }
1458         /*
1459          * We can return to the caller if we have found some (this
1460          * ensures forward progress). We'll be coming back to find
1461          * the rest.
1462          */
1463         if (!list_empty(&data->dispose))
1464                 ret = need_resched() ? D_WALK_QUIT : D_WALK_NORETRY;
1465 out:
1466         return ret;
1467 }
1468
1469 /**
1470  * shrink_dcache_parent - prune dcache
1471  * @parent: parent of entries to prune
1472  *
1473  * Prune the dcache to remove unused children of the parent dentry.
1474  */
1475 void shrink_dcache_parent(struct dentry *parent)
1476 {
1477         for (;;) {
1478                 struct select_data data;
1479
1480                 INIT_LIST_HEAD(&data.dispose);
1481                 data.start = parent;
1482                 data.found = 0;
1483
1484                 d_walk(parent, &data, select_collect, NULL);
1485                 if (!data.found)
1486                         break;
1487
1488                 shrink_dentry_list(&data.dispose);
1489                 cond_resched();
1490         }
1491 }
1492 EXPORT_SYMBOL(shrink_dcache_parent);
1493
1494 static enum d_walk_ret umount_check(void *_data, struct dentry *dentry)
1495 {
1496         /* it has busy descendents; complain about those instead */
1497         if (!list_empty(&dentry->d_subdirs))
1498                 return D_WALK_CONTINUE;
1499
1500         /* root with refcount 1 is fine */
1501         if (dentry == _data && dentry->d_lockref.count == 1)
1502                 return D_WALK_CONTINUE;
1503
1504         printk(KERN_ERR "BUG: Dentry %p{i=%lx,n=%pd} "
1505                         " still in use (%d) [unmount of %s %s]\n",
1506                        dentry,
1507                        dentry->d_inode ?
1508                        dentry->d_inode->i_ino : 0UL,
1509                        dentry,
1510                        dentry->d_lockref.count,
1511                        dentry->d_sb->s_type->name,
1512                        dentry->d_sb->s_id);
1513         WARN_ON(1);
1514         return D_WALK_CONTINUE;
1515 }
1516
1517 static void do_one_tree(struct dentry *dentry)
1518 {
1519         shrink_dcache_parent(dentry);
1520         d_walk(dentry, dentry, umount_check, NULL);
1521         d_drop(dentry);
1522         dput(dentry);
1523 }
1524
1525 /*
1526  * destroy the dentries attached to a superblock on unmounting
1527  */
1528 void shrink_dcache_for_umount(struct super_block *sb)
1529 {
1530         struct dentry *dentry;
1531
1532         WARN(down_read_trylock(&sb->s_umount), "s_umount should've been locked");
1533
1534         dentry = sb->s_root;
1535         sb->s_root = NULL;
1536         do_one_tree(dentry);
1537
1538         while (!hlist_bl_empty(&sb->s_roots)) {
1539                 dentry = dget(hlist_bl_entry(hlist_bl_first(&sb->s_roots), struct dentry, d_hash));
1540                 do_one_tree(dentry);
1541         }
1542 }
1543
1544 struct detach_data {
1545         struct select_data select;
1546         struct dentry *mountpoint;
1547 };
1548 static enum d_walk_ret detach_and_collect(void *_data, struct dentry *dentry)
1549 {
1550         struct detach_data *data = _data;
1551
1552         if (d_mountpoint(dentry)) {
1553                 __dget_dlock(dentry);
1554                 data->mountpoint = dentry;
1555                 return D_WALK_QUIT;
1556         }
1557
1558         return select_collect(&data->select, dentry);
1559 }
1560
1561 static void check_and_drop(void *_data)
1562 {
1563         struct detach_data *data = _data;
1564
1565         if (!data->mountpoint && list_empty(&data->select.dispose))
1566                 __d_drop(data->select.start);
1567 }
1568
1569 /**
1570  * d_invalidate - detach submounts, prune dcache, and drop
1571  * @dentry: dentry to invalidate (aka detach, prune and drop)
1572  *
1573  * no dcache lock.
1574  *
1575  * The final d_drop is done as an atomic operation relative to
1576  * rename_lock ensuring there are no races with d_set_mounted.  This
1577  * ensures there are no unhashed dentries on the path to a mountpoint.
1578  */
1579 void d_invalidate(struct dentry *dentry)
1580 {
1581         /*
1582          * If it's already been dropped, return OK.
1583          */
1584         spin_lock(&dentry->d_lock);
1585         if (d_unhashed(dentry)) {
1586                 spin_unlock(&dentry->d_lock);
1587                 return;
1588         }
1589         spin_unlock(&dentry->d_lock);
1590
1591         /* Negative dentries can be dropped without further checks */
1592         if (!dentry->d_inode) {
1593                 d_drop(dentry);
1594                 return;
1595         }
1596
1597         for (;;) {
1598                 struct detach_data data;
1599
1600                 data.mountpoint = NULL;
1601                 INIT_LIST_HEAD(&data.select.dispose);
1602                 data.select.start = dentry;
1603                 data.select.found = 0;
1604
1605                 d_walk(dentry, &data, detach_and_collect, check_and_drop);
1606
1607                 if (!list_empty(&data.select.dispose))
1608                         shrink_dentry_list(&data.select.dispose);
1609                 else if (!data.mountpoint)
1610                         return;
1611
1612                 if (data.mountpoint) {
1613                         detach_mounts(data.mountpoint);
1614                         dput(data.mountpoint);
1615                 }
1616                 cond_resched();
1617         }
1618 }
1619 EXPORT_SYMBOL(d_invalidate);
1620
1621 /**
1622  * __d_alloc    -       allocate a dcache entry
1623  * @sb: filesystem it will belong to
1624  * @name: qstr of the name
1625  *
1626  * Allocates a dentry. It returns %NULL if there is insufficient memory
1627  * available. On a success the dentry is returned. The name passed in is
1628  * copied and the copy passed in may be reused after this call.
1629  */
1630  
1631 struct dentry *__d_alloc(struct super_block *sb, const struct qstr *name)
1632 {
1633         struct dentry *dentry;
1634         char *dname;
1635         int err;
1636
1637         dentry = kmem_cache_alloc(dentry_cache, GFP_KERNEL);
1638         if (!dentry)
1639                 return NULL;
1640
1641         /*
1642          * We guarantee that the inline name is always NUL-terminated.
1643          * This way the memcpy() done by the name switching in rename
1644          * will still always have a NUL at the end, even if we might
1645          * be overwriting an internal NUL character
1646          */
1647         dentry->d_iname[DNAME_INLINE_LEN-1] = 0;
1648         if (unlikely(!name)) {
1649                 name = &slash_name;
1650                 dname = dentry->d_iname;
1651         } else if (name->len > DNAME_INLINE_LEN-1) {
1652                 size_t size = offsetof(struct external_name, name[1]);
1653                 struct external_name *p = kmalloc(size + name->len,
1654                                                   GFP_KERNEL_ACCOUNT);
1655                 if (!p) {
1656                         kmem_cache_free(dentry_cache, dentry); 
1657                         return NULL;
1658                 }
1659                 atomic_set(&p->u.count, 1);
1660                 dname = p->name;
1661         } else  {
1662                 dname = dentry->d_iname;
1663         }       
1664
1665         dentry->d_name.len = name->len;
1666         dentry->d_name.hash = name->hash;
1667         memcpy(dname, name->name, name->len);
1668         dname[name->len] = 0;
1669
1670         /* Make sure we always see the terminating NUL character */
1671         smp_store_release(&dentry->d_name.name, dname); /* ^^^ */
1672
1673         dentry->d_lockref.count = 1;
1674         dentry->d_flags = 0;
1675         spin_lock_init(&dentry->d_lock);
1676         seqcount_init(&dentry->d_seq);
1677         dentry->d_inode = NULL;
1678         dentry->d_parent = dentry;
1679         dentry->d_sb = sb;
1680         dentry->d_op = NULL;
1681         dentry->d_fsdata = NULL;
1682         INIT_HLIST_BL_NODE(&dentry->d_hash);
1683         INIT_LIST_HEAD(&dentry->d_lru);
1684         INIT_LIST_HEAD(&dentry->d_subdirs);
1685         INIT_HLIST_NODE(&dentry->d_u.d_alias);
1686         INIT_LIST_HEAD(&dentry->d_child);
1687         d_set_d_op(dentry, dentry->d_sb->s_d_op);
1688
1689         if (dentry->d_op && dentry->d_op->d_init) {
1690                 err = dentry->d_op->d_init(dentry);
1691                 if (err) {
1692                         if (dname_external(dentry))
1693                                 kfree(external_name(dentry));
1694                         kmem_cache_free(dentry_cache, dentry);
1695                         return NULL;
1696                 }
1697         }
1698
1699         this_cpu_inc(nr_dentry);
1700
1701         return dentry;
1702 }
1703
1704 /**
1705  * d_alloc      -       allocate a dcache entry
1706  * @parent: parent of entry to allocate
1707  * @name: qstr of the name
1708  *
1709  * Allocates a dentry. It returns %NULL if there is insufficient memory
1710  * available. On a success the dentry is returned. The name passed in is
1711  * copied and the copy passed in may be reused after this call.
1712  */
1713 struct dentry *d_alloc(struct dentry * parent, const struct qstr *name)
1714 {
1715         struct dentry *dentry = __d_alloc(parent->d_sb, name);
1716         if (!dentry)
1717                 return NULL;
1718         dentry->d_flags |= DCACHE_RCUACCESS;
1719         spin_lock(&parent->d_lock);
1720         /*
1721          * don't need child lock because it is not subject
1722          * to concurrency here
1723          */
1724         __dget_dlock(parent);
1725         dentry->d_parent = parent;
1726         list_add(&dentry->d_child, &parent->d_subdirs);
1727         spin_unlock(&parent->d_lock);
1728
1729         return dentry;
1730 }
1731 EXPORT_SYMBOL(d_alloc);
1732
1733 struct dentry *d_alloc_anon(struct super_block *sb)
1734 {
1735         return __d_alloc(sb, NULL);
1736 }
1737 EXPORT_SYMBOL(d_alloc_anon);
1738
1739 struct dentry *d_alloc_cursor(struct dentry * parent)
1740 {
1741         struct dentry *dentry = d_alloc_anon(parent->d_sb);
1742         if (dentry) {
1743                 dentry->d_flags |= DCACHE_RCUACCESS | DCACHE_DENTRY_CURSOR;
1744                 dentry->d_parent = dget(parent);
1745         }
1746         return dentry;
1747 }
1748
1749 /**
1750  * d_alloc_pseudo - allocate a dentry (for lookup-less filesystems)
1751  * @sb: the superblock
1752  * @name: qstr of the name
1753  *
1754  * For a filesystem that just pins its dentries in memory and never
1755  * performs lookups at all, return an unhashed IS_ROOT dentry.
1756  */
1757 struct dentry *d_alloc_pseudo(struct super_block *sb, const struct qstr *name)
1758 {
1759         return __d_alloc(sb, name);
1760 }
1761 EXPORT_SYMBOL(d_alloc_pseudo);
1762
1763 struct dentry *d_alloc_name(struct dentry *parent, const char *name)
1764 {
1765         struct qstr q;
1766
1767         q.name = name;
1768         q.hash_len = hashlen_string(parent, name);
1769         return d_alloc(parent, &q);
1770 }
1771 EXPORT_SYMBOL(d_alloc_name);
1772
1773 void d_set_d_op(struct dentry *dentry, const struct dentry_operations *op)
1774 {
1775         WARN_ON_ONCE(dentry->d_op);
1776         WARN_ON_ONCE(dentry->d_flags & (DCACHE_OP_HASH  |
1777                                 DCACHE_OP_COMPARE       |
1778                                 DCACHE_OP_REVALIDATE    |
1779                                 DCACHE_OP_WEAK_REVALIDATE       |
1780                                 DCACHE_OP_DELETE        |
1781                                 DCACHE_OP_REAL));
1782         dentry->d_op = op;
1783         if (!op)
1784                 return;
1785         if (op->d_hash)
1786                 dentry->d_flags |= DCACHE_OP_HASH;
1787         if (op->d_compare)
1788                 dentry->d_flags |= DCACHE_OP_COMPARE;
1789         if (op->d_revalidate)
1790                 dentry->d_flags |= DCACHE_OP_REVALIDATE;
1791         if (op->d_weak_revalidate)
1792                 dentry->d_flags |= DCACHE_OP_WEAK_REVALIDATE;
1793         if (op->d_delete)
1794                 dentry->d_flags |= DCACHE_OP_DELETE;
1795         if (op->d_prune)
1796                 dentry->d_flags |= DCACHE_OP_PRUNE;
1797         if (op->d_real)
1798                 dentry->d_flags |= DCACHE_OP_REAL;
1799
1800 }
1801 EXPORT_SYMBOL(d_set_d_op);
1802
1803
1804 /*
1805  * d_set_fallthru - Mark a dentry as falling through to a lower layer
1806  * @dentry - The dentry to mark
1807  *
1808  * Mark a dentry as falling through to the lower layer (as set with
1809  * d_pin_lower()).  This flag may be recorded on the medium.
1810  */
1811 void d_set_fallthru(struct dentry *dentry)
1812 {
1813         spin_lock(&dentry->d_lock);
1814         dentry->d_flags |= DCACHE_FALLTHRU;
1815         spin_unlock(&dentry->d_lock);
1816 }
1817 EXPORT_SYMBOL(d_set_fallthru);
1818
1819 static unsigned d_flags_for_inode(struct inode *inode)
1820 {
1821         unsigned add_flags = DCACHE_REGULAR_TYPE;
1822
1823         if (!inode)
1824                 return DCACHE_MISS_TYPE;
1825
1826         if (S_ISDIR(inode->i_mode)) {
1827                 add_flags = DCACHE_DIRECTORY_TYPE;
1828                 if (unlikely(!(inode->i_opflags & IOP_LOOKUP))) {
1829                         if (unlikely(!inode->i_op->lookup))
1830                                 add_flags = DCACHE_AUTODIR_TYPE;
1831                         else
1832                                 inode->i_opflags |= IOP_LOOKUP;
1833                 }
1834                 goto type_determined;
1835         }
1836
1837         if (unlikely(!(inode->i_opflags & IOP_NOFOLLOW))) {
1838                 if (unlikely(inode->i_op->get_link)) {
1839                         add_flags = DCACHE_SYMLINK_TYPE;
1840                         goto type_determined;
1841                 }
1842                 inode->i_opflags |= IOP_NOFOLLOW;
1843         }
1844
1845         if (unlikely(!S_ISREG(inode->i_mode)))
1846                 add_flags = DCACHE_SPECIAL_TYPE;
1847
1848 type_determined:
1849         if (unlikely(IS_AUTOMOUNT(inode)))
1850                 add_flags |= DCACHE_NEED_AUTOMOUNT;
1851         return add_flags;
1852 }
1853
1854 static void __d_instantiate(struct dentry *dentry, struct inode *inode)
1855 {
1856         unsigned add_flags = d_flags_for_inode(inode);
1857         WARN_ON(d_in_lookup(dentry));
1858
1859         spin_lock(&dentry->d_lock);
1860         hlist_add_head(&dentry->d_u.d_alias, &inode->i_dentry);
1861         raw_write_seqcount_begin(&dentry->d_seq);
1862         __d_set_inode_and_type(dentry, inode, add_flags);
1863         raw_write_seqcount_end(&dentry->d_seq);
1864         fsnotify_update_flags(dentry);
1865         spin_unlock(&dentry->d_lock);
1866 }
1867
1868 /**
1869  * d_instantiate - fill in inode information for a dentry
1870  * @entry: dentry to complete
1871  * @inode: inode to attach to this dentry
1872  *
1873  * Fill in inode information in the entry.
1874  *
1875  * This turns negative dentries into productive full members
1876  * of society.
1877  *
1878  * NOTE! This assumes that the inode count has been incremented
1879  * (or otherwise set) by the caller to indicate that it is now
1880  * in use by the dcache.
1881  */
1882  
1883 void d_instantiate(struct dentry *entry, struct inode * inode)
1884 {
1885         BUG_ON(!hlist_unhashed(&entry->d_u.d_alias));
1886         if (inode) {
1887                 security_d_instantiate(entry, inode);
1888                 spin_lock(&inode->i_lock);
1889                 __d_instantiate(entry, inode);
1890                 spin_unlock(&inode->i_lock);
1891         }
1892 }
1893 EXPORT_SYMBOL(d_instantiate);
1894
1895 /**
1896  * d_instantiate_no_diralias - instantiate a non-aliased dentry
1897  * @entry: dentry to complete
1898  * @inode: inode to attach to this dentry
1899  *
1900  * Fill in inode information in the entry.  If a directory alias is found, then
1901  * return an error (and drop inode).  Together with d_materialise_unique() this
1902  * guarantees that a directory inode may never have more than one alias.
1903  */
1904 int d_instantiate_no_diralias(struct dentry *entry, struct inode *inode)
1905 {
1906         BUG_ON(!hlist_unhashed(&entry->d_u.d_alias));
1907
1908         security_d_instantiate(entry, inode);
1909         spin_lock(&inode->i_lock);
1910         if (S_ISDIR(inode->i_mode) && !hlist_empty(&inode->i_dentry)) {
1911                 spin_unlock(&inode->i_lock);
1912                 iput(inode);
1913                 return -EBUSY;
1914         }
1915         __d_instantiate(entry, inode);
1916         spin_unlock(&inode->i_lock);
1917
1918         return 0;
1919 }
1920 EXPORT_SYMBOL(d_instantiate_no_diralias);
1921
1922 struct dentry *d_make_root(struct inode *root_inode)
1923 {
1924         struct dentry *res = NULL;
1925
1926         if (root_inode) {
1927                 res = d_alloc_anon(root_inode->i_sb);
1928                 if (res)
1929                         d_instantiate(res, root_inode);
1930                 else
1931                         iput(root_inode);
1932         }
1933         return res;
1934 }
1935 EXPORT_SYMBOL(d_make_root);
1936
1937 static struct dentry * __d_find_any_alias(struct inode *inode)
1938 {
1939         struct dentry *alias;
1940
1941         if (hlist_empty(&inode->i_dentry))
1942                 return NULL;
1943         alias = hlist_entry(inode->i_dentry.first, struct dentry, d_u.d_alias);
1944         __dget(alias);
1945         return alias;
1946 }
1947
1948 /**
1949  * d_find_any_alias - find any alias for a given inode
1950  * @inode: inode to find an alias for
1951  *
1952  * If any aliases exist for the given inode, take and return a
1953  * reference for one of them.  If no aliases exist, return %NULL.
1954  */
1955 struct dentry *d_find_any_alias(struct inode *inode)
1956 {
1957         struct dentry *de;
1958
1959         spin_lock(&inode->i_lock);
1960         de = __d_find_any_alias(inode);
1961         spin_unlock(&inode->i_lock);
1962         return de;
1963 }
1964 EXPORT_SYMBOL(d_find_any_alias);
1965
1966 static struct dentry *__d_instantiate_anon(struct dentry *dentry,
1967                                            struct inode *inode,
1968                                            bool disconnected)
1969 {
1970         struct dentry *res;
1971         unsigned add_flags;
1972
1973         security_d_instantiate(dentry, inode);
1974         spin_lock(&inode->i_lock);
1975         res = __d_find_any_alias(inode);
1976         if (res) {
1977                 spin_unlock(&inode->i_lock);
1978                 dput(dentry);
1979                 goto out_iput;
1980         }
1981
1982         /* attach a disconnected dentry */
1983         add_flags = d_flags_for_inode(inode);
1984
1985         if (disconnected)
1986                 add_flags |= DCACHE_DISCONNECTED;
1987
1988         spin_lock(&dentry->d_lock);
1989         __d_set_inode_and_type(dentry, inode, add_flags);
1990         hlist_add_head(&dentry->d_u.d_alias, &inode->i_dentry);
1991         if (!disconnected) {
1992                 hlist_bl_lock(&dentry->d_sb->s_roots);
1993                 hlist_bl_add_head(&dentry->d_hash, &dentry->d_sb->s_roots);
1994                 hlist_bl_unlock(&dentry->d_sb->s_roots);
1995         }
1996         spin_unlock(&dentry->d_lock);
1997         spin_unlock(&inode->i_lock);
1998
1999         return dentry;
2000
2001  out_iput:
2002         iput(inode);
2003         return res;
2004 }
2005
2006 struct dentry *d_instantiate_anon(struct dentry *dentry, struct inode *inode)
2007 {
2008         return __d_instantiate_anon(dentry, inode, true);
2009 }
2010 EXPORT_SYMBOL(d_instantiate_anon);
2011
2012 static struct dentry *__d_obtain_alias(struct inode *inode, bool disconnected)
2013 {
2014         struct dentry *tmp;
2015         struct dentry *res;
2016
2017         if (!inode)
2018                 return ERR_PTR(-ESTALE);
2019         if (IS_ERR(inode))
2020                 return ERR_CAST(inode);
2021
2022         res = d_find_any_alias(inode);
2023         if (res)
2024                 goto out_iput;
2025
2026         tmp = d_alloc_anon(inode->i_sb);
2027         if (!tmp) {
2028                 res = ERR_PTR(-ENOMEM);
2029                 goto out_iput;
2030         }
2031
2032         return __d_instantiate_anon(tmp, inode, disconnected);
2033
2034 out_iput:
2035         iput(inode);
2036         return res;
2037 }
2038
2039 /**
2040  * d_obtain_alias - find or allocate a DISCONNECTED dentry for a given inode
2041  * @inode: inode to allocate the dentry for
2042  *
2043  * Obtain a dentry for an inode resulting from NFS filehandle conversion or
2044  * similar open by handle operations.  The returned dentry may be anonymous,
2045  * or may have a full name (if the inode was already in the cache).
2046  *
2047  * When called on a directory inode, we must ensure that the inode only ever
2048  * has one dentry.  If a dentry is found, that is returned instead of
2049  * allocating a new one.
2050  *
2051  * On successful return, the reference to the inode has been transferred
2052  * to the dentry.  In case of an error the reference on the inode is released.
2053  * To make it easier to use in export operations a %NULL or IS_ERR inode may
2054  * be passed in and the error will be propagated to the return value,
2055  * with a %NULL @inode replaced by ERR_PTR(-ESTALE).
2056  */
2057 struct dentry *d_obtain_alias(struct inode *inode)
2058 {
2059         return __d_obtain_alias(inode, true);
2060 }
2061 EXPORT_SYMBOL(d_obtain_alias);
2062
2063 /**
2064  * d_obtain_root - find or allocate a dentry for a given inode
2065  * @inode: inode to allocate the dentry for
2066  *
2067  * Obtain an IS_ROOT dentry for the root of a filesystem.
2068  *
2069  * We must ensure that directory inodes only ever have one dentry.  If a
2070  * dentry is found, that is returned instead of allocating a new one.
2071  *
2072  * On successful return, the reference to the inode has been transferred
2073  * to the dentry.  In case of an error the reference on the inode is
2074  * released.  A %NULL or IS_ERR inode may be passed in and will be the
2075  * error will be propagate to the return value, with a %NULL @inode
2076  * replaced by ERR_PTR(-ESTALE).
2077  */
2078 struct dentry *d_obtain_root(struct inode *inode)
2079 {
2080         return __d_obtain_alias(inode, false);
2081 }
2082 EXPORT_SYMBOL(d_obtain_root);
2083
2084 /**
2085  * d_add_ci - lookup or allocate new dentry with case-exact name
2086  * @inode:  the inode case-insensitive lookup has found
2087  * @dentry: the negative dentry that was passed to the parent's lookup func
2088  * @name:   the case-exact name to be associated with the returned dentry
2089  *
2090  * This is to avoid filling the dcache with case-insensitive names to the
2091  * same inode, only the actual correct case is stored in the dcache for
2092  * case-insensitive filesystems.
2093  *
2094  * For a case-insensitive lookup match and if the the case-exact dentry
2095  * already exists in in the dcache, use it and return it.
2096  *
2097  * If no entry exists with the exact case name, allocate new dentry with
2098  * the exact case, and return the spliced entry.
2099  */
2100 struct dentry *d_add_ci(struct dentry *dentry, struct inode *inode,
2101                         struct qstr *name)
2102 {
2103         struct dentry *found, *res;
2104
2105         /*
2106          * First check if a dentry matching the name already exists,
2107          * if not go ahead and create it now.
2108          */
2109         found = d_hash_and_lookup(dentry->d_parent, name);
2110         if (found) {
2111                 iput(inode);
2112                 return found;
2113         }
2114         if (d_in_lookup(dentry)) {
2115                 found = d_alloc_parallel(dentry->d_parent, name,
2116                                         dentry->d_wait);
2117                 if (IS_ERR(found) || !d_in_lookup(found)) {
2118                         iput(inode);
2119                         return found;
2120                 }
2121         } else {
2122                 found = d_alloc(dentry->d_parent, name);
2123                 if (!found) {
2124                         iput(inode);
2125                         return ERR_PTR(-ENOMEM);
2126                 } 
2127         }
2128         res = d_splice_alias(inode, found);
2129         if (res) {
2130                 dput(found);
2131                 return res;
2132         }
2133         return found;
2134 }
2135 EXPORT_SYMBOL(d_add_ci);
2136
2137
2138 static inline bool d_same_name(const struct dentry *dentry,
2139                                 const struct dentry *parent,
2140                                 const struct qstr *name)
2141 {
2142         if (likely(!(parent->d_flags & DCACHE_OP_COMPARE))) {
2143                 if (dentry->d_name.len != name->len)
2144                         return false;
2145                 return dentry_cmp(dentry, name->name, name->len) == 0;
2146         }
2147         return parent->d_op->d_compare(dentry,
2148                                        dentry->d_name.len, dentry->d_name.name,
2149                                        name) == 0;
2150 }
2151
2152 /**
2153  * __d_lookup_rcu - search for a dentry (racy, store-free)
2154  * @parent: parent dentry
2155  * @name: qstr of name we wish to find
2156  * @seqp: returns d_seq value at the point where the dentry was found
2157  * Returns: dentry, or NULL
2158  *
2159  * __d_lookup_rcu is the dcache lookup function for rcu-walk name
2160  * resolution (store-free path walking) design described in
2161  * Documentation/filesystems/path-lookup.txt.
2162  *
2163  * This is not to be used outside core vfs.
2164  *
2165  * __d_lookup_rcu must only be used in rcu-walk mode, ie. with vfsmount lock
2166  * held, and rcu_read_lock held. The returned dentry must not be stored into
2167  * without taking d_lock and checking d_seq sequence count against @seq
2168  * returned here.
2169  *
2170  * A refcount may be taken on the found dentry with the d_rcu_to_refcount
2171  * function.
2172  *
2173  * Alternatively, __d_lookup_rcu may be called again to look up the child of
2174  * the returned dentry, so long as its parent's seqlock is checked after the
2175  * child is looked up. Thus, an interlocking stepping of sequence lock checks
2176  * is formed, giving integrity down the path walk.
2177  *
2178  * NOTE! The caller *has* to check the resulting dentry against the sequence
2179  * number we've returned before using any of the resulting dentry state!
2180  */
2181 struct dentry *__d_lookup_rcu(const struct dentry *parent,
2182                                 const struct qstr *name,
2183                                 unsigned *seqp)
2184 {
2185         u64 hashlen = name->hash_len;
2186         const unsigned char *str = name->name;
2187         struct hlist_bl_head *b = d_hash(hashlen_hash(hashlen));
2188         struct hlist_bl_node *node;
2189         struct dentry *dentry;
2190
2191         /*
2192          * Note: There is significant duplication with __d_lookup_rcu which is
2193          * required to prevent single threaded performance regressions
2194          * especially on architectures where smp_rmb (in seqcounts) are costly.
2195          * Keep the two functions in sync.
2196          */
2197
2198         /*
2199          * The hash list is protected using RCU.
2200          *
2201          * Carefully use d_seq when comparing a candidate dentry, to avoid
2202          * races with d_move().
2203          *
2204          * It is possible that concurrent renames can mess up our list
2205          * walk here and result in missing our dentry, resulting in the
2206          * false-negative result. d_lookup() protects against concurrent
2207          * renames using rename_lock seqlock.
2208          *
2209          * See Documentation/filesystems/path-lookup.txt for more details.
2210          */
2211         hlist_bl_for_each_entry_rcu(dentry, node, b, d_hash) {
2212                 unsigned seq;
2213
2214 seqretry:
2215                 /*
2216                  * The dentry sequence count protects us from concurrent
2217                  * renames, and thus protects parent and name fields.
2218                  *
2219                  * The caller must perform a seqcount check in order
2220                  * to do anything useful with the returned dentry.
2221                  *
2222                  * NOTE! We do a "raw" seqcount_begin here. That means that
2223                  * we don't wait for the sequence count to stabilize if it
2224                  * is in the middle of a sequence change. If we do the slow
2225                  * dentry compare, we will do seqretries until it is stable,
2226                  * and if we end up with a successful lookup, we actually
2227                  * want to exit RCU lookup anyway.
2228                  *
2229                  * Note that raw_seqcount_begin still *does* smp_rmb(), so
2230                  * we are still guaranteed NUL-termination of ->d_name.name.
2231                  */
2232                 seq = raw_seqcount_begin(&dentry->d_seq);
2233                 if (dentry->d_parent != parent)
2234                         continue;
2235                 if (d_unhashed(dentry))
2236                         continue;
2237
2238                 if (unlikely(parent->d_flags & DCACHE_OP_COMPARE)) {
2239                         int tlen;
2240                         const char *tname;
2241                         if (dentry->d_name.hash != hashlen_hash(hashlen))
2242                                 continue;
2243                         tlen = dentry->d_name.len;
2244                         tname = dentry->d_name.name;
2245                         /* we want a consistent (name,len) pair */
2246                         if (read_seqcount_retry(&dentry->d_seq, seq)) {
2247                                 cpu_relax();
2248                                 goto seqretry;
2249                         }
2250                         if (parent->d_op->d_compare(dentry,
2251                                                     tlen, tname, name) != 0)
2252                                 continue;
2253                 } else {
2254                         if (dentry->d_name.hash_len != hashlen)
2255                                 continue;
2256                         if (dentry_cmp(dentry, str, hashlen_len(hashlen)) != 0)
2257                                 continue;
2258                 }
2259                 *seqp = seq;
2260                 return dentry;
2261         }
2262         return NULL;
2263 }
2264
2265 /**
2266  * d_lookup - search for a dentry
2267  * @parent: parent dentry
2268  * @name: qstr of name we wish to find
2269  * Returns: dentry, or NULL
2270  *
2271  * d_lookup searches the children of the parent dentry for the name in
2272  * question. If the dentry is found its reference count is incremented and the
2273  * dentry is returned. The caller must use dput to free the entry when it has
2274  * finished using it. %NULL is returned if the dentry does not exist.
2275  */
2276 struct dentry *d_lookup(const struct dentry *parent, const struct qstr *name)
2277 {
2278         struct dentry *dentry;
2279         unsigned seq;
2280
2281         do {
2282                 seq = read_seqbegin(&rename_lock);
2283                 dentry = __d_lookup(parent, name);
2284                 if (dentry)
2285                         break;
2286         } while (read_seqretry(&rename_lock, seq));
2287         return dentry;
2288 }
2289 EXPORT_SYMBOL(d_lookup);
2290
2291 /**
2292  * __d_lookup - search for a dentry (racy)
2293  * @parent: parent dentry
2294  * @name: qstr of name we wish to find
2295  * Returns: dentry, or NULL
2296  *
2297  * __d_lookup is like d_lookup, however it may (rarely) return a
2298  * false-negative result due to unrelated rename activity.
2299  *
2300  * __d_lookup is slightly faster by avoiding rename_lock read seqlock,
2301  * however it must be used carefully, eg. with a following d_lookup in
2302  * the case of failure.
2303  *
2304  * __d_lookup callers must be commented.
2305  */
2306 struct dentry *__d_lookup(const struct dentry *parent, const struct qstr *name)
2307 {
2308         unsigned int hash = name->hash;
2309         struct hlist_bl_head *b = d_hash(hash);
2310         struct hlist_bl_node *node;
2311         struct dentry *found = NULL;
2312         struct dentry *dentry;
2313
2314         /*
2315          * Note: There is significant duplication with __d_lookup_rcu which is
2316          * required to prevent single threaded performance regressions
2317          * especially on architectures where smp_rmb (in seqcounts) are costly.
2318          * Keep the two functions in sync.
2319          */
2320
2321         /*
2322          * The hash list is protected using RCU.
2323          *
2324          * Take d_lock when comparing a candidate dentry, to avoid races
2325          * with d_move().
2326          *
2327          * It is possible that concurrent renames can mess up our list
2328          * walk here and result in missing our dentry, resulting in the
2329          * false-negative result. d_lookup() protects against concurrent
2330          * renames using rename_lock seqlock.
2331          *
2332          * See Documentation/filesystems/path-lookup.txt for more details.
2333          */
2334         rcu_read_lock();
2335         
2336         hlist_bl_for_each_entry_rcu(dentry, node, b, d_hash) {
2337
2338                 if (dentry->d_name.hash != hash)
2339                         continue;
2340
2341                 spin_lock(&dentry->d_lock);
2342                 if (dentry->d_parent != parent)
2343                         goto next;
2344                 if (d_unhashed(dentry))
2345                         goto next;
2346
2347                 if (!d_same_name(dentry, parent, name))
2348                         goto next;
2349
2350                 dentry->d_lockref.count++;
2351                 found = dentry;
2352                 spin_unlock(&dentry->d_lock);
2353                 break;
2354 next:
2355                 spin_unlock(&dentry->d_lock);
2356         }
2357         rcu_read_unlock();
2358
2359         return found;
2360 }
2361
2362 /**
2363  * d_hash_and_lookup - hash the qstr then search for a dentry
2364  * @dir: Directory to search in
2365  * @name: qstr of name we wish to find
2366  *
2367  * On lookup failure NULL is returned; on bad name - ERR_PTR(-error)
2368  */
2369 struct dentry *d_hash_and_lookup(struct dentry *dir, struct qstr *name)
2370 {
2371         /*
2372          * Check for a fs-specific hash function. Note that we must
2373          * calculate the standard hash first, as the d_op->d_hash()
2374          * routine may choose to leave the hash value unchanged.
2375          */
2376         name->hash = full_name_hash(dir, name->name, name->len);
2377         if (dir->d_flags & DCACHE_OP_HASH) {
2378                 int err = dir->d_op->d_hash(dir, name);
2379                 if (unlikely(err < 0))
2380                         return ERR_PTR(err);
2381         }
2382         return d_lookup(dir, name);
2383 }
2384 EXPORT_SYMBOL(d_hash_and_lookup);
2385
2386 /*
2387  * When a file is deleted, we have two options:
2388  * - turn this dentry into a negative dentry
2389  * - unhash this dentry and free it.
2390  *
2391  * Usually, we want to just turn this into
2392  * a negative dentry, but if anybody else is
2393  * currently using the dentry or the inode
2394  * we can't do that and we fall back on removing
2395  * it from the hash queues and waiting for
2396  * it to be deleted later when it has no users
2397  */
2398  
2399 /**
2400  * d_delete - delete a dentry
2401  * @dentry: The dentry to delete
2402  *
2403  * Turn the dentry into a negative dentry if possible, otherwise
2404  * remove it from the hash queues so it can be deleted later
2405  */
2406  
2407 void d_delete(struct dentry * dentry)
2408 {
2409         struct inode *inode = dentry->d_inode;
2410         int isdir = d_is_dir(dentry);
2411
2412         spin_lock(&inode->i_lock);
2413         spin_lock(&dentry->d_lock);
2414         /*
2415          * Are we the only user?
2416          */
2417         if (dentry->d_lockref.count == 1) {
2418                 dentry->d_flags &= ~DCACHE_CANT_MOUNT;
2419                 dentry_unlink_inode(dentry);
2420         } else {
2421                 __d_drop(dentry);
2422                 spin_unlock(&dentry->d_lock);
2423                 spin_unlock(&inode->i_lock);
2424         }
2425         fsnotify_nameremove(dentry, isdir);
2426 }
2427 EXPORT_SYMBOL(d_delete);
2428
2429 static void __d_rehash(struct dentry *entry)
2430 {
2431         struct hlist_bl_head *b = d_hash(entry->d_name.hash);
2432
2433         hlist_bl_lock(b);
2434         hlist_bl_add_head_rcu(&entry->d_hash, b);
2435         hlist_bl_unlock(b);
2436 }
2437
2438 /**
2439  * d_rehash     - add an entry back to the hash
2440  * @entry: dentry to add to the hash
2441  *
2442  * Adds a dentry to the hash according to its name.
2443  */
2444  
2445 void d_rehash(struct dentry * entry)
2446 {
2447         spin_lock(&entry->d_lock);
2448         __d_rehash(entry);
2449         spin_unlock(&entry->d_lock);
2450 }
2451 EXPORT_SYMBOL(d_rehash);
2452
2453 static inline unsigned start_dir_add(struct inode *dir)
2454 {
2455
2456         for (;;) {
2457                 unsigned n = dir->i_dir_seq;
2458                 if (!(n & 1) && cmpxchg(&dir->i_dir_seq, n, n + 1) == n)
2459                         return n;
2460                 cpu_relax();
2461         }
2462 }
2463
2464 static inline void end_dir_add(struct inode *dir, unsigned n)
2465 {
2466         smp_store_release(&dir->i_dir_seq, n + 2);
2467 }
2468
2469 static void d_wait_lookup(struct dentry *dentry)
2470 {
2471         if (d_in_lookup(dentry)) {
2472                 DECLARE_WAITQUEUE(wait, current);
2473                 add_wait_queue(dentry->d_wait, &wait);
2474                 do {
2475                         set_current_state(TASK_UNINTERRUPTIBLE);
2476                         spin_unlock(&dentry->d_lock);
2477                         schedule();
2478                         spin_lock(&dentry->d_lock);
2479                 } while (d_in_lookup(dentry));
2480         }
2481 }
2482
2483 struct dentry *d_alloc_parallel(struct dentry *parent,
2484                                 const struct qstr *name,
2485                                 wait_queue_head_t *wq)
2486 {
2487         unsigned int hash = name->hash;
2488         struct hlist_bl_head *b = in_lookup_hash(parent, hash);
2489         struct hlist_bl_node *node;
2490         struct dentry *new = d_alloc(parent, name);
2491         struct dentry *dentry;
2492         unsigned seq, r_seq, d_seq;
2493
2494         if (unlikely(!new))
2495                 return ERR_PTR(-ENOMEM);
2496
2497 retry:
2498         rcu_read_lock();
2499         seq = smp_load_acquire(&parent->d_inode->i_dir_seq);
2500         r_seq = read_seqbegin(&rename_lock);
2501         dentry = __d_lookup_rcu(parent, name, &d_seq);
2502         if (unlikely(dentry)) {
2503                 if (!lockref_get_not_dead(&dentry->d_lockref)) {
2504                         rcu_read_unlock();
2505                         goto retry;
2506                 }
2507                 if (read_seqcount_retry(&dentry->d_seq, d_seq)) {
2508                         rcu_read_unlock();
2509                         dput(dentry);
2510                         goto retry;
2511                 }
2512                 rcu_read_unlock();
2513                 dput(new);
2514                 return dentry;
2515         }
2516         if (unlikely(read_seqretry(&rename_lock, r_seq))) {
2517                 rcu_read_unlock();
2518                 goto retry;
2519         }
2520
2521         if (unlikely(seq & 1)) {
2522                 rcu_read_unlock();
2523                 goto retry;
2524         }
2525
2526         hlist_bl_lock(b);
2527         if (unlikely(READ_ONCE(parent->d_inode->i_dir_seq) != seq)) {
2528                 hlist_bl_unlock(b);
2529                 rcu_read_unlock();
2530                 goto retry;
2531         }
2532         /*
2533          * No changes for the parent since the beginning of d_lookup().
2534          * Since all removals from the chain happen with hlist_bl_lock(),
2535          * any potential in-lookup matches are going to stay here until
2536          * we unlock the chain.  All fields are stable in everything
2537          * we encounter.
2538          */
2539         hlist_bl_for_each_entry(dentry, node, b, d_u.d_in_lookup_hash) {
2540                 if (dentry->d_name.hash != hash)
2541                         continue;
2542                 if (dentry->d_parent != parent)
2543                         continue;
2544                 if (!d_same_name(dentry, parent, name))
2545                         continue;
2546                 hlist_bl_unlock(b);
2547                 /* now we can try to grab a reference */
2548                 if (!lockref_get_not_dead(&dentry->d_lockref)) {
2549                         rcu_read_unlock();
2550                         goto retry;
2551                 }
2552
2553                 rcu_read_unlock();
2554                 /*
2555                  * somebody is likely to be still doing lookup for it;
2556                  * wait for them to finish
2557                  */
2558                 spin_lock(&dentry->d_lock);
2559                 d_wait_lookup(dentry);
2560                 /*
2561                  * it's not in-lookup anymore; in principle we should repeat
2562                  * everything from dcache lookup, but it's likely to be what
2563                  * d_lookup() would've found anyway.  If it is, just return it;
2564                  * otherwise we really have to repeat the whole thing.
2565                  */
2566                 if (unlikely(dentry->d_name.hash != hash))
2567                         goto mismatch;
2568                 if (unlikely(dentry->d_parent != parent))
2569                         goto mismatch;
2570                 if (unlikely(d_unhashed(dentry)))
2571                         goto mismatch;
2572                 if (unlikely(!d_same_name(dentry, parent, name)))
2573                         goto mismatch;
2574                 /* OK, it *is* a hashed match; return it */
2575                 spin_unlock(&dentry->d_lock);
2576                 dput(new);
2577                 return dentry;
2578         }
2579         rcu_read_unlock();
2580         /* we can't take ->d_lock here; it's OK, though. */
2581         new->d_flags |= DCACHE_PAR_LOOKUP;
2582         new->d_wait = wq;
2583         hlist_bl_add_head_rcu(&new->d_u.d_in_lookup_hash, b);
2584         hlist_bl_unlock(b);
2585         return new;
2586 mismatch:
2587         spin_unlock(&dentry->d_lock);
2588         dput(dentry);
2589         goto retry;
2590 }
2591 EXPORT_SYMBOL(d_alloc_parallel);
2592
2593 void __d_lookup_done(struct dentry *dentry)
2594 {
2595         struct hlist_bl_head *b = in_lookup_hash(dentry->d_parent,
2596                                                  dentry->d_name.hash);
2597         hlist_bl_lock(b);
2598         dentry->d_flags &= ~DCACHE_PAR_LOOKUP;
2599         __hlist_bl_del(&dentry->d_u.d_in_lookup_hash);
2600         wake_up_all(dentry->d_wait);
2601         dentry->d_wait = NULL;
2602         hlist_bl_unlock(b);
2603         INIT_HLIST_NODE(&dentry->d_u.d_alias);
2604         INIT_LIST_HEAD(&dentry->d_lru);
2605 }
2606 EXPORT_SYMBOL(__d_lookup_done);
2607
2608 /* inode->i_lock held if inode is non-NULL */
2609
2610 static inline void __d_add(struct dentry *dentry, struct inode *inode)
2611 {
2612         struct inode *dir = NULL;
2613         unsigned n;
2614         spin_lock(&dentry->d_lock);
2615         if (unlikely(d_in_lookup(dentry))) {
2616                 dir = dentry->d_parent->d_inode;
2617                 n = start_dir_add(dir);
2618                 __d_lookup_done(dentry);
2619         }
2620         if (inode) {
2621                 unsigned add_flags = d_flags_for_inode(inode);
2622                 hlist_add_head(&dentry->d_u.d_alias, &inode->i_dentry);
2623                 raw_write_seqcount_begin(&dentry->d_seq);
2624                 __d_set_inode_and_type(dentry, inode, add_flags);
2625                 raw_write_seqcount_end(&dentry->d_seq);
2626                 fsnotify_update_flags(dentry);
2627         }
2628         __d_rehash(dentry);
2629         if (dir)
2630                 end_dir_add(dir, n);
2631         spin_unlock(&dentry->d_lock);
2632         if (inode)
2633                 spin_unlock(&inode->i_lock);
2634 }
2635
2636 /**
2637  * d_add - add dentry to hash queues
2638  * @entry: dentry to add
2639  * @inode: The inode to attach to this dentry
2640  *
2641  * This adds the entry to the hash queues and initializes @inode.
2642  * The entry was actually filled in earlier during d_alloc().
2643  */
2644
2645 void d_add(struct dentry *entry, struct inode *inode)
2646 {
2647         if (inode) {
2648                 security_d_instantiate(entry, inode);
2649                 spin_lock(&inode->i_lock);
2650         }
2651         __d_add(entry, inode);
2652 }
2653 EXPORT_SYMBOL(d_add);
2654
2655 /**
2656  * d_exact_alias - find and hash an exact unhashed alias
2657  * @entry: dentry to add
2658  * @inode: The inode to go with this dentry
2659  *
2660  * If an unhashed dentry with the same name/parent and desired
2661  * inode already exists, hash and return it.  Otherwise, return
2662  * NULL.
2663  *
2664  * Parent directory should be locked.
2665  */
2666 struct dentry *d_exact_alias(struct dentry *entry, struct inode *inode)
2667 {
2668         struct dentry *alias;
2669         unsigned int hash = entry->d_name.hash;
2670
2671         spin_lock(&inode->i_lock);
2672         hlist_for_each_entry(alias, &inode->i_dentry, d_u.d_alias) {
2673                 /*
2674                  * Don't need alias->d_lock here, because aliases with
2675                  * d_parent == entry->d_parent are not subject to name or
2676                  * parent changes, because the parent inode i_mutex is held.
2677                  */
2678                 if (alias->d_name.hash != hash)
2679                         continue;
2680                 if (alias->d_parent != entry->d_parent)
2681                         continue;
2682                 if (!d_same_name(alias, entry->d_parent, &entry->d_name))
2683                         continue;
2684                 spin_lock(&alias->d_lock);
2685                 if (!d_unhashed(alias)) {
2686                         spin_unlock(&alias->d_lock);
2687                         alias = NULL;
2688                 } else {
2689                         __dget_dlock(alias);
2690                         __d_rehash(alias);
2691                         spin_unlock(&alias->d_lock);
2692                 }
2693                 spin_unlock(&inode->i_lock);
2694                 return alias;
2695         }
2696         spin_unlock(&inode->i_lock);
2697         return NULL;
2698 }
2699 EXPORT_SYMBOL(d_exact_alias);
2700
2701 /**
2702  * dentry_update_name_case - update case insensitive dentry with a new name
2703  * @dentry: dentry to be updated
2704  * @name: new name
2705  *
2706  * Update a case insensitive dentry with new case of name.
2707  *
2708  * dentry must have been returned by d_lookup with name @name. Old and new
2709  * name lengths must match (ie. no d_compare which allows mismatched name
2710  * lengths).
2711  *
2712  * Parent inode i_mutex must be held over d_lookup and into this call (to
2713  * keep renames and concurrent inserts, and readdir(2) away).
2714  */
2715 void dentry_update_name_case(struct dentry *dentry, const struct qstr *name)
2716 {
2717         BUG_ON(!inode_is_locked(dentry->d_parent->d_inode));
2718         BUG_ON(dentry->d_name.len != name->len); /* d_lookup gives this */
2719
2720         spin_lock(&dentry->d_lock);
2721         write_seqcount_begin(&dentry->d_seq);
2722         memcpy((unsigned char *)dentry->d_name.name, name->name, name->len);
2723         write_seqcount_end(&dentry->d_seq);
2724         spin_unlock(&dentry->d_lock);
2725 }
2726 EXPORT_SYMBOL(dentry_update_name_case);
2727
2728 static void swap_names(struct dentry *dentry, struct dentry *target)
2729 {
2730         if (unlikely(dname_external(target))) {
2731                 if (unlikely(dname_external(dentry))) {
2732                         /*
2733                          * Both external: swap the pointers
2734                          */
2735                         swap(target->d_name.name, dentry->d_name.name);
2736                 } else {
2737                         /*
2738                          * dentry:internal, target:external.  Steal target's
2739                          * storage and make target internal.
2740                          */
2741                         memcpy(target->d_iname, dentry->d_name.name,
2742                                         dentry->d_name.len + 1);
2743                         dentry->d_name.name = target->d_name.name;
2744                         target->d_name.name = target->d_iname;
2745                 }
2746         } else {
2747                 if (unlikely(dname_external(dentry))) {
2748                         /*
2749                          * dentry:external, target:internal.  Give dentry's
2750                          * storage to target and make dentry internal
2751                          */
2752                         memcpy(dentry->d_iname, target->d_name.name,
2753                                         target->d_name.len + 1);
2754                         target->d_name.name = dentry->d_name.name;
2755                         dentry->d_name.name = dentry->d_iname;
2756                 } else {
2757                         /*
2758                          * Both are internal.
2759                          */
2760                         unsigned int i;
2761                         BUILD_BUG_ON(!IS_ALIGNED(DNAME_INLINE_LEN, sizeof(long)));
2762                         for (i = 0; i < DNAME_INLINE_LEN / sizeof(long); i++) {
2763                                 swap(((long *) &dentry->d_iname)[i],
2764                                      ((long *) &target->d_iname)[i]);
2765                         }
2766                 }
2767         }
2768         swap(dentry->d_name.hash_len, target->d_name.hash_len);
2769 }
2770
2771 static void copy_name(struct dentry *dentry, struct dentry *target)
2772 {
2773         struct external_name *old_name = NULL;
2774         if (unlikely(dname_external(dentry)))
2775                 old_name = external_name(dentry);
2776         if (unlikely(dname_external(target))) {
2777                 atomic_inc(&external_name(target)->u.count);
2778                 dentry->d_name = target->d_name;
2779         } else {
2780                 memcpy(dentry->d_iname, target->d_name.name,
2781                                 target->d_name.len + 1);
2782                 dentry->d_name.name = dentry->d_iname;
2783                 dentry->d_name.hash_len = target->d_name.hash_len;
2784         }
2785         if (old_name && likely(atomic_dec_and_test(&old_name->u.count)))
2786                 kfree_rcu(old_name, u.head);
2787 }
2788
2789 static void dentry_lock_for_move(struct dentry *dentry, struct dentry *target)
2790 {
2791         /*
2792          * XXXX: do we really need to take target->d_lock?
2793          */
2794         if (IS_ROOT(dentry) || dentry->d_parent == target->d_parent)
2795                 spin_lock(&target->d_parent->d_lock);
2796         else {
2797                 if (d_ancestor(dentry->d_parent, target->d_parent)) {
2798                         spin_lock(&dentry->d_parent->d_lock);
2799                         spin_lock_nested(&target->d_parent->d_lock,
2800                                                 DENTRY_D_LOCK_NESTED);
2801                 } else {
2802                         spin_lock(&target->d_parent->d_lock);
2803                         spin_lock_nested(&dentry->d_parent->d_lock,
2804                                                 DENTRY_D_LOCK_NESTED);
2805                 }
2806         }
2807         if (target < dentry) {
2808                 spin_lock_nested(&target->d_lock, 2);
2809                 spin_lock_nested(&dentry->d_lock, 3);
2810         } else {
2811                 spin_lock_nested(&dentry->d_lock, 2);
2812                 spin_lock_nested(&target->d_lock, 3);
2813         }
2814 }
2815
2816 static void dentry_unlock_for_move(struct dentry *dentry, struct dentry *target)
2817 {
2818         if (target->d_parent != dentry->d_parent)
2819                 spin_unlock(&dentry->d_parent->d_lock);
2820         if (target->d_parent != target)
2821                 spin_unlock(&target->d_parent->d_lock);
2822         spin_unlock(&target->d_lock);
2823         spin_unlock(&dentry->d_lock);
2824 }
2825
2826 /*
2827  * When switching names, the actual string doesn't strictly have to
2828  * be preserved in the target - because we're dropping the target
2829  * anyway. As such, we can just do a simple memcpy() to copy over
2830  * the new name before we switch, unless we are going to rehash
2831  * it.  Note that if we *do* unhash the target, we are not allowed
2832  * to rehash it without giving it a new name/hash key - whether
2833  * we swap or overwrite the names here, resulting name won't match
2834  * the reality in filesystem; it's only there for d_path() purposes.
2835  * Note that all of this is happening under rename_lock, so the
2836  * any hash lookup seeing it in the middle of manipulations will
2837  * be discarded anyway.  So we do not care what happens to the hash
2838  * key in that case.
2839  */
2840 /*
2841  * __d_move - move a dentry
2842  * @dentry: entry to move
2843  * @target: new dentry
2844  * @exchange: exchange the two dentries
2845  *
2846  * Update the dcache to reflect the move of a file name. Negative
2847  * dcache entries should not be moved in this way. Caller must hold
2848  * rename_lock, the i_mutex of the source and target directories,
2849  * and the sb->s_vfs_rename_mutex if they differ. See lock_rename().
2850  */
2851 static void __d_move(struct dentry *dentry, struct dentry *target,
2852                      bool exchange)
2853 {
2854         struct inode *dir = NULL;
2855         unsigned n;
2856         if (!dentry->d_inode)
2857                 printk(KERN_WARNING "VFS: moving negative dcache entry\n");
2858
2859         BUG_ON(d_ancestor(dentry, target));
2860         BUG_ON(d_ancestor(target, dentry));
2861
2862         dentry_lock_for_move(dentry, target);
2863         if (unlikely(d_in_lookup(target))) {
2864                 dir = target->d_parent->d_inode;
2865                 n = start_dir_add(dir);
2866                 __d_lookup_done(target);
2867         }
2868
2869         write_seqcount_begin(&dentry->d_seq);
2870         write_seqcount_begin_nested(&target->d_seq, DENTRY_D_LOCK_NESTED);
2871
2872         /* unhash both */
2873         if (!d_unhashed(dentry))
2874                 ___d_drop(dentry);
2875         if (!d_unhashed(target))
2876                 ___d_drop(target);
2877
2878         /* Switch the names.. */
2879         if (exchange)
2880                 swap_names(dentry, target);
2881         else
2882                 copy_name(dentry, target);
2883
2884         /* rehash in new place(s) */
2885         __d_rehash(dentry);
2886         if (exchange)
2887                 __d_rehash(target);
2888         else
2889                 target->d_hash.pprev = NULL;
2890
2891         /* ... and switch them in the tree */
2892         if (IS_ROOT(dentry)) {
2893                 /* splicing a tree */
2894                 dentry->d_flags |= DCACHE_RCUACCESS;
2895                 dentry->d_parent = target->d_parent;
2896                 target->d_parent = target;
2897                 list_del_init(&target->d_child);
2898                 list_move(&dentry->d_child, &dentry->d_parent->d_subdirs);
2899         } else {
2900                 /* swapping two dentries */
2901                 swap(dentry->d_parent, target->d_parent);
2902                 list_move(&target->d_child, &target->d_parent->d_subdirs);
2903                 list_move(&dentry->d_child, &dentry->d_parent->d_subdirs);
2904                 if (exchange)
2905                         fsnotify_update_flags(target);
2906                 fsnotify_update_flags(dentry);
2907         }
2908
2909         write_seqcount_end(&target->d_seq);
2910         write_seqcount_end(&dentry->d_seq);
2911
2912         if (dir)
2913                 end_dir_add(dir, n);
2914         dentry_unlock_for_move(dentry, target);
2915 }
2916
2917 /*
2918  * d_move - move a dentry
2919  * @dentry: entry to move
2920  * @target: new dentry
2921  *
2922  * Update the dcache to reflect the move of a file name. Negative
2923  * dcache entries should not be moved in this way. See the locking
2924  * requirements for __d_move.
2925  */
2926 void d_move(struct dentry *dentry, struct dentry *target)
2927 {
2928         write_seqlock(&rename_lock);
2929         __d_move(dentry, target, false);
2930         write_sequnlock(&rename_lock);
2931 }
2932 EXPORT_SYMBOL(d_move);
2933
2934 /*
2935  * d_exchange - exchange two dentries
2936  * @dentry1: first dentry
2937  * @dentry2: second dentry
2938  */
2939 void d_exchange(struct dentry *dentry1, struct dentry *dentry2)
2940 {
2941         write_seqlock(&rename_lock);
2942
2943         WARN_ON(!dentry1->d_inode);
2944         WARN_ON(!dentry2->d_inode);
2945         WARN_ON(IS_ROOT(dentry1));
2946         WARN_ON(IS_ROOT(dentry2));
2947
2948         __d_move(dentry1, dentry2, true);
2949
2950         write_sequnlock(&rename_lock);
2951 }
2952
2953 /**
2954  * d_ancestor - search for an ancestor
2955  * @p1: ancestor dentry
2956  * @p2: child dentry
2957  *
2958  * Returns the ancestor dentry of p2 which is a child of p1, if p1 is
2959  * an ancestor of p2, else NULL.
2960  */
2961 struct dentry *d_ancestor(struct dentry *p1, struct dentry *p2)
2962 {
2963         struct dentry *p;
2964
2965         for (p = p2; !IS_ROOT(p); p = p->d_parent) {
2966                 if (p->d_parent == p1)
2967                         return p;
2968         }
2969         return NULL;
2970 }
2971
2972 /*
2973  * This helper attempts to cope with remotely renamed directories
2974  *
2975  * It assumes that the caller is already holding
2976  * dentry->d_parent->d_inode->i_mutex, and rename_lock
2977  *
2978  * Note: If ever the locking in lock_rename() changes, then please
2979  * remember to update this too...
2980  */
2981 static int __d_unalias(struct inode *inode,
2982                 struct dentry *dentry, struct dentry *alias)
2983 {
2984         struct mutex *m1 = NULL;
2985         struct rw_semaphore *m2 = NULL;
2986         int ret = -ESTALE;
2987
2988         /* If alias and dentry share a parent, then no extra locks required */
2989         if (alias->d_parent == dentry->d_parent)
2990                 goto out_unalias;
2991
2992         /* See lock_rename() */
2993         if (!mutex_trylock(&dentry->d_sb->s_vfs_rename_mutex))
2994                 goto out_err;
2995         m1 = &dentry->d_sb->s_vfs_rename_mutex;
2996         if (!inode_trylock_shared(alias->d_parent->d_inode))
2997                 goto out_err;
2998         m2 = &alias->d_parent->d_inode->i_rwsem;
2999 out_unalias:
3000         __d_move(alias, dentry, false);
3001         ret = 0;
3002 out_err:
3003         if (m2)
3004                 up_read(m2);
3005         if (m1)
3006                 mutex_unlock(m1);
3007         return ret;
3008 }
3009
3010 /**
3011  * d_splice_alias - splice a disconnected dentry into the tree if one exists
3012  * @inode:  the inode which may have a disconnected dentry
3013  * @dentry: a negative dentry which we want to point to the inode.
3014  *
3015  * If inode is a directory and has an IS_ROOT alias, then d_move that in
3016  * place of the given dentry and return it, else simply d_add the inode
3017  * to the dentry and return NULL.
3018  *
3019  * If a non-IS_ROOT directory is found, the filesystem is corrupt, and
3020  * we should error out: directories can't have multiple aliases.
3021  *
3022  * This is needed in the lookup routine of any filesystem that is exportable
3023  * (via knfsd) so that we can build dcache paths to directories effectively.
3024  *
3025  * If a dentry was found and moved, then it is returned.  Otherwise NULL
3026  * is returned.  This matches the expected return value of ->lookup.
3027  *
3028  * Cluster filesystems may call this function with a negative, hashed dentry.
3029  * In that case, we know that the inode will be a regular file, and also this
3030  * will only occur during atomic_open. So we need to check for the dentry
3031  * being already hashed only in the final case.
3032  */
3033 struct dentry *d_splice_alias(struct inode *inode, struct dentry *dentry)
3034 {
3035         if (IS_ERR(inode))
3036                 return ERR_CAST(inode);
3037
3038         BUG_ON(!d_unhashed(dentry));
3039
3040         if (!inode)
3041                 goto out;
3042
3043         security_d_instantiate(dentry, inode);
3044         spin_lock(&inode->i_lock);
3045         if (S_ISDIR(inode->i_mode)) {
3046                 struct dentry *new = __d_find_any_alias(inode);
3047                 if (unlikely(new)) {
3048                         /* The reference to new ensures it remains an alias */
3049                         spin_unlock(&inode->i_lock);
3050                         write_seqlock(&rename_lock);
3051                         if (unlikely(d_ancestor(new, dentry))) {
3052                                 write_sequnlock(&rename_lock);
3053                                 dput(new);
3054                                 new = ERR_PTR(-ELOOP);
3055                                 pr_warn_ratelimited(
3056                                         "VFS: Lookup of '%s' in %s %s"
3057                                         " would have caused loop\n",
3058                                         dentry->d_name.name,
3059                                         inode->i_sb->s_type->name,
3060                                         inode->i_sb->s_id);
3061                         } else if (!IS_ROOT(new)) {
3062                                 int err = __d_unalias(inode, dentry, new);
3063                                 write_sequnlock(&rename_lock);
3064                                 if (err) {
3065                                         dput(new);
3066                                         new = ERR_PTR(err);
3067                                 }
3068                         } else {
3069                                 __d_move(new, dentry, false);
3070                                 write_sequnlock(&rename_lock);
3071                         }
3072                         iput(inode);
3073                         return new;
3074                 }
3075         }
3076 out:
3077         __d_add(dentry, inode);
3078         return NULL;
3079 }
3080 EXPORT_SYMBOL(d_splice_alias);
3081
3082 static int prepend(char **buffer, int *buflen, const char *str, int namelen)
3083 {
3084         *buflen -= namelen;
3085         if (*buflen < 0)
3086                 return -ENAMETOOLONG;
3087         *buffer -= namelen;
3088         memcpy(*buffer, str, namelen);
3089         return 0;
3090 }
3091
3092 /**
3093  * prepend_name - prepend a pathname in front of current buffer pointer
3094  * @buffer: buffer pointer
3095  * @buflen: allocated length of the buffer
3096  * @name:   name string and length qstr structure
3097  *
3098  * With RCU path tracing, it may race with d_move(). Use READ_ONCE() to
3099  * make sure that either the old or the new name pointer and length are
3100  * fetched. However, there may be mismatch between length and pointer.
3101  * The length cannot be trusted, we need to copy it byte-by-byte until
3102  * the length is reached or a null byte is found. It also prepends "/" at
3103  * the beginning of the name. The sequence number check at the caller will
3104  * retry it again when a d_move() does happen. So any garbage in the buffer
3105  * due to mismatched pointer and length will be discarded.
3106  *
3107  * Load acquire is needed to make sure that we see that terminating NUL.
3108  */
3109 static int prepend_name(char **buffer, int *buflen, const struct qstr *name)
3110 {
3111         const char *dname = smp_load_acquire(&name->name); /* ^^^ */
3112         u32 dlen = READ_ONCE(name->len);
3113         char *p;
3114
3115         *buflen -= dlen + 1;
3116         if (*buflen < 0)
3117                 return -ENAMETOOLONG;
3118         p = *buffer -= dlen + 1;
3119         *p++ = '/';
3120         while (dlen--) {
3121                 char c = *dname++;
3122                 if (!c)
3123                         break;
3124                 *p++ = c;
3125         }
3126         return 0;
3127 }
3128
3129 /**
3130  * prepend_path - Prepend path string to a buffer
3131  * @path: the dentry/vfsmount to report
3132  * @root: root vfsmnt/dentry
3133  * @buffer: pointer to the end of the buffer
3134  * @buflen: pointer to buffer length
3135  *
3136  * The function will first try to write out the pathname without taking any
3137  * lock other than the RCU read lock to make sure that dentries won't go away.
3138  * It only checks the sequence number of the global rename_lock as any change
3139  * in the dentry's d_seq will be preceded by changes in the rename_lock
3140  * sequence number. If the sequence number had been changed, it will restart
3141  * the whole pathname back-tracing sequence again by taking the rename_lock.
3142  * In this case, there is no need to take the RCU read lock as the recursive
3143  * parent pointer references will keep the dentry chain alive as long as no
3144  * rename operation is performed.
3145  */
3146 static int prepend_path(const struct path *path,
3147                         const struct path *root,
3148                         char **buffer, int *buflen)
3149 {
3150         struct dentry *dentry;
3151         struct vfsmount *vfsmnt;
3152         struct mount *mnt;
3153         int error = 0;
3154         unsigned seq, m_seq = 0;
3155         char *bptr;
3156         int blen;
3157
3158         rcu_read_lock();
3159 restart_mnt:
3160         read_seqbegin_or_lock(&mount_lock, &m_seq);
3161         seq = 0;
3162         rcu_read_lock();
3163 restart:
3164         bptr = *buffer;
3165         blen = *buflen;
3166         error = 0;
3167         dentry = path->dentry;
3168         vfsmnt = path->mnt;
3169         mnt = real_mount(vfsmnt);
3170         read_seqbegin_or_lock(&rename_lock, &seq);
3171         while (dentry != root->dentry || vfsmnt != root->mnt) {
3172                 struct dentry * parent;
3173
3174                 if (dentry == vfsmnt->mnt_root || IS_ROOT(dentry)) {
3175                         struct mount *parent = READ_ONCE(mnt->mnt_parent);
3176                         /* Escaped? */
3177                         if (dentry != vfsmnt->mnt_root) {
3178                                 bptr = *buffer;
3179                                 blen = *buflen;
3180                                 error = 3;
3181                                 break;
3182                         }
3183                         /* Global root? */
3184                         if (mnt != parent) {
3185                                 dentry = READ_ONCE(mnt->mnt_mountpoint);
3186                                 mnt = parent;
3187                                 vfsmnt = &mnt->mnt;
3188                                 continue;
3189                         }
3190                         if (!error)
3191                                 error = is_mounted(vfsmnt) ? 1 : 2;
3192                         break;
3193                 }
3194                 parent = dentry->d_parent;
3195                 prefetch(parent);
3196                 error = prepend_name(&bptr, &blen, &dentry->d_name);
3197                 if (error)
3198                         break;
3199
3200                 dentry = parent;
3201         }
3202         if (!(seq & 1))
3203                 rcu_read_unlock();
3204         if (need_seqretry(&rename_lock, seq)) {
3205                 seq = 1;
3206                 goto restart;
3207         }
3208         done_seqretry(&rename_lock, seq);
3209
3210         if (!(m_seq & 1))
3211                 rcu_read_unlock();
3212         if (need_seqretry(&mount_lock, m_seq)) {
3213                 m_seq = 1;
3214                 goto restart_mnt;
3215         }
3216         done_seqretry(&mount_lock, m_seq);
3217
3218         if (error >= 0 && bptr == *buffer) {
3219                 if (--blen < 0)
3220                         error = -ENAMETOOLONG;
3221                 else
3222                         *--bptr = '/';
3223         }
3224         *buffer = bptr;
3225         *buflen = blen;
3226         return error;
3227 }
3228
3229 /**
3230  * __d_path - return the path of a dentry
3231  * @path: the dentry/vfsmount to report
3232  * @root: root vfsmnt/dentry
3233  * @buf: buffer to return value in
3234  * @buflen: buffer length
3235  *
3236  * Convert a dentry into an ASCII path name.
3237  *
3238  * Returns a pointer into the buffer or an error code if the
3239  * path was too long.
3240  *
3241  * "buflen" should be positive.
3242  *
3243  * If the path is not reachable from the supplied root, return %NULL.
3244  */
3245 char *__d_path(const struct path *path,
3246                const struct path *root,
3247                char *buf, int buflen)
3248 {
3249         char *res = buf + buflen;
3250         int error;
3251
3252         prepend(&res, &buflen, "\0", 1);
3253         error = prepend_path(path, root, &res, &buflen);
3254
3255         if (error < 0)
3256                 return ERR_PTR(error);
3257         if (error > 0)
3258                 return NULL;
3259         return res;
3260 }
3261
3262 char *d_absolute_path(const struct path *path,
3263                char *buf, int buflen)
3264 {
3265         struct path root = {};
3266         char *res = buf + buflen;
3267         int error;
3268
3269         prepend(&res, &buflen, "\0", 1);
3270         error = prepend_path(path, &root, &res, &buflen);
3271
3272         if (error > 1)
3273                 error = -EINVAL;
3274         if (error < 0)
3275                 return ERR_PTR(error);
3276         return res;
3277 }
3278
3279 /*
3280  * same as __d_path but appends "(deleted)" for unlinked files.
3281  */
3282 static int path_with_deleted(const struct path *path,
3283                              const struct path *root,
3284                              char **buf, int *buflen)
3285 {
3286         prepend(buf, buflen, "\0", 1);
3287         if (d_unlinked(path->dentry)) {
3288                 int error = prepend(buf, buflen, " (deleted)", 10);
3289                 if (error)
3290                         return error;
3291         }
3292
3293         return prepend_path(path, root, buf, buflen);
3294 }
3295
3296 static int prepend_unreachable(char **buffer, int *buflen)
3297 {
3298         return prepend(buffer, buflen, "(unreachable)", 13);
3299 }
3300
3301 static void get_fs_root_rcu(struct fs_struct *fs, struct path *root)
3302 {
3303         unsigned seq;
3304
3305         do {
3306                 seq = read_seqcount_begin(&fs->seq);
3307                 *root = fs->root;
3308         } while (read_seqcount_retry(&fs->seq, seq));
3309 }
3310
3311 /**
3312  * d_path - return the path of a dentry
3313  * @path: path to report
3314  * @buf: buffer to return value in
3315  * @buflen: buffer length
3316  *
3317  * Convert a dentry into an ASCII path name. If the entry has been deleted
3318  * the string " (deleted)" is appended. Note that this is ambiguous.
3319  *
3320  * Returns a pointer into the buffer or an error code if the path was
3321  * too long. Note: Callers should use the returned pointer, not the passed
3322  * in buffer, to use the name! The implementation often starts at an offset
3323  * into the buffer, and may leave 0 bytes at the start.
3324  *
3325  * "buflen" should be positive.
3326  */
3327 char *d_path(const struct path *path, char *buf, int buflen)
3328 {
3329         char *res = buf + buflen;
3330         struct path root;
3331         int error;
3332
3333         /*
3334          * We have various synthetic filesystems that never get mounted.  On
3335          * these filesystems dentries are never used for lookup purposes, and
3336          * thus don't need to be hashed.  They also don't need a name until a
3337          * user wants to identify the object in /proc/pid/fd/.  The little hack
3338          * below allows us to generate a name for these objects on demand:
3339          *
3340          * Some pseudo inodes are mountable.  When they are mounted
3341          * path->dentry == path->mnt->mnt_root.  In that case don't call d_dname
3342          * and instead have d_path return the mounted path.
3343          */
3344         if (path->dentry->d_op && path->dentry->d_op->d_dname &&
3345             (!IS_ROOT(path->dentry) || path->dentry != path->mnt->mnt_root))
3346                 return path->dentry->d_op->d_dname(path->dentry, buf, buflen);
3347
3348         rcu_read_lock();
3349         get_fs_root_rcu(current->fs, &root);
3350         error = path_with_deleted(path, &root, &res, &buflen);
3351         rcu_read_unlock();
3352
3353         if (error < 0)
3354                 res = ERR_PTR(error);
3355         return res;
3356 }
3357 EXPORT_SYMBOL(d_path);
3358
3359 /*
3360  * Helper function for dentry_operations.d_dname() members
3361  */
3362 char *dynamic_dname(struct dentry *dentry, char *buffer, int buflen,
3363                         const char *fmt, ...)
3364 {
3365         va_list args;
3366         char temp[64];
3367         int sz;
3368
3369         va_start(args, fmt);
3370         sz = vsnprintf(temp, sizeof(temp), fmt, args) + 1;
3371         va_end(args);
3372
3373         if (sz > sizeof(temp) || sz > buflen)
3374                 return ERR_PTR(-ENAMETOOLONG);
3375
3376         buffer += buflen - sz;
3377         return memcpy(buffer, temp, sz);
3378 }
3379
3380 char *simple_dname(struct dentry *dentry, char *buffer, int buflen)
3381 {
3382         char *end = buffer + buflen;
3383         /* these dentries are never renamed, so d_lock is not needed */
3384         if (prepend(&end, &buflen, " (deleted)", 11) ||
3385             prepend(&end, &buflen, dentry->d_name.name, dentry->d_name.len) ||
3386             prepend(&end, &buflen, "/", 1))  
3387                 end = ERR_PTR(-ENAMETOOLONG);
3388         return end;
3389 }
3390 EXPORT_SYMBOL(simple_dname);
3391
3392 /*
3393  * Write full pathname from the root of the filesystem into the buffer.
3394  */
3395 static char *__dentry_path(struct dentry *d, char *buf, int buflen)
3396 {
3397         struct dentry *dentry;
3398         char *end, *retval;
3399         int len, seq = 0;
3400         int error = 0;
3401
3402         if (buflen < 2)
3403                 goto Elong;
3404
3405         rcu_read_lock();
3406 restart:
3407         dentry = d;
3408         end = buf + buflen;
3409         len = buflen;
3410         prepend(&end, &len, "\0", 1);
3411         /* Get '/' right */
3412         retval = end-1;
3413         *retval = '/';
3414         read_seqbegin_or_lock(&rename_lock, &seq);
3415         while (!IS_ROOT(dentry)) {
3416                 struct dentry *parent = dentry->d_parent;
3417
3418                 prefetch(parent);
3419                 error = prepend_name(&end, &len, &dentry->d_name);
3420                 if (error)
3421                         break;
3422
3423                 retval = end;
3424                 dentry = parent;
3425         }
3426         if (!(seq & 1))
3427                 rcu_read_unlock();
3428         if (need_seqretry(&rename_lock, seq)) {
3429                 seq = 1;
3430                 goto restart;
3431         }
3432         done_seqretry(&rename_lock, seq);
3433         if (error)
3434                 goto Elong;
3435         return retval;
3436 Elong:
3437         return ERR_PTR(-ENAMETOOLONG);
3438 }
3439
3440 char *dentry_path_raw(struct dentry *dentry, char *buf, int buflen)
3441 {
3442         return __dentry_path(dentry, buf, buflen);
3443 }
3444 EXPORT_SYMBOL(dentry_path_raw);
3445
3446 char *dentry_path(struct dentry *dentry, char *buf, int buflen)
3447 {
3448         char *p = NULL;
3449         char *retval;
3450
3451         if (d_unlinked(dentry)) {
3452                 p = buf + buflen;
3453                 if (prepend(&p, &buflen, "//deleted", 10) != 0)
3454                         goto Elong;
3455                 buflen++;
3456         }
3457         retval = __dentry_path(dentry, buf, buflen);
3458         if (!IS_ERR(retval) && p)
3459                 *p = '/';       /* restore '/' overriden with '\0' */
3460         return retval;
3461 Elong:
3462         return ERR_PTR(-ENAMETOOLONG);
3463 }
3464
3465 static void get_fs_root_and_pwd_rcu(struct fs_struct *fs, struct path *root,
3466                                     struct path *pwd)
3467 {
3468         unsigned seq;
3469
3470         do {
3471                 seq = read_seqcount_begin(&fs->seq);
3472                 *root = fs->root;
3473                 *pwd = fs->pwd;
3474         } while (read_seqcount_retry(&fs->seq, seq));
3475 }
3476
3477 /*
3478  * NOTE! The user-level library version returns a
3479  * character pointer. The kernel system call just
3480  * returns the length of the buffer filled (which
3481  * includes the ending '\0' character), or a negative
3482  * error value. So libc would do something like
3483  *
3484  *      char *getcwd(char * buf, size_t size)
3485  *      {
3486  *              int retval;
3487  *
3488  *              retval = sys_getcwd(buf, size);
3489  *              if (retval >= 0)
3490  *                      return buf;
3491  *              errno = -retval;
3492  *              return NULL;
3493  *      }
3494  */
3495 SYSCALL_DEFINE2(getcwd, char __user *, buf, unsigned long, size)
3496 {
3497         int error;
3498         struct path pwd, root;
3499         char *page = __getname();
3500
3501         if (!page)
3502                 return -ENOMEM;
3503
3504         rcu_read_lock();
3505         get_fs_root_and_pwd_rcu(current->fs, &root, &pwd);
3506
3507         error = -ENOENT;
3508         if (!d_unlinked(pwd.dentry)) {
3509                 unsigned long len;
3510                 char *cwd = page + PATH_MAX;
3511                 int buflen = PATH_MAX;
3512
3513                 prepend(&cwd, &buflen, "\0", 1);
3514                 error = prepend_path(&pwd, &root, &cwd, &buflen);
3515                 rcu_read_unlock();
3516
3517                 if (error < 0)
3518                         goto out;
3519
3520                 /* Unreachable from current root */
3521                 if (error > 0) {
3522                         error = prepend_unreachable(&cwd, &buflen);
3523                         if (error)
3524                                 goto out;
3525                 }
3526
3527                 error = -ERANGE;
3528                 len = PATH_MAX + page - cwd;
3529                 if (len <= size) {
3530                         error = len;
3531                         if (copy_to_user(buf, cwd, len))
3532                                 error = -EFAULT;
3533                 }
3534         } else {
3535                 rcu_read_unlock();
3536         }
3537
3538 out:
3539         __putname(page);
3540         return error;
3541 }
3542
3543 /*
3544  * Test whether new_dentry is a subdirectory of old_dentry.
3545  *
3546  * Trivially implemented using the dcache structure
3547  */
3548
3549 /**
3550  * is_subdir - is new dentry a subdirectory of old_dentry
3551  * @new_dentry: new dentry
3552  * @old_dentry: old dentry
3553  *
3554  * Returns true if new_dentry is a subdirectory of the parent (at any depth).
3555  * Returns false otherwise.
3556  * Caller must ensure that "new_dentry" is pinned before calling is_subdir()
3557  */
3558   
3559 bool is_subdir(struct dentry *new_dentry, struct dentry *old_dentry)
3560 {
3561         bool result;
3562         unsigned seq;
3563
3564         if (new_dentry == old_dentry)
3565                 return true;
3566
3567         do {
3568                 /* for restarting inner loop in case of seq retry */
3569                 seq = read_seqbegin(&rename_lock);
3570                 /*
3571                  * Need rcu_readlock to protect against the d_parent trashing
3572                  * due to d_move
3573                  */
3574                 rcu_read_lock();
3575                 if (d_ancestor(old_dentry, new_dentry))
3576                         result = true;
3577                 else
3578                         result = false;
3579                 rcu_read_unlock();
3580         } while (read_seqretry(&rename_lock, seq));
3581
3582         return result;
3583 }
3584 EXPORT_SYMBOL(is_subdir);
3585
3586 static enum d_walk_ret d_genocide_kill(void *data, struct dentry *dentry)
3587 {
3588         struct dentry *root = data;
3589         if (dentry != root) {
3590                 if (d_unhashed(dentry) || !dentry->d_inode)
3591                         return D_WALK_SKIP;
3592
3593                 if (!(dentry->d_flags & DCACHE_GENOCIDE)) {
3594                         dentry->d_flags |= DCACHE_GENOCIDE;
3595                         dentry->d_lockref.count--;
3596                 }
3597         }
3598         return D_WALK_CONTINUE;
3599 }
3600
3601 void d_genocide(struct dentry *parent)
3602 {
3603         d_walk(parent, parent, d_genocide_kill, NULL);
3604 }
3605
3606 void d_tmpfile(struct dentry *dentry, struct inode *inode)
3607 {
3608         inode_dec_link_count(inode);
3609         BUG_ON(dentry->d_name.name != dentry->d_iname ||
3610                 !hlist_unhashed(&dentry->d_u.d_alias) ||
3611                 !d_unlinked(dentry));
3612         spin_lock(&dentry->d_parent->d_lock);
3613         spin_lock_nested(&dentry->d_lock, DENTRY_D_LOCK_NESTED);
3614         dentry->d_name.len = sprintf(dentry->d_iname, "#%llu",
3615                                 (unsigned long long)inode->i_ino);
3616         spin_unlock(&dentry->d_lock);
3617         spin_unlock(&dentry->d_parent->d_lock);
3618         d_instantiate(dentry, inode);
3619 }
3620 EXPORT_SYMBOL(d_tmpfile);
3621
3622 static __initdata unsigned long dhash_entries;
3623 static int __init set_dhash_entries(char *str)
3624 {
3625         if (!str)
3626                 return 0;
3627         dhash_entries = simple_strtoul(str, &str, 0);
3628         return 1;
3629 }
3630 __setup("dhash_entries=", set_dhash_entries);
3631
3632 static void __init dcache_init_early(void)
3633 {
3634         /* If hashes are distributed across NUMA nodes, defer
3635          * hash allocation until vmalloc space is available.
3636          */
3637         if (hashdist)
3638                 return;
3639
3640         dentry_hashtable =
3641                 alloc_large_system_hash("Dentry cache",
3642                                         sizeof(struct hlist_bl_head),
3643                                         dhash_entries,
3644                                         13,
3645                                      &