----------------------------------------------
Unix/Linux File System - (correct explanation)
----------------------------------------------
-IAN! idallen@idallen.ca

Most diagrams showing file systems and links in Unix texts are wrong
and range from confusing to seriously misleading.  Here's the truth.

Names are stored in directories, not with the things to which the
names refer.  Most texts make the error of putting the names on the
things that are being named.  That is misleading and the cause of many
misunderstandings about Unix/Linux files and directories.

The name of a thing (file, directory, special file, etc.) is kept in
a directory, separate from the thing it names.  This allows things to
have multiple names; all the names refer to the same thing.

-------------
Inode numbers
-------------

The actual data for each Unix file or directory stored on disk is managed
by on-disk data structures called "inodes" (index nodes), one inode
per file or directory.  Unix inodes have unique numbers, not names.
The "-i" option to "ls" shows these inode numbers.

A Unix inode contains a list of pointers to the disk blocks that belong
to that file or directory.  The larger the file or directory, the more
disk block pointers it needs in the inode.  Also stored in the inode are
the attributes of the file or directory (permissions, owner, group, size,
access/modify times, etc.); but, not the name of the file or directory.
Inodes have only numbers, not names.

Everything in a Unix file system has a unique inode number: every file,
directory, special file, etc.  Files and directories are both managed
with inodes.

Directory inodes
----------------

File and directory names are stored in directories, not in the inodes
with the things that they name.  The *name* of a file or directory is
not kept in the inode; the name is kept in a directory somewhere else.

Directories are what give names to inodes on Unix.  Like most other
inodes, directory inodes contain attribute information about the inode
(permissions, owner, etc.) and one or more disk block pointers in which
to store data; but, what is stored in the disk blocks of a directory is
not file data but directory data.

A Unix directory is simply a list of pairs of names and associated inode
numbers.  That is all - the disk blocks in Unix directories contain only
names and inode numbers.  The rest of the attribute information about
an item named in a directory (permissions, owner, etc.) is kept with the
inode associated with the name.  You must use the inode number from the
directory to find the inode on disk to read its attribute information;
reading the directory only tells you the name and inode number.

Reading a Unix directory tells you only some names and inode numbers;
you know nothing about what kind of things those inodes are unless you
go out to disk and access them.  You can't even tell whether a name
in a directory is the name of a file or the name of a sub-directory
without using the associated inode number to find the inode of the item
and looking at its attributes.  This is why "ls" or "ls -i" are much
faster than "ls -l", since "ls -l" has to do a lookup on every inode in
the directory to find out the inode attributes; but, "ls" or "ls -i"
only needs to read the names and inode numbers from the directory -
no additional inode access is needed (because no attributes are being
queried).

No attribute information about the things named in the directory is
kept in the directory.  The directory only contains pairs of names and
inode numbers.  (But remember that since each directory is managed by an
inode, the inode for the directory itself contains attribute information
about the *directory*, not about the things named in the directory.)

To find a thing by name, the system goes to a directory inode, looks up
the name in the disk space allocated to that directory, finds the inode
number associated with the name, then goes out to the disk a second time
and finds that inode.  If that inode is another directory, the process
repeats from left-to-right along the pathname until the inode of the
last pathname component (on the far right in the pathname) is found.
Then the disk block pointers of that last inode can be used to find the
data contents of the last pathname component.

The name and inode number pairing in a directory is the only connection
between a name and the thing it names on disk.  The name and inode
number in the directory is kept separate from the data belonging to the
thing it names (the actual inode on disk).  If a disk error damages a
directory inode or the directory disk blocks, data is not usually lost;
since, the actual data for the things named in the directory is stored
in inodes separate from the directory itself.  Only the name is lost.

The name of an item is kept in a directory inode that is separate from
the inode of the thing it names.  The name is stored in some directory;
the data for the item named has its own inode somewhere else.

Multiple names - hard links
---------------------------

Because (1) a file is managed by an inode with a unique number, (2)
the name of the file is not kept in that inode, and (3) directories pair
names with inode numbers, a Unix file (inode) can be given multiple names.

Inode 123 may be paired with the name "cat" in one directory and the
same 123 may be paired with the name "dog" in the same or a different
directory.  Either name leads to the same 123 file inode and the same
data and attributes.  Though there appear to be two different files "cat"
and "dog" in the directory, the only thing different between the two is
the name - both names lead to the same inode and therefore to the same
data and attributes (permissions, owner, etc.).

Multiple names are called "hard links" to the file.  The "ln" command
creates a new hard link to an inode.  The system keeps a "link count"
in each inode that counts the number of names each inode has been given.
The "rm" command removes hard links to an inode.  When the link count
goes to zero, the file has no names and the file inode is recycled and
all the file data is released.

---------
Pathnames
---------

When you look at a Unix pathname, remember that that the slashes separate
names of pathname components.  All the components to the left of the
rightmost slash must be directories, including the "empty" ROOT directory
name to the left of the leftmost slash.  For example:

    /home/alex/foobar
   
In the above example, there are three slashes and therefore four
pathname components.  The "empty" name in front of the first slash is
the name of the ROOT directory.  The ROOT directory doesn't have a name.
(Some books get around this by calling the ROOT directory "slash" or "/".
That is wrong.  ROOT doesn't have a name - slashes *separate* names.)

Inside the ROOT directory is the name of the "home" directory.
Inside the home directory is the name of the "alex" directory.
Inside the alex directory is the name of the "foobar" file.

The last (rightmost) component of a pathname can be a file or a
directory; for this example, let's assume it's a file name.

Below is a file system diagram written correctly, with the names for
things shown one level *above* the things to which the names actually
refer.  Each box represents an inode; the inode numbers are on the left.
Inside the directory inodes you can see the pairs of names and inode
numbers:

    +----+-----+-----------------------------------------+
#2  |. 2 |.. 2 | home 5 | usr 9 | tmp 11 | etc 23 | ...  |
    +----+-----+-----------------------------------------+

The above box is the nameless ROOT directory, inode #2.  ROOT has the name
"home" in it, paired with inode #5.  The *directory* "home" is not here;
only the *name* "home" is here.  To read the "home" directory, you have
to find inode #5 on disk and look there.  The ROOT directory itself does
not have a name; because, it has no parent to give it a name!

The ROOT directory is the only directory that is its own parent; both
the names "." and ".." lead back to ROOT (inode #2).

    +----+-----+---------------------------------------------------+
#5  |. 5 |.. 2 | alex 31 | leslie 36 | pat 39 | abcd0001 21 | ...  |
    +----+-----+---------------------------------------------------+

The above box is the "home" directory, inode #5.  The name "home"
isn't in this directory; the name "home" is up in the ROOT directory.
This "home" directory has the name "alex" in it, paired with inode #31.
The *directory* "alex" is not here; only the *name* "alex" is here.
To read the "alex" directory, you have to find inode #31 on disk and
look there.  (In fact, until you look up inode #31 and find out that
it is a directory, you have no way of even knowing that the name "alex"
is a name of a directory!)

    +----+-----+---------------------------------------------+
#31 |. 31|.. 5 | foobar 12 | temp 15 | literature 7 | demo 6 |
    +----+-----+---------------------------------------------+

The above box is the "alex" directory, inode #31.  The name "alex"
isn't in this directory; the name "alex" is up in the "home" directory.
This "alex" directory has the name "foobar" in it, paired with inode #12.
The *file* "foobar" is not here; only the *name* "foobar" is here.
To read the data from file "foobar", you have to find inode #13 on disk
and look there.  (In fact, until you look up inode #13 and find out
that it is a plain file, you have no way of even knowing that the name
"foobar" is a name of a plain file!)

    *-----------*
#12 | file data |
    *-----------*

The above box is the "foobar" file, inode #12.  The name "foobar" isn't
here; the name "foobar" is up in the "alex" directory.  This inode is
a file inode, not a directory inode.  The inode for a file contains
pointers to file data, not directory data.  There are no special names
"." and ".." in files.  There are no names here at all; the disk block
pointers in this inode point to just file data (whatever is in the file).

    +----+-----+----------------------------------------------+
#7  |. 7 |.. 31| dwiz 51 | barfoo 12 | forwubla 123 | junk 99 |
    +----+-----+----------------------------------------------+

The above box is the "literature" directory, inode #7.  The name
"literature" isn't in this directory; the name "literature" is up in the
"alex" directory.  This "literature" directory has the name "barfoo"
in it, paired with inode #12.  The *file* "barfoo" is not here; only
the *name* "barfoo" is here.  You will note that inode #12 now has two
different names; names "foobar" and "barfoo" both link to inode #12.
Two names means the "link count" of inode #12 is set to "two".

To follow a valid path such as:

    /home/alex/literature/barfoo

just walk the tree.  Everything to the left of the rightmost slash must be
a directory.  Start with the nameless ROOT directory in front of the first
slash (ROOT doesn't have a name, since it does not appear in any parent
directory) and look for the first pathname component ("home") inside
that directory (inside inode #2).

Let's trace the pathname:

Look in the ROOT directory (inode #2) for the name of the first pathname
component: "home".  We find the name "home" inside the ROOT directory,
paired with inode number 5.  Go back out to the disk to find the "home"
directory that is inode 5.

[Note how the names are separate from the things they name.  The actual
directory inode of "home" (#5) is not the same as the inode of the ROOT
directory containing the name "home" (#2).  The name is in a different
place than the thing it names.]

In the directory that has the name "home" (inode #5), look for the name
"alex".  We find "alex" paired with inode #31.  Go back out to the disk
to find the "alex" directory that is inode #31.  [Again, the name "alex"
contained in directory "home" (inode #5) is separate from the inode that
is the actual directory "alex" (inode #31).]

In the directory that has the name "alex" (inode #31), look for the
name "literature".  We find "literature" paired with inode #7.  Go back
out to the disk to find the "literature" directory that is inode #7.
(Again, the name "literature" contained in inode #31 is separate from
the inode #7 that is the actual directory "literature".)

In the directory that is "literature", look for the name "barfoo".
We find it paired with inode #12.  Go back out to the disk to find the
"barfoo" file that is inode #12.  (Again, the name is separate from the
thing it names, so the name is not part of the inode data that makes up
the actual file.)

You now have the disk node (inode) that is your file data: inode #12.
If that file inode has appropriate permission attributes, you can read it
or write it.  The permissions on the directory containing the name of the
file don't matter, once you have found the inode containing the file data.
(If the inodes of the directories leading down to the file inode #12 don't
have search permission, you won't be able to reach the file's inode and
won't be able to access the file's data using those directories; but,
perhaps some other directories may lead you there.)

-----
Notes
-----

"What permissions do I need on a file to delete it from a directory?"

   None!  You don't even have to own the file.  You need *write* and
   *search* permissions on the *directory* that contains the *name* of the
   file, to remove the *name* of the file from the *directory*.  (When all
   links to a file are gone, the file is reclaimed by the system.)

   Removing a file is a directory operation that deletes a name (a name is
   a link); it has absolutely nothing to do with the permissions or owner
   on whatever the link happens to point to.  If you can write and search
   the directory that contains the file name ("wx" permissions on the
   directory), you can delete the file name (the link) from the directory.

"What if I want to delete a sub-directory from a directory?"

   You need "wx" permissions to remove the sub-directory name from the
   directory, just as if the name pointed to a file.

   However: You can only delete from a directory a name that points
   to a sub-directory if that other sub-directory is *empty*.  If you
   don't have permission to empty out that sub-directory, you won't be
   able to delete its name from its parent directory, even if you have
   permissions on the parent directory.

Scenario:
   
   Alex creates, in his home directory, a sub-directory "foo" with write
   permissions for everyone.  Ian creates a sub-sub-directory "foo/bar"
   with permissions only for Ian, and then Ian creates a file "foo/bar/haha".

   It is now impossible for Alex to delete the foo sub-directory from
   his own home directory, because Alex cannot empty out and remove
   the sub-sub-directory foo/bar, because only Ian has permissions to
   remove the file name foo/bar/haha from the foo/bar sub-sub-directory.
   (Only Ian can write the sub-sub-directory named foo/bar.)  Alex is
   stuck with the foo sub-directory in his account.  Alex can rename it
   (e.g. mv foo .junk, which changes the name); but, he can't delete
   the foo directory until Ian makes it empty.

   Only empty directories may be deleted.

Directories Rule:

    "X" (execute) permissions on a directory mean you can pass "through"
    the directory to access a thing if you already know the name of the
    thing you want to access.  ("X" means "search permission" for dirs.)

    "R" permissions on a directory mean you can see the names in the
    directory.  (Directories only contain names and inode numbers.)
    
    You can't get a *long* listing of the files in a directory ("ls
    -l") unless you have X permissions to pass through the directory to
    find out what kind of nodes the names in the directory represent.
    You can get a short listing of just the *names* in a directory
    without needing X permissions (only "read" is needed for names).

In other words:

    If you don't have R permission, you can't see the names inside a
    directory.  If you happen to know some names, and you have X permission,
    you can go *through* the directory to get to the things pointed to
    by the names that you know. 

    If you don't have X permission, then you can't *get to* the files,
    even if you have R permission and can see their names.  Names are
    separate from content; you may be able to see the names without being
    able to pass through the directory to go get the content contained
    in the inodes associated with those names.

"I'm logged in as idallen over in /home/idallen. 
 What permissions do I need to read ../alex/demo?"

   This is a *relative* pathname.  It starts with the current
   directory and goes up from there.

   You need X permission on the current directory "." ("." is
   /home/idallen) to let you pass through using name ".." to your parent
   directory.  In this example, your parent directory would be "/home".
   ".." is a relative pathname, meaning it starts with an entry in
   your current directory, and so you must have X perms on the current
   directory to use the name ".." in the current directory to go up
   one level.

   You need X permission on your parent directory ("home") to pass through
   it using name "alex" to the inode that is the actual directory named
   "alex".  (Remember - names are separate from the things they name!)

   You need X permission on directory "alex" to pass through it using name
   "demo" to the actual file inode for the name "demo".

   You need R permissions on the "demo" file inode to read the data.

"I'm logged in as idallen over in /home/idallen. 
 What permissions do I need to read /home/alex/demo?"

   This is an *absolute* pathname.  It ignores the current directory.
   Nothing about the current directory is needed.  The path search
   starts from the ROOT directory.  The following sequence is
   identical, no matter what directory is your current directory:

   You need X permission on the ROOT directory to pass through it using
   name "home" to the inode of the directory named "home".  (Remember -
   names are separate from the things they name!)

   You need X permission on the inode of the "home" directory to pass
   through it using name "alex" to inode of the directory named "alex".
   (Remember - names are separate from the things they name!)

   You need X permission on inode of the directory "alex" to pass through
   it using name "demo" to the actual file inode for "demo".

   You need R permissions on the "demo" file inode to read the data.

"The *name* of a file is separate from the actual file data.
 What information *is* kept with the file data?"

   Everything else, except the name, is part of the inode that holds
   the file data.  This means: owner, group, access and modify times,
   permissions, size, etc.  None of this information appears in the
   directory; it is all kept in the file inode along with the pointers
   to the disk blocks that contain the actual file data.

   No matter what name you use to find a file's inode on disk, the file
   has the same owner, group, permissions, etc. because one copy of all
   that information is kept in the inode *with the file data*, not in
   the directory.

   The only things you will find in a Unix directory are names and inode
   numbers - everything else is in the inode of the file.

Explain this sequence (removing X permission on a directory):

    $ mkdir /tmp/idallen
    $ cd /tmp/idallen
    $ touch a b c d
    $ ls
    a  b  c  d
    $ chmod -x .
    $ ls
    ls: .: Permission denied
    $ ls ..
    ls: ..: Permission denied
    $ ls a b c d
    ls: a: Permission denied
    ls: b: Permission denied
    ls: c: Permission denied
    ls: d: Permission denied
    $ ls /tmp/idallen
    a  b  c  d
    $ ls -l /tmp/idallen
    ls: /tmp/idallen/a: Permission denied
    ls: /tmp/idallen/b: Permission denied
    ls: /tmp/idallen/c: Permission denied
    ls: /tmp/idallen/d: Permission denied
    $ ls /tmp/idallen/a
    ls: /tmp/idallen/a: Permission denied
    $ ls -l /tmp/idallen/a
    ls: /tmp/idallen/a: Permission denied
    $ chmod +x .
    chmod: .: Permission denied
    $ chmod +x /tmp/idallen
    $ ls
    a  b  c  d

Note how "ls -l /tmp/idallen" can find the *names* in the directory
(because it can read the directory); but, it can't go *through* the
directory to actually look at what the names point to!  So it can't
tell you anything about what the names actually *are*.  An "ls -l" long
listing needs to know what the names *are* - it requires more permissions
that a plain "ls" that only needs to know the names, not what they are.

And now study this one (removing R permission on a directory):

    $ mkdir /tmp/idallen
    $ cd /tmp/idallen
    $ touch a b c d
    $ ls
    a  b  c  d
    $ chmod -r .
    $ ls
    ls: .: Permission denied
    $ ls ..
    file1    file2    file3   idallen
    $ ls a b c d
    a  b  c  d
    $ ls /tmp/idallen
    ls: /tmp/idallen: Permission denied
    $ ls -l /tmp/idallen
    ls: /tmp/idallen: Permission denied
    $ ls /tmp/idallen/a
    /tmp/idallen/a
    $ ls -l /tmp/idallen/a
    -rw-r--r--   1 idallen  users           0 Jan 28 13:43 /tmp/idallen/a
    $ chmod +r .
    $ ls
    a  b  c  d

Without read permission on the directory, we can't find out what names
are in the directory.  But, if we already know some of the names in the
directory we can go through the directory to get the details about the
inodes that the the names point to, because we still have X (search)
permission.

---------------------
A Study in File Links
---------------------

What is the "link count" field displayed by the "ls -l" command?
What causes a file's link count to increment?
What happens when a file's link count becomes zero?
What is the link count of an empty directory?  Why?

On ACADUNIX, use the "-i" option to "ls" on this set of files:

   $ ls -li /usr/bin/*sh

Note the inode numbers of each name in this directory.  Which names
are really the same file?  (The inode numbers will tell you!)  Sort the
output to make the inode numbers that are the same come together and be
easier to see:

   $ ls -li /usr/bin/*sh | sort

Look at the entire /usr/bin directory and note which names in this
directory are actually pointers (hard links) to the same file:

   $ ls -li /usr/bin | sort | more

Where is the name of the file "csh" stored?
Where is the name of the directory "bin" stored?
Where is the name of the directory "usr" stored?

---------------------
Links and Directories
---------------------

- What command and options are needed to see the access permissions
  and link count of a directory, instead of the *contents* of a
  directory?

- When you are inside a directory, what is the name you use to refer to 
  the directory itself?  (This name works inside any directory.)

- How many links does a brand new, empty directory have?
  Why isn't it just one link, as it is for a new file?
  (In other words, why does a new file have one link and a new directory
  have more than that?)

- Why does creating a sub-directory in a directory cause the directory's
  link count to increase by one for every sub-directory created?

- Why doesn't the link count of the directory increase when you create
  files in the directory?

- Give the Unix command and its output that shows the inode number
  and owners of the following directories:

    a) your HOME directory
    b) the /bin directory
    c) the root directory

  Note: Show only one line of output for each single directory; do
  not show the contents of the directory.  Use a command (and options)
  that will show only the directory itself, not its contents.