lib/nexthop.c

   1 /* A generic nexthop structure
   2  * Copyright (C) 2013 Cumulus Networks, Inc.
   3  *
   4  * This file is part of Quagga.
   5  *
   6  * Quagga is free software; you can redistribute it and/or modify it
   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  *
  11  * Quagga is distributed in the hope that it will be useful, but
  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  *
  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
  19  */
  20 #include <zebra.h>
  21
  22 #include "prefix.h"
  23 #include "table.h"
  24 #include "memory.h"
  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"
  33 #include "mpls.h"
  34 #include "jhash.h"
  35 #include "printfrr.h"
  36
  37 DEFINE_MTYPE_STATIC(LIB, NEXTHOP, "Nexthop")
  38 DEFINE_MTYPE_STATIC(LIB, NH_LABEL, "Nexthop label")
  39
  40 static int _nexthop_labels_cmp(const struct nexthop *nh1,
  41                                const struct nexthop *nh2)
  42 {
  43         const struct mpls_label_stack *nhl1 = NULL;
  44         const struct mpls_label_stack *nhl2 = NULL;
  45
  46         nhl1 = nh1->nh_label;
  47         nhl2 = nh2->nh_label;
  48
  49         /* No labels is a match */
  50         if (!nhl1 && !nhl2)
  51                 return 0;
  52
  53         if (nhl1 && !nhl2)
  54                 return 1;
  55
  56         if (nhl2 && !nhl1)
  57                 return -1;
  58
  59         if (nhl1->num_labels > nhl2->num_labels)
  60                 return 1;
  61
  62         if (nhl1->num_labels < nhl2->num_labels)
  63                 return -1;
  64
  65         return memcmp(nhl1->label, nhl2->label, nhl1->num_labels);
  66 }
  67
  68 static int _nexthop_g_addr_cmp(enum nexthop_types_t type,
  69                                const union g_addr *addr1,
  70                                const union g_addr *addr2)
  71 {
  72         int ret = 0;
  73
  74         switch (type) {
  75         case NEXTHOP_TYPE_IPV4:
  76         case NEXTHOP_TYPE_IPV4_IFINDEX:
  77                 ret = IPV4_ADDR_CMP(&addr1->ipv4, &addr2->ipv4);
  78                 break;
  79         case NEXTHOP_TYPE_IPV6:
  80         case NEXTHOP_TYPE_IPV6_IFINDEX:
  81                 ret = IPV6_ADDR_CMP(&addr1->ipv6, &addr2->ipv6);
  82                 break;
  83         case NEXTHOP_TYPE_IFINDEX:
  84         case NEXTHOP_TYPE_BLACKHOLE:
  85                 /* No addr here */
  86                 break;
  87         }
  88
  89         return ret;
  90 }
  91
  92 static int _nexthop_gateway_cmp(const struct nexthop *nh1,
  93                                 const struct nexthop *nh2)
  94 {
  95         return _nexthop_g_addr_cmp(nh1->type, &nh1->gate, &nh2->gate);
  96 }
  97
  98 static int _nexthop_source_cmp(const struct nexthop *nh1,
  99                                const struct nexthop *nh2)
 100 {
 101         return _nexthop_g_addr_cmp(nh1->type, &nh1->src, &nh2->src);
 102 }
 103
 104 static int _nexthop_cmp_no_labels(const struct nexthop *next1,
 105                                   const struct nexthop *next2)
 106 {
 107         int ret = 0;
 108
 109         if (next1->vrf_id < next2->vrf_id)
 110                 return -1;
 111
 112         if (next1->vrf_id > next2->vrf_id)
 113                 return 1;
 114
 115         if (next1->type < next2->type)
 116                 return -1;
 117
 118         if (next1->type > next2->type)
 119                 return 1;
 120
 121         switch (next1->type) {
 122         case NEXTHOP_TYPE_IPV4:
 123         case NEXTHOP_TYPE_IPV6:
 124                 ret = _nexthop_gateway_cmp(next1, next2);
 125                 if (ret != 0)
 126                         return ret;
 127                 break;
 128         case NEXTHOP_TYPE_IPV4_IFINDEX:
 129         case NEXTHOP_TYPE_IPV6_IFINDEX:
 130                 ret = _nexthop_gateway_cmp(next1, next2);
 131                 if (ret != 0)
 132                         return ret;
 133                 /* Intentional Fall-Through */
 134         case NEXTHOP_TYPE_IFINDEX:
 135                 if (next1->ifindex < next2->ifindex)
 136                         return -1;
 137
 138                 if (next1->ifindex > next2->ifindex)
 139                         return 1;
 140                 break;
 141         case NEXTHOP_TYPE_BLACKHOLE:
 142                 if (next1->bh_type < next2->bh_type)
 143                         return -1;
 144
 145                 if (next1->bh_type > next2->bh_type)
 146                         return 1;
 147                 break;
 148         }
 149
 150         ret = _nexthop_source_cmp(next1, next2);
 151
 152         return ret;
 153 }
 154
 155 int nexthop_cmp(const struct nexthop *next1, const struct nexthop *next2)
 156 {
 157         int ret = 0;
 158
 159         ret = _nexthop_cmp_no_labels(next1, next2);
 160         if (ret != 0)
 161                 return ret;
 162
 163         ret = _nexthop_labels_cmp(next1, next2);
 164
 165         return ret;
 166 }
 167
 168 int nexthop_same_firsthop(struct nexthop *next1, struct nexthop *next2)
 169 {
 170         int type1 = NEXTHOP_FIRSTHOPTYPE(next1->type);
 171         int type2 = NEXTHOP_FIRSTHOPTYPE(next2->type);
 172
 173         if (type1 != type2)
 174                 return 0;
 175         switch (type1) {
 176         case NEXTHOP_TYPE_IPV4_IFINDEX:
 177                 if (!IPV4_ADDR_SAME(&next1->gate.ipv4, &next2->gate.ipv4))
 178                         return 0;
 179                 if (next1->ifindex != next2->ifindex)
 180                         return 0;
 181                 break;
 182         case NEXTHOP_TYPE_IFINDEX:
 183                 if (next1->ifindex != next2->ifindex)
 184                         return 0;
 185                 break;
 186         case NEXTHOP_TYPE_IPV6_IFINDEX:
 187                 if (!IPV6_ADDR_SAME(&next1->gate.ipv6, &next2->gate.ipv6))
 188                         return 0;
 189                 if (next1->ifindex != next2->ifindex)
 190                         return 0;
 191                 break;
 192         default:
 193                 /* do nothing */
 194                 break;
 195         }
 196         return 1;
 197 }
 198
 199 /*
 200  * nexthop_type_to_str
 201  */
 202 const char *nexthop_type_to_str(enum nexthop_types_t nh_type)
 203 {
 204         static const char *desc[] = {
 205                 "none",          "Directly connected",
 206                 "IPv4 nexthop",  "IPv4 nexthop with ifindex",
 207                 "IPv6 nexthop",  "IPv6 nexthop with ifindex",
 208                 "Null0 nexthop",
 209         };
 210
 211         return desc[nh_type];
 212 }
 213
 214 /*
 215  * Check if the labels match for the 2 nexthops specified.
 216  */
 217 bool nexthop_labels_match(const struct nexthop *nh1, const struct nexthop *nh2)
 218 {
 219         if (_nexthop_labels_cmp(nh1, nh2) != 0)
 220                 return false;
 221
 222         return true;
 223 }
 224
 225 struct nexthop *nexthop_new(void)
 226 {
 227         return XCALLOC(MTYPE_NEXTHOP, sizeof(struct nexthop));
 228 }
 229
 230 /* Free nexthop. */
 231 void nexthop_free(struct nexthop *nexthop)
 232 {
 233         nexthop_del_labels(nexthop);
 234         if (nexthop->resolved)
 235                 nexthops_free(nexthop->resolved);
 236         XFREE(MTYPE_NEXTHOP, nexthop);
 237 }
 238
 239 /* Frees a list of nexthops */
 240 void nexthops_free(struct nexthop *nexthop)
 241 {
 242         struct nexthop *nh, *next;
 243
 244         for (nh = nexthop; nh; nh = next) {
 245                 next = nh->next;
 246                 nexthop_free(nh);
 247         }
 248 }
 249
 250 bool nexthop_same(const struct nexthop *nh1, const struct nexthop *nh2)
 251 {
 252         if (nh1 && !nh2)
 253                 return false;
 254
 255         if (!nh1 && nh2)
 256                 return false;
 257
 258         if (nh1 == nh2)
 259                 return true;
 260
 261         if (nexthop_cmp(nh1, nh2) != 0)
 262                 return false;
 263
 264         return true;
 265 }
 266
 267 bool nexthop_same_no_labels(const struct nexthop *nh1,
 268                             const struct nexthop *nh2)
 269 {
 270         if (nh1 && !nh2)
 271                 return false;
 272
 273         if (!nh1 && nh2)
 274                 return false;
 275
 276         if (nh1 == nh2)
 277                 return true;
 278
 279         if (_nexthop_cmp_no_labels(nh1, nh2) != 0)
 280                 return false;
 281
 282         return true;
 283 }
 284
 285 /* Update nexthop with label information. */
 286 void nexthop_add_labels(struct nexthop *nexthop, enum lsp_types_t type,
 287                         uint8_t num_labels, mpls_label_t *label)
 288 {
 289         struct mpls_label_stack *nh_label;
 290         int i;
 291
 292         nexthop->nh_label_type = type;
 293         nh_label = XCALLOC(MTYPE_NH_LABEL,
 294                            sizeof(struct mpls_label_stack)
 295                                    + num_labels * sizeof(mpls_label_t));
 296         nh_label->num_labels = num_labels;
 297         for (i = 0; i < num_labels; i++)
 298                 nh_label->label[i] = *(label + i);
 299         nexthop->nh_label = nh_label;
 300 }
 301
 302 /* Free label information of nexthop, if present. */
 303 void nexthop_del_labels(struct nexthop *nexthop)
 304 {
 305         if (nexthop->nh_label) {
 306                 XFREE(MTYPE_NH_LABEL, nexthop->nh_label);
 307                 nexthop->nh_label_type = ZEBRA_LSP_NONE;
 308         }
 309 }
 310
 311 const char *nexthop2str(const struct nexthop *nexthop, char *str, int size)
 312 {
 313         switch (nexthop->type) {
 314         case NEXTHOP_TYPE_IFINDEX:
 315                 snprintf(str, size, "if %u", nexthop->ifindex);
 316                 break;
 317         case NEXTHOP_TYPE_IPV4:
 318         case NEXTHOP_TYPE_IPV4_IFINDEX:
 319                 snprintf(str, size, "%s if %u", inet_ntoa(nexthop->gate.ipv4),
 320                          nexthop->ifindex);
 321                 break;
 322         case NEXTHOP_TYPE_IPV6:
 323         case NEXTHOP_TYPE_IPV6_IFINDEX:
 324                 snprintf(str, size, "%s if %u", inet6_ntoa(nexthop->gate.ipv6),
 325                          nexthop->ifindex);
 326                 break;
 327         case NEXTHOP_TYPE_BLACKHOLE:
 328                 snprintf(str, size, "blackhole");
 329                 break;
 330         default:
 331                 snprintf(str, size, "unknown");
 332                 break;
 333         }
 334
 335         return str;
 336 }
 337
 338 /*
 339  * Iteration step for ALL_NEXTHOPS macro:
 340  * This is the tricky part. Check if `nexthop' has
 341  * NEXTHOP_FLAG_RECURSIVE set. If yes, this implies that `nexthop' has
 342  * at least one nexthop attached to `nexthop->resolved', which will be
 343  * the next one.
 344  *
 345  * If NEXTHOP_FLAG_RECURSIVE is not set, `nexthop' will progress in its
 346  * current chain. In case its current chain end is reached, it will move
 347  * upwards in the recursion levels and progress there. Whenever a step
 348  * forward in a chain is done, recursion will be checked again.
 349  * In a nustshell, it's equivalent to a pre-traversal order assuming that
 350  * left branch is 'resolved' and right branch is 'next':
 351  * https://en.wikipedia.org/wiki/Tree_traversal#/media/File:Sorted_binary_tree_preorder.svg
 352  */
 353 struct nexthop *nexthop_next(struct nexthop *nexthop)
 354 {
 355         if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
 356                 return nexthop->resolved;
 357
 358         if (nexthop->next)
 359                 return nexthop->next;
 360
 361         for (struct nexthop *par = nexthop->rparent; par; par = par->rparent)
 362                 if (par->next)
 363                         return par->next;
 364
 365         return NULL;
 366 }
 367
 368 unsigned int nexthop_level(struct nexthop *nexthop)
 369 {
 370         unsigned int rv = 0;
 371
 372         for (struct nexthop *par = nexthop->rparent; par; par = par->rparent)
 373                 rv++;
 374
 375         return rv;
 376 }
 377
 378 uint32_t nexthop_hash(const struct nexthop *nexthop)
 379 {
 380         uint32_t key = 0x45afe398;
 381
 382         key = jhash_3words(nexthop->type, nexthop->vrf_id,
 383                            nexthop->nh_label_type, key);
 384         /* gate and blackhole are together in a union */
 385         key = jhash(&nexthop->gate, sizeof(nexthop->gate), key);
 386         key = jhash(&nexthop->src, sizeof(nexthop->src), key);
 387         key = jhash(&nexthop->rmap_src, sizeof(nexthop->rmap_src), key);
 388
 389         if (nexthop->nh_label) {
 390                 int labels = nexthop->nh_label->num_labels;
 391                 int i = 0;
 392
 393                 while (labels >= 3) {
 394                         key = jhash_3words(nexthop->nh_label->label[i],
 395                                            nexthop->nh_label->label[i + 1],
 396                                            nexthop->nh_label->label[i + 2],
 397                                            key);
 398                         labels -= 3;
 399                         i += 3;
 400                 }
 401
 402                 if (labels >= 2) {
 403                         key = jhash_2words(nexthop->nh_label->label[i],
 404                                            nexthop->nh_label->label[i + 1],
 405                                            key);
 406                         labels -= 2;
 407                         i += 2;
 408                 }
 409
 410                 if (labels >= 1)
 411                         key = jhash_1word(nexthop->nh_label->label[i], key);
 412         }
 413
 414         switch (nexthop->type) {
 415         case NEXTHOP_TYPE_IPV4_IFINDEX:
 416         case NEXTHOP_TYPE_IPV6_IFINDEX:
 417         case NEXTHOP_TYPE_IFINDEX:
 418                 key = jhash_1word(nexthop->ifindex, key);
 419                 break;
 420         case NEXTHOP_TYPE_BLACKHOLE:
 421         case NEXTHOP_TYPE_IPV4:
 422         case NEXTHOP_TYPE_IPV6:
 423                 break;
 424         }
 425         return key;
 426 }
 427
 428 /*
 429  * nexthop printing variants:
 430  *      %pNHvv
 431  *              via 1.2.3.4
 432  *              via 1.2.3.4, eth0
 433  *              is directly connected, eth0
 434  *              unreachable (blackhole)
 435  *      %pNHv
 436  *              1.2.3.4
 437  *              1.2.3.4, via eth0
 438  *              directly connected, eth0
 439  *              unreachable (blackhole)
 440  *      %pNHs
 441  *              nexthop2str()
 442  */
 443 printfrr_ext_autoreg_p("NH", printfrr_nh)
 444 static ssize_t printfrr_nh(char *buf, size_t bsz, const char *fmt,
 445                            int prec, const void *ptr)
 446 {
 447         const struct nexthop *nexthop = ptr;
 448         struct fbuf fb = { .buf = buf, .pos = buf, .len = bsz - 1 };
 449         bool do_ifi = false;
 450         const char *s, *v_is = "", *v_via = "", *v_viaif = "via ";
 451         ssize_t ret = 3;
 452
 453         switch (fmt[2]) {
 454         case 'v':
 455                 if (fmt[3] == 'v') {
 456                         v_is = "is ";
 457                         v_via = "via ";
 458                         v_viaif = "";
 459                         ret++;
 460                 }
 461
 462                 switch (nexthop->type) {
 463                 case NEXTHOP_TYPE_IPV4:
 464                 case NEXTHOP_TYPE_IPV4_IFINDEX:
 465                         bprintfrr(&fb, "%s%pI4", v_via, &nexthop->gate.ipv4);
 466                         do_ifi = true;
 467                         break;
 468                 case NEXTHOP_TYPE_IPV6:
 469                 case NEXTHOP_TYPE_IPV6_IFINDEX:
 470                         bprintfrr(&fb, "%s%pI6", v_via, &nexthop->gate.ipv6);
 471                         do_ifi = true;
 472                         break;
 473                 case NEXTHOP_TYPE_IFINDEX:
 474                         bprintfrr(&fb, "%sdirectly connected, %s", v_is,
 475                                 ifindex2ifname(nexthop->ifindex,
 476                                                nexthop->vrf_id));
 477                         break;
 478                 case NEXTHOP_TYPE_BLACKHOLE:
 479                         switch (nexthop->bh_type) {
 480                         case BLACKHOLE_REJECT:
 481                                 s = " (ICMP unreachable)";
 482                                 break;
 483                         case BLACKHOLE_ADMINPROHIB:
 484                                 s = " (ICMP admin-prohibited)";
 485                                 break;
 486                         case BLACKHOLE_NULL:
 487                                 s = " (blackhole)";
 488                                 break;
 489                         default:
 490                                 s = "";
 491                                 break;
 492                         }
 493                         bprintfrr(&fb, "unreachable%s", s);
 494                         break;
 495                 default:
 496                         break;
 497                 }
 498                 if (do_ifi && nexthop->ifindex)
 499                         bprintfrr(&fb, ", %s%s", v_viaif, ifindex2ifname(
 500                                         nexthop->ifindex,
 501                                         nexthop->vrf_id));
 502
 503                 *fb.pos = '\0';
 504                 return ret;
 505         case 's':
 506                 nexthop2str(nexthop, buf, bsz);
 507                 return 3;
 508         }
 509         return 0;
 510 }