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


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