By: Gezhi Liu and Rebecca Hubeny
What happens when commands, such as sort, require temporary files?
First, a file is opened in the /temp directory. Ideally, we would use a library function that is implemented on top of a system call, opentempfile, so we may be tempted to write the function as follows.
int opentempfile(void)
{
return open ("/tmp/foo",O_RDWR|O_CREAT|O_TRUNC, 0600);
}
However, if the function is called more than once, the same file will be opened multiple times. A possible solution is to instead pass a pointer to the filename into the function.
int opentempfile(char* file)
{
open (file, O_RDWR|O_CREAT|O_TRUNC, 0600);
}
The problem with this code is that we cannot be certain that the file name is not yet taken. We can use the stat function to try to bypass this issue. It will discover if the specified file is already in use.
int opentempfile(char* file)
{
struct stat st;
if (stat (file, &st) == 0)
{
errno = EEXIST;
return -1;
}
open (file, O_RDWR|O_CREAT|O_TRUNC, 0600);
}
However, there is now the issue of the race condition. A race condition is a bug that will occur if one process finishes slightly before the other. In this case, someone could make the file after the stat function check is run and before the system call opens the file. Removing the O_TRUNC flag and adding the O_EXCL flag to the open function does help improve the function though. The open system call will fail if the file exists, but ideally, we want it to just open another file.
We can try taking another approach altogether. The process ID is unique to each process, so we can incorporate it into the filename as follows:
//Let sort create filename[1000]
sprintf(filename, "/tmp/sort%d", getpid());
The issue with this implementation is that multithreaded processes have the same process ID. To fix this, we could instead get the thread ID as follows:
//Let sort create filename[1000]
sprintf(filename, "/tmp/sort%d", getthreadid());
However, we still have to figure out a file name. We could try generating a random string.
mktemp(char* filename, size_t filenamesize)
{
struct stat st;
do
{
randomstring(filename, filename_size, "/tmp/sort");
}
while(stat(filename, &st) == 0);
}
The problem with this approach is that we can't rely on auxilary functions because we come up with the same race condition problem.
A better implementation of sort would NOT require temporary files.
Instead, we could run multiple processes from the input and merge them together before the output, as shown in the figure below.
If we can connect the process to merge without a file, we don't need the temp files.
There are several advantages to using pipes.
A pipe uses two files, one to read from and one to write into, so the kernel provides two file descriptors and allocates a bounded buffer for the pipe.
If we create pipe for a single process, its entry in the process table will allocate two of its file descriptors for this task.
The bounded buffer is controlled by the two file descriptors.
fd[0] is the read end, and fd[1] is the write end.
The function below creates a pipe or returns -1 if it fails.
int pipe(int[2]);
What if we call fork() on this process and create a child process?
The child process will store the same file descriptors in its process entry.
Therefore, the parent and the child can share the same buffer in kernel memory.
This is useful because we can create two or more processes that do operations on a single buffer
(usually we have two child processes: one is the reader and the other is the writer).
Using the "tricks" listed above, there are two more advantages for pipes:
For example, consider the following command in shell:
sh:
$ tr a z | sort
sh is the parent process and it creates a pipe for command tr and command sort. It redirects tr's standard output to the standard input of sort. Let's see how it is implemented in C:
//parent process 1
Inside sh process:
pipe();
dup2(pipe[0], 0);
dup2(pipe[1], 1);
//child process 2
execvp(sort);
fork();
//grandchild process 3
fork();
execvp(tr);
waitpid();
The first system call dup2() redirects the standard input to the read end of the pipe. The second system call dup2() redirects the standard output to the write end of the pipe. The shell creates a second process (child process) and then the second process creates a third process (grandchild process) and then execute tr command. Within the third process, sort is executed.
It seems like sort executes before tr in the code. Actually, when the system calls execvp on sort, the pipe is empty. This process halts until the pipe is not empty (i.e. tr gets executed and writes into the pipe).
sort exits after tr closes the write end (i.e. tr process exists).
A graphical representation of this pipe command is shown as below:
sh
\
sort
/
tr
(a)
In our implementation, sort is the child process of sh and tr is the grandchild process of sh. There is also an alternative implementation in which sh creates two child processes:
sh
/ \
sort tr
(b)
There is another alternative implementation. But there is no way for us to wait for sort in the parent process. So this implementation will not work in our case.
sh
\
tr
/
sort
(c)
Dancing pipe problems occur because the read end and the write end of the pipe are left open in some processes. We want only one read end and one write end open to control the data flow. So, it is essential to close the unused ends in every process.
Signals provide a way to get a process's attention (usually to interrupts). Signals are essentially asynchronous notification events.
Why do we need signals?
For example, during the application runtime, the user can type control-C to kill this process. Without signals,
we need to add an infinite loop to check if control-C has arrived. So we will have something like this:
for(;;)
{
if control-C arrives
do something
}
Apparently, this is not what we want. With signals, applications need not be modified too much and can still respond to the system.
Suppose the kill syscall sends a signal to an application. It is the application's job to tell the operating system what signal handler it wants when a particular signal arrives. The signal handler is thus called when signal is delivered, and it will takeover the process. Then, the application will continue do its work.
The signal handler is of the type:
typedef void(*sighandler_t) (int);
Inside every process table entry, there is a handler table which stores the signal numbers and their corresponding handlers.
sighandler_t signal(int, sighandler_t);
This function will return the previous signal handler.
Now, suppose we need to gzip a tar file and we type this command in the shell:
$ gzip hw1.tar
While doing this, we type control-C in the shell to terminate the execution. What will happen?
There are two desired outcomes:
We do not want only part of hw1.tar compressed because gzip deletes the compressed files from the original hw1.tar. It will be hard to recover hw1.tar.
Here is an implementation of gzip operation:
1 char *file;
2 char * volatile out;
3 //out is a volatile pointer
4 //it forces compilor to cache it to a register instead of the RAM
5 int main(int argc, char **argv)
6 {
7 file = argv[1];
8 sprintf(out = malloc(strlen(file)+4),"%.gz",file);
9 int ifd = open(file, O_EXCL...); //Use O_EXCL to avoid race condition
10 int ofd = open(file, O_WRONLY|O_CREAT|O_TRUNC, 0600);
11 compress(ifd, ofd);
12 unlink(file);
13 }
There exists race condition at line 7 if another process removes the file. Then at line 12, null pointer is removed.
If control-C (or any other type of signal) arrives at line 8, we want to remove the partially compressed file. So, we can add a signal handler after out is setup. Also, if any signal arrives at line 11 during compress(), we want the process to ignore the signal so compress will finish its job. We also need to add a signal handler between line 11 and 12.
To remove the partially compressed file, we need a function to unlink out as the signal handler.
void cleanup(int sig)
{
unlink(out);
_exit(100);
}
1 char *file;
2 char * volatile out;
3 //out is a volatile pointer
4 //it forces compilor to cache it to a register instead of the RAM
5 int main(int argc, char **argv)
6 {
7 file = argv[1];
8 sprintf(out = malloc(strlen(file)+4),"%.gz",file);
9 void cleanup(int sig);
10 signal(SIGINT, cleanup);
11 signal(SIGPIPE, cleanup);
12 signal(SIGPWR, cleanup);
13 int ifd = open(file, O_EXCL...); //Use O_EXCL to avoid race condition
14 int ofd = open(file, O_WRONLY|O_CREAT|O_TRUNC, 0600);
15 compress(ifd, ofd);
16 signal(SIGINT, SIG_IGN); //Ignore any signals
17 unlink(file);
18 }