Hi,
davidv1992 wrote:
This post has gotten a bit larger than I had hoped, but I think it is important enough to post it anyway.
It is good to realize that there are two viewpoints as to how to handle .. people are presenting here:
Option 1 (POSIX):
One option is to take the view that .. always points to the same thing, the "canonical" parent of the directory. In this view, the directory structure is a pure tree, and when we follow a symlink, we forget that we ever did that.
This has the advantage that the current position is everything you need to determine what any name, including .., means. Furthermore, if you implement the chdir function, this view conforms to the POSIX standard, which might make porting easier in some cases.
The disadvantage is that this breaks the notion that /a/b/../c/d always equals /a/c/d, which can be counter-intuitive towards users. It is also part of the cause of the admittedly somewhat crazy rules for the shell cd command in the posix standard.
Option 2
The alternative is to take the view that to be in a directory always means to have specified some path from root to that directory. Accessing .. then translates to removing the last element of that path.
This has as an advantage that .. in a larger path will always behave as expected, so specifying /a/b/../c/d always means /a/c/d. Hence, one can always simplify path without worrying that this might actually change their meaning.
However, this scheme also has some disadvantages: First of all, everywhere where you access directories using some form of reference, that reference needs to either point or contain the path used to generate this. This would most likely require some amount of extra storage. Furthermore, you end up with some other strange behaviour: for example, two programs could have a handle to the same point in a directory tree, but which contain different origin paths. In that case, they would get different results when interrogating the properties of what the .. entry in that directory points to.
Further notes
Both options are valid ways of implementing the behaviour of symbolic links. Each has their advantages and disadvantages, and you will need to decide what is most important in your system.
For some example implementations, the linux kernel, or at least the glibc/linux chdir function, behaves according to option 1. In contrast, bash behaviour mostly seems to follow option 2, which it seems to achieve by keeping track of the current working directory internally as well.
This is why I wrote "
Note: POSIX may or may not be compatible with "should"." in my original post - I wasn't entirely sure, but suspected that POSIX is a hideous disaster that gets everything wrong (and that there's a huge amount of software that has bugs in the presence of symbolic links because POSIX does it wrong).
For the way I do it (which is definitely not compatible with POSIX for many reasons); a current working directory is just a "prefix string" (with no associated inode) that's maintained by the process itself; and the kernel and VFS only ever sees canonical absolute paths. E.g. if a process does "chdir("/foo/../bar");" it does pure text manipulation to set the prefix string to "/bar/" itself (possibly without checking or caring if "/foo" or "/bar" exist if that's what the process wanted to do), then if the process opens the file "baz" it prepends the prefix string itself and asks VFS to open "/bar/baz". If the process doesn't want to use any current working directory at all, that's fine (e.g. it can use absolute paths for everything). If the process wants to give each thread its own independent current working directory, that's fine too. Of course this could all be delegated to a library (potentially including having a library that emulates POSIX brokenness).
For the VFS; it converts the absolute path to a hash, then tries to find the inode in a glorified hash table. If it's not found it chops the last path separator and whatever followed it off of the end of the string (e.g. the string "/foo/bar/baz" becomes "/foo/bar") and retries to find the parent directory's inode, and so on (until it finds something that is in its cache, and can start doing "VFS cache miss or bad path" handling). Keeping track of the current working directory's inode does not speed this up and doesn't improve performance at all. Instead; nothing outside the VFS is allowed to have a reference to the VFS's internal data (separation of concerns) and the VFS's ability to manage its caches (including "least recently used inode eviction") isn't complicated by lots of processes holding references to inodes that aren't associated with open file/directory descriptors.
The downside is that if/when something has multiple absolute paths (e.g. due to symbolic links) it may have multiple hash table entries and each of its paths (that VFS knows about) need to be stored in the inode to complete hash table lookup.
Note 1: In theory (I've never implemented it); the VFS's hash table can be distributed across multiple VFS threads where an absolute path is converted to "thread number and hash for that thread"; and where each VFS thread can manage its own private hash table and its own private caches. This could have benefits for cache locality and scalability (especially many CPU and NUMA systems), and in some cases would allow the VFS process to benefit from my OS's thread specific storage (e.g. on a 32-bit system with PAE; a VFS process with 128 threads can use up to 256 GiB of RAM for caches because each thread has 2 GIB of thread specific storage).
Note 2: If I ever implement something like "chroot()", it'd essentially be the same - just a simple string that's prefixed to a process' absolute paths (by VFS instead of by the process itself).
Cheers,
Brendan