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"
43 #include "ospf6_nssa.h"
46 unsigned char conf_debug_ospf6_flooding
;
48 struct ospf6_lsdb
*ospf6_get_scoped_lsdb(struct ospf6_lsa
*lsa
)
50 struct ospf6_lsdb
*lsdb
= NULL
;
51 switch (OSPF6_LSA_SCOPE(lsa
->header
->type
)) {
52 case OSPF6_SCOPE_LINKLOCAL
:
53 lsdb
= OSPF6_INTERFACE(lsa
->lsdb
->data
)->lsdb
;
55 case OSPF6_SCOPE_AREA
:
56 lsdb
= OSPF6_AREA(lsa
->lsdb
->data
)->lsdb
;
59 lsdb
= OSPF6_PROCESS(lsa
->lsdb
->data
)->lsdb
;
68 struct ospf6_lsdb
*ospf6_get_scoped_lsdb_self(struct ospf6_lsa
*lsa
)
70 struct ospf6_lsdb
*lsdb_self
= NULL
;
71 switch (OSPF6_LSA_SCOPE(lsa
->header
->type
)) {
72 case OSPF6_SCOPE_LINKLOCAL
:
73 lsdb_self
= OSPF6_INTERFACE(lsa
->lsdb
->data
)->lsdb_self
;
75 case OSPF6_SCOPE_AREA
:
76 lsdb_self
= OSPF6_AREA(lsa
->lsdb
->data
)->lsdb_self
;
79 lsdb_self
= OSPF6_PROCESS(lsa
->lsdb
->data
)->lsdb_self
;
88 void ospf6_lsa_originate(struct ospf6
*ospf6
, struct ospf6_lsa
*lsa
)
90 struct ospf6_lsa
*old
;
91 struct ospf6_lsdb
*lsdb_self
;
93 if (lsa
->header
->adv_router
== INADDR_ANY
) {
94 if (IS_OSPF6_DEBUG_ORIGINATE_TYPE(lsa
->header
->type
))
96 "Refusing to originate LSA (zero router ID): %s",
99 ospf6_lsa_delete(lsa
);
103 /* find previous LSA */
104 old
= ospf6_lsdb_lookup(lsa
->header
->type
, lsa
->header
->id
,
105 lsa
->header
->adv_router
, lsa
->lsdb
);
107 /* if the new LSA does not differ from previous,
108 suppress this update of the LSA */
109 if (old
&& !OSPF6_LSA_IS_DIFFER(lsa
, old
)
110 && !ospf6
->gr_info
.finishing_restart
) {
111 if (IS_OSPF6_DEBUG_ORIGINATE_TYPE(lsa
->header
->type
))
112 zlog_debug("Suppress updating LSA: %s", lsa
->name
);
113 ospf6_lsa_delete(lsa
);
117 /* store it in the LSDB for self-originated LSAs */
118 lsdb_self
= ospf6_get_scoped_lsdb_self(lsa
);
119 ospf6_lsdb_add(ospf6_lsa_copy(lsa
), lsdb_self
);
121 THREAD_OFF(lsa
->refresh
);
122 thread_add_timer(master
, ospf6_lsa_refresh
, lsa
, OSPF_LS_REFRESH_TIME
,
125 if (IS_OSPF6_DEBUG_LSA_TYPE(lsa
->header
->type
)
126 || IS_OSPF6_DEBUG_ORIGINATE_TYPE(lsa
->header
->type
)) {
127 zlog_debug("LSA Originate:");
128 ospf6_lsa_header_print(lsa
);
131 ospf6_install_lsa(lsa
);
132 ospf6_flood(NULL
, lsa
);
135 void ospf6_lsa_originate_process(struct ospf6_lsa
*lsa
, struct ospf6
*process
)
137 lsa
->lsdb
= process
->lsdb
;
138 ospf6_lsa_originate(process
, lsa
);
141 void ospf6_lsa_originate_area(struct ospf6_lsa
*lsa
, struct ospf6_area
*oa
)
143 lsa
->lsdb
= oa
->lsdb
;
144 ospf6_lsa_originate(oa
->ospf6
, lsa
);
147 void ospf6_lsa_originate_interface(struct ospf6_lsa
*lsa
,
148 struct ospf6_interface
*oi
)
150 lsa
->lsdb
= oi
->lsdb
;
151 ospf6_lsa_originate(oi
->area
->ospf6
, lsa
);
154 void ospf6_external_lsa_purge(struct ospf6
*ospf6
, struct ospf6_lsa
*lsa
)
156 uint32_t id
= lsa
->header
->id
;
157 struct ospf6_area
*oa
;
158 struct listnode
*lnode
;
160 ospf6_lsa_purge(lsa
);
162 /* Delete the corresponding NSSA LSA */
163 for (ALL_LIST_ELEMENTS_RO(ospf6
->area_list
, lnode
, oa
)) {
164 lsa
= ospf6_lsdb_lookup(htons(OSPF6_LSTYPE_TYPE_7
), id
,
165 ospf6
->router_id
, oa
->lsdb
);
167 if (IS_OSPF6_DEBUG_NSSA
)
168 zlog_debug("withdraw type 7 lsa, LS ID: %u",
171 ospf6_lsa_purge(lsa
);
176 void ospf6_lsa_purge(struct ospf6_lsa
*lsa
)
178 struct ospf6_lsa
*self
;
179 struct ospf6_lsdb
*lsdb_self
;
181 /* remove it from the LSDB for self-originated LSAs */
182 lsdb_self
= ospf6_get_scoped_lsdb_self(lsa
);
183 self
= ospf6_lsdb_lookup(lsa
->header
->type
, lsa
->header
->id
,
184 lsa
->header
->adv_router
, lsdb_self
);
186 THREAD_OFF(self
->expire
);
187 THREAD_OFF(self
->refresh
);
188 ospf6_lsdb_remove(self
, lsdb_self
);
191 ospf6_lsa_premature_aging(lsa
);
194 /* Puring Multi Link-State IDs LSAs:
195 * Same Advertising Router with Multiple Link-State IDs
196 * LSAs, purging require to traverse all Link-State IDs
198 void ospf6_lsa_purge_multi_ls_id(struct ospf6_area
*oa
, struct ospf6_lsa
*lsa
)
201 struct ospf6_lsa
*lsa_next
;
204 type
= lsa
->header
->type
;
206 ospf6_lsa_purge(lsa
);
208 lsa_next
= ospf6_lsdb_lookup(type
, htonl(++ls_id
),
209 oa
->ospf6
->router_id
, oa
->lsdb
);
211 ospf6_lsa_purge(lsa_next
);
212 lsa_next
= ospf6_lsdb_lookup(type
, htonl(++ls_id
),
213 oa
->ospf6
->router_id
, oa
->lsdb
);
217 void ospf6_increment_retrans_count(struct ospf6_lsa
*lsa
)
219 /* The LSA must be the original one (see the description
220 in ospf6_decrement_retrans_count () below) */
221 lsa
->retrans_count
++;
224 void ospf6_decrement_retrans_count(struct ospf6_lsa
*lsa
)
226 struct ospf6_lsdb
*lsdb
;
227 struct ospf6_lsa
*orig
;
229 /* The LSA must be on the retrans-list of a neighbor. It means
230 the "lsa" is a copied one, and we have to decrement the
231 retransmission count of the original one (instead of this "lsa"'s).
232 In order to find the original LSA, first we have to find
233 appropriate LSDB that have the original LSA. */
234 lsdb
= ospf6_get_scoped_lsdb(lsa
);
236 /* Find the original LSA of which the retrans_count should be
238 orig
= ospf6_lsdb_lookup(lsa
->header
->type
, lsa
->header
->id
,
239 lsa
->header
->adv_router
, lsdb
);
241 orig
->retrans_count
--;
242 assert(orig
->retrans_count
>= 0);
246 /* RFC2328 section 13.2 Installing LSAs in the database */
247 void ospf6_install_lsa(struct ospf6_lsa
*lsa
)
251 struct ospf6_lsa
*old
;
252 struct ospf6_area
*area
= NULL
;
254 ospf6
= ospf6_get_by_lsdb(lsa
);
257 /* Remove the old instance from all neighbors' Link state
258 retransmission list (RFC2328 13.2 last paragraph) */
259 old
= ospf6_lsdb_lookup(lsa
->header
->type
, lsa
->header
->id
,
260 lsa
->header
->adv_router
, lsa
->lsdb
);
262 if (ntohs(lsa
->header
->type
) == OSPF6_LSTYPE_TYPE_7
) {
263 if (IS_OSPF6_DEBUG_NSSA
)
264 zlog_debug("%s : old LSA %s", __func__
,
266 lsa
->external_lsa_id
= old
->external_lsa_id
;
268 THREAD_OFF(old
->expire
);
269 THREAD_OFF(old
->refresh
);
270 ospf6_flood_clear(old
);
274 if (!OSPF6_LSA_IS_MAXAGE(lsa
)) {
275 thread_add_timer(master
, ospf6_lsa_expire
, lsa
,
276 OSPF_LSA_MAXAGE
+ lsa
->birth
.tv_sec
282 if (OSPF6_LSA_IS_SEQWRAP(lsa
)
283 && !(CHECK_FLAG(lsa
->flag
, OSPF6_LSA_SEQWRAPPED
)
284 && lsa
->header
->seqnum
== htonl(OSPF_MAX_SEQUENCE_NUMBER
))) {
285 if (IS_OSPF6_DEBUG_EXAMIN_TYPE(lsa
->header
->type
))
286 zlog_debug("lsa install wrapping: sequence 0x%x",
287 ntohl(lsa
->header
->seqnum
));
288 SET_FLAG(lsa
->flag
, OSPF6_LSA_SEQWRAPPED
);
289 /* in lieu of premature_aging, since we do not want to recreate
291 * and/or mess with timers etc, we just want to wrap the
293 * and reflood the lsa before continuing.
294 * NOTE: Flood needs to be called right after this function
298 lsa
->header
->seqnum
= htonl(OSPF_MAX_SEQUENCE_NUMBER
);
299 lsa
->header
->age
= htons(OSPF_LSA_MAXAGE
);
300 ospf6_lsa_checksum(lsa
->header
);
303 if (IS_OSPF6_DEBUG_LSA_TYPE(lsa
->header
->type
)
304 || IS_OSPF6_DEBUG_EXAMIN_TYPE(lsa
->header
->type
))
305 zlog_debug("%s Install LSA: %s age %d seqnum %x in LSDB.",
306 __func__
, lsa
->name
, ntohs(lsa
->header
->age
),
307 ntohl(lsa
->header
->seqnum
));
309 /* actually install */
310 lsa
->installed
= now
;
312 /* Topo change handling */
313 if (CHECK_LSA_TOPO_CHG_ELIGIBLE(ntohs(lsa
->header
->type
))
314 && !CHECK_FLAG(lsa
->flag
, OSPF6_LSA_DUPLICATE
)) {
316 /* check if it is new lsa ? or existing lsa got modified ?*/
317 if (!old
|| OSPF6_LSA_IS_CHANGED(old
, lsa
))
318 ospf6_helper_handle_topo_chg(ospf6
, lsa
);
321 ospf6_lsdb_add(lsa
, lsa
->lsdb
);
323 if (ntohs(lsa
->header
->type
) == OSPF6_LSTYPE_TYPE_7
324 && lsa
->header
->adv_router
!= ospf6
->router_id
) {
325 area
= OSPF6_AREA(lsa
->lsdb
->data
);
326 ospf6_translated_nssa_refresh(area
, lsa
, NULL
);
327 ospf6_schedule_abr_task(area
->ospf6
);
330 if (ntohs(lsa
->header
->type
) == OSPF6_LSTYPE_ROUTER
) {
331 area
= OSPF6_AREA(lsa
->lsdb
->data
);
333 if (IS_OSPF6_DEBUG_LSA_TYPE(lsa
->header
->type
)
334 || IS_OSPF6_DEBUG_EXAMIN_TYPE(lsa
->header
->type
))
335 zlog_debug("%s: New router LSA %s", __func__
,
337 ospf6_abr_nssa_check_status(area
->ospf6
);
343 /* RFC2740 section 3.5.2. Sending Link State Update packets */
344 /* RFC2328 section 13.3 Next step in the flooding procedure */
345 void ospf6_flood_interface(struct ospf6_neighbor
*from
, struct ospf6_lsa
*lsa
,
346 struct ospf6_interface
*oi
)
348 struct listnode
*node
, *nnode
;
349 struct ospf6_neighbor
*on
;
350 struct ospf6_lsa
*req
, *old
;
351 int retrans_added
= 0;
354 if (IS_OSPF6_DEBUG_FLOODING
355 || IS_OSPF6_DEBUG_FLOOD_TYPE(lsa
->header
->type
)) {
357 zlog_debug("Flooding on %s: %s", oi
->interface
->name
,
361 /* (1) For each neighbor */
362 for (ALL_LIST_ELEMENTS(oi
->neighbor_list
, node
, nnode
, on
)) {
364 zlog_debug("To neighbor %s", on
->name
);
366 /* (a) if neighbor state < Exchange, examin next */
367 if (on
->state
< OSPF6_NEIGHBOR_EXCHANGE
) {
370 "Neighbor state less than ExChange, next neighbor");
374 /* (b) if neighbor not yet Full, check request-list */
375 if (on
->state
!= OSPF6_NEIGHBOR_FULL
) {
377 zlog_debug("Neighbor not yet Full");
379 req
= ospf6_lsdb_lookup(
380 lsa
->header
->type
, lsa
->header
->id
,
381 lsa
->header
->adv_router
, on
->request_list
);
385 "Not on request-list for this neighbor");
388 /* If new LSA less recent, examin next neighbor
390 if (ospf6_lsa_compare(lsa
, req
) > 0) {
393 "Requesting is older, next neighbor");
397 /* If the same instance, delete from
399 examin next neighbor */
400 if (ospf6_lsa_compare(lsa
, req
) == 0) {
403 "Requesting the same, remove it, next neighbor");
404 if (req
== on
->last_ls_req
) {
405 /* sanity check refcount */
406 assert(req
->lock
>= 2);
407 req
= ospf6_lsa_unlock(req
);
408 on
->last_ls_req
= NULL
;
412 req
, on
->request_list
);
413 ospf6_check_nbr_loading(on
);
417 /* If the new LSA is more recent, delete from
419 if (ospf6_lsa_compare(lsa
, req
) < 0) {
422 "Received is newer, remove requesting");
423 if (req
== on
->last_ls_req
) {
424 req
= ospf6_lsa_unlock(req
);
425 on
->last_ls_req
= NULL
;
428 ospf6_lsdb_remove(req
,
430 ospf6_check_nbr_loading(on
);
436 /* (c) If the new LSA was received from this neighbor,
437 examin next neighbor */
441 "Received is from the neighbor, next neighbor");
445 if ((oi
->area
->ospf6
->inst_shutdown
)
446 || CHECK_FLAG(lsa
->flag
, OSPF6_LSA_FLUSH
)) {
449 "%s: Send LSA %s (age %d) update now",
451 ntohs(lsa
->header
->age
));
452 ospf6_lsupdate_send_neighbor_now(on
, lsa
);
455 /* (d) add retrans-list, schedule retransmission */
457 zlog_debug("Add retrans-list of neighbor %s ",
460 /* Do not increment the retrans count if the lsa is
461 * already present in the retrans list.
463 old
= ospf6_lsdb_lookup(
464 lsa
->header
->type
, lsa
->header
->id
,
465 lsa
->header
->adv_router
, on
->retrans_list
);
469 "Increment %s from retrans_list of %s",
470 lsa
->name
, on
->name
);
471 ospf6_increment_retrans_count(lsa
);
472 ospf6_lsdb_add(ospf6_lsa_copy(lsa
),
475 master
, ospf6_lsupdate_send_neighbor
,
476 on
, on
->ospf6_if
->rxmt_interval
,
477 &on
->thread_send_lsupdate
);
483 /* (2) examin next interface if not added to retrans-list */
484 if (retrans_added
== 0) {
487 "No retransmission scheduled, next interface %s",
488 oi
->interface
->name
);
492 /* (3) If the new LSA was received on this interface,
493 and it was from DR or BDR, examin next interface */
494 if (from
&& from
->ospf6_if
== oi
495 && (from
->router_id
== oi
->drouter
496 || from
->router_id
== oi
->bdrouter
)) {
499 "Received is from the I/F's DR or BDR, next interface");
503 /* (4) If the new LSA was received on this interface,
504 and the interface state is BDR, examin next interface */
505 if (from
&& from
->ospf6_if
== oi
) {
506 if (oi
->state
== OSPF6_INTERFACE_BDR
) {
509 "Received is from the I/F, itself BDR, next interface");
512 SET_FLAG(lsa
->flag
, OSPF6_LSA_FLOODBACK
);
515 /* (5) flood the LSA out the interface. */
517 zlog_debug("Schedule flooding for the interface");
518 if ((oi
->type
== OSPF_IFTYPE_BROADCAST
)
519 || (oi
->type
== OSPF_IFTYPE_POINTOPOINT
)) {
520 ospf6_lsdb_add(ospf6_lsa_copy(lsa
), oi
->lsupdate_list
);
521 thread_add_event(master
, ospf6_lsupdate_send_interface
, oi
, 0,
522 &oi
->thread_send_lsupdate
);
524 /* reschedule retransmissions to all neighbors */
525 for (ALL_LIST_ELEMENTS(oi
->neighbor_list
, node
, nnode
, on
)) {
526 THREAD_OFF(on
->thread_send_lsupdate
);
527 thread_add_event(master
, ospf6_lsupdate_send_neighbor
,
528 on
, 0, &on
->thread_send_lsupdate
);
533 void ospf6_flood_area(struct ospf6_neighbor
*from
, struct ospf6_lsa
*lsa
,
534 struct ospf6_area
*oa
)
536 struct listnode
*node
, *nnode
;
537 struct ospf6_interface
*oi
;
539 for (ALL_LIST_ELEMENTS(oa
->if_list
, node
, nnode
, oi
)) {
540 if (OSPF6_LSA_SCOPE(lsa
->header
->type
) == OSPF6_SCOPE_LINKLOCAL
541 && oi
!= OSPF6_INTERFACE(lsa
->lsdb
->data
))
544 ospf6_flood_interface(from
, lsa
, oi
);
548 static void ospf6_flood_process(struct ospf6_neighbor
*from
,
549 struct ospf6_lsa
*lsa
, struct ospf6
*process
)
551 struct listnode
*node
, *nnode
;
552 struct ospf6_area
*oa
;
554 for (ALL_LIST_ELEMENTS(process
->area_list
, node
, nnode
, oa
)) {
556 /* If unknown LSA and U-bit clear, treat as link local
559 if (!OSPF6_LSA_IS_KNOWN(lsa
->header
->type
)
560 && !(ntohs(lsa
->header
->type
) & OSPF6_LSTYPE_UBIT_MASK
)
561 && (oa
!= OSPF6_INTERFACE(lsa
->lsdb
->data
)->area
)) {
563 if (IS_OSPF6_DEBUG_FLOODING
)
564 zlog_debug("Unknown LSA, do not flood");
568 if (OSPF6_LSA_SCOPE(lsa
->header
->type
) == OSPF6_SCOPE_AREA
569 && oa
!= OSPF6_AREA(lsa
->lsdb
->data
))
571 if (OSPF6_LSA_SCOPE(lsa
->header
->type
) == OSPF6_SCOPE_LINKLOCAL
572 && oa
!= OSPF6_INTERFACE(lsa
->lsdb
->data
)->area
)
575 if (ntohs(lsa
->header
->type
) == OSPF6_LSTYPE_AS_EXTERNAL
576 && (IS_AREA_STUB(oa
) || IS_AREA_NSSA(oa
)))
579 /* Check for NSSA LSA */
580 if (ntohs(lsa
->header
->type
) == OSPF6_LSTYPE_TYPE_7
581 && !IS_AREA_NSSA(oa
) && !OSPF6_LSA_IS_MAXAGE(lsa
))
584 ospf6_flood_area(from
, lsa
, oa
);
588 void ospf6_flood(struct ospf6_neighbor
*from
, struct ospf6_lsa
*lsa
)
592 ospf6
= ospf6_get_by_lsdb(lsa
);
596 ospf6_flood_process(from
, lsa
, ospf6
);
599 static void ospf6_flood_clear_interface(struct ospf6_lsa
*lsa
,
600 struct ospf6_interface
*oi
)
602 struct listnode
*node
, *nnode
;
603 struct ospf6_neighbor
*on
;
604 struct ospf6_lsa
*rem
;
606 for (ALL_LIST_ELEMENTS(oi
->neighbor_list
, node
, nnode
, on
)) {
607 rem
= ospf6_lsdb_lookup(lsa
->header
->type
, lsa
->header
->id
,
608 lsa
->header
->adv_router
,
610 if (rem
&& !ospf6_lsa_compare(rem
, lsa
)) {
611 if (IS_OSPF6_DEBUG_FLOODING
612 || IS_OSPF6_DEBUG_FLOOD_TYPE(lsa
->header
->type
))
613 zlog_debug("Remove %s from retrans_list of %s",
614 rem
->name
, on
->name
);
615 ospf6_decrement_retrans_count(rem
);
616 ospf6_lsdb_remove(rem
, on
->retrans_list
);
621 void ospf6_flood_clear_area(struct ospf6_lsa
*lsa
, struct ospf6_area
*oa
)
623 struct listnode
*node
, *nnode
;
624 struct ospf6_interface
*oi
;
626 for (ALL_LIST_ELEMENTS(oa
->if_list
, node
, nnode
, oi
)) {
627 if (OSPF6_LSA_SCOPE(lsa
->header
->type
) == OSPF6_SCOPE_LINKLOCAL
628 && oi
!= OSPF6_INTERFACE(lsa
->lsdb
->data
))
631 ospf6_flood_clear_interface(lsa
, oi
);
635 static void ospf6_flood_clear_process(struct ospf6_lsa
*lsa
,
636 struct ospf6
*process
)
638 struct listnode
*node
, *nnode
;
639 struct ospf6_area
*oa
;
641 for (ALL_LIST_ELEMENTS(process
->area_list
, node
, nnode
, oa
)) {
642 if (OSPF6_LSA_SCOPE(lsa
->header
->type
) == OSPF6_SCOPE_AREA
643 && oa
!= OSPF6_AREA(lsa
->lsdb
->data
))
645 if (OSPF6_LSA_SCOPE(lsa
->header
->type
) == OSPF6_SCOPE_LINKLOCAL
646 && oa
!= OSPF6_INTERFACE(lsa
->lsdb
->data
)->area
)
649 if (ntohs(lsa
->header
->type
) == OSPF6_LSTYPE_AS_EXTERNAL
650 && (IS_AREA_STUB(oa
) || (IS_AREA_NSSA(oa
))))
652 /* Check for NSSA LSA */
653 if (ntohs(lsa
->header
->type
) == OSPF6_LSTYPE_TYPE_7
654 && !IS_AREA_NSSA(oa
))
657 ospf6_flood_clear_area(lsa
, oa
);
661 void ospf6_flood_clear(struct ospf6_lsa
*lsa
)
665 ospf6
= ospf6_get_by_lsdb(lsa
);
668 ospf6_flood_clear_process(lsa
, ospf6
);
672 /* RFC2328 13.5 (Table 19): Sending link state acknowledgements. */
673 static void ospf6_acknowledge_lsa_bdrouter(struct ospf6_lsa
*lsa
,
675 struct ospf6_neighbor
*from
)
677 struct ospf6_interface
*oi
;
680 if (IS_OSPF6_DEBUG_FLOODING
681 || IS_OSPF6_DEBUG_FLOOD_TYPE(lsa
->header
->type
))
684 assert(from
&& from
->ospf6_if
);
687 /* LSA is more recent than database copy, but was not flooded
688 back out receiving interface. Delayed acknowledgement sent
689 if advertisement received from Designated Router,
690 otherwide do nothing. */
691 if (ismore_recent
< 0) {
692 if (oi
->drouter
== from
->router_id
) {
695 "Delayed acknowledgement (BDR & MoreRecent & from DR)");
696 /* Delayed acknowledgement */
697 ospf6_lsdb_add(ospf6_lsa_copy(lsa
), oi
->lsack_list
);
698 thread_add_timer(master
, ospf6_lsack_send_interface
, oi
,
699 3, &oi
->thread_send_lsack
);
703 "No acknowledgement (BDR & MoreRecent & ! from DR)");
708 /* LSA is a duplicate, and was treated as an implied acknowledgement.
709 Delayed acknowledgement sent if advertisement received from
710 Designated Router, otherwise do nothing */
711 if (CHECK_FLAG(lsa
->flag
, OSPF6_LSA_DUPLICATE
)
712 && CHECK_FLAG(lsa
->flag
, OSPF6_LSA_IMPLIEDACK
)) {
713 if (oi
->drouter
== from
->router_id
) {
716 "Delayed acknowledgement (BDR & Duplicate & ImpliedAck & from DR)");
717 /* Delayed acknowledgement */
718 ospf6_lsdb_add(ospf6_lsa_copy(lsa
), oi
->lsack_list
);
719 thread_add_timer(master
, ospf6_lsack_send_interface
, oi
,
720 3, &oi
->thread_send_lsack
);
724 "No acknowledgement (BDR & Duplicate & ImpliedAck & ! from DR)");
729 /* LSA is a duplicate, and was not treated as an implied
731 Direct acknowledgement sent */
732 if (CHECK_FLAG(lsa
->flag
, OSPF6_LSA_DUPLICATE
)
733 && !CHECK_FLAG(lsa
->flag
, OSPF6_LSA_IMPLIEDACK
)) {
735 zlog_debug("Direct acknowledgement (BDR & Duplicate)");
736 ospf6_lsdb_add(ospf6_lsa_copy(lsa
), from
->lsack_list
);
737 thread_add_event(master
, ospf6_lsack_send_neighbor
, from
, 0,
738 &from
->thread_send_lsack
);
742 /* LSA's LS age is equal to Maxage, and there is no current instance
743 of the LSA in the link state database, and none of router's
744 neighbors are in states Exchange or Loading */
745 /* Direct acknowledgement sent, but this case is handled in
746 early of ospf6_receive_lsa () */
749 static void ospf6_acknowledge_lsa_allother(struct ospf6_lsa
*lsa
,
751 struct ospf6_neighbor
*from
)
753 struct ospf6_interface
*oi
;
756 if (IS_OSPF6_DEBUG_FLOODING
757 || IS_OSPF6_DEBUG_FLOOD_TYPE(lsa
->header
->type
))
760 assert(from
&& from
->ospf6_if
);
763 /* LSA has been flood back out receiving interface.
764 No acknowledgement sent. */
765 if (CHECK_FLAG(lsa
->flag
, OSPF6_LSA_FLOODBACK
)) {
767 zlog_debug("No acknowledgement (AllOther & FloodBack)");
771 /* LSA is more recent than database copy, but was not flooded
772 back out receiving interface. Delayed acknowledgement sent. */
773 if (ismore_recent
< 0) {
776 "Delayed acknowledgement (AllOther & MoreRecent)");
777 /* Delayed acknowledgement */
778 ospf6_lsdb_add(ospf6_lsa_copy(lsa
), oi
->lsack_list
);
779 thread_add_timer(master
, ospf6_lsack_send_interface
, oi
, 3,
780 &oi
->thread_send_lsack
);
784 /* LSA is a duplicate, and was treated as an implied acknowledgement.
785 No acknowledgement sent. */
786 if (CHECK_FLAG(lsa
->flag
, OSPF6_LSA_DUPLICATE
)
787 && CHECK_FLAG(lsa
->flag
, OSPF6_LSA_IMPLIEDACK
)) {
790 "No acknowledgement (AllOther & Duplicate & ImpliedAck)");
794 /* LSA is a duplicate, and was not treated as an implied
796 Direct acknowledgement sent */
797 if (CHECK_FLAG(lsa
->flag
, OSPF6_LSA_DUPLICATE
)
798 && !CHECK_FLAG(lsa
->flag
, OSPF6_LSA_IMPLIEDACK
)) {
801 "Direct acknowledgement (AllOther & Duplicate)");
802 ospf6_lsdb_add(ospf6_lsa_copy(lsa
), from
->lsack_list
);
803 thread_add_event(master
, ospf6_lsack_send_neighbor
, from
, 0,
804 &from
->thread_send_lsack
);
808 /* LSA's LS age is equal to Maxage, and there is no current instance
809 of the LSA in the link state database, and none of router's
810 neighbors are in states Exchange or Loading */
811 /* Direct acknowledgement sent, but this case is handled in
812 early of ospf6_receive_lsa () */
815 static void ospf6_acknowledge_lsa(struct ospf6_lsa
*lsa
, int ismore_recent
,
816 struct ospf6_neighbor
*from
)
818 struct ospf6_interface
*oi
;
820 assert(from
&& from
->ospf6_if
);
823 if (oi
->state
== OSPF6_INTERFACE_BDR
)
824 ospf6_acknowledge_lsa_bdrouter(lsa
, ismore_recent
, from
);
826 ospf6_acknowledge_lsa_allother(lsa
, ismore_recent
, from
);
829 /* RFC2328 section 13 (4):
830 if MaxAge LSA and if we have no instance, and no neighbor
831 is in states Exchange or Loading
832 returns 1 if match this case, else returns 0 */
833 static int ospf6_is_maxage_lsa_drop(struct ospf6_lsa
*lsa
,
834 struct ospf6_neighbor
*from
)
836 struct ospf6_neighbor
*on
;
837 struct ospf6_interface
*oi
;
838 struct ospf6_area
*oa
;
839 struct ospf6
*process
= NULL
;
840 struct listnode
*i
, *j
, *k
;
843 if (!OSPF6_LSA_IS_MAXAGE(lsa
))
846 if (ospf6_lsdb_lookup(lsa
->header
->type
, lsa
->header
->id
,
847 lsa
->header
->adv_router
, lsa
->lsdb
))
850 process
= from
->ospf6_if
->area
->ospf6
;
852 for (ALL_LIST_ELEMENTS_RO(process
->area_list
, i
, oa
))
853 for (ALL_LIST_ELEMENTS_RO(oa
->if_list
, j
, oi
))
854 for (ALL_LIST_ELEMENTS_RO(oi
->neighbor_list
, k
, on
))
855 if (on
->state
== OSPF6_NEIGHBOR_EXCHANGE
856 || on
->state
== OSPF6_NEIGHBOR_LOADING
)
864 /* RFC2328 section 13 The Flooding Procedure */
865 void ospf6_receive_lsa(struct ospf6_neighbor
*from
,
866 struct ospf6_lsa_header
*lsa_header
)
868 struct ospf6_lsa
*new = NULL
, *old
= NULL
, *rem
= NULL
;
871 unsigned int time_delta_ms
;
876 /* if we receive a LSA with invalid seqnum drop it */
877 if (ntohl(lsa_header
->seqnum
) - 1 == OSPF_MAX_SEQUENCE_NUMBER
) {
878 if (IS_OSPF6_DEBUG_EXAMIN_TYPE(lsa_header
->type
)) {
880 "received lsa [%s Id:%pI4 Adv:%pI4] with invalid seqnum 0x%x, ignore",
881 ospf6_lstype_name(lsa_header
->type
),
882 &lsa_header
->id
, &lsa_header
->adv_router
,
883 ntohl(lsa_header
->seqnum
));
888 /* make lsa structure for received lsa */
889 new = ospf6_lsa_create(lsa_header
);
891 if (IS_OSPF6_DEBUG_FLOODING
892 || IS_OSPF6_DEBUG_FLOOD_TYPE(new->header
->type
)) {
894 zlog_debug("LSA Receive from %s", from
->name
);
895 ospf6_lsa_header_print(new);
898 /* (1) LSA Checksum */
899 if (!ospf6_lsa_checksum_valid(new->header
)) {
901 zlog_debug("Wrong LSA Checksum, discard");
902 ospf6_lsa_delete(new);
906 /* (2) Examine the LSA's LS type.
907 RFC2470 3.5.1. Receiving Link State Update packets */
908 if (IS_AREA_STUB(from
->ospf6_if
->area
)
909 && OSPF6_LSA_SCOPE(new->header
->type
) == OSPF6_SCOPE_AS
) {
912 "AS-External-LSA (or AS-scope LSA) in stub area, discard");
913 ospf6_lsa_delete(new);
917 /* (3) LSA which have reserved scope is discarded
918 RFC2470 3.5.1. Receiving Link State Update packets */
919 /* Flooding scope check. LSAs with unknown scope are discarded here.
920 Set appropriate LSDB for the LSA */
921 switch (OSPF6_LSA_SCOPE(new->header
->type
)) {
922 case OSPF6_SCOPE_LINKLOCAL
:
923 new->lsdb
= from
->ospf6_if
->lsdb
;
925 case OSPF6_SCOPE_AREA
:
926 new->lsdb
= from
->ospf6_if
->area
->lsdb
;
929 new->lsdb
= from
->ospf6_if
->area
->ospf6
->lsdb
;
933 zlog_debug("LSA has reserved scope, discard");
934 ospf6_lsa_delete(new);
938 /* (4) if MaxAge LSA and if we have no instance, and no neighbor
939 is in states Exchange or Loading */
940 if (ospf6_is_maxage_lsa_drop(new, from
)) {
944 "Drop MaxAge LSA with direct acknowledgement.");
946 /* a) Acknowledge back to neighbor (Direct acknowledgement,
948 ospf6_lsdb_add(ospf6_lsa_copy(new), from
->lsack_list
);
949 thread_add_event(master
, ospf6_lsack_send_neighbor
, from
, 0,
950 &from
->thread_send_lsack
);
953 ospf6_lsa_delete(new);
958 /* lookup the same database copy in lsdb */
959 old
= ospf6_lsdb_lookup(new->header
->type
, new->header
->id
,
960 new->header
->adv_router
, new->lsdb
);
962 ismore_recent
= ospf6_lsa_compare(new, old
);
963 if (ntohl(new->header
->seqnum
) == ntohl(old
->header
->seqnum
)) {
965 zlog_debug("Received is duplicated LSA");
966 SET_FLAG(new->flag
, OSPF6_LSA_DUPLICATE
);
970 /* if no database copy or received is more recent */
971 if (old
== NULL
|| ismore_recent
< 0) {
972 bool self_originated
;
974 /* in case we have no database copy */
977 /* (a) MinLSArrival check */
979 struct timeval now
, res
;
981 timersub(&now
, &old
->installed
, &res
);
983 (res
.tv_sec
* 1000) + (int)(res
.tv_usec
/ 1000);
985 < from
->ospf6_if
->area
->ospf6
->lsa_minarrival
) {
988 "LSA can't be updated within MinLSArrival, %dms < %dms, discard",
990 from
->ospf6_if
->area
->ospf6
992 ospf6_lsa_delete(new);
993 return; /* examin next lsa */
997 monotime(&new->received
);
1001 "Install, Flood, Possibly acknowledge the received LSA");
1003 /* Remove older copies of this LSA from retx lists */
1005 ospf6_flood_clear(old
);
1007 self_originated
= (new->header
->adv_router
1008 == from
->ospf6_if
->area
->ospf6
->router_id
);
1010 /* Received non-self-originated Grace LSA. */
1011 if (IS_GRACE_LSA(new) && !self_originated
) {
1012 struct ospf6
*ospf6
;
1014 ospf6
= ospf6_get_by_lsdb(new);
1018 if (OSPF6_LSA_IS_MAXAGE(new)) {
1020 if (IS_DEBUG_OSPF6_GR
)
1022 "%s, Received a maxage GraceLSA from router %pI4",
1024 &new->header
->adv_router
);
1026 ospf6_process_maxage_grace_lsa(
1029 if (IS_DEBUG_OSPF6_GR
)
1031 "%s, GraceLSA doesn't exist in lsdb, so discarding GraceLSA",
1037 if (IS_DEBUG_OSPF6_GR
)
1039 "%s, Received a GraceLSA from router %pI4",
1041 &new->header
->adv_router
);
1043 if (ospf6_process_grace_lsa(ospf6
, new, from
)
1044 == OSPF6_GR_NOT_HELPER
) {
1045 if (IS_DEBUG_OSPF6_GR
)
1047 "%s, Not moving to HELPER role, So dicarding GraceLSA",
1054 /* (b) immediately flood and (c) remove from all retrans-list */
1055 /* Prevent self-originated LSA to be flooded. this is to make
1056 * reoriginated instance of the LSA not to be rejected by other
1057 * routers due to MinLSArrival.
1059 if (!self_originated
)
1060 ospf6_flood(from
, new);
1062 /* (d), installing lsdb, which may cause routing
1063 table calculation (replacing database copy) */
1064 ospf6_install_lsa(new);
1066 if (OSPF6_LSA_IS_MAXAGE(new))
1067 ospf6_maxage_remove(from
->ospf6_if
->area
->ospf6
);
1069 /* (e) possibly acknowledge */
1070 ospf6_acknowledge_lsa(new, ismore_recent
, from
);
1072 /* (f) Self Originated LSA, section 13.4 */
1073 if (self_originated
) {
1074 if (from
->ospf6_if
->area
->ospf6
->gr_info
1075 .restart_in_progress
) {
1076 if (IS_DEBUG_OSPF6_GR
)
1078 "Graceful Restart in progress -- not flushing self-originated LSA: %s",
1083 /* Self-originated LSA (newer than ours) is received
1085 another router. We have to make a new instance of the
1087 or have to flush this LSA. */
1090 "Newer instance of the self-originated LSA");
1091 zlog_debug("Schedule reorigination");
1093 thread_add_event(master
, ospf6_lsa_refresh
, new, 0,
1097 struct ospf6
*ospf6
= from
->ospf6_if
->area
->ospf6
;
1098 struct ospf6_area
*area
= from
->ospf6_if
->area
;
1099 if (ospf6
->gr_info
.restart_in_progress
)
1100 ospf6_gr_check_lsdb_consistency(ospf6
, area
);
1105 /* (6) if there is instance on sending neighbor's request list */
1106 if (ospf6_lsdb_lookup(new->header
->type
, new->header
->id
,
1107 new->header
->adv_router
, from
->request_list
)) {
1108 /* if no database copy, should go above state (5) */
1112 "Received is not newer, on the neighbor %s request-list",
1115 "BadLSReq, discard the received LSA lsa %s send badLSReq",
1119 thread_add_event(master
, bad_lsreq
, from
, 0, NULL
);
1121 ospf6_lsa_delete(new);
1125 /* (7) if neither one is more recent */
1126 if (ismore_recent
== 0) {
1129 "The same instance as database copy (neither recent)");
1131 /* (a) if on retrans-list, Treat this LSA as an Ack: Implied Ack
1133 rem
= ospf6_lsdb_lookup(new->header
->type
, new->header
->id
,
1134 new->header
->adv_router
,
1135 from
->retrans_list
);
1139 "It is on the neighbor's retrans-list.");
1141 "Treat as an Implied acknowledgement");
1143 SET_FLAG(new->flag
, OSPF6_LSA_IMPLIEDACK
);
1144 ospf6_decrement_retrans_count(rem
);
1145 ospf6_lsdb_remove(rem
, from
->retrans_list
);
1149 zlog_debug("Possibly acknowledge and then discard");
1151 /* (b) possibly acknowledge */
1152 ospf6_acknowledge_lsa(new, ismore_recent
, from
);
1154 ospf6_lsa_delete(new);
1158 /* (8) previous database copy is more recent */
1162 /* If database copy is in 'Seqnumber Wrapping',
1163 simply discard the received LSA */
1164 if (OSPF6_LSA_IS_MAXAGE(old
)
1165 && old
->header
->seqnum
== htonl(OSPF_MAX_SEQUENCE_NUMBER
)) {
1167 zlog_debug("The LSA is in Seqnumber Wrapping");
1168 zlog_debug("MaxAge & MaxSeqNum, discard");
1170 ospf6_lsa_delete(new);
1174 /* Otherwise, Send database copy of this LSA to this neighbor */
1177 zlog_debug("Database copy is more recent.");
1179 "Send back directly and then discard");
1182 /* Neighbor router sent recent age for LSA,
1183 * Router could be restarted while current copy is
1184 * MAXAGEd and not removed.*/
1185 if (OSPF6_LSA_IS_MAXAGE(old
)
1186 && !OSPF6_LSA_IS_MAXAGE(new)) {
1187 if (new->header
->adv_router
1188 != from
->ospf6_if
->area
->ospf6
->router_id
) {
1191 "%s: Current copy of LSA %s is MAXAGE, but new has recent age, flooding/installing.",
1192 __PRETTY_FUNCTION__
, old
->name
);
1193 ospf6_lsa_purge(old
);
1194 ospf6_flood(from
, new);
1195 ospf6_install_lsa(new);
1198 /* For self-originated LSA, only trust
1199 * ourselves. Fall through and send
1200 * LS Update with our current copy.
1204 "%s: Current copy of self-originated LSA %s is MAXAGE, but new has recent age, re-sending current one.",
1205 __PRETTY_FUNCTION__
, old
->name
);
1208 /* XXX, MinLSArrival check !? RFC 2328 13 (8) */
1210 ospf6_lsdb_add(ospf6_lsa_copy(old
),
1211 from
->lsupdate_list
);
1212 thread_add_event(master
, ospf6_lsupdate_send_neighbor
,
1213 from
, 0, &from
->thread_send_lsupdate
);
1215 ospf6_lsa_delete(new);
1221 DEFUN (debug_ospf6_flooding
,
1222 debug_ospf6_flooding_cmd
,
1223 "debug ospf6 flooding",
1226 "Debug OSPFv3 flooding function\n"
1229 OSPF6_DEBUG_FLOODING_ON();
1233 DEFUN (no_debug_ospf6_flooding
,
1234 no_debug_ospf6_flooding_cmd
,
1235 "no debug ospf6 flooding",
1239 "Debug OSPFv3 flooding function\n"
1242 OSPF6_DEBUG_FLOODING_OFF();
1246 int config_write_ospf6_debug_flood(struct vty
*vty
)
1248 if (IS_OSPF6_DEBUG_FLOODING
)
1249 vty_out(vty
, "debug ospf6 flooding\n");
1253 void install_element_ospf6_debug_flood(void)
1255 install_element(ENABLE_NODE
, &debug_ospf6_flooding_cmd
);
1256 install_element(ENABLE_NODE
, &no_debug_ospf6_flooding_cmd
);
1257 install_element(CONFIG_NODE
, &debug_ospf6_flooding_cmd
);
1258 install_element(CONFIG_NODE
, &no_debug_ospf6_flooding_cmd
);