tcp from first principles

motivation

TCP, for all intents and purposes, is a pretty simple protocol to use. In high school, I was able to write a small game that used TCP to communicate between a client and a server, even though I had no idea what I was doing. After revisiting networking for an internship, I realized that we have a lot to think about when communicating; namely:

• 1 Routing: How do we actually route to the correct IP? What does a packet even look like?
• 2 Correctness: How do we ensure that all of our packets arrive in order and correctly?
• 3 Connection: How do we avoid overwhelming our NICs?
• 4 Lifecycle: How does a connection eventually end up in user space if the kernel takes it in?
• 5 Alternatives: What are some other alternatives to TCP (namely RDMA)? How do they work?

I won't answer these questions in order, but I'll try to motivate them and take you on a rabbit hole to show you how fucking awesome these communication protocols really are!

1. routing

You've probably learned in your computer networking class that in order to establish a TCP connection, we must perform what is known as a 3-way handshake. Here's a little diagram as a refresher:

In order to establish the connection, the client sends a SYN (short for synchronize) packet to the server carrying an Initial Sequence Number (ISN). My initial high school implementation always used the same values for this SYN. However, this is really bad because predictable ISNs allow people to hijack your connection. The modern Linux kernel uses the following equation to derive an ISN. You can check out the code in net/core/secure_seq.c.

ISN = M + SipHash(net_secret, source address, destination address, source port, destination port)

Here, M is a monotonically increasing counter calculated via seq_scale(). SipHash produces a per-connection pseudorandom offset keyed by a secret (and other metadata) to prevent spoofing. Anyway, let's examine how the Linux kernel derives the clock scaling in net/core/secure_seq.c:

static u32 seq_scale(u32 seq)
{
	/*
	 *	As close as possible to RFC 793, which 
	 *	suggests using a 250 kHz clock.
	 *	Further reading shows this assumes 2 Mb/s networks.
	 *	For 10 Mb/s Ethernet, a 1 MHz clock is appropriate.
	 *	For 10 Gb/s Ethernet, a 1 GHz clock should be ok, but
	 *	we also need to limit the resolution so that the u32 seq
	 *	overlaps less than one time per MSL (2 minutes).
	 *	Choosing a clock of 64 ns period is OK. (period of 274 s) 
	 */
	return seq + (ktime_to_ns(ktime_get_real()) >> 6); 
}

After the client sends a SYN with ISN, the server replies with a SYN-ACK carrying its own secure ISN and acknowledging the client's sequence (ACK = client_ISN + 1). Finally, the client sends an ACK = server_ISN + 1 to complete the 3-way handshake.

In order to understand what exactly gets communicated, we should look at the structure of a TCP request. At the core of TCP is its 20-byte header (excluding options, which are variable in size). Every field must be strictly aligned and encoded using big-endian order. Here is the official Linux kernel tcp header:

#include <linux/types.h>

struct tcphdr {
	__be16	source;    /* [1] Source port (big-endian) */
	__be16	dest;      /* Destination port (big-endian) */
	__be32	seq;       /* [2] Sequence number */
	__be32	ack_seq;   /* Acknowledgment number */
#if defined(__LITTLE_ENDIAN_BITFIELD) [3]
	__u16	res1:4,    /* reserved bits */
		doff:4,    /* TCP header length in 32-bit words */
		fin:1,     /* [4] flag bits start here */
		syn:1,
		rst:1,
		psh:1,
		ack:1,
		urg:1,
		ece:1,
		cwr:1;
#elif defined(__BIG_ENDIAN_BITFIELD)
	__u16	doff:4,
		res1:4,
		cwr:1,
		ece:1,
		urg:1,
		ack:1,
		psh:1,
		rst:1,
		syn:1,
		fin:1;
#else
#error	"Adjust your <asm/byteorder.h> defines"
#endif
	__be16	window;    /* [5] Flow control window size */
	__be16	check;     /* Checksum */
	__be16	urg_ptr;   /* Urgent pointer */
    /* 
        Options start here; they include PAWS (Protection Against Wrapped Sequence numbers).
        No, I'm not making that acronym up :3 (it addresses the thing about frequency that
        we talked about earlier)
    */
};

To be honest, I think there are a lot of questions that I've left unanswered (you can suggest some more and I'll update the page). But, we should think: we have the source port and destination port, but how do we actually get the packet to the destination that we want? What about retries? How is that handled? What about MTU (maximum transmission unit)? How do we split the packet up such that the source and destination are able to both handle it using their network interface cards? And how about regular connections? We've learned about how a handshake works in relative rigor, but how does a stable connecion work in this model?

2. layer encapsulation

I think it might be best to go down the OSI model stack. In case you aren't really familiar, a brief run down is as follows: We have Transport (TCP) → Network (IP) → Data Link (Ethernet / Wi-Fi). There are layers above these, but we'll go into them later...

TCP describes the type of transmission protocol and safety guarantees that we have. IP describes how we will route the packet. The data link layer describes the format that the data will be physically transmitted in (ie. Ethernet or IEEE 802.11 WiFi). Lastly, we have the physical layer, which is mystical and EEs tend to deal in that wizardry. Now, let's look at a diagram of the actual "wire frame" that is being sent and start diving into things!

layer 3: the network layer (ipv4 & ipv6)

Stepping directly below TCP brings us to the Internet Protocol (IP). While TCP manages end-to-end reliability between ports, IP is responsible for global routing across routers, packet sizing, and link fragmentation. You might have heard about IPv4 and IPv6 before. IPv4 is an old standard that uses a 32-bit address, while IPv6 is the new kid on the block that uses a 128-bit address. 11. We actually skipped 64-bit because standard IPv6 addressing splits the address into a 64-bit network prefix (which IDs which network the address belongs to) and a 64-bit interface identifier (which IDs a specific host within that network); we also reserve a bunch of IPs so we can't touch a portion of the 128 bits. BTW, here's an IP census map from 2013 to show you what the internet IPs look like

1. ipv4

IPv4 uses a variable 20-60 byte header with 32-bit addresses. Let's walk through the official definition:

#include <linux/types.h>

struct iphdr {
#if defined(__LITTLE_ENDIAN_BITFIELD)
	__u8	ihl:4,         /* Internet Header Len (in 4-byte words) */
		version:4;     /* IP version (4 for IPv4) */
#elif defined (__BIG_ENDIAN_BITFIELD)
	__u8	version:4,
		ihl:4;
#else
#error	"Please fix <asm/byteorder.h>"
#endif
	__u8	tos;           /* [1] Type of Service: DSCP (6 bits) + ECN (2 bits) */
	__be16	tot_len;       /* length of IP Header + TCP Header + Payload */
	__be16	id;            /* Packet ID for fragmentation tracking */
	__be16	frag_off;      /* [2] Fragmentation flags (DF, MF) + offset */
	__u8	ttl;           /* [3] Time to Live (hop limit) */
	__u8	protocol;      /* [4] Transport protocol (6 = TCP, 17 = UDP) */
	__sum16	check;         /* 16-bit One's Complement Header Checksum */
	__be32	saddr;         /* Source IP address */
	__be32	daddr;         /* Destination IP address */
	/* The options start here. */
};

2. ipv6

IPv6 is the more modern cousin of IPv4. It has a fixed 40-byte base header and again, it has 128 bits for addressing. It completely eliminates the L3 checksum (relieving intermediate routers from having to recalculate checksums on every hop). Let's go over the definition:

#include <linux/types.h>
#include <linux/in6.h>

struct ipv6hdr {
#if defined(__LITTLE_ENDIAN_BITFIELD)
	__u8	priority:4,    /* Traffic Class (equivalent to tos in IPv4) */
		version:4;     /* IP version  */
#elif defined(__BIG_ENDIAN_BITFIELD)
	__u8    version:4,
		priority:4;
#else
#error	"Please fix <asm/byteorder.h>"
#endif
	__u8    flow_lbl[3];   /* [1] 20-bit Flow Label for router ECMP hashing */
	__be16  payload_len;   /* Length of payload AFTER 40B header */
	__u8    nexthdr;       /* [2] Transport protocol (6 = TCP) or extension header */
	__u8    hop_limit;     /* Hop limit (equivalent to IPv4 TTL) */

	struct in6_addr	saddr; /* Source IPv6 address (128-bits) */
	struct in6_addr daddr; /* Destination IPv6 address */
};

Okay, I think it would be helpful to try to recap what we've gained from just looking at the fields in these structs. 22. Remember that we haven't even discussed the fact that this layer is parametric over the different transport layers. I haven't talked to you about UDP, etc. Perhaps a good mental model of UDP is that we kind of just send a packet once and just forget about it. The retry logic of TCP isn't baked into UDP. You can read this thread for a more conceptual understanding of UDP! First, let's think about the DF bit. So, when we think about different protocols, it doesn't make sense that the maximum transmission unit (MTU) would be the same across all of them. If we made different hardware only able to transmit a equal maximum size, surely we wouldn't be taking advantage of our hardware, right? This is especially important in datacenters, where we can play with really expensive network interface cards (NICs)!

Another thing: routers can help break packets up. The DF bit is a signal for the router to ping the sender. This can be for a variety of reasons, namely the fact that breaking up packets is pretty expensive work. Ideally, we would be sending in the minimum MTU that is bottlenecking our service anyway. Additionally, if a singular broken-up packet is dropped, our service will have to resend the entire original packet anyway.

We should also note the lack of a domain name (ie. google.com) as a field. We only deal with IPs in these parts. This is because we can send queries about IPs to a domain name service (DNS). Your router may have a DNS (and your OS just takes care of resolution via our router) or you might just be sending to an IP like 8.8.8.8 (which is google's public DNS). That's how we get IP addresses from your browser! 33. You can imagine that it's possible to have an attacker as a DNS; you can go down this rabbit hole if you want!

We should also think about how internet is a limited resource. I'm sure you've dealt with connection issues, right? Well, it seems to be reasonable that you would rather want GPS than Discord loading (or some other non-life-saving utility, who knows). As such, we have the ToS field in our packets. Plus, note the length field! This is how the receiver knows how much data we're loading in!

To conclude this section, let's just keep a running list of questions that we still need to answer! How do we ensure that a packet stays as an indivisible unit? What does the lifecycle of a TCP connection look like? How does ethernet and WiFi differ? How do retries *really* work? I'm starting to realize that there's just a lot to talk about... :(, and I haven't even asked all of the questions that I have! Let's just go along with ethernet and WiFi next.

layer 2: the data link layer

Remember, below IP sits the Data Link Layer, which determines how frames physically hop across your local NIC, whether through a physical copper wire (Ethernet) or over radio frequency waves (Wi-Fi).

1. ethernet

On wired connections, Ethernet (IEEE 802.3) is easy because cables are reliable point-to-point links. This is the header as follows:

#define ETH_ALEN	6		/* Bytes in one ethernet addr	 */
#define ETH_HLEN	14		/* Total bytes in header.	 */

struct ethhdr {
	unsigned char	h_dest[ETH_ALEN];	/* [1] Destination MAC address */
	unsigned char	h_source[ETH_ALEN];	/* Source MAC address */
	__be16		h_proto;		/* [3] Packet type ID field (EtherType) */
} __attribute__((packed));

2. WiFi (ieee 802.11)

WiFi is broadcasted on shared airwaves, so packets can be vulnerable to interference. As a result, we have much more complexity :(.

struct ieee80211_hdr {
	__le16 frame_control;  /* [1] Subtype, ToDS, FromDS, Retry flags, Power Mgmt */
	__le16 duration_id;    /* [2] Duration value for NAV virtual carrier sensing */
	u8 addr1[ETH_ALEN];    /* [3] Receiver MAC Address */
	u8 addr2[ETH_ALEN];    /* Transmitter MAC Address */
	u8 addr3[ETH_ALEN];    /* Filter / final destination MAC */
	__le16 seq_ctrl;       /* Sequence & Fragment number for wireless retries */
	u8 addr4[ETH_ALEN];    /* Optional 4th address for wireless mesh/wireless distribution system (WDS) bridging */
} __attribute__((packed));

You might have noticed our wire frame diagram earlier showed a 4-byte FCS (Frame Check Sequence) at the tail of the packet, but these structs seem to only encode the head. Don't worry, the FCS isn't hard to understand! It's just a CRC-32 checksum 44. Here is a short wikipedia article about it if you're interested. Here is a more in-depth stackoverflow discussion about CRC32 more specifically that's handled entirely by your NIC. When transmitting, the NIC hardware computes and appends the 4-byte FCS as the frame leaves the physical transceiver. When receiving, the NIC validates the CRC-32 on the fly; if electrical noise or a faulty cable corrupted any bits, the NIC drops the damaged frame directly in hardware before the Linux kernel or CPU even wakes up. If the frame is valid, the NIC strips off the FCS before transferring the packet to system memory.

3. the lifecycle of a connection

It's probably most helpful to think of a TCP connection as a contract. Under a stable connection, we can think of it as a finite state machine, with two endpoints interacting with each other in a standardized way. Let's try to take a look at what this looks like in terms of code.

1. the standard blocking server

A standard TCP server creates an endpoint, binds it to a port, moves the socket into a passive listening state, and blocks on accept() until a completed 3-way handshake is pulled from the kernel's Accept Queue:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <arpa/inet.h>
#include <sys/socket.h>

#define PORT 8080
#define BUFFER_SIZE 1024

int main() {
    int server_fd, client_fd;
    struct sockaddr_in server_addr = {0};
    struct sockaddr_in client_addr = {0};
    socklen_t client_len = sizeof(client_addr);
    char buffer[BUFFER_SIZE] = {0};

    /*  
        Create TCP socket; remember a socket is simply an abstraction that 
        tells the OS to send/receive data and demux it based on port + ip.
        AF_INET tells us the protocol is IPv4 + the following < 0 is
        if we encounter an error doing this process (this pattern continues
        for the rest of the code). SOCK_STREAM specifies that this is TCP
    */
    if ((server_fd = socket(AF_INET, SOCK_STREAM, 0)) < 0) { 1
        perror("socket failed");
        exit(EXIT_FAILURE);
    }

    // allow rapid restart without 2MSL TIME_WAIT bind error
    int opt = 1;
    setsockopt(server_fd, SOL_SOCKET, SO_REUSEADDR, &opt, sizeof(opt));

    // configure server address and bind to port 8080 on all local network interfaces
    server_addr.sin_family = AF_INET;
    server_addr.sin_addr.s_addr = INADDR_ANY; // Listen on 0.0.0.0 (all interfaces)
    server_addr.sin_port = htons(PORT);        // Convert port to Network Byte Order (Big Endian)

    // binds the file description with the ip address and port combination
    if (bind(server_fd, (struct sockaddr *)&server_addr, sizeof(server_addr)) < 0) {
        perror("bind failed");
        close(server_fd);
        exit(EXIT_FAILURE);
    }

    /*  
        [2] mark socket as passive and provision kernel SYN & Accept queues
        also sets connection backlog limit (SOMAXCONN)
    */
    if (listen(server_fd, SOMAXCONN) < 0) { 2
        perror("listen failed");
        close(server_fd);
        exit(EXIT_FAILURE);
    }
    printf("Server listening on port %d...\n", PORT);

    /* 
        Accept: blocks until a completed 3-way handshake is popped from the Accept Queue.
        The kernel writes the connecting client's IP and ephemeral port INTO client_addr
    */
    if ((client_fd = accept(server_fd, (struct sockaddr *)&client_addr, &client_len)) < 0) { 3
        perror("accept failed");
        close(server_fd);
        exit(EXIT_FAILURE);
    }
    printf("Client connected from %s:%d\n", 
           inet_ntoa(client_addr.sin_addr), ntohs(client_addr.sin_port));

    // read client data (triggers copy_to_user from kernel sk_receive_queue)
    ssize_t bytes_read = recv(client_fd, buffer, sizeof(buffer) - 1, 0);
    if (bytes_read > 0) {
        buffer[bytes_read] = '\0';
        // now we could pass messages!! yippeeee!!!
        printf("Received: %s\n", buffer);

        const char *response = "Hello from server!";
        send(client_fd, response, strlen(response), 0);
    } else if (bytes_read == 0) {
        printf("Client closed connection (EOF / FIN received).\n");
    } else {
        perror("recv failed");
    }

    // close active client socket (sends FIN packet to start 4-way teardown)
    close(client_fd);
    close(server_fd);
    return 0;
}

"But, wait, Jason!" you might interject. "How does the kernel demux packets to the right sockets? And can multiple processes share a socket?" And I'd tell you, "You know, that's quite impressive that you know that the kernel sends packets to sockets, rather than processes." Essentially, the kernel has some sort of table called the "established hash table" and it takes a 5-tuple of (protocol, source IP, source port, destination IP, destination port) to route packets to the proper socket.

A more interesting question, however, is "when a connection completes, who gets it?" It's possible that you called fork(), which spawns a child process with the same file descriptor table in that process. Historically, the kernel used to wake up all processes that blocked on accept, and they'd race to accept the socket lock. This is pretty wasteful, as you can tell so we have a couple of different solutions:

• WQ_FLAG_EXCLUSIVE: Linux just wakes one for blocking accept(), rather than all of them
• EPOLLEXCLUSIVE: for worker threads monitoring a socket via epoll (we'll go into epoll later)
• SO_REUSEPORT: we can setsockopt() with the flag SO_REUSEPORT so each process has a distinct listening socket and distinct accept queue. We pretty much take a hash of the packet's tuple to choose the specific socket that the packets will route to from now on

Remember, this is specifically for accept(). Also to clarify, it is generally NOT a good idea it's perfect valid for multiple threads to share one connected socket (same tuple). You should be able to reason about why this is the case. Good luck!

2. the standard client

On the client side, the application specifies the server's remote IP and port, and connect() initiates the active 3-way handshake:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <arpa/inet.h>
#include <sys/socket.h>

#define SERVER_IP "127.0.0.1"
#define PORT 8080
#define BUFFER_SIZE 1024

int main() {
    int sock_fd;
    struct sockaddr_in server_addr = {0};
    char buffer[BUFFER_SIZE] = {0};

    /* Create client TCP socket */
    if ((sock_fd = socket(AF_INET, SOCK_STREAM, 0)) < 0) {
        perror("socket creation failed");
        exit(EXIT_FAILURE);
    }

    server_addr.sin_family = AF_INET;
    server_addr.sin_port = htons(PORT);

    // Convert text IPv4 address to binary network byte order
    if (inet_pton(AF_INET, SERVER_IP, &server_addr.sin_addr) <= 0) {
        perror("invalid server address");
        close(sock_fd);
        exit(EXIT_FAILURE);
    }

    /* 
        [1] Connect: initiates the 3-Way Handshake (SYN -> SYN-ACK -> ACK).
        The client does not call bind(); the OS kernel automatically assigns
        a random ephemeral source port (range 49152-65535) and the local interface IP.
    */
    printf("Connecting to server at %s:%d...\n", SERVER_IP, PORT);
    if (connect(sock_fd, (struct sockaddr *)&server_addr, sizeof(server_addr)) < 0) {
        perror("connect failed");
        close(sock_fd);
        exit(EXIT_FAILURE);
    }
    printf("Connected! (State: SYN_SENT -> ESTABLISHED) yayyy\n");

    /* Transmit payload into kernel sk_write_queue */
    const char *msg = "Hello from client!";
    send(sock_fd, msg, strlen(msg), 0);

    /* Wait for server reply */
    ssize_t bytes_read = recv(sock_fd, buffer, sizeof(buffer) - 1, 0);
    if (bytes_read > 0) {
        buffer[bytes_read] = '\0';
        printf("Server replied: %s\n", buffer);
    } else if (bytes_read == 0) {
        printf("Server closed connection.\n");
    } else {
        perror("recv failed");
    }

    /* Active close initiates 4-Way Teardown (sends FIN, enters TIME_WAIT) */
    close(sock_fd);
    printf("Connection closed.\n");
    return 0;
}

Standard blocking sockets require a dedicated thread or process per connection, which hits a scaling wall at thousands of concurrent clients. To handle high concurrency, we configure sockets to non-blocking mode with O_NONBLOCK, allowing an event loop like epoll to multiplex thousands of active streams on a single CPU core. As a note, epoll is simply a kernel abstraction that allows us to watch many file descriptors at same time (this is a feature that allows us to scale up to serve many thousands of requests).

3. the 3-way handshake & the two kernel queues

Now that we've gone over the boilerplate code, we can finally focus more on the low-level systems that make this all possible. 55. genuine crazy ahh sidenote, a TCP connection can be represented via a finite state machine (FSM). To be honest, I don't think seeing it as an FSM is particularly illuminating, but i'll leave this as an exercise for an interested reader. Here's a diagram for the interested reader if you want to dive deeper into this. By the time accept() stops blocking and we get to call it, we've already completed the 3-way handshake. Let's try to break through this abstraction into something that we can actually understand.

When we call listen(), we create two separate queues in the kernel (the SYN Queue hash table and the Accept Queue FIFO linked list). The socket state becomes TCP_LISTEN, and we become ready to accept handshakes. When we call connect(), we kick off the handshake. The client sends a SYN, and a thread blocks in userspace to wait for the server's reply. Finally, the server's kernel receives the SYN, creates a struct and puts it in the SYN Queue, and we follow through with the SYN-ACK + ACK. connect() stops blocking on the client side and when the last ACK lands in the server, the kernel promotes the connection into the Accept Queue with state TCP_ESTABLISHED. 66. try to think about why we would want the ability to have a queue for accept(), if we can only accept() one thing per socket

An interesting implementation tidbit here is that a full TCP socket in Linux is quite expensive. As such, two queues is better than one because we can have a lighter weight allocation for the first queue. We only need to negotiate options like window scale, maximum segment size, selective acknowledgment (yes, the acronym is SACK), etc. We also have the exponential retries if the SYN-ACK fails 77. I thought I mentioned this earlier, but I guess I never talked about how TCP actually implements its retry logic. When a segment isn't acknowledged in time, TCP retransmits it. We have the concept of exponential backoff, where it will retry in 1s, 2s, 4s, etc. (usually up to 5 times). This is part of the concept of retransmission timeout (RTO), which is a whole rabbit hole in it of itself. You can read this thread for more (but there's also more interesting things here because we take into account system jitter, etc. (like woah wtf??)). But that's separate from maximum segment lifetime (MSL). MSL is essentially the maximum amount of time a segment can be wandering the network (set to 60s). After 2xMSL, you can be confident every packet that was ever part of the old connection has either been delivered or has died, and the IP + port can safely be used (remember PAWS!) .

what happens when the queues overflow? (the edge cases)

What happens under extreme load when one of these queues fills up? This is where networking gets really interesting:

• 1 SYN Queue: If an attacker floods a server with millions of spoofed SYN packets without ever sending the last ACK, the SYN Queue would fill up. However, if net.ipv4.tcp_syncookies = 1, when the SYN queue is full, the server instead encodes the connection metadata into the ISN using a secret key:
  

  ISN = [ Top 5 bits: Timestamp ] + [ 3 bits: MSS Index ] + [ 24 bits: SipHash(net_secret, source address, destination address, source port, destination port)]

  When a legitimate client sends the last ACK (which contains ISN + 1), the server subtracts 1, validates the cryptographic hash and timestamp, decodes the MSS, and creates the full socket on the fly with zero prior state
• 2 Accept Queue By default when net.ipv4.tcp_abort_on_overflow = 0, the Linux kernel drops the last ACK, and doesn't enter it into the accept queue (because we can always resend the SYN-ACK if we haven't heard back in time). If that value was 1, the kernel sends an RST packet to kill the connection immediately.

4. reliable byte streams

Now that we've covered more of the systems side of starting a connection, lets try to go deeper into the lifecycle of a TCP request. One cool thing is that the ISN is actually useful outside of the 3-way handshake. During a series of recv() and send(), the ISN maintains an invariant throughout the connection.

If we receive an ACK with ISN = K, that means that sender has received and verified all bytes from the original ISN up to K - 1.88. Keep in mind that TCP is a two-way connection, and that both the server and the client have their own respective ISNs that they do the accounting with. We don't use the same ISN. You might be rather astute and realize that at the start of a connection (when we sent a SYN), we replied with ISN + 1. That's because any packet that changes the state of a connection (this includes the FIN flag that we haven't seen before) needs to reply with ISN + 1. Note that this doesn't include ACK, which would imply that we would send an infinite recursive ACK storm otherwise!

Another particularly astute observation is that an ISN is a 32-bit value. As such, in a datacenter where transfer speeds are upwards of 100 GB/s, we can easier encounter wrap around here. PAWS (as we covered earlier) helps protect us in this case again because a wrap should occur when timestamps are monotonically increasing.

5. byte accounting, hole detection, & out-of-order reordering

Following this discussion about the ISNs, it seems pretty reasonable that the Linux kernel machines a sequence state machine for reassembly machinery, etc. After all, in a network, reorders can just happen. The Linux kernel maintains two distinct sequence counters for the socket (of course, we have a sender and receiver pipeline).

                 snd_una                snd_nxt             snd_una + snd_wnd
                    │                      │                        │
  ══════════════════╪══════════════════════╪════════════════════════╪════════════► (Byte Stream)
   ACKed by Peer    │   In-Flight / Sent   │  Can Send Immediately  │ Cannot Send Yet
   (Freed from mem) │   (Not yet ACKed)    │  (Within Window)       │ (Window Exceeded)
                    └───────┬──────────────┘
                            ▼
               FlightSize = snd_nxt - snd_una

               copied_seq               rcv_nxt               rcv_nxt + rcv_wnd
                    │                      │                        │
  ══════════════════╪══════════════════════╪════════════════════════╪════════════► (Byte Stream)
   Read by App via  │  In Kernel Queue     │ Advertised Free Window │ Dropped if Sent
   read() / recv()  │  (sk_receive_queue)  │ (Advertised rwnd)      │ (Exceeds Buffer)

Here are some notes:

• snd_una (Send Unacknowleddged) tracks the oldest byte that hasn't been acknowledged yet. When an ACK arrives, it advances snd_una, and the kernel frees those acknowledged sk_buff bytes from the socket retransmission queue
• snd_nxt (Send Next) is the next sequence number the sender will assign to newly transmitted data
• snd_wnd (Send Window) is the number of bytes the sender is currently allowed to have outstanding (sent but unacknowledged), which is typically the minimum of rcv_wnd (Receive Window; which we know from the Window field in ACK segments) and cwnd (which we will go into later on).
• rcv_nxt (Receive Next) is the exact next contiguous byte sequence number the receiver expects. The ACK should contain rcv_nxt (because remember the ISN = K invariant)
• copied_seq is the sequence offset up to which the user application has actually drained bytes from the kernel via recv() / read().

Now that we have a more principled understanding of how the kernel keeps track of bytes, we should look at the common case of out-of-order packets.

how the kernel handles out-of-order packets (tcp_ofo_queue)

Here's a short diagram (props to Gemini Flash 3.7) to show you what happens to out-of-order packets

Incoming Packet (tcp_data_queue)
       │
       ▼
Is seq == tp->rcv_nxt?
 ├── YES (In-Order):
 │     ├── 1. Append directly to sk->sk_receive_queue
 │     ├── 2. Advance: tp->rcv_nxt += skb->len
 │     └── 3. Check tp->out_of_order_queue: Can we drain cached future packets?
 │
 └── NO (Out-of-Order / Hole Detected):
       ├── 1. Cannot deliver to application yet (TCP guarantees strict in-order stream!)
       ├── 2. Insert sk_buff into augmented Red-Black Tree: tp->out_of_order_queue
       ├── 3. Fire Duplicate ACK (ack_seq = tp->rcv_nxt)
       └── 4. Append SACK option block: [start_seq, end_seq]

We talked about SACK earlier, but I'll go into it with more detail here because it seems necessary. The receiver might generate a ACK with the option enabled. The sender receives this ACK, which contains information that you don't have a certain range, but you have some bytes afterward, and therefore you don't need to resend the entire portion (only a select portion of the bytes). And once we have a contiguous sequence in sk_receive_queue, the kernel invokes sk->sk_data_ready(), waking up the userspace thread blocked on epoll_wait() or recv() to consume the contiguous data stream.

By the way, it's important to note that at every out-of-order arrival necessitates an immediate ACK from the receiver (it ACKs for rcv_nxt). Upon receiving 3 Duplicate ACKs for the same ack_seq, the sender (if they're running Linux) concludes the segment was lost (not just reordered) and retransmits it immediately, which allows us to skip the RTO transmission (which make take a lot longer).

packet trace diagram

Let's look at a diagram generated by our beloved Gemini Flash to see a toy example of some packets! Hopefully, it is slightly illuminating.

SENDER (Client)                                                  RECEIVER (Server)
  │                                                                     │
  │ ─── [Pkt 1] seq=1001..2000 (1000B) ───────────────────────────────► │ ──► rcv_nxt = 2001 (Appended to sk_receive_queue)
  │ ◄── ACK = 2001 ──────────────────────────────────────────────────── │
  │                                                                     │
  │ ─── [Pkt 2] seq=2001..3000 (1000B) ────► 💥 (DROPPED BY ROUTER!)    │
  │ ─── [Pkt 3] seq=3001..4000 (1000B) ───────────────────────────────► │ ──► Hole at 2001! Buffered in RB-Tree
  │ ◄── Dup-ACK 1: ack=2001, SACK=[3001..4001] ──────────────────────── │
  │                                                                     │
  │ ─── [Pkt 4] seq=4001..5000 (1000B) ───────────────────────────────► │ ──► Buffered in RB-Tree
  │ ◄── Dup-ACK 2: ack=2001, SACK=[3001..5001] ──────────────────────── │
  │                                                                     │
  │ ─── [Pkt 5] seq=5001..6000 (1000B) ───────────────────────────────► │ ──► Buffered in RB-Tree
  │ ◄── Dup-ACK 3: ack=2001, SACK=[3001..6001] ──────────────────────── │
  │                                                                     │
  ▼ [3 Duplicate ACKs Received! Trigger Fast Retransmit]                │
  │ ─── [FAST RETRANSMIT Pkt 2] seq=2001..3000 (1000B) ───────────────► │ ──► Missing Hole Arrived!
  │                                                                     │     1. Pkt 2 added to receive queue
  │                                                                     │     2. RB-tree drained: Pkts 3,4,5 spliced
  │                                                                     │     3. rcv_nxt advances 2001 -> 6001!
  │                                                                     │     4. sk_data_ready() wakes application
  │ ◄── Cumulative ACK = 6001 (All 5,000 bytes safe in order!) ──────── │
  ▼
[snd_una advances to 6001: All sent buffers freed from sk_write_queue]

6. closing a connection

Because TCP is full-duplex, terminating a connection requires closing both independent streams. In practice, application developers have three distinct ways to close a TCP connection, each with very different kernel behaviors:

• 1 close(fd) decrements the socket's file descriptor refcount. When refcount hits 0 (yay for garbage collection), it closes both the read and write directions, transmits a FIN segment, and places the active closer into FIN_WAIT_1. However, if there is still data to be read, and you call close(), the kernel sends a hard RST signal, which causes the other end to see an ECONNRESET (connection reset by peer) error.
• 2 shutdown(fd, SHUT_WR) transmits a FIN segment that tells the peer it doesn't want to send any data, but they can still send data to you (half-open ahh socket).
• 3 we can set SO_LINGER and l_linger (which determines how many seconds to linger for) for our socket options, which forces non-graceful termination + the kernel discards buffers + sends RST immediately (no 2xMSL wait time here; MSL was covered in a sidenote btw).

the 4-way fin handshake

When a graceful close is initiated, both peers negotiate the full 4-step teardown:

ACTIVE CLOSER (calls close() or shutdown())             PASSIVE CLOSER (receives FIN)
  │                                                               │
  │ ─── [1] FIN (seq=u) ────────────────────────────────────────► │ ──► [CLOSE_WAIT]
  ▼ [FIN_WAIT_1]                                                  │     (Application read() returns 0 / EOF)
  │ ◄── [2] ACK (ack=u+1) ─────────────────────────────────────── │
  ▼ [FIN_WAIT_2]                                                  │
  │                                                               ▼ Application calls close()
  │ ◄── [3] FIN (seq=w, ack=u+1) ──────────────────────────────── │ ──► [LAST_ACK]
  │                                                               │
  ▼ [TIME_WAIT] (starts 2MSL timer = 60s)                         │
  │ ─── [4] ACK (ack=w+1) ──────────────────────────────────────► │ ──► [CLOSED]
  │                                                               
  ▼ (after 2 * MSL = 60s)
[CLOSED]

4. how memory travels through the linux kernel

This is an added section meant to address a curiosity I had because I realized that at the end of the day, I didn't actually understand how the kernel received memory and moved it to the right socket. This is the most arcane shit ever, and I think this is honestly the question that I wanted to answer the most while exploring RDMA and stuff.

tx (transmit) path

• 1 When your program calls write(sockfd, buf, len), the CPU transitions into kernel space via a syscall trap to execute tcp_sendmsg().99. This transition is more expensive than it used to be because pre-2018, the kernel's entire address space was mapped into every process's page tables all the time; it was invisible to userspace only because the page table entries were marked supervisor-only, and the CPU was trusted to enforce that bit on every access. Meltdown (one of the two most famous speculative execution vulnerabilities) allowed a read to a "forbidden" kernel address and yadadada (I'm not the best person to explain how this works, so I'll link you this).
  
  Anyway, now we have KPTI (Kernel Page Table Isolation), which stops mapping the kernel page tables into userspace's page tables at all (aside from a tiny trampoline needed to even get into the kernel). That means this exact syscall trap now has to flush (and subsequently rewalk) non-global entries in the TLB upon entrance and exit of kernelspace. Search up CR3, PCID for more! The kernel allocates an sk_buff (socket buffer) struct and copies the payload from userspace into kernel memory. The size of said ipv4 struct is bounded by the values hidden in /proc/sys/net/ipv4/tcp_wmem.
• 2 tcp_write_xmit() breaks large buffers into chunks bounded by the path MSS (e.g. 1460 bytes) and checks whether the send window (min(cwnd, rwnd)) has available capacity so we can actually send something.
• 3 skb_push() prepends the TCP header, then ip_queue_xmit() prepends the IP header, and the Ethernet layer attaches the MAC addresses without re-allocating memory (we just adjust some pointers in place and shuffle things around).
• 4 The device driver (ndo_start_xmit) registers the physical memory address of the sk_buff via dma_map_single()1010. This is really fucky, but bear with me for a second. sk_buff lives in kernel memory allocated via kmalloc(). Kernel memory is never placed on swap/reclaim LRU lists (kswapd only walks anon / page-cache pages). As such, we can safely hand its address straight to the NIC without worrying that the memory is going to swapped to disk (which is bad because the NIC is supposed to DMA straight into RAM) and writes a memory descriptor into the NIC's TX Ring Buffer.
• 5 The CPU writes to a Memory-Mapped I/O (MMIO) PCIe register on the NIC, which tells the NIC's onboard DMA controller to pull the bytes across the PCIe bus and converts them into physical signals onto the wire.

Honestly, I'm quite frustrated that I couldn't explain this in a way such that there was very little boilerplate. If you feel like this explanation is unsatisfying, and you would want to learn way more, I suggest you check out this blog here. Enough moping about, let's learn about the receive path!

the rx (receive) path

• 1 Incoming frames hit the NIC, which DMAs the raw bytes directly into a pre-allocated host DRAM buffer1111. lowkey, i'm kinda confused on this. don't quote me on this, but we usually have a little headroom ontop of the MTU to make things easier to allocate (ie. 1500 -> 2048) and we have a slab allocator in the kernel for this (or I guess it's called a SLUB) called kmalloc-2048. For jumbo frames, the NIC has some scatter-gather hardware to just write the frame to multiple smaller buffers., referenced by an entry in the RX ring. This entry is a small, hardware/driver-specific descriptor struct (e.g. struct ixgbe_adv_rx_desc). 1212. The buffer has to exist before the frame shows up: the driver DMA-maps it with dma_map_single() / dma_map_page(), which hands back a bus/IOMMU address (because virtual memory is an abstraction the kernel makes). Btw, an RX queue's ring is per core. Receive Side Scaling (RSS) hashes the 5-tuple in hardware (usually Toeplitz) and steers each flow into one of many parallel RX queues, each pinned to a distinct CPU core via /proc/irq/N/smp_affinity. This allows single-producer, single-consumer for the buffers + other good stuff.
• 2 The NIC triggers an MSI-X hardware interrupt (this is some insane fucking ball knowledge). Because handling an interrupt per packet at 100 Gbps would melt the CPU (interrupt storms), the kernel interrupt handler quickly disables interrupts and schedules a NET_RX_SOFTIRQ. NAPI (New API) polls the ring buffer in batches using napi_gro_receive(), which also opportunistically coalesces several back-to-back segments of the same flow into one larger sk_buff before they ever reach the IP stack (Generic Receive Offload), cutting per-packet processing overhead. NAPI also adds the metadata needed for the socket buffer. Each poll call is bounded by a budget (netdev_budget / the NAPI weight); if a core can't drain its ring within that budget, the softirq work gets handed off to the ksoftirqd kernel thread instead of hogging the CPU indefinitely. Only once the ring is actually drained does the driver re-enable hardware interrupts.
• 3 In tcp_v4_rcv(), the kernel hashes the packet's 4-tuple to find the associated socket. And blah blah blah sk_receive_queue and tcp_ofo_queue which should be review for you.
• 4 The kernel calls sk->sk_data_ready(), which awakens threads blocked on a wait. The application calls read(), and tcp_recvmsg() executes copy_to_user() to copy bytes into user memory, and frees the sk_buff. 1313. "Frees" is not necessarily true because we do reference counting here. skb_clone() lets a copy of the packet ride the retransmission queue while the "original" gets handed up the stack, or lets a raw socket / tcpdump via AF_PACKET observe a frame without interfering with normal delivery. Notice the copy between user space and kernel space here.

sidenotes getting too long: softirq sidenote

This was supposed to be a sidenote, but ended up as a separate section. tcp_v4_rcv() runs in softirq (software interrupt queue) context, which is borrowed CPU time squeezed in between whatever else the kernel is doing. This is kinda messed up.

This is because inside tcp_v4_rcv(), there is logic that branches whether or not a userspace thread is currently inside a syscall on the socket. If it is, the software interrupt queue cannot touch the socket, so there's a dedicated socket backlog that the kernel process simply pushes onto to defer work so we don't just waste a CPU core waiting. Otherwise, (that is if there is no socket lock in place), we can simply process the packet and continue on the softirq. After both branches, we signal that the socket is ready. The socket backlog (if there is one) is drained as soon as release_sock() is called (which is pretty much anytime we have a syscall that touches a socket in our TCP path).

You should keep in mind that we've covered a lot. But that's because there was a lot to TCP: multiple context switches, SoftIRQs, socket buffer locks, and two full memory copies (writer has userspace to kernel and reader has kernel to userspace). There are things we can do to eliminate these copies before we use the real bazooka (RDMA with its kernel bypass).

tcp-native zero-copy techniques

• 1 send(fd, buf, len, MSG_ZEROCOPY) skips a copy in favor of the kernel pinning your page (as we discussed in a previous side note), attaching them directly as an skb_frag so the NIC can DMA it from the process's own memory. However, you need to check the socket's error queue later on to be sure that you can safely free that page. This is not worth it for small [O(10kB)] messages.
• 2 sendfile() / splice() is for reading from disk and writing to a socket (like when you're serving static content). This sidesteps a userspace hop by moving all of the bytes entirely into kernel space.
• 3 TCP_ZEROCOPY_RECEIVE is a getsockopt() flag. This makes the kernel remap actual pages backing the received socket buffers into your process's address space, so "receiving" becomes a page-table operation instead of a byte-for-byte copy. This needs a driver whose socket buffers are already backed by real page-aligned memory and not just linear buffers from a raw slab. It also requires packets be unique within page. Again, this only really pays off for large transfers.
• 4 io_uring cuts the syscall. Sends and receives get submitted into a ring buffer mmap'd between you and the kernel. The kernel drains it and posts results into a second ring, so many operations can go out behind a single io_uring_enter() call. You can run it in SQPOLL mode and a dedicated kernel thread polls the submission ring itself, so a steady-state sender can issue effectively zero syscalls.
  
  It also layers on top of zero-copy: on send, IORING_OP_SEND_ZC gets you the same pinned-page zero-copy send, but io_uring_register_buffers() lets you pin a fixed set of buffers once up front instead of paying the pinning cost on every single call. On receive, IORING_REGISTER_ZCRX_IFQ registers a pool of your own memory directly with the NIC driver, so incoming DMA writes land straight into already-mapped userspace pages, skipping the page remap that we needed.