zebra/rib.h

   1 /*
   2  * Routing Information Base header
   3  * Copyright (C) 1997 Kunihiro Ishiguro
   4  *
   5  * This file is part of GNU Zebra.
   6  *
   7  * GNU Zebra is free software; you can redistribute it and/or modify it
   8  * under the terms of the GNU General Public License as published by the
   9  * Free Software Foundation; either version 2, or (at your option) any
  10  * later version.
  11  *
  12  * GNU Zebra is distributed in the hope that it will be useful, but
  13  * WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License along
  18  * with this program; see the file COPYING; if not, write to the Free Software
  19  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  20  */
  21
  22 #ifndef _ZEBRA_RIB_H
  23 #define _ZEBRA_RIB_H
  24
  25 #include "zebra.h"
  26 #include "hook.h"
  27 #include "linklist.h"
  28 #include "prefix.h"
  29 #include "table.h"
  30 #include "queue.h"
  31 #include "nexthop.h"
  32 #include "vrf.h"
  33 #include "if.h"
  34 #include "mpls.h"
  35 #include "srcdest_table.h"
  36
  37 #define DISTANCE_INFINITY  255
  38 #define ZEBRA_KERNEL_TABLE_MAX 252 /* support for no more than this rt tables */
  39
  40 struct route_entry
  41 {
  42   /* Link list. */
  43   struct route_entry *next;
  44   struct route_entry *prev;
  45
  46   /* Nexthop structure */
  47   struct nexthop *nexthop;
  48
  49   /* Refrence count. */
  50   unsigned long refcnt;
  51
  52   /* Tag */
  53   route_tag_t tag;
  54
  55   /* Uptime. */
  56   time_t uptime;
  57
  58   /* Type fo this route. */
  59   int type;
  60
  61   /* Source protocol instance */
  62   u_short instance;
  63
  64   /* VRF identifier. */
  65   vrf_id_t vrf_id;
  66
  67   /* Which routing table */
  68   uint32_t table;
  69
  70   /* Metric */
  71   u_int32_t metric;
  72
  73   /* MTU */
  74   u_int32_t mtu;
  75   u_int32_t nexthop_mtu;
  76
  77   /* Distance. */
  78   u_char distance;
  79
  80   /* Flags of this route.
  81    * This flag's definition is in lib/zebra.h ZEBRA_FLAG_* and is exposed
  82    * to clients via Zserv
  83    */
  84   u_int32_t flags;
  85
  86   /* RIB internal status */
  87   u_char status;
  88 #define ROUTE_ENTRY_REMOVED          0x1
  89   /* to simplify NHT logic when NHs change, instead of doing a NH by NH cmp */
  90 #define ROUTE_ENTRY_NEXTHOPS_CHANGED 0x2
  91 #define ROUTE_ENTRY_CHANGED          0x4
  92 #define ROUTE_ENTRY_SELECTED_FIB     0x8
  93
  94   /* Nexthop information. */
  95   u_char nexthop_num;
  96   u_char nexthop_active_num;
  97 };
  98
  99 /* meta-queue structure:
 100  * sub-queue 0: connected, kernel
 101  * sub-queue 1: static
 102  * sub-queue 2: RIP, RIPng, OSPF, OSPF6, IS-IS, EIGRP, NHRP
 103  * sub-queue 3: iBGP, eBGP
 104  * sub-queue 4: any other origin (if any)
 105  */
 106 #define MQ_SIZE 5
 107 struct meta_queue
 108 {
 109   struct list *subq[MQ_SIZE];
 110   u_int32_t size; /* sum of lengths of all subqueues */
 111 };
 112
 113 /*
 114  * Structure that represents a single destination (prefix).
 115  */
 116 typedef struct rib_dest_t_
 117 {
 118
 119   /*
 120    * Back pointer to the route node for this destination. This helps
 121    * us get to the prefix that this structure is for.
 122    */
 123   struct route_node *rnode;
 124
 125   /*
 126    * Doubly-linked list of routes for this prefix.
 127    */
 128   struct route_entry *routes;
 129
 130   /*
 131    * Flags, see below.
 132    */
 133   u_int32_t flags;
 134
 135   /*
 136    * Linkage to put dest on the FPM processing queue.
 137    */
 138   TAILQ_ENTRY(rib_dest_t_) fpm_q_entries;
 139
 140 } rib_dest_t;
 141
 142 #define RIB_ROUTE_QUEUED(x)     (1 << (x))
 143
 144 /*
 145  * The maximum qindex that can be used.
 146  */
 147 #define ZEBRA_MAX_QINDEX        (MQ_SIZE - 1)
 148
 149 /*
 150  * This flag indicates that a given prefix has been 'advertised' to
 151  * the FPM to be installed in the forwarding plane.
 152  */
 153 #define RIB_DEST_SENT_TO_FPM   (1 << (ZEBRA_MAX_QINDEX + 1))
 154
 155 /*
 156  * This flag is set when we need to send an update to the FPM about a
 157  * dest.
 158  */
 159 #define RIB_DEST_UPDATE_FPM    (1 << (ZEBRA_MAX_QINDEX + 2))
 160
 161 /*
 162  * Macro to iterate over each route for a destination (prefix).
 163  */
 164 #define RE_DEST_FOREACH_ROUTE(dest, re)                         \
 165   for ((re) = (dest) ? (dest)->routes : NULL; (re); (re) = (re)->next)
 166
 167 /*
 168  * Same as above, but allows the current node to be unlinked.
 169  */
 170 #define RE_DEST_FOREACH_ROUTE_SAFE(dest, re, next)      \
 171   for ((re) = (dest) ? (dest)->routes : NULL;           \
 172        (re) && ((next) = (re)->next, 1);                \
 173        (re) = (next))
 174
 175 #define RNODE_FOREACH_RE(rn, re)                                \
 176   RE_DEST_FOREACH_ROUTE (rib_dest_from_rnode (rn), re)
 177
 178 #define RNODE_FOREACH_RE_SAFE(rn, re, next)                             \
 179   RE_DEST_FOREACH_ROUTE_SAFE (rib_dest_from_rnode (rn), re, next)
 180
 181 /* The following for loop allows to iterate over the nexthop
 182  * structure of routes.
 183  *
 184  * We have to maintain quite a bit of state:
 185  *
 186  * nexthop:   The pointer to the current nexthop, either in the
 187  *            top-level chain or in the resolved chain of ni.
 188  * tnexthop:  The pointer to the current nexthop in the top-level
 189  *            nexthop chain.
 190  * recursing: Information if nh currently is in the top-level chain
 191  *            (0) or in a resolved chain (1).
 192  *
 193  * Initialization: Set `nexthop' and `tnexthop' to the head of the
 194  * top-level chain. As nexthop is in the top level chain, set recursing
 195  * to 0.
 196  *
 197  * Iteration check: Check that the `nexthop' pointer is not NULL.
 198  *
 199  * Iteration step: This is the tricky part. Check if `nexthop' has
 200  * NEXTHOP_FLAG_RECURSIVE set. If yes, this implies that `nexthop' is in
 201  * the top level chain and has at least one nexthop attached to
 202  * `nexthop->resolved'. As we want to descend into `nexthop->resolved',
 203  * set `recursing' to 1 and set `nexthop' to `nexthop->resolved'.
 204  * `tnexthop' is left alone in that case so we can remember which nexthop
 205  * in the top level chain we are currently handling.
 206  *
 207  * If NEXTHOP_FLAG_RECURSIVE is not set, `nexthop' will progress in its
 208  * current chain. If we are recursing, `nexthop' will be set to
 209  * `nexthop->next' and `tnexthop' will be left alone. If we are not
 210  * recursing, both `tnexthop' and `nexthop' will be set to `nexthop->next'
 211  * as we are progressing in the top level chain.
 212  *   If we encounter `nexthop->next == NULL', we will clear the `recursing'
 213  * flag as we arived either at the end of the resolved chain or at the end
 214  * of the top level chain. In both cases, we set `tnexthop' and `nexthop'
 215  * to `tnexthop->next', progressing to the next position in the top-level
 216  * chain and possibly to its end marked by NULL.
 217  */
 218 #define ALL_NEXTHOPS_RO(head, nexthop, tnexthop, recursing) \
 219   (tnexthop) = (nexthop) = (head), (recursing) = 0; \
 220   (nexthop); \
 221   (nexthop) = CHECK_FLAG((nexthop)->flags, NEXTHOP_FLAG_RECURSIVE) \
 222     ? (((recursing) = 1), (nexthop)->resolved) \
 223     : ((nexthop)->next ? ((recursing) ? (nexthop)->next \
 224                                       : ((tnexthop) = (nexthop)->next)) \
 225                        : (((recursing) = 0),((tnexthop) = (tnexthop)->next)))
 226
 227 #if defined (HAVE_RTADV)
 228 /* Structure which hold status of router advertisement. */
 229 struct rtadv
 230 {
 231   int sock;
 232
 233   int adv_if_count;
 234   int adv_msec_if_count;
 235
 236   struct thread *ra_read;
 237   struct thread *ra_timer;
 238 };
 239 #endif /* HAVE_RTADV */
 240
 241 /*
 242  * rib_table_info_t
 243  *
 244  * Structure that is hung off of a route_table that holds information about
 245  * the table.
 246  */
 247 typedef struct rib_table_info_t_
 248 {
 249
 250   /*
 251    * Back pointer to zebra_vrf.
 252    */
 253   struct zebra_vrf *zvrf;
 254   afi_t afi;
 255   safi_t safi;
 256
 257 } rib_table_info_t;
 258
 259 typedef enum
 260 {
 261   RIB_TABLES_ITER_S_INIT,
 262   RIB_TABLES_ITER_S_ITERATING,
 263   RIB_TABLES_ITER_S_DONE
 264 } rib_tables_iter_state_t;
 265
 266 /*
 267  * Structure that holds state for iterating over all tables in the
 268  * Routing Information Base.
 269  */
 270 typedef struct rib_tables_iter_t_
 271 {
 272   vrf_id_t vrf_id;
 273   int afi_safi_ix;
 274
 275   rib_tables_iter_state_t state;
 276 } rib_tables_iter_t;
 277
 278 /* Events/reasons triggering a RIB update. */
 279 typedef enum
 280 {
 281   RIB_UPDATE_IF_CHANGE,
 282   RIB_UPDATE_RMAP_CHANGE,
 283   RIB_UPDATE_OTHER
 284 } rib_update_event_t;
 285
 286 extern struct nexthop *route_entry_nexthop_ifindex_add (struct route_entry *, ifindex_t);
 287 extern struct nexthop *route_entry_nexthop_blackhole_add (struct route_entry *);
 288 extern struct nexthop *route_entry_nexthop_ipv4_add (struct route_entry *,
 289                                                      struct in_addr *,
 290                                                      struct in_addr *);
 291 extern struct nexthop *route_entry_nexthop_ipv4_ifindex_add (struct route_entry *,
 292                                                              struct in_addr *,
 293                                                              struct in_addr *,
 294                                                              ifindex_t);
 295 extern void route_entry_nexthop_delete (struct route_entry *re, struct nexthop *nexthop);
 296 extern struct nexthop *route_entry_nexthop_ipv6_add (struct route_entry *,
 297                                                      struct in6_addr *);
 298 extern struct nexthop *route_entry_nexthop_ipv6_ifindex_add (struct route_entry *re,
 299                                                              struct in6_addr *ipv6,
 300                                                              ifindex_t ifindex);
 301 extern void route_entry_nexthop_add (struct route_entry *re, struct nexthop *nexthop);
 302 extern void route_entry_copy_nexthops (struct route_entry *re, struct nexthop *nh);
 303
 304 #define route_entry_dump(prefix, src, re) _route_entry_dump(__func__, prefix, src, re)
 305 extern void _route_entry_dump (const char *,
 306                                union prefixconstptr,
 307                                union prefixconstptr, const struct route_entry *);
 308 /* RPF lookup behaviour */
 309 enum multicast_mode
 310 {
 311   MCAST_NO_CONFIG = 0,  /* MIX_MRIB_FIRST, but no show in config write */
 312   MCAST_MRIB_ONLY,      /* MRIB only */
 313   MCAST_URIB_ONLY,      /* URIB only */
 314   MCAST_MIX_MRIB_FIRST, /* MRIB, if nothing at all then URIB */
 315   MCAST_MIX_DISTANCE,   /* MRIB & URIB, lower distance wins */
 316   MCAST_MIX_PFXLEN,     /* MRIB & URIB, longer prefix wins */
 317                         /* on equal value, MRIB wins for last 2 */
 318 };
 319
 320 extern void multicast_mode_ipv4_set (enum multicast_mode mode);
 321 extern enum multicast_mode multicast_mode_ipv4_get (void);
 322
 323 extern void rib_lookup_and_dump (struct prefix_ipv4 *, vrf_id_t);
 324 extern void rib_lookup_and_pushup (struct prefix_ipv4 *, vrf_id_t);
 325
 326 extern int rib_lookup_ipv4_route (struct prefix_ipv4 *, union sockunion *,
 327                                   vrf_id_t);
 328 #define ZEBRA_RIB_LOOKUP_ERROR -1
 329 #define ZEBRA_RIB_FOUND_EXACT 0
 330 #define ZEBRA_RIB_FOUND_NOGATE 1
 331 #define ZEBRA_RIB_FOUND_CONNECTED 2
 332 #define ZEBRA_RIB_NOTFOUND 3
 333
 334
 335
 336 extern int is_zebra_valid_kernel_table(u_int32_t table_id);
 337 extern int is_zebra_main_routing_table(u_int32_t table_id);
 338 extern int zebra_check_addr (struct prefix *p);
 339
 340 extern void rib_addnode (struct route_node *rn, struct route_entry *re, int process);
 341 extern void rib_delnode (struct route_node *rn, struct route_entry *re);
 342 extern int rib_install_kernel (struct route_node *rn, struct route_entry *re, struct route_entry *old);
 343 extern int rib_uninstall_kernel (struct route_node *rn, struct route_entry *re);
 344
 345 /* NOTE:
 346  * All rib_add function will not just add prefix into RIB, but
 347  * also implicitly withdraw equal prefix of same type. */
 348 extern int rib_add (afi_t afi, safi_t safi, vrf_id_t vrf_id, int type,
 349                     u_short instance, int flags, struct prefix *p,
 350                     struct prefix_ipv6 *src_p, union g_addr *gate, union g_addr *src,
 351                     ifindex_t ifindex, u_int32_t table_id,
 352                     u_int32_t, u_int32_t, u_char);
 353
 354 extern int rib_add_multipath (afi_t afi, safi_t safi, struct prefix *,
 355                               struct prefix_ipv6 *src_p, struct route_entry *);
 356
 357 extern void rib_delete (afi_t afi, safi_t safi, vrf_id_t vrf_id, int type,
 358                         u_short instance, int flags, struct prefix *p,
 359                         struct prefix_ipv6 *src_p, union g_addr *gate,
 360                         ifindex_t ifindex, u_int32_t table_id);
 361
 362 extern struct route_entry *rib_match (afi_t afi, safi_t safi, vrf_id_t, union g_addr *,
 363                               struct route_node **rn_out);
 364 extern struct route_entry *rib_match_ipv4_multicast (vrf_id_t vrf_id, struct in_addr addr,
 365                                              struct route_node **rn_out);
 366
 367 extern struct route_entry *rib_lookup_ipv4 (struct prefix_ipv4 *, vrf_id_t);
 368
 369 extern void rib_update (vrf_id_t, rib_update_event_t);
 370 extern void rib_weed_tables (void);
 371 extern void rib_sweep_route (void);
 372 extern void rib_close_table (struct route_table *);
 373 extern void rib_init (void);
 374 extern unsigned long rib_score_proto (u_char proto, u_short instance);
 375 extern void rib_queue_add (struct route_node *rn);
 376 extern void meta_queue_free (struct meta_queue *mq);
 377 extern int zebra_rib_labeled_unicast (struct route_entry *re);
 378 extern struct route_table *rib_table_ipv6;
 379
 380 extern void rib_unlink (struct route_node *, struct route_entry *);
 381 extern int rib_gc_dest (struct route_node *rn);
 382 extern struct route_table *rib_tables_iter_next (rib_tables_iter_t *iter);
 383
 384 extern u_char route_distance(int type);
 385
 386 /*
 387  * Inline functions.
 388  */
 389
 390 /*
 391  * rib_table_info
 392  */
 393 static inline rib_table_info_t *
 394 rib_table_info (struct route_table *table)
 395 {
 396   return (rib_table_info_t *) table->info;
 397 }
 398
 399 /*
 400  * rib_dest_from_rnode
 401  */
 402 static inline rib_dest_t *
 403 rib_dest_from_rnode (struct route_node *rn)
 404 {
 405   return (rib_dest_t *) rn->info;
 406 }
 407
 408 /*
 409  * rnode_to_ribs
 410  *
 411  * Returns a pointer to the list of routes corresponding to the given
 412  * route_node.
 413  */
 414 static inline struct route_entry *
 415 rnode_to_ribs (struct route_node *rn)
 416 {
 417   rib_dest_t *dest;
 418
 419   dest = rib_dest_from_rnode (rn);
 420   if (!dest)
 421     return NULL;
 422
 423   return dest->routes;
 424 }
 425
 426 /*
 427  * rib_dest_prefix
 428  */
 429 static inline struct prefix *
 430 rib_dest_prefix (rib_dest_t *dest)
 431 {
 432   return &dest->rnode->p;
 433 }
 434
 435 /*
 436  * rib_dest_af
 437  *
 438  * Returns the address family that the destination is for.
 439  */
 440 static inline u_char
 441 rib_dest_af (rib_dest_t *dest)
 442 {
 443   return dest->rnode->p.family;
 444 }
 445
 446 /*
 447  * rib_dest_table
 448  */
 449 static inline struct route_table *
 450 rib_dest_table (rib_dest_t *dest)
 451 {
 452   return srcdest_rnode_table(dest->rnode);
 453 }
 454
 455 /*
 456  * rib_dest_vrf
 457  */
 458 static inline struct zebra_vrf *
 459 rib_dest_vrf (rib_dest_t *dest)
 460 {
 461   return rib_table_info (rib_dest_table (dest))->zvrf;
 462 }
 463
 464 /*
 465  * rib_tables_iter_init
 466  */
 467 static inline void
 468 rib_tables_iter_init (rib_tables_iter_t *iter)
 469
 470 {
 471   memset (iter, 0, sizeof (*iter));
 472   iter->state = RIB_TABLES_ITER_S_INIT;
 473 }
 474
 475 /*
 476  * rib_tables_iter_started
 477  *
 478  * Returns TRUE if this iterator has started iterating over the set of
 479  * tables.
 480  */
 481 static inline int
 482 rib_tables_iter_started (rib_tables_iter_t *iter)
 483 {
 484   return iter->state != RIB_TABLES_ITER_S_INIT;
 485 }
 486
 487 /*
 488  * rib_tables_iter_cleanup
 489  */
 490 static inline void
 491 rib_tables_iter_cleanup (rib_tables_iter_t *iter)
 492 {
 493   iter->state = RIB_TABLES_ITER_S_DONE;
 494 }
 495
 496 DECLARE_HOOK(rib_update, (struct route_node *rn, const char *reason), (rn, reason))
 497
 498 #endif /*_ZEBRA_RIB_H */