11/3/71                                           FILE SYSTEM (V)

NAME            format of file system

SYNOPSIS        --

DESCRIPTION     Every file system storage volume (e.g. RF disk,

                RK disk, DECtape reel) has a common format for

                certain vital information.

                Every such volume is divided into a certain num-

                ber of 256 word (512 byte) blocks.  Blocks 0 and

                1 are collectively known as the super-block for

                the device; they define its extent and contain an

                i-node map and a free-storage map.  The first

                word contains the number of bytes in the free-

                storage map; it is always even.  It is followed

                by the map.  There is one bit for each block on

                the device; the bit is "1" if the block is free.

                Thus if the number of free-map bytes is n, the

                blocks on the device are numbered 0 through 8n-1.

                The free-map count is followed by the free map

                itself.  The bit for block k of the device is in

                byte k/8 of the map; it is offset k(mod 8) bits

                from the right.  Notice that bits exist for the

                superblock and the i-list, even though they are

                never allocated or freed.

                After the free map is a word containing the byte

                count for the i-node map.  It too is always even.

                I-numbers below 41(10) are reserved for special

                files, and are never allocated; the first bit in

                the i-node free map refers to i-number 41.

                Therefore the byte number in the i-node map for

                i-node i is (i-41)/8.  It is offset (i-41) (mod

                8) bits from the right; unlike the free map, a

                "0" bit indicates an available i-node.

                I-numbers begin at 1, and the storage for i-nodes

                begins at 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 of the
                file system, and begins 32 ((i+31)(mod 16)) bytes

                from its start.

                There is always one file system which is always

                mounted; in standard UNIX it resides on the RF

                disk.  This device is also used for swapping.

                The swap areas are at the high addresses on the

                device.  It would be convenient if these ad-

                dresses did not appear in the free list, but in

                fact this is not so.  Therefore a certain number

                of blocks at the top of the device appear in the

                free map, are not marked free, yet do not appear

                within any file.  These are the blocks that show

                up "missing" in a check of the RF disk.

                Again on the primary file system device, there

                are several pieces of information following that

                previously discussed.  They contain basically the

                information typed by the tm command; namely, the

                times spent since a cold boot in various cate-

                gories, and a count of I/O errors.  In particu-

                lar, there are two words with the calendar time

                (measured since 00:00 Jan 1, 1971); two words

                with the time spent executing in the system; two

                words with the time spent waiting for I/O on the

                RF and RK disks; two words with the time spent

                executing in a user's core; one byte with the

                count of errors on the RF disk; and one byte with

                the count of errors on the RK disk.  All the

                times are measured in sixtieths of a second.

                I-node 41(10) is reserved for the root directory

                of the file system.  No i-numbers other than this

                one and those from 1 to 40 (which represent spe-

                cial files) have a built-in meaning.  Each i-node

                represents one file.  The format of an i-node is

                as follows, where the left column represents the

                offset from the beginning of the i-node:

                   0-1     flags (see below)

                   2       number of links

                   3       user ID of owner

                   4-5     size in bytes

                   6-7     first indirect block or contents block


                   20-21   eighth indirect block or contents block

                   22-25   creation time

                   26-29   modification time

                   30-31           unused

                The flags are as follows:

                   100000  i-node is allocated

                   040000  directory

                   020000  file has been modified (always on)

                   010000  large file

                   000040  set user ID on execution

                   000020  executable

                   000010  read, owner

                   000004  write, owner

                   000002  read, non-owner

                   000001  write, non-owner

                The allocated bit (flag 100000) is believed even

                if the i-node map says the i-node is free; thus

                corruption of the map may cause i-nodes to become

                unallocatable, but will not cause active nodes to

                be reused.

                Byte number n of a file is accessed as follows: n

                is divided by 512 to find its logical block num-

                ber (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 corresponding to b

                is the bth entry in the address portion of the


                If the file is large, b is divided by 256 to

                yield a number which must be less than 8 (or the

                file is too large for UNIX to handle).  The cor-

                responding slot in the i-node address portion

                gives the physical block number of an indirect

                block.  The residue mod 256 of b is multiplied by

                two (to give a byte offset in the indirect block)

                and the word found there is the physical address

                of the block corresponding to b.

                If block b in a file exists, 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 corre-

                sponding block has never been allocated.  Such a

                missing block reads as if it contained all zero


FILES           --

SEE ALSO        format of directories


BUGS            Two blocks are not enough to handle the i- and

                free-storage maps for an RP02 disk pack, which

                contains around 10 million words.

OWNER           --