Implementation Guide¶

As you’ll see, you are provided with a lot of code. Fortunately, you will only have to interact with a small portion of it. Most of the provided code is scaffolding for the chiTCP architecture, which will allow you to focus on implementing the TCP protocol on a single file: the tcp.c file.

This implementation guide provides a roadmap for implementing TCP, as well as a description of header files and functions that you will need to be aware of as you implement your version of TCP. As a rule of thumb, if a function is not described here, you probably should not use it in your code.

Implementing RFC 793¶

In this project, you are going to implement a substantial portion of [RFC793]. In particular, you will be focusing on [RFC793 § 3.9] (Event Processing), which provides a detailed description of how TCP should behave (whereas the preceding sections focus more on describing use cases, header specifications, example communications, etc.). The second paragraph of this section sums up pretty nicely how a TCP implementation should behave:

The activity of the TCP can be characterized as responding to events.
The events that occur can be cast into three categories:  user calls,
arriving segments, and timeouts.  This section describes the
processing the TCP does in response to each of the events.  In many
cases the processing required depends on the state of the connection.

So, we can think of TCP as a state machine where:

The states are CLOSED, LISTEN, SYN_SENT, etc.
The inputs are a series of events defined in [RFC793] (we describe these in more detail below)
The transition from one TCP state to another is based on the current state, an event, and a series of TCP variables (SND.NXT, SND.UNA, etc.)
Transitions from one TCP state to another result in actions, typically sending a TCP packet with information dependent on the state of the TCP variables and the send/receive buffers.

The events defined in [RFC793 § 3.9] are:

OPEN: chiTCP will generate this event when the application layer calls chisocket_connect.
SEND: chiTCP will generate this event when the application layer calls chisocket_send.
RECEIVE: chiTCP will generate this event when the application layer calls chisocket_recv.
CLOSE: chiTCP will generate this event when the application layer calls chisocket_close.
ABORT: Not supported by chiTCP .
STATUS: Not supported by chiTCP .
SEGMENT ARRIVES: chiTCP will generate this event when a TCP packet arrives.
USER TIMEOUT: Not supported by chiTCP .
RETRANSMISSION TIMEOUT: A retransmission timeout (set after sending a packet) has expired, meaning that an ACK for that packet has not been received.
TIME-WAIT TIMEOUT: Not supported by chiTCP .

As described in the next section, your work in chiTCP will center mostly on a file called tcp.c where you are provided with functions that handle events in given TCP states. These functions are initially mostly empty, and it is up to you to write the code that will handle each event in each state.

Of course, a TCP implementation would have to consider every possible combination of states and events. However, many of these are actually invalid combinations. For example, [RFC793 § 3.9] specifies that that if the SEND event happens in the following states:

FIN-WAIT-1 STATE
FIN-WAIT-2 STATE
CLOSING STATE
LAST-ACK STATE
TIME-WAIT STATE

Then the following action must be taken:

Return "error:  connection closing" and do not service request.

Actions like this are actually handled in the chisocket layer, and you will not have to worry about them. For example, in the above case, the chisocket_send function will set errno to ENOTCONN.

Sections Assignment 1: TCP over a Reliable Network and Assignment 2: TCP over an Unreliable Network carve out exactly what state/event combinations you will have to implement. Additionally, your implementation should take the following into account:

You do not need to support delayed acknowledgements. An acknowledgement packet is sent immediately when data is received, although you can piggyback any data in the send buffer that is waiting to be sent (but you do not need to wait for a timeout to increase the probability that you’ll be able to piggyback data on the acknowledgement).
You do not need to support the RST bit.
You do not need to support the PSH bit.
You do not need to support the Urgent Pointer field or the URG bit in the TCP header. This also means you do not need to support the SND.UP, RCV.UP, or SEG.UP variables.
You do not need to support the SND.WL1 and SND.WL2 variables and can ignore any checks that involve those variables.
You do not need to support TCP’s “security/compartment” features, which means you can assume that SEG.PRC and TCB.PRC always have valid and correct values.
You do not need to support the checksum field of the TCP header.
You do not need to support TCP options.
You do not need to support the TIME_WAIT timeout. You should still update the TCP state to TIME_WAIT when required, but do not have to implement a timeout. Instead, you should immediately transition to CLOSED from the TIME_WAIT state.
You do not need to support simultaneous opens (i.e., the transition from SYN_SENT to SYN_RCVD).

Whenever something is unclear in RFC 793, please make sure you also take a look at [RFC1122 § 4.2], which clarifies a number of aspects of RFC 793, and even provides a few corrections.

Implementing the `tcp.c` file¶

Since TCP is essentially a state machine, chiTCP ’s implementation boils down to having a handler function for each of the TCP states (CLOSED, LISTEN, SYN_RCVD, etc.), all contained in the src/chitcpd/tcp.c file. If an event happens (e.g., a packet arrives) while the connection is in a specific state (e.g., ESTABLISHED), then the handler function for that state is called, along with information about the event that just happened. You will only have to worry about writing the code inside the handler function; the rest of the scaffolding (the socket library, the actual dispatching of events to the state machine, etc.) is already provided for you.

Each handler function has the following prototype:

int chitcpd_tcp_state_handle_STATENAME(serverinfo_t *si,
                                       chisocketentry_t *entry,
                                       tcp_event_type_t event);

The parameters to the function are:

si is a pointer to a struct with the chiTCP daemon’s runtime information (e.g., the socket table, etc.). You should not need to access or modify any of the data in that struct, but you will need the si pointer to call certain auxiliary functions.
entry is a pointer to the socket entry for the connection that is being handled. The socket entry contains the actual TCP data (variables, buffers, etc.), which can be accessed like this:
```
tcp_data_t *tcp_data = &entry->socket_state.active.tcp_data;
```
The contents of the tcp_data_t struct are described below.

entry also contains the value of the TCP state (SYN_SENT, ESTABLISHED, etc.) in the tcp_state variable:
```
tcp_state_t tcp_state = entry->tcp_state;
```
Since each handler function corresponds to a specific state, you ordinarily will not need to access this variable. However, if you write an auxiliary function that needs to check a socket’s current state, you can obtain the state via the tcp_state variable. Take into account that you should never modify that variable directly. You should only modify it using the chitcpd_update_tcp_state function described below.

Other than the TCP data and the TCP state, you should not access or modify any other information in entry.
event is the event that is being handled. The list of possible events corresponds roughly to the ones specified in [RFC793 3.9]. They are:
- APPLICATION_CONNECT: Application has called chisocket_connect() and a three-way handshake must be initiated.
- APPLICATION_SEND: Application has called chisocket_send(). The socket layer (which is already implemented for you) already takes care of placing the data in the socket’s TCP send buffer. This event is a notification that there may be new data in the send buffer, which should be sent if possible.
- APPLICATION_RECEIVE: Application has called chisocket_recv(). The socket layer already takes care of extracting the data from the socket’s TCP receive buffer. This event is a notification that there may now be additional space available in the receive buffer, which would require updating the socket’s receive window (and the advertised window).
- APPLICATION_CLOSE: Application has called chisocket_close() and a connection tear-down should be initiated once all outstanding data in the send buffer has been sent.
- PACKET_ARRIVAL: A packet has arrived through the network and needs to be processed (RFC 793 calls this “SEGMENT ARRIVES”)
- TIMEOUT_RTX: A retransmission timeout has happened.
- TIMEOUT_PST: The persist timer has timed out.

To implement the TCP protocol, you will need to implement the handler functions in tcp.c. You should not need to modify any other file. However, you will need to use a number of functions and structs defined elsewhere.

The `tcp_data_t` struct¶

This struct contains all the TCP data for a given socket. It is also useful to think of this struct as the “Transmission Control Block” for a given connection.

The pending packet queue

tcp_packet_list_t *pending_packets;
pthread_mutex_t lock_pending_packets;
pthread_cond_t cv_pending_packets;

As TCP packets arrive through the network, the chiTCP daemon places them in the pending packet queue of the appropriate socket (you do not need to inspect the origin and destination port of the TCP packet; this is taken care of for you). The queue is implemented as a doubly-linked list where the head of the list represents the front of the queue and the tail of the list represents the back of the queue. The list nodes contain pointers to tcp_packet_t structs (described below) in the heap. It is your responsibility to free this memory when you are done processing a packet.

The list is implemented using utlist, which is already included in the chiTCP code. While you can use the utlist macros directly, we also provide some helper functions in packet.h to manipulate lists of TCP packets. For example, extracting the packet from the head of the list would be done like this:

tcp_packet_t *packet = NULL
if(tcp_data->pending_packets)
{
    /* tcp_data->pending_packets points to the head node of the list */
    packet = tcp_data->pending_packets->packet;

    /* This removes the list node at the head of the list */
    chitcp_packet_list_pop_head(&tcp_data->pending_packets);
}

The lock_pending_packets mutex provides thread-safe access to the queue. The cv_pending_packets condition variable is used to notify other parts of the chiTCP code that there are new packets in the queue; you should not wait or signal this condition variable.

The TCP variables

/* Send sequence variables */
uint32_t ISS;      /* Initial send sequence number */
uint32_t SND_UNA;  /* First byte sent but not acknowledged */
uint32_t SND_NXT;  /* Next sendable byte */
uint32_t SND_WND;  /* Send Window */

/* Receive sequence variables */
uint32_t IRS;      /* Initial receive sequence number */
uint32_t RCV_NXT;  /* Next byte expected */
uint32_t RCV_WND;  /* Receive Window */

These are the TCP sequence variables as specified in [RFC793 3.2].

The TCP buffers

circular_buffer_t send;
circular_buffer_t recv;

These are the TCP send and receive buffers for this socket. The circular_buffer_t type is defined in the include/chitcp/buffer.h and src/libchitcp/buffer.c files.

The management of these buffers is already partially implemented:

The chisocket_send() function places data in the send buffer and generates an APPLICATION_SEND event.
The chisocket_recv() function extracts data from the receive buffer and generates an APPLICATION_RECV event.

In other words, you do not need to implement the above functionality; it is already implemented for you. On the other hand, you will be responsible for the following:

When an APPLICATION_SEND event happens, you must check the send buffer to see if there is any data ready to send, and you must send it out if possible (i.e., if allowed by the send window).
When a PACKET_ARRIVAL event happens (i.e., when the peer sends us data), you must extract the packets from the pending packet queue, extract the data from those packets, verify that the sequence numbers are correct and, if appropriate, put the data in the receive buffer.
When an APPLICATION_RECV event happens, you do not need to modify the receive buffer in any way, but you do need to check whether the size of the receive window should be adjusted.

The `tcp_packet_t` struct¶

The tcp_packet_t struct is used to store a single TCP packet:

typedef struct tcp_packet
{
    uint8_t *raw;
    size_t  length;
} tcp_packet_t;

This struct simply contains a pointer to the packet in the heap, along with its total length (including the TCP header). You will rarely have to work with the TCP packet directly at the bit level. Instead, the include/chitcp/packet.h header defines a number of functions, macros, and structs that you can use to more easily work with TCP packets. More specifically:

Use the TCP_PACKET_HEADER to extract the header of the packet (with type tcphdr_t, also defined in include/chitcp/packet.h, which provides convenient access to all the header fields. Take into account that all the values in the header are in network-order: you will need to convert them to host-order before using using (and viceversa when creating a packet that will be sent to the peer).
Use the TCP_PAYLOAD_START and TCP_PAYLOAD_LEN macros to obtain a pointer to the packet’s payload and its length, respectively.
Use the SEG_SEQ, SEG_ACK, SEG_LEN, SEG_WND, SEG_UP macros to access the SEG.* variables defined in [RFC793 3.2]. Take into account that these macros do convert the values from network-order to host-order.
Whenever you need to create a new TCP packet, always use the chitcpd_tcp_packet_create function defined in serverinfo.h. This will initialize certain fields in the TCP header that depend on the socket associated with that TCP packet (e.g., the source/destination ports). CAREFUL: There is a similarly-named function in packet.h called chitcp_tcp_packet_create; you should not use that function.

Example: Creating a packet without a payload¶

The following code creates a TCP packet with only the ACK flag set (and no other flags set), and with sequence number 1000, acknowledgement number 530, and window size 4096:

/* Allocate memory for the packet */
tcp_packet_t *packet = calloc(1, sizeof(tcp_packet_t));

/* Used to easily access header fields */
tcphdr_t *header;

/* chitcpd_tcp_packet_create will initialize certain fields of the
 * header that you do not need to worry about, like the ports.
 *
 * Note how we pass the 'entry' parameter that is passed to the
 * TCP state handler functions (and which points to the socket entry
 * for the connection this packet will be sent on)
 *
 * Since there is no payload, we pass NULL as the payload parameter,
 * and specify a payload length of zero */
chitcpd_tcp_packet_create(entry, packet, NULL, 0);

/* Get pointer to header */
header = TCP_PACKET_HEADER(packet);

/* Fill in header fields */
header->seq = chitcp_htonl(1000);
header->ack_seq = chitcp_htonl(530);
header->win = chitcp_htons(4096);
header->ack = 1

The `chitcpd_update_tcp_state` function¶

This function is defined in src/chitcpd/serverinfo.h. Whenever you need to change the TCP state, you must use this function. For example:

chitcpd_update_tcp_state(si, entry, ESTABLISHED);

The si and entry parameters are the same ones that are passed to the TCP handler function.

The `chitcpd_send_tcp_packet` function¶

This function is defined in src/chitcpd/connection.h. Whenever you need to send a TCP packet to the socket’s peer, you must use this function. For example:

tcp_packet_t packet;

/* Initialize values in packet */

chitcpd_send_tcp_packet(si, entry, &packet);

The si and entry parameters are the same ones that are passed to the TCP handler function.

The `chitcpd_timeout` function¶

This function is defined in src/chitcpd/serverinfo.h. This function will generate a TIMEOUT event for a given socket:

chitcpd_timeout(si, entry);

The si and entry parameters are the same ones that are passed to the TCP handler function.

The logging functions¶

The chiTCP daemon prints out detailed information to standard output using a series of logging functions declared in src/include/log.h. We encourage you to use these logging functions instead of using printf directly. More specifically, you should use the printf-style chilog() function to print messages:

chilog(WARNING, "Asked send buffer for %i bytes, but got %i.", nbytes, tosend);

And the chilog_tcp() function to dump the contents of a TCP packet:

tcp_packet_t packet;

/* Initialize values in packet */

chilog(DEBUG, "Sending packet...");
chilog_tcp(DEBUG, packet, LOG_OUTBOUND);
chitcpd_send_tcp_packet(si, entry, &packet);

The third parameter of chilog_tcp can be LOG_INBOUND or LOG_OUTBOUND to designate a packet that is being received or sent, respectively (this affects the formatting of the packet in the log). LOG_NO_DIRECTION can also be used to indicate that the packet is neither inbound nor outbound.

In both functions, the first parameter is used to specify the log level:

CRITICAL: Used for critical errors for which the only solution is to exit the program.
ERROR: Used for non-critical errors, which may allow the program to continue running, but a specific part of it to fail (e.g., an individual socket).
WARNING: Used to indicate unexpected situation which, while not technically an error, could cause one.
MINIMAL: Compact information about important events in a socket, as well as one-line summaries of received/sent packets. This log level is described in more detail in Testing your Implementation, and you should not use it yourself.
INFO: Used to print general information about the state of the program.
DEBUG: Used to print detailed information about the state of the program.
TRACE: Used to print low-level information, such as function entry/exit points, dumps of entire data structures, etc.

The level of logging is controlled by the -v argument when running chitcpd:

No -v argument: Print only CRITICAL and ERROR messages.
-v: Also print WARNING and MINIMAL messages.
-vv: Also print INFO messages.
-vvv: Also print DEBUG messages.
-vvvv: Also print TRACE messages.

Implementation Guide¶

Implementing RFC 793¶

Implementing the tcp.c file¶

The tcp_data_t struct¶

The tcp_packet_t struct¶

Example: Creating a packet without a payload¶

The chitcpd_update_tcp_state function¶

The chitcpd_send_tcp_packet function¶

The chitcpd_timeout function¶

The logging functions¶

Implementing the `tcp.c` file¶

The `tcp_data_t` struct¶

The `tcp_packet_t` struct¶

The `chitcpd_update_tcp_state` function¶

The `chitcpd_send_tcp_packet` function¶

The `chitcpd_timeout` function¶