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