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
  36 DEFINE_MTYPE_STATIC(LIB, NEXTHOP, "Nexthop")
  37 DEFINE_MTYPE_STATIC(LIB, NH_LABEL, "Nexthop label")
  38
  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
  67 int nexthop_cmp(const struct nexthop *next1, const struct nexthop *next2)
  68 {
  69         int ret = 0;
  70         uint32_t n1 = 0;
  71         uint32_2 n2 = 0;
  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
  85         switch (next1->type) {
  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));
  96                 if (ret)
  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));
 102                 if (ret)
 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));
 122         if (ret)
 123                 return ret;
 124
 125         ret = nexthop_labels_cmp(next1, next2);
 126         return ret;
 127 }
 128
 129 /* check if nexthops are same, non-recursive */
 130 int nexthop_same_no_recurse(const struct nexthop *next1,
 131                             const struct nexthop *next2)
 132 {
 133         if (next1->type != next2->type)
 134                 return 0;
 135
 136         switch (next1->type) {
 137         case NEXTHOP_TYPE_IPV4:
 138         case NEXTHOP_TYPE_IPV4_IFINDEX:
 139                 if (!IPV4_ADDR_SAME(&next1->gate.ipv4, &next2->gate.ipv4))
 140                         return 0;
 141                 if (next1->ifindex && (next1->ifindex != next2->ifindex))
 142                         return 0;
 143                 break;
 144         case NEXTHOP_TYPE_IFINDEX:
 145                 if (next1->ifindex != next2->ifindex)
 146                         return 0;
 147                 break;
 148         case NEXTHOP_TYPE_IPV6:
 149                 if (!IPV6_ADDR_SAME(&next1->gate.ipv6, &next2->gate.ipv6))
 150                         return 0;
 151                 break;
 152         case NEXTHOP_TYPE_IPV6_IFINDEX:
 153                 if (!IPV6_ADDR_SAME(&next1->gate.ipv6, &next2->gate.ipv6))
 154                         return 0;
 155                 if (next1->ifindex != next2->ifindex)
 156                         return 0;
 157                 break;
 158         default:
 159                 /* do nothing */
 160                 break;
 161         }
 162         return 1;
 163 }
 164
 165 int nexthop_same_firsthop(struct nexthop *next1, struct nexthop *next2)
 166 {
 167         int type1 = NEXTHOP_FIRSTHOPTYPE(next1->type);
 168         int type2 = NEXTHOP_FIRSTHOPTYPE(next2->type);
 169
 170         if (type1 != type2)
 171                 return 0;
 172         switch (type1) {
 173         case NEXTHOP_TYPE_IPV4_IFINDEX:
 174                 if (!IPV4_ADDR_SAME(&next1->gate.ipv4, &next2->gate.ipv4))
 175                         return 0;
 176                 if (next1->ifindex != next2->ifindex)
 177                         return 0;
 178                 break;
 179         case NEXTHOP_TYPE_IFINDEX:
 180                 if (next1->ifindex != next2->ifindex)
 181                         return 0;
 182                 break;
 183         case NEXTHOP_TYPE_IPV6_IFINDEX:
 184                 if (!IPV6_ADDR_SAME(&next1->gate.ipv6, &next2->gate.ipv6))
 185                         return 0;
 186                 if (next1->ifindex != next2->ifindex)
 187                         return 0;
 188                 break;
 189         default:
 190                 /* do nothing */
 191                 break;
 192         }
 193         return 1;
 194 }
 195
 196 /*
 197  * nexthop_type_to_str
 198  */
 199 const char *nexthop_type_to_str(enum nexthop_types_t nh_type)
 200 {
 201         static const char *desc[] = {
 202                 "none",          "Directly connected",
 203                 "IPv4 nexthop",  "IPv4 nexthop with ifindex",
 204                 "IPv6 nexthop",  "IPv6 nexthop with ifindex",
 205                 "Null0 nexthop",
 206         };
 207
 208         return desc[nh_type];
 209 }
 210
 211 /*
 212  * Check if the labels match for the 2 nexthops specified.
 213  */
 214 bool nexthop_labels_match(const struct nexthop *nh1, const struct nexthop *nh2)
 215 {
 216         if (nexthop_labels_cmp(nh1, nh2) != 0)
 217                 return false;
 218
 219         return true;
 220 }
 221
 222 struct nexthop *nexthop_new(void)
 223 {
 224         return XCALLOC(MTYPE_NEXTHOP, sizeof(struct nexthop));
 225 }
 226
 227 /* Free nexthop. */
 228 void nexthop_free(struct nexthop *nexthop)
 229 {
 230         nexthop_del_labels(nexthop);
 231         if (nexthop->resolved)
 232                 nexthops_free(nexthop->resolved);
 233         XFREE(MTYPE_NEXTHOP, nexthop);
 234 }
 235
 236 /* Frees a list of nexthops */
 237 void nexthops_free(struct nexthop *nexthop)
 238 {
 239         struct nexthop *nh, *next;
 240
 241         for (nh = nexthop; nh; nh = next) {
 242                 next = nh->next;
 243                 nexthop_free(nh);
 244         }
 245 }
 246
 247 bool nexthop_same(const struct nexthop *nh1, const struct nexthop *nh2)
 248 {
 249         if (nh1 && !nh2)
 250                 return false;
 251
 252         if (!nh1 && nh2)
 253                 return false;
 254
 255         if (nh1 == nh2)
 256                 return true;
 257
 258         if (nh1->vrf_id != nh2->vrf_id)
 259                 return false;
 260
 261         if (nh1->type != nh2->type)
 262                 return false;
 263
 264         switch (nh1->type) {
 265         case NEXTHOP_TYPE_IFINDEX:
 266                 if (nh1->ifindex != nh2->ifindex)
 267                         return false;
 268                 break;
 269         case NEXTHOP_TYPE_IPV4:
 270                 if (nh1->gate.ipv4.s_addr != nh2->gate.ipv4.s_addr)
 271                         return false;
 272                 break;
 273         case NEXTHOP_TYPE_IPV4_IFINDEX:
 274                 if (nh1->gate.ipv4.s_addr != nh2->gate.ipv4.s_addr)
 275                         return false;
 276                 if (nh1->ifindex != nh2->ifindex)
 277                         return false;
 278                 break;
 279         case NEXTHOP_TYPE_IPV6:
 280                 if (memcmp(&nh1->gate.ipv6, &nh2->gate.ipv6, 16))
 281                         return false;
 282                 break;
 283         case NEXTHOP_TYPE_IPV6_IFINDEX:
 284                 if (memcmp(&nh1->gate.ipv6, &nh2->gate.ipv6, 16))
 285                         return false;
 286                 if (nh1->ifindex != nh2->ifindex)
 287                         return false;
 288                 break;
 289         case NEXTHOP_TYPE_BLACKHOLE:
 290                 if (nh1->bh_type != nh2->bh_type)
 291                         return false;
 292                 break;
 293         }
 294
 295         /* Compare labels too (if present) */
 296         return (!!nexthop_labels_match(nh1, nh2));
 297 }
 298
 299 /* Update nexthop with label information. */
 300 void nexthop_add_labels(struct nexthop *nexthop, enum lsp_types_t type,
 301                         uint8_t num_labels, mpls_label_t *label)
 302 {
 303         struct mpls_label_stack *nh_label;
 304         int i;
 305
 306         nexthop->nh_label_type = type;
 307         nh_label = XCALLOC(MTYPE_NH_LABEL,
 308                            sizeof(struct mpls_label_stack)
 309                                    + num_labels * sizeof(mpls_label_t));
 310         nh_label->num_labels = num_labels;
 311         for (i = 0; i < num_labels; i++)
 312                 nh_label->label[i] = *(label + i);
 313         nexthop->nh_label = nh_label;
 314 }
 315
 316 /* Free label information of nexthop, if present. */
 317 void nexthop_del_labels(struct nexthop *nexthop)
 318 {
 319         if (nexthop->nh_label) {
 320                 XFREE(MTYPE_NH_LABEL, nexthop->nh_label);
 321                 nexthop->nh_label_type = ZEBRA_LSP_NONE;
 322         }
 323 }
 324
 325 const char *nexthop2str(const struct nexthop *nexthop, char *str, int size)
 326 {
 327         switch (nexthop->type) {
 328         case NEXTHOP_TYPE_IFINDEX:
 329                 snprintf(str, size, "if %u", nexthop->ifindex);
 330                 break;
 331         case NEXTHOP_TYPE_IPV4:
 332         case NEXTHOP_TYPE_IPV4_IFINDEX:
 333                 snprintf(str, size, "%s if %u", inet_ntoa(nexthop->gate.ipv4),
 334                          nexthop->ifindex);
 335                 break;
 336         case NEXTHOP_TYPE_IPV6:
 337         case NEXTHOP_TYPE_IPV6_IFINDEX:
 338                 snprintf(str, size, "%s if %u", inet6_ntoa(nexthop->gate.ipv6),
 339                          nexthop->ifindex);
 340                 break;
 341         case NEXTHOP_TYPE_BLACKHOLE:
 342                 snprintf(str, size, "blackhole");
 343                 break;
 344         default:
 345                 snprintf(str, size, "unknown");
 346                 break;
 347         }
 348
 349         return str;
 350 }
 351
 352 /*
 353  * Iteration step for ALL_NEXTHOPS macro:
 354  * This is the tricky part. Check if `nexthop' has
 355  * NEXTHOP_FLAG_RECURSIVE set. If yes, this implies that `nexthop' has
 356  * at least one nexthop attached to `nexthop->resolved', which will be
 357  * the next one.
 358  *
 359  * If NEXTHOP_FLAG_RECURSIVE is not set, `nexthop' will progress in its
 360  * current chain. In case its current chain end is reached, it will move
 361  * upwards in the recursion levels and progress there. Whenever a step
 362  * forward in a chain is done, recursion will be checked again.
 363  * In a nustshell, it's equivalent to a pre-traversal order assuming that
 364  * left branch is 'resolved' and right branch is 'next':
 365  * https://en.wikipedia.org/wiki/Tree_traversal#/media/File:Sorted_binary_tree_preorder.svg
 366  */
 367 struct nexthop *nexthop_next(struct nexthop *nexthop)
 368 {
 369         if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
 370                 return nexthop->resolved;
 371
 372         if (nexthop->next)
 373                 return nexthop->next;
 374
 375         for (struct nexthop *par = nexthop->rparent; par; par = par->rparent)
 376                 if (par->next)
 377                         return par->next;
 378
 379         return NULL;
 380 }
 381
 382 unsigned int nexthop_level(struct nexthop *nexthop)
 383 {
 384         unsigned int rv = 0;
 385
 386         for (struct nexthop *par = nexthop->rparent; par; par = par->rparent)
 387                 rv++;
 388
 389         return rv;
 390 }
 391
 392 uint32_t nexthop_hash(const struct nexthop *nexthop)
 393 {
 394         uint32_t key = 0x45afe398;
 395
 396         key = jhash_3words(nexthop->type, nexthop->vrf_id,
 397                            nexthop->nh_label_type, key);
 398         /* gate and blackhole are together in a union */
 399         key = jhash(&nexthop->gate, sizeof(nexthop->gate), key);
 400         key = jhash(&nexthop->src, sizeof(nexthop->src), key);
 401         key = jhash(&nexthop->rmap_src, sizeof(nexthop->rmap_src), key);
 402
 403         if (nexthop->nh_label) {
 404                 int labels = nexthop->nh_label->num_labels;
 405                 int i = 0;
 406
 407                 while (labels >= 3) {
 408                         key = jhash_3words(nexthop->nh_label->label[i],
 409                                            nexthop->nh_label->label[i + 1],
 410                                            nexthop->nh_label->label[i + 2],
 411                                            key);
 412                         labels -= 3;
 413                         i += 3;
 414                 }
 415
 416                 if (labels >= 2) {
 417                         key = jhash_2words(nexthop->nh_label->label[i],
 418                                            nexthop->nh_label->label[i + 1],
 419                                            key);
 420                         labels -= 2;
 421                         i += 2;
 422                 }
 423
 424                 if (labels >= 1)
 425                         key = jhash_1word(nexthop->nh_label->label[i], key);
 426         }
 427
 428         switch (nexthop->type) {
 429         case NEXTHOP_TYPE_IPV4_IFINDEX:
 430         case NEXTHOP_TYPE_IPV6_IFINDEX:
 431         case NEXTHOP_TYPE_IFINDEX:
 432                 key = jhash_1word(nexthop->ifindex, key);
 433                 break;
 434         case NEXTHOP_TYPE_BLACKHOLE:
 435         case NEXTHOP_TYPE_IPV4:
 436         case NEXTHOP_TYPE_IPV6:
 437                 break;
 438         }
 439         return key;
 440 }