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