The unix filesystem

After experimentation with this filesystem, he and several others went on to implement the rest of an operating system, which became unix.

Major features of the unix filesystem

• completely uniform -- the master (root) directory, user directories, subdirectories, and all organization of system files is all done using one simple hierarchy of directories
  • so users can make their own subdirectories just the same as system ones
  • Yields a directory "tree"; specify a file name in the tree with a "path name", which is how to get there from the root
  • Directories are just a special kind of file. If you want a directory listing, you just read the file which is that directory.
• No restrictions on or system interpretation of file names. File names can be any sequence of up to fourteen characters (this has been increased to 255 in all modern unix systems); periods are not special; upper and lower case are considered different. The only characters you're not allowed are the zero byte (i.e '\0'), because that will be used to indicate the end of a path name (end of a C string as passed to the operating system); and a slash, because that will be used to separate directory names in a path name.
• All of the available disks are integrated into one uniform file system. I might have a file called /usr/ajr/file, and that might be on a different disk than your file called /usr/you/file; but a new disk can be associated with one portion of the directory tree and it is seamless to users specifying file path names. A disk, or a disk partition, is "mounted" at a certain point in the filesystem. In the simplest case, if you have your own whole disk partition, it could be "mounted" as "/usr/you". Then the root directory on that disk becomes /usr/you in the whole tree.
• Thus it's easy to specify other people's files. Once you can refer to other people's files, you need an access protection capability -- you have to be able to specify who is allowed to do what to which of your files (read them, write them, delete them, ...). Unix has simple "file modes" to accomplish this (see chmod).
• No difference between "random access files" versus "sequential files", etc. A file is just a list of bytes; the operating system has no involvement in the format of the files, and it provides for efficient random OR sequential access to any file.

• Textbook chapters 1 and 4, and bits of chapter 3.
  • By the way, you may notice a discussion of ftw() in the textbook; I suggest not attempting to use ftw() for assignment two. (You don't have to know about it at all for this course actually.)
• Ritchie and Thompson, The UNIX Time-Sharing System, CACM 17 (1974) / BSTJ 57 (1978). Especially sections 3 and 4.

Any filesystem is basically a complex data structure on disk. The starting point for the unix filesystem is the "inode". 'i' for "index". This is an index entry for a single file on the disk.

A disk holding a unix filesystem contains a bunch of inodes and a bunch of data blocks. Each inode represents one file. Not necessarily a plain file; each directory gets its own inode too.

A directory is a list of records (structs), or pairs if you prefer, which are simply a file name and an inode number for that file. Here's an example "i-list":

i	mode	contents
2	D	usr 7, etc 4, bin 6
3		contents of password file
4	D	passwd 3
5	D	fsys.fig 10, src 11
6	D	date 9
7	D	bin 8, ajr 5, you 12
8	D	...
9		date program
10		...
11	D	hello.c 13
12	D	hello.c 14
13		...
14		...
...

The numbers on the left do not actually appear on the disk; we just have a big list of inodes in order. An array.

As well, the contents of the file is in the data blocks, not the inode; what is in the inode is the location of the data blocks which are the content of that file. The inode contains a variety of data, which is discussed below.

Directories' contents are much less substantial than the inode information. The contents of a directory is simply a list of pairs (structs of two elements), which are the file name and the inode number for that file. For example, the root directory above, the file contents pointed to by inode number 2, contain the three records which say that the directory contains three entries: usr, which is inode 7; etc, which is inode 4; and bin, which is inode 6.

The above chart thus represents the following directory tree:

We can identify a particular file in this hierarchical filesystem by giving a "path name", which is a sequence of directories to traverse until you get to the desired file (which, like any file, might be a directory; but the intermediate nodes in the path must be directories).
For example, the "hello.c" near the lower left can be identified as "/usr/ajr/src/hello.c". Since the path name begins with a "/", it starts from the root of the tree. Alternatively, if we do not begin with a slash, we start from the "current directory" (which you can change with the "cd" command as you know).

Suppose I want to have another name for the "date" command ("/bin/date", inode 9). I can call it "d" (in the current directory) by executing the command

		ln /bin/date d

% ls -li /bin/date /u/ajr/d
9 -r-xr-xr-x  2 root  wheel  14716 Jan  5 00:35 /bin/date
9 -r-xr-xr-x  2 root  wheel  14716 Jan  5 00:35 /u/ajr/d
% 

We can also note that the "link count" (third field above) is now two; there are two links to this file. There is only one actual file involved, although it is "in" two different directories. The only thing in the directory is the file name; thus all of the other ls -l information is the same: the protection, owner, size, times, and data block references are all in the inode.

With the "current directory" concept, you want to be able to specify "the current directory". e.g. If you run "ls" with no arguments, that means to list the current directory; it calls opendir(), and it needs something to pass to it.
Convention: in every directory, you have a "." entry which refers to the directory itself.

It also turns out to be convenient to specify "the parent directory". Convention: in every directory, you have a ".." entry which refers to the parent directory.

This gives us the following revised contents, after also doing the "ln /bin/date d" command in my home directory:

i	mode	contents
2	D	usr 7, etc 4, bin 6, . 2, .. 2
3		contents of password file
4	D	passwd 3, . 4, .. 2
5	D	fsys.fig 10, src 11, d 9, . 5, .. 7
6	D	date 9, . 6, .. 2
7	D	bin 8, ajr 5, you 12, . 7, .. 2
8	D	...
9		date program
10		...
11	D	hello.c 13, . 11, .. 5
12	D	hello.c 14, . 12, .. 7
13		...
14		...
...

For "/", in designing the unix filesystem they could have omitted the ".." directory entirely, but they chose to make /.. be / itself, as present above.

So, what data is in the inode? Not most of what's above. Most of the above is a statement of the contents of the files pointed to by the various inodes. The only data above which represents the actual inode contents is that 'D' meaning directory.

In addition to that one bit of information saying whether or not the file in question is a directory, the inode contains:

• "mode" -- the rwxrwxrwx stuff, also includes the 'd' bit for directories
• owner (uid -- "user id") (the owner can change the mode of the file, and whether or not you are the owner also affects the interpretation of the mode)
• group (gid) (similarly affects the interpretation of the mode; but no affect on who can change the mode, or even who can change the group)
• times: last modification time (mtime), last access time (atime), and last inode change time (ctime)
• NOT the file name. E.g. a file linked-in twice can have two different names.
• location on disk: list of block numbers, etc
  • ... bounded file sizes, cf chaining systems, etc

The unix filesystem is a reasonably simple way to achieve a number of objectives. Simplicity is good. This is a recurring theme amongst skilled computer programmers, and it's embodied very heavily in unix.

device files

• in addition to plain files, directories, ...
• don't need physical location info; put major/minor device numbers
• but otherwise, it's in the filesystem, has an inode number: hierarchical names, protection, you can link to it for convenience...
  • e.g. protection: tty modes
  • e.g. hierarchical: /dev/tape/3
• program can be expecting a "file", you give it a tty, or serial port, or printer, etc.

symlinks [circa 1980 [all previous was original design]]

• call existing things "hard links"
• hard links have equal status. Two links to a file: they have equal status; remove either one, the other one stays.
  • overwriting versus deleting and re-creating are very different if there are other links!
• that's unavoidable sometimes...
• we actually do want a facility to give one access point to a file an inferior status.
• "symlinks" -- special bit in inode: not plain file or directory, but symlink.
• File data content is path name to pointed-to file.
• The macintosh has basically this facility, introduced in system 7, they call "aliases". "Aliases" are more like symlinks than ms-windows "shortcuts", because they are interpreted by the OS, not user programs; you can just open an "alias" (macintosh) or a symlink (unix) and get the pointed-to file.
• dmr at ucb meeting said user-controlled hard links should be removed. He now appears to have been right.

n.b. that symlinks can cross filesystems... hard links can't!

The above scheme gives us a maximum file size which is just under a gigabyte. Since gigabyte disks were unheard of at the time, this was not a problem.

More modern allocation schemes, since the early 1980s, have wasted space a bit more on small files and the result is that the limitation is usually 2 GB. Still, this isn't good enough for some tasks.

So these days, many unix manufacturers have changed the system around a little to get a larger maximum file size, although some haven't -- this scheme doesn't prevent disks being more than a gigabyte, just individual files. Anyway, the changes are pretty straightforward: you can make that single-indirect block a double-indirect block; you can make the double-indirect block a triple-indirect block. Just don't lose the bound on the number of reads, or you no longer really have random access.

Another more modern innovation, some filesystems only, circa 1990: small files placed completely in the inode, thus taking zero blocks of disk space.

Good exercise: write "pwd". (e.g. in C)