.th "FILE SYSTEM" V 2/9/75
.sh NAME
fs \*- format of file system volume
.sh 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.
.s3
Block 1 is the
.it "super block."
Starting from its first word, the format of a super-block is
.s3
.nf
struct {
	int	isize;
	int	fsize;
	int	nfree;
	int	free[100];
	int	ninode;
	int	inode[100];
	char	flock;
	char	ilock;
	char	fmod;
	int	time[2];
};
.s3
.fi
.it Isize
is the number of blocks devoted to the i-list,
which starts just after the super-block, in block 2.
.it 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.
.s3
The free list for each volume is maintained as
follows.
The
.it free
array contains, in
.it "free[1], ... , free[nfree\*-1],"
up to 99 numbers of free blocks.
.it 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
.it nfree,
and the new block is
.it free[nfree].
If the new block number is 0,
there are no blocks left, so give an error.
If
.it nfree
became 0,
read in the block named by the new block number,
replace
.it nfree
by its first word,
and copy the block numbers in the next 100 words into the
.it free
array.
To free a block, check if
.it nfree
is 100; if so,
copy
.it nfree
and the
.it free
array into it,
write it out, and set
.it nfree
to 0.
In any event set
.it free[nfree]
to the freed block's number and
increment
.it nfree.
.s3
.it Ninode
is the number of free i-numbers in the
.it inode
array.
To allocate an i-node:
if
.it ninode
is greater than 0,
decrement it and return
.it inode[ninode].
If it was 0, read the i-list
and place the numbers of all free inodes
(up to 100) into the
.it inode
array,
then try again.
To free an i-node,
provided
.it ninode
is less than 100,
place its number into
.it inode[ninode]
and increment
.it ninode.
If
.it 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.
.s3
.it Flock
and
.it 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
.it 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.
.s3
.it 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
.it time
of the super-block for the root file system
is used to set the system's idea of the time.
.s3
I-numbers begin at 1, and the storage for i-nodes
begins in block 2.
.tr |
Also, i-nodes are 32 bytes long, so 16 of them fit into a block.
Therefore, i-node
.it i
is located in block (\fIi\fR|+|31)|/|16, and begins
32\u\fB.\fR\d((\fIi\fR|+|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.
.s3
.nf
.if t .ta .5i 1.i 2.5i
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 */
};
.dt
.fi
.s3
The flags are as follows:
.s3
.lp +10 9
100000	i-node is allocated
.lp +10 9
060000	2-bit file type:
.lp +15 9
000000	plain file
.lp +15 9
040000	directory
.lp +15 9
020000	character-type special file
.lp +15 9
060000	block-type special file.
.lp +10 9
010000	large file
.lp +10 9
004000	set user-ID on execution
.lp +10 9
002000	set group-ID on execution
.lp +10 9
000400	read (owner)
.lp +10 9
000200	write (owner)
.lp +10 9
000100	execute (owner)
.lp +10 9
000070	read, write, execute (group)
.lp +10 9
000007	read, write, execute (others)
.s3
.i0
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.
.s3
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
.it n
of a file is accessed as follows.
.it N
is divided by 512 to find its logical block number
(say
.it b
)
in the file.
If the file is small (flag 010000 is 0),
then
.it b
must be less than 8, and the physical
block number is
.it addr[b].
.s3
If the file is large,
.it b
is divided by 256 to yield
.it i.
If
.it i
is less than 7, then
.it 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.
.s3
If
.it i
is equal to 7,
then the file has become extra-large (huge),
and
.it 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
.it addr[7]
non-zero;
and that although this scheme allows for more than
256\*X256\*X512 = 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.
.s3
For block
.it b
in a file to exist,
it
is not necessary that all blocks less than
.it 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.
.sh "SEE ALSO"
icheck, dcheck (VIII)