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