]>
git.ipfire.org Git - thirdparty/bird.git/blob - proto/ospf/topology.c
c8ec730a1e44d581bb2da4827e069c35ebf78292
2 * BIRD -- OSPF Topological Database
4 * (c) 1999 Martin Mares <mj@ucw.cz>
5 * (c) 1999--2004 Ondrej Filip <feela@network.cz>
6 * (c) 2009--2014 Ondrej Zajicek <santiago@crfreenet.org>
7 * (c) 2009--2014 CZ.NIC z.s.p.o.
9 * Can be freely distributed and used under the terms of the GNU GPL.
12 #include "nest/bird.h"
13 #include "lib/string.h"
18 #define HASH_DEF_ORDER 6
19 #define HASH_HI_MARK *4
20 #define HASH_HI_STEP 2
21 #define HASH_HI_MAX 16
22 #define HASH_LO_MARK /5
23 #define HASH_LO_STEP 2
26 static inline void * lsab_flush(struct ospf_proto
*p
);
27 static inline void lsab_reset(struct ospf_proto
*p
);
31 * ospf_install_lsa - install new LSA into database
32 * @p: OSPF protocol instance
35 * @domain: domain of LSA
36 * @body: pointer to LSA body
38 * This function ensures installing new LSA received in LS update into LSA
39 * database. Old instance is replaced. Several actions are taken to detect if
40 * new routing table calculation is necessary. This is described in 13.2 of RFC
41 * 2328. This function is for received LSA only, locally originated LSAs are
42 * installed by ospf_originate_lsa().
44 * The LSA body in @body is expected to be mb_allocated by the caller and its
45 * ownership is transferred to the LSA entry structure.
47 struct top_hash_entry
*
48 ospf_install_lsa(struct ospf_proto
*p
, struct ospf_lsa_header
*lsa
, u32 type
, u32 domain
, void *body
)
50 struct top_hash_entry
*en
;
53 en
= ospf_hash_get(p
->gr
, domain
, lsa
->id
, lsa
->rt
, type
);
56 s_add_tail(&p
->lsal
, SNODE en
);
58 if ((en
->lsa_body
== NULL
) || /* No old LSA */
59 (en
->lsa
.length
!= lsa
->length
) ||
60 (en
->lsa
.type_raw
!= lsa
->type_raw
) || /* Check for OSPFv2 options */
61 (en
->lsa
.age
== LSA_MAXAGE
) ||
62 (lsa
->age
== LSA_MAXAGE
) ||
63 memcmp(en
->lsa_body
, body
, lsa
->length
- sizeof(struct ospf_lsa_header
)))
66 if ((en
->lsa
.age
== LSA_MAXAGE
) && (lsa
->age
== LSA_MAXAGE
))
69 mb_free(en
->lsa_body
);
72 en
->init_age
= en
->lsa
.age
;
73 en
->inst_time
= current_time();
74 en
->gr_dirty
= p
->gr_recovery
&& (lsa
->rt
== p
->router_id
);
77 * We do not set en->mode. It is either default LSA_M_BASIC, or in a special
78 * case when en is local but flushed, there is postponed LSA, self-originated
79 * LSA is received and ospf_install_lsa() is called from ospf_advance_lse(),
80 * then we have en->mode from the postponed LSA origination.
83 OSPF_TRACE(D_EVENTS
, "Installing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x, Age: %u",
84 en
->lsa_type
, en
->lsa
.id
, en
->lsa
.rt
, en
->lsa
.sn
, en
->lsa
.age
);
88 ospf_neigh_lsadb_changed(p
, en
);
89 ospf_schedule_rtcalc(p
);
96 * ospf_advance_lsa - handle received unexpected self-originated LSA
97 * @p: OSPF protocol instance
98 * @en: current LSA entry or NULL
99 * @lsa: new LSA header
101 * @domain: domain of LSA
102 * @body: pointer to LSA body
104 * This function handles received unexpected self-originated LSA (@lsa, @body)
105 * by either advancing sequence number of the local LSA instance (@en) and
106 * propagating it, or installing the received LSA and immediately flushing it
107 * (if there is no local LSA; i.e., @en is NULL or MaxAge).
109 * The LSA body in @body is expected to be mb_allocated by the caller and its
110 * ownership is transferred to the LSA entry structure or it is freed.
113 ospf_advance_lsa(struct ospf_proto
*p
, struct top_hash_entry
*en
, struct ospf_lsa_header
*lsa
, u32 type
, u32 domain
, void *body
)
117 if (en
&& (en
->lsa
.age
< LSA_MAXAGE
))
119 if (lsa
->sn
!= LSA_MAXSEQNO
)
122 * We simply advance current LSA to have higher seqnum than received LSA.
123 * The received LSA is ignored and the advanced LSA is propagated instead.
125 * Although this is an origination of distinct LSA instance and therefore
126 * should be limited by MinLSInterval, we do not enforce it here. Fast
127 * reaction is needed and we are already limited by MinLSArrival.
132 en
->lsa
.sn
= lsa
->sn
+ 1;
135 en
->inst_time
= current_time();
136 lsa_generate_checksum(&en
->lsa
, en
->lsa_body
);
138 OSPF_TRACE(D_EVENTS
, "Advancing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
139 en
->lsa_type
, en
->lsa
.id
, en
->lsa
.rt
, en
->lsa
.sn
);
144 * Received LSA has maximal sequence number, so we cannot simply override
145 * it. We have to install it to the database, immediately flush it to
146 * implement sequence number wrapping, and schedule our current LSA to be
147 * originated after the received instance is flushed.
150 if (en
->next_lsa_body
== NULL
)
152 /* Schedule current LSA */
153 en
->next_lsa_blen
= en
->lsa
.length
- sizeof(struct ospf_lsa_header
);
154 en
->next_lsa_body
= en
->lsa_body
;
155 en
->next_lsa_opts
= ospf_is_v2(p
) ? lsa_get_options(&en
->lsa
) : 0;
159 /* There is already scheduled LSA, so we just free current one */
160 mb_free(en
->lsa_body
);
165 en
->lsa
.age
= LSA_MAXAGE
;
166 en
->init_age
= lsa
->age
;
167 en
->inst_time
= current_time();
169 OSPF_TRACE(D_EVENTS
, "Resetting LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
170 en
->lsa_type
, en
->lsa
.id
, en
->lsa
.rt
, en
->lsa
.sn
);
171 OSPF_TRACE(D_EVENTS
, "Postponing LSA: Type: %04x, Id: %R, Rt: %R",
172 en
->lsa_type
, en
->lsa
.id
, en
->lsa
.rt
);
178 * We do not have received LSA in the database. We have to flush the
179 * received LSA. It has to be installed in the database to secure
180 * retransmissions. Note that the received LSA may already be MaxAge.
181 * Also note that en->next_lsa_* may be defined.
184 lsa
->age
= LSA_MAXAGE
;
185 en
= ospf_install_lsa(p
, lsa
, type
, domain
, body
);
189 * We flood the updated LSA. Although in some cases the to-be-flooded LSA is
190 * the same as the received LSA, and therefore we should propagate it as
191 * regular received LSA (send the acknowledgement instead of the update to
192 * the neighbor we received it from), we cheat a bit here.
195 ospf_flood_lsa(p
, en
, NULL
);
200 ospf_do_originate_lsa(struct ospf_proto
*p
, struct top_hash_entry
*en
, void *lsa_body
, u16 lsa_blen
, u16 lsa_opts
)
202 /* Enforce MinLSInterval */
203 if (!en
->init_age
&& en
->inst_time
&& (lsa_inst_age(en
) < MINLSINTERVAL
))
206 /* Handle wrapping sequence number */
207 if (en
->lsa
.sn
== LSA_MAXSEQNO
)
209 /* Prepare to flush old LSA */
210 if (en
->lsa
.age
!= LSA_MAXAGE
)
212 OSPF_TRACE(D_EVENTS
, "Resetting LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
213 en
->lsa_type
, en
->lsa
.id
, en
->lsa
.rt
, en
->lsa
.sn
);
215 en
->lsa
.age
= LSA_MAXAGE
;
216 ospf_flood_lsa(p
, en
, NULL
);
220 /* Already flushing */
221 if ((p
->padj
!= 0) || (en
->ret_count
!= 0))
224 /* Flush done, just clean up seqnum, lsa_body is freed below */
225 en
->lsa
.sn
= LSA_ZEROSEQNO
;
229 * lsa.type_raw is initialized by ospf_hash_get() to OSPFv3 LSA type.
230 * lsa_set_options() implicitly converts it to OSPFv2 LSA type, assuming that
231 * old type is just new type masked by 0xff. That holds for most OSPFv2 types,
232 * but we have to fix it for opaque LSAs.
237 if (lsa_is_opaque(en
->lsa_type
))
238 en
->lsa
.type_raw
= LSA_T_V2_OPAQUE_
+ LSA_SCOPE_ORDER(en
->lsa_type
);
240 lsa_set_options(&en
->lsa
, lsa_opts
);
243 mb_free(en
->lsa_body
);
244 en
->lsa_body
= lsa_body
;
245 en
->lsa
.length
= sizeof(struct ospf_lsa_header
) + lsa_blen
;
249 en
->inst_time
= current_time();
251 lsa_generate_checksum(&en
->lsa
, en
->lsa_body
);
253 OSPF_TRACE(D_EVENTS
, "Originating LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
254 en
->lsa_type
, en
->lsa
.id
, en
->lsa
.rt
, en
->lsa
.sn
);
256 ospf_flood_lsa(p
, en
, NULL
);
258 if (en
->mode
== LSA_M_BASIC
)
260 ospf_neigh_lsadb_changed(p
, en
);
261 ospf_schedule_rtcalc(p
);
268 * ospf_originate_lsa - originate new LSA
269 * @p: OSPF protocol instance
270 * @lsa: New LSA specification
272 * This function prepares a new LSA, installs it into the LSA database and
273 * floods it. If the new LSA cannot be originated now (because the old instance
274 * was originated within MinLSInterval, or because the LSA seqnum is currently
275 * wrapping), the origination is instead scheduled for later. If the new LSA is
276 * equivalent to the current LSA, the origination is skipped. In all cases, the
277 * corresponding LSA entry is returned. The new LSA is based on the LSA
278 * specification (@lsa) and the LSA body from lsab buffer of @p, which is
279 * emptied after the call. The opposite of this function is ospf_flush_lsa().
281 struct top_hash_entry
*
282 ospf_originate_lsa(struct ospf_proto
*p
, struct ospf_new_lsa
*lsa
)
284 struct top_hash_entry
*en
= NULL
;
285 void *lsa_body
= p
->lsab
;
286 u16 lsa_blen
= p
->lsab_used
;
287 u16 lsa_length
= sizeof(struct ospf_lsa_header
) + lsa_blen
;
289 /* RFC 3623 2 (1) - do not originate topology LSAs during graceful restart */
290 if (p
->gr_recovery
&& (LSA_FUNCTION(lsa
->type
) <= LSA_FUNCTION(LSA_T_NSSA
)))
293 /* For OSPFv2 Opaque LSAs, LS ID consists of Opaque Type and Opaque ID */
294 if (ospf_is_v2(p
) && lsa_is_opaque(lsa
->type
))
295 lsa
->id
|= (u32
) lsa_get_opaque_type(lsa
->type
) << 24;
297 en
= ospf_hash_get(p
->gr
, lsa
->dom
, lsa
->id
, p
->router_id
, lsa
->type
);
299 if (!SNODE_VALID(en
))
300 s_add_tail(&p
->lsal
, SNODE en
);
302 if (!en
->nf
|| !en
->lsa_body
)
305 if (en
->nf
!= lsa
->nf
)
307 log(L_ERR
"%s: LSA ID collision for %N",
308 p
->p
.name
, lsa
->nf
->fn
.addr
);
314 if (en
->mode
!= lsa
->mode
)
315 en
->mode
= lsa
->mode
;
317 if (en
->next_lsa_body
)
319 /* Ignore the new LSA if it is the same as the scheduled one */
320 if ((lsa_blen
== en
->next_lsa_blen
) &&
321 !memcmp(lsa_body
, en
->next_lsa_body
, lsa_blen
) &&
322 (!ospf_is_v2(p
) || (lsa
->opts
== en
->next_lsa_opts
)))
325 /* Free scheduled LSA */
326 mb_free(en
->next_lsa_body
);
327 en
->next_lsa_body
= NULL
;
328 en
->next_lsa_blen
= 0;
329 en
->next_lsa_opts
= 0;
332 /* The static analyzer complains here that en->lsa_body may be NULL.
333 * Yes, it may if ospf_hash_get() creates a new struct top_hash_entry.
334 * In this case, also en->lsa.length must be 0 and lsa_length is never
335 * equal to 0 while sizeof(struct ospf_lsa_header) is non-zero.
336 * Therefore memcmp() is never executed with NULL here.
338 ASSUME((en
->lsa
.length
== 0) == (en
->lsa_body
== NULL
));
340 /* Ignore the the new LSA if is the same as the current one */
341 if ((en
->lsa
.age
< LSA_MAXAGE
) &&
342 (lsa_length
== en
->lsa
.length
) &&
343 !memcmp(lsa_body
, en
->lsa_body
, lsa_blen
) &&
344 (!ospf_is_v2(p
) || (lsa
->opts
== lsa_get_options(&en
->lsa
))) &&
348 lsa_body
= lsab_flush(p
);
350 if (! ospf_do_originate_lsa(p
, en
, lsa_body
, lsa_blen
, lsa
->opts
))
352 OSPF_TRACE(D_EVENTS
, "Postponing LSA: Type: %04x, Id: %R, Rt: %R",
353 en
->lsa_type
, en
->lsa
.id
, en
->lsa
.rt
);
355 en
->next_lsa_body
= lsa_body
;
356 en
->next_lsa_blen
= lsa_blen
;
357 en
->next_lsa_opts
= lsa
->opts
;
368 ospf_originate_next_lsa(struct ospf_proto
*p
, struct top_hash_entry
*en
)
370 /* Called by ospf_update_lsadb() to handle scheduled origination */
372 if (! ospf_do_originate_lsa(p
, en
, en
->next_lsa_body
, en
->next_lsa_blen
, en
->next_lsa_opts
))
375 en
->next_lsa_body
= NULL
;
376 en
->next_lsa_blen
= 0;
377 en
->next_lsa_opts
= 0;
381 ospf_refresh_lsa(struct ospf_proto
*p
, struct top_hash_entry
*en
)
384 * Called by ospf_update_lsadb() for periodic LSA refresh.
386 * We know that lsa.age < LSA_MAXAGE and lsa.rt is our router ID. We can also
387 * assume that there is no scheduled LSA, because inst_time is deep in past,
388 * therefore ospf_originate_next_lsa() called before would either succeed or
389 * switched lsa.age to LSA_MAXAGE.
392 OSPF_TRACE(D_EVENTS
, "Refreshing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
393 en
->lsa_type
, en
->lsa
.id
, en
->lsa
.rt
, en
->lsa
.sn
);
395 ASSERT(en
->next_lsa_body
== NULL
);
397 /* Handle wrapping sequence number */
398 if (en
->lsa
.sn
== LSA_MAXSEQNO
)
400 /* Copy LSA body as next LSA to get automatic origination after flush is finished */
401 en
->next_lsa_blen
= en
->lsa
.length
- sizeof(struct ospf_lsa_header
);
402 en
->next_lsa_body
= mb_alloc(p
->p
.pool
, en
->next_lsa_blen
);
403 memcpy(en
->next_lsa_body
, en
->lsa_body
, en
->next_lsa_blen
);
404 en
->next_lsa_opts
= ospf_is_v2(p
) ? lsa_get_options(&en
->lsa
) : 0;
406 en
->lsa
.age
= LSA_MAXAGE
;
407 ospf_flood_lsa(p
, en
, NULL
);
414 en
->inst_time
= current_time();
415 lsa_generate_checksum(&en
->lsa
, en
->lsa_body
);
416 ospf_flood_lsa(p
, en
, NULL
);
420 * ospf_flush_lsa - flush LSA from OSPF domain
421 * @p: OSPF protocol instance
422 * @en: LSA entry to flush
424 * This function flushes @en from the OSPF domain by setting its age to
425 * %LSA_MAXAGE and flooding it. That also triggers subsequent events in LSA
426 * lifecycle leading to removal of the LSA from the LSA database (e.g. the LSA
427 * content is freed when flushing is acknowledged by neighbors). The function
428 * does nothing if the LSA is already being flushed. LSA entries are not
429 * immediately removed when being flushed, the caller may assume that @en still
430 * exists after the call. The function is the opposite of ospf_originate_lsa()
431 * and is supposed to do the right thing even in cases of postponed
435 ospf_flush_lsa(struct ospf_proto
*p
, struct top_hash_entry
*en
)
440 if (en
->next_lsa_body
)
442 mb_free(en
->next_lsa_body
);
443 en
->next_lsa_body
= NULL
;
444 en
->next_lsa_blen
= 0;
445 en
->next_lsa_opts
= 0;
448 if (en
->lsa
.age
== LSA_MAXAGE
)
451 OSPF_TRACE(D_EVENTS
, "Flushing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
452 en
->lsa_type
, en
->lsa
.id
, en
->lsa
.rt
, en
->lsa
.sn
);
454 en
->lsa
.age
= LSA_MAXAGE
;
455 ospf_flood_lsa(p
, en
, NULL
);
457 if (en
->mode
== LSA_M_BASIC
)
459 ospf_neigh_lsadb_changed(p
, en
);
460 ospf_schedule_rtcalc(p
);
463 en
->mode
= LSA_M_BASIC
;
467 ospf_clear_lsa(struct ospf_proto
*p
, struct top_hash_entry
*en
)
470 * Called by ospf_update_lsadb() as part of LSA flushing process.
471 * Flushed LSA was acknowledged by neighbors and we can free its content.
472 * The log message is for 'remove' - we hide empty LSAs from users.
475 OSPF_TRACE(D_EVENTS
, "Removing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
476 en
->lsa_type
, en
->lsa
.id
, en
->lsa
.rt
, en
->lsa
.sn
);
478 if (en
->lsa
.sn
== LSA_MAXSEQNO
)
479 en
->lsa
.sn
= LSA_ZEROSEQNO
;
481 mb_free(en
->lsa_body
);
486 ospf_remove_lsa(struct ospf_proto
*p
, struct top_hash_entry
*en
)
489 * Called by ospf_update_lsadb() as part of LSA flushing process.
490 * Both lsa_body and next_lsa_body are NULL.
493 s_rem_node(SNODE en
);
494 ospf_hash_delete(p
->gr
, en
);
498 * ospf_update_lsadb - update LSA database
499 * @p: OSPF protocol instance
501 * This function is periodicaly invoked from ospf_disp(). It does some periodic
502 * or postponed processing related to LSA entries. It originates postponed LSAs
503 * scheduled by ospf_originate_lsa(), It continues in flushing processes started
504 * by ospf_flush_lsa(). It also periodically refreshs locally originated LSAs --
505 * when the current instance is older %LSREFRESHTIME, a new instance is originated.
506 * Finally, it also ages stored LSAs and flushes ones that reached %LSA_MAXAGE.
508 * The RFC 2328 says that a router should periodically check checksums of all
509 * stored LSAs to detect hardware problems. This is not implemented.
512 ospf_update_lsadb(struct ospf_proto
*p
)
514 struct top_hash_entry
*en
, *nxt
;
515 btime now_
= current_time();
518 WALK_SLIST_DELSAFE(en
, nxt
, p
->lsal
)
520 if (en
->next_lsa_body
)
521 ospf_originate_next_lsa(p
, en
);
523 real_age
= en
->init_age
+ (now_
- en
->inst_time
) TO_S
;
525 if (en
->lsa
.age
== LSA_MAXAGE
)
527 if (en
->lsa_body
&& (p
->padj
== 0) && (en
->ret_count
== 0))
528 ospf_clear_lsa(p
, en
);
530 if ((en
->lsa_body
== NULL
) && (en
->next_lsa_body
== NULL
) &&
531 ((en
->lsa
.rt
!= p
->router_id
) || (real_age
>= LSA_MAXAGE
)))
532 ospf_remove_lsa(p
, en
);
537 if ((en
->lsa
.rt
== p
->router_id
) && (real_age
>= LSREFRESHTIME
))
539 ospf_refresh_lsa(p
, en
);
543 if (real_age
>= LSA_MAXAGE
)
545 ospf_flush_lsa(p
, en
);
549 en
->lsa
.age
= real_age
;
554 ospf_feed_begin(struct channel
*C
, int initial UNUSED
)
556 struct ospf_proto
*p
= (struct ospf_proto
*) C
->proto
;
557 struct top_hash_entry
*en
;
559 /* Mark all external LSAs as stale */
560 WALK_SLIST(en
, p
->lsal
)
561 if (en
->mode
== LSA_M_EXPORT
)
562 en
->mode
= LSA_M_EXPORT_STALE
;
566 ospf_feed_end(struct channel
*C
)
568 struct ospf_proto
*p
= (struct ospf_proto
*) C
->proto
;
569 struct top_hash_entry
*en
;
571 /* Flush stale LSAs */
572 WALK_SLIST(en
, p
->lsal
)
573 if (en
->mode
== LSA_M_EXPORT_STALE
)
574 ospf_flush_lsa(p
, en
);
578 ort_to_lsaid(struct ospf_proto
*p
, ort
*nf
)
581 * In OSPFv2, We have to map IP prefixes to u32 in such manner that resulting
582 * u32 interpreted as IP address is a member of given prefix. Therefore, /32
583 * prefix has to be mapped on itself. All received prefixes have to be mapped
586 * We have an assumption that if there is nontrivial (non-/32) network prefix,
587 * then there is not /32 prefix for the first and the last IP address of the
588 * network (these are usually reserved, therefore it is not an important
589 * restriction). The network prefix is mapped to the first or the last IP
590 * address in the manner that disallow collisions - we use the IP address that
591 * cannot be used by the parent prefix.
594 * 192.168.0.0/24 maps to 192.168.0.255
595 * 192.168.1.0/24 maps to 192.168.1.0
596 * because 192.168.0.0 and 192.168.1.255 might be used by 192.168.0.0/23 .
598 * Appendig E of RFC 2328 suggests different algorithm, that tries to maximize
599 * both compatibility and subnetting. But as it is not possible to have both
600 * reliably and the suggested algorithm was unnecessary complicated and it
601 * does crazy things like changing LSA ID for a network because different
602 * network appeared, we choose a different way.
604 * In OSPFv3, it is simpler. There is not a requirement for membership of the
605 * result in the input network, so we just allocate a unique ID from ID map
606 * and store it in nf->lsa_id for further reference.
612 nf
->lsa_id
= idm_alloc(&p
->idm
);
617 net_addr_ip4
*net
= (void *) nf
->fn
.addr
;
618 u32 id
= ip4_to_u32(net
->prefix
);
619 int pxlen
= net
->pxlen
;
621 if ((pxlen
== 0) || (pxlen
== 32))
624 if (id
& (1 << (32 - pxlen
)))
627 return id
| ~u32_mkmask(pxlen
);
632 lsab_alloc(struct ospf_proto
*p
, uint size
)
634 uint offset
= p
->lsab_used
;
635 p
->lsab_used
+= size
;
636 if (p
->lsab_used
> p
->lsab_size
)
638 p
->lsab_size
= MAX(p
->lsab_used
, 2 * p
->lsab_size
);
639 p
->lsab
= p
->lsab
? mb_realloc(p
->lsab
, p
->lsab_size
):
640 mb_alloc(p
->p
.pool
, p
->lsab_size
);
642 return ((byte
*) p
->lsab
) + offset
;
646 lsab_allocz(struct ospf_proto
*p
, uint size
)
648 void *r
= lsab_alloc(p
, size
);
654 lsab_flush(struct ospf_proto
*p
)
656 void *r
= mb_alloc(p
->p
.pool
, p
->lsab_used
);
657 memcpy(r
, p
->lsab
, p
->lsab_used
);
663 lsab_reset(struct ospf_proto
*p
)
669 lsab_offset(struct ospf_proto
*p
, uint offset
)
671 return ((byte
*) p
->lsab
) + offset
;
674 static inline void * UNUSED
675 lsab_end(struct ospf_proto
*p
)
677 return ((byte
*) p
->lsab
) + p
->lsab_used
;
682 * Router-LSA handling
687 configured_stubnet(struct ospf_area
*oa
, struct ifa
*a
)
689 /* Does not work for IA_PEER addresses, but it is not called on these */
690 struct ospf_stubnet_config
*sn
;
691 WALK_LIST(sn
, oa
->ac
->stubnet_list
)
695 if (net_in_netX(&a
->prefix
, &sn
->prefix
))
700 if (net_equal(&a
->prefix
, &sn
->prefix
))
709 bcast_net_active(struct ospf_iface
*ifa
)
711 struct ospf_neighbor
*neigh
;
713 if (ifa
->state
== OSPF_IS_WAITING
)
716 WALK_LIST(neigh
, ifa
->neigh_list
)
718 if (neigh
->state
== NEIGHBOR_FULL
)
720 if (neigh
->rid
== ifa
->drid
)
723 if (ifa
->state
== OSPF_IS_DR
)
732 get_rt_options(struct ospf_proto
*p
, struct ospf_area
*oa
, int bitv
)
739 if ((p
->areano
> 1) && oa_is_nssa(oa
) && oa
->ac
->translator
)
742 if (p
->asbr
&& !oa_is_stub(oa
))
752 add_rt2_lsa_link(struct ospf_proto
*p
, u8 type
, u32 id
, u32 data
, u16 metric
)
754 struct ospf_lsa_rt2_link
*ln
= lsab_alloc(p
, sizeof(struct ospf_lsa_rt2_link
));
763 prepare_rt2_lsa_body(struct ospf_proto
*p
, struct ospf_area
*oa
)
765 struct ospf_iface
*ifa
;
767 struct ospf_neighbor
*neigh
;
769 ASSERT(p
->lsab_used
== 0);
770 lsab_allocz(p
, sizeof(struct ospf_lsa_rt
));
771 /* ospf_lsa_rt header will be filled later */
773 WALK_LIST(ifa
, p
->iface_list
)
776 u32 link_cost
= p
->stub_router
? 0xffff : ifa
->cost
;
778 if ((ifa
->type
== OSPF_IT_VLINK
) && (ifa
->voa
== oa
) &&
779 (!EMPTY_LIST(ifa
->neigh_list
)))
781 neigh
= (struct ospf_neighbor
*) HEAD(ifa
->neigh_list
);
782 if ((neigh
->state
== NEIGHBOR_FULL
) && (ifa
->cost
<= 0xffff))
786 if ((ifa
->oa
!= oa
) || (ifa
->state
== OSPF_IS_DOWN
))
791 /* RFC 2328 - 12.4.1.1-4 */
796 WALK_LIST(neigh
, ifa
->neigh_list
)
797 if (neigh
->state
== NEIGHBOR_FULL
)
800 * ln->data should be ifa->iface_id in case of no/ptp
801 * address (ifa->addr->flags & IA_PEER) on PTP link (see
802 * RFC 2328 12.4.1.1.), but the iface ID value has no use,
803 * while using IP address even in this case is here for
804 * compatibility with some broken implementations that use
805 * this address as a next-hop.
807 add_rt2_lsa_link(p
, LSART_PTP
, neigh
->rid
, ipa_to_u32(ifa
->addr
->ip
), link_cost
);
814 if (bcast_net_active(ifa
))
816 add_rt2_lsa_link(p
, LSART_NET
, ipa_to_u32(ifa
->drip
), ipa_to_u32(ifa
->addr
->ip
), link_cost
);
823 neigh
= (struct ospf_neighbor
*) HEAD(ifa
->neigh_list
);
824 if ((!EMPTY_LIST(ifa
->neigh_list
)) && (neigh
->state
== NEIGHBOR_FULL
) && (ifa
->cost
<= 0xffff))
825 add_rt2_lsa_link(p
, LSART_VLNK
, neigh
->rid
, ipa_to_u32(ifa
->addr
->ip
), link_cost
), i
++;
829 log(L_BUG
"OSPF: Unknown interface type");
835 /* Now we will originate stub area if there is no primary */
837 (ifa
->type
== OSPF_IT_VLINK
) ||
838 ((ifa
->addr
->flags
& IA_PEER
) && ! ifa
->cf
->stub
) ||
839 configured_stubnet(oa
, ifa
->addr
))
842 /* Host or network stub entry */
843 if ((ifa
->addr
->flags
& IA_HOST
) ||
844 (ifa
->state
== OSPF_IS_LOOP
) ||
845 (ifa
->type
== OSPF_IT_PTMP
))
846 add_rt2_lsa_link(p
, LSART_STUB
, ipa_to_u32(ifa
->addr
->ip
), 0xffffffff, 0);
848 add_rt2_lsa_link(p
, LSART_STUB
, ip4_to_u32(net4_prefix(&ifa
->addr
->prefix
)),
849 u32_mkmask(net4_pxlen(&ifa
->addr
->prefix
)), ifa
->cost
);
855 struct ospf_stubnet_config
*sn
;
856 WALK_LIST(sn
, oa
->ac
->stubnet_list
)
858 add_rt2_lsa_link(p
, LSART_STUB
, ip4_to_u32(net4_prefix(&sn
->prefix
)),
859 u32_mkmask(net4_pxlen(&sn
->prefix
)), sn
->cost
), i
++;
861 struct ospf_lsa_rt
*rt
= p
->lsab
;
862 /* Store number of links in lower half of options */
863 rt
->options
= get_rt_options(p
, oa
, bitv
) | (u16
) i
;
867 add_rt3_lsa_link(struct ospf_proto
*p
, u8 type
, struct ospf_iface
*ifa
, u32 nif
, u32 id
)
869 struct ospf_lsa_rt3_link
*ln
= lsab_alloc(p
, sizeof(struct ospf_lsa_rt3_link
));
872 ln
->metric
= ifa
->cost
;
873 ln
->lif
= ifa
->iface_id
;
879 prepare_rt3_lsa_body(struct ospf_proto
*p
, struct ospf_area
*oa
)
881 struct ospf_iface
*ifa
;
882 struct ospf_neighbor
*neigh
;
886 ASSERT(p
->lsab_used
== 0);
887 lsab_allocz(p
, sizeof(struct ospf_lsa_rt
));
888 /* ospf_lsa_rt header will be filled later */
890 WALK_LIST(ifa
, p
->iface_list
)
892 if ((ifa
->type
== OSPF_IT_VLINK
) && (ifa
->voa
== oa
) &&
893 (!EMPTY_LIST(ifa
->neigh_list
)))
895 neigh
= (struct ospf_neighbor
*) HEAD(ifa
->neigh_list
);
896 if ((neigh
->state
== NEIGHBOR_FULL
) && (ifa
->cost
<= 0xffff))
900 if ((ifa
->oa
!= oa
) || (ifa
->state
== OSPF_IS_DOWN
))
905 /* RFC 5340 - 4.4.3.2 */
910 WALK_LIST(neigh
, ifa
->neigh_list
)
911 if (neigh
->state
== NEIGHBOR_FULL
)
912 add_rt3_lsa_link(p
, LSART_PTP
, ifa
, neigh
->iface_id
, neigh
->rid
), i
++;
917 if (bcast_net_active(ifa
))
918 add_rt3_lsa_link(p
, LSART_NET
, ifa
, ifa
->dr_iface_id
, ifa
->drid
), i
++;
922 neigh
= (struct ospf_neighbor
*) HEAD(ifa
->neigh_list
);
923 if ((!EMPTY_LIST(ifa
->neigh_list
)) && (neigh
->state
== NEIGHBOR_FULL
) && (ifa
->cost
<= 0xffff))
924 add_rt3_lsa_link(p
, LSART_VLNK
, ifa
, neigh
->iface_id
, neigh
->rid
), i
++;
928 log(L_BUG
"OSPF: Unknown interface type");
935 struct ospf_lsa_rt
*rt
= p
->lsab
;
936 rt
->options
= get_rt_options(p
, oa
, bitv
) | (oa
->options
& LSA_OPTIONS_MASK
);
940 ospf_originate_rt_lsa(struct ospf_proto
*p
, struct ospf_area
*oa
)
942 struct ospf_new_lsa lsa
= {
945 .id
= ospf_is_v2(p
) ? p
->router_id
: 0,
949 OSPF_TRACE(D_EVENTS
, "Updating router state for area %R", oa
->areaid
);
952 prepare_rt2_lsa_body(p
, oa
);
954 prepare_rt3_lsa_body(p
, oa
);
956 oa
->rt
= ospf_originate_lsa(p
, &lsa
);
966 prepare_net2_lsa_body(struct ospf_proto
*p
, struct ospf_iface
*ifa
)
968 struct ospf_lsa_net
*net
;
969 struct ospf_neighbor
*n
;
970 int nodes
= ifa
->fadj
+ 1;
973 ASSERT(p
->lsab_used
== 0);
974 net
= lsab_alloc(p
, sizeof(struct ospf_lsa_net
) + 4 * nodes
);
976 net
->optx
= u32_mkmask(ifa
->addr
->prefix
.pxlen
);
977 net
->routers
[0] = p
->router_id
;
979 WALK_LIST(n
, ifa
->neigh_list
)
981 if (n
->state
== NEIGHBOR_FULL
)
983 net
->routers
[i
] = n
->rid
;
991 prepare_net3_lsa_body(struct ospf_proto
*p
, struct ospf_iface
*ifa
)
993 struct ospf_lsa_net
*net
;
994 int nodes
= ifa
->fadj
+ 1;
998 ASSERT(p
->lsab_used
== 0);
999 net
= lsab_alloc(p
, sizeof(struct ospf_lsa_net
) + 4 * nodes
);
1001 net
->routers
[0] = p
->router_id
;
1003 struct ospf_neighbor
*n
;
1004 WALK_LIST(n
, ifa
->neigh_list
)
1006 if (n
->state
== NEIGHBOR_FULL
)
1008 /* In OSPFv3, we would like to merge options from Link LSAs of added neighbors */
1010 struct top_hash_entry
*en
=
1011 ospf_hash_find(p
->gr
, ifa
->iface_id
, n
->iface_id
, n
->rid
, LSA_T_LINK
);
1014 options
|= ((struct ospf_lsa_link
*) en
->lsa_body
)->options
;
1016 net
->routers
[i
] = n
->rid
;
1022 net
->optx
= options
& LSA_OPTIONS_MASK
;
1026 ospf_originate_net_lsa(struct ospf_proto
*p
, struct ospf_iface
*ifa
)
1028 struct ospf_new_lsa lsa
= {
1030 .dom
= ifa
->oa
->areaid
,
1031 .id
= ospf_is_v2(p
) ? ipa_to_u32(ifa
->addr
->ip
) : ifa
->iface_id
,
1032 .opts
= ifa
->oa
->options
,
1036 OSPF_TRACE(D_EVENTS
, "Updating network state for %s (Id: %R)", ifa
->ifname
, lsa
.id
);
1039 prepare_net2_lsa_body(p
, ifa
);
1041 prepare_net3_lsa_body(p
, ifa
);
1043 ifa
->net_lsa
= ospf_originate_lsa(p
, &lsa
);
1048 * (Net|Rt)-summary-LSA handling
1049 * (a.k.a. Inter-Area-(Prefix|Router)-LSA)
1050 * Type = LSA_T_SUM_NET, LSA_T_SUM_RT
1054 prepare_sum2_lsa_body(struct ospf_proto
*p
, uint pxlen
, u32 metric
)
1056 struct ospf_lsa_sum2
*sum
;
1058 sum
= lsab_allocz(p
, sizeof(struct ospf_lsa_sum2
));
1059 sum
->netmask
= u32_mkmask(pxlen
);
1060 sum
->metric
= metric
;
1064 prepare_sum3_net_lsa_body(struct ospf_proto
*p
, ort
*nf
, u32 metric
)
1066 struct ospf_lsa_sum3_net
*sum
;
1068 sum
= lsab_allocz(p
, sizeof(struct ospf_lsa_sum3_net
) +
1069 IPV6_PREFIX_SPACE(nf
->fn
.addr
->pxlen
));
1070 sum
->metric
= metric
;
1071 ospf3_put_prefix(sum
->prefix
, nf
->fn
.addr
, 0, 0);
1075 prepare_sum3_rt_lsa_body(struct ospf_proto
*p
, u32 drid
, u32 metric
, u32 options
)
1077 struct ospf_lsa_sum3_rt
*sum
;
1079 sum
= lsab_allocz(p
, sizeof(struct ospf_lsa_sum3_rt
));
1080 sum
->options
= options
;
1081 sum
->metric
= metric
;
1086 ospf_originate_sum_net_lsa(struct ospf_proto
*p
, struct ospf_area
*oa
, ort
*nf
, int metric
)
1088 struct ospf_new_lsa lsa
= {
1089 .type
= LSA_T_SUM_NET
,
1090 .mode
= LSA_M_RTCALC
,
1092 .id
= ort_to_lsaid(p
, nf
),
1093 .opts
= oa
->options
,
1098 prepare_sum2_lsa_body(p
, nf
->fn
.addr
->pxlen
, metric
);
1100 prepare_sum3_net_lsa_body(p
, nf
, metric
);
1102 ospf_originate_lsa(p
, &lsa
);
1106 ospf_originate_sum_rt_lsa(struct ospf_proto
*p
, struct ospf_area
*oa
, u32 drid
, int metric
, u32 options
)
1108 struct ospf_new_lsa lsa
= {
1109 .type
= LSA_T_SUM_RT
,
1110 .mode
= LSA_M_RTCALC
,
1112 .id
= drid
, /* Router ID of ASBR, irrelevant for OSPFv3 */
1117 prepare_sum2_lsa_body(p
, 0, metric
);
1119 prepare_sum3_rt_lsa_body(p
, drid
, metric
, options
& LSA_OPTIONS_MASK
);
1121 ospf_originate_lsa(p
, &lsa
);
1126 * AS-external-LSA and NSSA-LSA handling
1127 * Type = LSA_T_EXT, LSA_T_NSSA
1131 prepare_ext2_lsa_body(struct ospf_proto
*p
, uint pxlen
,
1132 u32 metric
, u32 ebit
, ip_addr fwaddr
, u32 tag
)
1134 struct ospf_lsa_ext2
*ext
;
1136 ext
= lsab_allocz(p
, sizeof(struct ospf_lsa_ext2
));
1137 ext
->metric
= metric
& LSA_METRIC_MASK
;
1138 ext
->netmask
= u32_mkmask(pxlen
);
1139 ext
->fwaddr
= ipa_to_u32(fwaddr
);
1143 ext
->metric
|= LSA_EXT2_EBIT
;
1147 prepare_ext3_lsa_body(struct ospf_proto
*p
, ort
*nf
,
1148 u32 metric
, u32 ebit
, ip_addr fwaddr
, u32 tag
, int pbit
, int dn
)
1150 struct ospf_lsa_ext3
*ext
;
1151 int bsize
= sizeof(struct ospf_lsa_ext3
)
1152 + IPV6_PREFIX_SPACE(nf
->fn
.addr
->pxlen
)
1153 + (ipa_nonzero(fwaddr
) ? 16 : 0)
1156 ext
= lsab_allocz(p
, bsize
);
1157 ext
->metric
= metric
& LSA_METRIC_MASK
;
1158 u32
*buf
= ext
->rest
;
1160 uint flags
= (pbit
? OPT_PX_P
: 0) | (dn
? OPT_PX_DN
: 0);
1161 buf
= ospf3_put_prefix(buf
, nf
->fn
.addr
, flags
, 0);
1164 ext
->metric
|= LSA_EXT3_EBIT
;
1166 if (ipa_nonzero(fwaddr
))
1168 ext
->metric
|= LSA_EXT3_FBIT
;
1169 buf
= ospf3_put_addr(buf
, fwaddr
);
1174 ext
->metric
|= LSA_EXT3_TBIT
;
1180 * originate_ext_lsa - new route received from nest and filters
1181 * @p: OSPF protocol instance
1182 * @oa: ospf_area for which LSA is originated
1183 * @nf: network prefix and mask
1184 * @mode: the mode of the LSA (LSA_M_EXPORT or LSA_M_RTCALC)
1185 * @metric: the metric of a route
1186 * @ebit: E-bit for route metric (bool)
1187 * @fwaddr: the forwarding address
1188 * @tag: the route tag
1189 * @pbit: P-bit for NSSA LSAs (bool), ignored for external LSAs
1191 * If I receive a message that new route is installed, I try to originate an
1192 * external LSA. If @oa is an NSSA area, NSSA-LSA is originated instead.
1193 * @oa should not be a stub area. @src does not specify whether the LSA
1194 * is external or NSSA, but it specifies the source of origination -
1195 * the export from ospf_rt_notify(), or the NSSA-EXT translation.
1198 ospf_originate_ext_lsa(struct ospf_proto
*p
, struct ospf_area
*oa
, ort
*nf
, u8 mode
,
1199 u32 metric
, u32 ebit
, ip_addr fwaddr
, u32 tag
, int pbit
, int dn
)
1201 struct ospf_new_lsa lsa
= {
1202 .type
= oa
? LSA_T_NSSA
: LSA_T_EXT
,
1203 .mode
= mode
, /* LSA_M_EXPORT or LSA_M_RTCALC */
1204 .dom
= oa
? oa
->areaid
: 0,
1205 .id
= ort_to_lsaid(p
, nf
),
1206 .opts
= (oa
? (pbit
? OPT_P
: 0) : OPT_E
) | (dn
? OPT_DN
: 0),
1211 prepare_ext2_lsa_body(p
, nf
->fn
.addr
->pxlen
, metric
, ebit
, fwaddr
, tag
);
1213 prepare_ext3_lsa_body(p
, nf
, metric
, ebit
, fwaddr
, tag
, oa
&& pbit
, dn
);
1215 ospf_originate_lsa(p
, &lsa
);
1218 static struct top_hash_entry
*
1219 ospf_hash_find_(struct top_graph
*f
, u32 domain
, u32 lsa
, u32 rtr
, u32 type
);
1222 ospf_flush_ext_lsa(struct ospf_proto
*p
, struct ospf_area
*oa
, ort
*nf
)
1224 struct top_hash_entry
*en
;
1226 u32 type
= oa
? LSA_T_NSSA
: LSA_T_EXT
;
1227 u32 dom
= oa
? oa
->areaid
: 0;
1228 u32 id
= ort_to_lsaid(p
, nf
);
1230 en
= ospf_hash_find_(p
->gr
, dom
, id
, p
->router_id
, type
);
1232 if (!en
|| (en
->nf
!= nf
))
1235 ospf_flush_lsa(p
, en
);
1239 use_gw_for_fwaddr(struct ospf_proto
*p
, ip_addr gw
, struct iface
*iface
)
1241 struct ospf_iface
*ifa
;
1243 if (ipa_zero(gw
) || ipa_is_link_local(gw
))
1246 WALK_LIST(ifa
, p
->iface_list
)
1247 if ((ifa
->iface
== iface
) &&
1248 (!ospf_is_v2(p
) || ipa_in_netX(gw
, &ifa
->addr
->prefix
)))
1254 static inline ip_addr
1255 find_surrogate_fwaddr(struct ospf_proto
*p
, struct ospf_area
*oa
)
1257 struct ospf_iface
*ifa
;
1258 struct ifa
*a
, *cur_addr
= NULL
;
1261 /* RFC 3101 2.3 - surrogate forwarding address selection */
1263 WALK_LIST(ifa
, p
->iface_list
)
1265 if ((ifa
->oa
!= oa
) ||
1266 (ifa
->type
== OSPF_IT_VLINK
))
1272 if (a
->flags
& IA_PEER
)
1275 np
= (a
->flags
& IA_HOST
) ? 3 : (ifa
->stub
? 2 : 1);
1284 WALK_LIST(a
, ifa
->iface
->addrs
)
1286 if ((a
->prefix
.type
!= ospf_get_af(p
)) ||
1287 (a
->flags
& IA_SECONDARY
) ||
1288 (a
->flags
& IA_PEER
) ||
1289 (a
->scope
<= SCOPE_LINK
))
1292 np
= (a
->flags
& IA_HOST
) ? 3 : (ifa
->stub
? 2 : 1);
1302 return cur_addr
? cur_addr
->ip
: IPA_NONE
;
1306 ospf_rt_notify(struct proto
*P
, struct channel
*ch UNUSED
, net
*n
, rte
*new, rte
*old UNUSED
)
1308 struct ospf_proto
*p
= (struct ospf_proto
*) P
;
1309 struct ospf_area
*oa
= NULL
; /* non-NULL for NSSA-LSA */
1313 * There are several posibilities:
1314 * 1) router in regular area - originate external LSA with global scope
1315 * 2) router in NSSA area - originate area-specific NSSA-LSA
1316 * 3) router in stub area - cannot export routes
1317 * 4) area border router - same as (1), it is attached to backbone
1320 if ((p
->areano
== 1) && oa_is_nssa(HEAD(p
->area_list
)))
1321 oa
= HEAD(p
->area_list
);
1325 nf
= fib_find(&p
->rtf
, n
->n
.addr
);
1327 if (!nf
|| !nf
->external_rte
)
1330 ospf_flush_ext_lsa(p
, oa
, nf
);
1331 nf
->external_rte
= 0;
1333 /* Old external route might blocked some NSSA translation */
1334 if ((p
->areano
> 1) && rt_is_nssa(nf
) && nf
->n
.oa
->translate
)
1335 ospf_schedule_rtcalc(p
);
1342 /* Get route attributes */
1343 rta
*a
= new->attrs
;
1344 eattr
*m1a
= ea_find(a
->eattrs
, EA_OSPF_METRIC1
);
1345 eattr
*m2a
= ea_find(a
->eattrs
, EA_OSPF_METRIC2
);
1346 uint m1
= m1a
? m1a
->u
.data
: 0;
1347 uint m2
= m2a
? m2a
->u
.data
: 10000;
1349 if (m1
> LSINFINITY
)
1351 log(L_WARN
"%s: Invalid ospf_metric1 value %u for route %N",
1352 p
->p
.name
, m1
, n
->n
.addr
);
1356 if (m2
> LSINFINITY
)
1358 log(L_WARN
"%s: Invalid ospf_metric2 value %u for route %N",
1359 p
->p
.name
, m2
, n
->n
.addr
);
1363 /* Ensure monotonicity of metric if both m1 and m2 are used */
1364 if ((m1
> 0) && (m2
< LSINFINITY
))
1367 uint ebit
= m2a
|| !m1a
;
1368 uint metric
= ebit
? m2
: m1
;
1369 uint tag
= ea_get_int(a
->eattrs
, EA_OSPF_TAG
, 0);
1371 ip_addr fwd
= IPA_NONE
;
1372 if ((a
->dest
== RTD_UNICAST
) && use_gw_for_fwaddr(p
, a
->nh
.gw
, a
->nh
.iface
))
1375 /* NSSA-LSA with P-bit set must have non-zero forwarding address */
1376 if (oa
&& ipa_zero(fwd
))
1378 fwd
= find_surrogate_fwaddr(p
, oa
);
1382 log(L_ERR
"%s: Cannot find forwarding address for NSSA-LSA %N",
1383 p
->p
.name
, n
->n
.addr
);
1388 nf
= fib_get(&p
->rtf
, n
->n
.addr
);
1389 ospf_originate_ext_lsa(p
, oa
, nf
, LSA_M_EXPORT
, metric
, ebit
, fwd
, tag
, 1, p
->vpn_pe
);
1390 nf
->external_rte
= 1;
1395 * Link-LSA handling (assume OSPFv3)
1400 lsab_put_prefix(struct ospf_proto
*p
, net_addr
*n
, u32 cost
)
1402 void *buf
= lsab_alloc(p
, IPV6_PREFIX_SPACE(net_pxlen(n
)));
1403 uint max
= (n
->type
== NET_IP4
) ? IP4_MAX_PREFIX_LENGTH
: IP6_MAX_PREFIX_LENGTH
;
1404 u8 flags
= (net_pxlen(n
) < max
) ? 0 : OPT_PX_LA
;
1405 ospf3_put_prefix(buf
, n
, flags
, cost
);
1409 prepare_link_lsa_body(struct ospf_proto
*p
, struct ospf_iface
*ifa
)
1411 ip_addr nh
= ospf_is_ip4(p
) ? IPA_NONE
: ifa
->addr
->ip
;
1414 /* Preallocating space for header */
1415 ASSERT(p
->lsab_used
== 0);
1416 lsab_allocz(p
, sizeof(struct ospf_lsa_link
));
1419 WALK_LIST(a
, ifa
->iface
->addrs
)
1421 if ((a
->prefix
.type
!= ospf_get_af(p
)) ||
1422 (a
->flags
& IA_SECONDARY
) ||
1423 (a
->scope
<= SCOPE_LINK
))
1426 if (ospf_is_ip4(p
) && ipa_zero(nh
))
1429 lsab_put_prefix(p
, &a
->prefix
, 0);
1433 /* Filling the preallocated header */
1434 struct ospf_lsa_link
*ll
= p
->lsab
;
1435 ll
->options
= ifa
->oa
->options
| (ifa
->priority
<< 24);
1436 ll
->lladdr
= ospf_is_ip4(p
) ? ospf3_4to6(ipa_to_ip4(nh
)) : ipa_to_ip6(nh
);
1440 log(L_ERR
"%s: Cannot find next hop address for %s", p
->p
.name
, ifa
->ifname
);
1444 ospf_originate_link_lsa(struct ospf_proto
*p
, struct ospf_iface
*ifa
)
1449 struct ospf_new_lsa lsa
= {
1451 .dom
= ifa
->iface_id
,
1452 .id
= ifa
->iface_id
,
1456 OSPF_TRACE(D_EVENTS
, "Updating link state for %s (Id: %R)", ifa
->ifname
, lsa
.id
);
1458 prepare_link_lsa_body(p
, ifa
);
1460 ifa
->link_lsa
= ospf_originate_lsa(p
, &lsa
);
1465 * Prefix-Rt-LSA handling (assume OSPFv3)
1466 * Type = LSA_T_PREFIX, referred type = LSA_T_RT
1470 prepare_prefix_rt_lsa_body(struct ospf_proto
*p
, struct ospf_area
*oa
)
1472 struct ospf_config
*cf
= (struct ospf_config
*) (p
->p
.cf
);
1473 struct ospf_iface
*ifa
;
1474 struct ospf_lsa_prefix
*lp
;
1475 uint max
= ospf_is_ip4(p
) ? IP4_MAX_PREFIX_LENGTH
: IP6_MAX_PREFIX_LENGTH
;
1480 ASSERT(p
->lsab_used
== 0);
1481 lp
= lsab_allocz(p
, sizeof(struct ospf_lsa_prefix
));
1482 lp
->ref_type
= LSA_T_RT
;
1484 lp
->ref_rt
= p
->router_id
;
1485 lp
= NULL
; /* buffer might be reallocated later */
1487 WALK_LIST(ifa
, p
->iface_list
)
1489 if ((ifa
->oa
!= oa
) || (ifa
->type
== OSPF_IT_VLINK
) || (ifa
->state
== OSPF_IS_DOWN
))
1492 ifa
->px_pos_beg
= i
;
1494 if ((ifa
->type
== OSPF_IT_BCAST
) ||
1495 (ifa
->type
== OSPF_IT_NBMA
))
1496 net_lsa
= bcast_net_active(ifa
);
1501 WALK_LIST(a
, ifa
->iface
->addrs
)
1503 if ((a
->prefix
.type
!= ospf_get_af(p
)) ||
1504 (a
->flags
& IA_SECONDARY
) ||
1505 (a
->flags
& IA_PEER
) ||
1506 (a
->scope
<= SCOPE_LINK
))
1509 if (((a
->prefix
.pxlen
< max
) && net_lsa
) ||
1510 configured_stubnet(oa
, a
))
1513 if ((a
->flags
& IA_HOST
) ||
1514 (ifa
->state
== OSPF_IS_LOOP
) ||
1515 (ifa
->type
== OSPF_IT_PTMP
))
1518 if (a
->prefix
.type
== NET_IP4
)
1519 net_fill_ip4(&net
, ipa_to_ip4(a
->ip
), IP4_MAX_PREFIX_LENGTH
);
1521 net_fill_ip6(&net
, ipa_to_ip6(a
->ip
), IP6_MAX_PREFIX_LENGTH
);
1523 lsab_put_prefix(p
, &net
, 0);
1527 lsab_put_prefix(p
, &a
->prefix
, ifa
->cost
);
1531 ifa
->px_pos_end
= i
;
1534 struct ospf_stubnet_config
*sn
;
1535 WALK_LIST(sn
, oa
->ac
->stubnet_list
)
1538 lsab_put_prefix(p
, &sn
->prefix
, sn
->cost
);
1539 if (sn
->prefix
.pxlen
== max
)
1544 /* If there are some configured vlinks, find some global address
1545 (even from another area), which will be used as a vlink endpoint. */
1546 if (!EMPTY_LIST(cf
->vlink_list
) && !host_addr
&& ospf_is_ip6(p
))
1548 WALK_LIST(ifa
, p
->iface_list
)
1550 if ((ifa
->type
== OSPF_IT_VLINK
) || (ifa
->state
== OSPF_IS_DOWN
))
1554 WALK_LIST(a
, ifa
->iface
->addrs
)
1556 if ((a
->prefix
.type
!= NET_IP6
) ||
1557 (a
->flags
& IA_SECONDARY
) ||
1558 (a
->scope
<= SCOPE_LINK
))
1562 net_addr_ip6 net
= NET_ADDR_IP6(a
->ip
, IP6_MAX_PREFIX_LENGTH
);
1563 lsab_put_prefix(p
, (net_addr
*) &net
, 0);
1576 ospf_originate_prefix_rt_lsa(struct ospf_proto
*p
, struct ospf_area
*oa
)
1581 struct ospf_new_lsa lsa
= {
1582 .type
= LSA_T_PREFIX
,
1587 prepare_prefix_rt_lsa_body(p
, oa
);
1589 ospf_originate_lsa(p
, &lsa
);
1594 * Prefix-Net-LSA handling (assume OSPFv3)
1595 * Type = LSA_T_PREFIX, referred type = LSA_T_NET
1599 prefix_space(u32
*buf
)
1601 int pxl
= *buf
>> 24;
1602 return IPV6_PREFIX_SPACE(pxl
);
1606 prefix_same(u32
*b1
, u32
*b2
)
1608 int pxl1
= *b1
>> 24;
1609 int pxl2
= *b2
>> 24;
1615 pxs
= IPV6_PREFIX_WORDS(pxl1
);
1616 for (i
= 1; i
< pxs
; i
++)
1624 prefix_advance(u32
*buf
)
1626 int pxl
= *buf
>> 24;
1627 return buf
+ IPV6_PREFIX_WORDS(pxl
);
1630 /* FIXME eliminate items with LA bit set? see 4.4.3.9 */
1632 add_prefix(struct ospf_proto
*p
, u32
*px
, int offset
, int *pxc
)
1634 u32
*pxl
= lsab_offset(p
, offset
);
1636 for (i
= 0; i
< *pxc
; pxl
= prefix_advance(pxl
), i
++)
1637 if (prefix_same(px
, pxl
))
1639 /* Options should be logically OR'ed together */
1640 *pxl
|= (*px
& 0x00FF0000);
1644 ASSERT(pxl
== lsab_end(p
));
1646 int pxspace
= prefix_space(px
);
1647 pxl
= lsab_alloc(p
, pxspace
);
1648 memcpy(pxl
, px
, pxspace
);
1649 *pxl
&= 0xFFFF0000; /* Set metric to zero */
1654 add_link_lsa(struct ospf_proto
*p
, struct ospf_lsa_link
*ll
, int offset
, int *pxc
)
1656 u32
*pxb
= ll
->rest
;
1659 for (j
= 0; j
< ll
->pxcount
; pxb
= prefix_advance(pxb
), j
++)
1661 u8 pxlen
= (pxb
[0] >> 24);
1662 u8 pxopts
= (pxb
[0] >> 16);
1664 /* Skip NU or LA prefixes */
1665 if (pxopts
& (OPT_PX_NU
| OPT_PX_LA
))
1668 /* Skip link-local prefixes */
1669 if (ospf_is_ip6(p
) && (pxlen
>= 10) && ((pxb
[1] & 0xffc00000) == 0xfe800000))
1672 add_prefix(p
, pxb
, offset
, pxc
);
1677 prepare_prefix_net_lsa_body(struct ospf_proto
*p
, struct ospf_iface
*ifa
)
1679 struct ospf_lsa_prefix
*lp
;
1680 struct ospf_neighbor
*n
;
1681 struct top_hash_entry
*en
;
1684 ASSERT(p
->lsab_used
== 0);
1685 lp
= lsab_allocz(p
, sizeof(struct ospf_lsa_prefix
));
1686 lp
->ref_type
= LSA_T_NET
;
1687 lp
->ref_id
= ifa
->net_lsa
->lsa
.id
;
1688 lp
->ref_rt
= p
->router_id
;
1689 lp
= NULL
; /* buffer might be reallocated later */
1692 offset
= p
->lsab_used
;
1694 /* Find all Link LSAs associated with the link and merge their prefixes */
1695 if (en
= ifa
->link_lsa
)
1696 add_link_lsa(p
, en
->next_lsa_body
?: en
->lsa_body
, offset
, &pxc
);
1698 WALK_LIST(n
, ifa
->neigh_list
)
1699 if ((n
->state
== NEIGHBOR_FULL
) &&
1700 (en
= ospf_hash_find(p
->gr
, ifa
->iface_id
, n
->iface_id
, n
->rid
, LSA_T_LINK
)))
1701 add_link_lsa(p
, en
->lsa_body
, offset
, &pxc
);
1708 ospf_originate_prefix_net_lsa(struct ospf_proto
*p
, struct ospf_iface
*ifa
)
1713 struct ospf_new_lsa lsa
= {
1714 .type
= LSA_T_PREFIX
,
1715 .dom
= ifa
->oa
->areaid
,
1716 .id
= ifa
->iface_id
,
1720 prepare_prefix_net_lsa_body(p
, ifa
);
1722 ifa
->pxn_lsa
= ospf_originate_lsa(p
, &lsa
);
1727 * Grace LSA handling
1728 * Type = LSA_T_GR, opaque type = LSA_OT_GR
1732 ospf_add_gr_period_tlv(struct ospf_proto
*p
, uint period
)
1734 struct ospf_tlv
*tlv
= lsab_allocz(p
, sizeof(struct ospf_tlv
) + sizeof(u32
));
1735 tlv
->type
= LSA_GR_PERIOD
;
1737 tlv
->data
[0] = period
;
1741 ospf_add_gr_reason_tlv(struct ospf_proto
*p
, uint reason
)
1743 struct ospf_tlv
*tlv
= lsab_allocz(p
, sizeof(struct ospf_tlv
) + sizeof(u32
));
1744 tlv
->type
= LSA_GR_REASON
;
1746 tlv
->data
[0] = reason
<< 24;
1750 ospf_add_gr_address_tlv(struct ospf_proto
*p
, ip4_addr addr
)
1752 struct ospf_tlv
*tlv
= lsab_allocz(p
, sizeof(struct ospf_tlv
) + sizeof(u32
));
1753 tlv
->type
= LSA_GR_ADDRESS
;
1755 tlv
->data
[0] = ip4_to_u32(addr
);
1759 ospf_originate_gr_lsa(struct ospf_proto
*p
, struct ospf_iface
*ifa
)
1761 struct ospf_new_lsa lsa
= {
1763 .dom
= ifa
->iface_id
,
1764 .id
= ospf_is_v2(p
) ? 0 : ifa
->iface_id
,
1768 ospf_add_gr_period_tlv(p
, p
->gr_time
);
1769 ospf_add_gr_reason_tlv(p
, 0);
1772 if (ospf_is_v2(p
) && ((t
== OSPF_IT_BCAST
) || (t
== OSPF_IT_NBMA
) || (t
== OSPF_IT_PTMP
)))
1773 ospf_add_gr_address_tlv(p
, ipa_to_ip4(ifa
->addr
->ip
));
1775 ospf_originate_lsa(p
, &lsa
);
1780 * Router Information LSA handling
1781 * Type = LSA_T_RI_AREA, opaque type = LSA_OT_RI
1785 ospf_add_ric_tlv(struct ospf_proto
*p
)
1787 struct ospf_tlv
*ri
= lsab_allocz(p
, sizeof(struct ospf_tlv
) + sizeof(u32
));
1788 ri
->type
= LSA_RI_RIC
;
1789 ri
->length
= sizeof(struct ospf_tlv
) + sizeof(u32
);
1791 BIT32R_SET(ri
->data
, LSA_RIC_STUB_ROUTER
);
1795 ospf_originate_ri_lsa(struct ospf_proto
*p
, struct ospf_area
*oa
)
1797 struct ospf_new_lsa lsa
= {
1798 .type
= LSA_T_RI_AREA
,
1800 .id
= p
->instance_id
1803 ospf_add_ric_tlv(p
);
1805 ospf_originate_lsa(p
, &lsa
);
1810 * Generic topology code
1813 static inline int breaks_minlsinterval(struct top_hash_entry
*en
)
1814 { return en
&& (en
->lsa
.age
< LSA_MAXAGE
) && (lsa_inst_age(en
) < MINLSINTERVAL
); }
1817 ospf_update_topology(struct ospf_proto
*p
)
1819 struct ospf_area
*oa
;
1820 struct ospf_iface
*ifa
;
1822 /* No LSA reorigination during GR recovery */
1826 WALK_LIST(oa
, p
->area_list
)
1828 if (oa
->update_rt_lsa
)
1831 * Generally, MinLSInterval is enforced in ospf_do_originate_lsa(), but
1832 * origination of (prefix) router LSA is a special case. We do not want to
1833 * prepare a new router LSA body and then postpone it in en->next_lsa_body
1834 * for later origination, because there are side effects (updates of
1835 * rt_pos_* and px_pos_* in ospf_iface structures) during that, which may
1836 * confuse routing table calculation if executed after LSA body
1837 * preparation but before final LSA origination (as rtcalc would use
1838 * current rt_pos_* indexes but the old router LSA body).
1840 * Here, we ensure that MinLSInterval is observed and we do not even try
1841 * to originate these LSAs if it is not. Therefore, origination, when
1842 * requested, will succeed unless there is also a seqnum wrapping, which
1843 * is not a problem because in that case rtcalc is blocked by MaxAge.
1846 if (breaks_minlsinterval(oa
->rt
) || breaks_minlsinterval(oa
->pxr_lsa
))
1849 ospf_originate_rt_lsa(p
, oa
);
1850 ospf_originate_prefix_rt_lsa(p
, oa
);
1851 // ospf_originate_ri_lsa(p, oa);
1852 oa
->update_rt_lsa
= 0;
1856 WALK_LIST(ifa
, p
->iface_list
)
1858 if (ifa
->type
== OSPF_IT_VLINK
)
1861 if (ifa
->update_link_lsa
)
1863 if ((ifa
->state
> OSPF_IS_LOOP
) && !ifa
->link_lsa_suppression
)
1864 ospf_originate_link_lsa(p
, ifa
);
1866 ospf_flush2_lsa(p
, &ifa
->link_lsa
);
1868 ifa
->update_link_lsa
= 0;
1871 if (ifa
->update_net_lsa
)
1873 if ((ifa
->state
== OSPF_IS_DR
) && (ifa
->fadj
> 0))
1875 ospf_originate_net_lsa(p
, ifa
);
1876 ospf_originate_prefix_net_lsa(p
, ifa
);
1880 ospf_flush2_lsa(p
, &ifa
->net_lsa
);
1881 ospf_flush2_lsa(p
, &ifa
->pxn_lsa
);
1884 ifa
->update_net_lsa
= 0;
1891 ospf_top_ht_alloc(struct top_graph
*f
)
1893 f
->hash_size
= 1 << f
->hash_order
;
1894 f
->hash_mask
= f
->hash_size
- 1;
1895 if (f
->hash_order
> HASH_HI_MAX
- HASH_HI_STEP
)
1896 f
->hash_entries_max
= ~0;
1898 f
->hash_entries_max
= f
->hash_size HASH_HI_MARK
;
1899 if (f
->hash_order
< HASH_LO_MIN
+ HASH_LO_STEP
)
1900 f
->hash_entries_min
= 0;
1902 f
->hash_entries_min
= f
->hash_size HASH_LO_MARK
;
1903 DBG("Allocating OSPF hash of order %d: %d hash_entries, %d low, %d high\n",
1904 f
->hash_order
, f
->hash_size
, f
->hash_entries_min
, f
->hash_entries_max
);
1906 mb_alloc(f
->pool
, f
->hash_size
* sizeof(struct top_hash_entry
*));
1907 bzero(f
->hash_table
, f
->hash_size
* sizeof(struct top_hash_entry
*));
1911 ospf_top_ht_free(struct top_hash_entry
**h
)
1917 ospf_top_hash_u32(u32 a
)
1919 /* Shamelessly stolen from IP address hashing in ipv4.h */
1926 ospf_top_hash(struct top_graph
*f
, u32 domain
, u32 lsaid
, u32 rtrid
, u32 type
)
1928 /* In OSPFv2, we don't know Router ID when looking for network LSAs.
1929 In OSPFv3, we don't know LSA ID when looking for router LSAs.
1930 In both cases, there is (usually) just one (or small number)
1931 appropriate LSA, so we just clear unknown part of key. */
1933 return (((f
->ospf2
&& (type
== LSA_T_NET
)) ? 0 : ospf_top_hash_u32(rtrid
)) +
1934 ((!f
->ospf2
&& (type
== LSA_T_RT
)) ? 0 : ospf_top_hash_u32(lsaid
)) +
1935 type
+ domain
) & f
->hash_mask
;
1938 return (ospf_top_hash_u32(lsaid) + ospf_top_hash_u32(rtrid) +
1939 type + areaid) & f->hash_mask;
1944 * ospf_top_new - allocated new topology database
1945 * @p: OSPF protocol instance
1946 * @pool: pool for allocation
1948 * This dynamically hashed structure is used for keeping LSAs. Mainly it is used
1949 * for the LSA database of the OSPF protocol, but also for LSA retransmission
1950 * and request lists of OSPF neighbors.
1953 ospf_top_new(struct ospf_proto
*p
, pool
*pool
)
1955 struct top_graph
*f
;
1957 f
= mb_allocz(pool
, sizeof(struct top_graph
));
1959 f
->hash_slab
= sl_new(f
->pool
, sizeof(struct top_hash_entry
));
1960 f
->hash_order
= HASH_DEF_ORDER
;
1961 ospf_top_ht_alloc(f
);
1962 f
->hash_entries
= 0;
1963 f
->hash_entries_min
= 0;
1964 f
->ospf2
= ospf_is_v2(p
);
1969 ospf_top_free(struct top_graph
*f
)
1971 rfree(f
->hash_slab
);
1972 ospf_top_ht_free(f
->hash_table
);
1977 ospf_top_rehash(struct top_graph
*f
, int step
)
1979 struct top_hash_entry
**n
, **oldt
, **newt
, *e
, *x
;
1982 oldn
= f
->hash_size
;
1983 oldt
= f
->hash_table
;
1984 DBG("re-hashing topology hash from order %d to %d\n", f
->hash_order
,
1985 f
->hash_order
+ step
);
1986 f
->hash_order
+= step
;
1987 ospf_top_ht_alloc(f
);
1988 newt
= f
->hash_table
;
1990 for (oldh
= 0; oldh
< oldn
; oldh
++)
1996 n
= newt
+ ospf_top_hash(f
, e
->domain
, e
->lsa
.id
, e
->lsa
.rt
, e
->lsa_type
);
2002 ospf_top_ht_free(oldt
);
2005 static struct top_hash_entry
*
2006 ospf_hash_find_(struct top_graph
*f
, u32 domain
, u32 lsa
, u32 rtr
, u32 type
)
2008 struct top_hash_entry
*e
;
2009 e
= f
->hash_table
[ospf_top_hash(f
, domain
, lsa
, rtr
, type
)];
2011 while (e
&& (e
->lsa
.id
!= lsa
|| e
->lsa
.rt
!= rtr
||
2012 e
->lsa_type
!= type
|| e
->domain
!= domain
))
2018 struct top_hash_entry
*
2019 ospf_hash_find(struct top_graph
*f
, u32 domain
, u32 lsa
, u32 rtr
, u32 type
)
2021 struct top_hash_entry
*e
= ospf_hash_find_(f
, domain
, lsa
, rtr
, type
);
2023 /* Hide hash entry with empty lsa_body */
2024 return (e
&& e
->lsa_body
) ? e
: NULL
;
2027 /* In OSPFv2, lsa.id is the same as lsa.rt for router LSA. In OSPFv3, we don't know
2028 lsa.id when looking for router LSAs. We return matching LSA with smallest lsa.id. */
2029 struct top_hash_entry
*
2030 ospf_hash_find_rt(struct top_graph
*f
, u32 domain
, u32 rtr
)
2032 struct top_hash_entry
*rv
= NULL
;
2033 struct top_hash_entry
*e
;
2034 /* We can put rtr for lsa.id to hash fn, it is ignored in OSPFv3 */
2035 e
= f
->hash_table
[ospf_top_hash(f
, domain
, rtr
, rtr
, LSA_T_RT
)];
2039 if (e
->lsa
.rt
== rtr
&& e
->lsa_type
== LSA_T_RT
&& e
->domain
== domain
&& e
->lsa_body
)
2041 if (f
->ospf2
&& (e
->lsa
.id
== rtr
))
2043 if (!f
->ospf2
&& (!rv
|| e
->lsa
.id
< rv
->lsa
.id
))
2053 * ospf_hash_find_rt3_first() and ospf_hash_find_rt3_next() are used exclusively
2054 * for lsa_walk_rt_init(), lsa_walk_rt(), therefore they skip MaxAge entries.
2056 static inline struct top_hash_entry
*
2057 find_matching_rt3(struct top_hash_entry
*e
, u32 domain
, u32 rtr
)
2059 while (e
&& (e
->lsa
.rt
!= rtr
|| e
->lsa_type
!= LSA_T_RT
||
2060 e
->domain
!= domain
|| e
->lsa
.age
== LSA_MAXAGE
))
2065 struct top_hash_entry
*
2066 ospf_hash_find_rt3_first(struct top_graph
*f
, u32 domain
, u32 rtr
)
2068 struct top_hash_entry
*e
;
2069 e
= f
->hash_table
[ospf_top_hash(f
, domain
, 0, rtr
, LSA_T_RT
)];
2070 return find_matching_rt3(e
, domain
, rtr
);
2073 struct top_hash_entry
*
2074 ospf_hash_find_rt3_next(struct top_hash_entry
*e
)
2076 return find_matching_rt3(e
->next
, e
->domain
, e
->lsa
.rt
);
2079 /* In OSPFv2, we don't know Router ID when looking for network LSAs.
2080 There should be just one, so we find any match. */
2081 struct top_hash_entry
*
2082 ospf_hash_find_net2(struct top_graph
*f
, u32 domain
, u32 id
)
2084 struct top_hash_entry
*e
;
2085 e
= f
->hash_table
[ospf_top_hash(f
, domain
, id
, 0, LSA_T_NET
)];
2087 while (e
&& (e
->lsa
.id
!= id
|| e
->lsa_type
!= LSA_T_NET
||
2088 e
->domain
!= domain
|| e
->lsa_body
== NULL
))
2095 struct top_hash_entry
*
2096 ospf_hash_get(struct top_graph
*f
, u32 domain
, u32 lsa
, u32 rtr
, u32 type
)
2098 struct top_hash_entry
**ee
;
2099 struct top_hash_entry
*e
;
2101 ee
= f
->hash_table
+ ospf_top_hash(f
, domain
, lsa
, rtr
, type
);
2104 while (e
&& (e
->lsa
.id
!= lsa
|| e
->lsa
.rt
!= rtr
||
2105 e
->lsa_type
!= type
|| e
->domain
!= domain
))
2111 e
= sl_alloc(f
->hash_slab
);
2112 bzero(e
, sizeof(struct top_hash_entry
));
2115 e
->dist
= LSINFINITY
;
2116 e
->lsa
.type_raw
= type
;
2119 e
->lsa
.sn
= LSA_ZEROSEQNO
;
2124 if (f
->hash_entries
++ > f
->hash_entries_max
)
2125 ospf_top_rehash(f
, HASH_HI_STEP
);
2130 ospf_hash_delete(struct top_graph
*f
, struct top_hash_entry
*e
)
2132 struct top_hash_entry
**ee
= f
->hash_table
+
2133 ospf_top_hash(f
, e
->domain
, e
->lsa
.id
, e
->lsa
.rt
, e
->lsa_type
);
2140 sl_free(f
->hash_slab
, e
);
2141 if (f
->hash_entries
-- < f
->hash_entries_min
)
2142 ospf_top_rehash(f
, -HASH_LO_STEP
);
2145 ee
= &((*ee
)->next
);
2147 bug("ospf_hash_delete() called for invalid node");
2152 ospf_dump_lsa(struct top_hash_entry *he, struct proto *p)
2155 struct ospf_lsa_rt *rt = NULL;
2156 struct ospf_lsa_rt_link *rr = NULL;
2157 struct ospf_lsa_net *ln = NULL;
2161 OSPF_TRACE(D_EVENTS, "- %1x %-1R %-1R %4u 0x%08x 0x%04x %-1R",
2162 he->lsa.type, he->lsa.id, he->lsa.rt, he->lsa.age, he->lsa.sn,
2163 he->lsa.checksum, he->domain);
2166 switch (he->lsa.type)
2170 rr = (struct ospf_lsa_rt_link *) (rt + 1);
2172 for (i = 0; i < lsa_rt_items(&he->lsa); i++)
2173 OSPF_TRACE(D_EVENTS, " - %1x %-1R %-1R %5u",
2174 rr[i].type, rr[i].id, rr[i].data, rr[i].metric);
2179 rts = (u32 *) (ln + 1);
2181 for (i = 0; i < lsa_net_items(&he->lsa); i++)
2182 OSPF_TRACE(D_EVENTS, " - %-1R", rts[i]);
2191 ospf_top_dump(struct top_graph *f, struct proto *p)
2194 OSPF_TRACE(D_EVENTS, "Hash entries: %d", f->hash_entries);
2196 for (i = 0; i < f->hash_size; i++)
2198 struct top_hash_entry *e;
2199 for (e = f->hash_table[i]; e != NULL; e = e->next)
2200 ospf_dump_lsa(e, p);