4530879cb2d82d4f1d98a5ee4823f7ecef62a4a6
[akaros.git] / kern / include / net / tcp.h
1 /* Copyright © 1994-1999 Lucent Technologies Inc.  All rights reserved.
2  * Portions Copyright © 1997-1999 Vita Nuova Limited
3  * Portions Copyright © 2000-2007 Vita Nuova Holdings Limited
4  *                                (www.vitanuova.com)
5  * Revisions Copyright © 2000-2007 Lucent Technologies Inc. and others
6  *
7  * Modified for the Akaros operating system:
8  * Copyright (c) 2013-2014 The Regents of the University of California
9  * Copyright (c) 2013-2017 Google Inc.
10  *
11  * Permission is hereby granted, free of charge, to any person obtaining a copy
12  * of this software and associated documentation files (the "Software"), to deal
13  * in the Software without restriction, including without limitation the rights
14  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
15  * copies of the Software, and to permit persons to whom the Software is
16  * furnished to do so, subject to the following conditions:
17  *
18  * The above copyright notice and this permission notice shall be included in
19  * all copies or substantial portions of the Software.
20  *
21  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
22  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
23  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
24  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
25  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
26  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
27  * SOFTWARE. */
28
29 #pragma once
30
31 #include <net/ip.h>
32
33 enum {
34         QMAX = 64 * 1024 - 1,
35         IP_TCPPROTO = 6,
36
37         TCP4_IPLEN = 8,
38         TCP4_PHDRSIZE = 12,
39         TCP4_HDRSIZE = 20,
40         TCP4_TCBPHDRSZ = 40,
41         TCP4_PKT = TCP4_IPLEN + TCP4_PHDRSIZE,
42
43         TCP6_IPLEN = 0,
44         TCP6_PHDRSIZE = 40,
45         TCP6_HDRSIZE = 20,
46         TCP6_TCBPHDRSZ = 60,
47         TCP6_PKT = TCP6_IPLEN + TCP6_PHDRSIZE,
48
49         TcptimerOFF = 0,
50         TcptimerON = 1,
51         TcptimerDONE = 2,
52         MAX_TIME = (1 << 20),   /* Forever */
53         TCP_ACK = 50,   /* Timed ack sequence in ms */
54         MAXBACKMS = 9 * 60 * 1000,      /* longest backoff time (ms) before hangup */
55
56         URG = 0x20,     /* Data marked urgent */
57         ACK = 0x10,     /* Acknowledge is valid */
58         PSH = 0x08,     /* Whole data pipe is pushed */
59         RST = 0x04,     /* Reset connection */
60         SYN = 0x02,     /* Pkt. is synchronise */
61         FIN = 0x01,     /* Start close down */
62
63         EOLOPT = 0,
64         NOOPOPT = 1,
65         MSSOPT = 2,
66         MSS_LENGTH = 4, /* max segment size header option length */
67         WSOPT = 3,
68         WS_LENGTH = 3,  /* WS header option length */
69         MAX_WS_VALUE = 14,      /* RFC specified.  Limits available window to 2^30 */
70         TS_OPT = 8,
71         TS_LENGTH = 10,
72         TS_SEND_PREPAD = 2,     /* For non-SYNs, pre-pad 2 nops for 32 byte alignment */
73         SACK_OK_OPT = 4,
74         SACK_OK_LENGTH = 2,
75         SACK_OPT = 5,
76         MSL2 = 10,
77         MSPTICK = 50,   /* Milliseconds per timer tick */
78         DEF_MSS = 1460, /* Default mean segment */
79         DEF_MSS6 = 1280,        /* Default mean segment (min) for v6 */
80         SACK_SUPPORTED = TRUE,  /* SACK is on by default */
81         MAX_NR_SACKS_PER_PACKET = 4,    /* limited by TCP's opts size */
82         MAX_NR_SND_SACKS = 10,
83         MAX_NR_RCV_SACKS = 3,   /* We could try for 4, but don't need to */
84         DEF_RTT = 500,  /* Default round trip */
85         DEF_KAT = 120000,       /* Default time (ms) between keep alives */
86         TCP_LISTEN = 0, /* Listen connection */
87         TCP_CONNECT = 1,        /* Outgoing connection */
88         SYNACK_RXTIMER = 250,   /* ms between SYNACK retransmits */
89
90         TCPREXMTTHRESH = 3,     /* dupack threshold for recovery */
91         SACK_RETRANS_RECOVERY = 1,
92         FAST_RETRANS_RECOVERY = 2,
93         RTO_RETRANS_RECOVERY = 3,
94         CWIND_SCALE = 10,       /* initial CWIND will be MSS * this */
95
96         FORCE                   = 1 << 0,
97         CLONE                   = 1 << 1,
98         ACTIVE                  = 1 << 2,
99         SYNACK                  = 1 << 3,
100         TSO                             = 1 << 4,
101
102         RTTM_ALPHA_SHIFT = 3,   /* alpha = 1/8 */
103         RTTM_BRAVO_SHIFT = 2,   /* bravo = 1/4 (beta) */
104
105         Closed = 0,     /* Connection states */
106         Listen,
107         Syn_sent,
108         Established,
109         Finwait1,
110         Finwait2,
111         Close_wait,
112         Closing,
113         Last_ack,
114         Time_wait,
115
116         Maxlimbo = 1000,        /* maximum procs waiting for response to SYN ACK */
117         NLHT = 256,     /* hash table size, must be a power of 2 */
118         LHTMASK = NLHT - 1,
119
120         HaveWS = 1 << 8,
121 };
122
123 typedef struct tcptimer Tcptimer;
124 struct tcptimer {
125         Tcptimer *next;
126         Tcptimer *prev;
127         Tcptimer *readynext;
128         int state;
129         uint64_t start;
130         uint64_t count;
131         void (*func) (void *);
132         void *arg;
133 };
134
135 struct tcphdr {
136         uint8_t tcpsport[2];
137         uint8_t tcpdport[2];
138         uint8_t tcpseq[4];
139         uint8_t tcpack[4];
140         uint8_t tcpflag[2];
141         uint8_t tcpwin[2];
142         uint8_t tcpcksum[2];
143         uint8_t tcpurg[2];
144         /* Options segment */
145         uint8_t tcpopt[1];
146 };
147
148 /*
149  *  v4 and v6 pseudo headers used for
150  *  checksuming tcp
151  */
152 typedef struct tcp4hdr Tcp4hdr;
153 struct tcp4hdr {
154         uint8_t vihl;                           /* Version and header length */
155         uint8_t tos;                            /* Type of service */
156         uint8_t length[2];                      /* packet length */
157         uint8_t id[2];                          /* Identification */
158         uint8_t frag[2];                        /* Fragment information */
159         uint8_t Unused;
160         uint8_t proto;
161         uint8_t tcplen[2];
162         uint8_t tcpsrc[4];
163         uint8_t tcpdst[4];
164         struct tcphdr;
165 };
166
167 typedef struct tcp6hdr Tcp6hdr;
168 struct tcp6hdr {
169         uint8_t vcf[4];
170         uint8_t ploadlen[2];
171         uint8_t proto;
172         uint8_t ttl;
173         uint8_t tcpsrc[IPaddrlen];
174         uint8_t tcpdst[IPaddrlen];
175         struct tcphdr;
176 };
177
178 struct sack_block {
179         uint32_t left;
180         uint32_t right;
181 };
182
183 /*
184  *  this represents the control info
185  *  for a single packet.  It is derived from
186  *  a packet in ntohtcp{4,6}() and stuck into
187  *  a packet in htontcp{4,6}().
188  */
189 typedef struct tcp Tcp;
190 struct tcp {
191         uint16_t source;
192         uint16_t dest;
193         uint32_t seq;
194         uint32_t ack;
195         uint8_t flags;
196         uint16_t ws;                            /* window scale option (if not zero) */
197         uint32_t wnd;
198         uint16_t urg;
199         uint16_t mss;                           /* max segment size option (if not zero) */
200         uint16_t len;                           /* size of data */
201         uint32_t ts_val;                        /* timestamp val from sender */
202         uint32_t ts_ecr;                        /* timestamp echo response from sender */
203         bool sack_ok;                           /* header had/should have SACK_PERMITTED */
204         uint8_t nr_sacks;
205         struct sack_block sacks[MAX_NR_SACKS_PER_PACKET];
206 };
207
208 /*
209  *  this header is malloc'd to thread together fragments
210  *  waiting to be coalesced
211  */
212 typedef struct reseq Reseq;
213 struct reseq {
214         Reseq *next;
215         Tcp seg;
216         struct block *bp;
217         uint16_t length;
218 };
219
220 /*
221  *  the qlock in the Conv locks this structure
222  */
223 typedef struct tcpctl Tcpctl;
224 struct tcpctl {
225         uint8_t state;                          /* Connection state */
226         uint8_t type;                           /* Listening or active connection */
227         uint8_t code;                           /* Icmp code */
228         struct {
229                 uint32_t una;                   /* Left edge of unacked data region */
230                 uint32_t nxt;                   /* Next seq to send, right edge of unacked */
231                 uint32_t rtx;                   /* Next to send for retrans */
232                 uint32_t wnd;                   /* Tcp send window */
233                 uint32_t urg;                   /* Urgent data pointer */
234                 uint32_t wl2;
235                 int scale;                              /* how much to right shift window for xmit */
236                 uint32_t in_flight;             /* estimate of how much is in flight */
237                 uint8_t loss_hint;              /* number of loss hints rcvd */
238                 uint8_t sack_loss_hint; /* For detecting sack rxmit losses */
239                 bool flush_sacks;               /* Two timeouts in a row == dump sacks */
240                 uint8_t recovery;               /* loss recovery flag */
241                 uint32_t recovery_pt;   /* right window for recovery point */
242                 uint8_t nr_sacks;
243                 struct sack_block sacks[MAX_NR_SND_SACKS];
244         } snd;
245         struct {
246                 uint32_t nxt;                   /* Receive pointer to next uint8_t slot */
247                 uint32_t wnd;                   /* Receive window incoming */
248                 uint32_t urg;                   /* Urgent pointer */
249                 int blocked;
250                 int una;                                /* unacked data segs */
251                 int scale;                              /* how much to left shift window for rx */
252                 uint8_t nr_sacks;
253                 struct sack_block sacks[MAX_NR_RCV_SACKS];
254         } rcv;
255         uint32_t iss;                           /* Initial sequence number */
256         int sawwsopt;                           /* true if we saw a wsopt on the incoming SYN */
257         uint32_t cwind;                         /* Congestion window */
258         int scale;                                      /* desired snd.scale */
259         uint32_t ssthresh;                      /* Slow start threshold */
260         int irs;                                        /* Initial received squence */
261         uint16_t mss;                           /* Max segment size */
262         uint16_t typical_mss;           /* MSS for most packets (< MSS for some opts) */
263         int rerecv;                                     /* Overlap of data rerecevived */
264         uint32_t window;                        /* Recevive window */
265         uint8_t backoff;                        /* Exponential backoff counter */
266         int backedoff;                          /* ms we've backed off for rexmits */
267         uint8_t flags;                          /* State flags */
268         Reseq *reseq;                           /* Resequencing queue */
269         Tcptimer timer;                         /* Activity timer */
270         Tcptimer acktimer;                      /* Acknowledge timer */
271         Tcptimer rtt_timer;                     /* Round trip timer */
272         Tcptimer katimer;                       /* keep alive timer */
273         uint32_t rttseq;                        /* Round trip sequence */
274         int srtt;                                       /* Shortened round trip */
275         int mdev;                                       /* Mean deviation of round trip */
276         int kacounter;                          /* count down for keep alive */
277         uint64_t sndsyntime;            /* time syn sent */
278         uint64_t time;                          /* time Finwait2 was sent */
279         int nochecksum;                         /* non-zero means don't send checksums */
280         int flgcnt;                                     /* number of flags in the sequence (FIN,SYN) */
281         uint32_t ts_recent;                     /* timestamp received around last_ack_sent */
282         uint32_t last_ack_sent;         /* to determine when to update timestamp */
283         bool sack_ok;                           /* Can use SACK for this connection */
284
285         union {
286                 Tcp4hdr tcp4hdr;
287                 Tcp6hdr tcp6hdr;
288         } protohdr;                                     /* prototype header */
289 };
290
291 /* New calls are put in limbo rather than having a conversation structure
292  *  allocated.  Thus, a SYN attack results in lots of limbo'd calls but not any
293  *  real Conv structures mucking things up.  Calls in limbo rexmit their SYN ACK
294  *  every SYNACK_RXTIMER ms up to 4 times, i.e., they disappear after 1 second.
295  *
296  *  In particular they aren't on a listener's queue so that they don't figure in
297  *  the input queue limit.
298  *
299  *  If 1/2 of a T3 was attacking SYN packets, we'ld have a permanent queue of
300  *  70000 limbo'd calls.  Not great for a linear list but doable.  Therefore
301  *  there is no hashing of this list.
302  */
303 typedef struct limbo Limbo;
304 struct limbo {
305         Limbo *next;
306
307         uint8_t laddr[IPaddrlen];
308         uint8_t raddr[IPaddrlen];
309         uint16_t lport;
310         uint16_t rport;
311         uint32_t irs;                           /* initial received sequence */
312         uint32_t iss;                           /* initial sent sequence */
313         uint16_t mss;                           /* mss from the other end */
314         uint16_t rcvscale;                      /* how much to scale rcvd windows */
315         uint16_t sndscale;                      /* how much to scale sent windows */
316         uint64_t lastsend;                      /* last time we sent a synack */
317         uint8_t version;                        /* v4 or v6 */
318         uint8_t rexmits;                        /* number of retransmissions */
319         bool sack_ok;                           /* other side said SACK_OK */
320         uint32_t ts_val;                        /* timestamp val from sender */
321 };
322
323 enum {
324         /* MIB stats */
325         MaxConn,
326         ActiveOpens,
327         PassiveOpens,
328         EstabResets,
329         CurrEstab,
330         InSegs,
331         OutSegs,
332         RetransSegs,
333         RetransTimeouts,
334         InErrs,
335         OutRsts,
336
337         /* non-MIB stats */
338         CsumErrs,
339         HlenErrs,
340         LenErrs,
341         OutOfOrder,
342
343         Nstats
344 };
345
346 typedef struct tcppriv Tcppriv;
347 struct tcppriv {
348         /* List of active timers */
349         qlock_t tl;
350         Tcptimer *timers;
351
352         /* hash table for matching conversations */
353         struct Ipht ht;
354
355         /* calls in limbo waiting for an ACK to our SYN ACK */
356         int nlimbo;
357         Limbo *lht[NLHT];
358
359         /* for keeping track of tcpackproc */
360         qlock_t apl;
361         int ackprocstarted;
362
363         uint32_t stats[Nstats];
364 };
365
366 static inline int seq_within(uint32_t x, uint32_t low, uint32_t high)
367 {
368         if (low <= high) {
369                 if (low <= x && x <= high)
370                         return 1;
371         } else {
372                 if (x >= low || x <= high)
373                         return 1;
374         }
375         return 0;
376 }
377
378 static inline int seq_lt(uint32_t x, uint32_t y)
379 {
380         return (int)(x - y) < 0;
381 }
382
383 static inline int seq_le(uint32_t x, uint32_t y)
384 {
385         return (int)(x - y) <= 0;
386 }
387
388 static inline int seq_gt(uint32_t x, uint32_t y)
389 {
390         return (int)(x - y) > 0;
391 }
392
393 static inline int seq_ge(uint32_t x, uint32_t y)
394 {
395         return (int)(x - y) >= 0;
396 }
397
398 static inline uint32_t seq_max(uint32_t x, uint32_t y)
399 {
400         return seq_ge(x, y) ? x : y;
401 }
402
403 static inline uint32_t seq_min(uint32_t x, uint32_t y)
404 {
405         return seq_le(x, y) ? x : y;
406 }
407
408 /* Caller needs to know we're TCP and with transport_offset set, which is
409  * usually on the outbound network path. */
410 static inline struct tcphdr *tcp_hdr(struct block *bp)
411 {
412         return (struct tcphdr*)(bp->rp + bp->transport_offset);
413 }
414
415 static inline size_t tcp_hdrlen(struct block *bp)
416 {
417         struct tcphdr *hdr = tcp_hdr(bp);
418         uint8_t data_offset;
419
420         data_offset = hdr->tcpflag[0] >> 4;
421         return data_offset * 4;
422 }