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 rib
  41 {
  42   /* Link list. */
  43   struct rib *next;
  44   struct rib *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 RIB_ENTRY_REMOVED          0x1
  89   /* to simplify NHT logic when NHs change, instead of doing a NH by NH cmp */
  90 #define RIB_ENTRY_NEXTHOPS_CHANGED 0x2
  91 #define RIB_ENTRY_CHANGED          0x4
  92 #define RIB_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
 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 rib *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 RIB_DEST_FOREACH_ROUTE(dest, rib)                               \
 165   for ((rib) = (dest) ? (dest)->routes : NULL; (rib); (rib) = (rib)->next)
 166
 167 /*
 168  * Same as above, but allows the current node to be unlinked.
 169  */
 170 #define RIB_DEST_FOREACH_ROUTE_SAFE(dest, rib, next)    \
 171   for ((rib) = (dest) ? (dest)->routes : NULL;          \
 172        (rib) && ((next) = (rib)->next, 1);              \
 173        (rib) = (next))
 174
 175 #define RNODE_FOREACH_RIB(rn, rib)                              \
 176   RIB_DEST_FOREACH_ROUTE (rib_dest_from_rnode (rn), rib)
 177
 178 #define RNODE_FOREACH_RIB_SAFE(rn, rib, next)                           \
 179   RIB_DEST_FOREACH_ROUTE_SAFE (rib_dest_from_rnode (rn), rib, 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 *rib_nexthop_ifindex_add (struct rib *, ifindex_t);
 287 extern struct nexthop *rib_nexthop_blackhole_add (struct rib *);
 288 extern struct nexthop *rib_nexthop_ipv4_add (struct rib *, struct in_addr *,
 289                                              struct in_addr *);
 290 extern struct nexthop *rib_nexthop_ipv4_ifindex_add (struct rib *,
 291                                                      struct in_addr *,
 292                                                      struct in_addr *,
 293                                                      ifindex_t);
 294 extern void rib_nexthop_add (struct rib *rib, struct nexthop *nexthop);
 295 extern void rib_copy_nexthops (struct rib *rib, struct nexthop *nh);
 296
 297 /* RPF lookup behaviour */
 298 enum multicast_mode
 299 {
 300   MCAST_NO_CONFIG = 0,  /* MIX_MRIB_FIRST, but no show in config write */
 301   MCAST_MRIB_ONLY,      /* MRIB only */
 302   MCAST_URIB_ONLY,      /* URIB only */
 303   MCAST_MIX_MRIB_FIRST, /* MRIB, if nothing at all then URIB */
 304   MCAST_MIX_DISTANCE,   /* MRIB & URIB, lower distance wins */
 305   MCAST_MIX_PFXLEN,     /* MRIB & URIB, longer prefix wins */
 306                         /* on equal value, MRIB wins for last 2 */
 307 };
 308
 309 extern void multicast_mode_ipv4_set (enum multicast_mode mode);
 310 extern enum multicast_mode multicast_mode_ipv4_get (void);
 311
 312 extern int nexthop_has_fib_child(struct nexthop *);
 313 extern void rib_lookup_and_dump (struct prefix_ipv4 *, vrf_id_t);
 314 extern void rib_lookup_and_pushup (struct prefix_ipv4 *, vrf_id_t);
 315 #define rib_dump(prefix, src, rib) _rib_dump(__func__, prefix, src, rib)
 316 extern void _rib_dump (const char *,
 317                        union prefixconstptr,
 318                        union prefixconstptr, const struct rib *);
 319 extern int rib_lookup_ipv4_route (struct prefix_ipv4 *, union sockunion *,
 320                                   vrf_id_t);
 321 #define ZEBRA_RIB_LOOKUP_ERROR -1
 322 #define ZEBRA_RIB_FOUND_EXACT 0
 323 #define ZEBRA_RIB_FOUND_NOGATE 1
 324 #define ZEBRA_RIB_FOUND_CONNECTED 2
 325 #define ZEBRA_RIB_NOTFOUND 3
 326
 327 extern void rib_nexthop_delete (struct rib *rib, struct nexthop *nexthop);
 328 extern struct nexthop *rib_nexthop_ipv6_add (struct rib *, struct in6_addr *);
 329 extern struct nexthop *rib_nexthop_ipv6_ifindex_add (struct rib *rib,
 330                                                      struct in6_addr *ipv6,
 331                                                      ifindex_t ifindex);
 332
 333 extern int is_zebra_valid_kernel_table(u_int32_t table_id);
 334 extern int is_zebra_main_routing_table(u_int32_t table_id);
 335 extern int zebra_check_addr (struct prefix *p);
 336
 337 extern void rib_addnode (struct route_node *rn, struct rib *rib, int process);
 338 extern void rib_delnode (struct route_node *rn, struct rib *rib);
 339 extern int rib_install_kernel (struct route_node *rn, struct rib *rib, struct rib *old);
 340 extern int rib_uninstall_kernel (struct route_node *rn, struct rib *rib);
 341
 342 /* NOTE:
 343  * All rib_add function will not just add prefix into RIB, but
 344  * also implicitly withdraw equal prefix of same type. */
 345 extern int rib_add (afi_t afi, safi_t safi, vrf_id_t vrf_id, int type,
 346                     u_short instance, int flags, struct prefix *p,
 347                     struct prefix_ipv6 *src_p, union g_addr *gate, union g_addr *src,
 348                     ifindex_t ifindex, u_int32_t table_id,
 349                     u_int32_t, u_int32_t, u_char);
 350
 351 extern int rib_add_multipath (afi_t afi, safi_t safi, struct prefix *,
 352                               struct prefix_ipv6 *src_p, struct rib *);
 353
 354 extern void rib_delete (afi_t afi, safi_t safi, vrf_id_t vrf_id, int type,
 355                         u_short instance, int flags, struct prefix *p,
 356                         struct prefix_ipv6 *src_p, union g_addr *gate,
 357                         ifindex_t ifindex, u_int32_t table_id);
 358
 359 extern struct rib *rib_match (afi_t afi, safi_t safi, vrf_id_t, union g_addr *,
 360                               struct route_node **rn_out);
 361 extern struct rib *rib_match_ipv4_multicast (vrf_id_t vrf_id, struct in_addr addr,
 362                                              struct route_node **rn_out);
 363
 364 extern struct rib *rib_lookup_ipv4 (struct prefix_ipv4 *, vrf_id_t);
 365
 366 extern void rib_update (vrf_id_t, rib_update_event_t);
 367 extern void rib_weed_tables (void);
 368 extern void rib_sweep_route (void);
 369 extern void rib_close_table (struct route_table *);
 370 extern void rib_init (void);
 371 extern unsigned long rib_score_proto (u_char proto, u_short instance);
 372 extern void rib_queue_add (struct route_node *rn);
 373 extern void meta_queue_free (struct meta_queue *mq);
 374 extern int zebra_rib_labeled_unicast (struct rib *rib);
 375 extern struct route_table *rib_table_ipv6;
 376
 377 extern void rib_unlink (struct route_node *, struct rib *);
 378 extern int rib_gc_dest (struct route_node *rn);
 379 extern struct route_table *rib_tables_iter_next (rib_tables_iter_t *iter);
 380
 381 extern u_char route_distance(int type);
 382
 383 /*
 384  * Inline functions.
 385  */
 386
 387 /*
 388  * rib_table_info
 389  */
 390 static inline rib_table_info_t *
 391 rib_table_info (struct route_table *table)
 392 {
 393   return (rib_table_info_t *) table->info;
 394 }
 395
 396 /*
 397  * rib_dest_from_rnode
 398  */
 399 static inline rib_dest_t *
 400 rib_dest_from_rnode (struct route_node *rn)
 401 {
 402   return (rib_dest_t *) rn->info;
 403 }
 404
 405 /*
 406  * rnode_to_ribs
 407  *
 408  * Returns a pointer to the list of routes corresponding to the given
 409  * route_node.
 410  */
 411 static inline struct rib *
 412 rnode_to_ribs (struct route_node *rn)
 413 {
 414   rib_dest_t *dest;
 415
 416   dest = rib_dest_from_rnode (rn);
 417   if (!dest)
 418     return NULL;
 419
 420   return dest->routes;
 421 }
 422
 423 /*
 424  * rib_dest_prefix
 425  */
 426 static inline struct prefix *
 427 rib_dest_prefix (rib_dest_t *dest)
 428 {
 429   return &dest->rnode->p;
 430 }
 431
 432 /*
 433  * rib_dest_af
 434  *
 435  * Returns the address family that the destination is for.
 436  */
 437 static inline u_char
 438 rib_dest_af (rib_dest_t *dest)
 439 {
 440   return dest->rnode->p.family;
 441 }
 442
 443 /*
 444  * rib_dest_table
 445  */
 446 static inline struct route_table *
 447 rib_dest_table (rib_dest_t *dest)
 448 {
 449   return srcdest_rnode_table(dest->rnode);
 450 }
 451
 452 /*
 453  * rib_dest_vrf
 454  */
 455 static inline struct zebra_vrf *
 456 rib_dest_vrf (rib_dest_t *dest)
 457 {
 458   return rib_table_info (rib_dest_table (dest))->zvrf;
 459 }
 460
 461 /*
 462  * rib_tables_iter_init
 463  */
 464 static inline void
 465 rib_tables_iter_init (rib_tables_iter_t *iter)
 466
 467 {
 468   memset (iter, 0, sizeof (*iter));
 469   iter->state = RIB_TABLES_ITER_S_INIT;
 470 }
 471
 472 /*
 473  * rib_tables_iter_started
 474  *
 475  * Returns TRUE if this iterator has started iterating over the set of
 476  * tables.
 477  */
 478 static inline int
 479 rib_tables_iter_started (rib_tables_iter_t *iter)
 480 {
 481   return iter->state != RIB_TABLES_ITER_S_INIT;
 482 }
 483
 484 /*
 485  * rib_tables_iter_cleanup
 486  */
 487 static inline void
 488 rib_tables_iter_cleanup (rib_tables_iter_t *iter)
 489 {
 490   iter->state = RIB_TABLES_ITER_S_DONE;
 491 }
 492
 493 DECLARE_HOOK(rib_update, (struct route_node *rn, const char *reason), (rn, reason))
 494
 495 #endif /*_ZEBRA_RIB_H */