]>
git.ipfire.org Git - thirdparty/bird.git/blob - proto/ospf/topology.c
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
)
409 if (en
->next_lsa_body
)
411 mb_free(en
->next_lsa_body
);
412 en
->next_lsa_body
= NULL
;
413 en
->next_lsa_blen
= 0;
414 en
->next_lsa_opts
= 0;
417 if (en
->lsa
.age
== LSA_MAXAGE
)
420 OSPF_TRACE(D_EVENTS
, "Flushing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
421 en
->lsa_type
, en
->lsa
.id
, en
->lsa
.rt
, en
->lsa
.sn
);
423 en
->lsa
.age
= LSA_MAXAGE
;
424 ospf_flood_lsa(p
, en
, NULL
);
426 if (en
->mode
== LSA_M_BASIC
)
427 ospf_schedule_rtcalc(p
);
429 en
->mode
= LSA_M_BASIC
;
433 ospf_clear_lsa(struct ospf_proto
*p
, struct top_hash_entry
*en
)
436 * Called by ospf_update_lsadb() as part of LSA flushing process.
437 * Flushed LSA was acknowledged by neighbors and we can free its content.
438 * The log message is for 'remove' - we hide empty LSAs from users.
441 OSPF_TRACE(D_EVENTS
, "Removing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
442 en
->lsa_type
, en
->lsa
.id
, en
->lsa
.rt
, en
->lsa
.sn
);
444 if (en
->lsa
.sn
== LSA_MAXSEQNO
)
445 en
->lsa
.sn
= LSA_ZEROSEQNO
;
447 mb_free(en
->lsa_body
);
452 ospf_remove_lsa(struct ospf_proto
*p
, struct top_hash_entry
*en
)
455 * Called by ospf_update_lsadb() as part of LSA flushing process.
456 * Both lsa_body and next_lsa_body are NULL.
459 s_rem_node(SNODE en
);
460 ospf_hash_delete(p
->gr
, en
);
464 * ospf_update_lsadb - update LSA database
465 * @p: OSPF protocol instance
467 * This function is periodicaly invoked from ospf_disp(). It does some periodic
468 * or postponed processing related to LSA entries. It originates postponed LSAs
469 * scheduled by ospf_originate_lsa(), It continues in flushing processes started
470 * by ospf_flush_lsa(). It also periodically refreshs locally originated LSAs --
471 * when the current instance is older %LSREFRESHTIME, a new instance is originated.
472 * Finally, it also ages stored LSAs and flushes ones that reached %LSA_MAXAGE.
474 * The RFC 2328 says that a router should periodically check checksums of all
475 * stored LSAs to detect hardware problems. This is not implemented.
478 ospf_update_lsadb(struct ospf_proto
*p
)
480 struct top_hash_entry
*en
, *nxt
;
481 btime now_
= current_time();
484 WALK_SLIST_DELSAFE(en
, nxt
, p
->lsal
)
486 if (en
->next_lsa_body
)
487 ospf_originate_next_lsa(p
, en
);
489 real_age
= en
->init_age
+ (now_
- en
->inst_time
) TO_S
;
491 if (en
->lsa
.age
== LSA_MAXAGE
)
493 if (en
->lsa_body
&& (p
->padj
== 0) && (en
->ret_count
== 0))
494 ospf_clear_lsa(p
, en
);
496 if ((en
->lsa_body
== NULL
) && (en
->next_lsa_body
== NULL
) &&
497 ((en
->lsa
.rt
!= p
->router_id
) || (real_age
>= LSA_MAXAGE
)))
498 ospf_remove_lsa(p
, en
);
503 if ((en
->lsa
.rt
== p
->router_id
) && (real_age
>= LSREFRESHTIME
))
505 ospf_refresh_lsa(p
, en
);
509 if (real_age
>= LSA_MAXAGE
)
511 ospf_flush_lsa(p
, en
);
515 en
->lsa
.age
= real_age
;
521 ort_to_lsaid(struct ospf_proto
*p
, ort
*nf
)
524 * In OSPFv2, We have to map IP prefixes to u32 in such manner that resulting
525 * u32 interpreted as IP address is a member of given prefix. Therefore, /32
526 * prefix has to be mapped on itself. All received prefixes have to be mapped
529 * We have an assumption that if there is nontrivial (non-/32) network prefix,
530 * then there is not /32 prefix for the first and the last IP address of the
531 * network (these are usually reserved, therefore it is not an important
532 * restriction). The network prefix is mapped to the first or the last IP
533 * address in the manner that disallow collisions - we use the IP address that
534 * cannot be used by the parent prefix.
537 * 192.168.0.0/24 maps to 192.168.0.255
538 * 192.168.1.0/24 maps to 192.168.1.0
539 * because 192.168.0.0 and 192.168.1.255 might be used by 192.168.0.0/23 .
541 * Appendig E of RFC 2328 suggests different algorithm, that tries to maximize
542 * both compatibility and subnetting. But as it is not possible to have both
543 * reliably and the suggested algorithm was unnecessary complicated and it
544 * does crazy things like changing LSA ID for a network because different
545 * network appeared, we choose a different way.
547 * In OSPFv3, it is simpler. There is not a requirement for membership of the
548 * result in the input network, so we just allocate a unique ID from ID map
549 * and store it in nf->lsa_id for further reference.
555 nf
->lsa_id
= idm_alloc(&p
->idm
);
560 net_addr_ip4
*net
= (void *) nf
->fn
.addr
;
561 u32 id
= ip4_to_u32(net
->prefix
);
562 int pxlen
= net
->pxlen
;
564 if ((pxlen
== 0) || (pxlen
== 32))
567 if (id
& (1 << (32 - pxlen
)))
570 return id
| ~u32_mkmask(pxlen
);
575 lsab_alloc(struct ospf_proto
*p
, uint size
)
577 uint offset
= p
->lsab_used
;
578 p
->lsab_used
+= size
;
579 if (p
->lsab_used
> p
->lsab_size
)
581 p
->lsab_size
= MAX(p
->lsab_used
, 2 * p
->lsab_size
);
582 p
->lsab
= p
->lsab
? mb_realloc(p
->lsab
, p
->lsab_size
):
583 mb_alloc(p
->p
.pool
, p
->lsab_size
);
585 return ((byte
*) p
->lsab
) + offset
;
589 lsab_allocz(struct ospf_proto
*p
, uint size
)
591 void *r
= lsab_alloc(p
, size
);
597 lsab_flush(struct ospf_proto
*p
)
599 void *r
= mb_alloc(p
->p
.pool
, p
->lsab_used
);
600 memcpy(r
, p
->lsab
, p
->lsab_used
);
606 lsab_reset(struct ospf_proto
*p
)
612 lsab_offset(struct ospf_proto
*p
, uint offset
)
614 return ((byte
*) p
->lsab
) + offset
;
617 static inline void * UNUSED
618 lsab_end(struct ospf_proto
*p
)
620 return ((byte
*) p
->lsab
) + p
->lsab_used
;
625 * Router-LSA handling
630 configured_stubnet(struct ospf_area
*oa
, struct ifa
*a
)
632 /* Does not work for IA_PEER addresses, but it is not called on these */
633 struct ospf_stubnet_config
*sn
;
634 WALK_LIST(sn
, oa
->ac
->stubnet_list
)
638 if (net_in_netX(&a
->prefix
, &sn
->prefix
))
643 if (net_equal(&a
->prefix
, &sn
->prefix
))
652 bcast_net_active(struct ospf_iface
*ifa
)
654 struct ospf_neighbor
*neigh
;
656 if (ifa
->state
== OSPF_IS_WAITING
)
659 WALK_LIST(neigh
, ifa
->neigh_list
)
661 if (neigh
->state
== NEIGHBOR_FULL
)
663 if (neigh
->rid
== ifa
->drid
)
666 if (ifa
->state
== OSPF_IS_DR
)
675 get_rt_options(struct ospf_proto
*p
, struct ospf_area
*oa
, int bitv
)
682 if ((p
->areano
> 1) && oa_is_nssa(oa
) && oa
->ac
->translator
)
685 if (p
->asbr
&& !oa_is_stub(oa
))
695 add_rt2_lsa_link(struct ospf_proto
*p
, u8 type
, u32 id
, u32 data
, u16 metric
)
697 struct ospf_lsa_rt2_link
*ln
= lsab_alloc(p
, sizeof(struct ospf_lsa_rt2_link
));
706 prepare_rt2_lsa_body(struct ospf_proto
*p
, struct ospf_area
*oa
)
708 struct ospf_iface
*ifa
;
710 struct ospf_neighbor
*neigh
;
712 ASSERT(p
->lsab_used
== 0);
713 lsab_allocz(p
, sizeof(struct ospf_lsa_rt
));
714 /* ospf_lsa_rt header will be filled later */
716 WALK_LIST(ifa
, p
->iface_list
)
719 u32 link_cost
= p
->stub_router
? 0xffff : ifa
->cost
;
721 if ((ifa
->type
== OSPF_IT_VLINK
) && (ifa
->voa
== oa
) &&
722 (!EMPTY_LIST(ifa
->neigh_list
)))
724 neigh
= (struct ospf_neighbor
*) HEAD(ifa
->neigh_list
);
725 if ((neigh
->state
== NEIGHBOR_FULL
) && (ifa
->cost
<= 0xffff))
729 if ((ifa
->oa
!= oa
) || (ifa
->state
== OSPF_IS_DOWN
))
734 /* RFC 2328 - 12.4.1.1-4 */
739 WALK_LIST(neigh
, ifa
->neigh_list
)
740 if (neigh
->state
== NEIGHBOR_FULL
)
743 * ln->data should be ifa->iface_id in case of no/ptp
744 * address (ifa->addr->flags & IA_PEER) on PTP link (see
745 * RFC 2328 12.4.1.1.), but the iface ID value has no use,
746 * while using IP address even in this case is here for
747 * compatibility with some broken implementations that use
748 * this address as a next-hop.
750 add_rt2_lsa_link(p
, LSART_PTP
, neigh
->rid
, ipa_to_u32(ifa
->addr
->ip
), link_cost
);
757 if (bcast_net_active(ifa
))
759 add_rt2_lsa_link(p
, LSART_NET
, ipa_to_u32(ifa
->drip
), ipa_to_u32(ifa
->addr
->ip
), link_cost
);
766 neigh
= (struct ospf_neighbor
*) HEAD(ifa
->neigh_list
);
767 if ((!EMPTY_LIST(ifa
->neigh_list
)) && (neigh
->state
== NEIGHBOR_FULL
) && (ifa
->cost
<= 0xffff))
768 add_rt2_lsa_link(p
, LSART_VLNK
, neigh
->rid
, ipa_to_u32(ifa
->addr
->ip
), link_cost
), i
++;
772 log(L_BUG
"OSPF: Unknown interface type");
778 /* Now we will originate stub area if there is no primary */
780 (ifa
->type
== OSPF_IT_VLINK
) ||
781 ((ifa
->addr
->flags
& IA_PEER
) && ! ifa
->cf
->stub
) ||
782 configured_stubnet(oa
, ifa
->addr
))
785 /* Host or network stub entry */
786 if ((ifa
->addr
->flags
& IA_HOST
) ||
787 (ifa
->state
== OSPF_IS_LOOP
) ||
788 (ifa
->type
== OSPF_IT_PTMP
))
789 add_rt2_lsa_link(p
, LSART_STUB
, ipa_to_u32(ifa
->addr
->ip
), 0xffffffff, 0);
791 add_rt2_lsa_link(p
, LSART_STUB
, ip4_to_u32(net4_prefix(&ifa
->addr
->prefix
)),
792 u32_mkmask(net4_pxlen(&ifa
->addr
->prefix
)), ifa
->cost
);
798 struct ospf_stubnet_config
*sn
;
799 WALK_LIST(sn
, oa
->ac
->stubnet_list
)
801 add_rt2_lsa_link(p
, LSART_STUB
, ip4_to_u32(net4_prefix(&sn
->prefix
)),
802 u32_mkmask(net4_pxlen(&sn
->prefix
)), sn
->cost
), i
++;
804 struct ospf_lsa_rt
*rt
= p
->lsab
;
805 /* Store number of links in lower half of options */
806 rt
->options
= get_rt_options(p
, oa
, bitv
) | (u16
) i
;
810 add_rt3_lsa_link(struct ospf_proto
*p
, u8 type
, struct ospf_iface
*ifa
, u32 nif
, u32 id
)
812 struct ospf_lsa_rt3_link
*ln
= lsab_alloc(p
, sizeof(struct ospf_lsa_rt3_link
));
815 ln
->metric
= ifa
->cost
;
816 ln
->lif
= ifa
->iface_id
;
822 prepare_rt3_lsa_body(struct ospf_proto
*p
, struct ospf_area
*oa
)
824 struct ospf_iface
*ifa
;
825 struct ospf_neighbor
*neigh
;
829 ASSERT(p
->lsab_used
== 0);
830 lsab_allocz(p
, sizeof(struct ospf_lsa_rt
));
831 /* ospf_lsa_rt header will be filled later */
833 WALK_LIST(ifa
, p
->iface_list
)
835 if ((ifa
->type
== OSPF_IT_VLINK
) && (ifa
->voa
== oa
) &&
836 (!EMPTY_LIST(ifa
->neigh_list
)))
838 neigh
= (struct ospf_neighbor
*) HEAD(ifa
->neigh_list
);
839 if ((neigh
->state
== NEIGHBOR_FULL
) && (ifa
->cost
<= 0xffff))
843 if ((ifa
->oa
!= oa
) || (ifa
->state
== OSPF_IS_DOWN
))
848 /* RFC 5340 - 4.4.3.2 */
853 WALK_LIST(neigh
, ifa
->neigh_list
)
854 if (neigh
->state
== NEIGHBOR_FULL
)
855 add_rt3_lsa_link(p
, LSART_PTP
, ifa
, neigh
->iface_id
, neigh
->rid
), i
++;
860 if (bcast_net_active(ifa
))
861 add_rt3_lsa_link(p
, LSART_NET
, ifa
, ifa
->dr_iface_id
, ifa
->drid
), i
++;
865 neigh
= (struct ospf_neighbor
*) HEAD(ifa
->neigh_list
);
866 if ((!EMPTY_LIST(ifa
->neigh_list
)) && (neigh
->state
== NEIGHBOR_FULL
) && (ifa
->cost
<= 0xffff))
867 add_rt3_lsa_link(p
, LSART_VLNK
, ifa
, neigh
->iface_id
, neigh
->rid
), i
++;
871 log(L_BUG
"OSPF: Unknown interface type");
878 struct ospf_lsa_rt
*rt
= p
->lsab
;
879 rt
->options
= get_rt_options(p
, oa
, bitv
) | (oa
->options
& LSA_OPTIONS_MASK
);
883 ospf_originate_rt_lsa(struct ospf_proto
*p
, struct ospf_area
*oa
)
885 struct ospf_new_lsa lsa
= {
888 .id
= ospf_is_v2(p
) ? p
->router_id
: 0,
892 OSPF_TRACE(D_EVENTS
, "Updating router state for area %R", oa
->areaid
);
895 prepare_rt2_lsa_body(p
, oa
);
897 prepare_rt3_lsa_body(p
, oa
);
899 oa
->rt
= ospf_originate_lsa(p
, &lsa
);
909 prepare_net2_lsa_body(struct ospf_proto
*p
, struct ospf_iface
*ifa
)
911 struct ospf_lsa_net
*net
;
912 struct ospf_neighbor
*n
;
913 int nodes
= ifa
->fadj
+ 1;
916 ASSERT(p
->lsab_used
== 0);
917 net
= lsab_alloc(p
, sizeof(struct ospf_lsa_net
) + 4 * nodes
);
919 net
->optx
= u32_mkmask(ifa
->addr
->prefix
.pxlen
);
920 net
->routers
[0] = p
->router_id
;
922 WALK_LIST(n
, ifa
->neigh_list
)
924 if (n
->state
== NEIGHBOR_FULL
)
926 net
->routers
[i
] = n
->rid
;
934 prepare_net3_lsa_body(struct ospf_proto
*p
, struct ospf_iface
*ifa
)
936 struct ospf_lsa_net
*net
;
937 int nodes
= ifa
->fadj
+ 1;
941 ASSERT(p
->lsab_used
== 0);
942 net
= lsab_alloc(p
, sizeof(struct ospf_lsa_net
) + 4 * nodes
);
944 net
->routers
[0] = p
->router_id
;
946 struct ospf_neighbor
*n
;
947 WALK_LIST(n
, ifa
->neigh_list
)
949 if (n
->state
== NEIGHBOR_FULL
)
951 /* In OSPFv3, we would like to merge options from Link LSAs of added neighbors */
953 struct top_hash_entry
*en
=
954 ospf_hash_find(p
->gr
, ifa
->iface_id
, n
->iface_id
, n
->rid
, LSA_T_LINK
);
957 options
|= ((struct ospf_lsa_link
*) en
->lsa_body
)->options
;
959 net
->routers
[i
] = n
->rid
;
965 net
->optx
= options
& LSA_OPTIONS_MASK
;
969 ospf_originate_net_lsa(struct ospf_proto
*p
, struct ospf_iface
*ifa
)
971 struct ospf_new_lsa lsa
= {
973 .dom
= ifa
->oa
->areaid
,
974 .id
= ospf_is_v2(p
) ? ipa_to_u32(ifa
->addr
->ip
) : ifa
->iface_id
,
975 .opts
= ifa
->oa
->options
,
979 OSPF_TRACE(D_EVENTS
, "Updating network state for %s (Id: %R)", ifa
->ifname
, lsa
.id
);
982 prepare_net2_lsa_body(p
, ifa
);
984 prepare_net3_lsa_body(p
, ifa
);
986 ifa
->net_lsa
= ospf_originate_lsa(p
, &lsa
);
991 * (Net|Rt)-summary-LSA handling
992 * (a.k.a. Inter-Area-(Prefix|Router)-LSA)
993 * Type = LSA_T_SUM_NET, LSA_T_SUM_RT
997 prepare_sum2_lsa_body(struct ospf_proto
*p
, uint pxlen
, u32 metric
)
999 struct ospf_lsa_sum2
*sum
;
1001 sum
= lsab_allocz(p
, sizeof(struct ospf_lsa_sum2
));
1002 sum
->netmask
= u32_mkmask(pxlen
);
1003 sum
->metric
= metric
;
1007 prepare_sum3_net_lsa_body(struct ospf_proto
*p
, ort
*nf
, u32 metric
)
1009 struct ospf_lsa_sum3_net
*sum
;
1011 sum
= lsab_allocz(p
, sizeof(struct ospf_lsa_sum3_net
) +
1012 IPV6_PREFIX_SPACE(nf
->fn
.addr
->pxlen
));
1013 sum
->metric
= metric
;
1014 ospf3_put_prefix(sum
->prefix
, nf
->fn
.addr
, 0, 0);
1018 prepare_sum3_rt_lsa_body(struct ospf_proto
*p
, u32 drid
, u32 metric
, u32 options
)
1020 struct ospf_lsa_sum3_rt
*sum
;
1022 sum
= lsab_allocz(p
, sizeof(struct ospf_lsa_sum3_rt
));
1023 sum
->options
= options
;
1024 sum
->metric
= metric
;
1029 ospf_originate_sum_net_lsa(struct ospf_proto
*p
, struct ospf_area
*oa
, ort
*nf
, int metric
)
1031 struct ospf_new_lsa lsa
= {
1032 .type
= LSA_T_SUM_NET
,
1033 .mode
= LSA_M_RTCALC
,
1035 .id
= ort_to_lsaid(p
, nf
),
1036 .opts
= oa
->options
,
1041 prepare_sum2_lsa_body(p
, nf
->fn
.addr
->pxlen
, metric
);
1043 prepare_sum3_net_lsa_body(p
, nf
, metric
);
1045 ospf_originate_lsa(p
, &lsa
);
1049 ospf_originate_sum_rt_lsa(struct ospf_proto
*p
, struct ospf_area
*oa
, u32 drid
, int metric
, u32 options
)
1051 struct ospf_new_lsa lsa
= {
1052 .type
= LSA_T_SUM_RT
,
1053 .mode
= LSA_M_RTCALC
,
1055 .id
= drid
, /* Router ID of ASBR, irrelevant for OSPFv3 */
1060 prepare_sum2_lsa_body(p
, 0, metric
);
1062 prepare_sum3_rt_lsa_body(p
, drid
, metric
, options
& LSA_OPTIONS_MASK
);
1064 ospf_originate_lsa(p
, &lsa
);
1069 * AS-external-LSA and NSSA-LSA handling
1070 * Type = LSA_T_EXT, LSA_T_NSSA
1074 prepare_ext2_lsa_body(struct ospf_proto
*p
, uint pxlen
,
1075 u32 metric
, u32 ebit
, ip_addr fwaddr
, u32 tag
)
1077 struct ospf_lsa_ext2
*ext
;
1079 ext
= lsab_allocz(p
, sizeof(struct ospf_lsa_ext2
));
1080 ext
->metric
= metric
& LSA_METRIC_MASK
;
1081 ext
->netmask
= u32_mkmask(pxlen
);
1082 ext
->fwaddr
= ipa_to_u32(fwaddr
);
1086 ext
->metric
|= LSA_EXT2_EBIT
;
1090 prepare_ext3_lsa_body(struct ospf_proto
*p
, ort
*nf
,
1091 u32 metric
, u32 ebit
, ip_addr fwaddr
, u32 tag
, int pbit
)
1093 struct ospf_lsa_ext3
*ext
;
1094 int bsize
= sizeof(struct ospf_lsa_ext3
)
1095 + IPV6_PREFIX_SPACE(nf
->fn
.addr
->pxlen
)
1096 + (ipa_nonzero(fwaddr
) ? 16 : 0)
1099 ext
= lsab_allocz(p
, bsize
);
1100 ext
->metric
= metric
& LSA_METRIC_MASK
;
1101 u32
*buf
= ext
->rest
;
1103 buf
= ospf3_put_prefix(buf
, nf
->fn
.addr
, pbit
? OPT_PX_P
: 0, 0);
1106 ext
->metric
|= LSA_EXT3_EBIT
;
1108 if (ipa_nonzero(fwaddr
))
1110 ext
->metric
|= LSA_EXT3_FBIT
;
1111 buf
= ospf3_put_addr(buf
, fwaddr
);
1116 ext
->metric
|= LSA_EXT3_TBIT
;
1122 * originate_ext_lsa - new route received from nest and filters
1123 * @p: OSPF protocol instance
1124 * @oa: ospf_area for which LSA is originated
1125 * @nf: network prefix and mask
1126 * @mode: the mode of the LSA (LSA_M_EXPORT or LSA_M_RTCALC)
1127 * @metric: the metric of a route
1128 * @ebit: E-bit for route metric (bool)
1129 * @fwaddr: the forwarding address
1130 * @tag: the route tag
1131 * @pbit: P-bit for NSSA LSAs (bool), ignored for external LSAs
1133 * If I receive a message that new route is installed, I try to originate an
1134 * external LSA. If @oa is an NSSA area, NSSA-LSA is originated instead.
1135 * @oa should not be a stub area. @src does not specify whether the LSA
1136 * is external or NSSA, but it specifies the source of origination -
1137 * the export from ospf_rt_notify(), or the NSSA-EXT translation.
1140 ospf_originate_ext_lsa(struct ospf_proto
*p
, struct ospf_area
*oa
, ort
*nf
, u8 mode
,
1141 u32 metric
, u32 ebit
, ip_addr fwaddr
, u32 tag
, int pbit
)
1143 struct ospf_new_lsa lsa
= {
1144 .type
= oa
? LSA_T_NSSA
: LSA_T_EXT
,
1145 .mode
= mode
, /* LSA_M_EXPORT or LSA_M_RTCALC */
1146 .dom
= oa
? oa
->areaid
: 0,
1147 .id
= ort_to_lsaid(p
, nf
),
1148 .opts
= oa
? (pbit
? OPT_P
: 0) : OPT_E
,
1153 prepare_ext2_lsa_body(p
, nf
->fn
.addr
->pxlen
, metric
, ebit
, fwaddr
, tag
);
1155 prepare_ext3_lsa_body(p
, nf
, metric
, ebit
, fwaddr
, tag
, oa
&& pbit
);
1157 ospf_originate_lsa(p
, &lsa
);
1160 static struct top_hash_entry
*
1161 ospf_hash_find_(struct top_graph
*f
, u32 domain
, u32 lsa
, u32 rtr
, u32 type
);
1164 ospf_flush_ext_lsa(struct ospf_proto
*p
, struct ospf_area
*oa
, ort
*nf
)
1166 struct top_hash_entry
*en
;
1168 u32 type
= oa
? LSA_T_NSSA
: LSA_T_EXT
;
1169 u32 dom
= oa
? oa
->areaid
: 0;
1170 u32 id
= ort_to_lsaid(p
, nf
);
1172 en
= ospf_hash_find_(p
->gr
, dom
, id
, p
->router_id
, type
);
1174 if (!en
|| (en
->nf
!= nf
))
1177 ospf_flush_lsa(p
, en
);
1181 use_gw_for_fwaddr(struct ospf_proto
*p
, ip_addr gw
, struct iface
*iface
)
1183 struct ospf_iface
*ifa
;
1185 if (ipa_zero(gw
) || ipa_is_link_local(gw
))
1188 WALK_LIST(ifa
, p
->iface_list
)
1189 if ((ifa
->iface
== iface
) &&
1190 (!ospf_is_v2(p
) || ipa_in_netX(gw
, &ifa
->addr
->prefix
)))
1196 static inline ip_addr
1197 find_surrogate_fwaddr(struct ospf_proto
*p
, struct ospf_area
*oa
)
1199 struct ospf_iface
*ifa
;
1200 struct ifa
*a
, *cur_addr
= NULL
;
1203 /* RFC 3101 2.3 - surrogate forwarding address selection */
1205 WALK_LIST(ifa
, p
->iface_list
)
1207 if ((ifa
->oa
!= oa
) ||
1208 (ifa
->type
== OSPF_IT_VLINK
))
1214 if (a
->flags
& IA_PEER
)
1217 np
= (a
->flags
& IA_HOST
) ? 3 : (ifa
->stub
? 2 : 1);
1226 WALK_LIST(a
, ifa
->iface
->addrs
)
1228 if ((a
->prefix
.type
!= ospf_get_af(p
)) ||
1229 (a
->flags
& IA_SECONDARY
) ||
1230 (a
->flags
& IA_PEER
) ||
1231 (a
->scope
<= SCOPE_LINK
))
1234 np
= (a
->flags
& IA_HOST
) ? 3 : (ifa
->stub
? 2 : 1);
1244 return cur_addr
? cur_addr
->ip
: IPA_NONE
;
1248 ospf_rt_notify(struct proto
*P
, struct channel
*ch UNUSED
, net
*n
, rte
*new, rte
*old UNUSED
)
1250 struct ospf_proto
*p
= (struct ospf_proto
*) P
;
1251 struct ospf_area
*oa
= NULL
; /* non-NULL for NSSA-LSA */
1255 * There are several posibilities:
1256 * 1) router in regular area - originate external LSA with global scope
1257 * 2) router in NSSA area - originate area-specific NSSA-LSA
1258 * 3) router in stub area - cannot export routes
1259 * 4) area border router - same as (1), it is attached to backbone
1262 if ((p
->areano
== 1) && oa_is_nssa(HEAD(p
->area_list
)))
1263 oa
= HEAD(p
->area_list
);
1267 nf
= fib_find(&p
->rtf
, n
->n
.addr
);
1269 if (!nf
|| !nf
->external_rte
)
1272 ospf_flush_ext_lsa(p
, oa
, nf
);
1273 nf
->external_rte
= 0;
1275 /* Old external route might blocked some NSSA translation */
1276 if ((p
->areano
> 1) && rt_is_nssa(nf
) && nf
->n
.oa
->translate
)
1277 ospf_schedule_rtcalc(p
);
1284 /* Get route attributes */
1285 rta
*a
= new->attrs
;
1286 eattr
*m1a
= ea_find(a
->eattrs
, EA_OSPF_METRIC1
);
1287 eattr
*m2a
= ea_find(a
->eattrs
, EA_OSPF_METRIC2
);
1288 uint m1
= m1a
? m1a
->u
.data
: 0;
1289 uint m2
= m2a
? m2a
->u
.data
: 10000;
1291 if (m1
> LSINFINITY
)
1293 log(L_WARN
"%s: Invalid ospf_metric1 value %u for route %N",
1294 p
->p
.name
, m1
, n
->n
.addr
);
1298 if (m2
> LSINFINITY
)
1300 log(L_WARN
"%s: Invalid ospf_metric2 value %u for route %N",
1301 p
->p
.name
, m2
, n
->n
.addr
);
1305 /* Ensure monotonicity of metric if both m1 and m2 are used */
1306 if ((m1
> 0) && (m2
< LSINFINITY
))
1309 uint ebit
= m2a
|| !m1a
;
1310 uint metric
= ebit
? m2
: m1
;
1311 uint tag
= ea_get_int(a
->eattrs
, EA_OSPF_TAG
, 0);
1313 ip_addr fwd
= IPA_NONE
;
1314 if ((a
->dest
== RTD_UNICAST
) && use_gw_for_fwaddr(p
, a
->nh
.gw
, a
->nh
.iface
))
1317 /* NSSA-LSA with P-bit set must have non-zero forwarding address */
1318 if (oa
&& ipa_zero(fwd
))
1320 fwd
= find_surrogate_fwaddr(p
, oa
);
1324 log(L_ERR
"%s: Cannot find forwarding address for NSSA-LSA %N",
1325 p
->p
.name
, n
->n
.addr
);
1330 nf
= fib_get(&p
->rtf
, n
->n
.addr
);
1331 ospf_originate_ext_lsa(p
, oa
, nf
, LSA_M_EXPORT
, metric
, ebit
, fwd
, tag
, 1);
1332 nf
->external_rte
= 1;
1337 * Link-LSA handling (assume OSPFv3)
1342 lsab_put_prefix(struct ospf_proto
*p
, net_addr
*n
, u32 cost
)
1344 void *buf
= lsab_alloc(p
, IPV6_PREFIX_SPACE(net_pxlen(n
)));
1345 uint max
= (n
->type
== NET_IP4
) ? IP4_MAX_PREFIX_LENGTH
: IP6_MAX_PREFIX_LENGTH
;
1346 u8 flags
= (net_pxlen(n
) < max
) ? 0 : OPT_PX_LA
;
1347 ospf3_put_prefix(buf
, n
, flags
, cost
);
1351 prepare_link_lsa_body(struct ospf_proto
*p
, struct ospf_iface
*ifa
)
1353 ip_addr nh
= ospf_is_ip4(p
) ? IPA_NONE
: ifa
->addr
->ip
;
1356 /* Preallocating space for header */
1357 ASSERT(p
->lsab_used
== 0);
1358 lsab_allocz(p
, sizeof(struct ospf_lsa_link
));
1361 WALK_LIST(a
, ifa
->iface
->addrs
)
1363 if ((a
->prefix
.type
!= ospf_get_af(p
)) ||
1364 (a
->flags
& IA_SECONDARY
) ||
1365 (a
->scope
<= SCOPE_LINK
))
1368 if (ospf_is_ip4(p
) && ipa_zero(nh
))
1371 lsab_put_prefix(p
, &a
->prefix
, 0);
1375 /* Filling the preallocated header */
1376 struct ospf_lsa_link
*ll
= p
->lsab
;
1377 ll
->options
= ifa
->oa
->options
| (ifa
->priority
<< 24);
1378 ll
->lladdr
= ospf_is_ip4(p
) ? ospf3_4to6(ipa_to_ip4(nh
)) : ipa_to_ip6(nh
);
1382 log(L_ERR
"%s: Cannot find next hop address for %s", p
->p
.name
, ifa
->ifname
);
1386 ospf_originate_link_lsa(struct ospf_proto
*p
, struct ospf_iface
*ifa
)
1391 struct ospf_new_lsa lsa
= {
1393 .dom
= ifa
->iface_id
,
1394 .id
= ifa
->iface_id
,
1398 OSPF_TRACE(D_EVENTS
, "Updating link state for %s (Id: %R)", ifa
->ifname
, lsa
.id
);
1400 prepare_link_lsa_body(p
, ifa
);
1402 ifa
->link_lsa
= ospf_originate_lsa(p
, &lsa
);
1407 * Prefix-Rt-LSA handling (assume OSPFv3)
1408 * Type = LSA_T_PREFIX, referred type = LSA_T_RT
1412 prepare_prefix_rt_lsa_body(struct ospf_proto
*p
, struct ospf_area
*oa
)
1414 struct ospf_config
*cf
= (struct ospf_config
*) (p
->p
.cf
);
1415 struct ospf_iface
*ifa
;
1416 struct ospf_lsa_prefix
*lp
;
1421 ASSERT(p
->lsab_used
== 0);
1422 lp
= lsab_allocz(p
, sizeof(struct ospf_lsa_prefix
));
1423 lp
->ref_type
= LSA_T_RT
;
1425 lp
->ref_rt
= p
->router_id
;
1426 lp
= NULL
; /* buffer might be reallocated later */
1428 WALK_LIST(ifa
, p
->iface_list
)
1430 if ((ifa
->oa
!= oa
) || (ifa
->type
== OSPF_IT_VLINK
) || (ifa
->state
== OSPF_IS_DOWN
))
1433 ifa
->px_pos_beg
= i
;
1435 if ((ifa
->type
== OSPF_IT_BCAST
) ||
1436 (ifa
->type
== OSPF_IT_NBMA
))
1437 net_lsa
= bcast_net_active(ifa
);
1442 WALK_LIST(a
, ifa
->iface
->addrs
)
1444 if ((a
->prefix
.type
!= ospf_get_af(p
)) ||
1445 (a
->flags
& IA_SECONDARY
) ||
1446 (a
->flags
& IA_PEER
) ||
1447 (a
->scope
<= SCOPE_LINK
))
1450 if (((a
->prefix
.pxlen
< IP6_MAX_PREFIX_LENGTH
) && net_lsa
) ||
1451 configured_stubnet(oa
, a
))
1454 if ((a
->flags
& IA_HOST
) ||
1455 (ifa
->state
== OSPF_IS_LOOP
) ||
1456 (ifa
->type
== OSPF_IT_PTMP
))
1458 net_addr_ip6 net
= NET_ADDR_IP6(a
->ip
, IP6_MAX_PREFIX_LENGTH
);
1459 lsab_put_prefix(p
, (net_addr
*) &net
, 0);
1463 lsab_put_prefix(p
, &a
->prefix
, ifa
->cost
);
1467 ifa
->px_pos_end
= i
;
1470 struct ospf_stubnet_config
*sn
;
1471 WALK_LIST(sn
, oa
->ac
->stubnet_list
)
1474 lsab_put_prefix(p
, &sn
->prefix
, sn
->cost
);
1475 if (sn
->prefix
.pxlen
== IP6_MAX_PREFIX_LENGTH
)
1480 /* If there are some configured vlinks, find some global address
1481 (even from another area), which will be used as a vlink endpoint. */
1482 if (!EMPTY_LIST(cf
->vlink_list
) && !host_addr
&& ospf_is_ip6(p
))
1484 WALK_LIST(ifa
, p
->iface_list
)
1486 if ((ifa
->type
== OSPF_IT_VLINK
) || (ifa
->state
== OSPF_IS_DOWN
))
1490 WALK_LIST(a
, ifa
->iface
->addrs
)
1492 if ((a
->prefix
.type
!= NET_IP6
) ||
1493 (a
->flags
& IA_SECONDARY
) ||
1494 (a
->scope
<= SCOPE_LINK
))
1498 net_addr_ip6 net
= NET_ADDR_IP6(a
->ip
, IP6_MAX_PREFIX_LENGTH
);
1499 lsab_put_prefix(p
, (net_addr
*) &net
, 0);
1512 ospf_originate_prefix_rt_lsa(struct ospf_proto
*p
, struct ospf_area
*oa
)
1517 struct ospf_new_lsa lsa
= {
1518 .type
= LSA_T_PREFIX
,
1523 prepare_prefix_rt_lsa_body(p
, oa
);
1525 ospf_originate_lsa(p
, &lsa
);
1530 * Prefix-Net-LSA handling (assume OSPFv3)
1531 * Type = LSA_T_PREFIX, referred type = LSA_T_NET
1535 prefix_space(u32
*buf
)
1537 int pxl
= *buf
>> 24;
1538 return IPV6_PREFIX_SPACE(pxl
);
1542 prefix_same(u32
*b1
, u32
*b2
)
1544 int pxl1
= *b1
>> 24;
1545 int pxl2
= *b2
>> 24;
1551 pxs
= IPV6_PREFIX_WORDS(pxl1
);
1552 for (i
= 1; i
< pxs
; i
++)
1560 prefix_advance(u32
*buf
)
1562 int pxl
= *buf
>> 24;
1563 return buf
+ IPV6_PREFIX_WORDS(pxl
);
1566 /* FIXME eliminate items with LA bit set? see 4.4.3.9 */
1568 add_prefix(struct ospf_proto
*p
, u32
*px
, int offset
, int *pxc
)
1570 u32
*pxl
= lsab_offset(p
, offset
);
1572 for (i
= 0; i
< *pxc
; pxl
= prefix_advance(pxl
), i
++)
1573 if (prefix_same(px
, pxl
))
1575 /* Options should be logically OR'ed together */
1576 *pxl
|= (*px
& 0x00FF0000);
1580 ASSERT(pxl
== lsab_end(p
));
1582 int pxspace
= prefix_space(px
);
1583 pxl
= lsab_alloc(p
, pxspace
);
1584 memcpy(pxl
, px
, pxspace
);
1585 *pxl
&= 0xFFFF0000; /* Set metric to zero */
1590 add_link_lsa(struct ospf_proto
*p
, struct ospf_lsa_link
*ll
, int offset
, int *pxc
)
1592 u32
*pxb
= ll
->rest
;
1595 for (j
= 0; j
< ll
->pxcount
; pxb
= prefix_advance(pxb
), j
++)
1597 u8 pxlen
= (pxb
[0] >> 24);
1598 u8 pxopts
= (pxb
[0] >> 16);
1600 /* Skip NU or LA prefixes */
1601 if (pxopts
& (OPT_PX_NU
| OPT_PX_LA
))
1604 /* Skip link-local prefixes */
1605 if (ospf_is_ip6(p
) && (pxlen
>= 10) && ((pxb
[1] & 0xffc00000) == 0xfe800000))
1608 add_prefix(p
, pxb
, offset
, pxc
);
1613 prepare_prefix_net_lsa_body(struct ospf_proto
*p
, struct ospf_iface
*ifa
)
1615 struct ospf_lsa_prefix
*lp
;
1616 struct ospf_neighbor
*n
;
1617 struct top_hash_entry
*en
;
1620 ASSERT(p
->lsab_used
== 0);
1621 lp
= lsab_allocz(p
, sizeof(struct ospf_lsa_prefix
));
1622 lp
->ref_type
= LSA_T_NET
;
1623 lp
->ref_id
= ifa
->net_lsa
->lsa
.id
;
1624 lp
->ref_rt
= p
->router_id
;
1625 lp
= NULL
; /* buffer might be reallocated later */
1628 offset
= p
->lsab_used
;
1630 /* Find all Link LSAs associated with the link and merge their prefixes */
1631 if (en
= ifa
->link_lsa
)
1632 add_link_lsa(p
, en
->next_lsa_body
?: en
->lsa_body
, offset
, &pxc
);
1634 WALK_LIST(n
, ifa
->neigh_list
)
1635 if ((n
->state
== NEIGHBOR_FULL
) &&
1636 (en
= ospf_hash_find(p
->gr
, ifa
->iface_id
, n
->iface_id
, n
->rid
, LSA_T_LINK
)))
1637 add_link_lsa(p
, en
->lsa_body
, offset
, &pxc
);
1644 ospf_originate_prefix_net_lsa(struct ospf_proto
*p
, struct ospf_iface
*ifa
)
1649 struct ospf_new_lsa lsa
= {
1650 .type
= LSA_T_PREFIX
,
1651 .dom
= ifa
->oa
->areaid
,
1652 .id
= ifa
->iface_id
,
1656 prepare_prefix_net_lsa_body(p
, ifa
);
1658 ifa
->pxn_lsa
= ospf_originate_lsa(p
, &lsa
);
1661 static inline int breaks_minlsinterval(struct top_hash_entry
*en
)
1662 { return en
&& (en
->lsa
.age
< LSA_MAXAGE
) && (lsa_inst_age(en
) < MINLSINTERVAL
); }
1665 ospf_update_topology(struct ospf_proto
*p
)
1667 struct ospf_area
*oa
;
1668 struct ospf_iface
*ifa
;
1670 WALK_LIST(oa
, p
->area_list
)
1672 if (oa
->update_rt_lsa
)
1675 * Generally, MinLSInterval is enforced in ospf_do_originate_lsa(), but
1676 * origination of (prefix) router LSA is a special case. We do not want to
1677 * prepare a new router LSA body and then postpone it in en->next_lsa_body
1678 * for later origination, because there are side effects (updates of
1679 * rt_pos_* and px_pos_* in ospf_iface structures) during that, which may
1680 * confuse routing table calculation if executed after LSA body
1681 * preparation but before final LSA origination (as rtcalc would use
1682 * current rt_pos_* indexes but the old router LSA body).
1684 * Here, we ensure that MinLSInterval is observed and we do not even try
1685 * to originate these LSAs if it is not. Therefore, origination, when
1686 * requested, will succeed unless there is also a seqnum wrapping, which
1687 * is not a problem because in that case rtcalc is blocked by MaxAge.
1690 if (breaks_minlsinterval(oa
->rt
) || breaks_minlsinterval(oa
->pxr_lsa
))
1693 ospf_originate_rt_lsa(p
, oa
);
1694 ospf_originate_prefix_rt_lsa(p
, oa
);
1695 oa
->update_rt_lsa
= 0;
1699 WALK_LIST(ifa
, p
->iface_list
)
1701 if (ifa
->type
== OSPF_IT_VLINK
)
1704 if (ifa
->update_link_lsa
)
1706 if ((ifa
->state
> OSPF_IS_LOOP
) && !ifa
->link_lsa_suppression
)
1707 ospf_originate_link_lsa(p
, ifa
);
1709 ospf_flush2_lsa(p
, &ifa
->link_lsa
);
1711 ifa
->update_link_lsa
= 0;
1714 if (ifa
->update_net_lsa
)
1716 if ((ifa
->state
== OSPF_IS_DR
) && (ifa
->fadj
> 0))
1718 ospf_originate_net_lsa(p
, ifa
);
1719 ospf_originate_prefix_net_lsa(p
, ifa
);
1723 ospf_flush2_lsa(p
, &ifa
->net_lsa
);
1724 ospf_flush2_lsa(p
, &ifa
->pxn_lsa
);
1727 ifa
->update_net_lsa
= 0;
1734 ospf_top_ht_alloc(struct top_graph
*f
)
1736 f
->hash_size
= 1 << f
->hash_order
;
1737 f
->hash_mask
= f
->hash_size
- 1;
1738 if (f
->hash_order
> HASH_HI_MAX
- HASH_HI_STEP
)
1739 f
->hash_entries_max
= ~0;
1741 f
->hash_entries_max
= f
->hash_size HASH_HI_MARK
;
1742 if (f
->hash_order
< HASH_LO_MIN
+ HASH_LO_STEP
)
1743 f
->hash_entries_min
= 0;
1745 f
->hash_entries_min
= f
->hash_size HASH_LO_MARK
;
1746 DBG("Allocating OSPF hash of order %d: %d hash_entries, %d low, %d high\n",
1747 f
->hash_order
, f
->hash_size
, f
->hash_entries_min
, f
->hash_entries_max
);
1749 mb_alloc(f
->pool
, f
->hash_size
* sizeof(struct top_hash_entry
*));
1750 bzero(f
->hash_table
, f
->hash_size
* sizeof(struct top_hash_entry
*));
1754 ospf_top_ht_free(struct top_hash_entry
**h
)
1760 ospf_top_hash_u32(u32 a
)
1762 /* Shamelessly stolen from IP address hashing in ipv4.h */
1769 ospf_top_hash(struct top_graph
*f
, u32 domain
, u32 lsaid
, u32 rtrid
, u32 type
)
1771 /* In OSPFv2, we don't know Router ID when looking for network LSAs.
1772 In OSPFv3, we don't know LSA ID when looking for router LSAs.
1773 In both cases, there is (usually) just one (or small number)
1774 appropriate LSA, so we just clear unknown part of key. */
1776 return (((f
->ospf2
&& (type
== LSA_T_NET
)) ? 0 : ospf_top_hash_u32(rtrid
)) +
1777 ((!f
->ospf2
&& (type
== LSA_T_RT
)) ? 0 : ospf_top_hash_u32(lsaid
)) +
1778 type
+ domain
) & f
->hash_mask
;
1781 return (ospf_top_hash_u32(lsaid) + ospf_top_hash_u32(rtrid) +
1782 type + areaid) & f->hash_mask;
1787 * ospf_top_new - allocated new topology database
1788 * @p: OSPF protocol instance
1789 * @pool: pool for allocation
1791 * This dynamically hashed structure is used for keeping LSAs. Mainly it is used
1792 * for the LSA database of the OSPF protocol, but also for LSA retransmission
1793 * and request lists of OSPF neighbors.
1796 ospf_top_new(struct ospf_proto
*p
, pool
*pool
)
1798 struct top_graph
*f
;
1800 f
= mb_allocz(pool
, sizeof(struct top_graph
));
1802 f
->hash_slab
= sl_new(f
->pool
, sizeof(struct top_hash_entry
));
1803 f
->hash_order
= HASH_DEF_ORDER
;
1804 ospf_top_ht_alloc(f
);
1805 f
->hash_entries
= 0;
1806 f
->hash_entries_min
= 0;
1807 f
->ospf2
= ospf_is_v2(p
);
1812 ospf_top_free(struct top_graph
*f
)
1814 rfree(f
->hash_slab
);
1815 ospf_top_ht_free(f
->hash_table
);
1820 ospf_top_rehash(struct top_graph
*f
, int step
)
1822 struct top_hash_entry
**n
, **oldt
, **newt
, *e
, *x
;
1825 oldn
= f
->hash_size
;
1826 oldt
= f
->hash_table
;
1827 DBG("re-hashing topology hash from order %d to %d\n", f
->hash_order
,
1828 f
->hash_order
+ step
);
1829 f
->hash_order
+= step
;
1830 ospf_top_ht_alloc(f
);
1831 newt
= f
->hash_table
;
1833 for (oldh
= 0; oldh
< oldn
; oldh
++)
1839 n
= newt
+ ospf_top_hash(f
, e
->domain
, e
->lsa
.id
, e
->lsa
.rt
, e
->lsa_type
);
1845 ospf_top_ht_free(oldt
);
1848 static struct top_hash_entry
*
1849 ospf_hash_find_(struct top_graph
*f
, u32 domain
, u32 lsa
, u32 rtr
, u32 type
)
1851 struct top_hash_entry
*e
;
1852 e
= f
->hash_table
[ospf_top_hash(f
, domain
, lsa
, rtr
, type
)];
1854 while (e
&& (e
->lsa
.id
!= lsa
|| e
->lsa
.rt
!= rtr
||
1855 e
->lsa_type
!= type
|| e
->domain
!= domain
))
1861 struct top_hash_entry
*
1862 ospf_hash_find(struct top_graph
*f
, u32 domain
, u32 lsa
, u32 rtr
, u32 type
)
1864 struct top_hash_entry
*e
= ospf_hash_find_(f
, domain
, lsa
, rtr
, type
);
1866 /* Hide hash entry with empty lsa_body */
1867 return (e
&& e
->lsa_body
) ? e
: NULL
;
1870 /* In OSPFv2, lsa.id is the same as lsa.rt for router LSA. In OSPFv3, we don't know
1871 lsa.id when looking for router LSAs. We return matching LSA with smallest lsa.id. */
1872 struct top_hash_entry
*
1873 ospf_hash_find_rt(struct top_graph
*f
, u32 domain
, u32 rtr
)
1875 struct top_hash_entry
*rv
= NULL
;
1876 struct top_hash_entry
*e
;
1877 /* We can put rtr for lsa.id to hash fn, it is ignored in OSPFv3 */
1878 e
= f
->hash_table
[ospf_top_hash(f
, domain
, rtr
, rtr
, LSA_T_RT
)];
1882 if (e
->lsa
.rt
== rtr
&& e
->lsa_type
== LSA_T_RT
&& e
->domain
== domain
&& e
->lsa_body
)
1884 if (f
->ospf2
&& (e
->lsa
.id
== rtr
))
1886 if (!f
->ospf2
&& (!rv
|| e
->lsa
.id
< rv
->lsa
.id
))
1896 * ospf_hash_find_rt3_first() and ospf_hash_find_rt3_next() are used exclusively
1897 * for lsa_walk_rt_init(), lsa_walk_rt(), therefore they skip MaxAge entries.
1899 static inline struct top_hash_entry
*
1900 find_matching_rt3(struct top_hash_entry
*e
, u32 domain
, u32 rtr
)
1902 while (e
&& (e
->lsa
.rt
!= rtr
|| e
->lsa_type
!= LSA_T_RT
||
1903 e
->domain
!= domain
|| e
->lsa
.age
== LSA_MAXAGE
))
1908 struct top_hash_entry
*
1909 ospf_hash_find_rt3_first(struct top_graph
*f
, u32 domain
, u32 rtr
)
1911 struct top_hash_entry
*e
;
1912 e
= f
->hash_table
[ospf_top_hash(f
, domain
, 0, rtr
, LSA_T_RT
)];
1913 return find_matching_rt3(e
, domain
, rtr
);
1916 struct top_hash_entry
*
1917 ospf_hash_find_rt3_next(struct top_hash_entry
*e
)
1919 return find_matching_rt3(e
->next
, e
->domain
, e
->lsa
.rt
);
1922 /* In OSPFv2, we don't know Router ID when looking for network LSAs.
1923 There should be just one, so we find any match. */
1924 struct top_hash_entry
*
1925 ospf_hash_find_net2(struct top_graph
*f
, u32 domain
, u32 id
)
1927 struct top_hash_entry
*e
;
1928 e
= f
->hash_table
[ospf_top_hash(f
, domain
, id
, 0, LSA_T_NET
)];
1930 while (e
&& (e
->lsa
.id
!= id
|| e
->lsa_type
!= LSA_T_NET
||
1931 e
->domain
!= domain
|| e
->lsa_body
== NULL
))
1938 struct top_hash_entry
*
1939 ospf_hash_get(struct top_graph
*f
, u32 domain
, u32 lsa
, u32 rtr
, u32 type
)
1941 struct top_hash_entry
**ee
;
1942 struct top_hash_entry
*e
;
1944 ee
= f
->hash_table
+ ospf_top_hash(f
, domain
, lsa
, rtr
, type
);
1947 while (e
&& (e
->lsa
.id
!= lsa
|| e
->lsa
.rt
!= rtr
||
1948 e
->lsa_type
!= type
|| e
->domain
!= domain
))
1954 e
= sl_alloc(f
->hash_slab
);
1955 bzero(e
, sizeof(struct top_hash_entry
));
1958 e
->dist
= LSINFINITY
;
1959 e
->lsa
.type_raw
= type
;
1962 e
->lsa
.sn
= LSA_ZEROSEQNO
;
1967 if (f
->hash_entries
++ > f
->hash_entries_max
)
1968 ospf_top_rehash(f
, HASH_HI_STEP
);
1973 ospf_hash_delete(struct top_graph
*f
, struct top_hash_entry
*e
)
1975 struct top_hash_entry
**ee
= f
->hash_table
+
1976 ospf_top_hash(f
, e
->domain
, e
->lsa
.id
, e
->lsa
.rt
, e
->lsa_type
);
1983 sl_free(f
->hash_slab
, e
);
1984 if (f
->hash_entries
-- < f
->hash_entries_min
)
1985 ospf_top_rehash(f
, -HASH_LO_STEP
);
1988 ee
= &((*ee
)->next
);
1990 bug("ospf_hash_delete() called for invalid node");
1995 ospf_dump_lsa(struct top_hash_entry *he, struct proto *p)
1998 struct ospf_lsa_rt *rt = NULL;
1999 struct ospf_lsa_rt_link *rr = NULL;
2000 struct ospf_lsa_net *ln = NULL;
2004 OSPF_TRACE(D_EVENTS, "- %1x %-1R %-1R %4u 0x%08x 0x%04x %-1R",
2005 he->lsa.type, he->lsa.id, he->lsa.rt, he->lsa.age, he->lsa.sn,
2006 he->lsa.checksum, he->domain);
2009 switch (he->lsa.type)
2013 rr = (struct ospf_lsa_rt_link *) (rt + 1);
2015 for (i = 0; i < lsa_rt_items(&he->lsa); i++)
2016 OSPF_TRACE(D_EVENTS, " - %1x %-1R %-1R %5u",
2017 rr[i].type, rr[i].id, rr[i].data, rr[i].metric);
2022 rts = (u32 *) (ln + 1);
2024 for (i = 0; i < lsa_net_items(&he->lsa); i++)
2025 OSPF_TRACE(D_EVENTS, " - %-1R", rts[i]);
2034 ospf_top_dump(struct top_graph *f, struct proto *p)
2037 OSPF_TRACE(D_EVENTS, "Hash entries: %d", f->hash_entries);
2039 for (i = 0; i < f->hash_size; i++)
2041 struct top_hash_entry *e;
2042 for (e = f->hash_table[i]; e != NULL; e = e->next)
2043 ospf_dump_lsa(e, p);