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