Project 3: Multithreaded servers

Background information

DHCP is based on an older protocol called BOOTP. Both protocols use a data structure that was defined for exchanging network information. The data structure is described in RFC 2131, which you will need to reference throughout this project (see Figure 1). The options portion of the data structure is variable-sized, and the possible values are described in RFC 2132. Note that, with the exception of the End option, all options follow a specific structure:

• Code - one byte to indicate which option is used
• Len - one byte to specify the length of the option value
• Value - variable-length field containing the option value

As an example, consider the following two options and their interpretation (all numbers are in hexadecimal):

The options that must be set vary based on which kind of message is being sent. These specifications are in Table 3 and Table 5 of RFC 2131. For this project, you are required to support the options that are identified as "MUST" or "MUST NOT" in those tables. (Note that some depend on which state the client is in. This will be discussed in the client implementation and you should ignore these until then.)

The basic sequence of messages in DHCP consist of the following (in order):

1. Client sends DHCP Discover: This is a BOOTREQUEST message with information about the client's hardware and a randomly chosen xid to identify the request.
2. Server sends DHCP Offer: This is a BOOTREPLY message with the client's hardware and xid values, along with a suggested IP address (yiaddr) and other information.
3. Client sends DHCP Request: This is a BOOTREQUEST message with the client's hardware and xid values, along with the requested IP address and server identifier.
4. Server sends DHCP ACK: This is a BOOTREPLY message with the client's hardware and xid values, along with the assigned IP address (yiaddr) and other information.

You will also need to support three other types of messages that can occur:

• Client sends DHCP Decline if the address offered in the DHCP Offer is already in use.
• Server sends DHCP NAK if the address requested in the DHCP Request is already in use.
• Client sends DHCP Release to voluntarily unassign the IP address.

Testing infrastructure modification

This project focuses on building a server rather than a client. As such, the standard make test procedure does not work adequately for debugging. Specifically, for much of the project, your code is tested indirectly based on what your server sends to the client rather than what it produces as output. This can cause misleading debugging practices. You will need to adjust your testing and debugging practices based on the phases described below.

Implementation requirements

As with previous projects, this project will be built incrementally. Your first task involves responding to a single client message, then shutting down. Next, you will implement the server responses for the full four-message sequence, assigning IP addresses for up to four clients. You'll then add support for releasing an IP address. Finally, you'll add a minimal multithreaded structure to emulate the behavior of a more realistic server.

Phase 1: Responding to single messages (partial credit)

For this first phase, you will focus on receiving and responding to a single message sent from the client. The client will send either a DHCPDISCOVER or a DHCPREQUEST message. Your task is to interpret these messages and print a human-readable version of the data, then construct the DHCPOFFER or DHCPACK message in response.

To get started, you need to complete the msg_t definition in src/dhcp.h. The fields should be based on Section 2 of RFC 2131 and should use appropriate types, such as uint32_t for 32-bit values (not int) and struct in_addr for IPv4 addresses.

You are generally free to structure your code as you see fit, but we recommend using the provided files as described below. Doing so will allow you to make more module use of the code for later phases of the project:

src/dhcp.c, src/dhcp.h

Use these files to define the msg_t struct to hold the fixed-size BOOTP fields (i.e., not the options) and to work with this struct.

src/format.c

Use this file to control the printing of the fields for both BOOTP and DHCP.

src/server.c

Use this file to define the control flow for your server, including any network setup and message processing.

In this phase only, your server will produce output based on the data received from the client. See the files in tests/expected for the expected formatting.

The dhcp.h file contains important constants that you should reference, including the supported hardware types and lengths. You only need to support the values listed in that file. When printing the hardware type, your output should match the names given in the ARP Parameters. All IP addresses are IPv4 and should be formatted in dotted decimal notation.

The chaddr field tends to be a source of headaches for many students, as they try to find a way to print the field all at once with a single printf(). You cannot do this because these hardware addresses can have a variety of lengths, including odd sizes like 3 bytes. Instead, use a for-loop, relying on the fact that the length of the chaddr value is based on the hardware address length field (hlen).

Testing your formatting

To test your implementation of this phase, run make test in the p3-dhcps directory. In addition to compiling your code, this command will do the following:

• Compile and run tests/testsuite based on the tests/public.c unit tests. Initially, there are no unit tests. You should add tests here to test your implementation.
• Run tests/integration.sh to test your dhcps output based on the arguments in tests/itests.include. This will also run valgrind to test for memory leaks.

Phase 2: A DHCP server (C requirements)

In this phase, you'll extend your server by implementing the full four-message sequence for DHCP. That is, you will first receive a DHCPDISCOVER and reply with a DHCPOFFER that includes a unique IP address. The client will then send a DHCPREQUEST. If the IP address and server ID match, you will respond with a DHCPACK. However, if there is a mismatch for either, you will send a DHCPNAK.

You'll need to support up to 4 clients, assigning the IP addresses 192.168.1.1, 192.168.1.2, etc. If you receive a 5th DHCPDISCOVER, you should reply with a DHCPNAK.

You will distinguish this version of your server from the version in Phase 1 based on the XID of the messages received. In Phase 1, all XID values were set to 0. If the value is not 0, then you will need to handle the full DHCP protocol message exchange.

The provided test client program issues messages based on files stored in tests/data. These files contain information about how to generate messages in a predictable manner. These files contain lines such as the following:

1 1 42 010102020303:DHCPDISCOVER [htype=ETH, xid=42, chaddr=010102020303]
3 1 42 010102020303 192.168.1.0 192.168.1.1:DHCPREQUEST [htype=ETH, xid=42, chaddr=010102020303, server=192.168.1.0, reqid=192.168.1.1]

Each line starts by indicating the message type (1=DHCPDISCOVER on the first line 3=DHCPREQUEST on the second), then the hardware type (1=ETH for both), and the XID value. The lines also show the the hardware address (010102020303 is chaddr). The DHCPREQUEST message must also include a server ID (192.168.1.0) and requested IP address (192.168.1.1). Note that the information after the ":" is just to provide a human-readable interpretation and is not actually used.

Phase 3: Tracking and releasing assignments (B requirements)

For this phase, you'll need to build a mechanism for tracking the IP addresses that have been assigned to a given chaddr. You'll need to do this for a couple of reasons. First, messages might be interleaved. For example, assume you originally encounter the following sequence:

Client 1 (xid=15, chaddr=1234) sends DHCPDISCOVER
Server offers 192.168.1.1 to Client 1
Client 1 sends DHCPREQUEST for 192.168.1.1
Server sends ACK to Client 1
Client 2 (xid=99, chaddr=5566) sends DHCPDISCOVER
Server offers 192.168.1.2 to Client 2
...

You now have to support the following sequence:

Client 1 (xid=15, chaddr=1234) sends DHCPDISCOVER
Server offers 192.168.1.1 to Client 1
Client 2 (xid=99, chaddr=5566) sends DHCPDISCOVER
Server offers 192.168.1.2 to Client 2
Client 1 sends DHCPREQUEST for 192.168.1.1
Server sends ACK to Client 1
...

The second reason for tracking offers is to add support for DHCPRELEASE messages. These are sent by clients voluntarily to allow an IP address to be re-assigned. When you receive a DHCPRELEASE, you do not send a reply to the client.

It is important to note one key feature that goes along with DHCPRELEASE actions: servers try to assign the same IP address to subsequent DHCPDISCOVER messages from the same chaddr. That is, if a client previously used 192.168.1.3, sent a DHCPRELEASE to release its DHCP lease, then sends a subsequent DHCPDISCOVER, the server should again offer 192.168.1.3 unless it has been assigned to a different client.

There are many ways you could implement this tracking and removal of records. A simple way would be to create an array of four records, each of which contains the chaddr and a "tombstone" record, which are commonly used in data structures like hash tables. When you use a tombstone, you just mark the record as no longer in use but leave the data otherwise intact.

Phase 4: Once more with threads (A requirements)

In this final phase, you'll emulate part of the behavior of a multithreaded DHCP server. Instead of processing DHCPDISCOVER requests right away, your main thread (the one calling recvfrom()) will launch a new thread, then go back to waiting on another incoming message. Your main thread will get a total of 8 requests, then join all 8 threads before shutting down. To distinguish this version from the earlier phases, you will need to take a -t command-line option to indicate it is the multithreaded version.

In the helper threads, you only need to work on constructing a DHCPOFFER message. For simplicity, you can either use the same IP address for all (192.168.1.1) or return them in incrementing order (192.168.1.1, 192.168.1.2, 192.168.1.3, etc.). For additional simplicity, you do not need to implement the full protocol here. Each thread should exit after sending the DHCPOFFER.

However, to show that you are handling these requests in a separate thread, you will not return them in the order received. Instead, in the helper thread, you will call usleep() on the XID value to sleep for a certain number of microseconds before responding. The effect of this is that your responses should be received by the client in a sorted ascending order based on the XID values.

Testing notes

Given the values used for the XID values, the output of this test case (there is only one for this phase) should be deterministic. However, it is possible that a request/respone gets flipped because of fluke timing caused by a lot of processes on stu or other random factors. If this happens, you will need to manually inspect the output to convince yourself that your code is working correctly. When grading this phase, we will also run your code manually and inspect the implementation to determine if it is correct.