1 /* $OpenBSD: rde_srt.c,v 1.22 2009/04/16 20:11:12 michele Exp $ */ 2 3 /* 4 * Copyright (c) 2009 Michele Marchetto <michele@openbsd.org> 5 * Copyright (c) 2005, 2006 Esben Norby <norby@openbsd.org> 6 * 7 * Permission to use, copy, modify, and distribute this software for any 8 * purpose with or without fee is hereby granted, provided that the above 9 * copyright notice and this permission notice appear in all copies. 10 * 11 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 12 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 13 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 14 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 15 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 16 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 17 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 18 */ 19 20 #include <sys/types.h> 21 #include <sys/socket.h> 22 #include <sys/tree.h> 23 #include <netinet/in.h> 24 #include <arpa/inet.h> 25 #include <err.h> 26 #include <stdlib.h> 27 #include <string.h> 28 29 #include "igmp.h" 30 #include "dvmrp.h" 31 #include "dvmrpd.h" 32 #include "log.h" 33 #include "dvmrpe.h" 34 #include "rde.h" 35 36 /* source route tree */ 37 38 void rt_invalidate(void); 39 void rt_expire_timer(int, short, void *); 40 int rt_start_expire_timer(struct rt_node *); 41 void rt_holddown_timer(int, short, void *); 42 void rt_start_holddown_timer(struct rt_node *); 43 44 void srt_set_upstream(struct rt_node *, u_int32_t); 45 46 /* Designated forwarder */ 47 void srt_set_forwarder_self(struct rt_node *, struct iface *); 48 void srt_update_ds_forwarders(struct rt_node *, struct iface *, 49 u_int32_t); 50 void srt_current_forwarder(struct rt_node *, struct iface *, 51 u_int32_t, u_int32_t); 52 53 /* Downstream neighbors */ 54 void srt_add_ds(struct rt_node *, u_int32_t, u_int32_t); 55 struct ds_nbr *srt_find_ds(struct rt_node *, u_int32_t); 56 void srt_delete_ds(struct rt_node *, struct ds_nbr *, 57 struct iface *); 58 59 /* Flash updates */ 60 void flash_update(struct rt_node *); 61 void flash_update_ds(struct rt_node *); 62 63 RB_HEAD(rt_tree, rt_node) rt; 64 RB_PROTOTYPE(rt_tree, rt_node, entry, rt_compare) 65 RB_GENERATE(rt_tree, rt_node, entry, rt_compare) 66 67 extern struct dvmrpd_conf *rdeconf; 68 69 /* timers */ 70 void 71 rt_expire_timer(int fd, short event, void *arg) 72 { 73 struct rt_node *rn = arg; 74 struct timeval tv; 75 76 log_debug("rt_expire_timer: route %s/%d", inet_ntoa(rn->prefix), 77 rn->prefixlen); 78 79 timerclear(&tv); 80 rn->old_cost = rn->cost; 81 rn->cost = INFINITY_METRIC; 82 tv.tv_sec = ROUTE_HOLD_DOWN; 83 84 if (evtimer_add(&rn->holddown_timer, &tv) == -1) 85 fatal("rt_expire_timer"); 86 } 87 88 int 89 rt_start_expire_timer(struct rt_node *rn) 90 { 91 struct timeval tv; 92 93 rn->old_cost = 0; 94 95 if (evtimer_pending(&rn->holddown_timer, NULL)) 96 if (evtimer_del(&rn->holddown_timer) == -1) 97 fatal("rt_start_expire_timer"); 98 99 timerclear(&tv); 100 tv.tv_sec = ROUTE_EXPIRATION_TIME; 101 return (evtimer_add(&rn->expiration_timer, &tv)); 102 } 103 104 void 105 rt_holddown_timer(int fd, short event, void *arg) 106 { 107 struct rt_node *rn = arg; 108 109 log_debug("rt_holddown_timer: route %s/%d", inet_ntoa(rn->prefix), 110 rn->prefixlen); 111 112 rt_remove(rn); 113 } 114 115 void 116 rt_start_holddown_timer(struct rt_node *rn) 117 { 118 struct timeval tv; 119 120 timerclear(&tv); 121 tv.tv_sec = ROUTE_HOLD_DOWN; 122 if (evtimer_pending(&rn->expiration_timer, NULL)) { 123 if (evtimer_del(&rn->expiration_timer) == -1) 124 fatal("rt_start_holddown_timer"); 125 evtimer_add(&rn->holddown_timer, &tv); 126 } 127 } 128 129 /* route table */ 130 void 131 rt_init(void) 132 { 133 RB_INIT(&rt); 134 } 135 136 int 137 rt_compare(struct rt_node *a, struct rt_node *b) 138 { 139 /* 140 * sort route entries based on prefixlen since generating route 141 * reports rely on that. 142 */ 143 if (a->prefixlen < b->prefixlen) 144 return (-1); 145 if (a->prefixlen > b->prefixlen) 146 return (1); 147 if (ntohl(a->prefix.s_addr) < ntohl(b->prefix.s_addr)) 148 return (-1); 149 if (ntohl(a->prefix.s_addr) > ntohl(b->prefix.s_addr)) 150 return (1); 151 return (0); 152 } 153 154 struct rt_node * 155 rt_find(in_addr_t prefix, u_int8_t prefixlen) 156 { 157 struct rt_node s; 158 159 s.prefix.s_addr = prefix; 160 s.prefixlen = prefixlen; 161 162 return (RB_FIND(rt_tree, &rt, &s)); 163 } 164 165 struct rt_node * 166 rr_new_rt(struct route_report *rr, u_int32_t adj_metric, int connected) 167 { 168 struct timespec now; 169 struct rt_node *rn; 170 int i; 171 172 clock_gettime(CLOCK_MONOTONIC, &now); 173 174 if ((rn = calloc(1, sizeof(*rn))) == NULL) 175 fatal("rr_new_rt"); 176 177 rn->prefix.s_addr = rr->net.s_addr; 178 rn->prefixlen = mask2prefixlen(rr->mask.s_addr); 179 rn->nexthop.s_addr = rr->nexthop.s_addr; 180 rn->cost = adj_metric; 181 rn->ifindex = rr->ifindex; 182 183 for (i = 0; i < MAXVIFS; i++) { 184 rn->ttls[i] = 0; 185 rn->ds_cnt[i] = 0; 186 rn->adv_rtr[i].addr.s_addr = 0; 187 rn->adv_rtr[i].metric = 0; 188 } 189 190 LIST_INIT(&rn->ds_list); 191 192 rn->flags = F_DVMRPD_INSERTED; 193 rn->connected = connected; 194 rn->uptime = now.tv_sec; 195 196 evtimer_set(&rn->expiration_timer, rt_expire_timer, rn); 197 evtimer_set(&rn->holddown_timer, rt_holddown_timer, rn); 198 199 return (rn); 200 } 201 202 int 203 rt_insert(struct rt_node *r) 204 { 205 log_debug("rt_insert: inserting route %s/%d", inet_ntoa(r->prefix), 206 r->prefixlen); 207 208 if (RB_INSERT(rt_tree, &rt, r) != NULL) { 209 log_warnx("rt_insert failed for %s/%u", inet_ntoa(r->prefix), 210 r->prefixlen); 211 free(r); 212 return (-1); 213 } 214 215 return (0); 216 } 217 218 int 219 rt_remove(struct rt_node *r) 220 { 221 struct ds_nbr *ds_nbr; 222 223 if (RB_REMOVE(rt_tree, &rt, r) == NULL) { 224 log_warnx("rt_remove failed for %s/%u", 225 inet_ntoa(r->prefix), r->prefixlen); 226 return (-1); 227 } 228 229 LIST_FOREACH(ds_nbr, &r->ds_list, entry) { 230 LIST_REMOVE(ds_nbr, entry); 231 free(ds_nbr); 232 } 233 234 free(r); 235 return (0); 236 } 237 238 void 239 rt_invalidate(void) 240 { 241 struct rt_node *r, *nr; 242 243 for (r = RB_MIN(rt_tree, &rt); r != NULL; r = nr) { 244 nr = RB_NEXT(rt_tree, &rt, r); 245 if (r->invalid) 246 rt_remove(r); 247 else 248 r->invalid = 1; 249 } 250 } 251 252 void 253 rt_clear(void) 254 { 255 struct rt_node *r; 256 257 while ((r = RB_MIN(rt_tree, &rt)) != NULL) 258 rt_remove(r); 259 } 260 261 void 262 rt_snap(u_int32_t peerid) 263 { 264 struct rt_node *r; 265 struct route_report rr; 266 267 RB_FOREACH(r, rt_tree, &rt) { 268 if (r->invalid) 269 continue; 270 271 rr.net = r->prefix; 272 rr.mask.s_addr = ntohl(prefixlen2mask(r->prefixlen)); 273 rr.metric = r->cost; 274 rr.ifindex = r->ifindex; 275 rde_imsg_compose_dvmrpe(IMSG_FULL_ROUTE_REPORT, peerid, 0, &rr, 276 sizeof(rr)); 277 } 278 } 279 280 void 281 rt_dump(pid_t pid) 282 { 283 static struct ctl_rt rtctl; 284 struct timespec now; 285 struct timeval tv, now2, res; 286 struct rt_node *r; 287 288 clock_gettime(CLOCK_MONOTONIC, &now); 289 290 RB_FOREACH(r, rt_tree, &rt) { 291 if (r->invalid) 292 continue; 293 294 rtctl.prefix.s_addr = r->prefix.s_addr; 295 rtctl.nexthop.s_addr = r->nexthop.s_addr; 296 rtctl.cost = r->cost; 297 rtctl.flags = r->flags; 298 rtctl.prefixlen = r->prefixlen; 299 rtctl.uptime = now.tv_sec - r->uptime; 300 301 gettimeofday(&now2, NULL); 302 if (evtimer_pending(&r->expiration_timer, &tv)) { 303 timersub(&tv, &now2, &res); 304 rtctl.expire = res.tv_sec; 305 } else 306 rtctl.expire = -1; 307 308 rde_imsg_compose_dvmrpe(IMSG_CTL_SHOW_RIB, 0, pid, &rtctl, 309 sizeof(rtctl)); 310 } 311 } 312 313 void 314 rt_update(struct rt_node *rn) 315 { 316 if (!rn->connected) 317 rt_start_expire_timer(rn); 318 } 319 320 struct rt_node * 321 rt_match_origin(in_addr_t src) 322 { 323 struct rt_node *r; 324 325 RB_FOREACH(r, rt_tree, &rt) { 326 if (r->prefix.s_addr == (src & 327 htonl(prefixlen2mask(r->prefixlen)))) 328 return (r); 329 } 330 331 return (NULL); 332 } 333 334 int 335 srt_check_route(struct route_report *rr, int connected) 336 { 337 struct rt_node *rn; 338 struct iface *iface; 339 struct ds_nbr *ds_nbr; 340 u_int32_t adj_metric; 341 u_int32_t nbr_ip, nbr_report, ifindex; 342 343 if ((iface = if_find_index(rr->ifindex)) == NULL) 344 return (-1); 345 346 ifindex = iface->ifindex; 347 348 /* Interpret special case 0.0.0.0/8 as 0.0.0.0/0 */ 349 if (rr->net.s_addr == 0) 350 rr->mask.s_addr = 0; 351 352 if (connected) 353 adj_metric = rr->metric; 354 else 355 adj_metric = rr->metric + iface->metric; 356 357 if (adj_metric > INFINITY_METRIC) 358 adj_metric = INFINITY_METRIC; 359 360 /* If the route is new and the Adjusted Metric is less than infinity, 361 the route should be added. */ 362 rn = rt_find(rr->net.s_addr, mask2prefixlen(rr->mask.s_addr)); 363 if (rn == NULL) { 364 if (adj_metric < INFINITY_METRIC) { 365 rn = rr_new_rt(rr, adj_metric, connected); 366 rt_insert(rn); 367 } 368 return (0); 369 } 370 371 /* If the route is connected accept only downstream neighbors reports */ 372 if (rn->connected && rr->metric <= INFINITY_METRIC) 373 return (0); 374 375 nbr_ip = rn->nexthop.s_addr; 376 nbr_report = rr->nexthop.s_addr; 377 378 if (rr->metric < INFINITY_METRIC) { 379 /* If it is our current nexthop it cannot be a 380 * downstream router */ 381 if (nbr_ip != nbr_report) 382 if ((ds_nbr = srt_find_ds(rn, nbr_report))) 383 srt_delete_ds(rn, ds_nbr, iface); 384 385 if (adj_metric > rn->cost) { 386 if (nbr_ip == nbr_report) { 387 rn->cost = adj_metric; 388 flash_update_ds(rn); 389 } 390 } else if (adj_metric < rn->cost) { 391 rn->cost = adj_metric; 392 if (nbr_ip != nbr_report) { 393 rn->nexthop.s_addr = nbr_report; 394 srt_set_upstream(rn, ifindex); 395 flash_update(rn); 396 } 397 /* We have a new best route to source, update the 398 * designated forwarders on downstream interfaces to 399 * reflect the new metric */ 400 srt_update_ds_forwarders(rn, iface, nbr_report); 401 } else { 402 if (nbr_report < nbr_ip) { 403 rn->nexthop.s_addr = nbr_report; 404 srt_set_upstream(rn, ifindex); 405 flash_update(rn); 406 } else if (nbr_report == nbr_ip && 407 adj_metric == rn->old_cost) 408 rt_update(rn); 409 flash_update_ds(rn); 410 } 411 /* Update forwarder of current interface if necessary and 412 * refresh the route */ 413 srt_current_forwarder(rn, iface, rr->metric, nbr_report); 414 rt_update(rn); 415 } else if (rr->metric == INFINITY_METRIC) { 416 if (nbr_report == rn->adv_rtr[ifindex].addr.s_addr) 417 srt_set_forwarder_self(rn, iface); 418 infinity: 419 if (nbr_ip == nbr_report) { 420 if (rn->cost < INFINITY_METRIC) 421 rt_start_holddown_timer(rn); 422 } else 423 if ((ds_nbr = srt_find_ds(rn, nbr_report))) 424 srt_delete_ds(rn, ds_nbr, iface); 425 } else if (INFINITY_METRIC < rr->metric && 426 rr->metric < 2 * INFINITY_METRIC) { 427 /* Neighbor is reporting his dependency for this source */ 428 if (nbr_report == rn->adv_rtr[ifindex].addr.s_addr) 429 srt_set_forwarder_self(rn, iface); 430 431 if (rn->ifindex == ifindex) 432 goto infinity; 433 else 434 if (srt_find_ds(rn, nbr_report) == NULL) 435 srt_add_ds(rn, nbr_report, ifindex); 436 } 437 438 return (0); 439 } 440 441 void 442 srt_current_forwarder(struct rt_node *rn, struct iface *iface, 443 u_int32_t metric, u_int32_t nbr_report) 444 { 445 struct adv_rtr *adv = &rn->adv_rtr[iface->ifindex]; 446 447 if (nbr_report == adv->addr.s_addr) { 448 if (metric > rn->cost || (metric == rn->cost && 449 iface->addr.s_addr < nbr_report)) 450 srt_set_forwarder_self(rn, iface); 451 452 } else { 453 if (metric < adv->metric || 454 (metric == adv->metric && nbr_report < adv->addr.s_addr)) 455 if (adv->addr.s_addr == iface->addr.s_addr) 456 rn->ttls[iface->ifindex] = 0; 457 458 adv->addr.s_addr = nbr_report; 459 adv->metric = metric; 460 461 mfc_update_source(rn); 462 } 463 464 } 465 466 void 467 srt_update_ds_forwarders(struct rt_node *rn, struct iface *iface, 468 u_int32_t nbr_report) 469 { 470 struct iface *ifa; 471 int i; 472 473 for (i = 0; i < MAXVIFS; i++) { 474 if (rn->adv_rtr[i].addr.s_addr && 475 (rn->cost < rn->adv_rtr[i].metric || 476 (rn->cost == rn->adv_rtr[i].metric && 477 iface->addr.s_addr < nbr_report))) { 478 ifa = if_find_index(i); 479 srt_set_forwarder_self(rn, ifa); 480 } 481 } 482 } 483 484 void 485 srt_set_forwarder_self(struct rt_node *rn, struct iface *iface) 486 { 487 rn->adv_rtr[iface->ifindex].addr.s_addr = iface->addr.s_addr; 488 rn->adv_rtr[iface->ifindex].metric = rn->cost; 489 rn->ttls[iface->ifindex] = 1; 490 491 mfc_update_source(rn); 492 } 493 494 void 495 srt_set_upstream(struct rt_node *rn, u_int32_t ifindex) 496 { 497 if (rn->ifindex != ifindex) { 498 rn->ttls[rn->ifindex] = 1; 499 rn->ifindex = ifindex; 500 } 501 502 mfc_update_source(rn); 503 } 504 505 void 506 srt_add_ds(struct rt_node *rn, u_int32_t nbr_report, u_int32_t ifindex) 507 { 508 struct ds_nbr *ds_nbr; 509 510 log_debug("srt_add_ds: adding downstream router for source %s/%d", 511 inet_ntoa(rn->prefix), rn->prefixlen); 512 513 if ((ds_nbr = malloc(sizeof(struct ds_nbr))) == NULL) 514 fatal("srt_add_ds"); 515 516 ds_nbr->addr.s_addr = nbr_report; 517 518 LIST_INSERT_HEAD(&rn->ds_list, ds_nbr, entry); 519 rn->ds_cnt[ifindex]++; 520 rn->ttls[ifindex] = 1; 521 522 mfc_update_source(rn); 523 } 524 525 struct ds_nbr * 526 srt_find_ds(struct rt_node *rn, u_int32_t nbr_report) 527 { 528 struct ds_nbr *ds_nbr; 529 530 LIST_FOREACH(ds_nbr, &rn->ds_list, entry) 531 if (ds_nbr->addr.s_addr == nbr_report) 532 return (ds_nbr); 533 534 return (NULL); 535 } 536 537 void 538 srt_delete_ds(struct rt_node *rn, struct ds_nbr *ds_nbr, struct iface *iface) 539 { 540 log_debug("srt_delete_ds: deleting downstream router for source %s/%d", 541 inet_ntoa(rn->prefix), rn->prefixlen); 542 543 LIST_REMOVE(ds_nbr, entry); 544 free(ds_nbr); 545 rn->ds_cnt[iface->ifindex]--; 546 547 srt_check_downstream_ifaces(rn, iface); 548 } 549 550 void 551 srt_check_downstream_ifaces(struct rt_node *rn, struct iface *iface) 552 { 553 /* We are not the designated forwarder for this source on this 554 interface. Keep things as they currently are */ 555 if (rn->adv_rtr[iface->ifindex].addr.s_addr != iface->addr.s_addr) 556 return; 557 558 /* There are still downstream dependent router for this source 559 Keep things as they currently are */ 560 if (rn->ds_cnt[iface->ifindex]) 561 return; 562 563 /* There are still group members for this source on this iface 564 Keep things as they currently are */ 565 if (mfc_check_members(rn, iface)) 566 return; 567 568 /* Remove interface from the downstream list */ 569 rn->ttls[iface->ifindex] = 0; 570 mfc_update_source(rn); 571 } 572 573 void 574 srt_expire_nbr(struct in_addr addr, unsigned int ifindex) 575 { 576 struct ds_nbr *ds; 577 struct rt_node *rn; 578 struct iface *iface; 579 580 iface = if_find_index(ifindex); 581 if (iface == NULL) 582 fatal("srt_expire_nbr: interface not found"); 583 584 RB_FOREACH(rn, rt_tree, &rt) { 585 if (rn->adv_rtr[ifindex].addr.s_addr == addr.s_addr) { 586 rn->adv_rtr[ifindex].addr.s_addr = 587 iface->addr.s_addr; 588 rn->adv_rtr[ifindex].metric = rn->cost; 589 /* XXX: delete all routes learned from this nbr */ 590 } else if (rn->adv_rtr[ifindex].addr.s_addr == 591 iface->addr.s_addr) { 592 ds = srt_find_ds(rn, addr.s_addr); 593 if (ds) { 594 srt_delete_ds(rn, ds, iface); 595 srt_check_downstream_ifaces(rn, iface); 596 } 597 } 598 } 599 } 600 601 void 602 flash_update(struct rt_node *rn) { 603 struct route_report rr; 604 605 rr.net = rn->prefix; 606 rr.mask.s_addr = ntohl(prefixlen2mask(rn->prefixlen)); 607 rr.metric = rn->cost; 608 rr.ifindex = rn->ifindex; 609 rde_imsg_compose_dvmrpe(IMSG_FLASH_UPDATE, 0, 0, &rr, sizeof(rr)); 610 } 611 612 void 613 flash_update_ds(struct rt_node *rn) { 614 struct route_report rr; 615 616 rr.net = rn->prefix; 617 rr.mask.s_addr = ntohl(prefixlen2mask(rn->prefixlen)); 618 rr.metric = rn->cost; 619 rr.ifindex = rn->ifindex; 620 rde_imsg_compose_dvmrpe(IMSG_FLASH_UPDATE_DS, 0, 0, &rr, sizeof(rr)); 621 } 622