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 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 * 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 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 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 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 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 * 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 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 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 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 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 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