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