Users that cannot write a directory cannot acquire the
mutex, but they can still obtain a consistent view of directory segment entries by atomically reading a generation
number and busy flag before and after reading each entry.
The generation number is incremented by the library on
each directory update.
Since file system objects correspond to HiStar kernel
objects, permissions are specified in terms of labels, and
are enforced by the kernel, not by the untrusted library
file system code. For example, a file that should be accessible by only one user would be labeled {ur, uw}, where
only that user owns ur and uw. A world-readable file that
can be modified by only that user would be labeled {uw}.
Labels are similarly used for directories; read privilege
on a directory allows listing the files in that directory and
write privilege allows creating new files and renaming or
deleting existing files.
3. 2. Processes
A process in HiStar is a user-space convention. Figure 4 illustrates the kernel objects that make up a typical process. Each
process P has two categories, pr and pw, that protect its secrecy
and integrity, respectively. Threads in a process typically own
{pr, pw}, granting them full access to the process. The process
consists of two containers: a process container and an internal container. The process container exposes objects that
define the external interface to the process, such as a gate to
receive signals from other processes (described in detail in
the OSDI paper18) and a segment to store the process’s exit
status. The process container and exit status segment are
labeled { pw}, allowing other processes to read them, but
not modify them (since other processes do not own this process’s pw). The internal container, address space, and segment objects are labeled { pr, pw}, preventing direct access by
other processes.
3. 3. file descriptors
All of the state typically associated with a file descriptor,
such as the current seek position and open flags, is stored
in a file descriptor segment in HiStar. Every file descriptor
figure 4. structure of a histar process. a process container is
represented by a thick border. Not shown are some label components
that, e.g., ensure other users cannot read the exit status of this
process. Bold and dashed lines represent hard and soft links.
Signal Gate
O = {pr, pw}
G = {uw}
Process Container
L = {pw}
Internal Container
L = {pr, pw}
Exit Status Segment
L = {pw}
Thread
O = {pr, pw}
Executable File
Segment
Heap Segment
Stack Segment
Address
Space
number corresponds to a specific virtual memory address.
When a file descriptor is open in a process, the corresponding file descriptor segment is memory-mapped at the virtual
address for that file descriptor number.
Typically each file descriptor segment has a label of
{ fdr, fdw}, where categories fdr and fdw grant read and
write access to the file descriptor state. Access to the file
descriptor is granted by granting ownership of { fdr, fdw}.
Multiple processes can share file descriptors by mapping
the same descriptor segment into their respective address
spaces. By convention, every process adds hard links for
all of its file descriptor segments to its own container. As
a result, a shared descriptor segment is deallocated only
when it has been closed and unlinked from the container
of each process.
3. 4. users
A pair of unique categories ur and uw define the read and
write privileges of each Unix user U in HiStar, including
root. Typically, threads running on behalf of user U own
{ur, uw}, and a user’s private files would have a label of
{ur, uw}. One consequence of this design is that a single
process can possess the privilege of multiple users, or perhaps multiple user roles, something that is hard to implement in Unix. On the other hand, our prototype does not
support access control lists. (One way to implement access
control lists would be to allocate a pair of categories for
each ACL and to create a gate that would invoke code to
evaluate the ACL rules and selectively grant ownership of
these categories.) The authentication service, which verifies user passwords and grants user privileges, is described
in more detail in Zeldovich et al.
18
3. 5. Gate calls
Gates provide a mechanism for implementing IPC. As an
example, consider a phonebook service that allows looking up people’s phone numbers by their name. Storing all
names in a file may be undesirable, since users could easily obtain a list of all names. A HiStar process could provide
this service by creating a service gate whose initial program
counter corresponded to a function that looks up a name in
a database that is accessible only to that process.
Gates in HiStar have no implicit return mechanism;
the caller explicitly creates a return gate before invoking
the service gate, which allows the calling thread to regain
all of the privileges it had prior to calling the service. A
return category rw is allocated to prevent arbitrary threads
from invoking the return gate; the return gate’s guard set
requires ownership of rw to invoke the gate, and the caller
grants ownership of rw when invoking the service gate.
Figure 5 illustrates a gate call from process P to daemon D.
While this design prevents a user from enumerating
the daemon’s private database, it does not ensure privacy
of users’ queries. If users do not trust the daemon to keep
their queries private, they can enforce the privacy of their
queries, as follows. The calling thread allocates a new
secrecy category xr and invokes the service gate in step
2 with a label of {xr} (instead of ∅). This thread can now
read D’s address space and any of D’s segments, by virtue