xref: /original-bsd/sys/ufs/lfs/README (revision e59fb703) 
1#	@(#)README	7.3 (Berkeley) 12/06/91
2
3The disk is laid out in segments.  The first segment starts 8K into the
4disk (the first 8K is used for boot information).  Each segment is composed
5of the following:
6
7	An optional super block
8	One or more groups of:
9		segment summary
10		0 or more data blocks
11		0 or more inode blocks
12
13The segment summary and inode/data blocks start after the super block (if
14present), and grow toward the end of the segment.
15
16	_______________________________________________
17	|         |            |         |            |
18	| summary | data/inode | summary | data/inode |
19	|  block  |   blocks   |  block  |   blocks   | ...
20	|_________|____________|_________|____________|
21
22The data/inode blocks following a summary block are described by the
23summary block.  In order to permit the segment to be written in any order
24and in a forward direction only, a checksum is calculated across the
25blocks described by the summary.  Additionally, the summary is checksummed
26and timestamped.  Both of these are intended for recovery; the former is
27to make it easy to determine that it *is* a summary block and the latter
28is to make it easy to determine when recovery is finished for partially
29written segments.
30
31	Summary block (detail)
32	________________
33	| sum cksum    |
34	| data cksum   |
35	| next segment |
36	| timestamp    |
37	| FINFO count  |
38	| inode count  |
39	|______________|
40	|   FINFO-1    | 0 or more file info structures, identifying the
41	|     .        | blocks in the segment.
42	|     .        |
43	|     .        |
44	|   FINFO-N    |
45	|   inode-N    |
46	|     .        |
47	|     .        |
48	|     .        | 0 or more inode daddr_t's, identifying the inode
49	|   inode-1    | blocks in the segment.
50	|______________|
51
52Inode blocks are blocks of on-disk inodes in the same format as those in
53the FFS.  They are packed page_size / sizeof(inode) to a block.  Data blocks
54are exactly as in the FFS.  Both inodes and data blocks move around the
55file system at will.
56
57The file system is described by a super-block which is replicated and
58occurs as the first block of the first and other segments.  (The maximum
59number of super-blocks is MAXNUMSB).  Each super-block maintains a list
60of the disk addresses of all the super-blocks.  The super-block maintains
61a small amount of checkpoint information, essentially just enough to find
62the inode for the IFILE.
63
64The IFILE is visible in the file system, as inode number IFILE_INUM.  It
65contains information shared between the kernel and various user processes.
66
67	Ifile (detail)
68	________________
69	| cleaner info | Cleaner information per file system.  (Page
70	|              | granularity.)
71	|______________|
72	| segment      | Space available and last modified times per
73	| usage table  | segment.  (Page granularity.)
74	|______________|
75	|   IFILE-1    | Per inode status information: current version #,
76	|     .        | if currently allocated, last access time and
77	|     .        | current disk address of containing inode block.
78	|     .        | If current disk address is LFS_UNUSED_DADDR, the
79	|   IFILE-N    | inode is not in use, and it's on the free list.
80	|______________|
81
82
83First Segment at Creation Time:
84_____________________________________________________________
85|        |       |         |       |       |       |       |
86| 8K pad | Super | summary | inode | ifile | root  | l + f |
87|        | block |         | block |       | dir   | dir   |
88|________|_______|_________|_______|_______|_______|_______|
89	  ^
90           Segment starts here.
91
92Some differences from the Sprite LFS implementation.
93
941. The LFS implementation placed the ifile metadata and the super block
95   at fixed locations.  This implementation replicates the super block
96   and puts each at a fixed location.  The checkpoint data is divided into
97   two parts -- just enough information to find the IFILE is stored in
98   two of the super blocks, although it is not toggled between them as in
99   the Sprite implementation.  (This was deliberate, to avoid a single
100   point of failure.)  The remaining checkpoint information is treated as
101   a regular file, which means that the cleaner info, the segment usage
102   table and the ifile meta-data are stored in normal log segments.
103   (Tastes great, less filling...)
104
1052. The segment layout is radically different in Sprite; this implementation
106   uses something a lot like network framing, where data/inode blocks are
107   written asynchronously, and a checksum is used to validate any set of
108   summary and data/inode blocks.  Sprite writes summary blocks synchronously
109   after the data/inode blocks have been written and the existence of the
110   summary block validates the data/inode blocks.  This permits us to write
111   everything contiguously, even partial segments and their summaries, whereas
112   Sprite is forced to seek (from the end of the data inode to the summary
113   which lives at the end of the segment).  Additionally, writing the summary
114   synchronously should cost about 1/2 a rotation per summary.
115
1163. Sprite LFS distinguishes between different types of blocks in the segment.
117   Other than inode blocks and data blocks, we don't.
118
1194. Sprite LFS traverses the IFILE looking for free blocks.  We maintain a
120   free list threaded through the IFILE entries.
121
1225. The cleaner runs in user space, as opposed to kernel space.  It shares
123   information with the kernel by reading/writing the IFILE and through
124   cleaner specific system calls.
125
126