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 int utcp_recv(struct utcp *utcp, void *data, size_t len) {
387 fprintf(stderr, "%p got: ", utcp);
388 print_packet(data, len);
391 if(len < sizeof hdr) {
396 memcpy(&hdr, data, sizeof hdr);
400 if(hdr.ctl & ~(SYN | ACK | RST | FIN)) {
405 //list_connections(utcp);
407 struct utcp_connection *c = find_connection(utcp, hdr.dst, hdr.src);
409 // Is it for a new connection?
415 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
417 c->snd.wnd = hdr.wnd;
418 c->rcv.irs = hdr.seq;
419 c->rcv.nxt = c->rcv.irs + 1;
420 set_state(c, SYN_RECEIVED);
424 hdr.ack = c->rcv.irs + 1;
425 hdr.seq = c->snd.iss;
427 utcp->send(utcp, &hdr, sizeof hdr);
435 fprintf(stderr, "%p state %s\n", c->utcp, strstate[c->state]);
437 if(c->state == CLOSED) {
438 fprintf(stderr, "Error: packet recv()d on closed connection %p\n", c);
443 // It is for an existing connection.
445 if(c->state == SYN_SENT) {
447 if(hdr.ack <= c->snd.iss || hdr.ack > c->snd.nxt) {
448 fprintf(stderr, "Invalid ACK, %u %u %u\n", hdr.ack, c->snd.iss, c->snd.nxt);
455 set_state(c, CLOSED);
456 errno = ECONNREFUSED;
462 c->rcv.nxt = hdr.seq + 1;
463 c->rcv.irs = hdr.seq;
464 c->snd.wnd = hdr.wnd;
467 c->snd.una = hdr.ack;
468 if(c->snd.una > c->snd.iss) {
469 set_state(c, ESTABLISHED);
472 hdr.seq = c->snd.nxt;
473 hdr.ack = c->rcv.nxt;
476 set_state(c, SYN_RECEIVED);
478 hdr.seq = c->snd.iss;
479 hdr.ack = c->rcv.nxt;
482 utcp->send(utcp, &hdr, sizeof hdr);
483 // TODO: queue any data?
493 acceptable = hdr.seq == c->rcv.nxt;
495 acceptable = (hdr.seq >= c->rcv.nxt && hdr.seq < c->rcv.nxt + c->rcv.wnd);
500 acceptable = (hdr.seq >= c->rcv.nxt && hdr.seq < c->rcv.nxt + c->rcv.wnd)
501 || (hdr.seq + len - 1 >= c->rcv.nxt && hdr.seq + len - 1 < c->rcv.nxt + c->rcv.wnd);
504 fprintf(stderr, "Packet not acceptable, %u %u %u %zu\n", hdr.seq, c->rcv.nxt, c->rcv.wnd, len);
510 c->snd.wnd = hdr.wnd;
512 // TODO: check whether segment really starts at rcv.nxt, otherwise trim it.
517 // TODO: delete connection?
523 set_state(c, CLOSED);
530 // TODO: delete connection?
536 set_state(c, CLOSED);
550 set_state(c, CLOSED);
566 if(hdr.ack >= c->snd.una && hdr.ack <= c->snd.nxt)
567 c->utcp->accept(c, hdr.dst);
569 if(c->state != ESTABLISHED)
574 if(hdr.ack < c->snd.una)
576 if(hdr.ack > c->snd.nxt)
578 if(hdr.ack > c->snd.una && hdr.ack <= c->snd.nxt) {
579 c->snd.una = hdr.ack;
580 if(c->snd.wl1 < hdr.seq || (c->snd.wl1 == hdr.seq && c->snd.wl2 <= hdr.ack)) {
581 c->snd.wnd = hdr.wnd;
582 c->snd.wl1 = hdr.seq;
583 c->snd.wl2 = hdr.ack;
588 if(hdr.ack == c->snd.nxt)
589 set_state(c, FIN_WAIT_2);
592 // TODO: If nothing left to send, close.
595 if(hdr.ack == c->snd.nxt) {
596 set_state(c, TIME_WAIT);
600 if(hdr.ack == c->snd.nxt) {
601 set_state(c, CLOSED);
605 // TODO: retransmission of remote FIN, ACK and restart 2 MSL timeout
617 // TODO: process the data, see page 74
636 set_state(c, CLOSE_WAIT);
640 set_state(c, CLOSING);
644 set_state(c, TIME_WAIT);
660 c->recv(c, data, len);
674 hdr.ack = hdr.seq + len;
678 utcp->send(utcp, &hdr, sizeof hdr);
683 hdr.seq = c->snd.nxt;
684 hdr.ack = c->rcv.nxt;
686 utcp->send(utcp, &hdr, sizeof hdr);
687 if(c->state == CLOSE_WAIT || c->state == TIME_WAIT) {
694 int utcp_shutdown(struct utcp_connection *c, int dir) {
701 fprintf(stderr, "Error: shutdown() called on closed connection %p\n", c);
713 set_state(c, CLOSED);
718 set_state(c, FIN_WAIT_1);
724 set_state(c, LAST_ACK);
739 hdr.seq = c->snd.nxt;
740 hdr.ack = c->rcv.nxt;
741 hdr.wnd = c->snd.wnd;
746 c->utcp->send(c->utcp, &hdr, sizeof hdr);
750 int utcp_close(struct utcp_connection *c) {
751 if(utcp_shutdown(c, SHUT_RDWR))
757 int utcp_abort(struct utcp_connection *c) {
764 fprintf(stderr, "Error: abort() called on closed connection %p\n", c);
779 set_state(c, CLOSED);
787 set_state(c, CLOSED);
797 hdr.seq = c->snd.nxt;
802 c->utcp->send(c->utcp, &hdr, sizeof hdr);
806 void utcp_timeout(struct utcp *utcp) {
808 gettimeofday(&now, NULL);
810 for(int i = 0; i < utcp->nconnections; i++) {
811 struct utcp_connection *c = utcp->connections[i];
816 fprintf(stderr, "Reaping %p\n", c);
821 if(c->state == CLOSED)
824 if(c->conn_timeout.tv_sec && timercmp(&c->conn_timeout, &now, <)) {
833 if(c->rtrx_timeout.tv_sec && timercmp(&c->rtrx_timeout, &now, <)) {
834 // TODO: retransmit stuff;
839 struct utcp *utcp_init(utcp_accept_t accept, utcp_pre_accept_t pre_accept, utcp_send_t send, void *priv) {
840 struct utcp *utcp = calloc(1, sizeof *utcp);
844 utcp->accept = accept;
845 utcp->pre_accept = pre_accept;
854 void utcp_exit(struct utcp *utcp) {
857 for(int i = 0; i < utcp->nconnections; i++)
858 free_connection(utcp->connections[i]);