git.meshlink.io Git - utcp/blob - utcp.c

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