5. Orthogonality, processes, and races

Yitao Dai: 404127437
Joanna Chen: 004125181
David Hung: 604191130
Victor Kwan: 004151151

        |
        |
        |------• < I love orthogonality!
        |      |
files   |------|-----• < Yeah! processes are totally independent!
        |      |     |
        |      |     |
        +------|-----|-------
               1     2
              processes

When you make a choice, you want that choice to be independent of the other choice. Ideally, decisions don't leak! This is a fundamental way that you can control (or manage) complexity. One application of orthogonality is that operations on files should be independent of what they do with processes. We can generalize that there are two classes of operations: operations that deal with filenames, and operations that don't.

Operations on files
`open(string)`	`close(fd)`	`read(fd)`
`write(fd, ...)`	Create	`remove(string)`
Permissions	Link	`truncate(fd)`
Copy	Append

*As it turns out, the C functions related to these file operations are closely related to where the operations stand with regards to these two classes.

Handles

A handle is an abstract reference to a resource. There are three main methods through which they are implemented:

Pointers: Pointers are simple and fast. However, they are similarly simple to manipulate, and are ultimately unsafe.
Opaque pointers: The opaque pointer struct opaque *f is an incomplete type. It solves the unsafety problem by preventing the program from dereferencing the pointer value. However it works well only for well-behaved programs. Should a program dereference the opaque pointer char *p = (char *)f the program is then able to see the bytes stored and possibly modify the memory location.
Integers: By wrapping opaque pointers as integers typedef int opaque we achieve the desired safety at the expense of complexity, performance, as well as type safety. The operating system interprets each integers in system calls such as read(27, buf, sizeof(buf)) making it so that the user can only receive read information but not memory location.

To elaborate on this notion of type safety, a C compiler would allow the assignment of one variable of typedef int pid_t to another variable of typedef int signal_t. On one hand, this provides us with the necessary obscurity to guarantee the security of these handles, but on the other, it encourages type unsafety and the arbitrary assignment of one pointer to another.

In computer systems, it is important to deal with create and remove processes properly. In unix, a process that ends and exits becomes a zombie process. This zombie process needs to be reaped, where it gets properly removed from the process table. Processes are reaped usually by the parent process of the current process, or in some cases by the init process, the master process.

execvp

#include <unistd.h>
int execvp(const char *file, char *const argv[]);

argv
+---------+
|         | -> "awk"
+---------+
|         | -> "-l"
+---------+
|   •••   |
+---------+
|         |
+---------+

The first argument, by convention, should point to the filename associated with the file being executed. The array of pointers is expected to be terminated by a null pointer or the behavior would be undefined. When execvp(...) is executed, the program file given by the first argument will be loaded into the caller's address space and over-write the program there. Then, the second argument will be provided to the program and starts the execution. it returns nothing and terminates the current process it’s in if the execution succeeds, or -1 if fails.

fork

#include <unistd.h>
pid_t fork(void);

    Process table
    +---------------------------------------------------------+
    |                           •••                           |
    +---------------------------------------------------------+
01  |    | registers |             |fd0|fd1|fd2|fd3|          |
    +---------------------------------------------------------+
02  |    | copied    |             |fd0|fd1|fd2|fd3|          |
    |    | registers |             |   |   |   |   |          | // forked!
    +---------------------------------------------------------+
    |                           •••                           |
    +---------------------------------------------------------+

fork() creates a new process by duplicating the calling process. The new process created is refered to as the child process, and orignal one as parent process. The system call returns 0 to the child, the child’s process ID to the parent process or -1 upon failure. When we fork a process, all the file descriptors are duplicated!

_exit

#include <unistd.h>
void _exit(int status);

_exit() terminates the calling process immediately, the value status is returned to the parent process as the process's exit status, and can be collected using the macro WEXITSTATUS. Note that the process table doesn’t shrink after calling _exit(). The process could now be considered a zombie process - a process that is dead but not yet reaped.

waitpid

#include <sys/wait.h>
pid_t waitpid(pid_t pid, int *stat_loc, int options);

The waitpid(...) system call suspends execution of the calling process until a child specified by pid argument has changed state. It’s important to note that in the Linux process tree, a process can only call waitpid(...) on its immediate child. waitpid(...) serves to complete the cycle of removing a process from the process tree. The big picture, then, is that we have a living, breathing system: the child is dead, but the Grim Reaper has yet to collect its body! waitpid(...) is the scythe that reclaims the process for reuse.

On Unix systems, process 1 is always designated to the init process. In a large way, it is the “benevolent process in charge” – when a child is orphaned, the init process adopts the child and reaps it when it exits.

bool printdate(void)
{
    pid_t p = fork();
    switch(p)
    {
        case 0:
            execvp("usr/bin/date", (char **){"date", "-u", NULL});
            exit(127); // If this were "return false;" an execvp failure
                       // would result in a second parent process being run! Tricky!
        case -1:
            return false;
        default:
            if(waitpid(p, &status, 0) < 0)
                return false;
            return true;
    }
}

What can go wrong?

Neglectful parent: This is a subprocess or process ID leak. If a parent never calls waitpid(...), the process table will fill up and fork() will eventually fail because no more processes can be added.
Orphan process: This occurs when the parent process is killed before child process. In this case, waitpid(...) is not called on the child. The kernel deals with this by reassigning the orphan to be a child of the init process. The init process then reaps orphans in a function akin to while(waitpid(-1, &status, 0) >= 0) continue;
Child misbehaves: This occurs when the child is doing harmful things to the system and needs to be killed. In this case, we invoke kill(getpid(), SIGKILL): the system call takes the process ID of the child and the SIGKILL signal number that causes the process to terminate immediately.

The big Unix idea is to treat all files and devices the same. For example:

#1
fd = open("/dev/tty03", ...);  // open the keyboard – a stream device – as a file
read(fd, ...);

#2
cat /dev/tty03  /home/eggert/profile // the keyboard is identically treated as a file

If we want primitives to apply to all devices, we need to choose the right primitives! The primitives that we discuss above – open, write, and close – are all examples of orthogonal primitives. However, it is important to note that some of these Unix generalities fail. For example, the operation lseek is a read operation that operates only on random access storage devices and not stream devices. This way, we have the flexibility to operate on both forms of storage while still maintaining neutrality.

Redirecting using file descriptors

// does not work (it’s buggy) if stdin is closed!
$ date -u > /tmp/out
close (1)
int fd = open (“tmp/out”, O_WRONLY|O_CREAT|C_TRUNC)
if (fd < 0) {_exit(126) }
if (fd == 0) {
	fd = dup(fd)
	close (0);
}
if (fd < 0) { _exit(); }

// ^^^ fixed using dup2
$ date -u > /tmp/out
int fd = open (“/tmp/out”, O_WRONLY|O_CREAT|O_TRUNC)
if (fd != 1) {
	if (dup2 (fd, 1) < 0)
		_exit();
	close(fd);
}

int fd = open(“file”, O_RDWR)
if (fd >= 0) {
	unlink (“file”);
	if (read (fd, buf, bufsize)) 
	close(fd);

meaning of oflags:
	O_WRONLY-- Open for writing only
	O_RDWR-- Open for reading and writing
	O_CREAT-- If file already exists no effect; if file does not already exist, the file is created.)
	O_TRUNC-- If the file (regular) already exists and is successfully opened O_RDWR or O_WRONLY, its length is truncated to 0 and the mode of and owner are unchanged.

What is a file descriptor?

A file descriptor is an abstract indicator for accessing a file. Essentially, a file descriptor is an integer number that uniquely represents an opened file in the OS – in our context, a file descriptor is an index for an entry in a process table.

What can go wrong with file descriptors?

The process opens a bunch of files and never closes them!
The kernel limits this; adjusted using ulimit.
Read past the end of the file
The function returns the number of bytes read. In the case of a stream, if no data has been read yet, then the program waits. Otherwise, the read fails if we're in NDELAY mode.