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

   1 /*
   2     utcp.c -- Userspace TCP
   3     Copyright (C) 2014-2017 Guus Sliepen <guus@tinc-vpn.org>
   4
   5     This program is free software; you can redistribute it and/or modify
   6     it under the terms of the GNU General Public License as published by
   7     the Free Software Foundation; either version 2 of the License, or
   8     (at your option) any later version.
   9
  10     This program is distributed in the hope that it will be useful,
  11     but WITHOUT ANY WARRANTY; without even the implied warranty of
  12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13     GNU General Public License for more details.
  14
  15     You should have received a copy of the GNU General Public License along
  16     with this program; if not, write to the Free Software Foundation, Inc.,
  17     51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18 */
  19
  20 #define _GNU_SOURCE
  21
  22 #include <assert.h>
  23 #include <errno.h>
  24 #include <stdio.h>
  25 #include <stdlib.h>
  26 #include <stdint.h>
  27 #include <stdbool.h>
  28 #include <string.h>
  29 #include <unistd.h>
  30 #include <sys/time.h>
  31 #include <sys/socket.h>
  32 #include <time.h>
  33
  34 #include "utcp_priv.h"
  35
  36 #ifndef EBADMSG
  37 #define EBADMSG         104
  38 #endif
  39
  40 #ifndef SHUT_RDWR
  41 #define SHUT_RDWR 2
  42 #endif
  43
  44 #ifdef poll
  45 #undef poll
  46 #endif
  47
  48 #ifndef timersub
  49 #define timersub(a, b, r)\
  50         do {\
  51                 (r)->tv_sec = (a)->tv_sec - (b)->tv_sec;\
  52                 (r)->tv_usec = (a)->tv_usec - (b)->tv_usec;\
  53                 if((r)->tv_usec < 0)\
  54                         (r)->tv_sec--, (r)->tv_usec += USEC_PER_SEC;\
  55         } while (0)
  56 #endif
  57
  58 static inline size_t min(size_t a, size_t b) {
  59         return a < b ? a : b;
  60 }
  61
  62 static inline size_t max(size_t a, size_t b) {
  63         return a > b ? a : b;
  64 }
  65
  66 #ifdef UTCP_DEBUG
  67 #include <stdarg.h>
  68
  69 #ifndef UTCP_DEBUG_DATALEN
  70 #define UTCP_DEBUG_DATALEN 20
  71 #endif
  72
  73 static void debug(struct utcp_connection *c, const char *format, ...) {
  74         struct timespec tv;
  75         char buf[1024];
  76         int len;
  77
  78         clock_gettime(CLOCK_REALTIME, &tv);
  79         len = snprintf(buf, sizeof(buf), "%ld.%06lu %u:%u ", (long)tv.tv_sec, tv.tv_nsec / 1000, c ? c->src : 0, c ? c->dst : 0);
  80         va_list ap;
  81         va_start(ap, format);
  82         len += vsnprintf(buf + len, sizeof(buf) - len, format, ap);
  83         va_end(ap);
  84
  85         if(len > 0 && (size_t)len < sizeof(buf)) {
  86                 fwrite(buf, len, 1, stderr);
  87         }
  88 }
  89
  90 static void print_packet(struct utcp_connection *c, const char *dir, const void *pkt, size_t len) {
  91         struct hdr hdr;
  92
  93         if(len < sizeof(hdr)) {
  94                 debug(c, "%s: short packet (%lu bytes)\n", dir, (unsigned long)len);
  95                 return;
  96         }
  97
  98         memcpy(&hdr, pkt, sizeof(hdr));
  99
 100         uint32_t datalen;
 101
 102         if(len > sizeof(hdr)) {
 103                 datalen = min(len - sizeof(hdr), UTCP_DEBUG_DATALEN);
 104         } else {
 105                 datalen = 0;
 106         }
 107
 108
 109         const uint8_t *data = (uint8_t *)pkt + sizeof(hdr);
 110         char str[datalen * 2 + 1];
 111         char *p = str;
 112
 113         for(uint32_t i = 0; i < datalen; i++) {
 114                 *p++ = "0123456789ABCDEF"[data[i] >> 4];
 115                 *p++ = "0123456789ABCDEF"[data[i] & 15];
 116         }
 117
 118         *p = 0;
 119
 120         debug(c, "%s: len %lu src %u dst %u seq %u ack %u wnd %u aux %x ctl %s%s%s%s data %s\n",
 121               dir, (unsigned long)len, hdr.src, hdr.dst, hdr.seq, hdr.ack, hdr.wnd, hdr.aux,
 122               hdr.ctl & SYN ? "SYN" : "",
 123               hdr.ctl & RST ? "RST" : "",
 124               hdr.ctl & FIN ? "FIN" : "",
 125               hdr.ctl & ACK ? "ACK" : "",
 126               str
 127              );
 128 }
 129
 130 static void debug_cwnd(struct utcp_connection *c) {
 131         debug(c, "snd.cwnd %u snd.ssthresh %u\n", c->snd.cwnd, ~c->snd.ssthresh ? c->snd.ssthresh : 0);
 132 }
 133 #else
 134 #define debug(...) do {} while(0)
 135 #define print_packet(...) do {} while(0)
 136 #define debug_cwnd(...) do {} while(0)
 137 #endif
 138
 139 static void set_state(struct utcp_connection *c, enum state state) {
 140         c->state = state;
 141
 142         if(state == ESTABLISHED) {
 143                 timerclear(&c->conn_timeout);
 144         }
 145
 146         debug(c, "state %s\n", strstate[state]);
 147 }
 148
 149 static bool fin_wanted(struct utcp_connection *c, uint32_t seq) {
 150         if(seq != c->snd.last) {
 151                 return false;
 152         }
 153
 154         switch(c->state) {
 155         case FIN_WAIT_1:
 156         case CLOSING:
 157         case LAST_ACK:
 158                 return true;
 159
 160         default:
 161                 return false;
 162         }
 163 }
 164
 165 static bool is_reliable(struct utcp_connection *c) {
 166         return c->flags & UTCP_RELIABLE;
 167 }
 168
 169 static int32_t seqdiff(uint32_t a, uint32_t b) {
 170         return a - b;
 171 }
 172
 173 // Buffer functions
 174 // TODO: convert to ringbuffers to avoid memmove() operations.
 175
 176 // Store data into the buffer
 177 static ssize_t buffer_put_at(struct buffer *buf, size_t offset, const void *data, size_t len) {
 178         debug(NULL, "buffer_put_at %lu %lu %lu\n", (unsigned long)buf->used, (unsigned long)offset, (unsigned long)len);
 179
 180         size_t required = offset + len;
 181
 182         if(required > buf->maxsize) {
 183                 if(offset >= buf->maxsize) {
 184                         return 0;
 185                 }
 186
 187                 len = buf->maxsize - offset;
 188                 required = buf->maxsize;
 189         }
 190
 191         if(required > buf->size) {
 192                 size_t newsize = buf->size;
 193
 194                 if(!newsize) {
 195                         newsize = required;
 196                 } else {
 197                         do {
 198                                 newsize *= 2;
 199                         } while(newsize < required);
 200                 }
 201
 202                 if(newsize > buf->maxsize) {
 203                         newsize = buf->maxsize;
 204                 }
 205
 206                 char *newdata = realloc(buf->data, newsize);
 207
 208                 if(!newdata) {
 209                         return -1;
 210                 }
 211
 212                 buf->data = newdata;
 213                 buf->size = newsize;
 214         }
 215
 216         memcpy(buf->data + offset, data, len);
 217
 218         if(required > buf->used) {
 219                 buf->used = required;
 220         }
 221
 222         return len;
 223 }
 224
 225 static ssize_t buffer_put(struct buffer *buf, const void *data, size_t len) {
 226         return buffer_put_at(buf, buf->used, data, len);
 227 }
 228
 229 // Get data from the buffer. data can be NULL.
 230 static ssize_t buffer_get(struct buffer *buf, void *data, size_t len) {
 231         if(len > buf->used) {
 232                 len = buf->used;
 233         }
 234
 235         if(data) {
 236                 memcpy(data, buf->data, len);
 237         }
 238
 239         if(len < buf->used) {
 240                 memmove(buf->data, buf->data + len, buf->used - len);
 241         }
 242
 243         buf->used -= len;
 244         return len;
 245 }
 246
 247 // Copy data from the buffer without removing it.
 248 static ssize_t buffer_copy(struct buffer *buf, void *data, size_t offset, size_t len) {
 249         if(offset >= buf->used) {
 250                 return 0;
 251         }
 252
 253         if(offset + len > buf->used) {
 254                 len = buf->used - offset;
 255         }
 256
 257         memcpy(data, buf->data + offset, len);
 258         return len;
 259 }
 260
 261 static bool buffer_init(struct buffer *buf, uint32_t len, uint32_t maxlen) {
 262         memset(buf, 0, sizeof(*buf));
 263
 264         if(len) {
 265                 buf->data = malloc(len);
 266
 267                 if(!buf->data) {
 268                         return false;
 269                 }
 270         }
 271
 272         buf->size = len;
 273         buf->maxsize = maxlen;
 274         return true;
 275 }
 276
 277 static void buffer_exit(struct buffer *buf) {
 278         free(buf->data);
 279         memset(buf, 0, sizeof(*buf));
 280 }
 281
 282 static uint32_t buffer_free(const struct buffer *buf) {
 283         return buf->maxsize - buf->used;
 284 }
 285
 286 // Connections are stored in a sorted list.
 287 // This gives O(log(N)) lookup time, O(N log(N)) insertion time and O(N) deletion time.
 288
 289 static int compare(const void *va, const void *vb) {
 290         assert(va && vb);
 291
 292         const struct utcp_connection *a = *(struct utcp_connection **)va;
 293         const struct utcp_connection *b = *(struct utcp_connection **)vb;
 294
 295         assert(a && b);
 296         assert(a->src && b->src);
 297
 298         int c = (int)a->src - (int)b->src;
 299
 300         if(c) {
 301                 return c;
 302         }
 303
 304         c = (int)a->dst - (int)b->dst;
 305         return c;
 306 }
 307
 308 static struct utcp_connection *find_connection(const struct utcp *utcp, uint16_t src, uint16_t dst) {
 309         if(!utcp->nconnections) {
 310                 return NULL;
 311         }
 312
 313         struct utcp_connection key = {
 314                 .src = src,
 315                 .dst = dst,
 316         }, *keyp = &key;
 317         struct utcp_connection **match = bsearch(&keyp, utcp->connections, utcp->nconnections, sizeof(*utcp->connections), compare);
 318         return match ? *match : NULL;
 319 }
 320
 321 static void free_connection(struct utcp_connection *c) {
 322         struct utcp *utcp = c->utcp;
 323         struct utcp_connection **cp = bsearch(&c, utcp->connections, utcp->nconnections, sizeof(*utcp->connections), compare);
 324
 325         assert(cp);
 326
 327         int i = cp - utcp->connections;
 328         memmove(cp, cp + 1, (utcp->nconnections - i - 1) * sizeof(*cp));
 329         utcp->nconnections--;
 330
 331         buffer_exit(&c->rcvbuf);
 332         buffer_exit(&c->sndbuf);
 333         free(c);
 334 }
 335
 336 static struct utcp_connection *allocate_connection(struct utcp *utcp, uint16_t src, uint16_t dst) {
 337         // Check whether this combination of src and dst is free
 338
 339         if(src) {
 340                 if(find_connection(utcp, src, dst)) {
 341                         errno = EADDRINUSE;
 342                         return NULL;
 343                 }
 344         } else { // If src == 0, generate a random port number with the high bit set
 345                 if(utcp->nconnections >= 32767) {
 346                         errno = ENOMEM;
 347                         return NULL;
 348                 }
 349
 350                 src = rand() | 0x8000;
 351
 352                 while(find_connection(utcp, src, dst)) {
 353                         src++;
 354                 }
 355         }
 356
 357         // Allocate memory for the new connection
 358
 359         if(utcp->nconnections >= utcp->nallocated) {
 360                 if(!utcp->nallocated) {
 361                         utcp->nallocated = 4;
 362                 } else {
 363                         utcp->nallocated *= 2;
 364                 }
 365
 366                 struct utcp_connection **new_array = realloc(utcp->connections, utcp->nallocated * sizeof(*utcp->connections));
 367
 368                 if(!new_array) {
 369                         return NULL;
 370                 }
 371
 372                 utcp->connections = new_array;
 373         }
 374
 375         struct utcp_connection *c = calloc(1, sizeof(*c));
 376
 377         if(!c) {
 378                 return NULL;
 379         }
 380
 381         if(!buffer_init(&c->sndbuf, DEFAULT_SNDBUFSIZE, DEFAULT_MAXSNDBUFSIZE)) {
 382                 free(c);
 383                 return NULL;
 384         }
 385
 386         if(!buffer_init(&c->rcvbuf, DEFAULT_RCVBUFSIZE, DEFAULT_MAXRCVBUFSIZE)) {
 387                 buffer_exit(&c->sndbuf);
 388                 free(c);
 389                 return NULL;
 390         }
 391
 392         // Fill in the details
 393
 394         c->src = src;
 395         c->dst = dst;
 396 #ifdef UTCP_DEBUG
 397         c->snd.iss = 0;
 398 #else
 399         c->snd.iss = rand();
 400 #endif
 401         c->snd.una = c->snd.iss;
 402         c->snd.nxt = c->snd.iss + 1;
 403         c->snd.last = c->snd.nxt;
 404         c->snd.cwnd = (utcp->mtu > 2190 ? 2 : utcp->mtu > 1095 ? 3 : 4) * utcp->mtu;
 405         c->snd.ssthresh = ~0;
 406         debug_cwnd(c);
 407         c->utcp = utcp;
 408
 409         // Add it to the sorted list of connections
 410
 411         utcp->connections[utcp->nconnections++] = c;
 412         qsort(utcp->connections, utcp->nconnections, sizeof(*utcp->connections), compare);
 413
 414         return c;
 415 }
 416
 417 static inline uint32_t absdiff(uint32_t a, uint32_t b) {
 418         if(a > b) {
 419                 return a - b;
 420         } else {
 421                 return b - a;
 422         }
 423 }
 424
 425 // Update RTT variables. See RFC 6298.
 426 static void update_rtt(struct utcp_connection *c, uint32_t rtt) {
 427         if(!rtt) {
 428                 debug(c, "invalid rtt\n");
 429                 return;
 430         }
 431
 432         struct utcp *utcp = c->utcp;
 433
 434         if(!utcp->srtt) {
 435                 utcp->srtt = rtt;
 436                 utcp->rttvar = rtt / 2;
 437         } else {
 438                 utcp->rttvar = (utcp->rttvar * 3 + absdiff(utcp->srtt, rtt)) / 4;
 439                 utcp->srtt = (utcp->srtt * 7 + rtt) / 8;
 440         }
 441
 442         utcp->rto = utcp->srtt + max(4 * utcp->rttvar, CLOCK_GRANULARITY);
 443
 444         if(utcp->rto > MAX_RTO) {
 445                 utcp->rto = MAX_RTO;
 446         }
 447
 448         debug(c, "rtt %u srtt %u rttvar %u rto %u\n", rtt, utcp->srtt, utcp->rttvar, utcp->rto);
 449 }
 450
 451 static void start_retransmit_timer(struct utcp_connection *c) {
 452         gettimeofday(&c->rtrx_timeout, NULL);
 453         c->rtrx_timeout.tv_usec += c->utcp->rto;
 454
 455         while(c->rtrx_timeout.tv_usec >= 1000000) {
 456                 c->rtrx_timeout.tv_usec -= 1000000;
 457                 c->rtrx_timeout.tv_sec++;
 458         }
 459
 460         debug(c, "rtrx_timeout %ld.%06lu\n", c->rtrx_timeout.tv_sec, c->rtrx_timeout.tv_usec);
 461 }
 462
 463 static void stop_retransmit_timer(struct utcp_connection *c) {
 464         timerclear(&c->rtrx_timeout);
 465         debug(c, "rtrx_timeout cleared\n");
 466 }
 467
 468 struct utcp_connection *utcp_connect_ex(struct utcp *utcp, uint16_t dst, utcp_recv_t recv, void *priv, uint32_t flags) {
 469         struct utcp_connection *c = allocate_connection(utcp, 0, dst);
 470
 471         if(!c) {
 472                 return NULL;
 473         }
 474
 475         assert((flags & ~0x1f) == 0);
 476
 477         c->flags = flags;
 478         c->recv = recv;
 479         c->priv = priv;
 480
 481         struct {
 482                 struct hdr hdr;
 483                 uint8_t init[4];
 484         } pkt;
 485
 486         pkt.hdr.src = c->src;
 487         pkt.hdr.dst = c->dst;
 488         pkt.hdr.seq = c->snd.iss;
 489         pkt.hdr.ack = 0;
 490         pkt.hdr.wnd = c->rcvbuf.maxsize;
 491         pkt.hdr.ctl = SYN;
 492         pkt.hdr.aux = 0x0101;
 493         pkt.init[0] = 1;
 494         pkt.init[1] = 0;
 495         pkt.init[2] = 0;
 496         pkt.init[3] = flags & 0x7;
 497
 498         set_state(c, SYN_SENT);
 499
 500         print_packet(c, "send", &pkt, sizeof(pkt));
 501         utcp->send(utcp, &pkt, sizeof(pkt));
 502
 503         gettimeofday(&c->conn_timeout, NULL);
 504         c->conn_timeout.tv_sec += utcp->timeout;
 505
 506         start_retransmit_timer(c);
 507
 508         return c;
 509 }
 510
 511 struct utcp_connection *utcp_connect(struct utcp *utcp, uint16_t dst, utcp_recv_t recv, void *priv) {
 512         return utcp_connect_ex(utcp, dst, recv, priv, UTCP_TCP);
 513 }
 514
 515 void utcp_accept(struct utcp_connection *c, utcp_recv_t recv, void *priv) {
 516         if(c->reapable || c->state != SYN_RECEIVED) {
 517                 debug(c, "accept() called on invalid connection in state %s\n", c, strstate[c->state]);
 518                 return;
 519         }
 520
 521         debug(c, "accepted %p %p\n", c, recv, priv);
 522         c->recv = recv;
 523         c->priv = priv;
 524         set_state(c, ESTABLISHED);
 525 }
 526
 527 static void ack(struct utcp_connection *c, bool sendatleastone) {
 528         int32_t left = seqdiff(c->snd.last, c->snd.nxt);
 529         int32_t cwndleft = min(c->snd.cwnd, c->snd.wnd) - seqdiff(c->snd.nxt, c->snd.una);
 530
 531         assert(left >= 0);
 532
 533         if(cwndleft <= 0) {
 534                 left = 0;
 535         } else if(cwndleft < left) {
 536                 left = cwndleft;
 537
 538                 if(!sendatleastone || cwndleft > c->utcp->mtu) {
 539                         left -= left % c->utcp->mtu;
 540                 }
 541         }
 542
 543         debug(c, "cwndleft %d left %d\n", cwndleft, left);
 544
 545         if(!left && !sendatleastone) {
 546                 return;
 547         }
 548
 549         struct {
 550                 struct hdr hdr;
 551                 uint8_t data[];
 552         } *pkt;
 553
 554         pkt = malloc(sizeof(pkt->hdr) + c->utcp->mtu);
 555
 556         if(!pkt) {
 557                 return;
 558         }
 559
 560         pkt->hdr.src = c->src;
 561         pkt->hdr.dst = c->dst;
 562         pkt->hdr.ack = c->rcv.nxt;
 563         pkt->hdr.wnd = c->rcvbuf.maxsize;
 564         pkt->hdr.ctl = ACK;
 565         pkt->hdr.aux = 0;
 566
 567         do {
 568                 uint32_t seglen = left > c->utcp->mtu ? c->utcp->mtu : left;
 569                 pkt->hdr.seq = c->snd.nxt;
 570
 571                 buffer_copy(&c->sndbuf, pkt->data, seqdiff(c->snd.nxt, c->snd.una), seglen);
 572
 573                 c->snd.nxt += seglen;
 574                 left -= seglen;
 575
 576                 if(seglen && fin_wanted(c, c->snd.nxt)) {
 577                         seglen--;
 578                         pkt->hdr.ctl |= FIN;
 579                 }
 580
 581                 if(!c->rtt_start.tv_sec) {
 582                         // Start RTT measurement
 583                         gettimeofday(&c->rtt_start, NULL);
 584                         c->rtt_seq = pkt->hdr.seq + seglen;
 585                         debug(c, "starting RTT measurement, expecting ack %u\n", c->rtt_seq);
 586                 }
 587
 588                 print_packet(c, "send", pkt, sizeof(pkt->hdr) + seglen);
 589                 c->utcp->send(c->utcp, pkt, sizeof(pkt->hdr) + seglen);
 590         } while(left);
 591
 592         free(pkt);
 593 }
 594
 595 ssize_t utcp_send(struct utcp_connection *c, const void *data, size_t len) {
 596         if(c->reapable) {
 597                 debug(c, "send() called on closed connection\n");
 598                 errno = EBADF;
 599                 return -1;
 600         }
 601
 602         switch(c->state) {
 603         case CLOSED:
 604         case LISTEN:
 605                 debug(c, "send() called on unconnected connection\n");
 606                 errno = ENOTCONN;
 607                 return -1;
 608
 609         case SYN_SENT:
 610         case SYN_RECEIVED:
 611         case ESTABLISHED:
 612         case CLOSE_WAIT:
 613                 break;
 614
 615         case FIN_WAIT_1:
 616         case FIN_WAIT_2:
 617         case CLOSING:
 618         case LAST_ACK:
 619         case TIME_WAIT:
 620                 debug(c, "send() called on closed connection\n");
 621                 errno = EPIPE;
 622                 return -1;
 623         }
 624
 625         // Exit early if we have nothing to send.
 626
 627         if(!len) {
 628                 return 0;
 629         }
 630
 631         if(!data) {
 632                 errno = EFAULT;
 633                 return -1;
 634         }
 635
 636         // Check if we need to be able to buffer all data
 637
 638         if(c->flags & UTCP_NO_PARTIAL) {
 639                 if(len > buffer_free(&c->sndbuf)) {
 640                         if(len > c->sndbuf.maxsize) {
 641                                 errno = EMSGSIZE;
 642                                 return -1;
 643                         } else {
 644                                 errno = EWOULDBLOCK;
 645                                 return 0;
 646                         }
 647                 }
 648         }
 649
 650         // Add data to send buffer.
 651
 652         if(is_reliable(c) || (c->state != SYN_SENT && c->state != SYN_RECEIVED)) {
 653                 len = buffer_put(&c->sndbuf, data, len);
 654         } else {
 655                 return 0;
 656         }
 657
 658         if(len <= 0) {
 659                 if(is_reliable(c)) {
 660                         errno = EWOULDBLOCK;
 661                         return 0;
 662                 } else {
 663                         return len;
 664                 }
 665         }
 666
 667         c->snd.last += len;
 668
 669         // Don't send anything yet if the connection has not fully established yet
 670
 671         if(c->state == SYN_SENT || c->state == SYN_RECEIVED) {
 672                 return len;
 673         }
 674
 675         ack(c, false);
 676
 677         if(!is_reliable(c)) {
 678                 c->snd.una = c->snd.nxt = c->snd.last;
 679                 buffer_get(&c->sndbuf, NULL, c->sndbuf.used);
 680         }
 681
 682         if(is_reliable(c) && !timerisset(&c->rtrx_timeout)) {
 683                 start_retransmit_timer(c);
 684         }
 685
 686         if(is_reliable(c) && !timerisset(&c->conn_timeout)) {
 687                 gettimeofday(&c->conn_timeout, NULL);
 688                 c->conn_timeout.tv_sec += c->utcp->timeout;
 689         }
 690
 691         return len;
 692 }
 693
 694 static void swap_ports(struct hdr *hdr) {
 695         uint16_t tmp = hdr->src;
 696         hdr->src = hdr->dst;
 697         hdr->dst = tmp;
 698 }
 699
 700 static void fast_retransmit(struct utcp_connection *c) {
 701         if(c->state == CLOSED || c->snd.last == c->snd.una) {
 702                 debug(c, "fast_retransmit() called but nothing to retransmit!\n");
 703                 return;
 704         }
 705
 706         struct utcp *utcp = c->utcp;
 707
 708         struct {
 709                 struct hdr hdr;
 710                 uint8_t data[];
 711         } *pkt;
 712
 713         pkt = malloc(sizeof(pkt->hdr) + c->utcp->mtu);
 714
 715         if(!pkt) {
 716                 return;
 717         }
 718
 719         pkt->hdr.src = c->src;
 720         pkt->hdr.dst = c->dst;
 721         pkt->hdr.wnd = c->rcvbuf.maxsize;
 722         pkt->hdr.aux = 0;
 723
 724         switch(c->state) {
 725         case ESTABLISHED:
 726         case FIN_WAIT_1:
 727         case CLOSE_WAIT:
 728         case CLOSING:
 729         case LAST_ACK:
 730                 // Send unacked data again.
 731                 pkt->hdr.seq = c->snd.una;
 732                 pkt->hdr.ack = c->rcv.nxt;
 733                 pkt->hdr.ctl = ACK;
 734                 uint32_t len = min(seqdiff(c->snd.last, c->snd.una), utcp->mtu);
 735
 736                 if(fin_wanted(c, c->snd.una + len)) {
 737                         len--;
 738                         pkt->hdr.ctl |= FIN;
 739                 }
 740
 741                 buffer_copy(&c->sndbuf, pkt->data, 0, len);
 742                 print_packet(c, "rtrx", pkt, sizeof(pkt->hdr) + len);
 743                 utcp->send(utcp, pkt, sizeof(pkt->hdr) + len);
 744                 break;
 745
 746         default:
 747                 break;
 748         }
 749
 750         free(pkt);
 751 }
 752
 753 static void retransmit(struct utcp_connection *c) {
 754         if(c->state == CLOSED || c->snd.last == c->snd.una) {
 755                 debug(c, "retransmit() called but nothing to retransmit!\n");
 756                 stop_retransmit_timer(c);
 757                 return;
 758         }
 759
 760         struct utcp *utcp = c->utcp;
 761
 762         struct {
 763                 struct hdr hdr;
 764                 uint8_t data[];
 765         } *pkt;
 766
 767         pkt = malloc(sizeof(pkt->hdr) + c->utcp->mtu);
 768
 769         if(!pkt) {
 770                 return;
 771         }
 772
 773         pkt->hdr.src = c->src;
 774         pkt->hdr.dst = c->dst;
 775         pkt->hdr.wnd = c->rcvbuf.maxsize;
 776         pkt->hdr.aux = 0;
 777
 778         switch(c->state) {
 779         case SYN_SENT:
 780                 // Send our SYN again
 781                 pkt->hdr.seq = c->snd.iss;
 782                 pkt->hdr.ack = 0;
 783                 pkt->hdr.ctl = SYN;
 784                 pkt->hdr.aux = 0x0101;
 785                 pkt->data[0] = 1;
 786                 pkt->data[1] = 0;
 787                 pkt->data[2] = 0;
 788                 pkt->data[3] = c->flags & 0x7;
 789                 print_packet(c, "rtrx", pkt, sizeof(pkt->hdr) + 4);
 790                 utcp->send(utcp, pkt, sizeof(pkt->hdr) + 4);
 791                 break;
 792
 793         case SYN_RECEIVED:
 794                 // Send SYNACK again
 795                 pkt->hdr.seq = c->snd.nxt;
 796                 pkt->hdr.ack = c->rcv.nxt;
 797                 pkt->hdr.ctl = SYN | ACK;
 798                 print_packet(c, "rtrx", pkt, sizeof(pkt->hdr));
 799                 utcp->send(utcp, pkt, sizeof(pkt->hdr));
 800                 break;
 801
 802         case ESTABLISHED:
 803         case FIN_WAIT_1:
 804         case CLOSE_WAIT:
 805         case CLOSING:
 806         case LAST_ACK:
 807                 // Send unacked data again.
 808                 pkt->hdr.seq = c->snd.una;
 809                 pkt->hdr.ack = c->rcv.nxt;
 810                 pkt->hdr.ctl = ACK;
 811                 uint32_t len = min(seqdiff(c->snd.last, c->snd.una), utcp->mtu);
 812
 813                 if(fin_wanted(c, c->snd.una + len)) {
 814                         len--;
 815                         pkt->hdr.ctl |= FIN;
 816                 }
 817
 818                 // RFC 5681 slow start after timeout
 819                 uint32_t flightsize = seqdiff(c->snd.nxt, c->snd.una);
 820                 c->snd.ssthresh = max(flightsize / 2, utcp->mtu * 2); // eq. 4
 821                 c->snd.cwnd = utcp->mtu;
 822                 debug_cwnd(c);
 823
 824                 buffer_copy(&c->sndbuf, pkt->data, 0, len);
 825                 print_packet(c, "rtrx", pkt, sizeof(pkt->hdr) + len);
 826                 utcp->send(utcp, pkt, sizeof(pkt->hdr) + len);
 827
 828                 c->snd.nxt = c->snd.una + len;
 829                 break;
 830
 831         case CLOSED:
 832         case LISTEN:
 833         case TIME_WAIT:
 834         case FIN_WAIT_2:
 835                 // We shouldn't need to retransmit anything in this state.
 836 #ifdef UTCP_DEBUG
 837                 abort();
 838 #endif
 839                 stop_retransmit_timer(c);
 840                 goto cleanup;
 841         }
 842
 843         start_retransmit_timer(c);
 844         utcp->rto *= 2;
 845
 846         if(utcp->rto > MAX_RTO) {
 847                 utcp->rto = MAX_RTO;
 848         }
 849
 850         c->rtt_start.tv_sec = 0; // invalidate RTT timer
 851         c->dupack = 0; // cancel any ongoing fast recovery
 852
 853 cleanup:
 854         free(pkt);
 855 }
 856
 857 /* Update receive buffer and SACK entries after consuming data.
 858  *
 859  * Situation:
 860  *
 861  * |.....0000..1111111111.....22222......3333|
 862  * |---------------^
 863  *
 864  * 0..3 represent the SACK entries. The ^ indicates up to which point we want
 865  * to remove data from the receive buffer. The idea is to substract "len"
 866  * from the offset of all the SACK entries, and then remove/cut down entries
 867  * that are shifted to before the start of the receive buffer.
 868  *
 869  * There are three cases:
 870  * - the SACK entry is after ^, in that case just change the offset.
 871  * - the SACK entry starts before and ends after ^, so we have to
 872  *   change both its offset and size.
 873  * - the SACK entry is completely before ^, in that case delete it.
 874  */
 875 static void sack_consume(struct utcp_connection *c, size_t len) {
 876         debug(c, "sack_consume %lu\n", (unsigned long)len);
 877
 878         if(len > c->rcvbuf.used) {
 879                 debug(c, "all SACK entries consumed\n");
 880                 c->sacks[0].len = 0;
 881                 return;
 882         }
 883
 884         buffer_get(&c->rcvbuf, NULL, len);
 885
 886         for(int i = 0; i < NSACKS && c->sacks[i].len;) {
 887                 if(len < c->sacks[i].offset) {
 888                         c->sacks[i].offset -= len;
 889                         i++;
 890                 } else if(len < c->sacks[i].offset + c->sacks[i].len) {
 891                         c->sacks[i].len -= len - c->sacks[i].offset;
 892                         c->sacks[i].offset = 0;
 893                         i++;
 894                 } else {
 895                         if(i < NSACKS - 1) {
 896                                 memmove(&c->sacks[i], &c->sacks[i + 1], (NSACKS - 1 - i) * sizeof(c->sacks)[i]);
 897                                 c->sacks[NSACKS - 1].len = 0;
 898                         } else {
 899                                 c->sacks[i].len = 0;
 900                                 break;
 901                         }
 902                 }
 903         }
 904
 905         for(int i = 0; i < NSACKS && c->sacks[i].len; i++) {
 906                 debug(c, "SACK[%d] offset %u len %u\n", i, c->sacks[i].offset, c->sacks[i].len);
 907         }
 908 }
 909
 910 static void handle_out_of_order(struct utcp_connection *c, uint32_t offset, const void *data, size_t len) {
 911         debug(c, "out of order packet, offset %u\n", offset);
 912         // Packet loss or reordering occured. Store the data in the buffer.
 913         ssize_t rxd = buffer_put_at(&c->rcvbuf, offset, data, len);
 914
 915         if(rxd < 0 || (size_t)rxd < len) {
 916                 abort();
 917         }
 918
 919         // Make note of where we put it.
 920         for(int i = 0; i < NSACKS; i++) {
 921                 if(!c->sacks[i].len) { // nothing to merge, add new entry
 922                         debug(c, "new SACK entry %d\n", i);
 923                         c->sacks[i].offset = offset;
 924                         c->sacks[i].len = rxd;
 925                         break;
 926                 } else if(offset < c->sacks[i].offset) {
 927                         if(offset + rxd < c->sacks[i].offset) { // insert before
 928                                 if(!c->sacks[NSACKS - 1].len) { // only if room left
 929                                         debug(c, "insert SACK entry at %d\n", i);
 930                                         memmove(&c->sacks[i + 1], &c->sacks[i], (NSACKS - i - 1) * sizeof(c->sacks)[i]);
 931                                         c->sacks[i].offset = offset;
 932                                         c->sacks[i].len = rxd;
 933                                 } else {
 934                                         debug(c, "SACK entries full, dropping packet\n");
 935                                 }
 936
 937                                 break;
 938                         } else { // merge
 939                                 debug(c, "merge with start of SACK entry at %d\n", i);
 940                                 c->sacks[i].offset = offset;
 941                                 break;
 942                         }
 943                 } else if(offset <= c->sacks[i].offset + c->sacks[i].len) {
 944                         if(offset + rxd > c->sacks[i].offset + c->sacks[i].len) { // merge
 945                                 debug(c, "merge with end of SACK entry at %d\n", i);
 946                                 c->sacks[i].len = offset + rxd - c->sacks[i].offset;
 947                                 // TODO: handle potential merge with next entry
 948                         }
 949
 950                         break;
 951                 }
 952         }
 953
 954         for(int i = 0; i < NSACKS && c->sacks[i].len; i++) {
 955                 debug(c, "SACK[%d] offset %u len %u\n", i, c->sacks[i].offset, c->sacks[i].len);
 956         }
 957 }
 958
 959 static void handle_in_order(struct utcp_connection *c, const void *data, size_t len) {
 960         // Check if we can process out-of-order data now.
 961         if(c->sacks[0].len && len >= c->sacks[0].offset) { // TODO: handle overlap with second SACK
 962                 debug(c, "incoming packet len %lu connected with SACK at %u\n", (unsigned long)len, c->sacks[0].offset);
 963                 buffer_put_at(&c->rcvbuf, 0, data, len); // TODO: handle return value
 964                 len = max(len, c->sacks[0].offset + c->sacks[0].len);
 965                 data = c->rcvbuf.data;
 966         }
 967
 968         if(c->recv) {
 969                 ssize_t rxd = c->recv(c, data, len);
 970
 971                 if(rxd < 0 || (size_t)rxd != len) {
 972                         // TODO: handle the application not accepting all data.
 973                         abort();
 974                 }
 975         }
 976
 977         if(c->rcvbuf.used) {
 978                 sack_consume(c, len);
 979         }
 980
 981         c->rcv.nxt += len;
 982 }
 983
 984
 985 static void handle_incoming_data(struct utcp_connection *c, uint32_t seq, const void *data, size_t len) {
 986         if(!is_reliable(c)) {
 987                 c->recv(c, data, len);
 988                 c->rcv.nxt = seq + len;
 989                 return;
 990         }
 991
 992         uint32_t offset = seqdiff(seq, c->rcv.nxt);
 993
 994         if(offset + len > c->rcvbuf.maxsize) {
 995                 abort();
 996         }
 997
 998         if(offset) {
 999                 handle_out_of_order(c, offset, data, len);
1000         } else {
1001                 handle_in_order(c, data, len);
1002         }
1003 }
1004
1005
1006 ssize_t utcp_recv(struct utcp *utcp, const void *data, size_t len) {
1007         const uint8_t *ptr = data;
1008
1009         if(!utcp) {
1010                 errno = EFAULT;
1011                 return -1;
1012         }
1013
1014         if(!len) {
1015                 return 0;
1016         }
1017
1018         if(!data) {
1019                 errno = EFAULT;
1020                 return -1;
1021         }
1022
1023         // Drop packets smaller than the header
1024
1025         struct hdr hdr;
1026
1027         if(len < sizeof(hdr)) {
1028                 print_packet(NULL, "recv", data, len);
1029                 errno = EBADMSG;
1030                 return -1;
1031         }
1032
1033         // Make a copy from the potentially unaligned data to a struct hdr
1034
1035         memcpy(&hdr, ptr, sizeof(hdr));
1036
1037         // Try to match the packet to an existing connection
1038
1039         struct utcp_connection *c = find_connection(utcp, hdr.dst, hdr.src);
1040         print_packet(c, "recv", data, len);
1041
1042         // Process the header
1043
1044         ptr += sizeof(hdr);
1045         len -= sizeof(hdr);
1046
1047         // Drop packets with an unknown CTL flag
1048
1049         if(hdr.ctl & ~(SYN | ACK | RST | FIN)) {
1050                 print_packet(NULL, "recv", data, len);
1051                 errno = EBADMSG;
1052                 return -1;
1053         }
1054
1055         // Check for auxiliary headers
1056
1057         const uint8_t *init = NULL;
1058
1059         uint16_t aux = hdr.aux;
1060
1061         while(aux) {
1062                 size_t auxlen = 4 * (aux >> 8) & 0xf;
1063                 uint8_t auxtype = aux & 0xff;
1064
1065                 if(len < auxlen) {
1066                         errno = EBADMSG;
1067                         return -1;
1068                 }
1069
1070                 switch(auxtype) {
1071                 case AUX_INIT:
1072                         if(!(hdr.ctl & SYN) || auxlen != 4) {
1073                                 errno = EBADMSG;
1074                                 return -1;
1075                         }
1076
1077                         init = ptr;
1078                         break;
1079
1080                 default:
1081                         errno = EBADMSG;
1082                         return -1;
1083                 }
1084
1085                 len -= auxlen;
1086                 ptr += auxlen;
1087
1088                 if(!(aux & 0x800)) {
1089                         break;
1090                 }
1091
1092                 if(len < 2) {
1093                         errno = EBADMSG;
1094                         return -1;
1095                 }
1096
1097                 memcpy(&aux, ptr, 2);
1098                 len -= 2;
1099                 ptr += 2;
1100         }
1101
1102         bool has_data = len || (hdr.ctl & (SYN | FIN));
1103
1104         // Is it for a new connection?
1105
1106         if(!c) {
1107                 // Ignore RST packets
1108
1109                 if(hdr.ctl & RST) {
1110                         return 0;
1111                 }
1112
1113                 // Is it a SYN packet and are we LISTENing?
1114
1115                 if(hdr.ctl & SYN && !(hdr.ctl & ACK) && utcp->accept) {
1116                         // If we don't want to accept it, send a RST back
1117                         if((utcp->pre_accept && !utcp->pre_accept(utcp, hdr.dst))) {
1118                                 len = 1;
1119                                 goto reset;
1120                         }
1121
1122                         // Try to allocate memory, otherwise send a RST back
1123                         c = allocate_connection(utcp, hdr.dst, hdr.src);
1124
1125                         if(!c) {
1126                                 len = 1;
1127                                 goto reset;
1128                         }
1129
1130                         // Parse auxilliary information
1131                         if(init) {
1132                                 if(init[0] < 1) {
1133                                         len = 1;
1134                                         goto reset;
1135                                 }
1136
1137                                 c->flags = init[3] & 0x7;
1138                         } else {
1139                                 c->flags = UTCP_TCP;
1140                         }
1141
1142 synack:
1143                         // Return SYN+ACK, go to SYN_RECEIVED state
1144                         c->snd.wnd = hdr.wnd;
1145                         c->rcv.irs = hdr.seq;
1146                         c->rcv.nxt = c->rcv.irs + 1;
1147                         set_state(c, SYN_RECEIVED);
1148
1149                         struct {
1150                                 struct hdr hdr;
1151                                 uint8_t data[4];
1152                         } pkt;
1153
1154                         pkt.hdr.src = c->src;
1155                         pkt.hdr.dst = c->dst;
1156                         pkt.hdr.ack = c->rcv.irs + 1;
1157                         pkt.hdr.seq = c->snd.iss;
1158                         pkt.hdr.wnd = c->rcvbuf.maxsize;
1159                         pkt.hdr.ctl = SYN | ACK;
1160
1161                         if(init) {
1162                                 pkt.hdr.aux = 0x0101;
1163                                 pkt.data[0] = 1;
1164                                 pkt.data[1] = 0;
1165                                 pkt.data[2] = 0;
1166                                 pkt.data[3] = c->flags & 0x7;
1167                                 print_packet(c, "send", &pkt, sizeof(hdr) + 4);
1168                                 utcp->send(utcp, &pkt, sizeof(hdr) + 4);
1169                         } else {
1170                                 pkt.hdr.aux = 0;
1171                                 print_packet(c, "send", &pkt, sizeof(hdr));
1172                                 utcp->send(utcp, &pkt, sizeof(hdr));
1173                         }
1174                 } else {
1175                         // No, we don't want your packets, send a RST back
1176                         len = 1;
1177                         goto reset;
1178                 }
1179
1180                 return 0;
1181         }
1182
1183         debug(c, "state %s\n", strstate[c->state]);
1184
1185         // In case this is for a CLOSED connection, ignore the packet.
1186         // TODO: make it so incoming packets can never match a CLOSED connection.
1187
1188         if(c->state == CLOSED) {
1189                 debug(c, "got packet for closed connection\n");
1190                 return 0;
1191         }
1192
1193         // It is for an existing connection.
1194
1195         // 1. Drop invalid packets.
1196
1197         // 1a. Drop packets that should not happen in our current state.
1198
1199         switch(c->state) {
1200         case SYN_SENT:
1201         case SYN_RECEIVED:
1202         case ESTABLISHED:
1203         case FIN_WAIT_1:
1204         case FIN_WAIT_2:
1205         case CLOSE_WAIT:
1206         case CLOSING:
1207         case LAST_ACK:
1208         case TIME_WAIT:
1209                 break;
1210
1211         default:
1212 #ifdef UTCP_DEBUG
1213                 abort();
1214 #endif
1215                 break;
1216         }
1217
1218         // 1b. Discard data that is not in our receive window.
1219
1220         if(is_reliable(c)) {
1221                 bool acceptable;
1222
1223                 if(c->state == SYN_SENT) {
1224                         acceptable = true;
1225                 } else if(len == 0) {
1226                         acceptable = seqdiff(hdr.seq, c->rcv.nxt) >= 0;
1227                 } else {
1228                         int32_t rcv_offset = seqdiff(hdr.seq, c->rcv.nxt);
1229
1230                         // cut already accepted front overlapping
1231                         if(rcv_offset < 0) {
1232                                 acceptable = len > (size_t) - rcv_offset;
1233
1234                                 if(acceptable) {
1235                                         ptr -= rcv_offset;
1236                                         len += rcv_offset;
1237                                         hdr.seq -= rcv_offset;
1238                                 }
1239                         } else {
1240                                 acceptable = seqdiff(hdr.seq, c->rcv.nxt) >= 0 && seqdiff(hdr.seq, c->rcv.nxt) + len <= c->rcvbuf.maxsize;
1241                         }
1242                 }
1243
1244                 if(!acceptable) {
1245                         debug(c, "packet not acceptable, %u <= %u + %lu < %u\n", c->rcv.nxt, hdr.seq, (unsigned long)len, c->rcv.nxt + c->rcvbuf.maxsize);
1246
1247                         // Ignore unacceptable RST packets.
1248                         if(hdr.ctl & RST) {
1249                                 return 0;
1250                         }
1251
1252                         // Otherwise, continue processing.
1253                         len = 0;
1254                 }
1255         }
1256
1257         c->snd.wnd = hdr.wnd; // TODO: move below
1258
1259         // 1c. Drop packets with an invalid ACK.
1260         // ackno should not roll back, and it should also not be bigger than what we ever could have sent
1261         // (= snd.una + c->sndbuf.used).
1262
1263         if(!is_reliable(c)) {
1264                 if(hdr.ack != c->snd.last && c->state >= ESTABLISHED) {
1265                         hdr.ack = c->snd.una;
1266                 }
1267         }
1268
1269         if(hdr.ctl & ACK && (seqdiff(hdr.ack, c->snd.last) > 0 || seqdiff(hdr.ack, c->snd.una) < 0)) {
1270                 debug(c, "packet ack seqno out of range, %u <= %u < %u\n", c->snd.una, hdr.ack, c->snd.una + c->sndbuf.used);
1271
1272                 // Ignore unacceptable RST packets.
1273                 if(hdr.ctl & RST) {
1274                         return 0;
1275                 }
1276
1277                 goto reset;
1278         }
1279
1280         // 2. Handle RST packets
1281
1282         if(hdr.ctl & RST) {
1283                 switch(c->state) {
1284                 case SYN_SENT:
1285                         if(!(hdr.ctl & ACK)) {
1286                                 return 0;
1287                         }
1288
1289                         // The peer has refused our connection.
1290                         set_state(c, CLOSED);
1291                         errno = ECONNREFUSED;
1292
1293                         if(c->recv) {
1294                                 c->recv(c, NULL, 0);
1295                         }
1296
1297                         if(c->poll && !c->reapable) {
1298                                 c->poll(c, 0);
1299                         }
1300
1301                         return 0;
1302
1303                 case SYN_RECEIVED:
1304                         if(hdr.ctl & ACK) {
1305                                 return 0;
1306                         }
1307
1308                         // We haven't told the application about this connection yet. Silently delete.
1309                         free_connection(c);
1310                         return 0;
1311
1312                 case ESTABLISHED:
1313                 case FIN_WAIT_1:
1314                 case FIN_WAIT_2:
1315                 case CLOSE_WAIT:
1316                         if(hdr.ctl & ACK) {
1317                                 return 0;
1318                         }
1319
1320                         // The peer has aborted our connection.
1321                         set_state(c, CLOSED);
1322                         errno = ECONNRESET;
1323
1324                         if(c->recv) {
1325                                 c->recv(c, NULL, 0);
1326                         }
1327
1328                         if(c->poll && !c->reapable) {
1329                                 c->poll(c, 0);
1330                         }
1331
1332                         return 0;
1333
1334                 case CLOSING:
1335                 case LAST_ACK:
1336                 case TIME_WAIT:
1337                         if(hdr.ctl & ACK) {
1338                                 return 0;
1339                         }
1340
1341                         // As far as the application is concerned, the connection has already been closed.
1342                         // If it has called utcp_close() already, we can immediately free this connection.
1343                         if(c->reapable) {
1344                                 free_connection(c);
1345                                 return 0;
1346                         }
1347
1348                         // Otherwise, immediately move to the CLOSED state.
1349                         set_state(c, CLOSED);
1350                         return 0;
1351
1352                 default:
1353 #ifdef UTCP_DEBUG
1354                         abort();
1355 #endif
1356                         break;
1357                 }
1358         }
1359
1360         uint32_t advanced;
1361
1362         if(!(hdr.ctl & ACK)) {
1363                 advanced = 0;
1364                 goto skip_ack;
1365         }
1366
1367         // 3. Advance snd.una
1368
1369         advanced = seqdiff(hdr.ack, c->snd.una);
1370
1371         if(advanced) {
1372                 // RTT measurement
1373                 if(c->rtt_start.tv_sec) {
1374                         if(c->rtt_seq == hdr.ack) {
1375                                 struct timeval now, diff;
1376                                 gettimeofday(&now, NULL);
1377                                 timersub(&now, &c->rtt_start, &diff);
1378                                 update_rtt(c, diff.tv_sec * 1000000 + diff.tv_usec);
1379                                 c->rtt_start.tv_sec = 0;
1380                         } else if(c->rtt_seq < hdr.ack) {
1381                                 debug(c, "cancelling RTT measurement: %u < %u\n", c->rtt_seq, hdr.ack);
1382                                 c->rtt_start.tv_sec = 0;
1383                         }
1384                 }
1385
1386                 int32_t data_acked = advanced;
1387
1388                 switch(c->state) {
1389                 case SYN_SENT:
1390                 case SYN_RECEIVED:
1391                         data_acked--;
1392                         break;
1393
1394                 // TODO: handle FIN as well.
1395                 default:
1396                         break;
1397                 }
1398
1399                 assert(data_acked >= 0);
1400
1401 #ifndef NDEBUG
1402                 int32_t bufused = seqdiff(c->snd.last, c->snd.una);
1403                 assert(data_acked <= bufused);
1404 #endif
1405
1406                 if(data_acked) {
1407                         buffer_get(&c->sndbuf, NULL, data_acked);
1408                 }
1409
1410                 // Also advance snd.nxt if possible
1411                 if(seqdiff(c->snd.nxt, hdr.ack) < 0) {
1412                         c->snd.nxt = hdr.ack;
1413                 }
1414
1415                 c->snd.una = hdr.ack;
1416
1417                 if(c->dupack) {
1418                         if(c->dupack >= 3) {
1419                                 debug(c, "fast recovery ended\n");
1420                                 c->snd.cwnd = c->snd.ssthresh;
1421                         }
1422
1423                         c->dupack = 0;
1424                 }
1425
1426                 // Increase the congestion window according to RFC 5681
1427                 if(c->snd.cwnd < c->snd.ssthresh) {
1428                         c->snd.cwnd += min(advanced, utcp->mtu); // eq. 2
1429                 } else {
1430                         c->snd.cwnd += max(1, (utcp->mtu * utcp->mtu) / c->snd.cwnd); // eq. 3
1431                 }
1432
1433                 if(c->snd.cwnd > c->sndbuf.maxsize) {
1434                         c->snd.cwnd = c->sndbuf.maxsize;
1435                 }
1436
1437                 debug_cwnd(c);
1438
1439                 // Check if we have sent a FIN that is now ACKed.
1440                 switch(c->state) {
1441                 case FIN_WAIT_1:
1442                         if(c->snd.una == c->snd.last) {
1443                                 set_state(c, FIN_WAIT_2);
1444                         }
1445
1446                         break;
1447
1448                 case CLOSING:
1449                         if(c->snd.una == c->snd.last) {
1450                                 gettimeofday(&c->conn_timeout, NULL);
1451                                 c->conn_timeout.tv_sec += utcp->timeout;
1452                                 set_state(c, TIME_WAIT);
1453                         }
1454
1455                         break;
1456
1457                 default:
1458                         break;
1459                 }
1460         } else {
1461                 if(!len && is_reliable(c) && c->snd.una != c->snd.last) {
1462                         c->dupack++;
1463                         debug(c, "duplicate ACK %d\n", c->dupack);
1464
1465                         if(c->dupack == 3) {
1466                                 // RFC 5681 fast recovery
1467                                 debug(c, "fast recovery started\n", c->dupack);
1468                                 uint32_t flightsize = seqdiff(c->snd.nxt, c->snd.una);
1469                                 c->snd.ssthresh = max(flightsize / 2, utcp->mtu * 2); // eq. 4
1470                                 c->snd.cwnd = min(c->snd.ssthresh + 3 * utcp->mtu, c->sndbuf.maxsize);
1471
1472                                 if(c->snd.cwnd > c->sndbuf.maxsize) {
1473                                         c->snd.cwnd = c->sndbuf.maxsize;
1474                                 }
1475
1476                                 debug_cwnd(c);
1477
1478                                 fast_retransmit(c);
1479                         } else if(c->dupack > 3) {
1480                                 c->snd.cwnd += utcp->mtu;
1481
1482                                 if(c->snd.cwnd > c->sndbuf.maxsize) {
1483                                         c->snd.cwnd = c->sndbuf.maxsize;
1484                                 }
1485
1486                                 debug_cwnd(c);
1487                         }
1488
1489                         // We got an ACK which indicates the other side did get one of our packets.
1490                         // Reset the retransmission timer to avoid going to slow start,
1491                         // but don't touch the connection timeout.
1492                         start_retransmit_timer(c);
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 }