| blob | 7d00ceaa4efd8fb745f6ad851b5c32ab3bd691e2 |
1 .\" Copyright (c) 1982, 1993
2 .\" The Regents of the University of California. All rights reserved.
3 .\"
4 .\" Redistribution and use in source and binary forms, with or without
5 .\" modification, are permitted provided that the following conditions
6 .\" are met:
7 .\" 1. Redistributions of source code must retain the above copyright
8 .\" notice, this list of conditions and the following disclaimer.
9 .\" 2. Redistributions in binary form must reproduce the above copyright
10 .\" notice, this list of conditions and the following disclaimer in the
11 .\" documentation and/or other materials provided with the distribution.
12 .\" 3. All advertising materials mentioning features or use of this software
13 .\" must display the following acknowledgement:
14 .\" This product includes software developed by the University of
15 .\" California, Berkeley and its contributors.
16 .\" 4. Neither the name of the University nor the names of its contributors
17 .\" may be used to endorse or promote products derived from this software
18 .\" without specific prior written permission.
19 .\"
20 .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 .\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 .\" SUCH DAMAGE.
31 .\"
32 .\" @(#)2.t 8.1 (Berkeley) 6/5/93
33 .\"
34 .ds RH Overview of the file system
35 .NH
36 Overview of the file system
37 .PP
38 The file system is discussed in detail in [Mckusick84];
39 this section gives a brief overview.
40 .NH 2
41 Superblock
42 .PP
43 A file system is described by its
44 .I "super-block" .
45 The super-block is built when the file system is created (\c
46 .I newfs (8))
47 and never changes.
48 The super-block
49 contains the basic parameters of the file system,
50 such as the number of data blocks it contains
51 and a count of the maximum number of files.
52 Because the super-block contains critical data,
53 .I newfs
54 replicates it to protect against catastrophic loss.
55 The
56 .I "default super block"
57 always resides at a fixed offset from the beginning
58 of the file system's disk partition.
59 The
60 .I "redundant super blocks"
61 are not referenced unless a head crash
62 or other hard disk error causes the default super-block
63 to be unusable.
64 The redundant blocks are sprinkled throughout the disk partition.
65 .PP
66 Within the file system are files.
67 Certain files are distinguished as directories and contain collections
68 of pointers to files that may themselves be directories.
69 Every file has a descriptor associated with it called an
70 .I "inode".
71 The inode contains information describing ownership of the file,
72 time stamps indicating modification and access times for the file,
73 and an array of indices pointing to the data blocks for the file.
74 In this section,
75 we assume that the first 12 blocks
76 of the file are directly referenced by values stored
77 in the inode structure itself\(dg.
78 .FS
79 \(dgThe actual number may vary from system to system, but is usually in
80 the range 5-13.
81 .FE
82 The inode structure may also contain references to indirect blocks
83 containing further data block indices.
84 In a file system with a 4096 byte block size, a singly indirect
85 block contains 1024 further block addresses,
86 a doubly indirect block contains 1024 addresses of further single indirect
87 blocks,
88 and a triply indirect block contains 1024 addresses of further doubly indirect
89 blocks (the triple indirect block is never needed in practice).
90 .PP
91 In order to create files with up to
92 2\(ua32 bytes,
93 using only two levels of indirection,
94 the minimum size of a file system block is 4096 bytes.
95 The size of file system blocks can be any power of two
96 greater than or equal to 4096.
97 The block size of the file system is maintained in the super-block,
98 so it is possible for file systems of different block sizes
99 to be accessible simultaneously on the same system.
100 The block size must be decided when
101 .I newfs
102 creates the file system;
103 the block size cannot be subsequently
104 changed without rebuilding the file system.
105 .NH 2
106 Summary information
107 .PP
108 Associated with the super block is non replicated
109 .I "summary information" .
110 The summary information changes
111 as the file system is modified.
112 The summary information contains
113 the number of blocks, fragments, inodes and directories in the file system.
114 .NH 2
115 Cylinder groups
116 .PP
117 The file system partitions the disk into one or more areas called
118 .I "cylinder groups".
119 A cylinder group is comprised of one or more consecutive
120 cylinders on a disk.
121 Each cylinder group includes inode slots for files, a
122 .I "block map"
123 describing available blocks in the cylinder group,
124 and summary information describing the usage of data blocks
125 within the cylinder group.
126 A fixed number of inodes is allocated for each cylinder group
127 when the file system is created.
128 The current policy is to allocate one inode for each 2048
129 bytes of disk space;
130 this is expected to be far more inodes than will ever be needed.
131 .PP
132 All the cylinder group bookkeeping information could be
133 placed at the beginning of each cylinder group.
134 However if this approach were used,
135 all the redundant information would be on the top platter.
136 A single hardware failure that destroyed the top platter
137 could cause the loss of all copies of the redundant super-blocks.
138 Thus the cylinder group bookkeeping information
139 begins at a floating offset from the beginning of the cylinder group.
140 The offset for
141 the
142 .I "i+1" st
143 cylinder group is about one track further
144 from the beginning of the cylinder group
145 than it was for the
146 .I "i" th
147 cylinder group.
148 In this way,
149 the redundant
150 information spirals down into the pack;
151 any single track, cylinder,
152 or platter can be lost without losing all copies of the super-blocks.
153 Except for the first cylinder group,
154 the space between the beginning of the cylinder group
155 and the beginning of the cylinder group information stores data.
156 .NH 2
157 Fragments
158 .PP
159 To avoid waste in storing small files,
160 the file system space allocator divides a single
161 file system block into one or more
162 .I "fragments".
163 The fragmentation of the file system is specified
164 when the file system is created;
165 each file system block can be optionally broken into
166 2, 4, or 8 addressable fragments.
167 The lower bound on the size of these fragments is constrained
168 by the disk sector size;
169 typically 512 bytes is the lower bound on fragment size.
170 The block map associated with each cylinder group
171 records the space availability at the fragment level.
172 Aligned fragments are examined
173 to determine block availability.
174 .PP
175 On a file system with a block size of 4096 bytes
176 and a fragment size of 1024 bytes,
177 a file is represented by zero or more 4096 byte blocks of data,
178 and possibly a single fragmented block.
179 If a file system block must be fragmented to obtain
180 space for a small amount of data,
181 the remainder of the block is made available for allocation
182 to other files.
183 For example,
184 consider an 11000 byte file stored on
185 a 4096/1024 byte file system.
186 This file uses two full size blocks and a 3072 byte fragment.
187 If no fragments with at least 3072 bytes
188 are available when the file is created,
189 a full size block is split yielding the necessary 3072 byte
190 fragment and an unused 1024 byte fragment.
191 This remaining fragment can be allocated to another file, as needed.
192 .NH 2
193 Updates to the file system
194 .PP
195 Every working day hundreds of files
196 are created, modified, and removed.
197 Every time a file is modified,
198 the operating system performs a
199 series of file system updates.
200 These updates, when written on disk, yield a consistent file system.
201 The file system stages
202 all modifications of critical information;
203 modification can
204 either be completed or cleanly backed out after a crash.
205 Knowing the information that is first written to the file system,
206 deterministic procedures can be developed to
207 repair a corrupted file system.
208 To understand this process,
209 the order that the update
210 requests were being honored must first be understood.
211 .PP
212 When a user program does an operation to change the file system,
213 such as a
214 .I write ,
215 the data to be written is copied into an internal
216 .I "in-core"
217 buffer in the kernel.
218 Normally, the disk update is handled asynchronously;
219 the user process is allowed to proceed even though
220 the data has not yet been written to the disk.
221 The data,
222 along with the inode information reflecting the change,
223 is eventually written out to disk.
224 The real disk write may not happen until long after the
225 .I write
226 system call has returned.
227 Thus at any given time, the file system,
228 as it resides on the disk,
229 lags the state of the file system represented by the in-core information.
230 .PP
231 The disk information is updated to reflect the in-core information
232 when the buffer is required for another use,
233 when a
234 .I sync (2)
235 is done (at 30 second intervals) by
236 .I "/etc/update" "(8),"
237 or by manual operator intervention with the
238 .I sync (8)
239 command.
240 If the system is halted without writing out the in-core information,
241 the file system on the disk will be in an inconsistent state.
242 .PP
243 If all updates are done asynchronously, several serious
244 inconsistencies can arise.
245 One inconsistency is that a block may be claimed by two inodes.
246 Such an inconsistency can occur when the system is halted before
247 the pointer to the block in the old inode has been cleared
248 in the copy of the old inode on the disk,
249 and after the pointer to the block in the new inode has been written out
250 to the copy of the new inode on the disk.
251 Here,
252 there is no deterministic method for deciding
253 which inode should really claim the block.
254 A similar problem can arise with a multiply claimed inode.
255 .PP
256 The problem with asynchronous inode updates
257 can be avoided by doing all inode deallocations synchronously.
258 Consequently,
259 inodes and indirect blocks are written to the disk synchronously
260 (\fIi.e.\fP the process blocks until the information is
261 really written to disk)
262 when they are being deallocated.
263 Similarly inodes are kept consistent by synchronously
264 deleting, adding, or changing directory entries.
265 .ds RH Fixing corrupted file systems