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