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