dentry-locking.txt 8.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173
  1. RCU-based dcache locking model
  2. ==============================
  3. On many workloads, the most common operation on dcache is to look up a
  4. dentry, given a parent dentry and the name of the child. Typically,
  5. for every open(), stat() etc., the dentry corresponding to the
  6. pathname will be looked up by walking the tree starting with the first
  7. component of the pathname and using that dentry along with the next
  8. component to look up the next level and so on. Since it is a frequent
  9. operation for workloads like multiuser environments and web servers,
  10. it is important to optimize this path.
  11. Prior to 2.5.10, dcache_lock was acquired in d_lookup and thus in
  12. every component during path look-up. Since 2.5.10 onwards, fast-walk
  13. algorithm changed this by holding the dcache_lock at the beginning and
  14. walking as many cached path component dentries as possible. This
  15. significantly decreases the number of acquisition of
  16. dcache_lock. However it also increases the lock hold time
  17. significantly and affects performance in large SMP machines. Since
  18. 2.5.62 kernel, dcache has been using a new locking model that uses RCU
  19. to make dcache look-up lock-free.
  20. The current dcache locking model is not very different from the
  21. existing dcache locking model. Prior to 2.5.62 kernel, dcache_lock
  22. protected the hash chain, d_child, d_alias, d_lru lists as well as
  23. d_inode and several other things like mount look-up. RCU-based changes
  24. affect only the way the hash chain is protected. For everything else
  25. the dcache_lock must be taken for both traversing as well as
  26. updating. The hash chain updates too take the dcache_lock. The
  27. significant change is the way d_lookup traverses the hash chain, it
  28. doesn't acquire the dcache_lock for this and rely on RCU to ensure
  29. that the dentry has not been *freed*.
  30. Dcache locking details
  31. ======================
  32. For many multi-user workloads, open() and stat() on files are very
  33. frequently occurring operations. Both involve walking of path names to
  34. find the dentry corresponding to the concerned file. In 2.4 kernel,
  35. dcache_lock was held during look-up of each path component. Contention
  36. and cache-line bouncing of this global lock caused significant
  37. scalability problems. With the introduction of RCU in Linux kernel,
  38. this was worked around by making the look-up of path components during
  39. path walking lock-free.
  40. Safe lock-free look-up of dcache hash table
  41. ===========================================
  42. Dcache is a complex data structure with the hash table entries also
  43. linked together in other lists. In 2.4 kernel, dcache_lock protected
  44. all the lists. We applied RCU only on hash chain walking. The rest of
  45. the lists are still protected by dcache_lock. Some of the important
  46. changes are :
  47. 1. The deletion from hash chain is done using hlist_del_rcu() macro
  48. which doesn't initialize next pointer of the deleted dentry and
  49. this allows us to walk safely lock-free while a deletion is
  50. happening.
  51. 2. Insertion of a dentry into the hash table is done using
  52. hlist_add_head_rcu() which take care of ordering the writes - the
  53. writes to the dentry must be visible before the dentry is
  54. inserted. This works in conjunction with hlist_for_each_rcu() while
  55. walking the hash chain. The only requirement is that all
  56. initialization to the dentry must be done before
  57. hlist_add_head_rcu() since we don't have dcache_lock protection
  58. while traversing the hash chain. This isn't different from the
  59. existing code.
  60. 3. The dentry looked up without holding dcache_lock by cannot be
  61. returned for walking if it is unhashed. It then may have a NULL
  62. d_inode or other bogosity since RCU doesn't protect the other
  63. fields in the dentry. We therefore use a flag DCACHE_UNHASHED to
  64. indicate unhashed dentries and use this in conjunction with a
  65. per-dentry lock (d_lock). Once looked up without the dcache_lock,
  66. we acquire the per-dentry lock (d_lock) and check if the dentry is
  67. unhashed. If so, the look-up is failed. If not, the reference count
  68. of the dentry is increased and the dentry is returned.
  69. 4. Once a dentry is looked up, it must be ensured during the path walk
  70. for that component it doesn't go away. In pre-2.5.10 code, this was
  71. done holding a reference to the dentry. dcache_rcu does the same.
  72. In some sense, dcache_rcu path walking looks like the pre-2.5.10
  73. version.
  74. 5. All dentry hash chain updates must take the dcache_lock as well as
  75. the per-dentry lock in that order. dput() does this to ensure that
  76. a dentry that has just been looked up in another CPU doesn't get
  77. deleted before dget() can be done on it.
  78. 6. There are several ways to do reference counting of RCU protected
  79. objects. One such example is in ipv4 route cache where deferred
  80. freeing (using call_rcu()) is done as soon as the reference count
  81. goes to zero. This cannot be done in the case of dentries because
  82. tearing down of dentries require blocking (dentry_iput()) which
  83. isn't supported from RCU callbacks. Instead, tearing down of
  84. dentries happen synchronously in dput(), but actual freeing happens
  85. later when RCU grace period is over. This allows safe lock-free
  86. walking of the hash chains, but a matched dentry may have been
  87. partially torn down. The checking of DCACHE_UNHASHED flag with
  88. d_lock held detects such dentries and prevents them from being
  89. returned from look-up.
  90. Maintaining POSIX rename semantics
  91. ==================================
  92. Since look-up of dentries is lock-free, it can race against a
  93. concurrent rename operation. For example, during rename of file A to
  94. B, look-up of either A or B must succeed. So, if look-up of B happens
  95. after A has been removed from the hash chain but not added to the new
  96. hash chain, it may fail. Also, a comparison while the name is being
  97. written concurrently by a rename may result in false positive matches
  98. violating rename semantics. Issues related to race with rename are
  99. handled as described below :
  100. 1. Look-up can be done in two ways - d_lookup() which is safe from
  101. simultaneous renames and __d_lookup() which is not. If
  102. __d_lookup() fails, it must be followed up by a d_lookup() to
  103. correctly determine whether a dentry is in the hash table or
  104. not. d_lookup() protects look-ups using a sequence lock
  105. (rename_lock).
  106. 2. The name associated with a dentry (d_name) may be changed if a
  107. rename is allowed to happen simultaneously. To avoid memcmp() in
  108. __d_lookup() go out of bounds due to a rename and false positive
  109. comparison, the name comparison is done while holding the
  110. per-dentry lock. This prevents concurrent renames during this
  111. operation.
  112. 3. Hash table walking during look-up may move to a different bucket as
  113. the current dentry is moved to a different bucket due to rename.
  114. But we use hlists in dcache hash table and they are
  115. null-terminated. So, even if a dentry moves to a different bucket,
  116. hash chain walk will terminate. [with a list_head list, it may not
  117. since termination is when the list_head in the original bucket is
  118. reached]. Since we redo the d_parent check and compare name while
  119. holding d_lock, lock-free look-up will not race against d_move().
  120. 4. There can be a theoretical race when a dentry keeps coming back to
  121. original bucket due to double moves. Due to this look-up may
  122. consider that it has never moved and can end up in a infinite loop.
  123. But this is not any worse that theoretical livelocks we already
  124. have in the kernel.
  125. Important guidelines for filesystem developers related to dcache_rcu
  126. ====================================================================
  127. 1. Existing dcache interfaces (pre-2.5.62) exported to filesystem
  128. don't change. Only dcache internal implementation changes. However
  129. filesystems *must not* delete from the dentry hash chains directly
  130. using the list macros like allowed earlier. They must use dcache
  131. APIs like d_drop() or __d_drop() depending on the situation.
  132. 2. d_flags is now protected by a per-dentry lock (d_lock). All access
  133. to d_flags must be protected by it.
  134. 3. For a hashed dentry, checking of d_count needs to be protected by
  135. d_lock.
  136. Papers and other documentation on dcache locking
  137. ================================================
  138. 1. Scaling dcache with RCU (http://linuxjournal.com/article.php?sid=7124).
  139. 2. http://lse.sourceforge.net/locking/dcache/dcache.html