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