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_remove_id_from_external_id_table(struct ospf6
*ospf6
,
157 struct prefix prefix_id
;
158 struct route_node
*node
;
160 /* remove binding in external_id_table */
161 prefix_id
.family
= AF_INET
;
162 prefix_id
.prefixlen
= 32;
163 prefix_id
.u
.prefix4
.s_addr
= id
;
164 node
= route_node_lookup(ospf6
->external_id_table
, &prefix_id
);
167 route_unlock_node(node
); /* to free the lookup lock */
168 route_unlock_node(node
); /* to free the original lock */
172 void ospf6_external_lsa_purge(struct ospf6
*ospf6
, struct ospf6_lsa
*lsa
)
174 uint32_t id
= lsa
->header
->id
;
175 struct ospf6_area
*oa
;
176 struct listnode
*lnode
;
178 ospf6_lsa_purge(lsa
);
180 ospf6_remove_id_from_external_id_table(ospf6
, id
);
182 /* Delete the corresponding NSSA LSA */
183 for (ALL_LIST_ELEMENTS_RO(ospf6
->area_list
, lnode
, oa
)) {
184 lsa
= ospf6_lsdb_lookup(htons(OSPF6_LSTYPE_TYPE_7
), id
,
185 ospf6
->router_id
, oa
->lsdb
);
187 if (IS_OSPF6_DEBUG_NSSA
)
188 zlog_debug("withdraw type 7 lsa, LS ID: %u",
191 ospf6_lsa_purge(lsa
);
196 void ospf6_lsa_purge(struct ospf6_lsa
*lsa
)
198 struct ospf6_lsa
*self
;
199 struct ospf6_lsdb
*lsdb_self
;
201 /* remove it from the LSDB for self-originated LSAs */
202 lsdb_self
= ospf6_get_scoped_lsdb_self(lsa
);
203 self
= ospf6_lsdb_lookup(lsa
->header
->type
, lsa
->header
->id
,
204 lsa
->header
->adv_router
, lsdb_self
);
206 THREAD_OFF(self
->expire
);
207 THREAD_OFF(self
->refresh
);
208 ospf6_lsdb_remove(self
, lsdb_self
);
211 ospf6_lsa_premature_aging(lsa
);
214 /* Puring Multi Link-State IDs LSAs:
215 * Same Advertising Router with Multiple Link-State IDs
216 * LSAs, purging require to traverse all Link-State IDs
218 void ospf6_lsa_purge_multi_ls_id(struct ospf6_area
*oa
, struct ospf6_lsa
*lsa
)
221 struct ospf6_lsa
*lsa_next
;
224 type
= lsa
->header
->type
;
226 ospf6_lsa_purge(lsa
);
228 lsa_next
= ospf6_lsdb_lookup(type
, htonl(++ls_id
),
229 oa
->ospf6
->router_id
, oa
->lsdb
);
231 ospf6_lsa_purge(lsa_next
);
232 lsa_next
= ospf6_lsdb_lookup(type
, htonl(++ls_id
),
233 oa
->ospf6
->router_id
, oa
->lsdb
);
237 void ospf6_increment_retrans_count(struct ospf6_lsa
*lsa
)
239 /* The LSA must be the original one (see the description
240 in ospf6_decrement_retrans_count () below) */
241 lsa
->retrans_count
++;
244 void ospf6_decrement_retrans_count(struct ospf6_lsa
*lsa
)
246 struct ospf6_lsdb
*lsdb
;
247 struct ospf6_lsa
*orig
;
249 /* The LSA must be on the retrans-list of a neighbor. It means
250 the "lsa" is a copied one, and we have to decrement the
251 retransmission count of the original one (instead of this "lsa"'s).
252 In order to find the original LSA, first we have to find
253 appropriate LSDB that have the original LSA. */
254 lsdb
= ospf6_get_scoped_lsdb(lsa
);
256 /* Find the original LSA of which the retrans_count should be
258 orig
= ospf6_lsdb_lookup(lsa
->header
->type
, lsa
->header
->id
,
259 lsa
->header
->adv_router
, lsdb
);
261 orig
->retrans_count
--;
262 assert(orig
->retrans_count
>= 0);
266 /* RFC2328 section 13.2 Installing LSAs in the database */
267 void ospf6_install_lsa(struct ospf6_lsa
*lsa
)
270 struct ospf6_lsa
*old
;
271 struct ospf6_area
*area
= NULL
;
273 /* Remove the old instance from all neighbors' Link state
274 retransmission list (RFC2328 13.2 last paragraph) */
275 old
= ospf6_lsdb_lookup(lsa
->header
->type
, lsa
->header
->id
,
276 lsa
->header
->adv_router
, lsa
->lsdb
);
278 if (ntohs(lsa
->header
->type
) == OSPF6_LSTYPE_TYPE_7
) {
279 if (IS_OSPF6_DEBUG_NSSA
)
280 zlog_debug("%s : old LSA %s", __func__
,
282 lsa
->external_lsa_id
= old
->external_lsa_id
;
284 THREAD_OFF(old
->expire
);
285 THREAD_OFF(old
->refresh
);
286 ospf6_flood_clear(old
);
290 if (!OSPF6_LSA_IS_MAXAGE(lsa
)) {
292 thread_add_timer(master
, ospf6_lsa_expire
, lsa
,
293 OSPF_LSA_MAXAGE
+ lsa
->birth
.tv_sec
299 if (OSPF6_LSA_IS_SEQWRAP(lsa
)
300 && !(CHECK_FLAG(lsa
->flag
, OSPF6_LSA_SEQWRAPPED
)
301 && lsa
->header
->seqnum
== htonl(OSPF_MAX_SEQUENCE_NUMBER
))) {
302 if (IS_OSPF6_DEBUG_EXAMIN_TYPE(lsa
->header
->type
))
303 zlog_debug("lsa install wrapping: sequence 0x%x",
304 ntohl(lsa
->header
->seqnum
));
305 SET_FLAG(lsa
->flag
, OSPF6_LSA_SEQWRAPPED
);
306 /* in lieu of premature_aging, since we do not want to recreate
308 * and/or mess with timers etc, we just want to wrap the
310 * and reflood the lsa before continuing.
311 * NOTE: Flood needs to be called right after this function
315 lsa
->header
->seqnum
= htonl(OSPF_MAX_SEQUENCE_NUMBER
);
316 lsa
->header
->age
= htons(OSPF_LSA_MAXAGE
);
317 ospf6_lsa_checksum(lsa
->header
);
320 if (IS_OSPF6_DEBUG_LSA_TYPE(lsa
->header
->type
)
321 || IS_OSPF6_DEBUG_EXAMIN_TYPE(lsa
->header
->type
))
322 zlog_debug("%s Install LSA: %s age %d seqnum %x in LSDB.",
323 __func__
, lsa
->name
, ntohs(lsa
->header
->age
),
324 ntohl(lsa
->header
->seqnum
));
326 /* actually install */
327 lsa
->installed
= now
;
329 /* Topo change handling */
330 if (CHECK_LSA_TOPO_CHG_ELIGIBLE(ntohs(lsa
->header
->type
))
331 && !CHECK_FLAG(lsa
->flag
, OSPF6_LSA_DUPLICATE
)) {
333 /* check if it is new lsa ? or existing lsa got modified ?*/
334 if (!old
|| OSPF6_LSA_IS_CHANGED(old
, lsa
)) {
337 ospf6
= ospf6_get_by_lsdb(lsa
);
341 ospf6_helper_handle_topo_chg(ospf6
, lsa
);
345 ospf6_lsdb_add(lsa
, lsa
->lsdb
);
347 if (ntohs(lsa
->header
->type
) == OSPF6_LSTYPE_TYPE_7
) {
348 area
= OSPF6_AREA(lsa
->lsdb
->data
);
349 ospf6_translated_nssa_refresh(area
, lsa
, NULL
);
350 ospf6_schedule_abr_task(area
->ospf6
);
353 if (ntohs(lsa
->header
->type
) == OSPF6_LSTYPE_ROUTER
) {
354 area
= OSPF6_AREA(lsa
->lsdb
->data
);
356 if (IS_OSPF6_DEBUG_LSA_TYPE(lsa
->header
->type
)
357 || IS_OSPF6_DEBUG_EXAMIN_TYPE(lsa
->header
->type
))
358 zlog_debug("%s: New router LSA %s", __func__
,
360 ospf6_abr_nssa_check_status(area
->ospf6
);
366 /* RFC2740 section 3.5.2. Sending Link State Update packets */
367 /* RFC2328 section 13.3 Next step in the flooding procedure */
368 void ospf6_flood_interface(struct ospf6_neighbor
*from
, struct ospf6_lsa
*lsa
,
369 struct ospf6_interface
*oi
)
371 struct listnode
*node
, *nnode
;
372 struct ospf6_neighbor
*on
;
373 struct ospf6_lsa
*req
, *old
;
374 int retrans_added
= 0;
377 if (IS_OSPF6_DEBUG_FLOODING
378 || IS_OSPF6_DEBUG_FLOOD_TYPE(lsa
->header
->type
)) {
380 zlog_debug("Flooding on %s: %s", oi
->interface
->name
,
384 /* (1) For each neighbor */
385 for (ALL_LIST_ELEMENTS(oi
->neighbor_list
, node
, nnode
, on
)) {
387 zlog_debug("To neighbor %s", on
->name
);
389 /* (a) if neighbor state < Exchange, examin next */
390 if (on
->state
< OSPF6_NEIGHBOR_EXCHANGE
) {
393 "Neighbor state less than ExChange, next neighbor");
397 /* (b) if neighbor not yet Full, check request-list */
398 if (on
->state
!= OSPF6_NEIGHBOR_FULL
) {
400 zlog_debug("Neighbor not yet Full");
402 req
= ospf6_lsdb_lookup(
403 lsa
->header
->type
, lsa
->header
->id
,
404 lsa
->header
->adv_router
, on
->request_list
);
408 "Not on request-list for this neighbor");
411 /* If new LSA less recent, examin next neighbor
413 if (ospf6_lsa_compare(lsa
, req
) > 0) {
416 "Requesting is older, next neighbor");
420 /* If the same instance, delete from
422 examin next neighbor */
423 if (ospf6_lsa_compare(lsa
, req
) == 0) {
426 "Requesting the same, remove it, next neighbor");
427 if (req
== on
->last_ls_req
) {
428 /* sanity check refcount */
429 assert(req
->lock
>= 2);
430 req
= ospf6_lsa_unlock(req
);
431 on
->last_ls_req
= NULL
;
435 req
, on
->request_list
);
436 ospf6_check_nbr_loading(on
);
440 /* If the new LSA is more recent, delete from
442 if (ospf6_lsa_compare(lsa
, req
) < 0) {
445 "Received is newer, remove requesting");
446 if (req
== on
->last_ls_req
) {
447 req
= ospf6_lsa_unlock(req
);
448 on
->last_ls_req
= NULL
;
451 ospf6_lsdb_remove(req
,
453 ospf6_check_nbr_loading(on
);
459 /* (c) If the new LSA was received from this neighbor,
460 examin next neighbor */
464 "Received is from the neighbor, next neighbor");
468 if ((oi
->area
->ospf6
->inst_shutdown
)
469 || CHECK_FLAG(lsa
->flag
, OSPF6_LSA_FLUSH
)) {
472 "%s: Send LSA %s (age %d) update now",
474 ntohs(lsa
->header
->age
));
475 ospf6_lsupdate_send_neighbor_now(on
, lsa
);
478 /* (d) add retrans-list, schedule retransmission */
480 zlog_debug("Add retrans-list of neighbor %s ",
483 /* Do not increment the retrans count if the lsa is
484 * already present in the retrans list.
486 old
= ospf6_lsdb_lookup(
487 lsa
->header
->type
, lsa
->header
->id
,
488 lsa
->header
->adv_router
, on
->retrans_list
);
492 "Increment %s from retrans_list of %s",
493 lsa
->name
, on
->name
);
494 ospf6_increment_retrans_count(lsa
);
495 ospf6_lsdb_add(ospf6_lsa_copy(lsa
),
498 master
, ospf6_lsupdate_send_neighbor
,
499 on
, on
->ospf6_if
->rxmt_interval
,
500 &on
->thread_send_lsupdate
);
506 /* (2) examin next interface if not added to retrans-list */
507 if (retrans_added
== 0) {
510 "No retransmission scheduled, next interface %s",
511 oi
->interface
->name
);
515 /* (3) If the new LSA was received on this interface,
516 and it was from DR or BDR, examin next interface */
517 if (from
&& from
->ospf6_if
== oi
518 && (from
->router_id
== oi
->drouter
519 || from
->router_id
== oi
->bdrouter
)) {
522 "Received is from the I/F's DR or BDR, next interface");
526 /* (4) If the new LSA was received on this interface,
527 and the interface state is BDR, examin next interface */
528 if (from
&& from
->ospf6_if
== oi
) {
529 if (oi
->state
== OSPF6_INTERFACE_BDR
) {
532 "Received is from the I/F, itself BDR, next interface");
535 SET_FLAG(lsa
->flag
, OSPF6_LSA_FLOODBACK
);
538 /* (5) flood the LSA out the interface. */
540 zlog_debug("Schedule flooding for the interface");
541 if ((oi
->type
== OSPF_IFTYPE_BROADCAST
)
542 || (oi
->type
== OSPF_IFTYPE_POINTOPOINT
)) {
543 ospf6_lsdb_add(ospf6_lsa_copy(lsa
), oi
->lsupdate_list
);
544 thread_add_event(master
, ospf6_lsupdate_send_interface
, oi
, 0,
545 &oi
->thread_send_lsupdate
);
547 /* reschedule retransmissions to all neighbors */
548 for (ALL_LIST_ELEMENTS(oi
->neighbor_list
, node
, nnode
, on
)) {
549 THREAD_OFF(on
->thread_send_lsupdate
);
550 on
->thread_send_lsupdate
= NULL
;
551 thread_add_event(master
, ospf6_lsupdate_send_neighbor
,
552 on
, 0, &on
->thread_send_lsupdate
);
557 void ospf6_flood_area(struct ospf6_neighbor
*from
, struct ospf6_lsa
*lsa
,
558 struct ospf6_area
*oa
)
560 struct listnode
*node
, *nnode
;
561 struct ospf6_interface
*oi
;
563 for (ALL_LIST_ELEMENTS(oa
->if_list
, node
, nnode
, oi
)) {
564 if (OSPF6_LSA_SCOPE(lsa
->header
->type
) == OSPF6_SCOPE_LINKLOCAL
565 && oi
!= OSPF6_INTERFACE(lsa
->lsdb
->data
))
568 ospf6_flood_interface(from
, lsa
, oi
);
572 static void ospf6_flood_process(struct ospf6_neighbor
*from
,
573 struct ospf6_lsa
*lsa
, struct ospf6
*process
)
575 struct listnode
*node
, *nnode
;
576 struct ospf6_area
*oa
;
578 for (ALL_LIST_ELEMENTS(process
->area_list
, node
, nnode
, oa
)) {
580 /* If unknown LSA and U-bit clear, treat as link local
583 if (!OSPF6_LSA_IS_KNOWN(lsa
->header
->type
)
584 && !(ntohs(lsa
->header
->type
) & OSPF6_LSTYPE_UBIT_MASK
)
585 && (oa
!= OSPF6_INTERFACE(lsa
->lsdb
->data
)->area
)) {
587 if (IS_OSPF6_DEBUG_FLOODING
)
588 zlog_debug("Unknown LSA, do not flood");
592 if (OSPF6_LSA_SCOPE(lsa
->header
->type
) == OSPF6_SCOPE_AREA
593 && oa
!= OSPF6_AREA(lsa
->lsdb
->data
))
595 if (OSPF6_LSA_SCOPE(lsa
->header
->type
) == OSPF6_SCOPE_LINKLOCAL
596 && oa
!= OSPF6_INTERFACE(lsa
->lsdb
->data
)->area
)
599 if (ntohs(lsa
->header
->type
) == OSPF6_LSTYPE_AS_EXTERNAL
600 && (IS_AREA_STUB(oa
) || IS_AREA_NSSA(oa
)))
603 /* Check for NSSA LSA */
604 if (ntohs(lsa
->header
->type
) == OSPF6_LSTYPE_TYPE_7
605 && !IS_AREA_NSSA(oa
) && !OSPF6_LSA_IS_MAXAGE(lsa
))
608 ospf6_flood_area(from
, lsa
, oa
);
612 void ospf6_flood(struct ospf6_neighbor
*from
, struct ospf6_lsa
*lsa
)
616 ospf6
= ospf6_get_by_lsdb(lsa
);
620 ospf6_flood_process(from
, lsa
, ospf6
);
623 static void ospf6_flood_clear_interface(struct ospf6_lsa
*lsa
,
624 struct ospf6_interface
*oi
)
626 struct listnode
*node
, *nnode
;
627 struct ospf6_neighbor
*on
;
628 struct ospf6_lsa
*rem
;
630 for (ALL_LIST_ELEMENTS(oi
->neighbor_list
, node
, nnode
, on
)) {
631 rem
= ospf6_lsdb_lookup(lsa
->header
->type
, lsa
->header
->id
,
632 lsa
->header
->adv_router
,
634 if (rem
&& !ospf6_lsa_compare(rem
, lsa
)) {
635 if (IS_OSPF6_DEBUG_FLOODING
636 || IS_OSPF6_DEBUG_FLOOD_TYPE(lsa
->header
->type
))
637 zlog_debug("Remove %s from retrans_list of %s",
638 rem
->name
, on
->name
);
639 ospf6_decrement_retrans_count(rem
);
640 ospf6_lsdb_remove(rem
, on
->retrans_list
);
645 void ospf6_flood_clear_area(struct ospf6_lsa
*lsa
, struct ospf6_area
*oa
)
647 struct listnode
*node
, *nnode
;
648 struct ospf6_interface
*oi
;
650 for (ALL_LIST_ELEMENTS(oa
->if_list
, node
, nnode
, oi
)) {
651 if (OSPF6_LSA_SCOPE(lsa
->header
->type
) == OSPF6_SCOPE_LINKLOCAL
652 && oi
!= OSPF6_INTERFACE(lsa
->lsdb
->data
))
655 ospf6_flood_clear_interface(lsa
, oi
);
659 static void ospf6_flood_clear_process(struct ospf6_lsa
*lsa
,
660 struct ospf6
*process
)
662 struct listnode
*node
, *nnode
;
663 struct ospf6_area
*oa
;
665 for (ALL_LIST_ELEMENTS(process
->area_list
, node
, nnode
, oa
)) {
666 if (OSPF6_LSA_SCOPE(lsa
->header
->type
) == OSPF6_SCOPE_AREA
667 && oa
!= OSPF6_AREA(lsa
->lsdb
->data
))
669 if (OSPF6_LSA_SCOPE(lsa
->header
->type
) == OSPF6_SCOPE_LINKLOCAL
670 && oa
!= OSPF6_INTERFACE(lsa
->lsdb
->data
)->area
)
673 if (ntohs(lsa
->header
->type
) == OSPF6_LSTYPE_AS_EXTERNAL
674 && (IS_AREA_STUB(oa
) || (IS_AREA_NSSA(oa
))))
676 /* Check for NSSA LSA */
677 if (ntohs(lsa
->header
->type
) == OSPF6_LSTYPE_TYPE_7
678 && !IS_AREA_NSSA(oa
))
681 ospf6_flood_clear_area(lsa
, oa
);
685 void ospf6_flood_clear(struct ospf6_lsa
*lsa
)
689 ospf6
= ospf6_get_by_lsdb(lsa
);
692 ospf6_flood_clear_process(lsa
, ospf6
);
696 /* RFC2328 13.5 (Table 19): Sending link state acknowledgements. */
697 static void ospf6_acknowledge_lsa_bdrouter(struct ospf6_lsa
*lsa
,
699 struct ospf6_neighbor
*from
)
701 struct ospf6_interface
*oi
;
704 if (IS_OSPF6_DEBUG_FLOODING
705 || IS_OSPF6_DEBUG_FLOOD_TYPE(lsa
->header
->type
))
708 assert(from
&& from
->ospf6_if
);
711 /* LSA is more recent than database copy, but was not flooded
712 back out receiving interface. Delayed acknowledgement sent
713 if advertisement received from Designated Router,
714 otherwide do nothing. */
715 if (ismore_recent
< 0) {
716 if (oi
->drouter
== from
->router_id
) {
719 "Delayed acknowledgement (BDR & MoreRecent & from DR)");
720 /* Delayed acknowledgement */
721 ospf6_lsdb_add(ospf6_lsa_copy(lsa
), oi
->lsack_list
);
722 thread_add_timer(master
, ospf6_lsack_send_interface
, oi
,
723 3, &oi
->thread_send_lsack
);
727 "No acknowledgement (BDR & MoreRecent & ! from DR)");
732 /* LSA is a duplicate, and was treated as an implied acknowledgement.
733 Delayed acknowledgement sent if advertisement received from
734 Designated Router, otherwise do nothing */
735 if (CHECK_FLAG(lsa
->flag
, OSPF6_LSA_DUPLICATE
)
736 && CHECK_FLAG(lsa
->flag
, OSPF6_LSA_IMPLIEDACK
)) {
737 if (oi
->drouter
== from
->router_id
) {
740 "Delayed acknowledgement (BDR & Duplicate & ImpliedAck & from DR)");
741 /* Delayed acknowledgement */
742 ospf6_lsdb_add(ospf6_lsa_copy(lsa
), oi
->lsack_list
);
743 thread_add_timer(master
, ospf6_lsack_send_interface
, oi
,
744 3, &oi
->thread_send_lsack
);
748 "No acknowledgement (BDR & Duplicate & ImpliedAck & ! from DR)");
753 /* LSA is a duplicate, and was not treated as an implied
755 Direct acknowledgement sent */
756 if (CHECK_FLAG(lsa
->flag
, OSPF6_LSA_DUPLICATE
)
757 && !CHECK_FLAG(lsa
->flag
, OSPF6_LSA_IMPLIEDACK
)) {
759 zlog_debug("Direct acknowledgement (BDR & Duplicate)");
760 ospf6_lsdb_add(ospf6_lsa_copy(lsa
), from
->lsack_list
);
761 thread_add_event(master
, ospf6_lsack_send_neighbor
, from
, 0,
762 &from
->thread_send_lsack
);
766 /* LSA's LS age is equal to Maxage, and there is no current instance
767 of the LSA in the link state database, and none of router's
768 neighbors are in states Exchange or Loading */
769 /* Direct acknowledgement sent, but this case is handled in
770 early of ospf6_receive_lsa () */
773 static void ospf6_acknowledge_lsa_allother(struct ospf6_lsa
*lsa
,
775 struct ospf6_neighbor
*from
)
777 struct ospf6_interface
*oi
;
780 if (IS_OSPF6_DEBUG_FLOODING
781 || IS_OSPF6_DEBUG_FLOOD_TYPE(lsa
->header
->type
))
784 assert(from
&& from
->ospf6_if
);
787 /* LSA has been flood back out receiving interface.
788 No acknowledgement sent. */
789 if (CHECK_FLAG(lsa
->flag
, OSPF6_LSA_FLOODBACK
)) {
791 zlog_debug("No acknowledgement (AllOther & FloodBack)");
795 /* LSA is more recent than database copy, but was not flooded
796 back out receiving interface. Delayed acknowledgement sent. */
797 if (ismore_recent
< 0) {
800 "Delayed acknowledgement (AllOther & MoreRecent)");
801 /* Delayed acknowledgement */
802 ospf6_lsdb_add(ospf6_lsa_copy(lsa
), oi
->lsack_list
);
803 thread_add_timer(master
, ospf6_lsack_send_interface
, oi
, 3,
804 &oi
->thread_send_lsack
);
808 /* LSA is a duplicate, and was treated as an implied acknowledgement.
809 No acknowledgement sent. */
810 if (CHECK_FLAG(lsa
->flag
, OSPF6_LSA_DUPLICATE
)
811 && CHECK_FLAG(lsa
->flag
, OSPF6_LSA_IMPLIEDACK
)) {
814 "No acknowledgement (AllOther & Duplicate & ImpliedAck)");
818 /* LSA is a duplicate, and was not treated as an implied
820 Direct acknowledgement sent */
821 if (CHECK_FLAG(lsa
->flag
, OSPF6_LSA_DUPLICATE
)
822 && !CHECK_FLAG(lsa
->flag
, OSPF6_LSA_IMPLIEDACK
)) {
825 "Direct acknowledgement (AllOther & Duplicate)");
826 ospf6_lsdb_add(ospf6_lsa_copy(lsa
), from
->lsack_list
);
827 thread_add_event(master
, ospf6_lsack_send_neighbor
, from
, 0,
828 &from
->thread_send_lsack
);
832 /* LSA's LS age is equal to Maxage, and there is no current instance
833 of the LSA in the link state database, and none of router's
834 neighbors are in states Exchange or Loading */
835 /* Direct acknowledgement sent, but this case is handled in
836 early of ospf6_receive_lsa () */
839 static void ospf6_acknowledge_lsa(struct ospf6_lsa
*lsa
, int ismore_recent
,
840 struct ospf6_neighbor
*from
)
842 struct ospf6_interface
*oi
;
844 assert(from
&& from
->ospf6_if
);
847 if (oi
->state
== OSPF6_INTERFACE_BDR
)
848 ospf6_acknowledge_lsa_bdrouter(lsa
, ismore_recent
, from
);
850 ospf6_acknowledge_lsa_allother(lsa
, ismore_recent
, from
);
853 /* RFC2328 section 13 (4):
854 if MaxAge LSA and if we have no instance, and no neighbor
855 is in states Exchange or Loading
856 returns 1 if match this case, else returns 0 */
857 static int ospf6_is_maxage_lsa_drop(struct ospf6_lsa
*lsa
,
858 struct ospf6_neighbor
*from
)
860 struct ospf6_neighbor
*on
;
861 struct ospf6_interface
*oi
;
862 struct ospf6_area
*oa
;
863 struct ospf6
*process
= NULL
;
864 struct listnode
*i
, *j
, *k
;
867 if (!OSPF6_LSA_IS_MAXAGE(lsa
))
870 if (ospf6_lsdb_lookup(lsa
->header
->type
, lsa
->header
->id
,
871 lsa
->header
->adv_router
, lsa
->lsdb
))
874 process
= from
->ospf6_if
->area
->ospf6
;
876 for (ALL_LIST_ELEMENTS_RO(process
->area_list
, i
, oa
))
877 for (ALL_LIST_ELEMENTS_RO(oa
->if_list
, j
, oi
))
878 for (ALL_LIST_ELEMENTS_RO(oi
->neighbor_list
, k
, on
))
879 if (on
->state
== OSPF6_NEIGHBOR_EXCHANGE
880 || on
->state
== OSPF6_NEIGHBOR_LOADING
)
888 /* RFC2328 section 13 The Flooding Procedure */
889 void ospf6_receive_lsa(struct ospf6_neighbor
*from
,
890 struct ospf6_lsa_header
*lsa_header
)
892 struct ospf6_lsa
*new = NULL
, *old
= NULL
, *rem
= NULL
;
895 unsigned int time_delta_ms
;
900 /* if we receive a LSA with invalid seqnum drop it */
901 if (ntohl(lsa_header
->seqnum
) - 1 == OSPF_MAX_SEQUENCE_NUMBER
) {
902 if (IS_OSPF6_DEBUG_EXAMIN_TYPE(lsa_header
->type
)) {
904 "received lsa [%s Id:%pI4 Adv:%pI4] with invalid seqnum 0x%x, ignore",
905 ospf6_lstype_name(lsa_header
->type
),
906 &lsa_header
->id
, &lsa_header
->adv_router
,
907 ntohl(lsa_header
->seqnum
));
912 /* make lsa structure for received lsa */
913 new = ospf6_lsa_create(lsa_header
);
915 if (IS_OSPF6_DEBUG_FLOODING
916 || IS_OSPF6_DEBUG_FLOOD_TYPE(new->header
->type
)) {
918 zlog_debug("LSA Receive from %s", from
->name
);
919 ospf6_lsa_header_print(new);
922 /* (1) LSA Checksum */
923 if (!ospf6_lsa_checksum_valid(new->header
)) {
925 zlog_debug("Wrong LSA Checksum, discard");
926 ospf6_lsa_delete(new);
930 /* (2) Examine the LSA's LS type.
931 RFC2470 3.5.1. Receiving Link State Update packets */
932 if (IS_AREA_STUB(from
->ospf6_if
->area
)
933 && OSPF6_LSA_SCOPE(new->header
->type
) == OSPF6_SCOPE_AS
) {
936 "AS-External-LSA (or AS-scope LSA) in stub area, discard");
937 ospf6_lsa_delete(new);
941 /* (3) LSA which have reserved scope is discarded
942 RFC2470 3.5.1. Receiving Link State Update packets */
943 /* Flooding scope check. LSAs with unknown scope are discarded here.
944 Set appropriate LSDB for the LSA */
945 switch (OSPF6_LSA_SCOPE(new->header
->type
)) {
946 case OSPF6_SCOPE_LINKLOCAL
:
947 new->lsdb
= from
->ospf6_if
->lsdb
;
949 case OSPF6_SCOPE_AREA
:
950 new->lsdb
= from
->ospf6_if
->area
->lsdb
;
953 new->lsdb
= from
->ospf6_if
->area
->ospf6
->lsdb
;
957 zlog_debug("LSA has reserved scope, discard");
958 ospf6_lsa_delete(new);
962 /* (4) if MaxAge LSA and if we have no instance, and no neighbor
963 is in states Exchange or Loading */
964 if (ospf6_is_maxage_lsa_drop(new, from
)) {
968 "Drop MaxAge LSA with direct acknowledgement.");
970 /* a) Acknowledge back to neighbor (Direct acknowledgement,
972 ospf6_lsdb_add(ospf6_lsa_copy(new), from
->lsack_list
);
973 thread_add_event(master
, ospf6_lsack_send_neighbor
, from
, 0,
974 &from
->thread_send_lsack
);
977 ospf6_lsa_delete(new);
982 /* lookup the same database copy in lsdb */
983 old
= ospf6_lsdb_lookup(new->header
->type
, new->header
->id
,
984 new->header
->adv_router
, new->lsdb
);
986 ismore_recent
= ospf6_lsa_compare(new, old
);
987 if (ntohl(new->header
->seqnum
) == ntohl(old
->header
->seqnum
)) {
989 zlog_debug("Received is duplicated LSA");
990 SET_FLAG(new->flag
, OSPF6_LSA_DUPLICATE
);
994 /* if no database copy or received is more recent */
995 if (old
== NULL
|| ismore_recent
< 0) {
996 bool self_originated
;
998 /* in case we have no database copy */
1001 /* (a) MinLSArrival check */
1003 struct timeval now
, res
;
1005 timersub(&now
, &old
->installed
, &res
);
1007 (res
.tv_sec
* 1000) + (int)(res
.tv_usec
/ 1000);
1009 < from
->ospf6_if
->area
->ospf6
->lsa_minarrival
) {
1012 "LSA can't be updated within MinLSArrival, %dms < %dms, discard",
1014 from
->ospf6_if
->area
->ospf6
1016 ospf6_lsa_delete(new);
1017 return; /* examin next lsa */
1021 monotime(&new->received
);
1025 "Install, Flood, Possibly acknowledge the received LSA");
1027 /* Remove older copies of this LSA from retx lists */
1029 ospf6_flood_clear(old
);
1031 /* (b) immediately flood and (c) remove from all retrans-list */
1032 /* Prevent self-originated LSA to be flooded. this is to make
1033 reoriginated instance of the LSA not to be rejected by other
1035 due to MinLSArrival. */
1036 self_originated
= (new->header
->adv_router
1037 == from
->ospf6_if
->area
->ospf6
->router_id
);
1038 if (!self_originated
)
1039 ospf6_flood(from
, new);
1041 /* Received non-self-originated Grace LSA. */
1042 if (IS_GRACE_LSA(new) && !self_originated
) {
1043 struct ospf6
*ospf6
;
1045 ospf6
= ospf6_get_by_lsdb(new);
1049 if (OSPF6_LSA_IS_MAXAGE(new)) {
1051 if (IS_DEBUG_OSPF6_GR
)
1053 "%s, Received a maxage GraceLSA from router %pI4",
1055 &new->header
->adv_router
);
1057 ospf6_process_maxage_grace_lsa(
1060 if (IS_DEBUG_OSPF6_GR
)
1062 "%s, GraceLSA doesn't exist in lsdb, so discarding GraceLSA",
1068 if (IS_DEBUG_OSPF6_GR
)
1070 "%s, Received a GraceLSA from router %pI4",
1072 &new->header
->adv_router
);
1074 if (ospf6_process_grace_lsa(ospf6
, new, from
)
1075 == OSPF6_GR_NOT_HELPER
) {
1076 if (IS_DEBUG_OSPF6_GR
)
1078 "%s, Not moving to HELPER role, So dicarding GraceLSA",
1085 /* (d), installing lsdb, which may cause routing
1086 table calculation (replacing database copy) */
1087 ospf6_install_lsa(new);
1089 if (OSPF6_LSA_IS_MAXAGE(new))
1090 ospf6_maxage_remove(from
->ospf6_if
->area
->ospf6
);
1092 /* (e) possibly acknowledge */
1093 ospf6_acknowledge_lsa(new, ismore_recent
, from
);
1095 /* (f) Self Originated LSA, section 13.4 */
1096 if (self_originated
) {
1097 if (from
->ospf6_if
->area
->ospf6
->gr_info
1098 .restart_in_progress
) {
1099 if (IS_DEBUG_OSPF6_GR
)
1101 "Graceful Restart in progress -- not flushing self-originated LSA: %s",
1106 /* Self-originated LSA (newer than ours) is received
1108 another router. We have to make a new instance of the
1110 or have to flush this LSA. */
1113 "Newer instance of the self-originated LSA");
1114 zlog_debug("Schedule reorigination");
1116 new->refresh
= NULL
;
1117 thread_add_event(master
, ospf6_lsa_refresh
, new, 0,
1121 struct ospf6
*ospf6
= from
->ospf6_if
->area
->ospf6
;
1122 struct ospf6_area
*area
= from
->ospf6_if
->area
;
1123 if (ospf6
->gr_info
.restart_in_progress
)
1124 ospf6_gr_check_lsdb_consistency(ospf6
, area
);
1129 /* (6) if there is instance on sending neighbor's request list */
1130 if (ospf6_lsdb_lookup(new->header
->type
, new->header
->id
,
1131 new->header
->adv_router
, from
->request_list
)) {
1132 /* if no database copy, should go above state (5) */
1136 "Received is not newer, on the neighbor %s request-list",
1139 "BadLSReq, discard the received LSA lsa %s send badLSReq",
1143 thread_add_event(master
, bad_lsreq
, from
, 0, NULL
);
1145 ospf6_lsa_delete(new);
1149 /* (7) if neither one is more recent */
1150 if (ismore_recent
== 0) {
1153 "The same instance as database copy (neither recent)");
1155 /* (a) if on retrans-list, Treat this LSA as an Ack: Implied Ack
1157 rem
= ospf6_lsdb_lookup(new->header
->type
, new->header
->id
,
1158 new->header
->adv_router
,
1159 from
->retrans_list
);
1163 "It is on the neighbor's retrans-list.");
1165 "Treat as an Implied acknowledgement");
1167 SET_FLAG(new->flag
, OSPF6_LSA_IMPLIEDACK
);
1168 ospf6_decrement_retrans_count(rem
);
1169 ospf6_lsdb_remove(rem
, from
->retrans_list
);
1173 zlog_debug("Possibly acknowledge and then discard");
1175 /* (b) possibly acknowledge */
1176 ospf6_acknowledge_lsa(new, ismore_recent
, from
);
1178 ospf6_lsa_delete(new);
1182 /* (8) previous database copy is more recent */
1186 /* If database copy is in 'Seqnumber Wrapping',
1187 simply discard the received LSA */
1188 if (OSPF6_LSA_IS_MAXAGE(old
)
1189 && old
->header
->seqnum
== htonl(OSPF_MAX_SEQUENCE_NUMBER
)) {
1191 zlog_debug("The LSA is in Seqnumber Wrapping");
1192 zlog_debug("MaxAge & MaxSeqNum, discard");
1194 ospf6_lsa_delete(new);
1198 /* Otherwise, Send database copy of this LSA to this neighbor */
1201 zlog_debug("Database copy is more recent.");
1203 "Send back directly and then discard");
1206 /* Neighbor router sent recent age for LSA,
1207 * Router could be restarted while current copy is
1208 * MAXAGEd and not removed.*/
1209 if (OSPF6_LSA_IS_MAXAGE(old
)
1210 && !OSPF6_LSA_IS_MAXAGE(new)) {
1211 if (new->header
->adv_router
1212 != from
->ospf6_if
->area
->ospf6
->router_id
) {
1215 "%s: Current copy of LSA %s is MAXAGE, but new has recent age, flooding/installing.",
1216 __PRETTY_FUNCTION__
, old
->name
);
1217 ospf6_lsa_purge(old
);
1218 ospf6_flood(from
, new);
1219 ospf6_install_lsa(new);
1222 /* For self-originated LSA, only trust
1223 * ourselves. Fall through and send
1224 * LS Update with our current copy.
1228 "%s: Current copy of self-originated LSA %s is MAXAGE, but new has recent age, re-sending current one.",
1229 __PRETTY_FUNCTION__
, old
->name
);
1232 /* XXX, MinLSArrival check !? RFC 2328 13 (8) */
1234 ospf6_lsdb_add(ospf6_lsa_copy(old
),
1235 from
->lsupdate_list
);
1236 thread_add_event(master
, ospf6_lsupdate_send_neighbor
,
1237 from
, 0, &from
->thread_send_lsupdate
);
1239 ospf6_lsa_delete(new);
1246 DEFUN (debug_ospf6_flooding
,
1247 debug_ospf6_flooding_cmd
,
1248 "debug ospf6 flooding",
1251 "Debug OSPFv3 flooding function\n"
1254 OSPF6_DEBUG_FLOODING_ON();
1258 DEFUN (no_debug_ospf6_flooding
,
1259 no_debug_ospf6_flooding_cmd
,
1260 "no debug ospf6 flooding",
1264 "Debug OSPFv3 flooding function\n"
1267 OSPF6_DEBUG_FLOODING_OFF();
1271 int config_write_ospf6_debug_flood(struct vty
*vty
)
1273 if (IS_OSPF6_DEBUG_FLOODING
)
1274 vty_out(vty
, "debug ospf6 flooding\n");
1278 void install_element_ospf6_debug_flood(void)
1280 install_element(ENABLE_NODE
, &debug_ospf6_flooding_cmd
);
1281 install_element(ENABLE_NODE
, &no_debug_ospf6_flooding_cmd
);
1282 install_element(CONFIG_NODE
, &debug_ospf6_flooding_cmd
);
1283 install_element(CONFIG_NODE
, &no_debug_ospf6_flooding_cmd
);