1 /* $OpenBSD: rde_mfc.c,v 1.10 2015/12/07 19:14:49 mmcc Exp $ */ 2 3 /* 4 * Copyright (c) 2009 Michele Marchetto <michele@openbsd.org> 5 * Copyright (c) 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 /* multicast forwarding cache */ 37 38 void mfc_send_prune(struct rt_node *, struct mfc_node *); 39 void mfc_add_prune(struct mfc_node *, struct prune *); 40 struct prune_node *mfc_find_prune(struct mfc_node *, struct prune *); 41 void mfc_delete_prune(struct mfc_node *, 42 struct prune_node *); 43 44 int prune_compare(struct mfc_node *, struct rt_node *, int); 45 void prune_expire_timer(int, short, void *); 46 int mfc_reset_prune_expire_timer(struct prune_node *); 47 48 49 void mfc_expire_timer(int, short, void *); 50 int mfc_start_expire_timer(struct mfc_node *); 51 int mfc_reset_expire_timer(struct mfc_node *); 52 void mfc_prune_timer(int, short, void *); 53 int mfc_start_prune_timer(struct mfc_node *); 54 int mfc_reset_prune_timer(struct mfc_node *); 55 56 int mfc_compare(struct mfc_node *, struct mfc_node *); 57 void mfc_invalidate(void); 58 59 RB_HEAD(mfc_tree, mfc_node) mfc; 60 RB_PROTOTYPE(mfc_tree, mfc_node, entry, mfc_compare) 61 RB_GENERATE(mfc_tree, mfc_node, entry, mfc_compare) 62 63 extern struct dvmrpd_conf *rdeconf; 64 65 /* timers */ 66 void 67 mfc_expire_timer(int fd, short event, void *arg) 68 { 69 struct mfc_node *mn = arg; 70 struct mfc nmfc; 71 72 log_debug("mfc_expire_timer: group %s", inet_ntoa(mn->group)); 73 74 /* remove route entry */ 75 nmfc.origin = mn->origin; 76 nmfc.group = mn->group; 77 rde_imsg_compose_parent(IMSG_MFC_DEL, 0, &nmfc, sizeof(nmfc)); 78 79 event_del(&mn->expiration_timer); 80 mfc_remove(mn); 81 } 82 83 int 84 mfc_reset_expire_timer(struct mfc_node *mn) 85 { 86 struct timeval tv; 87 88 timerclear(&tv); 89 tv.tv_sec = ROUTE_EXPIRATION_TIME; 90 return (evtimer_add(&mn->expiration_timer, &tv)); 91 } 92 93 int 94 mfc_start_expire_timer(struct mfc_node *mn) 95 { 96 struct timeval tv; 97 98 log_debug("mfc_start_expire_timer: group %s", inet_ntoa(mn->group)); 99 100 timerclear(&tv); 101 tv.tv_sec = ROUTE_EXPIRATION_TIME; 102 return (evtimer_add(&mn->expiration_timer, &tv)); 103 } 104 105 void 106 mfc_prune_timer(int fd, short event, void *arg) 107 { 108 struct mfc_node *mn = arg; 109 110 log_debug("mfc_prune_timer: group %s", inet_ntoa(mn->group)); 111 112 event_del(&mn->prune_timer); 113 } 114 115 int 116 mfc_start_prune_timer(struct mfc_node *mn) 117 { 118 struct timeval tv; 119 120 log_debug("mfc_start_prune_timer: group %s", inet_ntoa(mn->group)); 121 122 timerclear(&tv); 123 tv.tv_sec = MAX_PRUNE_LIFETIME; 124 return (evtimer_add(&mn->prune_timer, &tv)); 125 } 126 127 int 128 mfc_reset_prune_timer(struct mfc_node *mn) 129 { 130 struct timeval tv; 131 132 timerclear(&tv); 133 tv.tv_sec = MAX_PRUNE_LIFETIME; 134 return (evtimer_add(&mn->prune_timer, &tv)); 135 } 136 137 /* route table */ 138 void 139 mfc_init(void) 140 { 141 RB_INIT(&mfc); 142 } 143 144 int 145 mfc_compare(struct mfc_node *a, struct mfc_node *b) 146 { 147 if (ntohl(a->origin.s_addr) < ntohl(b->origin.s_addr)) 148 return (-1); 149 if (ntohl(a->origin.s_addr) > ntohl(b->origin.s_addr)) 150 return (1); 151 if (ntohl(a->group.s_addr) < ntohl(b->group.s_addr)) 152 return (-1); 153 if (ntohl(a->group.s_addr) > ntohl(b->group.s_addr)) 154 return (1); 155 return (0); 156 } 157 158 struct mfc_node * 159 mfc_find(in_addr_t origin, in_addr_t group) 160 { 161 struct mfc_node s; 162 163 s.origin.s_addr = origin; 164 s.group.s_addr = group; 165 166 return (RB_FIND(mfc_tree, &mfc, &s)); 167 } 168 169 int 170 mfc_insert(struct mfc_node *m) 171 { 172 if (RB_INSERT(mfc_tree, &mfc, m) != NULL) { 173 log_warnx("mfc_insert failed for group %s", 174 inet_ntoa(m->group)); 175 free(m); 176 return (-1); 177 } 178 179 return (0); 180 } 181 182 int 183 mfc_remove(struct mfc_node *m) 184 { 185 if (RB_REMOVE(mfc_tree, &mfc, m) == NULL) { 186 log_warnx("mfc_remove failed for group %s", 187 inet_ntoa(m->group)); 188 return (-1); 189 } 190 191 free(m); 192 return (0); 193 } 194 195 void 196 mfc_clear(void) 197 { 198 struct mfc_node *m; 199 200 while ((m = RB_MIN(mfc_tree, &mfc)) != NULL) 201 mfc_remove(m); 202 } 203 204 void 205 mfc_dump(pid_t pid) 206 { 207 static struct ctl_mfc mfcctl; 208 struct timespec now; 209 struct timeval tv, now2, res; 210 struct mfc_node *mn; 211 int i; 212 213 clock_gettime(CLOCK_MONOTONIC, &now); 214 215 RB_FOREACH(mn, mfc_tree, &mfc) { 216 mfcctl.origin.s_addr = mn->origin.s_addr; 217 mfcctl.group.s_addr = mn->group.s_addr; 218 mfcctl.uptime = now.tv_sec - mn->uptime; 219 mfcctl.ifindex = mn->ifindex; 220 221 for (i = 0; i < MAXVIFS; i ++) { 222 mfcctl.ttls[i] = mn->ttls[i]; 223 } 224 225 gettimeofday(&now2, NULL); 226 if (evtimer_pending(&mn->expiration_timer, &tv)) { 227 timersub(&tv, &now2, &res); 228 mfcctl.expire = res.tv_sec; 229 } else 230 mfcctl.expire = -1; 231 232 rde_imsg_compose_dvmrpe(IMSG_CTL_SHOW_MFC, 0, pid, &mfcctl, 233 sizeof(mfcctl)); 234 } 235 } 236 237 struct rt_node * 238 mfc_find_origin(struct in_addr group) 239 { 240 struct mfc_node *mn; 241 242 RB_FOREACH(mn, mfc_tree, &mfc) 243 if (group.s_addr == mn->group.s_addr) 244 return (rt_match_origin(mn->origin.s_addr)); 245 246 return (NULL); 247 } 248 249 void 250 mfc_send_prune(struct rt_node *rn, struct mfc_node *mn) 251 { 252 struct prune p; 253 254 memset(&p, 0, sizeof(p)); 255 256 p.origin.s_addr = (mn->origin.s_addr & 257 htonl(prefixlen2mask(rn->prefixlen))); 258 p.netmask.s_addr = htonl(prefixlen2mask(rn->prefixlen)); 259 p.group.s_addr = mn->group.s_addr; 260 p.nexthop.s_addr = rn->nexthop.s_addr; 261 p.ifindex = mn->ifindex; 262 263 rde_imsg_compose_dvmrpe(IMSG_SEND_PRUNE, 0, 0, &p, sizeof(p)); 264 265 mfc_start_prune_timer(mn); 266 } 267 268 void 269 mfc_update_source(struct rt_node *rn) 270 { 271 struct mfc_node *mn; 272 struct mfc m; 273 int i; 274 u_int8_t found; 275 276 RB_FOREACH(mn, mfc_tree, &mfc) { 277 if (rn->prefix.s_addr == (mn->origin.s_addr & 278 htonl(prefixlen2mask(rn->prefixlen)))) { 279 mn->ifindex = rn->ifindex; 280 281 found = 0; 282 283 for (i = 0; i < MAXVIFS; i++) { 284 mn->ttls[i] = rn->ttls[i]; 285 if (mn->ttls[i] != 0) 286 found = 1; 287 } 288 289 m.origin.s_addr = mn->origin.s_addr; 290 m.group.s_addr = mn->group.s_addr; 291 m.ifindex = mn->ifindex; 292 293 for (i = 0; i < MAXVIFS; i++) 294 m.ttls[i] = mn->ttls[i]; 295 296 rde_imsg_compose_parent(IMSG_MFC_ADD, 0, &m, sizeof(m)); 297 298 mfc_reset_expire_timer(mn); 299 300 if (!found && !rn->connected) 301 mfc_send_prune(rn, mn); 302 } 303 } 304 } 305 306 void 307 mfc_update(struct mfc *nmfc) 308 { 309 struct mfc_node *mn; 310 struct rt_node *rn; 311 struct timespec now; 312 int i; 313 u_int8_t found = 0; 314 315 clock_gettime(CLOCK_MONOTONIC, &now); 316 317 if ((mn = mfc_find(nmfc->origin.s_addr, nmfc->group.s_addr)) == NULL) { 318 if ((mn = calloc(1, sizeof(struct mfc_node))) == NULL) 319 fatalx("mfc_update"); 320 321 mn->origin.s_addr = nmfc->origin.s_addr; 322 mn->group.s_addr = nmfc->group.s_addr; 323 mn->ifindex = nmfc->ifindex; 324 mn->uptime = now.tv_sec; 325 for (i = 0; i < MAXVIFS; i++) { 326 mn->ttls[i] = nmfc->ttls[i]; 327 if (mn->ttls[i] != 0) 328 found = 1; 329 } 330 331 if (mfc_insert(mn) == 0) { 332 rde_imsg_compose_parent(IMSG_MFC_ADD, 0, nmfc, 333 sizeof(*nmfc)); 334 } 335 336 evtimer_set(&mn->expiration_timer, mfc_expire_timer, mn); 337 evtimer_set(&mn->prune_timer, mfc_expire_timer, mn); 338 mfc_start_expire_timer(mn); 339 340 if (!found) { 341 /* We removed all downstream interfaces, 342 start the pruning process */ 343 rn = rt_match_origin(mn->origin.s_addr); 344 if (rn == NULL) { 345 fatal("mfc_update: cannot find information " 346 " about source"); 347 } 348 349 mfc_send_prune(rn, mn); 350 } 351 } 352 } 353 354 void 355 mfc_delete(struct mfc *nmfc) 356 { 357 struct mfc_node *mn; 358 359 if ((mn = mfc_find(nmfc->origin.s_addr, nmfc->group.s_addr)) == NULL) 360 return; 361 362 /* XXX decide if it should really be removed */ 363 mfc_remove(mn); 364 365 /* XXX notify parent */ 366 } 367 368 int 369 mfc_check_members(struct rt_node *rn, struct iface *iface) 370 { 371 struct mfc_node *mn; 372 373 RB_FOREACH(mn, mfc_tree, &mfc) { 374 if (mn->origin.s_addr == rn->prefix.s_addr) { 375 if (rde_group_list_find(iface, mn->group) != 0) 376 return (1); 377 } 378 } 379 380 return (0); 381 } 382 383 void 384 mfc_recv_prune(struct prune *p) 385 { 386 struct rt_node *rn; 387 struct mfc_node *mn; 388 struct prune_node *pn; 389 struct iface *iface; 390 struct mfc m; 391 392 iface = if_find_index(p->ifindex); 393 if (iface == NULL) { 394 log_debug("mfc_recv_prune: unknown interface"); 395 return; 396 } 397 398 rn = rt_match_origin(p->origin.s_addr); 399 if (rn == NULL) { 400 log_debug("mfc_recv_prune: no information for %s\n", 401 inet_ntoa(p->origin)); 402 return; 403 } 404 405 if (srt_find_ds(rn, p->nexthop.s_addr) == NULL) { 406 log_debug("mfc_recv_prune: prune received from a " 407 "non downstream neighbor\n"); 408 return; 409 } 410 411 mn = mfc_find(p->origin.s_addr, p->group.s_addr); 412 if (mn) { 413 log_debug("mfc_recv_prune: no information for %s\n", 414 inet_ntoa(p->origin)); 415 return; 416 } 417 418 pn = mfc_find_prune(mn, p); 419 if (pn == NULL) { 420 mfc_add_prune(mn, p); 421 if (prune_compare(mn, rn, p->ifindex) && 422 !rde_group_list_find(iface, p->group)) { 423 mn->ttls[p->ifindex] = 0; 424 425 m.ifindex = p->ifindex; 426 m.origin.s_addr = p->origin.s_addr; 427 m.group.s_addr = p->group.s_addr; 428 mfc_update(&m); 429 } 430 } else 431 mfc_reset_prune_expire_timer(pn); 432 } 433 434 void 435 mfc_add_prune(struct mfc_node *mn, struct prune *p) 436 { 437 struct prune_node *pn; 438 struct timeval tv; 439 440 pn = calloc(1, sizeof(struct prune)); 441 if (pn == NULL) 442 fatal("prune_add"); 443 444 timerclear(&tv); 445 tv.tv_sec = MAX_PRUNE_LIFETIME; 446 447 pn->nbr.s_addr = p->nexthop.s_addr; 448 pn->ifindex = p->ifindex; 449 pn->parent = mn; 450 451 evtimer_set(&pn->lifetime_timer, prune_expire_timer, pn); 452 evtimer_add(&pn->lifetime_timer, &tv); 453 454 LIST_INSERT_HEAD(&mn->prune_list, pn, entry); 455 456 mn->prune_cnt[p->ifindex]++; 457 } 458 459 struct prune_node * 460 mfc_find_prune(struct mfc_node *mn, struct prune *p) 461 { 462 struct prune_node *pn; 463 464 LIST_FOREACH(pn, &mn->prune_list, entry) { 465 if (p->nexthop.s_addr == pn->nbr.s_addr) 466 return (pn); 467 } 468 469 return (NULL); 470 } 471 472 void 473 mfc_delete_prune(struct mfc_node *mn, struct prune_node *pn) 474 { 475 unsigned int ifindex = pn->ifindex; 476 477 if (evtimer_pending(&pn->lifetime_timer, NULL)) 478 if (evtimer_del(&pn->lifetime_timer) == -1) 479 fatal("mfc_delete_prune"); 480 481 LIST_REMOVE(pn, entry); 482 free(pn); 483 mn->prune_cnt[ifindex]--; 484 } 485 486 int 487 prune_compare(struct mfc_node *mn, struct rt_node *rn, int ifindex) 488 { 489 if (mn->prune_cnt[ifindex] == rn->ds_cnt[ifindex]) 490 return (1); 491 492 return (0); 493 } 494 495 int 496 mfc_reset_prune_expire_timer(struct prune_node *pn) 497 { 498 struct timeval tv; 499 500 timerclear(&tv); 501 tv.tv_sec = MAX_PRUNE_LIFETIME; 502 503 return (evtimer_add(&pn->lifetime_timer, &tv)); 504 } 505 506 void 507 prune_expire_timer(int fd, short event, void *arg) 508 { 509 struct prune_node *pn = arg; 510 511 LIST_REMOVE(pn, entry); 512 513 pn->parent->prune_cnt[pn->ifindex]--; 514 pn->parent->ttls[pn->ifindex] = 1; 515 516 free(pn); 517 } 518