1 /* $OpenBSD: lde_lib.c,v 1.6 2009/09/28 09:48:46 michele 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 <netinet/in.h> 24 #include <arpa/inet.h> 25 #include <net/if.h> 26 #include <net/if_types.h> 27 #include <netmpls/mpls.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 extern struct ldpd_conf *ldeconf; 42 RB_HEAD(rt_tree, rt_node) rt; 43 RB_PROTOTYPE(rt_tree, rt_node, entry, rt_compare) 44 RB_GENERATE(rt_tree, rt_node, entry, rt_compare) 45 46 u_int32_t lde_assign_label(void); 47 48 /* route table */ 49 void 50 rt_init(void) 51 { 52 RB_INIT(&rt); 53 } 54 55 int 56 rt_compare(struct rt_node *a, struct rt_node *b) 57 { 58 if (ntohl(a->prefix.s_addr) < ntohl(b->prefix.s_addr)) 59 return (-1); 60 if (ntohl(a->prefix.s_addr) > ntohl(b->prefix.s_addr)) 61 return (1); 62 if (a->prefixlen < b->prefixlen) 63 return (-1); 64 if (a->prefixlen > b->prefixlen) 65 return (1); 66 67 return (0); 68 } 69 70 struct rt_node * 71 rt_find(in_addr_t prefix, u_int8_t prefixlen) 72 { 73 struct rt_node s; 74 75 s.prefix.s_addr = prefix; 76 s.prefixlen = prefixlen; 77 78 return (RB_FIND(rt_tree, &rt, &s)); 79 } 80 81 int 82 rt_insert(struct rt_node *r) 83 { 84 if (RB_INSERT(rt_tree, &rt, r) != NULL) { 85 log_warnx("rt_insert failed for %s/%u", 86 inet_ntoa(r->prefix), r->prefixlen); 87 free(r); 88 return (-1); 89 } 90 91 return (0); 92 } 93 94 int 95 rt_remove(struct rt_node *r) 96 { 97 if (RB_REMOVE(rt_tree, &rt, r) == NULL) { 98 log_warnx("rt_remove failed for %s/%u", 99 inet_ntoa(r->prefix), r->prefixlen); 100 return (-1); 101 } 102 103 free(r); 104 return (0); 105 } 106 107 void 108 rt_dump(pid_t pid) 109 { 110 struct rt_node *r; 111 static struct ctl_rt rtctl; 112 113 RB_FOREACH(r, rt_tree, &rt) { 114 if (!r->present) 115 continue; 116 117 rtctl.prefix.s_addr = r->prefix.s_addr; 118 rtctl.prefixlen = r->prefixlen; 119 rtctl.nexthop.s_addr = r->nexthop.s_addr; 120 rtctl.flags = r->flags; 121 rtctl.local_label = r->local_label; 122 rtctl.remote_label = r->remote_label; 123 124 if (rtctl.nexthop.s_addr == htonl(INADDR_LOOPBACK)) 125 rtctl.connected = 1; 126 else 127 rtctl.connected = 0; 128 129 lde_imsg_compose_ldpe(IMSG_CTL_SHOW_LIB, 0, pid, &rtctl, 130 sizeof(rtctl)); 131 } 132 } 133 134 void 135 rt_snap(u_int32_t peerid) 136 { 137 struct rt_node *r; 138 struct map map; 139 140 bzero(&map, sizeof(map)); 141 142 RB_FOREACH(r, rt_tree, &rt) { 143 map.prefix = r->prefix.s_addr; 144 map.prefixlen = r->prefixlen; 145 map.label = (ntohl(r->local_label) & MPLS_LABEL_MASK) >> 146 MPLS_LABEL_OFFSET; 147 148 lde_imsg_compose_ldpe(IMSG_MAPPING_ADD, peerid, 0, &map, 149 sizeof(map)); 150 } 151 } 152 153 void 154 rt_clear(void) 155 { 156 struct rt_node *r; 157 158 while ((r = RB_MIN(rt_tree, &rt)) != NULL) 159 rt_remove(r); 160 } 161 162 u_int32_t 163 lde_assign_label() 164 { 165 static u_int32_t label = MPLS_LABEL_RESERVED_MAX; 166 167 /* XXX some checks needed */ 168 label++; 169 return (htonl(label << MPLS_LABEL_OFFSET)); 170 } 171 172 void 173 lde_kernel_insert(struct kroute *kr) 174 { 175 struct rt_node *rn; 176 struct rt_label *rl; 177 struct lde_nbr_address *addr; 178 179 rn = rt_find(kr->prefix.s_addr, kr->prefixlen); 180 if (rn == NULL) { 181 rn = calloc(1, sizeof(*rn)); 182 if (rn == NULL) 183 fatal("lde_insert"); 184 185 rn->prefix.s_addr = kr->prefix.s_addr; 186 rn->prefixlen = kr->prefixlen; 187 TAILQ_INIT(&rn->labels_list); 188 189 rt_insert(rn); 190 } 191 192 if (rn->present) { 193 if (kr->nexthop.s_addr == rn->nexthop.s_addr) 194 return; 195 196 /* The nexthop has changed, change also the label associated 197 with prefix */ 198 rn->remote_label = 0; 199 rn->nexthop.s_addr = kr->nexthop.s_addr; 200 201 if ((ldeconf->mode & MODE_RET_LIBERAL) == 0) { 202 /* XXX: we support just liberal retention for now */ 203 return; 204 } 205 206 TAILQ_FOREACH(rl, &rn->labels_list, entry) { 207 addr = lde_address_find(rl->nexthop, &rn->nexthop); 208 if (addr != NULL) { 209 rn->remote_label = 210 htonl(rl->label << MPLS_LABEL_OFFSET); 211 break; 212 } 213 } 214 215 log_debug("lde_kernel_insert: prefix %s, changing label to %u", 216 inet_ntoa(rn->prefix), rl->label); 217 218 lde_send_change_klabel(rn); 219 return; 220 } 221 222 rn->present = 1; 223 rn->nexthop.s_addr = kr->nexthop.s_addr; 224 225 /* There is static assigned label for this route, record it in lib */ 226 if (kr->local_label) { 227 rn->local_label = (htonl(kr->local_label) << MPLS_LABEL_OFFSET); 228 return; 229 } 230 231 /* There is already a local mapping, check if there 232 is also a remote one */ 233 if (rn->local_label) { 234 TAILQ_FOREACH(rl, &rn->labels_list, entry) { 235 addr = lde_address_find(rl->nexthop, &rn->nexthop); 236 if (addr != NULL) { 237 rn->remote_label = 238 htonl(rl->label << MPLS_LABEL_OFFSET); 239 break; 240 } 241 } 242 } else { 243 /* Directly connected route */ 244 if (kr->nexthop.s_addr == INADDR_ANY) { 245 rn->local_label = 246 htonl(MPLS_LABEL_IMPLNULL << MPLS_LABEL_OFFSET); 247 rn->nexthop.s_addr = htonl(INADDR_LOOPBACK); 248 } else 249 rn->local_label = lde_assign_label(); 250 } 251 252 lde_send_insert_klabel(rn); 253 } 254 255 void 256 lde_kernel_remove(struct kroute *kr) 257 { 258 struct rt_node *rn; 259 struct rt_label *rl; 260 struct lde_nbr *ln; 261 262 rn = rt_find(kr->prefix.s_addr, kr->prefixlen); 263 if (rn == NULL) 264 return; 265 266 if (ldeconf->mode & MODE_RET_LIBERAL) { 267 rl = calloc(1, sizeof(*rl)); 268 if (rl == NULL) 269 fatal("lde_kernel_remove"); 270 271 rl->label = rn->remote_label; 272 273 ln = lde_find_address(rn->nexthop); 274 if (ln == NULL) 275 fatalx("lde_kernel_remove: unable to find neighbor"); 276 277 rl->nexthop = ln; 278 279 TAILQ_INSERT_TAIL(&rn->labels_list, rl, entry); 280 } 281 282 /* XXX */ 283 rn->remote_label = 0; 284 rn->nexthop.s_addr = INADDR_ANY; 285 rn->present = 0; 286 } 287 288 void 289 lde_check_mapping(struct map *map, struct lde_nbr *ln) 290 { 291 struct rt_node *rn; 292 struct rt_label *rl; 293 struct lde_nbr_address *addr; 294 struct lde_map_entry *me, *menew; 295 struct lde_req_entry *req; 296 struct iface *iface; 297 struct map localmap; 298 299 /* The route is not yet in fib. If we are in liberal mode create a 300 route and record the label */ 301 rn = rt_find(map->prefix, map->prefixlen); 302 if (rn == NULL) { 303 if (ldeconf->mode & MODE_RET_CONSERVATIVE) 304 return; 305 306 rn = calloc(1, sizeof(*rn)); 307 if (rn == NULL) 308 fatal("lde_check_mapping"); 309 310 rn->prefix.s_addr = map->prefix; 311 rn->prefixlen = map->prefixlen; 312 rn->local_label = lde_assign_label(); 313 rn->present = 0; 314 315 TAILQ_INIT(&rn->labels_list); 316 317 rt_insert(rn); 318 } 319 320 TAILQ_FOREACH(me, &ln->recv_map_list, entry) { 321 if (me->prefix.s_addr == map->prefix && 322 me->prefixlen == map->prefixlen) { 323 if (me->label == map->label) { 324 lde_send_labelrelease(ln->peerid, map); 325 return; 326 } 327 } 328 } 329 330 addr = lde_address_find(ln, &rn->nexthop); 331 if (addr == NULL || !rn->present) { 332 if (ldeconf->mode & MODE_RET_CONSERVATIVE) { 333 lde_send_labelrelease(ln->peerid, map); 334 return; 335 } 336 337 rl = calloc(1, sizeof(*rl)); 338 if (rl == NULL) 339 fatal("lde_check_mapping"); 340 341 rl->label = map->label; 342 rl->nexthop = ln; 343 344 TAILQ_INSERT_TAIL(&rn->labels_list, rl, entry); 345 return; 346 } 347 348 rn->remote_label = htonl(map->label << MPLS_LABEL_OFFSET); 349 350 /* If we are ingress for this LSP install the label */ 351 if (rn->nexthop.s_addr == INADDR_ANY) 352 lde_send_change_klabel(rn); 353 354 /* Record the mapping from this peer */ 355 menew = calloc(1, sizeof(*menew)); 356 if (menew == NULL) 357 fatal("lde_check_mapping"); 358 359 menew->prefix.s_addr = map->prefix; 360 menew->prefixlen = map->prefixlen; 361 menew->label = map->label; 362 363 TAILQ_INSERT_HEAD(&ln->recv_map_list, menew, entry); 364 365 /* Redistribute the current mapping to every nbr */ 366 localmap.label = rn->local_label; 367 localmap.prefix = rn->prefix.s_addr; 368 localmap.prefixlen = rn->prefixlen; 369 370 LIST_FOREACH(iface, &ldeconf->iface_list, entry) { 371 LIST_FOREACH(ln, &iface->lde_nbr_list, entry) { 372 /* Did we already send a mapping to this peer? */ 373 TAILQ_FOREACH(me, &ln->sent_map_list, entry) { 374 if (me->prefix.s_addr == rn->prefix.s_addr && 375 me->prefixlen == rn->prefixlen) 376 break; 377 } 378 if (me != NULL) { 379 /* XXX: check RAttributes */ 380 continue; 381 } 382 383 if (ldeconf->mode & MODE_ADV_UNSOLICITED && 384 ldeconf->mode & MODE_DIST_ORDERED) { 385 lde_send_labelmapping(ln->peerid, &localmap); 386 387 menew = calloc(1, sizeof(*menew)); 388 if (menew == NULL) 389 fatal("lde_check_mapping"); 390 391 menew->prefix.s_addr = map->prefix; 392 menew->prefixlen = map->prefixlen; 393 menew->label = map->label; 394 395 TAILQ_INSERT_HEAD(&ln->sent_map_list, menew, 396 entry); 397 } 398 399 TAILQ_FOREACH(req, &ln->req_list, entry) { 400 if (req->prefix.s_addr == rn->prefix.s_addr && 401 req->prefixlen == rn->prefixlen) 402 break; 403 } 404 if (req != NULL) { 405 lde_send_labelmapping(ln->peerid, &localmap); 406 407 menew = calloc(1, sizeof(*menew)); 408 if (menew == NULL) 409 fatal("lde_check_mapping"); 410 411 menew->prefix.s_addr = map->prefix; 412 menew->prefixlen = map->prefixlen; 413 menew->label = map->label; 414 415 TAILQ_INSERT_HEAD(&ln->sent_map_list, menew, 416 entry); 417 418 TAILQ_REMOVE(&ln->req_list, req, entry); 419 free(req); 420 } 421 } 422 } 423 424 lde_send_change_klabel(rn); 425 } 426 427 void 428 lde_check_request(struct map *map, struct lde_nbr *ln) 429 { 430 struct lde_req_entry *lre, *newlre; 431 struct rt_node *rn; 432 struct lde_nbr *lnn; 433 struct map localmap; 434 435 bzero(&newlre, sizeof(newlre)); 436 437 rn = rt_find(map->prefix, map->prefixlen); 438 if (rn == NULL || rn->remote_label == NO_LABEL) { 439 lde_send_notification(ln->peerid, S_NO_ROUTE, map->messageid, 440 MSG_TYPE_LABELREQUEST); 441 return; 442 } 443 444 if (lde_address_find(ln, &rn->nexthop)) { 445 lde_send_notification(ln->peerid, S_LOOP_DETECTED, 446 map->messageid, MSG_TYPE_LABELREQUEST); 447 return; 448 } 449 450 TAILQ_FOREACH(lre, &ln->req_list, entry) { 451 if (lre->prefix.s_addr == map->prefix && 452 lre->prefixlen == map->prefixlen) 453 return; 454 } 455 456 /* XXX: if we are egress ? */ 457 if (rn->remote_label != NO_LABEL) { 458 bzero(&localmap, sizeof(localmap)); 459 localmap.prefix = map->prefix; 460 localmap.prefixlen = map->prefixlen; 461 localmap.label = rn->local_label; 462 463 lde_send_labelmapping(ln->peerid, &localmap); 464 } else { 465 lnn = lde_find_address(rn->nexthop); 466 if (lnn == NULL) 467 return; 468 469 lde_send_labelrequest(lnn->peerid, map); 470 471 newlre = calloc(1, sizeof(*newlre)); 472 if (newlre == NULL) 473 fatal("lde_check_request"); 474 475 newlre->prefix.s_addr = map->prefix; 476 newlre->prefixlen = map->prefixlen; 477 478 TAILQ_INSERT_HEAD(&ln->req_list, newlre, entry); 479 } 480 } 481