]> git.proxmox.com Git - mirror_frr.git/blob - ospf6d/ospf6_flood.c
projects / mirror_frr.git / blob
? search:


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