File: | src/usr.sbin/ospf6d/rde_spf.c |
Warning: | line 409, column 4 Value stored to 'p' is never read |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | /* $OpenBSD: rde_spf.c,v 1.29 2023/03/08 04:43:14 guenther Exp $ */ |
2 | |
3 | /* |
4 | * Copyright (c) 2005 Esben Norby <norby@openbsd.org> |
5 | * |
6 | * Permission to use, copy, modify, and distribute this software for any |
7 | * purpose with or without fee is hereby granted, provided that the above |
8 | * copyright notice and this permission notice appear in all copies. |
9 | * |
10 | * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES |
11 | * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF |
12 | * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR |
13 | * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES |
14 | * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN |
15 | * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF |
16 | * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. |
17 | */ |
18 | |
19 | #include <sys/types.h> |
20 | #include <sys/socket.h> |
21 | #include <netinet/in.h> |
22 | #include <arpa/inet.h> |
23 | #include <err.h> |
24 | #include <stdlib.h> |
25 | #include <string.h> |
26 | |
27 | #include "ospf6d.h" |
28 | #include "ospf6.h" |
29 | #include "log.h" |
30 | #include "rde.h" |
31 | |
32 | extern struct ospfd_conf *rdeconf; |
33 | TAILQ_HEAD(, vertex)struct { struct vertex *tqh_first; struct vertex **tqh_last; } cand_list; |
34 | RB_HEAD(rt_tree, rt_node)struct rt_tree { struct rt_node *rbh_root; } rt; |
35 | RB_PROTOTYPE(rt_tree, rt_node, entry, rt_compare)void rt_tree_RB_INSERT_COLOR(struct rt_tree *, struct rt_node *); void rt_tree_RB_REMOVE_COLOR(struct rt_tree *, struct rt_node *, struct rt_node *); struct rt_node *rt_tree_RB_REMOVE(struct rt_tree *, struct rt_node *); struct rt_node *rt_tree_RB_INSERT (struct rt_tree *, struct rt_node *); struct rt_node *rt_tree_RB_FIND (struct rt_tree *, struct rt_node *); struct rt_node *rt_tree_RB_NFIND (struct rt_tree *, struct rt_node *); struct rt_node *rt_tree_RB_NEXT (struct rt_node *); struct rt_node *rt_tree_RB_PREV(struct rt_node *); struct rt_node *rt_tree_RB_MINMAX(struct rt_tree *, int) ; |
36 | RB_GENERATE(rt_tree, rt_node, entry, rt_compare)void rt_tree_RB_INSERT_COLOR(struct rt_tree *head, struct rt_node *elm) { struct rt_node *parent, *gparent, *tmp; while ((parent = (elm)->entry.rbe_parent) && (parent)->entry. rbe_color == 1) { gparent = (parent)->entry.rbe_parent; if (parent == (gparent)->entry.rbe_left) { tmp = (gparent)-> entry.rbe_right; if (tmp && (tmp)->entry.rbe_color == 1) { (tmp)->entry.rbe_color = 0; do { (parent)->entry .rbe_color = 0; (gparent)->entry.rbe_color = 1; } while (0 ); elm = gparent; continue; } if ((parent)->entry.rbe_right == elm) { do { (tmp) = (parent)->entry.rbe_right; if (((parent )->entry.rbe_right = (tmp)->entry.rbe_left)) { ((tmp)-> entry.rbe_left)->entry.rbe_parent = (parent); } do {} while (0); if (((tmp)->entry.rbe_parent = (parent)->entry.rbe_parent )) { if ((parent) == ((parent)->entry.rbe_parent)->entry .rbe_left) ((parent)->entry.rbe_parent)->entry.rbe_left = (tmp); else ((parent)->entry.rbe_parent)->entry.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->entry .rbe_left = (parent); (parent)->entry.rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent)) do {} while ( 0); } while (0); tmp = parent; parent = elm; elm = tmp; } do { (parent)->entry.rbe_color = 0; (gparent)->entry.rbe_color = 1; } while (0); do { (tmp) = (gparent)->entry.rbe_left; if (((gparent)->entry.rbe_left = (tmp)->entry.rbe_right )) { ((tmp)->entry.rbe_right)->entry.rbe_parent = (gparent ); } do {} while (0); if (((tmp)->entry.rbe_parent = (gparent )->entry.rbe_parent)) { if ((gparent) == ((gparent)->entry .rbe_parent)->entry.rbe_left) ((gparent)->entry.rbe_parent )->entry.rbe_left = (tmp); else ((gparent)->entry.rbe_parent )->entry.rbe_right = (tmp); } else (head)->rbh_root = ( tmp); (tmp)->entry.rbe_right = (gparent); (gparent)->entry .rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent )) do {} while (0); } while (0); } else { tmp = (gparent)-> entry.rbe_left; if (tmp && (tmp)->entry.rbe_color == 1) { (tmp)->entry.rbe_color = 0; do { (parent)->entry. rbe_color = 0; (gparent)->entry.rbe_color = 1; } while (0) ; elm = gparent; continue; } if ((parent)->entry.rbe_left == elm) { do { (tmp) = (parent)->entry.rbe_left; if (((parent )->entry.rbe_left = (tmp)->entry.rbe_right)) { ((tmp)-> entry.rbe_right)->entry.rbe_parent = (parent); } do {} while (0); if (((tmp)->entry.rbe_parent = (parent)->entry.rbe_parent )) { if ((parent) == ((parent)->entry.rbe_parent)->entry .rbe_left) ((parent)->entry.rbe_parent)->entry.rbe_left = (tmp); else ((parent)->entry.rbe_parent)->entry.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->entry .rbe_right = (parent); (parent)->entry.rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent)) do {} while (0); } while (0); tmp = parent; parent = elm; elm = tmp; } do { (parent)->entry.rbe_color = 0; (gparent)->entry.rbe_color = 1; } while (0); do { (tmp) = (gparent)->entry.rbe_right ; if (((gparent)->entry.rbe_right = (tmp)->entry.rbe_left )) { ((tmp)->entry.rbe_left)->entry.rbe_parent = (gparent ); } do {} while (0); if (((tmp)->entry.rbe_parent = (gparent )->entry.rbe_parent)) { if ((gparent) == ((gparent)->entry .rbe_parent)->entry.rbe_left) ((gparent)->entry.rbe_parent )->entry.rbe_left = (tmp); else ((gparent)->entry.rbe_parent )->entry.rbe_right = (tmp); } else (head)->rbh_root = ( tmp); (tmp)->entry.rbe_left = (gparent); (gparent)->entry .rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent )) do {} while (0); } while (0); } } (head->rbh_root)-> entry.rbe_color = 0; } void rt_tree_RB_REMOVE_COLOR(struct rt_tree *head, struct rt_node *parent, struct rt_node *elm) { struct rt_node *tmp; while ((elm == ((void *)0) || (elm)->entry. rbe_color == 0) && elm != (head)->rbh_root) { if ( (parent)->entry.rbe_left == elm) { tmp = (parent)->entry .rbe_right; if ((tmp)->entry.rbe_color == 1) { do { (tmp)-> entry.rbe_color = 0; (parent)->entry.rbe_color = 1; } while (0); do { (tmp) = (parent)->entry.rbe_right; if (((parent )->entry.rbe_right = (tmp)->entry.rbe_left)) { ((tmp)-> entry.rbe_left)->entry.rbe_parent = (parent); } do {} while (0); if (((tmp)->entry.rbe_parent = (parent)->entry.rbe_parent )) { if ((parent) == ((parent)->entry.rbe_parent)->entry .rbe_left) ((parent)->entry.rbe_parent)->entry.rbe_left = (tmp); else ((parent)->entry.rbe_parent)->entry.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->entry .rbe_left = (parent); (parent)->entry.rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent)) do {} while ( 0); } while (0); tmp = (parent)->entry.rbe_right; } if ((( tmp)->entry.rbe_left == ((void *)0) || ((tmp)->entry.rbe_left )->entry.rbe_color == 0) && ((tmp)->entry.rbe_right == ((void *)0) || ((tmp)->entry.rbe_right)->entry.rbe_color == 0)) { (tmp)->entry.rbe_color = 1; elm = parent; parent = (elm)->entry.rbe_parent; } else { if ((tmp)->entry.rbe_right == ((void *)0) || ((tmp)->entry.rbe_right)->entry.rbe_color == 0) { struct rt_node *oleft; if ((oleft = (tmp)->entry. rbe_left)) (oleft)->entry.rbe_color = 0; (tmp)->entry.rbe_color = 1; do { (oleft) = (tmp)->entry.rbe_left; if (((tmp)-> entry.rbe_left = (oleft)->entry.rbe_right)) { ((oleft)-> entry.rbe_right)->entry.rbe_parent = (tmp); } do {} while ( 0); if (((oleft)->entry.rbe_parent = (tmp)->entry.rbe_parent )) { if ((tmp) == ((tmp)->entry.rbe_parent)->entry.rbe_left ) ((tmp)->entry.rbe_parent)->entry.rbe_left = (oleft); else ((tmp)->entry.rbe_parent)->entry.rbe_right = (oleft); } else (head)->rbh_root = (oleft); (oleft)->entry.rbe_right = (tmp); (tmp)->entry.rbe_parent = (oleft); do {} while ( 0); if (((oleft)->entry.rbe_parent)) do {} while (0); } while (0); tmp = (parent)->entry.rbe_right; } (tmp)->entry.rbe_color = (parent)->entry.rbe_color; (parent)->entry.rbe_color = 0; if ((tmp)->entry.rbe_right) ((tmp)->entry.rbe_right )->entry.rbe_color = 0; do { (tmp) = (parent)->entry.rbe_right ; if (((parent)->entry.rbe_right = (tmp)->entry.rbe_left )) { ((tmp)->entry.rbe_left)->entry.rbe_parent = (parent ); } do {} while (0); if (((tmp)->entry.rbe_parent = (parent )->entry.rbe_parent)) { if ((parent) == ((parent)->entry .rbe_parent)->entry.rbe_left) ((parent)->entry.rbe_parent )->entry.rbe_left = (tmp); else ((parent)->entry.rbe_parent )->entry.rbe_right = (tmp); } else (head)->rbh_root = ( tmp); (tmp)->entry.rbe_left = (parent); (parent)->entry .rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent )) do {} while (0); } while (0); elm = (head)->rbh_root; break ; } } else { tmp = (parent)->entry.rbe_left; if ((tmp)-> entry.rbe_color == 1) { do { (tmp)->entry.rbe_color = 0; ( parent)->entry.rbe_color = 1; } while (0); do { (tmp) = (parent )->entry.rbe_left; if (((parent)->entry.rbe_left = (tmp )->entry.rbe_right)) { ((tmp)->entry.rbe_right)->entry .rbe_parent = (parent); } do {} while (0); if (((tmp)->entry .rbe_parent = (parent)->entry.rbe_parent)) { if ((parent) == ((parent)->entry.rbe_parent)->entry.rbe_left) ((parent )->entry.rbe_parent)->entry.rbe_left = (tmp); else ((parent )->entry.rbe_parent)->entry.rbe_right = (tmp); } else ( head)->rbh_root = (tmp); (tmp)->entry.rbe_right = (parent ); (parent)->entry.rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent)) do {} while (0); } while (0); tmp = (parent)->entry.rbe_left; } if (((tmp)->entry.rbe_left == ((void *)0) || ((tmp)->entry.rbe_left)->entry.rbe_color == 0) && ((tmp)->entry.rbe_right == ((void *)0) || ((tmp)->entry.rbe_right)->entry.rbe_color == 0)) { (tmp )->entry.rbe_color = 1; elm = parent; parent = (elm)->entry .rbe_parent; } else { if ((tmp)->entry.rbe_left == ((void * )0) || ((tmp)->entry.rbe_left)->entry.rbe_color == 0) { struct rt_node *oright; if ((oright = (tmp)->entry.rbe_right )) (oright)->entry.rbe_color = 0; (tmp)->entry.rbe_color = 1; do { (oright) = (tmp)->entry.rbe_right; if (((tmp)-> entry.rbe_right = (oright)->entry.rbe_left)) { ((oright)-> entry.rbe_left)->entry.rbe_parent = (tmp); } do {} while ( 0); if (((oright)->entry.rbe_parent = (tmp)->entry.rbe_parent )) { if ((tmp) == ((tmp)->entry.rbe_parent)->entry.rbe_left ) ((tmp)->entry.rbe_parent)->entry.rbe_left = (oright); else ((tmp)->entry.rbe_parent)->entry.rbe_right = (oright ); } else (head)->rbh_root = (oright); (oright)->entry. rbe_left = (tmp); (tmp)->entry.rbe_parent = (oright); do { } while (0); if (((oright)->entry.rbe_parent)) do {} while (0); } while (0); tmp = (parent)->entry.rbe_left; } (tmp) ->entry.rbe_color = (parent)->entry.rbe_color; (parent) ->entry.rbe_color = 0; if ((tmp)->entry.rbe_left) ((tmp )->entry.rbe_left)->entry.rbe_color = 0; do { (tmp) = ( parent)->entry.rbe_left; if (((parent)->entry.rbe_left = (tmp)->entry.rbe_right)) { ((tmp)->entry.rbe_right)-> entry.rbe_parent = (parent); } do {} while (0); if (((tmp)-> entry.rbe_parent = (parent)->entry.rbe_parent)) { if ((parent ) == ((parent)->entry.rbe_parent)->entry.rbe_left) ((parent )->entry.rbe_parent)->entry.rbe_left = (tmp); else ((parent )->entry.rbe_parent)->entry.rbe_right = (tmp); } else ( head)->rbh_root = (tmp); (tmp)->entry.rbe_right = (parent ); (parent)->entry.rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent)) do {} while (0); } while (0); elm = (head)->rbh_root; break; } } } if (elm) (elm)->entry .rbe_color = 0; } struct rt_node * rt_tree_RB_REMOVE(struct rt_tree *head, struct rt_node *elm) { struct rt_node *child, *parent , *old = elm; int color; if ((elm)->entry.rbe_left == ((void *)0)) child = (elm)->entry.rbe_right; else if ((elm)-> entry.rbe_right == ((void *)0)) child = (elm)->entry.rbe_left ; else { struct rt_node *left; elm = (elm)->entry.rbe_right ; while ((left = (elm)->entry.rbe_left)) elm = left; child = (elm)->entry.rbe_right; parent = (elm)->entry.rbe_parent ; color = (elm)->entry.rbe_color; if (child) (child)->entry .rbe_parent = parent; if (parent) { if ((parent)->entry.rbe_left == elm) (parent)->entry.rbe_left = child; else (parent)-> entry.rbe_right = child; do {} while (0); } else (head)->rbh_root = child; if ((elm)->entry.rbe_parent == old) parent = elm ; (elm)->entry = (old)->entry; if ((old)->entry.rbe_parent ) { if (((old)->entry.rbe_parent)->entry.rbe_left == old ) ((old)->entry.rbe_parent)->entry.rbe_left = elm; else ((old)->entry.rbe_parent)->entry.rbe_right = elm; do { } while (0); } else (head)->rbh_root = elm; ((old)->entry .rbe_left)->entry.rbe_parent = elm; if ((old)->entry.rbe_right ) ((old)->entry.rbe_right)->entry.rbe_parent = elm; if ( parent) { left = parent; do { do {} while (0); } while ((left = (left)->entry.rbe_parent)); } goto color; } parent = (elm )->entry.rbe_parent; color = (elm)->entry.rbe_color; if (child) (child)->entry.rbe_parent = parent; if (parent) { if ((parent)->entry.rbe_left == elm) (parent)->entry.rbe_left = child; else (parent)->entry.rbe_right = child; do {} while (0); } else (head)->rbh_root = child; color: if (color == 0) rt_tree_RB_REMOVE_COLOR(head, parent, child); return (old ); } struct rt_node * rt_tree_RB_INSERT(struct rt_tree *head, struct rt_node *elm) { struct rt_node *tmp; struct rt_node * parent = ((void *)0); int comp = 0; tmp = (head)->rbh_root ; while (tmp) { parent = tmp; comp = (rt_compare)(elm, parent ); if (comp < 0) tmp = (tmp)->entry.rbe_left; else if ( comp > 0) tmp = (tmp)->entry.rbe_right; else return (tmp ); } do { (elm)->entry.rbe_parent = parent; (elm)->entry .rbe_left = (elm)->entry.rbe_right = ((void *)0); (elm)-> entry.rbe_color = 1; } while (0); if (parent != ((void *)0)) { if (comp < 0) (parent)->entry.rbe_left = elm; else (parent )->entry.rbe_right = elm; do {} while (0); } else (head)-> rbh_root = elm; rt_tree_RB_INSERT_COLOR(head, elm); return (( (void *)0)); } struct rt_node * rt_tree_RB_FIND(struct rt_tree *head, struct rt_node *elm) { struct rt_node *tmp = (head)-> rbh_root; int comp; while (tmp) { comp = rt_compare(elm, tmp) ; if (comp < 0) tmp = (tmp)->entry.rbe_left; else if (comp > 0) tmp = (tmp)->entry.rbe_right; else return (tmp); } return (((void *)0)); } struct rt_node * rt_tree_RB_NFIND(struct rt_tree *head, struct rt_node *elm) { struct rt_node *tmp = ( head)->rbh_root; struct rt_node *res = ((void *)0); int comp ; while (tmp) { comp = rt_compare(elm, tmp); if (comp < 0) { res = tmp; tmp = (tmp)->entry.rbe_left; } else if (comp > 0) tmp = (tmp)->entry.rbe_right; else return (tmp); } return (res); } struct rt_node * rt_tree_RB_NEXT(struct rt_node *elm) { if ((elm)->entry.rbe_right) { elm = (elm)->entry .rbe_right; while ((elm)->entry.rbe_left) elm = (elm)-> entry.rbe_left; } else { if ((elm)->entry.rbe_parent && (elm == ((elm)->entry.rbe_parent)->entry.rbe_left)) elm = (elm)->entry.rbe_parent; else { while ((elm)->entry. rbe_parent && (elm == ((elm)->entry.rbe_parent)-> entry.rbe_right)) elm = (elm)->entry.rbe_parent; elm = (elm )->entry.rbe_parent; } } return (elm); } struct rt_node * rt_tree_RB_PREV (struct rt_node *elm) { if ((elm)->entry.rbe_left) { elm = (elm)->entry.rbe_left; while ((elm)->entry.rbe_right) elm = (elm)->entry.rbe_right; } else { if ((elm)->entry.rbe_parent && (elm == ((elm)->entry.rbe_parent)->entry.rbe_right )) elm = (elm)->entry.rbe_parent; else { while ((elm)-> entry.rbe_parent && (elm == ((elm)->entry.rbe_parent )->entry.rbe_left)) elm = (elm)->entry.rbe_parent; elm = (elm)->entry.rbe_parent; } } return (elm); } struct rt_node * rt_tree_RB_MINMAX(struct rt_tree *head, int val) { struct rt_node *tmp = (head)->rbh_root; struct rt_node *parent = ((void * )0); while (tmp) { parent = tmp; if (val < 0) tmp = (tmp)-> entry.rbe_left; else tmp = (tmp)->entry.rbe_right; } return (parent); } |
37 | struct vertex *spf_root = NULL((void *)0); |
38 | |
39 | struct in6_addr *calc_nexthop_lladdr(struct vertex *, struct lsa_rtr_link *, |
40 | unsigned int); |
41 | void calc_nexthop_transit_nbr(struct vertex *, struct vertex *, |
42 | unsigned int); |
43 | void calc_nexthop(struct vertex *, struct vertex *, |
44 | struct area *, struct lsa_rtr_link *); |
45 | void rt_nexthop_clear(struct rt_node *); |
46 | void rt_nexthop_add(struct rt_node *, struct v_nexthead *, |
47 | u_int16_t, struct in_addr); |
48 | void rt_update(struct in6_addr *, u_int8_t, struct v_nexthead *, |
49 | u_int16_t, u_int32_t, u_int32_t, struct in_addr, |
50 | struct in_addr, enum path_type, enum dst_type, u_int8_t, |
51 | u_int32_t); |
52 | struct rt_node *rt_lookup(enum dst_type, struct in6_addr *); |
53 | void rt_invalidate(struct area *); |
54 | int linked(struct vertex *, struct vertex *); |
55 | |
56 | void |
57 | spf_calc(struct area *area) |
58 | { |
59 | struct vertex *v, *w; |
60 | struct lsa_rtr_link *rtr_link = NULL((void *)0); |
61 | struct lsa_net_link *net_link; |
62 | u_int32_t d; |
63 | unsigned int i; |
64 | |
65 | /* clear SPF tree */ |
66 | spf_tree_clr(area); |
67 | cand_list_clr(); |
68 | |
69 | /* initialize SPF tree */ |
70 | if ((v = spf_root = lsa_find_rtr(area, rde_router_id())) == NULL((void *)0)) |
71 | /* empty area because no interface is active */ |
72 | return; |
73 | |
74 | area->transit = 0; |
75 | spf_root->cost = 0; |
76 | w = NULL((void *)0); |
77 | |
78 | /* calculate SPF tree */ |
79 | do { |
80 | /* loop links */ |
81 | for (i = 0; i < lsa_num_links(v); i++) { |
82 | switch (v->type) { |
83 | case LSA_TYPE_ROUTER0x2001: |
84 | rtr_link = get_rtr_link(v, i); |
85 | switch (rtr_link->type) { |
86 | case LINK_TYPE_POINTTOPOINT1: |
87 | case LINK_TYPE_VIRTUAL4: |
88 | /* find router LSA */ |
89 | w = lsa_find_rtr(area, |
90 | rtr_link->nbr_rtr_id); |
91 | break; |
92 | case LINK_TYPE_TRANSIT_NET2: |
93 | /* find network LSA */ |
94 | w = lsa_find_tree(&area->lsa_tree, |
95 | htons(LSA_TYPE_NETWORK)(__uint16_t)(__builtin_constant_p(0x2002) ? (__uint16_t)(((__uint16_t )(0x2002) & 0xffU) << 8 | ((__uint16_t)(0x2002) & 0xff00U) >> 8) : __swap16md(0x2002)), |
96 | rtr_link->nbr_iface_id, |
97 | rtr_link->nbr_rtr_id); |
98 | break; |
99 | default: |
100 | fatalx("spf_calc: invalid link type"); |
101 | } |
102 | break; |
103 | case LSA_TYPE_NETWORK0x2002: |
104 | net_link = get_net_link(v, i); |
105 | /* find router LSA */ |
106 | w = lsa_find_rtr(area, net_link->att_rtr); |
107 | break; |
108 | default: |
109 | fatalx("spf_calc: invalid LSA type"); |
110 | } |
111 | |
112 | if (w == NULL((void *)0)) |
113 | continue; |
114 | |
115 | if (ntohs(w->lsa->hdr.age)(__uint16_t)(__builtin_constant_p(w->lsa->hdr.age) ? (__uint16_t )(((__uint16_t)(w->lsa->hdr.age) & 0xffU) << 8 | ((__uint16_t)(w->lsa->hdr.age) & 0xff00U) >> 8) : __swap16md(w->lsa->hdr.age)) == MAX_AGE3600) |
116 | continue; |
117 | |
118 | if (lsa_num_links(w) == 0) |
119 | continue; |
120 | |
121 | if (!linked(w, v)) { |
122 | log_debug("spf_calc: w adv_rtr %s ls_id %s " |
123 | "type 0x%x numlinks %hu has no link to " |
124 | "v adv_rtr %s ls_id %s type 0x%x", |
125 | log_rtr_id(htonl(w->adv_rtr)(__uint32_t)(__builtin_constant_p(w->adv_rtr) ? (__uint32_t )(((__uint32_t)(w->adv_rtr) & 0xff) << 24 | ((__uint32_t )(w->adv_rtr) & 0xff00) << 8 | ((__uint32_t)(w-> adv_rtr) & 0xff0000) >> 8 | ((__uint32_t)(w->adv_rtr ) & 0xff000000) >> 24) : __swap32md(w->adv_rtr))), |
126 | log_rtr_id(htonl(w->ls_id)(__uint32_t)(__builtin_constant_p(w->ls_id) ? (__uint32_t) (((__uint32_t)(w->ls_id) & 0xff) << 24 | ((__uint32_t )(w->ls_id) & 0xff00) << 8 | ((__uint32_t)(w-> ls_id) & 0xff0000) >> 8 | ((__uint32_t)(w->ls_id ) & 0xff000000) >> 24) : __swap32md(w->ls_id))), w->type, |
127 | lsa_num_links(w), |
128 | log_rtr_id(htonl(v->adv_rtr)(__uint32_t)(__builtin_constant_p(v->adv_rtr) ? (__uint32_t )(((__uint32_t)(v->adv_rtr) & 0xff) << 24 | ((__uint32_t )(v->adv_rtr) & 0xff00) << 8 | ((__uint32_t)(v-> adv_rtr) & 0xff0000) >> 8 | ((__uint32_t)(v->adv_rtr ) & 0xff000000) >> 24) : __swap32md(v->adv_rtr))), |
129 | log_rtr_id(htonl(v->ls_id)(__uint32_t)(__builtin_constant_p(v->ls_id) ? (__uint32_t) (((__uint32_t)(v->ls_id) & 0xff) << 24 | ((__uint32_t )(v->ls_id) & 0xff00) << 8 | ((__uint32_t)(v-> ls_id) & 0xff0000) >> 8 | ((__uint32_t)(v->ls_id ) & 0xff000000) >> 24) : __swap32md(v->ls_id))), v->type); |
130 | continue; |
131 | } |
132 | |
133 | if (v->type == LSA_TYPE_ROUTER0x2001) |
134 | d = v->cost + ntohs(rtr_link->metric)(__uint16_t)(__builtin_constant_p(rtr_link->metric) ? (__uint16_t )(((__uint16_t)(rtr_link->metric) & 0xffU) << 8 | ((__uint16_t)(rtr_link->metric) & 0xff00U) >> 8 ) : __swap16md(rtr_link->metric)); |
135 | else |
136 | d = v->cost; |
137 | |
138 | if (cand_list_present(w)) { |
139 | if (d > w->cost) |
140 | continue; |
141 | if (d < w->cost) { |
142 | w->cost = d; |
143 | vertex_nexthop_clear(w); |
144 | calc_nexthop(w, v, area, rtr_link); |
145 | /* |
146 | * need to readd to candidate list |
147 | * because the list is sorted |
148 | */ |
149 | TAILQ_REMOVE(&cand_list, w, cand)do { if (((w)->cand.tqe_next) != ((void *)0)) (w)->cand .tqe_next->cand.tqe_prev = (w)->cand.tqe_prev; else (& cand_list)->tqh_last = (w)->cand.tqe_prev; *(w)->cand .tqe_prev = (w)->cand.tqe_next; ; ; } while (0); |
150 | cand_list_add(w); |
151 | } else |
152 | /* equal cost path */ |
153 | calc_nexthop(w, v, area, rtr_link); |
154 | } else if (w->cost == LS_INFINITY0xffffff && d < LS_INFINITY0xffffff) { |
155 | w->cost = d; |
156 | |
157 | vertex_nexthop_clear(w); |
158 | calc_nexthop(w, v, area, rtr_link); |
159 | cand_list_add(w); |
160 | } |
161 | } |
162 | |
163 | /* get next vertex */ |
164 | v = cand_list_pop(); |
165 | w = NULL((void *)0); |
166 | } while (v != NULL((void *)0)); |
167 | |
168 | /* spf_dump(area); */ |
169 | log_debug("spf_calc: area %s calculated", inet_ntoa(area->id)); |
170 | |
171 | /* Dump SPF tree to log */ |
172 | RB_FOREACH(v, lsa_tree, &area->lsa_tree)for ((v) = lsa_tree_RB_MINMAX(&area->lsa_tree, -1); (v ) != ((void *)0); (v) = lsa_tree_RB_NEXT(v)) { |
173 | struct v_nexthop *vn; |
174 | char hops[4096]; |
175 | struct iface *iface; |
176 | |
177 | bzero(hops, sizeof(hops)); |
178 | |
179 | if (v->type != LSA_TYPE_ROUTER0x2001 && v->type != LSA_TYPE_NETWORK0x2002) |
180 | continue; |
181 | |
182 | TAILQ_FOREACH(vn, &v->nexthop, entry)for((vn) = ((&v->nexthop)->tqh_first); (vn) != ((void *)0); (vn) = ((vn)->entry.tqe_next)) { |
183 | strlcat(hops, log_in6addr(&vn->nexthop), sizeof(hops)); |
184 | strlcat(hops, "%", sizeof(hops)); |
185 | if ((iface = if_find(vn->ifindex)) == NULL((void *)0)) |
186 | fatalx("spf_calc: lost iface"); |
187 | strlcat(hops, iface->name, sizeof(hops)); |
188 | if (vn != TAILQ_LAST(&v->nexthop, v_nexthead)(*(((struct v_nexthead *)((&v->nexthop)->tqh_last)) ->tqh_last))) |
189 | strlcat(hops, ", ", sizeof(hops)); |
190 | } |
191 | log_debug("%s(%s, 0x%x, %s) cost %u has nexthops [%s]", |
192 | v == spf_root ? "*" : " ", log_rtr_id(htonl(v->adv_rtr)(__uint32_t)(__builtin_constant_p(v->adv_rtr) ? (__uint32_t )(((__uint32_t)(v->adv_rtr) & 0xff) << 24 | ((__uint32_t )(v->adv_rtr) & 0xff00) << 8 | ((__uint32_t)(v-> adv_rtr) & 0xff0000) >> 8 | ((__uint32_t)(v->adv_rtr ) & 0xff000000) >> 24) : __swap32md(v->adv_rtr))), |
193 | v->type, log_rtr_id(htonl(v->ls_id)(__uint32_t)(__builtin_constant_p(v->ls_id) ? (__uint32_t) (((__uint32_t)(v->ls_id) & 0xff) << 24 | ((__uint32_t )(v->ls_id) & 0xff00) << 8 | ((__uint32_t)(v-> ls_id) & 0xff0000) >> 8 | ((__uint32_t)(v->ls_id ) & 0xff000000) >> 24) : __swap32md(v->ls_id))), v->cost, hops); |
194 | } |
195 | |
196 | area->num_spf_calc++; |
197 | start_spf_timer(); |
198 | } |
199 | |
200 | void |
201 | rt_calc(struct vertex *v, struct area *area, struct ospfd_conf *conf) |
202 | { |
203 | struct vertex *w; |
204 | struct lsa_intra_prefix *iap; |
205 | struct lsa_prefix *prefix; |
206 | struct in_addr adv_rtr; |
207 | struct in6_addr ia6; |
208 | u_int16_t i, off; |
209 | u_int8_t flags; |
210 | |
211 | lsa_age(v); |
212 | if (ntohs(v->lsa->hdr.age)(__uint16_t)(__builtin_constant_p(v->lsa->hdr.age) ? (__uint16_t )(((__uint16_t)(v->lsa->hdr.age) & 0xffU) << 8 | ((__uint16_t)(v->lsa->hdr.age) & 0xff00U) >> 8) : __swap16md(v->lsa->hdr.age)) == MAX_AGE3600) |
213 | return; |
214 | |
215 | switch (v->type) { |
216 | case LSA_TYPE_ROUTER0x2001: |
217 | if (v->cost >= LS_INFINITY0xffffff || TAILQ_EMPTY(&v->nexthop)(((&v->nexthop)->tqh_first) == ((void *)0))) |
218 | return; |
219 | |
220 | /* router, only add border and as-external routers */ |
221 | flags = LSA_24_GETHI(ntohl(v->lsa->data.rtr.opts))(((__uint32_t)(__builtin_constant_p(v->lsa->data.rtr.opts ) ? (__uint32_t)(((__uint32_t)(v->lsa->data.rtr.opts) & 0xff) << 24 | ((__uint32_t)(v->lsa->data.rtr.opts ) & 0xff00) << 8 | ((__uint32_t)(v->lsa->data .rtr.opts) & 0xff0000) >> 8 | ((__uint32_t)(v->lsa ->data.rtr.opts) & 0xff000000) >> 24) : __swap32md (v->lsa->data.rtr.opts))) >> 24); |
222 | if ((flags & (OSPF_RTR_B0x01 | OSPF_RTR_E0x02)) == 0) |
223 | return; |
224 | |
225 | bzero(&ia6, sizeof(ia6)); |
226 | adv_rtr.s_addr = htonl(v->adv_rtr)(__uint32_t)(__builtin_constant_p(v->adv_rtr) ? (__uint32_t )(((__uint32_t)(v->adv_rtr) & 0xff) << 24 | ((__uint32_t )(v->adv_rtr) & 0xff00) << 8 | ((__uint32_t)(v-> adv_rtr) & 0xff0000) >> 8 | ((__uint32_t)(v->adv_rtr ) & 0xff000000) >> 24) : __swap32md(v->adv_rtr)); |
227 | bcopy(&adv_rtr, &ia6.s6_addr__u6_addr.__u6_addr8[12], sizeof(adv_rtr)); |
228 | |
229 | rt_update(&ia6, 128, &v->nexthop, v->type, v->cost, 0, area->id, |
230 | adv_rtr, PT_INTER_AREA, DT_RTR, flags, 0); |
231 | break; |
232 | case LSA_TYPE_INTRA_A_PREFIX0x2009: |
233 | /* Find referenced LSA */ |
234 | iap = &v->lsa->data.pref_intra; |
235 | switch (ntohs(iap->ref_type)(__uint16_t)(__builtin_constant_p(iap->ref_type) ? (__uint16_t )(((__uint16_t)(iap->ref_type) & 0xffU) << 8 | ( (__uint16_t)(iap->ref_type) & 0xff00U) >> 8) : __swap16md (iap->ref_type))) { |
236 | case LSA_TYPE_ROUTER0x2001: |
237 | w = lsa_find_rtr(area, iap->ref_adv_rtr); |
238 | if (w == NULL((void *)0)) { |
239 | warnx("rt_calc: Intra-Area-Prefix LSA (%s, %u) " |
240 | "references non-existent router %s", |
241 | log_rtr_id(htonl(v->adv_rtr)(__uint32_t)(__builtin_constant_p(v->adv_rtr) ? (__uint32_t )(((__uint32_t)(v->adv_rtr) & 0xff) << 24 | ((__uint32_t )(v->adv_rtr) & 0xff00) << 8 | ((__uint32_t)(v-> adv_rtr) & 0xff0000) >> 8 | ((__uint32_t)(v->adv_rtr ) & 0xff000000) >> 24) : __swap32md(v->adv_rtr))), |
242 | v->ls_id, log_rtr_id(iap->ref_adv_rtr)); |
243 | return; |
244 | } |
245 | flags = LSA_24_GETHI(ntohl(w->lsa->data.rtr.opts))(((__uint32_t)(__builtin_constant_p(w->lsa->data.rtr.opts ) ? (__uint32_t)(((__uint32_t)(w->lsa->data.rtr.opts) & 0xff) << 24 | ((__uint32_t)(w->lsa->data.rtr.opts ) & 0xff00) << 8 | ((__uint32_t)(w->lsa->data .rtr.opts) & 0xff0000) >> 8 | ((__uint32_t)(w->lsa ->data.rtr.opts) & 0xff000000) >> 24) : __swap32md (w->lsa->data.rtr.opts))) >> 24); |
246 | break; |
247 | case LSA_TYPE_NETWORK0x2002: |
248 | w = lsa_find_tree(&area->lsa_tree, iap->ref_type, |
249 | iap->ref_ls_id, iap->ref_adv_rtr); |
250 | if (w == NULL((void *)0)) { |
251 | warnx("rt_calc: Intra-Area-Prefix LSA (%s, %u) " |
252 | "references non-existent Network LSA (%s, " |
253 | "%u)", log_rtr_id(htonl(v->adv_rtr)(__uint32_t)(__builtin_constant_p(v->adv_rtr) ? (__uint32_t )(((__uint32_t)(v->adv_rtr) & 0xff) << 24 | ((__uint32_t )(v->adv_rtr) & 0xff00) << 8 | ((__uint32_t)(v-> adv_rtr) & 0xff0000) >> 8 | ((__uint32_t)(v->adv_rtr ) & 0xff000000) >> 24) : __swap32md(v->adv_rtr))), |
254 | v->ls_id, log_rtr_id(iap->ref_adv_rtr), |
255 | ntohl(iap->ref_ls_id)(__uint32_t)(__builtin_constant_p(iap->ref_ls_id) ? (__uint32_t )(((__uint32_t)(iap->ref_ls_id) & 0xff) << 24 | ( (__uint32_t)(iap->ref_ls_id) & 0xff00) << 8 | (( __uint32_t)(iap->ref_ls_id) & 0xff0000) >> 8 | ( (__uint32_t)(iap->ref_ls_id) & 0xff000000) >> 24 ) : __swap32md(iap->ref_ls_id))); |
256 | return; |
257 | } |
258 | flags = 0; |
259 | break; |
260 | default: |
261 | warnx("rt_calc: Intra-Area-Prefix LSA (%s, %u) has " |
262 | "invalid ref_type 0x%hx", log_rtr_id(v->adv_rtr), |
263 | v->ls_id, ntohs(iap->ref_type)(__uint16_t)(__builtin_constant_p(iap->ref_type) ? (__uint16_t )(((__uint16_t)(iap->ref_type) & 0xffU) << 8 | ( (__uint16_t)(iap->ref_type) & 0xff00U) >> 8) : __swap16md (iap->ref_type))); |
264 | return; |
265 | } |
266 | |
267 | if (w->cost >= LS_INFINITY0xffffff || TAILQ_EMPTY(&w->nexthop)(((&w->nexthop)->tqh_first) == ((void *)0))) |
268 | return; |
269 | |
270 | /* Add prefixes listed in Intra-Area-Prefix LSA to routing |
271 | * table, using w as destination. */ |
272 | off = sizeof(v->lsa->hdr) + sizeof(struct lsa_intra_prefix); |
273 | for (i = 0; i < ntohs(v->lsa->data.pref_intra.numprefix)(__uint16_t)(__builtin_constant_p(v->lsa->data.pref_intra .numprefix) ? (__uint16_t)(((__uint16_t)(v->lsa->data.pref_intra .numprefix) & 0xffU) << 8 | ((__uint16_t)(v->lsa ->data.pref_intra.numprefix) & 0xff00U) >> 8) : __swap16md (v->lsa->data.pref_intra.numprefix)); i++) { |
274 | prefix = (struct lsa_prefix *)((char *)(v->lsa) + off); |
275 | if (!(prefix->options & OSPF_PREFIX_NU0x01)) { |
276 | bzero(&ia6, sizeof(ia6)); |
277 | bcopy(prefix + 1, &ia6, |
278 | LSA_PREFIXSIZE(prefix->prefixlen)(((prefix->prefixlen) + 31)/32 * 4)); |
279 | |
280 | adv_rtr.s_addr = htonl(w->adv_rtr)(__uint32_t)(__builtin_constant_p(w->adv_rtr) ? (__uint32_t )(((__uint32_t)(w->adv_rtr) & 0xff) << 24 | ((__uint32_t )(w->adv_rtr) & 0xff00) << 8 | ((__uint32_t)(w-> adv_rtr) & 0xff0000) >> 8 | ((__uint32_t)(w->adv_rtr ) & 0xff000000) >> 24) : __swap32md(w->adv_rtr)); |
281 | |
282 | rt_update(&ia6, prefix->prefixlen, &w->nexthop, |
283 | v->type, w->cost + ntohs(prefix->metric)(__uint16_t)(__builtin_constant_p(prefix->metric) ? (__uint16_t )(((__uint16_t)(prefix->metric) & 0xffU) << 8 | ( (__uint16_t)(prefix->metric) & 0xff00U) >> 8) : __swap16md (prefix->metric)), 0, |
284 | area->id, adv_rtr, PT_INTRA_AREA, DT_NET, |
285 | flags, 0); |
286 | } |
287 | off += sizeof(struct lsa_prefix) |
288 | + LSA_PREFIXSIZE(prefix->prefixlen)(((prefix->prefixlen) + 31)/32 * 4); |
289 | } |
290 | break; |
291 | case LSA_TYPE_INTER_A_PREFIX0x2003: |
292 | /* XXX if ABR only look at area 0.0.0.0 LSA */ |
293 | /* ignore self-originated stuff */ |
294 | if (v->self) |
295 | return; |
296 | |
297 | adv_rtr.s_addr = htonl(v->adv_rtr)(__uint32_t)(__builtin_constant_p(v->adv_rtr) ? (__uint32_t )(((__uint32_t)(v->adv_rtr) & 0xff) << 24 | ((__uint32_t )(v->adv_rtr) & 0xff00) << 8 | ((__uint32_t)(v-> adv_rtr) & 0xff0000) >> 8 | ((__uint32_t)(v->adv_rtr ) & 0xff000000) >> 24) : __swap32md(v->adv_rtr)); |
298 | w = lsa_find_rtr(area, adv_rtr.s_addr); |
299 | if (w == NULL((void *)0)) { |
300 | warnx("rt_calc: Inter-Area-Router LSA (%s, %u) " |
301 | "originated from non-existent router", |
302 | log_rtr_id(htonl(v->adv_rtr)(__uint32_t)(__builtin_constant_p(v->adv_rtr) ? (__uint32_t )(((__uint32_t)(v->adv_rtr) & 0xff) << 24 | ((__uint32_t )(v->adv_rtr) & 0xff00) << 8 | ((__uint32_t)(v-> adv_rtr) & 0xff0000) >> 8 | ((__uint32_t)(v->adv_rtr ) & 0xff000000) >> 24) : __swap32md(v->adv_rtr))), |
303 | v->ls_id); |
304 | return; |
305 | } |
306 | if (w->cost >= LS_INFINITY0xffffff || TAILQ_EMPTY(&w->nexthop)(((&w->nexthop)->tqh_first) == ((void *)0))) |
307 | return; |
308 | |
309 | /* Add prefix listed in Inter-Area-Prefix LSA to routing |
310 | * table, using w as destination. */ |
311 | off = sizeof(v->lsa->hdr) + sizeof(struct lsa_prefix_sum); |
312 | prefix = (struct lsa_prefix *)((char *)(v->lsa) + off); |
313 | if (prefix->options & OSPF_PREFIX_NU0x01) |
314 | return; |
315 | |
316 | bzero(&ia6, sizeof(ia6)); |
317 | bcopy(prefix + 1, &ia6, LSA_PREFIXSIZE(prefix->prefixlen)(((prefix->prefixlen) + 31)/32 * 4)); |
318 | |
319 | rt_update(&ia6, prefix->prefixlen, &w->nexthop, v->type, |
320 | w->cost + (ntohs(v->lsa->data.rtr_sum.metric)(__uint16_t)(__builtin_constant_p(v->lsa->data.rtr_sum. metric) ? (__uint16_t)(((__uint16_t)(v->lsa->data.rtr_sum .metric) & 0xffU) << 8 | ((__uint16_t)(v->lsa-> data.rtr_sum.metric) & 0xff00U) >> 8) : __swap16md( v->lsa->data.rtr_sum.metric)) & |
321 | LSA_METRIC_MASK0x00ffffff), 0, area->id, adv_rtr, PT_INTER_AREA, |
322 | DT_NET, 0, 0); |
323 | break; |
324 | case LSA_TYPE_INTER_A_ROUTER0x2004: |
325 | /* XXX if ABR only look at area 0.0.0.0 LSA */ |
326 | /* ignore self-originated stuff */ |
327 | if (v->self) |
328 | return; |
329 | |
330 | adv_rtr.s_addr = htonl(v->adv_rtr)(__uint32_t)(__builtin_constant_p(v->adv_rtr) ? (__uint32_t )(((__uint32_t)(v->adv_rtr) & 0xff) << 24 | ((__uint32_t )(v->adv_rtr) & 0xff00) << 8 | ((__uint32_t)(v-> adv_rtr) & 0xff0000) >> 8 | ((__uint32_t)(v->adv_rtr ) & 0xff000000) >> 24) : __swap32md(v->adv_rtr)); |
331 | w = lsa_find_rtr(area, adv_rtr.s_addr); |
332 | if (w == NULL((void *)0)) { |
333 | warnx("rt_calc: Inter-Area-Router LSA (%s, %u) " |
334 | "originated from non-existent router", |
335 | log_rtr_id(htonl(v->adv_rtr)(__uint32_t)(__builtin_constant_p(v->adv_rtr) ? (__uint32_t )(((__uint32_t)(v->adv_rtr) & 0xff) << 24 | ((__uint32_t )(v->adv_rtr) & 0xff00) << 8 | ((__uint32_t)(v-> adv_rtr) & 0xff0000) >> 8 | ((__uint32_t)(v->adv_rtr ) & 0xff000000) >> 24) : __swap32md(v->adv_rtr))), |
336 | v->ls_id); |
337 | return; |
338 | } |
339 | if (w->cost >= LS_INFINITY0xffffff || TAILQ_EMPTY(&w->nexthop)(((&w->nexthop)->tqh_first) == ((void *)0))) |
340 | return; |
341 | |
342 | /* Add router listed in Inter-Area-Router LSA to routing |
343 | * table, using w as destination. */ |
344 | bzero(&ia6, sizeof(ia6)); |
345 | bcopy(&v->lsa->data.rtr_sum.dest_rtr_id, &ia6.s6_addr__u6_addr.__u6_addr8[12], |
346 | 4); |
347 | |
348 | rt_update(&ia6, 128, &w->nexthop, v->type, w->cost + |
349 | (ntohs(v->lsa->data.rtr_sum.metric)(__uint16_t)(__builtin_constant_p(v->lsa->data.rtr_sum. metric) ? (__uint16_t)(((__uint16_t)(v->lsa->data.rtr_sum .metric) & 0xffU) << 8 | ((__uint16_t)(v->lsa-> data.rtr_sum.metric) & 0xff00U) >> 8) : __swap16md( v->lsa->data.rtr_sum.metric)) & LSA_METRIC_MASK0x00ffffff), 0, |
350 | area->id, adv_rtr, PT_INTER_AREA, DT_RTR, 0, 0); |
351 | break; |
352 | default: |
353 | break; |
354 | } |
355 | } |
356 | |
357 | void |
358 | asext_calc(struct vertex *v) |
359 | { |
360 | struct in6_addr addr, fw_addr; |
361 | struct rt_node *r; |
362 | struct rt_nexthop *rn; |
363 | struct lsa_prefix *prefix; |
364 | struct in_addr adv_rtr, area; |
365 | char *p; |
366 | u_int32_t metric, cost2, ext_tag = 0; |
367 | enum path_type type; |
368 | |
369 | lsa_age(v); |
370 | if (ntohs(v->lsa->hdr.age)(__uint16_t)(__builtin_constant_p(v->lsa->hdr.age) ? (__uint16_t )(((__uint16_t)(v->lsa->hdr.age) & 0xffU) << 8 | ((__uint16_t)(v->lsa->hdr.age) & 0xff00U) >> 8) : __swap16md(v->lsa->hdr.age)) == MAX_AGE3600 || |
371 | (ntohl(v->lsa->data.asext.metric)(__uint32_t)(__builtin_constant_p(v->lsa->data.asext.metric ) ? (__uint32_t)(((__uint32_t)(v->lsa->data.asext.metric ) & 0xff) << 24 | ((__uint32_t)(v->lsa->data. asext.metric) & 0xff00) << 8 | ((__uint32_t)(v-> lsa->data.asext.metric) & 0xff0000) >> 8 | ((__uint32_t )(v->lsa->data.asext.metric) & 0xff000000) >> 24) : __swap32md(v->lsa->data.asext.metric)) & LSA_METRIC_MASK0x00ffffff) >= |
372 | LS_INFINITY0xffffff) |
373 | return; |
374 | |
375 | switch (v->type) { |
376 | case LSA_TYPE_EXTERNAL0x4005: |
377 | /* ignore self-originated stuff */ |
378 | if (v->self) |
379 | return; |
380 | |
381 | adv_rtr.s_addr = htonl(v->adv_rtr)(__uint32_t)(__builtin_constant_p(v->adv_rtr) ? (__uint32_t )(((__uint32_t)(v->adv_rtr) & 0xff) << 24 | ((__uint32_t )(v->adv_rtr) & 0xff00) << 8 | ((__uint32_t)(v-> adv_rtr) & 0xff0000) >> 8 | ((__uint32_t)(v->adv_rtr ) & 0xff000000) >> 24) : __swap32md(v->adv_rtr)); |
382 | bzero(&addr, sizeof(addr)); |
383 | bcopy(&adv_rtr, &addr.s6_addr__u6_addr.__u6_addr8[12], sizeof(adv_rtr)); |
384 | if ((r = rt_lookup(DT_RTR, &addr)) == NULL((void *)0)) |
385 | return; |
386 | |
387 | prefix = &v->lsa->data.asext.prefix; |
388 | if (prefix->options & OSPF_PREFIX_NU0x01) |
389 | break; |
390 | bzero(&addr, sizeof(addr)); |
391 | bcopy(prefix + 1, &addr, |
392 | LSA_PREFIXSIZE(prefix->prefixlen)(((prefix->prefixlen) + 31)/32 * 4)); |
393 | |
394 | p = (char *)(prefix + 1) + LSA_PREFIXSIZE(prefix->prefixlen)(((prefix->prefixlen) + 31)/32 * 4); |
395 | metric = ntohl(v->lsa->data.asext.metric)(__uint32_t)(__builtin_constant_p(v->lsa->data.asext.metric ) ? (__uint32_t)(((__uint32_t)(v->lsa->data.asext.metric ) & 0xff) << 24 | ((__uint32_t)(v->lsa->data. asext.metric) & 0xff00) << 8 | ((__uint32_t)(v-> lsa->data.asext.metric) & 0xff0000) >> 8 | ((__uint32_t )(v->lsa->data.asext.metric) & 0xff000000) >> 24) : __swap32md(v->lsa->data.asext.metric)); |
396 | |
397 | if (metric & LSA_ASEXT_F_FLAG0x02000000) { |
398 | bcopy(p, &fw_addr, sizeof(fw_addr)); |
399 | p += sizeof(fw_addr); |
400 | |
401 | /* lookup forwarding address */ |
402 | if ((r = rt_lookup(DT_NET, &fw_addr)) == NULL((void *)0) || |
403 | (r->p_type != PT_INTRA_AREA && |
404 | r->p_type != PT_INTER_AREA)) |
405 | return; |
406 | } |
407 | if (metric & LSA_ASEXT_T_FLAG0x01000000) { |
408 | bcopy(p, &ext_tag, sizeof(ext_tag)); |
409 | p += sizeof(ext_tag); |
Value stored to 'p' is never read | |
410 | } |
411 | if (metric & LSA_ASEXT_E_FLAG0x04000000) { |
412 | v->cost = r->cost; |
413 | cost2 = metric & LSA_METRIC_MASK0x00ffffff; |
414 | type = PT_TYPE2_EXT; |
415 | } else { |
416 | v->cost = r->cost + (metric & LSA_METRIC_MASK0x00ffffff); |
417 | cost2 = 0; |
418 | type = PT_TYPE1_EXT; |
419 | } |
420 | |
421 | area.s_addr = 0; |
422 | vertex_nexthop_clear(v); |
423 | TAILQ_FOREACH(rn, &r->nexthop, entry)for((rn) = ((&r->nexthop)->tqh_first); (rn) != ((void *)0); (rn) = ((rn)->entry.tqe_next)) { |
424 | if (rn->invalid) |
425 | continue; |
426 | |
427 | if (rn->connected && r->d_type == DT_NET) { |
428 | if (metric & LSA_ASEXT_F_FLAG0x02000000) |
429 | vertex_nexthop_add(v, NULL((void *)0), &fw_addr, |
430 | rn->ifindex); |
431 | else |
432 | fatalx("asext_calc: I'm sorry Dave, " |
433 | "I'm afraid I can't do that."); |
434 | } else |
435 | vertex_nexthop_add(v, NULL((void *)0), &rn->nexthop, |
436 | rn->ifindex); |
437 | } |
438 | |
439 | rt_update(&addr, prefix->prefixlen, &v->nexthop, v->type, |
440 | v->cost, cost2, area, adv_rtr, type, DT_NET, 0, ext_tag); |
441 | break; |
442 | default: |
443 | fatalx("asext_calc: invalid LSA type"); |
444 | } |
445 | } |
446 | |
447 | void |
448 | spf_tree_clr(struct area *area) |
449 | { |
450 | struct lsa_tree *tree = &area->lsa_tree; |
451 | struct vertex *v; |
452 | |
453 | RB_FOREACH(v, lsa_tree, tree)for ((v) = lsa_tree_RB_MINMAX(tree, -1); (v) != ((void *)0); ( v) = lsa_tree_RB_NEXT(v)) { |
454 | v->cost = LS_INFINITY0xffffff; |
455 | vertex_nexthop_clear(v); |
456 | } |
457 | } |
458 | |
459 | struct in6_addr * |
460 | calc_nexthop_lladdr(struct vertex *dst, struct lsa_rtr_link *rtr_link, |
461 | unsigned int ifindex) |
462 | { |
463 | struct iface *iface; |
464 | struct vertex *link; |
465 | struct rde_nbr *nbr; |
466 | |
467 | /* Find outgoing interface, we need its LSA tree */ |
468 | LIST_FOREACH(iface, &dst->area->iface_list, entry)for((iface) = ((&dst->area->iface_list)->lh_first ); (iface)!= ((void *)0); (iface) = ((iface)->entry.le_next )) { |
469 | if (ifindex == iface->ifindex) |
470 | break; |
471 | } |
472 | if (!iface) { |
473 | log_warnx("calc_nexthop_lladdr: no interface found for " |
474 | "ifindex %d", ntohl(rtr_link->iface_id)(__uint32_t)(__builtin_constant_p(rtr_link->iface_id) ? (__uint32_t )(((__uint32_t)(rtr_link->iface_id) & 0xff) << 24 | ((__uint32_t)(rtr_link->iface_id) & 0xff00) << 8 | ((__uint32_t)(rtr_link->iface_id) & 0xff0000) >> 8 | ((__uint32_t)(rtr_link->iface_id) & 0xff000000) >> 24) : __swap32md(rtr_link->iface_id))); |
475 | return (NULL((void *)0)); |
476 | } |
477 | |
478 | /* Determine neighbor's link-local address. |
479 | * Try to get it from link LSA first. */ |
480 | link = lsa_find_tree(&iface->lsa_tree, |
481 | htons(LSA_TYPE_LINK)(__uint16_t)(__builtin_constant_p(0x0008) ? (__uint16_t)(((__uint16_t )(0x0008) & 0xffU) << 8 | ((__uint16_t)(0x0008) & 0xff00U) >> 8) : __swap16md(0x0008)), rtr_link->iface_id, |
482 | htonl(dst->adv_rtr)(__uint32_t)(__builtin_constant_p(dst->adv_rtr) ? (__uint32_t )(((__uint32_t)(dst->adv_rtr) & 0xff) << 24 | (( __uint32_t)(dst->adv_rtr) & 0xff00) << 8 | ((__uint32_t )(dst->adv_rtr) & 0xff0000) >> 8 | ((__uint32_t) (dst->adv_rtr) & 0xff000000) >> 24) : __swap32md (dst->adv_rtr))); |
483 | if (link) |
484 | return &link->lsa->data.link.lladdr; |
485 | |
486 | /* Not found, so fall back to source address |
487 | * advertised in hello packet. */ |
488 | if ((nbr = rde_nbr_find(dst->peerid)) == NULL((void *)0)) |
489 | fatalx("next hop is not a neighbor"); |
490 | return &nbr->addr; |
491 | } |
492 | |
493 | void |
494 | calc_nexthop_transit_nbr(struct vertex *dst, struct vertex *parent, |
495 | unsigned int ifindex) |
496 | { |
497 | struct lsa_rtr_link *rtr_link; |
498 | unsigned int i; |
499 | struct in6_addr *lladdr; |
500 | |
501 | if (dst->type != LSA_TYPE_ROUTER0x2001) |
502 | fatalx("calc_nexthop_transit_nbr: dst is not a router"); |
503 | if (parent->type != LSA_TYPE_NETWORK0x2002) |
504 | fatalx("calc_nexthop_transit_nbr: parent is not a network"); |
505 | |
506 | /* dst is a neighbor on a directly attached transit network. |
507 | * Figure out dst's link local address and add it as nexthop. */ |
508 | for (i = 0; i < lsa_num_links(dst); i++) { |
509 | rtr_link = get_rtr_link(dst, i); |
510 | if (rtr_link->type == LINK_TYPE_TRANSIT_NET2 && |
511 | rtr_link->nbr_rtr_id == parent->lsa->hdr.adv_rtr && |
512 | rtr_link->nbr_iface_id == parent->lsa->hdr.ls_id) { |
513 | lladdr = calc_nexthop_lladdr(dst, rtr_link, ifindex); |
514 | vertex_nexthop_add(dst, parent, lladdr, ifindex); |
515 | } |
516 | } |
517 | } |
518 | |
519 | void |
520 | calc_nexthop(struct vertex *dst, struct vertex *parent, |
521 | struct area *area, struct lsa_rtr_link *rtr_link) |
522 | { |
523 | struct v_nexthop *vn; |
524 | struct in6_addr *nexthop; |
525 | |
526 | /* case 1 */ |
527 | if (parent == spf_root) { |
528 | switch (dst->type) { |
529 | case LSA_TYPE_ROUTER0x2001: |
530 | if (rtr_link->type != LINK_TYPE_POINTTOPOINT1) |
531 | fatalx("inconsistent SPF tree"); |
532 | nexthop = calc_nexthop_lladdr(dst, rtr_link, |
533 | ntohl(rtr_link->iface_id)(__uint32_t)(__builtin_constant_p(rtr_link->iface_id) ? (__uint32_t )(((__uint32_t)(rtr_link->iface_id) & 0xff) << 24 | ((__uint32_t)(rtr_link->iface_id) & 0xff00) << 8 | ((__uint32_t)(rtr_link->iface_id) & 0xff0000) >> 8 | ((__uint32_t)(rtr_link->iface_id) & 0xff000000) >> 24) : __swap32md(rtr_link->iface_id))); |
534 | break; |
535 | case LSA_TYPE_NETWORK0x2002: |
536 | if (rtr_link->type != LINK_TYPE_TRANSIT_NET2) |
537 | fatalx("inconsistent SPF tree"); |
538 | |
539 | /* Next hop address cannot be determined yet, |
540 | * we only know the outgoing interface. */ |
541 | nexthop = NULL((void *)0); |
542 | break; |
543 | default: |
544 | fatalx("calc_nexthop: invalid dst type"); |
545 | } |
546 | |
547 | vertex_nexthop_add(dst, parent, nexthop, |
548 | ntohl(rtr_link->iface_id)(__uint32_t)(__builtin_constant_p(rtr_link->iface_id) ? (__uint32_t )(((__uint32_t)(rtr_link->iface_id) & 0xff) << 24 | ((__uint32_t)(rtr_link->iface_id) & 0xff00) << 8 | ((__uint32_t)(rtr_link->iface_id) & 0xff0000) >> 8 | ((__uint32_t)(rtr_link->iface_id) & 0xff000000) >> 24) : __swap32md(rtr_link->iface_id))); |
549 | return; |
550 | } |
551 | |
552 | /* case 2 */ |
553 | if (parent->type == LSA_TYPE_NETWORK0x2002 && dst->type == LSA_TYPE_ROUTER0x2001) { |
554 | TAILQ_FOREACH(vn, &parent->nexthop, entry)for((vn) = ((&parent->nexthop)->tqh_first); (vn) != ((void *)0); (vn) = ((vn)->entry.tqe_next)) { |
555 | if (vn->prev == spf_root) |
556 | calc_nexthop_transit_nbr(dst, parent, |
557 | vn->ifindex); |
558 | else |
559 | /* dst is more than one transit net away */ |
560 | vertex_nexthop_add(dst, parent, &vn->nexthop, |
561 | vn->ifindex); |
562 | } |
563 | return; |
564 | } |
565 | |
566 | /* case 3 */ |
567 | TAILQ_FOREACH(vn, &parent->nexthop, entry)for((vn) = ((&parent->nexthop)->tqh_first); (vn) != ((void *)0); (vn) = ((vn)->entry.tqe_next)) |
568 | vertex_nexthop_add(dst, parent, &vn->nexthop, vn->ifindex); |
569 | } |
570 | |
571 | /* candidate list */ |
572 | void |
573 | cand_list_init(void) |
574 | { |
575 | TAILQ_INIT(&cand_list)do { (&cand_list)->tqh_first = ((void *)0); (&cand_list )->tqh_last = &(&cand_list)->tqh_first; } while (0); |
576 | } |
577 | |
578 | void |
579 | cand_list_add(struct vertex *v) |
580 | { |
581 | struct vertex *c = NULL((void *)0); |
582 | |
583 | TAILQ_FOREACH(c, &cand_list, cand)for((c) = ((&cand_list)->tqh_first); (c) != ((void *)0 ); (c) = ((c)->cand.tqe_next)) { |
584 | if (c->cost > v->cost) { |
585 | TAILQ_INSERT_BEFORE(c, v, cand)do { (v)->cand.tqe_prev = (c)->cand.tqe_prev; (v)->cand .tqe_next = (c); *(c)->cand.tqe_prev = (v); (c)->cand.tqe_prev = &(v)->cand.tqe_next; } while (0); |
586 | return; |
587 | } else if (c->cost == v->cost && c->type == LSA_TYPE_ROUTER0x2001 && |
588 | v->type == LSA_TYPE_NETWORK0x2002) { |
589 | TAILQ_INSERT_BEFORE(c, v, cand)do { (v)->cand.tqe_prev = (c)->cand.tqe_prev; (v)->cand .tqe_next = (c); *(c)->cand.tqe_prev = (v); (c)->cand.tqe_prev = &(v)->cand.tqe_next; } while (0); |
590 | return; |
591 | } |
592 | } |
593 | TAILQ_INSERT_TAIL(&cand_list, v, cand)do { (v)->cand.tqe_next = ((void *)0); (v)->cand.tqe_prev = (&cand_list)->tqh_last; *(&cand_list)->tqh_last = (v); (&cand_list)->tqh_last = &(v)->cand.tqe_next ; } while (0); |
594 | } |
595 | |
596 | struct vertex * |
597 | cand_list_pop(void) |
598 | { |
599 | struct vertex *c; |
600 | |
601 | if ((c = TAILQ_FIRST(&cand_list)((&cand_list)->tqh_first)) != NULL((void *)0)) { |
602 | TAILQ_REMOVE(&cand_list, c, cand)do { if (((c)->cand.tqe_next) != ((void *)0)) (c)->cand .tqe_next->cand.tqe_prev = (c)->cand.tqe_prev; else (& cand_list)->tqh_last = (c)->cand.tqe_prev; *(c)->cand .tqe_prev = (c)->cand.tqe_next; ; ; } while (0); |
603 | } |
604 | |
605 | return (c); |
606 | } |
607 | |
608 | int |
609 | cand_list_present(struct vertex *v) |
610 | { |
611 | struct vertex *c; |
612 | |
613 | TAILQ_FOREACH(c, &cand_list, cand)for((c) = ((&cand_list)->tqh_first); (c) != ((void *)0 ); (c) = ((c)->cand.tqe_next)) { |
614 | if (c == v) |
615 | return (1); |
616 | } |
617 | |
618 | return (0); |
619 | } |
620 | |
621 | void |
622 | cand_list_clr(void) |
623 | { |
624 | struct vertex *c; |
625 | |
626 | while ((c = TAILQ_FIRST(&cand_list)((&cand_list)->tqh_first)) != NULL((void *)0)) { |
627 | TAILQ_REMOVE(&cand_list, c, cand)do { if (((c)->cand.tqe_next) != ((void *)0)) (c)->cand .tqe_next->cand.tqe_prev = (c)->cand.tqe_prev; else (& cand_list)->tqh_last = (c)->cand.tqe_prev; *(c)->cand .tqe_prev = (c)->cand.tqe_next; ; ; } while (0); |
628 | } |
629 | } |
630 | |
631 | /* timers */ |
632 | void |
633 | spf_timer(int fd, short event, void *arg) |
634 | { |
635 | struct vertex *v; |
636 | struct ospfd_conf *conf = arg; |
637 | struct area *area; |
638 | struct rt_node *r; |
639 | |
640 | switch (conf->spf_state) { |
641 | case SPF_IDLE: |
642 | fatalx("spf_timer: invalid state IDLE"); |
643 | case SPF_HOLDQUEUE: |
644 | conf->spf_state = SPF_DELAY; |
645 | /* FALLTHROUGH */ |
646 | case SPF_DELAY: |
647 | LIST_FOREACH(area, &conf->area_list, entry)for((area) = ((&conf->area_list)->lh_first); (area) != ((void *)0); (area) = ((area)->entry.le_next)) { |
648 | if (area->dirty) { |
649 | /* invalidate RIB entries of this area */ |
650 | rt_invalidate(area); |
651 | |
652 | /* calculate SPF tree */ |
653 | spf_calc(area); |
654 | |
655 | /* calculate route table */ |
656 | RB_FOREACH(v, lsa_tree, &area->lsa_tree)for ((v) = lsa_tree_RB_MINMAX(&area->lsa_tree, -1); (v ) != ((void *)0); (v) = lsa_tree_RB_NEXT(v)) { |
657 | rt_calc(v, area, conf); |
658 | } |
659 | |
660 | area->dirty = 0; |
661 | } |
662 | } |
663 | |
664 | /* calculate as-external routes, first invalidate them */ |
665 | rt_invalidate(NULL((void *)0)); |
666 | RB_FOREACH(v, lsa_tree, &asext_tree)for ((v) = lsa_tree_RB_MINMAX(&asext_tree, -1); (v) != (( void *)0); (v) = lsa_tree_RB_NEXT(v)) { |
667 | asext_calc(v); |
668 | } |
669 | |
670 | RB_FOREACH(r, rt_tree, &rt)for ((r) = rt_tree_RB_MINMAX(&rt, -1); (r) != ((void *)0) ; (r) = rt_tree_RB_NEXT(r)) { |
671 | LIST_FOREACH(area, &conf->area_list, entry)for((area) = ((&conf->area_list)->lh_first); (area) != ((void *)0); (area) = ((area)->entry.le_next)) |
672 | rde_summary_update(r, area); |
673 | |
674 | if (r->d_type != DT_NET) |
675 | continue; |
676 | |
677 | if (r->invalid) |
678 | rde_send_delete_kroute(r); |
679 | else |
680 | rde_send_change_kroute(r); |
681 | } |
682 | |
683 | LIST_FOREACH(area, &conf->area_list, entry)for((area) = ((&conf->area_list)->lh_first); (area) != ((void *)0); (area) = ((area)->entry.le_next)) |
684 | lsa_remove_invalid_sums(area); |
685 | |
686 | start_spf_holdtimer(conf); |
687 | break; |
688 | case SPF_HOLD: |
689 | conf->spf_state = SPF_IDLE; |
690 | break; |
691 | default: |
692 | fatalx("spf_timer: unknown state"); |
693 | } |
694 | } |
695 | |
696 | void |
697 | start_spf_timer(void) |
698 | { |
699 | struct timeval tv; |
700 | |
701 | switch (rdeconf->spf_state) { |
702 | case SPF_IDLE: |
703 | timerclear(&tv)(&tv)->tv_sec = (&tv)->tv_usec = 0; |
704 | tv.tv_sec = rdeconf->spf_delay; |
705 | rdeconf->spf_state = SPF_DELAY; |
706 | if (evtimer_add(&rdeconf->ev, &tv)event_add(&rdeconf->ev, &tv) == -1) |
707 | fatal("start_spf_timer"); |
708 | break; |
709 | case SPF_DELAY: |
710 | /* ignore */ |
711 | break; |
712 | case SPF_HOLD: |
713 | rdeconf->spf_state = SPF_HOLDQUEUE; |
714 | break; |
715 | case SPF_HOLDQUEUE: |
716 | /* ignore */ |
717 | break; |
718 | default: |
719 | fatalx("start_spf_timer: invalid spf_state"); |
720 | } |
721 | } |
722 | |
723 | void |
724 | stop_spf_timer(struct ospfd_conf *conf) |
725 | { |
726 | if (evtimer_del(&conf->ev)event_del(&conf->ev) == -1) |
727 | fatal("stop_spf_timer"); |
728 | } |
729 | |
730 | void |
731 | start_spf_holdtimer(struct ospfd_conf *conf) |
732 | { |
733 | struct timeval tv; |
734 | |
735 | switch (conf->spf_state) { |
736 | case SPF_DELAY: |
737 | timerclear(&tv)(&tv)->tv_sec = (&tv)->tv_usec = 0; |
738 | tv.tv_sec = conf->spf_hold_time; |
739 | conf->spf_state = SPF_HOLD; |
740 | if (evtimer_add(&conf->ev, &tv)event_add(&conf->ev, &tv) == -1) |
741 | fatal("start_spf_holdtimer"); |
742 | break; |
743 | case SPF_IDLE: |
744 | case SPF_HOLD: |
745 | case SPF_HOLDQUEUE: |
746 | fatalx("start_spf_holdtimer: invalid state"); |
747 | default: |
748 | fatalx("start_spf_holdtimer: unknown state"); |
749 | } |
750 | } |
751 | |
752 | /* route table */ |
753 | void |
754 | rt_init(void) |
755 | { |
756 | RB_INIT(&rt)do { (&rt)->rbh_root = ((void *)0); } while (0); |
757 | } |
758 | |
759 | int |
760 | rt_compare(struct rt_node *a, struct rt_node *b) |
761 | { |
762 | int i; |
763 | |
764 | /* XXX maybe a & b need to be switched */ |
765 | i = memcmp(&a->prefix, &b->prefix, sizeof(a->prefix)); |
766 | if (i) |
767 | return (i); |
768 | if (a->prefixlen < b->prefixlen) |
769 | return (-1); |
770 | if (a->prefixlen > b->prefixlen) |
771 | return (1); |
772 | if (a->d_type > b->d_type) |
773 | return (-1); |
774 | if (a->d_type < b->d_type) |
775 | return (1); |
776 | return (0); |
777 | } |
778 | |
779 | struct rt_node * |
780 | rt_find(struct in6_addr *prefix, u_int8_t prefixlen, enum dst_type d_type) |
781 | { |
782 | struct rt_node s; |
783 | |
784 | s.prefix = *prefix; |
785 | s.prefixlen = prefixlen; |
786 | s.d_type = d_type; |
787 | |
788 | return (RB_FIND(rt_tree, &rt, &s)rt_tree_RB_FIND(&rt, &s)); |
789 | } |
790 | |
791 | int |
792 | rt_insert(struct rt_node *r) |
793 | { |
794 | if (RB_INSERT(rt_tree, &rt, r)rt_tree_RB_INSERT(&rt, r) != NULL((void *)0)) { |
795 | log_warnx("rt_insert failed for %s/%u", |
796 | log_in6addr(&r->prefix), r->prefixlen); |
797 | free(r); |
798 | return (-1); |
799 | } |
800 | |
801 | return (0); |
802 | } |
803 | |
804 | int |
805 | rt_remove(struct rt_node *r) |
806 | { |
807 | if (RB_REMOVE(rt_tree, &rt, r)rt_tree_RB_REMOVE(&rt, r) == NULL((void *)0)) { |
808 | log_warnx("rt_remove failed for %s/%u", |
809 | log_in6addr(&r->prefix), r->prefixlen); |
810 | return (-1); |
811 | } |
812 | |
813 | rt_nexthop_clear(r); |
814 | free(r); |
815 | return (0); |
816 | } |
817 | |
818 | void |
819 | rt_invalidate(struct area *area) |
820 | { |
821 | struct rt_node *r, *nr; |
822 | struct rt_nexthop *rn, *nrn; |
823 | |
824 | for (r = RB_MIN(rt_tree, &rt)rt_tree_RB_MINMAX(&rt, -1); r != NULL((void *)0); r = nr) { |
825 | nr = RB_NEXT(rt_tree, &rt, r)rt_tree_RB_NEXT(r); |
826 | if (area == NULL((void *)0)) { |
827 | /* look only at as_ext routes */ |
828 | if (r->p_type != PT_TYPE1_EXT && |
829 | r->p_type != PT_TYPE2_EXT) |
830 | continue; |
831 | } else { |
832 | /* ignore all as_ext routes */ |
833 | if (r->p_type == PT_TYPE1_EXT || |
834 | r->p_type == PT_TYPE2_EXT) |
835 | continue; |
836 | |
837 | /* look only at routes matching the area */ |
838 | if (r->area.s_addr != area->id.s_addr) |
839 | continue; |
840 | } |
841 | r->invalid = 1; |
842 | for (rn = TAILQ_FIRST(&r->nexthop)((&r->nexthop)->tqh_first); rn != NULL((void *)0); rn = nrn) { |
843 | nrn = TAILQ_NEXT(rn, entry)((rn)->entry.tqe_next); |
844 | if (rn->invalid) { |
845 | TAILQ_REMOVE(&r->nexthop, rn, entry)do { if (((rn)->entry.tqe_next) != ((void *)0)) (rn)->entry .tqe_next->entry.tqe_prev = (rn)->entry.tqe_prev; else ( &r->nexthop)->tqh_last = (rn)->entry.tqe_prev; * (rn)->entry.tqe_prev = (rn)->entry.tqe_next; ; ; } while (0); |
846 | free(rn); |
847 | } else |
848 | rn->invalid = 1; |
849 | } |
850 | if (TAILQ_EMPTY(&r->nexthop)(((&r->nexthop)->tqh_first) == ((void *)0))) |
851 | rt_remove(r); |
852 | } |
853 | } |
854 | |
855 | void |
856 | rt_nexthop_clear(struct rt_node *r) |
857 | { |
858 | struct rt_nexthop *rn; |
859 | |
860 | while ((rn = TAILQ_FIRST(&r->nexthop)((&r->nexthop)->tqh_first)) != NULL((void *)0)) { |
861 | TAILQ_REMOVE(&r->nexthop, rn, entry)do { if (((rn)->entry.tqe_next) != ((void *)0)) (rn)->entry .tqe_next->entry.tqe_prev = (rn)->entry.tqe_prev; else ( &r->nexthop)->tqh_last = (rn)->entry.tqe_prev; * (rn)->entry.tqe_prev = (rn)->entry.tqe_next; ; ; } while (0); |
862 | free(rn); |
863 | } |
864 | } |
865 | |
866 | void |
867 | rt_nexthop_add(struct rt_node *r, struct v_nexthead *vnh, u_int16_t type, |
868 | struct in_addr adv_rtr) |
869 | { |
870 | struct v_nexthop *vn; |
871 | struct rt_nexthop *rn; |
872 | struct timespec now; |
873 | |
874 | TAILQ_FOREACH(vn, vnh, entry)for((vn) = ((vnh)->tqh_first); (vn) != ((void *)0); (vn) = ((vn)->entry.tqe_next)) { |
875 | TAILQ_FOREACH(rn, &r->nexthop, entry)for((rn) = ((&r->nexthop)->tqh_first); (rn) != ((void *)0); (rn) = ((rn)->entry.tqe_next)) { |
876 | if (!IN6_ARE_ADDR_EQUAL(&rn->nexthop, &vn->nexthop)(memcmp(&(&rn->nexthop)->__u6_addr.__u6_addr8[0 ], &(&vn->nexthop)->__u6_addr.__u6_addr8[0], sizeof (struct in6_addr)) == 0)) |
877 | continue; |
878 | |
879 | rn->adv_rtr.s_addr = adv_rtr.s_addr; |
880 | rn->connected = (type == LSA_TYPE_NETWORK0x2002 && |
881 | vn->prev == spf_root) || |
882 | (IN6_IS_ADDR_UNSPECIFIED(&vn->nexthop)((*(const u_int32_t *)(const void *)(&(&vn->nexthop )->__u6_addr.__u6_addr8[0]) == 0) && (*(const u_int32_t *)(const void *)(&(&vn->nexthop)->__u6_addr.__u6_addr8 [4]) == 0) && (*(const u_int32_t *)(const void *)(& (&vn->nexthop)->__u6_addr.__u6_addr8[8]) == 0) && (*(const u_int32_t *)(const void *)(&(&vn->nexthop )->__u6_addr.__u6_addr8[12]) == 0))); |
883 | rn->invalid = 0; |
884 | |
885 | r->invalid = 0; |
886 | break; |
887 | } |
888 | if (rn) |
889 | continue; |
890 | |
891 | if ((rn = calloc(1, sizeof(struct rt_nexthop))) == NULL((void *)0)) |
892 | fatal("rt_nexthop_add"); |
893 | |
894 | clock_gettime(CLOCK_MONOTONIC3, &now); |
895 | rn->nexthop = vn->nexthop; |
896 | rn->ifindex = vn->ifindex; |
897 | rn->adv_rtr.s_addr = adv_rtr.s_addr; |
898 | rn->uptime = now.tv_sec; |
899 | rn->connected = (type == LSA_TYPE_NETWORK0x2002 && |
900 | vn->prev == spf_root) || |
901 | (IN6_IS_ADDR_UNSPECIFIED(&vn->nexthop)((*(const u_int32_t *)(const void *)(&(&vn->nexthop )->__u6_addr.__u6_addr8[0]) == 0) && (*(const u_int32_t *)(const void *)(&(&vn->nexthop)->__u6_addr.__u6_addr8 [4]) == 0) && (*(const u_int32_t *)(const void *)(& (&vn->nexthop)->__u6_addr.__u6_addr8[8]) == 0) && (*(const u_int32_t *)(const void *)(&(&vn->nexthop )->__u6_addr.__u6_addr8[12]) == 0))); |
902 | rn->invalid = 0; |
903 | |
904 | r->invalid = 0; |
905 | TAILQ_INSERT_TAIL(&r->nexthop, rn, entry)do { (rn)->entry.tqe_next = ((void *)0); (rn)->entry.tqe_prev = (&r->nexthop)->tqh_last; *(&r->nexthop)-> tqh_last = (rn); (&r->nexthop)->tqh_last = &(rn )->entry.tqe_next; } while (0); |
906 | } |
907 | } |
908 | |
909 | void |
910 | rt_clear(void) |
911 | { |
912 | struct rt_node *r; |
913 | |
914 | while ((r = RB_MIN(rt_tree, &rt)rt_tree_RB_MINMAX(&rt, -1)) != NULL((void *)0)) |
915 | rt_remove(r); |
916 | } |
917 | |
918 | void |
919 | rt_dump(struct in_addr area, pid_t pid, u_int8_t r_type) |
920 | { |
921 | static struct ctl_rt rtctl; |
922 | struct timespec now; |
923 | struct rt_node *r; |
924 | struct rt_nexthop *rn; |
925 | |
926 | clock_gettime(CLOCK_MONOTONIC3, &now); |
927 | |
928 | RB_FOREACH(r, rt_tree, &rt)for ((r) = rt_tree_RB_MINMAX(&rt, -1); (r) != ((void *)0) ; (r) = rt_tree_RB_NEXT(r)) { |
929 | if (r->invalid) |
930 | continue; |
931 | |
932 | if (r->area.s_addr != area.s_addr) |
933 | continue; |
934 | |
935 | switch (r_type) { |
936 | case RIB_RTR: |
937 | if (r->d_type != DT_RTR) |
938 | continue; |
939 | break; |
940 | case RIB_NET: |
941 | if (r->d_type != DT_NET) |
942 | continue; |
943 | if (r->p_type == PT_TYPE1_EXT || |
944 | r->p_type == PT_TYPE2_EXT) |
945 | continue; |
946 | break; |
947 | case RIB_EXT: |
948 | if (r->p_type != PT_TYPE1_EXT && |
949 | r->p_type != PT_TYPE2_EXT) |
950 | continue; |
951 | break; |
952 | default: |
953 | fatalx("rt_dump: invalid RIB type"); |
954 | } |
955 | |
956 | memset(&rtctl, 0, sizeof(rtctl)); |
957 | rtctl.prefix = r->prefix; |
958 | rtctl.area.s_addr = r->area.s_addr; |
959 | rtctl.cost = r->cost; |
960 | rtctl.cost2 = r->cost2; |
961 | rtctl.p_type = r->p_type; |
962 | rtctl.d_type = r->d_type; |
963 | rtctl.flags = r->flags; |
964 | rtctl.prefixlen = r->prefixlen; |
965 | |
966 | TAILQ_FOREACH(rn, &r->nexthop, entry)for((rn) = ((&r->nexthop)->tqh_first); (rn) != ((void *)0); (rn) = ((rn)->entry.tqe_next)) { |
967 | if (rn->invalid) |
968 | continue; |
969 | |
970 | rtctl.connected = rn->connected; |
971 | rtctl.nexthop = rn->nexthop; |
972 | rtctl.ifindex = rn->ifindex; |
973 | rtctl.adv_rtr.s_addr = rn->adv_rtr.s_addr; |
974 | rtctl.uptime = now.tv_sec - rn->uptime; |
975 | |
976 | rde_imsg_compose_ospfe(IMSG_CTL_SHOW_RIB, 0, pid, |
977 | &rtctl, sizeof(rtctl)); |
978 | } |
979 | } |
980 | } |
981 | |
982 | void |
983 | rt_update(struct in6_addr *prefix, u_int8_t prefixlen, struct v_nexthead *vnh, |
984 | u_int16_t v_type, u_int32_t cost, u_int32_t cost2, struct in_addr area, |
985 | struct in_addr adv_rtr, enum path_type p_type, enum dst_type d_type, |
986 | u_int8_t flags, u_int32_t tag) |
987 | { |
988 | struct rt_node *rte; |
989 | struct rt_nexthop *rn; |
990 | int better = 0, equal = 0; |
991 | |
992 | if (vnh == NULL((void *)0) || TAILQ_EMPTY(vnh)(((vnh)->tqh_first) == ((void *)0))) /* XXX remove */ |
993 | fatalx("rt_update: invalid nexthop"); |
994 | |
995 | if ((rte = rt_find(prefix, prefixlen, d_type)) == NULL((void *)0)) { |
996 | if ((rte = calloc(1, sizeof(struct rt_node))) == NULL((void *)0)) |
997 | fatal("rt_update"); |
998 | |
999 | TAILQ_INIT(&rte->nexthop)do { (&rte->nexthop)->tqh_first = ((void *)0); (& rte->nexthop)->tqh_last = &(&rte->nexthop)-> tqh_first; } while (0); |
1000 | rte->prefix = *prefix; |
1001 | rte->prefixlen = prefixlen; |
1002 | rte->cost = cost; |
1003 | rte->cost2 = cost2; |
1004 | rte->area = area; |
1005 | rte->p_type = p_type; |
1006 | rte->d_type = d_type; |
1007 | rte->flags = flags; |
1008 | rte->ext_tag = tag; |
1009 | |
1010 | rt_nexthop_add(rte, vnh, v_type, adv_rtr); |
1011 | |
1012 | rt_insert(rte); |
1013 | } else { |
1014 | /* order: |
1015 | * 1. intra-area |
1016 | * 2. inter-area |
1017 | * 3. type 1 as ext |
1018 | * 4. type 2 as ext |
1019 | */ |
1020 | if (rte->invalid) /* everything is better than invalid */ |
1021 | better = 1; |
1022 | else if (p_type < rte->p_type) |
1023 | better = 1; |
1024 | else if (p_type == rte->p_type) |
1025 | switch (p_type) { |
1026 | case PT_INTRA_AREA: |
1027 | case PT_INTER_AREA: |
1028 | if (cost < rte->cost) |
1029 | better = 1; |
1030 | else if (cost == rte->cost && |
1031 | rte->area.s_addr == area.s_addr) |
1032 | equal = 1; |
1033 | break; |
1034 | case PT_TYPE1_EXT: |
1035 | if (cost < rte->cost) |
1036 | better = 1; |
1037 | else if (cost == rte->cost) |
1038 | equal = 1; |
1039 | break; |
1040 | case PT_TYPE2_EXT: |
1041 | if (cost2 < rte->cost2) |
1042 | better = 1; |
1043 | else if (cost2 == rte->cost2 && |
1044 | cost < rte->cost) |
1045 | better = 1; |
1046 | else if (cost2 == rte->cost2 && |
1047 | cost == rte->cost) |
1048 | equal = 1; |
1049 | break; |
1050 | } |
1051 | |
1052 | if (better) { |
1053 | TAILQ_FOREACH(rn, &rte->nexthop, entry)for((rn) = ((&rte->nexthop)->tqh_first); (rn) != (( void *)0); (rn) = ((rn)->entry.tqe_next)) |
1054 | rn->invalid = 1; |
1055 | |
1056 | rte->area = area; |
1057 | rte->cost = cost; |
1058 | rte->cost2 = cost2; |
1059 | rte->p_type = p_type; |
1060 | rte->flags = flags; |
1061 | rte->ext_tag = tag; |
1062 | } |
1063 | |
1064 | if (equal || better) |
1065 | rt_nexthop_add(rte, vnh, v_type, adv_rtr); |
1066 | } |
1067 | } |
1068 | |
1069 | struct rt_node * |
1070 | rt_lookup(enum dst_type type, struct in6_addr *addr) |
1071 | { |
1072 | struct rt_node *rn; |
1073 | struct in6_addr ina; |
1074 | u_int8_t i = 128; |
1075 | |
1076 | if (type == DT_RTR) { |
1077 | rn = rt_find(addr, 128, type); |
1078 | if (rn && rn->invalid == 0) |
1079 | return (rn); |
1080 | return (NULL((void *)0)); |
1081 | } |
1082 | |
1083 | /* type == DT_NET */ |
1084 | do { |
1085 | inet6applymask(&ina, addr, i); |
1086 | if ((rn = rt_find(&ina, i, type)) && rn->invalid == 0) |
1087 | return (rn); |
1088 | } while (i-- != 0); |
1089 | |
1090 | return (NULL((void *)0)); |
1091 | } |
1092 | |
1093 | /* router LSA links */ |
1094 | struct lsa_rtr_link * |
1095 | get_rtr_link(struct vertex *v, unsigned int idx) |
1096 | { |
1097 | struct lsa_rtr_link *rtr_link = NULL((void *)0); |
1098 | unsigned int frag = 1; |
1099 | unsigned int frag_nlinks; |
1100 | unsigned int nlinks = 0; |
1101 | unsigned int i; |
1102 | |
1103 | if (v->type != LSA_TYPE_ROUTER0x2001) |
1104 | fatalx("get_rtr_link: invalid LSA type"); |
1105 | |
1106 | /* Treat multiple Router-LSAs originated by the same router |
1107 | * as an aggregate. */ |
1108 | do { |
1109 | /* number of links validated earlier by lsa_check() */ |
1110 | rtr_link = (struct lsa_rtr_link *)((char *)v->lsa + |
1111 | sizeof(v->lsa->hdr) + sizeof(struct lsa_rtr)); |
1112 | frag_nlinks = ((ntohs(v->lsa->hdr.len)(__uint16_t)(__builtin_constant_p(v->lsa->hdr.len) ? (__uint16_t )(((__uint16_t)(v->lsa->hdr.len) & 0xffU) << 8 | ((__uint16_t)(v->lsa->hdr.len) & 0xff00U) >> 8) : __swap16md(v->lsa->hdr.len)) - |
1113 | sizeof(struct lsa_hdr) - sizeof(struct lsa_rtr)) / |
1114 | sizeof(struct lsa_rtr_link)); |
1115 | if (nlinks + frag_nlinks > idx) { |
1116 | for (i = 0; i < frag_nlinks; i++) { |
1117 | if (i + nlinks == idx) |
1118 | return (rtr_link); |
1119 | rtr_link++; |
1120 | } |
1121 | } |
1122 | nlinks += frag_nlinks; |
1123 | v = lsa_find_rtr_frag(v->area, htonl(v->adv_rtr)(__uint32_t)(__builtin_constant_p(v->adv_rtr) ? (__uint32_t )(((__uint32_t)(v->adv_rtr) & 0xff) << 24 | ((__uint32_t )(v->adv_rtr) & 0xff00) << 8 | ((__uint32_t)(v-> adv_rtr) & 0xff0000) >> 8 | ((__uint32_t)(v->adv_rtr ) & 0xff000000) >> 24) : __swap32md(v->adv_rtr)), frag++); |
1124 | } while (v); |
1125 | |
1126 | fatalx("get_rtr_link: index not found"); |
1127 | } |
1128 | |
1129 | /* network LSA links */ |
1130 | struct lsa_net_link * |
1131 | get_net_link(struct vertex *v, unsigned int idx) |
1132 | { |
1133 | struct lsa_net_link *net_link = NULL((void *)0); |
1134 | char *buf = (char *)v->lsa; |
1135 | unsigned int i, nlinks; |
1136 | |
1137 | if (v->type != LSA_TYPE_NETWORK0x2002) |
1138 | fatalx("get_net_link: invalid LSA type"); |
1139 | |
1140 | net_link = (struct lsa_net_link *)(buf + sizeof(v->lsa->hdr) + |
1141 | sizeof(struct lsa_net)); |
1142 | |
1143 | /* number of links validated earlier by lsa_check() */ |
1144 | nlinks = lsa_num_links(v); |
1145 | for (i = 0; i < nlinks; i++) { |
1146 | if (i == idx) |
1147 | return (net_link); |
1148 | net_link++; |
1149 | } |
1150 | |
1151 | fatalx("get_net_link: index not found"); |
1152 | } |
1153 | |
1154 | /* misc */ |
1155 | int |
1156 | linked(struct vertex *w, struct vertex *v) |
1157 | { |
1158 | struct lsa_rtr_link *rtr_link = NULL((void *)0); |
1159 | struct lsa_net_link *net_link = NULL((void *)0); |
1160 | unsigned int i; |
1161 | |
1162 | switch (w->type) { |
1163 | case LSA_TYPE_ROUTER0x2001: |
1164 | for (i = 0; i < lsa_num_links(w); i++) { |
1165 | rtr_link = get_rtr_link(w, i); |
1166 | switch (v->type) { |
1167 | case LSA_TYPE_ROUTER0x2001: |
1168 | if (rtr_link->type == LINK_TYPE_POINTTOPOINT1 && |
1169 | rtr_link->nbr_rtr_id == htonl(v->adv_rtr)(__uint32_t)(__builtin_constant_p(v->adv_rtr) ? (__uint32_t )(((__uint32_t)(v->adv_rtr) & 0xff) << 24 | ((__uint32_t )(v->adv_rtr) & 0xff00) << 8 | ((__uint32_t)(v-> adv_rtr) & 0xff0000) >> 8 | ((__uint32_t)(v->adv_rtr ) & 0xff000000) >> 24) : __swap32md(v->adv_rtr))) |
1170 | return (1); |
1171 | break; |
1172 | case LSA_TYPE_NETWORK0x2002: |
1173 | if (rtr_link->type == LINK_TYPE_TRANSIT_NET2 && |
1174 | rtr_link->nbr_rtr_id == htonl(v->adv_rtr)(__uint32_t)(__builtin_constant_p(v->adv_rtr) ? (__uint32_t )(((__uint32_t)(v->adv_rtr) & 0xff) << 24 | ((__uint32_t )(v->adv_rtr) & 0xff00) << 8 | ((__uint32_t)(v-> adv_rtr) & 0xff0000) >> 8 | ((__uint32_t)(v->adv_rtr ) & 0xff000000) >> 24) : __swap32md(v->adv_rtr)) && |
1175 | rtr_link->nbr_iface_id == htonl(v->ls_id)(__uint32_t)(__builtin_constant_p(v->ls_id) ? (__uint32_t) (((__uint32_t)(v->ls_id) & 0xff) << 24 | ((__uint32_t )(v->ls_id) & 0xff00) << 8 | ((__uint32_t)(v-> ls_id) & 0xff0000) >> 8 | ((__uint32_t)(v->ls_id ) & 0xff000000) >> 24) : __swap32md(v->ls_id))) |
1176 | return (1); |
1177 | break; |
1178 | default: |
1179 | fatalx("linked: invalid type"); |
1180 | } |
1181 | } |
1182 | return (0); |
1183 | case LSA_TYPE_NETWORK0x2002: |
1184 | for (i = 0; i < lsa_num_links(w); i++) { |
1185 | net_link = get_net_link(w, i); |
1186 | switch (v->type) { |
1187 | case LSA_TYPE_ROUTER0x2001: |
1188 | if (net_link->att_rtr == htonl(v->adv_rtr)(__uint32_t)(__builtin_constant_p(v->adv_rtr) ? (__uint32_t )(((__uint32_t)(v->adv_rtr) & 0xff) << 24 | ((__uint32_t )(v->adv_rtr) & 0xff00) << 8 | ((__uint32_t)(v-> adv_rtr) & 0xff0000) >> 8 | ((__uint32_t)(v->adv_rtr ) & 0xff000000) >> 24) : __swap32md(v->adv_rtr))) |
1189 | return (1); |
1190 | break; |
1191 | default: |
1192 | fatalx("linked: invalid type"); |
1193 | } |
1194 | } |
1195 | return (0); |
1196 | default: |
1197 | fatalx("linked: invalid LSA type"); |
1198 | } |
1199 | |
1200 | return (0); |
1201 | } |