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