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;
259 c->sndbufsize = 65536;
260 c->sndbuf = malloc(c->sndbufsize);
264 // Add it to the sorted list of connections
266 utcp->connections[utcp->nconnections++] = c;
267 qsort(utcp->connections, utcp->nconnections, sizeof *utcp->connections, compare);
272 struct utcp_connection *utcp_connect(struct utcp *utcp, uint16_t dst, utcp_recv_t recv, void *priv) {
273 struct utcp_connection *c = allocate_connection(utcp, 0, dst);
283 hdr.seq = c->snd.iss;
286 hdr.wnd = c->rcv.wnd;
288 set_state(c, SYN_SENT);
290 utcp->send(utcp, &hdr, sizeof hdr);
297 void utcp_accept(struct utcp_connection *c, utcp_recv_t recv, void *priv) {
298 if(c->reapable || c->state != SYN_RECEIVED) {
299 fprintf(stderr, "Error: accept() called on invalid connection %p in state %s\n", c, strstate[c->state]);
303 fprintf(stderr, "%p accepted, %p %p\n", c, recv, priv);
306 set_state(c, ESTABLISHED);
309 ssize_t utcp_send(struct utcp_connection *c, void *data, size_t len) {
311 fprintf(stderr, "Error: send() called on closed connection %p\n", c);
321 fprintf(stderr, "Error: send() called on unconnected connection %p\n", c);
332 fprintf(stderr, "Error: send() called on closing connection %p\n", c);
337 // Add data to send buffer
347 uint32_t bufused = c->snd.nxt - c->snd.una;
349 if(len > c->sndbufsize - bufused)
350 len = c->sndbufsize - bufused;
352 memcpy(c->sndbuf + (c->snd.nxt - c->snd.una), data, len);
358 char data[c->utcp->mtu];
361 pkt.hdr.src = c->src;
362 pkt.hdr.dst = c->dst;
363 pkt.hdr.ack = c->rcv.nxt;
364 pkt.hdr.wnd = c->snd.wnd;
370 uint32_t seglen = left > c->utcp->mtu ? c->utcp->mtu : left;
371 pkt.hdr.seq = c->snd.nxt;
373 memcpy(pkt.data, data, seglen);
375 c->snd.nxt += seglen;
379 c->utcp->send(c->utcp, &pkt, sizeof pkt.hdr + seglen);
382 fprintf(stderr, "len=%u\n", len);
386 static void swap_ports(struct hdr *hdr) {
387 uint16_t tmp = hdr->src;
392 static int16_t seqdiff(uint16_t a, uint16_t b) {
396 int utcp_recv(struct utcp *utcp, void *data, size_t len) {
410 fprintf(stderr, "%p got: ", utcp);
411 print_packet(data, len);
414 if(len < sizeof hdr) {
419 memcpy(&hdr, data, sizeof hdr);
423 if(hdr.ctl & ~(SYN | ACK | RST | FIN)) {
428 //list_connections(utcp);
430 struct utcp_connection *c = find_connection(utcp, hdr.dst, hdr.src);
432 // Is it for a new connection?
438 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
440 c->snd.wnd = hdr.wnd;
441 c->rcv.irs = hdr.seq;
442 c->rcv.nxt = c->rcv.irs + 1;
443 set_state(c, SYN_RECEIVED);
447 hdr.ack = c->rcv.irs + 1;
448 hdr.seq = c->snd.iss;
450 utcp->send(utcp, &hdr, sizeof hdr);
458 fprintf(stderr, "%p state %s\n", c->utcp, strstate[c->state]);
460 if(c->state == CLOSED) {
461 fprintf(stderr, "Error: packet recv()d on closed connection %p\n", c);
466 // It is for an existing connection.
468 if(c->state == SYN_SENT) {
470 if(seqdiff(hdr.ack, c->snd.iss) <= 0 || seqdiff(hdr.ack, c->snd.nxt) > 0) {
471 fprintf(stderr, "Invalid ACK, %u %u %u\n", hdr.ack, c->snd.iss, c->snd.nxt);
478 set_state(c, CLOSED);
479 errno = ECONNREFUSED;
485 c->rcv.nxt = hdr.seq + 1;
486 c->rcv.irs = hdr.seq;
487 c->snd.wnd = hdr.wnd;
490 c->snd.una = hdr.ack;
491 if(seqdiff(c->snd.una, c->snd.iss) > 0) {
492 set_state(c, ESTABLISHED);
495 hdr.seq = c->snd.nxt;
496 hdr.ack = c->rcv.nxt;
499 set_state(c, SYN_RECEIVED);
501 hdr.seq = c->snd.iss;
502 hdr.ack = c->rcv.nxt;
505 utcp->send(utcp, &hdr, sizeof hdr);
506 // TODO: queue any data?
516 acceptable = hdr.seq == c->rcv.nxt;
518 acceptable = (hdr.seq >= c->rcv.nxt && hdr.seq < c->rcv.nxt + c->rcv.wnd);
523 acceptable = (hdr.seq >= c->rcv.nxt && hdr.seq < c->rcv.nxt + c->rcv.wnd)
524 || (hdr.seq + len - 1 >= c->rcv.nxt && hdr.seq + len - 1 < c->rcv.nxt + c->rcv.wnd);
527 fprintf(stderr, "Packet not acceptable, %u %u %u %zu\n", hdr.seq, c->rcv.nxt, c->rcv.wnd, len);
533 c->snd.wnd = hdr.wnd;
535 // TODO: check whether segment really starts at rcv.nxt, otherwise trim it.
540 // TODO: delete connection?
546 set_state(c, CLOSED);
553 // TODO: delete connection?
559 set_state(c, CLOSED);
573 set_state(c, CLOSED);
589 if(seqdiff(hdr.ack, c->snd.una) >= 0 && seqdiff(hdr.ack, c->snd.nxt) <= 0)
590 c->utcp->accept(c, hdr.dst);
592 if(c->state != ESTABLISHED)
597 if(seqdiff(hdr.ack, c->snd.una) < 0)
599 if(seqdiff(hdr.ack, c->snd.nxt) > 0)
601 if(seqdiff(hdr.ack, c->snd.una) > 0 && seqdiff(hdr.ack, c->snd.nxt) <= 0) {
602 c->snd.una = hdr.ack;
603 if(seqdiff(c->snd.wl1, hdr.seq) < 0 || (c->snd.wl1 == hdr.seq && seqdiff(c->snd.wl2, hdr.ack) <= 0)) {
604 c->snd.wnd = hdr.wnd;
605 c->snd.wl1 = hdr.seq;
606 c->snd.wl2 = hdr.ack;
611 if(hdr.ack == c->snd.nxt)
612 set_state(c, FIN_WAIT_2);
615 // TODO: If nothing left to send, close.
618 if(hdr.ack == c->snd.nxt) {
619 set_state(c, TIME_WAIT);
623 if(hdr.ack == c->snd.nxt) {
624 set_state(c, CLOSED);
628 // TODO: retransmission of remote FIN, ACK and restart 2 MSL timeout
640 // TODO: process the data, see page 74
659 set_state(c, CLOSE_WAIT);
663 set_state(c, CLOSING);
667 set_state(c, TIME_WAIT);
683 c->recv(c, data, len);
697 hdr.ack = hdr.seq + len;
701 utcp->send(utcp, &hdr, sizeof hdr);
706 hdr.seq = c->snd.nxt;
707 hdr.ack = c->rcv.nxt;
709 utcp->send(utcp, &hdr, sizeof hdr);
710 if(c->state == CLOSE_WAIT || c->state == TIME_WAIT) {
717 int utcp_shutdown(struct utcp_connection *c, int dir) {
724 fprintf(stderr, "Error: shutdown() called on closed connection %p\n", c);
736 set_state(c, CLOSED);
741 set_state(c, FIN_WAIT_1);
747 set_state(c, LAST_ACK);
762 hdr.seq = c->snd.nxt;
763 hdr.ack = c->rcv.nxt;
764 hdr.wnd = c->snd.wnd;
769 c->utcp->send(c->utcp, &hdr, sizeof hdr);
773 int utcp_close(struct utcp_connection *c) {
774 if(utcp_shutdown(c, SHUT_RDWR))
780 int utcp_abort(struct utcp_connection *c) {
787 fprintf(stderr, "Error: abort() called on closed connection %p\n", c);
802 set_state(c, CLOSED);
810 set_state(c, CLOSED);
820 hdr.seq = c->snd.nxt;
825 c->utcp->send(c->utcp, &hdr, sizeof hdr);
829 void utcp_timeout(struct utcp *utcp) {
831 gettimeofday(&now, NULL);
833 for(int i = 0; i < utcp->nconnections; i++) {
834 struct utcp_connection *c = utcp->connections[i];
839 fprintf(stderr, "Reaping %p\n", c);
844 if(c->state == CLOSED)
847 if(c->conn_timeout.tv_sec && timercmp(&c->conn_timeout, &now, <)) {
856 if(c->rtrx_timeout.tv_sec && timercmp(&c->rtrx_timeout, &now, <)) {
857 // TODO: retransmit stuff;
862 struct utcp *utcp_init(utcp_accept_t accept, utcp_pre_accept_t pre_accept, utcp_send_t send, void *priv) {
863 struct utcp *utcp = calloc(1, sizeof *utcp);
867 utcp->accept = accept;
868 utcp->pre_accept = pre_accept;
877 void utcp_exit(struct utcp *utcp) {
880 for(int i = 0; i < utcp->nconnections; i++)
881 free_connection(utcp->connections[i]);