]> git.proxmox.com Git - mirror_frr.git/blame - lib/nexthop.c
lib,zebra,bgpd: Remove nexthop_same_no_recurse()
[mirror_frr.git] / lib / nexthop.c
CommitLineData
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 36DEFINE_MTYPE_STATIC(LIB, NEXTHOP, "Nexthop")
37DEFINE_MTYPE_STATIC(LIB, NH_LABEL, "Nexthop label")
4a1ab8e4 38
ebc403dd
SW
39static 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
67int 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 129int 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 163const 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 178bool 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 186struct nexthop *nexthop_new(void)
a399694f 187{
d62a17ae 188 return XCALLOC(MTYPE_NEXTHOP, sizeof(struct nexthop));
a399694f
DS
189}
190
a399694f 191/* Free nexthop. */
d62a17ae 192void 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 201void 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
211bool 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 229void 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 246void 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 254const 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 296struct 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 311unsigned 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 321uint32_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}