]>
Commit | Line | Data |
---|---|---|
fb018d25 DS |
1 | /* A generic nexthop structure |
2 | * Copyright (C) 2013 Cumulus Networks, Inc. | |
3 | * | |
a399694f | 4 | * This file is part of Quagga. |
fb018d25 | 5 | * |
a399694f | 6 | * Quagga is free software; you can redistribute it and/or modify it |
fb018d25 DS |
7 | * under the terms of the GNU General Public License as published by the |
8 | * Free Software Foundation; either version 2, or (at your option) any | |
9 | * later version. | |
10 | * | |
a399694f | 11 | * Quagga is distributed in the hope that it will be useful, but |
fb018d25 DS |
12 | * WITHOUT ANY WARRANTY; without even the implied warranty of |
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | * General Public License for more details. | |
15 | * | |
896014f4 DL |
16 | * You should have received a copy of the GNU General Public License along |
17 | * with this program; see the file COPYING; if not, write to the Free Software | |
18 | * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA | |
fb018d25 DS |
19 | */ |
20 | #include <zebra.h> | |
21 | ||
22 | #include "prefix.h" | |
23 | #include "table.h" | |
24 | #include "memory.h" | |
fb018d25 DS |
25 | #include "command.h" |
26 | #include "if.h" | |
27 | #include "log.h" | |
28 | #include "sockunion.h" | |
29 | #include "linklist.h" | |
30 | #include "thread.h" | |
31 | #include "prefix.h" | |
32 | #include "nexthop.h" | |
40c7bdb0 | 33 | #include "mpls.h" |
d36d0d57 | 34 | #include "jhash.h" |
fb018d25 | 35 | |
d62a17ae | 36 | DEFINE_MTYPE_STATIC(LIB, NEXTHOP, "Nexthop") |
37 | DEFINE_MTYPE_STATIC(LIB, NH_LABEL, "Nexthop label") | |
4a1ab8e4 | 38 | |
fb018d25 | 39 | /* check if nexthops are same, non-recursive */ |
fd36be7e DL |
40 | int nexthop_same_no_recurse(const struct nexthop *next1, |
41 | const struct nexthop *next2) | |
fb018d25 | 42 | { |
d62a17ae | 43 | if (next1->type != next2->type) |
44 | return 0; | |
45 | ||
46 | switch (next1->type) { | |
47 | case NEXTHOP_TYPE_IPV4: | |
48 | case NEXTHOP_TYPE_IPV4_IFINDEX: | |
49 | if (!IPV4_ADDR_SAME(&next1->gate.ipv4, &next2->gate.ipv4)) | |
50 | return 0; | |
51 | if (next1->ifindex && (next1->ifindex != next2->ifindex)) | |
52 | return 0; | |
53 | break; | |
54 | case NEXTHOP_TYPE_IFINDEX: | |
55 | if (next1->ifindex != next2->ifindex) | |
56 | return 0; | |
57 | break; | |
58 | case NEXTHOP_TYPE_IPV6: | |
59 | if (!IPV6_ADDR_SAME(&next1->gate.ipv6, &next2->gate.ipv6)) | |
60 | return 0; | |
61 | break; | |
62 | case NEXTHOP_TYPE_IPV6_IFINDEX: | |
63 | if (!IPV6_ADDR_SAME(&next1->gate.ipv6, &next2->gate.ipv6)) | |
64 | return 0; | |
65 | if (next1->ifindex != next2->ifindex) | |
66 | return 0; | |
25b9cb0c DL |
67 | break; |
68 | default: | |
69 | /* do nothing */ | |
70 | break; | |
71 | } | |
72 | return 1; | |
73 | } | |
74 | ||
996c9314 | 75 | int nexthop_same_firsthop(struct nexthop *next1, struct nexthop *next2) |
25b9cb0c DL |
76 | { |
77 | int type1 = NEXTHOP_FIRSTHOPTYPE(next1->type); | |
78 | int type2 = NEXTHOP_FIRSTHOPTYPE(next2->type); | |
79 | ||
80 | if (type1 != type2) | |
81 | return 0; | |
996c9314 | 82 | switch (type1) { |
25b9cb0c | 83 | case NEXTHOP_TYPE_IPV4_IFINDEX: |
996c9314 | 84 | if (!IPV4_ADDR_SAME(&next1->gate.ipv4, &next2->gate.ipv4)) |
25b9cb0c DL |
85 | return 0; |
86 | if (next1->ifindex != next2->ifindex) | |
87 | return 0; | |
88 | break; | |
89 | case NEXTHOP_TYPE_IFINDEX: | |
90 | if (next1->ifindex != next2->ifindex) | |
91 | return 0; | |
92 | break; | |
93 | case NEXTHOP_TYPE_IPV6_IFINDEX: | |
996c9314 | 94 | if (!IPV6_ADDR_SAME(&next1->gate.ipv6, &next2->gate.ipv6)) |
25b9cb0c DL |
95 | return 0; |
96 | if (next1->ifindex != next2->ifindex) | |
97 | return 0; | |
d62a17ae | 98 | break; |
99 | default: | |
100 | /* do nothing */ | |
101 | break; | |
102 | } | |
103 | return 1; | |
fb018d25 DS |
104 | } |
105 | ||
106 | /* | |
107 | * nexthop_type_to_str | |
108 | */ | |
d62a17ae | 109 | const char *nexthop_type_to_str(enum nexthop_types_t nh_type) |
fb018d25 | 110 | { |
d62a17ae | 111 | static const char *desc[] = { |
112 | "none", "Directly connected", | |
113 | "IPv4 nexthop", "IPv4 nexthop with ifindex", | |
114 | "IPv6 nexthop", "IPv6 nexthop with ifindex", | |
115 | "Null0 nexthop", | |
116 | }; | |
117 | ||
118 | return desc[nh_type]; | |
fb018d25 | 119 | } |
a399694f | 120 | |
a64448ba DS |
121 | /* |
122 | * Check if the labels match for the 2 nexthops specified. | |
123 | */ | |
55f93d4b | 124 | int nexthop_labels_match(const struct nexthop *nh1, const struct nexthop *nh2) |
a64448ba | 125 | { |
55f93d4b | 126 | const struct mpls_label_stack *nhl1, *nhl2; |
a64448ba | 127 | |
d62a17ae | 128 | nhl1 = nh1->nh_label; |
129 | nhl2 = nh2->nh_label; | |
55f93d4b MS |
130 | |
131 | /* No labels is a match */ | |
132 | if (!nhl1 && !nhl2) | |
133 | return 1; | |
134 | ||
3f58e1b3 | 135 | if (!nhl1 || !nhl2) |
d62a17ae | 136 | return 0; |
a64448ba | 137 | |
d62a17ae | 138 | if (nhl1->num_labels != nhl2->num_labels) |
139 | return 0; | |
a64448ba | 140 | |
d62a17ae | 141 | if (memcmp(nhl1->label, nhl2->label, nhl1->num_labels)) |
142 | return 0; | |
a64448ba | 143 | |
d62a17ae | 144 | return 1; |
a64448ba DS |
145 | } |
146 | ||
d62a17ae | 147 | struct nexthop *nexthop_new(void) |
a399694f | 148 | { |
d62a17ae | 149 | return XCALLOC(MTYPE_NEXTHOP, sizeof(struct nexthop)); |
a399694f DS |
150 | } |
151 | ||
a399694f | 152 | /* Free nexthop. */ |
d62a17ae | 153 | void nexthop_free(struct nexthop *nexthop) |
a399694f | 154 | { |
d62a17ae | 155 | nexthop_del_labels(nexthop); |
156 | if (nexthop->resolved) | |
157 | nexthops_free(nexthop->resolved); | |
158 | XFREE(MTYPE_NEXTHOP, nexthop); | |
a399694f DS |
159 | } |
160 | ||
161 | /* Frees a list of nexthops */ | |
d62a17ae | 162 | void nexthops_free(struct nexthop *nexthop) |
a399694f | 163 | { |
d62a17ae | 164 | struct nexthop *nh, *next; |
a399694f | 165 | |
d62a17ae | 166 | for (nh = nexthop; nh; nh = next) { |
167 | next = nh->next; | |
168 | nexthop_free(nh); | |
169 | } | |
a399694f | 170 | } |
80c2442a | 171 | |
31919191 DS |
172 | bool nexthop_same(const struct nexthop *nh1, const struct nexthop *nh2) |
173 | { | |
174 | if (nh1 && !nh2) | |
175 | return false; | |
176 | ||
177 | if (!nh1 && nh2) | |
178 | return false; | |
179 | ||
180 | if (nh1 == nh2) | |
181 | return true; | |
182 | ||
183 | if (nh1->vrf_id != nh2->vrf_id) | |
184 | return false; | |
185 | ||
186 | if (nh1->type != nh2->type) | |
187 | return false; | |
188 | ||
189 | switch (nh1->type) { | |
190 | case NEXTHOP_TYPE_IFINDEX: | |
191 | if (nh1->ifindex != nh2->ifindex) | |
192 | return false; | |
193 | break; | |
194 | case NEXTHOP_TYPE_IPV4: | |
195 | if (nh1->gate.ipv4.s_addr != nh2->gate.ipv4.s_addr) | |
196 | return false; | |
197 | break; | |
198 | case NEXTHOP_TYPE_IPV4_IFINDEX: | |
199 | if (nh1->gate.ipv4.s_addr != nh2->gate.ipv4.s_addr) | |
200 | return false; | |
201 | if (nh1->ifindex != nh2->ifindex) | |
202 | return false; | |
203 | break; | |
204 | case NEXTHOP_TYPE_IPV6: | |
205 | if (memcmp(&nh1->gate.ipv6, &nh2->gate.ipv6, 16)) | |
206 | return false; | |
207 | break; | |
208 | case NEXTHOP_TYPE_IPV6_IFINDEX: | |
209 | if (memcmp(&nh1->gate.ipv6, &nh2->gate.ipv6, 16)) | |
210 | return false; | |
211 | if (nh1->ifindex != nh2->ifindex) | |
212 | return false; | |
213 | break; | |
214 | case NEXTHOP_TYPE_BLACKHOLE: | |
215 | if (nh1->bh_type != nh2->bh_type) | |
216 | return false; | |
217 | break; | |
218 | } | |
219 | ||
55f93d4b MS |
220 | /* Compare labels too (if present) */ |
221 | return (!!nexthop_labels_match(nh1, nh2)); | |
31919191 DS |
222 | } |
223 | ||
40c7bdb0 | 224 | /* Update nexthop with label information. */ |
d62a17ae | 225 | void nexthop_add_labels(struct nexthop *nexthop, enum lsp_types_t type, |
d7c0a89a | 226 | uint8_t num_labels, mpls_label_t *label) |
40c7bdb0 | 227 | { |
8ecdb26e | 228 | struct mpls_label_stack *nh_label; |
d62a17ae | 229 | int i; |
230 | ||
231 | nexthop->nh_label_type = type; | |
232 | nh_label = XCALLOC(MTYPE_NH_LABEL, | |
8ecdb26e | 233 | sizeof(struct mpls_label_stack) |
d62a17ae | 234 | + num_labels * sizeof(mpls_label_t)); |
235 | nh_label->num_labels = num_labels; | |
236 | for (i = 0; i < num_labels; i++) | |
237 | nh_label->label[i] = *(label + i); | |
238 | nexthop->nh_label = nh_label; | |
40c7bdb0 | 239 | } |
240 | ||
241 | /* Free label information of nexthop, if present. */ | |
d62a17ae | 242 | void nexthop_del_labels(struct nexthop *nexthop) |
40c7bdb0 | 243 | { |
d62a17ae | 244 | if (nexthop->nh_label) { |
245 | XFREE(MTYPE_NH_LABEL, nexthop->nh_label); | |
246 | nexthop->nh_label_type = ZEBRA_LSP_NONE; | |
247 | } | |
40c7bdb0 | 248 | } |
249 | ||
d36d0d57 | 250 | const char *nexthop2str(const struct nexthop *nexthop, char *str, int size) |
80c2442a | 251 | { |
d62a17ae | 252 | switch (nexthop->type) { |
253 | case NEXTHOP_TYPE_IFINDEX: | |
254 | snprintf(str, size, "if %u", nexthop->ifindex); | |
255 | break; | |
256 | case NEXTHOP_TYPE_IPV4: | |
d62a17ae | 257 | case NEXTHOP_TYPE_IPV4_IFINDEX: |
258 | snprintf(str, size, "%s if %u", inet_ntoa(nexthop->gate.ipv4), | |
259 | nexthop->ifindex); | |
260 | break; | |
261 | case NEXTHOP_TYPE_IPV6: | |
d62a17ae | 262 | case NEXTHOP_TYPE_IPV6_IFINDEX: |
263 | snprintf(str, size, "%s if %u", inet6_ntoa(nexthop->gate.ipv6), | |
264 | nexthop->ifindex); | |
265 | break; | |
266 | case NEXTHOP_TYPE_BLACKHOLE: | |
267 | snprintf(str, size, "blackhole"); | |
268 | break; | |
269 | default: | |
270 | snprintf(str, size, "unknown"); | |
271 | break; | |
272 | } | |
273 | ||
274 | return str; | |
80c2442a | 275 | } |
9fb47c05 CF |
276 | |
277 | /* | |
278 | * Iteration step for ALL_NEXTHOPS macro: | |
279 | * This is the tricky part. Check if `nexthop' has | |
280 | * NEXTHOP_FLAG_RECURSIVE set. If yes, this implies that `nexthop' has | |
281 | * at least one nexthop attached to `nexthop->resolved', which will be | |
282 | * the next one. | |
283 | * | |
284 | * If NEXTHOP_FLAG_RECURSIVE is not set, `nexthop' will progress in its | |
285 | * current chain. In case its current chain end is reached, it will move | |
286 | * upwards in the recursion levels and progress there. Whenever a step | |
287 | * forward in a chain is done, recursion will be checked again. | |
288 | * In a nustshell, it's equivalent to a pre-traversal order assuming that | |
289 | * left branch is 'resolved' and right branch is 'next': | |
290 | * https://en.wikipedia.org/wiki/Tree_traversal#/media/File:Sorted_binary_tree_preorder.svg | |
291 | */ | |
d62a17ae | 292 | struct nexthop *nexthop_next(struct nexthop *nexthop) |
9fb47c05 | 293 | { |
d62a17ae | 294 | if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_RECURSIVE)) |
295 | return nexthop->resolved; | |
9fb47c05 | 296 | |
d62a17ae | 297 | if (nexthop->next) |
298 | return nexthop->next; | |
9fb47c05 | 299 | |
d62a17ae | 300 | for (struct nexthop *par = nexthop->rparent; par; par = par->rparent) |
301 | if (par->next) | |
302 | return par->next; | |
9fb47c05 | 303 | |
d62a17ae | 304 | return NULL; |
9fb47c05 | 305 | } |
e3054ee9 | 306 | |
d62a17ae | 307 | unsigned int nexthop_level(struct nexthop *nexthop) |
e3054ee9 | 308 | { |
d62a17ae | 309 | unsigned int rv = 0; |
e3054ee9 | 310 | |
d62a17ae | 311 | for (struct nexthop *par = nexthop->rparent; par; par = par->rparent) |
312 | rv++; | |
e3054ee9 | 313 | |
d62a17ae | 314 | return rv; |
e3054ee9 | 315 | } |
d36d0d57 | 316 | |
1b1fe1c4 | 317 | uint32_t nexthop_hash(const struct nexthop *nexthop) |
d36d0d57 | 318 | { |
1b1fe1c4 | 319 | uint32_t key = 0x45afe398; |
d36d0d57 | 320 | |
1b1fe1c4 SW |
321 | key = jhash_3words(nexthop->type, nexthop->vrf_id, |
322 | nexthop->nh_label_type, key); | |
323 | /* gate and blackhole are together in a union */ | |
324 | key = jhash(&nexthop->gate, sizeof(nexthop->gate), key); | |
325 | key = jhash(&nexthop->src, sizeof(nexthop->src), key); | |
326 | key = jhash(&nexthop->rmap_src, sizeof(nexthop->rmap_src), key); | |
d36d0d57 | 327 | |
1b1fe1c4 SW |
328 | if (nexthop->nh_label) { |
329 | int labels = nexthop->nh_label->num_labels; | |
330 | int i = 0; | |
331 | ||
332 | while (labels >= 3) { | |
333 | key = jhash_3words(nexthop->nh_label->label[i], | |
334 | nexthop->nh_label->label[i + 1], | |
335 | nexthop->nh_label->label[i + 2], | |
336 | key); | |
337 | labels -= 3; | |
338 | i += 3; | |
339 | } | |
340 | ||
341 | if (labels >= 2) { | |
342 | key = jhash_2words(nexthop->nh_label->label[i], | |
343 | nexthop->nh_label->label[i + 1], | |
344 | key); | |
345 | labels -= 2; | |
346 | i += 2; | |
347 | } | |
348 | ||
349 | if (labels >= 1) | |
350 | key = jhash_1word(nexthop->nh_label->label[i], key); | |
351 | } | |
352 | ||
353 | switch (nexthop->type) { | |
354 | case NEXTHOP_TYPE_IPV4_IFINDEX: | |
355 | case NEXTHOP_TYPE_IPV6_IFINDEX: | |
356 | case NEXTHOP_TYPE_IFINDEX: | |
357 | key = jhash_1word(nexthop->ifindex, key); | |
358 | break; | |
359 | case NEXTHOP_TYPE_BLACKHOLE: | |
360 | case NEXTHOP_TYPE_IPV4: | |
361 | case NEXTHOP_TYPE_IPV6: | |
362 | break; | |
363 | } | |
d36d0d57 QY |
364 | return key; |
365 | } |