From 027abc36cfb0a8247625f5f6af65b7ce63065a33 Mon Sep 17 00:00:00 2001 From: Guus Sliepen Date: Mon, 19 Oct 2015 22:04:50 +0200 Subject: [PATCH 01/16] Fix bugs in sack_consume() causing data corruption or abort()s. Put in a lengthy comment with some ASCII-art to describe what we are actually trying to do in this function. --- utcp.c | 23 ++++++++++++++++++++--- 1 file changed, 20 insertions(+), 3 deletions(-) diff --git a/utcp.c b/utcp.c index 7c57701..607af2d 100644 --- a/utcp.c +++ b/utcp.c @@ -633,7 +633,24 @@ cleanup: free(pkt); } -// Update receive buffer and SACK entries after consuming data. +/* Update receive buffer and SACK entries after consuming data. + * + * Situation: + * + * |.....0000..1111111111.....22222......3333| + * |---------------^ + * + * 0..3 represent the SACK entries. The ^ indicates up to which point we want + * to remove data from the receive buffer. The idea is to substract "len" + * from the offset of all the SACK entries, and then remove/cut down entries + * that are shifted to before the start of the receive buffer. + * + * There are three cases: + * - the SACK entry is ahead of ^, in that case just change the offset. + * - the SACK entry starts before and ends after ^, so we have to + * change both its offset and size. + * - the SACK entry is completely before ^, in that case delete it. + */ static void sack_consume(struct utcp_connection *c, size_t len) { debug("sack_consume %zu\n", len); if(len > c->rcvbuf.used) @@ -646,13 +663,13 @@ static void sack_consume(struct utcp_connection *c, size_t len) { c->sacks[i].offset -= len; i++; } else if(len < c->sacks[i].offset + c->sacks[i].len) { - c->sacks[i].offset = 0; c->sacks[i].len -= len - c->sacks[i].offset; + c->sacks[i].offset = 0; i++; } else { if(i < NSACKS - 1) { memmove(&c->sacks[i], &c->sacks[i + 1], (NSACKS - 1 - i) * sizeof c->sacks[i]); - c->sacks[i + 1].len = 0; + c->sacks[NSACKS - 1].len = 0; } else { c->sacks[i].len = 0; break; -- 2.39.2 From 05ee8ad65c1c7f1318e1185ddf299a2cce6c6474 Mon Sep 17 00:00:00 2001 From: Guus Sliepen Date: Thu, 29 Oct 2015 16:26:54 +0100 Subject: [PATCH 02/16] Always check the return value of malloc(). --- test.c | 4 ++++ utcp.c | 4 ++++ 2 files changed, 8 insertions(+) diff --git a/test.c b/test.c index 47732e4..3491e29 100644 --- a/test.c +++ b/test.c @@ -73,6 +73,10 @@ ssize_t do_send(struct utcp *utcp, const void *data, size_t len) { return len; if(!reorder_data && drand48() < reorder) { reorder_data = malloc(len); + if(!reorder_data) { + debug("Out of memory\n"); + return len; + } reorder_len = len; memcpy(reorder_data, data, len); reorder_countdown = 1 + drand48() * reorder_dist; diff --git a/utcp.c b/utcp.c index 607af2d..95a82c4 100644 --- a/utcp.c +++ b/utcp.c @@ -88,6 +88,10 @@ static void print_packet(struct utcp *utcp, const char *dir, const void *pkt, si if(len > sizeof hdr) { uint32_t datalen = len - sizeof hdr; uint8_t *str = malloc((datalen << 1) + 7); + if(!str) { + debug("out of memory"); + return; + } memcpy(str, " data=", 6); uint8_t *strptr = str + 6; const uint8_t *data = pkt; -- 2.39.2 From f02ecc4e4cf3860c6f3d833bfb549df1adab7764 Mon Sep 17 00:00:00 2001 From: Guus Sliepen Date: Thu, 29 Oct 2015 16:31:17 +0100 Subject: [PATCH 03/16] Don't use ?: without the middle argument. --- test.c | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-) diff --git a/test.c b/test.c index 3491e29..d138fd6 100644 --- a/test.c +++ b/test.c @@ -25,7 +25,7 @@ long outpktno; long dropfrom; long dropto; double reorder; -long reorder_dist; +long reorder_dist = 10; double dropin; double dropout; long total_out; @@ -110,12 +110,12 @@ int main(int argc, char *argv[]) { bool server = argc == 2; bool connected = false; - dropin = atof(getenv("DROPIN") ?: "0"); - dropout = atof(getenv("DROPOUT") ?: "0"); - dropfrom = atoi(getenv("DROPFROM") ?: "0"); - dropto = atoi(getenv("DROPTO") ?: "0"); - reorder = atof(getenv("REORDER") ?: "0"); - reorder_dist = atoi(getenv("REORDER_DIST") ?: "10"); + if(getenv("DROPIN")) dropin = atof(getenv("DROPIN")); + if(getenv("DROPOUT")) dropout = atof(getenv("DROPOUT")); + if(getenv("DROPFROM")) dropfrom = atoi(getenv("DROPFROM")); + if(getenv("DROPTO")) dropto = atoi(getenv("DROPTO")); + if(getenv("REORDER")) reorder = atof(getenv("REORDER")); + if(getenv("REORDER_DIST")) reorder_dist = atoi(getenv("REORDER_DIST")); if(dropto < dropfrom) dropto = 1 << 30; -- 2.39.2 From b0cd5e3cc7c991afbab53f64f7a57887f6c5d403 Mon Sep 17 00:00:00 2001 From: Guus Sliepen Date: Thu, 29 Oct 2015 16:33:45 +0100 Subject: [PATCH 04/16] Make max() an inline function. --- utcp.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/utcp.c b/utcp.c index 95a82c4..fc147c2 100644 --- a/utcp.c +++ b/utcp.c @@ -53,9 +53,9 @@ } while (0) #endif -#ifndef max -#define max(a, b) ((a) > (b) ? (a) : (b)) -#endif +static inline size_t max(size_t a, size_t b) { + return a > b ? a : b; +} #ifdef UTCP_DEBUG #include -- 2.39.2 From c66102829d1fce09cdf8dcba94b14255448a2395 Mon Sep 17 00:00:00 2001 From: Guus Sliepen Date: Thu, 29 Oct 2015 16:35:16 +0100 Subject: [PATCH 05/16] Clarify description of sack_consume(). --- utcp.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/utcp.c b/utcp.c index fc147c2..57b3157 100644 --- a/utcp.c +++ b/utcp.c @@ -650,7 +650,7 @@ cleanup: * that are shifted to before the start of the receive buffer. * * There are three cases: - * - the SACK entry is ahead of ^, in that case just change the offset. + * - the SACK entry is after ^, in that case just change the offset. * - the SACK entry starts before and ends after ^, so we have to * change both its offset and size. * - the SACK entry is completely before ^, in that case delete it. -- 2.39.2 From de4f8ad9205a0fcf3198d75ad0747fac9faa9787 Mon Sep 17 00:00:00 2001 From: Guus Sliepen Date: Thu, 29 Oct 2015 16:36:39 +0100 Subject: [PATCH 06/16] Add debug message when dropping a packet because all SACK entries are used. --- utcp.c | 2 ++ 1 file changed, 2 insertions(+) diff --git a/utcp.c b/utcp.c index 57b3157..1627be7 100644 --- a/utcp.c +++ b/utcp.c @@ -706,6 +706,8 @@ static void handle_out_of_order(struct utcp_connection *c, uint32_t offset, cons memmove(&c->sacks[i + 1], &c->sacks[i], (NSACKS - i - 1) * sizeof c->sacks[i]); c->sacks[i].offset = offset; c->sacks[i].len = rxd; + } else { + debug("SACK entries full, dropping packet\n"); } break; } else { // merge -- 2.39.2 From ab52e5aeafdda3721a3843f489f2c43c05c45033 Mon Sep 17 00:00:00 2001 From: Guus Sliepen Date: Sun, 2 Jul 2017 12:13:24 +0200 Subject: [PATCH 07/16] Define USEC_PER_SEC, use "sec" and "usec" in comments. --- utcp.c | 6 +++--- utcp_priv.h | 17 +++++++++-------- 2 files changed, 12 insertions(+), 11 deletions(-) diff --git a/utcp.c b/utcp.c index 1627be7..f2354b1 100644 --- a/utcp.c +++ b/utcp.c @@ -49,7 +49,7 @@ (r)->tv_sec = (a)->tv_sec - (b)->tv_sec;\ (r)->tv_usec = (a)->tv_usec - (b)->tv_usec;\ if((r)->tv_usec < 0)\ - (r)->tv_sec--, (r)->tv_usec += 1000000;\ + (r)->tv_sec--, (r)->tv_usec += USEC_PER_SEC;\ } while (0) #endif @@ -1434,8 +1434,8 @@ struct utcp *utcp_init(utcp_accept_t accept, utcp_pre_accept_t pre_accept, utcp_ utcp->send = send; utcp->priv = priv; utcp->mtu = DEFAULT_MTU; - utcp->timeout = DEFAULT_USER_TIMEOUT; // s - utcp->rto = START_RTO; // us + utcp->timeout = DEFAULT_USER_TIMEOUT; // sec + utcp->rto = START_RTO; // usec return utcp; } diff --git a/utcp_priv.h b/utcp_priv.h index 24f4158..143ed60 100644 --- a/utcp_priv.h +++ b/utcp_priv.h @@ -38,10 +38,11 @@ #define DEFAULT_MTU 1000 -#define DEFAULT_USER_TIMEOUT 60 // s -#define CLOCK_GRANULARITY 1000 // us -#define START_RTO 1000000 // us -#define MAX_RTO 3000000 // us +#define USEC_PER_SEC 1000000 +#define DEFAULT_USER_TIMEOUT 60 // sec +#define CLOCK_GRANULARITY 1000 // usec +#define START_RTO 1000000 // usec +#define MAX_RTO 3000000 // usec struct hdr { uint16_t src; // Source port @@ -164,13 +165,13 @@ struct utcp { // Global socket options uint16_t mtu; - int timeout; // s + int timeout; // sec // RTT variables - uint32_t srtt; // us - uint32_t rttvar; // us - uint32_t rto; // us + uint32_t srtt; // usec + uint32_t rttvar; // usec + uint32_t rto; // usec // Connection management -- 2.39.2 From d91fb4d8ac423f782ceb863b20e40095b891231b Mon Sep 17 00:00:00 2001 From: Guus Sliepen Date: Fri, 30 Oct 2015 23:16:24 +0100 Subject: [PATCH 08/16] Log when dropping packets in the test program. --- test.c | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) diff --git a/test.c b/test.c index d138fd6..15d5772 100644 --- a/test.c +++ b/test.c @@ -69,8 +69,10 @@ ssize_t do_send(struct utcp *utcp, const void *data, size_t len) { int s = *(int *)utcp->priv; outpktno++; if(outpktno >= dropfrom && outpktno < dropto) { - if(drand48() < dropout) + if(drand48() < dropout) { + debug("Dropped outgoing packet\n"); return len; + } if(!reorder_data && drand48() < reorder) { reorder_data = malloc(len); if(!reorder_data) { @@ -214,6 +216,8 @@ int main(int argc, char *argv[]) { if(inpktno >= dropto || inpktno < dropfrom || drand48() >= dropin) { total_in += len; utcp_recv(u, buf, len); + } else { + debug("Dropped incoming packet\n"); } } -- 2.39.2 From 4e0031cf31b22f6cff80969c3e6e11c3c3001b04 Mon Sep 17 00:00:00 2001 From: Guus Sliepen Date: Fri, 30 Oct 2015 23:16:47 +0100 Subject: [PATCH 09/16] Ensure utcp_close() works properly on a socket that is in the CLOSED state. --- utcp.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/utcp.c b/utcp.c index f2354b1..026fb31 100644 --- a/utcp.c +++ b/utcp.c @@ -1294,7 +1294,7 @@ int utcp_shutdown(struct utcp_connection *c, int dir) { } int utcp_close(struct utcp_connection *c) { - if(utcp_shutdown(c, SHUT_RDWR)) + if(utcp_shutdown(c, SHUT_RDWR) && errno != ENOTCONN) return -1; c->recv = NULL; c->poll = NULL; -- 2.39.2 From 526b4278d148a1d902ca4144e2f6c6f8436aa06e Mon Sep 17 00:00:00 2001 From: Guus Sliepen Date: Fri, 30 Oct 2015 23:42:35 +0100 Subject: [PATCH 10/16] Add more debug messages. --- test.c | 3 ++- utcp.c | 4 +++- 2 files changed, 5 insertions(+), 2 deletions(-) diff --git a/test.c b/test.c index 15d5772..a078e1f 100644 --- a/test.c +++ b/test.c @@ -215,7 +215,8 @@ int main(int argc, char *argv[]) { inpktno++; if(inpktno >= dropto || inpktno < dropfrom || drand48() >= dropin) { total_in += len; - utcp_recv(u, buf, len); + if(utcp_recv(u, buf, len) == -1) + debug("Error receiving UTCP packet: %s\n", strerror(errno)); } else { debug("Dropped incoming packet\n"); } diff --git a/utcp.c b/utcp.c index 026fb31..9bae7b9 100644 --- a/utcp.c +++ b/utcp.c @@ -857,8 +857,10 @@ ssize_t utcp_recv(struct utcp *utcp, const void *data, size_t len) { // In case this is for a CLOSED connection, ignore the packet. // TODO: make it so incoming packets can never match a CLOSED connection. - if(c->state == CLOSED) + if(c->state == CLOSED) { + debug("Got packet for closed connection\n"); return 0; + } // It is for an existing connection. -- 2.39.2 From 5bad36c4252858693b5cfe59a94540ccd2b0be42 Mon Sep 17 00:00:00 2001 From: Guus Sliepen Date: Sun, 15 Nov 2015 20:35:30 +0100 Subject: [PATCH 11/16] Only log debug messages in test program when UTCP_DEBUG is defined. --- test.c | 4 ++++ 1 file changed, 4 insertions(+) diff --git a/test.c b/test.c index a078e1f..81244f9 100644 --- a/test.c +++ b/test.c @@ -35,6 +35,7 @@ char *reorder_data; size_t reorder_len; int reorder_countdown; +#if UTCP_DEBUG void debug(const char *format, ...) { struct timeval now; gettimeofday(&now, NULL); @@ -44,6 +45,9 @@ void debug(const char *format, ...) { vfprintf(stderr, format, ap); va_end(ap); } +#else +#define debug(...) +#endif ssize_t do_recv(struct utcp_connection *c, const void *data, size_t len) { if(!data || !len) { -- 2.39.2 From 16ecd6d75bfabb97193581bcc8095652759cdb8e Mon Sep 17 00:00:00 2001 From: Guus Sliepen Date: Thu, 17 Dec 2015 18:07:19 +0100 Subject: [PATCH 12/16] Fix buffer resizing logic in buffer_put_at(). When growing the buffer when it's not big enough for new data, the current size is doubled repeatedly until it is big enough for the new data. The required new size is stored in the variable "required", however the doubling loop exited when the new size was at least buf->used + len, which might be much smaller than "required" if an out-of-order packet is received. --- utcp.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/utcp.c b/utcp.c index 9bae7b9..13f4658 100644 --- a/utcp.c +++ b/utcp.c @@ -173,7 +173,7 @@ static ssize_t buffer_put_at(struct buffer *buf, size_t offset, const void *data } else { do { newsize *= 2; - } while(newsize < buf->used + len); + } while(newsize < required); } if(newsize > buf->maxsize) newsize = buf->maxsize; -- 2.39.2 From 2b97914c7e2d7d589258cc18e58ad92e32a3457c Mon Sep 17 00:00:00 2001 From: Guus Sliepen Date: Sun, 2 Jul 2017 12:47:58 +0200 Subject: [PATCH 13/16] Fix compiler warnings. --- utcp.c | 40 +++++++++++++++------------------------- 1 file changed, 15 insertions(+), 25 deletions(-) diff --git a/utcp.c b/utcp.c index 13f4658..bb29de5 100644 --- a/utcp.c +++ b/utcp.c @@ -70,12 +70,12 @@ static void debug(const char *format, ...) { static void print_packet(struct utcp *utcp, const char *dir, const void *pkt, size_t len) { struct hdr hdr; if(len < sizeof hdr) { - debug("%p %s: short packet (%zu bytes)\n", utcp, dir, len); + debug("%p %s: short packet (%lu bytes)\n", utcp, dir, (unsigned long)len); return; } memcpy(&hdr, pkt, sizeof hdr); - fprintf (stderr, "%p %s: len=%zu, src=%u dst=%u seq=%u ack=%u wnd=%u ctl=", utcp, dir, len, hdr.src, hdr.dst, hdr.seq, hdr.ack, hdr.wnd); + debug("%p %s: len=%lu, src=%u dst=%u seq=%u ack=%u wnd=%u ctl=", utcp, dir, (unsigned long)len, hdr.src, hdr.dst, hdr.seq, hdr.ack, hdr.wnd); if(hdr.ctl & SYN) debug("SYN"); if(hdr.ctl & RST) @@ -87,27 +87,17 @@ static void print_packet(struct utcp *utcp, const char *dir, const void *pkt, si if(len > sizeof hdr) { uint32_t datalen = len - sizeof hdr; - uint8_t *str = malloc((datalen << 1) + 7); - if(!str) { - debug("out of memory"); - return; - } - memcpy(str, " data=", 6); - uint8_t *strptr = str + 6; - const uint8_t *data = pkt; - const uint8_t *dataend = data + datalen; - - while(data != dataend) { - *strptr = (*data >> 4) > 9? (*data >> 4) + 55 : (*data >> 4) + 48; - ++strptr; - *strptr = (*data & 0xf) > 9? (*data & 0xf) + 55 : (*data & 0xf) + 48; - ++strptr; - ++data; + const uint8_t *data = (uint8_t *)pkt + sizeof hdr; + char str[datalen * 2 + 1]; + char *p = str; + + for(uint32_t i = 0; i < datalen; i++) { + *p++ = "0123456789ABCDEF"[data[i] >> 4]; + *p++ = "0123456789ABCDEF"[data[i] & 15]; } - *strptr = 0; + *p = 0; - debug(str); - free(str); + debug(" data=%s", str); } debug("\n"); @@ -155,7 +145,7 @@ static ssize_t buffer_put_at(struct buffer *buf, size_t offset, const void *data if(buf->maxsize <= buf->used) return 0; - debug("buffer_put_at %zu %zu %zu\n", buf->used, offset, len); + debug("buffer_put_at %lu %lu %lu\n", (unsigned long)buf->used, (unsigned long)offset, (unsigned long)len); size_t required = offset + len; if(required > buf->maxsize) { @@ -656,7 +646,7 @@ cleanup: * - the SACK entry is completely before ^, in that case delete it. */ static void sack_consume(struct utcp_connection *c, size_t len) { - debug("sack_consume %zu\n", len); + debug("sack_consume %lu\n", (unsigned long)len); if(len > c->rcvbuf.used) abort(); @@ -732,7 +722,7 @@ static void handle_out_of_order(struct utcp_connection *c, uint32_t offset, cons static void handle_in_order(struct utcp_connection *c, const void *data, size_t len) { // Check if we can process out-of-order data now. if(c->sacks[0].len && len >= c->sacks[0].offset) { // TODO: handle overlap with second SACK - debug("incoming packet len %zu connected with SACK at %u\n", len, c->sacks[0].offset); + debug("incoming packet len %lu connected with SACK at %u\n", (unsigned long)len, c->sacks[0].offset); buffer_put_at(&c->rcvbuf, 0, data, len); // TODO: handle return value len = max(len, c->sacks[0].offset + c->sacks[0].len); data = c->rcvbuf.data; @@ -912,7 +902,7 @@ ssize_t utcp_recv(struct utcp *utcp, const void *data, size_t len) { } if(!acceptable) { - debug("Packet not acceptable, %u <= %u + %zu < %u\n", c->rcv.nxt, hdr.seq, len, c->rcv.nxt + c->rcvbuf.maxsize); + debug("Packet not acceptable, %u <= %u + %lu < %u\n", c->rcv.nxt, hdr.seq, (unsigned long)len, c->rcv.nxt + c->rcvbuf.maxsize); // Ignore unacceptable RST packets. if(hdr.ctl & RST) return 0; -- 2.39.2 From b52e9aa456dfeedfaa8c3be0e8347d1e1477b611 Mon Sep 17 00:00:00 2001 From: Guus Sliepen Date: Sun, 2 Jul 2017 14:58:08 +0200 Subject: [PATCH 14/16] Allow test program to compare input to a reference file. --- test.c | 16 ++++++++++++++++ 1 file changed, 16 insertions(+) diff --git a/test.c b/test.c index 81244f9..4a1bf16 100644 --- a/test.c +++ b/test.c @@ -30,6 +30,7 @@ double dropin; double dropout; long total_out; long total_in; +FILE *reference; char *reorder_data; size_t reorder_len; @@ -60,6 +61,17 @@ ssize_t do_recv(struct utcp_connection *c, const void *data, size_t len) { } return -1; } + if(reference) { + char buf[len]; + if(fread(buf, len, 1, reference) != 1) { + debug("Error reading reference\n"); + abort(); + } + if(memcmp(buf, data, len)) { + debug("Received data differs from reference\n"); + abort(); + } + } return write(1, data, len); } @@ -123,6 +135,10 @@ int main(int argc, char *argv[]) { if(getenv("REORDER")) reorder = atof(getenv("REORDER")); if(getenv("REORDER_DIST")) reorder_dist = atoi(getenv("REORDER_DIST")); + char *reference_filename = getenv("REFERENCE"); + if(reference_filename) + reference = fopen(reference_filename, "r"); + if(dropto < dropfrom) dropto = 1 << 30; -- 2.39.2 From 7271cf87721ab667a03f50bd40b4a8ec83b989d3 Mon Sep 17 00:00:00 2001 From: Guus Sliepen Date: Sun, 2 Jul 2017 14:58:56 +0200 Subject: [PATCH 15/16] Remove two unnecessary calls to abort(). --- utcp.c | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-) diff --git a/utcp.c b/utcp.c index bb29de5..b0ba054 100644 --- a/utcp.c +++ b/utcp.c @@ -151,7 +151,6 @@ static ssize_t buffer_put_at(struct buffer *buf, size_t offset, const void *data if(required > buf->maxsize) { if(offset >= buf->maxsize) return 0; - abort(); len = buf->maxsize - offset; required = buf->maxsize; } @@ -647,8 +646,11 @@ cleanup: */ static void sack_consume(struct utcp_connection *c, size_t len) { debug("sack_consume %lu\n", (unsigned long)len); - if(len > c->rcvbuf.used) - abort(); + if(len > c->rcvbuf.used) { + debug("All SACK entries consumed"); + c->sacks[0].len = 0; + return; + } buffer_get(&c->rcvbuf, NULL, len); -- 2.39.2 From ff52b8b4f37eeb4e0bfafb00d403f28395c2c957 Mon Sep 17 00:00:00 2001 From: Guus Sliepen Date: Sun, 2 Jul 2017 15:43:57 +0200 Subject: [PATCH 16/16] Fix handling retransmitted data when the receive buffer is full. --- utcp.c | 3 --- 1 file changed, 3 deletions(-) diff --git a/utcp.c b/utcp.c index b0ba054..6b882c6 100644 --- a/utcp.c +++ b/utcp.c @@ -142,9 +142,6 @@ static int32_t seqdiff(uint32_t a, uint32_t b) { // Store data into the buffer static ssize_t buffer_put_at(struct buffer *buf, size_t offset, const void *data, size_t len) { - if(buf->maxsize <= buf->used) - return 0; - debug("buffer_put_at %lu %lu %lu\n", (unsigned long)buf->used, (unsigned long)offset, (unsigned long)len); size_t required = offset + len; -- 2.39.2