]> git.meshlink.io Git - utcp/blob - utcp.c
d837d27a1b96fe05b860ce8fcf692bbda115f092
[utcp] / utcp.c
1 /*
2     utcp.c -- Userspace TCP
3     Copyright (C) 2014-2017 Guus Sliepen <guus@tinc-vpn.org>
4
5     This program is free software; you can redistribute it and/or modify
6     it under the terms of the GNU General Public License as published by
7     the Free Software Foundation; either version 2 of the License, or
8     (at your option) any later version.
9
10     This program is distributed in the hope that it will be useful,
11     but WITHOUT ANY WARRANTY; without even the implied warranty of
12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13     GNU General Public License for more details.
14
15     You should have received a copy of the GNU General Public License along
16     with this program; if not, write to the Free Software Foundation, Inc.,
17     51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
18 */
19
20 #define _GNU_SOURCE
21
22 #include <assert.h>
23 #include <errno.h>
24 #include <stdio.h>
25 #include <stdlib.h>
26 #include <stdint.h>
27 #include <stdbool.h>
28 #include <string.h>
29 #include <unistd.h>
30 #include <sys/time.h>
31 #include <sys/socket.h>
32
33 #include "utcp_priv.h"
34
35 #ifndef EBADMSG
36 #define EBADMSG         104
37 #endif
38
39 #ifndef SHUT_RDWR
40 #define SHUT_RDWR 2
41 #endif
42
43 #ifdef poll
44 #undef poll
45 #endif
46
47 #ifndef timersub
48 #define timersub(a, b, r)\
49         do {\
50                 (r)->tv_sec = (a)->tv_sec - (b)->tv_sec;\
51                 (r)->tv_usec = (a)->tv_usec - (b)->tv_usec;\
52                 if((r)->tv_usec < 0)\
53                         (r)->tv_sec--, (r)->tv_usec += USEC_PER_SEC;\
54         } while (0)
55 #endif
56
57 static inline size_t max(size_t a, size_t b) {
58         return a > b ? a : b;
59 }
60
61 #ifdef UTCP_DEBUG
62 #include <stdarg.h>
63
64 static void debug(const char *format, ...) {
65         va_list ap;
66         va_start(ap, format);
67         vfprintf(stderr, format, ap);
68         va_end(ap);
69 }
70
71 static void print_packet(struct utcp *utcp, const char *dir, const void *pkt, size_t len) {
72         struct hdr hdr;
73
74         if(len < sizeof(hdr)) {
75                 debug("%p %s: short packet (%lu bytes)\n", utcp, dir, (unsigned long)len);
76                 return;
77         }
78
79         memcpy(&hdr, pkt, sizeof(hdr));
80         debug("%p %s: len=%lu, src=%u dst=%u seq=%u ack=%u wnd=%u aux=%x ctl=", utcp, dir, (unsigned long)len, hdr.src, hdr.dst, hdr.seq, hdr.ack, hdr.wnd, hdr.aux);
81
82         if(hdr.ctl & SYN) {
83                 debug("SYN");
84         }
85
86         if(hdr.ctl & RST) {
87                 debug("RST");
88         }
89
90         if(hdr.ctl & FIN) {
91                 debug("FIN");
92         }
93
94         if(hdr.ctl & ACK) {
95                 debug("ACK");
96         }
97
98         if(len > sizeof(hdr)) {
99                 uint32_t datalen = len - sizeof(hdr);
100                 const uint8_t *data = (uint8_t *)pkt + sizeof(hdr);
101                 char str[datalen * 2 + 1];
102                 char *p = str;
103
104                 for(uint32_t i = 0; i < datalen; i++) {
105                         *p++ = "0123456789ABCDEF"[data[i] >> 4];
106                         *p++ = "0123456789ABCDEF"[data[i] & 15];
107                 }
108
109                 *p = 0;
110
111                 debug(" data=%s", str);
112         }
113
114         debug("\n");
115 }
116 #else
117 #define debug(...) do {} while(0)
118 #define print_packet(...) do {} while(0)
119 #endif
120
121 static void set_state(struct utcp_connection *c, enum state state) {
122         c->state = state;
123
124         if(state == ESTABLISHED) {
125                 timerclear(&c->conn_timeout);
126         }
127
128         debug("%p new state: %s\n", c->utcp, strstate[state]);
129 }
130
131 static bool fin_wanted(struct utcp_connection *c, uint32_t seq) {
132         if(seq != c->snd.last) {
133                 return false;
134         }
135
136         switch(c->state) {
137         case FIN_WAIT_1:
138         case CLOSING:
139         case LAST_ACK:
140                 return true;
141
142         default:
143                 return false;
144         }
145 }
146
147 static bool is_reliable(struct utcp_connection *c) {
148         return c->flags & UTCP_RELIABLE;
149 }
150
151 static int32_t seqdiff(uint32_t a, uint32_t b) {
152         return a - b;
153 }
154
155 // Buffer functions
156 // TODO: convert to ringbuffers to avoid memmove() operations.
157
158 // Store data into the buffer
159 static ssize_t buffer_put_at(struct buffer *buf, size_t offset, const void *data, size_t len) {
160         debug("buffer_put_at %lu %lu %lu\n", (unsigned long)buf->used, (unsigned long)offset, (unsigned long)len);
161
162         size_t required = offset + len;
163
164         if(required > buf->maxsize) {
165                 if(offset >= buf->maxsize) {
166                         return 0;
167                 }
168
169                 len = buf->maxsize - offset;
170                 required = buf->maxsize;
171         }
172
173         if(required > buf->size) {
174                 size_t newsize = buf->size;
175
176                 if(!newsize) {
177                         newsize = required;
178                 } else {
179                         do {
180                                 newsize *= 2;
181                         } while(newsize < required);
182                 }
183
184                 if(newsize > buf->maxsize) {
185                         newsize = buf->maxsize;
186                 }
187
188                 char *newdata = realloc(buf->data, newsize);
189
190                 if(!newdata) {
191                         return -1;
192                 }
193
194                 buf->data = newdata;
195                 buf->size = newsize;
196         }
197
198         memcpy(buf->data + offset, data, len);
199
200         if(required > buf->used) {
201                 buf->used = required;
202         }
203
204         return len;
205 }
206
207 static ssize_t buffer_put(struct buffer *buf, const void *data, size_t len) {
208         return buffer_put_at(buf, buf->used, data, len);
209 }
210
211 // Get data from the buffer. data can be NULL.
212 static ssize_t buffer_get(struct buffer *buf, void *data, size_t len) {
213         if(len > buf->used) {
214                 len = buf->used;
215         }
216
217         if(data) {
218                 memcpy(data, buf->data, len);
219         }
220
221         if(len < buf->used) {
222                 memmove(buf->data, buf->data + len, buf->used - len);
223         }
224
225         buf->used -= len;
226         return len;
227 }
228
229 // Copy data from the buffer without removing it.
230 static ssize_t buffer_copy(struct buffer *buf, void *data, size_t offset, size_t len) {
231         if(offset >= buf->used) {
232                 return 0;
233         }
234
235         if(offset + len > buf->used) {
236                 len = buf->used - offset;
237         }
238
239         memcpy(data, buf->data + offset, len);
240         return len;
241 }
242
243 static bool buffer_init(struct buffer *buf, uint32_t len, uint32_t maxlen) {
244         memset(buf, 0, sizeof(*buf));
245
246         if(len) {
247                 buf->data = malloc(len);
248
249                 if(!buf->data) {
250                         return false;
251                 }
252         }
253
254         buf->size = len;
255         buf->maxsize = maxlen;
256         return true;
257 }
258
259 static void buffer_exit(struct buffer *buf) {
260         free(buf->data);
261         memset(buf, 0, sizeof(*buf));
262 }
263
264 static uint32_t buffer_free(const struct buffer *buf) {
265         return buf->maxsize - buf->used;
266 }
267
268 // Connections are stored in a sorted list.
269 // This gives O(log(N)) lookup time, O(N log(N)) insertion time and O(N) deletion time.
270
271 static int compare(const void *va, const void *vb) {
272         assert(va && vb);
273
274         const struct utcp_connection *a = *(struct utcp_connection **)va;
275         const struct utcp_connection *b = *(struct utcp_connection **)vb;
276
277         assert(a && b);
278         assert(a->src && b->src);
279
280         int c = (int)a->src - (int)b->src;
281
282         if(c) {
283                 return c;
284         }
285
286         c = (int)a->dst - (int)b->dst;
287         return c;
288 }
289
290 static struct utcp_connection *find_connection(const struct utcp *utcp, uint16_t src, uint16_t dst) {
291         if(!utcp->nconnections) {
292                 return NULL;
293         }
294
295         struct utcp_connection key = {
296                 .src = src,
297                 .dst = dst,
298         }, *keyp = &key;
299         struct utcp_connection **match = bsearch(&keyp, utcp->connections, utcp->nconnections, sizeof(*utcp->connections), compare);
300         return match ? *match : NULL;
301 }
302
303 static void free_connection(struct utcp_connection *c) {
304         struct utcp *utcp = c->utcp;
305         struct utcp_connection **cp = bsearch(&c, utcp->connections, utcp->nconnections, sizeof(*utcp->connections), compare);
306
307         assert(cp);
308
309         int i = cp - utcp->connections;
310         memmove(cp, cp + 1, (utcp->nconnections - i - 1) * sizeof(*cp));
311         utcp->nconnections--;
312
313         buffer_exit(&c->rcvbuf);
314         buffer_exit(&c->sndbuf);
315         free(c);
316 }
317
318 static struct utcp_connection *allocate_connection(struct utcp *utcp, uint16_t src, uint16_t dst) {
319         // Check whether this combination of src and dst is free
320
321         if(src) {
322                 if(find_connection(utcp, src, dst)) {
323                         errno = EADDRINUSE;
324                         return NULL;
325                 }
326         } else { // If src == 0, generate a random port number with the high bit set
327                 if(utcp->nconnections >= 32767) {
328                         errno = ENOMEM;
329                         return NULL;
330                 }
331
332                 src = rand() | 0x8000;
333
334                 while(find_connection(utcp, src, dst)) {
335                         src++;
336                 }
337         }
338
339         // Allocate memory for the new connection
340
341         if(utcp->nconnections >= utcp->nallocated) {
342                 if(!utcp->nallocated) {
343                         utcp->nallocated = 4;
344                 } else {
345                         utcp->nallocated *= 2;
346                 }
347
348                 struct utcp_connection **new_array = realloc(utcp->connections, utcp->nallocated * sizeof(*utcp->connections));
349
350                 if(!new_array) {
351                         return NULL;
352                 }
353
354                 utcp->connections = new_array;
355         }
356
357         struct utcp_connection *c = calloc(1, sizeof(*c));
358
359         if(!c) {
360                 return NULL;
361         }
362
363         if(!buffer_init(&c->sndbuf, DEFAULT_SNDBUFSIZE, DEFAULT_MAXSNDBUFSIZE)) {
364                 free(c);
365                 return NULL;
366         }
367
368         if(!buffer_init(&c->rcvbuf, DEFAULT_RCVBUFSIZE, DEFAULT_MAXRCVBUFSIZE)) {
369                 buffer_exit(&c->sndbuf);
370                 free(c);
371                 return NULL;
372         }
373
374         // Fill in the details
375
376         c->src = src;
377         c->dst = dst;
378 #ifdef UTCP_DEBUG
379         c->snd.iss = 0;
380 #else
381         c->snd.iss = rand();
382 #endif
383         c->snd.una = c->snd.iss;
384         c->snd.nxt = c->snd.iss + 1;
385         c->rcv.wnd = utcp->mtu;
386         c->snd.last = c->snd.nxt;
387         c->snd.cwnd = utcp->mtu;
388         c->utcp = utcp;
389
390         // Add it to the sorted list of connections
391
392         utcp->connections[utcp->nconnections++] = c;
393         qsort(utcp->connections, utcp->nconnections, sizeof(*utcp->connections), compare);
394
395         return c;
396 }
397
398 static inline uint32_t absdiff(uint32_t a, uint32_t b) {
399         if(a > b) {
400                 return a - b;
401         } else {
402                 return b - a;
403         }
404 }
405
406 // Update RTT variables. See RFC 6298.
407 static void update_rtt(struct utcp_connection *c, uint32_t rtt) {
408         if(!rtt) {
409                 debug("invalid rtt\n");
410                 return;
411         }
412
413         struct utcp *utcp = c->utcp;
414
415         if(!utcp->srtt) {
416                 utcp->srtt = rtt;
417                 utcp->rttvar = rtt / 2;
418                 utcp->rto = rtt + max(2 * rtt, CLOCK_GRANULARITY);
419         } else {
420                 utcp->rttvar = (utcp->rttvar * 3 + absdiff(utcp->srtt, rtt)) / 4;
421                 utcp->srtt = (utcp->srtt * 7 + rtt) / 8;
422                 utcp->rto = utcp->srtt + max(utcp->rttvar, CLOCK_GRANULARITY);
423         }
424
425         if(utcp->rto > MAX_RTO) {
426                 utcp->rto = MAX_RTO;
427         }
428
429         debug("rtt %u srtt %u rttvar %u rto %u\n", rtt, utcp->srtt, utcp->rttvar, utcp->rto);
430 }
431
432 static void start_retransmit_timer(struct utcp_connection *c) {
433         gettimeofday(&c->rtrx_timeout, NULL);
434         c->rtrx_timeout.tv_usec += c->utcp->rto;
435
436         while(c->rtrx_timeout.tv_usec >= 1000000) {
437                 c->rtrx_timeout.tv_usec -= 1000000;
438                 c->rtrx_timeout.tv_sec++;
439         }
440
441         debug("timeout set to %lu.%06lu (%u)\n", c->rtrx_timeout.tv_sec, c->rtrx_timeout.tv_usec, c->utcp->rto);
442 }
443
444 static void stop_retransmit_timer(struct utcp_connection *c) {
445         timerclear(&c->rtrx_timeout);
446         debug("timeout cleared\n");
447 }
448
449 struct utcp_connection *utcp_connect_ex(struct utcp *utcp, uint16_t dst, utcp_recv_t recv, void *priv, uint32_t flags) {
450         struct utcp_connection *c = allocate_connection(utcp, 0, dst);
451
452         if(!c) {
453                 return NULL;
454         }
455
456         assert((flags & ~0xf) == 0);
457
458         c->flags = flags;
459         c->recv = recv;
460         c->priv = priv;
461
462         struct {
463                 struct hdr hdr;
464                 uint8_t init[4];
465         } pkt;
466
467         pkt.hdr.src = c->src;
468         pkt.hdr.dst = c->dst;
469         pkt.hdr.seq = c->snd.iss;
470         pkt.hdr.ack = 0;
471         pkt.hdr.wnd = c->rcv.wnd;
472         pkt.hdr.ctl = SYN;
473         pkt.hdr.aux = 0x0101;
474         pkt.init[0] = 1;
475         pkt.init[1] = 0;
476         pkt.init[2] = 0;
477         pkt.init[3] = flags & 0x7;
478
479         set_state(c, SYN_SENT);
480
481         print_packet(utcp, "send", &pkt, sizeof(pkt));
482         utcp->send(utcp, &pkt, sizeof(pkt));
483
484         gettimeofday(&c->conn_timeout, NULL);
485         c->conn_timeout.tv_sec += utcp->timeout;
486
487         start_retransmit_timer(c);
488
489         return c;
490 }
491
492 struct utcp_connection *utcp_connect(struct utcp *utcp, uint16_t dst, utcp_recv_t recv, void *priv) {
493         return utcp_connect_ex(utcp, dst, recv, priv, UTCP_TCP);
494 }
495
496 void utcp_accept(struct utcp_connection *c, utcp_recv_t recv, void *priv) {
497         if(c->reapable || c->state != SYN_RECEIVED) {
498                 debug("Error: accept() called on invalid connection %p in state %s\n", c, strstate[c->state]);
499                 return;
500         }
501
502         debug("%p accepted, %p %p\n", c, recv, priv);
503         c->recv = recv;
504         c->priv = priv;
505         set_state(c, ESTABLISHED);
506 }
507
508 static void ack(struct utcp_connection *c, bool sendatleastone) {
509         int32_t left = seqdiff(c->snd.last, c->snd.nxt);
510         int32_t cwndleft = c->snd.cwnd - seqdiff(c->snd.nxt, c->snd.una);
511         debug("cwndleft = %d\n", cwndleft);
512
513         assert(left >= 0);
514
515         if(cwndleft <= 0) {
516                 cwndleft = 0;
517         }
518
519         if(cwndleft < left) {
520                 left = cwndleft;
521         }
522
523         if(!left && !sendatleastone) {
524                 return;
525         }
526
527         struct {
528                 struct hdr hdr;
529                 uint8_t data[];
530         } *pkt;
531
532         pkt = malloc(sizeof(pkt->hdr) + c->utcp->mtu);
533
534         if(!pkt) {
535                 return;
536         }
537
538         pkt->hdr.src = c->src;
539         pkt->hdr.dst = c->dst;
540         pkt->hdr.ack = c->rcv.nxt;
541         pkt->hdr.wnd = c->snd.wnd;
542         pkt->hdr.ctl = ACK;
543         pkt->hdr.aux = 0;
544
545         do {
546                 uint32_t seglen = left > c->utcp->mtu ? c->utcp->mtu : left;
547                 pkt->hdr.seq = c->snd.nxt;
548
549                 buffer_copy(&c->sndbuf, pkt->data, seqdiff(c->snd.nxt, c->snd.una), seglen);
550
551                 c->snd.nxt += seglen;
552                 left -= seglen;
553
554                 if(seglen && fin_wanted(c, c->snd.nxt)) {
555                         seglen--;
556                         pkt->hdr.ctl |= FIN;
557                 }
558
559                 if(!c->rtt_start.tv_sec) {
560                         // Start RTT measurement
561                         gettimeofday(&c->rtt_start, NULL);
562                         c->rtt_seq = pkt->hdr.seq + seglen;
563                         debug("Starting RTT measurement, expecting ack %u\n", c->rtt_seq);
564                 }
565
566                 print_packet(c->utcp, "send", pkt, sizeof(pkt->hdr) + seglen);
567                 c->utcp->send(c->utcp, pkt, sizeof(pkt->hdr) + seglen);
568         } while(left);
569
570         free(pkt);
571 }
572
573 ssize_t utcp_send(struct utcp_connection *c, const void *data, size_t len) {
574         if(c->reapable) {
575                 debug("Error: send() called on closed connection %p\n", c);
576                 errno = EBADF;
577                 return -1;
578         }
579
580         switch(c->state) {
581         case CLOSED:
582         case LISTEN:
583                 debug("Error: send() called on unconnected connection %p\n", c);
584                 errno = ENOTCONN;
585                 return -1;
586
587         case SYN_SENT:
588         case SYN_RECEIVED:
589         case ESTABLISHED:
590         case CLOSE_WAIT:
591                 break;
592
593         case FIN_WAIT_1:
594         case FIN_WAIT_2:
595         case CLOSING:
596         case LAST_ACK:
597         case TIME_WAIT:
598                 debug("Error: send() called on closing connection %p\n", c);
599                 errno = EPIPE;
600                 return -1;
601         }
602
603         // Exit early if we have nothing to send.
604
605         if(!len) {
606                 return 0;
607         }
608
609         if(!data) {
610                 errno = EFAULT;
611                 return -1;
612         }
613
614         // Add data to send buffer.
615
616         len = buffer_put(&c->sndbuf, data, len);
617
618         if(len <= 0) {
619                 errno = EWOULDBLOCK;
620                 return 0;
621         }
622
623         c->snd.last += len;
624
625         // Don't send anything yet if the connection has not fully established yet
626
627         if(c->state == SYN_SENT || c->state == SYN_RECEIVED) {
628                 return len;
629         }
630
631         ack(c, false);
632
633         if(!is_reliable(c)) {
634                 c->snd.una = c->snd.nxt = c->snd.last;
635                 buffer_get(&c->sndbuf, NULL, c->sndbuf.used);
636         }
637
638         if(is_reliable(c) && !timerisset(&c->rtrx_timeout)) {
639                 start_retransmit_timer(c);
640         }
641
642         if(is_reliable(c) && !timerisset(&c->conn_timeout)) {
643                 gettimeofday(&c->conn_timeout, NULL);
644                 c->conn_timeout.tv_sec += c->utcp->timeout;
645         }
646
647         return len;
648 }
649
650 static void swap_ports(struct hdr *hdr) {
651         uint16_t tmp = hdr->src;
652         hdr->src = hdr->dst;
653         hdr->dst = tmp;
654 }
655
656 static void retransmit(struct utcp_connection *c) {
657         if(c->state == CLOSED || c->snd.last == c->snd.una) {
658                 debug("Retransmit() called but nothing to retransmit!\n");
659                 stop_retransmit_timer(c);
660                 return;
661         }
662
663         struct utcp *utcp = c->utcp;
664
665         struct {
666                 struct hdr hdr;
667                 uint8_t data[];
668         } *pkt;
669
670         pkt = malloc(sizeof(pkt->hdr) + c->utcp->mtu);
671
672         if(!pkt) {
673                 return;
674         }
675
676         pkt->hdr.src = c->src;
677         pkt->hdr.dst = c->dst;
678         pkt->hdr.wnd = c->rcv.wnd;
679         pkt->hdr.aux = 0;
680
681         switch(c->state) {
682         case SYN_SENT:
683                 // Send our SYN again
684                 pkt->hdr.seq = c->snd.iss;
685                 pkt->hdr.ack = 0;
686                 pkt->hdr.ctl = SYN;
687                 pkt->hdr.aux = 0x0101;
688                 pkt->data[0] = 1;
689                 pkt->data[1] = 0;
690                 pkt->data[2] = 0;
691                 pkt->data[3] = c->flags & 0x7;
692                 print_packet(c->utcp, "rtrx", pkt, sizeof(pkt->hdr) + 4);
693                 utcp->send(utcp, pkt, sizeof(pkt->hdr) + 4);
694                 break;
695
696         case SYN_RECEIVED:
697                 // Send SYNACK again
698                 pkt->hdr.seq = c->snd.nxt;
699                 pkt->hdr.ack = c->rcv.nxt;
700                 pkt->hdr.ctl = SYN | ACK;
701                 print_packet(c->utcp, "rtrx", pkt, sizeof(pkt->hdr));
702                 utcp->send(utcp, pkt, sizeof(pkt->hdr));
703                 break;
704
705         case ESTABLISHED:
706         case FIN_WAIT_1:
707         case CLOSE_WAIT:
708         case CLOSING:
709         case LAST_ACK:
710                 // Send unacked data again.
711                 pkt->hdr.seq = c->snd.una;
712                 pkt->hdr.ack = c->rcv.nxt;
713                 pkt->hdr.ctl = ACK;
714                 uint32_t len = seqdiff(c->snd.last, c->snd.una);
715
716                 if(len > utcp->mtu) {
717                         len = utcp->mtu;
718                 }
719
720                 if(fin_wanted(c, c->snd.una + len)) {
721                         len--;
722                         pkt->hdr.ctl |= FIN;
723                 }
724
725                 c->snd.nxt = c->snd.una + len;
726                 c->snd.cwnd = utcp->mtu; // reduce cwnd on retransmit
727                 buffer_copy(&c->sndbuf, pkt->data, 0, len);
728                 print_packet(c->utcp, "rtrx", pkt, sizeof(pkt->hdr) + len);
729                 utcp->send(utcp, pkt, sizeof(pkt->hdr) + len);
730                 break;
731
732         case CLOSED:
733         case LISTEN:
734         case TIME_WAIT:
735         case FIN_WAIT_2:
736                 // We shouldn't need to retransmit anything in this state.
737 #ifdef UTCP_DEBUG
738                 abort();
739 #endif
740                 stop_retransmit_timer(c);
741                 goto cleanup;
742         }
743
744         start_retransmit_timer(c);
745         utcp->rto *= 2;
746
747         if(utcp->rto > MAX_RTO) {
748                 utcp->rto = MAX_RTO;
749         }
750
751         c->rtt_start.tv_sec = 0; // invalidate RTT timer
752
753 cleanup:
754         free(pkt);
755 }
756
757 /* Update receive buffer and SACK entries after consuming data.
758  *
759  * Situation:
760  *
761  * |.....0000..1111111111.....22222......3333|
762  * |---------------^
763  *
764  * 0..3 represent the SACK entries. The ^ indicates up to which point we want
765  * to remove data from the receive buffer. The idea is to substract "len"
766  * from the offset of all the SACK entries, and then remove/cut down entries
767  * that are shifted to before the start of the receive buffer.
768  *
769  * There are three cases:
770  * - the SACK entry is after ^, in that case just change the offset.
771  * - the SACK entry starts before and ends after ^, so we have to
772  *   change both its offset and size.
773  * - the SACK entry is completely before ^, in that case delete it.
774  */
775 static void sack_consume(struct utcp_connection *c, size_t len) {
776         debug("sack_consume %lu\n", (unsigned long)len);
777
778         if(len > c->rcvbuf.used) {
779                 debug("All SACK entries consumed");
780                 c->sacks[0].len = 0;
781                 return;
782         }
783
784         buffer_get(&c->rcvbuf, NULL, len);
785
786         for(int i = 0; i < NSACKS && c->sacks[i].len;) {
787                 if(len < c->sacks[i].offset) {
788                         c->sacks[i].offset -= len;
789                         i++;
790                 } else if(len < c->sacks[i].offset + c->sacks[i].len) {
791                         c->sacks[i].len -= len - c->sacks[i].offset;
792                         c->sacks[i].offset = 0;
793                         i++;
794                 } else {
795                         if(i < NSACKS - 1) {
796                                 memmove(&c->sacks[i], &c->sacks[i + 1], (NSACKS - 1 - i) * sizeof(c->sacks)[i]);
797                                 c->sacks[NSACKS - 1].len = 0;
798                         } else {
799                                 c->sacks[i].len = 0;
800                                 break;
801                         }
802                 }
803         }
804
805         for(int i = 0; i < NSACKS && c->sacks[i].len; i++) {
806                 debug("SACK[%d] offset %u len %u\n", i, c->sacks[i].offset, c->sacks[i].len);
807         }
808 }
809
810 static void handle_out_of_order(struct utcp_connection *c, uint32_t offset, const void *data, size_t len) {
811         debug("out of order packet, offset %u\n", offset);
812         // Packet loss or reordering occured. Store the data in the buffer.
813         ssize_t rxd = buffer_put_at(&c->rcvbuf, offset, data, len);
814
815         if(rxd < 0 || (size_t)rxd < len) {
816                 abort();
817         }
818
819         // Make note of where we put it.
820         for(int i = 0; i < NSACKS; i++) {
821                 if(!c->sacks[i].len) { // nothing to merge, add new entry
822                         debug("New SACK entry %d\n", i);
823                         c->sacks[i].offset = offset;
824                         c->sacks[i].len = rxd;
825                         break;
826                 } else if(offset < c->sacks[i].offset) {
827                         if(offset + rxd < c->sacks[i].offset) { // insert before
828                                 if(!c->sacks[NSACKS - 1].len) { // only if room left
829                                         debug("Insert SACK entry at %d\n", i);
830                                         memmove(&c->sacks[i + 1], &c->sacks[i], (NSACKS - i - 1) * sizeof(c->sacks)[i]);
831                                         c->sacks[i].offset = offset;
832                                         c->sacks[i].len = rxd;
833                                 } else {
834                                         debug("SACK entries full, dropping packet\n");
835                                 }
836
837                                 break;
838                         } else { // merge
839                                 debug("Merge with start of SACK entry at %d\n", i);
840                                 c->sacks[i].offset = offset;
841                                 break;
842                         }
843                 } else if(offset <= c->sacks[i].offset + c->sacks[i].len) {
844                         if(offset + rxd > c->sacks[i].offset + c->sacks[i].len) { // merge
845                                 debug("Merge with end of SACK entry at %d\n", i);
846                                 c->sacks[i].len = offset + rxd - c->sacks[i].offset;
847                                 // TODO: handle potential merge with next entry
848                         }
849
850                         break;
851                 }
852         }
853
854         for(int i = 0; i < NSACKS && c->sacks[i].len; i++) {
855                 debug("SACK[%d] offset %u len %u\n", i, c->sacks[i].offset, c->sacks[i].len);
856         }
857 }
858
859 static void handle_in_order(struct utcp_connection *c, const void *data, size_t len) {
860         // Check if we can process out-of-order data now.
861         if(c->sacks[0].len && len >= c->sacks[0].offset) { // TODO: handle overlap with second SACK
862                 debug("incoming packet len %lu connected with SACK at %u\n", (unsigned long)len, c->sacks[0].offset);
863                 buffer_put_at(&c->rcvbuf, 0, data, len); // TODO: handle return value
864                 len = max(len, c->sacks[0].offset + c->sacks[0].len);
865                 data = c->rcvbuf.data;
866         }
867
868         if(c->recv) {
869                 ssize_t rxd = c->recv(c, data, len);
870
871                 if(rxd < 0 || (size_t)rxd != len) {
872                         // TODO: handle the application not accepting all data.
873                         abort();
874                 }
875         }
876
877         if(c->rcvbuf.used) {
878                 sack_consume(c, len);
879         }
880
881         c->rcv.nxt += len;
882 }
883
884
885 static void handle_incoming_data(struct utcp_connection *c, uint32_t seq, const void *data, size_t len) {
886         if(!is_reliable(c)) {
887                 c->recv(c, data, len);
888                 c->rcv.nxt = seq + len;
889                 return;
890         }
891
892         uint32_t offset = seqdiff(seq, c->rcv.nxt);
893
894         if(offset + len > c->rcvbuf.maxsize) {
895                 abort();
896         }
897
898         if(offset) {
899                 handle_out_of_order(c, offset, data, len);
900         } else {
901                 handle_in_order(c, data, len);
902         }
903 }
904
905
906 ssize_t utcp_recv(struct utcp *utcp, const void *data, size_t len) {
907         const uint8_t *ptr = data;
908
909         if(!utcp) {
910                 errno = EFAULT;
911                 return -1;
912         }
913
914         if(!len) {
915                 return 0;
916         }
917
918         if(!data) {
919                 errno = EFAULT;
920                 return -1;
921         }
922
923         print_packet(utcp, "recv", data, len);
924
925         // Drop packets smaller than the header
926
927         struct hdr hdr;
928
929         if(len < sizeof(hdr)) {
930                 errno = EBADMSG;
931                 return -1;
932         }
933
934         // Make a copy from the potentially unaligned data to a struct hdr
935
936         memcpy(&hdr, ptr, sizeof(hdr));
937         ptr += sizeof(hdr);
938         len -= sizeof(hdr);
939
940         // Drop packets with an unknown CTL flag
941
942         if(hdr.ctl & ~(SYN | ACK | RST | FIN)) {
943                 errno = EBADMSG;
944                 return -1;
945         }
946
947         // Check for auxiliary headers
948
949         const uint8_t *init = NULL;
950
951         uint16_t aux = hdr.aux;
952
953         while(aux) {
954                 size_t auxlen = 4 * (aux >> 8) & 0xf;
955                 uint8_t auxtype = aux & 0xff;
956
957                 if(len < auxlen) {
958                         errno = EBADMSG;
959                         return -1;
960                 }
961
962                 switch(auxtype) {
963                 case AUX_INIT:
964                         if(!(hdr.ctl & SYN) || auxlen != 4) {
965                                 errno = EBADMSG;
966                                 return -1;
967                         }
968
969                         init = ptr;
970                         break;
971
972                 default:
973                         errno = EBADMSG;
974                         return -1;
975                 }
976
977                 len -= auxlen;
978                 ptr += auxlen;
979
980                 if(!(aux & 0x800)) {
981                         break;
982                 }
983
984                 if(len < 2) {
985                         errno = EBADMSG;
986                         return -1;
987                 }
988
989                 memcpy(&aux, ptr, 2);
990                 len -= 2;
991                 ptr += 2;
992         }
993
994         // Try to match the packet to an existing connection
995
996         struct utcp_connection *c = find_connection(utcp, hdr.dst, hdr.src);
997
998         // Is it for a new connection?
999
1000         if(!c) {
1001                 // Ignore RST packets
1002
1003                 if(hdr.ctl & RST) {
1004                         return 0;
1005                 }
1006
1007                 // Is it a SYN packet and are we LISTENing?
1008
1009                 if(hdr.ctl & SYN && !(hdr.ctl & ACK) && utcp->accept) {
1010                         // If we don't want to accept it, send a RST back
1011                         if((utcp->pre_accept && !utcp->pre_accept(utcp, hdr.dst))) {
1012                                 len = 1;
1013                                 goto reset;
1014                         }
1015
1016                         // Try to allocate memory, otherwise send a RST back
1017                         c = allocate_connection(utcp, hdr.dst, hdr.src);
1018
1019                         if(!c) {
1020                                 len = 1;
1021                                 goto reset;
1022                         }
1023
1024                         // Parse auxilliary information
1025                         if(init) {
1026                                 if(init[0] < 1) {
1027                                         len = 1;
1028                                         goto reset;
1029                                 }
1030
1031                                 c->flags = init[3] & 0x7;
1032                         } else {
1033                                 c->flags = UTCP_TCP;
1034                         }
1035
1036                         // Return SYN+ACK, go to SYN_RECEIVED state
1037                         c->snd.wnd = hdr.wnd;
1038                         c->rcv.irs = hdr.seq;
1039                         c->rcv.nxt = c->rcv.irs + 1;
1040                         set_state(c, SYN_RECEIVED);
1041
1042                         struct {
1043                                 struct hdr hdr;
1044                                 uint8_t data[4];
1045                         } pkt;
1046
1047                         pkt.hdr.src = c->src;
1048                         pkt.hdr.dst = c->dst;
1049                         pkt.hdr.ack = c->rcv.irs + 1;
1050                         pkt.hdr.seq = c->snd.iss;
1051                         pkt.hdr.wnd = c->rcv.wnd;
1052                         pkt.hdr.ctl = SYN | ACK;
1053
1054                         if(init) {
1055                                 pkt.hdr.aux = 0x0101;
1056                                 pkt.data[0] = 1;
1057                                 pkt.data[1] = 0;
1058                                 pkt.data[2] = 0;
1059                                 pkt.data[3] = c->flags & 0x7;
1060                                 print_packet(c->utcp, "send", &pkt, sizeof(hdr) + 4);
1061                                 utcp->send(utcp, &pkt, sizeof(hdr) + 4);
1062                         } else {
1063                                 pkt.hdr.aux = 0;
1064                                 print_packet(c->utcp, "send", &pkt, sizeof(hdr));
1065                                 utcp->send(utcp, &pkt, sizeof(hdr));
1066                         }
1067                 } else {
1068                         // No, we don't want your packets, send a RST back
1069                         len = 1;
1070                         goto reset;
1071                 }
1072
1073                 return 0;
1074         }
1075
1076         debug("%p state %s\n", c->utcp, strstate[c->state]);
1077
1078         // In case this is for a CLOSED connection, ignore the packet.
1079         // TODO: make it so incoming packets can never match a CLOSED connection.
1080
1081         if(c->state == CLOSED) {
1082                 debug("Got packet for closed connection\n");
1083                 return 0;
1084         }
1085
1086         // It is for an existing connection.
1087
1088         uint32_t prevrcvnxt = c->rcv.nxt;
1089
1090         // 1. Drop invalid packets.
1091
1092         // 1a. Drop packets that should not happen in our current state.
1093
1094         switch(c->state) {
1095         case SYN_SENT:
1096         case SYN_RECEIVED:
1097         case ESTABLISHED:
1098         case FIN_WAIT_1:
1099         case FIN_WAIT_2:
1100         case CLOSE_WAIT:
1101         case CLOSING:
1102         case LAST_ACK:
1103         case TIME_WAIT:
1104                 break;
1105
1106         default:
1107 #ifdef UTCP_DEBUG
1108                 abort();
1109 #endif
1110                 break;
1111         }
1112
1113         // 1b. Drop packets with a sequence number not in our receive window.
1114
1115         bool acceptable;
1116
1117         if(c->state == SYN_SENT) {
1118                 acceptable = true;
1119         } else if(len == 0) {
1120                 acceptable = seqdiff(hdr.seq, c->rcv.nxt) >= 0;
1121         } else {
1122                 int32_t rcv_offset = seqdiff(hdr.seq, c->rcv.nxt);
1123
1124                 // cut already accepted front overlapping
1125                 if(rcv_offset < 0) {
1126                         acceptable = len > (size_t) - rcv_offset;
1127
1128                         if(acceptable) {
1129                                 ptr -= rcv_offset;
1130                                 len += rcv_offset;
1131                                 hdr.seq -= rcv_offset;
1132                         }
1133                 } else {
1134                         acceptable = seqdiff(hdr.seq, c->rcv.nxt) >= 0 && seqdiff(hdr.seq, c->rcv.nxt) + len <= c->rcvbuf.maxsize;
1135                 }
1136         }
1137
1138         if(!acceptable) {
1139                 debug("Packet not acceptable, %u <= %u + %lu < %u\n", c->rcv.nxt, hdr.seq, (unsigned long)len, c->rcv.nxt + c->rcvbuf.maxsize);
1140
1141                 // Ignore unacceptable RST packets.
1142                 if(hdr.ctl & RST) {
1143                         return 0;
1144                 }
1145
1146                 // Otherwise, continue processing.
1147                 len = 0;
1148         }
1149
1150         c->snd.wnd = hdr.wnd; // TODO: move below
1151
1152         // 1c. Drop packets with an invalid ACK.
1153         // ackno should not roll back, and it should also not be bigger than what we ever could have sent
1154         // (= snd.una + c->sndbuf.used).
1155
1156         if(hdr.ctl & ACK && (seqdiff(hdr.ack, c->snd.last) > 0 || seqdiff(hdr.ack, c->snd.una) < 0)) {
1157                 debug("Packet ack seqno out of range, %u <= %u < %u\n", c->snd.una, hdr.ack, c->snd.una + c->sndbuf.used);
1158
1159                 // Ignore unacceptable RST packets.
1160                 if(hdr.ctl & RST) {
1161                         return 0;
1162                 }
1163
1164                 goto reset;
1165         }
1166
1167         // 2. Handle RST packets
1168
1169         if(hdr.ctl & RST) {
1170                 switch(c->state) {
1171                 case SYN_SENT:
1172                         if(!(hdr.ctl & ACK)) {
1173                                 return 0;
1174                         }
1175
1176                         // The peer has refused our connection.
1177                         set_state(c, CLOSED);
1178                         errno = ECONNREFUSED;
1179
1180                         if(c->recv) {
1181                                 c->recv(c, NULL, 0);
1182                         }
1183
1184                         return 0;
1185
1186                 case SYN_RECEIVED:
1187                         if(hdr.ctl & ACK) {
1188                                 return 0;
1189                         }
1190
1191                         // We haven't told the application about this connection yet. Silently delete.
1192                         free_connection(c);
1193                         return 0;
1194
1195                 case ESTABLISHED:
1196                 case FIN_WAIT_1:
1197                 case FIN_WAIT_2:
1198                 case CLOSE_WAIT:
1199                         if(hdr.ctl & ACK) {
1200                                 return 0;
1201                         }
1202
1203                         // The peer has aborted our connection.
1204                         set_state(c, CLOSED);
1205                         errno = ECONNRESET;
1206
1207                         if(c->recv) {
1208                                 c->recv(c, NULL, 0);
1209                         }
1210
1211                         return 0;
1212
1213                 case CLOSING:
1214                 case LAST_ACK:
1215                 case TIME_WAIT:
1216                         if(hdr.ctl & ACK) {
1217                                 return 0;
1218                         }
1219
1220                         // As far as the application is concerned, the connection has already been closed.
1221                         // If it has called utcp_close() already, we can immediately free this connection.
1222                         if(c->reapable) {
1223                                 free_connection(c);
1224                                 return 0;
1225                         }
1226
1227                         // Otherwise, immediately move to the CLOSED state.
1228                         set_state(c, CLOSED);
1229                         return 0;
1230
1231                 default:
1232 #ifdef UTCP_DEBUG
1233                         abort();
1234 #endif
1235                         break;
1236                 }
1237         }
1238
1239         uint32_t advanced;
1240
1241         if(!(hdr.ctl & ACK)) {
1242                 advanced = 0;
1243                 goto skip_ack;
1244         }
1245
1246         // 3. Advance snd.una
1247
1248         advanced = seqdiff(hdr.ack, c->snd.una);
1249         prevrcvnxt = c->rcv.nxt;
1250
1251         if(advanced) {
1252                 // RTT measurement
1253                 if(c->rtt_start.tv_sec) {
1254                         if(c->rtt_seq == hdr.ack) {
1255                                 struct timeval now, diff;
1256                                 gettimeofday(&now, NULL);
1257                                 timersub(&now, &c->rtt_start, &diff);
1258                                 update_rtt(c, diff.tv_sec * 1000000 + diff.tv_usec);
1259                                 c->rtt_start.tv_sec = 0;
1260                         } else if(c->rtt_seq < hdr.ack) {
1261                                 debug("Cancelling RTT measurement: %u < %u\n", c->rtt_seq, hdr.ack);
1262                                 c->rtt_start.tv_sec = 0;
1263                         }
1264                 }
1265
1266                 int32_t data_acked = advanced;
1267
1268                 switch(c->state) {
1269                 case SYN_SENT:
1270                 case SYN_RECEIVED:
1271                         data_acked--;
1272                         break;
1273
1274                 // TODO: handle FIN as well.
1275                 default:
1276                         break;
1277                 }
1278
1279                 assert(data_acked >= 0);
1280
1281                 int32_t bufused = seqdiff(c->snd.last, c->snd.una);
1282                 assert(data_acked <= bufused);
1283
1284                 if(data_acked) {
1285                         buffer_get(&c->sndbuf, NULL, data_acked);
1286                 }
1287
1288                 // Also advance snd.nxt if possible
1289                 if(seqdiff(c->snd.nxt, hdr.ack) < 0) {
1290                         c->snd.nxt = hdr.ack;
1291                 }
1292
1293                 c->snd.una = hdr.ack;
1294
1295                 c->dupack = 0;
1296                 c->snd.cwnd += utcp->mtu;
1297
1298                 if(c->snd.cwnd > c->sndbuf.maxsize) {
1299                         c->snd.cwnd = c->sndbuf.maxsize;
1300                 }
1301
1302                 // Check if we have sent a FIN that is now ACKed.
1303                 switch(c->state) {
1304                 case FIN_WAIT_1:
1305                         if(c->snd.una == c->snd.last) {
1306                                 set_state(c, FIN_WAIT_2);
1307                         }
1308
1309                         break;
1310
1311                 case CLOSING:
1312                         if(c->snd.una == c->snd.last) {
1313                                 gettimeofday(&c->conn_timeout, NULL);
1314                                 c->conn_timeout.tv_sec += 60;
1315                                 set_state(c, TIME_WAIT);
1316                         }
1317
1318                         break;
1319
1320                 default:
1321                         break;
1322                 }
1323         } else {
1324                 if(!len && is_reliable(c)) {
1325                         c->dupack++;
1326
1327                         if(c->dupack == 3) {
1328                                 debug("Triplicate ACK\n");
1329                                 //TODO: Resend one packet and go to fast recovery mode. See RFC 6582.
1330                                 //We do a very simple variant here; reset the nxt pointer to the last acknowledged packet from the peer.
1331                                 //Reset the congestion window so we wait for ACKs.
1332                                 c->snd.nxt = c->snd.una;
1333                                 c->snd.cwnd = utcp->mtu;
1334                                 start_retransmit_timer(c);
1335                         }
1336                 }
1337         }
1338
1339         // 4. Update timers
1340
1341         if(advanced) {
1342                 if(c->snd.una == c->snd.last) {
1343                         stop_retransmit_timer(c);
1344                         timerclear(&c->conn_timeout);
1345                 } else if(is_reliable(c)) {
1346                         start_retransmit_timer(c);
1347                         gettimeofday(&c->conn_timeout, NULL);
1348                         c->conn_timeout.tv_sec += utcp->timeout;
1349                 }
1350         }
1351
1352 skip_ack:
1353         // 5. Process SYN stuff
1354
1355         if(hdr.ctl & SYN) {
1356                 switch(c->state) {
1357                 case SYN_SENT:
1358
1359                         // This is a SYNACK. It should always have ACKed the SYN.
1360                         if(!advanced) {
1361                                 goto reset;
1362                         }
1363
1364                         c->rcv.irs = hdr.seq;
1365                         c->rcv.nxt = hdr.seq;
1366
1367                         if(c->shut_wr) {
1368                                 c->snd.last++;
1369                                 set_state(c, FIN_WAIT_1);
1370                         } else {
1371                                 set_state(c, ESTABLISHED);
1372                         }
1373
1374                         // TODO: notify application of this somehow.
1375                         break;
1376
1377                 case SYN_RECEIVED:
1378                 case ESTABLISHED:
1379                 case FIN_WAIT_1:
1380                 case FIN_WAIT_2:
1381                 case CLOSE_WAIT:
1382                 case CLOSING:
1383                 case LAST_ACK:
1384                 case TIME_WAIT:
1385                         // Ehm, no. We should never receive a second SYN.
1386                         return 0;
1387
1388                 default:
1389 #ifdef UTCP_DEBUG
1390                         abort();
1391 #endif
1392                         return 0;
1393                 }
1394
1395                 // SYN counts as one sequence number
1396                 c->rcv.nxt++;
1397         }
1398
1399         // 6. Process new data
1400
1401         if(c->state == SYN_RECEIVED) {
1402                 // This is the ACK after the SYNACK. It should always have ACKed the SYNACK.
1403                 if(!advanced) {
1404                         goto reset;
1405                 }
1406
1407                 // Are we still LISTENing?
1408                 if(utcp->accept) {
1409                         utcp->accept(c, c->src);
1410                 }
1411
1412                 if(c->state != ESTABLISHED) {
1413                         set_state(c, CLOSED);
1414                         c->reapable = true;
1415                         goto reset;
1416                 }
1417         }
1418
1419         if(len) {
1420                 switch(c->state) {
1421                 case SYN_SENT:
1422                 case SYN_RECEIVED:
1423                         // This should never happen.
1424 #ifdef UTCP_DEBUG
1425                         abort();
1426 #endif
1427                         return 0;
1428
1429                 case ESTABLISHED:
1430                 case FIN_WAIT_1:
1431                 case FIN_WAIT_2:
1432                         break;
1433
1434                 case CLOSE_WAIT:
1435                 case CLOSING:
1436                 case LAST_ACK:
1437                 case TIME_WAIT:
1438                         // Ehm no, We should never receive more data after a FIN.
1439                         goto reset;
1440
1441                 default:
1442 #ifdef UTCP_DEBUG
1443                         abort();
1444 #endif
1445                         return 0;
1446                 }
1447
1448                 handle_incoming_data(c, hdr.seq, ptr, len);
1449         }
1450
1451         // 7. Process FIN stuff
1452
1453         if((hdr.ctl & FIN) && hdr.seq + len == c->rcv.nxt) {
1454                 switch(c->state) {
1455                 case SYN_SENT:
1456                 case SYN_RECEIVED:
1457                         // This should never happen.
1458 #ifdef UTCP_DEBUG
1459                         abort();
1460 #endif
1461                         break;
1462
1463                 case ESTABLISHED:
1464                         set_state(c, CLOSE_WAIT);
1465                         break;
1466
1467                 case FIN_WAIT_1:
1468                         set_state(c, CLOSING);
1469                         break;
1470
1471                 case FIN_WAIT_2:
1472                         gettimeofday(&c->conn_timeout, NULL);
1473                         c->conn_timeout.tv_sec += 60;
1474                         set_state(c, TIME_WAIT);
1475                         break;
1476
1477                 case CLOSE_WAIT:
1478                 case CLOSING:
1479                 case LAST_ACK:
1480                 case TIME_WAIT:
1481                         // Ehm, no. We should never receive a second FIN.
1482                         goto reset;
1483
1484                 default:
1485 #ifdef UTCP_DEBUG
1486                         abort();
1487 #endif
1488                         break;
1489                 }
1490
1491                 // FIN counts as one sequence number
1492                 c->rcv.nxt++;
1493                 len++;
1494
1495                 // Inform the application that the peer closed the connection.
1496                 if(c->recv) {
1497                         errno = 0;
1498                         c->recv(c, NULL, 0);
1499                 }
1500         }
1501
1502         // Now we send something back if:
1503         // - we advanced rcv.nxt (ie, we got some data that needs to be ACKed)
1504         //   -> sendatleastone = true
1505         // - or we got an ack, so we should maybe send a bit more data
1506         //   -> sendatleastone = false
1507
1508         ack(c, len || prevrcvnxt != c->rcv.nxt);
1509         return 0;
1510
1511 reset:
1512         swap_ports(&hdr);
1513         hdr.wnd = 0;
1514         hdr.aux = 0;
1515
1516         if(hdr.ctl & ACK) {
1517                 hdr.seq = hdr.ack;
1518                 hdr.ctl = RST;
1519         } else {
1520                 hdr.ack = hdr.seq + len;
1521                 hdr.seq = 0;
1522                 hdr.ctl = RST | ACK;
1523         }
1524
1525         print_packet(utcp, "send", &hdr, sizeof(hdr));
1526         utcp->send(utcp, &hdr, sizeof(hdr));
1527         return 0;
1528
1529 }
1530
1531 int utcp_shutdown(struct utcp_connection *c, int dir) {
1532         debug("%p shutdown %d at %u\n", c ? c->utcp : NULL, dir, c ? c->snd.last : 0);
1533
1534         if(!c) {
1535                 errno = EFAULT;
1536                 return -1;
1537         }
1538
1539         if(c->reapable) {
1540                 debug("Error: shutdown() called on closed connection %p\n", c);
1541                 errno = EBADF;
1542                 return -1;
1543         }
1544
1545         if(!(dir == UTCP_SHUT_RD || dir == UTCP_SHUT_WR || dir == UTCP_SHUT_RDWR)) {
1546                 errno = EINVAL;
1547                 return -1;
1548         }
1549
1550         // TCP does not have a provision for stopping incoming packets.
1551         // The best we can do is to just ignore them.
1552         if(dir == UTCP_SHUT_RD || dir == UTCP_SHUT_RDWR) {
1553                 c->recv = NULL;
1554         }
1555
1556         // The rest of the code deals with shutting down writes.
1557         if(dir == UTCP_SHUT_RD) {
1558                 return 0;
1559         }
1560
1561         // Only process shutting down writes once.
1562         if(c->shut_wr) {
1563                 return 0;
1564         }
1565
1566         c->shut_wr = true;
1567
1568         switch(c->state) {
1569         case CLOSED:
1570         case LISTEN:
1571                 errno = ENOTCONN;
1572                 return -1;
1573
1574         case SYN_SENT:
1575                 return 0;
1576
1577         case SYN_RECEIVED:
1578         case ESTABLISHED:
1579                 set_state(c, FIN_WAIT_1);
1580                 break;
1581
1582         case FIN_WAIT_1:
1583         case FIN_WAIT_2:
1584                 return 0;
1585
1586         case CLOSE_WAIT:
1587                 set_state(c, CLOSING);
1588                 break;
1589
1590         case CLOSING:
1591         case LAST_ACK:
1592         case TIME_WAIT:
1593                 return 0;
1594         }
1595
1596         c->snd.last++;
1597
1598         ack(c, false);
1599
1600         if(!timerisset(&c->rtrx_timeout)) {
1601                 start_retransmit_timer(c);
1602         }
1603
1604         return 0;
1605 }
1606
1607 static bool reset_connection(struct utcp_connection *c) {
1608         if(!c) {
1609                 errno = EFAULT;
1610                 return false;
1611         }
1612
1613         if(c->reapable) {
1614                 debug("Error: abort() called on closed connection %p\n", c);
1615                 errno = EBADF;
1616                 return false;
1617         }
1618
1619         c->recv = NULL;
1620         c->poll = NULL;
1621
1622         switch(c->state) {
1623         case CLOSED:
1624                 return true;
1625
1626         case LISTEN:
1627         case SYN_SENT:
1628         case CLOSING:
1629         case LAST_ACK:
1630         case TIME_WAIT:
1631                 set_state(c, CLOSED);
1632                 return true;
1633
1634         case SYN_RECEIVED:
1635         case ESTABLISHED:
1636         case FIN_WAIT_1:
1637         case FIN_WAIT_2:
1638         case CLOSE_WAIT:
1639                 set_state(c, CLOSED);
1640                 break;
1641         }
1642
1643         // Send RST
1644
1645         struct hdr hdr;
1646
1647         hdr.src = c->src;
1648         hdr.dst = c->dst;
1649         hdr.seq = c->snd.nxt;
1650         hdr.ack = 0;
1651         hdr.wnd = 0;
1652         hdr.ctl = RST;
1653
1654         print_packet(c->utcp, "send", &hdr, sizeof(hdr));
1655         c->utcp->send(c->utcp, &hdr, sizeof(hdr));
1656         return true;
1657 }
1658
1659 // Closes all the opened connections
1660 void utcp_abort_all_connections(struct utcp *utcp) {
1661         if(!utcp) {
1662                 errno = EINVAL;
1663                 return;
1664         }
1665
1666         for(int i = 0; i < utcp->nconnections; i++) {
1667                 struct utcp_connection *c = utcp->connections[i];
1668
1669                 if(c->reapable || c->state == CLOSED) {
1670                         continue;
1671                 }
1672
1673                 utcp_recv_t old_recv = c->recv;
1674
1675                 reset_connection(c);
1676
1677                 if(old_recv) {
1678                         errno = 0;
1679                         old_recv(c, NULL, 0);
1680                 }
1681         }
1682
1683         return;
1684 }
1685
1686 int utcp_close(struct utcp_connection *c) {
1687         if(utcp_shutdown(c, SHUT_RDWR) && errno != ENOTCONN) {
1688                 return -1;
1689         }
1690
1691         c->recv = NULL;
1692         c->poll = NULL;
1693         c->reapable = true;
1694         return 0;
1695 }
1696
1697 int utcp_abort(struct utcp_connection *c) {
1698         if(!reset_connection(c)) {
1699                 return -1;
1700         }
1701
1702         c->reapable = true;
1703         return 0;
1704 }
1705
1706 /* Handle timeouts.
1707  * One call to this function will loop through all connections,
1708  * checking if something needs to be resent or not.
1709  * The return value is the time to the next timeout in milliseconds,
1710  * or maybe a negative value if the timeout is infinite.
1711  */
1712 struct timeval utcp_timeout(struct utcp *utcp) {
1713         struct timeval now;
1714         gettimeofday(&now, NULL);
1715         struct timeval next = {now.tv_sec + 3600, now.tv_usec};
1716
1717         for(int i = 0; i < utcp->nconnections; i++) {
1718                 struct utcp_connection *c = utcp->connections[i];
1719
1720                 if(!c) {
1721                         continue;
1722                 }
1723
1724                 // delete connections that have been utcp_close()d.
1725                 if(c->state == CLOSED) {
1726                         if(c->reapable) {
1727                                 debug("Reaping %p\n", c);
1728                                 free_connection(c);
1729                                 i--;
1730                         }
1731
1732                         continue;
1733                 }
1734
1735                 if(timerisset(&c->conn_timeout) && timercmp(&c->conn_timeout, &now, <)) {
1736                         errno = ETIMEDOUT;
1737                         c->state = CLOSED;
1738
1739                         if(c->recv) {
1740                                 c->recv(c, NULL, 0);
1741                         }
1742
1743                         if(c->poll) {
1744                                 c->poll(c, 0);
1745                         }
1746
1747                         continue;
1748                 }
1749
1750                 if(timerisset(&c->rtrx_timeout) && timercmp(&c->rtrx_timeout, &now, <)) {
1751                         debug("retransmit()\n");
1752                         retransmit(c);
1753                 }
1754
1755                 if(c->poll) {
1756                         if((c->state == ESTABLISHED || c->state == CLOSE_WAIT)) {
1757                                 uint32_t len =  buffer_free(&c->sndbuf);
1758
1759                                 if(len) {
1760                                         c->poll(c, len);
1761                                 }
1762                         } else if(c->state == CLOSED) {
1763                                 c->poll(c, 0);
1764                         }
1765                 }
1766
1767                 if(timerisset(&c->conn_timeout) && timercmp(&c->conn_timeout, &next, <)) {
1768                         next = c->conn_timeout;
1769                 }
1770
1771                 if(timerisset(&c->rtrx_timeout) && timercmp(&c->rtrx_timeout, &next, <)) {
1772                         next = c->rtrx_timeout;
1773                 }
1774         }
1775
1776         struct timeval diff;
1777
1778         timersub(&next, &now, &diff);
1779
1780         return diff;
1781 }
1782
1783 bool utcp_is_active(struct utcp *utcp) {
1784         if(!utcp) {
1785                 return false;
1786         }
1787
1788         for(int i = 0; i < utcp->nconnections; i++)
1789                 if(utcp->connections[i]->state != CLOSED && utcp->connections[i]->state != TIME_WAIT) {
1790                         return true;
1791                 }
1792
1793         return false;
1794 }
1795
1796 struct utcp *utcp_init(utcp_accept_t accept, utcp_pre_accept_t pre_accept, utcp_send_t send, void *priv) {
1797         if(!send) {
1798                 errno = EFAULT;
1799                 return NULL;
1800         }
1801
1802         struct utcp *utcp = calloc(1, sizeof(*utcp));
1803
1804         if(!utcp) {
1805                 return NULL;
1806         }
1807
1808         utcp->accept = accept;
1809         utcp->pre_accept = pre_accept;
1810         utcp->send = send;
1811         utcp->priv = priv;
1812         utcp->mtu = DEFAULT_MTU;
1813         utcp->timeout = DEFAULT_USER_TIMEOUT; // sec
1814         utcp->rto = START_RTO; // usec
1815
1816         return utcp;
1817 }
1818
1819 void utcp_exit(struct utcp *utcp) {
1820         if(!utcp) {
1821                 return;
1822         }
1823
1824         for(int i = 0; i < utcp->nconnections; i++) {
1825                 struct utcp_connection *c = utcp->connections[i];
1826
1827                 if(!c->reapable)
1828                         if(c->recv) {
1829                                 c->recv(c, NULL, 0);
1830                         }
1831
1832                 buffer_exit(&c->rcvbuf);
1833                 buffer_exit(&c->sndbuf);
1834                 free(c);
1835         }
1836
1837         free(utcp->connections);
1838         free(utcp);
1839 }
1840
1841 uint16_t utcp_get_mtu(struct utcp *utcp) {
1842         return utcp ? utcp->mtu : 0;
1843 }
1844
1845 void utcp_set_mtu(struct utcp *utcp, uint16_t mtu) {
1846         // TODO: handle overhead of the header
1847         if(utcp) {
1848                 utcp->mtu = mtu;
1849         }
1850 }
1851
1852 void utcp_reset_timers(struct utcp *utcp) {
1853         if(!utcp) {
1854                 return;
1855         }
1856
1857         struct timeval now, then;
1858
1859         gettimeofday(&now, NULL);
1860
1861         then = now;
1862
1863         then.tv_sec += utcp->timeout;
1864
1865         for(int i = 0; i < utcp->nconnections; i++) {
1866                 struct utcp_connection *c = utcp->connections[i];
1867
1868                 if(c->reapable) {
1869                         continue;
1870                 }
1871
1872                 c->rtrx_timeout = now;
1873                 c->conn_timeout = then;
1874                 c->rtt_start.tv_sec = 0;
1875         }
1876
1877         if(utcp->rto > START_RTO) {
1878                 utcp->rto = START_RTO;
1879         }
1880 }
1881
1882 int utcp_get_user_timeout(struct utcp *u) {
1883         return u ? u->timeout : 0;
1884 }
1885
1886 void utcp_set_user_timeout(struct utcp *u, int timeout) {
1887         if(u) {
1888                 u->timeout = timeout;
1889         }
1890 }
1891
1892 size_t utcp_get_sndbuf(struct utcp_connection *c) {
1893         return c ? c->sndbuf.maxsize : 0;
1894 }
1895
1896 size_t utcp_get_sndbuf_free(struct utcp_connection *c) {
1897         if(!c) {
1898                 return 0;
1899         }
1900
1901         switch(c->state) {
1902         case SYN_SENT:
1903         case SYN_RECEIVED:
1904         case ESTABLISHED:
1905         case CLOSE_WAIT:
1906                 return buffer_free(&c->sndbuf);
1907
1908         default:
1909                 return 0;
1910         }
1911 }
1912
1913 void utcp_set_sndbuf(struct utcp_connection *c, size_t size) {
1914         if(!c) {
1915                 return;
1916         }
1917
1918         c->sndbuf.maxsize = size;
1919
1920         if(c->sndbuf.maxsize != size) {
1921                 c->sndbuf.maxsize = -1;
1922         }
1923 }
1924
1925 size_t utcp_get_rcvbuf(struct utcp_connection *c) {
1926         return c ? c->rcvbuf.maxsize : 0;
1927 }
1928
1929 size_t utcp_get_rcvbuf_free(struct utcp_connection *c) {
1930         if(c && (c->state == ESTABLISHED || c->state == CLOSE_WAIT)) {
1931                 return buffer_free(&c->rcvbuf);
1932         } else {
1933                 return 0;
1934         }
1935 }
1936
1937 void utcp_set_rcvbuf(struct utcp_connection *c, size_t size) {
1938         if(!c) {
1939                 return;
1940         }
1941
1942         c->rcvbuf.maxsize = size;
1943
1944         if(c->rcvbuf.maxsize != size) {
1945                 c->rcvbuf.maxsize = -1;
1946         }
1947 }
1948
1949 size_t utcp_get_sendq(struct utcp_connection *c) {
1950         return c->sndbuf.used;
1951 }
1952
1953 size_t utcp_get_recvq(struct utcp_connection *c) {
1954         return c->rcvbuf.used;
1955 }
1956
1957 bool utcp_get_nodelay(struct utcp_connection *c) {
1958         return c ? c->nodelay : false;
1959 }
1960
1961 void utcp_set_nodelay(struct utcp_connection *c, bool nodelay) {
1962         if(c) {
1963                 c->nodelay = nodelay;
1964         }
1965 }
1966
1967 bool utcp_get_keepalive(struct utcp_connection *c) {
1968         return c ? c->keepalive : false;
1969 }
1970
1971 void utcp_set_keepalive(struct utcp_connection *c, bool keepalive) {
1972         if(c) {
1973                 c->keepalive = keepalive;
1974         }
1975 }
1976
1977 size_t utcp_get_outq(struct utcp_connection *c) {
1978         return c ? seqdiff(c->snd.nxt, c->snd.una) : 0;
1979 }
1980
1981 void utcp_set_recv_cb(struct utcp_connection *c, utcp_recv_t recv) {
1982         if(c) {
1983                 c->recv = recv;
1984         }
1985 }
1986
1987 void utcp_set_poll_cb(struct utcp_connection *c, utcp_poll_t poll) {
1988         if(c) {
1989                 c->poll = poll;
1990         }
1991 }
1992
1993 void utcp_set_accept_cb(struct utcp *utcp, utcp_accept_t accept, utcp_pre_accept_t pre_accept) {
1994         if(utcp) {
1995                 utcp->accept = accept;
1996                 utcp->pre_accept = pre_accept;
1997         }
1998 }
1999
2000 void utcp_expect_data(struct utcp_connection *c, bool expect) {
2001         if(!c || c->reapable) {
2002                 return;
2003         }
2004
2005         if(!(c->state == ESTABLISHED || c->state == FIN_WAIT_1 || c->state == FIN_WAIT_2)) {
2006                 return;
2007         }
2008
2009         if(expect) {
2010                 // If we expect data, start the connection timer.
2011                 if(!timerisset(&c->conn_timeout)) {
2012                         gettimeofday(&c->conn_timeout, NULL);
2013                         c->conn_timeout.tv_sec += c->utcp->timeout;
2014                 }
2015         } else {
2016                 // If we want to cancel expecting data, only clear the timer when there is no unACKed data.
2017                 if(c->snd.una == c->snd.last) {
2018                         timerclear(&c->conn_timeout);
2019                 }
2020         }
2021 }
2022
2023 void utcp_offline(struct utcp *utcp, bool offline) {
2024         for(int i = 0; i < utcp->nconnections; i++) {
2025                 struct utcp_connection *c = utcp->connections[i];
2026
2027                 if(!c->reapable) {
2028                         utcp_expect_data(c, offline);
2029
2030                         // If we are online again, reset the retransmission timers, but keep the connection timeout as it is,
2031                         // to prevent peers toggling online/offline state frequently from keeping connections alive
2032                         // if there is no progress in sending actual data.
2033                         if(!offline) {
2034                                 gettimeofday(&utcp->connections[i]->rtrx_timeout, NULL);
2035                                 utcp->connections[i]->rtt_start.tv_sec = 0;
2036                         }
2037                 }
2038         }
2039
2040         if(!offline && utcp->rto > START_RTO) {
2041                 utcp->rto = START_RTO;
2042         }
2043 }