1{\rtf1\ansi\ansicpg1252\cocoartf949\cocoasubrtf270
2{\fonttbl\f0\froman\fcharset0 Times-Roman;\f1\fswiss\fcharset0 Helvetica;\f2\fnil\fcharset0 Monaco;
3}
4{\colortbl;\red255\green255\blue255;}
5\pard\tx720\tx1440\tx2160\tx2880\tx3600\tx4320\tx5040\tx5760\tx6480\tx7200\tx7920\tx8640\qc\pardirnatural
6
7\f0\b\fs36 \cf0 msdosfs Locking Model\
8\pard\tx720\tx1440\tx2160\tx2880\tx3600\tx4320\tx5040\tx5760\tx6480\tx7200\tx7920\tx8640\ql\qnatural\pardirnatural
9
10\f1\b0\fs24 \cf0 \
11This document describes the locking model used by the msdosfs KEXT.\
12\
13There 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:\
14	\'95 vnodes (denodes)\
15	\'95 denode hash\
16	\'95 rename\
17	\'95 cluster extent cache (de_cluster_lock)\
18	\'95 FAT\
19	\'95 buffer cache\
20\
21No 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.\
22\
23
24\b vnodes (denodes)
25\b0 \
26VFS 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.\
27\
28The 
29\f2\fs18 \CocoaLigature0 de_lock
30\f1\fs24 \CocoaLigature1  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.\
31\
32When multiple denodes must be locked, they are locked in order of increasing address (of the denode itself, not the vnode).\
33	\
34
35\b denode hash
36\b0 \
37The 
38\f2\fs18 \CocoaLigature0 msdosfs_hash_lock
39\f1\fs24  is used to protect the denode hash table (
40\f2\fs18 dehashtbl
41\f1\fs24 ).  It is only locked long enough to search, insert or remove a denode.  When a new denode must be added to the hash, the 
42\f2\fs18 msdosfs_hash_lock
43\f1\fs24  is 
44\i not
45\i0  held while the denode is initialized (which generally requires I/O).  Instead, a minimally initialized denode with the 
46\f2\fs18 DE_INIT
47\f1\fs24  flag set is inserted into the hash.  When searching for a denode, if the 
48\f2\fs18 DE_INIT
49\f1\fs24  flag is set, then the 
50\f2\fs18 msdosfs_hash_lock
51\f1\fs24  is released, the thread sleeps waiting for 
52\f2\fs18 DE_INIT
53\f1\fs24  to be cleared, and then reacquires the 
54\f2\fs18 msdosfs_hash_lock
55\f1\fs24  to search again.\
56\
57The 
58\f2\fs18 msdosfs_hash_lock
59\f1\fs24  is global to msdosfs.kext; it is not per-volume.  The hash table is shared by all volumes.\
60\CocoaLigature1 \
61
62\b rename
63\b0 \
64Per-volume lock for renames which "reshape" the hierarchy.  If renaming a directory, and the directory will be moving to a new parent, then the 
65\f2\fs18 \CocoaLigature0 pm_rename_lock
66\f1\fs24 \CocoaLigature1  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.\
67	\
68
69\b cluster extent cache
70\b0  (
71\f2\fs18 de_cluster_lock
72\f1\fs24 )\
73This 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 
74\f2\fs18 de_cluster_
75\f1\fs24 * fields that follow the 
76\f2\fs18 de_cluster_lock
77\f1\fs24  field in 
78\f2\fs18 struct denode
79\f1\fs24 .\
80\
81
82\b FAT
83\b0 \
84The 
85\f2\fs18 \CocoaLigature0 pm_fat_lock
86\f1\fs24 \CocoaLigature1  is a per-volume lock which protects that volume's File Allocation Table on disk.\
87\
88
89\b buffer cache
90\b0 \
91The 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).\
92}