aboutsummaryrefslogtreecommitdiffstats
path: root/Documentation/filesystems/vfs.txt
diff options
context:
space:
mode:
authorPekka Enberg <penberg@cs.helsinki.fi>2005-11-07 04:01:09 -0500
committerLinus Torvalds <torvalds@g5.osdl.org>2005-11-07 10:53:56 -0500
commitcbf8f0f36a2339f87b9dabbbd301ffd86744620c (patch)
tree5b4e307a5c39cf17d08fb650d1c3d0fa78d52df0 /Documentation/filesystems/vfs.txt
parentcc7d1f8f96a4d048b56edb22e8c5b0f2c2bd7549 (diff)
[PATCH] VFS: split dentry locking documentation
This patch splits dentry locking documentation from Documentation/filesystems/vfs.txt to a separate file. The dentry locking bits are useful but do not fit into the VFS overview document as is. Signed-off-by: Pekka Enberg <penberg@cs.helsinki.fi> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
Diffstat (limited to 'Documentation/filesystems/vfs.txt')
-rw-r--r--Documentation/filesystems/vfs.txt177
1 files changed, 2 insertions, 175 deletions
diff --git a/Documentation/filesystems/vfs.txt b/Documentation/filesystems/vfs.txt
index 821090946a1a..ee4c0a8b8db7 100644
--- a/Documentation/filesystems/vfs.txt
+++ b/Documentation/filesystems/vfs.txt
@@ -721,181 +721,8 @@ manipulate dentries:
721 and the dentry is returned. The caller must use d_put() 721 and the dentry is returned. The caller must use d_put()
722 to free the dentry when it finishes using it. 722 to free the dentry when it finishes using it.
723 723
724 724For further information on dentry locking, please refer to the document
725RCU-based dcache locking model 725Documentation/filesystems/dentry-locking.txt.
726------------------------------
727
728On many workloads, the most common operation on dcache is
729to look up a dentry, given a parent dentry and the name
730of the child. Typically, for every open(), stat() etc.,
731the dentry corresponding to the pathname will be looked
732up by walking the tree starting with the first component
733of the pathname and using that dentry along with the next
734component to look up the next level and so on. Since it
735is a frequent operation for workloads like multiuser
736environments and web servers, it is important to optimize
737this path.
738
739Prior to 2.5.10, dcache_lock was acquired in d_lookup and thus
740in every component during path look-up. Since 2.5.10 onwards,
741fast-walk algorithm changed this by holding the dcache_lock
742at the beginning and walking as many cached path component
743dentries as possible. This significantly decreases the number
744of acquisition of dcache_lock. However it also increases the
745lock hold time significantly and affects performance in large
746SMP machines. Since 2.5.62 kernel, dcache has been using
747a new locking model that uses RCU to make dcache look-up
748lock-free.
749
750The current dcache locking model is not very different from the existing
751dcache locking model. Prior to 2.5.62 kernel, dcache_lock
752protected the hash chain, d_child, d_alias, d_lru lists as well
753as d_inode and several other things like mount look-up. RCU-based
754changes affect only the way the hash chain is protected. For everything
755else the dcache_lock must be taken for both traversing as well as
756updating. The hash chain updates too take the dcache_lock.
757The significant change is the way d_lookup traverses the hash chain,
758it doesn't acquire the dcache_lock for this and rely on RCU to
759ensure that the dentry has not been *freed*.
760
761
762Dcache locking details
763----------------------
764
765For many multi-user workloads, open() and stat() on files are
766very frequently occurring operations. Both involve walking
767of path names to find the dentry corresponding to the
768concerned file. In 2.4 kernel, dcache_lock was held
769during look-up of each path component. Contention and
770cache-line bouncing of this global lock caused significant
771scalability problems. With the introduction of RCU
772in Linux kernel, this was worked around by making
773the look-up of path components during path walking lock-free.
774
775
776Safe lock-free look-up of dcache hash table
777===========================================
778
779Dcache is a complex data structure with the hash table entries
780also linked together in other lists. In 2.4 kernel, dcache_lock
781protected all the lists. We applied RCU only on hash chain
782walking. The rest of the lists are still protected by dcache_lock.
783Some of the important changes are :
784
7851. The deletion from hash chain is done using hlist_del_rcu() macro which
786 doesn't initialize next pointer of the deleted dentry and this
787 allows us to walk safely lock-free while a deletion is happening.
788
7892. Insertion of a dentry into the hash table is done using
790 hlist_add_head_rcu() which take care of ordering the writes -
791 the writes to the dentry must be visible before the dentry
792 is inserted. This works in conjunction with hlist_for_each_rcu()
793 while walking the hash chain. The only requirement is that
794 all initialization to the dentry must be done before hlist_add_head_rcu()
795 since we don't have dcache_lock protection while traversing
796 the hash chain. This isn't different from the existing code.
797
7983. The dentry looked up without holding dcache_lock by cannot be
799 returned for walking if it is unhashed. It then may have a NULL
800 d_inode or other bogosity since RCU doesn't protect the other
801 fields in the dentry. We therefore use a flag DCACHE_UNHASHED to
802 indicate unhashed dentries and use this in conjunction with a
803 per-dentry lock (d_lock). Once looked up without the dcache_lock,
804 we acquire the per-dentry lock (d_lock) and check if the
805 dentry is unhashed. If so, the look-up is failed. If not, the
806 reference count of the dentry is increased and the dentry is returned.
807
8084. Once a dentry is looked up, it must be ensured during the path
809 walk for that component it doesn't go away. In pre-2.5.10 code,
810 this was done holding a reference to the dentry. dcache_rcu does
811 the same. In some sense, dcache_rcu path walking looks like
812 the pre-2.5.10 version.
813
8145. All dentry hash chain updates must take the dcache_lock as well as
815 the per-dentry lock in that order. dput() does this to ensure
816 that a dentry that has just been looked up in another CPU
817 doesn't get deleted before dget() can be done on it.
818
8196. There are several ways to do reference counting of RCU protected
820 objects. One such example is in ipv4 route cache where
821 deferred freeing (using call_rcu()) is done as soon as
822 the reference count goes to zero. This cannot be done in
823 the case of dentries because tearing down of dentries
824 require blocking (dentry_iput()) which isn't supported from
825 RCU callbacks. Instead, tearing down of dentries happen
826 synchronously in dput(), but actual freeing happens later
827 when RCU grace period is over. This allows safe lock-free
828 walking of the hash chains, but a matched dentry may have
829 been partially torn down. The checking of DCACHE_UNHASHED
830 flag with d_lock held detects such dentries and prevents
831 them from being returned from look-up.
832
833
834Maintaining POSIX rename semantics
835==================================
836
837Since look-up of dentries is lock-free, it can race against
838a concurrent rename operation. For example, during rename
839of file A to B, look-up of either A or B must succeed.
840So, if look-up of B happens after A has been removed from the
841hash chain but not added to the new hash chain, it may fail.
842Also, a comparison while the name is being written concurrently
843by a rename may result in false positive matches violating
844rename semantics. Issues related to race with rename are
845handled as described below :
846
8471. Look-up can be done in two ways - d_lookup() which is safe
848 from simultaneous renames and __d_lookup() which is not.
849 If __d_lookup() fails, it must be followed up by a d_lookup()
850 to correctly determine whether a dentry is in the hash table
851 or not. d_lookup() protects look-ups using a sequence
852 lock (rename_lock).
853
8542. The name associated with a dentry (d_name) may be changed if
855 a rename is allowed to happen simultaneously. To avoid memcmp()
856 in __d_lookup() go out of bounds due to a rename and false
857 positive comparison, the name comparison is done while holding the
858 per-dentry lock. This prevents concurrent renames during this
859 operation.
860
8613. Hash table walking during look-up may move to a different bucket as
862 the current dentry is moved to a different bucket due to rename.
863 But we use hlists in dcache hash table and they are null-terminated.
864 So, even if a dentry moves to a different bucket, hash chain
865 walk will terminate. [with a list_head list, it may not since
866 termination is when the list_head in the original bucket is reached].
867 Since we redo the d_parent check and compare name while holding
868 d_lock, lock-free look-up will not race against d_move().
869
8704. There can be a theoretical race when a dentry keeps coming back
871 to original bucket due to double moves. Due to this look-up may
872 consider that it has never moved and can end up in a infinite loop.
873 But this is not any worse that theoretical livelocks we already
874 have in the kernel.
875
876
877Important guidelines for filesystem developers related to dcache_rcu
878====================================================================
879
8801. Existing dcache interfaces (pre-2.5.62) exported to filesystem
881 don't change. Only dcache internal implementation changes. However
882 filesystems *must not* delete from the dentry hash chains directly
883 using the list macros like allowed earlier. They must use dcache
884 APIs like d_drop() or __d_drop() depending on the situation.
885
8862. d_flags is now protected by a per-dentry lock (d_lock). All
887 access to d_flags must be protected by it.
888
8893. For a hashed dentry, checking of d_count needs to be protected
890 by d_lock.
891
892
893Papers and other documentation on dcache locking
894================================================
895
8961. Scaling dcache with RCU (http://linuxjournal.com/article.php?sid=7124).
897
8982. http://lse.sourceforge.net/locking/dcache/dcache.html
899 726
900 727
901Resources 728Resources