Programming Assignment Three

Goal: Using Pthreads to code a DNS name resolution engine


    • Introduction

In this assignment you will develop a multi-threaded application that resolves domain names to IP addresses, similar to the operation performed each time you access a new website in your web browser. The application is composed of two sub-systems, each with one thread pool: requesters and resolvers. The sub-systems communicate with each other using a bounded array. See Figure 1 for a visual description.



































1
    • Description

2.1    Input: Name Files

Your appliction will take as input a set of name les. Names les contain one hostname per line. Each name le should be serviced by a single requester thread from the requester thread pool. The number of requester threads may be less than or more than the number of input le.

2.2    Requester Threads

Your appliction will take as input the number of requester threads. These threads service a set of name les, each of which contains a list of domain names. Each name that is read from each of the les is placed on a shared array. If a requester thread tries to write to the array but nds that it is full, it should block until a space opens up in the array. After servicing a name le, a requester thread checks if there are any remaining name les to service. If so, it one of the remaining name les next. This process goes on until all name les have been serviced. If there are no more name les remaining, the thread writes the number of les it serviced in a new line in a le named serviced.txt in the following format:

Thread <thread id> serviced ### files.

To get the thread id of a thread on Linux systems, use gettid( ).

2.3    Resolver Threads

The second thread pool is comprised of a set of resolver threads. The resolver thread pool services the shared array by taking a name o the array and querying its IP address. After the name has been mapped to an IP address, the output is written to a line in the results.txt le in the following format:

www.google.com,74.125.224.81

If a resolver thread tries to read from the array but nds that it is empty, it should block until there is a new item in the array or all names in the input les have been serviced.

2.4    Synchronization and Deadlock

Your application should synchronize access to shared resources and avoid any deadlock or busy wait. You should use mutexes and condition variables to meet this requirement. There are at least three shared resources that must be protected: the shared array, serviced.txt and result.txt. Neither of these resources is thread-safe by default.







2
2.5    Ending the Program

Your program must end after all names in each le have been serviced by the application. This means that all the hostnames in all the input les have received a corresponding line in the output le. At the end, your program must print the total runtime on the standard output. Use gettimeofday( ) system call for this purpose.


    • What’s Included

Some les are included with this assignment for your bene t. You are not required to use these les, but they may prove helpful.

    1. util.c and util.h: These two les contain the DNS lookup utility function. This function abstracts away a lot of the complexity involved with performing a DNS lookup. The function accepts a hostname as input and generates a corresponding dot-formatted IPv4 IP address string as output.

Please consult the util.h header le for more detailed descriptions of each available function.

    2. input/names*.txt This is a set of sample name les. They follow the same format as mentioned earlier. Use them to test your program.

    3. results-ref.txt This result le is a sample output of the IPs for the hostnames from the names1.txt le.


    • Additional Speci cations

Many of the speci cations for your program are embedded in the descriptions above. This section details additional speci cations you must adhere to.

4.1    Program Arguments

Your executable program should be named \multi-lookup". The rst argument is the num-ber of requester threads, the second argument is the number of resolver threads, the third argument is name of the le in which reslover threads write the IP addresses, the fourth ar-gument is the name of the le in which requester threads write the number of les serviced. All following arguments should be interpreted as input le names containing hostnames in the aforementioned format.

An example call involving 3 requester threads, 4 resolver threads, output les result.txt and serviced.txt, and 5 input les is as follows:

multi-lookup 3 4 result.txt serviced.txt names1.txt names2.txt names3.txt names4.txt names5.txt




3
4.2    Limits

If necessary, you may impose the following limits on your program. If the user speci es input that would require the violation of an imposed limit, your program should gracefully alert the user to the limit and exit with an error.

MAX INPUT FILES: 10 Files (This is an optional upper-limit. Your program may also handle more les, or an unbounded number of les, but may not be limited to less than 10 input les.)

MAX RESOLVER THREADS: 10 Threads. This is an optional upper-limit. Your program may also handle more threads.

MAX REQUESTER THREADS: 5 Threads. This is an optional upper-limit. Your program may also handle more threads.

MAX NAME LENGTH: 1025 Characters, including null terminator (This is an optional upper-limit. Your program may handle longer names, but you may not limit the name length to less than 1025 characters.)

MAX IP LENGTH: INET6 ADDRSTRLEN (This is an optional upper-limit. Your program may handle longer IP address strings, but you may not limit the name length to less than INET6 ADDRSTRLEN characters including the null terminator.)


4.3    Error Handling

You must handle the following errors in the following manners:

Bogus Hostname: Given a hostname that can not be resolved, your program should output a blank string for the IP address, such that the output le contines the host-name, followed by a comma, followed by a line return. You should also print a message to stderr alerting the user to the bogus hostname.

Bogus Output File Path: Given a bad output le path, your program should exit and print an appropriate error to stderr.

Bogus Input File Path: Given a bad input le path, your program should print an appropriate error to stderr and move on to the next le.

All system and library calls should be checked for errors. If you encounter errors not listed above, you should print an appropriate message to stderr, and then either exit or continue, depending upon whether or not you can recover from the error gracefully.


    • External Resources

You may use the following libraries and code to complete this assignment, as well as anything you have written for this assignment:

4

Any functions listed in util.h

Any functions in the C Standard Library Standard Linux pthread functions

Standard Linux Random Number Generator functions Standard Linux le i/o functions

If you would like to use additional external libraries, you must clear it with the TA rst. You will not be allowed to use pre-existing thread-safe queue or le i/o libraries since the point of this assignment is to teach you how to make non-thread-safe resources thread-safe.


    • What You Must Provide

To receive full credit, you must submit the following items to Moodle by the due date. Please combine the les into a single zip or tar archive.

multi-lookup.c: Your program, conforming to the above requirements.

multi-lookup.h: A header le containing prototypes for any function you write as part of your program.

Make le: A make le that builds your program as the default target. It should also contain a \clean" target that will remove any les generated during the course of building and/or running your program.

README: A readme describing how to build and run your program.

performance.txt: Run your program over the ve input les provided in the input directory for six di erent scenarios: 1 requester thread and 1 resolver thread, 1 re-quester thread and 3 resolver threads, 3 requester threads and 1 resolver thread, 3 requester threads and 3 resolver threads, 5 requester threads and 5 resolver threads, and 8 requester threads and 5 resolver threads.

For each scenario, provide the following information in a le named performance.txt. Use the following format:

Number for requester thread = xxx Number for resolver thread = xxx Total run time: xxx

For each thread, thread id and the number of input  les serviced

Finally, at the end of performance.txt, provide a 1-2 paragraph explanantion of the di erences in runtimes among the six scenarios.

Any additional  les necessary to build or run your program

5
    • Extra Credit

There are a few options for receiving extra credit on this assignment. Completion of each of the following items will gain you 5 points of extra credit per item.

Multiple IP Addresses: Many hostnames return more than a single IP address. Add support for listing an arbitrary number of addresses to your program. These addresses should be printed to the output le as additional comma-separated strings after the hostname. For example:

www.google.com,74.125.224.81,76.125.232.80,75.125.211.70

You may nd it necessary to modify code in the util.h and util.c les to add this functionality. If you do this, please maintain backwards compatibility with the existing util.h functions. This is most easily done by adding new function instead of modifying the existing ones.

IPv6 Support and Testing: Add support for IPv6 IP addresses and  nd an IPv6 aware environment where you can test this support.  Since IPv6 is relatively new, nding an environment for testing this support is probably harder than adding it. You must be able to demonstrate IPv6 support during your grading session to receive credit for this item. You may  nd it necessary to modify code in util.h and util.c to complete this item. If you do so, please maintain backward compatibility with the existing code.


    • Grading

To received full credit your program must:

Meet all requirements elicited in this document.

Build with \-Wall" and \-Wextra" enabled, producing no errors or warnings. Run without leaking any memory, as measured using valgrind

To verify that you do not leak memory, TAs may use valgrind to test your program. To install valgrind, use the following command:

sudo apt-get install valgrind

And to use valgrind to monitor your program, use this command:

valgrind ./pa2main text1.txt text2.txt ...... textN.txt results.txt

Valgrind should report that you have freed all allocated memory and should not produce any additional warnings or errors.

You can write your code in any environment you like. But you have to make sure that your programs can be compiled and executed in the Virtual Machine that has been provided for this class or on the CSEL machines.

6
    • References

Refer to your textbook and class notes on the Moodle for descriptions of producer/consumer and reader/writer problems and the di erent strategies used to solve them.

The Internet is also a good resource for nding information related to solving this assign-ment.


























































7