See a path that stops carrying larger datagrams, and go back to the first size

A link that found the path carries 1,452 bytes kept sending them when a
route changed and larger packets were dropped with nothing said (a
black hole): it lost them one after another and stood still (test-link:
8 of 3,000 records in ten minutes). Now, as RFC 8899 §4.3 has it, it goes
back to 1,200 bytes when three larger packets in a row are lost while an
acknowledgment covers only smaller ones, or when two probes in a row go
unanswered, and tries the larger size again a second on (three tries,
then ten minutes). The case completes in 1.2 s of virtual time; the M6
simulator's results are the same to the byte in eight paths of loss,
reordering and a bottleneck.

3 files changed, 54 insertions, 16 deletions

diff --git a/link/link-protocol.c b/link/link-protocol.c
index e4661cb..5b9eaa3 100644
--- a/link/link-protocol.c
+++ b/link/link-protocol.c
@@ -32,8 +32,12 @@ enum { WINDOW_FIRST = 10 * DATAGRAM, WINDOW_LEAST = 2 * DATAGRAM };
  * events with no late packet before the patience halves. */
 enum { REORDER_FIRST = 3, REORDER_PACKETS_MOST = 256, REORDER_QUARTERS_MOST = 8, CALM = 16 };
 /* A probe of a larger datagram lost is tried again a second on, three
- * times, then ten minutes on. */
-enum { REACH_TRIES = 3 };
+ * times, then ten minutes on. A path that stops carrying the larger ones
+ * (a black hole, RFC 8899 §4.3) is seen when this many of them in a row
+ * are lost while only smaller ones are acknowledged, or when two probes in
+ * a row go unanswered: the datagram goes back to the first, and the larger
+ * is tried again a second on. */
+enum { REACH_TRIES = 3, HOLE_LOST = 3, HOLE_PROBES = 2 };
 /* Challenges a sender keeps to say back, the newest first. */
 enum { RESPONSES = 4 };
 /* Keys made for runs that do not open, and new epochs accepted: a second,
@@ -273,7 +277,7 @@ struct PureLinkSender {
     uint32_t datagram;
     bool reaching, filled; /* filled: a packet was full with more to go (a larger one would carry more) */
     uint64_t reach_at;
-    unsigned reach_lost;
+    unsigned reach_lost, larger_lost; /* larger_lost: packets larger than the first datagram lost since one came */
     uint64_t received;    /* parts received and not yet stored */
     uint64_t unsent_from; /* no record before this number has a part unsent */
     unsigned pto_count, probes;
@@ -467,9 +471,19 @@ static void settle(PureLinkSender *l, Flight *f) {
     }
 }
 
+/* The path carries no datagram larger than the first now (a black hole):
+ * back to it, and the larger tried again a second on. */
+static void shrink(PureLinkSender *l, uint64_t now) {
+    l->datagram = DATAGRAM;
+    l->reaching = false;
+    l->larger_lost = 0;
+    l->reach_at = now + REACH_AGAIN;
+}
+
 /* A packet lost: what it carried and was not received otherwise goes again. */
 static void lose(PureLinkSender *l, Flight *f, uint64_t now, bool by_time) {
     settle(l, f);
+    if (f->bytes > DATAGRAM) ++l->larger_lost;
     if (f->reach) { /* the path does not carry it (yet): tried again a while on, three times, then rarely */
         l->reaching = false;
         l->reach_at = now + (++l->reach_lost < REACH_TRIES ? REACH_AGAIN : REACH_RARELY);
@@ -607,6 +621,7 @@ static void on_ack(PureLinkSender *l, const unsigned char *p, size_t size, uint6
     if (size < 13 || size < 13 + 16u * p[12]) return;
     uint64_t largest = get64(p), delay = (uint64_t)get32(p + 8) * 1000;
     Flight *top = NULL;
+    bool smaller = false, larger = false; /* acknowledged now, of the first datagram's size or less, and larger */
     if (!l->acked_any || largest > l->largest_acked) l->largest_acked = largest;
     for (unsigned k = 0; k < p[12]; ++k) {
         uint64_t first = get64(p + 13 + 16 * k), last = get64(p + 21 + 16 * k);
@@ -619,6 +634,8 @@ static void on_ack(PureLinkSender *l, const unsigned char *p, size_t size, uint6
             settle(l, f);
             ++l->counts.acknowledged;
             if (f->reach) l->datagram = DATAGRAM_MOST, l->reaching = false; /* the path carries it */
+            if (f->bytes > DATAGRAM) larger = true, l->larger_lost = 0;
+            else smaller = true;
             for (uint16_t u = 0; u < f->count; ++u) carried(l, &f->units[u], f->pn, true, now);
             if (f->eliciting && f->sent > l->cc.recovery_start && !l->unused) grow(l, f->bytes, now);
             if (pn == largest) top = f;
@@ -628,6 +645,7 @@ static void on_ack(PureLinkSender *l, const unsigned char *p, size_t size, uint6
     if (top && top->eliciting) sample_rtt(l, now - top->sent, delay);
     l->pto_count = 0;
     detect_lost(l, now);
+    if (smaller && !larger && l->datagram > DATAGRAM && l->larger_lost >= HOLE_LOST) shrink(l, now);
     /* Done ones go; one called lost stays a while, so it is known if it
      * comes late. */
     uint64_t keep = 2 * most(l->latest_rtt, l->sampled ? l->smoothed_rtt : FIRST_RTT);
@@ -957,8 +975,9 @@ void pure_link_sender_tick(PureLinkSender *l, uint64_t now) {
     }
     if (l->loss_time && l->loss_time <= now) detect_lost(l, now);
     else if (l->eliciting && l->last_eliciting + pto_period(l) <= now) {
-        /* Nothing heard for a while: a probe, what flies longest sent again. */
-        ++l->pto_count;
+        /* Nothing heard for a while: a probe, what flies longest sent again
+         * (in a datagram of the first size, the second time). */
+        if (++l->pto_count >= HOLE_PROBES && l->datagram > DATAGRAM) shrink(l, now);
         l->probes = 1;
         for (size_t k = 0; k < l->count; ++k) {
             Record *r = record_at(l, k);
diff --git a/link/link-protocol.h b/link/link-protocol.h
index e7ca38c..b2995e5 100644
--- a/link/link-protocol.h
+++ b/link/link-protocol.h
@@ -106,7 +106,8 @@
 /* A packet is PURE_LINK_DATAGRAM bytes at most at first, and up to
  * PURE_LINK_DATAGRAM_MOST once the path is found to carry that many (a
  * probe of that size acknowledged: DPLPMTUD, RFC 8899; a link probes once
- * a packet of its was full, else a larger one would carry nothing more); a
+ * a packet of its was full, else a larger one would carry nothing more, and
+ * goes back to the first size when the larger stop coming, §4.3); a
  * source's or an input's name is 1 to PURE_LINK_NAME bytes; a receiver
  * keeps a packet's path (where it came from, and the address of its own it
  * came to: link/link.c answers from there) in PURE_LINK_ADDRESS bytes. */
diff --git a/link/test-link.c b/link/test-link.c
index 0cfd3e4..c409063 100644
--- a/link/test-link.c
+++ b/link/test-link.c
@@ -87,6 +87,9 @@ typedef struct {
      * moment the sender begins an epoch (before the receiver has seen it). */
     uint64_t cut_until;
     unsigned cuts;
+    /* A black hole: from when the sender's datagram grew, the path carries
+     * nothing larger than PURE_LINK_DATAGRAM (and says nothing of it). */
+    bool black_hole, hole;
     /* The receiving app: its last heard (kept across the receiver's
      * restarts), what it said of deliveries (given at the next turn). */
     uint64_t heard, applied, deliveries;
@@ -97,6 +100,7 @@ typedef struct {
 
 static void put_packet(World *w, bool to_receiver, const unsigned char *bytes, size_t size) {
     ++w->sent;
+    if (w->hole && size > PURE_LINK_DATAGRAM) return;
     for (int copies = chance(w->doubled) ? 2 : 1; copies--;) {
         if (chance(w->loss) || w->count == PACKETS) continue;
         Packet *p = &w->packets[w->count++];
@@ -193,6 +197,7 @@ typedef struct {
     uint64_t epoch_ms; /* epochs this long (0: an hour) */
     bool forgetful;    /* the receiver keeps no memo: it starts again knowing no epoch */
     unsigned cuts;     /* the path cut for 3 s so many times, as an epoch begins */
+    bool black_hole;   /* larger packets lost from when the path was found to carry them */
 } Case;
 
 static bool nothing_sent(void *context, const unsigned char *packet, size_t size, const unsigned char *to, size_t to_size) {
@@ -245,7 +250,12 @@ static void replay(World *w, PureLinkSender *s, PureLinkReceiver *r, const char
     }
 }
 
-typedef struct { PureLinkCounts sent, heard; uint64_t packets, seconds_ms; } Outcome;
+typedef struct {
+    PureLinkCounts sent, heard;
+    uint64_t packets, seconds_ms;
+    size_t datagram; /* the sender's at the end */
+    bool hole;       /* a black hole opened */
+} Outcome;
 
 /* One who later has both nodes' private keys: the keys of the sender's
  * packets under the nodes' static secret (link-protocol.c's derive). */
@@ -358,7 +368,7 @@ static Outcome run(const Case *c, const char *dir) {
     unlink(memo);
     World w = {.packets = malloc(PACKETS * sizeof(Packet)), .loss = c->loss, .doubled = c->doubled,
                .spread_ms = c->spread_ms, .fail_every = c->fail_every, .replay = c->replay, .tamper = c->tamper,
-               .cuts = c->cuts, .history = malloc(HISTORY * sizeof(Packet))};
+               .cuts = c->cuts, .black_hole = c->black_hole, .history = malloc(HISTORY * sizeof(Packet))};
     if (!w.packets || !w.history) exit(1);
     char from[8] = "sender0";
     epoch_ms = c->epoch_ms;
@@ -384,6 +394,7 @@ static Outcome run(const Case *c, const char *dir) {
             w.sent_log[w.sent_log_count] = (Packet){.size = size};
             memcpy(w.sent_log[w.sent_log_count++].bytes, out, size);
             put_packet(&w, true, out, size);
+            if (w.black_hole && pure_link_sender_datagram(s) > PURE_LINK_DATAGRAM) w.hole = true;
         }
         /* Then the next thing to happen. */
         uint64_t next = UINT64_MAX, due = pure_link_sender_due(s), turn = pure_link_receiver_due(r);
@@ -453,7 +464,7 @@ static Outcome run(const Case *c, const char *dir) {
             snprintf(from, sizeof(from), "sender%u", ++w.gen); /* a new process: another address */
         }
     }
-    Outcome o = {.packets = w.sent, .seconds_ms = w.now / MS};
+    Outcome o = {.packets = w.sent, .seconds_ms = w.now / MS, .datagram = pure_link_sender_datagram(s), .hole = w.hole};
     pure_link_sender_counts(s, &o.sent);
     pure_link_receiver_counts(r, &o.heard);
     o.sent.packets += sent_before.packets, o.sent.resent += sent_before.resent, o.sent.epochs += sent_before.epochs;
@@ -621,7 +632,7 @@ int main(void) {
         return 1;
     }
     /* A clean network: nothing is sent twice. */
-    Case clean = {"clean", 3000, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, false, 0, false, 0};
+    Case clean = {"clean", 3000, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, false, 0, false, 0, false};
     Outcome o = run(&clean, dir);
     CHECK(o.sent.resent == 0 && o.sent.lost == 0, "clean: %llu sent again, %llu lost", (unsigned long long)o.sent.resent,
           (unsigned long long)o.sent.lost);
@@ -630,7 +641,7 @@ int main(void) {
      * starting again: the receiver remembers its secret, so it wakes the
      * sender without an X25519. */
     for (uint64_t s = 1; s <= 4; ++s) {
-        Case rough = {"rough", 3000, s * 7919, 10, 3, 20, 37, 1500, 800, 2200, 300, 0, false, 0, false, 0};
+        Case rough = {"rough", 3000, s * 7919, 10, 3, 20, 37, 1500, 800, 2200, 300, 0, false, 0, false, 0, false};
         o = run(&rough, dir);
         CHECK(o.sent.resent > 0 && o.heard.swept >= 1 && o.heard.woken >= 1 && o.heard.remembered >= 1,
               "rough: sent again %llu, swept %llu, woken %llu, remembered %llu", (unsigned long long)o.sent.resent,
@@ -640,29 +651,36 @@ int main(void) {
     /* An attacker on the path: packets changed on the way, and packets of
      * the past sent again, from the sender's address and its own, across the
      * same restarts and pause. */
-    Case changed = {"changed", 1500, 31, 3, 0, 5, 0, 0, 0, 0, 0, 0, true, 0, false, 0};
+    Case changed = {"changed", 1500, 31, 3, 0, 5, 0, 0, 0, 0, 0, 0, true, 0, false, 0, false};
     run(&changed, dir);
     for (uint64_t s = 1; s <= 2; ++s) {
-        Case again = {"replayed", 3000, s * 104729, 5, 3, 20, 37, 1500, 800, 2200, 300, 25, false, 0, false, 0};
+        Case again = {"replayed", 3000, s * 104729, 5, 3, 20, 37, 1500, 800, 2200, 300, 25, false, 0, false, 0, false};
         run(&again, dir);
     }
     /* Epochs a fifth of a second long (a new one a second, as the receiver
      * accepts), and a receiver that starts again with no memo: it knows no
      * epoch, and the sender begins them again. */
-    Case epochs = {"epochs", 3000, 271, 5, 3, 20, 37, 1500, 800, 2200, 300, 10, false, 200, false, 0};
+    Case epochs = {"epochs", 3000, 271, 5, 3, 20, 37, 1500, 800, 2200, 300, 10, false, 200, false, 0, false};
     o = run(&epochs, dir);
     CHECK(o.sent.epochs >= 10, "epochs: %llu begun", (unsigned long long)o.sent.epochs);
-    Case forgetful = {"forgetful", 3000, 409, 5, 3, 20, 37, 0, 800, 0, 0, 0, false, 0, true, 0};
+    Case forgetful = {"forgetful", 3000, 409, 5, 3, 20, 37, 0, 800, 0, 0, 0, false, 0, true, 0, false};
     o = run(&forgetful, dir);
     CHECK(o.sent.epochs >= 2, "forgetful: %llu epochs begun (none again)", (unsigned long long)o.sent.epochs);
     /* The path cut for 3 s the moment the sender begins an epoch, three
      * times: the receiver never saw the epoch used, and the sender, hearing
      * nothing, offers another epoch 1 with a new key. The accept of the old
      * offer must not begin it. */
-    Case cut = {"cut", 3000, 919, 0, 0, 20, 37, 0, 0, 0, 0, 0, false, 200, false, 3};
+    Case cut = {"cut", 3000, 919, 0, 0, 20, 37, 0, 0, 0, 0, 0, false, 200, false, 3, false};
     o = run(&cut, dir);
     CHECK(o.sent.epochs >= 4 && o.sent.fallbacks == 3, "cut: %llu epochs begun, %llu taken for lost (3 cuts)",
           (unsigned long long)o.sent.epochs, (unsigned long long)o.sent.fallbacks);
+    /* A path that carried 1,452-byte packets and then, from the moment the
+     * link found it did, carries none larger than 1,200 (a route changed,
+     * and no ICMP says so): the link must see it and go back. */
+    Case hole = {"black hole", 3000, 1601, 0, 0, 0, 0, 0, 0, 0, 0, 0, false, 0, false, 0, true};
+    o = run(&hole, dir);
+    CHECK(o.hole && o.datagram == PURE_LINK_DATAGRAM, "black hole: %s, a datagram of %zu at the end",
+          o.hole ? "opened" : "never opened", o.datagram);
     impostors(dir);
     flood(dir);
     char command[600];