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