UNIX 16-Bit Filesystem Structure ================================ http://mdfs.net/Docs/Comp/Disk/Format/Unix/16bit The Unix 16-bit filesystem uses 512-byte disk blocks. Blocks are counted with 16-bit numbers from &0000 at the start of the filesystem. The Unix filesystem is also known as UFS and S5FS (System 5 filesystem). Large values are stored 'NUXI' format, that is: 16-bit values: b0-b7, b8-b15 24-bit values: b16-b23, b0-b7, b8-b15 32-bit values: b16-b23, b24-b31, b0-b7, b8-b15 Block &0000 ----------- The first block is not used by the Unix filesystem and can be used by the disk system itself to hold data about the disk. It usually holds boot code to load the initial system code. Block &0001 ----------- Disk superblock. This contains information about the whole disk. 000-001 s_isize : size in blocks of inode table 002-003 s_fsize : size in blocks of entire volume 004-005 s_nfree : number of in-core free blocks (0-100) 006-0CD s_free[100] : in-core free blocks 0CE-0CF s_ninode : number of in-core i-nodes (0-100) 0D0-197 s_inode[100] : in-core free i-nodes (This sentence seems contradictory: When the free space list in the superblock is exhausted, the inode table is scanned to find 100 more blocks.) 198 s_flock : locked during free list manipulation 199 s_ilock : locked during i-list manipulation 19A s_fmod : super block modified flag 19B s_ronly : disk is read-only 19C-19F s_time[2] : date of last update, seconds since 1970 1A0-1FF s_pad[48] : padding (defined as s_pad[50] in source code) Free space ---------- s_free[] is a list of disk block numbers. s_free[1] to s_free[s_nfree] point to free blocks. s_free[0] points to a block which is the start of a chain of free block lists. In the chain of free block lists: 000-001 nfree : number of free blocks in this block list 002-003 flink : next free space block list block, or zero 004- free[] : free blocks The total free space can be calculated by following the chain of free block lists adding nfree-1 at 000-001, and adding s_nfree in the superblock. The total used space is found with s_fsize - total_free. Block &0002 ----------- Block &0002 onwards holds the inode table. Each inode entry is 32 bytes long. An inode is a 16-bit number. inode entries in the inode table are numbered from &0001 upwards. inode 1 is the root directory. If inode 1 has a valid 16-bit allocation vector (inode bytes 8-9 are nonzero), then the file system is a 16-bit Unix filesystem, and inode 1 is the root. If inode 1 does not have a valid 16-bit allocation vector (inode bytes 8-9 are zero), then the file system is a 24-bit Unix filesystem, and inode 2 is the root. inode entry ----------- 000-001 : i_mode - object mode, "adclugsrwxrwxrwx" bit 0 : "x" - executable by world bit 1 : "w" - writable by world bit 2 : "r" - readable by world bit 3 : "x" - executable by group bit 4 : "w" - writable by group bit 5 : "r" - readable by group bit 6 : "x" - executable by owner bit 7 : "w" - writable by owner bit 8 : "r" - readable by owner bit 9 : "s" - save swapped text bit 10 : "g" - set group ID on execution bit 11 : "u" - set user ID on execution bit 12 : "l" - large object bit 13 : "c" - character device "c"+"d"="b" - block device bit 14 : "d" - directory bit 15 : "a" - space allocated on disk 002 : i_nlink - number of directory entries for this object if zero, this inode if free 003 : i_uid - object owner user id 004 : i_gid - object owner groups id 005 : i_size0 - b16-b23 of object size 006-007 : i_size1 - b0-b15 of object size, low byte first 008-017 : i_addr[8] - object allocation vector of eight 16-bit block numbers, or device number for block device If i_mode bit 12 is zero, then the eight blocks pointed to by the allocation vector contain the object's data. The first pointer points to the object's first 512 bytes, the second pointer to the second 512 bytes, etc, up to 8K in total. If i_mode bit 12 is one, then the eight blocks pointed to by the allocation vector each point to a block containing up to 256 block pointers that actually point to the object's contents. The first pointer points to a block that points to the data for the first 128K, the second pointer points to a block that points to the data for the second 128K, etc, up to 1M in total. If i_mode bit 12 is one and the file is larger than 1M, then the eight blocks pointed to by the allocation vector are a double indirected allocation vector. [needs details] If addr[7] is non-zero, the object is a huge file, and addr[7] is the block number of a indirect allocation block. A block number of zero indicates that that part of the object has not been allocated any disk space. 018-01B : i_atime[2] - object last access time, seconds since 1970 01C-01F : i_mtime[2] - object last modified time, seconds since 1970 Directories ----------- Directories are a file with the "d" bit set in the inode entry. The directory contains a list of directory entries in no particular order (other than the first two). The directory entries are usually in the order they were first created. The end of the directory is the end of the directory file. Directory entry --------------- 000-001 : i_node - inode of this object, if zero, this entry is free 002-00F : i_name[14] - object name, padded with NULs The first two entries of a directory are always '..' pointing to the parent, and '.' pointing to the same directory. The subsequent directory entries are not stored in any particular order. Blank disk ========== A blank disk is laid out in the following way: Block &0000 system-specific information Block &0001 superblock Block &0002 inode table Block &rrrr empty root directory Block &nnnn free space block lists The free space block lists and root directory can theoretically be anywhere on the disk, but is is simpler to creater a blank disk with them immediately after the inode table. mkfs6 creates: eg 720K disk: boot% &0000 + 1 system-specific information super% &0001 + 1 superblock !00 isize =32 !02 fsize =1440 !04 nfree =6 !06 &0028 -> next block of free blocks !08 &0027 !10 &0026 !12 &0025 !14 &0024 !16 &0023 !18 &0000 ... !&CE ninode =&0000 !&CF =&0000 itable% &0002 + &20 inode table !00 mode = &C1FF adrwxrwxrwx ?02 nlink = &02 ?03 uid = &00 ?04 gid = &00 ?05 sizehi = &00 !06 sizelo = &20 !08 addr[0]= &0022 first block !24 atime[2] !28 mtime[2] root% &0022 + &01 empty root directory $00 &0001,".." $10 &0001,"." cfree% &0023 + &06 free space block pointed to by superblock contents random lfree%[0] &0028 + &01 free space blocks to load after superblock used !&00 = 100 !&02 = &008C block n+99 -> next block of free blocks !&04 = &008B block n+98 ... !&C4 = &002A block n+1 !&C8 = &0029 block n lfree%[1] &008C + &01 !&00 = 100 !&02 = &00F0 block n+99 -> next block of free blocks ... !&C8 = &008D block n lfree%[2] &00F0 !&00 = 100 !&02 = &0154 block n+99 -> next block of free blocks etc lfree%[13] &053C !&00 = 100 !&02 = &0000 block n+99 => end of chain !&04 = &059F etc. Unused blocks interspersed between free space blocks MkUnix creates: eg 720K disk: boot% &0000 + 1 system-specific information super% &0001 + 1 superblock !00 isize =32 !02 fsize =1440 !04 nfree =6 !06 &0028 -> next block of free blocks !08 &0027 !10 &0026 !12 &0025 !14 &0024 !16 &0023 !18 &0000 ... !&CE ninode =&0000 !&CF =&0000 itable% &0002 + &20 inode table !00 mode = &C1FF adrwxrwxrwx ?02 nlink = &02 ?03 uid = &00 ?04 gid = &00 ?05 sizehi = &00 !06 sizelo = &20 !08 addr[0]= &0022 first block !24 atime[2] !28 mtime[2] root% &0022 + &01 empty root directory $00 &0001,".." $10 &0001,"." cfree% &0023 + &06 free space block pointed to by superblock contents random lfree%[0] &0028 + &01 free space blocks to load after superblock used !&00 = 100 !&02 = &008C block n+99 -> next block of free blocks !&04 = &008B block n+98 ... !&C4 = &002A block n+1 !&C8 = &0029 block n lfree%[1] &0029 + &01 !&00 = 100 !&02 = &00F0 block n+99 -> next block of free blocks ... !&C8 = &008D block n lfree%[2] &002A !&00 = 100 !&02 = &0154 block n+99 -> next block of free blocks etc lfree%[13] &0035 !&00 = 100 !&02 = &0000 block n+99 => end of chain !&04 = &059F etc. bfree% &0036 unused disk blocks dsize% &05A0 Block &0001 ----------- Set all of the superblock to zero, except for the following entries: 000-001 s_isize : mkfs reserves one block for the inode table for every 12.5K of disk space using s_isize = s_fsize / 25. The maximum table size is for 65500 inodes, which gives an s_isize of 1025. (check this) 002-003 s_fsize : size in blocks of entire volume. 004-005 s_nfree : number of in-core free blocks. Set to 100 and place the first 100 free block numbers in s_free[]. 006-0CD s_free[100] : first 100 free blocks. s_free[0] will then be the first block in the free space chain. 19C-19F s_time[2] : set to the creation time/date, seconds since 1970 Block &0002 to block s_isize-1 ------------------------------ Set all blocks of the inode table to zero. Then set the first entry (inode 1) to the following: inode 1 : 000-001 : i_mode : &C1FF for dwrxwrxwrx 002 : i_nlink : set to 2, this makes the root directory undeletable as there is actually only one object pointed to 003 : i_uid : 0 - user=root 004 : i_gid : 0 - group=root 005 : i_sizehi : 0 006-007 : i_sizelo : 32 - two 16-byte directory entries 008-009 : s_isize : block of root directory 018-01F : set both times to creation time/date, same as s_time[] Root directory block -------------------- It is simplest to put this at block s_isize, immediately after the inode table. It just contains the two empty directory entries: 000-001 : &0001 - inode of current directory 002-00F : ".", zero padded 010-011 : &0001 - inode of parent directory 012-01F : "..", zero padded Free blocks list ---------------- It is simplest to put these at s_isize+1, immediately after the empty root directory. The first 100 free blocks will be listed in the superblock. The first of these blocks (ie this block) will be the start of a chain of free blocks. Build the chain of free blocks listing the free blocks. It can be simplest to put all the free block lists immediately after the root directory at s_isize+1, listing all the free blocks on disk that would then start immediately after the chained free block lists. The number of chained free space blocks needed will be: (s_fsize - s_isize - 1) / 100.