The stack · TCP (sysn 003)

A conversation as a value

TCP, as the rest of the stack is: functions over buffers and memory the caller lends, bytes in and bytes out, with no clock, no tasks and no source of randomness. The stack keeps each conversation's sequence numbers, windows and one timer; the caller keeps the bytes. It is enough for sysk's network shell, a person on the host reaching the machine, and for dialling out: passive and active open, several segments in flight, retransmission, both ways of closing, and the checks a stack facing a hostile network needs.

The caller keeps the bytes

What the caller has written stays with the caller until the peer acknowledges it. Every call that may send is handed a view of those bytes, from the first one not yet acknowledged; the stack cuts its segment out of the view, at the end of what is in flight for new data, or at the start to send again. When an acknowledgement arrives, the stack says how many bytes it covers, (acked 5), and the caller lets that many go from the front. So the stack holds no packets, and a retransmission is a send like any other. uIP had the idea first, with a callback and a promise to "send the exact same data"; here the promise is a check: a view shorter than what is in flight sends nothing, and the payload of every segment is proven to lie within the view.

The stack keeps una, the first byte not acknowledged, and out, how many sequence numbers are in flight after it, as a number. The next to send is una + out. Acknowledging is then subtraction, and the proofs need no reasoning about numbers that wrap at 2³²: an ACK frees a = ack − una bytes when 0 < a ≤ out, read as a difference of words, and anything else is answered or dropped as RFC 5961 says.

Its states

RFC 9293's states, without LISTEN: a SYN to an announced port is answered with a cookie and nothing kept, and the ACK that returns it opens a conversation in syn-rcvd and moves it on at once (Strangers, below); a free conversation is closed. Every call that changes a conversation ensures moves of its state before and after: it stays, goes to closed, or takes one edge of the diagram. One segment takes two edges in one case only, an ACK and a FIN together in syn-rcvd. Pick a recording to see the states it passed through.

A session, segment by segment

The recordings, drawn as TCP draws them: sequence numbers relative to each side's first, so a SYN is 0 and the first byte 1. On the left, what the caller did and what the stack said; a frame lost on purpose ends short. These are real sessions with slirp, replayed by make test.

Time is the caller's

The stack reads no clock. Every call that may need the time is given it, in nanoseconds, and tcp-due says when the stack must next be called for a conversation; the caller calls tcp-tick then. One deadline a conversation does every timer's work, its role given by the state: send again what is not acknowledged, probe a window that has shut, end time-wait, or give up a fin-wait-2 the peer has left silent.

The first sequence number

RFC 6528: a count of 4 µs from the time given, plus a keyed hash of the four that name the conversation, so that no one off the path can guess it. The hash is SipHash-2-4, sysc's (sysc/crypto/sip.sysp), under a 16-byte key the caller lends with the memory, once; the stack still has no source of randomness. The four are hashed as the SYN or SYN-ACK carries them: the stack writes our address, theirs and the two ports into the frame it is about to send, and hashes those 12 bytes in place, so nothing is copied. A conversation we open takes its port the same way, from the hash with our port 0.

Strangers

A conversation costs a slot, and there are at most 64. Since sysn 008 a stranger cannot take one by sending SYNs, nor keep one by going silent, nor fill the table with closed ones:

The cookie is the SYN-ACK's sequence number, 32 bits. A cookie is good for the count of 64 s it was made in and the next, so for 64 to 128 s; the MSS it can say is one of Linux's four, the largest no larger than the peer's offer, and 536 for an offer below it. Linux makes cookies only when its queue of half-open conversations overflows; here every passive open uses them, so there is no such queue and no second path. The price, as RFC 4987 says, is that a SYN-ACK is never sent again: if the ACK that returns the cookie is lost, the peer believes it is connected and the stack knows nothing of it until the peer's next segment, whose ACK still carries the cookie. A shell that speaks first waits, then, for its peer's first keystroke.

A blind attacker

Someone who can guess a conversation's ports can send it resets and SYNs. RFC 5961 makes them guess the sequence number exactly, too:

Each is a case in the hostile test. A segment for no conversation draws a reset, unless it is a reset, or returns a good cookie; a returned cookie when every conversation is taken, none of them in time-wait, is dropped, full: the peer sends it again with its next segment.

In the state's memory

TCP's part follows the neighbours and counts in the memory the caller lends net-new: eight announced ports, each with the window its conversations start with, the key, the throttle, then as many conversations as the memory holds, 120 bytes each, up to 64. (net-size k) is the memory for k conversations; with none it is what it was before TCP, and every SYN draws a reset. A conversation is read with con-load only when its bytes make a valid conversation (a state, times and windows in range); anything else is a free one. So nothing is assumed about the memory, and con.sysp's functions are proven over a value, never over bytes.

What netd does

sysk runs the stack in netd, which serves it as Plan 9's /net/tcp is served, with the protocols beside the cards at the top of /net (sysn 012, agreed with sysk; sysk: TCP, and tell). It dials out (sysn 012) and takes calls (sysn 013, sysk: Listening):

The key is 16 bytes netd reads from the rng driver at start; without them it lends no conversations, and ICMP and UDP go on as before. It has four tcp conversations and two buffer pairs, and lends the stack a conversation for each pair: a conversation that carries bytes, dialled or a call, keeps 2,048 bytes not yet acknowledged and 2,048 not yet read, at least one segment of 1,460, or the window, which the stack advertises in whole segments, would be 0; one that only announces keeps none. A call takes a slot and a pair when the stack opens it; with none free, or no announcer for its port, netd resets it. The caller's loop, which the host program plays here and netd plays one frame at a time:

on a frame:      g = net-input(frame, now)
                 if g is (tcp c did len): send out[0, len) if len > 0;
                   let did.acked bytes of c's queue go; hand did's payload to c's reader;
                   on did.fin, c's reader sees the end; when did.end is not open, c is done;
                   then tcp-send(c, queue, now) until it writes nothing
                 if g is (unreached (proto 6) c ...): c's status may say so; it goes on (sysn 009)
                 if g is a datagram for a port no one holds: net-unreachable(frame, 3), as often
                   as netd allows
on a write to c: append to c's queue; tcp-send(c, queue, now) until it writes nothing
on close of c:   tcp-close(c, queue, now)
at the earliest tcp-due(c) of all c: tcp-tick(c, queue, now)

Left out, and why

Each is a SHOULD or a MAY of RFC 9293, and each would be state to prove for throughput a shell does not need: delayed ACK (more ACKs instead, never a violation), Nagle (a shell wants its keystrokes now), keep-alive, window scaling, SACK and timestamps and a queue of segments that came early (they are dropped and the next expected byte acknowledged again). Urgent data is handed up in line with no signal, as smoltcp and utcp do; RFC 9293 itself advises new applications not to use it.

Taken from