1 /* $OpenBSD: rde_srt.c,v 1.27 2018/09/21 01:33:55 jsg 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
rt_expire_timer(int fd,short event,void * arg)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
rt_start_expire_timer(struct rt_node * rn)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
rt_holddown_timer(int fd,short event,void * arg)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
rt_start_holddown_timer(struct rt_node * rn)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
rt_init(void)130 rt_init(void)
131 {
132 RB_INIT(&rt);
133 }
134
135 int
rt_compare(struct rt_node * a,struct rt_node * b)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 *
rt_find(in_addr_t prefix,u_int8_t prefixlen)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 *
rr_new_rt(struct route_report * rr,u_int32_t adj_metric,int connected)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
rt_insert(struct rt_node * r)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
rt_remove(struct rt_node * r)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 while ((ds_nbr = LIST_FIRST(&r->ds_list)) != NULL) {
229 LIST_REMOVE(ds_nbr, entry);
230 free(ds_nbr);
231 }
232
233 free(r);
234 return (0);
235 }
236
237 void
rt_invalidate(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
rt_clear(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
rt_snap(u_int32_t peerid)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
rt_dump(pid_t pid)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
rt_update(struct rt_node * rn)313 rt_update(struct rt_node *rn)
314 {
315 if (!rn->connected)
316 rt_start_expire_timer(rn);
317 }
318
319 struct rt_node *
rt_match_origin(in_addr_t src)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
srt_check_route(struct route_report * rr,int connected)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 }
411 /* Update forwarder of current interface if necessary and
412 * refresh the route */
413 srt_current_forwarder(rn, iface, rr->metric, nbr_report);
414 rt_update(rn);
415 } else if (rr->metric == INFINITY_METRIC) {
416 if (nbr_report == rn->adv_rtr[ifindex].addr.s_addr)
417 srt_set_forwarder_self(rn, iface);
418 infinity:
419 if (nbr_ip == nbr_report) {
420 if (rn->cost < INFINITY_METRIC)
421 rt_start_holddown_timer(rn);
422 } else
423 if ((ds_nbr = srt_find_ds(rn, nbr_report)))
424 srt_delete_ds(rn, ds_nbr, iface);
425 } else if (INFINITY_METRIC < rr->metric &&
426 rr->metric < 2 * INFINITY_METRIC) {
427 /* Neighbor is reporting his dependency for this source */
428 if (nbr_report == rn->adv_rtr[ifindex].addr.s_addr)
429 srt_set_forwarder_self(rn, iface);
430
431 if (rn->ifindex == ifindex)
432 goto infinity;
433 else
434 if (srt_find_ds(rn, nbr_report) == NULL)
435 srt_add_ds(rn, nbr_report, ifindex);
436 }
437
438 return (0);
439 }
440
441 void
srt_current_forwarder(struct rt_node * rn,struct iface * iface,u_int32_t metric,u_int32_t nbr_report)442 srt_current_forwarder(struct rt_node *rn, struct iface *iface,
443 u_int32_t metric, u_int32_t nbr_report)
444 {
445 struct adv_rtr *adv = &rn->adv_rtr[iface->ifindex];
446
447 if (nbr_report == adv->addr.s_addr) {
448 if (metric > rn->cost || (metric == rn->cost &&
449 iface->addr.s_addr < nbr_report))
450 srt_set_forwarder_self(rn, iface);
451
452 } else {
453 if (metric < adv->metric ||
454 (metric == adv->metric && nbr_report < adv->addr.s_addr))
455 if (adv->addr.s_addr == iface->addr.s_addr)
456 rn->ttls[iface->ifindex] = 0;
457
458 adv->addr.s_addr = nbr_report;
459 adv->metric = metric;
460
461 mfc_update_source(rn);
462 }
463
464 }
465
466 void
srt_update_ds_forwarders(struct rt_node * rn,struct iface * iface,u_int32_t nbr_report)467 srt_update_ds_forwarders(struct rt_node *rn, struct iface *iface,
468 u_int32_t nbr_report)
469 {
470 struct iface *ifa;
471 int i;
472
473 for (i = 0; i < MAXVIFS; i++) {
474 if (rn->adv_rtr[i].addr.s_addr &&
475 (rn->cost < rn->adv_rtr[i].metric ||
476 (rn->cost == rn->adv_rtr[i].metric &&
477 iface->addr.s_addr < nbr_report))) {
478 ifa = if_find_index(i);
479 srt_set_forwarder_self(rn, ifa);
480 }
481 }
482 }
483
484 void
srt_set_forwarder_self(struct rt_node * rn,struct iface * iface)485 srt_set_forwarder_self(struct rt_node *rn, struct iface *iface)
486 {
487 rn->adv_rtr[iface->ifindex].addr.s_addr = iface->addr.s_addr;
488 rn->adv_rtr[iface->ifindex].metric = rn->cost;
489 rn->ttls[iface->ifindex] = 1;
490
491 mfc_update_source(rn);
492 }
493
494 void
srt_set_upstream(struct rt_node * rn,u_int32_t ifindex)495 srt_set_upstream(struct rt_node *rn, u_int32_t ifindex)
496 {
497 if (rn->ifindex != ifindex) {
498 rn->ttls[rn->ifindex] = 1;
499 rn->ifindex = ifindex;
500 }
501
502 mfc_update_source(rn);
503 }
504
505 void
srt_add_ds(struct rt_node * rn,u_int32_t nbr_report,u_int32_t ifindex)506 srt_add_ds(struct rt_node *rn, u_int32_t nbr_report, u_int32_t ifindex)
507 {
508 struct ds_nbr *ds_nbr;
509
510 log_debug("srt_add_ds: adding downstream router for source %s/%d",
511 inet_ntoa(rn->prefix), rn->prefixlen);
512
513 if ((ds_nbr = malloc(sizeof(struct ds_nbr))) == NULL)
514 fatal("srt_add_ds");
515
516 ds_nbr->addr.s_addr = nbr_report;
517
518 LIST_INSERT_HEAD(&rn->ds_list, ds_nbr, entry);
519 rn->ds_cnt[ifindex]++;
520 rn->ttls[ifindex] = 1;
521
522 mfc_update_source(rn);
523 }
524
525 struct ds_nbr *
srt_find_ds(struct rt_node * rn,u_int32_t nbr_report)526 srt_find_ds(struct rt_node *rn, u_int32_t nbr_report)
527 {
528 struct ds_nbr *ds_nbr;
529
530 LIST_FOREACH(ds_nbr, &rn->ds_list, entry)
531 if (ds_nbr->addr.s_addr == nbr_report)
532 return (ds_nbr);
533
534 return (NULL);
535 }
536
537 void
srt_delete_ds(struct rt_node * rn,struct ds_nbr * ds_nbr,struct iface * iface)538 srt_delete_ds(struct rt_node *rn, struct ds_nbr *ds_nbr, struct iface *iface)
539 {
540 log_debug("srt_delete_ds: deleting downstream router for source %s/%d",
541 inet_ntoa(rn->prefix), rn->prefixlen);
542
543 LIST_REMOVE(ds_nbr, entry);
544 free(ds_nbr);
545 rn->ds_cnt[iface->ifindex]--;
546
547 srt_check_downstream_ifaces(rn, iface);
548 }
549
550 void
srt_check_downstream_ifaces(struct rt_node * rn,struct iface * iface)551 srt_check_downstream_ifaces(struct rt_node *rn, struct iface *iface)
552 {
553 /* We are not the designated forwarder for this source on this
554 interface. Keep things as they currently are */
555 if (rn->adv_rtr[iface->ifindex].addr.s_addr != iface->addr.s_addr)
556 return;
557
558 /* There are still downstream dependent router for this source
559 Keep things as they currently are */
560 if (rn->ds_cnt[iface->ifindex])
561 return;
562
563 /* There are still group members for this source on this iface
564 Keep things as they currently are */
565 if (mfc_check_members(rn, iface))
566 return;
567
568 /* Remove interface from the downstream list */
569 rn->ttls[iface->ifindex] = 0;
570 mfc_update_source(rn);
571 }
572
573 void
srt_expire_nbr(struct in_addr addr,unsigned int ifindex)574 srt_expire_nbr(struct in_addr addr, unsigned int ifindex)
575 {
576 struct ds_nbr *ds;
577 struct rt_node *rn;
578 struct iface *iface;
579
580 iface = if_find_index(ifindex);
581 if (iface == NULL)
582 fatal("srt_expire_nbr: interface not found");
583
584 RB_FOREACH(rn, rt_tree, &rt) {
585 if (rn->adv_rtr[ifindex].addr.s_addr == addr.s_addr) {
586 rn->adv_rtr[ifindex].addr.s_addr =
587 iface->addr.s_addr;
588 rn->adv_rtr[ifindex].metric = rn->cost;
589 /* XXX: delete all routes learned from this nbr */
590 } else if (rn->adv_rtr[ifindex].addr.s_addr ==
591 iface->addr.s_addr) {
592 ds = srt_find_ds(rn, addr.s_addr);
593 if (ds) {
594 srt_delete_ds(rn, ds, iface);
595 srt_check_downstream_ifaces(rn, iface);
596 }
597 }
598 }
599 }
600
601 void
flash_update(struct rt_node * rn)602 flash_update(struct rt_node *rn) {
603 struct route_report rr;
604
605 rr.net = rn->prefix;
606 rr.mask.s_addr = ntohl(prefixlen2mask(rn->prefixlen));
607 rr.metric = rn->cost;
608 rr.ifindex = rn->ifindex;
609 rde_imsg_compose_dvmrpe(IMSG_FLASH_UPDATE, 0, 0, &rr, sizeof(rr));
610 }
611
612 void
flash_update_ds(struct rt_node * rn)613 flash_update_ds(struct rt_node *rn) {
614 struct route_report rr;
615
616 rr.net = rn->prefix;
617 rr.mask.s_addr = ntohl(prefixlen2mask(rn->prefixlen));
618 rr.metric = rn->cost;
619 rr.ifindex = rn->ifindex;
620 rde_imsg_compose_dvmrpe(IMSG_FLASH_UPDATE_DS, 0, 0, &rr, sizeof(rr));
621 }
622