1.SH 2The server processes 3.PP 4The main file system algorithm is a set 5of identical processes 6named 7.CW srv 8that honor the 99P protocol. 10Each file system process waits on 11a message queue for an incoming request. 12The request contains a 9P message and 13the address of a reply queue. 14A 15.CW srv 16process parses the message, 17performs pseudo-disk I/O 18to the corresponding file system block device, 19formulates a response, 20and sends the 21response back to the reply queue. 22.PP 23The unit of storage is a 24logical block 25(not physical sector) of data on a device: 26.Ex 27.TA 0.5i 1i 1.5i 2i 2.5i 3i 3.5i 4i 4.5i 5i 5.5i 28 enum 29 { 30 RBUFSIZE = 8*1024 31 }; 32 33 typedef vlong Off; 34 typedef 35 struct 36 { 37 short pad; 38 short tag; 39 Off path; 40 } Tag; 41 42 enum 43 { 44 BUFSIZE = RBUFSIZE - sizeof(Tag) 45 }; 46 47 typedef 48 struct 49 { 50 uchar data[BUFSIZE]; 51 Tag tag; 52 } Block; 53.Ee 54All devices are idealized as a perfect disk 55of contiguously numbered blocks each of size 56.CW RBUFSIZE . 57Each block has a tag that identifies what type 58of block it is and a unique id of the file or directory 59where this block resides. 60The remaining data in the block depends on 61what type of block it is. 62.PP 63The 64.CW srv 65process's main data structure is the directory entry. 66This is the equivalent of a UNIX i-node and 67defines the set of block addresses that comprise a file or directory. 68Unlike the i-node, 69the directory entry also has the name of the 70file or directory in it: 71.Ex 72 enum 73 { 74 NAMELEN = 56, 75 NDBLOCK = 6, 76 NIBLOCK = 4, 77 }; 78.Ee 79.Ex 80 typedef 81 struct 82 { 83 char name[NAMELEN]; 84 short uid; 85 short gid; 86 ushort mode; 87 short wuid; 88 Qid qid; 89 Off size; 90 Off dblock[NDBLOCK]; 91 Off iblocks[NIBLOCK]; 92 long atime; 93 long mtime; 94 } Dentry; 95.Ee 96Each directory entry holds the file or directory 97name, protection mode, access times, user-id, group-id, and addressing 98information. 99The entry 100.CW wuid 101is the user-id of the last writer of the file 102and 103.CW size 104is the size of the file in bytes. 105The addresses of the first 6 106blocks of the file are held in the 107.CW dblock 108array. 109If the file is larger than that, 110an indirect block is allocated that holds 111the next 112.CW BUFSIZE/sizeof(Off) 113block addresses of the file. 114The indirect block address is held in 115.CW iblocks[0] . 116If the file is larger yet, 117then there is a double indirect block that points 118at indirect blocks. 119The double indirect address is held in 120.CW iblocks[1] 121and can point at another 122.CW (BUFSIZE/sizeof(Off))\u\s-2\&2\s+2\d 123blocks of data. 124This is extended through a quadruple indirect block at 125.CW iblocks[3] 126but the code is now parameterised to permit easily changing the 127number of direct blocks and the depth of indirect blocks, 128and also the maximum size of a file name component. 129The maximum addressable size of a file is 130therefore 7.93 petabytes at a block size of 8k, 131but 7.98 exabytes (just under $2 sup 63$ bytes) at a block size of 32k. 132File size is restricted to $2 sup 63 - 1$ bytes in any case 133because the length of a file is maintained in a 134(signed) 135.I vlong . 136These numbers are based on 137.I fs64 138which has a block size of 8k and 139.CW sizeof(Off) 140is 8. 141.PP 142The declarations of the indirect and double indirect blocks 143are as follows. 144.Ex 145 enum 146 { 147 INDPERBUF = BUFSIZE/sizeof(Off), 148 }; 149.Ee 150.Ex 151 typedef 152 { 153 Off dblock[INDPERBUF]; 154 Tag ibtag; 155 } Iblock; 156.Ee 157.Ex 158 typedef 159 { 160 Off iblock[INDPERBUF]; 161 Tag dibtag; 162 } Diblock; 163.Ee 164.PP 165The root of a file system is a single directory entry 166at a known block address. 167A directory is a file that consists of a list of 168directory entries. 169To make access easier, 170a directory entry cannot cross blocks. 171In 172.I fs64 173there are 47 directory entries per block. 174.PP 175The device on which the blocks reside is implicit 176and ultimately comes from the 9P 177.CW attach 178message that specifies the name of the 179device containing the root. 180