]>
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 | |
ebc403dd SW |
39 | static int nexthop_labels_cmp(const struct nexthop *nh1, |
40 | const struct nexthop *nh2) | |
41 | { | |
42 | const struct mpls_label_stack *nhl1 = NULL; | |
43 | const struct mpls_label_stack *nhl2 = NULL; | |
44 | ||
45 | nhl1 = nh1->nh_label; | |
46 | nhl2 = nh2->nh_label; | |
47 | ||
48 | /* No labels is a match */ | |
49 | if (!nhl1 && !nhl2) | |
50 | return 0; | |
51 | ||
52 | if (nhl1 && !nhl2) | |
53 | return 1; | |
54 | ||
55 | if (nhl2 && !nhl1) | |
56 | return -1; | |
57 | ||
58 | if (nhl1->num_labels > nhl2->num_labels) | |
59 | return 1; | |
60 | ||
61 | if (nhl1->num_labels < nhl2->num_labels) | |
62 | return -1; | |
63 | ||
64 | return memcmp(nhl1->label, nhl2->label, nhl1->num_labels); | |
65 | } | |
66 | ||
776c3e90 DS |
67 | int nexthop_cmp(const struct nexthop *next1, const struct nexthop *next2) |
68 | { | |
ff0e16da SW |
69 | int ret = 0; |
70 | uint32_t n1 = 0; | |
2ed74b93 | 71 | uint32_t n2 = 0; |
776c3e90 DS |
72 | |
73 | if (next1->vrf_id < next2->vrf_id) | |
74 | return -1; | |
75 | ||
76 | if (next1->vrf_id > next2->vrf_id) | |
77 | return 1; | |
78 | ||
79 | if (next1->type < next2->type) | |
80 | return -1; | |
81 | ||
82 | if (next1->type > next2->type) | |
83 | return 1; | |
84 | ||
ff0e16da | 85 | switch (next1->type) { |
776c3e90 DS |
86 | case NEXTHOP_TYPE_IPV4: |
87 | n1 = ntohl(next1->gate.ipv4.s_addr); | |
88 | n2 = ntohl(next2->gate.ipv4.s_addr); | |
89 | if (n1 < n2) | |
90 | return -1; | |
91 | if (n1 > n2) | |
92 | return 1; | |
93 | break; | |
94 | case NEXTHOP_TYPE_IPV6: | |
95 | ret = memcmp(&next1->gate, &next2->gate, sizeof(union g_addr)); | |
f932ce86 | 96 | if (ret) |
776c3e90 DS |
97 | return ret; |
98 | break; | |
99 | case NEXTHOP_TYPE_IPV4_IFINDEX: | |
100 | case NEXTHOP_TYPE_IPV6_IFINDEX: | |
101 | ret = memcmp(&next1->gate, &next2->gate, sizeof(union g_addr)); | |
f932ce86 | 102 | if (ret) |
776c3e90 DS |
103 | return ret; |
104 | /* Intentional Fall-Through */ | |
105 | case NEXTHOP_TYPE_IFINDEX: | |
106 | if (next1->ifindex < next2->ifindex) | |
107 | return -1; | |
108 | ||
109 | if (next1->ifindex > next2->ifindex) | |
110 | return 1; | |
111 | break; | |
112 | case NEXTHOP_TYPE_BLACKHOLE: | |
113 | if (next1->bh_type < next2->bh_type) | |
114 | return -1; | |
115 | ||
116 | if (next1->bh_type > next2->bh_type) | |
117 | return 1; | |
118 | break; | |
119 | } | |
120 | ||
121 | ret = memcmp(&next1->src, &next2->src, sizeof(union g_addr)); | |
ff0e16da SW |
122 | if (ret) |
123 | return ret; | |
124 | ||
125 | ret = nexthop_labels_cmp(next1, next2); | |
776c3e90 DS |
126 | return ret; |
127 | } | |
128 | ||
996c9314 | 129 | int nexthop_same_firsthop(struct nexthop *next1, struct nexthop *next2) |
25b9cb0c DL |
130 | { |
131 | int type1 = NEXTHOP_FIRSTHOPTYPE(next1->type); | |
132 | int type2 = NEXTHOP_FIRSTHOPTYPE(next2->type); | |
133 | ||
134 | if (type1 != type2) | |
135 | return 0; | |
996c9314 | 136 | switch (type1) { |
25b9cb0c | 137 | case NEXTHOP_TYPE_IPV4_IFINDEX: |
996c9314 | 138 | if (!IPV4_ADDR_SAME(&next1->gate.ipv4, &next2->gate.ipv4)) |
25b9cb0c DL |
139 | return 0; |
140 | if (next1->ifindex != next2->ifindex) | |
141 | return 0; | |
142 | break; | |
143 | case NEXTHOP_TYPE_IFINDEX: | |
144 | if (next1->ifindex != next2->ifindex) | |
145 | return 0; | |
146 | break; | |
147 | case NEXTHOP_TYPE_IPV6_IFINDEX: | |
996c9314 | 148 | if (!IPV6_ADDR_SAME(&next1->gate.ipv6, &next2->gate.ipv6)) |
25b9cb0c DL |
149 | return 0; |
150 | if (next1->ifindex != next2->ifindex) | |
151 | return 0; | |
d62a17ae | 152 | break; |
153 | default: | |
154 | /* do nothing */ | |
155 | break; | |
156 | } | |
157 | return 1; | |
fb018d25 DS |
158 | } |
159 | ||
160 | /* | |
161 | * nexthop_type_to_str | |
162 | */ | |
d62a17ae | 163 | const char *nexthop_type_to_str(enum nexthop_types_t nh_type) |
fb018d25 | 164 | { |
d62a17ae | 165 | static const char *desc[] = { |
166 | "none", "Directly connected", | |
167 | "IPv4 nexthop", "IPv4 nexthop with ifindex", | |
168 | "IPv6 nexthop", "IPv6 nexthop with ifindex", | |
169 | "Null0 nexthop", | |
170 | }; | |
171 | ||
172 | return desc[nh_type]; | |
fb018d25 | 173 | } |
a399694f | 174 | |
a64448ba DS |
175 | /* |
176 | * Check if the labels match for the 2 nexthops specified. | |
177 | */ | |
89dc3160 | 178 | bool nexthop_labels_match(const struct nexthop *nh1, const struct nexthop *nh2) |
a64448ba | 179 | { |
89dc3160 SW |
180 | if (nexthop_labels_cmp(nh1, nh2) != 0) |
181 | return false; | |
a64448ba | 182 | |
89dc3160 | 183 | return true; |
a64448ba DS |
184 | } |
185 | ||
d62a17ae | 186 | struct nexthop *nexthop_new(void) |
a399694f | 187 | { |
d62a17ae | 188 | return XCALLOC(MTYPE_NEXTHOP, sizeof(struct nexthop)); |
a399694f DS |
189 | } |
190 | ||
a399694f | 191 | /* Free nexthop. */ |
d62a17ae | 192 | void nexthop_free(struct nexthop *nexthop) |
a399694f | 193 | { |
d62a17ae | 194 | nexthop_del_labels(nexthop); |
195 | if (nexthop->resolved) | |
196 | nexthops_free(nexthop->resolved); | |
197 | XFREE(MTYPE_NEXTHOP, nexthop); | |
a399694f DS |
198 | } |
199 | ||
200 | /* Frees a list of nexthops */ | |
d62a17ae | 201 | void nexthops_free(struct nexthop *nexthop) |
a399694f | 202 | { |
d62a17ae | 203 | struct nexthop *nh, *next; |
a399694f | 204 | |
d62a17ae | 205 | for (nh = nexthop; nh; nh = next) { |
206 | next = nh->next; | |
207 | nexthop_free(nh); | |
208 | } | |
a399694f | 209 | } |
80c2442a | 210 | |
31919191 DS |
211 | bool nexthop_same(const struct nexthop *nh1, const struct nexthop *nh2) |
212 | { | |
213 | if (nh1 && !nh2) | |
214 | return false; | |
215 | ||
216 | if (!nh1 && nh2) | |
217 | return false; | |
218 | ||
219 | if (nh1 == nh2) | |
220 | return true; | |
221 | ||
2ed74b93 | 222 | if (nexthop_cmp(nh1, nh2) != 0) |
31919191 DS |
223 | return false; |
224 | ||
2ed74b93 | 225 | return true; |
31919191 DS |
226 | } |
227 | ||
40c7bdb0 | 228 | /* Update nexthop with label information. */ |
d62a17ae | 229 | void nexthop_add_labels(struct nexthop *nexthop, enum lsp_types_t type, |
d7c0a89a | 230 | uint8_t num_labels, mpls_label_t *label) |
40c7bdb0 | 231 | { |
8ecdb26e | 232 | struct mpls_label_stack *nh_label; |
d62a17ae | 233 | int i; |
234 | ||
235 | nexthop->nh_label_type = type; | |
236 | nh_label = XCALLOC(MTYPE_NH_LABEL, | |
8ecdb26e | 237 | sizeof(struct mpls_label_stack) |
d62a17ae | 238 | + num_labels * sizeof(mpls_label_t)); |
239 | nh_label->num_labels = num_labels; | |
240 | for (i = 0; i < num_labels; i++) | |
241 | nh_label->label[i] = *(label + i); | |
242 | nexthop->nh_label = nh_label; | |
40c7bdb0 | 243 | } |
244 | ||
245 | /* Free label information of nexthop, if present. */ | |
d62a17ae | 246 | void nexthop_del_labels(struct nexthop *nexthop) |
40c7bdb0 | 247 | { |
d62a17ae | 248 | if (nexthop->nh_label) { |
249 | XFREE(MTYPE_NH_LABEL, nexthop->nh_label); | |
250 | nexthop->nh_label_type = ZEBRA_LSP_NONE; | |
251 | } | |
40c7bdb0 | 252 | } |
253 | ||
d36d0d57 | 254 | const char *nexthop2str(const struct nexthop *nexthop, char *str, int size) |
80c2442a | 255 | { |
d62a17ae | 256 | switch (nexthop->type) { |
257 | case NEXTHOP_TYPE_IFINDEX: | |
258 | snprintf(str, size, "if %u", nexthop->ifindex); | |
259 | break; | |
260 | case NEXTHOP_TYPE_IPV4: | |
d62a17ae | 261 | case NEXTHOP_TYPE_IPV4_IFINDEX: |
262 | snprintf(str, size, "%s if %u", inet_ntoa(nexthop->gate.ipv4), | |
263 | nexthop->ifindex); | |
264 | break; | |
265 | case NEXTHOP_TYPE_IPV6: | |
d62a17ae | 266 | case NEXTHOP_TYPE_IPV6_IFINDEX: |
267 | snprintf(str, size, "%s if %u", inet6_ntoa(nexthop->gate.ipv6), | |
268 | nexthop->ifindex); | |
269 | break; | |
270 | case NEXTHOP_TYPE_BLACKHOLE: | |
271 | snprintf(str, size, "blackhole"); | |
272 | break; | |
273 | default: | |
274 | snprintf(str, size, "unknown"); | |
275 | break; | |
276 | } | |
277 | ||
278 | return str; | |
80c2442a | 279 | } |
9fb47c05 CF |
280 | |
281 | /* | |
282 | * Iteration step for ALL_NEXTHOPS macro: | |
283 | * This is the tricky part. Check if `nexthop' has | |
284 | * NEXTHOP_FLAG_RECURSIVE set. If yes, this implies that `nexthop' has | |
285 | * at least one nexthop attached to `nexthop->resolved', which will be | |
286 | * the next one. | |
287 | * | |
288 | * If NEXTHOP_FLAG_RECURSIVE is not set, `nexthop' will progress in its | |
289 | * current chain. In case its current chain end is reached, it will move | |
290 | * upwards in the recursion levels and progress there. Whenever a step | |
291 | * forward in a chain is done, recursion will be checked again. | |
292 | * In a nustshell, it's equivalent to a pre-traversal order assuming that | |
293 | * left branch is 'resolved' and right branch is 'next': | |
294 | * https://en.wikipedia.org/wiki/Tree_traversal#/media/File:Sorted_binary_tree_preorder.svg | |
295 | */ | |
d62a17ae | 296 | struct nexthop *nexthop_next(struct nexthop *nexthop) |
9fb47c05 | 297 | { |
d62a17ae | 298 | if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_RECURSIVE)) |
299 | return nexthop->resolved; | |
9fb47c05 | 300 | |
d62a17ae | 301 | if (nexthop->next) |
302 | return nexthop->next; | |
9fb47c05 | 303 | |
d62a17ae | 304 | for (struct nexthop *par = nexthop->rparent; par; par = par->rparent) |
305 | if (par->next) | |
306 | return par->next; | |
9fb47c05 | 307 | |
d62a17ae | 308 | return NULL; |
9fb47c05 | 309 | } |
e3054ee9 | 310 | |
d62a17ae | 311 | unsigned int nexthop_level(struct nexthop *nexthop) |
e3054ee9 | 312 | { |
d62a17ae | 313 | unsigned int rv = 0; |
e3054ee9 | 314 | |
d62a17ae | 315 | for (struct nexthop *par = nexthop->rparent; par; par = par->rparent) |
316 | rv++; | |
e3054ee9 | 317 | |
d62a17ae | 318 | return rv; |
e3054ee9 | 319 | } |
d36d0d57 | 320 | |
1b1fe1c4 | 321 | uint32_t nexthop_hash(const struct nexthop *nexthop) |
d36d0d57 | 322 | { |
1b1fe1c4 | 323 | uint32_t key = 0x45afe398; |
d36d0d57 | 324 | |
1b1fe1c4 SW |
325 | key = jhash_3words(nexthop->type, nexthop->vrf_id, |
326 | nexthop->nh_label_type, key); | |
327 | /* gate and blackhole are together in a union */ | |
328 | key = jhash(&nexthop->gate, sizeof(nexthop->gate), key); | |
329 | key = jhash(&nexthop->src, sizeof(nexthop->src), key); | |
330 | key = jhash(&nexthop->rmap_src, sizeof(nexthop->rmap_src), key); | |
d36d0d57 | 331 | |
1b1fe1c4 SW |
332 | if (nexthop->nh_label) { |
333 | int labels = nexthop->nh_label->num_labels; | |
334 | int i = 0; | |
335 | ||
336 | while (labels >= 3) { | |
337 | key = jhash_3words(nexthop->nh_label->label[i], | |
338 | nexthop->nh_label->label[i + 1], | |
339 | nexthop->nh_label->label[i + 2], | |
340 | key); | |
341 | labels -= 3; | |
342 | i += 3; | |
343 | } | |
344 | ||
345 | if (labels >= 2) { | |
346 | key = jhash_2words(nexthop->nh_label->label[i], | |
347 | nexthop->nh_label->label[i + 1], | |
348 | key); | |
349 | labels -= 2; | |
350 | i += 2; | |
351 | } | |
352 | ||
353 | if (labels >= 1) | |
354 | key = jhash_1word(nexthop->nh_label->label[i], key); | |
355 | } | |
356 | ||
357 | switch (nexthop->type) { | |
358 | case NEXTHOP_TYPE_IPV4_IFINDEX: | |
359 | case NEXTHOP_TYPE_IPV6_IFINDEX: | |
360 | case NEXTHOP_TYPE_IFINDEX: | |
361 | key = jhash_1word(nexthop->ifindex, key); | |
362 | break; | |
363 | case NEXTHOP_TYPE_BLACKHOLE: | |
364 | case NEXTHOP_TYPE_IPV4: | |
365 | case NEXTHOP_TYPE_IPV6: | |
366 | break; | |
367 | } | |
d36d0d57 QY |
368 | return key; |
369 | } |