[L] Change in openvpn[master]: oob: Add probe-result ranking for server selection

Attention is currently required from: plaisthos.

Hello plaisthos, 

I'd like you to reexamine a change. Please visit

    http://gerrit.openvpn.net/c/openvpn/+/1746?usp=email

to look at the new patch set (#13).


Change subject: oob: Add probe-result ranking for server selection
......................................................................

oob: Add probe-result ranking for server selection

Add oob_rank_probe_results(), which orders remotes best-first from their probe
results, following the DNS-SRV (RFC 2782) semantics of the probe_reply TLV:

  - remotes that answered rank before those that did not (non-responders keep
    their original relative order, last);
  - responders are grouped by priority, lowest value first (an absolute
    ordering, never overridden by latency or weight);
  - within a priority group the "candidates" are the responders whose RTT is
    no more than a margin larger than the fastest, so the fastest is always
    one; candidates rank ahead of non-candidates;
  - candidates are ordered by RFC-2782 weighted-random selection by weight, so
    a server is chosen first with probability proportional to its weight (load
    distribution); non-candidates follow, ordered by RTT.

oob_effective_margin() decides that margin: the client's --server-probe value if
it set one, otherwise the server's advertised max_latency_diff, where 0 admits
only the fastest responder and whatever ties with it.

The RNG is injected as a function pointer so this module stays free of the
crypto layer and the weighted ordering is deterministically unit-testable (the
client will pass get_random; the tests pass stubs).

Exercised by unit tests; the client probe path calls it in a follow-up, which
also populates RTT -- until then every responder sits in the band and selection
is purely weighted-random.

Change-Id: I55da68cc341bcfc707fd34ca2f84ff9b6a55501f
Signed-off-by: Lev Stipakov <[email protected]>
---
M src/openvpn/oob.c
M src/openvpn/oob.h
M tests/unit_tests/openvpn/test_oob.c
3 files changed, 432 insertions(+), 0 deletions(-)


  git pull ssh://gerrit.openvpn.net:29418/openvpn refs/changes/46/1746/13

diff --git a/src/openvpn/oob.c b/src/openvpn/oob.c
index bc0e7a3..3884ae3 100644
--- a/src/openvpn/oob.c
+++ b/src/openvpn/oob.c
@@ -155,3 +155,160 @@
     reply->peer_session_id = *peer_sid;
     return true;
 }
+
+/* Base ordering: responders before non-responders, then by priority (lower
+ * first), then by RTT (lower first), then by original index for determinism.
+ * This groups responders into priority runs pre-sorted by RTT, which the
+ * candidate-band step below relies on (run[0] is the fastest in its group). */
+static int
+oob_probe_result_compare(const void *a, const void *b)
+{
+    const struct oob_probe_result *ra = a;
+    const struct oob_probe_result *rb = b;
+
+    if (ra->responded && rb->responded)
+    {
+        /* both answered: lowest priority first, then lowest RTT */
+        if (ra->reply.priority != rb->reply.priority)
+        {
+            return ra->reply.priority < rb->reply.priority ? -1 : 1;
+        }
+        if (ra->rtt_ms != rb->rtt_ms)
+        {
+            return ra->rtt_ms < rb->rtt_ms ? -1 : 1;
+        }
+    }
+    else if (ra->responded)
+    {
+        return -1; /* only a answered: it ranks first */
+    }
+    else if (rb->responded)
+    {
+        return 1; /* only b answered */
+    }
+
+    /* neither answered, or all keys equal: keep the configured order */
+    return ra->index - rb->index;
+}
+
+int
+oob_effective_margin(const struct oob_probe_result *r, int client_margin)
+{
+    if (client_margin >= 0)
+    {
+        return client_margin;              /* the client's own setting is authoritative */
+    }
+    return (int)r->reply.max_latency_diff; /* else the server's advertised value */
+}
+
+/* Reorder the index list idx[0..m) into DNS-SRV (RFC 2782) weighted-random
+ * order by results[idx[k]].reply.weight: each position is filled by a remaining entry
+ * chosen with probability proportional to its weight. When all remaining
+ * weights are 0 the current (RTT-sorted) order is kept. */
+static void
+oob_weighted_order(const struct oob_probe_result *results, int *idx, int m, int64_t (*rng)(void))
+{
+    for (int pos = 0; pos < m; pos++)
+    {
+        long sum = 0;
+        for (int k = pos; k < m; k++)
+        {
+            sum += results[idx[k]].reply.weight;
+        }
+        int chosen = pos;
+        if (sum > 0)
+        {
+            int64_t r = rng() % sum; /* uniform in [0, sum) */
+            long acc = 0;
+            for (int k = pos; k < m; k++)
+            {
+                acc += results[idx[k]].reply.weight;
+                if (acc > r)
+                {
+                    chosen = k;
+                    break;
+                }
+            }
+        }
+        int t = idx[pos];
+        idx[pos] = idx[chosen];
+        idx[chosen] = t;
+    }
+}
+
+/* Reorder one priority run (run[0..m), already RTT-sorted) in place:
+ * candidates (RTT within the band of the fastest) first, ordered by weighted
+ * random; then non-candidates in RTT order. */
+static void
+oob_order_priority_run(struct oob_probe_result *run, int m, int client_margin, int64_t (*rng)(void),
+                       struct gc_arena *gc)
+{
+    if (m <= 1)
+    {
+        return;
+    }
+
+    unsigned int best_rtt = run[0].rtt_ms; /* run is RTT-sorted: [0] is fastest */
+
+    int *cand = gc_malloc(sizeof(int) * m, false, gc);
+    int *non = gc_malloc(sizeof(int) * m, false, gc);
+    int nc = 0;
+    int nn = 0;
+    for (int k = 0; k < m; k++)
+    {
+        /* "no more than their max_latency_diff larger than the lowest RTT", so the
+         * comparison includes the margin itself. That also keeps the fastest of
+         * the run a candidate when it advertises 0: announcing 0 asks not to be
+         * compared on weight, not to be ranked behind a slower server. */
+        unsigned int gap = run[k].rtt_ms - best_rtt;
+        if (gap <= (unsigned int)oob_effective_margin(&run[k], client_margin))
+        {
+            cand[nc++] = k;
+        }
+        else
+        {
+            non[nn++] = k;
+        }
+    }
+
+    oob_weighted_order(run, cand, nc, rng);
+
+    struct oob_probe_result *tmp = gc_malloc(sizeof(*tmp) * m, false, gc);
+    int t = 0;
+    for (int k = 0; k < nc; k++)
+    {
+        tmp[t++] = run[cand[k]];
+    }
+    for (int k = 0; k < nn; k++)
+    {
+        tmp[t++] = run[non[k]];
+    }
+    memcpy(run, tmp, sizeof(*run) * m);
+}
+
+void
+oob_rank_probe_results(struct oob_probe_result *results, int n, int client_margin,
+                       int64_t (*rng)(void), struct gc_arena *gc)
+{
+    if (n <= 1)
+    {
+        return;
+    }
+
+    /* Base order: responders first, grouped by priority, RTT-sorted within. */
+    qsort(results, (size_t)n, sizeof(*results), oob_probe_result_compare);
+
+    /* Reorder each priority run of responders by candidate-band + weight. */
+    int i = 0;
+    while (i < n && results[i].responded)
+    {
+        int j = i;
+        while (j < n && results[j].responded
+               && results[j].reply.priority == results[i].reply.priority)
+        {
+            j++;
+        }
+        oob_order_priority_run(results + i, j - i, client_margin, rng, gc);
+        i = j;
+    }
+}
diff --git a/src/openvpn/oob.h b/src/openvpn/oob.h
index 80775a4..0b96a11 100644
--- a/src/openvpn/oob.h
+++ b/src/openvpn/oob.h
@@ -180,4 +180,56 @@
 bool oob_build_probe_reply(struct buffer *probe_payload, uint64_t now, uint64_t window_secs,
                            const struct session_id *peer_sid, struct oob_probe_reply *reply);
 
+/* Candidate-band margin (ms) a server advertises when --server-probe-reply does
+ * not set one. Announcing 0 is a valid choice with a distinct meaning -- only
+ * the lowest-latency server is a candidate -- so an unconfigured server has to
+ * announce something else; the spec suggests 10 to 20 ms. */
+#define OOB_DEFAULT_LATENCY_MARGIN_MS 10
+
+/* Outcome of probing one remote, used to order remotes best-first. @index is
+ * the caller's identifier for the remote (e.g. its position in the connection
+ * list); priority/weight are only meaningful when @responded is true. */
+struct oob_probe_result
+{
+    int index;
+    bool responded;
+    unsigned int rtt_ms;          /* probe round-trip time in ms (responders only) */
+    struct oob_probe_reply reply; /* the values the server advertised */
+};
+
+/**
+ * Order results best-first, in place, per the server-probe selection policy:
+ *   - remotes that responded rank before those that did not (non-responders keep
+ *     their original relative order, last);
+ *   - responders are grouped by priority, lowest priority value first (an
+ *     absolute ordering, never overridden by latency or weight);
+ *   - within a priority group, the "candidates" are the responders whose RTT is
+ *     no more than a margin larger than the fastest in the group (see
+ *     oob_effective_margin()), so the fastest is always one. Candidates are
+ *     ordered ahead of non-candidates;
+ *   - candidates are ordered by DNS-SRV (RFC 2782) weighted-random selection by
+ *     weight, so a server is chosen first with probability proportional to its
+ *     weight (load distribution). Non-candidates follow, ordered by RTT.
+ *
+ * @param results        results to reorder in place
+ * @param n              number of results
+ * @param client_margin  client's candidate-band margin in ms, or < 0 if the
+ *                        client did not set one (see oob_effective_margin())
+ * @param rng            returns a non-negative random value (e.g. get_random);
+ *                       injected so this module stays free of the crypto layer
+ *                       and the weighted ordering is deterministically testable
+ * @param gc             arena for scratch allocation
+ */
+void oob_rank_probe_results(struct oob_probe_result *results, int n, int client_margin,
+                            int64_t (*rng)(void), struct gc_arena *gc);
+
+/**
+ * The candidate-band margin (ms) that applies to one probed remote -- how much
+ * slower than the group's fastest that remote may be and still be a candidate.
+ * It is per-remote: the client's own setting is authoritative, and when
+ * client_margin < 0 each remote is judged by the max_latency_diff its own server
+ * advertised. 0 then admits only the fastest remote and whatever ties with it.
+ */
+int oob_effective_margin(const struct oob_probe_result *r, int client_margin);
+
 #endif /* OOB_H */
diff --git a/tests/unit_tests/openvpn/test_oob.c b/tests/unit_tests/openvpn/test_oob.c
index 183e107..4cac61f 100644
--- a/tests/unit_tests/openvpn/test_oob.c
+++ b/tests/unit_tests/openvpn/test_oob.c
@@ -566,6 +566,219 @@
     gc_free(&gc);
 }
 
+/* Deterministic RNG stubs for the weighted-selection ordering. rank_rng_zero
+ * makes the weighted draw always pick the first remaining candidate, preserving
+ * order; rank_rng_fixed returns a value we set to land in a chosen weight slice. */
+static int64_t
+rank_rng_zero(void)
+{
+    return 0;
+}
+
+static int64_t rank_rng_value;
+static int64_t
+rank_rng_fixed(void)
+{
+    return rank_rng_value;
+}
+
+/* Responders rank ahead of non-responders regardless of index order. */
+static void
+test_rank_responder_before_nonresponder(void **state)
+{
+    struct gc_arena gc = gc_new();
+    struct oob_probe_result r[] = {
+        { .index = 0, .responded = false },
+        { .index = 1, .responded = true, .reply = { .priority = 100, .weight = 50 } },
+    };
+    oob_rank_probe_results(r, 2, 10, rank_rng_zero, &gc);
+    assert_int_equal(r[0].index, 1);
+    assert_int_equal(r[1].index, 0);
+    gc_free(&gc);
+}
+
+/* Among responders, the lowest priority value wins (an absolute ordering). */
+static void
+test_rank_by_priority(void **state)
+{
+    struct gc_arena gc = gc_new();
+    struct oob_probe_result r[] = {
+        { .index = 0, .responded = true, .reply = { .priority = 20, .weight = 50 } },
+        { .index = 1, .responded = true, .reply = { .priority = 5, .weight = 50 } },
+        { .index = 2, .responded = true, .reply = { .priority = 10, .weight = 50 } },
+    };
+    oob_rank_probe_results(r, 3, 10, rank_rng_zero, &gc);
+    assert_int_equal(r[0].index, 1); /* priority 5 */
+    assert_int_equal(r[1].index, 2); /* priority 10 */
+    assert_int_equal(r[2].index, 0); /* priority 20 */
+    gc_free(&gc);
+}
+
+/* Within a priority, only servers within the latency margin of the fastest are
+ * candidates; a slower (out-of-band) server ranks behind a faster one no matter
+ * how large its weight. */
+static void
+test_rank_candidate_band(void **state)
+{
+    struct gc_arena gc = gc_new();
+    struct oob_probe_result r[] = {
+        { .index = 0, .responded = true, .rtt_ms = 100, .reply = { .priority = 10, .weight = 1000 } },
+        { .index = 1, .responded = true, .rtt_ms = 20, .reply = { .priority = 10, .weight = 1 } },
+    };
+    /* margin 10ms: 20ms is fastest; 100ms is 80ms slower -> out of band */
+    oob_rank_probe_results(r, 2, 10, rank_rng_zero, &gc);
+    assert_int_equal(r[0].index, 1); /* fast, in-band, despite tiny weight */
+    assert_int_equal(r[1].index, 0); /* slow, out-of-band, despite huge weight */
+    gc_free(&gc);
+}
+
+/* A server widens its own band via the advertised max_latency_diff, joining the
+ * candidate set even when it is well behind the fastest; it then participates in
+ * the weighted selection. */
+static void
+test_rank_advertised_margin(void **state)
+{
+    struct gc_arena gc = gc_new();
+    struct oob_probe_result r[] = {
+        { .index = 0, .responded = true, .rtt_ms = 20, .reply = { .priority = 10, .weight = 1 } },
+        { .index = 1,
+          .responded = true,
+          .rtt_ms = 100,
+          .reply = { .priority = 10, .weight = 1000, .max_latency_diff = 200 } },
+    };
+    /* Client did not set a margin (-1), so each server's advertised value
+     * applies: the 100ms server advertises 200 -> it is a candidate 80ms behind
+     * the fastest; with weight 1000 (slice [1,1001)) a draw of 500 selects it
+     * first. */
+    rank_rng_value = 500;
+    oob_rank_probe_results(r, 2, -1, rank_rng_fixed, &gc);
+    assert_int_equal(r[0].index, 1);
+    gc_free(&gc);
+}
+
+/* Among candidates, weight drives RFC-2782 proportional selection: a draw is
+ * mapped to the server whose cumulative weight slice it falls in. */
+static void
+test_rank_weighted_selection(void **state)
+{
+    struct gc_arena gc = gc_new();
+    /* equal priority and RTT -> both in band; weights 30 and 70, sum 100:
+     * index 0 owns [0,30), index 1 owns [30,100). */
+    const struct oob_probe_result base[] = {
+        { .index = 0, .responded = true, .rtt_ms = 20, .reply = { .priority = 10, .weight = 30 } },
+        { .index = 1, .responded = true, .rtt_ms = 20, .reply = { .priority = 10, .weight = 70 } },
+    };
+    struct oob_probe_result r[2];
+
+    memcpy(r, base, sizeof(base));
+    rank_rng_value = 10; /* falls in index 0's slice */
+    oob_rank_probe_results(r, 2, 50, rank_rng_fixed, &gc);
+    assert_int_equal(r[0].index, 0);
+
+    memcpy(r, base, sizeof(base));
+    rank_rng_value = 50; /* falls in index 1's slice */
+    oob_rank_probe_results(r, 2, 50, rank_rng_fixed, &gc);
+    assert_int_equal(r[0].index, 1);
+
+    gc_free(&gc);
+}
+
+/* An advertised max_latency_diff of 0 means "compare on latency alone": the
+ * server's own band is empty, so weight cannot float it ahead of a faster peer.
+ * The same pair with a band advertised does let weight decide. */
+static void
+test_rank_advertised_zero_margin(void **state)
+{
+    struct gc_arena gc = gc_new();
+    const struct oob_probe_result base[] = {
+        { .index = 0, .responded = true, .rtt_ms = 20, .reply = { .priority = 10, .weight = 1 } },
+        { .index = 1, .responded = true, .rtt_ms = 40, .reply = { .priority = 10, .weight = 1000 } },
+    };
+    struct oob_probe_result r[2];
+
+    memcpy(r, base, sizeof(base));
+    rank_rng_value = 500;
+    oob_rank_probe_results(r, 2, -1, rank_rng_fixed, &gc);
+    assert_int_equal(r[0].index, 0); /* both advertise 0 -> fastest wins */
+
+    memcpy(r, base, sizeof(base));
+    r[0].reply.max_latency_diff = 50;
+    r[1].reply.max_latency_diff = 50;
+    rank_rng_value = 500;            /* falls in the weight-1000 slice [1,1001) */
+    oob_rank_probe_results(r, 2, -1, rank_rng_fixed, &gc);
+    assert_int_equal(r[0].index, 1); /* 20ms behind but inside a 50ms band */
+
+    gc_free(&gc);
+}
+
+/* The fastest remote is a candidate even when it advertises 0: it competes with
+ * a slower remote whose own band covers the gap instead of being ranked behind
+ * it outright. Neither carries weight here, so the candidate order is RTT order
+ * -- had the fastest fallen out of the band, the slower one would lead. */
+static void
+test_rank_zero_margin_keeps_fastest_a_candidate(void **state)
+{
+    struct gc_arena gc = gc_new();
+    struct oob_probe_result r[] = {
+        { .index = 0, .responded = true, .rtt_ms = 50, .reply = { .priority = 10, .weight = 0, .max_latency_diff = 0 } },
+        { .index = 1, .responded = true, .rtt_ms = 100, .reply = { .priority = 10, .weight = 0, .max_latency_diff = 100 } },
+    };
+    oob_rank_probe_results(r, 2, -1, rank_rng_zero, &gc);
+    assert_int_equal(r[0].index, 0);
+    gc_free(&gc);
+}
+
+/* Remotes tied at the fastest RTT are all candidates even at margin 0, so weight
+ * still distributes load between them. */
+static void
+test_rank_zero_margin_weights_ties(void **state)
+{
+    struct gc_arena gc = gc_new();
+    struct oob_probe_result r[] = {
+        { .index = 0, .responded = true, .rtt_ms = 20, .reply = { .priority = 10, .weight = 1, .max_latency_diff = 0 } },
+        { .index = 1, .responded = true, .rtt_ms = 20, .reply = { .priority = 10, .weight = 1000, .max_latency_diff = 0 } },
+    };
+    rank_rng_value = 500; /* falls in the weight-1000 slice [1,1001) */
+    oob_rank_probe_results(r, 2, -1, rank_rng_fixed, &gc);
+    assert_int_equal(r[0].index, 1);
+    gc_free(&gc);
+}
+
+/* A remote exactly its advertised margin behind the fastest is still a candidate
+ * ("no more than max_latency_diff larger than the lowest RTT"). */
+static void
+test_rank_margin_boundary_is_inclusive(void **state)
+{
+    struct gc_arena gc = gc_new();
+    struct oob_probe_result r[] = {
+        { .index = 0, .responded = true, .rtt_ms = 20, .reply = { .priority = 10, .weight = 1, .max_latency_diff = 10 } },
+        { .index = 1, .responded = true, .rtt_ms = 30, .reply = { .priority = 10, .weight = 1000, .max_latency_diff = 10 } },
+    };
+    rank_rng_value = 500;
+    oob_rank_probe_results(r, 2, -1, rank_rng_fixed, &gc);
+    assert_int_equal(r[0].index, 1); /* exactly 10ms behind, in band, wins on weight */
+    gc_free(&gc);
+}
+
+/* Non-responders are placed last, keeping their original relative order. */
+static void
+test_rank_nonresponders_last(void **state)
+{
+    struct gc_arena gc = gc_new();
+    struct oob_probe_result r[] = {
+        { .index = 0, .responded = false },
+        { .index = 1, .responded = true, .rtt_ms = 20, .reply = { .priority = 10, .weight = 50 } },
+        { .index = 2, .responded = false },
+        { .index = 3, .responded = true, .rtt_ms = 20, .reply = { .priority = 10, .weight = 50 } },
+    };
+    oob_rank_probe_results(r, 4, 10, rank_rng_zero, &gc);
+    assert_int_equal(r[0].index, 1); /* responder (rng_zero keeps order) */
+    assert_int_equal(r[1].index, 3); /* responder */
+    assert_int_equal(r[2].index, 0); /* non-responder, original order kept */
+    assert_int_equal(r[3].index, 2);
+    gc_free(&gc);
+}
+
 int
 main(void)
 {
@@ -593,6 +806,16 @@
         cmocka_unit_test(test_client_reply_read_rejects_unknown_mandatory),
         cmocka_unit_test(test_client_reply_read_missing),
         cmocka_unit_test(test_client_reply_read_wrong_msg_type),
+        cmocka_unit_test(test_rank_responder_before_nonresponder),
+        cmocka_unit_test(test_rank_by_priority),
+        cmocka_unit_test(test_rank_candidate_band),
+        cmocka_unit_test(test_rank_advertised_margin),
+        cmocka_unit_test(test_rank_advertised_zero_margin),
+        cmocka_unit_test(test_rank_zero_margin_keeps_fastest_a_candidate),
+        cmocka_unit_test(test_rank_zero_margin_weights_ties),
+        cmocka_unit_test(test_rank_margin_boundary_is_inclusive),
+        cmocka_unit_test(test_rank_weighted_selection),
+        cmocka_unit_test(test_rank_nonresponders_last),
     };
 
     return cmocka_run_group_tests_name("oob tests", tests, NULL, NULL);

-- 
To view, visit http://gerrit.openvpn.net/c/openvpn/+/1746?usp=email
To unsubscribe, or for help writing mail filters, visit http://gerrit.openvpn.net/settings?usp=email

Gerrit-MessageType: newpatchset
Gerrit-Project: openvpn
Gerrit-Branch: master
Gerrit-Change-Id: I55da68cc341bcfc707fd34ca2f84ff9b6a55501f
Gerrit-Change-Number: 1746
Gerrit-PatchSet: 13
Gerrit-Owner: stipa <[email protected]>
Gerrit-Reviewer: plaisthos <[email protected]>
Gerrit-CC: openvpn-devel <[email protected]>
Gerrit-Attention: plaisthos <[email protected]>

_______________________________________________
Openvpn-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/openvpn-devel