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