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