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 9293¶

In this project, you are going to implement a substantial portion of [RFC9293]. In particular, you will be focusing on [RFC9293 § 3.10] (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 endpoint 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 endpoint 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 [RFC9293] (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 segment with information dependent on the state of the TCP variables and the send/receive buffers.

The events defined in [RFC9293 § 3.10] 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 segment arrives.
USER TIMEOUT: Not supported by chiTCP .
RETRANSMISSION TIMEOUT: A retransmission timeout (set after sending a segment) has expired, meaning that an ACK for that segment 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, [RFC9293 § 3.10] 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 segment 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 implement algorithms for Silly Window Syndrome Avoidance. This means that the sender is always allowed to send data, as long as that data falls within the effective window, and the receiver always sends the current size of the receive window (i.e., the amount of available space in the receive buffer).
You do not need to implement any TCP Congestion Control mechanisms.
You do not need to support the following flags and variables. This means you can ignore any parts of RFC 9293 that depend on checking the value of these flags/variables, or involve sending segments with these flags set, or updating these variables.
- RST, PSH, and ECE flags in the TCP header.
- Urgent Pointer field or the URG bit in the TCP header, as well as the SND.UP, RCV.UP, or SEG.UP variables.
- SND.WL1 and SND.WL2 variables.
You can ignore any references to checking the “security/compartment” of a segment or TCB.
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 by the RFC, but do not have to implement a timeout.

In other words, if the RFC specifies that you must transition to TIME_WAIT, you should do so and, after doing so, you must immediately transition to CLOSED (in a sense, we are setting the TIME_WAIT timeout to zero seconds)
You do not need to support simultaneous opens (i.e., the transition from SYN_SENT to SYN_RCVD).

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 segment 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 [RFC9293 § 3.10]. 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.
- SEGMENT_ARRIVAL: A segment has arrived through the network and needs to be processed (RFC 9293 calls this “SEGMENT ARRIVES”)
- TIMEOUT_RTX: A retransmission timeout has happened.
- TIMEOUT_PST: The persist timer has timed out.
- CLEANUP: The socket has reached the CLOSED state and is about to be freed. This event is only delivered to the CLOSED state handler, and gives you a chance to release any additional resources associated with the socket.

To implement the TCP protocol, you will need to implement the handler functions in tcp.c. However, the vast majority of your code will actually reside in the chitcpd_tcp_handle_segment function, which is called from the handler functions when a SEGMENT_ARRIVAL event is received (i.e., when a new segment arrives).

Finally, please note that most of your code will be in tcp.c. However, you will also need to modify src/chitcpd/tcp.h, which defines the tcp_data_t struct (see below), and any other files an assignment specifically tells you to modify. You should not need to modify any other files, but you will need to use a number of functions and structs defined elsewhere, which we describe below.

The `tcp_data_t` struct¶

This struct is defined in src/chitcpd/tcp.h, and 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 struct already includes the fields you will need for Assignment 1, but you are allowed (and, in Assignment 2, expected) to add your own fields to it. If you do, make sure to initialize them in tcp_data_init and free any resources they use in tcp_data_free (both in tcp.c).

The pending segment queue

tcp_segment_list_t *pending_segments;
pthread_mutex_t lock_pending_segments;
pthread_cond_t cv_pending_segments;

As TCP segments arrive through the network, the chiTCP daemon places them in the pending segment queue of the appropriate socket (you do not need to inspect the origin and destination port of the TCP segment; 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_segment_t structs (described below) in the heap. It is your responsibility to free this memory when you are done processing a segment.

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 segment.h to manipulate lists of TCP segments. For example, extracting the segment from the head of the list would be done like this:

tcp_segment_t *segment = NULL;
if(tcp_data->pending_segments)
{
    /* tcp_data->pending_segments points to the head node of the list */
    segment = tcp_data->pending_segments->segment;

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

The lock_pending_segments mutex provides thread-safe access to the queue. The cv_pending_segments condition variable is used to notify other parts of the chiTCP code that there are new segments 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 */
uint16_t SND_WND;  /* Send Window */

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

These are the TCP sequence variables as specified in [RFC9293 3.3.1].

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_RECEIVE 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 SEGMENT_ARRIVAL event happens (i.e., when the peer sends us data), you must extract the segments from the pending segment queue, extract the data from those segments, verify that the sequence numbers are correct and, if appropriate, put the data in the receive buffer.
When an APPLICATION_RECEIVE 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_segment_t` struct¶

The tcp_segment_t struct is used to store a single TCP segment:

typedef struct tcp_segment
{
    uint8_t *raw;
    size_t  length;
} tcp_segment_t;

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

Use the TCP_SEGMENT_HEADER to extract the header of the segment (with type tcphdr_t, also defined in include/chitcp/segment.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 segment that will be sent to the peer).
Use the TCP_PAYLOAD_START and TCP_PAYLOAD_LEN macros to obtain a pointer to the segment’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 [RFC9293 3.3.1]. Take into account that these macros do convert the values from network-order to host-order.
Whenever you need to create a new TCP segment, always use the chitcpd_tcp_segment_create function defined in serverinfo.h. This will initialize certain fields in the TCP header that depend on the socket associated with that TCP segment (e.g., the source/destination ports).

Example: Creating a segment without a payload¶

The following code creates a TCP segment 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 segment */
tcp_segment_t *segment = calloc(1, sizeof(tcp_segment_t));

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

/* chitcpd_tcp_segment_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 segment 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_segment_create(entry, segment, NULL, 0);

/* Get pointer to header */
header = TCP_SEGMENT_HEADER(segment);

/* 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_segment` function¶

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

tcp_segment_t segment;

/* Initialize values in segment */

chitcpd_send_tcp_segment(si, entry, &segment);

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

Take into account that chitcpd_send_tcp_segment does not free the segment (it sends a copy of the segment’s contents). The caller remains responsible for freeing it when it is no longer needed: chitcp_tcp_segment_free frees the raw contents of the segment (header and payload) and, if the tcp_segment_t itself was allocated in the heap, you must also free it.

The `chitcpd_timeout` function¶

This function is defined in src/chitcpd/serverinfo.h. This function will generate a timeout event for a given socket. Its third parameter is the type of timer that has expired (RETRANSMISSION or PERSIST, defined in src/chitcpd/tcp.h), which will generate a TIMEOUT_RTX or TIMEOUT_PST event, respectively:

chitcpd_timeout(si, entry, RETRANSMISSION);

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 include/chitcp/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 segment:

tcp_segment_t segment;

/* Initialize values in segment */

chilog(DEBUG, "Sending segment...");
chilog_tcp(DEBUG, &segment, LOG_OUTBOUND);
chitcpd_send_tcp_segment(si, entry, &segment);

The third parameter of chilog_tcp can be LOG_INBOUND or LOG_OUTBOUND to designate a segment that is being received or sent, respectively (this affects the formatting of the segment in the log). LOG_NO_DIRECTION can also be used to indicate that the segment 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 segments. 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 9293¶

Implementing the tcp.c file¶

The tcp_data_t struct¶

The tcp_segment_t struct¶

Example: Creating a segment without a payload¶

The chitcpd_update_tcp_state function¶

The chitcpd_send_tcp_segment function¶

The chitcpd_timeout function¶

The logging functions¶

Implementing the `tcp.c` file¶

The `tcp_data_t` struct¶

The `tcp_segment_t` struct¶

The `chitcpd_update_tcp_state` function¶

The `chitcpd_send_tcp_segment` function¶

The `chitcpd_timeout` function¶