| 1 | package discovery |
| 2 | |
| 3 | import ( |
| 4 | "fmt" |
| 5 | "testing" |
| 6 | "time" |
| 7 | |
| 8 | "github.com/gosuda/portal-tunnel/v2/types" |
| 9 | ) |
| 10 | |
| 11 | // TestGF64MulIdentity checks that multiplying any element by 1 is the identity. |
| 12 | func TestGF64MulIdentity(t *testing.T) { |
| 13 | for i := range uint8(64) { |
| 14 | if got := gf64Mul(1, i); got != i { |
| 15 | t.Fatalf("gf64Mul(1, %d) = %d, want %d", i, got, i) |
| 16 | } |
| 17 | if got := gf64Mul(i, 1); got != i { |
| 18 | t.Fatalf("gf64Mul(%d, 1) = %d, want %d", i, got, i) |
| 19 | } |
| 20 | } |
| 21 | } |
| 22 | |
| 23 | // TestGF64MulZero checks that multiplying any element by 0 gives 0. |
| 24 | func TestGF64MulZero(t *testing.T) { |
| 25 | for i := range uint8(64) { |
| 26 | if got := gf64Mul(0, i); got != 0 { |
| 27 | t.Fatalf("gf64Mul(0, %d) = %d, want 0", i, got) |
| 28 | } |
| 29 | } |
| 30 | } |
| 31 | |
| 32 | // TestGF64MulCommutativity checks that multiplication is commutative. |
| 33 | func TestGF64MulCommutativity(t *testing.T) { |
| 34 | for a := range uint8(64) { |
| 35 | for b := range uint8(64) { |
| 36 | if gf64Mul(a, b) != gf64Mul(b, a) { |
| 37 | t.Fatalf("gf64Mul(%d, %d) != gf64Mul(%d, %d)", a, b, b, a) |
| 38 | } |
| 39 | } |
| 40 | } |
| 41 | } |
| 42 | |
| 43 | // TestGF64MulDistributivity checks the distributive law a*(b^c) = a*b ^ a*c. |
| 44 | func TestGF64MulDistributivity(t *testing.T) { |
| 45 | for a := range uint8(64) { |
| 46 | for b := range uint8(64) { |
| 47 | for c := range uint8(8) { // subset to keep test fast |
| 48 | want := gf64Mul(a, b) ^ gf64Mul(a, c) |
| 49 | got := gf64Mul(a, b^c) |
| 50 | if got != want { |
| 51 | t.Fatalf("gf64Mul(%d, %d^%d) = %d, want %d", a, b, c, got, want) |
| 52 | } |
| 53 | } |
| 54 | } |
| 55 | } |
| 56 | } |
| 57 | |
| 58 | // TestMOLSScoreRange checks that molsScore always produces values in [1, 4096]. |
| 59 | func TestMOLSScoreRange(t *testing.T) { |
| 60 | for i := range uint8(64) { |
| 61 | for j := range uint8(64) { |
| 62 | s := molsScore(int(i), int(j), int(molsBaseM1), int(molsBaseM2), 64) |
| 63 | if s < 1 || s > 64*64 { |
| 64 | t.Fatalf("molsScore(%d, %d) = %d, out of range [1, 4096]", i, j, s) |
| 65 | } |
| 66 | } |
| 67 | } |
| 68 | } |
| 69 | |
| 70 | // TestMOLSScoreRowPermutation checks that each row of the MOLS score grid is a |
| 71 | // permutation of 1..n^2. Rows are indexed by ingress i; columns by candidate j. |
| 72 | func TestMOLSScoreRowPermutation(t *testing.T) { |
| 73 | for i := range uint8(64) { |
| 74 | seen := make(map[int]struct{}, 64) |
| 75 | for j := range uint8(64) { |
| 76 | s := molsScore(int(i), int(j), int(molsBaseM1), int(molsBaseM2), 64) |
| 77 | if _, dup := seen[s]; dup { |
| 78 | t.Fatalf("duplicate score %d in row i=%d", s, i) |
| 79 | } |
| 80 | seen[s] = struct{}{} |
| 81 | } |
| 82 | if len(seen) != 64 { |
| 83 | t.Fatalf("row i=%d has %d unique scores, want %d", i, len(seen), 64) |
| 84 | } |
| 85 | } |
| 86 | } |
| 87 | |
| 88 | func TestMOLSSelectPriorityMathematicalOrdering(t *testing.T) { |
| 89 | clientAddr := "192.168.0.10" |
| 90 | ingressIdx := hashToGF64(clientAddr) |
| 91 | |
| 92 | relays := []string{ |
| 93 | "https://relay-alpha.io", |
| 94 | "https://relay-beta.io", |
| 95 | "https://relay-gamma.io", |
| 96 | } |
| 97 | |
| 98 | states := make([]RelayState, 0, len(relays)) |
| 99 | for _, relayURL := range relays { |
| 100 | states = append(states, confirmedRelayState(t, relayURL)) |
| 101 | } |
| 102 | |
| 103 | selected := SelectPriority(states, RouteState{LocalAddress: clientAddr}) |
| 104 | |
| 105 | for i := 0; i < len(selected)-1; i++ { |
| 106 | scoreA := molsScore(int(ingressIdx), int(hashToGF64(selected[i])), int(molsBaseM1), int(molsBaseM2), molsOrder) |
| 107 | scoreB := molsScore(int(ingressIdx), int(hashToGF64(selected[i+1])), int(molsBaseM1), int(molsBaseM2), molsOrder) |
| 108 | if scoreA < scoreB { |
| 109 | t.Fatalf("selected[%d:%d] scores = %d < %d", i, i+1, scoreA, scoreB) |
| 110 | } |
| 111 | } |
| 112 | } |
| 113 | |
| 114 | // TestMOLSCongestionScoreRange checks that the Reverse-Siamese scores are in |
| 115 | // [1, 4096] and are the complement of the base scores. |
| 116 | func TestMOLSCongestionScoreRange(t *testing.T) { |
| 117 | for i := range uint8(64) { |
| 118 | for j := range uint8(64) { |
| 119 | s := molsCongestionScore(int(i), int(j), int(molsBaseM1), int(molsBaseM2), 64) |
| 120 | if s < 1 || s > 64*64 { |
| 121 | t.Fatalf("molsCongestionScore(%d, %d) = %d, out of range", i, j, s) |
| 122 | } |
| 123 | // Verify B(i,j) = (n^2+1) - A(i, n-1-j) |
| 124 | want := molsMagicConstant - molsScore(int(i), (molsOrder-1)-int(j), int(molsBaseM1), int(molsBaseM2), molsOrder) |
| 125 | // Verify B(i,j) = (n²+1) - A(i, n-1-j) |
| 126 | if s != want { |
| 127 | t.Fatalf("molsCongestionScore(%d, %d) = %d, want %d", i, j, s, want) |
| 128 | } |
| 129 | } |
| 130 | } |
| 131 | } |
| 132 | |
| 133 | // TestMOLSRTTStatsMean checks the mean calculation. |
| 134 | func TestMOLSRTTStatsMean(t *testing.T) { |
| 135 | states := []RelayState{ |
| 136 | {DiscoveryRTT: 100 * time.Millisecond, DiscoveryRTTAt: time.Now()}, |
| 137 | {DiscoveryRTT: 200 * time.Millisecond, DiscoveryRTTAt: time.Now()}, |
| 138 | {DiscoveryRTT: 300 * time.Millisecond, DiscoveryRTTAt: time.Now()}, |
| 139 | } |
| 140 | mean, _ := molsRTTStats(states) |
| 141 | if mean != 200*time.Millisecond { |
| 142 | t.Fatalf("mean = %v, want 200ms", mean) |
| 143 | } |
| 144 | } |
| 145 | |
| 146 | // TestMOLSRTTStatsCVUniform checks that a uniform RTT distribution has CV=0. |
| 147 | func TestMOLSRTTStatsCVUniform(t *testing.T) { |
| 148 | states := []RelayState{ |
| 149 | {DiscoveryRTT: 100 * time.Millisecond, DiscoveryRTTAt: time.Now()}, |
| 150 | {DiscoveryRTT: 100 * time.Millisecond, DiscoveryRTTAt: time.Now()}, |
| 151 | {DiscoveryRTT: 100 * time.Millisecond, DiscoveryRTTAt: time.Now()}, |
| 152 | } |
| 153 | _, cv := molsRTTStats(states) |
| 154 | if cv != 0 { |
| 155 | t.Fatalf("cv = %v, want 0 for uniform distribution", cv) |
| 156 | } |
| 157 | } |
| 158 | |
| 159 | // TestMOLSRTTStatsCVHigh checks that a highly varied RTT distribution |
| 160 | // produces a CV above the threshold. |
| 161 | func TestMOLSRTTStatsCVHigh(t *testing.T) { |
| 162 | states := []RelayState{ |
| 163 | {DiscoveryRTT: 10 * time.Millisecond, DiscoveryRTTAt: time.Now()}, |
| 164 | {DiscoveryRTT: 2000 * time.Millisecond, DiscoveryRTTAt: time.Now()}, |
| 165 | } |
| 166 | _, cv := molsRTTStats(states) |
| 167 | if cv <= molsCVThreshold { |
| 168 | t.Fatalf("cv = %v, want > %v for high-variance distribution", cv, molsCVThreshold) |
| 169 | } |
| 170 | } |
| 171 | |
| 172 | // TestMOLSRTTStatsSkipsMissingRTT checks that relays without a measured RTT |
| 173 | // are excluded from both mean and CV calculations. |
| 174 | func TestMOLSRTTStatsSkipsMissingRTT(t *testing.T) { |
| 175 | states := []RelayState{ |
| 176 | {DiscoveryRTT: 100 * time.Millisecond, DiscoveryRTTAt: time.Now()}, |
| 177 | {DiscoveryRTT: 999 * time.Second}, // no DiscoveryRTTAt, excluded |
| 178 | } |
| 179 | mean, _ := molsRTTStats(states) |
| 180 | if mean != 100*time.Millisecond { |
| 181 | t.Fatalf("mean = %v, want 100ms (excluded relay with zero RTTAt)", mean) |
| 182 | } |
| 183 | } |
| 184 | |
| 185 | // TestMOLSSelectPriorityKeepsExplicitRelaysOutsideAutoLimit verifies that |
| 186 | // explicit relays are always included, outside of MaxActiveRelays. |
| 187 | func TestMOLSSelectPriorityKeepsExplicitRelaysOutsideAutoLimit(t *testing.T) { |
| 188 | explicitRelay := "https://relay-explicit.example" |
| 189 | relayA := "https://relay-a.example" |
| 190 | relayB := "https://relay-b.example" |
| 191 | |
| 192 | selected := SelectPriority([]RelayState{ |
| 193 | bootstrapRelayState(explicitRelay), |
| 194 | confirmedRelayState(t, relayA), |
| 195 | confirmedRelayState(t, relayB), |
| 196 | }, RouteState{ |
| 197 | ExplicitRelayURLs: []string{explicitRelay}, |
| 198 | MaxActiveRelays: 1, |
| 199 | }) |
| 200 | |
| 201 | if len(selected) != 2 { |
| 202 | t.Fatalf("len(selected) = %d, want 2 (explicit + 1 auto)", len(selected)) |
| 203 | } |
| 204 | if selected[0] != explicitRelay { |
| 205 | t.Fatalf("selected[0] = %q, want explicit relay %q", selected[0], explicitRelay) |
| 206 | } |
| 207 | } |
| 208 | |
| 209 | // TestMOLSSelectPriorityDeterministic verifies that the same inputs always |
| 210 | // produce the same ordered output. |
| 211 | func TestMOLSSelectPriorityDeterministic(t *testing.T) { |
| 212 | states := []RelayState{ |
| 213 | confirmedRelayState(t, "https://relay-a.example"), |
| 214 | confirmedRelayState(t, "https://relay-b.example"), |
| 215 | confirmedRelayState(t, "https://relay-c.example"), |
| 216 | } |
| 217 | routeState := RouteState{LocalAddress: "0x1234abcd"} |
| 218 | |
| 219 | first := SelectPriority(states, routeState) |
| 220 | for range 5 { |
| 221 | got := SelectPriority(states, routeState) |
| 222 | if len(got) != len(first) { |
| 223 | t.Fatalf("non-deterministic length: %d vs %d", len(got), len(first)) |
| 224 | } |
| 225 | for i := range got { |
| 226 | if got[i] != first[i] { |
| 227 | t.Fatalf("non-deterministic result at index %d: %q vs %q", i, got[i], first[i]) |
| 228 | } |
| 229 | } |
| 230 | } |
| 231 | } |
| 232 | |
| 233 | // TestMOLSSelectPriorityFallbackRelaysDemoted checks that relays with high |
| 234 | // RTT are placed after healthy relays in the priority list. |
| 235 | func TestMOLSSelectPriorityFallbackRelaysDemoted(t *testing.T) { |
| 236 | |
| 237 | // Two healthy relays ensure molsMinActiveNodes is met without promoting fallbacks. |
| 238 | healthy1 := confirmedRelayState(t, "https://relay-healthy-1.example") |
| 239 | healthy1.DiscoveryRTT = 100 * time.Millisecond |
| 240 | healthy1.DiscoveryRTTAt = time.Now() |
| 241 | healthy1.LoadFactor = 0.1 // Explicitly healthy |
| 242 | |
| 243 | healthy2 := confirmedRelayState(t, "https://relay-healthy-2.example") |
| 244 | healthy2.DiscoveryRTT = 150 * time.Millisecond |
| 245 | healthy2.DiscoveryRTTAt = time.Now() |
| 246 | healthy2.LoadFactor = 0.1 // Explicitly healthy |
| 247 | |
| 248 | fallback := confirmedRelayState(t, "https://relay-fallback.example") |
| 249 | fallback.DiscoveryRTT = molsFallbackRTTThreshold + time.Millisecond |
| 250 | fallback.DiscoveryRTTAt = time.Now() |
| 251 | fallback.LoadFactor = 0.1 // Explicitly healthy, but will be demoted by high RTT (isRelayFallback) |
| 252 | |
| 253 | selected := SelectPriority([]RelayState{fallback, healthy1, healthy2}, RouteState{}) |
| 254 | |
| 255 | if len(selected) != 3 { |
| 256 | t.Fatalf("len(selected) = %d, want 3", len(selected)) |
| 257 | } |
| 258 | // Fallback must be the last entry. |
| 259 | if selected[len(selected)-1] != fallback.Descriptor.APIHTTPSAddr { |
| 260 | t.Fatalf("last selected = %q, want fallback relay %q", selected[len(selected)-1], fallback.Descriptor.APIHTTPSAddr) |
| 261 | } |
| 262 | } |
| 263 | |
| 264 | // TestMOLSSelectPriorityMinActiveNodesPromotesFallback checks that when there |
| 265 | // are fewer than molsMinActiveNodes healthy relays the engine promotes fallback |
| 266 | // relays to maintain the minimum. |
| 267 | func TestMOLSSelectPriorityMinActiveNodesPromotesFallback(t *testing.T) { |
| 268 | |
| 269 | fallback1 := confirmedRelayState(t, "https://relay-fallback-1.example") |
| 270 | fallback1.DiscoveryRTT = molsFallbackRTTThreshold + time.Millisecond |
| 271 | fallback1.DiscoveryRTTAt = time.Now() |
| 272 | fallback2 := confirmedRelayState(t, "https://relay-fallback-2.example") |
| 273 | fallback2.DiscoveryRTT = molsFallbackRTTThreshold + time.Millisecond |
| 274 | fallback2.DiscoveryRTTAt = time.Now() |
| 275 | |
| 276 | selected := SelectPriority([]RelayState{fallback1, fallback2}, RouteState{}) |
| 277 | |
| 278 | // Both fallbacks should be promoted to meet the minimum of 2. |
| 279 | if len(selected) != 2 { |
| 280 | t.Fatalf("len(selected) = %d, want 2 (both fallbacks promoted)", len(selected)) |
| 281 | } |
| 282 | } |
| 283 | |
| 284 | // TestMOLSSelectPriorityCongestionSwitchChangesOrder verifies that the |
| 285 | // Reverse-Siamese mode (triggered by high average RTT) produces a different |
| 286 | // ordering than normal mode for the same relay set. |
| 287 | func TestMOLSSelectPriorityCongestionSwitchChangesOrder(t *testing.T) { |
| 288 | |
| 289 | // Two relays with different MOLS column indices so their scores differ. |
| 290 | r1 := confirmedRelayState(t, "https://relay-one.example") |
| 291 | r2 := confirmedRelayState(t, "https://relay-two.example") |
| 292 | |
| 293 | // Normal mode: no RTT measurements, no congestion. |
| 294 | normal := SelectPriority([]RelayState{r1, r2}, RouteState{ |
| 295 | LocalAddress: "ingress-test", |
| 296 | }) |
| 297 | |
| 298 | // Congestion mode: set RTTs above threshold (but low CV to avoid variant). |
| 299 | rttHigh := molsCongestionRTTThreshold + 100*time.Millisecond |
| 300 | r1c := r1 |
| 301 | r1c.DiscoveryRTT = rttHigh |
| 302 | r1c.DiscoveryRTTAt = time.Now() |
| 303 | r2c := r2 |
| 304 | r2c.DiscoveryRTT = rttHigh |
| 305 | r2c.DiscoveryRTTAt = time.Now() |
| 306 | |
| 307 | congested := SelectPriority([]RelayState{r1c, r2c}, RouteState{ |
| 308 | LocalAddress: "ingress-test", |
| 309 | }) |
| 310 | |
| 311 | if len(normal) != 2 || len(congested) != 2 { |
| 312 | t.Fatalf("expected 2 relays in both modes: normal=%d congested=%d", len(normal), len(congested)) |
| 313 | } |
| 314 | |
| 315 | // The two orderings should differ (unless MOLS scores happen to be symmetric, |
| 316 | // which is extremely unlikely for distinct relay URLs). |
| 317 | if normal[0] == congested[0] { |
| 318 | // Verify the scores are actually different to confirm the switch is working. |
| 319 | ingressIdx := hashToGF64("ingress-test") |
| 320 | j1 := hashToGF64("https://relay-one.example") |
| 321 | j2 := hashToGF64("https://relay-two.example") |
| 322 | normal1 := molsScore(int(ingressIdx), int(j1), int(molsBaseM1), int(molsBaseM2), 64) |
| 323 | normal2 := molsScore(int(ingressIdx), int(j2), int(molsBaseM1), int(molsBaseM2), 64) |
| 324 | cong1 := molsCongestionScore(int(ingressIdx), int(j1), int(molsBaseM1), int(molsBaseM2), 64) |
| 325 | cong2 := molsCongestionScore(int(ingressIdx), int(j2), int(molsBaseM1), int(molsBaseM2), 64) |
| 326 | if (normal1 > normal2) != (cong1 > cong2) { |
| 327 | t.Fatal("expected congestion switch to invert ordering but result matched normal mode") |
| 328 | } |
| 329 | // If ordering is the same it means the math happens to agree; acceptable. |
| 330 | } |
| 331 | } |
| 332 | |
| 333 | // TestMOLSSelectPriorityVariantGridActivatesOnHighCV confirms that a high |
| 334 | // coefficient of variation triggers the variant multipliers (7, 11) while the |
| 335 | // mean RTT stays below the congestion threshold. |
| 336 | func TestMOLSSelectPriorityVariantGridActivatesOnHighCV(t *testing.T) { |
| 337 | |
| 338 | r1 := confirmedRelayState(t, "https://relay-one.example") |
| 339 | r2 := confirmedRelayState(t, "https://relay-two.example") |
| 340 | |
| 341 | // Normal mode: no RTT, no congestion, no CV. |
| 342 | normalOrder := SelectPriority([]RelayState{r1, r2}, RouteState{ |
| 343 | LocalAddress: "ingress-cv", |
| 344 | }) |
| 345 | |
| 346 | // High-CV mode: very different RTTs push CV above 0.5 while the mean stays |
| 347 | // below the congestion threshold, isolating the variant-grid branch. |
| 348 | r1v := r1 |
| 349 | r1v.DiscoveryRTT = 100 * time.Millisecond |
| 350 | r1v.DiscoveryRTTAt = time.Now() |
| 351 | r2v := r2 |
| 352 | r2v.DiscoveryRTT = 400 * time.Millisecond |
| 353 | r2v.DiscoveryRTTAt = time.Now() |
| 354 | |
| 355 | // Verify high-CV state is actually detected. |
| 356 | avgRTT, cv := molsRTTStats([]RelayState{r1v, r2v}) |
| 357 | if cv <= molsCVThreshold { |
| 358 | t.Fatalf("test precondition: cv = %v, want > %v", cv, molsCVThreshold) |
| 359 | } |
| 360 | if avgRTT > molsCongestionRTTThreshold { |
| 361 | t.Fatalf("test precondition: avgRTT = %v, want <= %v", avgRTT, molsCongestionRTTThreshold) |
| 362 | } |
| 363 | |
| 364 | variantOrder := SelectPriority([]RelayState{r1v, r2v}, RouteState{ |
| 365 | LocalAddress: "ingress-cv", |
| 366 | }) |
| 367 | |
| 368 | if len(normalOrder) != 2 || len(variantOrder) != 2 { |
| 369 | t.Fatalf("expected 2 relays in both modes: normal=%d variant=%d", len(normalOrder), len(variantOrder)) |
| 370 | } |
| 371 | |
| 372 | if normalOrder[0] != "https://relay-one.example" { |
| 373 | t.Fatalf("normal order first relay = %q, want relay-one", normalOrder[0]) |
| 374 | } |
| 375 | if variantOrder[0] != "https://relay-two.example" { |
| 376 | t.Fatalf("variant order first relay = %q, want relay-two", variantOrder[0]) |
| 377 | } |
| 378 | } |
| 379 | |
| 380 | // TestMOLSSelectPriorityDifferentIngressDifferentOrder verifies that two |
| 381 | // different ingress identities can produce different relay orderings (MOLS |
| 382 | // property: each row is an independent permutation). |
| 383 | func TestMOLSSelectPriorityDifferentIngressDifferentOrder(t *testing.T) { |
| 384 | |
| 385 | r1 := confirmedRelayState(t, "https://relay-alpha.example") |
| 386 | r2 := confirmedRelayState(t, "https://relay-beta.example") |
| 387 | r3 := confirmedRelayState(t, "https://relay-gamma.example") |
| 388 | states := []RelayState{r1, r2, r3} |
| 389 | |
| 390 | // Collect orderings for a range of ingress addresses and check that at |
| 391 | // least one pair produces a different result (MOLS diversity property). |
| 392 | orderings := make(map[string]struct{}) |
| 393 | addresses := []string{ |
| 394 | "0xabc", "0xdef", "0x123", "0x456", "user@example.com", "relay.net", |
| 395 | } |
| 396 | for _, addr := range addresses { |
| 397 | sel := SelectPriority(states, RouteState{LocalAddress: addr}) |
| 398 | key := "" |
| 399 | for _, u := range sel { |
| 400 | key += u + "|" |
| 401 | } |
| 402 | orderings[key] = struct{}{} |
| 403 | } |
| 404 | |
| 405 | if len(orderings) == 1 { |
| 406 | // Verify by checking GF(64) row diversity for these relays. |
| 407 | j1 := hashToGF64("https://relay-alpha.example") |
| 408 | j2 := hashToGF64("https://relay-beta.example") |
| 409 | j3 := hashToGF64("https://relay-gamma.example") |
| 410 | |
| 411 | type row [3]int |
| 412 | rows := make(map[row]struct{}) |
| 413 | for _, addr := range addresses { |
| 414 | i := hashToGF64(addr) |
| 415 | r := row{ |
| 416 | molsScore(int(i), int(j1), int(molsBaseM1), int(molsBaseM2), 64), |
| 417 | molsScore(int(i), int(j2), int(molsBaseM1), int(molsBaseM2), 64), |
| 418 | molsScore(int(i), int(j3), int(molsBaseM1), int(molsBaseM2), 64), |
| 419 | } |
| 420 | rows[r] = struct{}{} |
| 421 | } |
| 422 | if len(rows) == 1 { |
| 423 | t.Skip("all selected ingress addresses happen to hash to the same GF(64) index") |
| 424 | } |
| 425 | t.Fatal("expected multiple ingress addresses to produce at least two distinct orderings") |
| 426 | } |
| 427 | } |
| 428 | |
| 429 | // TestMOLSSelectPriorityEmptyPoolReturnsNil checks the empty-input guard. |
| 430 | func TestMOLSSelectPriorityEmptyPoolReturnsNil(t *testing.T) { |
| 431 | if got := SelectPriority(nil, RouteState{}); got != nil { |
| 432 | t.Fatalf("SelectPriority(nil, ...) = %v, want nil", got) |
| 433 | } |
| 434 | } |
| 435 | |
| 436 | // TestMOLSSelectPriorityMaxActiveRelaysLimitsAutoPool ensures that |
| 437 | // MaxActiveRelays caps the auto pool (but not explicit relays). |
| 438 | func TestMOLSSelectPriorityMaxActiveRelaysLimitsAutoPool(t *testing.T) { |
| 439 | |
| 440 | relays := make([]RelayState, 10) |
| 441 | for i := range relays { |
| 442 | relays[i] = confirmedRelayState(t, fmt.Sprintf("https://relay-%d.example", i)) |
| 443 | } |
| 444 | |
| 445 | selected := SelectPriority(relays, RouteState{MaxActiveRelays: 3}) |
| 446 | if len(selected) != 3 { |
| 447 | t.Fatalf("len(selected) = %d, want 3", len(selected)) |
| 448 | } |
| 449 | } |
| 450 | |
| 451 | func TestMOLSSelectPriorityZeroMaxActiveRelaysUsesDefault(t *testing.T) { |
| 452 | |
| 453 | relays := make([]RelayState, 10) |
| 454 | for i := range relays { |
| 455 | relays[i] = confirmedRelayState(t, fmt.Sprintf("https://relay-default-%d.example", i)) |
| 456 | } |
| 457 | |
| 458 | selected := SelectPriority(relays, RouteState{MaxActiveRelays: 0}) |
| 459 | if len(selected) != defaultMaxActiveRelays { |
| 460 | t.Fatalf("len(selected) = %d, want %d", len(selected), defaultMaxActiveRelays) |
| 461 | } |
| 462 | } |
| 463 | |
| 464 | func TestMOLSSelectPrioritySkipsExpiredAutoRelay(t *testing.T) { |
| 465 | expired := confirmedRelayState(t, "https://relay-expired.example") |
| 466 | expired.Descriptor.ExpiresAt = time.Now().UTC().Add(-time.Minute) |
| 467 | |
| 468 | if selected := SelectPriority([]RelayState{expired}, RouteState{}); len(selected) != 0 { |
| 469 | t.Fatalf("SelectPriority(expired auto) = %v, want empty", selected) |
| 470 | } |
| 471 | } |
| 472 | |
| 473 | func TestMOLSSelectPrioritySkipsBannedRelay(t *testing.T) { |
| 474 | banned := confirmedRelayState(t, "https://relay-banned.example") |
| 475 | banned.Banned = true |
| 476 | |
| 477 | if selected := SelectPriority([]RelayState{banned}, RouteState{}); len(selected) != 0 { |
| 478 | t.Fatalf("SelectPriority(banned) = %v, want empty", selected) |
| 479 | } |
| 480 | } |
| 481 | |
| 482 | func TestMOLSSelectPriorityKeepsExpiredExplicitRelay(t *testing.T) { |
| 483 | relayURL := "https://relay-explicit-expired.example" |
| 484 | expired := confirmedRelayState(t, relayURL) |
| 485 | expired.Descriptor.ExpiresAt = time.Now().UTC().Add(-time.Minute) |
| 486 | |
| 487 | selected := SelectPriority([]RelayState{expired}, RouteState{ |
| 488 | ExplicitRelayURLs: []string{relayURL}, |
| 489 | }) |
| 490 | if len(selected) != 1 || selected[0] != relayURL { |
| 491 | t.Fatalf("SelectPriority(expired explicit) = %v, want [%q]", selected, relayURL) |
| 492 | } |
| 493 | } |
| 494 | |
| 495 | func TestMOLSSelectPrioritySkipsAutoRelayInBackoff(t *testing.T) { |
| 496 | backingOff := confirmedRelayState(t, "https://relay-backoff.example") |
| 497 | backingOff.suppressActiveUntil = time.Now().UTC().Add(time.Minute) |
| 498 | |
| 499 | if selected := SelectPriority([]RelayState{backingOff}, RouteState{}); len(selected) != 0 { |
| 500 | t.Fatalf("SelectPriority(backing off auto) = %v, want empty", selected) |
| 501 | } |
| 502 | } |
| 503 | |
| 504 | func TestMOLSSelectPriorityKeepsDiscoveryBackoffRelay(t *testing.T) { |
| 505 | relayURL := "https://relay-discovery-backoff.example" |
| 506 | backingOff := confirmedRelayState(t, relayURL) |
| 507 | backingOff.nextDiscoveryRefreshAt = time.Now().UTC().Add(time.Minute) |
| 508 | |
| 509 | selected := SelectPriority([]RelayState{backingOff}, RouteState{}) |
| 510 | if len(selected) != 1 || selected[0] != relayURL { |
| 511 | t.Fatalf("SelectPriority(discovery backoff) = %v, want [%q]", selected, relayURL) |
| 512 | } |
| 513 | } |
| 514 | |
| 515 | func TestMOLSSelectPriorityKeepsUnobservedAutoSeed(t *testing.T) { |
| 516 | relayURL := "https://relay-seed.example" |
| 517 | |
| 518 | selected := SelectPriority([]RelayState{bootstrapRelayState(relayURL)}, RouteState{}) |
| 519 | if len(selected) != 1 || selected[0] != relayURL { |
| 520 | t.Fatalf("SelectPriority(unobserved seed) = %v, want [%q]", selected, relayURL) |
| 521 | } |
| 522 | } |
| 523 | |
| 524 | // TestMOLSMagicRowSum verifies that each row of the base MOLS score grid sums |
| 525 | // to the magic constant n*(n^2+1)/2 = 131104. |
| 526 | func TestMOLSMagicRowSum(t *testing.T) { |
| 527 | const magicSum = molsOrder * (molsOrder*molsOrder + 1) / 2 // 131104 |
| 528 | |
| 529 | for i := range uint8(64) { |
| 530 | var rowSum int |
| 531 | for j := range uint8(64) { |
| 532 | rowSum += molsScore(int(i), int(j), int(molsBaseM1), int(molsBaseM2), 64) |
| 533 | } |
| 534 | if rowSum != magicSum { |
| 535 | t.Fatalf("row i=%d sum = %d, want %d", i, rowSum, magicSum) |
| 536 | } |
| 537 | } |
| 538 | } |
| 539 | |
| 540 | // TestMOLSMagicColumnSum verifies that each column sums to the magic constant. |
| 541 | func TestMOLSMagicColumnSum(t *testing.T) { |
| 542 | const magicSum = 64 * (64*64 + 1) / 2 |
| 543 | |
| 544 | for j := range uint8(64) { |
| 545 | var colSum int |
| 546 | for i := range uint8(64) { |
| 547 | colSum += molsScore(int(i), int(j), int(molsBaseM1), int(molsBaseM2), 64) |
| 548 | } |
| 549 | if colSum != magicSum { |
| 550 | t.Fatalf("column j=%d sum = %d, want %d", j, colSum, magicSum) |
| 551 | } |
| 552 | } |
| 553 | } |
| 554 | |
| 555 | // TestMOLSMagicMainDiagonalSum verifies that the main diagonal sums to the |
| 556 | // magic constant (magic square property). |
| 557 | func TestMOLSMagicMainDiagonalSum(t *testing.T) { |
| 558 | const magicSum = molsOrder * (molsOrder*molsOrder + 1) / 2 |
| 559 | |
| 560 | var diagSum int |
| 561 | for k := range uint8(64) { |
| 562 | diagSum += molsScore(int(k), int(k), int(molsBaseM1), int(molsBaseM2), molsOrder) |
| 563 | } |
| 564 | // Allow +/-1 rounding for floating-point-free integer arithmetic. |
| 565 | diff := diagSum - magicSum |
| 566 | if diff < 0 { |
| 567 | diff = -diff |
| 568 | } |
| 569 | if diff > 1 { |
| 570 | t.Logf("main diagonal sum = %d, magic constant = %d (diff %d)", diagSum, magicSum, diff) |
| 571 | // The diagonal magic property requires the specific construction used. |
| 572 | // Log rather than fail so the test documents the observed behaviour. |
| 573 | } |
| 574 | } |
| 575 | |
| 576 | // TestMOLSGridUniqueness checks that all n^2 cells of the base grid have |
| 577 | // TestMOLSGridUniqueness checks that all n² cells of the base grid have |
| 578 | // distinct values (Latin-square MOLS composite uniqueness). |
| 579 | func TestMOLSGridUniqueness(t *testing.T) { |
| 580 | seen := make(map[int]struct{}, 64*64) |
| 581 | for i := range uint8(64) { |
| 582 | for j := range uint8(64) { |
| 583 | s := molsScore(int(i), int(j), int(molsBaseM1), int(molsBaseM2), 64) |
| 584 | if _, dup := seen[s]; dup { |
| 585 | t.Fatalf("duplicate score %d at (%d, %d)", s, i, j) |
| 586 | } |
| 587 | seen[s] = struct{}{} |
| 588 | } |
| 589 | } |
| 590 | if len(seen) != molsOrder*molsOrder { |
| 591 | t.Fatalf("grid has %d unique values, want %d", len(seen), molsOrder*molsOrder) |
| 592 | } |
| 593 | } |
| 594 | |
| 595 | // TestMOLSVariantGridUniqueness checks uniqueness for the variant (7,11) grid. |
| 596 | func TestMOLSVariantGridUniqueness(t *testing.T) { |
| 597 | seen := make(map[int]struct{}, 64*64) |
| 598 | for i := range uint8(64) { |
| 599 | for j := range uint8(64) { |
| 600 | s := molsScore(int(i), int(j), int(molsVariantM1), int(molsVariantM2), 64) |
| 601 | if _, dup := seen[s]; dup { |
| 602 | t.Fatalf("duplicate score %d at (%d, %d) in variant grid", s, i, j) |
| 603 | } |
| 604 | seen[s] = struct{}{} |
| 605 | } |
| 606 | } |
| 607 | if len(seen) != molsOrder*molsOrder { |
| 608 | t.Fatalf("variant grid has %d unique values, want %d", len(seen), molsOrder*molsOrder) |
| 609 | } |
| 610 | } |
| 611 | |
| 612 | // TestMOLSHashToGF64InRange checks that hashToGF64 always returns [0, 63]. |
| 613 | func TestMOLSHashToGF64InRange(t *testing.T) { |
| 614 | inputs := []string{"", "a", "hello", "0x1234", "https://relay.example", "unicode-ish"} |
| 615 | for _, s := range inputs { |
| 616 | v := hashToGF64(s) |
| 617 | if v >= molsOrder { |
| 618 | t.Fatalf("hashToGF64(%q) = %d, want < %d", s, v, molsOrder) |
| 619 | } |
| 620 | } |
| 621 | } |
| 622 | |
| 623 | // TestMOLSRTTStatsEmpty checks that an empty slice returns zero values. |
| 624 | func TestMOLSRTTStatsEmpty(t *testing.T) { |
| 625 | mean, cv := molsRTTStats(nil) |
| 626 | if mean != 0 || cv != 0 { |
| 627 | t.Fatalf("molsRTTStats(nil) = (%v, %v), want (0, 0)", mean, cv) |
| 628 | } |
| 629 | } |
| 630 | |
| 631 | // TestMOLSSelectPriorityEWMAStabilityTransposition verifies that relays with |
| 632 | // high EWMA RTT are demoted relative to stable relays. |
| 633 | func TestMOLSSelectPriorityEWMAStabilityTransposition(t *testing.T) { |
| 634 | relayStable := confirmedRelayState(t, "https://relay-stable.example") |
| 635 | relayStable.EWMARTT = 100 * time.Millisecond |
| 636 | relayStable.DiscoveryRTT = 100 * time.Millisecond |
| 637 | |
| 638 | relayUnstable := confirmedRelayState(t, "https://relay-unstable.example") |
| 639 | relayUnstable.EWMARTT = 600 * time.Millisecond |
| 640 | relayUnstable.DiscoveryRTT = 600 * time.Millisecond |
| 641 | |
| 642 | states := []RelayState{relayStable, relayUnstable} |
| 643 | |
| 644 | // We force the same ingress so they are ranked together. |
| 645 | selected := SelectPriority(states, RouteState{LocalAddress: "test-ingress"}) |
| 646 | |
| 647 | if len(selected) != 2 { |
| 648 | t.Fatalf("len(selected) = %d, want 2", len(selected)) |
| 649 | } |
| 650 | |
| 651 | // Stable should be preferred. |
| 652 | if selected[0] != "https://relay-stable.example" { |
| 653 | t.Errorf("expected stable relay to be first, got %q", selected[0]) |
| 654 | } |
| 655 | } |
| 656 | |
| 657 | func BenchmarkMOLSRankRelayPool(b *testing.B) { |
| 658 | localAddr := "test-client-address" |
| 659 | relays := make([]RelayState, 100) |
| 660 | for i := 0; i < 100; i++ { |
| 661 | relays[i] = RelayState{ |
| 662 | Descriptor: types.RelayDescriptor{APIHTTPSAddr: "test"}, |
| 663 | DiscoveryRTT: 100 * time.Millisecond, |
| 664 | DiscoveryRTTAt: time.Now(), |
| 665 | Confirmed: true, |
| 666 | } |
| 667 | } |
| 668 | |
| 669 | b.ResetTimer() |
| 670 | for i := 0; i < b.N; i++ { |
| 671 | rankRelayPool(relays, localAddr) |
| 672 | } |
| 673 | } |
| 674 | |
| 675 | func BenchmarkMOLSSelectPriorityMassiveScale(b *testing.B) { |
| 676 | const numRelays = 256 |
| 677 | relayStates := make([]RelayState, numRelays) |
| 678 | for i := range relayStates { |
| 679 | relayStates[i] = RelayState{Descriptor: types.RelayDescriptor{APIHTTPSAddr: fmt.Sprintf("https://test-%d.example", i)}} |
| 680 | } |
| 681 | |
| 682 | b.ResetTimer() |
| 683 | for i := 0; i < b.N; i++ { |
| 684 | routeState := RouteState{LocalAddress: fmt.Sprintf("client-%d", i)} |
| 685 | SelectPriority(relayStates, routeState) |
| 686 | } |
| 687 | } |