1 /* $OpenBSD: rde_decide_test.c,v 1.6 2021/08/31 10:54:40 claudio Exp $ */ 2 3 /* 4 * Copyright (c) 2020 Claudio Jeker <claudio@openbsd.org> 5 * 6 * Permission to use, copy, modify, and distribute this software for any 7 * purpose with or without fee is hereby granted, provided that the above 8 * copyright notice and this permission notice appear in all copies. 9 * 10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 17 */ 18 #include <sys/types.h> 19 #include <sys/queue.h> 20 21 #include <err.h> 22 #include <stdio.h> 23 #include <stdlib.h> 24 #include <string.h> 25 26 #include "rde.h" 27 28 struct rde_memstats rdemem; 29 30 struct rib dummy_rib = { 31 .name = "regress RIB", 32 .flags = 0, 33 }; 34 35 struct rib_entry dummy_re; 36 37 struct nexthop nh_reach = { 38 .state = NEXTHOP_REACH 39 }; 40 struct nexthop nh_unreach = { 41 .state = NEXTHOP_UNREACH 42 }; 43 44 struct rde_peer peer1 = { 45 .conf.ebgp = 1, 46 .remote_bgpid = 1, 47 .remote_addr = { .aid = AID_INET, .v4.s_addr = 0xef000001 }, 48 }; 49 struct rde_peer peer2 = { 50 .conf.ebgp = 1, 51 .remote_bgpid = 2, 52 .remote_addr = { .aid = AID_INET, .v4.s_addr = 0xef000002 }, 53 }; 54 struct rde_peer peer3 = { 55 .conf.ebgp = 1, 56 .remote_bgpid = 3, 57 .remote_addr = { .aid = AID_INET, .v4.s_addr = 0xef000003 }, 58 }; 59 struct rde_peer peer1_a4 = { 60 .conf.ebgp = 1, 61 .remote_bgpid = 1, 62 .remote_addr = { .aid = AID_INET, .v4.s_addr = 0xef000004 }, 63 }; 64 struct rde_peer peer1_i = { 65 .conf.ebgp = 0, 66 .remote_bgpid = 3, 67 .remote_addr = { .aid = AID_INET, .v4.s_addr = 0xef000003 }, 68 }; 69 70 union a { 71 struct aspath a; 72 struct { 73 LIST_ENTRY(aspath) entry; 74 u_int32_t source_as; 75 int refcnt; 76 uint16_t len; 77 uint16_t ascnt; 78 uint8_t d[6]; 79 } x; 80 } asdata[] = { 81 { .x = { .len = 6, .ascnt = 2, .d = { 2, 1, 0, 0, 0, 1 } } }, 82 { .x = { .len = 6, .ascnt = 3, .d = { 2, 1, 0, 0, 0, 1 } } }, 83 { .x = { .len = 6, .ascnt = 2, .d = { 2, 1, 0, 0, 0, 2 } } }, 84 { .x = { .len = 6, .ascnt = 3, .d = { 2, 1, 0, 0, 0, 2 } } }, 85 }; 86 87 struct rde_aspath asp[] = { 88 { .aspath = &asdata[0].a, .med = 100, .lpref = 100, .origin = ORIGIN_IGP, .weight = 1000 }, 89 /* 1 & 2: errors and loops */ 90 { .aspath = &asdata[0].a, .med = 100, .lpref = 100, .origin = ORIGIN_IGP, .flags=F_ATTR_PARSE_ERR }, 91 { .aspath = &asdata[0].a, .med = 100, .lpref = 100, .origin = ORIGIN_IGP, .flags=F_ATTR_LOOP }, 92 /* 3: local preference */ 93 { .aspath = &asdata[0].a, .med = 100, .lpref = 50, .origin = ORIGIN_IGP }, 94 /* 4: aspath count */ 95 { .aspath = &asdata[1].a, .med = 100, .lpref = 100, .origin = ORIGIN_IGP }, 96 /* 5 & 6: origin */ 97 { .aspath = &asdata[0].a, .med = 100, .lpref = 100, .origin = ORIGIN_EGP }, 98 { .aspath = &asdata[0].a, .med = 100, .lpref = 100, .origin = ORIGIN_INCOMPLETE }, 99 /* 7: MED */ 100 { .aspath = &asdata[0].a, .med = 200, .lpref = 100, .origin = ORIGIN_IGP }, 101 /* 8: Weight */ 102 { .aspath = &asdata[0].a, .med = 100, .lpref = 100, .origin = ORIGIN_IGP, .weight = 100 }, 103 }; 104 105 #define T1 1610980000 106 #define T2 1610983600 107 108 struct test { 109 char *what; 110 struct prefix p; 111 } test_pfx[] = { 112 { .what = "test prefix", 113 .p = { .entry.list.re = &dummy_re, .aspath = &asp[0], .peer = &peer1, .nexthop = &nh_reach, .lastchange = T1, } }, 114 /* pathes with errors are not eligible */ 115 { .what = "prefix with error", 116 .p = { .entry.list.re = &dummy_re, .aspath = &asp[1], .peer = &peer1, .nexthop = &nh_reach, .lastchange = T1, } }, 117 /* only loop free pathes are eligible */ 118 { .what = "prefix with loop", 119 .p = { .entry.list.re = &dummy_re, .aspath = &asp[2], .peer = &peer1, .nexthop = &nh_reach, .lastchange = T1, } }, 120 /* 1. check if prefix is eligible a.k.a reachable */ 121 { .what = "prefix with unreachable nexthop", 122 .p = { .entry.list.re = &dummy_re, .aspath = &asp[0], .peer = &peer1, .nexthop = &nh_unreach, .lastchange = T1, } }, 123 /* 2. local preference of prefix, bigger is better */ 124 { .what = "local preference check", 125 .p = { .entry.list.re = &dummy_re, .aspath = &asp[3], .peer = &peer1, .nexthop = &nh_reach, .lastchange = T1, } }, 126 /* 3. aspath count, the shorter the better */ 127 { .what = "aspath count check", 128 .p = { .entry.list.re = &dummy_re, .aspath = &asp[4], .peer = &peer1, .nexthop = &nh_reach, .lastchange = T1, } }, 129 /* 4. origin, the lower the better */ 130 { .what = "origin EGP", 131 .p = { .entry.list.re = &dummy_re, .aspath = &asp[5], .peer = &peer1, .nexthop = &nh_reach, .lastchange = T1, } }, 132 { .what = "origin INCOMPLETE", 133 .p = { .entry.list.re = &dummy_re, .aspath = &asp[6], .peer = &peer1, .nexthop = &nh_reach, .lastchange = T1, } }, 134 /* 5. MED decision */ 135 { .what = "MED", 136 .p = { .entry.list.re = &dummy_re, .aspath = &asp[7], .peer = &peer1, .nexthop = &nh_reach, .lastchange = T1, } }, 137 /* 6. EBGP is cooler than IBGP */ 138 { .what = "EBGP vs IBGP", 139 .p = { .entry.list.re = &dummy_re, .aspath = &asp[0], .peer = &peer1_i, .nexthop = &nh_reach, .lastchange = T1, } }, 140 /* 7. weight */ 141 { .what = "local weight", 142 .p = { .entry.list.re = &dummy_re, .aspath = &asp[8], .peer = &peer1, .nexthop = &nh_reach, .lastchange = T1, } }, 143 /* 8. nexthop cost not implemented */ 144 /* 9. route age */ 145 { .what = "route age", 146 .p = { .entry.list.re = &dummy_re, .aspath = &asp[0], .peer = &peer1, .nexthop = &nh_reach, .lastchange = T2, } }, 147 /* 10. BGP Id or ORIGINATOR_ID if present */ 148 { .what = "BGP ID", 149 .p = { .entry.list.re = &dummy_re, .aspath = &asp[0], .peer = &peer2, .nexthop = &nh_reach, .lastchange = T1, } }, 150 /* 11. CLUSTER_LIST length, TODO */ 151 /* 12. lowest peer address wins */ 152 { .what = "remote peer address", 153 .p = { .entry.list.re = &dummy_re, .aspath = &asp[0], .peer = &peer1_a4, .nexthop = &nh_reach, .lastchange = T1, } }, 154 }; 155 156 struct rde_aspath med_asp[] = { 157 { .aspath = &asdata[0].a, .med = 100, .lpref = 100, .origin = ORIGIN_EGP }, 158 { .aspath = &asdata[0].a, .med = 150, .lpref = 100, .origin = ORIGIN_EGP }, 159 { .aspath = &asdata[2].a, .med = 75, .lpref = 100, .origin = ORIGIN_EGP }, 160 { .aspath = &asdata[2].a, .med = 125, .lpref = 100, .origin = ORIGIN_EGP }, 161 { .aspath = &asdata[1].a, .med = 110, .lpref = 100, .origin = ORIGIN_EGP }, 162 { .aspath = &asdata[1].a, .med = 90, .lpref = 100, .origin = ORIGIN_EGP }, 163 }; 164 165 /* 166 * Test 'rde med compare strict' vs 'rde med compare always' 167 * med_pfx1 > med_pfx2 in both cases 168 * med_pfx1 > med_pfx3 for strict but med_pfx1 < med_pfx3 for always 169 * med_pfx1 < med_pfx4 for strict but med_pfx1 > med_pfx4 for always 170 * For med_pfx3 and med_pfx4 the strict case differs in the bgp-id. 171 */ 172 struct prefix med_pfx1 = 173 { .entry.list.re = &dummy_re, .aspath = &med_asp[0], .peer = &peer2, .nexthop = &nh_reach, .lastchange = T1, }; 174 struct prefix med_pfx2 = 175 { .entry.list.re = &dummy_re, .aspath = &med_asp[1], .peer = &peer1, .nexthop = &nh_reach, .lastchange = T1, }; 176 struct prefix med_pfx3 = 177 { .entry.list.re = &dummy_re, .aspath = &med_asp[2], .peer = &peer3, .nexthop = &nh_reach, .lastchange = T1, }; 178 struct prefix med_pfx4 = 179 { .entry.list.re = &dummy_re, .aspath = &med_asp[3], .peer = &peer1_a4, .nexthop = &nh_reach, .lastchange = T1, }; 180 /* the next two prefixes have a longer aspath than med_pfx1 & 2 */ 181 struct prefix med_pfx5 = 182 { .entry.list.re = &dummy_re, .aspath = &med_asp[5], .peer = &peer3, .nexthop = &nh_reach, .lastchange = T1, }; 183 struct prefix med_pfx6 = 184 { .entry.list.re = &dummy_re, .aspath = &med_asp[4], .peer = &peer1, .nexthop = &nh_reach, .lastchange = T1, }; 185 186 /* 187 * Define two prefixes where pfx1 > pfx2 if 'rde route-age evaluate' 188 * but pfx1 < pfx2 if 'rde route-age ignore' 189 */ 190 struct prefix age_pfx1 = 191 { .entry.list.re = &dummy_re, .aspath = &asp[0], .peer = &peer2, .nexthop = &nh_reach, .lastchange = T1, }; 192 struct prefix age_pfx2 = 193 { .entry.list.re = &dummy_re, .aspath = &asp[0], .peer = &peer1, .nexthop = &nh_reach, .lastchange = T2, }; 194 195 int prefix_cmp(struct prefix *, struct prefix *, int *); 196 197 int decision_flags = BGPD_FLAG_DECISION_ROUTEAGE; 198 199 int failed; 200 201 static int 202 test(struct prefix *a, struct prefix *b, int v) 203 { 204 int rv = 0, dummy; 205 if (prefix_cmp(a, b, &dummy) < 0) { 206 if (v) printf(" FAILED\n"); 207 failed = rv = 1; 208 } else if (prefix_cmp(b, a, &dummy) > 0) { 209 if (v) printf(" reverse cmp FAILED\n"); 210 failed = rv = 1; 211 } else if (v) 212 printf(" OK\n"); 213 214 return rv; 215 } 216 217 static size_t 218 which(struct prefix **orig, struct prefix *p) 219 { 220 size_t i; 221 222 for (i = 0; orig[i] != NULL; i++) 223 if (orig[i] == p) 224 return i; 225 return 9999; 226 } 227 228 /* 229 * Evaluate a set of prefixes in all possible ways. 230 * The input in orig should be in the expected order. 231 */ 232 static int 233 test_evaluate(struct prefix **orig, struct prefix **in, size_t nin) 234 { 235 struct prefix *next[nin - 1]; 236 size_t i, j, n; 237 int r = 0; 238 239 if (nin == 0) { 240 struct prefix *xp; 241 242 j = 0; 243 LIST_FOREACH(xp, &dummy_re.prefix_h, entry.list.rib) 244 if (which(orig, xp) != j++) 245 r = 1; 246 if (r != 0) { 247 printf("bad order"); 248 LIST_FOREACH(xp, &dummy_re.prefix_h, entry.list.rib) 249 printf(" %zu", which(orig, xp)); 250 printf(" FAILED\n"); 251 } 252 } 253 for (i = 0; i < nin; i++) { 254 /* add prefix to dummy_re */ 255 prefix_evaluate(&dummy_re, in[i], NULL); 256 257 for (n = j = 0; j < nin; j++) { 258 if (j == i) 259 continue; 260 next[n++] = in[j]; 261 } 262 r |= test_evaluate(orig, next, n); 263 264 /* remove prefix from dummy_re */ 265 prefix_evaluate(&dummy_re, NULL, in[i]); 266 } 267 268 return r; 269 } 270 271 int 272 main(int argc, char **argv) 273 { 274 struct prefix *med_strict[7] = { 275 &med_pfx1, &med_pfx2, &med_pfx3, &med_pfx4, 276 &med_pfx5, &med_pfx6, NULL 277 }; 278 struct prefix *med_always[7] = { 279 &med_pfx3, &med_pfx1, &med_pfx4, &med_pfx2, 280 &med_pfx5, &med_pfx6, NULL 281 }; 282 size_t i, ntest; 283 284 ntest = sizeof(test_pfx) / sizeof(*test_pfx); 285 for (i = 1; i < ntest; i++) { 286 printf("test %zu: %s", i, test_pfx[i].what); 287 test(&test_pfx[0].p, &test_pfx[i].p, 1); 288 } 289 290 printf("test NULL element"); 291 test(&test_pfx[0].p, NULL, 1); 292 293 printf("test rde med compare strict 1"); 294 test(&med_pfx1, &med_pfx2, 1); 295 printf("test rde med compare strict 2"); 296 test(&med_pfx1, &med_pfx3, 1); 297 printf("test rde med compare strict 3"); 298 test(&med_pfx4, &med_pfx1, 1); 299 300 decision_flags |= BGPD_FLAG_DECISION_MED_ALWAYS; 301 printf("test rde med compare always 1"); 302 test(&med_pfx1, &med_pfx2, 1); 303 printf("test rde med compare always 2"); 304 test(&med_pfx3, &med_pfx1, 1); 305 printf("test rde med compare always 3"); 306 test(&med_pfx1, &med_pfx4, 1); 307 308 printf("test rde route-age evaluate"); 309 test(&age_pfx1, &age_pfx2, 1); 310 decision_flags &= ~BGPD_FLAG_DECISION_ROUTEAGE; 311 printf("test rde route-age ignore"); 312 test(&age_pfx2, &age_pfx1, 1); 313 314 decision_flags = 0; 315 printf("evaluate with rde med compare strict\n"); 316 if (test_evaluate(med_strict, med_strict, 6) == 0) 317 printf("all OK\n"); 318 319 decision_flags = BGPD_FLAG_DECISION_MED_ALWAYS; 320 printf("evaluate with rde med compare always\n"); 321 if (test_evaluate(med_always, med_always, 6) == 0) 322 printf("all OK\n"); 323 324 if (failed) 325 printf("some tests FAILED\n"); 326 else 327 printf("all tests OK\n"); 328 exit(failed); 329 } 330 331 /* this function is called by prefix_cmp to alter the decision process */ 332 int 333 rde_decisionflags(void) 334 { 335 return decision_flags; 336 } 337 338 /* 339 * Helper functions need to link and run the tests. 340 */ 341 u_int32_t 342 rde_local_as(void) 343 { 344 return 65000; 345 } 346 347 int 348 rde_evaluate_all(void) 349 { 350 return 0; 351 } 352 353 int 354 as_set_match(const struct as_set *aset, u_int32_t asnum) 355 { 356 errx(1, __func__); 357 } 358 359 struct rib * 360 rib_byid(u_int16_t id) 361 { 362 return &dummy_rib; 363 } 364 365 void 366 rde_generate_updates(struct rib *rib, struct prefix *new, struct prefix *old, 367 int eval_all) 368 { 369 /* maybe we want to do something here */ 370 } 371 372 __dead void 373 fatalx(const char *emsg, ...) 374 { 375 va_list ap; 376 va_start(ap, emsg); 377 verrx(2, emsg, ap); 378 } 379 380 __dead void 381 fatal(const char *emsg, ...) 382 { 383 va_list ap; 384 va_start(ap, emsg); 385 verr(2, emsg, ap); 386 } 387 388 void 389 log_warnx(const char *emsg, ...) 390 { 391 va_list ap; 392 va_start(ap, emsg); 393 vwarnx(emsg, ap); 394 va_end(ap); 395 } 396 397