2 utcp.c -- Userspace TCP
3 Copyright (C) 2014 Guus Sliepen <guus@tinc-vpn.org>
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.
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.
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.
30 #include <sys/socket.h>
35 #define PREP(l) char pkt[(l) + sizeof struct hdr]; struct hdr *hdr = &pkt;
43 uint16_t src; // Source port
44 uint16_t dst; // Destination port
45 uint32_t seq; // Sequence number
46 uint32_t ack; // Acknowledgement number
47 uint32_t wnd; // Window size
48 uint16_t ctl; // Flags (SYN, ACK, FIN, RST)
49 uint16_t aux; // other stuff
66 const char *strstate[] = {
80 struct utcp_connection {
89 // The following two structures form the TCB
110 struct timeval conn_timeout;
111 struct timeval rtrx_timeout;
120 utcp_accept_t accept;
121 utcp_pre_accept_t pre_accept;
126 struct utcp_connection **connections;
132 static void set_state(struct utcp_connection *c, enum state state) {
134 fprintf(stderr, "%p new state: %s\n", c->utcp, strstate[state]);
137 static void print_packet(void *pkt, size_t len) {
139 if(len < sizeof hdr) {
140 fprintf(stderr, "short packet (%zu bytes)\n", len);
144 memcpy(&hdr, pkt, sizeof hdr);
145 fprintf (stderr, "src=%u dst=%u seq=%u ack=%u wnd=%u ctl=", hdr.src, hdr.dst, hdr.seq, hdr.ack, hdr.wnd);
147 fprintf(stderr, "SYN");
149 fprintf(stderr, "RST");
151 fprintf(stderr, "FIN");
153 fprintf(stderr, "ACK");
155 if(len > sizeof hdr) {
156 fprintf(stderr, " data=");
157 for(int i = sizeof hdr; i < len; i++) {
159 fprintf(stderr, "%c", data[i] >= 32 ? data[i] : '.');
163 fprintf(stderr, "\n");
166 static void list_connections(struct utcp *utcp) {
167 fprintf(stderr, "%p has %d connections:\n", utcp, utcp->nconnections);
168 for(int i = 0; i < utcp->nconnections; i++)
169 fprintf(stderr, " %u -> %u state %s\n", utcp->connections[i]->src, utcp->connections[i]->dst, strstate[utcp->connections[i]->state]);
172 // Connections are stored in a sorted list.
173 // This gives O(log(N)) lookup time, O(N log(N)) insertion time and O(N) deletion time.
175 static int compare(const void *va, const void *vb) {
176 const struct utcp_connection *a = *(struct utcp_connection **)va;
177 const struct utcp_connection *b = *(struct utcp_connection **)vb;
178 if(!a->src || !b->src)
180 int c = (int)a->src - (int)b->src;
183 c = (int)a->dst - (int)b->dst;
187 static struct utcp_connection *find_connection(const struct utcp *utcp, uint16_t src, uint16_t dst) {
188 if(!utcp->nconnections)
190 struct utcp_connection key = {
194 struct utcp_connection **match = bsearch(&keyp, utcp->connections, utcp->nconnections, sizeof *utcp->connections, compare);
195 return match ? *match : NULL;
198 static void free_connection(struct utcp_connection *c) {
199 struct utcp *utcp = c->utcp;
200 struct utcp_connection **cp = bsearch(&c, utcp->connections, utcp->nconnections, sizeof *utcp->connections, compare);
204 int i = cp - utcp->connections;
205 memmove(cp + i, cp + i + 1, (utcp->nconnections - i - 1) * sizeof *cp);
206 utcp->nconnections--;
211 static struct utcp_connection *allocate_connection(struct utcp *utcp, uint16_t src, uint16_t dst) {
212 // Check whether this combination of src and dst is free
215 if(find_connection(utcp, src, dst)) {
219 } else { // If src == 0, generate a random port number with the high bit set
220 if(utcp->nconnections >= 32767) {
224 src = rand() | 0x8000;
225 while(find_connection(utcp, src, dst))
229 // Allocate memory for the new connection
231 if(utcp->nconnections >= utcp->nallocated) {
232 if(!utcp->nallocated)
233 utcp->nallocated = 4;
235 utcp->nallocated *= 2;
236 struct utcp_connection **new_array = realloc(utcp->connections, utcp->nallocated * sizeof *utcp->connections);
241 utcp->connections = new_array;
244 struct utcp_connection *c = calloc(1, sizeof *c);
250 // Fill in the details
255 c->snd.una = c->snd.iss;
256 c->snd.nxt = c->snd.iss + 1;
257 c->rcv.wnd = utcp->mtu;
260 // Add it to the sorted list of connections
262 utcp->connections[utcp->nconnections++] = c;
263 qsort(utcp->connections, utcp->nconnections, sizeof *utcp->connections, compare);
268 struct utcp_connection *utcp_connect(struct utcp *utcp, uint16_t dst, utcp_recv_t recv, void *priv) {
269 struct utcp_connection *c = allocate_connection(utcp, 0, dst);
279 hdr.seq = c->snd.iss;
282 hdr.wnd = c->rcv.wnd;
284 set_state(c, SYN_SENT);
286 utcp->send(utcp, &hdr, sizeof hdr);
293 void utcp_accept(struct utcp_connection *c, utcp_recv_t recv, void *priv) {
294 if(c->reapable || c->state != SYN_RECEIVED) {
295 fprintf(stderr, "Error: accept() called on invalid connection %p in state %s\n", c, strstate[c->state]);
299 fprintf(stderr, "%p accepted, %p %p\n", c, recv, priv);
302 set_state(c, ESTABLISHED);
305 int utcp_send(struct utcp_connection *c, void *data, size_t len) {
307 fprintf(stderr, "Error: send() called on closed connection %p\n", c);
317 fprintf(stderr, "Error: send() called on unconnected connection %p\n", c);
328 fprintf(stderr, "Error: send() called on closing connection %p\n", c);
347 pkt.hdr.src = c->src;
348 pkt.hdr.dst = c->dst;
349 pkt.hdr.seq = c->snd.nxt;
350 pkt.hdr.ack = c->rcv.nxt;
351 pkt.hdr.wnd = c->snd.wnd;
354 memcpy(pkt.data, data, len);
358 c->utcp->send(c->utcp, &pkt, sizeof pkt.hdr + len);
360 // Can we add it to the send window?
362 // Do we need to kick some timers?
367 static void swap_ports(struct hdr *hdr) {
368 uint16_t tmp = hdr->src;
373 static int16_t seqdiff(uint16_t a, uint16_t b) {
377 int utcp_recv(struct utcp *utcp, void *data, size_t len) {
391 fprintf(stderr, "%p got: ", utcp);
392 print_packet(data, len);
395 if(len < sizeof hdr) {
400 memcpy(&hdr, data, sizeof hdr);
404 if(hdr.ctl & ~(SYN | ACK | RST | FIN)) {
409 //list_connections(utcp);
411 struct utcp_connection *c = find_connection(utcp, hdr.dst, hdr.src);
413 // Is it for a new connection?
419 if(hdr.ctl & SYN && !(hdr.ctl & ACK) && utcp->accept && (!utcp->pre_accept || utcp->pre_accept(utcp, hdr.dst)) && (c = allocate_connection(utcp, hdr.dst, hdr.src))) { // LISTEN
421 c->snd.wnd = hdr.wnd;
422 c->rcv.irs = hdr.seq;
423 c->rcv.nxt = c->rcv.irs + 1;
424 set_state(c, SYN_RECEIVED);
428 hdr.ack = c->rcv.irs + 1;
429 hdr.seq = c->snd.iss;
431 utcp->send(utcp, &hdr, sizeof hdr);
439 fprintf(stderr, "%p state %s\n", c->utcp, strstate[c->state]);
441 if(c->state == CLOSED) {
442 fprintf(stderr, "Error: packet recv()d on closed connection %p\n", c);
447 // It is for an existing connection.
449 if(c->state == SYN_SENT) {
451 if(seqdiff(hdr.ack, c->snd.iss) <= 0 || seqdiff(hdr.ack, c->snd.nxt) > 0) {
452 fprintf(stderr, "Invalid ACK, %u %u %u\n", hdr.ack, c->snd.iss, c->snd.nxt);
459 set_state(c, CLOSED);
460 errno = ECONNREFUSED;
466 c->rcv.nxt = hdr.seq + 1;
467 c->rcv.irs = hdr.seq;
468 c->snd.wnd = hdr.wnd;
471 c->snd.una = hdr.ack;
472 if(seqdiff(c->snd.una, c->snd.iss) > 0) {
473 set_state(c, ESTABLISHED);
476 hdr.seq = c->snd.nxt;
477 hdr.ack = c->rcv.nxt;
480 set_state(c, SYN_RECEIVED);
482 hdr.seq = c->snd.iss;
483 hdr.ack = c->rcv.nxt;
486 utcp->send(utcp, &hdr, sizeof hdr);
487 // TODO: queue any data?
497 acceptable = hdr.seq == c->rcv.nxt;
499 acceptable = (hdr.seq >= c->rcv.nxt && hdr.seq < c->rcv.nxt + c->rcv.wnd);
504 acceptable = (hdr.seq >= c->rcv.nxt && hdr.seq < c->rcv.nxt + c->rcv.wnd)
505 || (hdr.seq + len - 1 >= c->rcv.nxt && hdr.seq + len - 1 < c->rcv.nxt + c->rcv.wnd);
508 fprintf(stderr, "Packet not acceptable, %u %u %u %zu\n", hdr.seq, c->rcv.nxt, c->rcv.wnd, len);
514 c->snd.wnd = hdr.wnd;
516 // TODO: check whether segment really starts at rcv.nxt, otherwise trim it.
521 // TODO: delete connection?
527 set_state(c, CLOSED);
534 // TODO: delete connection?
540 set_state(c, CLOSED);
554 set_state(c, CLOSED);
570 if(seqdiff(hdr.ack, c->snd.una) >= 0 && seqdiff(hdr.ack, c->snd.nxt) <= 0)
571 c->utcp->accept(c, hdr.dst);
573 if(c->state != ESTABLISHED)
578 if(seqdiff(hdr.ack, c->snd.una) < 0)
580 if(seqdiff(hdr.ack, c->snd.nxt) > 0)
582 if(seqdiff(hdr.ack, c->snd.una) > 0 && seqdiff(hdr.ack, c->snd.nxt) <= 0) {
583 c->snd.una = hdr.ack;
584 if(seqdiff(c->snd.wl1, hdr.seq) < 0 || (c->snd.wl1 == hdr.seq && seqdiff(c->snd.wl2, hdr.ack) <= 0)) {
585 c->snd.wnd = hdr.wnd;
586 c->snd.wl1 = hdr.seq;
587 c->snd.wl2 = hdr.ack;
592 if(hdr.ack == c->snd.nxt)
593 set_state(c, FIN_WAIT_2);
596 // TODO: If nothing left to send, close.
599 if(hdr.ack == c->snd.nxt) {
600 set_state(c, TIME_WAIT);
604 if(hdr.ack == c->snd.nxt) {
605 set_state(c, CLOSED);
609 // TODO: retransmission of remote FIN, ACK and restart 2 MSL timeout
621 // TODO: process the data, see page 74
640 set_state(c, CLOSE_WAIT);
644 set_state(c, CLOSING);
648 set_state(c, TIME_WAIT);
664 c->recv(c, data, len);
678 hdr.ack = hdr.seq + len;
682 utcp->send(utcp, &hdr, sizeof hdr);
687 hdr.seq = c->snd.nxt;
688 hdr.ack = c->rcv.nxt;
690 utcp->send(utcp, &hdr, sizeof hdr);
691 if(c->state == CLOSE_WAIT || c->state == TIME_WAIT) {
698 int utcp_shutdown(struct utcp_connection *c, int dir) {
705 fprintf(stderr, "Error: shutdown() called on closed connection %p\n", c);
717 set_state(c, CLOSED);
722 set_state(c, FIN_WAIT_1);
728 set_state(c, LAST_ACK);
743 hdr.seq = c->snd.nxt;
744 hdr.ack = c->rcv.nxt;
745 hdr.wnd = c->snd.wnd;
750 c->utcp->send(c->utcp, &hdr, sizeof hdr);
754 int utcp_close(struct utcp_connection *c) {
755 if(utcp_shutdown(c, SHUT_RDWR))
761 int utcp_abort(struct utcp_connection *c) {
768 fprintf(stderr, "Error: abort() called on closed connection %p\n", c);
783 set_state(c, CLOSED);
791 set_state(c, CLOSED);
801 hdr.seq = c->snd.nxt;
806 c->utcp->send(c->utcp, &hdr, sizeof hdr);
810 void utcp_timeout(struct utcp *utcp) {
812 gettimeofday(&now, NULL);
814 for(int i = 0; i < utcp->nconnections; i++) {
815 struct utcp_connection *c = utcp->connections[i];
820 fprintf(stderr, "Reaping %p\n", c);
825 if(c->state == CLOSED)
828 if(c->conn_timeout.tv_sec && timercmp(&c->conn_timeout, &now, <)) {
837 if(c->rtrx_timeout.tv_sec && timercmp(&c->rtrx_timeout, &now, <)) {
838 // TODO: retransmit stuff;
843 struct utcp *utcp_init(utcp_accept_t accept, utcp_pre_accept_t pre_accept, utcp_send_t send, void *priv) {
844 struct utcp *utcp = calloc(1, sizeof *utcp);
848 utcp->accept = accept;
849 utcp->pre_accept = pre_accept;
858 void utcp_exit(struct utcp *utcp) {
861 for(int i = 0; i < utcp->nconnections; i++)
862 free_connection(utcp->connections[i]);