Attention is currently required from: plaisthos.
Hello plaisthos,
I'd like you to do a code review.
Please visit
http://gerrit.openvpn.net/c/openvpn/+/1746?usp=email
to review the following change.
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, 343 insertions(+), 0 deletions(-)
git pull ssh://gerrit.openvpn.net:29418/openvpn refs/changes/46/1746/1
diff --git a/src/openvpn/oob.c b/src/openvpn/oob.c
index 9cc7c42..9b359dd 100644
--- a/src/openvpn/oob.c
+++ b/src/openvpn/oob.c
@@ -241,3 +241,151 @@
/* priority/weight/connect_lifetime/flags left at 0 for now */
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)
+ {
+ return ra->responded ? -1 : 1;
+ }
+ if (ra->responded)
+ {
+ 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;
+ }
+ }
+ 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 @p 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,
long (*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)
+ {
+ long 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 (@p 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,
long (*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,
+ long (*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 9040416..65e84bd 100644
--- a/src/openvpn/oob.h
+++ b/src/openvpn/oob.h
@@ -215,4 +215,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 @p 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,
+ long (*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 @p client_margin >= 0 (the client set
+ * --server-probe with a value) it is used for every remote. Otherwise the
+ * server's advertised @c 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 1029399..b66ade2 100644
--- a/tests/unit_tests/openvpn/test_oob.c
+++ b/tests/unit_tests/openvpn/test_oob.c
@@ -429,6 +429,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 long
+rank_rng_zero(void)
+{
+ return 0;
+}
+
+static long rank_rng_value;
+static long
+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)
{
@@ -452,6 +590,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: newchange
Gerrit-Project: openvpn
Gerrit-Branch: master
Gerrit-Change-Id: I55da68cc341bcfc707fd34ca2f84ff9b6a55501f
Gerrit-Change-Number: 1746
Gerrit-PatchSet: 1
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
