2 * Copyright (C) 2003 Yasuhiro Ohara
4 * This file is part of GNU Zebra.
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
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.
16 * You should have received a copy of the GNU General Public License along
17 * with this program; see the file COPYING; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
30 #include "ospf6_proto.h"
31 #include "ospf6_lsa.h"
32 #include "ospf6_lsdb.h"
33 #include "ospf6_message.h"
34 #include "ospf6_route.h"
35 #include "ospf6_spf.h"
37 #include "ospf6_top.h"
38 #include "ospf6_area.h"
39 #include "ospf6_interface.h"
40 #include "ospf6_neighbor.h"
42 #include "ospf6_flood.h"
44 unsigned char conf_debug_ospf6_flooding
;
46 struct ospf6_lsdb
*ospf6_get_scoped_lsdb(struct ospf6_lsa
*lsa
)
48 struct ospf6_lsdb
*lsdb
= NULL
;
49 switch (OSPF6_LSA_SCOPE(lsa
->header
->type
)) {
50 case OSPF6_SCOPE_LINKLOCAL
:
51 lsdb
= OSPF6_INTERFACE(lsa
->lsdb
->data
)->lsdb
;
53 case OSPF6_SCOPE_AREA
:
54 lsdb
= OSPF6_AREA(lsa
->lsdb
->data
)->lsdb
;
57 lsdb
= OSPF6_PROCESS(lsa
->lsdb
->data
)->lsdb
;
66 struct ospf6_lsdb
*ospf6_get_scoped_lsdb_self(struct ospf6_lsa
*lsa
)
68 struct ospf6_lsdb
*lsdb_self
= NULL
;
69 switch (OSPF6_LSA_SCOPE(lsa
->header
->type
)) {
70 case OSPF6_SCOPE_LINKLOCAL
:
71 lsdb_self
= OSPF6_INTERFACE(lsa
->lsdb
->data
)->lsdb_self
;
73 case OSPF6_SCOPE_AREA
:
74 lsdb_self
= OSPF6_AREA(lsa
->lsdb
->data
)->lsdb_self
;
77 lsdb_self
= OSPF6_PROCESS(lsa
->lsdb
->data
)->lsdb_self
;
86 void ospf6_lsa_originate(struct ospf6_lsa
*lsa
)
88 struct ospf6_lsa
*old
;
89 struct ospf6_lsdb
*lsdb_self
;
91 /* find previous LSA */
92 old
= ospf6_lsdb_lookup(lsa
->header
->type
, lsa
->header
->id
,
93 lsa
->header
->adv_router
, lsa
->lsdb
);
95 /* if the new LSA does not differ from previous,
96 suppress this update of the LSA */
97 if (old
&& !OSPF6_LSA_IS_DIFFER(lsa
, old
)) {
98 if (IS_OSPF6_DEBUG_ORIGINATE_TYPE(lsa
->header
->type
))
99 zlog_debug("Suppress updating LSA: %s", lsa
->name
);
100 ospf6_lsa_delete(lsa
);
104 /* store it in the LSDB for self-originated LSAs */
105 lsdb_self
= ospf6_get_scoped_lsdb_self(lsa
);
106 ospf6_lsdb_add(ospf6_lsa_copy(lsa
), lsdb_self
);
109 thread_add_timer(master
, ospf6_lsa_refresh
, lsa
, OSPF_LS_REFRESH_TIME
,
112 if (IS_OSPF6_DEBUG_LSA_TYPE(lsa
->header
->type
)
113 || IS_OSPF6_DEBUG_ORIGINATE_TYPE(lsa
->header
->type
)) {
114 zlog_debug("LSA Originate:");
115 ospf6_lsa_header_print(lsa
);
118 ospf6_install_lsa(lsa
);
119 ospf6_flood(NULL
, lsa
);
122 void ospf6_lsa_originate_process(struct ospf6_lsa
*lsa
, struct ospf6
*process
)
124 lsa
->lsdb
= process
->lsdb
;
125 ospf6_lsa_originate(lsa
);
128 void ospf6_lsa_originate_area(struct ospf6_lsa
*lsa
, struct ospf6_area
*oa
)
130 lsa
->lsdb
= oa
->lsdb
;
131 ospf6_lsa_originate(lsa
);
134 void ospf6_lsa_originate_interface(struct ospf6_lsa
*lsa
,
135 struct ospf6_interface
*oi
)
137 lsa
->lsdb
= oi
->lsdb
;
138 ospf6_lsa_originate(lsa
);
141 void ospf6_lsa_purge(struct ospf6_lsa
*lsa
)
143 struct ospf6_lsa
*self
;
144 struct ospf6_lsdb
*lsdb_self
;
146 /* remove it from the LSDB for self-originated LSAs */
147 lsdb_self
= ospf6_get_scoped_lsdb_self(lsa
);
148 self
= ospf6_lsdb_lookup(lsa
->header
->type
, lsa
->header
->id
,
149 lsa
->header
->adv_router
, lsdb_self
);
151 THREAD_OFF(self
->expire
);
152 THREAD_OFF(self
->refresh
);
153 ospf6_lsdb_remove(self
, lsdb_self
);
156 ospf6_lsa_premature_aging(lsa
);
159 /* Puring Multi Link-State IDs LSAs:
160 * Same Advertising Router with Multiple Link-State IDs
161 * LSAs, purging require to traverse all Link-State IDs
163 void ospf6_lsa_purge_multi_ls_id(struct ospf6_area
*oa
, struct ospf6_lsa
*lsa
)
166 struct ospf6_lsa
*lsa_next
;
169 type
= lsa
->header
->type
;
171 ospf6_lsa_purge(lsa
);
173 lsa_next
= ospf6_lsdb_lookup(type
, htonl(++ls_id
),
174 oa
->ospf6
->router_id
, oa
->lsdb
);
176 ospf6_lsa_purge(lsa_next
);
177 lsa_next
= ospf6_lsdb_lookup(type
, htonl(++ls_id
),
178 oa
->ospf6
->router_id
, oa
->lsdb
);
182 void ospf6_increment_retrans_count(struct ospf6_lsa
*lsa
)
184 /* The LSA must be the original one (see the description
185 in ospf6_decrement_retrans_count () below) */
186 lsa
->retrans_count
++;
189 void ospf6_decrement_retrans_count(struct ospf6_lsa
*lsa
)
191 struct ospf6_lsdb
*lsdb
;
192 struct ospf6_lsa
*orig
;
194 /* The LSA must be on the retrans-list of a neighbor. It means
195 the "lsa" is a copied one, and we have to decrement the
196 retransmission count of the original one (instead of this "lsa"'s).
197 In order to find the original LSA, first we have to find
198 appropriate LSDB that have the original LSA. */
199 lsdb
= ospf6_get_scoped_lsdb(lsa
);
201 /* Find the original LSA of which the retrans_count should be
203 orig
= ospf6_lsdb_lookup(lsa
->header
->type
, lsa
->header
->id
,
204 lsa
->header
->adv_router
, lsdb
);
206 orig
->retrans_count
--;
207 assert(orig
->retrans_count
>= 0);
211 /* RFC2328 section 13.2 Installing LSAs in the database */
212 void ospf6_install_lsa(struct ospf6_lsa
*lsa
)
215 struct ospf6_lsa
*old
;
217 /* Remove the old instance from all neighbors' Link state
218 retransmission list (RFC2328 13.2 last paragraph) */
219 old
= ospf6_lsdb_lookup(lsa
->header
->type
, lsa
->header
->id
,
220 lsa
->header
->adv_router
, lsa
->lsdb
);
222 THREAD_OFF(old
->expire
);
223 THREAD_OFF(old
->refresh
);
224 ospf6_flood_clear(old
);
228 if (!OSPF6_LSA_IS_MAXAGE(lsa
)) {
230 thread_add_timer(master
, ospf6_lsa_expire
, lsa
,
231 OSPF_LSA_MAXAGE
+ lsa
->birth
.tv_sec
237 if (OSPF6_LSA_IS_SEQWRAP(lsa
)
238 && !(CHECK_FLAG(lsa
->flag
, OSPF6_LSA_SEQWRAPPED
)
239 && lsa
->header
->seqnum
== htonl(OSPF_MAX_SEQUENCE_NUMBER
))) {
240 if (IS_OSPF6_DEBUG_EXAMIN_TYPE(lsa
->header
->type
))
241 zlog_debug("lsa install wrapping: sequence 0x%x",
242 ntohl(lsa
->header
->seqnum
));
243 SET_FLAG(lsa
->flag
, OSPF6_LSA_SEQWRAPPED
);
244 /* in lieu of premature_aging, since we do not want to recreate
246 * and/or mess with timers etc, we just want to wrap the
248 * and reflood the lsa before continuing.
249 * NOTE: Flood needs to be called right after this function
253 lsa
->header
->seqnum
= htonl(OSPF_MAX_SEQUENCE_NUMBER
);
254 lsa
->header
->age
= htons(OSPF_LSA_MAXAGE
);
255 ospf6_lsa_checksum(lsa
->header
);
258 if (IS_OSPF6_DEBUG_LSA_TYPE(lsa
->header
->type
)
259 || IS_OSPF6_DEBUG_EXAMIN_TYPE(lsa
->header
->type
))
260 zlog_debug("%s Install LSA: %s age %d seqnum %x in LSDB.",
261 __func__
, lsa
->name
, ntohs(lsa
->header
->age
),
262 ntohl(lsa
->header
->seqnum
));
264 /* actually install */
265 lsa
->installed
= now
;
266 ospf6_lsdb_add(lsa
, lsa
->lsdb
);
271 /* RFC2740 section 3.5.2. Sending Link State Update packets */
272 /* RFC2328 section 13.3 Next step in the flooding procedure */
273 void ospf6_flood_interface(struct ospf6_neighbor
*from
, struct ospf6_lsa
*lsa
,
274 struct ospf6_interface
*oi
)
276 struct listnode
*node
, *nnode
;
277 struct ospf6_neighbor
*on
;
278 struct ospf6_lsa
*req
;
279 int retrans_added
= 0;
282 if (IS_OSPF6_DEBUG_FLOODING
283 || IS_OSPF6_DEBUG_FLOOD_TYPE(lsa
->header
->type
)) {
285 zlog_debug("Flooding on %s: %s", oi
->interface
->name
,
289 /* (1) For each neighbor */
290 for (ALL_LIST_ELEMENTS(oi
->neighbor_list
, node
, nnode
, on
)) {
292 zlog_debug("To neighbor %s", on
->name
);
294 /* (a) if neighbor state < Exchange, examin next */
295 if (on
->state
< OSPF6_NEIGHBOR_EXCHANGE
) {
298 "Neighbor state less than ExChange, next neighbor");
302 /* (b) if neighbor not yet Full, check request-list */
303 if (on
->state
!= OSPF6_NEIGHBOR_FULL
) {
305 zlog_debug("Neighbor not yet Full");
307 req
= ospf6_lsdb_lookup(
308 lsa
->header
->type
, lsa
->header
->id
,
309 lsa
->header
->adv_router
, on
->request_list
);
313 "Not on request-list for this neighbor");
316 /* If new LSA less recent, examin next neighbor
318 if (ospf6_lsa_compare(lsa
, req
) > 0) {
321 "Requesting is older, next neighbor");
325 /* If the same instance, delete from
327 examin next neighbor */
328 if (ospf6_lsa_compare(lsa
, req
) == 0) {
331 "Requesting the same, remove it, next neighbor");
332 if (req
== on
->last_ls_req
) {
333 /* sanity check refcount */
334 assert(req
->lock
>= 2);
335 req
= ospf6_lsa_unlock(req
);
336 on
->last_ls_req
= NULL
;
340 req
, on
->request_list
);
341 ospf6_check_nbr_loading(on
);
345 /* If the new LSA is more recent, delete from
347 if (ospf6_lsa_compare(lsa
, req
) < 0) {
350 "Received is newer, remove requesting");
351 if (req
== on
->last_ls_req
) {
352 req
= ospf6_lsa_unlock(req
);
353 on
->last_ls_req
= NULL
;
356 ospf6_lsdb_remove(req
,
358 ospf6_check_nbr_loading(on
);
364 /* (c) If the new LSA was received from this neighbor,
365 examin next neighbor */
369 "Received is from the neighbor, next neighbor");
373 if (ospf6
->inst_shutdown
) {
376 "%s: Send LSA %s (age %d) update now",
378 ntohs(lsa
->header
->age
));
379 ospf6_lsupdate_send_neighbor_now(on
, lsa
);
382 /* (d) add retrans-list, schedule retransmission */
384 zlog_debug("Add retrans-list of this neighbor");
385 ospf6_increment_retrans_count(lsa
);
386 ospf6_lsdb_add(ospf6_lsa_copy(lsa
), on
->retrans_list
);
387 thread_add_timer(master
, ospf6_lsupdate_send_neighbor
,
388 on
, on
->ospf6_if
->rxmt_interval
,
389 &on
->thread_send_lsupdate
);
394 /* (2) examin next interface if not added to retrans-list */
395 if (retrans_added
== 0) {
398 "No retransmission scheduled, next interface");
402 /* (3) If the new LSA was received on this interface,
403 and it was from DR or BDR, examin next interface */
404 if (from
&& from
->ospf6_if
== oi
405 && (from
->router_id
== oi
->drouter
406 || from
->router_id
== oi
->bdrouter
)) {
409 "Received is from the I/F's DR or BDR, next interface");
413 /* (4) If the new LSA was received on this interface,
414 and the interface state is BDR, examin next interface */
415 if (from
&& from
->ospf6_if
== oi
) {
416 if (oi
->state
== OSPF6_INTERFACE_BDR
) {
419 "Received is from the I/F, itself BDR, next interface");
422 SET_FLAG(lsa
->flag
, OSPF6_LSA_FLOODBACK
);
425 /* (5) flood the LSA out the interface. */
427 zlog_debug("Schedule flooding for the interface");
428 if ((oi
->type
== OSPF_IFTYPE_BROADCAST
)
429 || (oi
->type
== OSPF_IFTYPE_POINTOPOINT
)) {
430 ospf6_lsdb_add(ospf6_lsa_copy(lsa
), oi
->lsupdate_list
);
431 thread_add_event(master
, ospf6_lsupdate_send_interface
, oi
, 0,
432 &oi
->thread_send_lsupdate
);
434 /* reschedule retransmissions to all neighbors */
435 for (ALL_LIST_ELEMENTS(oi
->neighbor_list
, node
, nnode
, on
)) {
436 THREAD_OFF(on
->thread_send_lsupdate
);
437 on
->thread_send_lsupdate
= NULL
;
438 thread_add_event(master
, ospf6_lsupdate_send_neighbor
,
439 on
, 0, &on
->thread_send_lsupdate
);
444 void ospf6_flood_area(struct ospf6_neighbor
*from
, struct ospf6_lsa
*lsa
,
445 struct ospf6_area
*oa
)
447 struct listnode
*node
, *nnode
;
448 struct ospf6_interface
*oi
;
450 for (ALL_LIST_ELEMENTS(oa
->if_list
, node
, nnode
, oi
)) {
451 if (OSPF6_LSA_SCOPE(lsa
->header
->type
) == OSPF6_SCOPE_LINKLOCAL
452 && oi
!= OSPF6_INTERFACE(lsa
->lsdb
->data
))
456 if (OSPF6_LSA_SCOPE (lsa
->header
->type
) == OSPF6_SCOPE_AS
&&
457 ospf6_is_interface_virtual_link (oi
))
461 ospf6_flood_interface(from
, lsa
, oi
);
465 static void ospf6_flood_process(struct ospf6_neighbor
*from
,
466 struct ospf6_lsa
*lsa
, struct ospf6
*process
)
468 struct listnode
*node
, *nnode
;
469 struct ospf6_area
*oa
;
471 for (ALL_LIST_ELEMENTS(process
->area_list
, node
, nnode
, oa
)) {
472 if (OSPF6_LSA_SCOPE(lsa
->header
->type
) == OSPF6_SCOPE_AREA
473 && oa
!= OSPF6_AREA(lsa
->lsdb
->data
))
475 if (OSPF6_LSA_SCOPE(lsa
->header
->type
) == OSPF6_SCOPE_LINKLOCAL
476 && oa
!= OSPF6_INTERFACE(lsa
->lsdb
->data
)->area
)
479 if (ntohs(lsa
->header
->type
) == OSPF6_LSTYPE_AS_EXTERNAL
483 ospf6_flood_area(from
, lsa
, oa
);
487 void ospf6_flood(struct ospf6_neighbor
*from
, struct ospf6_lsa
*lsa
)
489 ospf6_flood_process(from
, lsa
, ospf6
);
492 static void ospf6_flood_clear_interface(struct ospf6_lsa
*lsa
,
493 struct ospf6_interface
*oi
)
495 struct listnode
*node
, *nnode
;
496 struct ospf6_neighbor
*on
;
497 struct ospf6_lsa
*rem
;
499 for (ALL_LIST_ELEMENTS(oi
->neighbor_list
, node
, nnode
, on
)) {
500 rem
= ospf6_lsdb_lookup(lsa
->header
->type
, lsa
->header
->id
,
501 lsa
->header
->adv_router
,
503 if (rem
&& !ospf6_lsa_compare(rem
, lsa
)) {
504 if (IS_OSPF6_DEBUG_FLOODING
505 || IS_OSPF6_DEBUG_FLOOD_TYPE(lsa
->header
->type
))
506 zlog_debug("Remove %s from retrans_list of %s",
507 rem
->name
, on
->name
);
508 ospf6_decrement_retrans_count(rem
);
509 ospf6_lsdb_remove(rem
, on
->retrans_list
);
514 static void ospf6_flood_clear_area(struct ospf6_lsa
*lsa
, struct ospf6_area
*oa
)
516 struct listnode
*node
, *nnode
;
517 struct ospf6_interface
*oi
;
519 for (ALL_LIST_ELEMENTS(oa
->if_list
, node
, nnode
, oi
)) {
520 if (OSPF6_LSA_SCOPE(lsa
->header
->type
) == OSPF6_SCOPE_LINKLOCAL
521 && oi
!= OSPF6_INTERFACE(lsa
->lsdb
->data
))
525 if (OSPF6_LSA_SCOPE (lsa
->header
->type
) == OSPF6_SCOPE_AS
&&
526 ospf6_is_interface_virtual_link (oi
))
530 ospf6_flood_clear_interface(lsa
, oi
);
534 static void ospf6_flood_clear_process(struct ospf6_lsa
*lsa
,
535 struct ospf6
*process
)
537 struct listnode
*node
, *nnode
;
538 struct ospf6_area
*oa
;
540 for (ALL_LIST_ELEMENTS(process
->area_list
, node
, nnode
, oa
)) {
541 if (OSPF6_LSA_SCOPE(lsa
->header
->type
) == OSPF6_SCOPE_AREA
542 && oa
!= OSPF6_AREA(lsa
->lsdb
->data
))
544 if (OSPF6_LSA_SCOPE(lsa
->header
->type
) == OSPF6_SCOPE_LINKLOCAL
545 && oa
!= OSPF6_INTERFACE(lsa
->lsdb
->data
)->area
)
548 if (ntohs(lsa
->header
->type
) == OSPF6_LSTYPE_AS_EXTERNAL
552 ospf6_flood_clear_area(lsa
, oa
);
556 void ospf6_flood_clear(struct ospf6_lsa
*lsa
)
558 ospf6_flood_clear_process(lsa
, ospf6
);
562 /* RFC2328 13.5 (Table 19): Sending link state acknowledgements. */
563 static void ospf6_acknowledge_lsa_bdrouter(struct ospf6_lsa
*lsa
,
565 struct ospf6_neighbor
*from
)
567 struct ospf6_interface
*oi
;
570 if (IS_OSPF6_DEBUG_FLOODING
571 || IS_OSPF6_DEBUG_FLOOD_TYPE(lsa
->header
->type
))
574 assert(from
&& from
->ospf6_if
);
577 /* LSA is more recent than database copy, but was not flooded
578 back out receiving interface. Delayed acknowledgement sent
579 if advertisement received from Designated Router,
580 otherwide do nothing. */
581 if (ismore_recent
< 0) {
582 if (oi
->drouter
== from
->router_id
) {
585 "Delayed acknowledgement (BDR & MoreRecent & from DR)");
586 /* Delayed acknowledgement */
587 ospf6_lsdb_add(ospf6_lsa_copy(lsa
), oi
->lsack_list
);
588 thread_add_timer(master
, ospf6_lsack_send_interface
, oi
,
589 3, &oi
->thread_send_lsack
);
593 "No acknowledgement (BDR & MoreRecent & ! from DR)");
598 /* LSA is a duplicate, and was treated as an implied acknowledgement.
599 Delayed acknowledgement sent if advertisement received from
600 Designated Router, otherwise do nothing */
601 if (CHECK_FLAG(lsa
->flag
, OSPF6_LSA_DUPLICATE
)
602 && CHECK_FLAG(lsa
->flag
, OSPF6_LSA_IMPLIEDACK
)) {
603 if (oi
->drouter
== from
->router_id
) {
606 "Delayed acknowledgement (BDR & Duplicate & ImpliedAck & from DR)");
607 /* Delayed acknowledgement */
608 ospf6_lsdb_add(ospf6_lsa_copy(lsa
), oi
->lsack_list
);
609 thread_add_timer(master
, ospf6_lsack_send_interface
, oi
,
610 3, &oi
->thread_send_lsack
);
614 "No acknowledgement (BDR & Duplicate & ImpliedAck & ! from DR)");
619 /* LSA is a duplicate, and was not treated as an implied
621 Direct acknowledgement sent */
622 if (CHECK_FLAG(lsa
->flag
, OSPF6_LSA_DUPLICATE
)
623 && !CHECK_FLAG(lsa
->flag
, OSPF6_LSA_IMPLIEDACK
)) {
625 zlog_debug("Direct acknowledgement (BDR & Duplicate)");
626 ospf6_lsdb_add(ospf6_lsa_copy(lsa
), from
->lsack_list
);
627 thread_add_event(master
, ospf6_lsack_send_neighbor
, from
, 0,
628 &from
->thread_send_lsack
);
632 /* LSA's LS age is equal to Maxage, and there is no current instance
633 of the LSA in the link state database, and none of router's
634 neighbors are in states Exchange or Loading */
635 /* Direct acknowledgement sent, but this case is handled in
636 early of ospf6_receive_lsa () */
639 static void ospf6_acknowledge_lsa_allother(struct ospf6_lsa
*lsa
,
641 struct ospf6_neighbor
*from
)
643 struct ospf6_interface
*oi
;
646 if (IS_OSPF6_DEBUG_FLOODING
647 || IS_OSPF6_DEBUG_FLOOD_TYPE(lsa
->header
->type
))
650 assert(from
&& from
->ospf6_if
);
653 /* LSA has been flood back out receiving interface.
654 No acknowledgement sent. */
655 if (CHECK_FLAG(lsa
->flag
, OSPF6_LSA_FLOODBACK
)) {
657 zlog_debug("No acknowledgement (AllOther & FloodBack)");
661 /* LSA is more recent than database copy, but was not flooded
662 back out receiving interface. Delayed acknowledgement sent. */
663 if (ismore_recent
< 0) {
666 "Delayed acknowledgement (AllOther & MoreRecent)");
667 /* Delayed acknowledgement */
668 ospf6_lsdb_add(ospf6_lsa_copy(lsa
), oi
->lsack_list
);
669 thread_add_timer(master
, ospf6_lsack_send_interface
, oi
, 3,
670 &oi
->thread_send_lsack
);
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
)) {
680 "No acknowledgement (AllOther & Duplicate & ImpliedAck)");
684 /* LSA is a duplicate, and was not treated as an implied
686 Direct acknowledgement sent */
687 if (CHECK_FLAG(lsa
->flag
, OSPF6_LSA_DUPLICATE
)
688 && !CHECK_FLAG(lsa
->flag
, OSPF6_LSA_IMPLIEDACK
)) {
691 "Direct acknowledgement (AllOther & Duplicate)");
692 ospf6_lsdb_add(ospf6_lsa_copy(lsa
), from
->lsack_list
);
693 thread_add_event(master
, ospf6_lsack_send_neighbor
, from
, 0,
694 &from
->thread_send_lsack
);
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 () */
705 static void ospf6_acknowledge_lsa(struct ospf6_lsa
*lsa
, int ismore_recent
,
706 struct ospf6_neighbor
*from
)
708 struct ospf6_interface
*oi
;
710 assert(from
&& from
->ospf6_if
);
713 if (oi
->state
== OSPF6_INTERFACE_BDR
)
714 ospf6_acknowledge_lsa_bdrouter(lsa
, ismore_recent
, from
);
716 ospf6_acknowledge_lsa_allother(lsa
, ismore_recent
, from
);
719 /* RFC2328 section 13 (4):
720 if MaxAge LSA and if we have no instance, and no neighbor
721 is in states Exchange or Loading
722 returns 1 if match this case, else returns 0 */
723 static int ospf6_is_maxage_lsa_drop(struct ospf6_lsa
*lsa
,
724 struct ospf6_neighbor
*from
)
726 struct ospf6_neighbor
*on
;
727 struct ospf6_interface
*oi
;
728 struct ospf6_area
*oa
;
729 struct ospf6
*process
= NULL
;
730 struct listnode
*i
, *j
, *k
;
733 if (!OSPF6_LSA_IS_MAXAGE(lsa
))
736 if (ospf6_lsdb_lookup(lsa
->header
->type
, lsa
->header
->id
,
737 lsa
->header
->adv_router
, lsa
->lsdb
))
740 process
= from
->ospf6_if
->area
->ospf6
;
742 for (ALL_LIST_ELEMENTS_RO(process
->area_list
, i
, oa
))
743 for (ALL_LIST_ELEMENTS_RO(oa
->if_list
, j
, oi
))
744 for (ALL_LIST_ELEMENTS_RO(oi
->neighbor_list
, k
, on
))
745 if (on
->state
== OSPF6_NEIGHBOR_EXCHANGE
746 || on
->state
== OSPF6_NEIGHBOR_LOADING
)
754 /* RFC2328 section 13 The Flooding Procedure */
755 void ospf6_receive_lsa(struct ospf6_neighbor
*from
,
756 struct ospf6_lsa_header
*lsa_header
)
758 struct ospf6_lsa
*new = NULL
, *old
= NULL
, *rem
= NULL
;
761 unsigned int time_delta_ms
;
766 /* make lsa structure for received lsa */
767 new = ospf6_lsa_create(lsa_header
);
769 if (IS_OSPF6_DEBUG_FLOODING
770 || IS_OSPF6_DEBUG_FLOOD_TYPE(new->header
->type
)) {
772 zlog_debug("LSA Receive from %s", from
->name
);
773 ospf6_lsa_header_print(new);
776 /* (1) LSA Checksum */
777 if (!ospf6_lsa_checksum_valid(new->header
)) {
779 zlog_debug("Wrong LSA Checksum, discard");
780 ospf6_lsa_delete(new);
784 /* (2) Examine the LSA's LS type.
785 RFC2470 3.5.1. Receiving Link State Update packets */
786 if (IS_AREA_STUB(from
->ospf6_if
->area
)
787 && OSPF6_LSA_SCOPE(new->header
->type
) == OSPF6_SCOPE_AS
) {
790 "AS-External-LSA (or AS-scope LSA) in stub area, discard");
791 ospf6_lsa_delete(new);
795 /* (3) LSA which have reserved scope is discarded
796 RFC2470 3.5.1. Receiving Link State Update packets */
797 /* Flooding scope check. LSAs with unknown scope are discarded here.
798 Set appropriate LSDB for the LSA */
799 switch (OSPF6_LSA_SCOPE(new->header
->type
)) {
800 case OSPF6_SCOPE_LINKLOCAL
:
801 new->lsdb
= from
->ospf6_if
->lsdb
;
803 case OSPF6_SCOPE_AREA
:
804 new->lsdb
= from
->ospf6_if
->area
->lsdb
;
807 new->lsdb
= from
->ospf6_if
->area
->ospf6
->lsdb
;
811 zlog_debug("LSA has reserved scope, discard");
812 ospf6_lsa_delete(new);
816 /* (4) if MaxAge LSA and if we have no instance, and no neighbor
817 is in states Exchange or Loading */
818 if (ospf6_is_maxage_lsa_drop(new, from
)) {
822 "Drop MaxAge LSA with direct acknowledgement.");
824 /* a) Acknowledge back to neighbor (Direct acknowledgement,
826 ospf6_lsdb_add(ospf6_lsa_copy(new), from
->lsack_list
);
827 thread_add_event(master
, ospf6_lsack_send_neighbor
, from
, 0,
828 &from
->thread_send_lsack
);
831 ospf6_lsa_delete(new);
836 /* lookup the same database copy in lsdb */
837 old
= ospf6_lsdb_lookup(new->header
->type
, new->header
->id
,
838 new->header
->adv_router
, new->lsdb
);
840 ismore_recent
= ospf6_lsa_compare(new, old
);
841 if (ntohl(new->header
->seqnum
) == ntohl(old
->header
->seqnum
)) {
843 zlog_debug("Received is duplicated LSA");
844 SET_FLAG(new->flag
, OSPF6_LSA_DUPLICATE
);
848 /* if no database copy or received is more recent */
849 if (old
== NULL
|| ismore_recent
< 0) {
850 /* in case we have no database copy */
853 /* (a) MinLSArrival check */
855 struct timeval now
, res
;
857 timersub(&now
, &old
->installed
, &res
);
859 (res
.tv_sec
* 1000) + (int)(res
.tv_usec
/ 1000);
861 < from
->ospf6_if
->area
->ospf6
->lsa_minarrival
) {
864 "LSA can't be updated within MinLSArrival, %dms < %dms, discard",
866 from
->ospf6_if
->area
->ospf6
868 ospf6_lsa_delete(new);
869 return; /* examin next lsa */
873 monotime(&new->received
);
877 "Install, Flood, Possibly acknowledge the received LSA");
879 /* Remove older copies of this LSA from retx lists */
881 ospf6_flood_clear(old
);
883 /* (b) immediately flood and (c) remove from all retrans-list */
884 /* Prevent self-originated LSA to be flooded. this is to make
885 reoriginated instance of the LSA not to be rejected by other
887 due to MinLSArrival. */
888 if (new->header
->adv_router
889 != from
->ospf6_if
->area
->ospf6
->router_id
)
890 ospf6_flood(from
, new);
892 /* (d), installing lsdb, which may cause routing
893 table calculation (replacing database copy) */
894 ospf6_install_lsa(new);
896 if (OSPF6_LSA_IS_MAXAGE(new))
897 ospf6_maxage_remove(from
->ospf6_if
->area
->ospf6
);
899 /* (e) possibly acknowledge */
900 ospf6_acknowledge_lsa(new, ismore_recent
, from
);
902 /* (f) Self Originated LSA, section 13.4 */
903 if (new->header
->adv_router
904 == from
->ospf6_if
->area
->ospf6
->router_id
) {
905 /* Self-originated LSA (newer than ours) is received
907 another router. We have to make a new instance of the
909 or have to flush this LSA. */
912 "Newer instance of the self-originated LSA");
913 zlog_debug("Schedule reorigination");
916 thread_add_event(master
, ospf6_lsa_refresh
, new, 0,
923 /* (6) if there is instance on sending neighbor's request list */
924 if (ospf6_lsdb_lookup(new->header
->type
, new->header
->id
,
925 new->header
->adv_router
, from
->request_list
)) {
926 /* if no database copy, should go above state (5) */
931 "Received is not newer, on the neighbor's request-list");
932 zlog_debug("BadLSReq, discard the received LSA");
936 thread_add_event(master
, bad_lsreq
, from
, 0, NULL
);
938 ospf6_lsa_delete(new);
942 /* (7) if neither one is more recent */
943 if (ismore_recent
== 0) {
946 "The same instance as database copy (neither recent)");
948 /* (a) if on retrans-list, Treat this LSA as an Ack: Implied Ack
950 rem
= ospf6_lsdb_lookup(new->header
->type
, new->header
->id
,
951 new->header
->adv_router
,
956 "It is on the neighbor's retrans-list.");
958 "Treat as an Implied acknowledgement");
960 SET_FLAG(new->flag
, OSPF6_LSA_IMPLIEDACK
);
961 ospf6_decrement_retrans_count(rem
);
962 ospf6_lsdb_remove(rem
, from
->retrans_list
);
966 zlog_debug("Possibly acknowledge and then discard");
968 /* (b) possibly acknowledge */
969 ospf6_acknowledge_lsa(new, ismore_recent
, from
);
971 ospf6_lsa_delete(new);
975 /* (8) previous database copy is more recent */
979 /* If database copy is in 'Seqnumber Wrapping',
980 simply discard the received LSA */
981 if (OSPF6_LSA_IS_MAXAGE(old
)
982 && old
->header
->seqnum
== htonl(OSPF_MAX_SEQUENCE_NUMBER
)) {
984 zlog_debug("The LSA is in Seqnumber Wrapping");
985 zlog_debug("MaxAge & MaxSeqNum, discard");
987 ospf6_lsa_delete(new);
991 /* Otherwise, Send database copy of this LSA to this neighbor */
994 zlog_debug("Database copy is more recent.");
996 "Send back directly and then discard");
999 /* Neighbor router sent recent age for LSA,
1000 * Router could be restarted while current copy is
1001 * MAXAGEd and not removed.*/
1002 if (OSPF6_LSA_IS_MAXAGE(old
)
1003 && !OSPF6_LSA_IS_MAXAGE(new)) {
1004 if (new->header
->adv_router
1005 != from
->ospf6_if
->area
->ospf6
->router_id
) {
1008 "%s: Current copy of LSA %s is MAXAGE, but new has recent age, flooding/installing.",
1009 old
->name
, __PRETTY_FUNCTION__
);
1010 ospf6_lsa_purge(old
);
1011 ospf6_flood(from
, new);
1012 ospf6_install_lsa(new);
1016 "%s: Current copy of self-originated LSA %s is MAXAGE, but new has recent age, ignoring new.",
1017 old
->name
, __PRETTY_FUNCTION__
);
1018 ospf6_lsa_delete(new);
1023 /* XXX, MinLSArrival check !? RFC 2328 13 (8) */
1025 ospf6_lsdb_add(ospf6_lsa_copy(old
),
1026 from
->lsupdate_list
);
1027 thread_add_event(master
, ospf6_lsupdate_send_neighbor
,
1028 from
, 0, &from
->thread_send_lsupdate
);
1030 ospf6_lsa_delete(new);
1037 DEFUN (debug_ospf6_flooding
,
1038 debug_ospf6_flooding_cmd
,
1039 "debug ospf6 flooding",
1042 "Debug OSPFv3 flooding function\n"
1045 OSPF6_DEBUG_FLOODING_ON();
1049 DEFUN (no_debug_ospf6_flooding
,
1050 no_debug_ospf6_flooding_cmd
,
1051 "no debug ospf6 flooding",
1055 "Debug OSPFv3 flooding function\n"
1058 OSPF6_DEBUG_FLOODING_OFF();
1062 int config_write_ospf6_debug_flood(struct vty
*vty
)
1064 if (IS_OSPF6_DEBUG_FLOODING
)
1065 vty_out(vty
, "debug ospf6 flooding\n");
1069 void install_element_ospf6_debug_flood(void)
1071 install_element(ENABLE_NODE
, &debug_ospf6_flooding_cmd
);
1072 install_element(ENABLE_NODE
, &no_debug_ospf6_flooding_cmd
);
1073 install_element(CONFIG_NODE
, &debug_ospf6_flooding_cmd
);
1074 install_element(CONFIG_NODE
, &no_debug_ospf6_flooding_cmd
);