1: /*
2: * Copyright (C) 2003 Yasuhiro Ohara
3: *
4: * This file is part of GNU Zebra.
5: *
6: * GNU Zebra is free software; you can redistribute it and/or modify it
7: * under the terms of the GNU General Public License as published by the
8: * Free Software Foundation; either version 2, or (at your option) any
9: * later version.
10: *
11: * GNU Zebra is distributed in the hope that it will be useful, but
12: * WITHOUT ANY WARRANTY; without even the implied warranty of
13: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14: * General Public License for more details.
15: *
16: * You should have received a copy of the GNU General Public License
17: * along with GNU Zebra; see the file COPYING. If not, write to the
18: * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
19: * Boston, MA 02111-1307, USA.
20: */
21:
22: #include <zebra.h>
23:
24: #include "log.h"
25: #include "thread.h"
26: #include "linklist.h"
27: #include "vty.h"
28: #include "command.h"
29:
30: #include "ospf6d.h"
31: #include "ospf6_proto.h"
32: #include "ospf6_lsa.h"
33: #include "ospf6_lsdb.h"
34: #include "ospf6_message.h"
35: #include "ospf6_route.h"
36: #include "ospf6_spf.h"
37:
38: #include "ospf6_top.h"
39: #include "ospf6_area.h"
40: #include "ospf6_interface.h"
41: #include "ospf6_neighbor.h"
42:
43: #include "ospf6_flood.h"
44:
45: unsigned char conf_debug_ospf6_flooding;
46:
47: struct ospf6_lsdb *
48: ospf6_get_scoped_lsdb (struct ospf6_lsa *lsa)
49: {
50: struct ospf6_lsdb *lsdb = NULL;
51: switch (OSPF6_LSA_SCOPE (lsa->header->type))
52: {
53: case OSPF6_SCOPE_LINKLOCAL:
54: lsdb = OSPF6_INTERFACE (lsa->lsdb->data)->lsdb;
55: break;
56: case OSPF6_SCOPE_AREA:
57: lsdb = OSPF6_AREA (lsa->lsdb->data)->lsdb;
58: break;
59: case OSPF6_SCOPE_AS:
60: lsdb = OSPF6_PROCESS (lsa->lsdb->data)->lsdb;
61: break;
62: default:
63: assert (0);
64: break;
65: }
66: return lsdb;
67: }
68:
69: struct ospf6_lsdb *
70: ospf6_get_scoped_lsdb_self (struct ospf6_lsa *lsa)
71: {
72: struct ospf6_lsdb *lsdb_self = NULL;
73: switch (OSPF6_LSA_SCOPE (lsa->header->type))
74: {
75: case OSPF6_SCOPE_LINKLOCAL:
76: lsdb_self = OSPF6_INTERFACE (lsa->lsdb->data)->lsdb_self;
77: break;
78: case OSPF6_SCOPE_AREA:
79: lsdb_self = OSPF6_AREA (lsa->lsdb->data)->lsdb_self;
80: break;
81: case OSPF6_SCOPE_AS:
82: lsdb_self = OSPF6_PROCESS (lsa->lsdb->data)->lsdb_self;
83: break;
84: default:
85: assert (0);
86: break;
87: }
88: return lsdb_self;
89: }
90:
91: void
92: ospf6_lsa_originate (struct ospf6_lsa *lsa)
93: {
94: struct ospf6_lsa *old;
95: struct ospf6_lsdb *lsdb_self;
96:
97: /* find previous LSA */
98: old = ospf6_lsdb_lookup (lsa->header->type, lsa->header->id,
99: lsa->header->adv_router, lsa->lsdb);
100:
101: /* if the new LSA does not differ from previous,
102: suppress this update of the LSA */
103: if (old && ! OSPF6_LSA_IS_DIFFER (lsa, old))
104: {
105: if (IS_OSPF6_DEBUG_ORIGINATE_TYPE (lsa->header->type))
106: zlog_debug ("Suppress updating LSA: %s", lsa->name);
107: ospf6_lsa_delete (lsa);
108: return;
109: }
110:
111: /* store it in the LSDB for self-originated LSAs */
112: lsdb_self = ospf6_get_scoped_lsdb_self (lsa);
113: ospf6_lsdb_add (ospf6_lsa_copy (lsa), lsdb_self);
114:
115: lsa->refresh = thread_add_timer (master, ospf6_lsa_refresh, lsa,
116: OSPF_LS_REFRESH_TIME);
117:
118: if (IS_OSPF6_DEBUG_LSA_TYPE (lsa->header->type) ||
119: IS_OSPF6_DEBUG_ORIGINATE_TYPE (lsa->header->type))
120: {
121: zlog_debug ("LSA Originate:");
122: ospf6_lsa_header_print (lsa);
123: }
124:
125: ospf6_install_lsa (lsa);
126: ospf6_flood (NULL, lsa);
127: }
128:
129: void
130: ospf6_lsa_originate_process (struct ospf6_lsa *lsa,
131: struct ospf6 *process)
132: {
133: lsa->lsdb = process->lsdb;
134: ospf6_lsa_originate (lsa);
135: }
136:
137: void
138: ospf6_lsa_originate_area (struct ospf6_lsa *lsa,
139: struct ospf6_area *oa)
140: {
141: lsa->lsdb = oa->lsdb;
142: ospf6_lsa_originate (lsa);
143: }
144:
145: void
146: ospf6_lsa_originate_interface (struct ospf6_lsa *lsa,
147: struct ospf6_interface *oi)
148: {
149: lsa->lsdb = oi->lsdb;
150: ospf6_lsa_originate (lsa);
151: }
152:
153: void
154: ospf6_lsa_purge (struct ospf6_lsa *lsa)
155: {
156: struct ospf6_lsa *self;
157: struct ospf6_lsdb *lsdb_self;
158:
159: /* remove it from the LSDB for self-originated LSAs */
160: lsdb_self = ospf6_get_scoped_lsdb_self (lsa);
161: self = ospf6_lsdb_lookup (lsa->header->type, lsa->header->id,
162: lsa->header->adv_router, lsdb_self);
163: if (self)
164: {
165: THREAD_OFF (self->expire);
166: THREAD_OFF (self->refresh);
167: ospf6_lsdb_remove (self, lsdb_self);
168: }
169:
170: ospf6_lsa_premature_aging (lsa);
171: }
172:
173:
174: void
175: ospf6_increment_retrans_count (struct ospf6_lsa *lsa)
176: {
177: /* The LSA must be the original one (see the description
178: in ospf6_decrement_retrans_count () below) */
179: lsa->retrans_count++;
180: }
181:
182: void
183: ospf6_decrement_retrans_count (struct ospf6_lsa *lsa)
184: {
185: struct ospf6_lsdb *lsdb;
186: struct ospf6_lsa *orig;
187:
188: /* The LSA must be on the retrans-list of a neighbor. It means
189: the "lsa" is a copied one, and we have to decrement the
190: retransmission count of the original one (instead of this "lsa"'s).
191: In order to find the original LSA, first we have to find
192: appropriate LSDB that have the original LSA. */
193: lsdb = ospf6_get_scoped_lsdb (lsa);
194:
195: /* Find the original LSA of which the retrans_count should be decremented */
196: orig = ospf6_lsdb_lookup (lsa->header->type, lsa->header->id,
197: lsa->header->adv_router, lsdb);
198: if (orig)
199: {
200: orig->retrans_count--;
201: assert (orig->retrans_count >= 0);
202: }
203: }
204:
205: /* RFC2328 section 13.2 Installing LSAs in the database */
206: void
207: ospf6_install_lsa (struct ospf6_lsa *lsa)
208: {
209: struct timeval now;
210: struct ospf6_lsa *old;
211:
212: if (IS_OSPF6_DEBUG_LSA_TYPE (lsa->header->type) ||
213: IS_OSPF6_DEBUG_EXAMIN_TYPE (lsa->header->type))
214: zlog_debug ("Install LSA: %s", lsa->name);
215:
216: /* Remove the old instance from all neighbors' Link state
217: retransmission list (RFC2328 13.2 last paragraph) */
218: old = ospf6_lsdb_lookup (lsa->header->type, lsa->header->id,
219: lsa->header->adv_router, lsa->lsdb);
220: if (old)
221: {
222: THREAD_OFF (old->expire);
223: THREAD_OFF (old->refresh);
224: ospf6_flood_clear (old);
225: }
226:
227: quagga_gettime (QUAGGA_CLK_MONOTONIC, &now);
228: if (! OSPF6_LSA_IS_MAXAGE (lsa))
229: lsa->expire = thread_add_timer (master, ospf6_lsa_expire, lsa,
230: OSPF_LSA_MAXAGE + lsa->birth.tv_sec - now.tv_sec);
231: else
232: lsa->expire = NULL;
233:
234: if (OSPF6_LSA_IS_SEQWRAP(lsa) &&
235: ! (CHECK_FLAG(lsa->flag,OSPF6_LSA_SEQWRAPPED) &&
236: lsa->header->seqnum == htonl(OSPF_MAX_SEQUENCE_NUMBER)))
237: {
238: if (IS_OSPF6_DEBUG_EXAMIN_TYPE (lsa->header->type))
239: zlog_debug("lsa install wrapping: sequence 0x%x",
240: ntohl(lsa->header->seqnum));
241: SET_FLAG(lsa->flag, OSPF6_LSA_SEQWRAPPED);
242: /* in lieu of premature_aging, since we do not want to recreate this lsa
243: * and/or mess with timers etc, we just want to wrap the sequence number
244: * and reflood the lsa before continuing.
245: * NOTE: Flood needs to be called right after this function call, by the
246: * caller
247: */
248: lsa->header->seqnum = htonl (OSPF_MAX_SEQUENCE_NUMBER);
249: lsa->header->age = htons (OSPF_LSA_MAXAGE);
250: ospf6_lsa_checksum (lsa->header);
251: }
252:
253: /* actually install */
254: lsa->installed = now;
255: ospf6_lsdb_add (lsa, lsa->lsdb);
256:
257: return;
258: }
259:
260: /* RFC2740 section 3.5.2. Sending Link State Update packets */
261: /* RFC2328 section 13.3 Next step in the flooding procedure */
262: static void
263: ospf6_flood_interface (struct ospf6_neighbor *from,
264: struct ospf6_lsa *lsa, struct ospf6_interface *oi)
265: {
266: struct listnode *node, *nnode;
267: struct ospf6_neighbor *on;
268: struct ospf6_lsa *req;
269: int retrans_added = 0;
270: int is_debug = 0;
271:
272: if (IS_OSPF6_DEBUG_FLOODING ||
273: IS_OSPF6_DEBUG_FLOOD_TYPE (lsa->header->type))
274: {
275: is_debug++;
276: zlog_debug ("Flooding on %s: %s", oi->interface->name, lsa->name);
277: }
278:
279: /* (1) For each neighbor */
280: for (ALL_LIST_ELEMENTS (oi->neighbor_list, node, nnode, on))
281: {
282: if (is_debug)
283: zlog_debug ("To neighbor %s", on->name);
284:
285: /* (a) if neighbor state < Exchange, examin next */
286: if (on->state < OSPF6_NEIGHBOR_EXCHANGE)
287: {
288: if (is_debug)
289: zlog_debug ("Neighbor state less than ExChange, next neighbor");
290: continue;
291: }
292:
293: /* (b) if neighbor not yet Full, check request-list */
294: if (on->state != OSPF6_NEIGHBOR_FULL)
295: {
296: if (is_debug)
297: zlog_debug ("Neighbor not yet Full");
298:
299: req = ospf6_lsdb_lookup (lsa->header->type, lsa->header->id,
300: lsa->header->adv_router, on->request_list);
301: if (req == NULL)
302: {
303: if (is_debug)
304: zlog_debug ("Not on request-list for this neighbor");
305: /* fall through */
306: }
307: else
308: {
309: /* If new LSA less recent, examin next neighbor */
310: if (ospf6_lsa_compare (lsa, req) > 0)
311: {
312: if (is_debug)
313: zlog_debug ("Requesting is older, next neighbor");
314: continue;
315: }
316:
317: /* If the same instance, delete from request-list and
318: examin next neighbor */
319: if (ospf6_lsa_compare (lsa, req) == 0)
320: {
321: if (is_debug)
322: zlog_debug ("Requesting the same, remove it, next neighbor");
323: if (req == on->last_ls_req)
324: {
325: ospf6_lsa_unlock (req);
326: on->last_ls_req = NULL;
327: }
328: ospf6_lsdb_remove (req, on->request_list);
329: ospf6_check_nbr_loading (on);
330: continue;
331: }
332:
333: /* If the new LSA is more recent, delete from request-list */
334: if (ospf6_lsa_compare (lsa, req) < 0)
335: {
336: if (is_debug)
337: zlog_debug ("Received is newer, remove requesting");
338: if (req == on->last_ls_req)
339: {
340: ospf6_lsa_unlock (req);
341: on->last_ls_req = NULL;
342: }
343: ospf6_lsdb_remove (req, on->request_list);
344: ospf6_check_nbr_loading (on);
345: /* fall through */
346: }
347: }
348: }
349:
350: /* (c) If the new LSA was received from this neighbor,
351: examin next neighbor */
352: if (from == on)
353: {
354: if (is_debug)
355: zlog_debug ("Received is from the neighbor, next neighbor");
356: continue;
357: }
358:
359: /* (d) add retrans-list, schedule retransmission */
360: if (is_debug)
361: zlog_debug ("Add retrans-list of this neighbor");
362: ospf6_increment_retrans_count (lsa);
363: ospf6_lsdb_add (ospf6_lsa_copy (lsa), on->retrans_list);
364: if (on->thread_send_lsupdate == NULL)
365: on->thread_send_lsupdate =
366: thread_add_timer (master, ospf6_lsupdate_send_neighbor,
367: on, on->ospf6_if->rxmt_interval);
368: retrans_added++;
369: }
370:
371: /* (2) examin next interface if not added to retrans-list */
372: if (retrans_added == 0)
373: {
374: if (is_debug)
375: zlog_debug ("No retransmission scheduled, next interface");
376: return;
377: }
378:
379: /* (3) If the new LSA was received on this interface,
380: and it was from DR or BDR, examin next interface */
381: if (from && from->ospf6_if == oi &&
382: (from->router_id == oi->drouter || from->router_id == oi->bdrouter))
383: {
384: if (is_debug)
385: zlog_debug ("Received is from the I/F's DR or BDR, next interface");
386: return;
387: }
388:
389: /* (4) If the new LSA was received on this interface,
390: and the interface state is BDR, examin next interface */
391: if (from && from->ospf6_if == oi)
392: {
393: if (oi->state == OSPF6_INTERFACE_BDR)
394: {
395: if (is_debug)
396: zlog_debug ("Received is from the I/F, itself BDR, next interface");
397: return;
398: }
399: SET_FLAG(lsa->flag, OSPF6_LSA_FLOODBACK);
400: }
401:
402: /* (5) flood the LSA out the interface. */
403: if (is_debug)
404: zlog_debug ("Schedule flooding for the interface");
405: if ((oi->type == OSPF_IFTYPE_BROADCAST) ||
406: (oi->type == OSPF_IFTYPE_POINTOPOINT))
407: {
408: ospf6_lsdb_add (ospf6_lsa_copy (lsa), oi->lsupdate_list);
409: if (oi->thread_send_lsupdate == NULL)
410: oi->thread_send_lsupdate =
411: thread_add_event (master, ospf6_lsupdate_send_interface, oi, 0);
412: }
413: else
414: {
415: /* reschedule retransmissions to all neighbors */
416: for (ALL_LIST_ELEMENTS (oi->neighbor_list, node, nnode, on))
417: {
418: THREAD_OFF (on->thread_send_lsupdate);
419: on->thread_send_lsupdate =
420: thread_add_event (master, ospf6_lsupdate_send_neighbor, on, 0);
421: }
422: }
423: }
424:
425: static void
426: ospf6_flood_area (struct ospf6_neighbor *from,
427: struct ospf6_lsa *lsa, struct ospf6_area *oa)
428: {
429: struct listnode *node, *nnode;
430: struct ospf6_interface *oi;
431:
432: for (ALL_LIST_ELEMENTS (oa->if_list, node, nnode, oi))
433: {
434: if (OSPF6_LSA_SCOPE (lsa->header->type) == OSPF6_SCOPE_LINKLOCAL &&
435: oi != OSPF6_INTERFACE (lsa->lsdb->data))
436: continue;
437:
438: #if 0
439: if (OSPF6_LSA_SCOPE (lsa->header->type) == OSPF6_SCOPE_AS &&
440: ospf6_is_interface_virtual_link (oi))
441: continue;
442: #endif/*0*/
443:
444: ospf6_flood_interface (from, lsa, oi);
445: }
446: }
447:
448: static void
449: ospf6_flood_process (struct ospf6_neighbor *from,
450: struct ospf6_lsa *lsa, struct ospf6 *process)
451: {
452: struct listnode *node, *nnode;
453: struct ospf6_area *oa;
454:
455: for (ALL_LIST_ELEMENTS (process->area_list, node, nnode, oa))
456: {
457: if (OSPF6_LSA_SCOPE (lsa->header->type) == OSPF6_SCOPE_AREA &&
458: oa != OSPF6_AREA (lsa->lsdb->data))
459: continue;
460: if (OSPF6_LSA_SCOPE (lsa->header->type) == OSPF6_SCOPE_LINKLOCAL &&
461: oa != OSPF6_INTERFACE (lsa->lsdb->data)->area)
462: continue;
463:
464: if (ntohs (lsa->header->type) == OSPF6_LSTYPE_AS_EXTERNAL &&
465: IS_AREA_STUB (oa))
466: continue;
467:
468: ospf6_flood_area (from, lsa, oa);
469: }
470: }
471:
472: void
473: ospf6_flood (struct ospf6_neighbor *from, struct ospf6_lsa *lsa)
474: {
475: ospf6_flood_process (from, lsa, ospf6);
476: }
477:
478: static void
479: ospf6_flood_clear_interface (struct ospf6_lsa *lsa, struct ospf6_interface *oi)
480: {
481: struct listnode *node, *nnode;
482: struct ospf6_neighbor *on;
483: struct ospf6_lsa *rem;
484:
485: for (ALL_LIST_ELEMENTS (oi->neighbor_list, node, nnode, on))
486: {
487: rem = ospf6_lsdb_lookup (lsa->header->type, lsa->header->id,
488: lsa->header->adv_router, on->retrans_list);
489: if (rem && ! ospf6_lsa_compare (rem, lsa))
490: {
491: if (IS_OSPF6_DEBUG_FLOODING ||
492: IS_OSPF6_DEBUG_FLOOD_TYPE (lsa->header->type))
493: zlog_debug ("Remove %s from retrans_list of %s",
494: rem->name, on->name);
495: ospf6_decrement_retrans_count (rem);
496: ospf6_lsdb_remove (rem, on->retrans_list);
497: }
498: }
499: }
500:
501: static void
502: ospf6_flood_clear_area (struct ospf6_lsa *lsa, struct ospf6_area *oa)
503: {
504: struct listnode *node, *nnode;
505: struct ospf6_interface *oi;
506:
507: for (ALL_LIST_ELEMENTS (oa->if_list, node, nnode, oi))
508: {
509: if (OSPF6_LSA_SCOPE (lsa->header->type) == OSPF6_SCOPE_LINKLOCAL &&
510: oi != OSPF6_INTERFACE (lsa->lsdb->data))
511: continue;
512:
513: #if 0
514: if (OSPF6_LSA_SCOPE (lsa->header->type) == OSPF6_SCOPE_AS &&
515: ospf6_is_interface_virtual_link (oi))
516: continue;
517: #endif/*0*/
518:
519: ospf6_flood_clear_interface (lsa, oi);
520: }
521: }
522:
523: static void
524: ospf6_flood_clear_process (struct ospf6_lsa *lsa, struct ospf6 *process)
525: {
526: struct listnode *node, *nnode;
527: struct ospf6_area *oa;
528:
529: for (ALL_LIST_ELEMENTS (process->area_list, node, nnode, oa))
530: {
531: if (OSPF6_LSA_SCOPE (lsa->header->type) == OSPF6_SCOPE_AREA &&
532: oa != OSPF6_AREA (lsa->lsdb->data))
533: continue;
534: if (OSPF6_LSA_SCOPE (lsa->header->type) == OSPF6_SCOPE_LINKLOCAL &&
535: oa != OSPF6_INTERFACE (lsa->lsdb->data)->area)
536: continue;
537:
538: if (ntohs (lsa->header->type) == OSPF6_LSTYPE_AS_EXTERNAL &&
539: IS_AREA_STUB (oa))
540: continue;
541:
542: ospf6_flood_clear_area (lsa, oa);
543: }
544: }
545:
546: void
547: ospf6_flood_clear (struct ospf6_lsa *lsa)
548: {
549: ospf6_flood_clear_process (lsa, ospf6);
550: }
551:
552:
553: /* RFC2328 13.5 (Table 19): Sending link state acknowledgements. */
554: static void
555: ospf6_acknowledge_lsa_bdrouter (struct ospf6_lsa *lsa, int ismore_recent,
556: struct ospf6_neighbor *from)
557: {
558: struct ospf6_interface *oi;
559: int is_debug = 0;
560:
561: if (IS_OSPF6_DEBUG_FLOODING ||
562: IS_OSPF6_DEBUG_FLOOD_TYPE (lsa->header->type))
563: is_debug++;
564:
565: assert (from && from->ospf6_if);
566: oi = from->ospf6_if;
567:
568: /* LSA is more recent than database copy, but was not flooded
569: back out receiving interface. Delayed acknowledgement sent
570: if advertisement received from Designated Router,
571: otherwide do nothing. */
572: if (ismore_recent < 0)
573: {
574: if (oi->drouter == from->router_id)
575: {
576: if (is_debug)
577: zlog_debug ("Delayed acknowledgement (BDR & MoreRecent & from DR)");
578: /* Delayed acknowledgement */
579: ospf6_lsdb_add (ospf6_lsa_copy (lsa), oi->lsack_list);
580: if (oi->thread_send_lsack == NULL)
581: oi->thread_send_lsack =
582: thread_add_timer (master, ospf6_lsack_send_interface, oi, 3);
583: }
584: else
585: {
586: if (is_debug)
587: zlog_debug ("No acknowledgement (BDR & MoreRecent & ! from DR)");
588: }
589: return;
590: }
591:
592: /* LSA is a duplicate, and was treated as an implied acknowledgement.
593: Delayed acknowledgement sent if advertisement received from
594: Designated Router, otherwise do nothing */
595: if (CHECK_FLAG (lsa->flag, OSPF6_LSA_DUPLICATE) &&
596: CHECK_FLAG (lsa->flag, OSPF6_LSA_IMPLIEDACK))
597: {
598: if (oi->drouter == from->router_id)
599: {
600: if (is_debug)
601: zlog_debug ("Delayed acknowledgement (BDR & Duplicate & ImpliedAck & from DR)");
602: /* Delayed acknowledgement */
603: ospf6_lsdb_add (ospf6_lsa_copy (lsa), oi->lsack_list);
604: if (oi->thread_send_lsack == NULL)
605: oi->thread_send_lsack =
606: thread_add_timer (master, ospf6_lsack_send_interface, oi, 3);
607: }
608: else
609: {
610: if (is_debug)
611: zlog_debug ("No acknowledgement (BDR & Duplicate & ImpliedAck & ! from DR)");
612: }
613: return;
614: }
615:
616: /* LSA is a duplicate, and was not treated as an implied acknowledgement.
617: Direct acknowledgement sent */
618: if (CHECK_FLAG (lsa->flag, OSPF6_LSA_DUPLICATE) &&
619: ! CHECK_FLAG (lsa->flag, OSPF6_LSA_IMPLIEDACK))
620: {
621: if (is_debug)
622: zlog_debug ("Direct acknowledgement (BDR & Duplicate)");
623: ospf6_lsdb_add (ospf6_lsa_copy (lsa), from->lsack_list);
624: if (from->thread_send_lsack == NULL)
625: from->thread_send_lsack =
626: thread_add_event (master, ospf6_lsack_send_neighbor, from, 0);
627: return;
628: }
629:
630: /* LSA's LS age is equal to Maxage, and there is no current instance
631: of the LSA in the link state database, and none of router's
632: neighbors are in states Exchange or Loading */
633: /* Direct acknowledgement sent, but this case is handled in
634: early of ospf6_receive_lsa () */
635: }
636:
637: static void
638: ospf6_acknowledge_lsa_allother (struct ospf6_lsa *lsa, int ismore_recent,
639: struct ospf6_neighbor *from)
640: {
641: struct ospf6_interface *oi;
642: int is_debug = 0;
643:
644: if (IS_OSPF6_DEBUG_FLOODING ||
645: IS_OSPF6_DEBUG_FLOOD_TYPE (lsa->header->type))
646: is_debug++;
647:
648: assert (from && from->ospf6_if);
649: oi = from->ospf6_if;
650:
651: /* LSA has been flood back out receiving interface.
652: No acknowledgement sent. */
653: if (CHECK_FLAG (lsa->flag, OSPF6_LSA_FLOODBACK))
654: {
655: if (is_debug)
656: zlog_debug ("No acknowledgement (AllOther & FloodBack)");
657: return;
658: }
659:
660: /* LSA is more recent than database copy, but was not flooded
661: back out receiving interface. Delayed acknowledgement sent. */
662: if (ismore_recent < 0)
663: {
664: if (is_debug)
665: zlog_debug ("Delayed acknowledgement (AllOther & MoreRecent)");
666: /* Delayed acknowledgement */
667: ospf6_lsdb_add (ospf6_lsa_copy (lsa), oi->lsack_list);
668: if (oi->thread_send_lsack == NULL)
669: oi->thread_send_lsack =
670: thread_add_timer (master, ospf6_lsack_send_interface, oi, 3);
671: return;
672: }
673:
674: /* LSA is a duplicate, and was treated as an implied acknowledgement.
675: No acknowledgement sent. */
676: if (CHECK_FLAG (lsa->flag, OSPF6_LSA_DUPLICATE) &&
677: CHECK_FLAG (lsa->flag, OSPF6_LSA_IMPLIEDACK))
678: {
679: if (is_debug)
680: zlog_debug ("No acknowledgement (AllOther & Duplicate & ImpliedAck)");
681: return;
682: }
683:
684: /* LSA is a duplicate, and was not treated as an implied acknowledgement.
685: Direct acknowledgement sent */
686: if (CHECK_FLAG (lsa->flag, OSPF6_LSA_DUPLICATE) &&
687: ! CHECK_FLAG (lsa->flag, OSPF6_LSA_IMPLIEDACK))
688: {
689: if (is_debug)
690: zlog_debug ("Direct acknowledgement (AllOther & Duplicate)");
691: ospf6_lsdb_add (ospf6_lsa_copy (lsa), from->lsack_list);
692: if (from->thread_send_lsack == NULL)
693: from->thread_send_lsack =
694: thread_add_event (master, ospf6_lsack_send_neighbor, from, 0);
695: return;
696: }
697:
698: /* LSA's LS age is equal to Maxage, and there is no current instance
699: of the LSA in the link state database, and none of router's
700: neighbors are in states Exchange or Loading */
701: /* Direct acknowledgement sent, but this case is handled in
702: early of ospf6_receive_lsa () */
703: }
704:
705: static void
706: ospf6_acknowledge_lsa (struct ospf6_lsa *lsa, int ismore_recent,
707: struct ospf6_neighbor *from)
708: {
709: struct ospf6_interface *oi;
710:
711: assert (from && from->ospf6_if);
712: oi = from->ospf6_if;
713:
714: if (oi->state == OSPF6_INTERFACE_BDR)
715: ospf6_acknowledge_lsa_bdrouter (lsa, ismore_recent, from);
716: else
717: ospf6_acknowledge_lsa_allother (lsa, ismore_recent, from);
718: }
719:
720: /* RFC2328 section 13 (4):
721: if MaxAge LSA and if we have no instance, and no neighbor
722: is in states Exchange or Loading
723: returns 1 if match this case, else returns 0 */
724: static int
725: ospf6_is_maxage_lsa_drop (struct ospf6_lsa *lsa, struct ospf6_neighbor *from)
726: {
727: struct ospf6_neighbor *on;
728: struct ospf6_interface *oi;
729: struct ospf6_area *oa;
730: struct ospf6 *process = NULL;
731: struct listnode *i, *j, *k;
732: int count = 0;
733:
734: if (! OSPF6_LSA_IS_MAXAGE (lsa))
735: return 0;
736:
737: if (ospf6_lsdb_lookup (lsa->header->type, lsa->header->id,
738: lsa->header->adv_router, lsa->lsdb))
739: return 0;
740:
741: process = from->ospf6_if->area->ospf6;
742:
743: for (ALL_LIST_ELEMENTS_RO (process->area_list, i, oa))
744: for (ALL_LIST_ELEMENTS_RO (oa->if_list, j, oi))
745: for (ALL_LIST_ELEMENTS_RO (oi->neighbor_list, k, on))
746: if (on->state == OSPF6_NEIGHBOR_EXCHANGE ||
747: on->state == OSPF6_NEIGHBOR_LOADING)
748: count++;
749:
750: if (count == 0)
751: return 1;
752: return 0;
753: }
754:
755: /* RFC2328 section 13 The Flooding Procedure */
756: void
757: ospf6_receive_lsa (struct ospf6_neighbor *from,
758: struct ospf6_lsa_header *lsa_header)
759: {
760: struct ospf6_lsa *new = NULL, *old = NULL, *rem = NULL;
761: int ismore_recent;
762: int is_debug = 0;
763:
764: ismore_recent = 1;
765: assert (from);
766:
767: /* make lsa structure for received lsa */
768: new = ospf6_lsa_create (lsa_header);
769:
770: if (IS_OSPF6_DEBUG_FLOODING ||
771: IS_OSPF6_DEBUG_FLOOD_TYPE (new->header->type))
772: {
773: is_debug++;
774: zlog_debug ("LSA Receive from %s", from->name);
775: ospf6_lsa_header_print (new);
776: }
777:
778: /* (1) LSA Checksum */
779: if (! ospf6_lsa_checksum_valid (new->header))
780: {
781: if (is_debug)
782: zlog_debug ("Wrong LSA Checksum, discard");
783: ospf6_lsa_delete (new);
784: return;
785: }
786:
787: /* (2) Examine the LSA's LS type.
788: RFC2470 3.5.1. Receiving Link State Update packets */
789: if (IS_AREA_STUB (from->ospf6_if->area) &&
790: OSPF6_LSA_SCOPE (new->header->type) == OSPF6_SCOPE_AS)
791: {
792: if (is_debug)
793: zlog_debug ("AS-External-LSA (or AS-scope LSA) in stub area, discard");
794: ospf6_lsa_delete (new);
795: return;
796: }
797:
798: /* (3) LSA which have reserved scope is discarded
799: RFC2470 3.5.1. Receiving Link State Update packets */
800: /* Flooding scope check. LSAs with unknown scope are discarded here.
801: Set appropriate LSDB for the LSA */
802: switch (OSPF6_LSA_SCOPE (new->header->type))
803: {
804: case OSPF6_SCOPE_LINKLOCAL:
805: new->lsdb = from->ospf6_if->lsdb;
806: break;
807: case OSPF6_SCOPE_AREA:
808: new->lsdb = from->ospf6_if->area->lsdb;
809: break;
810: case OSPF6_SCOPE_AS:
811: new->lsdb = from->ospf6_if->area->ospf6->lsdb;
812: break;
813: default:
814: if (is_debug)
815: zlog_debug ("LSA has reserved scope, discard");
816: ospf6_lsa_delete (new);
817: return;
818: }
819:
820: /* (4) if MaxAge LSA and if we have no instance, and no neighbor
821: is in states Exchange or Loading */
822: if (ospf6_is_maxage_lsa_drop (new, from))
823: {
824: /* log */
825: if (is_debug)
826: zlog_debug ("Drop MaxAge LSA with direct acknowledgement.");
827:
828: /* a) Acknowledge back to neighbor (Direct acknowledgement, 13.5) */
829: ospf6_lsdb_add (ospf6_lsa_copy (new), from->lsack_list);
830: if (from->thread_send_lsack == NULL)
831: from->thread_send_lsack =
832: thread_add_event (master, ospf6_lsack_send_neighbor, from, 0);
833:
834: /* b) Discard */
835: ospf6_lsa_delete (new);
836: return;
837: }
838:
839: /* (5) */
840: /* lookup the same database copy in lsdb */
841: old = ospf6_lsdb_lookup (new->header->type, new->header->id,
842: new->header->adv_router, new->lsdb);
843: if (old)
844: {
845: ismore_recent = ospf6_lsa_compare (new, old);
846: if (ntohl (new->header->seqnum) == ntohl (old->header->seqnum))
847: {
848: if (is_debug)
849: zlog_debug ("Received is duplicated LSA");
850: SET_FLAG (new->flag, OSPF6_LSA_DUPLICATE);
851: }
852: }
853:
854: /* if no database copy or received is more recent */
855: if (old == NULL || ismore_recent < 0)
856: {
857: /* in case we have no database copy */
858: ismore_recent = -1;
859:
860: /* (a) MinLSArrival check */
861: if (old)
862: {
863: struct timeval now, res;
864: quagga_gettime (QUAGGA_CLK_MONOTONIC, &now);
865: timersub (&now, &old->installed, &res);
866: if (res.tv_sec < (OSPF_MIN_LS_ARRIVAL / 1000))
867: {
868: if (is_debug)
869: zlog_debug ("LSA can't be updated within MinLSArrival, discard");
870: ospf6_lsa_delete (new);
871: return; /* examin next lsa */
872: }
873: }
874:
875: quagga_gettime (QUAGGA_CLK_MONOTONIC, &new->received);
876:
877: if (is_debug)
878: zlog_debug ("Install, Flood, Possibly acknowledge the received LSA");
879:
880: /* Remove older copies of this LSA from retx lists */
881: if (old)
882: ospf6_flood_clear (old);
883:
884: /* (b) immediately flood and (c) remove from all retrans-list */
885: /* Prevent self-originated LSA to be flooded. this is to make
886: reoriginated instance of the LSA not to be rejected by other routers
887: due to MinLSArrival. */
888: if (new->header->adv_router != from->ospf6_if->area->ospf6->router_id)
889: ospf6_flood (from, new);
890:
891: /* (d), installing lsdb, which may cause routing
892: table calculation (replacing database copy) */
893: ospf6_install_lsa (new);
894:
895: /* (e) possibly acknowledge */
896: ospf6_acknowledge_lsa (new, ismore_recent, from);
897:
898: /* (f) Self Originated LSA, section 13.4 */
899: if (new->header->adv_router == from->ospf6_if->area->ospf6->router_id)
900: {
901: /* Self-originated LSA (newer than ours) is received from
902: another router. We have to make a new instance of the LSA
903: or have to flush this LSA. */
904: if (is_debug)
905: {
906: zlog_debug ("Newer instance of the self-originated LSA");
907: zlog_debug ("Schedule reorigination");
908: }
909: new->refresh = thread_add_event (master, ospf6_lsa_refresh, new, 0);
910: }
911:
912: return;
913: }
914:
915: /* (6) if there is instance on sending neighbor's request list */
916: if (ospf6_lsdb_lookup (new->header->type, new->header->id,
917: new->header->adv_router, from->request_list))
918: {
919: /* if no database copy, should go above state (5) */
920: assert (old);
921:
922: if (is_debug)
923: {
924: zlog_debug ("Received is not newer, on the neighbor's request-list");
925: zlog_debug ("BadLSReq, discard the received LSA");
926: }
927:
928: /* BadLSReq */
929: thread_add_event (master, bad_lsreq, from, 0);
930:
931: ospf6_lsa_delete (new);
932: return;
933: }
934:
935: /* (7) if neither one is more recent */
936: if (ismore_recent == 0)
937: {
938: if (is_debug)
939: zlog_debug ("The same instance as database copy (neither recent)");
940:
941: /* (a) if on retrans-list, Treat this LSA as an Ack: Implied Ack */
942: rem = ospf6_lsdb_lookup (new->header->type, new->header->id,
943: new->header->adv_router, from->retrans_list);
944: if (rem)
945: {
946: if (is_debug)
947: {
948: zlog_debug ("It is on the neighbor's retrans-list.");
949: zlog_debug ("Treat as an Implied acknowledgement");
950: }
951: SET_FLAG (new->flag, OSPF6_LSA_IMPLIEDACK);
952: ospf6_decrement_retrans_count (rem);
953: ospf6_lsdb_remove (rem, from->retrans_list);
954: }
955:
956: if (is_debug)
957: zlog_debug ("Possibly acknowledge and then discard");
958:
959: /* (b) possibly acknowledge */
960: ospf6_acknowledge_lsa (new, ismore_recent, from);
961:
962: ospf6_lsa_delete (new);
963: return;
964: }
965:
966: /* (8) previous database copy is more recent */
967: {
968: assert (old);
969:
970: /* If database copy is in 'Seqnumber Wrapping',
971: simply discard the received LSA */
972: if (OSPF6_LSA_IS_MAXAGE (old) &&
973: old->header->seqnum == htonl (OSPF_MAX_SEQUENCE_NUMBER))
974: {
975: if (is_debug)
976: {
977: zlog_debug ("The LSA is in Seqnumber Wrapping");
978: zlog_debug ("MaxAge & MaxSeqNum, discard");
979: }
980: ospf6_lsa_delete (new);
981: return;
982: }
983:
984: /* Otherwise, Send database copy of this LSA to this neighbor */
985: {
986: if (is_debug)
987: {
988: zlog_debug ("Database copy is more recent.");
989: zlog_debug ("Send back directly and then discard");
990: }
991:
992: /* XXX, MinLSArrival check !? RFC 2328 13 (8) */
993:
994: ospf6_lsdb_add (ospf6_lsa_copy (old), from->lsupdate_list);
995: if (from->thread_send_lsupdate == NULL)
996: from->thread_send_lsupdate =
997: thread_add_event (master, ospf6_lsupdate_send_neighbor, from, 0);
998: ospf6_lsa_delete (new);
999: return;
1000: }
1001: return;
1002: }
1003: }
1004:
1005:
1006: DEFUN (debug_ospf6_flooding,
1007: debug_ospf6_flooding_cmd,
1008: "debug ospf6 flooding",
1009: DEBUG_STR
1010: OSPF6_STR
1011: "Debug OSPFv3 flooding function\n"
1012: )
1013: {
1014: OSPF6_DEBUG_FLOODING_ON ();
1015: return CMD_SUCCESS;
1016: }
1017:
1018: DEFUN (no_debug_ospf6_flooding,
1019: no_debug_ospf6_flooding_cmd,
1020: "no debug ospf6 flooding",
1021: NO_STR
1022: DEBUG_STR
1023: OSPF6_STR
1024: "Debug OSPFv3 flooding function\n"
1025: )
1026: {
1027: OSPF6_DEBUG_FLOODING_OFF ();
1028: return CMD_SUCCESS;
1029: }
1030:
1031: int
1032: config_write_ospf6_debug_flood (struct vty *vty)
1033: {
1034: if (IS_OSPF6_DEBUG_FLOODING)
1035: vty_out (vty, "debug ospf6 flooding%s", VNL);
1036: return 0;
1037: }
1038:
1039: void
1040: install_element_ospf6_debug_flood (void)
1041: {
1042: install_element (ENABLE_NODE, &debug_ospf6_flooding_cmd);
1043: install_element (ENABLE_NODE, &no_debug_ospf6_flooding_cmd);
1044: install_element (CONFIG_NODE, &debug_ospf6_flooding_cmd);
1045: install_element (CONFIG_NODE, &no_debug_ospf6_flooding_cmd);
1046: }
1047:
1048:
1049:
1050:
1051:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to ospf6_flood.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / quagga / ospf6d