1 /* $OpenBSD: rde_aspa.c,v 1.5 2023/08/16 08:26:35 claudio Exp $ */
2
3 /*
4 * Copyright (c) 2022 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
19 #include <stdint.h>
20 #include <stdlib.h>
21 #include <string.h>
22
23 #include "bgpd.h"
24 #include "rde.h"
25
26 enum cp_state {
27 UNKNOWN,
28 NOT_PROVIDER,
29 PROVIDER,
30 };
31
32 struct rde_aspa_set {
33 uint32_t as;
34 uint32_t num;
35 uint32_t *pas;
36 int next;
37 };
38
39 /*
40 * Power of 2 hash table
41 * The nodes are stored in the sets array.
42 * Additonal data for the rde_aspa_set are stored in data.
43 * For lookups only table and mask need to be accessed.
44 */
45 struct rde_aspa {
46 struct rde_aspa_set **table;
47 uint32_t mask;
48 uint32_t maxset;
49 struct rde_aspa_set *sets;
50 uint32_t *data;
51 size_t maxdata;
52 size_t curdata;
53 uint32_t curset;
54 time_t lastchange;
55 };
56
57 struct aspa_state {
58 int nhops;
59 int nup_p;
60 int nup_u;
61 int nup_np;
62 int ndown_p;
63 int ndown_u;
64 int ndown_np;
65 };
66
67 /*
68 * Use fmix32() the finalization mix of MurmurHash3 as a 32bit hash function.
69 */
70 static inline uint32_t
hash(uint32_t h)71 hash(uint32_t h)
72 {
73 h ^= h >> 16;
74 h *= 0x85ebca6b;
75 h ^= h >> 13;
76 h *= 0xc2b2ae35;
77 h ^= h >> 16;
78 return h;
79 }
80
81 /*
82 * Lookup an asnum in the aspa hash table.
83 */
84 static struct rde_aspa_set *
aspa_lookup(struct rde_aspa * ra,uint32_t asnum)85 aspa_lookup(struct rde_aspa *ra, uint32_t asnum)
86 {
87 struct rde_aspa_set *aspa;
88 uint32_t h;
89
90 h = hash(asnum) & ra->mask;
91 aspa = ra->table[h];
92 if (aspa == NULL)
93 return NULL;
94
95 while (aspa->as < asnum) {
96 if (!aspa->next)
97 break;
98 aspa++;
99 }
100
101 if (aspa->as == asnum)
102 return aspa;
103 return NULL;
104 }
105
106 /*
107 * Lookup if there is a customer - provider relation between cas and pas.
108 * Returns UNKNOWN if cas is not in the ra table or the aid is out of range.
109 * Returns PROVIDER if pas is registered for cas for the specified aid.
110 * Retruns NOT_PROVIDER otherwise.
111 * This function is called very frequently and needs to be fast.
112 */
113 static enum cp_state
aspa_cp_lookup(struct rde_aspa * ra,uint32_t cas,uint32_t pas)114 aspa_cp_lookup(struct rde_aspa *ra, uint32_t cas, uint32_t pas)
115 {
116 struct rde_aspa_set *aspa;
117 uint32_t i;
118
119 aspa = aspa_lookup(ra, cas);
120 if (aspa == NULL)
121 return UNKNOWN;
122
123 if (aspa->num < 16) {
124 for (i = 0; i < aspa->num; i++) {
125 if (aspa->pas[i] == pas)
126 break;
127 if (aspa->pas[i] > pas)
128 return NOT_PROVIDER;
129 }
130 if (i == aspa->num)
131 return NOT_PROVIDER;
132 } else {
133 uint32_t lim, x;
134 for (i = 0, lim = aspa->num; lim != 0; lim /= 2) {
135 x = lim / 2;
136 i += x;
137 if (aspa->pas[i] == pas) {
138 break;
139 } else if (aspa->pas[i] < pas) {
140 /* move right */
141 i++;
142 lim--;
143 } else {
144 /* move left */
145 i -= x;
146 }
147 }
148 if (lim == 0)
149 return NOT_PROVIDER;
150 }
151
152 return PROVIDER;
153 }
154
155 /*
156 * Calculate the various indexes of an aspath.
157 * The up-ramp starts at the source-as which is the right-most / last element
158 * in the aspath. The down-ramp starts at index 1.
159 * nhops: number of unique hops in the path
160 * nup_p: smallest index after which all aspath hops are provider valid
161 * nup_u: The biggest index of an unknown aspath hop.
162 * nup_np: The biggest index of a not-provider aspath hop.
163 * ndown_p: biggest index before which all aspath hops are provider valid
164 * ndown_u: The smallest index of an unknown aspath hop.
165 * ndown_np: The smallest index of a not-provider aspath hop.
166 * Returns 0 on success and -1 if a AS_SET is encountered.
167 */
168 static int
aspa_check_aspath(struct rde_aspa * ra,struct aspath * a,struct aspa_state * s)169 aspa_check_aspath(struct rde_aspa *ra, struct aspath *a, struct aspa_state *s)
170 {
171 uint8_t *seg;
172 uint32_t as, prevas = 0;
173 uint16_t len, seg_size;
174 uint8_t i, seg_type, seg_len;
175
176 /* the neighbor-as itself is by definition valid */
177 s->ndown_p = 1;
178
179 /*
180 * Walk aspath and validate if necessary both up- and down-ramp.
181 * If an AS_SET is found return -1 to indicate failure.
182 */
183 seg = aspath_dump(a);
184 len = aspath_length(a);
185 for (; len > 0; len -= seg_size, seg += seg_size) {
186 seg_type = seg[0];
187 seg_len = seg[1];
188 seg_size = 2 + sizeof(uint32_t) * seg_len;
189
190 if (seg_type != AS_SEQUENCE)
191 return -1;
192
193 for (i = 0; i < seg_len; i++) {
194 as = aspath_extract(seg, i);
195
196 if (as == prevas)
197 continue; /* skip prepends */
198
199 s->nhops++;
200 if (prevas == 0) {
201 prevas = as; /* skip left-most AS */
202 continue;
203 }
204
205 /*
206 * down-ramp check, remember the
207 * left-most unknown or not-provider
208 * node and the right-most provider node
209 * for which all nodes before are valid.
210 */
211 switch (aspa_cp_lookup(ra, prevas, as)) {
212 case UNKNOWN:
213 if (s->ndown_u == 0)
214 s->ndown_u = s->nhops;
215 break;
216 case PROVIDER:
217 if (s->ndown_p + 1 == s->nhops)
218 s->ndown_p = s->nhops;
219 break;
220 case NOT_PROVIDER:
221 if (s->ndown_np == 0)
222 s->ndown_np = s->nhops;
223 break;
224 }
225
226 /*
227 * up-ramp check, remember the right-most
228 * unknown and not-provider node and the
229 * left-most provider node for which all nodes
230 * after are valid.
231 * We recorde the nhops value of prevas,
232 * that's why the use of nhops - 1.
233 */
234 switch (aspa_cp_lookup(ra, as, prevas)) {
235 case UNKNOWN:
236 s->nup_p = 0;
237 s->nup_u = s->nhops - 1;
238 break;
239 case PROVIDER:
240 if (s->nup_p == 0)
241 s->nup_p = s->nhops - 1;
242 break;
243 case NOT_PROVIDER:
244 s->nup_p = 0;
245 s->nup_np = s->nhops - 1;
246 break;
247 }
248 prevas = as;
249 }
250 }
251
252 /* the source-as itself is by definition valid */
253 if (s->nup_p == 0)
254 s->nup_p = s->nhops;
255 return 0;
256 }
257
258 /*
259 * Set the two possible aspa outcomes for up-ramp only and up/down ramp
260 * in the vstate array.
261 */
262 static void
aspa_check_finalize(struct aspa_state * state,uint8_t * onlyup,uint8_t * downup)263 aspa_check_finalize(struct aspa_state *state, uint8_t *onlyup, uint8_t *downup)
264 {
265 /*
266 * Just an up-ramp:
267 * if a check returned NOT_PROVIDER then the result is invalid.
268 * if a check returned UNKNOWN then the result is unknown.
269 * else path is valid.
270 */
271 if (state->nup_np != 0)
272 *onlyup = ASPA_INVALID;
273 else if (state->nup_u != 0)
274 *onlyup = ASPA_UNKNOWN;
275 else
276 *onlyup = ASPA_VALID;
277
278 /*
279 * Both up-ramp and down-ramp:
280 * if nhops <= 2 the result is valid.
281 * if there is less than one AS hop between up-ramp and
282 * down-ramp then the result is valid.
283 * if not-provider nodes for both ramps exist and they
284 * do not overlap the path is invalid.
285 * else the path is unknown.
286 */
287 if (state->nhops <= 2)
288 *downup = ASPA_VALID;
289 else if (state->nup_p - state->ndown_p <= 1)
290 *downup = ASPA_VALID;
291 else if (state->nup_np != 0 && state->ndown_np != 0 &&
292 state->nup_np - state->ndown_np >= 0)
293 *downup = ASPA_INVALID;
294 else
295 *downup = ASPA_UNKNOWN;
296 }
297
298 /*
299 * Validate an aspath against the aspa_set *ra.
300 * Returns ASPA_VALID if the aspath is valid, ASPA_UNKNOWN if the
301 * aspath contains hops with unknown relation and ASPA_INVALID for
302 * empty aspaths, aspath with AS_SET and aspaths that fail validation.
303 */
304 void
aspa_validation(struct rde_aspa * ra,struct aspath * a,struct rde_aspa_state * vstate)305 aspa_validation(struct rde_aspa *ra, struct aspath *a,
306 struct rde_aspa_state *vstate)
307 {
308 struct aspa_state state = { 0 };
309
310 /* no aspa table, evrything is unknown */
311 if (ra == NULL) {
312 memset(vstate, ASPA_UNKNOWN, sizeof(*vstate));
313 return;
314 }
315
316 /* empty ASPATHs are always invalid */
317 if (aspath_length(a) == 0) {
318 memset(vstate, ASPA_INVALID, sizeof(*vstate));
319 return;
320 }
321
322 if (aspa_check_aspath(ra, a, &state) == -1) {
323 memset(vstate, ASPA_INVALID, sizeof(*vstate));
324 return;
325 }
326
327 aspa_check_finalize(&state, &vstate->onlyup, &vstate->downup);
328 }
329
330 /*
331 * Preallocate all data structures needed for the aspa table.
332 * There are entries number of rde_aspa_sets with data_size bytes of
333 * extra data (used to store SPAS and optional AFI bitmasks).
334 */
335 struct rde_aspa *
aspa_table_prep(uint32_t entries,size_t datasize)336 aspa_table_prep(uint32_t entries, size_t datasize)
337 {
338 struct rde_aspa *ra;
339 uint32_t hsize = 1024;
340
341 if (entries == 0)
342 return NULL;
343 if (entries > UINT32_MAX / 2)
344 fatalx("aspa_table_prep overflow");
345
346 while (hsize < entries)
347 hsize *= 2;
348
349 if ((ra = calloc(1, sizeof(*ra))) == NULL)
350 fatal("aspa table prep");
351
352 if ((ra->table = calloc(hsize, sizeof(ra->table[0]))) == NULL)
353 fatal("aspa table prep");
354
355 if ((ra->sets = calloc(entries, sizeof(ra->sets[0]))) == NULL)
356 fatal("aspa table prep");
357
358 if ((ra->data = malloc(datasize)) == NULL)
359 fatal("aspa table prep");
360
361 ra->mask = hsize - 1;
362 ra->maxset = entries;
363 ra->maxdata = datasize / sizeof(ra->data[0]);
364 ra->lastchange = getmonotime();
365
366 return ra;
367 }
368
369 /*
370 * Insert an aspa customer/provider set into the hash table.
371 * For hash conflict resulution insertion must happen in reverse order (biggest
372 * customer asnum first). On conflict objects in the sets array are moved
373 * around so that conflicting elements are direct neighbors.
374 * The per AID information is (if required) stored as 2bits per provider.
375 */
376 void
aspa_add_set(struct rde_aspa * ra,uint32_t cas,const uint32_t * pas,uint32_t pascnt)377 aspa_add_set(struct rde_aspa *ra, uint32_t cas, const uint32_t *pas,
378 uint32_t pascnt)
379 {
380 struct rde_aspa_set *aspa;
381 uint32_t h, i;
382
383 if (ra->curset >= ra->maxset)
384 fatalx("aspa set overflow");
385
386 h = hash(cas) & ra->mask;
387 aspa = ra->table[h];
388 if (aspa == NULL) {
389 aspa = &ra->sets[ra->curset++];
390 } else {
391 if (aspa->as <= cas)
392 fatalx("%s: bad order of adds", __func__);
393
394 /* insert before aspa */
395 memmove(aspa + 1, aspa,
396 (ra->sets + ra->curset - aspa) * sizeof(*aspa));
397 ra->curset++;
398 memset(aspa, 0, sizeof(*aspa));
399 aspa->next = 1;
400
401 /* adjust hashtable after shift of elements */
402 for (i = 0; i <= ra->mask; i++) {
403 if (ra->table[i] > aspa)
404 ra->table[i]++;
405 }
406 }
407 aspa->as = cas;
408 ra->table[h] = aspa;
409
410 if (ra->maxdata - ra->curdata < pascnt)
411 fatalx("aspa set data overflow");
412
413 aspa->num = pascnt;
414 aspa->pas = ra->data + ra->curdata;
415 for (i = 0; i < pascnt; i++)
416 ra->data[ra->curdata++] = pas[i];
417 }
418
419 void
aspa_table_free(struct rde_aspa * ra)420 aspa_table_free(struct rde_aspa *ra)
421 {
422 if (ra == NULL)
423 return;
424 free(ra->table);
425 free(ra->sets);
426 free(ra->data);
427 free(ra);
428 }
429
430 void
aspa_table_stats(const struct rde_aspa * ra,struct ctl_show_set * cset)431 aspa_table_stats(const struct rde_aspa *ra, struct ctl_show_set *cset)
432 {
433 if (ra == NULL)
434 return;
435 cset->lastchange = ra->lastchange;
436 cset->as_cnt = ra->maxset;
437 }
438
439 /*
440 * Return true if the two rde_aspa tables contain the same data.
441 */
442 int
aspa_table_equal(const struct rde_aspa * ra,const struct rde_aspa * rb)443 aspa_table_equal(const struct rde_aspa *ra, const struct rde_aspa *rb)
444 {
445 uint32_t i;
446
447 /* allow NULL pointers to be passed */
448 if (ra == NULL && rb == NULL)
449 return 1;
450 if (ra == NULL || rb == NULL)
451 return 0;
452
453 if (ra->maxset != rb->maxset ||
454 ra->maxdata != rb->maxdata)
455 return 0;
456 for (i = 0; i < ra->maxset; i++)
457 if (ra->sets[i].as != rb->sets[i].as)
458 return 0;
459 if (memcmp(ra->data, rb->data, ra->maxdata * sizeof(ra->data[0])) != 0)
460 return 0;
461
462 return 1;
463 }
464
465 void
aspa_table_unchanged(struct rde_aspa * ra,const struct rde_aspa * old)466 aspa_table_unchanged(struct rde_aspa *ra, const struct rde_aspa *old)
467 {
468 if (ra == NULL || old == NULL)
469 return;
470 ra->lastchange = old->lastchange;
471 }
472