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