]>
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>
7 * Can be freely distributed and used under the terms of the GNU GPL.
10 #include "nest/bird.h"
11 #include "lib/string.h"
15 #define HASH_DEF_ORDER 6
16 #define HASH_HI_MARK *4
17 #define HASH_HI_STEP 2
18 #define HASH_HI_MAX 16
19 #define HASH_LO_MARK /5
20 #define HASH_LO_STEP 2
23 void originate_prefix_rt_lsa(struct ospf_area
*oa
);
24 void originate_prefix_net_lsa(struct ospf_iface
*ifa
);
25 void flush_prefix_net_lsa(struct ospf_iface
*ifa
);
28 #define ipa_to_rid(x) _I(x)
30 #define ipa_to_rid(x) _I3(x)
36 fibnode_to_lsaid(struct proto_ospf
*po
, struct fib_node
*fn
)
38 /* We have to map IP prefixes to u32 in such manner that resulting
39 u32 interpreted as IP address is a member of given
40 prefix. Therefore, /32 prefix have to be mapped on itself.
41 All received prefixes have to be mapped on different u32s.
43 We have an assumption that if there is nontrivial (non-/32)
44 network prefix, then there is not /32 prefix for the first
45 and the last IP address of the network (these are usually
46 reserved, therefore it is not an important restriction).
47 The network prefix is mapped to the first or the last
48 IP address in the manner that disallow collisions - we
49 use IP address that cannot be used by parent prefix.
52 192.168.0.0/24 maps to 192.168.0.255
53 192.168.1.0/24 maps to 192.168.1.0
54 because 192.168.0.0 and 192.168.1.255 might be used by
57 This is not compatible with older RFC 1583, so we have an option
58 to the RFC 1583 compatible assignment (that always uses the first
59 address) which disallows subnetting.
61 Appendig E of RFC 2328 suggests different algorithm, that tries
62 to maximize both compatibility and subnetting. But as it is not
63 possible to have both reliably and the suggested algorithm was
64 unnecessary complicated and it does crazy things like changing
65 LSA ID for a network because different network appeared, we
66 choose a different way. */
68 u32 id
= _I(fn
->prefix
);
70 if ((po
->rfc1583
) || (fn
->pxlen
== 0) || (fn
->pxlen
== 32))
73 if (id
& (1 << (32 - fn
->pxlen
)))
76 return id
| ~u32_mkmask(fn
->pxlen
);
82 fibnode_to_lsaid(struct proto_ospf
*po
, struct fib_node
*fn
)
85 * In OSPFv3, it is simpler. There is not a requirement for
86 * membership of the result in the input network, so we just use a
87 * hash-based unique ID of a routing table entry for a route that
88 * originated given LSA. For ext-LSA, it is an imported route in the
89 * nest's routing table (p->table). For summary-LSA, it is a
90 * 'source' route in the protocol internal routing table (po->rtf).
99 lsab_alloc(struct proto_ospf
*po
, unsigned size
)
101 unsigned offset
= po
->lsab_used
;
102 po
->lsab_used
+= size
;
103 if (po
->lsab_used
> po
->lsab_size
)
105 po
->lsab_size
= MAX(po
->lsab_used
, 2 * po
->lsab_size
);
106 po
->lsab
= po
->lsab
? mb_realloc(po
->lsab
, po
->lsab_size
):
107 mb_alloc(po
->proto
.pool
, po
->lsab_size
);
109 return ((byte
*) po
->lsab
) + offset
;
113 lsab_allocz(struct proto_ospf
*po
, unsigned size
)
115 void *r
= lsab_alloc(po
, size
);
121 lsab_flush(struct proto_ospf
*po
)
123 void *r
= mb_alloc(po
->proto
.pool
, po
->lsab_used
);
124 memcpy(r
, po
->lsab
, po
->lsab_used
);
130 lsab_offset(struct proto_ospf
*po
, unsigned offset
)
132 return ((byte
*) po
->lsab
) + offset
;
136 lsab_end(struct proto_ospf
*po
)
138 return ((byte
*) po
->lsab
) + po
->lsab_used
;
142 get_seqnum(struct top_hash_entry
*en
)
145 return LSA_INITSEQNO
;
147 if (en
->lsa
.sn
== LSA_MAXSEQNO
)
149 log(L_WARN
"OSPF: Premature origination of LSA (Type: %04x, Id: %R, Rt: %R)",
150 en
->lsa
.type
, en
->lsa
.id
, en
->lsa
.rt
);
151 return LSA_INITSEQNO
;
154 return en
->lsa
.sn
+ 1;
159 configured_stubnet(struct ospf_area
*oa
, struct ifa
*a
)
164 /* Does not work for IA_PEER addresses, but it is not called on these */
165 struct ospf_stubnet_config
*sn
;
166 WALK_LIST(sn
, oa
->ac
->stubnet_list
)
170 if (ipa_in_net(a
->prefix
, sn
->px
.addr
, sn
->px
.len
) && (a
->pxlen
>= sn
->px
.len
))
175 if (ipa_equal(a
->prefix
, sn
->px
.addr
) && (a
->pxlen
== sn
->px
.len
))
183 bcast_net_active(struct ospf_iface
*ifa
)
185 struct ospf_neighbor
*neigh
;
187 if (ifa
->state
== OSPF_IS_WAITING
)
190 WALK_LIST(neigh
, ifa
->neigh_list
)
192 if (neigh
->state
== NEIGHBOR_FULL
)
194 if (neigh
->rid
== ifa
->drid
)
197 if (ifa
->state
== OSPF_IS_DR
)
209 originate_rt_lsa_body(struct ospf_area
*oa
, u16
*length
)
211 struct proto_ospf
*po
= oa
->po
;
212 struct ospf_iface
*ifa
;
214 struct ospf_lsa_rt
*rt
;
215 struct ospf_lsa_rt_link
*ln
;
216 struct ospf_neighbor
*neigh
;
218 ASSERT(po
->lsab_used
== 0);
219 rt
= lsab_allocz(po
, sizeof(struct ospf_lsa_rt
));
224 rt
->options
|= OPT_RT_B
;
226 if ((po
->areano
> 1) && oa_is_nssa(oa
) && oa
->ac
->translator
)
227 rt
->options
|= OPT_RT_NT
;
229 if (po
->ebit
&& !oa_is_stub(oa
))
230 rt
->options
|= OPT_RT_E
;
232 rt
= NULL
; /* buffer might be reallocated later */
234 WALK_LIST(ifa
, po
->iface_list
)
237 u32 link_cost
= po
->stub_router
? 0xffff : ifa
->cost
;
239 if ((ifa
->type
== OSPF_IT_VLINK
) && (ifa
->voa
== oa
) &&
240 (!EMPTY_LIST(ifa
->neigh_list
)))
242 neigh
= (struct ospf_neighbor
*) HEAD(ifa
->neigh_list
);
243 if ((neigh
->state
== NEIGHBOR_FULL
) && (ifa
->cost
<= 0xffff))
247 if ((ifa
->oa
!= oa
) || (ifa
->state
== OSPF_IS_DOWN
))
252 /* RFC2328 - 12.4.1.1-4 */
257 WALK_LIST(neigh
, ifa
->neigh_list
)
258 if (neigh
->state
== NEIGHBOR_FULL
)
260 ln
= lsab_alloc(po
, sizeof(struct ospf_lsa_rt_link
));
261 ln
->type
= LSART_PTP
;
265 * ln->data should be ifa->iface_id in case of no/ptp
266 * address (ifa->addr->flags & IA_PEER) on PTP link (see
267 * RFC 2328 12.4.1.1.), but the iface ID value has no use,
268 * while using IP address even in this case is here for
269 * compatibility with some broken implementations that use
270 * this address as a next-hop.
272 ln
->data
= ipa_to_u32(ifa
->addr
->ip
);
273 ln
->metric
= link_cost
;
281 if (bcast_net_active(ifa
))
283 ln
= lsab_alloc(po
, sizeof(struct ospf_lsa_rt_link
));
284 ln
->type
= LSART_NET
;
285 ln
->id
= ipa_to_u32(ifa
->drip
);
286 ln
->data
= ipa_to_u32(ifa
->addr
->ip
);
287 ln
->metric
= link_cost
;
295 neigh
= (struct ospf_neighbor
*) HEAD(ifa
->neigh_list
);
296 if ((!EMPTY_LIST(ifa
->neigh_list
)) && (neigh
->state
== NEIGHBOR_FULL
) && (ifa
->cost
<= 0xffff))
298 ln
= lsab_alloc(po
, sizeof(struct ospf_lsa_rt_link
));
299 ln
->type
= LSART_VLNK
;
301 ln
->data
= ipa_to_u32(ifa
->addr
->ip
);
302 ln
->metric
= link_cost
;
309 log("Unknown interface type %s", ifa
->ifname
);
315 /* Now we will originate stub area if there is no primary */
317 (ifa
->type
== OSPF_IT_VLINK
) ||
318 ((ifa
->addr
->flags
& IA_PEER
) && ! ifa
->cf
->stub
) ||
319 configured_stubnet(oa
, ifa
->addr
))
322 ln
= lsab_alloc(po
, sizeof(struct ospf_lsa_rt_link
));
323 if ((ifa
->addr
->flags
& IA_HOST
) ||
324 (ifa
->state
== OSPF_IS_LOOP
) ||
325 (ifa
->type
== OSPF_IT_PTMP
))
327 /* Host stub entry */
328 ln
->type
= LSART_STUB
;
329 ln
->id
= ipa_to_u32(ifa
->addr
->ip
);
330 ln
->data
= 0xffffffff;
336 /* Network stub entry */
337 ln
->type
= LSART_STUB
;
338 ln
->id
= ipa_to_u32(ifa
->addr
->prefix
);
339 ln
->data
= ipa_to_u32(ipa_mkmask(ifa
->addr
->pxlen
));
340 ln
->metric
= ifa
->cost
;
348 struct ospf_stubnet_config
*sn
;
350 WALK_LIST(sn
, oa
->ac
->stubnet_list
)
353 ln
= lsab_alloc(po
, sizeof(struct ospf_lsa_rt_link
));
354 ln
->type
= LSART_STUB
;
355 ln
->id
= ipa_to_u32(sn
->px
.addr
);
356 ln
->data
= ipa_to_u32(ipa_mkmask(sn
->px
.len
));
357 ln
->metric
= sn
->cost
;
366 rt
->options
|= OPT_RT_V
;
368 *length
= po
->lsab_used
+ sizeof(struct ospf_lsa_header
);
369 return lsab_flush(po
);
375 add_lsa_rt_link(struct proto_ospf
*po
, struct ospf_iface
*ifa
, u8 type
, u32 nif
, u32 id
)
377 struct ospf_lsa_rt_link
*ln
= lsab_alloc(po
, sizeof(struct ospf_lsa_rt_link
));
380 ln
->metric
= ifa
->cost
;
381 ln
->lif
= ifa
->iface_id
;
387 originate_rt_lsa_body(struct ospf_area
*oa
, u16
*length
)
389 struct proto_ospf
*po
= oa
->po
;
390 struct ospf_iface
*ifa
;
393 struct ospf_lsa_rt
*rt
;
394 struct ospf_neighbor
*neigh
;
396 ASSERT(po
->lsab_used
== 0);
397 rt
= lsab_allocz(po
, sizeof(struct ospf_lsa_rt
));
399 rt
->options
= oa
->options
& OPTIONS_MASK
;
402 rt
->options
|= OPT_RT_B
;
404 if ((po
->areano
> 1) && oa_is_nssa(oa
) && oa
->ac
->translator
)
405 rt
->options
|= OPT_RT_NT
;
407 if (po
->ebit
&& !oa_is_stub(oa
))
408 rt
->options
|= OPT_RT_E
;
410 rt
= NULL
; /* buffer might be reallocated later */
412 WALK_LIST(ifa
, po
->iface_list
)
414 if ((ifa
->type
== OSPF_IT_VLINK
) && (ifa
->voa
== oa
) &&
415 (!EMPTY_LIST(ifa
->neigh_list
)))
417 neigh
= (struct ospf_neighbor
*) HEAD(ifa
->neigh_list
);
418 if ((neigh
->state
== NEIGHBOR_FULL
) && (ifa
->cost
<= 0xffff))
422 if ((ifa
->oa
!= oa
) || (ifa
->state
== OSPF_IS_DOWN
))
427 /* RFC5340 - 4.4.3.2 */
432 WALK_LIST(neigh
, ifa
->neigh_list
)
433 if (neigh
->state
== NEIGHBOR_FULL
)
434 add_lsa_rt_link(po
, ifa
, LSART_PTP
, neigh
->iface_id
, neigh
->rid
), i
++;
439 if (bcast_net_active(ifa
))
440 add_lsa_rt_link(po
, ifa
, LSART_NET
, ifa
->dr_iface_id
, ifa
->drid
), i
++;
444 neigh
= (struct ospf_neighbor
*) HEAD(ifa
->neigh_list
);
445 if ((!EMPTY_LIST(ifa
->neigh_list
)) && (neigh
->state
== NEIGHBOR_FULL
) && (ifa
->cost
<= 0xffff))
446 add_lsa_rt_link(po
, ifa
, LSART_VLNK
, neigh
->iface_id
, neigh
->rid
), i
++;
450 log("Unknown interface type %s", ifa
->ifname
);
460 rt
->options
|= OPT_RT_V
;
463 *length
= po
->lsab_used
+ sizeof(struct ospf_lsa_header
);
464 return lsab_flush(po
);
470 * originate_rt_lsa - build new instance of router LSA
471 * @oa: ospf_area which is LSA built to
473 * It builds router LSA walking through all OSPF interfaces in
474 * specified OSPF area. This function is mostly called from
475 * area_disp(). Builds new LSA, increases sequence number (if old
476 * instance exists) and sets age of LSA to zero.
479 originate_rt_lsa(struct ospf_area
*oa
)
481 struct ospf_lsa_header lsa
;
482 struct proto_ospf
*po
= oa
->po
;
483 struct proto
*p
= &po
->proto
;
486 OSPF_TRACE(D_EVENTS
, "Originating router-LSA for area %R", oa
->areaid
);
492 lsa
.options
= oa
->options
;
493 lsa
.id
= po
->router_id
;
498 lsa
.rt
= po
->router_id
;
499 lsa
.sn
= get_seqnum(oa
->rt
);
500 u32 dom
= oa
->areaid
;
502 body
= originate_rt_lsa_body(oa
, &lsa
.length
);
503 lsasum_calculate(&lsa
, body
);
504 oa
->rt
= lsa_install_new(po
, &lsa
, dom
, body
);
505 ospf_lsupd_flood(po
, NULL
, NULL
, &lsa
, dom
, 1);
509 update_rt_lsa(struct ospf_area
*oa
)
511 struct proto_ospf
*po
= oa
->po
;
513 if ((oa
->rt
) && ((oa
->rt
->inst_t
+ MINLSINTERVAL
)) > now
)
516 * Tick is probably set to very low value. We cannot
517 * originate new LSA before MINLSINTERVAL. We will
518 * try to do it next tick.
521 originate_rt_lsa(oa
);
523 originate_prefix_rt_lsa(oa
);
531 originate_net_lsa_body(struct ospf_iface
*ifa
, u16
*length
,
532 struct proto_ospf
*po
)
535 struct ospf_neighbor
*n
;
536 struct ospf_lsa_net
*net
;
537 int nodes
= ifa
->fadj
+ 1;
539 net
= mb_alloc(po
->proto
.pool
, sizeof(struct ospf_lsa_net
)
540 + nodes
* sizeof(u32
));
543 net
->netmask
= ipa_mkmask(ifa
->addr
->pxlen
);
547 /* In OSPFv3, we would like to merge options from Link LSAs of added neighbors */
548 struct top_hash_entry
*en
;
552 net
->routers
[0] = po
->router_id
;
554 WALK_LIST(n
, ifa
->neigh_list
)
556 if (n
->state
== NEIGHBOR_FULL
)
559 en
= ospf_hash_find(po
->gr
, ifa
->iface_id
, n
->iface_id
, n
->rid
, LSA_T_LINK
);
561 options
|= ((struct ospf_lsa_link
*) en
->lsa_body
)->options
;
564 net
->routers
[i
] = n
->rid
;
571 net
->options
= options
& OPTIONS_MASK
;
574 *length
= sizeof(struct ospf_lsa_header
) + sizeof(struct ospf_lsa_net
)
575 + nodes
* sizeof(u32
);
581 * originate_net_lsa - originates of deletes network LSA
582 * @ifa: interface which is LSA originated for
584 * Interface counts number of adjacent neighbors. If this number is
585 * lower than one or interface is not in state %OSPF_IS_DR it deletes
586 * and premature ages instance of network LSA for specified interface.
587 * In other case, new instance of network LSA is originated.
590 originate_net_lsa(struct ospf_iface
*ifa
)
592 struct proto_ospf
*po
= ifa
->oa
->po
;
593 struct proto
*p
= &po
->proto
;
594 struct ospf_lsa_header lsa
;
595 u32 dom
= ifa
->oa
->areaid
;
599 OSPF_TRACE(D_EVENTS
, "Originating network-LSA for iface %s", ifa
->ifname
);
602 lsa
.type
= LSA_T_NET
;
605 lsa
.options
= ifa
->oa
->options
;
606 lsa
.id
= ipa_to_u32(ifa
->addr
->ip
);
608 lsa
.id
= ifa
->iface_id
;
611 lsa
.rt
= po
->router_id
;
612 lsa
.sn
= get_seqnum(ifa
->net_lsa
);
614 body
= originate_net_lsa_body(ifa
, &lsa
.length
, po
);
615 lsasum_calculate(&lsa
, body
);
616 ifa
->net_lsa
= lsa_install_new(po
, &lsa
, dom
, body
);
617 ospf_lsupd_flood(po
, NULL
, NULL
, &lsa
, dom
, 1);
621 flush_net_lsa(struct ospf_iface
*ifa
)
623 struct proto_ospf
*po
= ifa
->oa
->po
;
624 struct proto
*p
= &po
->proto
;
625 u32 dom
= ifa
->oa
->areaid
;
627 if (ifa
->net_lsa
== NULL
)
630 OSPF_TRACE(D_EVENTS
, "Flushing network-LSA for iface %s", ifa
->ifname
);
631 ifa
->net_lsa
->lsa
.sn
+= 1;
632 ifa
->net_lsa
->lsa
.age
= LSA_MAXAGE
;
633 lsasum_calculate(&ifa
->net_lsa
->lsa
, ifa
->net_lsa
->lsa_body
);
634 ospf_lsupd_flood(po
, NULL
, NULL
, &ifa
->net_lsa
->lsa
, dom
, 0);
635 flush_lsa(ifa
->net_lsa
, po
);
640 update_net_lsa(struct ospf_iface
*ifa
)
642 struct proto_ospf
*po
= ifa
->oa
->po
;
644 if (ifa
->net_lsa
&& ((ifa
->net_lsa
->inst_t
+ MINLSINTERVAL
) > now
))
647 * It's too early to originate new network LSA. We will
648 * try to do it next tick
651 if ((ifa
->state
!= OSPF_IS_DR
) || (ifa
->fadj
== 0))
655 flush_prefix_net_lsa(ifa
);
660 originate_net_lsa(ifa
);
662 originate_prefix_net_lsa(ifa
);
673 originate_sum_lsa_body(struct proto_ospf
*po
, u16
*length
, u32 mlen
, u32 metric
)
675 struct ospf_lsa_sum
*sum
= mb_alloc(po
->proto
.pool
, sizeof(struct ospf_lsa_sum
));
676 *length
= sizeof(struct ospf_lsa_header
) + sizeof(struct ospf_lsa_sum
);
678 sum
->netmask
= ipa_mkmask(mlen
);
679 sum
->metric
= metric
;
684 #define originate_sum_net_lsa_body(po,length,fn,metric) \
685 originate_sum_lsa_body(po, length, (fn)->pxlen, metric)
687 #define originate_sum_rt_lsa_body(po,length,drid,metric,options) \
688 originate_sum_lsa_body(po, length, 0, metric)
691 check_sum_net_lsaid_collision(struct fib_node
*fn
, struct top_hash_entry
*en
)
693 struct ospf_lsa_sum
*sum
= en
->lsa_body
;
694 return fn
->pxlen
!= ipa_mklen(sum
->netmask
);
698 check_sum_lsa_same(struct top_hash_entry
*en
, u32 metric
)
700 /* Netmask already checked in check_sum_net_lsaid_collision() */
701 struct ospf_lsa_sum
*sum
= en
->lsa_body
;
702 return (en
->lsa
.sn
!= LSA_MAXSEQNO
) && (sum
->metric
== metric
);
705 #define check_sum_net_lsa_same(en,metric) \
706 check_sum_lsa_same(en, metric)
708 #define check_sum_rt_lsa_same(en,drid,metric,options) \
709 check_sum_lsa_same(en, metric)
715 originate_sum_net_lsa_body(struct proto_ospf
*po
, u16
*length
, struct fib_node
*fn
, u32 metric
)
717 int size
= sizeof(struct ospf_lsa_sum_net
) + IPV6_PREFIX_SPACE(fn
->pxlen
);
718 struct ospf_lsa_sum_net
*sum
= mb_alloc(po
->proto
.pool
, size
);
719 *length
= sizeof(struct ospf_lsa_header
) + size
;
721 sum
->metric
= metric
;
722 put_ipv6_prefix(sum
->prefix
, fn
->prefix
, fn
->pxlen
, 0, 0);
728 check_sum_net_lsaid_collision(struct fib_node
*fn
, struct top_hash_entry
*en
)
730 struct ospf_lsa_sum_net
*sum
= en
->lsa_body
;
736 lsa_get_ipv6_prefix(sum
->prefix
, &prefix
, &pxlen
, &pxopts
, &rest
);
737 return (fn
->pxlen
!= pxlen
) || !ipa_equal(fn
->prefix
, prefix
);
741 check_sum_net_lsa_same(struct top_hash_entry
*en
, u32 metric
)
743 /* Prefix already checked in check_sum_net_lsaid_collision() */
744 struct ospf_lsa_sum_net
*sum
= en
->lsa_body
;
745 return (en
->lsa
.sn
!= LSA_MAXSEQNO
) && (sum
->metric
== metric
);
749 originate_sum_rt_lsa_body(struct proto_ospf
*po
, u16
*length
, u32 drid
, u32 metric
, u32 options
)
751 struct ospf_lsa_sum_rt
*sum
= mb_alloc(po
->proto
.pool
, sizeof(struct ospf_lsa_sum_rt
));
752 *length
= sizeof(struct ospf_lsa_header
) + sizeof(struct ospf_lsa_sum_rt
);
754 sum
->options
= options
;
755 sum
->metric
= metric
;
762 check_sum_rt_lsa_same(struct top_hash_entry
*en
, u32 drid
, u32 metric
, u32 options
)
764 struct ospf_lsa_sum_rt
*sum
= en
->lsa_body
;
765 return (en
->lsa
.sn
!= LSA_MAXSEQNO
) && (sum
->options
== options
) &&
766 (sum
->metric
== metric
) && (sum
->drid
== drid
);
772 originate_sum_net_lsa(struct ospf_area
*oa
, struct fib_node
*fn
, int metric
)
774 struct proto_ospf
*po
= oa
->po
;
775 struct proto
*p
= &po
->proto
;
776 struct top_hash_entry
*en
;
777 u32 dom
= oa
->areaid
;
778 struct ospf_lsa_header lsa
;
781 OSPF_TRACE(D_EVENTS
, "Originating net-summary-LSA for %I/%d (metric %d)",
782 fn
->prefix
, fn
->pxlen
, metric
);
784 /* options argument is used in ORT_NET and OSPFv3 only */
787 lsa
.options
= oa
->options
;
789 lsa
.type
= LSA_T_SUM_NET
;
790 lsa
.id
= fibnode_to_lsaid(po
, fn
);
791 lsa
.rt
= po
->router_id
;
793 if ((en
= ospf_hash_find_header(po
->gr
, dom
, &lsa
)) != NULL
)
795 if (check_sum_net_lsaid_collision(fn
, en
))
797 log(L_ERR
"%s: LSAID collision for %I/%d",
798 p
->name
, fn
->prefix
, fn
->pxlen
);
802 if (check_sum_net_lsa_same(en
, metric
))
805 lsa
.sn
= get_seqnum(en
);
807 body
= originate_sum_net_lsa_body(po
, &lsa
.length
, fn
, metric
);
808 lsasum_calculate(&lsa
, body
);
809 lsa_install_new(po
, &lsa
, dom
, body
);
810 ospf_lsupd_flood(po
, NULL
, NULL
, &lsa
, dom
, 1);
814 originate_sum_rt_lsa(struct ospf_area
*oa
, struct fib_node
*fn
, int metric
, u32 options UNUSED
)
816 struct proto_ospf
*po
= oa
->po
;
817 struct proto
*p
= &po
->proto
;
818 struct top_hash_entry
*en
;
819 u32 dom
= oa
->areaid
;
820 u32 rid
= ipa_to_rid(fn
->prefix
);
821 struct ospf_lsa_header lsa
;
824 OSPF_TRACE(D_EVENTS
, "Originating rt-summary-LSA for %R (metric %d)",
829 lsa
.options
= oa
->options
;
831 lsa
.type
= LSA_T_SUM_RT
;
832 /* In OSPFv3, LSA ID is meaningless, but we still use Router ID of ASBR */
834 lsa
.rt
= po
->router_id
;
836 options
&= OPTIONS_MASK
;
837 if ((en
= ospf_hash_find_header(po
->gr
, dom
, &lsa
)) != NULL
)
839 if (check_sum_rt_lsa_same(en
, lsa
.id
, metric
, options
))
842 lsa
.sn
= get_seqnum(en
);
844 body
= originate_sum_rt_lsa_body(po
, &lsa
.length
, lsa
.id
, metric
, options
);
845 lsasum_calculate(&lsa
, body
);
846 lsa_install_new(po
, &lsa
, dom
, body
);
847 ospf_lsupd_flood(po
, NULL
, NULL
, &lsa
, dom
, 1);
851 flush_sum_lsa(struct ospf_area
*oa
, struct fib_node
*fn
, int type
)
853 struct proto_ospf
*po
= oa
->po
;
854 struct proto
*p
= &po
->proto
;
855 struct top_hash_entry
*en
;
856 struct ospf_lsa_header lsa
;
858 lsa
.rt
= po
->router_id
;
861 lsa
.id
= fibnode_to_lsaid(po
, fn
);
862 lsa
.type
= LSA_T_SUM_NET
;
866 /* In OSPFv3, LSA ID is meaningless, but we still use Router ID of ASBR */
867 lsa
.id
= ipa_to_rid(fn
->prefix
);
868 lsa
.type
= LSA_T_SUM_RT
;
871 if ((en
= ospf_hash_find_header(po
->gr
, oa
->areaid
, &lsa
)) != NULL
)
873 OSPF_TRACE(D_EVENTS
, "Flushing summary-LSA (id=%R, type=%d)",
874 en
->lsa
.id
, en
->lsa
.type
);
876 if ((type
== ORT_NET
) && check_sum_net_lsaid_collision(fn
, en
))
878 log(L_ERR
"%s: LSAID collision for %I/%d",
879 p
->name
, fn
->prefix
, fn
->pxlen
);
883 struct ospf_lsa_sum
*sum
= en
->lsa_body
;
884 en
->lsa
.age
= LSA_MAXAGE
;
885 en
->lsa
.sn
= LSA_MAXSEQNO
;
886 lsasum_calculate(&en
->lsa
, sum
);
887 ospf_lsupd_flood(po
, NULL
, NULL
, &en
->lsa
, oa
->areaid
, 1);
888 if (can_flush_lsa(po
)) flush_lsa(en
, po
);
895 originate_ext_lsa_body(struct proto_ospf
*po
, u16
*length
, struct fib_node
*fn
,
896 u32 metric
, ip_addr fwaddr
, u32 tag
, int pbit UNUSED
)
898 struct ospf_lsa_ext
*ext
= mb_alloc(po
->proto
.pool
, sizeof(struct ospf_lsa_ext
));
899 *length
= sizeof(struct ospf_lsa_header
) + sizeof(struct ospf_lsa_ext
);
901 ext
->metric
= metric
;
902 ext
->netmask
= ipa_mkmask(fn
->pxlen
);
903 ext
->fwaddr
= fwaddr
;
910 * check_ext_lsa() combines functions of check_*_lsaid_collision() and
911 * check_*_lsa_same(). 'en' is existing ext LSA, and rest parameters
912 * are parameters of new ext route. Function returns -1 if there is
913 * LSAID collision, returns 1 if the existing LSA is the same and
914 * returns 0 otherwise (in that case, we need to originate a new LSA).
916 * Really, checking for the same parameters is not as important as in
917 * summary LSA origination, because in most cases the duplicate
918 * external route propagation would be stopped by the nest. But there
919 * are still some cases (route reload, the same route propagated through
920 * different protocol) so it is also done here.
924 check_ext_lsa(struct top_hash_entry
*en
, struct fib_node
*fn
, u32 metric
, ip_addr fwaddr
, u32 tag
)
926 struct ospf_lsa_ext
*ext
= en
->lsa_body
;
928 /* LSAID collision */
929 if (fn
->pxlen
!= ipa_mklen(ext
->netmask
))
932 return (en
->lsa
.sn
!= LSA_MAXSEQNO
) && (ext
->metric
== metric
) &&
933 (ext
->tag
== tag
) && ipa_equal(ext
->fwaddr
,fwaddr
);
939 originate_ext_lsa_body(struct proto_ospf
*po
, u16
*length
, struct fib_node
*fn
,
940 u32 metric
, ip_addr fwaddr
, u32 tag
, int pbit
)
942 int size
= sizeof(struct ospf_lsa_ext
)
943 + IPV6_PREFIX_SPACE(fn
->pxlen
)
944 + (ipa_nonzero(fwaddr
) ? 16 : 0)
947 struct ospf_lsa_ext
*ext
= mb_alloc(po
->proto
.pool
, size
);
948 *length
= sizeof(struct ospf_lsa_header
) + size
;
950 ext
->metric
= metric
;
952 u32
*buf
= ext
->rest
;
953 buf
= put_ipv6_prefix(buf
, fn
->prefix
, fn
->pxlen
, pbit
? OPT_PX_P
: 0, 0);
955 if (ipa_nonzero(fwaddr
))
957 ext
->metric
|= LSA_EXT_FBIT
;
958 buf
= put_ipv6_addr(buf
, fwaddr
);
963 ext
->metric
|= LSA_EXT_TBIT
;
971 check_ext_lsa(struct top_hash_entry
*en
, struct fib_node
*fn
, u32 metric
, ip_addr fwaddr
, u32 tag
)
973 struct ospf_lsa_ext
*ext
= en
->lsa_body
;
979 u32
*buf
= lsa_get_ipv6_prefix(ext
->rest
, &prefix
, &pxlen
, &pxopts
, &rest
);
981 /* LSAID collision */
982 if ((fn
->pxlen
!= pxlen
) || !ipa_equal(fn
->prefix
, prefix
))
985 if (en
->lsa
.sn
== LSA_MAXSEQNO
)
988 u32 rt_metric
= ext
->metric
& METRIC_MASK
;
989 ip_addr rt_fwaddr
= IPA_NONE
;
992 if (ext
->metric
& LSA_EXT_FBIT
)
993 buf
= lsa_get_ipv6_addr(buf
, &rt_fwaddr
);
995 if (ext
->metric
& LSA_EXT_TBIT
)
998 return (rt_metric
== metric
) && ipa_equal(rt_fwaddr
, fwaddr
) && (rt_tag
== tag
);
1004 static inline ip_addr
1005 find_surrogate_fwaddr(struct ospf_area
*oa
)
1007 struct proto_ospf
*po
= oa
->po
;
1008 struct ospf_iface
*ifa
;
1009 struct ifa
*a
, *cur_addr
= NULL
;
1012 WALK_LIST(ifa
, po
->iface_list
)
1014 if ((ifa
->oa
!= oa
) ||
1015 (ifa
->type
== OSPF_IT_VLINK
))
1020 if (a
->flags
& IA_PEER
)
1023 np
= ((a
->flags
& IA_HOST
) || ifa
->stub
) ? 2 : 1;
1031 WALK_LIST(a
, ifa
->iface
->addrs
)
1033 if ((a
->flags
& IA_SECONDARY
) ||
1034 (a
->flags
& IA_PEER
) ||
1035 (a
->scope
<= SCOPE_LINK
))
1038 np
= ((a
->flags
& IA_HOST
) || ifa
->stub
) ? 2 : 1;
1048 return cur_addr
? cur_addr
->ip
: IPA_NONE
;
1053 * originate_ext_lsa - new route received from nest and filters
1054 * @oa: ospf_area for which LSA is originated
1055 * @fn: network prefix and mask
1056 * @src: the source of origination of the LSA (EXT_EXPORT/EXT_NSSA)
1057 * @metric: the metric of a route
1058 * @fwaddr: the forwarding address
1059 * @tag: the route tag
1060 * @pbit: P-bit for NSSA LSAs, ignored for external LSAs
1062 * If I receive a message that new route is installed, I try to originate an
1063 * external LSA. If @oa is an NSSA area, NSSA-LSA is originated instead.
1064 * @oa should not be a stub area. @src does not specify whether the LSA
1065 * is external or NSSA, but it specifies the source of origination -
1066 * the export from ospf_rt_notify(), or the NSSA-EXT translation.
1068 * The function also sets flag ebit. If it's the first time, the new router lsa
1069 * origination is necessary.
1072 originate_ext_lsa(struct ospf_area
*oa
, struct fib_node
*fn
, int src
,
1073 u32 metric
, ip_addr fwaddr
, u32 tag
, int pbit
)
1075 struct proto_ospf
*po
= oa
->po
;
1076 struct proto
*p
= &po
->proto
;
1077 struct ospf_lsa_header lsa
;
1078 struct top_hash_entry
*en
= NULL
;
1080 int nssa
= oa_is_nssa(oa
);
1081 u32 dom
= nssa
? oa
->areaid
: 0;
1083 OSPF_TRACE(D_EVENTS
, "Originating %s-LSA for %I/%d",
1084 nssa
? "NSSA" : "AS-external", fn
->prefix
, fn
->pxlen
);
1088 lsa
.options
= nssa
? (pbit
? OPT_P
: 0) : OPT_E
;
1090 lsa
.type
= nssa
? LSA_T_NSSA
: LSA_T_EXT
;
1091 lsa
.id
= fibnode_to_lsaid(po
, fn
);
1092 lsa
.rt
= po
->router_id
;
1094 if (nssa
&& pbit
&& ipa_zero(fwaddr
))
1096 /* NSSA-LSA with P-bit set must have non-zero forwarding address */
1098 fwaddr
= find_surrogate_fwaddr(oa
);
1099 if (ipa_zero(fwaddr
))
1101 log(L_ERR
"%s: Cannot find forwarding address for NSSA-LSA %I/%d",
1102 p
->name
, fn
->prefix
, fn
->pxlen
);
1107 if ((en
= ospf_hash_find_header(po
->gr
, dom
, &lsa
)) != NULL
)
1109 int rv
= check_ext_lsa(en
, fn
, metric
, fwaddr
, tag
);
1112 log(L_ERR
"%s: LSAID collision for %I/%d",
1113 p
->name
, fn
->prefix
, fn
->pxlen
);
1120 lsa
.sn
= get_seqnum(en
);
1122 body
= originate_ext_lsa_body(po
, &lsa
.length
, fn
, metric
, fwaddr
, tag
, pbit
);
1123 lsasum_calculate(&lsa
, body
);
1128 lsa_install_new(po
, &lsa
, dom
, body
);
1129 ospf_lsupd_flood(po
, NULL
, NULL
, &lsa
, dom
, 1);
1134 WALK_LIST(oa
, po
->area_list
)
1136 schedule_rt_lsa(oa
);
1142 flush_ext_lsa(struct ospf_area
*oa
, struct fib_node
*fn
, int nssa
)
1144 struct proto_ospf
*po
= oa
->po
;
1145 struct proto
*p
= &po
->proto
;
1146 struct top_hash_entry
*en
;
1148 u32 dom
= nssa
? oa
->areaid
: 0;
1149 u32 type
= nssa
? LSA_T_NSSA
: LSA_T_EXT
;
1150 u32 lsaid
= fibnode_to_lsaid(po
, fn
);
1152 if (en
= ospf_hash_find(po
->gr
, dom
, lsaid
, po
->router_id
, type
))
1154 OSPF_TRACE(D_EVENTS
, "Flushing %s-LSA for %I/%d",
1155 nssa
? "NSSA" : "AS-external", fn
->prefix
, fn
->pxlen
);
1157 if (check_ext_lsa(en
, fn
, 0, IPA_NONE
, 0) < 0)
1159 log(L_ERR
"%s: LSAID collision for %I/%d",
1160 p
->name
, fn
->prefix
, fn
->pxlen
);
1165 ospf_lsupd_flush_nlsa(po
, en
);
1173 originate_link_lsa_body(struct ospf_iface
*ifa
, u16
*length
)
1175 struct proto_ospf
*po
= ifa
->oa
->po
;
1176 struct ospf_lsa_link
*ll
;
1180 ASSERT(po
->lsab_used
== 0);
1181 ll
= lsab_allocz(po
, sizeof(struct ospf_lsa_link
));
1182 ll
->options
= ifa
->oa
->options
| (ifa
->priority
<< 24);
1183 ll
->lladdr
= ifa
->addr
->ip
;
1184 ll
= NULL
; /* buffer might be reallocated later */
1187 WALK_LIST(a
, ifa
->iface
->addrs
)
1189 if ((a
->flags
& IA_SECONDARY
) ||
1190 (a
->scope
< SCOPE_SITE
))
1193 flags
= (a
->pxlen
< MAX_PREFIX_LENGTH
) ? 0 : OPT_PX_LA
;
1194 put_ipv6_prefix(lsab_alloc(po
, IPV6_PREFIX_SPACE(a
->pxlen
)),
1195 a
->ip
, a
->pxlen
, flags
, 0);
1201 *length
= po
->lsab_used
+ sizeof(struct ospf_lsa_header
);
1202 return lsab_flush(po
);
1206 originate_link_lsa(struct ospf_iface
*ifa
)
1208 struct ospf_lsa_header lsa
;
1209 struct proto_ospf
*po
= ifa
->oa
->po
;
1210 struct proto
*p
= &po
->proto
;
1213 /* Vlinks do not have link-LSAs */
1214 if (ifa
->type
== OSPF_IT_VLINK
)
1217 OSPF_TRACE(D_EVENTS
, "Originating link-LSA for iface %s", ifa
->ifname
);
1220 lsa
.type
= LSA_T_LINK
;
1221 lsa
.id
= ifa
->iface_id
;
1222 lsa
.rt
= po
->router_id
;
1223 lsa
.sn
= get_seqnum(ifa
->link_lsa
);
1224 u32 dom
= ifa
->iface_id
;
1226 body
= originate_link_lsa_body(ifa
, &lsa
.length
);
1227 lsasum_calculate(&lsa
, body
);
1228 ifa
->link_lsa
= lsa_install_new(po
, &lsa
, dom
, body
);
1229 ospf_lsupd_flood(po
, NULL
, NULL
, &lsa
, dom
, 1);
1231 /* Just to be sure to not forget on our link LSA */
1232 if (ifa
->state
== OSPF_IS_DR
)
1233 schedule_net_lsa(ifa
);
1237 update_link_lsa(struct ospf_iface
*ifa
)
1239 if (ifa
->link_lsa
&& ((ifa
->link_lsa
->inst_t
+ MINLSINTERVAL
) > now
))
1242 * It's too early to originate new link LSA. We will
1243 * try to do it next tick
1245 originate_link_lsa(ifa
);
1250 lsa_put_prefix(struct proto_ospf
*po
, ip_addr prefix
, u32 pxlen
, u32 cost
)
1252 put_ipv6_prefix(lsab_alloc(po
, IPV6_PREFIX_SPACE(pxlen
)), prefix
, pxlen
,
1253 (pxlen
< MAX_PREFIX_LENGTH
) ? 0 : OPT_PX_LA
, cost
);
1257 originate_prefix_rt_lsa_body(struct ospf_area
*oa
, u16
*length
)
1259 struct proto_ospf
*po
= oa
->po
;
1260 struct ospf_config
*cf
= (struct ospf_config
*) (po
->proto
.cf
);
1261 struct ospf_iface
*ifa
;
1262 struct ospf_lsa_prefix
*lp
;
1267 ASSERT(po
->lsab_used
== 0);
1268 lp
= lsab_allocz(po
, sizeof(struct ospf_lsa_prefix
));
1269 lp
->ref_type
= LSA_T_RT
;
1271 lp
->ref_rt
= po
->router_id
;
1272 lp
= NULL
; /* buffer might be reallocated later */
1274 WALK_LIST(ifa
, po
->iface_list
)
1276 if ((ifa
->oa
!= oa
) || (ifa
->type
== OSPF_IT_VLINK
) || (ifa
->state
== OSPF_IS_DOWN
))
1279 ifa
->px_pos_beg
= i
;
1281 if ((ifa
->type
== OSPF_IT_BCAST
) ||
1282 (ifa
->type
== OSPF_IT_NBMA
))
1283 net_lsa
= bcast_net_active(ifa
);
1288 WALK_LIST(a
, ifa
->iface
->addrs
)
1290 if ((a
->flags
& IA_SECONDARY
) ||
1291 (a
->flags
& IA_PEER
) ||
1292 (a
->scope
<= SCOPE_LINK
))
1295 if (((a
->pxlen
< MAX_PREFIX_LENGTH
) && net_lsa
) ||
1296 configured_stubnet(oa
, a
))
1299 if ((a
->flags
& IA_HOST
) ||
1300 (ifa
->state
== OSPF_IS_LOOP
) ||
1301 (ifa
->type
== OSPF_IT_PTMP
))
1303 lsa_put_prefix(po
, a
->ip
, MAX_PREFIX_LENGTH
, 0);
1307 lsa_put_prefix(po
, a
->prefix
, a
->pxlen
, ifa
->cost
);
1311 ifa
->px_pos_end
= i
;
1314 struct ospf_stubnet_config
*sn
;
1316 WALK_LIST(sn
, oa
->ac
->stubnet_list
)
1319 lsa_put_prefix(po
, sn
->px
.addr
, sn
->px
.len
, sn
->cost
);
1320 if (sn
->px
.len
== MAX_PREFIX_LENGTH
)
1325 /* If there are some configured vlinks, find some global address
1326 (even from another area), which will be used as a vlink endpoint. */
1327 if (!EMPTY_LIST(cf
->vlink_list
) && !host_addr
)
1329 WALK_LIST(ifa
, po
->iface_list
)
1331 if ((ifa
->type
== OSPF_IT_VLINK
) || (ifa
->state
== OSPF_IS_DOWN
))
1335 WALK_LIST(a
, ifa
->iface
->addrs
)
1337 if ((a
->flags
& IA_SECONDARY
) || (a
->scope
<= SCOPE_LINK
))
1341 lsa_put_prefix(po
, a
->ip
, MAX_PREFIX_LENGTH
, 0);
1351 *length
= po
->lsab_used
+ sizeof(struct ospf_lsa_header
);
1352 return lsab_flush(po
);
1356 originate_prefix_rt_lsa(struct ospf_area
*oa
)
1358 struct proto_ospf
*po
= oa
->po
;
1359 struct proto
*p
= &po
->proto
;
1360 struct ospf_lsa_header lsa
;
1363 OSPF_TRACE(D_EVENTS
, "Originating router prefix-LSA for area %R", oa
->areaid
);
1366 lsa
.type
= LSA_T_PREFIX
;
1368 lsa
.rt
= po
->router_id
;
1369 lsa
.sn
= get_seqnum(oa
->pxr_lsa
);
1370 u32 dom
= oa
->areaid
;
1372 body
= originate_prefix_rt_lsa_body(oa
, &lsa
.length
);
1373 lsasum_calculate(&lsa
, body
);
1374 oa
->pxr_lsa
= lsa_install_new(po
, &lsa
, dom
, body
);
1375 ospf_lsupd_flood(po
, NULL
, NULL
, &lsa
, dom
, 1);
1380 prefix_space(u32
*buf
)
1382 int pxl
= *buf
>> 24;
1383 return IPV6_PREFIX_SPACE(pxl
);
1387 prefix_same(u32
*b1
, u32
*b2
)
1389 int pxl1
= *b1
>> 24;
1390 int pxl2
= *b2
>> 24;
1396 pxs
= IPV6_PREFIX_WORDS(pxl1
);
1397 for (i
= 1; i
< pxs
; i
++)
1405 prefix_advance(u32
*buf
)
1407 int pxl
= *buf
>> 24;
1408 return buf
+ IPV6_PREFIX_WORDS(pxl
);
1411 /* FIXME eliminate items with LA bit set? see 4.4.3.9 */
1413 add_prefix(struct proto_ospf
*po
, u32
*px
, int offset
, int *pxc
)
1415 u32
*pxl
= lsab_offset(po
, offset
);
1417 for (i
= 0; i
< *pxc
; pxl
= prefix_advance(pxl
), i
++)
1418 if (prefix_same(px
, pxl
))
1420 /* Options should be logically OR'ed together */
1421 *pxl
|= (*px
& 0x00FF0000);
1425 ASSERT(pxl
== lsab_end(po
));
1427 int pxspace
= prefix_space(px
);
1428 pxl
= lsab_alloc(po
, pxspace
);
1429 memcpy(pxl
, px
, pxspace
);
1430 *pxl
&= 0xFFFF0000; /* Set metric to zero */
1435 add_link_lsa(struct proto_ospf
*po
, struct top_hash_entry
*en
, int offset
, int *pxc
)
1437 struct ospf_lsa_link
*ll
= en
->lsa_body
;
1438 u32
*pxb
= ll
->rest
;
1441 for (j
= 0; j
< ll
->pxcount
; pxb
= prefix_advance(pxb
), j
++)
1443 u8 pxlen
= (pxb
[0] >> 24);
1444 u8 pxopts
= (pxb
[0] >> 16);
1446 /* Skip NU or LA prefixes */
1447 if (pxopts
& (OPT_PX_NU
| OPT_PX_LA
))
1450 /* Skip link-local prefixes */
1451 if ((pxlen
>= 10) && ((pxb
[1] & 0xffc00000) == 0xfe800000))
1454 add_prefix(po
, pxb
, offset
, pxc
);
1461 originate_prefix_net_lsa_body(struct ospf_iface
*ifa
, u16
*length
)
1463 struct proto_ospf
*po
= ifa
->oa
->po
;
1464 struct ospf_lsa_prefix
*lp
;
1465 struct ospf_neighbor
*n
;
1466 struct top_hash_entry
*en
;
1469 ASSERT(po
->lsab_used
== 0);
1470 lp
= lsab_allocz(po
, sizeof(struct ospf_lsa_prefix
));
1471 lp
->ref_type
= LSA_T_NET
;
1472 lp
->ref_id
= ifa
->net_lsa
->lsa
.id
;
1473 lp
->ref_rt
= po
->router_id
;
1474 lp
= NULL
; /* buffer might be reallocated later */
1477 offset
= po
->lsab_used
;
1479 /* Find all Link LSAs associated with the link and merge their prefixes */
1481 add_link_lsa(po
, ifa
->link_lsa
, offset
, &pxc
);
1483 WALK_LIST(n
, ifa
->neigh_list
)
1484 if ((n
->state
== NEIGHBOR_FULL
) &&
1485 (en
= ospf_hash_find(po
->gr
, ifa
->iface_id
, n
->iface_id
, n
->rid
, LSA_T_LINK
)))
1486 add_link_lsa(po
, en
, offset
, &pxc
);
1490 *length
= po
->lsab_used
+ sizeof(struct ospf_lsa_header
);
1491 return lsab_flush(po
);
1495 originate_prefix_net_lsa(struct ospf_iface
*ifa
)
1497 struct proto_ospf
*po
= ifa
->oa
->po
;
1498 struct proto
*p
= &po
->proto
;
1499 struct ospf_lsa_header lsa
;
1502 OSPF_TRACE(D_EVENTS
, "Originating network prefix-LSA for iface %s", ifa
->ifname
);
1505 lsa
.type
= LSA_T_PREFIX
;
1506 lsa
.id
= ifa
->iface_id
;
1507 lsa
.rt
= po
->router_id
;
1508 lsa
.sn
= get_seqnum(ifa
->pxn_lsa
);
1509 u32 dom
= ifa
->oa
->areaid
;
1511 body
= originate_prefix_net_lsa_body(ifa
, &lsa
.length
);
1512 lsasum_calculate(&lsa
, body
);
1513 ifa
->pxn_lsa
= lsa_install_new(po
, &lsa
, dom
, body
);
1514 ospf_lsupd_flood(po
, NULL
, NULL
, &lsa
, dom
, 1);
1518 flush_prefix_net_lsa(struct ospf_iface
*ifa
)
1520 struct proto_ospf
*po
= ifa
->oa
->po
;
1521 struct proto
*p
= &po
->proto
;
1522 struct top_hash_entry
*en
= ifa
->pxn_lsa
;
1523 u32 dom
= ifa
->oa
->areaid
;
1528 OSPF_TRACE(D_EVENTS
, "Flushing network prefix-LSA for iface %s", ifa
->ifname
);
1531 en
->lsa
.age
= LSA_MAXAGE
;
1532 lsasum_calculate(&en
->lsa
, en
->lsa_body
);
1533 ospf_lsupd_flood(po
, NULL
, NULL
, &en
->lsa
, dom
, 0);
1535 ifa
->pxn_lsa
= NULL
;
1543 ospf_top_ht_alloc(struct top_graph
*f
)
1545 f
->hash_size
= 1 << f
->hash_order
;
1546 f
->hash_mask
= f
->hash_size
- 1;
1547 if (f
->hash_order
> HASH_HI_MAX
- HASH_HI_STEP
)
1548 f
->hash_entries_max
= ~0;
1550 f
->hash_entries_max
= f
->hash_size HASH_HI_MARK
;
1551 if (f
->hash_order
< HASH_LO_MIN
+ HASH_LO_STEP
)
1552 f
->hash_entries_min
= 0;
1554 f
->hash_entries_min
= f
->hash_size HASH_LO_MARK
;
1555 DBG("Allocating OSPF hash of order %d: %d hash_entries, %d low, %d high\n",
1556 f
->hash_order
, f
->hash_size
, f
->hash_entries_min
, f
->hash_entries_max
);
1558 mb_alloc(f
->pool
, f
->hash_size
* sizeof(struct top_hash_entry
*));
1559 bzero(f
->hash_table
, f
->hash_size
* sizeof(struct top_hash_entry
*));
1563 ospf_top_ht_free(struct top_hash_entry
**h
)
1569 ospf_top_hash_u32(u32 a
)
1571 /* Shamelessly stolen from IP address hashing in ipv4.h */
1577 static inline unsigned
1578 ospf_top_hash(struct top_graph
*f
, u32 domain
, u32 lsaid
, u32 rtrid
, u32 type
)
1580 /* In OSPFv2, we don't know Router ID when looking for network LSAs.
1581 In OSPFv3, we don't know LSA ID when looking for router LSAs.
1582 In both cases, there is (usually) just one (or small number)
1583 appropriate LSA, so we just clear unknown part of key. */
1587 ((type
== LSA_T_NET
) ? 0 : ospf_top_hash_u32(rtrid
)) +
1588 ospf_top_hash_u32(lsaid
) +
1590 ospf_top_hash_u32(rtrid
) +
1591 ((type
== LSA_T_RT
) ? 0 : ospf_top_hash_u32(lsaid
)) +
1593 type
+ domain
) & f
->hash_mask
;
1596 return (ospf_top_hash_u32(lsaid) + ospf_top_hash_u32(rtrid) +
1597 type + areaid) & f->hash_mask;
1602 * ospf_top_new - allocated new topology database
1603 * @p: current instance of ospf
1605 * this dynamically hashed structure is often used for keeping lsas. mainly
1606 * its used in @ospf_area structure.
1609 ospf_top_new(pool
*pool
)
1611 struct top_graph
*f
;
1613 f
= mb_allocz(pool
, sizeof(struct top_graph
));
1615 f
->hash_slab
= sl_new(f
->pool
, sizeof(struct top_hash_entry
));
1616 f
->hash_order
= HASH_DEF_ORDER
;
1617 ospf_top_ht_alloc(f
);
1618 f
->hash_entries
= 0;
1619 f
->hash_entries_min
= 0;
1624 ospf_top_free(struct top_graph
*f
)
1626 rfree(f
->hash_slab
);
1627 ospf_top_ht_free(f
->hash_table
);
1632 ospf_top_rehash(struct top_graph
*f
, int step
)
1634 unsigned int oldn
, oldh
;
1635 struct top_hash_entry
**n
, **oldt
, **newt
, *e
, *x
;
1637 oldn
= f
->hash_size
;
1638 oldt
= f
->hash_table
;
1639 DBG("re-hashing topology hash from order %d to %d\n", f
->hash_order
,
1640 f
->hash_order
+ step
);
1641 f
->hash_order
+= step
;
1642 ospf_top_ht_alloc(f
);
1643 newt
= f
->hash_table
;
1645 for (oldh
= 0; oldh
< oldn
; oldh
++)
1651 n
= newt
+ ospf_top_hash(f
, e
->domain
, e
->lsa
.id
, e
->lsa
.rt
, e
->lsa
.type
);
1657 ospf_top_ht_free(oldt
);
1663 ospf_lsa_domain(u32 type
, struct ospf_iface
*ifa
)
1665 return (type
== LSA_T_EXT
) ? 0 : ifa
->oa
->areaid
;
1671 ospf_lsa_domain(u32 type
, struct ospf_iface
*ifa
)
1673 switch (type
& LSA_SCOPE_MASK
)
1675 case LSA_SCOPE_LINK
:
1676 return ifa
->iface_id
;
1678 case LSA_SCOPE_AREA
:
1679 return ifa
->oa
->areaid
;
1689 struct top_hash_entry
*
1690 ospf_hash_find_header(struct top_graph
*f
, u32 domain
, struct ospf_lsa_header
*h
)
1692 return ospf_hash_find(f
, domain
, h
->id
, h
->rt
, h
->type
);
1695 struct top_hash_entry
*
1696 ospf_hash_get_header(struct top_graph
*f
, u32 domain
, struct ospf_lsa_header
*h
)
1698 return ospf_hash_get(f
, domain
, h
->id
, h
->rt
, h
->type
);
1701 struct top_hash_entry
*
1702 ospf_hash_find(struct top_graph
*f
, u32 domain
, u32 lsa
, u32 rtr
, u32 type
)
1704 struct top_hash_entry
*e
;
1705 e
= f
->hash_table
[ospf_top_hash(f
, domain
, lsa
, rtr
, type
)];
1707 while (e
&& (e
->lsa
.id
!= lsa
|| e
->lsa
.type
!= type
|| e
->lsa
.rt
!= rtr
|| e
->domain
!= domain
))
1716 /* In OSPFv2, sometimes we don't know Router ID when looking for network LSAs.
1717 There should be just one, so we find any match. */
1718 struct top_hash_entry
*
1719 ospf_hash_find_net(struct top_graph
*f
, u32 domain
, u32 lsa
)
1721 struct top_hash_entry
*e
;
1722 e
= f
->hash_table
[ospf_top_hash(f
, domain
, lsa
, 0, LSA_T_NET
)];
1724 while (e
&& (e
->lsa
.id
!= lsa
|| e
->lsa
.type
!= LSA_T_NET
|| e
->domain
!= domain
))
1735 /* In OSPFv3, usually we don't know LSA ID when looking for router
1736 LSAs. We return matching LSA with smallest LSA ID. */
1737 struct top_hash_entry
*
1738 ospf_hash_find_rt(struct top_graph
*f
, u32 domain
, u32 rtr
)
1740 struct top_hash_entry
*rv
= NULL
;
1741 struct top_hash_entry
*e
;
1742 e
= f
->hash_table
[ospf_top_hash(f
, domain
, 0, rtr
, LSA_T_RT
)];
1746 if (e
->lsa
.rt
== rtr
&& e
->lsa
.type
== LSA_T_RT
&& e
->domain
== domain
)
1747 if (!rv
|| e
->lsa
.id
< rv
->lsa
.id
)
1755 static inline struct top_hash_entry
*
1756 find_matching_rt(struct top_hash_entry
*e
, u32 domain
, u32 rtr
)
1758 while (e
&& (e
->lsa
.rt
!= rtr
|| e
->lsa
.type
!= LSA_T_RT
|| e
->domain
!= domain
))
1763 struct top_hash_entry
*
1764 ospf_hash_find_rt_first(struct top_graph
*f
, u32 domain
, u32 rtr
)
1766 struct top_hash_entry
*e
;
1767 e
= f
->hash_table
[ospf_top_hash(f
, domain
, 0, rtr
, LSA_T_RT
)];
1768 return find_matching_rt(e
, domain
, rtr
);
1771 struct top_hash_entry
*
1772 ospf_hash_find_rt_next(struct top_hash_entry
*e
)
1774 return find_matching_rt(e
->next
, e
->domain
, e
->lsa
.rt
);
1780 struct top_hash_entry
*
1781 ospf_hash_get(struct top_graph
*f
, u32 domain
, u32 lsa
, u32 rtr
, u32 type
)
1783 struct top_hash_entry
**ee
;
1784 struct top_hash_entry
*e
;
1786 ee
= f
->hash_table
+ ospf_top_hash(f
, domain
, lsa
, rtr
, type
);
1789 while (e
&& (e
->lsa
.id
!= lsa
|| e
->lsa
.rt
!= rtr
|| e
->lsa
.type
!= type
|| e
->domain
!= domain
))
1795 e
= sl_alloc(f
->hash_slab
);
1797 e
->dist
= LSINFINITY
;
1807 if (f
->hash_entries
++ > f
->hash_entries_max
)
1808 ospf_top_rehash(f
, HASH_HI_STEP
);
1813 ospf_hash_delete(struct top_graph
*f
, struct top_hash_entry
*e
)
1815 struct top_hash_entry
**ee
= f
->hash_table
+
1816 ospf_top_hash(f
, e
->domain
, e
->lsa
.id
, e
->lsa
.rt
, e
->lsa
.type
);
1823 sl_free(f
->hash_slab
, e
);
1824 if (f
->hash_entries
-- < f
->hash_entries_min
)
1825 ospf_top_rehash(f
, -HASH_LO_STEP
);
1828 ee
= &((*ee
)->next
);
1830 bug("ospf_hash_delete() called for invalid node");
1835 ospf_dump_lsa(struct top_hash_entry *he, struct proto *p)
1838 struct ospf_lsa_rt *rt = NULL;
1839 struct ospf_lsa_rt_link *rr = NULL;
1840 struct ospf_lsa_net *ln = NULL;
1844 OSPF_TRACE(D_EVENTS, "- %1x %-1R %-1R %4u 0x%08x 0x%04x %-1R",
1845 he->lsa.type, he->lsa.id, he->lsa.rt, he->lsa.age, he->lsa.sn,
1846 he->lsa.checksum, he->domain);
1849 switch (he->lsa.type)
1853 rr = (struct ospf_lsa_rt_link *) (rt + 1);
1855 for (i = 0; i < lsa_rt_items(&he->lsa); i++)
1856 OSPF_TRACE(D_EVENTS, " - %1x %-1R %-1R %5u",
1857 rr[i].type, rr[i].id, rr[i].data, rr[i].metric);
1862 rts = (u32 *) (ln + 1);
1864 for (i = 0; i < lsa_net_items(&he->lsa); i++)
1865 OSPF_TRACE(D_EVENTS, " - %-1R", rts[i]);
1874 ospf_top_dump(struct top_graph *f, struct proto *p)
1877 OSPF_TRACE(D_EVENTS, "Hash entries: %d", f->hash_entries);
1879 for (i = 0; i < f->hash_size; i++)
1881 struct top_hash_entry *e;
1882 for (e = f->hash_table[i]; e != NULL; e = e->next)
1883 ospf_dump_lsa(e, p);
1888 /* This is very inefficient, please don't call it often */
1890 /* I should also test for every LSA if it's in some link state
1891 * retransmission list for every neighbor. I will not test it.
1892 * It could happen that I'll receive some strange ls ack's.
1896 can_flush_lsa(struct proto_ospf
*po
)
1898 struct ospf_iface
*ifa
;
1899 struct ospf_neighbor
*n
;
1901 WALK_LIST(ifa
, po
->iface_list
)
1903 WALK_LIST(n
, ifa
->neigh_list
)
1905 if ((n
->state
== NEIGHBOR_EXCHANGE
) || (n
->state
== NEIGHBOR_LOADING
))