]>
git.ipfire.org Git - thirdparty/bird.git/blob - proto/ospf/topology.c
03b773499d9383ea75873d9f26ced2a5012ea530
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();
76 * We do not set en->mode. It is either default LSA_M_BASIC, or in a special
77 * case when en is local but flushed, there is postponed LSA, self-originated
78 * LSA is received and ospf_install_lsa() is called from ospf_advance_lse(),
79 * then we have en->mode from the postponed LSA origination.
82 OSPF_TRACE(D_EVENTS
, "Installing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x, Age: %u",
83 en
->lsa_type
, en
->lsa
.id
, en
->lsa
.rt
, en
->lsa
.sn
, en
->lsa
.age
);
86 ospf_schedule_rtcalc(p
);
92 * ospf_advance_lsa - handle received unexpected self-originated LSA
93 * @p: OSPF protocol instance
94 * @en: current LSA entry or NULL
95 * @lsa: new LSA header
97 * @domain: domain of LSA
98 * @body: pointer to LSA body
100 * This function handles received unexpected self-originated LSA (@lsa, @body)
101 * by either advancing sequence number of the local LSA instance (@en) and
102 * propagating it, or installing the received LSA and immediately flushing it
103 * (if there is no local LSA; i.e., @en is NULL or MaxAge).
105 * The LSA body in @body is expected to be mb_allocated by the caller and its
106 * ownership is transferred to the LSA entry structure or it is freed.
109 ospf_advance_lsa(struct ospf_proto
*p
, struct top_hash_entry
*en
, struct ospf_lsa_header
*lsa
, u32 type
, u32 domain
, void *body
)
113 if (en
&& (en
->lsa
.age
< LSA_MAXAGE
))
115 if (lsa
->sn
!= LSA_MAXSEQNO
)
118 * We simply advance current LSA to have higher seqnum than received LSA.
119 * The received LSA is ignored and the advanced LSA is propagated instead.
121 * Although this is an origination of distinct LSA instance and therefore
122 * should be limited by MinLSInterval, we do not enforce it here. Fast
123 * reaction is needed and we are already limited by MinLSArrival.
128 en
->lsa
.sn
= lsa
->sn
+ 1;
131 en
->inst_time
= current_time();
132 lsa_generate_checksum(&en
->lsa
, en
->lsa_body
);
134 OSPF_TRACE(D_EVENTS
, "Advancing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
135 en
->lsa_type
, en
->lsa
.id
, en
->lsa
.rt
, en
->lsa
.sn
);
140 * Received LSA has maximal sequence number, so we cannot simply override
141 * it. We have to install it to the database, immediately flush it to
142 * implement sequence number wrapping, and schedule our current LSA to be
143 * originated after the received instance is flushed.
146 if (en
->next_lsa_body
== NULL
)
148 /* Schedule current LSA */
149 en
->next_lsa_blen
= en
->lsa
.length
- sizeof(struct ospf_lsa_header
);
150 en
->next_lsa_body
= en
->lsa_body
;
151 en
->next_lsa_opts
= ospf_is_v2(p
) ? lsa_get_options(&en
->lsa
) : 0;
155 /* There is already scheduled LSA, so we just free current one */
156 mb_free(en
->lsa_body
);
161 en
->lsa
.age
= LSA_MAXAGE
;
162 en
->init_age
= lsa
->age
;
163 en
->inst_time
= current_time();
165 OSPF_TRACE(D_EVENTS
, "Resetting LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
166 en
->lsa_type
, en
->lsa
.id
, en
->lsa
.rt
, en
->lsa
.sn
);
167 OSPF_TRACE(D_EVENTS
, "Postponing LSA: Type: %04x, Id: %R, Rt: %R",
168 en
->lsa_type
, en
->lsa
.id
, en
->lsa
.rt
);
174 * We do not have received LSA in the database. We have to flush the
175 * received LSA. It has to be installed in the database to secure
176 * retransmissions. Note that the received LSA may already be MaxAge.
177 * Also note that en->next_lsa_* may be defined.
180 lsa
->age
= LSA_MAXAGE
;
181 en
= ospf_install_lsa(p
, lsa
, type
, domain
, body
);
185 * We flood the updated LSA. Although in some cases the to-be-flooded LSA is
186 * the same as the received LSA, and therefore we should propagate it as
187 * regular received LSA (send the acknowledgement instead of the update to
188 * the neighbor we received it from), we cheat a bit here.
191 ospf_flood_lsa(p
, en
, NULL
);
196 ospf_do_originate_lsa(struct ospf_proto
*p
, struct top_hash_entry
*en
, void *lsa_body
, u16 lsa_blen
, u16 lsa_opts
)
198 /* Enforce MinLSInterval */
199 if (!en
->init_age
&& en
->inst_time
&& (lsa_inst_age(en
) < MINLSINTERVAL
))
202 /* Handle wrapping sequence number */
203 if (en
->lsa
.sn
== LSA_MAXSEQNO
)
205 /* Prepare to flush old LSA */
206 if (en
->lsa
.age
!= LSA_MAXAGE
)
208 OSPF_TRACE(D_EVENTS
, "Resetting LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
209 en
->lsa_type
, en
->lsa
.id
, en
->lsa
.rt
, en
->lsa
.sn
);
211 en
->lsa
.age
= LSA_MAXAGE
;
212 ospf_flood_lsa(p
, en
, NULL
);
216 /* Already flushing */
217 if ((p
->padj
!= 0) || (en
->ret_count
!= 0))
220 /* Flush done, just clean up seqnum, lsa_body is freed below */
221 en
->lsa
.sn
= LSA_ZEROSEQNO
;
225 * lsa.type_raw is initialized by ospf_hash_get() to OSPFv3 LSA type.
226 * lsa_set_options() implicitly converts it to OSPFv2 LSA type, assuming that
227 * old type is just new type masked by 0xff. That is not universally true,
228 * but it holds for all OSPFv2 types currently supported by BIRD.
232 lsa_set_options(&en
->lsa
, lsa_opts
);
234 mb_free(en
->lsa_body
);
235 en
->lsa_body
= lsa_body
;
236 en
->lsa
.length
= sizeof(struct ospf_lsa_header
) + lsa_blen
;
240 en
->inst_time
= current_time();
241 lsa_generate_checksum(&en
->lsa
, en
->lsa_body
);
243 OSPF_TRACE(D_EVENTS
, "Originating LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
244 en
->lsa_type
, en
->lsa
.id
, en
->lsa
.rt
, en
->lsa
.sn
);
246 ospf_flood_lsa(p
, en
, NULL
);
248 if (en
->mode
== LSA_M_BASIC
)
249 ospf_schedule_rtcalc(p
);
255 * ospf_originate_lsa - originate new LSA
256 * @p: OSPF protocol instance
257 * @lsa: New LSA specification
259 * This function prepares a new LSA, installs it into the LSA database and
260 * floods it. If the new LSA cannot be originated now (because the old instance
261 * was originated within MinLSInterval, or because the LSA seqnum is currently
262 * wrapping), the origination is instead scheduled for later. If the new LSA is
263 * equivalent to the current LSA, the origination is skipped. In all cases, the
264 * corresponding LSA entry is returned. The new LSA is based on the LSA
265 * specification (@lsa) and the LSA body from lsab buffer of @p, which is
266 * emptied after the call. The opposite of this function is ospf_flush_lsa().
268 struct top_hash_entry
*
269 ospf_originate_lsa(struct ospf_proto
*p
, struct ospf_new_lsa
*lsa
)
271 struct top_hash_entry
*en
;
272 void *lsa_body
= p
->lsab
;
273 u16 lsa_blen
= p
->lsab_used
;
274 u16 lsa_length
= sizeof(struct ospf_lsa_header
) + lsa_blen
;
276 en
= ospf_hash_get(p
->gr
, lsa
->dom
, lsa
->id
, p
->router_id
, lsa
->type
);
278 if (!SNODE_VALID(en
))
279 s_add_tail(&p
->lsal
, SNODE en
);
281 if (!en
->nf
|| !en
->lsa_body
)
284 if (en
->nf
!= lsa
->nf
)
286 log(L_ERR
"%s: LSA ID collision for %N",
287 p
->p
.name
, lsa
->nf
->fn
.addr
);
293 if (en
->mode
!= lsa
->mode
)
294 en
->mode
= lsa
->mode
;
296 if (en
->next_lsa_body
)
298 /* Ignore the new LSA if it is the same as the scheduled one */
299 if ((lsa_blen
== en
->next_lsa_blen
) &&
300 !memcmp(lsa_body
, en
->next_lsa_body
, lsa_blen
) &&
301 (!ospf_is_v2(p
) || (lsa
->opts
== en
->next_lsa_opts
)))
304 /* Free scheduled LSA */
305 mb_free(en
->next_lsa_body
);
306 en
->next_lsa_body
= NULL
;
307 en
->next_lsa_blen
= 0;
308 en
->next_lsa_opts
= 0;
311 /* Ignore the the new LSA if is the same as the current one */
312 if ((en
->lsa
.age
< LSA_MAXAGE
) &&
313 (lsa_length
== en
->lsa
.length
) &&
314 !memcmp(lsa_body
, en
->lsa_body
, lsa_blen
) &&
315 (!ospf_is_v2(p
) || (lsa
->opts
== lsa_get_options(&en
->lsa
))))
318 lsa_body
= lsab_flush(p
);
320 if (! ospf_do_originate_lsa(p
, en
, lsa_body
, lsa_blen
, lsa
->opts
))
322 OSPF_TRACE(D_EVENTS
, "Postponing LSA: Type: %04x, Id: %R, Rt: %R",
323 en
->lsa_type
, en
->lsa
.id
, en
->lsa
.rt
);
325 en
->next_lsa_body
= lsa_body
;
326 en
->next_lsa_blen
= lsa_blen
;
327 en
->next_lsa_opts
= lsa
->opts
;
338 ospf_originate_next_lsa(struct ospf_proto
*p
, struct top_hash_entry
*en
)
340 /* Called by ospf_update_lsadb() to handle scheduled origination */
342 if (! ospf_do_originate_lsa(p
, en
, en
->next_lsa_body
, en
->next_lsa_blen
, en
->next_lsa_opts
))
345 en
->next_lsa_body
= NULL
;
346 en
->next_lsa_blen
= 0;
347 en
->next_lsa_opts
= 0;
351 ospf_refresh_lsa(struct ospf_proto
*p
, struct top_hash_entry
*en
)
354 * Called by ospf_update_lsadb() for periodic LSA refresh.
356 * We know that lsa.age < LSA_MAXAGE and lsa.rt is our router ID. We can also
357 * assume that there is no scheduled LSA, because inst_time is deep in past,
358 * therefore ospf_originate_next_lsa() called before would either succeed or
359 * switched lsa.age to LSA_MAXAGE.
362 OSPF_TRACE(D_EVENTS
, "Refreshing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
363 en
->lsa_type
, en
->lsa
.id
, en
->lsa
.rt
, en
->lsa
.sn
);
365 ASSERT(en
->next_lsa_body
== NULL
);
367 /* Handle wrapping sequence number */
368 if (en
->lsa
.sn
== LSA_MAXSEQNO
)
370 /* Copy LSA body as next LSA to get automatic origination after flush is finished */
371 en
->next_lsa_blen
= en
->lsa
.length
- sizeof(struct ospf_lsa_header
);
372 en
->next_lsa_body
= mb_alloc(p
->p
.pool
, en
->next_lsa_blen
);
373 memcpy(en
->next_lsa_body
, en
->lsa_body
, en
->next_lsa_blen
);
374 en
->next_lsa_opts
= ospf_is_v2(p
) ? lsa_get_options(&en
->lsa
) : 0;
376 en
->lsa
.age
= LSA_MAXAGE
;
377 ospf_flood_lsa(p
, en
, NULL
);
384 en
->inst_time
= current_time();
385 lsa_generate_checksum(&en
->lsa
, en
->lsa_body
);
386 ospf_flood_lsa(p
, en
, NULL
);
390 * ospf_flush_lsa - flush LSA from OSPF domain
391 * @p: OSPF protocol instance
392 * @en: LSA entry to flush
394 * This function flushes @en from the OSPF domain by setting its age to
395 * %LSA_MAXAGE and flooding it. That also triggers subsequent events in LSA
396 * lifecycle leading to removal of the LSA from the LSA database (e.g. the LSA
397 * content is freed when flushing is acknowledged by neighbors). The function
398 * does nothing if the LSA is already being flushed. LSA entries are not
399 * immediately removed when being flushed, the caller may assume that @en still
400 * exists after the call. The function is the opposite of ospf_originate_lsa()
401 * and is supposed to do the right thing even in cases of postponed
405 ospf_flush_lsa(struct ospf_proto
*p
, struct top_hash_entry
*en
)
407 if (en
->next_lsa_body
)
409 mb_free(en
->next_lsa_body
);
410 en
->next_lsa_body
= NULL
;
411 en
->next_lsa_blen
= 0;
412 en
->next_lsa_opts
= 0;
415 if (en
->lsa
.age
== LSA_MAXAGE
)
418 OSPF_TRACE(D_EVENTS
, "Flushing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
419 en
->lsa_type
, en
->lsa
.id
, en
->lsa
.rt
, en
->lsa
.sn
);
421 en
->lsa
.age
= LSA_MAXAGE
;
422 ospf_flood_lsa(p
, en
, NULL
);
424 if (en
->mode
== LSA_M_BASIC
)
425 ospf_schedule_rtcalc(p
);
427 en
->mode
= LSA_M_BASIC
;
431 ospf_clear_lsa(struct ospf_proto
*p
, struct top_hash_entry
*en
)
434 * Called by ospf_update_lsadb() as part of LSA flushing process.
435 * Flushed LSA was acknowledged by neighbors and we can free its content.
436 * The log message is for 'remove' - we hide empty LSAs from users.
439 OSPF_TRACE(D_EVENTS
, "Removing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
440 en
->lsa_type
, en
->lsa
.id
, en
->lsa
.rt
, en
->lsa
.sn
);
442 if (en
->lsa
.sn
== LSA_MAXSEQNO
)
443 en
->lsa
.sn
= LSA_ZEROSEQNO
;
445 mb_free(en
->lsa_body
);
450 ospf_remove_lsa(struct ospf_proto
*p
, struct top_hash_entry
*en
)
453 * Called by ospf_update_lsadb() as part of LSA flushing process.
454 * Both lsa_body and next_lsa_body are NULL.
457 s_rem_node(SNODE en
);
458 ospf_hash_delete(p
->gr
, en
);
462 * ospf_update_lsadb - update LSA database
463 * @p: OSPF protocol instance
465 * This function is periodicaly invoked from ospf_disp(). It does some periodic
466 * or postponed processing related to LSA entries. It originates postponed LSAs
467 * scheduled by ospf_originate_lsa(), It continues in flushing processes started
468 * by ospf_flush_lsa(). It also periodically refreshs locally originated LSAs --
469 * when the current instance is older %LSREFRESHTIME, a new instance is originated.
470 * Finally, it also ages stored LSAs and flushes ones that reached %LSA_MAXAGE.
472 * The RFC 2328 says that a router should periodically check checksums of all
473 * stored LSAs to detect hardware problems. This is not implemented.
476 ospf_update_lsadb(struct ospf_proto
*p
)
478 struct top_hash_entry
*en
, *nxt
;
479 btime now_
= current_time();
482 WALK_SLIST_DELSAFE(en
, nxt
, p
->lsal
)
484 if (en
->next_lsa_body
)
485 ospf_originate_next_lsa(p
, en
);
487 real_age
= en
->init_age
+ (now_
- en
->inst_time
) TO_S
;
489 if (en
->lsa
.age
== LSA_MAXAGE
)
491 if (en
->lsa_body
&& (p
->padj
== 0) && (en
->ret_count
== 0))
492 ospf_clear_lsa(p
, en
);
494 if ((en
->lsa_body
== NULL
) && (en
->next_lsa_body
== NULL
) &&
495 ((en
->lsa
.rt
!= p
->router_id
) || (real_age
>= LSA_MAXAGE
)))
496 ospf_remove_lsa(p
, en
);
501 if ((en
->lsa
.rt
== p
->router_id
) && (real_age
>= LSREFRESHTIME
))
503 ospf_refresh_lsa(p
, en
);
507 if (real_age
>= LSA_MAXAGE
)
509 ospf_flush_lsa(p
, en
);
513 en
->lsa
.age
= real_age
;
519 ort_to_lsaid(struct ospf_proto
*p
, ort
*nf
)
522 * In OSPFv2, We have to map IP prefixes to u32 in such manner that resulting
523 * u32 interpreted as IP address is a member of given prefix. Therefore, /32
524 * prefix has to be mapped on itself. All received prefixes have to be mapped
527 * We have an assumption that if there is nontrivial (non-/32) network prefix,
528 * then there is not /32 prefix for the first and the last IP address of the
529 * network (these are usually reserved, therefore it is not an important
530 * restriction). The network prefix is mapped to the first or the last IP
531 * address in the manner that disallow collisions - we use the IP address that
532 * cannot be used by the parent prefix.
535 * 192.168.0.0/24 maps to 192.168.0.255
536 * 192.168.1.0/24 maps to 192.168.1.0
537 * because 192.168.0.0 and 192.168.1.255 might be used by 192.168.0.0/23 .
539 * Appendig E of RFC 2328 suggests different algorithm, that tries to maximize
540 * both compatibility and subnetting. But as it is not possible to have both
541 * reliably and the suggested algorithm was unnecessary complicated and it
542 * does crazy things like changing LSA ID for a network because different
543 * network appeared, we choose a different way.
545 * In OSPFv3, it is simpler. There is not a requirement for membership of the
546 * result in the input network, so we just allocate a unique ID from ID map
547 * and store it in nf->lsa_id for further reference.
553 nf
->lsa_id
= idm_alloc(&p
->idm
);
558 net_addr_ip4
*net
= (void *) nf
->fn
.addr
;
559 u32 id
= ip4_to_u32(net
->prefix
);
560 int pxlen
= net
->pxlen
;
562 if ((pxlen
== 0) || (pxlen
== 32))
565 if (id
& (1 << (32 - pxlen
)))
568 return id
| ~u32_mkmask(pxlen
);
573 lsab_alloc(struct ospf_proto
*p
, uint size
)
575 uint offset
= p
->lsab_used
;
576 p
->lsab_used
+= size
;
577 if (p
->lsab_used
> p
->lsab_size
)
579 p
->lsab_size
= MAX(p
->lsab_used
, 2 * p
->lsab_size
);
580 p
->lsab
= p
->lsab
? mb_realloc(p
->lsab
, p
->lsab_size
):
581 mb_alloc(p
->p
.pool
, p
->lsab_size
);
583 return ((byte
*) p
->lsab
) + offset
;
587 lsab_allocz(struct ospf_proto
*p
, uint size
)
589 void *r
= lsab_alloc(p
, size
);
595 lsab_flush(struct ospf_proto
*p
)
597 void *r
= mb_alloc(p
->p
.pool
, p
->lsab_used
);
598 memcpy(r
, p
->lsab
, p
->lsab_used
);
604 lsab_reset(struct ospf_proto
*p
)
610 lsab_offset(struct ospf_proto
*p
, uint offset
)
612 return ((byte
*) p
->lsab
) + offset
;
615 static inline void * UNUSED
616 lsab_end(struct ospf_proto
*p
)
618 return ((byte
*) p
->lsab
) + p
->lsab_used
;
623 * Router-LSA handling
628 configured_stubnet(struct ospf_area
*oa
, struct ifa
*a
)
630 /* Does not work for IA_PEER addresses, but it is not called on these */
631 struct ospf_stubnet_config
*sn
;
632 WALK_LIST(sn
, oa
->ac
->stubnet_list
)
636 if (net_in_netX(&a
->prefix
, &sn
->prefix
))
641 if (net_equal(&a
->prefix
, &sn
->prefix
))
650 bcast_net_active(struct ospf_iface
*ifa
)
652 struct ospf_neighbor
*neigh
;
654 if (ifa
->state
== OSPF_IS_WAITING
)
657 WALK_LIST(neigh
, ifa
->neigh_list
)
659 if (neigh
->state
== NEIGHBOR_FULL
)
661 if (neigh
->rid
== ifa
->drid
)
664 if (ifa
->state
== OSPF_IS_DR
)
673 get_rt_options(struct ospf_proto
*p
, struct ospf_area
*oa
, int bitv
)
680 if ((p
->areano
> 1) && oa_is_nssa(oa
) && oa
->ac
->translator
)
683 if (p
->asbr
&& !oa_is_stub(oa
))
693 add_rt2_lsa_link(struct ospf_proto
*p
, u8 type
, u32 id
, u32 data
, u16 metric
)
695 struct ospf_lsa_rt2_link
*ln
= lsab_alloc(p
, sizeof(struct ospf_lsa_rt2_link
));
704 prepare_rt2_lsa_body(struct ospf_proto
*p
, struct ospf_area
*oa
)
706 struct ospf_iface
*ifa
;
708 struct ospf_neighbor
*neigh
;
710 ASSERT(p
->lsab_used
== 0);
711 lsab_allocz(p
, sizeof(struct ospf_lsa_rt
));
712 /* ospf_lsa_rt header will be filled later */
714 WALK_LIST(ifa
, p
->iface_list
)
717 u32 link_cost
= p
->stub_router
? 0xffff : ifa
->cost
;
719 if ((ifa
->type
== OSPF_IT_VLINK
) && (ifa
->voa
== oa
) &&
720 (!EMPTY_LIST(ifa
->neigh_list
)))
722 neigh
= (struct ospf_neighbor
*) HEAD(ifa
->neigh_list
);
723 if ((neigh
->state
== NEIGHBOR_FULL
) && (ifa
->cost
<= 0xffff))
727 if ((ifa
->oa
!= oa
) || (ifa
->state
== OSPF_IS_DOWN
))
732 /* RFC 2328 - 12.4.1.1-4 */
737 WALK_LIST(neigh
, ifa
->neigh_list
)
738 if (neigh
->state
== NEIGHBOR_FULL
)
741 * ln->data should be ifa->iface_id in case of no/ptp
742 * address (ifa->addr->flags & IA_PEER) on PTP link (see
743 * RFC 2328 12.4.1.1.), but the iface ID value has no use,
744 * while using IP address even in this case is here for
745 * compatibility with some broken implementations that use
746 * this address as a next-hop.
748 add_rt2_lsa_link(p
, LSART_PTP
, neigh
->rid
, ipa_to_u32(ifa
->addr
->ip
), link_cost
);
755 if (bcast_net_active(ifa
))
757 add_rt2_lsa_link(p
, LSART_NET
, ipa_to_u32(ifa
->drip
), ipa_to_u32(ifa
->addr
->ip
), link_cost
);
764 neigh
= (struct ospf_neighbor
*) HEAD(ifa
->neigh_list
);
765 if ((!EMPTY_LIST(ifa
->neigh_list
)) && (neigh
->state
== NEIGHBOR_FULL
) && (ifa
->cost
<= 0xffff))
766 add_rt2_lsa_link(p
, LSART_VLNK
, neigh
->rid
, ipa_to_u32(ifa
->addr
->ip
), link_cost
), i
++;
770 log(L_BUG
"OSPF: Unknown interface type");
776 /* Now we will originate stub area if there is no primary */
778 (ifa
->type
== OSPF_IT_VLINK
) ||
779 ((ifa
->addr
->flags
& IA_PEER
) && ! ifa
->cf
->stub
) ||
780 configured_stubnet(oa
, ifa
->addr
))
783 /* Host or network stub entry */
784 if ((ifa
->addr
->flags
& IA_HOST
) ||
785 (ifa
->state
== OSPF_IS_LOOP
) ||
786 (ifa
->type
== OSPF_IT_PTMP
))
787 add_rt2_lsa_link(p
, LSART_STUB
, ipa_to_u32(ifa
->addr
->ip
), 0xffffffff, 0);
789 add_rt2_lsa_link(p
, LSART_STUB
, ip4_to_u32(net4_prefix(&ifa
->addr
->prefix
)),
790 u32_mkmask(net4_pxlen(&ifa
->addr
->prefix
)), ifa
->cost
);
796 struct ospf_stubnet_config
*sn
;
797 WALK_LIST(sn
, oa
->ac
->stubnet_list
)
799 add_rt2_lsa_link(p
, LSART_STUB
, ip4_to_u32(net4_prefix(&sn
->prefix
)),
800 u32_mkmask(net4_pxlen(&sn
->prefix
)), sn
->cost
), i
++;
802 struct ospf_lsa_rt
*rt
= p
->lsab
;
803 /* Store number of links in lower half of options */
804 rt
->options
= get_rt_options(p
, oa
, bitv
) | (u16
) i
;
808 add_rt3_lsa_link(struct ospf_proto
*p
, u8 type
, struct ospf_iface
*ifa
, u32 nif
, u32 id
)
810 struct ospf_lsa_rt3_link
*ln
= lsab_alloc(p
, sizeof(struct ospf_lsa_rt3_link
));
813 ln
->metric
= ifa
->cost
;
814 ln
->lif
= ifa
->iface_id
;
820 prepare_rt3_lsa_body(struct ospf_proto
*p
, struct ospf_area
*oa
)
822 struct ospf_iface
*ifa
;
823 struct ospf_neighbor
*neigh
;
827 ASSERT(p
->lsab_used
== 0);
828 lsab_allocz(p
, sizeof(struct ospf_lsa_rt
));
829 /* ospf_lsa_rt header will be filled later */
831 WALK_LIST(ifa
, p
->iface_list
)
833 if ((ifa
->type
== OSPF_IT_VLINK
) && (ifa
->voa
== oa
) &&
834 (!EMPTY_LIST(ifa
->neigh_list
)))
836 neigh
= (struct ospf_neighbor
*) HEAD(ifa
->neigh_list
);
837 if ((neigh
->state
== NEIGHBOR_FULL
) && (ifa
->cost
<= 0xffff))
841 if ((ifa
->oa
!= oa
) || (ifa
->state
== OSPF_IS_DOWN
))
846 /* RFC 5340 - 4.4.3.2 */
851 WALK_LIST(neigh
, ifa
->neigh_list
)
852 if (neigh
->state
== NEIGHBOR_FULL
)
853 add_rt3_lsa_link(p
, LSART_PTP
, ifa
, neigh
->iface_id
, neigh
->rid
), i
++;
858 if (bcast_net_active(ifa
))
859 add_rt3_lsa_link(p
, LSART_NET
, ifa
, ifa
->dr_iface_id
, ifa
->drid
), i
++;
863 neigh
= (struct ospf_neighbor
*) HEAD(ifa
->neigh_list
);
864 if ((!EMPTY_LIST(ifa
->neigh_list
)) && (neigh
->state
== NEIGHBOR_FULL
) && (ifa
->cost
<= 0xffff))
865 add_rt3_lsa_link(p
, LSART_VLNK
, ifa
, neigh
->iface_id
, neigh
->rid
), i
++;
869 log(L_BUG
"OSPF: Unknown interface type");
876 struct ospf_lsa_rt
*rt
= p
->lsab
;
877 rt
->options
= get_rt_options(p
, oa
, bitv
) | (oa
->options
& LSA_OPTIONS_MASK
);
881 ospf_originate_rt_lsa(struct ospf_proto
*p
, struct ospf_area
*oa
)
883 struct ospf_new_lsa lsa
= {
886 .id
= ospf_is_v2(p
) ? p
->router_id
: 0,
890 OSPF_TRACE(D_EVENTS
, "Updating router state for area %R", oa
->areaid
);
893 prepare_rt2_lsa_body(p
, oa
);
895 prepare_rt3_lsa_body(p
, oa
);
897 oa
->rt
= ospf_originate_lsa(p
, &lsa
);
907 prepare_net2_lsa_body(struct ospf_proto
*p
, struct ospf_iface
*ifa
)
909 struct ospf_lsa_net
*net
;
910 struct ospf_neighbor
*n
;
911 int nodes
= ifa
->fadj
+ 1;
914 ASSERT(p
->lsab_used
== 0);
915 net
= lsab_alloc(p
, sizeof(struct ospf_lsa_net
) + 4 * nodes
);
917 net
->optx
= u32_mkmask(ifa
->addr
->prefix
.pxlen
);
918 net
->routers
[0] = p
->router_id
;
920 WALK_LIST(n
, ifa
->neigh_list
)
922 if (n
->state
== NEIGHBOR_FULL
)
924 net
->routers
[i
] = n
->rid
;
932 prepare_net3_lsa_body(struct ospf_proto
*p
, struct ospf_iface
*ifa
)
934 struct ospf_lsa_net
*net
;
935 int nodes
= ifa
->fadj
+ 1;
939 ASSERT(p
->lsab_used
== 0);
940 net
= lsab_alloc(p
, sizeof(struct ospf_lsa_net
) + 4 * nodes
);
942 net
->routers
[0] = p
->router_id
;
944 struct ospf_neighbor
*n
;
945 WALK_LIST(n
, ifa
->neigh_list
)
947 if (n
->state
== NEIGHBOR_FULL
)
949 /* In OSPFv3, we would like to merge options from Link LSAs of added neighbors */
951 struct top_hash_entry
*en
=
952 ospf_hash_find(p
->gr
, ifa
->iface_id
, n
->iface_id
, n
->rid
, LSA_T_LINK
);
955 options
|= ((struct ospf_lsa_link
*) en
->lsa_body
)->options
;
957 net
->routers
[i
] = n
->rid
;
963 net
->optx
= options
& LSA_OPTIONS_MASK
;
967 ospf_originate_net_lsa(struct ospf_proto
*p
, struct ospf_iface
*ifa
)
969 struct ospf_new_lsa lsa
= {
971 .dom
= ifa
->oa
->areaid
,
972 .id
= ospf_is_v2(p
) ? ipa_to_u32(ifa
->addr
->ip
) : ifa
->iface_id
,
973 .opts
= ifa
->oa
->options
,
977 OSPF_TRACE(D_EVENTS
, "Updating network state for %s (Id: %R)", ifa
->ifname
, lsa
.id
);
980 prepare_net2_lsa_body(p
, ifa
);
982 prepare_net3_lsa_body(p
, ifa
);
984 ifa
->net_lsa
= ospf_originate_lsa(p
, &lsa
);
989 * (Net|Rt)-summary-LSA handling
990 * (a.k.a. Inter-Area-(Prefix|Router)-LSA)
991 * Type = LSA_T_SUM_NET, LSA_T_SUM_RT
995 prepare_sum2_lsa_body(struct ospf_proto
*p
, uint pxlen
, u32 metric
)
997 struct ospf_lsa_sum2
*sum
;
999 sum
= lsab_allocz(p
, sizeof(struct ospf_lsa_sum2
));
1000 sum
->netmask
= u32_mkmask(pxlen
);
1001 sum
->metric
= metric
;
1005 prepare_sum3_net_lsa_body(struct ospf_proto
*p
, ort
*nf
, u32 metric
)
1007 struct ospf_lsa_sum3_net
*sum
;
1009 sum
= lsab_allocz(p
, sizeof(struct ospf_lsa_sum3_net
) +
1010 IPV6_PREFIX_SPACE(nf
->fn
.addr
->pxlen
));
1011 sum
->metric
= metric
;
1012 ospf3_put_prefix(sum
->prefix
, nf
->fn
.addr
, 0, 0);
1016 prepare_sum3_rt_lsa_body(struct ospf_proto
*p
, u32 drid
, u32 metric
, u32 options
)
1018 struct ospf_lsa_sum3_rt
*sum
;
1020 sum
= lsab_allocz(p
, sizeof(struct ospf_lsa_sum3_rt
));
1021 sum
->options
= options
;
1022 sum
->metric
= metric
;
1027 ospf_originate_sum_net_lsa(struct ospf_proto
*p
, struct ospf_area
*oa
, ort
*nf
, int metric
)
1029 struct ospf_new_lsa lsa
= {
1030 .type
= LSA_T_SUM_NET
,
1031 .mode
= LSA_M_RTCALC
,
1033 .id
= ort_to_lsaid(p
, nf
),
1034 .opts
= oa
->options
,
1039 prepare_sum2_lsa_body(p
, nf
->fn
.addr
->pxlen
, metric
);
1041 prepare_sum3_net_lsa_body(p
, nf
, metric
);
1043 ospf_originate_lsa(p
, &lsa
);
1047 ospf_originate_sum_rt_lsa(struct ospf_proto
*p
, struct ospf_area
*oa
, u32 drid
, int metric
, u32 options
)
1049 struct ospf_new_lsa lsa
= {
1050 .type
= LSA_T_SUM_RT
,
1051 .mode
= LSA_M_RTCALC
,
1053 .id
= drid
, /* Router ID of ASBR, irrelevant for OSPFv3 */
1058 prepare_sum2_lsa_body(p
, 0, metric
);
1060 prepare_sum3_rt_lsa_body(p
, drid
, metric
, options
& LSA_OPTIONS_MASK
);
1062 ospf_originate_lsa(p
, &lsa
);
1067 * AS-external-LSA and NSSA-LSA handling
1068 * Type = LSA_T_EXT, LSA_T_NSSA
1072 prepare_ext2_lsa_body(struct ospf_proto
*p
, uint pxlen
,
1073 u32 metric
, u32 ebit
, ip_addr fwaddr
, u32 tag
)
1075 struct ospf_lsa_ext2
*ext
;
1077 ext
= lsab_allocz(p
, sizeof(struct ospf_lsa_ext2
));
1078 ext
->metric
= metric
& LSA_METRIC_MASK
;
1079 ext
->netmask
= u32_mkmask(pxlen
);
1080 ext
->fwaddr
= ipa_to_u32(fwaddr
);
1084 ext
->metric
|= LSA_EXT2_EBIT
;
1088 prepare_ext3_lsa_body(struct ospf_proto
*p
, ort
*nf
,
1089 u32 metric
, u32 ebit
, ip_addr fwaddr
, u32 tag
, int pbit
)
1091 struct ospf_lsa_ext3
*ext
;
1092 int bsize
= sizeof(struct ospf_lsa_ext3
)
1093 + IPV6_PREFIX_SPACE(nf
->fn
.addr
->pxlen
)
1094 + (ipa_nonzero(fwaddr
) ? 16 : 0)
1097 ext
= lsab_allocz(p
, bsize
);
1098 ext
->metric
= metric
& LSA_METRIC_MASK
;
1099 u32
*buf
= ext
->rest
;
1101 buf
= ospf3_put_prefix(buf
, nf
->fn
.addr
, pbit
? OPT_PX_P
: 0, 0);
1104 ext
->metric
|= LSA_EXT3_EBIT
;
1106 if (ipa_nonzero(fwaddr
))
1108 ext
->metric
|= LSA_EXT3_FBIT
;
1109 buf
= ospf3_put_addr(buf
, fwaddr
);
1114 ext
->metric
|= LSA_EXT3_TBIT
;
1120 * originate_ext_lsa - new route received from nest and filters
1121 * @p: OSPF protocol instance
1122 * @oa: ospf_area for which LSA is originated
1123 * @nf: network prefix and mask
1124 * @mode: the mode of the LSA (LSA_M_EXPORT or LSA_M_RTCALC)
1125 * @metric: the metric of a route
1126 * @ebit: E-bit for route metric (bool)
1127 * @fwaddr: the forwarding address
1128 * @tag: the route tag
1129 * @pbit: P-bit for NSSA LSAs (bool), ignored for external LSAs
1131 * If I receive a message that new route is installed, I try to originate an
1132 * external LSA. If @oa is an NSSA area, NSSA-LSA is originated instead.
1133 * @oa should not be a stub area. @src does not specify whether the LSA
1134 * is external or NSSA, but it specifies the source of origination -
1135 * the export from ospf_rt_notify(), or the NSSA-EXT translation.
1138 ospf_originate_ext_lsa(struct ospf_proto
*p
, struct ospf_area
*oa
, ort
*nf
, u8 mode
,
1139 u32 metric
, u32 ebit
, ip_addr fwaddr
, u32 tag
, int pbit
)
1141 struct ospf_new_lsa lsa
= {
1142 .type
= oa
? LSA_T_NSSA
: LSA_T_EXT
,
1143 .mode
= mode
, /* LSA_M_EXPORT or LSA_M_RTCALC */
1144 .dom
= oa
? oa
->areaid
: 0,
1145 .id
= ort_to_lsaid(p
, nf
),
1146 .opts
= oa
? (pbit
? OPT_P
: 0) : OPT_E
,
1151 prepare_ext2_lsa_body(p
, nf
->fn
.addr
->pxlen
, metric
, ebit
, fwaddr
, tag
);
1153 prepare_ext3_lsa_body(p
, nf
, metric
, ebit
, fwaddr
, tag
, oa
&& pbit
);
1155 ospf_originate_lsa(p
, &lsa
);
1158 static struct top_hash_entry
*
1159 ospf_hash_find_(struct top_graph
*f
, u32 domain
, u32 lsa
, u32 rtr
, u32 type
);
1162 ospf_flush_ext_lsa(struct ospf_proto
*p
, struct ospf_area
*oa
, ort
*nf
)
1164 struct top_hash_entry
*en
;
1166 u32 type
= oa
? LSA_T_NSSA
: LSA_T_EXT
;
1167 u32 dom
= oa
? oa
->areaid
: 0;
1168 u32 id
= ort_to_lsaid(p
, nf
);
1170 en
= ospf_hash_find_(p
->gr
, dom
, id
, p
->router_id
, type
);
1172 if (!en
|| (en
->nf
!= nf
))
1175 ospf_flush_lsa(p
, en
);
1179 use_gw_for_fwaddr(struct ospf_proto
*p
, ip_addr gw
, struct iface
*iface
)
1181 struct ospf_iface
*ifa
;
1183 if (ipa_zero(gw
) || ipa_is_link_local(gw
))
1186 WALK_LIST(ifa
, p
->iface_list
)
1187 if ((ifa
->iface
== iface
) &&
1188 (!ospf_is_v2(p
) || ipa_in_netX(gw
, &ifa
->addr
->prefix
)))
1194 static inline ip_addr
1195 find_surrogate_fwaddr(struct ospf_proto
*p
, struct ospf_area
*oa
)
1197 struct ospf_iface
*ifa
;
1198 struct ifa
*a
, *cur_addr
= NULL
;
1201 /* RFC 3101 2.3 - surrogate forwarding address selection */
1203 WALK_LIST(ifa
, p
->iface_list
)
1205 if ((ifa
->oa
!= oa
) ||
1206 (ifa
->type
== OSPF_IT_VLINK
))
1212 if (a
->flags
& IA_PEER
)
1215 np
= (a
->flags
& IA_HOST
) ? 3 : (ifa
->stub
? 2 : 1);
1224 WALK_LIST(a
, ifa
->iface
->addrs
)
1226 if ((a
->prefix
.type
!= ospf_get_af(p
)) ||
1227 (a
->flags
& IA_SECONDARY
) ||
1228 (a
->flags
& IA_PEER
) ||
1229 (a
->scope
<= SCOPE_LINK
))
1232 np
= (a
->flags
& IA_HOST
) ? 3 : (ifa
->stub
? 2 : 1);
1242 return cur_addr
? cur_addr
->ip
: IPA_NONE
;
1246 ospf_rt_notify(struct proto
*P
, struct channel
*ch UNUSED
, net
*n
, rte
*new, rte
*old UNUSED
)
1248 struct ospf_proto
*p
= (struct ospf_proto
*) P
;
1249 struct ospf_area
*oa
= NULL
; /* non-NULL for NSSA-LSA */
1253 * There are several posibilities:
1254 * 1) router in regular area - originate external LSA with global scope
1255 * 2) router in NSSA area - originate area-specific NSSA-LSA
1256 * 3) router in stub area - cannot export routes
1257 * 4) area border router - same as (1), it is attached to backbone
1260 if ((p
->areano
== 1) && oa_is_nssa(HEAD(p
->area_list
)))
1261 oa
= HEAD(p
->area_list
);
1265 nf
= fib_find(&p
->rtf
, n
->n
.addr
);
1267 if (!nf
|| !nf
->external_rte
)
1270 ospf_flush_ext_lsa(p
, oa
, nf
);
1271 nf
->external_rte
= 0;
1273 /* Old external route might blocked some NSSA translation */
1274 if ((p
->areano
> 1) && rt_is_nssa(nf
) && nf
->n
.oa
->translate
)
1275 ospf_schedule_rtcalc(p
);
1282 /* Get route attributes */
1283 rta
*a
= new->attrs
;
1284 eattr
*m1a
= ea_find(a
->eattrs
, EA_OSPF_METRIC1
);
1285 eattr
*m2a
= ea_find(a
->eattrs
, EA_OSPF_METRIC2
);
1286 uint m1
= m1a
? m1a
->u
.data
: 0;
1287 uint m2
= m2a
? m2a
->u
.data
: 10000;
1289 if (m1
> LSINFINITY
)
1291 log(L_WARN
"%s: Invalid ospf_metric1 value %u for route %N",
1292 p
->p
.name
, m1
, n
->n
.addr
);
1296 if (m2
> LSINFINITY
)
1298 log(L_WARN
"%s: Invalid ospf_metric2 value %u for route %N",
1299 p
->p
.name
, m2
, n
->n
.addr
);
1303 /* Ensure monotonicity of metric if both m1 and m2 are used */
1304 if ((m1
> 0) && (m2
< LSINFINITY
))
1307 uint ebit
= m2a
|| !m1a
;
1308 uint metric
= ebit
? m2
: m1
;
1309 uint tag
= ea_get_int(a
->eattrs
, EA_OSPF_TAG
, 0);
1311 ip_addr fwd
= IPA_NONE
;
1312 if ((a
->dest
== RTD_UNICAST
) && use_gw_for_fwaddr(p
, a
->nh
.gw
, a
->nh
.iface
))
1315 /* NSSA-LSA with P-bit set must have non-zero forwarding address */
1316 if (oa
&& ipa_zero(fwd
))
1318 fwd
= find_surrogate_fwaddr(p
, oa
);
1322 log(L_ERR
"%s: Cannot find forwarding address for NSSA-LSA %N",
1323 p
->p
.name
, n
->n
.addr
);
1328 nf
= fib_get(&p
->rtf
, n
->n
.addr
);
1329 ospf_originate_ext_lsa(p
, oa
, nf
, LSA_M_EXPORT
, metric
, ebit
, fwd
, tag
, 1);
1330 nf
->external_rte
= 1;
1335 * Link-LSA handling (assume OSPFv3)
1340 lsab_put_prefix(struct ospf_proto
*p
, net_addr
*n
, u32 cost
)
1342 void *buf
= lsab_alloc(p
, IPV6_PREFIX_SPACE(net_pxlen(n
)));
1343 uint max
= (n
->type
== NET_IP4
) ? IP4_MAX_PREFIX_LENGTH
: IP6_MAX_PREFIX_LENGTH
;
1344 u8 flags
= (net_pxlen(n
) < max
) ? 0 : OPT_PX_LA
;
1345 ospf3_put_prefix(buf
, n
, flags
, cost
);
1349 prepare_link_lsa_body(struct ospf_proto
*p
, struct ospf_iface
*ifa
)
1351 ip_addr nh
= ospf_is_ip4(p
) ? IPA_NONE
: ifa
->addr
->ip
;
1354 /* Preallocating space for header */
1355 ASSERT(p
->lsab_used
== 0);
1356 lsab_allocz(p
, sizeof(struct ospf_lsa_link
));
1359 WALK_LIST(a
, ifa
->iface
->addrs
)
1361 if ((a
->prefix
.type
!= ospf_get_af(p
)) ||
1362 (a
->flags
& IA_SECONDARY
) ||
1363 (a
->scope
<= SCOPE_LINK
))
1366 if (ospf_is_ip4(p
) && ipa_zero(nh
))
1369 lsab_put_prefix(p
, &a
->prefix
, 0);
1373 /* Filling the preallocated header */
1374 struct ospf_lsa_link
*ll
= p
->lsab
;
1375 ll
->options
= ifa
->oa
->options
| (ifa
->priority
<< 24);
1376 ll
->lladdr
= ospf_is_ip4(p
) ? ospf3_4to6(ipa_to_ip4(nh
)) : ipa_to_ip6(nh
);
1380 log(L_ERR
"%s: Cannot find next hop address for %s", p
->p
.name
, ifa
->ifname
);
1384 ospf_originate_link_lsa(struct ospf_proto
*p
, struct ospf_iface
*ifa
)
1389 struct ospf_new_lsa lsa
= {
1391 .dom
= ifa
->iface_id
,
1392 .id
= ifa
->iface_id
,
1396 OSPF_TRACE(D_EVENTS
, "Updating link state for %s (Id: %R)", ifa
->ifname
, lsa
.id
);
1398 prepare_link_lsa_body(p
, ifa
);
1400 ifa
->link_lsa
= ospf_originate_lsa(p
, &lsa
);
1405 * Prefix-Rt-LSA handling (assume OSPFv3)
1406 * Type = LSA_T_PREFIX, referred type = LSA_T_RT
1410 prepare_prefix_rt_lsa_body(struct ospf_proto
*p
, struct ospf_area
*oa
)
1412 struct ospf_config
*cf
= (struct ospf_config
*) (p
->p
.cf
);
1413 struct ospf_iface
*ifa
;
1414 struct ospf_lsa_prefix
*lp
;
1419 ASSERT(p
->lsab_used
== 0);
1420 lp
= lsab_allocz(p
, sizeof(struct ospf_lsa_prefix
));
1421 lp
->ref_type
= LSA_T_RT
;
1423 lp
->ref_rt
= p
->router_id
;
1424 lp
= NULL
; /* buffer might be reallocated later */
1426 WALK_LIST(ifa
, p
->iface_list
)
1428 if ((ifa
->oa
!= oa
) || (ifa
->type
== OSPF_IT_VLINK
) || (ifa
->state
== OSPF_IS_DOWN
))
1431 ifa
->px_pos_beg
= i
;
1433 if ((ifa
->type
== OSPF_IT_BCAST
) ||
1434 (ifa
->type
== OSPF_IT_NBMA
))
1435 net_lsa
= bcast_net_active(ifa
);
1440 WALK_LIST(a
, ifa
->iface
->addrs
)
1442 if ((a
->prefix
.type
!= ospf_get_af(p
)) ||
1443 (a
->flags
& IA_SECONDARY
) ||
1444 (a
->flags
& IA_PEER
) ||
1445 (a
->scope
<= SCOPE_LINK
))
1448 if (((a
->prefix
.pxlen
< IP6_MAX_PREFIX_LENGTH
) && net_lsa
) ||
1449 configured_stubnet(oa
, a
))
1452 if ((a
->flags
& IA_HOST
) ||
1453 (ifa
->state
== OSPF_IS_LOOP
) ||
1454 (ifa
->type
== OSPF_IT_PTMP
))
1456 net_addr_ip6 net
= NET_ADDR_IP6(a
->ip
, IP6_MAX_PREFIX_LENGTH
);
1457 lsab_put_prefix(p
, (net_addr
*) &net
, 0);
1461 lsab_put_prefix(p
, &a
->prefix
, ifa
->cost
);
1465 ifa
->px_pos_end
= i
;
1468 struct ospf_stubnet_config
*sn
;
1469 WALK_LIST(sn
, oa
->ac
->stubnet_list
)
1472 lsab_put_prefix(p
, &sn
->prefix
, sn
->cost
);
1473 if (sn
->prefix
.pxlen
== IP6_MAX_PREFIX_LENGTH
)
1478 /* If there are some configured vlinks, find some global address
1479 (even from another area), which will be used as a vlink endpoint. */
1480 if (!EMPTY_LIST(cf
->vlink_list
) && !host_addr
&& ospf_is_ip6(p
))
1482 WALK_LIST(ifa
, p
->iface_list
)
1484 if ((ifa
->type
== OSPF_IT_VLINK
) || (ifa
->state
== OSPF_IS_DOWN
))
1488 WALK_LIST(a
, ifa
->iface
->addrs
)
1490 if ((a
->prefix
.type
!= NET_IP6
) ||
1491 (a
->flags
& IA_SECONDARY
) ||
1492 (a
->scope
<= SCOPE_LINK
))
1496 net_addr_ip6 net
= NET_ADDR_IP6(a
->ip
, IP6_MAX_PREFIX_LENGTH
);
1497 lsab_put_prefix(p
, (net_addr
*) &net
, 0);
1510 ospf_originate_prefix_rt_lsa(struct ospf_proto
*p
, struct ospf_area
*oa
)
1515 struct ospf_new_lsa lsa
= {
1516 .type
= LSA_T_PREFIX
,
1521 prepare_prefix_rt_lsa_body(p
, oa
);
1523 ospf_originate_lsa(p
, &lsa
);
1528 * Prefix-Net-LSA handling (assume OSPFv3)
1529 * Type = LSA_T_PREFIX, referred type = LSA_T_NET
1533 prefix_space(u32
*buf
)
1535 int pxl
= *buf
>> 24;
1536 return IPV6_PREFIX_SPACE(pxl
);
1540 prefix_same(u32
*b1
, u32
*b2
)
1542 int pxl1
= *b1
>> 24;
1543 int pxl2
= *b2
>> 24;
1549 pxs
= IPV6_PREFIX_WORDS(pxl1
);
1550 for (i
= 1; i
< pxs
; i
++)
1558 prefix_advance(u32
*buf
)
1560 int pxl
= *buf
>> 24;
1561 return buf
+ IPV6_PREFIX_WORDS(pxl
);
1564 /* FIXME eliminate items with LA bit set? see 4.4.3.9 */
1566 add_prefix(struct ospf_proto
*p
, u32
*px
, int offset
, int *pxc
)
1568 u32
*pxl
= lsab_offset(p
, offset
);
1570 for (i
= 0; i
< *pxc
; pxl
= prefix_advance(pxl
), i
++)
1571 if (prefix_same(px
, pxl
))
1573 /* Options should be logically OR'ed together */
1574 *pxl
|= (*px
& 0x00FF0000);
1578 ASSERT(pxl
== lsab_end(p
));
1580 int pxspace
= prefix_space(px
);
1581 pxl
= lsab_alloc(p
, pxspace
);
1582 memcpy(pxl
, px
, pxspace
);
1583 *pxl
&= 0xFFFF0000; /* Set metric to zero */
1588 add_link_lsa(struct ospf_proto
*p
, struct ospf_lsa_link
*ll
, int offset
, int *pxc
)
1590 u32
*pxb
= ll
->rest
;
1593 for (j
= 0; j
< ll
->pxcount
; pxb
= prefix_advance(pxb
), j
++)
1595 u8 pxlen
= (pxb
[0] >> 24);
1596 u8 pxopts
= (pxb
[0] >> 16);
1598 /* Skip NU or LA prefixes */
1599 if (pxopts
& (OPT_PX_NU
| OPT_PX_LA
))
1602 /* Skip link-local prefixes */
1603 if (ospf_is_ip6(p
) && (pxlen
>= 10) && ((pxb
[1] & 0xffc00000) == 0xfe800000))
1606 add_prefix(p
, pxb
, offset
, pxc
);
1611 prepare_prefix_net_lsa_body(struct ospf_proto
*p
, struct ospf_iface
*ifa
)
1613 struct ospf_lsa_prefix
*lp
;
1614 struct ospf_neighbor
*n
;
1615 struct top_hash_entry
*en
;
1618 ASSERT(p
->lsab_used
== 0);
1619 lp
= lsab_allocz(p
, sizeof(struct ospf_lsa_prefix
));
1620 lp
->ref_type
= LSA_T_NET
;
1621 lp
->ref_id
= ifa
->net_lsa
->lsa
.id
;
1622 lp
->ref_rt
= p
->router_id
;
1623 lp
= NULL
; /* buffer might be reallocated later */
1626 offset
= p
->lsab_used
;
1628 /* Find all Link LSAs associated with the link and merge their prefixes */
1629 if (en
= ifa
->link_lsa
)
1630 add_link_lsa(p
, en
->next_lsa_body
?: en
->lsa_body
, offset
, &pxc
);
1632 WALK_LIST(n
, ifa
->neigh_list
)
1633 if ((n
->state
== NEIGHBOR_FULL
) &&
1634 (en
= ospf_hash_find(p
->gr
, ifa
->iface_id
, n
->iface_id
, n
->rid
, LSA_T_LINK
)))
1635 add_link_lsa(p
, en
->lsa_body
, offset
, &pxc
);
1642 ospf_originate_prefix_net_lsa(struct ospf_proto
*p
, struct ospf_iface
*ifa
)
1647 struct ospf_new_lsa lsa
= {
1648 .type
= LSA_T_PREFIX
,
1649 .dom
= ifa
->oa
->areaid
,
1650 .id
= ifa
->iface_id
,
1654 prepare_prefix_net_lsa_body(p
, ifa
);
1656 ifa
->pxn_lsa
= ospf_originate_lsa(p
, &lsa
);
1659 static inline int breaks_minlsinterval(struct top_hash_entry
*en
)
1660 { return en
&& (en
->lsa
.age
< LSA_MAXAGE
) && (lsa_inst_age(en
) < MINLSINTERVAL
); }
1663 ospf_update_topology(struct ospf_proto
*p
)
1665 struct ospf_area
*oa
;
1666 struct ospf_iface
*ifa
;
1668 WALK_LIST(oa
, p
->area_list
)
1670 if (oa
->update_rt_lsa
)
1673 * Generally, MinLSInterval is enforced in ospf_do_originate_lsa(), but
1674 * origination of (prefix) router LSA is a special case. We do not want to
1675 * prepare a new router LSA body and then postpone it in en->next_lsa_body
1676 * for later origination, because there are side effects (updates of
1677 * rt_pos_* and px_pos_* in ospf_iface structures) during that, which may
1678 * confuse routing table calculation if executed after LSA body
1679 * preparation but before final LSA origination (as rtcalc would use
1680 * current rt_pos_* indexes but the old router LSA body).
1682 * Here, we ensure that MinLSInterval is observed and we do not even try
1683 * to originate these LSAs if it is not. Therefore, origination, when
1684 * requested, will succeed unless there is also a seqnum wrapping, which
1685 * is not a problem because in that case rtcalc is blocked by MaxAge.
1688 if (breaks_minlsinterval(oa
->rt
) || breaks_minlsinterval(oa
->pxr_lsa
))
1691 ospf_originate_rt_lsa(p
, oa
);
1692 ospf_originate_prefix_rt_lsa(p
, oa
);
1693 oa
->update_rt_lsa
= 0;
1697 WALK_LIST(ifa
, p
->iface_list
)
1699 if (ifa
->type
== OSPF_IT_VLINK
)
1702 if (ifa
->update_link_lsa
)
1704 if ((ifa
->state
> OSPF_IS_LOOP
) && !ifa
->link_lsa_suppression
)
1705 ospf_originate_link_lsa(p
, ifa
);
1707 ospf_flush2_lsa(p
, &ifa
->link_lsa
);
1709 ifa
->update_link_lsa
= 0;
1712 if (ifa
->update_net_lsa
)
1714 if ((ifa
->state
== OSPF_IS_DR
) && (ifa
->fadj
> 0))
1716 ospf_originate_net_lsa(p
, ifa
);
1717 ospf_originate_prefix_net_lsa(p
, ifa
);
1721 ospf_flush2_lsa(p
, &ifa
->net_lsa
);
1722 ospf_flush2_lsa(p
, &ifa
->pxn_lsa
);
1725 ifa
->update_net_lsa
= 0;
1732 ospf_top_ht_alloc(struct top_graph
*f
)
1734 f
->hash_size
= 1 << f
->hash_order
;
1735 f
->hash_mask
= f
->hash_size
- 1;
1736 if (f
->hash_order
> HASH_HI_MAX
- HASH_HI_STEP
)
1737 f
->hash_entries_max
= ~0;
1739 f
->hash_entries_max
= f
->hash_size HASH_HI_MARK
;
1740 if (f
->hash_order
< HASH_LO_MIN
+ HASH_LO_STEP
)
1741 f
->hash_entries_min
= 0;
1743 f
->hash_entries_min
= f
->hash_size HASH_LO_MARK
;
1744 DBG("Allocating OSPF hash of order %d: %d hash_entries, %d low, %d high\n",
1745 f
->hash_order
, f
->hash_size
, f
->hash_entries_min
, f
->hash_entries_max
);
1747 mb_alloc(f
->pool
, f
->hash_size
* sizeof(struct top_hash_entry
*));
1748 bzero(f
->hash_table
, f
->hash_size
* sizeof(struct top_hash_entry
*));
1752 ospf_top_ht_free(struct top_hash_entry
**h
)
1758 ospf_top_hash_u32(u32 a
)
1760 /* Shamelessly stolen from IP address hashing in ipv4.h */
1767 ospf_top_hash(struct top_graph
*f
, u32 domain
, u32 lsaid
, u32 rtrid
, u32 type
)
1769 /* In OSPFv2, we don't know Router ID when looking for network LSAs.
1770 In OSPFv3, we don't know LSA ID when looking for router LSAs.
1771 In both cases, there is (usually) just one (or small number)
1772 appropriate LSA, so we just clear unknown part of key. */
1774 return (((f
->ospf2
&& (type
== LSA_T_NET
)) ? 0 : ospf_top_hash_u32(rtrid
)) +
1775 ((!f
->ospf2
&& (type
== LSA_T_RT
)) ? 0 : ospf_top_hash_u32(lsaid
)) +
1776 type
+ domain
) & f
->hash_mask
;
1779 return (ospf_top_hash_u32(lsaid) + ospf_top_hash_u32(rtrid) +
1780 type + areaid) & f->hash_mask;
1785 * ospf_top_new - allocated new topology database
1786 * @p: OSPF protocol instance
1787 * @pool: pool for allocation
1789 * This dynamically hashed structure is used for keeping LSAs. Mainly it is used
1790 * for the LSA database of the OSPF protocol, but also for LSA retransmission
1791 * and request lists of OSPF neighbors.
1794 ospf_top_new(struct ospf_proto
*p
, pool
*pool
)
1796 struct top_graph
*f
;
1798 f
= mb_allocz(pool
, sizeof(struct top_graph
));
1800 f
->hash_slab
= sl_new(f
->pool
, sizeof(struct top_hash_entry
));
1801 f
->hash_order
= HASH_DEF_ORDER
;
1802 ospf_top_ht_alloc(f
);
1803 f
->hash_entries
= 0;
1804 f
->hash_entries_min
= 0;
1805 f
->ospf2
= ospf_is_v2(p
);
1810 ospf_top_free(struct top_graph
*f
)
1812 rfree(f
->hash_slab
);
1813 ospf_top_ht_free(f
->hash_table
);
1818 ospf_top_rehash(struct top_graph
*f
, int step
)
1820 struct top_hash_entry
**n
, **oldt
, **newt
, *e
, *x
;
1823 oldn
= f
->hash_size
;
1824 oldt
= f
->hash_table
;
1825 DBG("re-hashing topology hash from order %d to %d\n", f
->hash_order
,
1826 f
->hash_order
+ step
);
1827 f
->hash_order
+= step
;
1828 ospf_top_ht_alloc(f
);
1829 newt
= f
->hash_table
;
1831 for (oldh
= 0; oldh
< oldn
; oldh
++)
1837 n
= newt
+ ospf_top_hash(f
, e
->domain
, e
->lsa
.id
, e
->lsa
.rt
, e
->lsa_type
);
1843 ospf_top_ht_free(oldt
);
1846 static struct top_hash_entry
*
1847 ospf_hash_find_(struct top_graph
*f
, u32 domain
, u32 lsa
, u32 rtr
, u32 type
)
1849 struct top_hash_entry
*e
;
1850 e
= f
->hash_table
[ospf_top_hash(f
, domain
, lsa
, rtr
, type
)];
1852 while (e
&& (e
->lsa
.id
!= lsa
|| e
->lsa
.rt
!= rtr
||
1853 e
->lsa_type
!= type
|| e
->domain
!= domain
))
1859 struct top_hash_entry
*
1860 ospf_hash_find(struct top_graph
*f
, u32 domain
, u32 lsa
, u32 rtr
, u32 type
)
1862 struct top_hash_entry
*e
= ospf_hash_find_(f
, domain
, lsa
, rtr
, type
);
1864 /* Hide hash entry with empty lsa_body */
1865 return (e
&& e
->lsa_body
) ? e
: NULL
;
1868 /* In OSPFv2, lsa.id is the same as lsa.rt for router LSA. In OSPFv3, we don't know
1869 lsa.id when looking for router LSAs. We return matching LSA with smallest lsa.id. */
1870 struct top_hash_entry
*
1871 ospf_hash_find_rt(struct top_graph
*f
, u32 domain
, u32 rtr
)
1873 struct top_hash_entry
*rv
= NULL
;
1874 struct top_hash_entry
*e
;
1875 /* We can put rtr for lsa.id to hash fn, it is ignored in OSPFv3 */
1876 e
= f
->hash_table
[ospf_top_hash(f
, domain
, rtr
, rtr
, LSA_T_RT
)];
1880 if (e
->lsa
.rt
== rtr
&& e
->lsa_type
== LSA_T_RT
&& e
->domain
== domain
&& e
->lsa_body
)
1882 if (f
->ospf2
&& (e
->lsa
.id
== rtr
))
1884 if (!f
->ospf2
&& (!rv
|| e
->lsa
.id
< rv
->lsa
.id
))
1894 * ospf_hash_find_rt3_first() and ospf_hash_find_rt3_next() are used exclusively
1895 * for lsa_walk_rt_init(), lsa_walk_rt(), therefore they skip MaxAge entries.
1897 static inline struct top_hash_entry
*
1898 find_matching_rt3(struct top_hash_entry
*e
, u32 domain
, u32 rtr
)
1900 while (e
&& (e
->lsa
.rt
!= rtr
|| e
->lsa_type
!= LSA_T_RT
||
1901 e
->domain
!= domain
|| e
->lsa
.age
== LSA_MAXAGE
))
1906 struct top_hash_entry
*
1907 ospf_hash_find_rt3_first(struct top_graph
*f
, u32 domain
, u32 rtr
)
1909 struct top_hash_entry
*e
;
1910 e
= f
->hash_table
[ospf_top_hash(f
, domain
, 0, rtr
, LSA_T_RT
)];
1911 return find_matching_rt3(e
, domain
, rtr
);
1914 struct top_hash_entry
*
1915 ospf_hash_find_rt3_next(struct top_hash_entry
*e
)
1917 return find_matching_rt3(e
->next
, e
->domain
, e
->lsa
.rt
);
1920 /* In OSPFv2, we don't know Router ID when looking for network LSAs.
1921 There should be just one, so we find any match. */
1922 struct top_hash_entry
*
1923 ospf_hash_find_net2(struct top_graph
*f
, u32 domain
, u32 id
)
1925 struct top_hash_entry
*e
;
1926 e
= f
->hash_table
[ospf_top_hash(f
, domain
, id
, 0, LSA_T_NET
)];
1928 while (e
&& (e
->lsa
.id
!= id
|| e
->lsa_type
!= LSA_T_NET
||
1929 e
->domain
!= domain
|| e
->lsa_body
== NULL
))
1936 struct top_hash_entry
*
1937 ospf_hash_get(struct top_graph
*f
, u32 domain
, u32 lsa
, u32 rtr
, u32 type
)
1939 struct top_hash_entry
**ee
;
1940 struct top_hash_entry
*e
;
1942 ee
= f
->hash_table
+ ospf_top_hash(f
, domain
, lsa
, rtr
, type
);
1945 while (e
&& (e
->lsa
.id
!= lsa
|| e
->lsa
.rt
!= rtr
||
1946 e
->lsa_type
!= type
|| e
->domain
!= domain
))
1952 e
= sl_alloc(f
->hash_slab
);
1953 bzero(e
, sizeof(struct top_hash_entry
));
1956 e
->dist
= LSINFINITY
;
1957 e
->lsa
.type_raw
= type
;
1960 e
->lsa
.sn
= LSA_ZEROSEQNO
;
1965 if (f
->hash_entries
++ > f
->hash_entries_max
)
1966 ospf_top_rehash(f
, HASH_HI_STEP
);
1971 ospf_hash_delete(struct top_graph
*f
, struct top_hash_entry
*e
)
1973 struct top_hash_entry
**ee
= f
->hash_table
+
1974 ospf_top_hash(f
, e
->domain
, e
->lsa
.id
, e
->lsa
.rt
, e
->lsa_type
);
1981 sl_free(f
->hash_slab
, e
);
1982 if (f
->hash_entries
-- < f
->hash_entries_min
)
1983 ospf_top_rehash(f
, -HASH_LO_STEP
);
1986 ee
= &((*ee
)->next
);
1988 bug("ospf_hash_delete() called for invalid node");
1993 ospf_dump_lsa(struct top_hash_entry *he, struct proto *p)
1996 struct ospf_lsa_rt *rt = NULL;
1997 struct ospf_lsa_rt_link *rr = NULL;
1998 struct ospf_lsa_net *ln = NULL;
2002 OSPF_TRACE(D_EVENTS, "- %1x %-1R %-1R %4u 0x%08x 0x%04x %-1R",
2003 he->lsa.type, he->lsa.id, he->lsa.rt, he->lsa.age, he->lsa.sn,
2004 he->lsa.checksum, he->domain);
2007 switch (he->lsa.type)
2011 rr = (struct ospf_lsa_rt_link *) (rt + 1);
2013 for (i = 0; i < lsa_rt_items(&he->lsa); i++)
2014 OSPF_TRACE(D_EVENTS, " - %1x %-1R %-1R %5u",
2015 rr[i].type, rr[i].id, rr[i].data, rr[i].metric);
2020 rts = (u32 *) (ln + 1);
2022 for (i = 0; i < lsa_net_items(&he->lsa); i++)
2023 OSPF_TRACE(D_EVENTS, " - %-1R", rts[i]);
2032 ospf_top_dump(struct top_graph *f, struct proto *p)
2035 OSPF_TRACE(D_EVENTS, "Hash entries: %d", f->hash_entries);
2037 for (i = 0; i < f->hash_size; i++)
2039 struct top_hash_entry *e;
2040 for (e = f->hash_table[i]; e != NULL; e = e->next)
2041 ospf_dump_lsa(e, p);