In this lab, you will learn the following topics and practice C programming skills.

1. Using signal handlers, signal() and sigaction()
2. Scheduling alarm signals with alarm()
3. Using siginfo_t when handling SIGCHLD

Run the following command

~aviv/bin/ic221-up

Change into the lab directory

cd ~/ic221/lab/09

All the material you need to complete the lab can be found in the lab directory. All material you will submit, you should place within the lab directory. Throughout this lab, we refer to the lab directory, which you should interpret as the above path.

For this lab, all ubmission should be placed in the following folder:

~/ic221/lab/09

You are not required to provide your own Makefiles for this lab. One is provided for you.

In the top level of the lab directory, you will find a README file. You must fill out the README file with your name and alpha. Please include a short summary of each of the tasks and any other information you want to provide to the instructor.

You are provided a test script which prints pass/fail information for a set of tests for your programs. Note that passing all the tests does not mean you will receive a perfect score: other tests will be performed on your submission. To run the test script, execute test.sh from the lab directory.

./test.sh

You can comment out individual tests while working on different parts of the lab. Open up the test script and place comments at the bottom where appropriate.

In the collision directory, you'll find a program called hash (which you can compile by typing make). This program is good for testing, and will hash a password provided on the command line.

$ ./hash navy
57c5f2

The result is the hash, which is a sequence is in hex, 6 hex digits, or 3 bytes. Assuming you only had the hash, the challenge is finding the password, e.g., "navy" or another 4 letter word that hashes to the same value, a so called collision.

The routine for cracking a hash involves finding all the colliding ASCII printable passwords that hash to the same value. Even with a small password and small hash, this can take a long time to do, so we are going to divide the problem up amongst a set of child/worker processes.

To divide the work, each child will be assigned a first letter of a password to start with. The child will then exhaust the space of possible passwords starting with that letter. If a collision is found, it will signal the parent to print the password out. Once the child/worker has finished searching the space of passwords that begin with that first letter, it will stop and wait for the parent to send it another letter to try. The parent, meanwhile, will monitor the states of the children, and keep track of which first letters have been searched and which have not. Once all the first letters of passwords are exhausted, the parent will kill the children and exit itself.

There will be two forms of inter-process communication. First, each child will share a pipe with the parent. The pipe will be used to communicate the hash to be cracked as well as which first letter to start the cracking attempt on.

The second form of inter-process communication will be in the form of signaling. You will need to establish a signal handler in the parent for SIGUSR1 as the children will send that signal when it has found a password and written that password to the pipe. In the handler, the parent should read the password and print it out. In this way, it will never be the case that the parent gets blocked reading on the pipe when there is nothing to read.

Unfortunately, the signal() system call is not powerful enough to make this work because you will need to know which of the children sent the signal so that the parent reads from the correct pipe. To gain that information, you have to use the more powerful sigaction() system call to establish the handler. Read the manual page carefully for this, and you should consider using the SA_INFO and SA_RESTART flags to make this work. For example:

struct sigaction act;
 act.sa_sigaction = handler; //the handler to use for the signal
 act.sa_flags = SA_RESTART | SA_SIGINFO; //the flags
 sigaction(SIGUSR1, &act, NULL); //establish a signal handler for SIGUSR1

The handler function for the parent can be quite simple because the SIGUSR1 signal is only delivered when the child finds a hash collision. The only thing for the parent to do is to (a) determine which child sent the signal and (b) read from the appropriate pipe to print the password.

Unlike signal(), the prototype of the function expected for the signal handler by sigaction (if using the sa_sigaction option) is slight different.

void handler(int signum, siginfo_t * info, void * context);

The signum is the signal that was delivered such that the handler was invoked. The info is a pointer to a structure that contains information about how the signal was delivered, including which process sent the signal, info->si_pid. The context is used to manage the asynchronous execution stack, but you can ignore this variable

There also exists a second form of signaling. When the child has exhausted the search space for the first letter, it will raise(SIGSTOP) which will change the state of the child process. This functionality, and The parent can wait on such a state change, and when it happens, either write the next start letter to the pipe for that child then wake the child with SIGCONT, or kill the child if there are no more first letters to try with SIGKILL.

To get child state change information for stopped, you will need to use waitpid() system call with the WUNTRACED option.

cpid = waitpid(0,&status,WUNTRACED); // returns the pid of a child if
                                     // it was terminated OR stopped

Additionally, you will need to check the exist status to ensure that the state change of the child occurred due to being stopped and not because the parent killed it.

WIFSTOPPED(status) //returns true state change of child was STOPPED

If it was stopped, the search space for the first letter was exhausted, but it may also have been killed by the parent if there is no more work, generally, to do.

aviv@saddleback: collisions $ ./hash navy
57c5f2
aviv@saddleback: collisions $ ./collide $(./hash navy)
![X{
K==$
RjwY
navy
xp>\
ygTn
aviv@saddleback: collisions $ ./hash "RjwY"
57c5f2

aviv@saddleback: collisions $ time ./collide $(./hash navy) > /dev/null

real  0m7.763s
user  0m30.656s
sys   0m0.000s