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

Attention is currently required from: stipa.

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 (#10).


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
    within a margin of the fastest (see oob_effective_margin()); 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.

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
(production passes get_random; the tests pass stubs).

RTT is only populated once the client measures it (a later commit); 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, 350 insertions(+), 0 deletions(-)


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

diff --git a/src/openvpn/oob.c b/src/openvpn/oob.c
index bc0e7a3..d32eac6 100644
--- a/src/openvpn/oob.c
+++ b/src/openvpn/oob.c
@@ -155,3 +155,158 @@
     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->priority != rb->priority)
+        {
+            return ra->priority < rb->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 */
+    }
+    if (r->max_latency_diff > 0)
+    {
+        return (int)r->max_latency_diff; /* else the server's advertised value */
+    }
+    return OOB_DEFAULT_LATENCY_MARGIN_MS;
+}
+
+/* Reorder the index list idx[0..m) into DNS-SRV (RFC 2782) weighted-random
+ * order by results[idx[k]].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]].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]].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++)
+    {
+        if (run[k].rtt_ms - best_rtt < (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].priority == results[i].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..a8652ea 100644
--- a/src/openvpn/oob.h
+++ b/src/openvpn/oob.h
@@ -180,4 +180,55 @@
 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) used when neither the client nor the server
+ * specifies one. */
+#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;
+    uint16_t priority;
+    uint16_t weight;
+    uint16_t max_latency_diff; /* margin advertised by this server (ms); 0 = use client default */
+    unsigned int rtt_ms;       /* probe round-trip time in ms (responders only) */
+};
+
+/**
+ * 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
+ *     within a margin of the fastest in the group (see oob_effective_margin()).
+ *     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. The client's
+ * own setting is authoritative: when client_margin >= 0 (the client set
+ * --server-probe with a value) it is used for every remote. Otherwise the
+ * server's advertised max_latency_diff is used when non-zero, falling back to
+ * OOB_DEFAULT_LATENCY_MARGIN_MS.
+ */
+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 48bec2d..004ad8f 100644
--- a/tests/unit_tests/openvpn/test_oob.c
+++ b/tests/unit_tests/openvpn/test_oob.c
@@ -517,6 +517,144 @@
     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, .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, .priority = 20, .weight = 50 },
+        { .index = 1, .responded = true, .priority = 5, .weight = 50 },
+        { .index = 2, .responded = true, .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, .priority = 10, .weight = 1000, .rtt_ms = 100 },
+        { .index = 1, .responded = true, .priority = 10, .weight = 1, .rtt_ms = 20 },
+    };
+    /* 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, .priority = 10, .weight = 1, .rtt_ms = 20 },
+        { .index = 1,
+          .responded = true,
+          .priority = 10,
+          .weight = 1000,
+          .rtt_ms = 100,
+          .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 (the
+     * default 10 would have excluded it); 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, .priority = 10, .weight = 30, .rtt_ms = 20 },
+        { .index = 1, .responded = true, .priority = 10, .weight = 70, .rtt_ms = 20 },
+    };
+    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);
+}
+
+/* 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, .priority = 10, .weight = 50, .rtt_ms = 20 },
+        { .index = 2, .responded = false },
+        { .index = 3, .responded = true, .priority = 10, .weight = 50, .rtt_ms = 20 },
+    };
+    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)
 {
@@ -542,6 +680,12 @@
         cmocka_unit_test(test_client_reply_read_skips_unknown),
         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_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: 10
Gerrit-Owner: stipa <[email protected]>
Gerrit-Reviewer: plaisthos <[email protected]>
Gerrit-CC: openvpn-devel <[email protected]>
Gerrit-Attention: stipa <[email protected]>

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