blob: 0f485fe30eb7f2f7d4f29d89af038d997519efa4 [file] [log] [blame]
paul718e3742002-12-13 20:15:29 +00001/*
2 * OSPF Flooding -- RFC2328 Section 13.
3 * Copyright (C) 1999, 2000 Toshiaki Takada
4 *
5 * This file is part of GNU Zebra.
6 *
7 * GNU Zebra is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published
9 * by the Free Software Foundation; either version 2, or (at your
10 * option) any later version.
11 *
12 * GNU Zebra is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with GNU Zebra; see the file COPYING. If not, write to the
19 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
20 * Boston, MA 02111-1307, USA.
21 */
22
23#include <zebra.h>
24
25#include "linklist.h"
26#include "prefix.h"
27#include "if.h"
28#include "command.h"
29#include "table.h"
30#include "thread.h"
31#include "memory.h"
32#include "log.h"
33#include "zclient.h"
34
35#include "ospfd/ospfd.h"
36#include "ospfd/ospf_interface.h"
37#include "ospfd/ospf_ism.h"
38#include "ospfd/ospf_asbr.h"
39#include "ospfd/ospf_lsa.h"
40#include "ospfd/ospf_lsdb.h"
41#include "ospfd/ospf_neighbor.h"
42#include "ospfd/ospf_nsm.h"
43#include "ospfd/ospf_spf.h"
44#include "ospfd/ospf_flood.h"
45#include "ospfd/ospf_packet.h"
46#include "ospfd/ospf_abr.h"
47#include "ospfd/ospf_route.h"
48#include "ospfd/ospf_zebra.h"
49#include "ospfd/ospf_dump.h"
50
51extern struct zclient *zclient;
52
53/* Do the LSA acking specified in table 19, Section 13.5, row 2
54 * This get called from ospf_flood_out_interface. Declared inline
55 * for speed. */
56static void
57ospf_flood_delayed_lsa_ack (struct ospf_neighbor *inbr, struct ospf_lsa *lsa)
58{
59 /* LSA is more recent than database copy, but was not
60 flooded back out receiving interface. Delayed
61 acknowledgment sent. If interface is in Backup state
62 delayed acknowledgment sent only if advertisement
63 received from Designated Router, otherwise do nothing See
64 RFC 2328 Section 13.5 */
65
66 /* Whether LSA is more recent or not, and whether this is in
67 response to the LSA being sent out recieving interface has been
68 worked out previously */
69
70 /* Deal with router as BDR */
71 if (inbr->oi->state == ISM_Backup && ! NBR_IS_DR (inbr))
72 return;
73
74 /* Schedule a delayed LSA Ack to be sent */
Paul Jakma1fe6ed32006-07-26 09:37:26 +000075 listnode_add (inbr->oi->ls_ack, ospf_lsa_lock (lsa)); /* delayed LSA Ack */
paul718e3742002-12-13 20:15:29 +000076}
77
78/* Check LSA is related to external info. */
79struct external_info *
80ospf_external_info_check (struct ospf_lsa *lsa)
81{
82 struct as_external_lsa *al;
83 struct prefix_ipv4 p;
84 struct route_node *rn;
85 int type;
86
87 al = (struct as_external_lsa *) lsa->data;
88
89 p.family = AF_INET;
90 p.prefix = lsa->data->id;
91 p.prefixlen = ip_masklen (al->mask);
92
93 for (type = 0; type <= ZEBRA_ROUTE_MAX; type++)
94 {
95 int redist_type = is_prefix_default (&p) ? DEFAULT_ROUTE : type;
96 if (ospf_is_type_redistributed (redist_type))
97 if (EXTERNAL_INFO (type))
98 {
99 rn = route_node_lookup (EXTERNAL_INFO (type),
100 (struct prefix *) &p);
101 if (rn)
102 {
103 route_unlock_node (rn);
104 if (rn->info != NULL)
105 return (struct external_info *) rn->info;
106 }
107 }
108 }
109
110 return NULL;
111}
112
paul4dadc292005-05-06 21:37:42 +0000113static void
paul68980082003-03-25 05:07:42 +0000114ospf_process_self_originated_lsa (struct ospf *ospf,
115 struct ospf_lsa *new, struct ospf_area *area)
paul718e3742002-12-13 20:15:29 +0000116{
117 struct ospf_interface *oi;
118 struct external_info *ei;
hasso52dc7ee2004-09-23 19:18:23 +0000119 struct listnode *node;
paul718e3742002-12-13 20:15:29 +0000120
121 if (IS_DEBUG_OSPF_EVENT)
ajs60925302004-12-08 17:45:02 +0000122 zlog_debug ("LSA[Type%d:%s]: Process self-originated LSA seq 0x%x",
paul7ddf1d62003-10-13 09:06:46 +0000123 new->data->type, inet_ntoa (new->data->id),
paul0c2be262004-05-31 14:16:54 +0000124 ntohl(new->data->ls_seqnum));
paul718e3742002-12-13 20:15:29 +0000125
126 /* If we're here, we installed a self-originated LSA that we received
127 from a neighbor, i.e. it's more recent. We must see whether we want
128 to originate it.
129 If yes, we should use this LSA's sequence number and reoriginate
130 a new instance.
131 if not --- we must flush this LSA from the domain. */
132 switch (new->data->type)
133 {
134 case OSPF_ROUTER_LSA:
135 /* Originate a new instance and schedule flooding */
136 /* It shouldn't be necessary, but anyway */
Paul Jakma1fe6ed32006-07-26 09:37:26 +0000137 ospf_lsa_unlock (&area->router_lsa_self);
paul718e3742002-12-13 20:15:29 +0000138 area->router_lsa_self = ospf_lsa_lock (new);
139
140 ospf_router_lsa_timer_add (area);
141 return;
142 case OSPF_NETWORK_LSA:
143#ifdef HAVE_OPAQUE_LSA
144 case OSPF_OPAQUE_LINK_LSA:
145#endif /* HAVE_OPAQUE_LSA */
146 /* We must find the interface the LSA could belong to.
147 If the interface is no more a broadcast type or we are no more
148 the DR, we flush the LSA otherwise -- create the new instance and
149 schedule flooding. */
150
151 /* Look through all interfaces, not just area, since interface
152 could be moved from one area to another. */
paul1eb8ef22005-04-07 07:30:20 +0000153 for (ALL_LIST_ELEMENTS_RO (ospf->oiflist, node, oi))
paul718e3742002-12-13 20:15:29 +0000154 /* These are sanity check. */
paul1eb8ef22005-04-07 07:30:20 +0000155 if (IPV4_ADDR_SAME (&oi->address->u.prefix4, &new->data->id))
156 {
157 if (oi->area != area ||
158 oi->type != OSPF_IFTYPE_BROADCAST ||
159 !IPV4_ADDR_SAME (&oi->address->u.prefix4, &DR (oi)))
160 {
161 ospf_schedule_lsa_flush_area (area, new);
162 return;
163 }
164
paul718e3742002-12-13 20:15:29 +0000165#ifdef HAVE_OPAQUE_LSA
paul1eb8ef22005-04-07 07:30:20 +0000166 if (new->data->type == OSPF_OPAQUE_LINK_LSA)
167 {
168 ospf_opaque_lsa_refresh (new);
169 return;
170 }
paul718e3742002-12-13 20:15:29 +0000171#endif /* HAVE_OPAQUE_LSA */
172
Paul Jakma1fe6ed32006-07-26 09:37:26 +0000173 ospf_lsa_unlock (&oi->network_lsa_self);
paul1eb8ef22005-04-07 07:30:20 +0000174 oi->network_lsa_self = ospf_lsa_lock (new);
175
176 /* Schedule network-LSA origination. */
177 ospf_network_lsa_timer_add (oi);
178 return;
179 }
paul718e3742002-12-13 20:15:29 +0000180 break;
181 case OSPF_SUMMARY_LSA:
182 case OSPF_ASBR_SUMMARY_LSA:
paul68980082003-03-25 05:07:42 +0000183 ospf_schedule_abr_task (ospf);
paul718e3742002-12-13 20:15:29 +0000184 break;
185 case OSPF_AS_EXTERNAL_LSA :
paul718e3742002-12-13 20:15:29 +0000186 case OSPF_AS_NSSA_LSA:
pauld4a53d52003-07-12 21:30:57 +0000187 if ( (new->data->type == OSPF_AS_EXTERNAL_LSA)
188 && CHECK_FLAG (new->flags, OSPF_LSA_LOCAL_XLT))
189 {
190 ospf_translated_nssa_refresh (ospf, NULL, new);
191 return;
192 }
paul718e3742002-12-13 20:15:29 +0000193 ei = ospf_external_info_check (new);
194 if (ei)
pauld4a53d52003-07-12 21:30:57 +0000195 ospf_external_lsa_refresh (ospf, new, ei, LSA_REFRESH_FORCE);
paul718e3742002-12-13 20:15:29 +0000196 else
pauld4a53d52003-07-12 21:30:57 +0000197 ospf_lsa_flush_as (ospf, new);
paul718e3742002-12-13 20:15:29 +0000198 break;
199#ifdef HAVE_OPAQUE_LSA
200 case OSPF_OPAQUE_AREA_LSA:
201 ospf_opaque_lsa_refresh (new);
202 break;
203 case OSPF_OPAQUE_AS_LSA:
204 ospf_opaque_lsa_refresh (new); /* Reconsideration may needed. *//* XXX */
205 break;
206#endif /* HAVE_OPAQUE_LSA */
207 default:
208 break;
209 }
210}
211
212/* OSPF LSA flooding -- RFC2328 Section 13.(5). */
213
214/* Now Updated for NSSA operation, as follows:
215
216
217 Type-5's have no change. Blocked to STUB or NSSA.
218
219 Type-7's can be received, and if a DR
220 they will also flood the local NSSA Area as Type-7's
221
222 If a Self-Originated LSA (now an ASBR),
223 The LSDB will be updated as Type-5's, (for continual re-fresh)
224
225 If an NSSA-IR it is installed/flooded as Type-7, P-bit on.
226 if an NSSA-ABR it is installed/flooded as Type-7, P-bit off.
227
228 Later, during the ABR TASK, if the ABR is the Elected NSSA
229 translator, then All Type-7s (with P-bit ON) are Translated to
230 Type-5's and flooded to all non-NSSA/STUB areas.
231
232 During ASE Calculations,
233 non-ABRs calculate external routes from Type-7's
234 ABRs calculate external routes from Type-5's and non-self Type-7s
235*/
236int
paul68980082003-03-25 05:07:42 +0000237ospf_flood (struct ospf *ospf, struct ospf_neighbor *nbr,
238 struct ospf_lsa *current, struct ospf_lsa *new)
paul718e3742002-12-13 20:15:29 +0000239{
240 struct ospf_interface *oi;
paul718e3742002-12-13 20:15:29 +0000241 int lsa_ack_flag;
242
243 /* Type-7 LSA's will be flooded throughout their native NSSA area,
244 but will also be flooded as Type-5's into ABR capable links. */
245
246 if (IS_DEBUG_OSPF_EVENT)
ajs60925302004-12-08 17:45:02 +0000247 zlog_debug ("LSA[Flooding]: start, NBR %s (%s), cur(%p), New-LSA[%s]",
paul718e3742002-12-13 20:15:29 +0000248 inet_ntoa (nbr->router_id),
249 LOOKUP (ospf_nsm_state_msg, nbr->state),
250 current,
251 dump_lsa_key (new));
252
253 lsa_ack_flag = 0;
254 oi = nbr->oi;
255
paul718e3742002-12-13 20:15:29 +0000256 /* If there is already a database copy, and if the
257 database copy was received via flooding and installed less
258 than MinLSArrival seconds ago, discard the new LSA
259 (without acknowledging it). */
260 if (current != NULL) /* -- endo. */
261 {
262 if (IS_LSA_SELF (current)
263 && (ntohs (current->data->ls_age) == 0
264 && ntohl (current->data->ls_seqnum) == OSPF_INITIAL_SEQUENCE_NUMBER))
265 {
266 if (IS_DEBUG_OSPF_EVENT)
ajs60925302004-12-08 17:45:02 +0000267 zlog_debug ("LSA[Flooding]: Got a self-originated LSA, "
paul718e3742002-12-13 20:15:29 +0000268 "while local one is initial instance.");
269 ; /* Accept this LSA for quick LSDB resynchronization. */
270 }
Paul Jakma2518efd2006-08-27 06:49:29 +0000271 else if (tv_cmp (tv_sub (recent_relative_time (), current->tv_recv),
paul718e3742002-12-13 20:15:29 +0000272 int2tv (OSPF_MIN_LS_ARRIVAL)) < 0)
273 {
274 if (IS_DEBUG_OSPF_EVENT)
ajs60925302004-12-08 17:45:02 +0000275 zlog_debug ("LSA[Flooding]: LSA is received recently.");
paul718e3742002-12-13 20:15:29 +0000276 return -1;
277 }
278 }
279
280 /* Flood the new LSA out some subset of the router's interfaces.
281 In some cases (e.g., the state of the receiving interface is
282 DR and the LSA was received from a router other than the
283 Backup DR) the LSA will be flooded back out the receiving
284 interface. */
paul68980082003-03-25 05:07:42 +0000285 lsa_ack_flag = ospf_flood_through (ospf, nbr, new);
paul718e3742002-12-13 20:15:29 +0000286
287#ifdef HAVE_OPAQUE_LSA
288 /* Remove the current database copy from all neighbors' Link state
289 retransmission lists. AS_EXTERNAL and AS_EXTERNAL_OPAQUE does
290 ^^^^^^^^^^^^^^^^^^^^^^^
291 not have area ID.
292 All other (even NSSA's) do have area ID. */
293#else /* HAVE_OPAQUE_LSA */
294 /* Remove the current database copy from all neighbors' Link state
295 retransmission lists. Only AS_EXTERNAL does not have area ID.
296 All other (even NSSA's) do have area ID. */
297#endif /* HAVE_OPAQUE_LSA */
298 if (current)
299 {
300 switch (current->data->type)
301 {
302 case OSPF_AS_EXTERNAL_LSA:
303#ifdef HAVE_OPAQUE_LSA
304 case OSPF_OPAQUE_AS_LSA:
305#endif /* HAVE_OPAQUE_LSA */
paul68980082003-03-25 05:07:42 +0000306 ospf_ls_retransmit_delete_nbr_as (ospf, current);
paul718e3742002-12-13 20:15:29 +0000307 break;
308 default:
paul68980082003-03-25 05:07:42 +0000309 ospf_ls_retransmit_delete_nbr_area (nbr->oi->area, current);
paul718e3742002-12-13 20:15:29 +0000310 break;
311 }
312 }
313
314 /* Do some internal house keeping that is needed here */
315 SET_FLAG (new->flags, OSPF_LSA_RECEIVED);
paul68980082003-03-25 05:07:42 +0000316 ospf_lsa_is_self_originated (ospf, new); /* Let it set the flag */
paul718e3742002-12-13 20:15:29 +0000317
318 /* Install the new LSA in the link state database
319 (replacing the current database copy). This may cause the
320 routing table calculation to be scheduled. In addition,
321 timestamp the new LSA with the current time. The flooding
322 procedure cannot overwrite the newly installed LSA until
323 MinLSArrival seconds have elapsed. */
324
paul68980082003-03-25 05:07:42 +0000325 new = ospf_lsa_install (ospf, nbr->oi, new);
paul718e3742002-12-13 20:15:29 +0000326
327 /* Acknowledge the receipt of the LSA by sending a Link State
328 Acknowledgment packet back out the receiving interface. */
329 if (lsa_ack_flag)
330 ospf_flood_delayed_lsa_ack (nbr, new);
331
332 /* If this new LSA indicates that it was originated by the
333 receiving router itself, the router must take special action,
334 either updating the LSA or in some cases flushing it from
335 the routing domain. */
paul68980082003-03-25 05:07:42 +0000336 if (ospf_lsa_is_self_originated (ospf, new))
337 ospf_process_self_originated_lsa (ospf, new, oi->area);
paul718e3742002-12-13 20:15:29 +0000338 else
339 /* Update statistics value for OSPF-MIB. */
paul68980082003-03-25 05:07:42 +0000340 ospf->rx_lsa_count++;
paul718e3742002-12-13 20:15:29 +0000341
342 return 0;
343}
344
345/* OSPF LSA flooding -- RFC2328 Section 13.3. */
paul4dadc292005-05-06 21:37:42 +0000346static int
paul718e3742002-12-13 20:15:29 +0000347ospf_flood_through_interface (struct ospf_interface *oi,
348 struct ospf_neighbor *inbr,
349 struct ospf_lsa *lsa)
350{
351 struct ospf_neighbor *onbr;
352 struct route_node *rn;
353 int retx_flag;
354
355 if (IS_DEBUG_OSPF_EVENT)
ajs60925302004-12-08 17:45:02 +0000356 zlog_debug ("ospf_flood_through_interface(): "
paul718e3742002-12-13 20:15:29 +0000357 "considering int %s, INBR(%s), LSA[%s]",
358 IF_NAME (oi), inbr ? inet_ntoa (inbr->router_id) : "NULL",
359 dump_lsa_key (lsa));
360
361 if (!ospf_if_is_enable (oi))
362 return 0;
363
364 /* Remember if new LSA is aded to a retransmit list. */
365 retx_flag = 0;
366
367 /* Each of the neighbors attached to this interface are examined,
368 to determine whether they must receive the new LSA. The following
369 steps are executed for each neighbor: */
370 for (rn = route_top (oi->nbrs); rn; rn = route_next (rn))
371 {
372 struct ospf_lsa *ls_req;
373
374 if (rn->info == NULL)
375 continue;
376
377 onbr = rn->info;
378 if (IS_DEBUG_OSPF_EVENT)
ajs60925302004-12-08 17:45:02 +0000379 zlog_debug ("ospf_flood_through_interface(): considering nbr %s (%s)",
paul718e3742002-12-13 20:15:29 +0000380 inet_ntoa (onbr->router_id),
381 LOOKUP (ospf_nsm_state_msg, onbr->state));
382
383 /* If the neighbor is in a lesser state than Exchange, it
384 does not participate in flooding, and the next neighbor
385 should be examined. */
386 if (onbr->state < NSM_Exchange)
387 continue;
388
389 /* If the adjacency is not yet full (neighbor state is
390 Exchange or Loading), examine the Link state request
391 list associated with this adjacency. If there is an
392 instance of the new LSA on the list, it indicates that
393 the neighboring router has an instance of the LSA
394 already. Compare the new LSA to the neighbor's copy: */
395 if (onbr->state < NSM_Full)
396 {
397 if (IS_DEBUG_OSPF_EVENT)
ajs60925302004-12-08 17:45:02 +0000398 zlog_debug ("ospf_flood_through_interface(): nbr adj is not Full");
paul718e3742002-12-13 20:15:29 +0000399 ls_req = ospf_ls_request_lookup (onbr, lsa);
400 if (ls_req != NULL)
401 {
402 int ret;
403
404 ret = ospf_lsa_more_recent (ls_req, lsa);
405 /* The new LSA is less recent. */
406 if (ret > 0)
407 continue;
408 /* The two copies are the same instance, then delete
409 the LSA from the Link state request list. */
410 else if (ret == 0)
411 {
412 ospf_ls_request_delete (onbr, ls_req);
413 ospf_check_nbr_loading (onbr);
414 continue;
415 }
416 /* The new LSA is more recent. Delete the LSA
417 from the Link state request list. */
418 else
419 {
420 ospf_ls_request_delete (onbr, ls_req);
421 ospf_check_nbr_loading (onbr);
422 }
423 }
424 }
425
426#ifdef HAVE_OPAQUE_LSA
427 if (IS_OPAQUE_LSA (lsa->data->type))
428 {
429 if (! CHECK_FLAG (onbr->options, OSPF_OPTION_O))
430 {
431 if (IS_DEBUG_OSPF (lsa, LSA_FLOODING))
ajs60925302004-12-08 17:45:02 +0000432 zlog_debug ("Skip this neighbor: Not Opaque-capable.");
paul718e3742002-12-13 20:15:29 +0000433 continue;
434 }
435
paul29226d42003-12-06 17:10:11 +0000436 if (IS_OPAQUE_LSA_ORIGINATION_BLOCKED (oi->ospf->opaque)
paul718e3742002-12-13 20:15:29 +0000437 && IS_LSA_SELF (lsa)
438 && onbr->state == NSM_Full)
439 {
440 /* Small attempt to reduce unnecessary retransmission. */
441 if (IS_DEBUG_OSPF (lsa, LSA_FLOODING))
ajs60925302004-12-08 17:45:02 +0000442 zlog_debug ("Skip this neighbor: Initial flushing done.");
paul718e3742002-12-13 20:15:29 +0000443 continue;
444 }
445 }
446#endif /* HAVE_OPAQUE_LSA */
447
448 /* If the new LSA was received from this neighbor,
449 examine the next neighbor. */
450#ifdef ORIGINAL_CODING
451 if (inbr)
452 if (IPV4_ADDR_SAME (&inbr->router_id, &onbr->router_id))
453 continue;
454#else /* ORIGINAL_CODING */
455 if (inbr)
456 {
457 /*
458 * Triggered by LSUpd message parser "ospf_ls_upd ()".
459 * E.g., all LSAs handling here is received via network.
460 */
461 if (IPV4_ADDR_SAME (&inbr->router_id, &onbr->router_id))
462 {
463 if (IS_DEBUG_OSPF (lsa, LSA_FLOODING))
ajs60925302004-12-08 17:45:02 +0000464 zlog_debug ("Skip this neighbor: inbr == onbr");
paul718e3742002-12-13 20:15:29 +0000465 continue;
466 }
467 }
468 else
469 {
470 /*
471 * Triggered by MaxAge remover, so far.
472 * NULL "inbr" means flooding starts from this node.
473 */
474 if (IPV4_ADDR_SAME (&lsa->data->adv_router, &onbr->router_id))
475 {
476 if (IS_DEBUG_OSPF (lsa, LSA_FLOODING))
ajs60925302004-12-08 17:45:02 +0000477 zlog_debug ("Skip this neighbor: lsah->adv_router == onbr");
paul718e3742002-12-13 20:15:29 +0000478 continue;
479 }
480 }
481#endif /* ORIGINAL_CODING */
482
483 /* Add the new LSA to the Link state retransmission list
484 for the adjacency. The LSA will be retransmitted
485 at intervals until an acknowledgment is seen from
486 the neighbor. */
487 ospf_ls_retransmit_add (onbr, lsa);
488 retx_flag = 1;
489 }
490
491 /* If in the previous step, the LSA was NOT added to any of
492 the Link state retransmission lists, there is no need to
493 flood the LSA out the interface. */
494 if (retx_flag == 0)
495 {
496 return (inbr && inbr->oi == oi);
497 }
498
499 /* if we've received the lsa on this interface we need to perform
500 additional checking */
501 if (inbr && (inbr->oi == oi))
502 {
503 /* If the new LSA was received on this interface, and it was
504 received from either the Designated Router or the Backup
505 Designated Router, chances are that all the neighbors have
506 received the LSA already. */
507 if (NBR_IS_DR (inbr) || NBR_IS_BDR (inbr))
508 {
paul718e3742002-12-13 20:15:29 +0000509 if (IS_DEBUG_OSPF_NSSA)
ajs60925302004-12-08 17:45:02 +0000510 zlog_debug ("ospf_flood_through_interface(): "
paul718e3742002-12-13 20:15:29 +0000511 "DR/BDR NOT SEND to int %s", IF_NAME (oi));
paul718e3742002-12-13 20:15:29 +0000512 return 1;
513 }
514
515 /* If the new LSA was received on this interface, and the
516 interface state is Backup, examine the next interface. The
517 Designated Router will do the flooding on this interface.
518 However, if the Designated Router fails the router will
519 end up retransmitting the updates. */
520
521 if (oi->state == ISM_Backup)
522 {
paul718e3742002-12-13 20:15:29 +0000523 if (IS_DEBUG_OSPF_NSSA)
ajs60925302004-12-08 17:45:02 +0000524 zlog_debug ("ospf_flood_through_interface(): "
paul718e3742002-12-13 20:15:29 +0000525 "ISM_Backup NOT SEND to int %s", IF_NAME (oi));
paul718e3742002-12-13 20:15:29 +0000526 return 1;
527 }
528 }
529
530 /* The LSA must be flooded out the interface. Send a Link State
531 Update packet (including the new LSA as contents) out the
532 interface. The LSA's LS age must be incremented by InfTransDelay
533 (which must be > 0) when it is copied into the outgoing Link
534 State Update packet (until the LS age field reaches the maximum
535 value of MaxAge). */
hassobeebba72004-06-20 21:00:27 +0000536 /* XXX HASSO: Is this IS_DEBUG_OSPF_NSSA really correct? */
paul718e3742002-12-13 20:15:29 +0000537 if (IS_DEBUG_OSPF_NSSA)
ajs60925302004-12-08 17:45:02 +0000538 zlog_debug ("ospf_flood_through_interface(): "
paul718e3742002-12-13 20:15:29 +0000539 "DR/BDR sending upd to int %s", IF_NAME (oi));
paul718e3742002-12-13 20:15:29 +0000540
541 /* RFC2328 Section 13.3
542 On non-broadcast networks, separate Link State Update
543 packets must be sent, as unicasts, to each adjacent neighbor
544 (i.e., those in state Exchange or greater). The destination
545 IP addresses for these packets are the neighbors' IP
546 addresses. */
547 if (oi->type == OSPF_IFTYPE_NBMA)
548 {
549 struct route_node *rn;
550 struct ospf_neighbor *nbr;
551
552 for (rn = route_top (oi->nbrs); rn; rn = route_next (rn))
553 if ((nbr = rn->info) != NULL)
554 if (nbr != oi->nbr_self && nbr->state >= NSM_Exchange)
555 ospf_ls_upd_send_lsa (nbr, lsa, OSPF_SEND_PACKET_DIRECT);
556 }
557 else
558 ospf_ls_upd_send_lsa (oi->nbr_self, lsa, OSPF_SEND_PACKET_INDIRECT);
559
560 return 0;
561}
562
563int
paul68980082003-03-25 05:07:42 +0000564ospf_flood_through_area (struct ospf_area *area,
565 struct ospf_neighbor *inbr, struct ospf_lsa *lsa)
paul718e3742002-12-13 20:15:29 +0000566{
paul1eb8ef22005-04-07 07:30:20 +0000567 struct listnode *node, *nnode;
568 struct ospf_interface *oi;
paul718e3742002-12-13 20:15:29 +0000569 int lsa_ack_flag = 0;
570
571 /* All other types are specific to a single area (Area A). The
572 eligible interfaces are all those interfaces attaching to the
573 Area A. If Area A is the backbone, this includes all the virtual
574 links. */
paul1eb8ef22005-04-07 07:30:20 +0000575 for (ALL_LIST_ELEMENTS (area->oiflist, node, nnode, oi))
paul718e3742002-12-13 20:15:29 +0000576 {
paul718e3742002-12-13 20:15:29 +0000577 if (area->area_id.s_addr != OSPF_AREA_BACKBONE &&
578 oi->type == OSPF_IFTYPE_VIRTUALLINK)
579 continue;
580
581#ifdef HAVE_OPAQUE_LSA
582 if ((lsa->data->type == OSPF_OPAQUE_LINK_LSA) && (lsa->oi != oi))
583 {
584 /*
585 * Link local scoped Opaque-LSA should only be flooded
586 * for the link on which the LSA has received.
587 */
588 if (IS_DEBUG_OSPF (lsa, LSA_FLOODING))
ajs60925302004-12-08 17:45:02 +0000589 zlog_debug ("Type-9 Opaque-LSA: lsa->oi(%p) != oi(%p)", lsa->oi, oi);
paul718e3742002-12-13 20:15:29 +0000590 continue;
591 }
592#endif /* HAVE_OPAQUE_LSA */
593
594 if (ospf_flood_through_interface (oi, inbr, lsa))
595 lsa_ack_flag = 1;
596 }
597
598 return (lsa_ack_flag);
599}
600
601int
paul68980082003-03-25 05:07:42 +0000602ospf_flood_through_as (struct ospf *ospf, struct ospf_neighbor *inbr,
603 struct ospf_lsa *lsa)
paul718e3742002-12-13 20:15:29 +0000604{
hasso52dc7ee2004-09-23 19:18:23 +0000605 struct listnode *node;
paul1eb8ef22005-04-07 07:30:20 +0000606 struct ospf_area *area;
paul718e3742002-12-13 20:15:29 +0000607 int lsa_ack_flag;
608
609 lsa_ack_flag = 0;
610
611 /* The incoming LSA is type 5 or type 7 (AS-EXTERNAL or AS-NSSA )
612
613 Divert the Type-5 LSA's to all non-NSSA/STUB areas
614
615 Divert the Type-7 LSA's to all NSSA areas
616
617 AS-external-LSAs are flooded throughout the entire AS, with the
618 exception of stub areas (see Section 3.6). The eligible
619 interfaces are all the router's interfaces, excluding virtual
620 links and those interfaces attaching to stub areas. */
621
paul718e3742002-12-13 20:15:29 +0000622 if (CHECK_FLAG (lsa->flags, OSPF_LSA_LOCAL_XLT)) /* Translated from 7 */
623 if (IS_DEBUG_OSPF_NSSA)
ajs60925302004-12-08 17:45:02 +0000624 zlog_debug ("Flood/AS: NSSA TRANSLATED LSA");
paul718e3742002-12-13 20:15:29 +0000625
paul1eb8ef22005-04-07 07:30:20 +0000626 for (ALL_LIST_ELEMENTS_RO (ospf->areas, node, area))
paul718e3742002-12-13 20:15:29 +0000627 {
628 int continue_flag = 0;
hasso52dc7ee2004-09-23 19:18:23 +0000629 struct listnode *if_node;
paul1eb8ef22005-04-07 07:30:20 +0000630 struct ospf_interface *oi;
paul718e3742002-12-13 20:15:29 +0000631
632 switch (area->external_routing)
633 {
634 /* Don't send AS externals into stub areas. Various types
635 of support for partial stub areas can be implemented
636 here. NSSA's will receive Type-7's that have areas
637 matching the originl LSA. */
638 case OSPF_AREA_NSSA: /* Sending Type 5 or 7 into NSSA area */
paul718e3742002-12-13 20:15:29 +0000639 /* Type-7, flood NSSA area */
paul68980082003-03-25 05:07:42 +0000640 if (lsa->data->type == OSPF_AS_NSSA_LSA
641 && area == lsa->area)
paul718e3742002-12-13 20:15:29 +0000642 /* We will send it. */
643 continue_flag = 0;
paul68980082003-03-25 05:07:42 +0000644 else
paul718e3742002-12-13 20:15:29 +0000645 continue_flag = 1; /* Skip this NSSA area for Type-5's et al */
paul718e3742002-12-13 20:15:29 +0000646 break;
paul718e3742002-12-13 20:15:29 +0000647
648 case OSPF_AREA_TYPE_MAX:
649 case OSPF_AREA_STUB:
650 continue_flag = 1; /* Skip this area. */
651 break;
652
653 case OSPF_AREA_DEFAULT:
654 default:
paul718e3742002-12-13 20:15:29 +0000655 /* No Type-7 into normal area */
656 if (lsa->data->type == OSPF_AS_NSSA_LSA)
657 continue_flag = 1; /* skip Type-7 */
658 else
paul718e3742002-12-13 20:15:29 +0000659 continue_flag = 0; /* Do this area. */
660 break;
661 }
662
663 /* Do continue for above switch. Saves a big if then mess */
664 if (continue_flag)
665 continue; /* main for-loop */
666
667 /* send to every interface in this area */
668
paul1eb8ef22005-04-07 07:30:20 +0000669 for (ALL_LIST_ELEMENTS_RO (area->oiflist, if_node, oi))
paul718e3742002-12-13 20:15:29 +0000670 {
paul718e3742002-12-13 20:15:29 +0000671 /* Skip virtual links */
672 if (oi->type != OSPF_IFTYPE_VIRTUALLINK)
673 if (ospf_flood_through_interface (oi, inbr, lsa)) /* lsa */
674 lsa_ack_flag = 1;
675 }
676 } /* main area for-loop */
677
678 return (lsa_ack_flag);
679}
680
681int
paul68980082003-03-25 05:07:42 +0000682ospf_flood_through (struct ospf *ospf,
683 struct ospf_neighbor *inbr, struct ospf_lsa *lsa)
paul718e3742002-12-13 20:15:29 +0000684{
685 int lsa_ack_flag = 0;
686
687 /* Type-7 LSA's for NSSA are flooded throughout the AS here, and
688 upon return are updated in the LSDB for Type-7's. Later,
689 re-fresh will re-send them (and also, if ABR, packet code will
690 translate to Type-5's)
691
692 As usual, Type-5 LSA's (if not DISCARDED because we are STUB or
693 NSSA) are flooded throughout the AS, and are updated in the
694 global table. */
695#ifdef ORIGINAL_CODING
696 switch (lsa->data->type)
697 {
698 case OSPF_ROUTER_LSA:
699 case OSPF_NETWORK_LSA:
700 case OSPF_SUMMARY_LSA:
701 case OSPF_ASBR_SUMMARY_LSA:
702#ifdef HAVE_OPAQUE_LSA
703 case OSPF_OPAQUE_LINK_LSA: /* ospf_flood_through_interface ? */
704 case OSPF_OPAQUE_AREA_LSA:
705#endif /* HAVE_OPAQUE_LSA */
706 lsa_ack_flag = ospf_flood_through_area (inbr->oi->area, inbr, lsa);
707 break;
708 case OSPF_AS_EXTERNAL_LSA: /* Type-5 */
709#ifdef HAVE_OPAQUE_LSA
710 case OSPF_OPAQUE_AS_LSA:
711#endif /* HAVE_OPAQUE_LSA */
paul68980082003-03-25 05:07:42 +0000712 lsa_ack_flag = ospf_flood_through_as (ospf, inbr, lsa);
paul718e3742002-12-13 20:15:29 +0000713 break;
paul718e3742002-12-13 20:15:29 +0000714 /* Type-7 Only received within NSSA, then flooded */
715 case OSPF_AS_NSSA_LSA:
716 /* Any P-bit was installed with the Type-7. */
717 lsa_ack_flag = ospf_flood_through_area (inbr->oi->area, inbr, lsa);
718
719 if (IS_DEBUG_OSPF_NSSA)
ajs60925302004-12-08 17:45:02 +0000720 zlog_debug ("ospf_flood_through: LOCAL NSSA FLOOD of Type-7.");
paul718e3742002-12-13 20:15:29 +0000721 break;
paul718e3742002-12-13 20:15:29 +0000722 default:
723 break;
724 }
725#else /* ORIGINAL_CODING */
726 /*
727 * At the common sub-sub-function "ospf_flood_through_interface()",
728 * a parameter "inbr" will be used to distinguish the called context
729 * whether the given LSA was received from the neighbor, or the
730 * flooding for the LSA starts from this node (e.g. the LSA was self-
731 * originated, or the LSA is going to be flushed from routing domain).
732 *
733 * So, for consistency reasons, this function "ospf_flood_through()"
734 * should also allow the usage that the given "inbr" parameter to be
735 * NULL. If we do so, corresponding AREA parameter should be referred
736 * by "lsa->area", instead of "inbr->oi->area".
737 */
738 switch (lsa->data->type)
739 {
740 case OSPF_AS_EXTERNAL_LSA: /* Type-5 */
741#ifdef HAVE_OPAQUE_LSA
742 case OSPF_OPAQUE_AS_LSA:
743#endif /* HAVE_OPAQUE_LSA */
paul68980082003-03-25 05:07:42 +0000744 lsa_ack_flag = ospf_flood_through_as (ospf, inbr, lsa);
paul718e3742002-12-13 20:15:29 +0000745 break;
paul718e3742002-12-13 20:15:29 +0000746 /* Type-7 Only received within NSSA, then flooded */
747 case OSPF_AS_NSSA_LSA:
748 /* Any P-bit was installed with the Type-7. */
749
750 if (IS_DEBUG_OSPF_NSSA)
ajs60925302004-12-08 17:45:02 +0000751 zlog_debug ("ospf_flood_through: LOCAL NSSA FLOOD of Type-7.");
paul718e3742002-12-13 20:15:29 +0000752 /* Fallthrough */
paul718e3742002-12-13 20:15:29 +0000753 default:
754 lsa_ack_flag = ospf_flood_through_area (lsa->area, inbr, lsa);
755 break;
756 }
757#endif /* ORIGINAL_CODING */
758
759 return (lsa_ack_flag);
760}
761
762
763
764/* Management functions for neighbor's Link State Request list. */
765void
766ospf_ls_request_add (struct ospf_neighbor *nbr, struct ospf_lsa *lsa)
767{
768 /*
769 * We cannot make use of the newly introduced callback function
770 * "lsdb->new_lsa_hook" to replace debug output below, just because
771 * it seems no simple and smart way to pass neighbor information to
772 * the common function "ospf_lsdb_add()" -- endo.
773 */
774 if (IS_DEBUG_OSPF (lsa, LSA_FLOODING))
ajs60925302004-12-08 17:45:02 +0000775 zlog_debug ("RqstL(%lu)++, NBR(%s), LSA[%s]",
paul718e3742002-12-13 20:15:29 +0000776 ospf_ls_request_count (nbr),
777 inet_ntoa (nbr->router_id), dump_lsa_key (lsa));
778
779 ospf_lsdb_add (&nbr->ls_req, lsa);
780}
781
782unsigned long
783ospf_ls_request_count (struct ospf_neighbor *nbr)
784{
785 return ospf_lsdb_count_all (&nbr->ls_req);
786}
787
788int
789ospf_ls_request_isempty (struct ospf_neighbor *nbr)
790{
791 return ospf_lsdb_isempty (&nbr->ls_req);
792}
793
794/* Remove LSA from neighbor's ls-request list. */
795void
796ospf_ls_request_delete (struct ospf_neighbor *nbr, struct ospf_lsa *lsa)
797{
798 if (nbr->ls_req_last == lsa)
799 {
Paul Jakma1fe6ed32006-07-26 09:37:26 +0000800 ospf_lsa_unlock (&nbr->ls_req_last);
paul718e3742002-12-13 20:15:29 +0000801 nbr->ls_req_last = NULL;
802 }
803
804 if (IS_DEBUG_OSPF (lsa, LSA_FLOODING)) /* -- endo. */
ajs60925302004-12-08 17:45:02 +0000805 zlog_debug ("RqstL(%lu)--, NBR(%s), LSA[%s]",
paul718e3742002-12-13 20:15:29 +0000806 ospf_ls_request_count (nbr),
807 inet_ntoa (nbr->router_id), dump_lsa_key (lsa));
808
809 ospf_lsdb_delete (&nbr->ls_req, lsa);
810}
811
812/* Remove all LSA from neighbor's ls-requenst list. */
813void
814ospf_ls_request_delete_all (struct ospf_neighbor *nbr)
815{
Paul Jakma1fe6ed32006-07-26 09:37:26 +0000816 ospf_lsa_unlock (&nbr->ls_req_last);
paul718e3742002-12-13 20:15:29 +0000817 nbr->ls_req_last = NULL;
818 ospf_lsdb_delete_all (&nbr->ls_req);
819}
820
821/* Lookup LSA from neighbor's ls-request list. */
822struct ospf_lsa *
823ospf_ls_request_lookup (struct ospf_neighbor *nbr, struct ospf_lsa *lsa)
824{
825 return ospf_lsdb_lookup (&nbr->ls_req, lsa);
826}
827
828struct ospf_lsa *
829ospf_ls_request_new (struct lsa_header *lsah)
830{
831 struct ospf_lsa *new;
832
833 new = ospf_lsa_new ();
834 new->data = ospf_lsa_data_new (OSPF_LSA_HEADER_SIZE);
835 memcpy (new->data, lsah, OSPF_LSA_HEADER_SIZE);
836
837 return new;
838}
839
840
841/* Management functions for neighbor's ls-retransmit list. */
842unsigned long
843ospf_ls_retransmit_count (struct ospf_neighbor *nbr)
844{
845 return ospf_lsdb_count_all (&nbr->ls_rxmt);
846}
847
848unsigned long
849ospf_ls_retransmit_count_self (struct ospf_neighbor *nbr, int lsa_type)
850{
851 return ospf_lsdb_count_self (&nbr->ls_rxmt, lsa_type);
852}
853
854int
855ospf_ls_retransmit_isempty (struct ospf_neighbor *nbr)
856{
857 return ospf_lsdb_isempty (&nbr->ls_rxmt);
858}
859
860/* Add LSA to be retransmitted to neighbor's ls-retransmit list. */
861void
862ospf_ls_retransmit_add (struct ospf_neighbor *nbr, struct ospf_lsa *lsa)
863{
864 struct ospf_lsa *old;
865
866 old = ospf_ls_retransmit_lookup (nbr, lsa);
867
868 if (ospf_lsa_more_recent (old, lsa) < 0)
869 {
870 if (old)
871 {
872 old->retransmit_counter--;
873 ospf_lsdb_delete (&nbr->ls_rxmt, old);
874 }
875 lsa->retransmit_counter++;
876 /*
877 * We cannot make use of the newly introduced callback function
878 * "lsdb->new_lsa_hook" to replace debug output below, just because
879 * it seems no simple and smart way to pass neighbor information to
880 * the common function "ospf_lsdb_add()" -- endo.
881 */
882 if (IS_DEBUG_OSPF (lsa, LSA_FLOODING))
ajs60925302004-12-08 17:45:02 +0000883 zlog_debug ("RXmtL(%lu)++, NBR(%s), LSA[%s]",
paul718e3742002-12-13 20:15:29 +0000884 ospf_ls_retransmit_count (nbr),
885 inet_ntoa (nbr->router_id), dump_lsa_key (lsa));
886 ospf_lsdb_add (&nbr->ls_rxmt, lsa);
887 }
888}
889
890/* Remove LSA from neibghbor's ls-retransmit list. */
891void
892ospf_ls_retransmit_delete (struct ospf_neighbor *nbr, struct ospf_lsa *lsa)
893{
894 if (ospf_ls_retransmit_lookup (nbr, lsa))
895 {
896 lsa->retransmit_counter--;
897 if (IS_DEBUG_OSPF (lsa, LSA_FLOODING)) /* -- endo. */
ajs60925302004-12-08 17:45:02 +0000898 zlog_debug ("RXmtL(%lu)--, NBR(%s), LSA[%s]",
paul718e3742002-12-13 20:15:29 +0000899 ospf_ls_retransmit_count (nbr),
900 inet_ntoa (nbr->router_id), dump_lsa_key (lsa));
901 ospf_lsdb_delete (&nbr->ls_rxmt, lsa);
902 }
903}
904
905/* Clear neighbor's ls-retransmit list. */
906void
907ospf_ls_retransmit_clear (struct ospf_neighbor *nbr)
908{
909 struct ospf_lsdb *lsdb;
910 int i;
911
912 lsdb = &nbr->ls_rxmt;
913
914 for (i = OSPF_MIN_LSA; i < OSPF_MAX_LSA; i++)
915 {
916 struct route_table *table = lsdb->type[i].db;
917 struct route_node *rn;
918 struct ospf_lsa *lsa;
919
920 for (rn = route_top (table); rn; rn = route_next (rn))
921 if ((lsa = rn->info) != NULL)
922 ospf_ls_retransmit_delete (nbr, lsa);
923 }
924
Paul Jakma1fe6ed32006-07-26 09:37:26 +0000925 ospf_lsa_unlock (&nbr->ls_req_last);
paul718e3742002-12-13 20:15:29 +0000926 nbr->ls_req_last = NULL;
927}
928
929/* Lookup LSA from neighbor's ls-retransmit list. */
930struct ospf_lsa *
931ospf_ls_retransmit_lookup (struct ospf_neighbor *nbr, struct ospf_lsa *lsa)
932{
933 return ospf_lsdb_lookup (&nbr->ls_rxmt, lsa);
934}
935
paul4dadc292005-05-06 21:37:42 +0000936static void
paul68980082003-03-25 05:07:42 +0000937ospf_ls_retransmit_delete_nbr_if (struct ospf_interface *oi,
938 struct ospf_lsa *lsa)
paul718e3742002-12-13 20:15:29 +0000939{
paul68980082003-03-25 05:07:42 +0000940 struct route_node *rn;
941 struct ospf_neighbor *nbr;
942 struct ospf_lsa *lsr;
943
944 if (ospf_if_is_enable (oi))
945 for (rn = route_top (oi->nbrs); rn; rn = route_next (rn))
946 /* If LSA find in LS-retransmit list, then remove it. */
947 if ((nbr = rn->info) != NULL)
948 {
949 lsr = ospf_ls_retransmit_lookup (nbr, lsa);
paul718e3742002-12-13 20:15:29 +0000950
paul68980082003-03-25 05:07:42 +0000951 /* If LSA find in ls-retransmit list, remove it. */
952 if (lsr != NULL && lsr->data->ls_seqnum == lsa->data->ls_seqnum)
953 ospf_ls_retransmit_delete (nbr, lsr);
954 }
paul718e3742002-12-13 20:15:29 +0000955}
956
paul718e3742002-12-13 20:15:29 +0000957void
paul68980082003-03-25 05:07:42 +0000958ospf_ls_retransmit_delete_nbr_area (struct ospf_area *area,
959 struct ospf_lsa *lsa)
paul718e3742002-12-13 20:15:29 +0000960{
paul1eb8ef22005-04-07 07:30:20 +0000961 struct listnode *node, *nnode;
962 struct ospf_interface *oi;
paul718e3742002-12-13 20:15:29 +0000963
paul1eb8ef22005-04-07 07:30:20 +0000964 for (ALL_LIST_ELEMENTS (area->oiflist, node, nnode, oi))
965 ospf_ls_retransmit_delete_nbr_if (oi, lsa);
paul68980082003-03-25 05:07:42 +0000966}
paul718e3742002-12-13 20:15:29 +0000967
paul68980082003-03-25 05:07:42 +0000968void
969ospf_ls_retransmit_delete_nbr_as (struct ospf *ospf, struct ospf_lsa *lsa)
970{
paul1eb8ef22005-04-07 07:30:20 +0000971 struct listnode *node, *nnode;
972 struct ospf_interface *oi;
paul718e3742002-12-13 20:15:29 +0000973
paul1eb8ef22005-04-07 07:30:20 +0000974 for (ALL_LIST_ELEMENTS (ospf->oiflist, node, nnode, oi))
975 ospf_ls_retransmit_delete_nbr_if (oi, lsa);
paul718e3742002-12-13 20:15:29 +0000976}
977
978
979/* Sets ls_age to MaxAge and floods throu the area.
980 When we implement ASE routing, there will be anothe function
981 flushing an LSA from the whole domain. */
982void
983ospf_lsa_flush_area (struct ospf_lsa *lsa, struct ospf_area *area)
984{
985 lsa->data->ls_age = htons (OSPF_LSA_MAXAGE);
986 ospf_flood_through_area (area, NULL, lsa);
paul68980082003-03-25 05:07:42 +0000987 ospf_lsa_maxage (area->ospf, lsa);
paul718e3742002-12-13 20:15:29 +0000988}
989
990void
paul68980082003-03-25 05:07:42 +0000991ospf_lsa_flush_as (struct ospf *ospf, struct ospf_lsa *lsa)
paul718e3742002-12-13 20:15:29 +0000992{
993 lsa->data->ls_age = htons (OSPF_LSA_MAXAGE);
paul68980082003-03-25 05:07:42 +0000994 ospf_flood_through_as (ospf, NULL, lsa);
995 ospf_lsa_maxage (ospf, lsa);
paul718e3742002-12-13 20:15:29 +0000996}