blob: 6068c25b393ca21f5faf8c9ca1fdf8d6051fc836 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
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
Linus Torvalds1da177e2005-04-16 15:20:36 -070017#include <linux/syscalls.h>
18#include <linux/string.h>
19#include <linux/mm.h>
Miklos Szeredi31f3e0b2008-06-23 18:11:52 +020020#include <linux/fdtable.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070021#include <linux/fs.h>
John McCutchan7a91bf72005-08-08 13:52:16 -040022#include <linux/fsnotify.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070023#include <linux/slab.h>
24#include <linux/init.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070025#include <linux/hash.h>
26#include <linux/cache.h>
27#include <linux/module.h>
28#include <linux/mount.h>
29#include <linux/file.h>
30#include <asm/uaccess.h>
31#include <linux/security.h>
32#include <linux/seqlock.h>
33#include <linux/swap.h>
34#include <linux/bootmem.h>
David Howells07f3f05c2006-09-30 20:52:18 +020035#include "internal.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070036
Linus Torvalds1da177e2005-04-16 15:20:36 -070037
Eric Dumazetfa3536c2006-03-26 01:37:24 -080038int sysctl_vfs_cache_pressure __read_mostly = 100;
Linus Torvalds1da177e2005-04-16 15:20:36 -070039EXPORT_SYMBOL_GPL(sysctl_vfs_cache_pressure);
40
41 __cacheline_aligned_in_smp DEFINE_SPINLOCK(dcache_lock);
Al Viro74c3cbe2007-07-22 08:04:18 -040042__cacheline_aligned_in_smp DEFINE_SEQLOCK(rename_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -070043
44EXPORT_SYMBOL(dcache_lock);
45
Christoph Lametere18b8902006-12-06 20:33:20 -080046static struct kmem_cache *dentry_cache __read_mostly;
Linus Torvalds1da177e2005-04-16 15:20:36 -070047
48#define DNAME_INLINE_LEN (sizeof(struct dentry)-offsetof(struct dentry,d_iname))
49
50/*
51 * This is the single most critical data structure when it comes
52 * to the dcache: the hashtable for lookups. Somebody should try
53 * to make this good - I've just made it work.
54 *
55 * This hash-function tries to avoid losing too many bits of hash
56 * information, yet avoid using a prime hash-size or similar.
57 */
58#define D_HASHBITS d_hash_shift
59#define D_HASHMASK d_hash_mask
60
Eric Dumazetfa3536c2006-03-26 01:37:24 -080061static unsigned int d_hash_mask __read_mostly;
62static unsigned int d_hash_shift __read_mostly;
63static struct hlist_head *dentry_hashtable __read_mostly;
Linus Torvalds1da177e2005-04-16 15:20:36 -070064static LIST_HEAD(dentry_unused);
65
66/* Statistics gathering. */
67struct dentry_stat_t dentry_stat = {
68 .age_limit = 45,
69};
70
Eric Dumazetb3423412006-12-06 20:38:48 -080071static void __d_free(struct dentry *dentry)
Linus Torvalds1da177e2005-04-16 15:20:36 -070072{
Linus Torvalds1da177e2005-04-16 15:20:36 -070073 if (dname_external(dentry))
74 kfree(dentry->d_name.name);
75 kmem_cache_free(dentry_cache, dentry);
76}
77
Eric Dumazetb3423412006-12-06 20:38:48 -080078static void d_callback(struct rcu_head *head)
79{
80 struct dentry * dentry = container_of(head, struct dentry, d_u.d_rcu);
81 __d_free(dentry);
82}
83
Linus Torvalds1da177e2005-04-16 15:20:36 -070084/*
85 * no dcache_lock, please. The caller must decrement dentry_stat.nr_dentry
86 * inside dcache_lock.
87 */
88static void d_free(struct dentry *dentry)
89{
90 if (dentry->d_op && dentry->d_op->d_release)
91 dentry->d_op->d_release(dentry);
Eric Dumazetb3423412006-12-06 20:38:48 -080092 /* if dentry was never inserted into hash, immediate free is OK */
Akinobu Mitae8462ca2008-02-06 01:37:07 -080093 if (hlist_unhashed(&dentry->d_hash))
Eric Dumazetb3423412006-12-06 20:38:48 -080094 __d_free(dentry);
95 else
96 call_rcu(&dentry->d_u.d_rcu, d_callback);
Linus Torvalds1da177e2005-04-16 15:20:36 -070097}
98
Christoph Lameter4a0962a2008-02-14 19:38:45 -080099static void dentry_lru_remove(struct dentry *dentry)
100{
101 if (!list_empty(&dentry->d_lru)) {
102 list_del_init(&dentry->d_lru);
103 dentry_stat.nr_unused--;
104 }
105}
106
Linus Torvalds1da177e2005-04-16 15:20:36 -0700107/*
108 * Release the dentry's inode, using the filesystem
109 * d_iput() operation if defined.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700110 */
Arjan van de Ven858119e2006-01-14 13:20:43 -0800111static void dentry_iput(struct dentry * dentry)
Miklos Szeredi31f3e0b2008-06-23 18:11:52 +0200112 __releases(dentry->d_lock)
113 __releases(dcache_lock)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700114{
115 struct inode *inode = dentry->d_inode;
116 if (inode) {
117 dentry->d_inode = NULL;
118 list_del_init(&dentry->d_alias);
119 spin_unlock(&dentry->d_lock);
120 spin_unlock(&dcache_lock);
Linus Torvaldsf805fbd2005-09-19 19:54:29 -0700121 if (!inode->i_nlink)
122 fsnotify_inoderemove(inode);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700123 if (dentry->d_op && dentry->d_op->d_iput)
124 dentry->d_op->d_iput(dentry, inode);
125 else
126 iput(inode);
127 } else {
128 spin_unlock(&dentry->d_lock);
129 spin_unlock(&dcache_lock);
130 }
131}
132
Miklos Szeredid52b9082007-05-08 00:23:46 -0700133/**
134 * d_kill - kill dentry and return parent
135 * @dentry: dentry to kill
136 *
Miklos Szeredi31f3e0b2008-06-23 18:11:52 +0200137 * The dentry must already be unhashed and removed from the LRU.
Miklos Szeredid52b9082007-05-08 00:23:46 -0700138 *
139 * If this is the root of the dentry tree, return NULL.
140 */
141static struct dentry *d_kill(struct dentry *dentry)
Miklos Szeredi31f3e0b2008-06-23 18:11:52 +0200142 __releases(dentry->d_lock)
143 __releases(dcache_lock)
Miklos Szeredid52b9082007-05-08 00:23:46 -0700144{
145 struct dentry *parent;
146
147 list_del(&dentry->d_u.d_child);
148 dentry_stat.nr_dentry--; /* For d_free, below */
149 /*drops the locks, at that point nobody can reach this dentry */
150 dentry_iput(dentry);
151 parent = dentry->d_parent;
152 d_free(dentry);
153 return dentry == parent ? NULL : parent;
154}
155
Linus Torvalds1da177e2005-04-16 15:20:36 -0700156/*
157 * This is dput
158 *
159 * This is complicated by the fact that we do not want to put
160 * dentries that are no longer on any hash chain on the unused
161 * list: we'd much rather just get rid of them immediately.
162 *
163 * However, that implies that we have to traverse the dentry
164 * tree upwards to the parents which might _also_ now be
165 * scheduled for deletion (it may have been only waiting for
166 * its last child to go away).
167 *
168 * This tail recursion is done by hand as we don't want to depend
169 * on the compiler to always get this right (gcc generally doesn't).
170 * Real recursion would eat up our stack space.
171 */
172
173/*
174 * dput - release a dentry
175 * @dentry: dentry to release
176 *
177 * Release a dentry. This will drop the usage count and if appropriate
178 * call the dentry unlink method as well as removing it from the queues and
179 * releasing its resources. If the parent dentries were scheduled for release
180 * they too may now get deleted.
181 *
182 * no dcache lock, please.
183 */
184
185void dput(struct dentry *dentry)
186{
187 if (!dentry)
188 return;
189
190repeat:
191 if (atomic_read(&dentry->d_count) == 1)
192 might_sleep();
193 if (!atomic_dec_and_lock(&dentry->d_count, &dcache_lock))
194 return;
195
196 spin_lock(&dentry->d_lock);
197 if (atomic_read(&dentry->d_count)) {
198 spin_unlock(&dentry->d_lock);
199 spin_unlock(&dcache_lock);
200 return;
201 }
202
203 /*
204 * AV: ->d_delete() is _NOT_ allowed to block now.
205 */
206 if (dentry->d_op && dentry->d_op->d_delete) {
207 if (dentry->d_op->d_delete(dentry))
208 goto unhash_it;
209 }
210 /* Unreachable? Get rid of it */
211 if (d_unhashed(dentry))
212 goto kill_it;
213 if (list_empty(&dentry->d_lru)) {
214 dentry->d_flags |= DCACHE_REFERENCED;
215 list_add(&dentry->d_lru, &dentry_unused);
216 dentry_stat.nr_unused++;
217 }
218 spin_unlock(&dentry->d_lock);
219 spin_unlock(&dcache_lock);
220 return;
221
222unhash_it:
223 __d_drop(dentry);
Miklos Szeredid52b9082007-05-08 00:23:46 -0700224kill_it:
Christoph Lameter4a0962a2008-02-14 19:38:45 -0800225 dentry_lru_remove(dentry);
Miklos Szeredid52b9082007-05-08 00:23:46 -0700226 dentry = d_kill(dentry);
227 if (dentry)
228 goto repeat;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700229}
230
231/**
232 * d_invalidate - invalidate a dentry
233 * @dentry: dentry to invalidate
234 *
235 * Try to invalidate the dentry if it turns out to be
236 * possible. If there are other dentries that can be
237 * reached through this one we can't delete it and we
238 * return -EBUSY. On success we return 0.
239 *
240 * no dcache lock.
241 */
242
243int d_invalidate(struct dentry * dentry)
244{
245 /*
246 * If it's already been dropped, return OK.
247 */
248 spin_lock(&dcache_lock);
249 if (d_unhashed(dentry)) {
250 spin_unlock(&dcache_lock);
251 return 0;
252 }
253 /*
254 * Check whether to do a partial shrink_dcache
255 * to get rid of unused child entries.
256 */
257 if (!list_empty(&dentry->d_subdirs)) {
258 spin_unlock(&dcache_lock);
259 shrink_dcache_parent(dentry);
260 spin_lock(&dcache_lock);
261 }
262
263 /*
264 * Somebody else still using it?
265 *
266 * If it's a directory, we can't drop it
267 * for fear of somebody re-populating it
268 * with children (even though dropping it
269 * would make it unreachable from the root,
270 * we might still populate it if it was a
271 * working directory or similar).
272 */
273 spin_lock(&dentry->d_lock);
274 if (atomic_read(&dentry->d_count) > 1) {
275 if (dentry->d_inode && S_ISDIR(dentry->d_inode->i_mode)) {
276 spin_unlock(&dentry->d_lock);
277 spin_unlock(&dcache_lock);
278 return -EBUSY;
279 }
280 }
281
282 __d_drop(dentry);
283 spin_unlock(&dentry->d_lock);
284 spin_unlock(&dcache_lock);
285 return 0;
286}
287
288/* This should be called _only_ with dcache_lock held */
289
290static inline struct dentry * __dget_locked(struct dentry *dentry)
291{
292 atomic_inc(&dentry->d_count);
Christoph Lameter4a0962a2008-02-14 19:38:45 -0800293 dentry_lru_remove(dentry);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700294 return dentry;
295}
296
297struct dentry * dget_locked(struct dentry *dentry)
298{
299 return __dget_locked(dentry);
300}
301
302/**
303 * d_find_alias - grab a hashed alias of inode
304 * @inode: inode in question
305 * @want_discon: flag, used by d_splice_alias, to request
306 * that only a DISCONNECTED alias be returned.
307 *
308 * If inode has a hashed alias, or is a directory and has any alias,
309 * acquire the reference to alias and return it. Otherwise return NULL.
310 * Notice that if inode is a directory there can be only one alias and
311 * it can be unhashed only if it has no children, or if it is the root
312 * of a filesystem.
313 *
NeilBrown21c0d8f2006-10-04 02:16:16 -0700314 * If the inode has an IS_ROOT, DCACHE_DISCONNECTED alias, then prefer
Linus Torvalds1da177e2005-04-16 15:20:36 -0700315 * any other hashed alias over that one unless @want_discon is set,
NeilBrown21c0d8f2006-10-04 02:16:16 -0700316 * in which case only return an IS_ROOT, DCACHE_DISCONNECTED alias.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700317 */
318
319static struct dentry * __d_find_alias(struct inode *inode, int want_discon)
320{
321 struct list_head *head, *next, *tmp;
322 struct dentry *alias, *discon_alias=NULL;
323
324 head = &inode->i_dentry;
325 next = inode->i_dentry.next;
326 while (next != head) {
327 tmp = next;
328 next = tmp->next;
329 prefetch(next);
330 alias = list_entry(tmp, struct dentry, d_alias);
331 if (S_ISDIR(inode->i_mode) || !d_unhashed(alias)) {
NeilBrown21c0d8f2006-10-04 02:16:16 -0700332 if (IS_ROOT(alias) &&
333 (alias->d_flags & DCACHE_DISCONNECTED))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700334 discon_alias = alias;
335 else if (!want_discon) {
336 __dget_locked(alias);
337 return alias;
338 }
339 }
340 }
341 if (discon_alias)
342 __dget_locked(discon_alias);
343 return discon_alias;
344}
345
346struct dentry * d_find_alias(struct inode *inode)
347{
David Howells214fda12006-03-25 03:06:36 -0800348 struct dentry *de = NULL;
349
350 if (!list_empty(&inode->i_dentry)) {
351 spin_lock(&dcache_lock);
352 de = __d_find_alias(inode, 0);
353 spin_unlock(&dcache_lock);
354 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700355 return de;
356}
357
358/*
359 * Try to kill dentries associated with this inode.
360 * WARNING: you must own a reference to inode.
361 */
362void d_prune_aliases(struct inode *inode)
363{
Domen Puncer0cdca3f2005-09-10 00:27:07 -0700364 struct dentry *dentry;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700365restart:
366 spin_lock(&dcache_lock);
Domen Puncer0cdca3f2005-09-10 00:27:07 -0700367 list_for_each_entry(dentry, &inode->i_dentry, d_alias) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700368 spin_lock(&dentry->d_lock);
369 if (!atomic_read(&dentry->d_count)) {
370 __dget_locked(dentry);
371 __d_drop(dentry);
372 spin_unlock(&dentry->d_lock);
373 spin_unlock(&dcache_lock);
374 dput(dentry);
375 goto restart;
376 }
377 spin_unlock(&dentry->d_lock);
378 }
379 spin_unlock(&dcache_lock);
380}
381
382/*
Andrew Mortond702ccb2006-06-22 14:47:31 -0700383 * Throw away a dentry - free the inode, dput the parent. This requires that
384 * the LRU list has already been removed.
385 *
Miklos Szeredi85864e12007-10-16 23:27:09 -0700386 * Try to prune ancestors as well. This is necessary to prevent
387 * quadratic behavior of shrink_dcache_parent(), but is also expected
388 * to be beneficial in reducing dentry cache fragmentation.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700389 */
Miklos Szeredi85864e12007-10-16 23:27:09 -0700390static void prune_one_dentry(struct dentry * dentry)
Miklos Szeredi31f3e0b2008-06-23 18:11:52 +0200391 __releases(dentry->d_lock)
392 __releases(dcache_lock)
393 __acquires(dcache_lock)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700394{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700395 __d_drop(dentry);
Miklos Szeredid52b9082007-05-08 00:23:46 -0700396 dentry = d_kill(dentry);
Miklos Szeredid52b9082007-05-08 00:23:46 -0700397
398 /*
399 * Prune ancestors. Locking is simpler than in dput(),
400 * because dcache_lock needs to be taken anyway.
401 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700402 spin_lock(&dcache_lock);
Miklos Szeredid52b9082007-05-08 00:23:46 -0700403 while (dentry) {
404 if (!atomic_dec_and_lock(&dentry->d_count, &dentry->d_lock))
405 return;
406
407 if (dentry->d_op && dentry->d_op->d_delete)
408 dentry->d_op->d_delete(dentry);
Christoph Lameter4a0962a2008-02-14 19:38:45 -0800409 dentry_lru_remove(dentry);
Miklos Szeredid52b9082007-05-08 00:23:46 -0700410 __d_drop(dentry);
411 dentry = d_kill(dentry);
412 spin_lock(&dcache_lock);
413 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700414}
415
416/**
417 * prune_dcache - shrink the dcache
418 * @count: number of entries to try and free
NeilBrown0feae5c2006-06-22 14:47:28 -0700419 * @sb: if given, ignore dentries for other superblocks
420 * which are being unmounted.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700421 *
422 * Shrink the dcache. This is done when we need
423 * more memory, or simply when we need to unmount
424 * something (at which point we need to unuse
425 * all dentries).
426 *
427 * This function may fail to free any resources if
428 * all the dentries are in use.
429 */
430
Miklos Szeredi85864e12007-10-16 23:27:09 -0700431static void prune_dcache(int count, struct super_block *sb)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700432{
433 spin_lock(&dcache_lock);
434 for (; count ; count--) {
435 struct dentry *dentry;
436 struct list_head *tmp;
NeilBrown0feae5c2006-06-22 14:47:28 -0700437 struct rw_semaphore *s_umount;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700438
439 cond_resched_lock(&dcache_lock);
440
441 tmp = dentry_unused.prev;
Hua Zhongf58a1eb2006-06-25 05:49:32 -0700442 if (sb) {
NeilBrown0feae5c2006-06-22 14:47:28 -0700443 /* Try to find a dentry for this sb, but don't try
444 * too hard, if they aren't near the tail they will
445 * be moved down again soon
446 */
447 int skip = count;
448 while (skip && tmp != &dentry_unused &&
449 list_entry(tmp, struct dentry, d_lru)->d_sb != sb) {
450 skip--;
451 tmp = tmp->prev;
452 }
453 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700454 if (tmp == &dentry_unused)
455 break;
456 list_del_init(tmp);
457 prefetch(dentry_unused.prev);
458 dentry_stat.nr_unused--;
459 dentry = list_entry(tmp, struct dentry, d_lru);
460
461 spin_lock(&dentry->d_lock);
462 /*
463 * We found an inuse dentry which was not removed from
464 * dentry_unused because of laziness during lookup. Do not free
465 * it - just keep it off the dentry_unused list.
466 */
467 if (atomic_read(&dentry->d_count)) {
468 spin_unlock(&dentry->d_lock);
469 continue;
470 }
471 /* If the dentry was recently referenced, don't free it. */
472 if (dentry->d_flags & DCACHE_REFERENCED) {
473 dentry->d_flags &= ~DCACHE_REFERENCED;
474 list_add(&dentry->d_lru, &dentry_unused);
475 dentry_stat.nr_unused++;
476 spin_unlock(&dentry->d_lock);
477 continue;
478 }
NeilBrown0feae5c2006-06-22 14:47:28 -0700479 /*
480 * If the dentry is not DCACHED_REFERENCED, it is time
481 * to remove it from the dcache, provided the super block is
482 * NULL (which means we are trying to reclaim memory)
483 * or this dentry belongs to the same super block that
484 * we want to shrink.
485 */
486 /*
487 * If this dentry is for "my" filesystem, then I can prune it
488 * without taking the s_umount lock (I already hold it).
489 */
490 if (sb && dentry->d_sb == sb) {
Miklos Szeredi85864e12007-10-16 23:27:09 -0700491 prune_one_dentry(dentry);
NeilBrown0feae5c2006-06-22 14:47:28 -0700492 continue;
493 }
494 /*
495 * ...otherwise we need to be sure this filesystem isn't being
496 * unmounted, otherwise we could race with
497 * generic_shutdown_super(), and end up holding a reference to
498 * an inode while the filesystem is unmounted.
499 * So we try to get s_umount, and make sure s_root isn't NULL.
500 * (Take a local copy of s_umount to avoid a use-after-free of
501 * `dentry').
502 */
503 s_umount = &dentry->d_sb->s_umount;
504 if (down_read_trylock(s_umount)) {
505 if (dentry->d_sb->s_root != NULL) {
Miklos Szeredi85864e12007-10-16 23:27:09 -0700506 prune_one_dentry(dentry);
NeilBrown0feae5c2006-06-22 14:47:28 -0700507 up_read(s_umount);
508 continue;
509 }
510 up_read(s_umount);
511 }
512 spin_unlock(&dentry->d_lock);
Vasily Averin6eac3f92006-10-28 10:38:44 -0700513 /*
514 * Insert dentry at the head of the list as inserting at the
515 * tail leads to a cycle.
NeilBrown0feae5c2006-06-22 14:47:28 -0700516 */
Vasily Averin6eac3f92006-10-28 10:38:44 -0700517 list_add(&dentry->d_lru, &dentry_unused);
518 dentry_stat.nr_unused++;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700519 }
520 spin_unlock(&dcache_lock);
521}
522
523/*
524 * Shrink the dcache for the specified super block.
525 * This allows us to unmount a device without disturbing
526 * the dcache for the other devices.
527 *
528 * This implementation makes just two traversals of the
529 * unused list. On the first pass we move the selected
530 * dentries to the most recent end, and on the second
531 * pass we free them. The second pass must restart after
532 * each dput(), but since the target dentries are all at
533 * the end, it's really just a single traversal.
534 */
535
536/**
537 * shrink_dcache_sb - shrink dcache for a superblock
538 * @sb: superblock
539 *
540 * Shrink the dcache for the specified super block. This
541 * is used to free the dcache before unmounting a file
542 * system
543 */
544
545void shrink_dcache_sb(struct super_block * sb)
546{
547 struct list_head *tmp, *next;
548 struct dentry *dentry;
549
550 /*
551 * Pass one ... move the dentries for the specified
552 * superblock to the most recent end of the unused list.
553 */
554 spin_lock(&dcache_lock);
Denis V. Lunev37c42522007-10-16 23:29:53 -0700555 list_for_each_prev_safe(tmp, next, &dentry_unused) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700556 dentry = list_entry(tmp, struct dentry, d_lru);
557 if (dentry->d_sb != sb)
558 continue;
Denis V. Lunev37c42522007-10-16 23:29:53 -0700559 list_move_tail(tmp, &dentry_unused);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700560 }
561
562 /*
563 * Pass two ... free the dentries for this superblock.
564 */
565repeat:
Denis V. Lunev37c42522007-10-16 23:29:53 -0700566 list_for_each_prev_safe(tmp, next, &dentry_unused) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700567 dentry = list_entry(tmp, struct dentry, d_lru);
568 if (dentry->d_sb != sb)
569 continue;
570 dentry_stat.nr_unused--;
571 list_del_init(tmp);
572 spin_lock(&dentry->d_lock);
573 if (atomic_read(&dentry->d_count)) {
574 spin_unlock(&dentry->d_lock);
575 continue;
576 }
Miklos Szeredi85864e12007-10-16 23:27:09 -0700577 prune_one_dentry(dentry);
Kirill Korotaev2ab13462006-03-25 03:07:45 -0800578 cond_resched_lock(&dcache_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700579 goto repeat;
580 }
581 spin_unlock(&dcache_lock);
582}
583
584/*
David Howellsc636ebd2006-10-11 01:22:19 -0700585 * destroy a single subtree of dentries for unmount
586 * - see the comments on shrink_dcache_for_umount() for a description of the
587 * locking
588 */
589static void shrink_dcache_for_umount_subtree(struct dentry *dentry)
590{
591 struct dentry *parent;
David Howellsf8713572006-10-28 10:38:46 -0700592 unsigned detached = 0;
David Howellsc636ebd2006-10-11 01:22:19 -0700593
594 BUG_ON(!IS_ROOT(dentry));
595
596 /* detach this root from the system */
597 spin_lock(&dcache_lock);
Christoph Lameter4a0962a2008-02-14 19:38:45 -0800598 dentry_lru_remove(dentry);
David Howellsc636ebd2006-10-11 01:22:19 -0700599 __d_drop(dentry);
600 spin_unlock(&dcache_lock);
601
602 for (;;) {
603 /* descend to the first leaf in the current subtree */
604 while (!list_empty(&dentry->d_subdirs)) {
605 struct dentry *loop;
606
607 /* this is a branch with children - detach all of them
608 * from the system in one go */
609 spin_lock(&dcache_lock);
610 list_for_each_entry(loop, &dentry->d_subdirs,
611 d_u.d_child) {
Christoph Lameter4a0962a2008-02-14 19:38:45 -0800612 dentry_lru_remove(loop);
David Howellsc636ebd2006-10-11 01:22:19 -0700613 __d_drop(loop);
614 cond_resched_lock(&dcache_lock);
615 }
616 spin_unlock(&dcache_lock);
617
618 /* move to the first child */
619 dentry = list_entry(dentry->d_subdirs.next,
620 struct dentry, d_u.d_child);
621 }
622
623 /* consume the dentries from this leaf up through its parents
624 * until we find one with children or run out altogether */
625 do {
626 struct inode *inode;
627
628 if (atomic_read(&dentry->d_count) != 0) {
629 printk(KERN_ERR
630 "BUG: Dentry %p{i=%lx,n=%s}"
631 " still in use (%d)"
632 " [unmount of %s %s]\n",
633 dentry,
634 dentry->d_inode ?
635 dentry->d_inode->i_ino : 0UL,
636 dentry->d_name.name,
637 atomic_read(&dentry->d_count),
638 dentry->d_sb->s_type->name,
639 dentry->d_sb->s_id);
640 BUG();
641 }
642
643 parent = dentry->d_parent;
644 if (parent == dentry)
645 parent = NULL;
646 else
647 atomic_dec(&parent->d_count);
648
649 list_del(&dentry->d_u.d_child);
David Howellsf8713572006-10-28 10:38:46 -0700650 detached++;
David Howellsc636ebd2006-10-11 01:22:19 -0700651
652 inode = dentry->d_inode;
653 if (inode) {
654 dentry->d_inode = NULL;
655 list_del_init(&dentry->d_alias);
656 if (dentry->d_op && dentry->d_op->d_iput)
657 dentry->d_op->d_iput(dentry, inode);
658 else
659 iput(inode);
660 }
661
662 d_free(dentry);
663
664 /* finished when we fall off the top of the tree,
665 * otherwise we ascend to the parent and move to the
666 * next sibling if there is one */
667 if (!parent)
David Howellsf8713572006-10-28 10:38:46 -0700668 goto out;
David Howellsc636ebd2006-10-11 01:22:19 -0700669
670 dentry = parent;
671
672 } while (list_empty(&dentry->d_subdirs));
673
674 dentry = list_entry(dentry->d_subdirs.next,
675 struct dentry, d_u.d_child);
676 }
David Howellsf8713572006-10-28 10:38:46 -0700677out:
678 /* several dentries were freed, need to correct nr_dentry */
679 spin_lock(&dcache_lock);
680 dentry_stat.nr_dentry -= detached;
681 spin_unlock(&dcache_lock);
David Howellsc636ebd2006-10-11 01:22:19 -0700682}
683
684/*
685 * destroy the dentries attached to a superblock on unmounting
686 * - we don't need to use dentry->d_lock, and only need dcache_lock when
687 * removing the dentry from the system lists and hashes because:
688 * - the superblock is detached from all mountings and open files, so the
689 * dentry trees will not be rearranged by the VFS
690 * - s_umount is write-locked, so the memory pressure shrinker will ignore
691 * any dentries belonging to this superblock that it comes across
692 * - the filesystem itself is no longer permitted to rearrange the dentries
693 * in this superblock
694 */
695void shrink_dcache_for_umount(struct super_block *sb)
696{
697 struct dentry *dentry;
698
699 if (down_read_trylock(&sb->s_umount))
700 BUG();
701
702 dentry = sb->s_root;
703 sb->s_root = NULL;
704 atomic_dec(&dentry->d_count);
705 shrink_dcache_for_umount_subtree(dentry);
706
707 while (!hlist_empty(&sb->s_anon)) {
708 dentry = hlist_entry(sb->s_anon.first, struct dentry, d_hash);
709 shrink_dcache_for_umount_subtree(dentry);
710 }
711}
712
713/*
Linus Torvalds1da177e2005-04-16 15:20:36 -0700714 * Search for at least 1 mount point in the dentry's subdirs.
715 * We descend to the next level whenever the d_subdirs
716 * list is non-empty and continue searching.
717 */
718
719/**
720 * have_submounts - check for mounts over a dentry
721 * @parent: dentry to check.
722 *
723 * Return true if the parent or its subdirectories contain
724 * a mount point
725 */
726
727int have_submounts(struct dentry *parent)
728{
729 struct dentry *this_parent = parent;
730 struct list_head *next;
731
732 spin_lock(&dcache_lock);
733 if (d_mountpoint(parent))
734 goto positive;
735repeat:
736 next = this_parent->d_subdirs.next;
737resume:
738 while (next != &this_parent->d_subdirs) {
739 struct list_head *tmp = next;
Eric Dumazet5160ee62006-01-08 01:03:32 -0800740 struct dentry *dentry = list_entry(tmp, struct dentry, d_u.d_child);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700741 next = tmp->next;
742 /* Have we found a mount point ? */
743 if (d_mountpoint(dentry))
744 goto positive;
745 if (!list_empty(&dentry->d_subdirs)) {
746 this_parent = dentry;
747 goto repeat;
748 }
749 }
750 /*
751 * All done at this level ... ascend and resume the search.
752 */
753 if (this_parent != parent) {
Eric Dumazet5160ee62006-01-08 01:03:32 -0800754 next = this_parent->d_u.d_child.next;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700755 this_parent = this_parent->d_parent;
756 goto resume;
757 }
758 spin_unlock(&dcache_lock);
759 return 0; /* No mount points found in tree */
760positive:
761 spin_unlock(&dcache_lock);
762 return 1;
763}
764
765/*
766 * Search the dentry child list for the specified parent,
767 * and move any unused dentries to the end of the unused
768 * list for prune_dcache(). We descend to the next level
769 * whenever the d_subdirs list is non-empty and continue
770 * searching.
771 *
772 * It returns zero iff there are no unused children,
773 * otherwise it returns the number of children moved to
774 * the end of the unused list. This may not be the total
775 * number of unused children, because select_parent can
776 * drop the lock and return early due to latency
777 * constraints.
778 */
779static int select_parent(struct dentry * parent)
780{
781 struct dentry *this_parent = parent;
782 struct list_head *next;
783 int found = 0;
784
785 spin_lock(&dcache_lock);
786repeat:
787 next = this_parent->d_subdirs.next;
788resume:
789 while (next != &this_parent->d_subdirs) {
790 struct list_head *tmp = next;
Eric Dumazet5160ee62006-01-08 01:03:32 -0800791 struct dentry *dentry = list_entry(tmp, struct dentry, d_u.d_child);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700792 next = tmp->next;
793
Christoph Lameter4a0962a2008-02-14 19:38:45 -0800794 dentry_lru_remove(dentry);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700795 /*
796 * move only zero ref count dentries to the end
797 * of the unused list for prune_dcache
798 */
799 if (!atomic_read(&dentry->d_count)) {
Akinobu Mita8e130592006-06-26 00:24:37 -0700800 list_add_tail(&dentry->d_lru, &dentry_unused);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700801 dentry_stat.nr_unused++;
802 found++;
803 }
804
805 /*
806 * We can return to the caller if we have found some (this
807 * ensures forward progress). We'll be coming back to find
808 * the rest.
809 */
810 if (found && need_resched())
811 goto out;
812
813 /*
814 * Descend a level if the d_subdirs list is non-empty.
815 */
816 if (!list_empty(&dentry->d_subdirs)) {
817 this_parent = dentry;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700818 goto repeat;
819 }
820 }
821 /*
822 * All done at this level ... ascend and resume the search.
823 */
824 if (this_parent != parent) {
Eric Dumazet5160ee62006-01-08 01:03:32 -0800825 next = this_parent->d_u.d_child.next;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700826 this_parent = this_parent->d_parent;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700827 goto resume;
828 }
829out:
830 spin_unlock(&dcache_lock);
831 return found;
832}
833
834/**
835 * shrink_dcache_parent - prune dcache
836 * @parent: parent of entries to prune
837 *
838 * Prune the dcache to remove unused children of the parent dentry.
839 */
840
841void shrink_dcache_parent(struct dentry * parent)
842{
843 int found;
844
845 while ((found = select_parent(parent)) != 0)
Miklos Szeredi85864e12007-10-16 23:27:09 -0700846 prune_dcache(found, parent->d_sb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700847}
848
Linus Torvalds1da177e2005-04-16 15:20:36 -0700849/*
850 * Scan `nr' dentries and return the number which remain.
851 *
852 * We need to avoid reentering the filesystem if the caller is performing a
853 * GFP_NOFS allocation attempt. One example deadlock is:
854 *
855 * ext2_new_block->getblk->GFP->shrink_dcache_memory->prune_dcache->
856 * prune_one_dentry->dput->dentry_iput->iput->inode->i_sb->s_op->put_inode->
857 * ext2_discard_prealloc->ext2_free_blocks->lock_super->DEADLOCK.
858 *
859 * In this case we return -1 to tell the caller that we baled.
860 */
Al Viro27496a82005-10-21 03:20:48 -0400861static int shrink_dcache_memory(int nr, gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700862{
863 if (nr) {
864 if (!(gfp_mask & __GFP_FS))
865 return -1;
Miklos Szeredi85864e12007-10-16 23:27:09 -0700866 prune_dcache(nr, NULL);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700867 }
868 return (dentry_stat.nr_unused / 100) * sysctl_vfs_cache_pressure;
869}
870
Rusty Russell8e1f9362007-07-17 04:03:17 -0700871static struct shrinker dcache_shrinker = {
872 .shrink = shrink_dcache_memory,
873 .seeks = DEFAULT_SEEKS,
874};
875
Linus Torvalds1da177e2005-04-16 15:20:36 -0700876/**
877 * d_alloc - allocate a dcache entry
878 * @parent: parent of entry to allocate
879 * @name: qstr of the name
880 *
881 * Allocates a dentry. It returns %NULL if there is insufficient memory
882 * available. On a success the dentry is returned. The name passed in is
883 * copied and the copy passed in may be reused after this call.
884 */
885
886struct dentry *d_alloc(struct dentry * parent, const struct qstr *name)
887{
888 struct dentry *dentry;
889 char *dname;
890
Mel Gormane12ba742007-10-16 01:25:52 -0700891 dentry = kmem_cache_alloc(dentry_cache, GFP_KERNEL);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700892 if (!dentry)
893 return NULL;
894
895 if (name->len > DNAME_INLINE_LEN-1) {
896 dname = kmalloc(name->len + 1, GFP_KERNEL);
897 if (!dname) {
898 kmem_cache_free(dentry_cache, dentry);
899 return NULL;
900 }
901 } else {
902 dname = dentry->d_iname;
903 }
904 dentry->d_name.name = dname;
905
906 dentry->d_name.len = name->len;
907 dentry->d_name.hash = name->hash;
908 memcpy(dname, name->name, name->len);
909 dname[name->len] = 0;
910
911 atomic_set(&dentry->d_count, 1);
912 dentry->d_flags = DCACHE_UNHASHED;
913 spin_lock_init(&dentry->d_lock);
914 dentry->d_inode = NULL;
915 dentry->d_parent = NULL;
916 dentry->d_sb = NULL;
917 dentry->d_op = NULL;
918 dentry->d_fsdata = NULL;
919 dentry->d_mounted = 0;
Marcelo Tosatti47ba87e2006-02-03 03:04:06 -0800920#ifdef CONFIG_PROFILING
Linus Torvalds1da177e2005-04-16 15:20:36 -0700921 dentry->d_cookie = NULL;
Marcelo Tosatti47ba87e2006-02-03 03:04:06 -0800922#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -0700923 INIT_HLIST_NODE(&dentry->d_hash);
924 INIT_LIST_HEAD(&dentry->d_lru);
925 INIT_LIST_HEAD(&dentry->d_subdirs);
926 INIT_LIST_HEAD(&dentry->d_alias);
927
928 if (parent) {
929 dentry->d_parent = dget(parent);
930 dentry->d_sb = parent->d_sb;
931 } else {
Eric Dumazet5160ee62006-01-08 01:03:32 -0800932 INIT_LIST_HEAD(&dentry->d_u.d_child);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700933 }
934
935 spin_lock(&dcache_lock);
936 if (parent)
Eric Dumazet5160ee62006-01-08 01:03:32 -0800937 list_add(&dentry->d_u.d_child, &parent->d_subdirs);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700938 dentry_stat.nr_dentry++;
939 spin_unlock(&dcache_lock);
940
941 return dentry;
942}
943
944struct dentry *d_alloc_name(struct dentry *parent, const char *name)
945{
946 struct qstr q;
947
948 q.name = name;
949 q.len = strlen(name);
950 q.hash = full_name_hash(q.name, q.len);
951 return d_alloc(parent, &q);
952}
953
954/**
955 * d_instantiate - fill in inode information for a dentry
956 * @entry: dentry to complete
957 * @inode: inode to attach to this dentry
958 *
959 * Fill in inode information in the entry.
960 *
961 * This turns negative dentries into productive full members
962 * of society.
963 *
964 * NOTE! This assumes that the inode count has been incremented
965 * (or otherwise set) by the caller to indicate that it is now
966 * in use by the dcache.
967 */
968
969void d_instantiate(struct dentry *entry, struct inode * inode)
970{
Eric Sesterhenn28133c72006-03-26 18:25:39 +0200971 BUG_ON(!list_empty(&entry->d_alias));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700972 spin_lock(&dcache_lock);
973 if (inode)
974 list_add(&entry->d_alias, &inode->i_dentry);
975 entry->d_inode = inode;
Nick Pigginc32ccd82006-03-25 03:07:09 -0800976 fsnotify_d_instantiate(entry, inode);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700977 spin_unlock(&dcache_lock);
978 security_d_instantiate(entry, inode);
979}
980
981/**
982 * d_instantiate_unique - instantiate a non-aliased dentry
983 * @entry: dentry to instantiate
984 * @inode: inode to attach to this dentry
985 *
986 * Fill in inode information in the entry. On success, it returns NULL.
987 * If an unhashed alias of "entry" already exists, then we return the
Oleg Drokine866cfa2006-01-09 20:52:51 -0800988 * aliased dentry instead and drop one reference to inode.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700989 *
990 * Note that in order to avoid conflicts with rename() etc, the caller
991 * had better be holding the parent directory semaphore.
Oleg Drokine866cfa2006-01-09 20:52:51 -0800992 *
993 * This also assumes that the inode count has been incremented
994 * (or otherwise set) by the caller to indicate that it is now
995 * in use by the dcache.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700996 */
David Howells770bfad2006-08-22 20:06:07 -0400997static struct dentry *__d_instantiate_unique(struct dentry *entry,
998 struct inode *inode)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700999{
1000 struct dentry *alias;
1001 int len = entry->d_name.len;
1002 const char *name = entry->d_name.name;
1003 unsigned int hash = entry->d_name.hash;
1004
David Howells770bfad2006-08-22 20:06:07 -04001005 if (!inode) {
1006 entry->d_inode = NULL;
1007 return NULL;
1008 }
1009
Linus Torvalds1da177e2005-04-16 15:20:36 -07001010 list_for_each_entry(alias, &inode->i_dentry, d_alias) {
1011 struct qstr *qstr = &alias->d_name;
1012
1013 if (qstr->hash != hash)
1014 continue;
1015 if (alias->d_parent != entry->d_parent)
1016 continue;
1017 if (qstr->len != len)
1018 continue;
1019 if (memcmp(qstr->name, name, len))
1020 continue;
1021 dget_locked(alias);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001022 return alias;
1023 }
David Howells770bfad2006-08-22 20:06:07 -04001024
Linus Torvalds1da177e2005-04-16 15:20:36 -07001025 list_add(&entry->d_alias, &inode->i_dentry);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001026 entry->d_inode = inode;
Nick Pigginc32ccd82006-03-25 03:07:09 -08001027 fsnotify_d_instantiate(entry, inode);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001028 return NULL;
1029}
David Howells770bfad2006-08-22 20:06:07 -04001030
1031struct dentry *d_instantiate_unique(struct dentry *entry, struct inode *inode)
1032{
1033 struct dentry *result;
1034
1035 BUG_ON(!list_empty(&entry->d_alias));
1036
1037 spin_lock(&dcache_lock);
1038 result = __d_instantiate_unique(entry, inode);
1039 spin_unlock(&dcache_lock);
1040
1041 if (!result) {
1042 security_d_instantiate(entry, inode);
1043 return NULL;
1044 }
1045
1046 BUG_ON(!d_unhashed(result));
1047 iput(inode);
1048 return result;
1049}
1050
Linus Torvalds1da177e2005-04-16 15:20:36 -07001051EXPORT_SYMBOL(d_instantiate_unique);
1052
1053/**
1054 * d_alloc_root - allocate root dentry
1055 * @root_inode: inode to allocate the root for
1056 *
1057 * Allocate a root ("/") dentry for the inode given. The inode is
1058 * instantiated and returned. %NULL is returned if there is insufficient
1059 * memory or the inode passed is %NULL.
1060 */
1061
1062struct dentry * d_alloc_root(struct inode * root_inode)
1063{
1064 struct dentry *res = NULL;
1065
1066 if (root_inode) {
1067 static const struct qstr name = { .name = "/", .len = 1 };
1068
1069 res = d_alloc(NULL, &name);
1070 if (res) {
1071 res->d_sb = root_inode->i_sb;
1072 res->d_parent = res;
1073 d_instantiate(res, root_inode);
1074 }
1075 }
1076 return res;
1077}
1078
1079static inline struct hlist_head *d_hash(struct dentry *parent,
1080 unsigned long hash)
1081{
1082 hash += ((unsigned long) parent ^ GOLDEN_RATIO_PRIME) / L1_CACHE_BYTES;
1083 hash = hash ^ ((hash ^ GOLDEN_RATIO_PRIME) >> D_HASHBITS);
1084 return dentry_hashtable + (hash & D_HASHMASK);
1085}
1086
1087/**
1088 * d_alloc_anon - allocate an anonymous dentry
1089 * @inode: inode to allocate the dentry for
1090 *
1091 * This is similar to d_alloc_root. It is used by filesystems when
1092 * creating a dentry for a given inode, often in the process of
1093 * mapping a filehandle to a dentry. The returned dentry may be
1094 * anonymous, or may have a full name (if the inode was already
1095 * in the cache). The file system may need to make further
1096 * efforts to connect this dentry into the dcache properly.
1097 *
1098 * When called on a directory inode, we must ensure that
1099 * the inode only ever has one dentry. If a dentry is
1100 * found, that is returned instead of allocating a new one.
1101 *
1102 * On successful return, the reference to the inode has been transferred
1103 * to the dentry. If %NULL is returned (indicating kmalloc failure),
1104 * the reference on the inode has not been released.
1105 */
1106
1107struct dentry * d_alloc_anon(struct inode *inode)
1108{
1109 static const struct qstr anonstring = { .name = "" };
1110 struct dentry *tmp;
1111 struct dentry *res;
1112
1113 if ((res = d_find_alias(inode))) {
1114 iput(inode);
1115 return res;
1116 }
1117
1118 tmp = d_alloc(NULL, &anonstring);
1119 if (!tmp)
1120 return NULL;
1121
1122 tmp->d_parent = tmp; /* make sure dput doesn't croak */
1123
1124 spin_lock(&dcache_lock);
1125 res = __d_find_alias(inode, 0);
1126 if (!res) {
1127 /* attach a disconnected dentry */
1128 res = tmp;
1129 tmp = NULL;
1130 spin_lock(&res->d_lock);
1131 res->d_sb = inode->i_sb;
1132 res->d_parent = res;
1133 res->d_inode = inode;
1134 res->d_flags |= DCACHE_DISCONNECTED;
1135 res->d_flags &= ~DCACHE_UNHASHED;
1136 list_add(&res->d_alias, &inode->i_dentry);
1137 hlist_add_head(&res->d_hash, &inode->i_sb->s_anon);
1138 spin_unlock(&res->d_lock);
1139
1140 inode = NULL; /* don't drop reference */
1141 }
1142 spin_unlock(&dcache_lock);
1143
1144 if (inode)
1145 iput(inode);
1146 if (tmp)
1147 dput(tmp);
1148 return res;
1149}
1150
1151
1152/**
1153 * d_splice_alias - splice a disconnected dentry into the tree if one exists
1154 * @inode: the inode which may have a disconnected dentry
1155 * @dentry: a negative dentry which we want to point to the inode.
1156 *
1157 * If inode is a directory and has a 'disconnected' dentry (i.e. IS_ROOT and
1158 * DCACHE_DISCONNECTED), then d_move that in place of the given dentry
1159 * and return it, else simply d_add the inode to the dentry and return NULL.
1160 *
1161 * This is needed in the lookup routine of any filesystem that is exportable
1162 * (via knfsd) so that we can build dcache paths to directories effectively.
1163 *
1164 * If a dentry was found and moved, then it is returned. Otherwise NULL
1165 * is returned. This matches the expected return value of ->lookup.
1166 *
1167 */
1168struct dentry *d_splice_alias(struct inode *inode, struct dentry *dentry)
1169{
1170 struct dentry *new = NULL;
1171
NeilBrown21c0d8f2006-10-04 02:16:16 -07001172 if (inode && S_ISDIR(inode->i_mode)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001173 spin_lock(&dcache_lock);
1174 new = __d_find_alias(inode, 1);
1175 if (new) {
1176 BUG_ON(!(new->d_flags & DCACHE_DISCONNECTED));
Nick Pigginc32ccd82006-03-25 03:07:09 -08001177 fsnotify_d_instantiate(new, inode);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001178 spin_unlock(&dcache_lock);
1179 security_d_instantiate(new, inode);
1180 d_rehash(dentry);
1181 d_move(new, dentry);
1182 iput(inode);
1183 } else {
1184 /* d_instantiate takes dcache_lock, so we do it by hand */
1185 list_add(&dentry->d_alias, &inode->i_dentry);
1186 dentry->d_inode = inode;
Nick Pigginc32ccd82006-03-25 03:07:09 -08001187 fsnotify_d_instantiate(dentry, inode);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001188 spin_unlock(&dcache_lock);
1189 security_d_instantiate(dentry, inode);
1190 d_rehash(dentry);
1191 }
1192 } else
1193 d_add(dentry, inode);
1194 return new;
1195}
1196
1197
1198/**
1199 * d_lookup - search for a dentry
1200 * @parent: parent dentry
1201 * @name: qstr of name we wish to find
1202 *
1203 * Searches the children of the parent dentry for the name in question. If
1204 * the dentry is found its reference count is incremented and the dentry
1205 * is returned. The caller must use d_put to free the entry when it has
1206 * finished using it. %NULL is returned on failure.
1207 *
1208 * __d_lookup is dcache_lock free. The hash list is protected using RCU.
1209 * Memory barriers are used while updating and doing lockless traversal.
1210 * To avoid races with d_move while rename is happening, d_lock is used.
1211 *
1212 * Overflows in memcmp(), while d_move, are avoided by keeping the length
1213 * and name pointer in one structure pointed by d_qstr.
1214 *
1215 * rcu_read_lock() and rcu_read_unlock() are used to disable preemption while
1216 * lookup is going on.
1217 *
1218 * dentry_unused list is not updated even if lookup finds the required dentry
1219 * in there. It is updated in places such as prune_dcache, shrink_dcache_sb,
1220 * select_parent and __dget_locked. This laziness saves lookup from dcache_lock
1221 * acquisition.
1222 *
1223 * d_lookup() is protected against the concurrent renames in some unrelated
1224 * directory using the seqlockt_t rename_lock.
1225 */
1226
1227struct dentry * d_lookup(struct dentry * parent, struct qstr * name)
1228{
1229 struct dentry * dentry = NULL;
1230 unsigned long seq;
1231
1232 do {
1233 seq = read_seqbegin(&rename_lock);
1234 dentry = __d_lookup(parent, name);
1235 if (dentry)
1236 break;
1237 } while (read_seqretry(&rename_lock, seq));
1238 return dentry;
1239}
1240
1241struct dentry * __d_lookup(struct dentry * parent, struct qstr * name)
1242{
1243 unsigned int len = name->len;
1244 unsigned int hash = name->hash;
1245 const unsigned char *str = name->name;
1246 struct hlist_head *head = d_hash(parent,hash);
1247 struct dentry *found = NULL;
1248 struct hlist_node *node;
Paul E. McKenney665a7582005-11-07 00:59:17 -08001249 struct dentry *dentry;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001250
1251 rcu_read_lock();
1252
Paul E. McKenney665a7582005-11-07 00:59:17 -08001253 hlist_for_each_entry_rcu(dentry, node, head, d_hash) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001254 struct qstr *qstr;
1255
Linus Torvalds1da177e2005-04-16 15:20:36 -07001256 if (dentry->d_name.hash != hash)
1257 continue;
1258 if (dentry->d_parent != parent)
1259 continue;
1260
1261 spin_lock(&dentry->d_lock);
1262
1263 /*
1264 * Recheck the dentry after taking the lock - d_move may have
1265 * changed things. Don't bother checking the hash because we're
1266 * about to compare the whole name anyway.
1267 */
1268 if (dentry->d_parent != parent)
1269 goto next;
1270
1271 /*
1272 * It is safe to compare names since d_move() cannot
1273 * change the qstr (protected by d_lock).
1274 */
1275 qstr = &dentry->d_name;
1276 if (parent->d_op && parent->d_op->d_compare) {
1277 if (parent->d_op->d_compare(parent, qstr, name))
1278 goto next;
1279 } else {
1280 if (qstr->len != len)
1281 goto next;
1282 if (memcmp(qstr->name, str, len))
1283 goto next;
1284 }
1285
1286 if (!d_unhashed(dentry)) {
1287 atomic_inc(&dentry->d_count);
1288 found = dentry;
1289 }
1290 spin_unlock(&dentry->d_lock);
1291 break;
1292next:
1293 spin_unlock(&dentry->d_lock);
1294 }
1295 rcu_read_unlock();
1296
1297 return found;
1298}
1299
1300/**
Eric W. Biederman3e7e2412006-03-31 02:31:43 -08001301 * d_hash_and_lookup - hash the qstr then search for a dentry
1302 * @dir: Directory to search in
1303 * @name: qstr of name we wish to find
1304 *
1305 * On hash failure or on lookup failure NULL is returned.
1306 */
1307struct dentry *d_hash_and_lookup(struct dentry *dir, struct qstr *name)
1308{
1309 struct dentry *dentry = NULL;
1310
1311 /*
1312 * Check for a fs-specific hash function. Note that we must
1313 * calculate the standard hash first, as the d_op->d_hash()
1314 * routine may choose to leave the hash value unchanged.
1315 */
1316 name->hash = full_name_hash(name->name, name->len);
1317 if (dir->d_op && dir->d_op->d_hash) {
1318 if (dir->d_op->d_hash(dir, name) < 0)
1319 goto out;
1320 }
1321 dentry = d_lookup(dir, name);
1322out:
1323 return dentry;
1324}
1325
1326/**
Linus Torvalds1da177e2005-04-16 15:20:36 -07001327 * d_validate - verify dentry provided from insecure source
1328 * @dentry: The dentry alleged to be valid child of @dparent
1329 * @dparent: The parent dentry (known to be valid)
1330 * @hash: Hash of the dentry
1331 * @len: Length of the name
1332 *
1333 * An insecure source has sent us a dentry, here we verify it and dget() it.
1334 * This is used by ncpfs in its readdir implementation.
1335 * Zero is returned in the dentry is invalid.
1336 */
1337
1338int d_validate(struct dentry *dentry, struct dentry *dparent)
1339{
1340 struct hlist_head *base;
1341 struct hlist_node *lhp;
1342
1343 /* Check whether the ptr might be valid at all.. */
1344 if (!kmem_ptr_validate(dentry_cache, dentry))
1345 goto out;
1346
1347 if (dentry->d_parent != dparent)
1348 goto out;
1349
1350 spin_lock(&dcache_lock);
1351 base = d_hash(dparent, dentry->d_name.hash);
1352 hlist_for_each(lhp,base) {
Paul E. McKenney665a7582005-11-07 00:59:17 -08001353 /* hlist_for_each_entry_rcu() not required for d_hash list
Linus Torvalds1da177e2005-04-16 15:20:36 -07001354 * as it is parsed under dcache_lock
1355 */
1356 if (dentry == hlist_entry(lhp, struct dentry, d_hash)) {
1357 __dget_locked(dentry);
1358 spin_unlock(&dcache_lock);
1359 return 1;
1360 }
1361 }
1362 spin_unlock(&dcache_lock);
1363out:
1364 return 0;
1365}
1366
1367/*
1368 * When a file is deleted, we have two options:
1369 * - turn this dentry into a negative dentry
1370 * - unhash this dentry and free it.
1371 *
1372 * Usually, we want to just turn this into
1373 * a negative dentry, but if anybody else is
1374 * currently using the dentry or the inode
1375 * we can't do that and we fall back on removing
1376 * it from the hash queues and waiting for
1377 * it to be deleted later when it has no users
1378 */
1379
1380/**
1381 * d_delete - delete a dentry
1382 * @dentry: The dentry to delete
1383 *
1384 * Turn the dentry into a negative dentry if possible, otherwise
1385 * remove it from the hash queues so it can be deleted later
1386 */
1387
1388void d_delete(struct dentry * dentry)
1389{
John McCutchan7a91bf72005-08-08 13:52:16 -04001390 int isdir = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001391 /*
1392 * Are we the only user?
1393 */
1394 spin_lock(&dcache_lock);
1395 spin_lock(&dentry->d_lock);
John McCutchan7a91bf72005-08-08 13:52:16 -04001396 isdir = S_ISDIR(dentry->d_inode->i_mode);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001397 if (atomic_read(&dentry->d_count) == 1) {
1398 dentry_iput(dentry);
John McCutchan7a91bf72005-08-08 13:52:16 -04001399 fsnotify_nameremove(dentry, isdir);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001400 return;
1401 }
1402
1403 if (!d_unhashed(dentry))
1404 __d_drop(dentry);
1405
1406 spin_unlock(&dentry->d_lock);
1407 spin_unlock(&dcache_lock);
John McCutchan7a91bf72005-08-08 13:52:16 -04001408
1409 fsnotify_nameremove(dentry, isdir);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001410}
1411
1412static void __d_rehash(struct dentry * entry, struct hlist_head *list)
1413{
1414
1415 entry->d_flags &= ~DCACHE_UNHASHED;
1416 hlist_add_head_rcu(&entry->d_hash, list);
1417}
1418
David Howells770bfad2006-08-22 20:06:07 -04001419static void _d_rehash(struct dentry * entry)
1420{
1421 __d_rehash(entry, d_hash(entry->d_parent, entry->d_name.hash));
1422}
1423
Linus Torvalds1da177e2005-04-16 15:20:36 -07001424/**
1425 * d_rehash - add an entry back to the hash
1426 * @entry: dentry to add to the hash
1427 *
1428 * Adds a dentry to the hash according to its name.
1429 */
1430
1431void d_rehash(struct dentry * entry)
1432{
Linus Torvalds1da177e2005-04-16 15:20:36 -07001433 spin_lock(&dcache_lock);
1434 spin_lock(&entry->d_lock);
David Howells770bfad2006-08-22 20:06:07 -04001435 _d_rehash(entry);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001436 spin_unlock(&entry->d_lock);
1437 spin_unlock(&dcache_lock);
1438}
1439
1440#define do_switch(x,y) do { \
1441 __typeof__ (x) __tmp = x; \
1442 x = y; y = __tmp; } while (0)
1443
1444/*
1445 * When switching names, the actual string doesn't strictly have to
1446 * be preserved in the target - because we're dropping the target
1447 * anyway. As such, we can just do a simple memcpy() to copy over
1448 * the new name before we switch.
1449 *
1450 * Note that we have to be a lot more careful about getting the hash
1451 * switched - we have to switch the hash value properly even if it
1452 * then no longer matches the actual (corrupted) string of the target.
1453 * The hash value has to match the hash queue that the dentry is on..
1454 */
1455static void switch_names(struct dentry *dentry, struct dentry *target)
1456{
1457 if (dname_external(target)) {
1458 if (dname_external(dentry)) {
1459 /*
1460 * Both external: swap the pointers
1461 */
1462 do_switch(target->d_name.name, dentry->d_name.name);
1463 } else {
1464 /*
1465 * dentry:internal, target:external. Steal target's
1466 * storage and make target internal.
1467 */
J. Bruce Fields321bcf92007-10-21 16:41:38 -07001468 memcpy(target->d_iname, dentry->d_name.name,
1469 dentry->d_name.len + 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001470 dentry->d_name.name = target->d_name.name;
1471 target->d_name.name = target->d_iname;
1472 }
1473 } else {
1474 if (dname_external(dentry)) {
1475 /*
1476 * dentry:external, target:internal. Give dentry's
1477 * storage to target and make dentry internal
1478 */
1479 memcpy(dentry->d_iname, target->d_name.name,
1480 target->d_name.len + 1);
1481 target->d_name.name = dentry->d_name.name;
1482 dentry->d_name.name = dentry->d_iname;
1483 } else {
1484 /*
1485 * Both are internal. Just copy target to dentry
1486 */
1487 memcpy(dentry->d_iname, target->d_name.name,
1488 target->d_name.len + 1);
1489 }
1490 }
1491}
1492
1493/*
1494 * We cannibalize "target" when moving dentry on top of it,
1495 * because it's going to be thrown away anyway. We could be more
1496 * polite about it, though.
1497 *
1498 * This forceful removal will result in ugly /proc output if
1499 * somebody holds a file open that got deleted due to a rename.
1500 * We could be nicer about the deleted file, and let it show
J. Bruce Fieldsbc154b12007-10-16 23:29:42 -07001501 * up under the name it had before it was deleted rather than
1502 * under the original name of the file that was moved on top of it.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001503 */
1504
Trond Myklebust9eaef272006-10-21 10:24:20 -07001505/*
1506 * d_move_locked - move a dentry
Linus Torvalds1da177e2005-04-16 15:20:36 -07001507 * @dentry: entry to move
1508 * @target: new dentry
1509 *
1510 * Update the dcache to reflect the move of a file name. Negative
1511 * dcache entries should not be moved in this way.
1512 */
Trond Myklebust9eaef272006-10-21 10:24:20 -07001513static void d_move_locked(struct dentry * dentry, struct dentry * target)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001514{
1515 struct hlist_head *list;
1516
1517 if (!dentry->d_inode)
1518 printk(KERN_WARNING "VFS: moving negative dcache entry\n");
1519
Linus Torvalds1da177e2005-04-16 15:20:36 -07001520 write_seqlock(&rename_lock);
1521 /*
1522 * XXXX: do we really need to take target->d_lock?
1523 */
1524 if (target < dentry) {
1525 spin_lock(&target->d_lock);
Ingo Molnara90b9c02006-07-03 00:25:04 -07001526 spin_lock_nested(&dentry->d_lock, DENTRY_D_LOCK_NESTED);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001527 } else {
1528 spin_lock(&dentry->d_lock);
Ingo Molnara90b9c02006-07-03 00:25:04 -07001529 spin_lock_nested(&target->d_lock, DENTRY_D_LOCK_NESTED);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001530 }
1531
1532 /* Move the dentry to the target hash queue, if on different bucket */
Denis Chengf77e3492007-10-16 23:30:11 -07001533 if (d_unhashed(dentry))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001534 goto already_unhashed;
1535
1536 hlist_del_rcu(&dentry->d_hash);
1537
1538already_unhashed:
1539 list = d_hash(target->d_parent, target->d_name.hash);
1540 __d_rehash(dentry, list);
1541
1542 /* Unhash the target: dput() will then get rid of it */
1543 __d_drop(target);
1544
Eric Dumazet5160ee62006-01-08 01:03:32 -08001545 list_del(&dentry->d_u.d_child);
1546 list_del(&target->d_u.d_child);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001547
1548 /* Switch the names.. */
1549 switch_names(dentry, target);
1550 do_switch(dentry->d_name.len, target->d_name.len);
1551 do_switch(dentry->d_name.hash, target->d_name.hash);
1552
1553 /* ... and switch the parents */
1554 if (IS_ROOT(dentry)) {
1555 dentry->d_parent = target->d_parent;
1556 target->d_parent = target;
Eric Dumazet5160ee62006-01-08 01:03:32 -08001557 INIT_LIST_HEAD(&target->d_u.d_child);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001558 } else {
1559 do_switch(dentry->d_parent, target->d_parent);
1560
1561 /* And add them back to the (new) parent lists */
Eric Dumazet5160ee62006-01-08 01:03:32 -08001562 list_add(&target->d_u.d_child, &target->d_parent->d_subdirs);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001563 }
1564
Eric Dumazet5160ee62006-01-08 01:03:32 -08001565 list_add(&dentry->d_u.d_child, &dentry->d_parent->d_subdirs);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001566 spin_unlock(&target->d_lock);
Nick Pigginc32ccd82006-03-25 03:07:09 -08001567 fsnotify_d_move(dentry);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001568 spin_unlock(&dentry->d_lock);
1569 write_sequnlock(&rename_lock);
Trond Myklebust9eaef272006-10-21 10:24:20 -07001570}
1571
1572/**
1573 * d_move - move a dentry
1574 * @dentry: entry to move
1575 * @target: new dentry
1576 *
1577 * Update the dcache to reflect the move of a file name. Negative
1578 * dcache entries should not be moved in this way.
1579 */
1580
1581void d_move(struct dentry * dentry, struct dentry * target)
1582{
1583 spin_lock(&dcache_lock);
1584 d_move_locked(dentry, target);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001585 spin_unlock(&dcache_lock);
1586}
1587
David Howells770bfad2006-08-22 20:06:07 -04001588/*
Trond Myklebust9eaef272006-10-21 10:24:20 -07001589 * Helper that returns 1 if p1 is a parent of p2, else 0
1590 */
1591static int d_isparent(struct dentry *p1, struct dentry *p2)
1592{
1593 struct dentry *p;
1594
1595 for (p = p2; p->d_parent != p; p = p->d_parent) {
1596 if (p->d_parent == p1)
1597 return 1;
1598 }
1599 return 0;
1600}
1601
1602/*
1603 * This helper attempts to cope with remotely renamed directories
1604 *
1605 * It assumes that the caller is already holding
1606 * dentry->d_parent->d_inode->i_mutex and the dcache_lock
1607 *
1608 * Note: If ever the locking in lock_rename() changes, then please
1609 * remember to update this too...
Trond Myklebust9eaef272006-10-21 10:24:20 -07001610 */
1611static struct dentry *__d_unalias(struct dentry *dentry, struct dentry *alias)
Miklos Szeredi31f3e0b2008-06-23 18:11:52 +02001612 __releases(dcache_lock)
Trond Myklebust9eaef272006-10-21 10:24:20 -07001613{
1614 struct mutex *m1 = NULL, *m2 = NULL;
1615 struct dentry *ret;
1616
1617 /* If alias and dentry share a parent, then no extra locks required */
1618 if (alias->d_parent == dentry->d_parent)
1619 goto out_unalias;
1620
1621 /* Check for loops */
1622 ret = ERR_PTR(-ELOOP);
1623 if (d_isparent(alias, dentry))
1624 goto out_err;
1625
1626 /* See lock_rename() */
1627 ret = ERR_PTR(-EBUSY);
1628 if (!mutex_trylock(&dentry->d_sb->s_vfs_rename_mutex))
1629 goto out_err;
1630 m1 = &dentry->d_sb->s_vfs_rename_mutex;
1631 if (!mutex_trylock(&alias->d_parent->d_inode->i_mutex))
1632 goto out_err;
1633 m2 = &alias->d_parent->d_inode->i_mutex;
1634out_unalias:
1635 d_move_locked(alias, dentry);
1636 ret = alias;
1637out_err:
1638 spin_unlock(&dcache_lock);
1639 if (m2)
1640 mutex_unlock(m2);
1641 if (m1)
1642 mutex_unlock(m1);
1643 return ret;
1644}
1645
1646/*
David Howells770bfad2006-08-22 20:06:07 -04001647 * Prepare an anonymous dentry for life in the superblock's dentry tree as a
1648 * named dentry in place of the dentry to be replaced.
1649 */
1650static void __d_materialise_dentry(struct dentry *dentry, struct dentry *anon)
1651{
1652 struct dentry *dparent, *aparent;
1653
1654 switch_names(dentry, anon);
1655 do_switch(dentry->d_name.len, anon->d_name.len);
1656 do_switch(dentry->d_name.hash, anon->d_name.hash);
1657
1658 dparent = dentry->d_parent;
1659 aparent = anon->d_parent;
1660
1661 dentry->d_parent = (aparent == anon) ? dentry : aparent;
1662 list_del(&dentry->d_u.d_child);
1663 if (!IS_ROOT(dentry))
1664 list_add(&dentry->d_u.d_child, &dentry->d_parent->d_subdirs);
1665 else
1666 INIT_LIST_HEAD(&dentry->d_u.d_child);
1667
1668 anon->d_parent = (dparent == dentry) ? anon : dparent;
1669 list_del(&anon->d_u.d_child);
1670 if (!IS_ROOT(anon))
1671 list_add(&anon->d_u.d_child, &anon->d_parent->d_subdirs);
1672 else
1673 INIT_LIST_HEAD(&anon->d_u.d_child);
1674
1675 anon->d_flags &= ~DCACHE_DISCONNECTED;
1676}
1677
1678/**
1679 * d_materialise_unique - introduce an inode into the tree
1680 * @dentry: candidate dentry
1681 * @inode: inode to bind to the dentry, to which aliases may be attached
1682 *
1683 * Introduces an dentry into the tree, substituting an extant disconnected
1684 * root directory alias in its place if there is one
1685 */
1686struct dentry *d_materialise_unique(struct dentry *dentry, struct inode *inode)
1687{
Trond Myklebust9eaef272006-10-21 10:24:20 -07001688 struct dentry *actual;
David Howells770bfad2006-08-22 20:06:07 -04001689
1690 BUG_ON(!d_unhashed(dentry));
1691
1692 spin_lock(&dcache_lock);
1693
1694 if (!inode) {
1695 actual = dentry;
1696 dentry->d_inode = NULL;
1697 goto found_lock;
1698 }
1699
Trond Myklebust9eaef272006-10-21 10:24:20 -07001700 if (S_ISDIR(inode->i_mode)) {
1701 struct dentry *alias;
David Howells770bfad2006-08-22 20:06:07 -04001702
Trond Myklebust9eaef272006-10-21 10:24:20 -07001703 /* Does an aliased dentry already exist? */
1704 alias = __d_find_alias(inode, 0);
1705 if (alias) {
1706 actual = alias;
1707 /* Is this an anonymous mountpoint that we could splice
1708 * into our tree? */
1709 if (IS_ROOT(alias)) {
1710 spin_lock(&alias->d_lock);
1711 __d_materialise_dentry(dentry, alias);
1712 __d_drop(alias);
1713 goto found;
1714 }
1715 /* Nope, but we must(!) avoid directory aliasing */
1716 actual = __d_unalias(dentry, alias);
1717 if (IS_ERR(actual))
1718 dput(alias);
1719 goto out_nolock;
1720 }
David Howells770bfad2006-08-22 20:06:07 -04001721 }
1722
1723 /* Add a unique reference */
1724 actual = __d_instantiate_unique(dentry, inode);
1725 if (!actual)
1726 actual = dentry;
1727 else if (unlikely(!d_unhashed(actual)))
1728 goto shouldnt_be_hashed;
1729
1730found_lock:
1731 spin_lock(&actual->d_lock);
1732found:
1733 _d_rehash(actual);
1734 spin_unlock(&actual->d_lock);
1735 spin_unlock(&dcache_lock);
Trond Myklebust9eaef272006-10-21 10:24:20 -07001736out_nolock:
David Howells770bfad2006-08-22 20:06:07 -04001737 if (actual == dentry) {
1738 security_d_instantiate(dentry, inode);
1739 return NULL;
1740 }
1741
1742 iput(inode);
1743 return actual;
1744
David Howells770bfad2006-08-22 20:06:07 -04001745shouldnt_be_hashed:
1746 spin_unlock(&dcache_lock);
1747 BUG();
David Howells770bfad2006-08-22 20:06:07 -04001748}
1749
Miklos Szeredicdd16d02008-06-23 18:11:53 +02001750static int prepend(char **buffer, int *buflen, const char *str, int namelen)
Ram Pai6092d042008-03-27 13:06:20 +01001751{
1752 *buflen -= namelen;
1753 if (*buflen < 0)
1754 return -ENAMETOOLONG;
1755 *buffer -= namelen;
1756 memcpy(*buffer, str, namelen);
1757 return 0;
1758}
1759
Miklos Szeredicdd16d02008-06-23 18:11:53 +02001760static int prepend_name(char **buffer, int *buflen, struct qstr *name)
1761{
1762 return prepend(buffer, buflen, name->name, name->len);
1763}
1764
Linus Torvalds1da177e2005-04-16 15:20:36 -07001765/**
Miklos Szeredi31f3e0b2008-06-23 18:11:52 +02001766 * __d_path - return the path of a dentry
Miklos Szeredi9d1bc6012008-03-27 13:06:21 +01001767 * @path: the dentry/vfsmount to report
1768 * @root: root vfsmnt/dentry (may be modified by this function)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001769 * @buffer: buffer to return value in
1770 * @buflen: buffer length
1771 *
Linus Torvalds552ce542007-02-13 12:08:18 -08001772 * Convert a dentry into an ASCII path name. If the entry has been deleted
1773 * the string " (deleted)" is appended. Note that this is ambiguous.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001774 *
Linus Torvalds552ce542007-02-13 12:08:18 -08001775 * Returns the buffer or an error code if the path was too long.
1776 *
1777 * "buflen" should be positive. Caller holds the dcache_lock.
Miklos Szeredi9d1bc6012008-03-27 13:06:21 +01001778 *
1779 * If path is not reachable from the supplied root, then the value of
1780 * root is changed (without modifying refcounts).
Linus Torvalds1da177e2005-04-16 15:20:36 -07001781 */
Miklos Szeredi9d1bc6012008-03-27 13:06:21 +01001782char *__d_path(const struct path *path, struct path *root,
1783 char *buffer, int buflen)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001784{
Miklos Szeredi9d1bc6012008-03-27 13:06:21 +01001785 struct dentry *dentry = path->dentry;
1786 struct vfsmount *vfsmnt = path->mnt;
Miklos Szeredicdd16d02008-06-23 18:11:53 +02001787 char *end = buffer + buflen;
1788 char *retval;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001789
Andreas Gruenbacherbe285c72008-06-16 13:28:07 +02001790 spin_lock(&vfsmount_lock);
Ram Pai6092d042008-03-27 13:06:20 +01001791 prepend(&end, &buflen, "\0", 1);
1792 if (!IS_ROOT(dentry) && d_unhashed(dentry) &&
1793 (prepend(&end, &buflen, " (deleted)", 10) != 0))
Linus Torvalds552ce542007-02-13 12:08:18 -08001794 goto Elong;
Linus Torvalds552ce542007-02-13 12:08:18 -08001795
1796 if (buflen < 1)
1797 goto Elong;
1798 /* Get '/' right */
1799 retval = end-1;
1800 *retval = '/';
1801
1802 for (;;) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001803 struct dentry * parent;
1804
Jan Blunck329c97f2008-02-14 19:38:31 -08001805 if (dentry == root->dentry && vfsmnt == root->mnt)
Linus Torvalds552ce542007-02-13 12:08:18 -08001806 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001807 if (dentry == vfsmnt->mnt_root || IS_ROOT(dentry)) {
Linus Torvalds552ce542007-02-13 12:08:18 -08001808 /* Global root? */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001809 if (vfsmnt->mnt_parent == vfsmnt) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001810 goto global_root;
1811 }
1812 dentry = vfsmnt->mnt_mountpoint;
1813 vfsmnt = vfsmnt->mnt_parent;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001814 continue;
1815 }
1816 parent = dentry->d_parent;
1817 prefetch(parent);
Miklos Szeredicdd16d02008-06-23 18:11:53 +02001818 if ((prepend_name(&end, &buflen, &dentry->d_name) != 0) ||
Ram Pai6092d042008-03-27 13:06:20 +01001819 (prepend(&end, &buflen, "/", 1) != 0))
Linus Torvalds552ce542007-02-13 12:08:18 -08001820 goto Elong;
Linus Torvalds552ce542007-02-13 12:08:18 -08001821 retval = end;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001822 dentry = parent;
1823 }
1824
Andreas Gruenbacherbe285c72008-06-16 13:28:07 +02001825out:
1826 spin_unlock(&vfsmount_lock);
Linus Torvalds552ce542007-02-13 12:08:18 -08001827 return retval;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001828
1829global_root:
Ram Pai6092d042008-03-27 13:06:20 +01001830 retval += 1; /* hit the slash */
Miklos Szeredicdd16d02008-06-23 18:11:53 +02001831 if (prepend_name(&retval, &buflen, &dentry->d_name) != 0)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001832 goto Elong;
Miklos Szeredi9d1bc6012008-03-27 13:06:21 +01001833 root->mnt = vfsmnt;
1834 root->dentry = dentry;
Andreas Gruenbacherbe285c72008-06-16 13:28:07 +02001835 goto out;
1836
Linus Torvalds1da177e2005-04-16 15:20:36 -07001837Elong:
Andreas Gruenbacherbe285c72008-06-16 13:28:07 +02001838 retval = ERR_PTR(-ENAMETOOLONG);
1839 goto out;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001840}
1841
Jan Bluncka03a8a702008-02-14 19:38:32 -08001842/**
1843 * d_path - return the path of a dentry
Jan Blunckcf28b482008-02-14 19:38:44 -08001844 * @path: path to report
Jan Bluncka03a8a702008-02-14 19:38:32 -08001845 * @buf: buffer to return value in
1846 * @buflen: buffer length
1847 *
1848 * Convert a dentry into an ASCII path name. If the entry has been deleted
1849 * the string " (deleted)" is appended. Note that this is ambiguous.
1850 *
1851 * Returns the buffer or an error code if the path was too long.
1852 *
Miklos Szeredi31f3e0b2008-06-23 18:11:52 +02001853 * "buflen" should be positive.
Jan Bluncka03a8a702008-02-14 19:38:32 -08001854 */
Jan Engelhardt20d4fdc2008-06-09 16:40:36 -07001855char *d_path(const struct path *path, char *buf, int buflen)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001856{
1857 char *res;
Jan Blunck6ac08c32008-02-14 19:34:38 -08001858 struct path root;
Miklos Szeredi9d1bc6012008-03-27 13:06:21 +01001859 struct path tmp;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001860
Eric Dumazetc23fbb62007-05-08 00:26:18 -07001861 /*
1862 * We have various synthetic filesystems that never get mounted. On
1863 * these filesystems dentries are never used for lookup purposes, and
1864 * thus don't need to be hashed. They also don't need a name until a
1865 * user wants to identify the object in /proc/pid/fd/. The little hack
1866 * below allows us to generate a name for these objects on demand:
1867 */
Jan Blunckcf28b482008-02-14 19:38:44 -08001868 if (path->dentry->d_op && path->dentry->d_op->d_dname)
1869 return path->dentry->d_op->d_dname(path->dentry, buf, buflen);
Eric Dumazetc23fbb62007-05-08 00:26:18 -07001870
Linus Torvalds1da177e2005-04-16 15:20:36 -07001871 read_lock(&current->fs->lock);
Jan Blunck6ac08c32008-02-14 19:34:38 -08001872 root = current->fs->root;
Ram Pai6092d042008-03-27 13:06:20 +01001873 path_get(&root);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001874 read_unlock(&current->fs->lock);
Linus Torvalds552ce542007-02-13 12:08:18 -08001875 spin_lock(&dcache_lock);
Miklos Szeredi9d1bc6012008-03-27 13:06:21 +01001876 tmp = root;
1877 res = __d_path(path, &tmp, buf, buflen);
Linus Torvalds552ce542007-02-13 12:08:18 -08001878 spin_unlock(&dcache_lock);
Jan Blunck6ac08c32008-02-14 19:34:38 -08001879 path_put(&root);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001880 return res;
1881}
1882
1883/*
Eric Dumazetc23fbb62007-05-08 00:26:18 -07001884 * Helper function for dentry_operations.d_dname() members
1885 */
1886char *dynamic_dname(struct dentry *dentry, char *buffer, int buflen,
1887 const char *fmt, ...)
1888{
1889 va_list args;
1890 char temp[64];
1891 int sz;
1892
1893 va_start(args, fmt);
1894 sz = vsnprintf(temp, sizeof(temp), fmt, args) + 1;
1895 va_end(args);
1896
1897 if (sz > sizeof(temp) || sz > buflen)
1898 return ERR_PTR(-ENAMETOOLONG);
1899
1900 buffer += buflen - sz;
1901 return memcpy(buffer, temp, sz);
1902}
1903
1904/*
Ram Pai6092d042008-03-27 13:06:20 +01001905 * Write full pathname from the root of the filesystem into the buffer.
1906 */
1907char *dentry_path(struct dentry *dentry, char *buf, int buflen)
1908{
1909 char *end = buf + buflen;
1910 char *retval;
1911
1912 spin_lock(&dcache_lock);
1913 prepend(&end, &buflen, "\0", 1);
1914 if (!IS_ROOT(dentry) && d_unhashed(dentry) &&
1915 (prepend(&end, &buflen, "//deleted", 9) != 0))
1916 goto Elong;
1917 if (buflen < 1)
1918 goto Elong;
1919 /* Get '/' right */
1920 retval = end-1;
1921 *retval = '/';
1922
Miklos Szeredicdd16d02008-06-23 18:11:53 +02001923 while (!IS_ROOT(dentry)) {
1924 struct dentry *parent = dentry->d_parent;
Ram Pai6092d042008-03-27 13:06:20 +01001925
Ram Pai6092d042008-03-27 13:06:20 +01001926 prefetch(parent);
Miklos Szeredicdd16d02008-06-23 18:11:53 +02001927 if ((prepend_name(&end, &buflen, &dentry->d_name) != 0) ||
Ram Pai6092d042008-03-27 13:06:20 +01001928 (prepend(&end, &buflen, "/", 1) != 0))
1929 goto Elong;
1930
1931 retval = end;
1932 dentry = parent;
1933 }
1934 spin_unlock(&dcache_lock);
1935 return retval;
1936Elong:
1937 spin_unlock(&dcache_lock);
1938 return ERR_PTR(-ENAMETOOLONG);
1939}
1940
1941/*
Linus Torvalds1da177e2005-04-16 15:20:36 -07001942 * NOTE! The user-level library version returns a
1943 * character pointer. The kernel system call just
1944 * returns the length of the buffer filled (which
1945 * includes the ending '\0' character), or a negative
1946 * error value. So libc would do something like
1947 *
1948 * char *getcwd(char * buf, size_t size)
1949 * {
1950 * int retval;
1951 *
1952 * retval = sys_getcwd(buf, size);
1953 * if (retval >= 0)
1954 * return buf;
1955 * errno = -retval;
1956 * return NULL;
1957 * }
1958 */
1959asmlinkage long sys_getcwd(char __user *buf, unsigned long size)
1960{
Linus Torvalds552ce542007-02-13 12:08:18 -08001961 int error;
Jan Blunck6ac08c32008-02-14 19:34:38 -08001962 struct path pwd, root;
Linus Torvalds552ce542007-02-13 12:08:18 -08001963 char *page = (char *) __get_free_page(GFP_USER);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001964
1965 if (!page)
1966 return -ENOMEM;
1967
1968 read_lock(&current->fs->lock);
Jan Blunck6ac08c32008-02-14 19:34:38 -08001969 pwd = current->fs->pwd;
Ram Pai6092d042008-03-27 13:06:20 +01001970 path_get(&pwd);
Jan Blunck6ac08c32008-02-14 19:34:38 -08001971 root = current->fs->root;
Ram Pai6092d042008-03-27 13:06:20 +01001972 path_get(&root);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001973 read_unlock(&current->fs->lock);
1974
Linus Torvalds552ce542007-02-13 12:08:18 -08001975 error = -ENOENT;
1976 /* Has the current directory has been unlinked? */
1977 spin_lock(&dcache_lock);
Miklos Szeredicdd16d02008-06-23 18:11:53 +02001978 if (IS_ROOT(pwd.dentry) || !d_unhashed(pwd.dentry)) {
Linus Torvalds552ce542007-02-13 12:08:18 -08001979 unsigned long len;
Miklos Szeredi9d1bc6012008-03-27 13:06:21 +01001980 struct path tmp = root;
Linus Torvalds552ce542007-02-13 12:08:18 -08001981 char * cwd;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001982
Miklos Szeredi9d1bc6012008-03-27 13:06:21 +01001983 cwd = __d_path(&pwd, &tmp, page, PAGE_SIZE);
Linus Torvalds552ce542007-02-13 12:08:18 -08001984 spin_unlock(&dcache_lock);
1985
1986 error = PTR_ERR(cwd);
1987 if (IS_ERR(cwd))
1988 goto out;
1989
1990 error = -ERANGE;
1991 len = PAGE_SIZE + page - cwd;
1992 if (len <= size) {
1993 error = len;
1994 if (copy_to_user(buf, cwd, len))
1995 error = -EFAULT;
1996 }
1997 } else
1998 spin_unlock(&dcache_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001999
2000out:
Jan Blunck6ac08c32008-02-14 19:34:38 -08002001 path_put(&pwd);
2002 path_put(&root);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002003 free_page((unsigned long) page);
2004 return error;
2005}
2006
2007/*
2008 * Test whether new_dentry is a subdirectory of old_dentry.
2009 *
2010 * Trivially implemented using the dcache structure
2011 */
2012
2013/**
2014 * is_subdir - is new dentry a subdirectory of old_dentry
2015 * @new_dentry: new dentry
2016 * @old_dentry: old dentry
2017 *
2018 * Returns 1 if new_dentry is a subdirectory of the parent (at any depth).
2019 * Returns 0 otherwise.
2020 * Caller must ensure that "new_dentry" is pinned before calling is_subdir()
2021 */
2022
2023int is_subdir(struct dentry * new_dentry, struct dentry * old_dentry)
2024{
2025 int result;
2026 struct dentry * saved = new_dentry;
2027 unsigned long seq;
2028
2029 /* need rcu_readlock to protect against the d_parent trashing due to
2030 * d_move
2031 */
2032 rcu_read_lock();
2033 do {
2034 /* for restarting inner loop in case of seq retry */
2035 new_dentry = saved;
2036 result = 0;
2037 seq = read_seqbegin(&rename_lock);
2038 for (;;) {
2039 if (new_dentry != old_dentry) {
2040 struct dentry * parent = new_dentry->d_parent;
2041 if (parent == new_dentry)
2042 break;
2043 new_dentry = parent;
2044 continue;
2045 }
2046 result = 1;
2047 break;
2048 }
2049 } while (read_seqretry(&rename_lock, seq));
2050 rcu_read_unlock();
2051
2052 return result;
2053}
2054
2055void d_genocide(struct dentry *root)
2056{
2057 struct dentry *this_parent = root;
2058 struct list_head *next;
2059
2060 spin_lock(&dcache_lock);
2061repeat:
2062 next = this_parent->d_subdirs.next;
2063resume:
2064 while (next != &this_parent->d_subdirs) {
2065 struct list_head *tmp = next;
Eric Dumazet5160ee62006-01-08 01:03:32 -08002066 struct dentry *dentry = list_entry(tmp, struct dentry, d_u.d_child);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002067 next = tmp->next;
2068 if (d_unhashed(dentry)||!dentry->d_inode)
2069 continue;
2070 if (!list_empty(&dentry->d_subdirs)) {
2071 this_parent = dentry;
2072 goto repeat;
2073 }
2074 atomic_dec(&dentry->d_count);
2075 }
2076 if (this_parent != root) {
Eric Dumazet5160ee62006-01-08 01:03:32 -08002077 next = this_parent->d_u.d_child.next;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002078 atomic_dec(&this_parent->d_count);
2079 this_parent = this_parent->d_parent;
2080 goto resume;
2081 }
2082 spin_unlock(&dcache_lock);
2083}
2084
2085/**
2086 * find_inode_number - check for dentry with name
2087 * @dir: directory to check
2088 * @name: Name to find.
2089 *
2090 * Check whether a dentry already exists for the given name,
2091 * and return the inode number if it has an inode. Otherwise
2092 * 0 is returned.
2093 *
2094 * This routine is used to post-process directory listings for
2095 * filesystems using synthetic inode numbers, and is necessary
2096 * to keep getcwd() working.
2097 */
2098
2099ino_t find_inode_number(struct dentry *dir, struct qstr *name)
2100{
2101 struct dentry * dentry;
2102 ino_t ino = 0;
2103
Eric W. Biederman3e7e2412006-03-31 02:31:43 -08002104 dentry = d_hash_and_lookup(dir, name);
2105 if (dentry) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002106 if (dentry->d_inode)
2107 ino = dentry->d_inode->i_ino;
2108 dput(dentry);
2109 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002110 return ino;
2111}
2112
2113static __initdata unsigned long dhash_entries;
2114static int __init set_dhash_entries(char *str)
2115{
2116 if (!str)
2117 return 0;
2118 dhash_entries = simple_strtoul(str, &str, 0);
2119 return 1;
2120}
2121__setup("dhash_entries=", set_dhash_entries);
2122
2123static void __init dcache_init_early(void)
2124{
2125 int loop;
2126
2127 /* If hashes are distributed across NUMA nodes, defer
2128 * hash allocation until vmalloc space is available.
2129 */
2130 if (hashdist)
2131 return;
2132
2133 dentry_hashtable =
2134 alloc_large_system_hash("Dentry cache",
2135 sizeof(struct hlist_head),
2136 dhash_entries,
2137 13,
2138 HASH_EARLY,
2139 &d_hash_shift,
2140 &d_hash_mask,
2141 0);
2142
2143 for (loop = 0; loop < (1 << d_hash_shift); loop++)
2144 INIT_HLIST_HEAD(&dentry_hashtable[loop]);
2145}
2146
Denis Cheng74bf17c2007-10-16 23:26:30 -07002147static void __init dcache_init(void)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002148{
2149 int loop;
2150
2151 /*
2152 * A constructor could be added for stable state like the lists,
2153 * but it is probably not worth it because of the cache nature
2154 * of the dcache.
2155 */
Christoph Lameter0a31bd52007-05-06 14:49:57 -07002156 dentry_cache = KMEM_CACHE(dentry,
2157 SLAB_RECLAIM_ACCOUNT|SLAB_PANIC|SLAB_MEM_SPREAD);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002158
Rusty Russell8e1f9362007-07-17 04:03:17 -07002159 register_shrinker(&dcache_shrinker);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002160
2161 /* Hash may have been set up in dcache_init_early */
2162 if (!hashdist)
2163 return;
2164
2165 dentry_hashtable =
2166 alloc_large_system_hash("Dentry cache",
2167 sizeof(struct hlist_head),
2168 dhash_entries,
2169 13,
2170 0,
2171 &d_hash_shift,
2172 &d_hash_mask,
2173 0);
2174
2175 for (loop = 0; loop < (1 << d_hash_shift); loop++)
2176 INIT_HLIST_HEAD(&dentry_hashtable[loop]);
2177}
2178
2179/* SLAB cache for __getname() consumers */
Christoph Lametere18b8902006-12-06 20:33:20 -08002180struct kmem_cache *names_cachep __read_mostly;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002181
2182/* SLAB cache for file structures */
Christoph Lametere18b8902006-12-06 20:33:20 -08002183struct kmem_cache *filp_cachep __read_mostly;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002184
2185EXPORT_SYMBOL(d_genocide);
2186
Linus Torvalds1da177e2005-04-16 15:20:36 -07002187void __init vfs_caches_init_early(void)
2188{
2189 dcache_init_early();
2190 inode_init_early();
2191}
2192
2193void __init vfs_caches_init(unsigned long mempages)
2194{
2195 unsigned long reserve;
2196
2197 /* Base hash sizes on available memory, with a reserve equal to
2198 150% of current kernel size */
2199
2200 reserve = min((mempages - nr_free_pages()) * 3/2, mempages - 1);
2201 mempages -= reserve;
2202
2203 names_cachep = kmem_cache_create("names_cache", PATH_MAX, 0,
Paul Mundt20c2df82007-07-20 10:11:58 +09002204 SLAB_HWCACHE_ALIGN|SLAB_PANIC, NULL);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002205
2206 filp_cachep = kmem_cache_create("filp", sizeof(struct file), 0,
Paul Mundt20c2df82007-07-20 10:11:58 +09002207 SLAB_HWCACHE_ALIGN|SLAB_PANIC, NULL);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002208
Denis Cheng74bf17c2007-10-16 23:26:30 -07002209 dcache_init();
2210 inode_init();
Linus Torvalds1da177e2005-04-16 15:20:36 -07002211 files_init(mempages);
Denis Cheng74bf17c2007-10-16 23:26:30 -07002212 mnt_init();
Linus Torvalds1da177e2005-04-16 15:20:36 -07002213 bdev_cache_init();
2214 chrdev_init();
2215}
2216
2217EXPORT_SYMBOL(d_alloc);
2218EXPORT_SYMBOL(d_alloc_anon);
2219EXPORT_SYMBOL(d_alloc_root);
2220EXPORT_SYMBOL(d_delete);
2221EXPORT_SYMBOL(d_find_alias);
2222EXPORT_SYMBOL(d_instantiate);
2223EXPORT_SYMBOL(d_invalidate);
2224EXPORT_SYMBOL(d_lookup);
2225EXPORT_SYMBOL(d_move);
David Howells770bfad2006-08-22 20:06:07 -04002226EXPORT_SYMBOL_GPL(d_materialise_unique);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002227EXPORT_SYMBOL(d_path);
2228EXPORT_SYMBOL(d_prune_aliases);
2229EXPORT_SYMBOL(d_rehash);
2230EXPORT_SYMBOL(d_splice_alias);
2231EXPORT_SYMBOL(d_validate);
2232EXPORT_SYMBOL(dget_locked);
2233EXPORT_SYMBOL(dput);
2234EXPORT_SYMBOL(find_inode_number);
2235EXPORT_SYMBOL(have_submounts);
2236EXPORT_SYMBOL(names_cachep);
2237EXPORT_SYMBOL(shrink_dcache_parent);
2238EXPORT_SYMBOL(shrink_dcache_sb);