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