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