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