1 // SPDX-License-Identifier: GPL-2.0-or-later
3 * OSPF Flooding -- RFC2328 Section 13.
4 * Copyright (C) 1999, 2000 Toshiaki Takada
20 #include "ospfd/ospfd.h"
21 #include "ospfd/ospf_interface.h"
22 #include "ospfd/ospf_ism.h"
23 #include "ospfd/ospf_asbr.h"
24 #include "ospfd/ospf_lsa.h"
25 #include "ospfd/ospf_lsdb.h"
26 #include "ospfd/ospf_neighbor.h"
27 #include "ospfd/ospf_nsm.h"
28 #include "ospfd/ospf_spf.h"
29 #include "ospfd/ospf_flood.h"
30 #include "ospfd/ospf_packet.h"
31 #include "ospfd/ospf_abr.h"
32 #include "ospfd/ospf_route.h"
33 #include "ospfd/ospf_zebra.h"
34 #include "ospfd/ospf_dump.h"
36 extern struct zclient
*zclient
;
38 /** @brief Function to refresh type-5 and type-7 DNA
39 * LSAs when we receive an indication LSA.
40 * @param Ospf instance.
43 void ospf_refresh_dna_type5_and_type7_lsas(struct ospf
*ospf
)
45 struct route_node
*rn
;
46 struct ospf_lsa
*lsa
= NULL
;
48 LSDB_LOOP (EXTERNAL_LSDB(ospf
), rn
, lsa
)
49 if (IS_LSA_SELF(lsa
) &&
50 CHECK_FLAG(lsa
->data
->ls_age
, DO_NOT_AGE
))
51 ospf_lsa_refresh(ospf
, lsa
);
53 LSDB_LOOP (NSSA_LSDB(ospf
), rn
, lsa
)
54 if (IS_LSA_SELF(lsa
) &&
55 CHECK_FLAG(lsa
->data
->ls_age
, DO_NOT_AGE
))
56 ospf_lsa_refresh(ospf
, lsa
);
59 /** @brief Function to update area flood reduction states.
60 * @param area pointer.
63 void ospf_area_update_fr_state(struct ospf_area
*area
)
65 unsigned int count_router_lsas
= 0;
71 (unsigned int)(ospf_lsdb_count(area
->lsdb
, OSPF_ROUTER_LSA
) -
72 ospf_lsdb_count_self(area
->lsdb
,
75 if (count_router_lsas
>
76 (unsigned int)area
->fr_info
.router_lsas_recv_dc_bit
) {
77 area
->fr_info
.enabled
= false;
78 area
->fr_info
.area_dc_clear
= true;
80 } else if (count_router_lsas
<
81 (unsigned int)area
->fr_info
.router_lsas_recv_dc_bit
) {
82 /* This can never happen, total number of router lsas received
83 * can never be less than router lsas received with dc bit set
85 OSPF_LOG_ERR("%s: Counter mismatch for area %pI4", __func__
,
88 "%s: router LSAs in lsdb %d router LSAs recvd with dc bit set %d",
89 __func__
, count_router_lsas
,
90 area
->fr_info
.router_lsas_recv_dc_bit
);
94 area
->fr_info
.area_dc_clear
= false;
96 if (OSPF_FR_CONFIG(area
->ospf
, area
)) {
97 if (!area
->fr_info
.enabled
) {
98 area
->fr_info
.enabled
= true;
99 area
->fr_info
.state_changed
= true;
102 area
->fr_info
.enabled
= false;
103 area
->fr_info
.area_dc_clear
= true;
107 /* Do the LSA acking specified in table 19, Section 13.5, row 2
108 * This get called from ospf_flood_out_interface. Declared inline
110 static void ospf_flood_delayed_lsa_ack(struct ospf_neighbor
*inbr
,
111 struct ospf_lsa
*lsa
)
113 /* LSA is more recent than database copy, but was not
114 flooded back out receiving interface. Delayed
115 acknowledgment sent. If interface is in Backup state
116 delayed acknowledgment sent only if advertisement
117 received from Designated Router, otherwise do nothing See
118 RFC 2328 Section 13.5 */
120 /* Whether LSA is more recent or not, and whether this is in
121 response to the LSA being sent out recieving interface has been
122 worked out previously */
124 /* Deal with router as BDR */
125 if (inbr
->oi
->state
== ISM_Backup
&& !NBR_IS_DR(inbr
))
128 /* Schedule a delayed LSA Ack to be sent */
129 listnode_add(inbr
->oi
->ls_ack
,
130 ospf_lsa_lock(lsa
)); /* delayed LSA Ack */
133 /* Check LSA is related to external info. */
134 struct external_info
*ospf_external_info_check(struct ospf
*ospf
,
135 struct ospf_lsa
*lsa
)
137 struct as_external_lsa
*al
;
138 struct prefix_ipv4 p
;
139 struct route_node
*rn
;
140 struct list
*ext_list
;
141 struct listnode
*node
;
142 struct ospf_external
*ext
;
145 al
= (struct as_external_lsa
*)lsa
->data
;
148 p
.prefix
= lsa
->data
->id
;
149 p
.prefixlen
= ip_masklen(al
->mask
);
151 for (type
= 0; type
< ZEBRA_ROUTE_MAX
; type
++) {
155 is_default_prefix4(&p
)
157 zclient
->default_information
[AFI_IP
],
159 : (zclient
->mi_redist
[AFI_IP
][type
].enabled
161 zclient
->redist
[AFI_IP
][type
],
163 // Pending: check for MI above.
165 ext_list
= ospf
->external
[type
];
169 for (ALL_LIST_ELEMENTS_RO(ext_list
, node
, ext
)) {
171 if (ext
->external_info
)
172 rn
= route_node_lookup(
174 (struct prefix
*)&p
);
176 route_unlock_node(rn
);
177 if (rn
->info
!= NULL
)
178 return (struct external_info
*)
185 if (is_default_prefix4(&p
) && ospf
->external
[DEFAULT_ROUTE
]) {
186 ext_list
= ospf
->external
[DEFAULT_ROUTE
];
188 for (ALL_LIST_ELEMENTS_RO(ext_list
, node
, ext
)) {
189 if (!ext
->external_info
)
192 rn
= route_node_lookup(ext
->external_info
,
193 (struct prefix
*)&p
);
196 route_unlock_node(rn
);
197 if (rn
->info
!= NULL
)
198 return (struct external_info
*)rn
->info
;
204 static void ospf_process_self_originated_lsa(struct ospf
*ospf
,
205 struct ospf_lsa
*new,
206 struct ospf_area
*area
)
208 struct ospf_interface
*oi
;
209 struct external_info
*ei
;
210 struct listnode
*node
;
211 struct as_external_lsa
*al
;
212 struct prefix_ipv4 p
;
213 struct ospf_external_aggr_rt
*aggr
;
215 if (IS_DEBUG_OSPF_EVENT
)
217 "%s:LSA[Type%d:%pI4]: Process self-originated LSA seq 0x%x",
218 ospf_get_name(ospf
), new->data
->type
,
219 &new->data
->id
, ntohl(new->data
->ls_seqnum
));
221 /* If we're here, we installed a self-originated LSA that we received
222 from a neighbor, i.e. it's more recent. We must see whether we want
224 If yes, we should use this LSA's sequence number and reoriginate
226 if not --- we must flush this LSA from the domain. */
227 switch (new->data
->type
) {
228 case OSPF_ROUTER_LSA
:
229 /* Originate a new instance and schedule flooding */
230 if (area
->router_lsa_self
)
231 area
->router_lsa_self
->data
->ls_seqnum
=
232 new->data
->ls_seqnum
;
233 ospf_router_lsa_update_area(area
);
235 case OSPF_NETWORK_LSA
:
236 case OSPF_OPAQUE_LINK_LSA
:
237 /* We must find the interface the LSA could belong to.
238 If the interface is no more a broadcast type or we are no
240 the DR, we flush the LSA otherwise -- create the new instance
242 schedule flooding. */
244 /* Look through all interfaces, not just area, since interface
245 could be moved from one area to another. */
246 for (ALL_LIST_ELEMENTS_RO(ospf
->oiflist
, node
, oi
))
247 /* These are sanity check. */
248 if (IPV4_ADDR_SAME(&oi
->address
->u
.prefix4
,
251 || oi
->type
!= OSPF_IFTYPE_BROADCAST
252 || !IPV4_ADDR_SAME(&oi
->address
->u
.prefix4
,
254 ospf_schedule_lsa_flush_area(area
, new);
258 if (new->data
->type
== OSPF_OPAQUE_LINK_LSA
) {
259 ospf_opaque_lsa_refresh(new);
263 if (oi
->network_lsa_self
)
264 oi
->network_lsa_self
->data
->ls_seqnum
=
265 new->data
->ls_seqnum
;
266 /* Schedule network-LSA origination. */
267 ospf_network_lsa_update(oi
);
271 case OSPF_SUMMARY_LSA
:
272 case OSPF_ASBR_SUMMARY_LSA
:
273 ospf_schedule_abr_task(ospf
);
275 case OSPF_AS_EXTERNAL_LSA
:
276 case OSPF_AS_NSSA_LSA
:
277 if ((new->data
->type
== OSPF_AS_EXTERNAL_LSA
)
278 && CHECK_FLAG(new->flags
, OSPF_LSA_LOCAL_XLT
)) {
279 ospf_translated_nssa_refresh(ospf
, NULL
, new);
283 al
= (struct as_external_lsa
*)new->data
;
285 p
.prefixlen
= ip_masklen(al
->mask
);
286 p
.prefix
= new->data
->id
;
288 ei
= ospf_external_info_check(ospf
, new);
290 if (ospf_external_aggr_match(ospf
, &ei
->p
)) {
291 if (IS_DEBUG_OSPF(lsa
, EXTNL_LSA_AGGR
))
293 "%s, Matching external aggregate route found for %pI4, so don't refresh it.",
297 /* Aggregated external route shouldn't
300 if (!IS_LSA_MAXAGE(new))
301 ospf_lsa_flush_as(ospf
, new);
306 ospf_external_lsa_refresh(ospf
, new, ei
,
307 LSA_REFRESH_FORCE
, false);
309 aggr
= (struct ospf_external_aggr_rt
*)
310 ospf_extrenal_aggregator_lookup(ospf
, &p
);
312 struct external_info ei_aggr
;
315 sizeof(struct external_info
));
317 ei_aggr
.tag
= aggr
->tag
;
318 ei_aggr
.instance
= ospf
->instance
;
319 ei_aggr
.route_map_set
.metric
= -1;
320 ei_aggr
.route_map_set
.metric_type
= -1;
322 ospf_external_lsa_refresh(ospf
, new, &ei_aggr
,
323 LSA_REFRESH_FORCE
, true);
324 SET_FLAG(aggr
->flags
,
325 OSPF_EXTERNAL_AGGRT_ORIGINATED
);
327 ospf_lsa_flush_as(ospf
, new);
330 case OSPF_OPAQUE_AREA_LSA
:
331 ospf_opaque_lsa_refresh(new);
333 case OSPF_OPAQUE_AS_LSA
:
334 ospf_opaque_lsa_refresh(new);
335 /* Reconsideration may needed. */ /* XXX */
342 /* OSPF LSA flooding -- RFC2328 Section 13.(5). */
344 /* Now Updated for NSSA operation, as follows:
347 Type-5's have no change. Blocked to STUB or NSSA.
349 Type-7's can be received, and if a DR
350 they will also flood the local NSSA Area as Type-7's
352 If a Self-Originated LSA (now an ASBR),
353 The LSDB will be updated as Type-5's, (for continual re-fresh)
355 If an NSSA-IR it is installed/flooded as Type-7, P-bit on.
356 if an NSSA-ABR it is installed/flooded as Type-7, P-bit off.
358 Later, during the ABR TASK, if the ABR is the Elected NSSA
359 translator, then All Type-7s (with P-bit ON) are Translated to
360 Type-5's and flooded to all non-NSSA/STUB areas.
362 During ASE Calculations,
363 non-ABRs calculate external routes from Type-7's
364 ABRs calculate external routes from Type-5's and non-self Type-7s
366 int ospf_flood(struct ospf
*ospf
, struct ospf_neighbor
*nbr
,
367 struct ospf_lsa
*current
, struct ospf_lsa
*new)
369 struct ospf_interface
*oi
;
372 /* Type-7 LSA's will be flooded throughout their native NSSA area,
373 but will also be flooded as Type-5's into ABR capable links. */
375 if (IS_DEBUG_OSPF_EVENT
)
377 "%s:LSA[Flooding]: start, NBR %pI4 (%s), cur(%p), New-LSA[%s]",
378 ospf_get_name(ospf
), &nbr
->router_id
,
379 lookup_msg(ospf_nsm_state_msg
, nbr
->state
, NULL
),
380 (void *)current
, dump_lsa_key(new));
384 /* If there is already a database copy, and if the
385 database copy was received via flooding and installed less
386 than MinLSArrival seconds ago, discard the new LSA
387 (without acknowledging it). */
388 if (current
!= NULL
) /* -- endo. */
390 if (IS_LSA_SELF(current
)
391 && (ntohs(current
->data
->ls_age
) == 0
392 && ntohl(current
->data
->ls_seqnum
)
393 == OSPF_INITIAL_SEQUENCE_NUMBER
)) {
394 if (IS_DEBUG_OSPF_EVENT
)
396 "%s:LSA[Flooding]: Got a self-originated LSA, while local one is initial instance.",
397 ospf_get_name(ospf
));
398 ; /* Accept this LSA for quick LSDB resynchronization.
400 } else if (monotime_since(¤t
->tv_recv
, NULL
)
401 < ospf
->min_ls_arrival
* 1000LL) {
402 if (IS_DEBUG_OSPF_EVENT
)
404 "%s:LSA[Flooding]: LSA is received recently.",
405 ospf_get_name(ospf
));
410 /* Flood the new LSA out some subset of the router's interfaces.
411 In some cases (e.g., the state of the receiving interface is
412 DR and the LSA was received from a router other than the
413 Backup DR) the LSA will be flooded back out the receiving
415 lsa_ack_flag
= ospf_flood_through(ospf
, nbr
, new);
417 /* Remove the current database copy from all neighbors' Link state
418 retransmission lists. AS_EXTERNAL and AS_EXTERNAL_OPAQUE does
419 ^^^^^^^^^^^^^^^^^^^^^^^
421 All other (even NSSA's) do have area ID. */
423 switch (current
->data
->type
) {
424 case OSPF_AS_EXTERNAL_LSA
:
425 case OSPF_OPAQUE_AS_LSA
:
426 ospf_ls_retransmit_delete_nbr_as(ospf
, current
);
429 ospf_ls_retransmit_delete_nbr_area(oi
->area
, current
);
434 /* Do some internal house keeping that is needed here */
435 SET_FLAG(new->flags
, OSPF_LSA_RECEIVED
);
436 (void)ospf_lsa_is_self_originated(ospf
, new); /* Let it set the flag */
438 /* Received non-self-originated Grace LSA */
439 if (IS_GRACE_LSA(new) && !IS_LSA_SELF(new)) {
441 if (IS_LSA_MAXAGE(new)) {
443 /* Handling Max age grace LSA.*/
444 if (IS_DEBUG_OSPF_GR
)
446 "%s, Received a maxage GRACE-LSA from router %pI4",
447 __func__
, &new->data
->adv_router
);
450 ospf_process_maxage_grace_lsa(ospf
, new, nbr
);
452 if (IS_DEBUG_OSPF_GR
)
454 "%s, Grace LSA doesn't exist in lsdb, so discarding grace lsa",
459 if (IS_DEBUG_OSPF_GR
)
461 "%s, Received a GRACE-LSA from router %pI4",
462 __func__
, &new->data
->adv_router
);
464 if (ospf_process_grace_lsa(ospf
, new, nbr
)
465 == OSPF_GR_NOT_HELPER
) {
466 if (IS_DEBUG_OSPF_GR
)
468 "%s, Not moving to HELPER role, So discarding grace LSA",
475 /* Install the new LSA in the link state database
476 (replacing the current database copy). This may cause the
477 routing table calculation to be scheduled. In addition,
478 timestamp the new LSA with the current time. The flooding
479 procedure cannot overwrite the newly installed LSA until
480 MinLSArrival seconds have elapsed. */
482 if (!(new = ospf_lsa_install(ospf
, oi
, new)))
483 return -1; /* unknown LSA type or any other error condition */
485 /* check if the installed LSA is an indication LSA */
486 if (ospf_check_indication_lsa(new) && !IS_LSA_SELF(new) &&
487 !IS_LSA_MAXAGE(new)) {
488 new->area
->fr_info
.area_ind_lsa_recvd
= true;
489 /* check if there are already type 5 LSAs originated
490 * with DNA bit set, if yes reoriginate those LSAs.
492 ospf_refresh_dna_type5_and_type7_lsas(ospf
);
495 /* Check if we recived an indication LSA flush on backbone
498 ospf_recv_indication_lsa_flush(new);
500 if (new->area
&& OSPF_FR_CONFIG(ospf
, new->area
)) {
501 struct lsa_header
const *lsah
= new->data
;
503 if (!CHECK_FLAG(lsah
->options
, OSPF_OPTION_DC
) &&
504 !ospf_check_indication_lsa(new)) {
506 new->area
->fr_info
.area_dc_clear
= true;
507 /* check of previously area supported flood reduction */
508 if (new->area
->fr_info
.enabled
) {
509 new->area
->fr_info
.enabled
= false;
512 "Flood Reduction STATE on -> off by %s LSA",
514 /* if yes update all the lsa to the area the
515 * new LSAs will have DNA bit set to 0.
517 ospf_refresh_area_self_lsas(new->area
);
519 } else if (!new->area
->fr_info
.enabled
) {
520 /* check again after installing new LSA that area
521 * supports flood reduction.
523 ospf_area_update_fr_state(new->area
);
524 if (new->area
->fr_info
.enabled
) {
527 "Flood Reduction STATE off -> on by %s LSA",
529 ospf_refresh_area_self_lsas(new->area
);
534 /* Acknowledge the receipt of the LSA by sending a Link State
535 Acknowledgment packet back out the receiving interface. */
537 ospf_flood_delayed_lsa_ack(nbr
, new);
539 /* If this new LSA indicates that it was originated by the
540 receiving router itself, the router must take special action,
541 either updating the LSA or in some cases flushing it from
542 the routing domain. */
543 if (ospf_lsa_is_self_originated(ospf
, new))
544 ospf_process_self_originated_lsa(ospf
, new, oi
->area
);
546 /* Update statistics value for OSPF-MIB. */
547 ospf
->rx_lsa_count
++;
552 /* OSPF LSA flooding -- RFC2328 Section 13.3. */
553 int ospf_flood_through_interface(struct ospf_interface
*oi
,
554 struct ospf_neighbor
*inbr
,
555 struct ospf_lsa
*lsa
)
557 struct ospf_neighbor
*onbr
;
558 struct route_node
*rn
;
561 if (IS_DEBUG_OSPF_EVENT
)
563 "%s: considering int %s (%s), INBR(%pI4), LSA[%s] AGE %u",
564 __func__
, IF_NAME(oi
), ospf_get_name(oi
->ospf
),
565 inbr
? &inbr
->router_id
: NULL
, dump_lsa_key(lsa
),
566 ntohs(lsa
->data
->ls_age
));
568 if (!ospf_if_is_enable(oi
))
571 /* If flood reduction is configured, set the DC bit on the lsa. */
572 if (IS_LSA_SELF(lsa
)) {
573 if (OSPF_FR_CONFIG(oi
->area
->ospf
, oi
->area
)) {
574 if (!ospf_check_indication_lsa(lsa
)) {
575 SET_FLAG(lsa
->data
->options
, OSPF_OPTION_DC
);
576 ospf_lsa_checksum(lsa
->data
);
578 } else if (CHECK_FLAG(lsa
->data
->options
, OSPF_OPTION_DC
)) {
579 UNSET_FLAG(lsa
->data
->options
, OSPF_OPTION_DC
);
580 ospf_lsa_checksum(lsa
->data
);
583 /* If flood reduction is enabled then set DNA bit on the
586 if (oi
->area
->fr_info
.enabled
)
587 SET_FLAG(lsa
->data
->ls_age
, DO_NOT_AGE
);
590 /* Remember if new LSA is added to a retransmit list. */
593 /* Each of the neighbors attached to this interface are examined,
594 to determine whether they must receive the new LSA. The following
595 steps are executed for each neighbor: */
596 for (rn
= route_top(oi
->nbrs
); rn
; rn
= route_next(rn
)) {
597 struct ospf_lsa
*ls_req
;
599 if (rn
->info
== NULL
)
603 if (IS_DEBUG_OSPF_EVENT
)
605 "%s: considering nbr %pI4 via %s (%s), state: %s",
606 __func__
, &onbr
->router_id
, IF_NAME(oi
),
607 ospf_get_name(oi
->ospf
),
608 lookup_msg(ospf_nsm_state_msg
, onbr
->state
,
611 /* If the neighbor is in a lesser state than Exchange, it
612 does not participate in flooding, and the next neighbor
613 should be examined. */
614 if (onbr
->state
< NSM_Exchange
)
617 /* If the adjacency is not yet full (neighbor state is
618 Exchange or Loading), examine the Link state request
619 list associated with this adjacency. If there is an
620 instance of the new LSA on the list, it indicates that
621 the neighboring router has an instance of the LSA
622 already. Compare the new LSA to the neighbor's copy: */
623 if (onbr
->state
< NSM_Full
) {
624 if (IS_DEBUG_OSPF_EVENT
)
626 "%s: adj to onbr %pI4 is not Full (%s)",
627 __func__
, &onbr
->router_id
,
628 lookup_msg(ospf_nsm_state_msg
,
630 ls_req
= ospf_ls_request_lookup(onbr
, lsa
);
631 if (ls_req
!= NULL
) {
634 ret
= ospf_lsa_more_recent(ls_req
, lsa
);
635 /* The new LSA is less recent. */
638 /* The two copies are the same instance, then
640 the LSA from the Link state request list. */
642 ospf_ls_request_delete(onbr
, ls_req
);
643 ospf_check_nbr_loading(onbr
);
646 /* The new LSA is more recent. Delete the LSA
647 from the Link state request list. */
649 ospf_ls_request_delete(onbr
, ls_req
);
650 ospf_check_nbr_loading(onbr
);
655 if (IS_OPAQUE_LSA(lsa
->data
->type
)) {
656 if (!CHECK_FLAG(onbr
->options
, OSPF_OPTION_O
)) {
657 if (IS_DEBUG_OSPF(lsa
, LSA_FLOODING
))
659 "%s: Skipping neighbor %s via %pI4 -- Not Opaque-capable.",
660 __func__
, IF_NAME(oi
),
666 /* If the new LSA was received from this neighbor,
667 examine the next neighbor. */
670 * Triggered by LSUpd message parser "ospf_ls_upd ()".
671 * E.g., all LSAs handling here is received via network.
673 if (IPV4_ADDR_SAME(&inbr
->router_id
,
675 if (IS_DEBUG_OSPF(lsa
, LSA_FLOODING
))
677 "%s: Skipping neighbor %s via %pI4 -- inbr == onbr.",
678 __func__
, IF_NAME(oi
),
684 * Triggered by MaxAge remover, so far.
685 * NULL "inbr" means flooding starts from this node.
687 if (IPV4_ADDR_SAME(&lsa
->data
->adv_router
,
689 if (IS_DEBUG_OSPF(lsa
, LSA_FLOODING
))
691 "%s: Skipping neighbor %s via %pI4 -- lsah->adv_router == onbr.",
692 __func__
, IF_NAME(oi
),
698 /* Add the new LSA to the Link state retransmission list
699 for the adjacency. The LSA will be retransmitted
700 at intervals until an acknowledgment is seen from
702 ospf_ls_retransmit_add(onbr
, lsa
);
706 /* If in the previous step, the LSA was NOT added to any of
707 the Link state retransmission lists, there is no need to
708 flood the LSA out the interface. */
709 if (retx_flag
== 0) {
710 return (inbr
&& inbr
->oi
== oi
);
713 /* if we've received the lsa on this interface we need to perform
714 additional checking */
715 if (inbr
&& (inbr
->oi
== oi
)) {
716 /* If the new LSA was received on this interface, and it was
717 received from either the Designated Router or the Backup
718 Designated Router, chances are that all the neighbors have
719 received the LSA already. */
720 if (NBR_IS_DR(inbr
) || NBR_IS_BDR(inbr
)) {
721 if (IS_DEBUG_OSPF(lsa
, LSA_FLOODING
))
722 zlog_debug("%s: DR/BDR NOT SEND to int %s (%s)",
723 __func__
, IF_NAME(oi
),
724 ospf_get_name(oi
->ospf
));
728 /* If the new LSA was received on this interface, and the
729 interface state is Backup, examine the next interface. The
730 Designated Router will do the flooding on this interface.
731 However, if the Designated Router fails the router will
732 end up retransmitting the updates. */
734 if (oi
->state
== ISM_Backup
) {
735 if (IS_DEBUG_OSPF(lsa
, LSA_FLOODING
))
737 "%s: ISM_Backup NOT SEND to int %s (%s)",
738 __func__
, IF_NAME(oi
),
739 ospf_get_name(oi
->ospf
));
744 /* The LSA must be flooded out the interface. Send a Link State
745 Update packet (including the new LSA as contents) out the
746 interface. The LSA's LS age must be incremented by InfTransDelay
747 (which must be > 0) when it is copied into the outgoing Link
748 State Update packet (until the LS age field reaches the maximum
750 if (IS_DEBUG_OSPF(lsa
, LSA_FLOODING
))
751 zlog_debug("%s: DR/BDR sending upd to int %s (%s)", __func__
,
752 IF_NAME(oi
), ospf_get_name(oi
->ospf
));
754 /* RFC2328 Section 13.3
755 On non-broadcast networks, separate Link State Update
756 packets must be sent, as unicasts, to each adjacent neighbor
757 (i.e., those in state Exchange or greater). The destination
758 IP addresses for these packets are the neighbors' IP
760 if (oi
->type
== OSPF_IFTYPE_NBMA
) {
761 struct ospf_neighbor
*nbr
;
763 for (rn
= route_top(oi
->nbrs
); rn
; rn
= route_next(rn
)) {
768 if (nbr
!= oi
->nbr_self
&& nbr
->state
>= NSM_Exchange
)
769 ospf_ls_upd_send_lsa(nbr
, lsa
,
770 OSPF_SEND_PACKET_DIRECT
);
773 /* Optimization: for P2MP interfaces,
774 don't send back out the incoming interface immediately,
775 allow time to rx multicast ack to the rx'ed (multicast)
777 if (retx_flag
!= 1 ||
778 oi
->type
!= OSPF_IFTYPE_POINTOMULTIPOINT
|| inbr
== NULL
||
780 ospf_ls_upd_send_lsa(oi
->nbr_self
, lsa
,
781 OSPF_SEND_PACKET_INDIRECT
);
786 int ospf_flood_through_area(struct ospf_area
*area
, struct ospf_neighbor
*inbr
,
787 struct ospf_lsa
*lsa
)
789 struct listnode
*node
, *nnode
;
790 struct ospf_interface
*oi
;
791 int lsa_ack_flag
= 0;
794 /* All other types are specific to a single area (Area A). The
795 eligible interfaces are all those interfaces attaching to the
796 Area A. If Area A is the backbone, this includes all the virtual
798 for (ALL_LIST_ELEMENTS(area
->oiflist
, node
, nnode
, oi
)) {
799 if (area
->area_id
.s_addr
!= OSPF_AREA_BACKBONE
800 && oi
->type
== OSPF_IFTYPE_VIRTUALLINK
)
803 if ((lsa
->data
->type
== OSPF_OPAQUE_LINK_LSA
)
804 && (lsa
->oi
!= oi
)) {
806 * Link local scoped Opaque-LSA should only be flooded
807 * for the link on which the LSA has received.
809 if (IS_DEBUG_OSPF(lsa
, LSA_FLOODING
))
811 "Type-9 Opaque-LSA: lsa->oi(%p) != oi(%p)",
812 (void *)lsa
->oi
, (void *)oi
);
816 if (ospf_flood_through_interface(oi
, inbr
, lsa
))
820 return (lsa_ack_flag
);
823 int ospf_flood_through_as(struct ospf
*ospf
, struct ospf_neighbor
*inbr
,
824 struct ospf_lsa
*lsa
)
826 struct listnode
*node
;
827 struct ospf_area
*area
;
832 /* The incoming LSA is type 5 or type 7 (AS-EXTERNAL or AS-NSSA )
834 Divert the Type-5 LSA's to all non-NSSA/STUB areas
836 Divert the Type-7 LSA's to all NSSA areas
838 AS-external-LSAs are flooded throughout the entire AS, with the
839 exception of stub areas (see Section 3.6). The eligible
840 interfaces are all the router's interfaces, excluding virtual
841 links and those interfaces attaching to stub areas. */
843 if (CHECK_FLAG(lsa
->flags
, OSPF_LSA_LOCAL_XLT
)) /* Translated from 7 */
844 if (IS_DEBUG_OSPF_NSSA
)
845 zlog_debug("Flood/AS: NSSA TRANSLATED LSA");
847 for (ALL_LIST_ELEMENTS_RO(ospf
->areas
, node
, area
)) {
848 int continue_flag
= 0;
849 struct listnode
*if_node
;
850 struct ospf_interface
*oi
;
852 switch (area
->external_routing
) {
853 /* Don't send AS externals into stub areas. Various types
854 of support for partial stub areas can be implemented
855 here. NSSA's will receive Type-7's that have areas
856 matching the originl LSA. */
857 case OSPF_AREA_NSSA
: /* Sending Type 5 or 7 into NSSA area */
858 /* Type-7, flood NSSA area */
859 if (lsa
->data
->type
== OSPF_AS_NSSA_LSA
860 && area
== lsa
->area
)
861 /* We will send it. */
864 continue_flag
= 1; /* Skip this NSSA area for
868 case OSPF_AREA_TYPE_MAX
:
870 continue_flag
= 1; /* Skip this area. */
873 case OSPF_AREA_DEFAULT
:
875 /* No Type-7 into normal area */
876 if (lsa
->data
->type
== OSPF_AS_NSSA_LSA
)
877 continue_flag
= 1; /* skip Type-7 */
879 continue_flag
= 0; /* Do this area. */
883 /* Do continue for above switch. Saves a big if then mess */
885 continue; /* main for-loop */
887 /* send to every interface in this area */
889 for (ALL_LIST_ELEMENTS_RO(area
->oiflist
, if_node
, oi
)) {
890 /* Skip virtual links */
891 if (oi
->type
!= OSPF_IFTYPE_VIRTUALLINK
)
892 if (ospf_flood_through_interface(oi
, inbr
,
896 } /* main area for-loop */
898 return (lsa_ack_flag
);
901 int ospf_flood_through(struct ospf
*ospf
, struct ospf_neighbor
*inbr
,
902 struct ospf_lsa
*lsa
)
904 int lsa_ack_flag
= 0;
906 /* Type-7 LSA's for NSSA are flooded throughout the AS here, and
907 upon return are updated in the LSDB for Type-7's. Later,
908 re-fresh will re-send them (and also, if ABR, packet code will
909 translate to Type-5's)
911 As usual, Type-5 LSA's (if not DISCARDED because we are STUB or
912 NSSA) are flooded throughout the AS, and are updated in the
915 * At the common sub-sub-function "ospf_flood_through_interface()",
916 * a parameter "inbr" will be used to distinguish the called context
917 * whether the given LSA was received from the neighbor, or the
918 * flooding for the LSA starts from this node (e.g. the LSA was self-
919 * originated, or the LSA is going to be flushed from routing domain).
921 * So, for consistency reasons, this function "ospf_flood_through()"
922 * should also allow the usage that the given "inbr" parameter to be
923 * NULL. If we do so, corresponding AREA parameter should be referred
924 * by "lsa->area", instead of "inbr->oi->area".
926 switch (lsa
->data
->type
) {
927 case OSPF_AS_EXTERNAL_LSA
: /* Type-5 */
928 case OSPF_OPAQUE_AS_LSA
:
929 lsa_ack_flag
= ospf_flood_through_as(ospf
, inbr
, lsa
);
931 /* Type-7 Only received within NSSA, then flooded */
932 case OSPF_AS_NSSA_LSA
:
933 /* Any P-bit was installed with the Type-7. */
935 if (IS_DEBUG_OSPF_NSSA
)
936 zlog_debug("%s: LOCAL NSSA FLOOD of Type-7.", __func__
);
939 lsa_ack_flag
= ospf_flood_through_area(lsa
->area
, inbr
, lsa
);
943 /* always need to send ack when incoming intf is PTP or P2MP */
944 if (inbr
!= NULL
&& (inbr
->oi
->type
== OSPF_IFTYPE_POINTOMULTIPOINT
||
945 inbr
->oi
->type
== OSPF_IFTYPE_POINTOPOINT
))
948 return (lsa_ack_flag
);
952 /* Management functions for neighbor's Link State Request list. */
953 void ospf_ls_request_add(struct ospf_neighbor
*nbr
, struct ospf_lsa
*lsa
)
956 * We cannot make use of the newly introduced callback function
957 * "lsdb->new_lsa_hook" to replace debug output below, just because
958 * it seems no simple and smart way to pass neighbor information to
959 * the common function "ospf_lsdb_add()" -- endo.
961 if (IS_DEBUG_OSPF(lsa
, LSA_FLOODING
))
962 zlog_debug("RqstL(%lu)++, NBR(%pI4(%s)), LSA[%s]",
963 ospf_ls_request_count(nbr
),
965 ospf_get_name(nbr
->oi
->ospf
), dump_lsa_key(lsa
));
967 ospf_lsdb_add(&nbr
->ls_req
, lsa
);
970 unsigned long ospf_ls_request_count(struct ospf_neighbor
*nbr
)
972 return ospf_lsdb_count_all(&nbr
->ls_req
);
975 int ospf_ls_request_isempty(struct ospf_neighbor
*nbr
)
977 return ospf_lsdb_isempty(&nbr
->ls_req
);
980 /* Remove LSA from neighbor's ls-request list. */
981 void ospf_ls_request_delete(struct ospf_neighbor
*nbr
, struct ospf_lsa
*lsa
)
983 if (nbr
->ls_req_last
== lsa
) {
984 ospf_lsa_unlock(&nbr
->ls_req_last
);
985 nbr
->ls_req_last
= NULL
;
988 if (IS_DEBUG_OSPF(lsa
, LSA_FLOODING
)) /* -- endo. */
989 zlog_debug("RqstL(%lu)--, NBR(%pI4(%s)), LSA[%s]",
990 ospf_ls_request_count(nbr
),
992 ospf_get_name(nbr
->oi
->ospf
), dump_lsa_key(lsa
));
994 ospf_lsdb_delete(&nbr
->ls_req
, lsa
);
997 /* Remove all LSA from neighbor's ls-requenst list. */
998 void ospf_ls_request_delete_all(struct ospf_neighbor
*nbr
)
1000 ospf_lsa_unlock(&nbr
->ls_req_last
);
1001 nbr
->ls_req_last
= NULL
;
1002 ospf_lsdb_delete_all(&nbr
->ls_req
);
1005 /* Lookup LSA from neighbor's ls-request list. */
1006 struct ospf_lsa
*ospf_ls_request_lookup(struct ospf_neighbor
*nbr
,
1007 struct ospf_lsa
*lsa
)
1009 return ospf_lsdb_lookup(&nbr
->ls_req
, lsa
);
1012 struct ospf_lsa
*ospf_ls_request_new(struct lsa_header
*lsah
)
1014 struct ospf_lsa
*new;
1016 new = ospf_lsa_new_and_data(OSPF_LSA_HEADER_SIZE
);
1017 memcpy(new->data
, lsah
, OSPF_LSA_HEADER_SIZE
);
1023 /* Management functions for neighbor's ls-retransmit list. */
1024 unsigned long ospf_ls_retransmit_count(struct ospf_neighbor
*nbr
)
1026 return ospf_lsdb_count_all(&nbr
->ls_rxmt
);
1029 unsigned long ospf_ls_retransmit_count_self(struct ospf_neighbor
*nbr
,
1032 return ospf_lsdb_count_self(&nbr
->ls_rxmt
, lsa_type
);
1035 int ospf_ls_retransmit_isempty(struct ospf_neighbor
*nbr
)
1037 return ospf_lsdb_isempty(&nbr
->ls_rxmt
);
1040 /* Add LSA to be retransmitted to neighbor's ls-retransmit list. */
1041 void ospf_ls_retransmit_add(struct ospf_neighbor
*nbr
, struct ospf_lsa
*lsa
)
1043 struct ospf_lsa
*old
;
1045 old
= ospf_ls_retransmit_lookup(nbr
, lsa
);
1047 if (ospf_lsa_more_recent(old
, lsa
) < 0) {
1049 old
->retransmit_counter
--;
1050 if (IS_DEBUG_OSPF(lsa
, LSA_FLOODING
))
1051 zlog_debug("RXmtL(%lu)--, NBR(%pI4(%s)), LSA[%s]",
1052 ospf_ls_retransmit_count(nbr
),
1054 ospf_get_name(nbr
->oi
->ospf
),
1056 ospf_lsdb_delete(&nbr
->ls_rxmt
, old
);
1058 lsa
->retransmit_counter
++;
1060 * We cannot make use of the newly introduced callback function
1061 * "lsdb->new_lsa_hook" to replace debug output below, just
1063 * it seems no simple and smart way to pass neighbor information
1065 * the common function "ospf_lsdb_add()" -- endo.
1067 if (IS_DEBUG_OSPF(lsa
, LSA_FLOODING
))
1068 zlog_debug("RXmtL(%lu)++, NBR(%pI4(%s)), LSA[%s]",
1069 ospf_ls_retransmit_count(nbr
),
1071 ospf_get_name(nbr
->oi
->ospf
),
1073 ospf_lsdb_add(&nbr
->ls_rxmt
, lsa
);
1077 /* Remove LSA from neibghbor's ls-retransmit list. */
1078 void ospf_ls_retransmit_delete(struct ospf_neighbor
*nbr
, struct ospf_lsa
*lsa
)
1080 if (ospf_ls_retransmit_lookup(nbr
, lsa
)) {
1081 lsa
->retransmit_counter
--;
1082 if (IS_DEBUG_OSPF(lsa
, LSA_FLOODING
)) /* -- endo. */
1083 zlog_debug("RXmtL(%lu)--, NBR(%pI4(%s)), LSA[%s]",
1084 ospf_ls_retransmit_count(nbr
),
1086 ospf_get_name(nbr
->oi
->ospf
),
1088 ospf_lsdb_delete(&nbr
->ls_rxmt
, lsa
);
1092 /* Clear neighbor's ls-retransmit list. */
1093 void ospf_ls_retransmit_clear(struct ospf_neighbor
*nbr
)
1095 struct ospf_lsdb
*lsdb
;
1098 lsdb
= &nbr
->ls_rxmt
;
1100 for (i
= OSPF_MIN_LSA
; i
< OSPF_MAX_LSA
; i
++) {
1101 struct route_table
*table
= lsdb
->type
[i
].db
;
1102 struct route_node
*rn
;
1103 struct ospf_lsa
*lsa
;
1105 for (rn
= route_top(table
); rn
; rn
= route_next(rn
))
1106 if ((lsa
= rn
->info
) != NULL
)
1107 ospf_ls_retransmit_delete(nbr
, lsa
);
1110 ospf_lsa_unlock(&nbr
->ls_req_last
);
1111 nbr
->ls_req_last
= NULL
;
1114 /* Lookup LSA from neighbor's ls-retransmit list. */
1115 struct ospf_lsa
*ospf_ls_retransmit_lookup(struct ospf_neighbor
*nbr
,
1116 struct ospf_lsa
*lsa
)
1118 return ospf_lsdb_lookup(&nbr
->ls_rxmt
, lsa
);
1121 static void ospf_ls_retransmit_delete_nbr_if(struct ospf_interface
*oi
,
1122 struct ospf_lsa
*lsa
)
1124 struct route_node
*rn
;
1125 struct ospf_neighbor
*nbr
;
1126 struct ospf_lsa
*lsr
;
1128 if (ospf_if_is_enable(oi
))
1129 for (rn
= route_top(oi
->nbrs
); rn
; rn
= route_next(rn
)) {
1130 /* If LSA find in LS-retransmit list, then remove it. */
1136 lsr
= ospf_ls_retransmit_lookup(nbr
, lsa
);
1138 /* If LSA find in ls-retransmit list, remove it. */
1140 lsr
->data
->ls_seqnum
== lsa
->data
->ls_seqnum
)
1141 ospf_ls_retransmit_delete(nbr
, lsr
);
1145 void ospf_ls_retransmit_delete_nbr_area(struct ospf_area
*area
,
1146 struct ospf_lsa
*lsa
)
1148 struct listnode
*node
, *nnode
;
1149 struct ospf_interface
*oi
;
1151 for (ALL_LIST_ELEMENTS(area
->oiflist
, node
, nnode
, oi
))
1152 ospf_ls_retransmit_delete_nbr_if(oi
, lsa
);
1155 void ospf_ls_retransmit_delete_nbr_as(struct ospf
*ospf
, struct ospf_lsa
*lsa
)
1157 struct listnode
*node
, *nnode
;
1158 struct ospf_interface
*oi
;
1160 for (ALL_LIST_ELEMENTS(ospf
->oiflist
, node
, nnode
, oi
))
1161 ospf_ls_retransmit_delete_nbr_if(oi
, lsa
);
1165 /* Sets ls_age to MaxAge and floods throu the area.
1166 When we implement ASE routing, there will be another function
1167 flushing an LSA from the whole domain. */
1168 void ospf_lsa_flush_area(struct ospf_lsa
*lsa
, struct ospf_area
*area
)
1170 struct ospf
*ospf
= area
->ospf
;
1172 if (ospf_lsa_is_self_originated(ospf
, lsa
)
1173 && ospf
->gr_info
.restart_in_progress
) {
1174 if (IS_DEBUG_OSPF(lsa
, LSA_GENERATE
))
1176 "%s:LSA[Type%d:%pI4]: Graceful Restart in progress -- not flushing self-originated LSA",
1177 ospf_get_name(ospf
), lsa
->data
->type
,
1182 /* Reset the lsa origination time such that it gives
1183 more time for the ACK to be received and avoid
1185 lsa
->data
->ls_age
= htons(OSPF_LSA_MAXAGE
);
1186 if (IS_DEBUG_OSPF_EVENT
)
1187 zlog_debug("%s: MaxAge set to LSA[%s]", __func__
,
1189 monotime(&lsa
->tv_recv
);
1190 lsa
->tv_orig
= lsa
->tv_recv
;
1191 ospf_flood_through_area(area
, NULL
, lsa
);
1192 ospf_lsa_maxage(ospf
, lsa
);
1195 void ospf_lsa_flush_as(struct ospf
*ospf
, struct ospf_lsa
*lsa
)
1197 if (ospf_lsa_is_self_originated(ospf
, lsa
)
1198 && ospf
->gr_info
.restart_in_progress
) {
1199 if (IS_DEBUG_OSPF(lsa
, LSA_GENERATE
))
1201 "%s:LSA[Type%d:%pI4]: Graceful Restart in progress -- not flushing self-originated LSA",
1202 ospf_get_name(ospf
), lsa
->data
->type
,
1207 /* Reset the lsa origination time such that it gives
1208 more time for the ACK to be received and avoid
1210 lsa
->data
->ls_age
= htons(OSPF_LSA_MAXAGE
);
1211 if (IS_DEBUG_OSPF_EVENT
)
1212 zlog_debug("%s: MaxAge set to LSA[%s]", __func__
,
1214 monotime(&lsa
->tv_recv
);
1215 lsa
->tv_orig
= lsa
->tv_recv
;
1216 ospf_flood_through_as(ospf
, NULL
, lsa
);
1217 ospf_lsa_maxage(ospf
, lsa
);
1220 void ospf_lsa_flush(struct ospf
*ospf
, struct ospf_lsa
*lsa
)
1222 lsa
->data
->ls_age
= htons(OSPF_LSA_MAXAGE
);
1224 switch (lsa
->data
->type
) {
1225 case OSPF_ROUTER_LSA
:
1226 case OSPF_NETWORK_LSA
:
1227 case OSPF_SUMMARY_LSA
:
1228 case OSPF_ASBR_SUMMARY_LSA
:
1229 case OSPF_AS_NSSA_LSA
:
1230 case OSPF_OPAQUE_LINK_LSA
:
1231 case OSPF_OPAQUE_AREA_LSA
:
1232 ospf_lsa_flush_area(lsa
, lsa
->area
);
1234 case OSPF_AS_EXTERNAL_LSA
:
1235 case OSPF_OPAQUE_AS_LSA
:
1236 ospf_lsa_flush_as(ospf
, lsa
);
1239 zlog_info("%s: Unknown LSA type %u", __func__
, lsa
->data
->type
);