From patchwork Thu Oct 8 20:51:37 2026 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Gert Doering X-Patchwork-Id: 5452 Return-Path: Delivered-To: patchwork@openvpn.net Received: by 2002:a05:7000:32d1:b0:8d1:cccb:4552 with SMTP id y17csp2238880mad; Thu, 8 Oct 2026 13:51:57 -0700 (PDT) X-Forwarded-Encrypted: i=2; AKwUvBycGjAot1CcdWlypz3OPNtXEaFaDsiKamrWCsGdrWmAz4nlFJ9MTUz9myoVKMSM+yG3mTBt5f2x198=@openvpn.net X-Received: by 2002:a05:6820:4b97:b0:6c0:853f:7e6e with SMTP id 006d021491bc7-6e7a337e5famr6110598eaf.7.1791492717398; Thu, 08 Oct 2026 13:51:57 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1791492717; cv=none; d=google.com; s=arc-20260327; b=l9wLL7PIIKanb5puZDB4K7CY19SpQFwdB6FY+1o+GKfoHD4R6zpmoXgceYsuNPYv+K eT55PaFBMi9jtoUG87dpXYr/ihxaTGsxooxawIj+DFPmBP1WnUefElaBVJlSRwEF6blK jtYtOQIj7JlHXu3B0F+cTrglcSsy6M48XOTz3Bb7bCFoDY8if3b0yXv0RttzSwL4eFjx K4cnHIQawnSE3oTpy8v+ZV6hTFDWGHpO8HhRhEwWia63ey0Wu6sgHu7b5QoTKyCONVKJ Ie+MJY+LxV7HxlZxi5m/jBHmFdlityG1YpcKZXtCWr3LyhAuDGSevJgB4mIHUEvLPm0R cjLA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20260327; h=errors-to:content-transfer-encoding:list-subscribe:list-help :list-post:list-archive:list-unsubscribe:list-id:precedence:subject :mime-version:references:in-reply-to:message-id:date:to:from :dkim-signature:dkim-signature:dkim-signature; bh=8Xkc2HPBG+WJCKASLY79oKPtM1YEXk7rtUxl0rQtXzM=; fh=4NbAC/LsuMLI0S0hprUlLSLCiHwg6SCAifhH718Jh0Q=; b=aB0X6n/77IP/Ha73p/vPpb9RkgKCARxX6p1cXXc/FI6pctBsIJuVHtznHAkos2Hfra sW6AiTxdudo7mM7lCDCvtEQ95E1rh1r0Qxo3GM6OSaU1TCBiXfauOzgFh7ORyIlkCEgT tj3zwMhBrbHUeQHh0cA60WbmJEdTchsFwGPMuavzjcEx9CILVMhtH2+83Dt3L/rXxe1M 4TB3wIyTQA1pfNU/b26CCJQvqq+faGUyoKPyG3nwXDPk2GlxyiRbeAQ3/hpUiyaNpkTj iYl57qpn/1CXQ7wyF+Tfmg5HsYHSawS4rg2NCni20NeymquRcGcrp3JBB00OIrlrcpNh vgMw==; dara=google.com ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@lists.sourceforge.net header.s=beta header.b="Ssv2A/W9"; dkim=neutral (body hash did not verify) header.i=@sourceforge.net header.s=x header.b=A7tclUNF; dkim=neutral (body hash did not verify) header.i=@sf.net header.s=x header.b=YhQifxWl; spf=pass (google.com: domain of openvpn-devel-bounces@lists.sourceforge.net designates 216.105.38.7 as permitted sender) smtp.mailfrom=openvpn-devel-bounces@lists.sourceforge.net; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=muc.de Received: from lists.sourceforge.net (lists.sourceforge.net. [216.105.38.7]) by mx.google.com with ESMTPS id 006d021491bc7-6ee7a9d09aesi965808eaf.65.2026.10.08.13.51.57 (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Thu, 08 Oct 2026 13:51:57 -0700 (PDT) Received-SPF: pass (google.com: domain of openvpn-devel-bounces@lists.sourceforge.net designates 216.105.38.7 as permitted sender) client-ip=216.105.38.7; Authentication-Results: mx.google.com; dkim=pass header.i=@lists.sourceforge.net header.s=beta header.b="Ssv2A/W9"; dkim=neutral (body hash did not verify) header.i=@sourceforge.net header.s=x header.b=A7tclUNF; dkim=neutral (body hash did not verify) header.i=@sf.net header.s=x header.b=YhQifxWl; spf=pass (google.com: domain of openvpn-devel-bounces@lists.sourceforge.net designates 216.105.38.7 as permitted sender) smtp.mailfrom=openvpn-devel-bounces@lists.sourceforge.net; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=muc.de DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.sourceforge.net; s=beta; h=Content-Transfer-Encoding:Content-Type: List-Subscribe:List-Help:List-Post:List-Archive:List-Unsubscribe:List-Id: Subject:MIME-Version:References:In-Reply-To:Message-ID:Date:To:From:Sender: Reply-To:Cc:Content-ID:Content-Description:Resent-Date:Resent-From: Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:List-Owner; bh=8Xkc2HPBG+WJCKASLY79oKPtM1YEXk7rtUxl0rQtXzM=; b=Ssv2A/W9ff4i5awGDuk7+H3zk4 v0J9EI+80C4xIdfc/mS2Hw4DwNjv/Os3bfVz8hGi2uC633h8X4w+qH6Zb5Ml2vQdY17CgB2b9QUZD baXr8cVpEItrzHpVmOeXYwOpAY8SX0/0hq+R6IaqSj0l5ZrFPsoAfpDmz2inZ8ZrJKbs=; Received: from [127.0.0.1] (helo=sfs-ml-1.v29.lw.sourceforge.com) by sfs-ml-1.v29.lw.sourceforge.com with esmtp (Exim 4.95) (envelope-from ) id 1xEv5n-0001NR-C9; Thu, 08 Oct 2026 20:51:52 +0000 Received: from [172.30.29.66] (helo=mx.sourceforge.net) by sfs-ml-1.v29.lw.sourceforge.com with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.95) (envelope-from ) id 1xEv5l-0001NI-UU for openvpn-devel@lists.sourceforge.net; Thu, 08 Oct 2026 20:51:51 +0000 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=sourceforge.net; s=x; h=Content-Transfer-Encoding:MIME-Version:References: In-Reply-To:Message-ID:Date:Subject:To:From:Sender:Reply-To:Cc:Content-Type: Content-ID:Content-Description:Resent-Date:Resent-From:Resent-Sender: Resent-To:Resent-Cc:Resent-Message-ID:List-Id:List-Help:List-Unsubscribe: List-Subscribe:List-Post:List-Owner:List-Archive; bh=i684JQYfoYY8tdg3FunAFb/Gf4AwvTp955YNYXZ1x3M=; b=A7tclUNFK/i5vnoEoHRumrZsWj l56KbcQVVw3BZbbdu8sv8cBwb7DHSDaI9YOgO8G+52O3vtZnRK5vjfwO8QfllLXB/vg933tUa4+zR rk0YdOvAtD56JcvgI46p1qeOwGXetHuCLdz9300vG3EbGrIpcTb4d74T+ws1fluZhZLo=; DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=sf.net; s=x ; h=Content-Transfer-Encoding:MIME-Version:References:In-Reply-To:Message-ID: Date:Subject:To:From:Sender:Reply-To:Cc:Content-Type:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=i684JQYfoYY8tdg3FunAFb/Gf4AwvTp955YNYXZ1x3M=; b=YhQifxWlhdSdmzBRM0NUrHbJqY grvBnCTccxvbIU9W8eCfhL5shnEfVWsnrW54oTKq9RSSh0evEJ9h8rgE0Xk28gXOim/Imh17DomQ3 UIV5FdFufZAjxZiNM894CA27/SGUzy8qPugVybEZdyhWvzTu4AKUAhNdzU/8W8u7YVhg=; Received: from [193.149.48.129] (helo=blue.greenie.muc.de) by sfi-mx-1.v28.lw.sourceforge.com with esmtps (TLS1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (Exim 4.95) id 1xEv5h-0005PE-Qk for openvpn-devel@lists.sourceforge.net; Thu, 08 Oct 2026 20:51:51 +0000 Received: from blue.greenie.muc.de (localhost [127.0.0.1]) by blue.greenie.muc.de (8.18.1/8.18.1) with ESMTP id 698Kph7h028467 for ; Thu, 8 Oct 2026 22:51:43 +0200 Received: (from gert@localhost) by blue.greenie.muc.de (8.18.2/8.18.1/Submit) id 698KphN8028466 for openvpn-devel@lists.sourceforge.net; Thu, 8 Oct 2026 22:51:43 +0200 From: Gert Doering To: openvpn-devel@lists.sourceforge.net Date: Thu, 8 Oct 2026 22:51:37 +0200 Message-ID: <20261008205143.28452-1-gert@greenie.muc.de> X-Mailer: git-send-email 2.53.0 In-Reply-To: References: MIME-Version: 1.0 X-Spam-Score: 1.3 (+) X-Spam-Report: Spam detection software, running on the system "sfi-spamd-1.hosts.colo.sdot.me", has NOT identified this incoming email as spam. The original message has been attached to this so you can view it or label similar future email. If you have any questions, see the administrator of that system for details. Content preview: From: Razvan Cojocaru Every comparison becomes a modular distance against a stated bound. subtract_pid() stays and reliable_pid_in_range1() loses its suffix; reliable_pid_min() and reliable_pid_in_range2() go, and with the [...] Content analysis details: (1.3 points, 5.0 required) pts rule name description ---- ---------------------- -------------------------------------------------- 1.3 RDNS_NONE Delivered to internal network by a host with no rDNS X-Headers-End: 1xEv5h-0005PE-Qk Subject: [Openvpn-devel] [PATCH v3] reliable: drop the half-space packet id comparisons X-BeenThere: openvpn-devel@lists.sourceforge.net X-Mailman-Version: 2.1.21 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: openvpn-devel-bounces@lists.sourceforge.net X-getmail-retrieved-from-mailbox: Inbox X-GMAIL-THRID: 1878516267614884086 X-GMAIL-MSGID: 1878516267614884086 From: Razvan Cojocaru Every comparison becomes a modular distance against a stated bound. subtract_pid() stays and reliable_pid_in_range1() loses its suffix; reliable_pid_min() and reliable_pid_in_range2() go, and with them the last 0x80000000 in the file. The three scans for the oldest unacknowledged entry now track the largest distance below rel->packet_id, bounded by rel->size, in reliable_oldest_active_distance(). reliable_wont_break_sequentiality() bounds the distance ahead and accepts past ids outright, as the old comparison did without the 0x80000000 bias. reliable_can_send() counts the same entries without the window bound and its caller asserts on the result, so reliable_send() falls back to any eligible entry when the bound leaves nothing. Equivalent for every reachable input. Four deliberate differences: - Once rel->packet_id + rel->size overflows, the absolute clause makes reliable_wont_break_sequentiality() permissive: ids the old bias branch rejected are acknowledged. Nothing more is stored, reliable_not_replay() still bounding that to the receive window, which wraps with rel->packet_id. Needs ~2^32 control channel packets in one key state. - Above 2^31, an id absolutely below rel->packet_id + rel->size but more than rel->size ahead is acknowledged and no longer stored: it can never equal rel->packet_id, so its slot was held for the rest of the key state. Needs ~2^31 such packets; test_recv_filter_high_base's oracle switches to the new rule there, pinning behaviour rather than equivalence. - The ASSERT in reliable_mark_active_incoming() is the receive window rather than a half space, and runs before the entry is touched. Unobservable: it repeats the check reliable_not_replay() makes immediately before it. - A send entry more than rel->size below rel->packet_id is ignored by the scans instead of taken for a very old one, so reliable_get_num_output_sequenced_available() can no longer go negative. reliable_get_buf_output_sequenced() keeps every distance within rel->size, so it never could. Change-Id: Iaaa0af7d678eb447bc93741add8120d9f348d9eb Signed-off-by: Razvan Cojocaru Acked-by: Arne Schwabe Gerrit URL: https://gerrit.openvpn.net/c/openvpn/+/1900 --- This change was reviewed on Gerrit and approved by at least one developer. I request to merge it to master. Gerrit URL: https://gerrit.openvpn.net/c/openvpn/+/1900 This mail reflects revision 3 of this Change. Acked-by according to Gerrit (reflected above): Arne Schwabe diff --git a/src/openvpn/reliable.c b/src/openvpn/reliable.c index b5315ff..645fbfd 100644 --- a/src/openvpn/reliable.c +++ b/src/openvpn/reliable.c @@ -50,46 +50,12 @@ * verify that test - base < extent while allowing for base or test wraparound */ static inline bool -reliable_pid_in_range1(const packet_id_type test, const packet_id_type base, - const unsigned int extent) +reliable_pid_in_range(const packet_id_type test, const packet_id_type base, + const unsigned int extent) { return subtract_pid(test, base) < extent; } -/* - * verify that test < base + extent while allowing for base or test wraparound - */ -static inline bool -reliable_pid_in_range2(const packet_id_type test, const packet_id_type base, - const unsigned int extent) -{ - if (base + extent >= base) - { - if (test < base + extent) - { - return true; - } - } - else - { - if ((test + 0x80000000u) < (base + 0x80000000u) + extent) - { - return true; - } - } - - return false; -} - -/* - * verify that p1 < p2 while allowing for p1 or p2 wraparound - */ -static inline bool -reliable_pid_min(const packet_id_type p1, const packet_id_type p2) -{ - return !reliable_pid_in_range1(p1, p2, 0x80000000u); -} - /* check if a particular packet_id is present in ack */ static inline bool reliable_ack_packet_id_present(struct reliable_ack *ack, packet_id_type pid) @@ -393,8 +359,9 @@ int validate_packet_id_window(struct reliable *rel, packet_id_type pid) { - return reliable_pid_min(pid, rel->packet_id) - && reliable_pid_min(subtract_pid(rel->packet_id, RELIABLE_CAPACITY), pid); + const packet_id_type dist = subtract_pid(rel->packet_id, pid); + + return dist > 0 && dist < RELIABLE_CAPACITY; } /* del acknowledged items from send buf */ @@ -440,14 +407,17 @@ e->active = false; } - if (e->active && reliable_pid_min(e->packet_id, pid)) + /* Order the two by their distance below rel->packet_id, as + * comparing the ids directly misorders them across the wrap. + * Entries further back than rel->size are outside the send window + * and left alone. An ACK for a higher pid means this packet + * arrived out of order or was lost, and enough of them trigger + * the early resend. */ + const packet_id_type e_dist = subtract_pid(rel->packet_id, e->packet_id); + + if (e->active && e_dist <= (packet_id_type)rel->size + && e_dist > subtract_pid(rel->packet_id, pid)) { - /* We have received an ACK for a packet with a higher PID. Either - * we have received ACKs out of or order or the packet has been - * lost. We count the number of ACKs to determine if we should - * resend it early. The comparison needs to be wraparound aware, - * otherwise a peer can inflate n_acks with an ACK for a pid from - * the lower half of the id space and force a retransmit. */ e->n_acks++; } } @@ -505,7 +475,9 @@ reliable_not_replay(const struct reliable *rel, packet_id_type id) { struct gc_arena gc = gc_new(); - if (reliable_pid_min(id, rel->packet_id)) + + /* outside the receive window: already consumed, or too far ahead to store */ + if (!reliable_pid_in_range(id, rel->packet_id, rel->size)) { goto bad; } @@ -531,7 +503,12 @@ bool reliable_wont_break_sequentiality(const struct reliable *rel, packet_id_type id) { - const int ret = reliable_pid_in_range2(id, rel->packet_id, rel->size); + /* The first clause is the receive window. The second is an absolute + * comparison, kept so that already consumed ids still reach + * reliable_ack_acknowledge_packet_id() and a peer whose ACK was lost stops + * retransmitting; reliable_not_replay() rejects them. */ + const bool ret = (subtract_pid(id, rel->packet_id) < (packet_id_type)rel->size + || id < rel->packet_id); if (!ret) { @@ -562,57 +539,46 @@ return NULL; } -int -reliable_get_num_output_sequenced_available(struct reliable *rel) +/* Distance below rel->packet_id of the oldest unacknowledged entry, 0 if there + * is none. Entries more than rel->size away are outside the sequencing window + * and ignored, rather than taken for very old ones. */ +static packet_id_type +reliable_oldest_active_distance(const struct reliable *rel) { - packet_id_type min_id = 0; - bool min_id_defined = false; + packet_id_type max_dist = 0; - /* find minimum active packet_id */ for (int i = 0; i < rel->size; ++i) { const struct reliable_entry *e = &rel->array[i]; - if (e->active) + if (!e->active) { - if (!min_id_defined || reliable_pid_min(e->packet_id, min_id)) - { - min_id_defined = true; - min_id = e->packet_id; - } + continue; + } + + const packet_id_type dist = subtract_pid(rel->packet_id, e->packet_id); + if (dist <= (packet_id_type)rel->size && dist > max_dist) + { + max_dist = dist; } } - int ret = rel->size; - if (min_id_defined) - { - ret -= subtract_pid(rel->packet_id, min_id); - } - return ret; + return max_dist; +} + +int +reliable_get_num_output_sequenced_available(struct reliable *rel) +{ + return rel->size - (int)reliable_oldest_active_distance(rel); } /* grab a free buffer, fail if buffer clogged by unacknowledged low packet IDs */ struct buffer * reliable_get_buf_output_sequenced(struct reliable *rel) { - packet_id_type min_id = 0; - bool min_id_defined = false; struct buffer *ret = NULL; - /* find minimum active packet_id */ - for (int i = 0; i < rel->size; ++i) - { - const struct reliable_entry *e = &rel->array[i]; - if (e->active) - { - if (!min_id_defined || reliable_pid_min(e->packet_id, min_id)) - { - min_id_defined = true; - min_id = e->packet_id; - } - } - } - - if (!min_id_defined || reliable_pid_in_range1(rel->packet_id, min_id, rel->size)) + /* keep the next id within rel->size of the oldest unacknowledged one */ + if (reliable_oldest_active_distance(rel) < (packet_id_type)rel->size) { ret = reliable_get_buf(rel); } @@ -671,6 +637,8 @@ reliable_send(struct reliable *rel, int *opcode) { struct reliable_entry *best = NULL; + struct reliable_entry *eligible = NULL; + packet_id_type best_dist = 0; const time_t local_now = now; for (int i = 0; i < rel->size; ++i) @@ -682,13 +650,29 @@ * not expired yet. */ if (e->active && (e->n_acks >= N_ACK_RETRANSMIT || local_now >= e->next_try)) { - if (!best || reliable_pid_min(e->packet_id, best->packet_id)) + /* oldest = furthest below rel->packet_id, within the window */ + const packet_id_type dist = subtract_pid(rel->packet_id, e->packet_id); + if (dist <= (packet_id_type)rel->size && dist > best_dist) { best = e; + best_dist = dist; + } + + if (!eligible) + { + eligible = e; } } } + /* reliable_can_send() promises a non-NULL result for these same entries + * without applying the window bound, and its caller asserts on that, so + * never come back empty while one of them is eligible. */ + if (!best) + { + best = eligible; + } + if (best) { /* The initial timeout is bounded by RELIABLE_MAX_INITIAL_TIMEOUT, so @@ -776,14 +760,14 @@ struct reliable_entry *e = &rel->array[i]; if (buf == &e->buf) { + /* storable and not yet consumed, checked before touching the entry */ + ASSERT(reliable_pid_in_range(pid, rel->packet_id, rel->size)); + e->active = true; /* packets may not arrive in sequential order */ e->packet_id = pid; - /* check for replay */ - ASSERT(!reliable_pid_min(pid, rel->packet_id)); - e->opcode = opcode; e->next_try = 0; e->timeout = 0; diff --git a/src/openvpn/reliable.h b/src/openvpn/reliable.h index a85f2e9..04f3372 100644 --- a/src/openvpn/reliable.h +++ b/src/openvpn/reliable.h @@ -288,15 +288,16 @@ bool reliable_can_get(const struct reliable *rel); /** - * Check that a received packet's ID is not a replay. + * Check that a received packet's ID is not a replay and is inside the receive + * window. * * @param rel The reliable structure for handling this VPN tunnel's * received packets. * @param id The packet ID of the received packet. * * @return - * @li True, if the packet ID is not a replay. - * @li False, if the packet ID is a replay. + * @li True, if the packet ID is new and inside the receive window. + * @li False, if it is a replay, or too far ahead to be stored. */ bool reliable_not_replay(const struct reliable *rel, packet_id_type id); diff --git a/tests/unit_tests/openvpn/test_packet_id.c b/tests/unit_tests/openvpn/test_packet_id.c index aabb555..ac6c710 100644 --- a/tests/unit_tests/openvpn/test_packet_id.c +++ b/tests/unit_tests/openvpn/test_packet_id.c @@ -517,13 +517,16 @@ } /* - * Reference implementations of the packet id comparisons as they behave today. - * The sweeps below assert reliable.c agrees with them at the anchors swept, so - * a change to an accepted id set there fails a test. Keep them standalone: - * expressing them in terms of reliable.c would make the sweeps tautologies. + * Independent models of the id sets the packet id comparisons accept. The + * sweeps below assert reliable.c agrees with them at the anchors swept, so a + * change to an accepted id set there fails a test. Each model is tagged + * "preserved" or "introduced" against the comparisons that came before. Keep + * them standalone: expressing them in terms of reliable.c would make the + * sweeps tautologies. */ -/* "p1 < p2" with the 2^31 horizon, i.e. ((int32_t)(p1 - p2) < 0) */ +/* the dropped reliable_pid_min(): "p1 < p2" with the 2^31 horizon, + * i.e. ((int32_t)(p1 - p2) < 0) */ static bool ref_pid_min(packet_id_type p1, packet_id_type p2) { @@ -538,6 +541,7 @@ #define CHAR_N_SEND_BUFFERS 6 #define CHAR_OPCODE_CONTROL_V1 4 +/* preserved: the ids validate_packet_id_window() accepts */ static bool ref_pid_in_send_window(const struct reliable *rel, packet_id_type pid) { @@ -546,6 +550,7 @@ return dist >= 1 && dist <= CHARACTERIZED_SEND_WINDOW; } +/* preserved: reliable_pid_in_range2() */ static bool ref_wont_break_sequentiality(const struct reliable *rel, packet_id_type id) { @@ -559,6 +564,7 @@ return id < base + extent; } +/* preserved: the horizon check, then the slot scan */ static bool ref_not_replay(const struct reliable *rel, packet_id_type id) { @@ -691,6 +697,54 @@ } } +/* Once rel->packet_id + rel->size overflows, the absolute clause makes + * reliable_wont_break_sequentiality() permissive; what may be stored is still + * the receive window, which wraps with it. */ +static void +test_recv_window_bounded_at_wrap(void **state) +{ + struct reliable rel = { 0 }; + rel.size = RELIABLE_CAPACITY; + rel.packet_id = 0xFFFFFFF8; + + assert_int_equal(RECV_STORE, recv_filter(&rel, 0xFFFFFFF8)); + assert_int_equal(RECV_STORE, recv_filter(&rel, 0xFFFFFFFF)); + assert_int_equal(RECV_STORE, recv_filter(&rel, 3)); + + /* one past the window, and one behind it: acknowledged, never stored */ + assert_int_equal(RECV_ACK_ONLY, recv_filter(&rel, 4)); + assert_int_equal(RECV_ACK_ONLY, recv_filter(&rel, 0xFFFFFFF7)); +} + +/* The id the receiver is next waiting for has to be storable at every base, + * the packet id wrap included. */ +static void +test_wont_break_sequentiality_accepts_next_id(void **state) +{ + const packet_id_type bases[] = { + 0, + 1, + 500, + 0x7FFFFFFF, + 0x80000000, + 0xFFFFFFF3, + 0xFFFFFFF4, + 0xFFFFFFF8, + 0xFFFFFFFE, + 0xFFFFFFFF, + }; + + for (size_t i = 0; i < SIZE(bases); i++) + { + struct reliable rel = { 0 }; + rel.size = RELIABLE_CAPACITY; + rel.packet_id = bases[i]; + + assert_true(reliable_wont_break_sequentiality(&rel, rel.packet_id)); + assert_true(reliable_not_replay(&rel, rel.packet_id)); + } +} + /* bases at or below 2^31, where old and new agree; never to change */ static void test_recv_filter_characterization(void **state) @@ -698,12 +752,31 @@ sweep_recv_filter(char_anchors, SIZE(char_anchors), ref_recv_filter); } +/* Introduced, for the bases above 2^31 only: storing also requires the id to + * be inside the receive window. The ids between one further ahead and + * rel->packet_id cannot all fit alongside it, so rel->packet_id never reaches + * it and the slot is held for the rest of the key state. Still ACKed, like a + * replay. */ +static enum recv_verdict +ref_recv_filter_bounded(const struct reliable *rel, packet_id_type id) +{ + const enum recv_verdict verdict = ref_recv_filter(rel, id); + + if (verdict == RECV_STORE + && (packet_id_type)(id - rel->packet_id) >= (packet_id_type)rel->size) + { + return RECV_ACK_ONLY; + } + + return verdict; +} + /* bases above 2^31, where they diverge, kept apart so a change confined * there touches one test */ static void test_recv_filter_high_base(void **state) { - sweep_recv_filter(char_anchors_high, SIZE(char_anchors_high), ref_recv_filter); + sweep_recv_filter(char_anchors_high, SIZE(char_anchors_high), ref_recv_filter_bounded); } static void @@ -739,6 +812,60 @@ sweep_send_window(char_anchors_high, SIZE(char_anchors_high)); } +/* The window bound in the selection is what stops an entry sitting ahead of + * rel->packet_id from being taken for the oldest one: its distance below + * rel->packet_id is then nearly the whole id space. array[0] cannot arise + * through the API; array[1] is an ordinary outstanding packet. */ +static void +test_reliable_send_ignores_entry_ahead(void **state) +{ + now = 1000; + + struct reliable rel = { 0 }; + rel.size = CHAR_N_SEND_BUFFERS; + rel.initial_timeout = 2; + rel.packet_id = 3; + + /* scanned first, and outside the window */ + rel.array[0].active = true; + rel.array[0].packet_id = 0x40000000; + rel.array[0].timeout = 2; + rel.array[0].next_try = 0; + + /* a genuine outstanding packet, two below rel->packet_id */ + rel.array[1].active = true; + rel.array[1].packet_id = 1; + rel.array[1].timeout = 2; + rel.array[1].next_try = 0; + + int opcode = 0; + assert_ptr_equal(&rel.array[1].buf, reliable_send(&rel, &opcode)); +} + +/* reliable_can_send() promises reliable_send() will hand back a buffer, and + * its caller asserts on that. The state below cannot arise through the API -- + * the entry sits outside the send window -- but the two must not be able to + * disagree. */ +static void +test_reliable_send_matches_can_send(void **state) +{ + now = 1000; + + struct reliable rel = { 0 }; + rel.size = CHAR_N_SEND_BUFFERS; + rel.initial_timeout = 2; + rel.packet_id = 3; + + rel.array[0].active = true; + rel.array[0].packet_id = 0x40000000; + rel.array[0].timeout = 2; + rel.array[0].next_try = 0; + + int opcode = 0; + assert_true(reliable_can_send(&rel)); + assert_non_null(reliable_send(&rel, &opcode)); +} + /* reliable_send() picks the oldest eligible entry, across the wrap and the * signed midpoint */ static void @@ -880,10 +1007,14 @@ cmocka_unit_test(test_reliable_backoff_is_bounded), cmocka_unit_test(test_reliable_purge_ignores_forged_acks), cmocka_unit_test(test_reliable_purge_legitimate_ack), + cmocka_unit_test(test_wont_break_sequentiality_accepts_next_id), + cmocka_unit_test(test_recv_window_bounded_at_wrap), cmocka_unit_test(test_recv_filter_characterization), cmocka_unit_test(test_recv_filter_high_base), cmocka_unit_test(test_send_window_characterization), cmocka_unit_test(test_reliable_send_picks_oldest), + cmocka_unit_test(test_reliable_send_ignores_entry_ahead), + cmocka_unit_test(test_reliable_send_matches_can_send), cmocka_unit_test(test_get_buf_output_sequenced_boundary), cmocka_unit_test(test_mark_active_incoming_accepts_window), #ifndef _MSC_VER