FILE SYSTEM(V) 2/9/75 FILE SYSTEM(V)
NAME
fs - format of file system volume
DESCRIPTION
Every file system storage volume (e.g. RF disk, RK disk, RP
disk, DECtape reel) has a common format for certain vital
information. Every such volume is divided into a certain
number of 256 word (512 byte) blocks. Block 0 is unused and
is available to contain a bootstrap program, pack label, or
other information.
Block 1 is the super block. Starting from its first word,
the format of a super-block is
struct {
int isize;
int fsize;
int nfree;
int free[100];
int ninode;
int inode[100];
char flock;
char ilock;
char fmod;
int time[2];
};
Isize is the number of blocks devoted to the i-list, which
starts just after the super-block, in block 2. Fsize is the
first block not potentially available for allocation to a
file. These numbers are used by the system to check for bad
block numbers; if an ``impossible'' block number is
allocated from the free list or is freed, a diagnostic is
written on the on-line console. Moreover, the free array is
cleared, so as to prevent further allocation from a
presumably corrupted free list.
The free list for each volume is maintained as follows. The
free array contains, in free[1], ... , free[nfree-1], up to
99 numbers of free blocks. Free[0] is the block number of
the head of a chain of blocks constituting the free list.
The first word in each free-chain block is the number (up to
100) of free-block numbers listed in the next 100 words of
this chain member. The first of these 100 blocks is the
link to the next member of the chain. To allocate a block:
decrement nfree, and the new block is free[nfree]. If the
new block number is 0, there are no blocks left, so give an
error. If nfree became 0, read in the block named by the
new block number, replace nfree by its first word, and copy
the block numbers in the next 100 words into the free array.
To free a block, check if nfree is 100; if so, copy nfree
and the free array into it, write it out, and set nfree to
0. In any event set free[nfree] to the freed block's number
and increment nfree.
Ninode is the number of free i-numbers in the inode array.
To allocate an i-node: if ninode is greater than 0,
decrement it and return inode[ninode]. If it was 0, read
the i-list and place the numbers of all free inodes (up to
100) into the inode array, then try again. To free an i-
node, provided ninode is less than 100, place its number
into inode[ninode] and increment ninode. If ninode is
already 100, don't bother to enter the freed i-node into any
table. This list of i-nodes is only to speed up the
allocation process; the information as to whether the inode
is really free or not is maintained in the inode itself.
Flock and ilock are flags maintained in the core copy of the
file system while it is mounted and their values on disk are
immaterial. The value of fmod on disk is likewise
immaterial; it is used as a flag to indicate that the
super-block has changed and should be copied to the disk
during the next periodic update of file system information.
Time is the last time the super-block of the file system was
changed, and is a double-precision representation of the
number of seconds that have elapsed since 0000 Jan. 1 1970
(GMT). During a reboot, the time of the super-block for the
root file system is used to set the system's idea of the
time.
I-numbers begin at 1, and the storage for i-nodes begins in
block 2. Also, i-nodes are 32 bytes long, so 16 of them fit
into a block. Therefore, i-node i is located in block
.
(i + 31) / 16, and begins 32 ((i + 31) (mod 16) bytes from
its start. I-node 1 is reserved for the root directory of
the file system, but no other i-number has a built-in
meaning. Each i-node represents one file. The format of an
i-node is as follows.
struct {
int flags; /* +0: see below */
char nlinks; /* +2: number of links to file */
char uid; /* +3: user ID of owner */
char gid; /* +4: group ID of owner */
char size0; /* +5: high byte of 24-bit size */
int size1; /* +6: low word of 24-bit size */
int addr[8]; /* +8: block numbers or device number */
int actime[2]; /* +24: time of last access */
int modtime[2]; /* +28: time of last modification */
};
The flags are as follows:
100000 i-node is allocated
060000 2-bit file type:
000000 plain file
040000 directory
020000 character-type special file
060000 block-type special file.
010000 large file
004000 set user-ID on execution
002000 set group-ID on execution
000400 read (owner)
000200 write (owner)
000100 execute (owner)
000070 read, write, execute (group)
000007 read, write, execute (others)
Special files are recognized by their flags and not by i-
number. A block-type special file is basically one which
can potentially be mounted as a file system; a character-
type special file cannot, though it is not necessarily
character-oriented. For special files the high byte of the
first address word specifies the type of device; the low
byte specifies one of several devices of that type. The
device type numbers of block and character special files
overlap.
The address words of ordinary files and directories contain
the numbers of the blocks in the file (if it is small) or
the numbers of indirect blocks (if the file is large). Byte
number n of a file is accessed as follows. N is divided by
512 to find its logical block number (say b ) in the file.
If the file is small (flag 010000 is 0), then b must be less
than 8, and the physical block number is addr[b].
If the file is large, b is divided by 256 to yield i. If i
is less than 7, then addr[i] is the physical block number of
the indirect block. The remainder from the division yields
the word in the indirect block which contains the number of
the block for the sought-for byte.
If i is equal to 7, then the file has become extra-large
(huge), and addr[7] is the address of a first indirect
block. Each word in this block is the number of a second-
level indirect block; each word in the second-level indirect
blocks points to a data block. Notice that extra-large
files are not marked by any mode bit, but only by having
addr[7] non-zero; and that although this scheme allows for
more than 256X256X512 = 33,554,432 bytes per file, the
length of files is stored in 24 bits so in practice a file
can be at most 16,777,216 bytes long.
For block b in a file to exist, it is not necessary that all
blocks less than b exist. A zero block number either in the
address words of the i-node or in an indirect block
indicates that the corresponding block has never been
allocated. Such a missing block reads as if it contained
all zero words.
SEE ALSO
icheck, dcheck (VIII)