1: /*
2: * Copyright (c) 1998-2001
3: * University of Southern California/Information Sciences Institute.
4: * All rights reserved.
5: *
6: * Redistribution and use in source and binary forms, with or without
7: * modification, are permitted provided that the following conditions
8: * are met:
9: * 1. Redistributions of source code must retain the above copyright
10: * notice, this list of conditions and the following disclaimer.
11: * 2. Redistributions in binary form must reproduce the above copyright
12: * notice, this list of conditions and the following disclaimer in the
13: * documentation and/or other materials provided with the distribution.
14: * 3. Neither the name of the project nor the names of its contributors
15: * may be used to endorse or promote products derived from this software
16: * without specific prior written permission.
17: *
18: * THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND
19: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21: * ARE DISCLAIMED. IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE
22: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28: * SUCH DAMAGE.
29: */
30: /*
31: * $Id: mrt.c,v 1.1.1.1 2017/06/12 07:59:37 misho Exp $
32: */
33:
34:
35: #include "defs.h"
36:
37:
38: srcentry_t *srclist;
39: grpentry_t *grplist;
40:
41: /*
42: * Local functions definition
43: */
44: static srcentry_t *create_srcentry (uint32_t);
45: static int search_srclist (uint32_t, srcentry_t **);
46: static int search_srcmrtlink (srcentry_t *, uint32_t, mrtentry_t **);
47: static void insert_srcmrtlink (mrtentry_t *, mrtentry_t *, srcentry_t *);
48:
49: static grpentry_t *create_grpentry (uint32_t);
50: static int search_grplist (uint32_t, grpentry_t **);
51: static int search_grpmrtlink (grpentry_t *, uint32_t, mrtentry_t **);
52: static void insert_grpmrtlink (mrtentry_t *, mrtentry_t *, grpentry_t *);
53:
54: static mrtentry_t *alloc_mrtentry (srcentry_t *, grpentry_t *);
55: static mrtentry_t *create_mrtentry (srcentry_t *, grpentry_t *, uint16_t);
56:
57: static void move_kernel_cache (mrtentry_t *, uint16_t);
58:
59:
60: void init_pim_mrt(void)
61: {
62: /* TODO: delete any existing routing table */
63:
64: /* Initialize the source list */
65: /* The first entry has address 'INADDR_ANY' and is not used */
66: /* The order is the smallest address first. */
67: srclist = (srcentry_t *)calloc(1, sizeof(srcentry_t));
68: if (!srclist)
69: logit(LOG_ERR, 0, "Ran out of memory in init_pim_mrt()");
70: srclist->next = NULL;
71: srclist->prev = NULL;
72: srclist->address = INADDR_ANY_N;
73: srclist->mrtlink = NULL;
74: srclist->incoming = NO_VIF;
75: srclist->upstream = NULL;
76: srclist->metric = 0;
77: srclist->preference = 0;
78: RESET_TIMER(srclist->timer);
79: srclist->cand_rp = NULL;
80:
81: /* Initialize the group list */
82: /* The first entry has address 'INADDR_ANY' and is not used */
83: /* The order is the smallest address first. */
84: grplist = (grpentry_t *)calloc(1, sizeof(grpentry_t));
85: if (!grplist)
86: logit(LOG_ERR, 0, "Ran out of memory in init_pim_mrt()");
87: grplist->next = NULL;
88: grplist->prev = NULL;
89: grplist->rpnext = NULL;
90: grplist->rpprev = NULL;
91: grplist->group = INADDR_ANY_N;
92: grplist->rpaddr = INADDR_ANY_N;
93: grplist->mrtlink = NULL;
94: grplist->active_rp_grp = NULL;
95: grplist->grp_route = NULL;
96: }
97:
98:
99: grpentry_t *find_group(uint32_t group)
100: {
101: grpentry_t *grp;
102:
103: if (!IN_MULTICAST(ntohl(group)))
104: return NULL;
105:
106: if (search_grplist(group, &grp) == TRUE)
107: return grp; /* Group found! */
108:
109: return NULL;
110: }
111:
112:
113: srcentry_t *find_source(uint32_t source)
114: {
115: srcentry_t *src;
116:
117: if (!inet_valid_host(source))
118: return NULL;
119:
120: if (search_srclist(source, &src) == TRUE)
121: return src; /* Source found! */
122:
123: return NULL;
124: }
125:
126:
127: mrtentry_t *find_route(uint32_t source, uint32_t group, uint16_t flags, char create)
128: {
129: srcentry_t *src = NULL;
130: grpentry_t *grp = NULL;
131: mrtentry_t *mrt = NULL;
132: mrtentry_t *mrt_wc = NULL;
133: mrtentry_t *mrt_pmbr = NULL;
134: mrtentry_t *mrt2 = NULL;
135: rpentry_t *rp = NULL;
136: rp_grp_entry_t *rp_grp = NULL;
137:
138: if (flags & (MRTF_SG | MRTF_WC)) {
139: if (!IN_MULTICAST(ntohl(group))) {
140: logit(LOG_WARNING, 0, "find_route: Not a multicast group address (%s) ...",
141: inet_fmt(group, s1, sizeof(s1)));
142: return NULL;
143: }
144: }
145:
146: if (flags & MRTF_SG) {
147: if (!inet_valid_host(source) && !IN_PIM_SSM_RANGE(group)) {
148: logit(LOG_WARNING, 0, "find_route: Not a valid host (%s) ...",
149: inet_fmt(source, s1, sizeof(s1)));
150: return NULL;
151: }
152: }
153:
154: if (create == DONT_CREATE) {
155: if (flags & (MRTF_SG | MRTF_WC)) {
156: if (search_grplist(group, &grp) == FALSE) {
157: /* Group not found. Return the (*,*,RP) entry */
158: if (flags & MRTF_PMBR) {
159: rp = rp_match(group);
160: if (rp) {
161: logit(LOG_DEBUG, 0 , "find_route: Group not found. Return the (*,*,RP) entry");
162: return rp->mrtlink;
163: }
164: }
165:
166: logit(LOG_DEBUG, 0 , "find_route: Not PMBR, return NULL");
167: return NULL;
168: }
169:
170: /* Search for the source */
171: if (flags & MRTF_SG) {
172: if (search_grpmrtlink(grp, source, &mrt) == TRUE) {
173: /* Exact (S,G) entry found */
174: logit(LOG_DEBUG, 0 , "find_route: exact (S,G) entry found");
175: return mrt;
176: }
177:
178: logit(LOG_DEBUG, 0 , "find_route:(S,G) entry not found");
179: }
180:
181: /* No (S,G) entry. Return the (*,G) entry (if exist) */
182: if ((flags & MRTF_WC) && grp->grp_route) {
183: logit(LOG_DEBUG, 0 , "find_route: No (S,G) entry. Return the (*,G) entry");
184: return grp->grp_route;
185: }
186: }
187:
188: /* Return the (*,*,RP) entry */
189: if (flags & MRTF_PMBR) {
190: rp = NULL;
191: if (group != INADDR_ANY_N)
192: rp = rp_match(group);
193: else if (source != INADDR_ANY_N)
194: rp = rp_find(source);
195:
196: if (rp) {
197: logit(LOG_DEBUG, 0 , "find_route: Return the (*,*,RP) entry");
198: return rp->mrtlink;
199: }
200: }
201:
202: logit(LOG_DEBUG, 0 , "find_route: No SG|WC, return NULL");
203: return NULL;
204: }
205:
206:
207: /* Creation allowed */
208:
209: if (flags & (MRTF_SG | MRTF_WC)) {
210: grp = create_grpentry(group);
211: if (!grp)
212: return NULL;
213:
214: if (IN_PIM_SSM_RANGE(group)) {
215: if (rp_match(group) == (rpentry_t *) NULL) {
216: /* For SSM, virtual RP entry has to be created. RP is at local link 169.254.0.1
217: to be sure not to send any register messages outside, although sending them
218: has been disabled for SSM also in PIM protocol.
219: The address does not need to be really configured in any interface.
220: TODO: Avoid need for virtual RP by implementing SSM-specific state structures */
221: add_rp_grp_entry(&cand_rp_list, &grp_mask_list, 0x0100fea9, 20, 90, group,
222: 0xffffffff, curr_bsr_hash_mask, curr_bsr_fragment_tag);
223: }
224: }
225:
226: if (!grp->active_rp_grp) {
227: rp_grp = rp_grp_match(group);
228: if (!rp_grp) {
229: if (!grp->mrtlink && !grp->grp_route)
230: /* New created grpentry. Delete it. */
231: delete_grpentry(grp);
232:
233: return NULL;
234: }
235:
236: rp = rp_grp->rp->rpentry;
237: grp->active_rp_grp = rp_grp;
238: grp->rpaddr = rp->address;
239:
240: /* Link to the top of the rp_grp_chain */
241: grp->rpnext = rp_grp->grplink;
242: rp_grp->grplink = grp;
243: if (grp->rpnext)
244: grp->rpnext->rpprev = grp;
245: } else {
246: rp = grp->active_rp_grp->rp->rpentry;
247: }
248: }
249:
250: mrt_wc = mrt_pmbr = NULL;
251:
252: if (flags & MRTF_WC) {
253: /* Setup the (*,G) routing entry */
254: mrt_wc = create_mrtentry(NULL, grp, MRTF_WC);
255: if (!mrt_wc) {
256: if (!grp->mrtlink)
257: /* New created grpentry. Delete it. */
258: delete_grpentry(grp);
259:
260: return NULL;
261: }
262:
263: if (mrt_wc->flags & MRTF_NEW) {
264: mrt_pmbr = rp->mrtlink;
265:
266: /* Copy the oif list from the (*,*,RP) entry */
267: if (mrt_pmbr)
268: VOIF_COPY(mrt_pmbr, mrt_wc);
269:
270: mrt_wc->incoming = rp->incoming;
271: mrt_wc->upstream = rp->upstream;
272: mrt_wc->metric = rp->metric;
273: mrt_wc->preference = rp->preference;
274: move_kernel_cache(mrt_wc, 0);
275: #ifdef RSRR
276: rsrr_cache_bring_up(mrt_wc);
277: #endif /* RSRR */
278: }
279:
280: if (!(flags & MRTF_SG))
281: return mrt_wc;
282: }
283:
284: if (flags & MRTF_SG) {
285: /* Setup the (S,G) routing entry */
286: src = create_srcentry(source);
287: if (!src) {
288: /* TODO: XXX: The MRTF_NEW flag check may be misleading?? check */
289: if ((!grp->grp_route || (grp->grp_route && (grp->grp_route->flags & MRTF_NEW)))
290: && !grp->mrtlink) {
291: /* New created grpentry. Delete it. */
292: delete_grpentry(grp);
293: }
294:
295: return NULL;
296: }
297:
298: mrt = create_mrtentry(src, grp, MRTF_SG);
299: if (!mrt) {
300: if ((!grp->grp_route
301: || (grp->grp_route && (grp->grp_route->flags & MRTF_NEW)))
302: && !grp->mrtlink) {
303: /* New created grpentry. Delete it. */
304: delete_grpentry(grp);
305: }
306:
307: if (!src->mrtlink)
308: /* New created srcentry. Delete it. */
309: delete_srcentry(src);
310:
311: return NULL;
312: }
313:
314: if (mrt->flags & MRTF_NEW) {
315: mrt2 = grp->grp_route;
316: if (!mrt2)
317: mrt2 = rp->mrtlink;
318:
319: /* Copy the oif list from the existing (*,G) or (*,*,RP) entry */
320: if (mrt2) {
321: VOIF_COPY(mrt2, mrt);
322: if (flags & MRTF_RP) {
323: /* ~(S,G) prune entry */
324: mrt->incoming = mrt2->incoming;
325: mrt->upstream = mrt2->upstream;
326: mrt->metric = mrt2->metric;
327: mrt->preference = mrt2->preference;
328: mrt->flags |= MRTF_RP;
329: }
330: }
331:
332: if (!(mrt->flags & MRTF_RP)) {
333: mrt->incoming = src->incoming;
334: mrt->upstream = src->upstream;
335: mrt->metric = src->metric;
336: mrt->preference = src->preference;
337: }
338: move_kernel_cache(mrt, 0);
339: #ifdef RSRR
340: rsrr_cache_bring_up(mrt);
341: #endif /* RSRR */
342: }
343:
344: return mrt;
345: }
346:
347: if (flags & MRTF_PMBR) {
348: /* Get/return the (*,*,RP) routing entry */
349: if (group != INADDR_ANY_N)
350: rp = rp_match(group);
351: else if (source != INADDR_ANY_N)
352: rp = rp_find(source);
353: else
354: return NULL; /* source == group == INADDR_ANY */
355:
356: if (!rp)
357: return NULL;
358:
359: if (rp->mrtlink)
360: return rp->mrtlink;
361:
362: mrt = create_mrtentry(rp, NULL, MRTF_PMBR);
363: if (!mrt)
364: return NULL;
365:
366: mrt->incoming = rp->incoming;
367: mrt->upstream = rp->upstream;
368: mrt->metric = rp->metric;
369: mrt->preference = rp->preference;
370:
371: return mrt;
372: }
373:
374: return NULL;
375: }
376:
377:
378: void delete_srcentry(srcentry_t *src)
379: {
380: mrtentry_t *node;
381: mrtentry_t *next;
382:
383: if (!src)
384: return;
385:
386: /* TODO: XXX: the first entry is unused and always there */
387: src->prev->next = src->next;
388: if (src->next)
389: src->next->prev = src->prev;
390:
391: for (node = src->mrtlink; node; node = next) {
392: next = node->srcnext;
393: if (node->flags & MRTF_KERNEL_CACHE)
394: /* Delete the kernel cache first */
395: delete_mrtentry_all_kernel_cache(node);
396:
397: if (node->grpprev) {
398: node->grpprev->grpnext = node->grpnext;
399: } else {
400: node->group->mrtlink = node->grpnext;
401: if (!node->grpnext && !node->group->grp_route)
402: /* Delete the group entry if it has no (*,G) routing entry */
403: delete_grpentry(node->group);
404: }
405:
406: if (node->grpnext)
407: node->grpnext->grpprev = node->grpprev;
408:
409: FREE_MRTENTRY(node);
410: }
411:
412: free(src);
413: }
414:
415:
416: void delete_grpentry(grpentry_t *grp)
417: {
418: mrtentry_t *node;
419: mrtentry_t *next;
420:
421: if (!grp)
422: return;
423:
424: /* TODO: XXX: the first entry is unused and always there */
425: grp->prev->next = grp->next;
426: if (grp->next)
427: grp->next->prev = grp->prev;
428:
429: if (grp->grp_route) {
430: if (grp->grp_route->flags & MRTF_KERNEL_CACHE)
431: delete_mrtentry_all_kernel_cache(grp->grp_route);
432: FREE_MRTENTRY(grp->grp_route);
433: }
434:
435: /* Delete from the rp_grp_entry chain */
436: if (grp->active_rp_grp) {
437: if (grp->rpnext)
438: grp->rpnext->rpprev = grp->rpprev;
439:
440: if (grp->rpprev)
441: grp->rpprev->rpnext = grp->rpnext;
442: else
443: grp->active_rp_grp->grplink = grp->rpnext;
444: }
445:
446: for (node = grp->mrtlink; node; node = next) {
447: next = node->grpnext;
448: if (node->flags & MRTF_KERNEL_CACHE)
449: /* Delete the kernel cache first */
450: delete_mrtentry_all_kernel_cache(node);
451:
452: if (node->srcprev) {
453: node->srcprev->srcnext = node->srcnext;
454: } else {
455: node->source->mrtlink = node->srcnext;
456: if (!node->srcnext) {
457: /* Delete the srcentry if this was the last routing entry */
458: delete_srcentry(node->source);
459: }
460: }
461:
462: if (node->srcnext)
463: node->srcnext->srcprev = node->srcprev;
464:
465: FREE_MRTENTRY(node);
466: }
467:
468: free(grp);
469: }
470:
471:
472: void delete_mrtentry(mrtentry_t *mrt)
473: {
474: grpentry_t *grp;
475: mrtentry_t *mrt_wc;
476: mrtentry_t *mrt_rp;
477:
478: if (!mrt)
479: return;
480:
481: /* Delete the kernel cache first */
482: if (mrt->flags & MRTF_KERNEL_CACHE)
483: delete_mrtentry_all_kernel_cache(mrt);
484:
485: #ifdef RSRR
486: /* Tell the reservation daemon */
487: rsrr_cache_clean(mrt);
488: #endif /* RSRR */
489:
490: if (mrt->flags & MRTF_PMBR) {
491: /* (*,*,RP) mrtentry */
492: mrt->source->mrtlink = NULL;
493: } else if (mrt->flags & MRTF_SG) {
494: /* (S,G) mrtentry */
495:
496: /* Delete from the grpentry MRT chain */
497: if (mrt->grpprev) {
498: mrt->grpprev->grpnext = mrt->grpnext;
499: } else {
500: mrt->group->mrtlink = mrt->grpnext;
501: if (!mrt->grpnext) {
502: /* All (S,G) MRT entries are gone. Allow creating (*,G) MFC entries. */
503: mrt_rp = mrt->group->active_rp_grp->rp->rpentry->mrtlink;
504: mrt_wc = mrt->group->grp_route;
505: if (mrt_rp)
506: mrt_rp->flags &= ~MRTF_MFC_CLONE_SG;
507:
508: if (mrt_wc)
509: mrt_wc->flags &= ~MRTF_MFC_CLONE_SG;
510: else
511: /* Delete the group entry if it has no (*,G) routing entry */
512: delete_grpentry(mrt->group);
513: }
514: }
515:
516: if (mrt->grpnext)
517: mrt->grpnext->grpprev = mrt->grpprev;
518:
519: /* Delete from the srcentry MRT chain */
520: if (mrt->srcprev) {
521: mrt->srcprev->srcnext = mrt->srcnext;
522: } else {
523: mrt->source->mrtlink = mrt->srcnext;
524: if (!mrt->srcnext)
525: /* Delete the srcentry if this was the last routing entry */
526: delete_srcentry(mrt->source);
527: }
528:
529: if (mrt->srcnext)
530: mrt->srcnext->srcprev = mrt->srcprev;
531: } else {
532: /* This mrtentry should be (*,G) */
533: grp = mrt->group;
534: grp->grp_route = NULL;
535:
536: /* Delete the group entry if it has no (S,G) entries */
537: if (!grp->mrtlink)
538: delete_grpentry(grp);
539: }
540:
541: FREE_MRTENTRY(mrt);
542: }
543:
544:
545: static int search_srclist(uint32_t source, srcentry_t **found)
546: {
547: srcentry_t *prev, *node;
548: uint32_t source_h = ntohl(source);
549:
550: for (prev = srclist, node = prev->next; node; prev = node, node = node->next) {
551: /* The srclist is ordered with the smallest addresses first.
552: * The first entry is not used. */
553: if (ntohl(node->address) < source_h)
554: continue;
555:
556: if (node->address == source) {
557: *found = node;
558: return TRUE;
559: }
560: break;
561: }
562:
563: *found = prev; /* The insertion point is between s_prev and s */
564:
565: return FALSE;
566: }
567:
568:
569: static int search_grplist(uint32_t group, grpentry_t **found)
570: {
571: grpentry_t *prev, *node;
572: uint32_t group_h = ntohl(group);
573:
574: for (prev = grplist, node = prev->next; node; prev = node, node = node->next) {
575: /* The grplist is ordered with the smallest address first.
576: * The first entry is not used. */
577: if (ntohl(node->group) < group_h)
578: continue;
579:
580: if (node->group == group) {
581: *found = node;
582: return TRUE;
583: }
584: break;
585: }
586:
587: *found = prev; /* The insertion point is between prev and g */
588:
589: return FALSE;
590: }
591:
592:
593: static srcentry_t *create_srcentry(uint32_t source)
594: {
595: srcentry_t *node;
596: srcentry_t *prev;
597:
598: if (search_srclist(source, &prev) == TRUE)
599: return prev;
600:
601: node = calloc(1, sizeof(srcentry_t));
602: if (!node) {
603: logit(LOG_WARNING, 0, "Memory allocation error for srcentry %s",
604: inet_fmt(source, s1, sizeof(s1)));
605: return NULL;
606: }
607:
608: node->address = source;
609: /* Free the memory if there is error getting the iif and
610: * the next hop (upstream) router. */
611: if (set_incoming(node, PIM_IIF_SOURCE) == FALSE) {
612: free(node);
613: return NULL;
614: }
615:
616: RESET_TIMER(node->timer);
617: node->mrtlink = NULL;
618: node->cand_rp = NULL;
619: node->next = prev->next;
620: prev->next = node;
621: node->prev = prev;
622: if (node->next)
623: node->next->prev = node;
624:
625: IF_DEBUG(DEBUG_MFC) {
626: logit(LOG_DEBUG, 0, "create source entry, source %s",
627: inet_fmt(source, s1, sizeof(s1)));
628: }
629:
630: return node;
631: }
632:
633:
634: static grpentry_t *create_grpentry(uint32_t group)
635: {
636: grpentry_t *node;
637: grpentry_t *prev;
638:
639: /* If already exists, return it. Otheriwse search_grplist() returns the
640: * insertion point in prev. */
641: if (search_grplist(group, &prev) == TRUE)
642: return prev;
643:
644: node = calloc(1, sizeof(grpentry_t));
645: if (!node) {
646: logit(LOG_WARNING, 0, "Memory allocation error for grpentry %s",
647: inet_fmt(group, s1, sizeof(s1)));
648: return NULL;
649: }
650:
651: /*
652: * TODO: XXX: Note that this is NOT a (*,G) routing entry, but simply
653: * a group entry, probably used to search the routing table (to find
654: * (S,G) entries for example.)
655: * To become (*,G) routing entry, we must setup node->grp_route
656: */
657: node->group = group;
658: node->rpaddr = INADDR_ANY_N;
659: node->mrtlink = NULL;
660: node->active_rp_grp = NULL;
661: node->grp_route = NULL;
662: node->rpnext = NULL;
663: node->rpprev = NULL;
664:
665: /* Now it is safe to include the new group entry */
666: node->next = prev->next;
667: prev->next = node;
668: node->prev = prev;
669: if (node->next)
670: node->next->prev = node;
671:
672: IF_DEBUG(DEBUG_MFC) {
673: logit(LOG_DEBUG, 0, "create group entry, group %s", inet_fmt(group, s1, sizeof(s1)));
674: }
675:
676: return node;
677: }
678:
679:
680: /*
681: * Return TRUE if the entry is found and then *found is set to point to
682: * that entry. Otherwise return FALSE and *found points the previous
683: * entry, or NULL if first in the chain.
684: */
685: static int search_srcmrtlink(srcentry_t *src, uint32_t group, mrtentry_t **found)
686: {
687: mrtentry_t *node;
688: mrtentry_t *prev = NULL;
689: uint32_t group_h = ntohl(group);
690:
691: for (node = src->mrtlink; node; prev = node, node = node->srcnext) {
692: /* The entries are ordered with the smaller group address first.
693: * The addresses are in network order. */
694: if (ntohl(node->group->group) < group_h)
695: continue;
696:
697: if (node->group->group == group) {
698: *found = node;
699: return TRUE;
700: }
701:
702: break;
703: }
704:
705: *found = prev;
706:
707: return FALSE;
708: }
709:
710:
711: /*
712: * Return TRUE if the entry is found and then *found is set to point to
713: * that entry. Otherwise return FALSE and *found points the previous
714: * entry, or NULL if first in the chain.
715: */
716: static int search_grpmrtlink(grpentry_t *grp, uint32_t source, mrtentry_t **found)
717: {
718: mrtentry_t *node;
719: mrtentry_t *prev = NULL;
720: uint32_t source_h = ntohl(source);
721:
722: for (node = grp->mrtlink; node; prev = node, node = node->grpnext) {
723: /* The entries are ordered with the smaller source address first.
724: * The addresses are in network order. */
725: if (ntohl(node->source->address) < source_h)
726: continue;
727:
728: if (source == node->source->address) {
729: *found = node;
730: return TRUE;
731: }
732:
733: break;
734: }
735:
736: *found = prev;
737:
738: return FALSE;
739: }
740:
741:
742: static void insert_srcmrtlink(mrtentry_t *node, mrtentry_t *prev, srcentry_t *src)
743: {
744: if (!prev) {
745: /* Has to be insert as the head entry for this source */
746: node->srcnext = src->mrtlink;
747: node->srcprev = NULL;
748: src->mrtlink = node;
749: } else {
750: /* Insert right after the prev */
751: node->srcnext = prev->srcnext;
752: node->srcprev = prev;
753: prev->srcnext = node;
754: }
755:
756: if (node->srcnext)
757: node->srcnext->srcprev = node;
758: }
759:
760:
761: static void insert_grpmrtlink(mrtentry_t *node, mrtentry_t *prev, grpentry_t *grp)
762: {
763: if (!prev) {
764: /* Has to be insert as the head entry for this group */
765: node->grpnext = grp->mrtlink;
766: node->grpprev = NULL;
767: grp->mrtlink = node;
768: } else {
769: /* Insert right after the prev */
770: node->grpnext = prev->grpnext;
771: node->grpprev = prev;
772: prev->grpnext = node;
773: }
774:
775: if (node->grpnext)
776: node->grpnext->grpprev = node;
777: }
778:
779:
780: static mrtentry_t *alloc_mrtentry(srcentry_t *src, grpentry_t *grp)
781: {
782: mrtentry_t *mrt;
783: uint16_t i, *timer;
784: uint8_t vif_numbers;
785:
786: mrt = calloc(1, sizeof(mrtentry_t));
787: if (!mrt) {
788: logit(LOG_WARNING, 0, "alloc_mrtentry(): out of memory");
789: return NULL;
790: }
791:
792: /*
793: * grpnext, grpprev, srcnext, srcprev will be setup when we link the
794: * mrtentry to the source and group chains
795: */
796: mrt->source = src;
797: mrt->group = grp;
798: mrt->incoming = NO_VIF;
799: VIFM_CLRALL(mrt->joined_oifs);
800: VIFM_CLRALL(mrt->leaves);
801: VIFM_CLRALL(mrt->pruned_oifs);
802: VIFM_CLRALL(mrt->asserted_oifs);
803: VIFM_CLRALL(mrt->oifs);
804: mrt->upstream = NULL;
805: mrt->metric = 0;
806: mrt->preference = 0;
807: mrt->pmbr_addr = INADDR_ANY_N;
808: #ifdef RSRR
809: mrt->rsrr_cache = NULL;
810: #endif /* RSRR */
811:
812: /* XXX: TODO: if we are short in memory, we can reserve as few as possible
813: * space for vif timers (per group and/or routing entry), but then everytime
814: * when a new interfaces is configured, the router will be restarted and
815: * will delete the whole routing table. The "memory is cheap" solution is
816: * to reserve timer space for all potential vifs in advance and then no
817: * need to delete the routing table and disturb the forwarding.
818: */
819: #ifdef SAVE_MEMORY
820: mrt->vif_timers = (uint16_t *)calloc(1, sizeof(uint16_t) * numvifs);
821: mrt->vif_deletion_delay = (uint16_t *)calloc(1, sizeof(uint16_t) * numvifs);
822: vif_numbers = numvifs;
823: #else
824: mrt->vif_timers = (uint16_t *)calloc(1, sizeof(uint16_t) * total_interfaces);
825: mrt->vif_deletion_delay = (uint16_t *)calloc(1, sizeof(uint16_t) * total_interfaces);
826: vif_numbers = total_interfaces;
827: #endif /* SAVE_MEMORY */
828: if (!mrt->vif_timers || !mrt->vif_deletion_delay) {
829: logit(LOG_WARNING, 0, "alloc_mrtentry(): out of memory");
830: FREE_MRTENTRY(mrt);
831: return NULL;
832: }
833:
834: /* Reset the timers */
835: for (i = 0, timer = mrt->vif_timers; i < vif_numbers; i++, timer++)
836: RESET_TIMER(*timer);
837:
838: for (i = 0, timer = mrt->vif_deletion_delay; i < vif_numbers; i++, timer++)
839: RESET_TIMER(*timer);
840:
841: mrt->flags = MRTF_NEW;
842: RESET_TIMER(mrt->timer);
843: RESET_TIMER(mrt->jp_timer);
844: RESET_TIMER(mrt->rs_timer);
845: RESET_TIMER(mrt->assert_timer);
846: RESET_TIMER(mrt->assert_rate_timer);
847: mrt->kernel_cache = NULL;
848:
849: return mrt;
850: }
851:
852:
853: static mrtentry_t *create_mrtentry(srcentry_t *src, grpentry_t *grp, uint16_t flags)
854: {
855: mrtentry_t *node;
856: mrtentry_t *grp_insert, *src_insert; /* pointers to insert */
857: uint32_t source;
858: uint32_t group;
859:
860: if (flags & MRTF_SG) {
861: /* (S,G) entry */
862: source = src->address;
863: group = grp->group;
864:
865: if (search_grpmrtlink(grp, source, &grp_insert) == TRUE)
866: return grp_insert;
867:
868: if (search_srcmrtlink(src, group, &src_insert) == TRUE) {
869: /* Hmmm, search_grpmrtlink() didn't find the entry, but
870: * search_srcmrtlink() did find it! Shouldn't happen. Panic! */
871: logit(LOG_ERR, 0, "MRT inconsistency for src %s and grp %s\n",
872: inet_fmt(source, s1, sizeof(s1)), inet_fmt(group, s2, sizeof(s2)));
873:
874: /* not reached but to make lint happy */
875: return NULL;
876: }
877:
878: /* Create and insert in group mrtlink and source mrtlink chains. */
879: node = alloc_mrtentry(src, grp);
880: if (!node)
881: return NULL;
882:
883: /* node has to be insert right after grp_insert in the grp
884: * mrtlink chain and right after src_insert in the src mrtlink
885: * chain */
886: insert_grpmrtlink(node, grp_insert, grp);
887: insert_srcmrtlink(node, src_insert, src);
888: node->flags |= MRTF_SG;
889:
890: return node;
891: }
892:
893: if (flags & MRTF_WC) {
894: /* (*,G) entry */
895: if (grp->grp_route)
896: return grp->grp_route;
897:
898: node = alloc_mrtentry(src, grp);
899: if (!node)
900: return NULL;
901:
902: grp->grp_route = node;
903: node->flags |= (MRTF_WC | MRTF_RP);
904:
905: return node;
906: }
907:
908: if (flags & MRTF_PMBR) {
909: /* (*,*,RP) entry */
910: if (src->mrtlink)
911: return src->mrtlink;
912:
913: node = alloc_mrtentry(src, grp);
914: if (!node)
915: return NULL;
916:
917: src->mrtlink = node;
918: node->flags |= (MRTF_PMBR | MRTF_RP);
919:
920: return node;
921: }
922:
923: return NULL;
924: }
925:
926:
927: /*
928: * Delete all kernel cache for this mrtentry
929: */
930: void delete_mrtentry_all_kernel_cache(mrtentry_t *mrt)
931: {
932: kernel_cache_t *prev;
933: kernel_cache_t *node;
934:
935: if (!(mrt->flags & MRTF_KERNEL_CACHE))
936: return;
937:
938: /* Free all kernel_cache entries */
939: for (node = mrt->kernel_cache; node; ) {
940: prev = node;
941: node = node->next;
942:
943: logit(LOG_DEBUG, 0, "delete_mrtentry_all_kernel_cache: SG");
944: k_del_mfc(igmp_socket, prev->source, prev->group);
945: free(prev);
946: }
947: mrt->kernel_cache = NULL;
948:
949: /* turn off the cache flag(s) */
950: mrt->flags &= ~(MRTF_KERNEL_CACHE | MRTF_MFC_CLONE_SG);
951: }
952:
953:
954: void delete_single_kernel_cache(mrtentry_t *mrt, kernel_cache_t *node)
955: {
956: if (!mrt || !node)
957: return;
958:
959: if (!node->prev) {
960: mrt->kernel_cache = node->next;
961: if (!mrt->kernel_cache)
962: mrt->flags &= ~(MRTF_KERNEL_CACHE | MRTF_MFC_CLONE_SG);
963: } else {
964: node->prev->next = node->next;
965: }
966:
967: if (node->next)
968: node->next->prev = node->prev;
969:
970: IF_DEBUG(DEBUG_MFC) {
971: logit(LOG_DEBUG, 0, "Deleting MFC entry for source %s and group %s",
972: inet_fmt(node->source, s1, sizeof(s1)),
973: inet_fmt(node->group, s2, sizeof(s2)));
974: }
975:
976: logit(LOG_DEBUG, 0, "delete_single_kernel_cache: SG");
977: k_del_mfc(igmp_socket, node->source, node->group);
978: free(node);
979: }
980:
981:
982: void delete_single_kernel_cache_addr(mrtentry_t *mrt, uint32_t source, uint32_t group)
983: {
984: uint32_t source_h;
985: uint32_t group_h;
986: kernel_cache_t *node;
987:
988: if (!mrt)
989: return;
990:
991: source_h = ntohl(source);
992: group_h = ntohl(group);
993:
994: /* Find the exact (S,G) kernel_cache entry */
995: for (node = mrt->kernel_cache; node; node = node->next) {
996: if (ntohl(node->group) < group_h)
997: continue;
998: if (ntohl(node->group) > group_h)
999: return; /* Not found */
1000: if (ntohl(node->source) < source_h)
1001: continue;
1002: if (ntohl(node->source) > source_h)
1003: return; /* Not found */
1004:
1005: /* Found exact match */
1006: break;
1007: }
1008:
1009: if (!node)
1010: return;
1011:
1012: /* Found. Delete it */
1013: if (!node->prev) {
1014: mrt->kernel_cache = node->next;
1015: if (!mrt->kernel_cache)
1016: mrt->flags &= ~(MRTF_KERNEL_CACHE | MRTF_MFC_CLONE_SG);
1017: } else{
1018: node->prev->next = node->next;
1019: }
1020:
1021: if (node->next)
1022: node->next->prev = node->prev;
1023:
1024: IF_DEBUG(DEBUG_MFC) {
1025: logit(LOG_DEBUG, 0, "Deleting MFC entry for source %s and group %s",
1026: inet_fmt(node->source, s1, sizeof(s1)),
1027: inet_fmt(node->group, s2, sizeof(s2)));
1028: }
1029:
1030: logit(LOG_DEBUG, 0, "delete_single_kernel_cache_addr: SG");
1031: k_del_mfc(igmp_socket, node->source, node->group);
1032: free(node);
1033: }
1034:
1035:
1036: /*
1037: * Installs kernel cache for (source, group). Assumes mrt
1038: * is the correct entry.
1039: */
1040: void add_kernel_cache(mrtentry_t *mrt, uint32_t source, uint32_t group, uint16_t flags)
1041: {
1042: uint32_t source_h;
1043: uint32_t group_h;
1044: kernel_cache_t *next;
1045: kernel_cache_t *prev;
1046: kernel_cache_t *node;
1047:
1048: if (!mrt)
1049: return;
1050:
1051: move_kernel_cache(mrt, flags);
1052:
1053: if (mrt->flags & MRTF_SG) {
1054: /* (S,G) */
1055: if (mrt->flags & MRTF_KERNEL_CACHE)
1056: return;
1057:
1058: node = (kernel_cache_t *)calloc(1, sizeof(kernel_cache_t));
1059: node->next = NULL;
1060: node->prev = NULL;
1061: node->source = source;
1062: node->group = group;
1063: node->sg_count.pktcnt = 0;
1064: node->sg_count.bytecnt = 0;
1065: node->sg_count.wrong_if = 0;
1066: mrt->kernel_cache = node;
1067: mrt->flags |= MRTF_KERNEL_CACHE;
1068:
1069: return;
1070: }
1071:
1072: source_h = ntohl(source);
1073: group_h = ntohl(group);
1074: prev = NULL;
1075:
1076: for (next = mrt->kernel_cache; next; prev = next, next = next->next) {
1077: if (ntohl(next->group) < group_h)
1078: continue;
1079: if (ntohl(next->group) > group_h)
1080: break;
1081: if (ntohl(next->source) < source_h)
1082: continue;
1083: if (ntohl(next->source) > source_h)
1084: break;
1085:
1086: /* Found exact match. Nothing to change. */
1087: return;
1088: }
1089:
1090: /* The new entry must be placed between prev and
1091: * next */
1092: node = calloc(1, sizeof(kernel_cache_t));
1093: if (prev)
1094: prev->next = node;
1095: else
1096: mrt->kernel_cache = node;
1097:
1098: if (next)
1099: next->prev = node;
1100:
1101: node->prev = prev;
1102: node->next = next;
1103: node->source = source;
1104: node->group = group;
1105: node->sg_count.pktcnt = 0;
1106: node->sg_count.bytecnt = 0;
1107: node->sg_count.wrong_if = 0;
1108:
1109: mrt->flags |= MRTF_KERNEL_CACHE;
1110: }
1111:
1112: /*
1113: * Bring the kernel cache "UP": from the (*,*,RP) to (*,G) or (S,G)
1114: */
1115: static void move_kernel_cache(mrtentry_t *mrt, uint16_t flags)
1116: {
1117: kernel_cache_t *node;
1118: kernel_cache_t *insert_node;
1119: kernel_cache_t *first_node;
1120: kernel_cache_t *last_node;
1121: kernel_cache_t *prev_node;
1122: mrtentry_t *mrtentry_pmbr;
1123: mrtentry_t *mrtentry_rp;
1124: uint32_t group_h;
1125: uint32_t source_h;
1126: int found;
1127:
1128: if (!mrt)
1129: return;
1130:
1131: if (mrt->flags & MRTF_PMBR)
1132: return;
1133:
1134: if (mrt->flags & MRTF_WC) {
1135: /* Move the cache info from (*,*,RP) to (*,G) */
1136: group_h = ntohl(mrt->group->group);
1137: mrtentry_pmbr = mrt->group->active_rp_grp->rp->rpentry->mrtlink;
1138: if (!mrtentry_pmbr)
1139: return; /* Nothing to move */
1140:
1141: first_node = last_node = NULL;
1142: for (node = mrtentry_pmbr->kernel_cache; node; node = node->next) {
1143: /*
1144: * The order is: (1) smaller group;
1145: * (2) smaller source within group
1146: */
1147: if (ntohl(node->group) < group_h)
1148: continue;
1149:
1150: if (ntohl(node->group) != group_h)
1151: break;
1152:
1153: /* Select the kernel_cache entries to move */
1154: if (!first_node)
1155: first_node = last_node = node;
1156: else
1157: last_node = node;
1158: }
1159:
1160: if (first_node) {
1161: /* Fix the old chain */
1162: if (first_node->prev)
1163: first_node->prev->next = last_node->next;
1164: else
1165: mrtentry_pmbr->kernel_cache = last_node->next;
1166:
1167: if (last_node->next)
1168: last_node->next->prev = first_node->prev;
1169:
1170: if (!mrtentry_pmbr->kernel_cache)
1171: mrtentry_pmbr->flags &= ~(MRTF_KERNEL_CACHE | MRTF_MFC_CLONE_SG);
1172:
1173: /* Insert in the new place */
1174: prev_node = NULL;
1175: last_node->next = NULL;
1176: mrt->flags |= MRTF_KERNEL_CACHE;
1177:
1178: for (node = mrt->kernel_cache; node; ) {
1179: if (!first_node)
1180: break; /* All entries have been inserted */
1181:
1182: if (ntohl(node->source) > ntohl(first_node->source)) {
1183: /* Insert the entry before node */
1184: insert_node = first_node;
1185: first_node = first_node->next;
1186:
1187: if (node->prev)
1188: node->prev->next = insert_node;
1189: else
1190: mrt->kernel_cache = insert_node;
1191:
1192: insert_node->prev = node->prev;
1193: insert_node->next = node;
1194: node->prev = insert_node;
1195: }
1196: prev_node = node;
1197: node = node->next;
1198: }
1199:
1200: if (first_node) {
1201: /* Place all at the end after prev_node */
1202: if (prev_node)
1203: prev_node->next = first_node;
1204: else
1205: mrt->kernel_cache = first_node;
1206:
1207: first_node->prev = prev_node;
1208: }
1209: }
1210:
1211: return;
1212: }
1213:
1214: if (mrt->flags & MRTF_SG) {
1215: logit(LOG_DEBUG, 0, "move_kernel_cache: SG");
1216: /* (S,G) entry. Move the whole group cache from (*,*,RP) to (*,G) and
1217: * then get the necessary entry from (*,G).
1218: * TODO: Not optimized! The particular entry is moved first to (*,G),
1219: * then we have to search again (*,G) to find it and move to (S,G).
1220: */
1221: /* TODO: XXX: No need for this? Thinking.... */
1222: /* move_kernel_cache(mrt->group->grp_route, flags); */
1223: mrtentry_rp = mrt->group->grp_route;
1224: if (!mrtentry_rp) {
1225: mrtentry_rp = mrt->group->active_rp_grp->rp->rpentry->mrtlink;
1226: if (!mrtentry_rp)
1227: return;
1228: }
1229:
1230: if (mrtentry_rp->incoming != mrt->incoming) {
1231: /* XXX: the (*,*,RP) (or (*,G)) iif is different from the
1232: * (S,G) iif. No need to move the cache, because (S,G) don't
1233: * need it. After the first packet arrives on the shortest path,
1234: * the correct cache entry will be created.
1235: * If (flags & MFC_MOVE_FORCE) then we must move the cache.
1236: * This usually happens when switching to the shortest path.
1237: * The calling function will immediately call k_chg_mfc()
1238: * to modify the kernel cache.
1239: */
1240: if (!(flags & MFC_MOVE_FORCE))
1241: return;
1242: }
1243:
1244: /* Find the exact entry */
1245: source_h = ntohl(mrt->source->address);
1246: group_h = ntohl(mrt->group->group);
1247: found = FALSE;
1248: for (node = mrtentry_rp->kernel_cache; node; node = node->next) {
1249: if (ntohl(node->group) < group_h)
1250: continue;
1251:
1252: if (ntohl(node->group) > group_h)
1253: break;
1254:
1255: if (ntohl(node->source) < source_h)
1256: continue;
1257:
1258: if (ntohl(node->source) > source_h)
1259: break;
1260:
1261: /* We found it! */
1262: if (node->prev)
1263: node->prev->next = node->next;
1264: else
1265: mrtentry_rp->kernel_cache = node->next;
1266:
1267: if (node->next)
1268: node->next->prev = node->prev;
1269:
1270: found = TRUE;
1271:
1272: break;
1273: }
1274:
1275: if (found == TRUE) {
1276: if (!mrtentry_rp->kernel_cache)
1277: mrtentry_rp->flags &= ~(MRTF_KERNEL_CACHE | MRTF_MFC_CLONE_SG);
1278:
1279: if (mrt->kernel_cache)
1280: free(mrt->kernel_cache);
1281:
1282: mrt->flags |= MRTF_KERNEL_CACHE;
1283: mrt->kernel_cache = node;
1284:
1285: node->prev = NULL;
1286: node->next = NULL;
1287: }
1288: }
1289: }
1290:
1291: /**
1292: * Local Variables:
1293: * version-control: t
1294: * indent-tabs-mode: t
1295: * c-file-style: "ellemtel"
1296: * c-basic-offset: 4
1297: * End:
1298: */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to mrt.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / pimd