Chroot and ".."

[Jonathan S. Shapiro]

On Thu, 2005-10-13 at 11:00 +0200, Marcus Brinkmann wrote:
> At Wed, 12 Oct 2005 21:21:24 -0400,
> "Jonathan S. Shapiro" <address@hidden> wrote:
> > 
> > Umm, guys? Chroot() was a late bolt-on to UNIX that attempted to provide
> > a best-effort approximation to confinement in a system where it was way
> > too late to do the real thing.
> 
> Ok, it's confusing to overload a term.  I tried to avoid that trap,
> but it's difficult.

First, let me restrict the scope of my query: we obviously need chroot()
to be implemented inside a POSIX compatibility box. We also need ".." to
be implemented. My question is: why do we want a bad bolt-on mechanism
for the native Hurd OS?

Let me now deal with "..". I will first point out that ".." is
completely broken, explain how it came to exist, and then explain how to
make it sensible again.

> But in the Hurd, a directory capability allows you to look up the
> special filename "..", and this gives you a capability to the parent
> directory.

It does not, and it cannot. It cannot do this in UNIX either. The reason
it cannot do this is that the entire concept of ".." in the file system
is completely broken. It assumes that every directory has at most one
parent. Here are some examples of violations of your assumption from
UNIX:

  1. In classical UNIX, at any filesystem root, inode(..) =def= inode(.)
     In Linux, this is "patched" at mount time by the mount logic. Many
     UNIX implementations do not implement this patch.

  2. When a clone mount of an FS is performed, ".." is obvously not
     unique. I have not actually looked to see what Linux does in this
     case, but whatever it does cannot be strictly correct, because the
     problem does not in principle admit of solution. I am sure that
     Linux found a good working resolution for day to day purposes, and
     this seems fine to me: a useful but imperfect solution is better
     than none, as long as it doesn't violate any design principles.

  3. ".." Doesn't work at all sensibly for NFS mount points. It never
     did. It's the clone mount case with a vengeance: the parent
     directories aren't even on the same machine!

The only reason that our current use of .. "works" in practice is that
mount points are so rare, and that they invariably occur at
administrative boundaries. In practice, relative paths do not cross
these boundaries often enough to expose difficulties very often.

HISTORY OF "..":

The ".." special entry was introduced in UNIX to assist early
implementations of fsck. They wanted a way to reconnect directories, and
this redundant encoding was very helpful. The ".." special entry had the
further advantage that it restricted the directory structure to a strict
hierarchy, which allowed fsck (in principle) to run in log(n) space. At
a time when main memory was extremely expensive, this was perceived
(correctly) as critical.

The handling of ".." was so unusual that the original version of "rm"
did not implement directory remove. There was a separate program, "dvd",
which existed to do this. I think "dvd" was dropped in research unix
version 4, and the functionality was integrated into "rm".

  For 5 trivia points:

     Without consulting google, what did "dvd" stand for?

Our current use of ".." in paths was an unforeseen but pleasant outcome
of the fsck requirement.

Things started to come apart as Plan 9 was being developed, because the
hierarchy assumption was violated. Plan 9 has an operation equivalent to
clone mount, and it is used everywhere. Even before this, the research
version of RFS was making a mess of this in UNIX, and some people were
looking at network-based clusters which appeared to create issues.

Somewhere around 1986, Dave Korn and Emden Gansner argued strongly that
".." was completely busted, and that the only sensible implementation
was to represent CWD (logically) as a string and implement ".." as a
string to string transformation in namei() [at that time, namei()
implemented the inode path walk code]. That is, they argued that ".."
could only be given a sensible meaning if it was context sensitive. One
of his arguments, in fact, concerned the problem with chroot() that has
been discussed here. They implemented this for research UNIX. Given the
politics of the day at Bell Labs, Dave and Emden actually had to build a
prototype implementation for SVR4 including a novel inode traversal
cache that was *faster* than the then-existing implementation.

These arguments occurred a long time ago, and I have long since
forgotten most of the details. My memory is that Dennis, Brian, Rob,
Phil, and just about everybody else in computing research agreed with
Dave and Emden. I was then on the commercial side of the house, and I
argued for its inclusion. My memory is that most of the SVR4 kernel
development group favored it. However, the SVR4 change oversight board
rejected the change out of concern about the possible compatibility
repercussions. This was stupid, and a compromise was reached: Dave
implemented ".." his way in the Korn Shell, and it was agreed that ksh
would be distributed this way and used to evaluate the compatibility
impact of the change.

Of course, SVR4 became irrelevant before the change could ultimately be
incorporated, and I am not aware that any followup ever occurred in the
UNIX family.

Plan 9 implements essentially what Dave proposed. I do not know if there
is a ".." entry in the Plan 9 directory structure, but it is certainly
not used for path resolution.

> We need thus two types of directory capabilities.  One that allows
> looking up "..", because that is still useful in many contexts.  And
> one that is the "secure" version and disallows looking up "..".

I think that the Korn/Gansner proposal is a better solution, because the
hierarchy assumption that underlies ".." is wrong.


WHAT EROS DOES:

> How would you do it in the EROS filesystem?

In EROS, directories do not have the ".." entry. We cannot, because we
don't impose a hierarchy restriction. A directory is simply a set of
mappings from strings to capabilities where the strings are disjoint.

Our directories *do* implement a "." entry, mainly because it was easier
to seed the directory data structure that way.

For emulation purposes, I would adopt the Korn/Gansner design.