1 /* $OpenBSD: lde_lib.c,v 1.29 2010/11/04 09:49:07 claudio Exp $ */ 2 3 /* 4 * Copyright (c) 2009 Michele Marchetto <michele@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 <sys/types.h> 20 #include <sys/ioctl.h> 21 #include <sys/time.h> 22 #include <sys/socket.h> 23 #include <net/if.h> 24 #include <net/if_types.h> 25 #include <netinet/in.h> 26 #include <netmpls/mpls.h> 27 #include <arpa/inet.h> 28 #include <ctype.h> 29 #include <err.h> 30 #include <stdio.h> 31 #include <stdlib.h> 32 #include <unistd.h> 33 #include <string.h> 34 #include <event.h> 35 36 #include "ldpd.h" 37 #include "ldp.h" 38 #include "log.h" 39 #include "lde.h" 40 41 static int fec_compare(struct fec *, struct fec *); 42 43 void rt_free(void *); 44 struct rt_node *rt_add(struct in_addr, u_int8_t); 45 struct rt_lsp *rt_lsp_find(struct rt_node *, struct in_addr, u_int8_t); 46 struct rt_lsp *rt_lsp_add(struct rt_node *, struct in_addr, u_int8_t); 47 void rt_lsp_del(struct rt_lsp *); 48 49 RB_PROTOTYPE(fec_tree, fec, entry, fec_compare) 50 RB_GENERATE(fec_tree, fec, entry, fec_compare) 51 52 extern struct ldpd_conf *ldeconf; 53 54 struct fec_tree rt = RB_INITIALIZER(&rt); 55 56 /* FEC tree fucntions */ 57 void 58 fec_init(struct fec_tree *fh) 59 { 60 RB_INIT(fh); 61 } 62 63 static int 64 fec_compare(struct fec *a, struct fec *b) 65 { 66 if (ntohl(a->prefix.s_addr) < ntohl(b->prefix.s_addr)) 67 return (-1); 68 if (ntohl(a->prefix.s_addr) > ntohl(b->prefix.s_addr)) 69 return (1); 70 if (a->prefixlen < b->prefixlen) 71 return (-1); 72 if (a->prefixlen > b->prefixlen) 73 return (1); 74 75 return (0); 76 } 77 78 struct fec * 79 fec_find_prefix(struct fec_tree *fh, in_addr_t prefix, u_int8_t prefixlen) 80 { 81 struct fec s; 82 83 s.prefix.s_addr = prefix; 84 s.prefixlen = prefixlen; 85 86 return (fec_find(fh, &s)); 87 } 88 89 struct fec * 90 fec_find(struct fec_tree *fh, struct fec *f) 91 { 92 return (RB_FIND(fec_tree, fh, f)); 93 } 94 95 96 int 97 fec_insert(struct fec_tree *fh, struct fec *f) 98 { 99 if (RB_INSERT(fec_tree, fh, f) != NULL) 100 return (-1); 101 return (0); 102 } 103 104 int 105 fec_remove(struct fec_tree *fh, struct fec *f) 106 { 107 if (RB_REMOVE(fec_tree, fh, f) == NULL) { 108 log_warnx("fec_remove failed for %s/%u", 109 inet_ntoa(f->prefix), f->prefixlen); 110 return (-1); 111 } 112 return (0); 113 } 114 115 void 116 fec_clear(struct fec_tree *fh, void (*free_cb)(void *)) 117 { 118 struct fec *f; 119 120 while ((f = RB_ROOT(fh)) != NULL) { 121 fec_remove(fh, f); 122 free_cb(f); 123 } 124 } 125 126 127 /* routing table functions */ 128 void 129 rt_dump(pid_t pid) 130 { 131 struct fec *f; 132 struct rt_node *rr; 133 struct rt_lsp *rl; 134 struct lde_map *me; 135 static struct ctl_rt rtctl; 136 137 RB_FOREACH(f, fec_tree, &rt) { 138 rr = (struct rt_node *)f; 139 rtctl.prefix = rr->fec.prefix; 140 rtctl.prefixlen = rr->fec.prefixlen; 141 rtctl.flags = rr->flags; 142 rtctl.local_label = rr->local_label; 143 144 LIST_FOREACH(rl, &rr->lsp, entry) { 145 rtctl.nexthop = rl->nexthop; 146 rtctl.remote_label = rl->remote_label; 147 rtctl.in_use = 1; 148 149 if (rtctl.nexthop.s_addr == htonl(INADDR_ANY)) 150 rtctl.connected = 1; 151 else 152 rtctl.connected = 0; 153 154 lde_imsg_compose_ldpe(IMSG_CTL_SHOW_LIB, 0, pid, 155 &rtctl, sizeof(rtctl)); 156 } 157 if (LIST_EMPTY(&rr->lsp)) { 158 LIST_FOREACH(me, &rr->downstream, entry) { 159 rtctl.in_use = 0; 160 rtctl.connected = 0; 161 /* we don't know the nexthop use id instead */ 162 rtctl.nexthop = me->nexthop->id; 163 rtctl.remote_label = me->label; 164 165 lde_imsg_compose_ldpe(IMSG_CTL_SHOW_LIB, 0, pid, 166 &rtctl, sizeof(rtctl)); 167 } 168 } 169 } 170 } 171 172 void 173 rt_snap(struct lde_nbr *ln) 174 { 175 struct fec *f; 176 struct rt_node *r; 177 struct lde_map *me; 178 struct map map; 179 180 bzero(&map, sizeof(map)); 181 RB_FOREACH(f, fec_tree, &rt) { 182 r = (struct rt_node *)f; 183 map.prefix = r->fec.prefix; 184 map.prefixlen = r->fec.prefixlen; 185 map.label = r->local_label; 186 187 me = lde_map_add(ln, r, 1); 188 me->label = r->local_label; 189 190 lde_imsg_compose_ldpe(IMSG_MAPPING_ADD, ln->peerid, 0, &map, 191 sizeof(map)); 192 } 193 } 194 195 void 196 rt_free(void *arg) 197 { 198 struct rt_node *rr = arg; 199 struct rt_lsp *rl; 200 201 while ((rl = LIST_FIRST(&rr->lsp))) { 202 LIST_REMOVE(rl, entry); 203 free(rl); 204 } 205 206 if (!LIST_EMPTY(&rr->downstream)) 207 log_warnx("rt_free: fec %s/%u downstream list not empty", 208 inet_ntoa(rr->fec.prefix), rr->fec.prefixlen); 209 if (!LIST_EMPTY(&rr->upstream)) 210 log_warnx("rt_free: fec %s/%u upstream list not empty", 211 inet_ntoa(rr->fec.prefix), rr->fec.prefixlen); 212 213 free(rl); 214 } 215 216 void 217 rt_clear(void) 218 { 219 fec_clear(&rt, rt_free); 220 } 221 222 struct rt_node * 223 rt_add(struct in_addr prefix, u_int8_t prefixlen) 224 { 225 struct rt_node *rn; 226 227 rn = calloc(1, sizeof(*rn)); 228 if (rn == NULL) 229 fatal("rt_add"); 230 231 rn->fec.prefix.s_addr = prefix.s_addr; 232 rn->fec.prefixlen = prefixlen; 233 rn->local_label = NO_LABEL; 234 LIST_INIT(&rn->upstream); 235 LIST_INIT(&rn->downstream); 236 LIST_INIT(&rn->lsp); 237 238 if (fec_insert(&rt, &rn->fec)) 239 log_warnx("failed to add %s/%u to rt tree", 240 inet_ntoa(rn->fec.prefix), rn->fec.prefixlen); 241 242 return (rn); 243 } 244 245 struct rt_lsp * 246 rt_lsp_find(struct rt_node *rn, struct in_addr nexthop, u_int8_t prio) 247 { 248 struct rt_lsp *rl; 249 250 LIST_FOREACH(rl, &rn->lsp, entry) 251 if (rl->nexthop.s_addr == nexthop.s_addr && 252 rl->priority == prio) 253 return (rl); 254 return (NULL); 255 } 256 257 struct rt_lsp * 258 rt_lsp_add(struct rt_node *rn, struct in_addr nexthop, u_int8_t prio) 259 { 260 struct rt_lsp *rl, *nrl; 261 262 rl = calloc(1, sizeof(*rl)); 263 if (rl == NULL) 264 fatal("rt_lsp_add"); 265 266 rl->nexthop.s_addr = nexthop.s_addr; 267 rl->remote_label = NO_LABEL; 268 rl->priority = prio; 269 270 /* keep LSP list sorted by priority because only the best routes 271 * can be used in a LSP. */ 272 if (LIST_EMPTY(&rn->lsp)) 273 LIST_INSERT_HEAD(&rn->lsp, rl, entry); 274 else { 275 LIST_FOREACH(nrl, &rn->lsp, entry) { 276 if (prio < nrl->priority) { 277 LIST_INSERT_BEFORE(nrl, rl, entry); 278 break; 279 } 280 if (LIST_NEXT(nrl, entry) == NULL) { 281 LIST_INSERT_AFTER(nrl, rl, entry); 282 break; 283 } 284 } 285 } 286 return (rl); 287 } 288 289 void 290 rt_lsp_del(struct rt_lsp *rl) 291 { 292 LIST_REMOVE(rl, entry); 293 free(rl); 294 } 295 296 void 297 lde_kernel_insert(struct kroute *kr) 298 { 299 struct rt_node *rn; 300 struct rt_lsp *rl; 301 struct lde_nbr_address *addr; 302 struct lde_map *map; 303 304 log_debug("kernel add route %s/%u", inet_ntoa(kr->prefix), 305 kr->prefixlen); 306 307 rn = (struct rt_node *)fec_find_prefix(&rt, kr->prefix.s_addr, 308 kr->prefixlen); 309 if (rn == NULL) 310 rn = rt_add(kr->prefix, kr->prefixlen); 311 312 rl = rt_lsp_find(rn, kr->nexthop, kr->priority); 313 if (rl == NULL) 314 rl = rt_lsp_add(rn, kr->nexthop, kr->priority); 315 316 /* There is static assigned label for this route, record it in lib */ 317 if (kr->local_label != NO_LABEL) { 318 rn->local_label = kr->local_label; 319 return; 320 } 321 322 if (rn->local_label == NO_LABEL) { 323 if (kr->nexthop.s_addr == INADDR_ANY) 324 /* Directly connected route */ 325 rn->local_label = MPLS_LABEL_IMPLNULL; 326 else 327 rn->local_label = lde_assign_label(); 328 } 329 330 LIST_FOREACH(map, &rn->downstream, entry) { 331 addr = lde_address_find(map->nexthop, &rl->nexthop); 332 if (addr != NULL) { 333 rl->remote_label = map->label; 334 break; 335 } 336 } 337 338 lde_send_change_klabel(rn, rl); 339 340 /* Redistribute the current mapping to every nbr */ 341 lde_nbr_do_mappings(rn); 342 } 343 344 void 345 lde_kernel_remove(struct kroute *kr) 346 { 347 struct rt_node *rn; 348 struct rt_lsp *rl; 349 350 log_debug("kernel remove route %s/%u", inet_ntoa(kr->prefix), 351 kr->prefixlen); 352 353 rn = (struct rt_node *)fec_find_prefix(&rt, kr->prefix.s_addr, 354 kr->prefixlen); 355 if (rn == NULL) 356 /* route lost */ 357 return; 358 359 rl = rt_lsp_find(rn, kr->nexthop, kr->priority); 360 if (rl != NULL) 361 rt_lsp_del(rl); 362 363 /* XXX handling of total loss of route, withdraw mappings, etc */ 364 365 /* Redistribute the current mapping to every nbr */ 366 lde_nbr_do_mappings(rn); 367 } 368 369 void 370 lde_check_mapping(struct map *map, struct lde_nbr *ln) 371 { 372 struct rt_node *rn; 373 struct rt_lsp *rl; 374 struct lde_req *lre; 375 struct lde_nbr_address *addr = NULL; 376 struct lde_map *me; 377 378 log_debug("label mapping from nbr %s, FEC %s, label %u", 379 inet_ntoa(ln->id), log_fec(map), map->label); 380 381 rn = (struct rt_node *)fec_find_prefix(&rt, map->prefix.s_addr, 382 map->prefixlen); 383 if (rn == NULL) { 384 /* The route is not yet in fib. If we are in liberal mode 385 * create a route and record the label */ 386 if (ldeconf->mode & MODE_RET_CONSERVATIVE) 387 return; 388 389 rn = rt_add(map->prefix, map->prefixlen); 390 rn->local_label = lde_assign_label(); 391 } 392 393 /* first check if we have a pending request running */ 394 lre = (struct lde_req *)fec_find(&ln->sent_req, &rn->fec); 395 if (lre) 396 lde_req_del(ln, lre, 1); 397 398 /* TODO Loop detection LMp.3 - LMp.8 */ 399 400 LIST_FOREACH(me, &rn->downstream, entry) { 401 if (ln != me->nexthop) /* LMp.9 */ 402 continue; 403 if (lre) 404 /* LMp.10 Note 6: req. mappings are always new */ 405 break; 406 if (me->label != map->label) { /* LMp.10 */ 407 /* 408 * This is, according to the RFC, a try to install a 409 * multipath LSP which is not supported by the RFC. 410 * So instead release the old label and install the 411 * new one. 412 */ 413 log_debug("possible multipath FEC %s, " 414 "label %u, old label %u", 415 log_fec(map), map->label, me->label); 416 lde_send_labelrelease(ln, rn, me->label); 417 } 418 /* there can only be one mapping */ 419 break; 420 } 421 422 /* LMp.11: get nexthop */ 423 LIST_FOREACH(rl, &rn->lsp, entry) { 424 addr = lde_address_find(ln, &rl->nexthop); 425 if (addr) 426 break; 427 } 428 if (addr == NULL) { 429 /* route not yet available LMp.13 */ 430 if (ldeconf->mode & MODE_RET_CONSERVATIVE) { 431 log_debug("FEC %s: conservative ret but no route", 432 log_fec(map)); 433 lde_send_labelrelease(ln, rn, map->label); 434 return; 435 } 436 /* in liberal mode just note the mapping */ 437 if (me == NULL) 438 me = lde_map_add(ln, rn, 0); 439 me->label = map->label; 440 441 return; 442 } 443 444 /* LMp.14 do we actually need this FEC for now this is always true */ 445 rl->remote_label = map->label; 446 447 /* LMp.15 install FEC in FIB */ 448 lde_send_change_klabel(rn, rl); 449 450 /* Record the mapping from this peer LMp.16 */ 451 if (me == NULL) 452 me = lde_map_add(ln, rn, 0); 453 me->label = map->label; 454 455 /* Redistribute the current mapping to every nbr LMp.17-31 */ 456 lde_nbr_do_mappings(rn); 457 } 458 459 void 460 lde_check_request(struct map *map, struct lde_nbr *ln) 461 { 462 struct lde_req *lre; 463 struct rt_node *rn; 464 struct rt_lsp *rl; 465 struct lde_nbr *lnn; 466 u_int8_t prio = 0; 467 468 log_debug("label request from nbr %s, FEC %s", 469 inet_ntoa(ln->id), log_fec(map)); 470 471 rn = (struct rt_node *)fec_find_prefix(&rt, map->prefix.s_addr, 472 map->prefixlen); 473 if (rn == NULL) { 474 lde_send_notification(ln->peerid, S_NO_ROUTE, map->messageid, 475 MSG_TYPE_LABELREQUEST); 476 return; 477 } 478 479 LIST_FOREACH(rl, &rn->lsp, entry) { 480 /* only consider pathes with highest priority */ 481 if (prio == 0) 482 prio = rl->priority; 483 if (prio < rl->priority) 484 break; 485 if (lde_address_find(ln, &rl->nexthop)) { 486 lde_send_notification(ln->peerid, S_LOOP_DETECTED, 487 map->messageid, MSG_TYPE_LABELREQUEST); 488 return; 489 } 490 491 if (rl->remote_label != NO_LABEL) 492 break; 493 } 494 495 /* first check if we have a pending request running */ 496 lre = (struct lde_req *)fec_find(&ln->recv_req, &rn->fec); 497 if (lre != NULL) 498 return; 499 /* else record label request */ 500 lre = lde_req_add(ln, &rn->fec, 0); 501 if (lre != NULL) 502 lre->msgid = map->messageid; 503 504 /* there is a valid mapping available */ 505 if (rl != NULL) { 506 /* TODO loop protection handling (LRq.9) */ 507 lde_send_labelmapping(ln, rn); 508 return; 509 } 510 511 /* no mapping available, try to request */ 512 /* XXX depending on the request behaviour we could return here */ 513 LIST_FOREACH(rl, &rn->lsp, entry) { 514 /* only consider pathes with highest priority */ 515 if (prio == 0) 516 prio = rl->priority; 517 if (prio < rl->priority) 518 break; 519 lnn = lde_find_address(rl->nexthop); 520 if (lnn == NULL) 521 continue; 522 lde_send_labelrequest(lnn, rn); 523 } 524 } 525 526 void 527 lde_check_release(struct map *map, struct lde_nbr *ln) 528 { 529 struct rt_node *rn; 530 struct lde_req *lre; 531 struct lde_map *me; 532 533 log_debug("label release from nbr %s, FEC %s", 534 inet_ntoa(ln->id), log_fec(map)); 535 536 rn = (struct rt_node *)fec_find_prefix(&rt, map->prefix.s_addr, 537 map->prefixlen); 538 if (rn == NULL) 539 return; 540 541 /* first check if we have a pending withdraw running */ 542 lre = (struct lde_req *)fec_find(&ln->sent_wdraw, &rn->fec); 543 if (lre) { 544 fec_remove(&ln->sent_wdraw, &lre->fec); 545 free(lre); 546 } 547 548 /* check sent map list and remove it if available */ 549 me = (struct lde_map *)fec_find(&ln->sent_map, &rn->fec); 550 if (me) 551 lde_map_del(ln, me, 1); 552 553 /* remove FEC if not in use anymore */ 554 /* XXX what about outstanding label requests? */ 555 if (!LIST_EMPTY(&rn->upstream)) 556 return; 557 558 /* XXX if originated here free all resources */ 559 /* else decide if a label release should be forwarded. */ 560 /* Since we do liberal retention we can keep the path mapped. */ 561 } 562 563 void 564 lde_check_withdraw(struct map *map, struct lde_nbr *ln) 565 { 566 struct rt_node *rn; 567 struct rt_lsp *rl; 568 struct lde_map *me; 569 570 log_debug("label withdraw from nbr %s, FEC %s", 571 inet_ntoa(ln->id), log_fec(map)); 572 573 rn = (struct rt_node *)fec_find_prefix(&rt, map->prefix.s_addr, 574 map->prefixlen); 575 576 lde_send_labelrelease(ln, rn, map->label); 577 578 if (rn == NULL) 579 /* LSP not available, nothing to do */ 580 return; 581 582 /* remove LSP from kernel */ 583 LIST_FOREACH(rl, &rn->lsp, entry) { 584 if (lde_address_find(ln, &rl->nexthop)) 585 break; 586 } 587 if (rl) { 588 rl->remote_label = NO_LABEL; 589 lde_send_delete_klabel(rn, rl); 590 } 591 592 /* check recv map list and remove it if available */ 593 me = (struct lde_map *)fec_find(&ln->recv_map, &rn->fec); 594 if (me) 595 lde_map_del(ln, me, 0); 596 597 /* if ordered distribution */ 598 /* walk over upstream list and send withdraws for LSP that depend on 599 * the removed LSP */ 600 601 /* if independent distribution and adv on demand */ 602 /* Generate Event: Recognize New FEC for FEC. */ 603 } 604