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