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