4 The cache/WORM (cw) driver is by far the
5 largest and most complicated device driver in the file server.
6 There are four devices involved in the cw driver.
7 It implements a read/write pseudo-device (the cw-device)
8 and a read-only pseudo-device (the dump device)
9 by performing operations on its two constituent devices
10 the read-write c-device and the write-once-read-many
12 The block numbers on the four devices are distinct,
22 The cw-driver uses the w-device as the
23 stable storage of the file system at the time of the
25 All newly written and a large number of recently used
26 exact copies of blocks of the w-device are kept on the c-device.
27 The c-device is much smaller than the w-device and
28 so the subset of w-blocks that are kept on the c-device are
29 mapped through a hash table kept on a partition of the c-device.
31 The map portion of the c-device consists of blocks of buckets of entries.
32 The declarations follow.
37 CEPERBK = (BUFSIZE - BKPERBLK*sizeof(Off)) /
38 (sizeof(Centry)*BKPERBLK),
55 Centry entry[CEPERBK];
59 Bucket bucket[BKPERBLK];
61 There is exactly one entry structure for each block in the
62 data partition of the c-device.
63 A bucket contains all of the w-addresses that have
65 There are as many buckets as will fit
66 in a block and enough blocks to have the required
68 The entries in the bucket are maintained
69 in FIFO order with an age variable and an incrementing age generator.
70 When the age generator is about to overflow,
71 all of the ages in the bucket are rescaled
74 The following steps go into converting a w-address into a c-address.
75 The bucket is found by
77 bucket_number = w-address % total_buckets;
78 getbuf(c-device, bucket_offset + bucket_number/BKPERBLK);
80 After the desired bucket is found,
81 the desired entry is found by a linear search within the bucket for the
82 entry with the desired
85 The state variable in the entry is
98 Every w-address has a state.
99 Blocks that are not in the
100 c-device have the implied
105 state is for blocks that have the
106 same data as the corresponding block in
108 Since the c-device is much faster than the
111 blocks are kept as long as possible and
112 used in preference to reading the w-device.
114 blocks may be discarded from the c-device
115 when the space is needed for newer data.
118 state is when the c-device contains newer data
119 than the corresponding block on the w-device.
129 is when the c-device contains
130 new data and the corresponding block
131 on the w-device has never been written.
132 This happens when a new block has been
133 allocated from the free space on the w-device.
139 blocks are created and never removed.
140 Unless something is done to
141 convert these blocks,
142 the c-device will gradually
143 fill up and stop functioning.
151 a dump is to queue the writes that
152 have been shunted to the c-device
153 to be written to the w-device.
154 Since the w-device is a WORM,
155 blocks cannot be rewritten.
156 Blocks that have already been written to the WORM must be
157 relocated to the unused portion of the w-device.
158 These are precisely the
163 The dump algorithm is as follows:
165 The tree on the cw-device is walked
166 as long as the blocks visited have been
167 modified since the last dump.
168 These are the blocks with state
172 It is possible to restrict the search
173 to within these blocks
174 since the directory containing a modified
175 file must have been accessed to modify the
176 file and accessing a directory will set its
177 modified time thus causing the block containing it
179 The directory containing that directory must be
180 modified for the same reason.
181 The tree walk is thus drastically restrained and the
182 tree walk does not take much time.
186 blocks found in the tree search
187 are relocated to new blank blocks on the w-device
193 blocks are converted to
195 state without relocation.
197 all modified blocks in the cw-device
198 have w-addresses that point to unwritten
200 These blocks are marked for later
201 writing to the w-device
205 All open files that were pointing to modified
206 blocks are reopened to point at the corresponding
208 This causes the directories leading to the
209 open files to be modified.
210 Thus the invariant discussed in a) is maintained.
212 The background dumping process will slowly
213 go through the map of the c-device and write out
218 The dump takes a few minutes to walk the tree
220 It can take hours to write the marked blocks
222 If a marked block is rewritten before the old
223 copy has been written to the WORM,
224 it must be forced to the WORM before it is rewritten.
225 There is no problem if another dump is taken before the first one
227 The newly marked blocks are just added to the marked blocks
228 left from the first dump.
230 If there is an error writing a marked block
234 state is converted to
236 and manual intervention is needed.
242 These blocks can be disposed of by converting
245 so that they will be written again.
246 They can also be converted to
248 state so that they will be allocated new
249 addresses at the next dump.
250 In most other respects,