 |
Description  |
|
|
CROSS REFERENCE TO RELATED APPLICATIONS
This application is related in subject matter to the following applications
filed concurrently herewith and assigned to a common assignee:
U.S. Pat. No. 4,897,781 filed by A. Chang, G. H. Neuman, A. A.
Shaheen-Gouda, and T. A. Smith for A System And Method For Using Cached
Data At A Local Node After Re-opening A File At A Remote Node In A
Distributed Networking Environment.
Application Ser. No. 07/014,884, now abandoned, filed by D. W. Johnson, L.
W. Henson, A. A. Shaheen-Gouda, and T. A. Smith for A System Method for
Version Level Negotiation.
U.S. Pat. No. 4,887,204 filed by D. W. Johnson, G. H. Neuman, C. H. Sauer,
A. A. Shaheen-Gouda, and T. A. Smith for A System And Method For Accessing
Remote Files In A Distributed Networking Environment.
Application Ser. No. 07/014,900, now abandoned, filed by D. W. Johnson, A.
A. Shaheen-Gouda, T. A. Smith for Distributed File Access Structure Lock.
Application Ser. No. 07/014,891, now abandoned, filed by L. W. Henson, A.
A. Shaheen-Gouda, and T. A. Smith for Distributed File and Record Locking.
U.S. Pat. No. 5,001,628 filed by D. W. Johnson, L. K. Loucks, C. H. Sauer,
and T. A. Smith for Single System Image.
Application Ser. No. 07/014,888, now U.S. Pat. No. 5,133,053, filed by D.
W. Johnson, L. K. Loucks, A. A. Shaheen-Gouda for Interprocess
Communication Queue Location Transparency.
The disclosures of the foregoing co-pending applications are incorporated
herein by reference.
DESCRIPTION
TECHNICAL FIELD
This invention generally relates to improvements in operating systems for a
distributed data processing system and, more particularly, to an
improvement in an operating system for a multi-processor system
interconnected by a local area network (LAN) or a wide area network (WAN).
The improvement according to the invention provides an increased
efficiency in file directory caching for accessing files by processors in
the system, regardless of where those files are located in the system.
BACKGROUND ART
This invention is specifically concerned with distributed data processing
systems characterized by a plurality of processors interconnected in a
network. As actually implemented, the invention runs on a plurality of IBM
RT PC.sup.1 interconnected by IBM's Systems Network Architecture (SNA),
and more specifically SNA LU 6.2 Advanced Program to Program Communication
(APPC). SNA uses as its link level Ethernet.sup.2, a local area network
(LAN) developed by Xerox Corp., or SDLC (Synchronous Data Link Control). A
simplified description of local area networks including the Ethernet local
area network may be found in a book by .sup.1 RT and RT PC are registered
trademarks of IBM Corporation. .sup.2 Ethernet is a trademark of Xerox
Corporation. Larry E. Jordan and Bruce Churchill entitled Communications
and Networking for the IBM PC, published by Robert J. Brady (a
Prentice-Hall company) (1983). A more definitive description of
communications systems for computers, particularly of SNA and SDLC, is to
be found in a book by R. J. Cypser entitled Communications Architecture
for Distributed Systems, published by Addison-Wesley (1978). It will,
however, be understood that the invention may be implemented using other
and different computers than the IBM RT PC interconnected by other
networks than the Ethernet local area network or IBM's SNA.
As mentioned, the invention to be described hereinafter is directed to a
distributed data processing system in a communication network. In this
environment, each processor at a node, in the network potentially may
access all the files in the network regardless of the nodes at which the
files may reside. As shown in FIG. 1, a distributed network environment 1
may consist of two or more nodes A, B and C connected through a
communication link or network 3. The network 3 can be a local area network
(LAN) as mentioned or a wide area network (WAN), the latter comprising a
switched or leased teleprocessing (TP) connection to other nodes or to a
SNA network of systems. At any of the nodes A, B or C there may be a
processing system 10A, 10B or 10C, such as the aforementioned IBM RT PC.
Each of these systems 10A, 10B and 10C may be a single user system or a
multi-user system with the ability to use the network 3 to access files
located at a remote node in the network. For example, the processing
system 10A at local node A is able to access the files 5B and 5C at the
remote nodes B and C.
The problems encountered in accessing remote nodes can be better understood
by first examining how a standalone system accesses files In a standalone
system, such as 10 shown in FIG. 2, a local buffer 12 in the operating
system 11 is used to buffer the data transferred between the permanent
storage 2, such as a hard file or a disk in a personal computer, and the
user address space 14. The local buffer 12 in the operating system 11 is
also referred to as a local cache or kernel buffer. For more information
on the UNIX.sup.3 operating system kernel, see the book by Brian W.
Kernighan and Rob Pike entitled The Unix Programming Environment,
Prentiss-Hall (1984). A more detailed description of the design of the
UNIX operating system is to be found in the book by Maurice J. Bach,
Design of the Unix Operating System, Prentiss-Hall (1986). The local cache
can be best understood in terms of a memory resident disk. The data
retains the physical characteristics that it had on disk; however, the
information how resides in a medium that lends itself to faster data
transfer rates very close to the rates achieved in main system memory.
.sup.3 Developed and licensed by AT&T. UNIX is a registered trademark of
AT&T in the U.S.A. and other countries.
In the standalone system, the kernel buffer 12 is identified by blocks 15
which are designated as device number and logical block number within the
device. When a read system call 16 is issued, it is issued with a file
descriptor of the file 5 and a byte range within the file 5, as shown in
step 101 in FIG. 3. The operating system 11 takes this information and
converts it to device number and logical block numbers of the device in
step 102. Then the operating system 11 reads the cache 12 according to the
device number and logical block numbers, step 103.
Any data read from the disk 2 is kept in the cache block 15 until the cache
block 15 is needed. Consequently, any successive read requests from an
application program 4 that is running on the processing system 10 for the
same data previously read from the disk is accessed from the cache 12 and
not the disk 2. Reading from the cache is less time consuming than
accessing the disk; therefore, by reading from the cache, performance of
the application 4 is improved. Obviously, if the data which is to be
accessed is not in the cache, then a disk access must be made, but this
requirement occurs infrequently.
Similarly, data written from the application 4 is not saved immediately on
the disk 2 but is written to the cache 12. This again saves time,
improving the performance of the application 4. Modified data blocks in
the cache 12 are saved on the disk 2 periodically under the control of the
operating system 11.
Use of a cache in a standalone system that utilizes the AIX.sup.4 operating
system, which is the environment in which the invention was implemented,
improves the overall performance of the system disk and minimizes access
time by eliminating the need for successive read and write disk
operations.
.sup.4 AIX is a trademark of IBM Corporation.
In the distributed networking environment shown in FIG. 1, there are two
ways the processing system 10C in local node C could read the file 5A from
node A. In one way, the processing system 10C could copy the whole file 5A
and then read it as if it were a local file 5C residing at node C. Reading
the file in this way creates a problem if another processing system 10B at
node B, for example, modifies the file 5A after the file 5A has been
copied at node C. The processing system 10C would not have access to the
latest modifications to the file 5A.
Another way for processing system 10C to access a file 5A at node A is to
read one block at a time as the processing system at node C requires it. A
problem with this method is that every read has to go across the network
communications link 3 to the node A where the file resides. Sending the
data for every successive read is time consuming.
Accessing files across a network presents two competing problems as
illustrated above. One problem involves the time required to transmit data
across the network for successive reads and writes. On the other hand, if
the file data is stored in the node to reduce network traffic, the file
integrity may be lost. For example, if one of the several nodes is also
writing to the file, the other nodes accessing the file may not be
accessing the latest updated file that has just been written. As such, the
file integrity is lost, and a node may be accessing incorrect and outdated
files. Within this document, the term "server" will be used to indicate
the processing system where the file is permanently stored, and the term
client will be used to mean any other processing system having processes
accessing the file. The invention to be described hereinafter is part of
an operating system which provides a solution to the problem of managing
distributed information.
Other approaches to supporting a distributed data processing system in a
UNIX operating system environment are known. For example, Sun Microsystems
has released a Network File System (NFS) and Bell Laboratories has
developed a Remote File System (RFS). The Sun Microsystems NFS has been
described in a series of publications including S. R. Kleiman, "Vnodes: An
Architecture for Multiple File System Types in Sun UNIX", Conference
Proceedings, USENIX 1986 Summer Technical Conference and Exhibition, pp.
238 to 247; Russel Sandberg et al., "Design and Implementation of the Sun
Network Filesystem", Conference Proceedings, Usenix 1985, pp. 119 to 130;
Dan Walsh et al., "Overview of the Sun Network File System", pp. 117 to
124; JoMei Chang, "Status Monitor Provides Network Locking Service for
NFS"; JoMei Chang, "SunNet", pp. 71 to 75; and Bradley Taylor, "Secure
Networking in the Sun Environment", pp. 28 to 36. The AT&T RFS has also
been described in a series of publications including Andrew P. Rifkin et
al., "RFS Architectural Overview", USENIX Conference Proceedings, Atlanta,
Ga. (June 1986), pp. 1 to 12; Richard Hamilton et al., "An Administrator's
View of Remote File Sharing", pp. 1 to 9; Tom Houghton et al., "File
Systems Switch", pp. 1 to 2; and David J. Olander et al., "A Framework for
Networking in System V", pp. 1 to 8.
One feature of the distributed services system in which the subject
invention is implemented which distinguishes it from the Sun Microsystems
NFS, for example, is that Sun's approach was to design what is essentially
a stateless machine. More specifically, the server in a distributed system
may be designed to be stateless. This means that the server does not store
any information about client nodes, including such information as which
client nodes have a server file open, whether client processes have a file
open in read.sub.-- only or read.sub.-- write modes, or whether a client
has locks placed on byte ranges of the file. Such an implementation
simplifies the design of the server because the server does not have to
deal with error recovery situations which may arise when a client fails or
goes off-line without properly informing the server that it is releasing
its claim on server resources. An entirely different approach was taken in
the design of the distributed services system in which the present
invention is implemented. More specifically, the distributed services
system may be characterized as a "statefull implementation".
A "statefull" server, such as that described here, does keep information
about who is using its files and how the files are being used. This
requires that the server have some way to detect the loss of contact with
a client so that accumulated state information about that client can be
discarded. The cache management strategies described here, however, cannot
be implemented unless the server keeps such state information. The
management of the cache is affected, as described below, by the number of
client nodes which have issued requests to open a server file and the
read/write modes of those opens.
More specifically, because file path name resolution is so frequent, it is
important that it be done efficiently. Each system call that uses a file
name, for example mount or open, can require that a directory be read and
searched for each component of the file name's path. The performance
penalties of reading numerous directories each time a file name is used
are even more serious in a distributed environment where some of the
directories may be in remote nodes.
Some UNIX.TM. implementations cache directory entries each time they are
used in resolving a file's name. Subsequent file name resolution on the
same file or files with names that have path pieces in common with the
previously cached entries will run faster because directory entries can be
found in the cache. Finding directory entries in the cache is faster than
reading and searching directories because: (1), the directory cache is a
special data structure maintained by the operating system that is
optimized for searching; (2), the cache is kept in memory while the
directories need to be read from the file system; and (3), the cache will
usually have only a limited number of entries to be examined. The
directory cache holds the most recently used, and hence the most likely to
be useful, directory entries.
There are two major problems that the operating system faces in using a
directory cache. The contents of the cache must be kept consistent with
the contents of the directories, and the cache must be kept from getting
too big. It is important that the cache be kept consistent. If the
directory cache indicates that a file's inode number is, say, 45 but the
directory has been changed, perhaps due to a mv command, so that the
file's real inode number is 62, attempts to resolve the file's name will
resolve to the wrong file--an open could open a file different than the
one that was specified. If the cache is allowed to grow arbitrarily, it
will eventually be so large that the time required to search it will
negatively affect performance.
In a stand-alone system, the operating system itself is responsible for all
changes to directories, making it possible for the operating system to
purge from the directory cache any entries that may have changed, thus
always leaving the directory cache with consistent entries. When the cache
becomes full, some entries can be purged to make room for new entries. The
choice of entries to purge to make room is not critical, but performance
will usually be least impacted if the most recently used entries are
retained. Since the major problems of directory caching can be handled in
this fashion for stand-alone systems, several stand-alone UNIX.TM.
implementations including stand-alone AIX.TM. do directory caching.
The solutions available for stand-alone systems do not work in a
distributed environment. The directory cache is maintained by client
nodes, while changes to directories in other, server, nodes could result
in inconsistent cache entries. Attempts to maintain consistency by
communicating every directory change at every server to every client
caching directory entries could flood a network with these messages,
vitiating any performance advantages from the directory caching.
It would, therefore, provide greatly improved operating efficiency in
accessing file directories in networks as described above to have the
ability to cache file directory information and be assured of its
validity, while not needlessly and inefficiently updating this information
during periods when no changes have been made.
SUMMARY OF THE INVENTION
Accordingly, an improved directory caching technique is provided for a
plurality of data processing systems which are connected together in a
network. In the system, when a local, or client, data processing system
interrogates a remote, or server, data processing system for a unit of
directory information, the server system is enabled to automatically send
additional units of pertinent directory information back to the client
system in response to a subsequent change in the directory structure of
the server system. If the server system is unable to continue updating the
client system, for any of a plurality of possible reasons, the server
system informs the client system of this fact, which enables the client
system to purge itself of the formerly stored directory cache entry
relative to this path, since the client system can no longer consider this
cached path information to be currently correct.
Possible reasons that the server system can no longer continue to send
directory path updating information to the client system are: (1) a
general saturation of server processing resources, (2) a saturation of the
server's processing resources which have been allocated to the directory
caching updating function, (3) the current unavailability of a reliable
communications link between the server system and the client system, (4)
the necessity of disconnecting the server system from the communications
network, for example, to allow maintenance services at the server system,
and (5) because of a lack of a recent inquiry from the client system.
When a server system is updating a plurality of clients and nears
exhaustion of its resources to perform this updating function, the server
informs the clients having the least recent inquiries, on the basis that
those clients' systems' performances would be least affected by having
this updating facility suspended.
The foregoing and other objects, features, extensions and advantages of the
invention will be apparent from the following more particular description
of the preferred embodiments of the invention as illustrated in the
accompanying drawing.
BRIEF DESCRIPTION OF DRAWING
FIG. 1 is a block diagram showing a typical distributed data processing
system in which the subject invention is designed to operate;
FIG. 2 is a block diagram illustrating a typical stand-alone processor
system;
FIG. 3 is a flowchart showing the steps performed by an operating system
when a read system call is made by an application running on a processor;
FIG. 4 is a block diagram of the data structure illustrating the scenario
for following a path to a file operation at a local node as performed by
the operating system which supports the subject invention;
FIGS. 5 and 6 are block diagrams of the data structures illustrating the
before and after conditions of the scenario for a mount file operation at
a local node as performed by the operating system;
FIG. 7 is a block diagram, similar to FIG. 1, showing a distributed data
processing system according to the invention;
FIG. 8 is a block diagram of the data structure for the distributed file
system shown in FIG. 7;
FIGS. 9A, 9B, 9C, 9D, 9E and 9F are block diagrams of component parts of
the data structure shown in FIG. 8;
FIGS. 10, 11 and 12 are block diagrams of the data structures illustrating
the scenarios for a mount file operation and following a path to a file at
a local and remote node in a distributed system as performed by the
operating system;
FIG. 13 shows a typical directory tree structure which exists at a local or
client system.
FIG. 14 shows the client directory tree structure of FIG. 13 and,
additionally, a remote, or server, directory tree structure which is
available for access by the client system.
FIG. 15 shows the contents of a typical directory cache at a client.
FIG. 16 shows the structure of a typical Node Table at a server.
FIG. 17 is a flow diagram which shows the operations at the server during
directory updates in a system using the improved directory caching
technique of this invention.
FIG. 18 is a detailed flow diagram which shows the operation at the client
in response to a dfs.sub.-- fs advise in a system using the improved
directory caching technique of this invention.
FIG. 19 shows the detailed contents of an entry in the directory cache of
FIG. 20.
FIG. 20 shows the hash table technique used in searching the contents of
the directory cache.
FIG. 21 is a detailed flow diagram of server operations in response to the
dfs.sub.-- lookup rpc request in a system using the improved directory
caching technique of this invention.
FIG. 22 is a detailed flow diagram of the client operations during a lookup
of a file name in a remote directory in a system using the improved
directory caching technique of this invention.
FIG. 23 is a detailed flow diagram of the directory cache search operation
of this invention.
BEST MODE FOR CARRYING OUT THE INVENTION
The following disclosure describes solutions to problems which are
encountered when creating a distributed file system in which the logic
that manages a machine's files is altered to allow files that physically
reside in several different machines to appear to be part of the local
machine's file system. The implementation described is an extension of the
file system of the AIX operating system. Reference should be made to the
above-referenced Technical Reference for more information on this
operating system. Specific knowledge of the following AIX file system
concepts is assumed: tree structured file systems; directories; and file
system organization, including inodes.
The essential aspects of a file system that are relevant to this discussion
are listed below:
a) each file on an individual file system is uniquely identified by its
inode number
b) directories are files, and thus a directory can be uniquely identified
by its inode number.
Note: In some contexts it is necessary to distinguish between files which
are directories and files which are not directories (e.g., files which
simply contain ordinary data, or other files types supported by UNIX
derivative operating systems such as special files or pipes).
In this disclosure the term "simple file" is used to indicate such a
non-directory file. Unless otherwise indicated the term "file" may mean
either a directory file or a simple file, and, of course, the term
"directory" means a directory file.
c) a directory contains an array of entries of the following form:
name-inode number
where the inode number may be that of a simple file or that of another
directory.
Note: A directory may contain other directories, which, in turn, may
contain other directories or simple files.
Thus a directory may be viewed as the root of a subtree which may include
many levels of descendant directories, with the leaves of the tree being
"simple files".
In this disclosure the term "descendants" means all of the files which
exist in the file tree below a particular directory, even those which can
be reached only by going through other directories. The "immediate
descendants" of a directory are only those files (simple files or
directories) whose names appear in the directory.
d) by convention, the inode number of the file system's root directory is
inode number 2.
The following discussion describes how traditional UNIX operating systems
use mounts of entire file systems to create file trees, and how paths are
followed in such a file tree.
Following the path "/dir1/dir2/file" within a device's file system thus
involves the following steps:
1. Read the file identified by inode number 2 (the device's root
directory).
2. Search the directory for an entry with name=dir1.
3. Read the file identified by the inode number associated with dir1 (this
is the next directory in the path).
4. Search the directory for an entry with name=dir2.
5. Read the file identified by the inode number associated with dir2 (this
is the next directory in the path).
6. Search the directory for an entry with name=file.
7. The inode number associated with file in this directory is the inode
number of the simple file identified by the path "/dir1/dir2/file".
The file trees which reside on individual file systems are the building
blocks from which a node's aggregate file tree is built. A particular
device (e.g., hard file partition) is designated as the device which
contains a node's root file system. The file tree which resides on another
device can be added to the node's file tree by performing a mount
operation. The two principal parameters to the mount operation are (1) the
name of the device which holds the file tree to be mounted and (2) the
path to the directory upon which the device's file tree is to be mounted.
This directory must already be part of the node's file tree; i.e., it must
be a directory in the root file system, or it must be a directory in a
file system which has already been added (via a mount operation) to the
node's file tree.
After the mount has been accomplished, paths which would ordinarily flow
through the "mounted over" directory instead flow through the root inode
of the mounted file system. A mount operation proceeds as follows:
1. Follow the path to the mount point and get the inode number and device
number of the directory which is to be covered by the mounted device.
2. Create a data structure which contains essentially the following:
a) the device name and inode number of the covered directory; and
b) the device name of the mounted device.
The path following in the node's aggregate file tree consists of (a)
following the path in a device file tree until encountering an inode which
has been mounted over (or, of course, the end of the path); (b) once a
mount point is encountered, using the mount data structure to determine
which device is next in the path; and (c) begin following the path at
inode 2 (the root inode) in the device indicated in the mount structure.
The mount data structures are volatile; they are not recorded on disk. The
list of desired mounts must be re-issued each time the machine is powered
up as part of the Initial Program Load (IPL). The preceding discussion
describes how traditional UNIX operating systems use mounts of entire file
systems to create file trees and how paths are followed in such a file
tree. Such an implementation is restricted to mounting the entire file
system which resides on a device. The virtual file system concept
described herein and in the reference material allows (1) mounting a
portion of the file system which resides on a device by allowing the
mounting of files (directories or simple files) in addition to allowing
mounting of devices, and (2) mounting either remote or local directories
over directories which are already part of the file tree. The invention
described herein is an enhancement to the virtual file system concept
which further allows the mounting of simple files (remote or local) over
simple files which are already part of the file tree.
In the virtual file system, the operations which are performed on a
particular device file system are clearly separated from those operations
which deal with constructing and using the node's aggregate file tree. A
node's virtual file system allows access to both local and remote files.
The management of local files is a simpler problem than management of
remote files. For this reason, the discussion of the virtual file system
is broken into two parts. The first part describes only local operations.
This part provides a base from which to discuss remote operations. The
same data structures and operations are used for both remote and local
operations. The discussion on local operations describes those aspects of
the data and procedures which are relevant to standalone operations. The
discussion on remote operations adds information pertinent to remote
operations without, however, reiterating what was discussed in the local
operations section.
FIG. 4 shows the relationship that exists among the data structures of the
virtual file system. Every mount operation creates a new virtual file
system (vfs) data structure. The essential elements in this structure are
(a) a pointer to the root vnode (virtual node) of this virtual file system
(e.g., the arrow from block 21 to block 23), and (b) a pointer to the
vnode which was mounted over when this virtual file system was created
(e.g., the arrow from block 25 to block 24).
Whenever an inode needs to be represented in the file system independent
portion of the system, it is represented by a vnode. The essential
elements in this structure are the following:
a) a pointer to the vfs which contains the vnode (e.g., the arrow from
block 22 to block 21);
b) a pointer to the vfs which is mounted over this inode (e.g., the arrow
from block 24 to block 25); but note however that not all vnodes are the
mount point for a virtual file system, i.e., a null pointer indicates that
this vnode is not a mount point;
c) a pointer to either a surrogate inode or a real inode (e.g., the arrow
from block 26 to block 32); and
d) a pointer to a node table entry (this is a non-null only when the file
is a remote file).
The AIX operating system, in common with other UNIX operating systems,
keeps a memory resident table which contains information about each inode
that is being used by the system. For instance, when a file is opened, its
inode is read from the disk and a subset of this inode information,
together with some additional information, is stored in the inode table.
The essential elements of an inode table entry are (a) a pointer to the
head of a file access structure list and (b) information from the disk
inode, the details of which are not relevant here.
The file access structure records information about which nodes have the
file open, and about the modes (read only or read.sub.-- write) of these
opens. There is a separate file access structure for each node which has
the file open. This state information enables the server to know how each
client is using the server file.
The file system supports a set of operations which may be performed on it.
A process interacts with a file system by performing a file system
operation as follows:
1. The user calls one of the operations providing (perhaps) some input
parameters.
2. The file system logic performs the operation, which may alter the
internal data state of the file
3. The file system logic rcturns to the calling user, perhaps returning
some return parameters.
The operations which can be performed on a file system are referred to as
"vn.sub.-- operations" or "vn.sub.-- ops". There are several vn.sub.--
ops, but the ones which are important to this discussion are described
below:
VN.sub.-- LOOKUP
In the vn.sub.-- lookup operation, the essential iterative step in
following a path in a file system is to locate the name of a path
component in a directory and use the associated inode number to locate the
next file in the chain. The pseudo code for the vn.sub.-- lookup operation
on a local file is listed below:
______________________________________
function lookup
input: directory vnode pointer,
name to be looked up in directory
output: vnode pointer to named file/dir.
convert directory vnode pointer
to an inode pointer;
use pointer in vnode
lock directory's inode;
if( we don't have search permission in
directory )
unlock directory inode;
return error;
search directory for name;
if( found )
create file handle for name;
- use inode found in directory entry;
get pointer to vnode for file handle;
unlock directory inode;
return pointer to vnode;
else -- not found
unlock directory inode;
return error;
______________________________________
LOOKUPPN
The lookuppn operation is the function which follows paths. Its input is a
path (e.g., "/dir1/dir2/file"), and its return is a pointer to the vnode
which represents the file. Lookuppn calls vn.sub.-- lookup to read one
directory, then it checks to see if the vnode returned by vn.sub.-- lookup
has been mounted over. If the vnode is not mounted over, then lookuppn
calls vn.sub.-- lookup in the same file system. If the vnode has been
mounted over, then lookuppn follows the pointer from the mounted over
vnode (e.g., block 24 in FIG. 4) to the vfs of the mounted file system
(e.g., block 25 in FIG. 4). From the vfs, it follows the pointer to the
root vnode (e.g., block 26 in FIG. 4) and, if the vnode is a directory and
not a simple file, issues a new vn.sub.-- lookup giving as input the vfs's
root vnode and the name which constitutes the next element in the path.
The pseudo code for the lookuppn function is listed below:
______________________________________
function lookuppn
input: pathname
output: pointer to vnode for named file
if( first character of path is `/` )
current vnode for search is user's root
directory vnode;
else
current vnode for search is user's
current directory vnode;
repeat
if( next component of path is ". . " )
while( current vnode is root of a
virtual file system )
current vnode becomes the vnode that
the virtual file system is mounted
over;
if( there is not mounted over vnode )
return( error ); -- ". ." past root
of file system
use vn.sub.-- lookup to look up path component
in current vnode;
if( vn.sub.-- lookup found component );
current vnode becomes the vnode
returned by vn.sub.-- lookup;
while( current vnode is mounted over )
follow current vnode's pointer to vfs
structure that represents the
mounted virtual file system;
current vnode becomes root vnode of
the mounted vfs;
else -- vn.sub.-- lookup couldn't file component
return( error ); -- search failed
until( there are no additional path
components );
return( current vnode );
______________________________________
The operation will be illustrated by describing the scenarios of following
a path to a file and mounting a directory. First, in following a path to a
file, suppose an application process issues a system call (e.g., open) for
file "/u/dept54/status". This request is accomplished by the operating
system in the following manner with reference to FIG. 4 (operations which
are basically unchanged from the UNIX operating system are not explained
here in any detail). The following assumptions are made: First, the vfs
represented by block 21 is the root virtual file system. Second, the file
"/u" is represented by vnode block 24 and inode block 31. Third, a
previous mount operation has mounted a device's file system onto the
directory "/u". This mount created the vfs represented by block 25.
Fourth, all of the directories and files involved are on the same device.
Fifth, the following directory entries exist in the indicated directories:
______________________________________
DIRECTORY
INODE NUMBER NAME INODE NUMBER
______________________________________
2 "u" 15
45 "dept54" 71
71 "status" 12
______________________________________
The code which implements the system call calls lookuppn to follow the
path. Lookuppn starts at the root vnode (block 23) of the root virtual
file system (block 21) and calls vn.sub.-- lookup to look up the name "u"
in the directory file represented by this vnode. Vn.sub.-- lookup finds in
the directory that the name "u" is associated with inode 15 in block 31.
Vn.sub.-- lookup must return a pointer to a vnode associated with inode
15. To do this it first brings inode 15 into the inode table. Then it
checks to see if there is already a vnode in the parent vfs (the input
vnode (block 23) has a pointer to the parent vfs) for this vnode. In this
case there is. Vn.sub.-- lookup then finds the vnode (block 24) in the
root vfs (block 21) and returns a pointer to the vnode. Lookuppn discovers
that the returned vnode is mounted over in the parent vfs. It follows the
"mounted over" pointer from the vnode (block 24) to the mounted vfs (block
25). Lookuppn follows the "root vnode" pointer to the root vnode (block
26) of the new vfs (block 25). Lookuppn now calls vn.sub.-- lookup again,
this time inputting a pointer to the root vnode (block 26) and name
"dept54". As before, vn.sub.-- lookup reads the directory, finds the inode
associated with the name, finds or creates a vnode for this inode in the
parent vfs (block 25) and returns a pointer to this vnode. Lookuppn calls
vn.sub.-- lookup once more inputting the vnode for the just found
directory and the name "status". Vn.sub.-- lookup reads the directory,
finds the inode associated with the name (block 34), finds or creates a
vnode (block 28) for this inode in the parent vfs (block 25) and returns a
pointer to this vnode. The code which implements the system call now
performs the requested operation on the file.
Suppose now that an application process issues a "mount" system call to
mount the file "/u/gorp" over the directory "/u/foo". The following
scenario explains how this request is accomplished by the operating system
(again, operations which are basically unchanged from the UNIX operating
system are not explained in any detail).
This scenario refers to FIG. 5, which represents initial conditions, and
FIG. 6, which represents the final conditions, with the following
assumptions: First, the vfs represented by block 41 is the root virtual
file system. Second, all of the directories and files involved are on the
same device. Third, the following directory entries exist in the indicated
directories:
______________________________________
DIRECTORY
INODE NUMBER NAME INODE NUMBER
______________________________________
2 "u" 15
2 "etc" 83
15 "gorp" 92
83 "foo" 75
75 "file1" 89
______________________________________
The code which implements the mount system call performs the following
operations. Lookuppn is called to follow the path to the file which is to
be mounted over--"/etc/foo". At the completion of this operation, the root
vfs (block 41) contains a vnode for "/etc/foo" (block 44) which has a
pointer to the root vfs (block 41) and pointer to an inode table entry
(block 45) for inode 75. Lookuppn is called to follow a path to the file
which is to be mounted--"/etc/gorp". At the completion of this operation,
the root vfs (block 41) contains a vnode for "/etc/gorp" (block 49) whi | | |
