1 .HTML "Lexical File Names in Plan 9 or Getting Dot-Dot Right
5 Lexical File Names in Plan 9
12 .CW rob@plan9.bell-labs.com
17 Symbolic links make the Unix file system non-hierarchical, resulting in
18 multiple valid path names for a given file.
19 This ambiguity is a source of confusion, especially since some shells
20 work overtime to present a consistent view from programs such as
22 while other programs and
23 the kernel itself do nothing about the problem.
25 Plan 9 has no symbolic links but it does have other mechanisms that produce the same difficulty.
26 Moreover, Plan 9 is founded on the ability to control a program's environment
27 by manipulating its name space.
28 Ambiguous names muddle the result of operations such as copying a name space across
31 To address these problems,
32 the Plan 9 kernel has been modified to maintain an accurate path name for every active
33 file (open file, working directory, mount table entry) in the system.
34 The definition of `accurate' is that the path name for a file is guaranteed to be the rooted,
36 the program used to acquire it.
37 These names are maintained by an efficient method that combines lexical processing\(emsuch as
40 by just removing the last path name element of a directory\(emwith
41 local operations within the file system to maintain a consistently, easily understood view
43 Ambiguous situations are resolved by examining the lexically maintained names themselves.
47 returns the file name associated with an open file,
48 permitting the use of reliable names to improve system
52 Although this work was done in Plan 9,
53 Unix systems could also benefit from the addition of
54 a method to recover the accurate name of an
55 open file or the current directory.
60 Consider the following unedited transcript of a session running the Bourne shell on a modern
71 \&../rob: bad directory
74 (The same output results from running
79 To a neophyte being schooled in the delights of a hierarchical file name space,
80 this behavior must be baffling.
81 It is, of course, the consequence of a series of symbolic links intended to give users
82 the illusion they share a disk, when in fact their files are scattered over several devices:
85 % ls -ld /home/rob /home/ken
86 lrwxr-xr-x 1 root sys 14 Dec 26 1998 /home/ken -> /n/bopp/v6/ken
87 lrwxr-xr-x 1 root sys 14 Dec 23 1998 /home/rob -> /n/bopp/v7/rob
91 The introduction of symbolic links has changed the Unix file system from a true
92 hierarchy into a directed graph, rendering
94 ambiguous and sowing confusion.
96 Unix popularized hierarchical naming, but the introduction of symbolic links
97 made its naming irregular.
100 command, through the underlying
103 uses a tricky, expensive algorithm that often delivers the wrong answer.
104 Starting from the current directory,
108 and searches it for an entry whose i-number matches the current directory;
109 the matching entry is the final path element of the ultimate result.
110 Applying this process iteratively,
112 works back towards the root.
115 knows nothing about symbolic links, it will recover surprising names for
116 directories reached by them,
117 as illustrated by the example;
120 traverses will not backtrack across the links.
122 Partly for efficiency and partly to make
126 more predictable, the Korn shell
134 command must be a builtin in any shell, since the current directory is unique to each process.)
136 maintains its own private view of the file system to try to disguise symbolic links;
141 involve some lexical processing (somewhat like the
143 function discussed later
144 in this paper), augmented by heuristics such as examining the environment
149 to assist initialization of the state of the private view. [Korn00]
151 This transcript begins with a Bourne shell running:
161 This result is encouraging. Another example, again starting from a Bourne shell:
165 \&../ken: bad directory
175 the Korn shell is providing more sensible behavior,
176 but it is easy to defeat:
200 failed to produce the results
201 .CW /home/rob/bin "" (
204 that the previous example might have led us to expect.
205 The Korn shell is hiding the problem, not solving it, and in fact is not even hiding it very well.
207 A deeper question is whether the shell should even be trying to make
214 library call and every program that uses it will behave differently from the shell,
215 a situation that is sure to confuse.
216 Moreover, the ability to change directory to
218 with the Korn shell's
220 command but not with the
222 system call is a symptom of a diseased system, not a healthy shell.
224 The operating system should provide names that work and make sense.
225 Symbolic links, though, are here to stay, so we need a way to provide
226 sensible, unambiguous names in the face of a non-hierarchical name space.
227 This paper shows how the challenge was met on Plan 9, an operating system
228 with Unix-like naming.
232 Except for some details involved with bootstrapping, file names in Plan 9 have the same syntax as in Unix.
233 Plan 9 has no symbolic links, but its name space construction operators,
237 make it possible to build the same sort of non-hierarchical structures created
238 by symbolically linking directories on Unix.
242 system call takes a file descriptor
243 and attaches to the local name space the file system service it represents:
245 mount(fd, "/dir", flags)
249 is a file descriptor to a communications port such as a pipe or network connection;
250 at the other end of the port is a service, such as file server, that talks 9P, the Plan 9 file
252 After the call succeeds, the root directory of the service will be visible at the
260 argument specifies the nature of the attachment:
262 says that the contents of the root directory (appear to) replace the current contents of
265 says that the current contents of
267 remain visible, with the mounted directory's contents appearing
272 says that the contents remain visible, with
273 the mounted directory's contents appearing
276 These multicomponent directories are called
277 .I "union directories
278 and are somewhat different from union directories in 4.4BSD-Lite [PeMc95], because
279 only the top-level directory itself is unioned, not its descendents, recursively.
280 (Plan 9's union directories are used differently from 4.4BSD-Lite's, as will become apparent.)
282 For example, to bootstrap a diskless computer the system builds a local name space containing
283 only the root directory,
285 then uses the network to open a connection
286 to the main file server.
289 mount(rootfd, "/", MREPL);
291 After this call, the entire file server's tree is visible, starting from the root of the local machine.
295 connects a new service to the local name space,
297 rearranges the existing name space:
299 bind("tofile", "fromfile", flags)
301 causes subsequent mention of the
303 (which may be a plain file or a directory)
306 had been mentioned instead, somewhat like a symbolic link.
307 (Note, however, that the arguments are in the opposite order
313 argument is the same as with
316 As an example, a sequence something like the following is done at bootstrap time to
317 assemble, under the single directory
319 all of the binaries suitable for this architecture, represented by (say) the string
322 bind("/sparc/bin", "/bin", MREPL);
323 bind("/usr/rob/sparc/bin", "/bin", MAFTER);
329 to contain first the standard binaries, then the contents of
331 private SPARC binaries.
332 The ability to build such union directories
333 obviates the need for a shell
336 while providing opportunities for managing heterogeneity.
337 If the system were a Power PC, the same sequence would be run with
339 textually substituted for
341 to place the Power PC binaries in
343 rather than the SPARC binaries.
345 Trouble is already brewing. After these bindings are set up,
351 set the current working directory, to
357 We will return to this issue.
359 There are some important differences between
363 symbolic links are a static part of the file system, while
364 Plan 9 bindings are created at run time, are stored in the kernel,
365 and endure only as long as the system maintains them;
367 Since they are known to the kernel but not the file system, they must
368 be set up each time the kernel boots or a user logs in;
369 permanent bindings are created by editing system initialization scripts
370 and user profiles rather than by building them in the file system itself.
372 The Plan 9 kernel records what bindings are active for a process,
373 whereas symbolic links, being held on the Unix file server, may strike whenever the process evaluates
375 Also, symbolic links apply to all processes that evaluate the affected file, whereas
377 has a local scope, applying only to the process that executes it and possibly some of its
378 peers, as discussed in the next section.
379 Symbolic links cannot construct the sort of
381 directory built here; it is possible to have multiple directories point to
383 but not the other way around.
386 symbolic links are symbolic, like macros: they evaluate the associated names each time
388 Bindings, on the other hand, are evaluated only once, when the bind is executed;
389 after the binding is set up, the kernel associates the underlying files, rather than their names.
390 In fact, the kernel's representation of a bind is identical to its representation of a mount;
391 in effect, a bind is a mount of the
395 The binds and mounts coexist in a single
397 the subject of the next section.
401 Unix has a single global mount table
402 for all processes in the system, but Plan 9's mount tables are local to each process.
403 By default it is inherited when a process forks, so mounts and binds made by one
404 process affect the other, but a process may instead inherit a copy,
405 so modifications it makes will be invisible to other processes.
406 The convention is that related processes, such
407 as processes running in a single window, share a mount table, while sets of processes
408 in different windows have distinct mount tables.
409 In practice, the name spaces of the two windows will appear largely the same,
410 but the possibility for different processes to see different files (hence services) under
411 the same name is fundamental to the system,
412 affecting the design of key programs such as the
413 window system [Pike91].
415 The Plan 9 mount table is little more than an ordered list of pairs, mapping the
421 will be an item called a
425 pointing to the root of the file service,
426 while for a bind it will be the
442 The evaluation of a file name proceeds as follows.
443 If the name begins with a slash, start with the
445 for the root; otherwise start with the
447 for the current directory of the process.
448 For each path element in the name,
455 to that element [Pike93].
456 If the walk succeeds, look to see if the resulting
460 in the mount table, and if so, replace it by the corresponding
462 Advance to the next element and continue.
464 There are a couple of nuances. If the directory being walked is a union directory,
465 the walk is attempted in the elements of the union, in order, until a walk succeeds.
466 If none succeed, the operation fails.
467 Also, when the destination of a walk is a directory for a purpose such as the
473 once the final walk of the sequence has completed the operation stops;
474 the final check through the mount table is not done.
475 Among other things, this simplifies the management of union directories;
476 for example, subsequent
478 calls will append to the union associated with the underlying
480 instead of what is bound upon it.
482 A Definition of Dot-Dot
484 The ability to construct union directories and other intricate naming structures
485 introduces some thorny problems: as with symbolic links,
486 the name space is no longer hierarchical, files and directories can have multiple
487 names, and the meaning of
489 the parent directory, can be ambiguous.
493 is straightforward if the directory is in a locally hierarchical part of the name space,
496 should identify when the current directory is a mount point or union directory or
497 multiply symlinked spot (which we will henceforth call just a mount point, for brevity),
498 there is no obvious answer.
499 Name spaces have been part of Plan 9 from the beginning, but the definition of
501 has changed several times as we grappled with this issue.
502 In fact, several attempts to clarify the meaning of
505 resulted in definitions that could charitably be summarized as `what the implementation gives.'
507 Frustrated by this situation, and eager to have better-defined names for some of the
508 applications described later in this paper, we recently proposed the following definition
512 The parent of a directory
515 is the same directory that would obtain if
516 we instead accessed the directory named by stripping away the last
520 For example, if we are in the directory
528 as if we had executed a
533 This definition is easy to understand and seems natural.
534 It is, however, a purely
536 definition that flatly ignores evaluated file names, mount tables, and
537 other kernel-resident data structures.
538 Our challenge is to implement it efficiently.
539 One obvious (and correct)
540 implementation is to rewrite path names lexically to fold out
542 and then evaluate the file name forward from the root,
543 but this is expensive and unappealing.
544 We want to be able to use local operations to evaluate file names,
545 but maintain the global, lexical definition of dot-dot.
550 To operate lexically on file names, we associate a name with each open file in the kernel, that
554 The first step is therefore to store a
558 in the system, called its
566 are stored as full text strings, shared copy-on-write for efficiency.
567 The task is to maintain each
569 as an accurate absolute name using only local operations.
571 When a file is opened, the file name argument in the
577 or ...) call is recorded in the
581 When the file name begins with a slash, the name is stored as is,
582 subject to a cleanup pass described in the next section.
583 Otherwise, it is a local name, and the file name must be made
584 absolute by prefixing it with the
586 of the current directory, followed by a slash.
587 For example, if we are in
600 This assumes, of course, that the local file name contains no
603 If it does, instead of storing for example
605 we delete the last element of the existing name and set the
609 To maintain the lexical naming property we must guarantee that the resulting
611 if it were to be evaluated, would yield the identical directory to the one
612 we actually do get by the local
616 If the current directory is not a mount point, it is easy to maintain the lexical property.
617 If it is a mount point, though, it is still possible to maintain it on Plan 9
618 because the mount table, a kernel-resident data structure, contains all the
619 information about the non-hierarchical connectivity of the name space.
620 (On Unix, by contrast, symbolic links are stored on the file server rather than in the kernel.)
621 Moreover, the presence of a full file name for each
623 in the mount table provides the information necessary to resolve ambiguities.
625 The mount table is examined in the
627 direction when evaluating a name, but
629 points backwards in the hierarchy, so to evaluate
631 the table must be examined in the
634 (``How did we get here?'')
638 is ambiguous when there are multiple bindings (mount points) that point to
639 the directories involved in the evaluation of
641 For example, return to our original script with
643 (containing a home directory for
647 (containing a home directory for
651 This is represented by two entries in the mount table,
657 If we have set our current directory to
659 (which has landed us in the physical location
661 our current directory is not a mount point but its parent is.
664 is ambiguous: it could be
669 and the ambiguity is caused by two
673 By our definition, if we now evaluate
675 we should acquire the directory
679 could not possibly result in
681 home directory, which it should.
682 On the other hand, if we had originally gone to
690 home directory because there is no directory
695 The problem is that by using local file operations, it is impossible
696 to distinguish these cases: regardless of whether we got here using the name
700 the resulting directory is the same.
701 Moreover, the mount table does not itself have enough information
702 to disambiguate: when we do a local operation to evaluate
706 we discover that the directory is a
708 in the mount table; should we step back through the table to
712 The solution comes from the
715 Whether to step back through the mount point
722 directory is trivially resolved by asking the question,
725 for the directory begin
727 If it does, then the path that was evaluated to get us to the current
728 directory must have gone through this mount point, and we should
729 back up through it to evaluate
731 if not, then this mount table entry is irrelevant.
740 element in the path name is evaluated,
741 if the directory is a
743 in the mount table, the corresponding
745 is taken instead, provided the
751 of the original directory.
752 Since we always know the full name of the directory
753 we are evaluating, we can always compare it against all the entries in the mount table that point
754 to it, thereby resolving ambiguous situations
758 This check also guarantees we don't follow a misleading mount point, such as the entry pointing to
760 when we are really in
762 Keeping the full names with the
764 makes it easy to use the mount table to decide how we got here and, therefore,
767 In summary, the algorithm is as follows.
768 Use the usual file system operations to walk to
770 call the resulting directory
773 the last element of the initial file name.
774 Examine all entries in the mount table whose
782 identical to the truncated name.
785 is the correct result; by construction, it also has the right
787 In our example, evaluating
809 which matches that of the
815 Since this implementation uses only local operations to maintain its names,
816 it is possible to confuse it by external changes to the file system.
817 Deleting or renaming directories and files that are part of a
819 or modifying the mount table, can introduce errors.
820 With more implementation work, such mistakes could probably be caught,
821 but in a networked environment, with machines sharing a remote file server, renamings
822 and deletions made by one machine may go unnoticed by others.
823 These problems, however, are minor, uncommon and, most important, easy to understand.
824 The method maintains the lexical property of file names unless an external
825 agent changes the name surreptitiously;
826 within a stable file system, it is always maintained and
830 To recapitulate, maintaining the
832 absolute file names lexically and using the names to disambiguate the
833 mount table entries when evaluating
836 combine to maintain the lexical definition of
842 The lexical processing can generate names that are messy or redundant,
843 ones with extra slashes or embedded
847 elements and other extraneous artifacts.
848 As part of the kernel's implementation, we wrote a procedure,
850 that rewrites a name in place to canonicalize its appearance.
851 The procedure is useful enough that it is now part of the Plan 9 C
852 library and is employed by many programs to make sure they always
853 present clean file names.
856 is analogous to the URL-cleaning rules defined in RFC 1808 [Field95], although
857 the rules are slightly different.
859 iteratively does the following until no further processing can be done:
861 1. Reduce multiple slashes to a single slash.
866 (the current directory).
870 path name elements (the parent directory) and the
873 element that precedes them.
877 elements that begin a rooted path, that is, replace
881 at the beginning of a path.
885 elements that begin a non-rooted path.
887 If the result of this process is a null string,
891 representing the current directory.
893 The fd2path system call
895 Plan 9 has a new system call,
897 to enable programs to extract the
899 associated with an open file descriptor.
900 It takes three arguments: a file descriptor, a buffer, and the size of the buffer:
902 int fd2path(int fd, char *buf, int nbuf)
904 It returns an error if the file descriptor is invalid; otherwise it fills the buffer with the name
907 (If the name is too long, it is truncated; perhaps this condition should also draw an error.)
910 system call is very cheap, since all it does is copy the
912 string to user space.
914 The Plan 9 implementation of
918 rather than the tricky algorithm necessary in Unix:
921 getwd(char *buf, int nbuf)
925 fd = open(".", OREAD);
928 n = fd2path(fd, buf, nbuf);
935 (The Unix specification of
937 does not include a count argument.)
940 is not only straightforward, it is very efficient, reducing the performance
941 advantage of a built-in
943 command while guaranteeing that all commands, not just
945 see sensible directory names.
947 Here is a routine that prints the file name associated
948 with each of its open file descriptors; it is useful for tracking down file descriptors
949 left open by network listeners, text editors that spawn commands, and the like:
958 if(fd2path(i, buf, sizeof buf) >= 0)
959 print("%d: %s\en", i, buf);
967 was the motivation for getting names right, good file names are useful in many contexts
968 and have become a key part of the Plan 9 programming environment.
969 The compilers record in the symbol table the full name of the source file, which makes
970 it easy to track down the source of buggy, old software and also permits the
971 implementation of a program,
973 to automate tracking it down.
974 Given the name of a program,
976 reads its symbol table, extracts the file information,
977 and triggers the editor to open a window on the program's
981 No guesswork, no heuristics.
985 routine was the inspiration for a new file in the
987 file system [Kill84].
992 is a list of all its open files, including its working directory,
993 with associated information including its open status,
994 I/O offset, unique id (analogous to i-number)
996 Here is the contents of the
998 file for a process in the window system on the machine being used to write this paper:
1000 % cat /proc/125099/fd
1002 0 r M 5141 00000001.00000000 0 /mnt/term/dev/cons
1003 1 w M 5141 00000001.00000000 51 /mnt/term/dev/cons
1004 2 w M 5141 00000001.00000000 51 /mnt/term/dev/cons
1005 3 r M 5141 0000000b.00000000 1166 /dev/snarf
1006 4 rw M 5141 0ffffffc.00000000 288 /dev/draw/new
1007 5 rw M 5141 00000036.00000000 4266337 /dev/draw/3/data
1008 6 r M 5141 00000037.00000000 0 /dev/draw/3/refresh
1009 7 r c 0 00000004.00000000 6199848 /dev/bintime
1012 (The Linux implementation of
1014 provides a related service by giving a directory in which each file-descriptor-numbered file is
1015 a symbolic link to the file itself.)
1016 When debugging errant systems software, such information can be valuable.
1018 Another motivation for getting names right was the need to extract from the system
1019 an accurate description of the mount table, so that a process's name space could be
1020 recreated on another machine, in order to move (or simulate) a computing environment
1022 One program that does this is Plan 9's
1024 command, which recreates the local name space on a remote machine, typically a large
1025 fast multiprocessor.
1026 Without accurate names, it was impossible to do the job right; now
1028 provides a description of the name space of each process,
1029 .CW /proc/\f2n\fP/ns :
1031 % cat /proc/125099/ns
1040 bind -a /rc/bin /bin
1044 mount -a #s/dns /net
1046 mount -c #s/boot /n/emelie
1047 bind -c /n/emelie/mail /mail
1048 mount -c /net/il/134/data /mnt/term
1049 bind -a /usr/rob/bin/rc /bin
1050 bind -a /usr/rob/bin/386 /bin
1051 mount #s/boot /n/emelieother other
1052 bind -c /n/emelieother/rob /tmp
1053 mount #s/boot /n/dump dump
1054 bind /mnt/term/dev/cons /dev/cons
1061 notation identifies raw device drivers so they may be attached to the name space.)
1062 The last line of the file gives the working directory of the process.
1063 The format of this file is that used by a library routine,
1065 which reads a textual description like this and reconstructs a name space.
1066 Except for the need to quote
1068 characters, the output is also a shell script that invokes the user-level commands
1072 which are just interfaces to the underlying system calls.
1075 .CW /net/il/134/data
1076 represent network connections; to find out where they point, so that the corresponding
1077 calls can be reestablished for another process,
1078 they must be examined in more detail using the network device files [PrWi93]. Another program,
1080 does this; it reads the
1081 .CW /proc/\f2n\fP/ns
1082 file, decodes the information, and interprets it, translating the network
1083 addresses and quoting the names when required:
1086 mount -a '#s/dns' /net
1088 mount -c il!135.104.3.100!12884 /mnt/term
1091 These tools make it possible to capture an accurate description of a process's
1092 name space and recreate it elsewhere.
1093 And like the open file descriptor table,
1094 they are a boon to debugging; it is always helpful to know
1095 exactly what resources a program is using.
1099 This work was done for the Plan 9 operating system, which has the advantage that
1100 the non-hierarchical aspects of the name space are all known to the kernel.
1101 It should be possible, though, to adapt it to a Unix system.
1102 The problem is that Unix has nothing corresponding precisely to a
1104 which in Plan 9 represents the unique result of evaluating a name.
1107 structure is a shared structure that may represent a file
1108 known by several names, while the
1110 structure refers only to open files, but for example the current working
1111 directory of a process is not open.
1112 Possibilities to address this discrepancy include
1115 structure that connects a name and a
1117 or maintaining a separate per-process table that maps names to
1119 disambiguating using the techniques described here.
1121 the result would be an implementation of
1123 that reduces the need for a built-in
1125 in the shell and offers a consistent, sensible interpretation of the `parent directory'.
1127 We have not done this adaptation, but we recommend that the Unix community try it.
1131 It should be easy to discover a well-defined, absolute path name for every open file and
1132 directory in the system, even in the face of symbolic links and other non-hierarchical
1133 elements of the file name space.
1134 In earlier versions of Plan 9, and all current versions of Unix,
1135 names can instead be inconsistent and confusing.
1137 The Plan 9 operating system now maintains an accurate name for each file,
1138 using inexpensive lexical operations coupled with local file system actions.
1139 Ambiguities are resolved by examining the names themselves;
1140 since they reflect the path that was used to reach the file, they also reflect the path back,
1141 permitting a dependable answer to be recovered even when stepping backwards through
1142 a multiply-named directory.
1144 Names make sense again: they are sensible and consistent.
1145 Now that dependable names are available, system services can depend on them,
1146 and recent work in Plan 9 is doing just that.
1147 We\(emthe community of Unix and Unix-like systems\(emshould have done this work a long time ago.
1151 Phil Winterbottom devised the
1159 based on an earlier implementation of path name management that
1160 the work in this paper replaces.
1161 Russ Cox wrote the final version of
1163 and helped debug the code for reversing the mount table.
1164 Ken Thompson, Dave Presotto, and Jim McKie offered encouragement and consultation.
1170 ``Relative Uniform Resource Locators'',
1171 .I "Network Working Group Request for Comments: 1808" ,
1176 ``Processes as Files'',
1177 .I "Proceedings of the Summer 1984 USENIX Conference" ,
1178 Salt Lake City, 1984, pp. 203-207.
1182 ``ksh: An Extensible High Level Language'',
1183 .I "Proceedings of the USENIX Very High Level Languages Symposium" ,
1184 Santa Fe, 1994, pp. 129-146.
1188 personal communication.
1191 Jan-Simon Pendry and Marshall Kirk McKusick,
1192 ``Union Mounts in 4.4BSD-Lite'',
1193 .I "Proceedings of the 1995 USENIX Conference" ,
1198 ``8½, the Plan 9 Window System'',
1199 .I "Proceedings of the Summer 1991 USENIX Conference" ,
1200 Nashville, 1991, pp. 257-265.
1203 Rob Pike, Dave Presotto, Ken Thompson, Howard Trickey, and Phil Winterbottom,
1204 ``The Use of Name Spaces in Plan 9'',
1205 .I "Operating Systems Review" ,
1207 2, April 1993, pp. 72-76.
1210 Dave Presotto and Phil Winterbottom,
1211 ``The Organization of Networks in Plan 9'',
1212 .I "Proceedings of the Winter 1993 USENIX Conference" ,
1213 San Diego, 1993, pp. 43-50.
projects / plan9front.git / blob