README revision 1.1 
1#	from: @(#)README	8.1 (Berkeley) 6/11/93
2#	$Id: README,v 1.1 1994/06/08 11:42:16 mycroft Exp $
3
4The file system is reasonably stable, but incomplete.  There are
5places where cleaning performance can be improved dramatically (see
6comments in lfs_syscalls.c).  For details on the implementation,
7performance and why garbage collection always wins, see Dr. Margo
8Seltzer's thesis available for anonymous ftp from toe.cs.berkeley.edu,
9in the directory pub/personal/margo/thesis.ps.Z, or the January 1993
10USENIX paper.
11
12Missing Functionality:
13	Multiple block sizes and/or fragments are not yet implemented.
14
15----------
16The disk is laid out in segments.  The first segment starts 8K into the
17disk (the first 8K is used for boot information).  Each segment is composed
18of the following:
19
20	An optional super block
21	One or more groups of:
22		segment summary
23		0 or more data blocks
24		0 or more inode blocks
25
26The segment summary and inode/data blocks start after the super block (if
27present), and grow toward the end of the segment.
28
29	_______________________________________________
30	|         |            |         |            |
31	| summary | data/inode | summary | data/inode |
32	|  block  |   blocks   |  block  |   blocks   | ...
33	|_________|____________|_________|____________|
34
35The data/inode blocks following a summary block are described by the
36summary block.  In order to permit the segment to be written in any order
37and in a forward direction only, a checksum is calculated across the
38blocks described by the summary.  Additionally, the summary is checksummed
39and timestamped.  Both of these are intended for recovery; the former is
40to make it easy to determine that it *is* a summary block and the latter
41is to make it easy to determine when recovery is finished for partially
42written segments.  These checksums are also used by the cleaner.
43
44	Summary block (detail)
45	________________
46	| sum cksum    |
47	| data cksum   |
48	| next segment |
49	| timestamp    |
50	| FINFO count  |
51	| inode count  |
52	| flags        |
53	|______________|
54	|   FINFO-1    | 0 or more file info structures, identifying the
55	|     .        | blocks in the segment.
56	|     .        |
57	|     .        |
58	|   FINFO-N    |
59	|   inode-N    |
60	|     .        |
61	|     .        |
62	|     .        | 0 or more inode daddr_t's, identifying the inode
63	|   inode-1    | blocks in the segment.
64	|______________|
65
66Inode blocks are blocks of on-disk inodes in the same format as those in
67the FFS.  However, spare[0] contains the inode number of the inode so we
68can find a particular inode on a page.  They are packed page_size /
69sizeof(inode) to a block.  Data blocks are exactly as in the FFS.  Both
70inodes and data blocks move around the file system at will.
71
72The file system is described by a super-block which is replicated and
73occurs as the first block of the first and other segments.  (The maximum
74number of super-blocks is MAXNUMSB).  Each super-block maintains a list
75of the disk addresses of all the super-blocks.  The super-block maintains
76a small amount of checkpoint information, essentially just enough to find
77the inode for the IFILE (fs->lfs_idaddr).
78
79The IFILE is visible in the file system, as inode number IFILE_INUM.  It
80contains information shared between the kernel and various user processes.
81
82	Ifile (detail)
83	________________
84	| cleaner info | Cleaner information per file system.  (Page
85	|              | granularity.)
86	|______________|
87	| segment      | Space available and last modified times per
88	| usage table  | segment.  (Page granularity.)
89	|______________|
90	|   IFILE-1    | Per inode status information: current version #,
91	|     .        | if currently allocated, last access time and
92	|     .        | current disk address of containing inode block.
93	|     .        | If current disk address is LFS_UNUSED_DADDR, the
94	|   IFILE-N    | inode is not in use, and it's on the free list.
95	|______________|
96
97
98First Segment at Creation Time:
99_____________________________________________________________
100|        |       |         |       |       |       |       |
101| 8K pad | Super | summary | inode | ifile | root  | l + f |
102|        | block |         | block |       | dir   | dir   |
103|________|_______|_________|_______|_______|_______|_______|
104	  ^
105           Segment starts here.
106
107Some differences from the Sprite LFS implementation.
108
1091. The LFS implementation placed the ifile metadata and the super block
110   at fixed locations.  This implementation replicates the super block
111   and puts each at a fixed location.  The checkpoint data is divided into
112   two parts -- just enough information to find the IFILE is stored in
113   two of the super blocks, although it is not toggled between them as in
114   the Sprite implementation.  (This was deliberate, to avoid a single
115   point of failure.)  The remaining checkpoint information is treated as
116   a regular file, which means that the cleaner info, the segment usage
117   table and the ifile meta-data are stored in normal log segments.
118   (Tastes great, less filling...)
119
1202. The segment layout is radically different in Sprite; this implementation
121   uses something a lot like network framing, where data/inode blocks are
122   written asynchronously, and a checksum is used to validate any set of
123   summary and data/inode blocks.  Sprite writes summary blocks synchronously
124   after the data/inode blocks have been written and the existence of the
125   summary block validates the data/inode blocks.  This permits us to write
126   everything contiguously, even partial segments and their summaries, whereas
127   Sprite is forced to seek (from the end of the data inode to the summary
128   which lives at the end of the segment).  Additionally, writing the summary
129   synchronously should cost about 1/2 a rotation per summary.
130
1313. Sprite LFS distinguishes between different types of blocks in the segment.
132   Other than inode blocks and data blocks, we don't.
133
1344. Sprite LFS traverses the IFILE looking for free blocks.  We maintain a
135   free list threaded through the IFILE entries.
136
1375. The cleaner runs in user space, as opposed to kernel space.  It shares
138   information with the kernel by reading/writing the IFILE and through
139   cleaner specific system calls.
140
141