msdosfs Locking Model

This document describes the locking model used by the msdosfs KEXT.

There are five different kinds of locks used by msdosfs.  To avoid deadlock, msdosfs always acquires multiple locks in a specific, consistent order.  The different types of locks are acquired in this order:
	• vnodes (denodes)
	• denode hash
	• rename
	• cluster extent cache (de_cluster_lock)
	• FAT
	• buffer cache

No lock of a particular type may be acquired if any locks of types further down in the list have been acquired.  For example, if the FAT lock is acquired, no vnode locks may be acquired until the FAT lock (and denode hash, rename, or buffer cache locks) are released.  Specific details about each of the above lock types is provided below.

vnodes (denodes)
VFS calls us with a "use count" reference on all vnodes it passes to us.  But the reference does not prevent the underlying object from being renamed or deleted (or another object being created with the same name).  Therefore we cannot depend on a "child" vnode actually being a child of the "parent" vnode, or that the child still exists or still has the same name that was used to look up the vnode.

The de_lock in the denode protects the object.  The lock prevents the object's parent or name from changing (though it doesn't prevent other ancestors from changing, nor prevent the parent's name from changing), and protects changes to the object's size.  For directories, the lock prevents directory entries from being added, removed, or moved; it protects the name space within that directory.  The lock on a directory does not prevent changes to the contents of existing directory entries (other than the deName, and the flags which indicate whether the entry is a long name entry).  The lock on a file (including a symlink) protects that file's directory entry and its contents.

When multiple denodes must be locked, they are locked in order of increasing address (of the denode itself, not the vnode).
	
denode hash
The msdosfs_hash_lock is used to protect the denode hash table (dehashtbl).  It is only locked long enough to search, insert or remove a denode.  When a new denode must be added to the hash, the msdosfs_hash_lock is not held while the denode is initialized (which generally requires I/O).  Instead, a minimally initialized denode with the DE_INIT flag set is inserted into the hash.  When searching for a denode, if the DE_INIT flag is set, then the msdosfs_hash_lock is released, the thread sleeps waiting for DE_INIT to be cleared, and then reacquires the msdosfs_hash_lock to search again.

The msdosfs_hash_lock is global to msdosfs.kext; it is not per-volume.  The hash table is shared by all volumes.

rename
Per-volume lock for renames which "reshape" the hierarchy.  If renaming a directory, and the directory will be moving to a new parent, then the pm_rename_lock is taken.  This prevents the relationship between the "from" directory and the "to" directory from changing while rename verifies that the directory isn't being moved into one of its descendants.
	
cluster extent cache (de_cluster_lock)
This lock is used to protect the "cluster extent cache," which keeps track of the most recently mapped extent of contiguous clusters.  Specifically, it protects the de_cluster_* fields that follow the de_cluster_lock field in struct denode.

FAT
The pm_fat_lock is a per-volume lock which protects that volume's File Allocation Table on disk.

buffer cache
The buffer cache internally acquires a mutex when you "get" or read a buffer.  Only one buffer is acquired at a time.  Operations which affect multiple buffers must release a buffer before accessing another buffer.  Some operations (such as creating or removing a directory entry with multiple long name entries; or allocating or freeing multiple clusters) which affect multiple buffers protect the overall operation with one of the other lock types (for example, a directory's denode lock, or the FAT lock).