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: #include "defs.h"
32:
33:
34: /*
35: * The hash function. Stollen from Eddy's (eddy@isi.edu)
36: * implementation (for compatibility ;)
37: */
38: #define SEED1 1103515245
39: #define SEED2 12345
40: #define RP_HASH_VALUE(G, M, C) (((SEED1) * (((SEED1) * ((G) & (M)) + (SEED2)) ^ (C)) + (SEED2)) % 0x80000000)
41:
42: cand_rp_t *cand_rp_list;
43: grp_mask_t *grp_mask_list;
44: cand_rp_t *segmented_cand_rp_list;
45: grp_mask_t *segmented_grp_mask_list;
46: uint16_t curr_bsr_fragment_tag;
47: uint8_t curr_bsr_priority;
48: uint32_t curr_bsr_address;
49: uint32_t curr_bsr_hash_mask;
50: uint16_t pim_bootstrap_timer; /* For electing the BSR and
51: * sending Cand-RP-set msgs */
52: uint8_t my_bsr_priority;
53: uint32_t my_bsr_address;
54: uint32_t my_bsr_hash_mask;
55: uint8_t cand_bsr_flag = FALSE; /* Set to TRUE if I am
56: * a candidate BSR */
57: uint32_t my_cand_rp_address;
58: uint8_t my_cand_rp_priority;
59: uint16_t my_cand_rp_holdtime;
60: uint16_t my_cand_rp_adv_period; /* The locally configured
61: * Cand-RP adv. period. */
62: uint16_t pim_cand_rp_adv_timer;
63: uint8_t cand_rp_flag = FALSE; /* Candidate RP flag */
64: struct cand_rp_adv_message_ cand_rp_adv_message;
65: uint32_t rp_my_ipv4_hashmask;
66:
67:
68: /*
69: * Local functions definition.
70: */
71: static cand_rp_t *add_cand_rp (cand_rp_t **used_cand_rp_list, uint32_t address);
72: static grp_mask_t *add_grp_mask (grp_mask_t **used_grp_mask_list,
73: uint32_t group_addr,
74: uint32_t group_mask,
75: uint32_t hash_mask);
76: static void delete_grp_mask_entry (cand_rp_t **used_cand_rp_list,
77: grp_mask_t **used_grp_mask_list,
78: grp_mask_t *grp_mask_delete);
79: static void delete_rp_entry (cand_rp_t **used_cand_rp_list,
80: grp_mask_t **used_grp_mask_list,
81: cand_rp_t *cand_rp_ptr);
82:
83:
84: void init_rp_and_bsr(void)
85: {
86: /* TODO: if the grplist is not NULL, remap all groups ASAP! */
87: delete_rp_list(&cand_rp_list, &grp_mask_list);
88: delete_rp_list(&segmented_cand_rp_list, &segmented_grp_mask_list);
89:
90: if (cand_bsr_flag == FALSE) {
91: /*
92: * If I am not candidat BSR, initialize the "current BSR"
93: * as having the lowest priority.
94: */
95: curr_bsr_fragment_tag = 0;
96: curr_bsr_priority = 0; /* Lowest priority */
97: curr_bsr_address = INADDR_ANY_N; /* Lowest priority */
98: MASKLEN_TO_MASK(RP_DEFAULT_IPV4_HASHMASKLEN, curr_bsr_hash_mask);
99: SET_TIMER(pim_bootstrap_timer, PIM_BOOTSTRAP_TIMEOUT);
100: } else {
101: curr_bsr_fragment_tag = RANDOM();
102: curr_bsr_priority = my_bsr_priority;
103: curr_bsr_address = my_bsr_address;
104: curr_bsr_hash_mask = my_bsr_hash_mask;
105: SET_TIMER(pim_bootstrap_timer, bootstrap_initial_delay());
106: }
107:
108: if (cand_rp_flag != FALSE) {
109: MASKLEN_TO_MASK(RP_DEFAULT_IPV4_HASHMASKLEN, rp_my_ipv4_hashmask);
110: /* Setup the Cand-RP-Adv-Timer */
111: SET_TIMER(pim_cand_rp_adv_timer, RANDOM() % my_cand_rp_adv_period);
112: }
113: }
114:
115:
116: uint16_t bootstrap_initial_delay(void)
117: {
118: uint32_t addr_delay;
119: uint32_t delay;
120: uint32_t log_mask;
121: int32_t log_of_2;
122: uint8_t best_priority;
123:
124: /*
125: * The bootstrap timer initial value (if Cand-BSR).
126: * It depends of the bootstrap router priority:
127: * higher priority has shorter value:
128: *
129: * delay = 5 + 2 * log_2(1 + best_priority - myPriority) + addr_delay;
130: *
131: * best_priority = Max(storedPriority, myPriority);
132: * if (best_priority == myPriority)
133: * addr_delay = log_2(bestAddr - myAddr)/16;
134: * else
135: * addr_delay = 2 - (myAddr/2^31);
136: */
137:
138: best_priority = max(curr_bsr_priority, my_bsr_priority);
139: if (best_priority == my_bsr_priority) {
140: addr_delay = ntohl(curr_bsr_address) - ntohl(my_bsr_address);
141: /* Calculate the integer part of log_2 of (bestAddr - myAddr) */
142: /* To do so, have to find the position number of the first bit
143: * from left which is `1`
144: */
145: log_mask = sizeof(addr_delay) << 3;
146: log_mask = (1 << (log_mask - 1)); /* Set the leftmost bit to `1` */
147: for (log_of_2 = (sizeof(addr_delay) << 3) - 1 ; log_of_2; log_of_2--) {
148: if (addr_delay & log_mask)
149: break;
150:
151: log_mask >>= 1; /* Start shifting `1` on right */
152: }
153: addr_delay = log_of_2 / 16;
154: } else {
155: addr_delay = 2 - (ntohl(my_bsr_address) / ( 1 << 31));
156: }
157:
158: delay = 1 + best_priority - my_bsr_priority;
159: /* Calculate log_2(delay) */
160: log_mask = sizeof(delay) << 3;
161: log_mask = (1 << (log_mask - 1)); /* Set the leftmost bit to `1` */
162: for (log_of_2 = (sizeof(delay) << 3) - 1 ; log_of_2; log_of_2--) {
163: if (delay & log_mask)
164: break;
165:
166: log_mask >>= 1; /* Start shifting `1` on right */
167: }
168:
169: delay = 5 + 2 * log_of_2 + addr_delay;
170:
171: return (uint16_t)delay;
172: }
173:
174:
175: static cand_rp_t *add_cand_rp(cand_rp_t **used_cand_rp_list, uint32_t address)
176: {
177: cand_rp_t *prev = NULL;
178: cand_rp_t *next;
179: cand_rp_t *ptr;
180: rpentry_t *entry;
181: uint32_t addr_h = ntohl(address);
182:
183: /* The ordering is the bigger first */
184: for (next = *used_cand_rp_list; next; prev = next, next = next->next) {
185: if (ntohl(next->rpentry->address) > addr_h)
186: continue;
187:
188: if (next->rpentry->address == address)
189: return next;
190: else
191: break;
192: }
193:
194: /* Create and insert the new entry between prev and next */
195: ptr = (cand_rp_t *)calloc(1, sizeof(cand_rp_t));
196: if (!ptr)
197: logit(LOG_ERR, 0, "Ran out of memory in add_cand_rp()");
198: ptr->rp_grp_next = NULL;
199: ptr->next = next;
200: ptr->prev = prev;
201: if (next)
202: next->prev = ptr;
203: if (prev == NULL)
204: *used_cand_rp_list = ptr;
205: else
206: prev->next = ptr;
207:
208: entry = (rpentry_t *)calloc(1, sizeof(rpentry_t));
209: if (!entry)
210: logit(LOG_ERR, 0, "Ran out of memory in add_cand_rp()");
211: ptr->rpentry = entry;
212: entry->next = NULL;
213: entry->prev = NULL;
214: entry->address = address;
215: entry->mrtlink = NULL;
216: entry->incoming = NO_VIF;
217: entry->upstream = NULL;
218: /* TODO: setup the metric and the preference as ~0 (the lowest)? */
219: entry->metric = ~0;
220: entry->preference = ~0;
221: RESET_TIMER(entry->timer);
222: entry->cand_rp = ptr;
223:
224: /* TODO: XXX: check whether there is a route to that RP: if return value
225: * is FALSE, then no route.
226: */
227: if (local_address(entry->address) == NO_VIF)
228: /* TODO: check for error and delete */
229: set_incoming(entry, PIM_IIF_RP);
230: else
231: /* TODO: XXX: CHECK!!! */
232: entry->incoming = reg_vif_num;
233:
234: return ptr;
235: }
236:
237:
238: static grp_mask_t *add_grp_mask(grp_mask_t **used_grp_mask_list, uint32_t group_addr, uint32_t group_mask, uint32_t hash_mask)
239: {
240: grp_mask_t *prev = NULL;
241: grp_mask_t *next;
242: grp_mask_t *ptr;
243: uint32_t prefix_h = ntohl(group_addr & group_mask);
244:
245: /* The ordering of group_addr is: bigger first */
246: for (next = *used_grp_mask_list; next; prev = next, next = next->next) {
247: if (ntohl(next->group_addr & next->group_mask) > prefix_h)
248: continue;
249:
250: /* The ordering of group_mask is: bigger (longer) first */
251: if ((next->group_addr & next->group_mask) == (group_addr & group_mask)) {
252: if (ntohl(next->group_mask) > ntohl(group_mask))
253: continue;
254: else if (next->group_mask == group_mask)
255: return next;
256: else
257: break;
258: }
259: }
260:
261: ptr = (grp_mask_t *)calloc(1, sizeof(grp_mask_t));
262: if (!ptr)
263: logit(LOG_ERR, 0, "Ran out of memory in add_grp_mask()");
264:
265: ptr->grp_rp_next = (rp_grp_entry_t *)NULL;
266: ptr->next = next;
267: ptr->prev = prev;
268: if (next)
269: next->prev = ptr;
270: if (prev == NULL)
271: *used_grp_mask_list = ptr;
272: else
273: prev->next = ptr;
274:
275: ptr->group_addr = group_addr;
276: ptr->group_mask = group_mask;
277: ptr->hash_mask = hash_mask;
278: ptr->group_rp_number = 0;
279: ptr->fragment_tag = 0;
280:
281: return ptr;
282: }
283:
284:
285: /* TODO: XXX: BUG: a remapping for some groups currently using some other
286: * grp_mask may be required by the addition of the new entry!!!
287: * Remapping all groups might be a costly process...
288: */
289: rp_grp_entry_t *add_rp_grp_entry(cand_rp_t **used_cand_rp_list,
290: grp_mask_t **used_grp_mask_list,
291: uint32_t rp_addr,
292: uint8_t rp_priority,
293: uint16_t rp_holdtime,
294: uint32_t group_addr,
295: uint32_t group_mask,
296: uint32_t bsr_hash_mask,
297: uint16_t fragment_tag)
298: {
299: cand_rp_t *cand_rp_ptr;
300: grp_mask_t *mask_ptr;
301: rpentry_t *rpentry_ptr;
302: rp_grp_entry_t *entry_next;
303: rp_grp_entry_t *entry_new;
304: rp_grp_entry_t *entry_prev = NULL;
305: grpentry_t *grpentry_ptr_prev;
306: grpentry_t *grpentry_ptr_next;
307: uint32_t rp_addr_h;
308: uint8_t old_highest_priority = ~0; /* Smaller value means "higher" */
309:
310: /* Input data verification */
311: if (!inet_valid_host(rp_addr))
312: return NULL;
313: if (!IN_CLASSD(ntohl(group_addr)))
314: return NULL;
315:
316: mask_ptr = add_grp_mask(used_grp_mask_list, group_addr, group_mask, bsr_hash_mask);
317: if (mask_ptr == NULL)
318: return NULL;
319:
320: /* TODO: delete */
321: #if 0
322: if (mask_ptr->grp_rp_next) {
323: /* Check for obsolete grp_rp chain */
324: if ((my_bsr_address != curr_bsr_address) && (mask_ptr->grp_rp_next->fragment_tag != fragment_tag)) {
325: /* This grp_rp chain is obsolete. Delete it. */
326: delete_grp_mask(used_cand_rp_list, used_grp_mask_list, group_addr, group_mask);
327: mask_ptr = add_grp_mask(used_grp_mask_list, group_addr, group_mask, bsr_hash_mask);
328:
329: if (mask_ptr == NULL)
330: return NULL;
331: }
332: }
333: #endif /* 0 */
334:
335: cand_rp_ptr = add_cand_rp(used_cand_rp_list, rp_addr);
336: if (cand_rp_ptr == NULL) {
337: if (mask_ptr->grp_rp_next == NULL)
338: delete_grp_mask(used_cand_rp_list, used_grp_mask_list,
339: group_addr, group_mask);
340: return NULL;
341: }
342:
343: rpentry_ptr = cand_rp_ptr->rpentry;
344: SET_TIMER(rpentry_ptr->timer, rp_holdtime);
345: rp_addr_h = ntohl(rp_addr);
346: mask_ptr->fragment_tag = fragment_tag; /* For garbage collection */
347:
348: entry_prev = NULL;
349: entry_next = mask_ptr->grp_rp_next;
350: /* TODO: improve it */
351: if (entry_next != NULL)
352: old_highest_priority = entry_next->priority;
353: for ( ; entry_next; entry_prev = entry_next,
354: entry_next = entry_next->grp_rp_next) {
355: /* Smaller value means higher priority. The entries are
356: * sorted with the highest priority first.
357: */
358: if (entry_next->priority < rp_priority)
359: continue;
360: if (entry_next->priority > rp_priority)
361: break;
362:
363: /*
364: * Here we don't care about higher/lower addresses, because
365: * higher address does not guarantee higher hash_value,
366: * but anyway we do order with the higher address first,
367: * so it will be easier to find an existing entry and update the
368: * holdtime.
369: */
370: if (ntohl(entry_next->rp->rpentry->address) > rp_addr_h)
371: continue;
372: if (ntohl(entry_next->rp->rpentry->address) < rp_addr_h)
373: break;
374: /* We already have this entry. Update the holdtime */
375: /* TODO: We shoudn't have old existing entry, because with the
376: * current implementation all of them will be deleted
377: * (different fragment_tag). Debug and check and eventually
378: * delete.
379: */
380: entry_next->holdtime = rp_holdtime;
381: entry_next->fragment_tag = fragment_tag;
382:
383: return entry_next;
384: }
385:
386: /* Create and link the new entry */
387: entry_new = (rp_grp_entry_t *)calloc(1, sizeof(rp_grp_entry_t));
388: if (!entry_new)
389: logit(LOG_ERR, 0, "Ran out of memory in add_rp_grp_entry()");
390: entry_new->grp_rp_next = entry_next;
391: entry_new->grp_rp_prev = entry_prev;
392: if (entry_next)
393: entry_next->grp_rp_prev = entry_new;
394: if (entry_prev == NULL)
395: mask_ptr->grp_rp_next = entry_new;
396: else
397: entry_prev->grp_rp_next = entry_new;
398:
399: /*
400: * The rp_grp_entry chain is not ordered, so just plug
401: * the new entry at the head.
402: */
403: entry_new->rp_grp_next = cand_rp_ptr->rp_grp_next;
404: if (cand_rp_ptr->rp_grp_next)
405: cand_rp_ptr->rp_grp_next->rp_grp_prev = entry_new;
406: entry_new->rp_grp_prev = NULL;
407: cand_rp_ptr->rp_grp_next = entry_new;
408:
409: entry_new->holdtime = rp_holdtime;
410: entry_new->fragment_tag = fragment_tag;
411: entry_new->priority = rp_priority;
412: entry_new->group = mask_ptr;
413: entry_new->rp = cand_rp_ptr;
414: entry_new->grplink = NULL;
415:
416: /* If I am BSR candidate and rp_addr is NOT hacked SSM address, then log it */
417: if( cand_bsr_flag && rp_addr != 0x0100fea9 ) {
418: uint32_t mask;
419: MASK_TO_MASKLEN(group_mask, mask);
420: logit(LOG_INFO, 0, "New RP candidate %s for group %s/%d, priority %d",
421: inet_fmt(rp_addr, s1, sizeof(s1)), inet_fmt(group_addr, s2, sizeof(s2)), mask, rp_priority);
422: }
423:
424: mask_ptr->group_rp_number++;
425:
426: if (mask_ptr->grp_rp_next->priority == rp_priority) {
427: /* The first entries are with the best priority. */
428: /* Adding this rp_grp_entry may result in group_to_rp remapping */
429: for (entry_next = mask_ptr->grp_rp_next; entry_next; entry_next = entry_next->grp_rp_next) {
430: if (entry_next->priority > old_highest_priority)
431: break;
432:
433: for (grpentry_ptr_prev = entry_next->grplink; grpentry_ptr_prev; ) {
434: grpentry_ptr_next = grpentry_ptr_prev->rpnext;
435: remap_grpentry(grpentry_ptr_prev);
436: grpentry_ptr_prev = grpentry_ptr_next;
437: }
438: }
439: }
440:
441: return entry_new;
442: }
443:
444:
445: void delete_rp_grp_entry(cand_rp_t **used_cand_rp_list, grp_mask_t **used_grp_mask_list, rp_grp_entry_t *entry)
446: {
447: grpentry_t *ptr;
448: grpentry_t *ptr_next;
449:
450: if (entry == NULL)
451: return;
452: entry->group->group_rp_number--;
453:
454: /* Free the rp_grp* and grp_rp* links */
455: if (entry->rp_grp_prev)
456: entry->rp_grp_prev->rp_grp_next = entry->rp_grp_next;
457: else
458: entry->rp->rp_grp_next = entry->rp_grp_next;
459: if (entry->rp_grp_next)
460: entry->rp_grp_next->rp_grp_prev = entry->rp_grp_prev;
461:
462: if (entry->grp_rp_prev)
463: entry->grp_rp_prev->grp_rp_next = entry->grp_rp_next;
464: else
465: entry->group->grp_rp_next = entry->grp_rp_next;
466:
467: if (entry->grp_rp_next)
468: entry->grp_rp_next->grp_rp_prev = entry->grp_rp_prev;
469:
470: /* Delete Cand-RP or Group-prefix if useless */
471: if (entry->group->grp_rp_next == NULL)
472: delete_grp_mask_entry(used_cand_rp_list, used_grp_mask_list, entry->group);
473:
474: if (entry->rp->rp_grp_next == NULL)
475: delete_rp_entry(used_cand_rp_list, used_grp_mask_list, entry->rp);
476:
477: /* Remap all affected groups */
478: for (ptr = entry->grplink; ptr; ptr = ptr_next) {
479: ptr_next = ptr->rpnext;
480: remap_grpentry(ptr);
481: }
482:
483: free((char *)entry);
484: }
485:
486: /* TODO: XXX: the affected group entries will be partially
487: * setup, because may have group routing entry, but NULL pointers to RP.
488: * After the call to this function, must remap all group entries ASAP.
489: */
490: void delete_rp_list(cand_rp_t **used_cand_rp_list, grp_mask_t **used_grp_mask_list)
491: {
492: cand_rp_t *cand_ptr, *cand_next;
493: rp_grp_entry_t *entry_ptr, *entry_next;
494: grp_mask_t *mask_ptr, *mask_next;
495: grpentry_t *gentry_ptr, *gentry_ptr_next;
496:
497: for (cand_ptr = *used_cand_rp_list; cand_ptr; ) {
498: cand_next = cand_ptr->next;
499:
500: /* Free the mrtentry (if any) for this RP */
501: if (cand_ptr->rpentry->mrtlink) {
502: if (cand_ptr->rpentry->mrtlink->flags & MRTF_KERNEL_CACHE)
503: delete_mrtentry_all_kernel_cache(cand_ptr->rpentry->mrtlink);
504: FREE_MRTENTRY(cand_ptr->rpentry->mrtlink);
505: }
506: free(cand_ptr->rpentry);
507:
508: /* Free the whole chain of entry for this RP */
509: for (entry_ptr = cand_ptr->rp_grp_next; entry_ptr; entry_ptr = entry_next) {
510: entry_next = entry_ptr->rp_grp_next;
511:
512: /* Clear the RP related invalid pointers for all group entries */
513: for (gentry_ptr = entry_ptr->grplink; gentry_ptr; gentry_ptr = gentry_ptr_next) {
514: gentry_ptr_next = gentry_ptr->rpnext;
515: gentry_ptr->rpnext = NULL;
516: gentry_ptr->rpprev = NULL;
517: gentry_ptr->active_rp_grp = NULL;
518: gentry_ptr->rpaddr = INADDR_ANY_N;
519: }
520:
521: free(entry_ptr);
522: }
523:
524: free(cand_ptr);
525: cand_ptr = cand_next;
526: }
527: *used_cand_rp_list = NULL;
528:
529: for (mask_ptr = *used_grp_mask_list; mask_ptr; mask_ptr = mask_next) {
530: mask_next = mask_ptr->next;
531: free(mask_ptr);
532: }
533: *used_grp_mask_list = NULL;
534: }
535:
536:
537: void delete_grp_mask(cand_rp_t **used_cand_rp_list, grp_mask_t **used_grp_mask_list, uint32_t group_addr, uint32_t group_mask)
538: {
539: grp_mask_t *ptr;
540: uint32_t prefix_h = ntohl(group_addr & group_mask);
541:
542: for (ptr = *used_grp_mask_list; ptr; ptr = ptr->next) {
543: if (ntohl(ptr->group_addr & ptr->group_mask) > prefix_h)
544: continue;
545:
546: if (ptr->group_addr == group_addr) {
547: if (ntohl(ptr->group_mask) > ntohl(group_mask))
548: continue;
549: else if (ptr->group_mask == group_mask)
550: break;
551: else
552: return; /* Not found */
553: }
554: }
555:
556: if (ptr == (grp_mask_t *)NULL)
557: return; /* Not found */
558:
559: delete_grp_mask_entry(used_cand_rp_list, used_grp_mask_list, ptr);
560: }
561:
562: static void delete_grp_mask_entry(cand_rp_t **used_cand_rp_list, grp_mask_t **used_grp_mask_list, grp_mask_t *grp_mask_delete)
563: {
564: grpentry_t *grp_ptr, *grp_ptr_next;
565: rp_grp_entry_t *entry_ptr;
566: rp_grp_entry_t *entry_next;
567:
568: if (grp_mask_delete == NULL)
569: return;
570:
571: /* Remove from the grp_mask_list first */
572: if (grp_mask_delete->prev)
573: grp_mask_delete->prev->next = grp_mask_delete->next;
574: else
575: *used_grp_mask_list = grp_mask_delete->next;
576:
577: if (grp_mask_delete->next)
578: grp_mask_delete->next->prev = grp_mask_delete->prev;
579:
580: /* Remove all grp_rp entries for this grp_mask */
581: for (entry_ptr = grp_mask_delete->grp_rp_next; entry_ptr; entry_ptr = entry_next) {
582: entry_next = entry_ptr->grp_rp_next;
583:
584: /* Remap all related grpentry */
585: for (grp_ptr = entry_ptr->grplink; grp_ptr; grp_ptr = grp_ptr_next) {
586: grp_ptr_next = grp_ptr->rpnext;
587: remap_grpentry(grp_ptr);
588: }
589:
590: if (entry_ptr->rp_grp_prev != (rp_grp_entry_t *)NULL)
591: entry_ptr->rp_grp_prev->rp_grp_next = entry_ptr->rp_grp_next;
592: else
593: entry_ptr->rp->rp_grp_next = entry_ptr->rp_grp_next;
594:
595: if (entry_ptr->rp_grp_next != NULL)
596: entry_ptr->rp_grp_next->rp_grp_prev = entry_ptr->rp_grp_prev;
597:
598: /* Delete the RP entry */
599: if (entry_ptr->rp->rp_grp_next == NULL)
600: delete_rp_entry(used_cand_rp_list, used_grp_mask_list, entry_ptr->rp);
601:
602: free(entry_ptr);
603: }
604:
605: free(grp_mask_delete);
606: }
607:
608: /*
609: * TODO: currently not used.
610: */
611: void delete_rp(cand_rp_t **used_cand_rp_list, grp_mask_t **used_grp_mask_list, uint32_t rp_addr)
612: {
613: cand_rp_t *ptr;
614: uint32_t rp_addr_h = ntohl(rp_addr);
615:
616: for(ptr = *used_cand_rp_list; ptr != NULL; ptr = ptr->next) {
617: if (ntohl(ptr->rpentry->address) > rp_addr_h)
618: continue;
619:
620: if (ptr->rpentry->address == rp_addr)
621: break;
622: else
623: return; /* Not found */
624: }
625:
626: if (ptr == NULL)
627: return; /* Not found */
628:
629: delete_rp_entry(used_cand_rp_list, used_grp_mask_list, ptr);
630: }
631:
632:
633: static void delete_rp_entry(cand_rp_t **used_cand_rp_list, grp_mask_t **used_grp_mask_list, cand_rp_t *cand_rp_delete)
634: {
635: rp_grp_entry_t *entry_ptr;
636: rp_grp_entry_t *entry_next;
637: grpentry_t *grp_ptr;
638: grpentry_t *grp_ptr_next;
639:
640: if (cand_rp_delete == NULL)
641: return;
642:
643: /* Remove from the cand-RP chain */
644: if (cand_rp_delete->prev)
645: cand_rp_delete->prev->next = cand_rp_delete->next;
646: else
647: *used_cand_rp_list = cand_rp_delete->next;
648:
649: if (cand_rp_delete->next)
650: cand_rp_delete->next->prev = cand_rp_delete->prev;
651:
652: if (cand_rp_delete->rpentry->mrtlink) {
653: if (cand_rp_delete->rpentry->mrtlink->flags & MRTF_KERNEL_CACHE)
654: delete_mrtentry_all_kernel_cache(cand_rp_delete->rpentry->mrtlink);
655:
656: FREE_MRTENTRY(cand_rp_delete->rpentry->mrtlink);
657: }
658: free ((char *)cand_rp_delete->rpentry);
659:
660: /* Remove all rp_grp entries for this RP */
661: for (entry_ptr = cand_rp_delete->rp_grp_next; entry_ptr; entry_ptr = entry_next) {
662: entry_next = entry_ptr->rp_grp_next;
663: entry_ptr->group->group_rp_number--;
664:
665: /* First take care of the grp_rp chain */
666: if (entry_ptr->grp_rp_prev)
667: entry_ptr->grp_rp_prev->grp_rp_next = entry_ptr->grp_rp_next;
668: else
669: entry_ptr->group->grp_rp_next = entry_ptr->grp_rp_next;
670:
671: if (entry_ptr->grp_rp_next)
672: entry_ptr->grp_rp_next->grp_rp_prev = entry_ptr->grp_rp_prev;
673:
674: if (entry_ptr->grp_rp_next == NULL)
675: delete_grp_mask_entry(used_cand_rp_list, used_grp_mask_list, entry_ptr->group);
676:
677: /* Remap the related groups */
678: for (grp_ptr = entry_ptr->grplink; grp_ptr; grp_ptr = grp_ptr_next) {
679: grp_ptr_next = grp_ptr->rpnext;
680: remap_grpentry(grp_ptr);
681: }
682:
683: free(entry_ptr);
684: }
685:
686: free((char *)cand_rp_delete);
687: }
688:
689:
690: /*
691: * Rehash the RP for the group.
692: * XXX: currently, every time when remap_grpentry() is called, there has
693: * being a good reason to change the RP, so for performancy reasons
694: * no check is performed whether the RP will be really different one.
695: */
696: int remap_grpentry(grpentry_t *grpentry_ptr)
697: {
698: rpentry_t *rpentry_ptr;
699: rp_grp_entry_t *entry_ptr;
700: mrtentry_t *grp_route;
701: mrtentry_t *mrtentry_ptr;
702:
703: if (grpentry_ptr == NULL)
704: return FALSE;
705:
706: /* Remove from the list of all groups matching to the same RP */
707: if (grpentry_ptr->rpprev) {
708: grpentry_ptr->rpprev->rpnext = grpentry_ptr->rpnext;
709: } else {
710: if (grpentry_ptr->active_rp_grp)
711: grpentry_ptr->active_rp_grp->grplink = grpentry_ptr->rpnext;
712: }
713:
714: if (grpentry_ptr->rpnext)
715: grpentry_ptr->rpnext->rpprev = grpentry_ptr->rpprev;
716:
717: entry_ptr = rp_grp_match(grpentry_ptr->group);
718: if (entry_ptr == NULL) {
719: /* If cannot remap, delete the group */
720: delete_grpentry(grpentry_ptr);
721: return FALSE;
722: }
723: rpentry_ptr = entry_ptr->rp->rpentry;
724:
725: /* Add to the new chain of all groups mapping to the same RP */
726: grpentry_ptr->rpaddr = rpentry_ptr->address;
727: grpentry_ptr->active_rp_grp = entry_ptr;
728: grpentry_ptr->rpnext = entry_ptr->grplink;
729: if (grpentry_ptr->rpnext)
730: grpentry_ptr->rpnext->rpprev = grpentry_ptr;
731: grpentry_ptr->rpprev = NULL;
732: entry_ptr->grplink = grpentry_ptr;
733:
734: grp_route = grpentry_ptr->grp_route;
735: if (grp_route) {
736: grp_route->upstream = rpentry_ptr->upstream;
737: grp_route->metric = rpentry_ptr->metric;
738: grp_route->preference = rpentry_ptr->preference;
739: change_interfaces(grp_route, rpentry_ptr->incoming,
740: grp_route->joined_oifs,
741: grp_route->pruned_oifs,
742: grp_route->leaves,
743: grp_route->asserted_oifs, MFC_UPDATE_FORCE);
744: }
745:
746: for (mrtentry_ptr = grpentry_ptr->mrtlink; mrtentry_ptr; mrtentry_ptr = mrtentry_ptr->grpnext) {
747: if (!(mrtentry_ptr->flags & MRTF_RP))
748: continue;
749:
750: mrtentry_ptr->upstream = rpentry_ptr->upstream;
751: mrtentry_ptr->metric = rpentry_ptr->metric;
752: mrtentry_ptr->preference = rpentry_ptr->preference;
753: change_interfaces(mrtentry_ptr, rpentry_ptr->incoming,
754: mrtentry_ptr->joined_oifs,
755: mrtentry_ptr->pruned_oifs,
756: mrtentry_ptr->leaves,
757: mrtentry_ptr->asserted_oifs, MFC_UPDATE_FORCE);
758: }
759:
760: return TRUE;
761: }
762:
763:
764: rpentry_t *rp_match(uint32_t group)
765: {
766: rp_grp_entry_t *ptr;
767:
768: ptr = rp_grp_match(group);
769: if (ptr)
770: return ptr->rp->rpentry;
771:
772: return NULL;
773: }
774:
775: rp_grp_entry_t *rp_grp_match(uint32_t group)
776: {
777: grp_mask_t *mask_ptr;
778: rp_grp_entry_t *entry_ptr;
779: rp_grp_entry_t *best_entry = NULL;
780: uint8_t best_priority = ~0; /* Smaller is better */
781: uint32_t best_hash_value = 0; /* Bigger is better */
782: uint32_t best_address_h = 0; /* Bigger is better */
783: uint32_t curr_hash_value = 0;
784: uint32_t curr_address_h = 0;
785: uint32_t group_h = ntohl(group);
786:
787: if (grp_mask_list == NULL)
788: return NULL;
789:
790: for (mask_ptr = grp_mask_list; mask_ptr; mask_ptr = mask_ptr->next) {
791: /* Search the grp_mask (group-prefix) list */
792: if ((group_h & ntohl(mask_ptr->group_mask))
793: != ntohl(mask_ptr->group_mask & mask_ptr->group_addr))
794: continue;
795:
796: for (entry_ptr = mask_ptr->grp_rp_next; entry_ptr; entry_ptr = entry_ptr->grp_rp_next) {
797: if (best_priority < entry_ptr->priority)
798: break;
799:
800: curr_hash_value = RP_HASH_VALUE(group_h, mask_ptr->hash_mask, curr_address_h);
801: curr_address_h = ntohl(entry_ptr->rp->rpentry->address);
802:
803: if (best_priority == entry_ptr->priority) {
804: /* Compare the hash_value and then the addresses */
805: if (curr_hash_value < best_hash_value)
806: continue;
807:
808: if (curr_hash_value == best_hash_value) {
809: if (curr_address_h < best_address_h)
810: continue;
811: }
812: }
813:
814: /* The current entry in the loop is preferred */
815: best_entry = entry_ptr;
816: best_priority = best_entry->priority;
817: best_address_h = curr_address_h;
818: best_hash_value = curr_hash_value;
819: }
820: }
821:
822: return best_entry;
823: }
824:
825:
826: rpentry_t *rp_find(uint32_t rp_address)
827: {
828: cand_rp_t *cand_rp_ptr;
829: uint32_t address_h = ntohl(rp_address);
830:
831: for(cand_rp_ptr = cand_rp_list; cand_rp_ptr != NULL; cand_rp_ptr = cand_rp_ptr->next) {
832: if (ntohl(cand_rp_ptr->rpentry->address) > address_h)
833: continue;
834:
835: if (cand_rp_ptr->rpentry->address == rp_address)
836: return cand_rp_ptr->rpentry;
837:
838: return NULL;
839: }
840:
841: return NULL;
842: }
843:
844:
845: /*
846: * Create a bootstrap message in "send_buff" and returns the data size
847: * (excluding the IP header and the PIM header) Can be used both by the
848: * Bootstrap router to multicast the RP-set or by the DR to unicast it to
849: * a new neighbor. It DOES NOT change any timers.
850: */
851: int create_pim_bootstrap_message(char *send_buff)
852: {
853: uint8_t *data_ptr;
854: grp_mask_t *mask_ptr;
855: rp_grp_entry_t *entry_ptr;
856: int datalen;
857: uint8_t masklen;
858:
859: if (curr_bsr_address == INADDR_ANY_N)
860: return 0;
861:
862: data_ptr = (uint8_t *)(send_buff + sizeof(struct ip) + sizeof(pim_header_t));
863: if (curr_bsr_address == my_bsr_address)
864: curr_bsr_fragment_tag++;
865:
866: PUT_HOSTSHORT(curr_bsr_fragment_tag, data_ptr);
867: MASK_TO_MASKLEN(curr_bsr_hash_mask, masklen);
868: PUT_BYTE(masklen, data_ptr);
869: PUT_BYTE(curr_bsr_priority, data_ptr);
870: PUT_EUADDR(curr_bsr_address, data_ptr);
871:
872: /* TODO: XXX: No fragmentation support (yet) */
873: for (mask_ptr = grp_mask_list; mask_ptr; mask_ptr = mask_ptr->next) {
874: if (IN_PIM_SSM_RANGE(mask_ptr->group_addr)) {
875: continue; /* Do not advertise internal virtual RP for SSM groups */
876: }
877: MASK_TO_MASKLEN(mask_ptr->group_mask, masklen);
878: PUT_EGADDR(mask_ptr->group_addr, masklen, 0, data_ptr);
879: PUT_BYTE(mask_ptr->group_rp_number, data_ptr);
880: PUT_BYTE(mask_ptr->group_rp_number, data_ptr); /* TODO: if frag.*/
881: PUT_HOSTSHORT(0, data_ptr);
882:
883: for (entry_ptr = mask_ptr->grp_rp_next; entry_ptr; entry_ptr = entry_ptr->grp_rp_next) {
884: PUT_EUADDR(entry_ptr->rp->rpentry->address, data_ptr);
885: PUT_HOSTSHORT(entry_ptr->holdtime, data_ptr);
886: PUT_BYTE(entry_ptr->priority, data_ptr);
887: PUT_BYTE(0, data_ptr); /* The reserved field */
888: }
889: }
890:
891: datalen = (data_ptr - (uint8_t *)send_buff) - sizeof(struct ip) - sizeof(pim_header_t);
892:
893: return datalen;
894: }
895:
896:
897: /*
898: * Check if the addr is the RP for the group corresponding to mrt.
899: * Return TRUE or FALSE.
900: */
901: int check_mrtentry_rp(mrtentry_t *mrt, uint32_t addr)
902: {
903: rp_grp_entry_t *ptr;
904:
905: if (!mrt)
906: return FALSE;
907:
908: if (addr == INADDR_ANY_N)
909: return FALSE;
910:
911: ptr = mrt->group->active_rp_grp;
912: if (!ptr)
913: return FALSE;
914:
915: if (mrt->group->rpaddr == addr)
916: return TRUE;
917:
918: return FALSE;
919: }
920:
921: /**
922: * Local Variables:
923: * version-control: t
924: * indent-tabs-mode: t
925: * c-file-style: "ellemtel"
926: * c-basic-offset: 4
927: * End:
928: */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to rp.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