29

Say I log into a shell on a unix system and begin tapping away commands. I initially begin in my user's home directory ~. I might from there cd down to the directory Documents.

The command to change working directory here is very simple intuitively to understand: the parent node has a list of child nodes that it can access, and presumably it uses an (optimised) variant of a search to locate the existence of a child node with the name the user entered, and the working directory is then "altered" to match this — correct me if I'm wrong there. It may even be simpler that the shell simply "naively" tries to attempt to access the directory exactly as per the user's wishes and when the file system returns some type of error, the shell displays a response accordingly.

What I am interested in however, is how the same process works when I navigate up a directory, i.e. to a parent, or a parent's parent.

Given my unknown, presumably "blind" location of Documents, one of possibly many directories in the entire file system tree with that name, how does Unix determine where I should be placed next? Does it make a reference to pwd and examine that? If yes, how does pwd track the current navigational state?

75

The other answers are oversimplifications, each presenting only parts of the story, and are wrong on a couple of points.

There are two ways in which the working directory is tracked:

  • For every process, in the kernel-space data structure that represents that process, the kernel stores two vnode references to the vnodes of the working directory and the root directory for that process. The former reference is set by the chdir() and fchdir() system calls, the latter by chroot(). One can see them indirectly in /proc on Linux operating systems or via the fstat command on FreeBSD and the like:

    % fstat -p $$|head -n 5
    USER     CMD          PID   FD MOUNT      INUM MODE         SZ|DV R/W
    JdeBP    zsh        92648 text /         24958 -r-xr-xr-x  702360  r
    JdeBP    zsh        92648 ctty /dev        148 crw--w----   pts/4 rw
    JdeBP    zsh        92648   wd /usr/home/JdeBP      4 drwxr-xr-x     124  r
    JdeBP    zsh        92648 root /             4 drwxr-xr-x      35  r
    % 

    When pathname resolution operates, it begins at one or the other of those referenced vnodes, according to whether the path is relative or absolute. (There is a family of …at() system calls that allow pathname resolution to begin at the vnode referenced by an open (directory) file descriptor as a third option.)

    In microkernel Unices the data structure is in application space, but the principle of holding open references to these directories remains the same.

  • Internally, within shells such as the Z, Korn, Bourne Again, C, and Almquist shell, the shell additionally keeps track of the working directory using string manipulation of an internal string variable. It does this whenever it has cause to call chdir().

    If one changes to a relative pathname, it manipulates the string to append that name. If one changes to an absolute pathname, it replaces the string with the new name. In both cases, it adjusts the string to remove . and .. components and to chase down symbolic links replacing them with their linked-to names. (Here is the Z shell's code for that, for example.)

    The name in the internal string variable is tracked by a shell variable named PWD (or cwd in the C shells). This is conventionally exported as an environment variable (named PWD) to programs spawned by the shell.

These two methods of tracking things are revealed by the -P and -L options to the cd and pwd shell built-in commands, and by the differences between the shells' built-in pwd commands and both the /bin/pwd command and the built-in pwd commands of things like (amongst others) VIM and NeoVIM.

% mkdir a ; ln -s a b
% (cd b; pwd; /bin/pwd; printenv PWD)
/usr/home/JdeBP/b
/usr/home/JdeBP/a
/usr/home/JdeBP/b
% (cd b; pwd -P; /bin/pwd -P)
/usr/home/JdeBP/a
/usr/home/JdeBP/a
% (cd b; pwd -L; /bin/pwd -L)
/usr/home/JdeBP/b
/usr/home/JdeBP/b
% (cd -P b; pwd; /bin/pwd; printenv PWD)
/usr/home/JdeBP/a
/usr/home/JdeBP/a
/usr/home/JdeBP/a
% (cd b; PWD=/hello/there /bin/pwd -L)
/usr/home/JdeBP/a
% 

As you can see: obtaining the "logical" working directory is a matter of looking at the PWD shell variable (or environment variable if one is not the shell program); whereas obtaining the "physical" working directory is a matter of calling the getcwd() library function.

The operation of the /bin/pwd program when the -L option is used is somewhat subtle. It cannot trust the value of the PWD environment variable that it has inherited. After all, it need not have been invoked by a shell and intervening programs may not have implemented the shell's mechanism of making the PWD environment variable always track the name of the working directory. Or someone may do what I did just there.

So what it does is (as the POSIX standard says) check that the name given in PWD yields the same thing as the name ., as can be seen with a system call trace:

% ln -s a c
% (cd b;  truss /bin/pwd -L 3>&1 1>&2 2>&3 | grep -E '^stat|__getcwd')
stat("/usr/home/JdeBP/b",{ mode=drwxr-xr-x ,inode=120932,size=2,blksize=131072 }) = 0 (0x0)
stat(".",{ mode=drwxr-xr-x ,inode=120932,size=2,blksize=131072 }) = 0 (0x0)
/usr/home/JdeBP/b
% (cd b; PWD=/usr/local/etc truss /bin/pwd -L 3>&1 1>&2 2>&3 | grep -E '^stat|__getcwd')
stat("/usr/local/etc",{ mode=drwxr-xr-x ,inode=14835,size=158,blksize=10240 }) = 0 (0x0)
stat(".",{ mode=drwxr-xr-x ,inode=120932,size=2,blksize=131072 }) = 0 (0x0)
__getcwd("/usr/home/JdeBP/a",1024)       = 0 (0x0)
/usr/home/JdeBP/a
% (cd b; PWD=/hello/there truss /bin/pwd -L 3>&1 1>&2 2>&3 | grep -E '^stat|__getcwd')
stat("/hello/there",0x7fffffffe730)      ERR#2 'No such file or directory'
__getcwd("/usr/home/JdeBP/a",1024)       = 0 (0x0)
/usr/home/JdeBP/a
% (cd b; PWD=/usr/home/JdeBP/c truss /bin/pwd -L 3>&1 1>&2 2>&3 | grep -E '^stat|__getcwd')
stat("/usr/home/JdeBP/c",{ mode=drwxr-xr-x ,inode=120932,size=2,blksize=131072 }) = 0 (0x0)
stat(".",{ mode=drwxr-xr-x ,inode=120932,size=2,blksize=131072 }) = 0 (0x0)
/usr/home/JdeBP/c
%

As you can see: it only calls getcwd() if it detects a mismatch; and it can be fooled by setting PWD to a string that does indeed name the same directory, but by a different route.

The getcwd() library function is a subject in its own right. But to précis:

  • Originally it was purely a library function, that built up a pathname from the working directory back up to the root by repeatedly trying to look up the working directory in the .. directory. It stopped when it reached a loop where .. was the same as its working directory or when there was an error trying to open the next .. up. This would be a lot of system calls under the covers.
  • Nowadays the situation is slightly more complex. On FreeBSD, for example (this being true for other operating systems as well), it is a true system call, as you can see in the system call trace given earlier. All of the traversal from the working directory vnode up to the root is done in a single system call, which takes advantage of things like kernel mode code's direct access to the directory entry cache to do the pathname component lookups much more efficiently.

    However, note that even on FreeBSD and those other operating systems the kernel does not keep track of the working directory with a string.

Navigating to .. is again a subject in its own right. Another précis: Although directories conventionally (albeit, as already alluded to, this is not required) contain an actual .. in the directory data structure on disc, the kernel tracks the parent directory of each directory vnode itself and can thus navigate to the .. vnode of any working directory. This is somewhat complicated by the mountpoint and changed root mechanisms, which are beyond the scope of this answer.

Aside

Windows NT in fact does a similar thing. There is a single working directory per process, set by the SetCurrentDirectory() API call and tracked per process by the kernel via an (internal) open file handle to that directory; and there is a set of environment variables that Win32 programs (not just the command interpreters, but all Win32 programs) use to track the names of multiple working directories (one per drive), appending to or overwriting them whenever they change directory.

Conventionally, unlike the case with Unix and Linux operating systems, Win32 programs do not display these environment variables to users. One can sometimes see them in Unix-like subsystems running on Windows NT, though, as well as by using the command interpreters' SET commands in a particular way.

Further reading

  • 1
    This is far more than I ever expected. Thank you, and extra thanks for the further reading! – ReactingToAngularVues Dec 27 '17 at 9:27
  • doc.cat-v.org/plan_9/4th_edition/papers/lexnames talks about some of the problems with .. in the context of Plan9, – icarus Dec 27 '17 at 16:12
  • @JdeBP: Perhaps I’m missing something.  You say, “Internally, within …, bash, … and …, the shell additionally keeps track of the working directory using string manipulation of an internal string variable.  …, it adjusts the string to remove . and .. components and to chase down symbolic links replacing them with their linked-to names. …  The name in the internal string variable is tracked by a shell variable named PWD …” (emphasis added).  … (Cont’d) – G-Man Mar 8 '18 at 8:18
  • (Cont’d) … But your example shows PWD = …/b after a cd b command, even though b is a symbolic link to a — so the shell doesn’t “chase down” the a -> b link. Did you misstate, or did I misread? – G-Man Mar 8 '18 at 8:18
  • I simply glossed over a side point, and pointed you to the code for details. See the various shells' manuals for when and how they decide to chase symbolic links or not. The Z shell handily calls its shell option that is one part of the decision formula, CHASE_LINKS. – JdeBP Mar 8 '18 at 8:40
1

The kernel does not keep track of directory or file names; a file or directory is represented in the kernel by an inode/device pair. System calls like chdir(), open(), etc. take a path as parameter, which can be absolute (e.g. /etc/passwd), or relative to the current directory (examples: Documents, ..). When a process executes chdir("Documents"), a lookup is done for Documents in the current working directory, and the process's working directory is updated to refer to this directory. From the kernel's perspective, there is nothing special in the name "..", it's just a convention in the file system that .. refers to the parent directory.

The getcwd() function is not a system call, but a library function that has to work its way up to the root directory, recording the names of the path components on the way.

0

Interestingly, traditionally cd .. is much much more simple than pwd. Directories named .. are placed explicitly into the file system. The system keeps track of the device/inode of the current directory, so cd .. or more accurately the system call chdir("..") just entails looking up the name ".." in the file belonging to the current directory's inode and changing the current directory's device/inode to the value found there.

pwd (more accurately /bin/pwd) follows .. links successively and reads the respective directories until finding the inode where it came from, assembling the list of those names in reverse until it reaches the root directory (notably not containing a .. entry).

Now this is the original low-level basic behavior. Actual shell commands pwd instead rely on a variety of techniques caching the current path name. But at the core, it's only its inode that is actually known. That implies that once symlinks are used for navigating directories, the current work directory name notions of the current shell and of the system /bin/pwd might diverge.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.