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 "prefix.h"
  27 #include "table.h"
  28 #include "queue.h"
  29 #include "nexthop.h"
  30
  31 #define DISTANCE_INFINITY  255
  32
  33 struct rib
  34 {
  35   /* Link list. */
  36   struct rib *next;
  37   struct rib *prev;
  38
  39   /* Nexthop structure */
  40   struct nexthop *nexthop;
  41
  42   /* Refrence count. */
  43   unsigned long refcnt;
  44
  45   /* Uptime. */
  46   time_t uptime;
  47
  48   /* Type fo this route. */
  49   int type;
  50
  51   /* Which routing table */
  52   int table;
  53
  54   /* Metric */
  55   u_int32_t metric;
  56
  57   /* Distance. */
  58   u_char distance;
  59
  60   /* Flags of this route.
  61    * This flag's definition is in lib/zebra.h ZEBRA_FLAG_* and is exposed
  62    * to clients via Zserv
  63    */
  64   u_char flags;
  65
  66   /* RIB internal status */
  67   u_char status;
  68 #define RIB_ENTRY_REMOVED       (1 << 0)
  69
  70   /* Nexthop information. */
  71   u_char nexthop_num;
  72   u_char nexthop_active_num;
  73   u_char nexthop_fib_num;
  74 };
  75
  76 /* meta-queue structure:
  77  * sub-queue 0: connected, kernel
  78  * sub-queue 1: static
  79  * sub-queue 2: RIP, RIPng, OSPF, OSPF6, IS-IS
  80  * sub-queue 3: iBGP, eBGP
  81  * sub-queue 4: any other origin (if any)
  82  */
  83 #define MQ_SIZE 5
  84 struct meta_queue
  85 {
  86   struct list *subq[MQ_SIZE];
  87   u_int32_t size; /* sum of lengths of all subqueues */
  88 };
  89
  90 /*
  91  * Structure that represents a single destination (prefix).
  92  */
  93 typedef struct rib_dest_t_
  94 {
  95
  96   /*
  97    * Back pointer to the route node for this destination. This helps
  98    * us get to the prefix that this structure is for.
  99    */
 100   struct route_node *rnode;
 101
 102   /*
 103    * Doubly-linked list of routes for this prefix.
 104    */
 105   struct rib *routes;
 106
 107   /*
 108    * Flags, see below.
 109    */
 110   u_int32_t flags;
 111
 112   /*
 113    * Linkage to put dest on the FPM processing queue.
 114    */
 115   TAILQ_ENTRY(rib_dest_t_) fpm_q_entries;
 116
 117 } rib_dest_t;
 118
 119 #define RIB_ROUTE_QUEUED(x)     (1 << (x))
 120
 121 /*
 122  * The maximum qindex that can be used.
 123  */
 124 #define ZEBRA_MAX_QINDEX        (MQ_SIZE - 1)
 125
 126 /*
 127  * This flag indicates that a given prefix has been 'advertised' to
 128  * the FPM to be installed in the forwarding plane.
 129  */
 130 #define RIB_DEST_SENT_TO_FPM   (1 << (ZEBRA_MAX_QINDEX + 1))
 131
 132 /*
 133  * This flag is set when we need to send an update to the FPM about a
 134  * dest.
 135  */
 136 #define RIB_DEST_UPDATE_FPM    (1 << (ZEBRA_MAX_QINDEX + 2))
 137
 138 /*
 139  * Macro to iterate over each route for a destination (prefix).
 140  */
 141 #define RIB_DEST_FOREACH_ROUTE(dest, rib)                               \
 142   for ((rib) = (dest) ? (dest)->routes : NULL; (rib); (rib) = (rib)->next)
 143
 144 /*
 145  * Same as above, but allows the current node to be unlinked.
 146  */
 147 #define RIB_DEST_FOREACH_ROUTE_SAFE(dest, rib, next)    \
 148   for ((rib) = (dest) ? (dest)->routes : NULL;          \
 149        (rib) && ((next) = (rib)->next, 1);              \
 150        (rib) = (next))
 151
 152 #define RNODE_FOREACH_RIB(rn, rib)                              \
 153   RIB_DEST_FOREACH_ROUTE (rib_dest_from_rnode (rn), rib)
 154
 155 #define RNODE_FOREACH_RIB_SAFE(rn, rib, next)                           \
 156   RIB_DEST_FOREACH_ROUTE_SAFE (rib_dest_from_rnode (rn), rib, next)
 157
 158 /* Static route information. */
 159 struct static_ipv4
 160 {
 161   /* For linked list. */
 162   struct static_ipv4 *prev;
 163   struct static_ipv4 *next;
 164
 165   /* Administrative distance. */
 166   u_char distance;
 167
 168   /* Flag for this static route's type. */
 169   u_char type;
 170 #define STATIC_IPV4_GATEWAY     1
 171 #define STATIC_IPV4_IFNAME      2
 172 #define STATIC_IPV4_BLACKHOLE   3
 173
 174   /* Nexthop value. */
 175   union
 176   {
 177     struct in_addr ipv4;
 178     char *ifname;
 179   } gate;
 180
 181   /* bit flags */
 182   u_char flags;
 183 /*
 184  see ZEBRA_FLAG_REJECT
 185      ZEBRA_FLAG_BLACKHOLE
 186  */
 187 };
 188
 189 #ifdef HAVE_IPV6
 190 /* Static route information. */
 191 struct static_ipv6
 192 {
 193   /* For linked list. */
 194   struct static_ipv6 *prev;
 195   struct static_ipv6 *next;
 196
 197   /* Administrative distance. */
 198   u_char distance;
 199
 200   /* Flag for this static route's type. */
 201   u_char type;
 202 #define STATIC_IPV6_GATEWAY          1
 203 #define STATIC_IPV6_GATEWAY_IFNAME   2
 204 #define STATIC_IPV6_IFNAME           3
 205
 206   /* Nexthop value. */
 207   struct in6_addr ipv6;
 208   char *ifname;
 209
 210   /* bit flags */
 211   u_char flags;
 212 /*
 213  see ZEBRA_FLAG_REJECT
 214      ZEBRA_FLAG_BLACKHOLE
 215  */
 216 };
 217 #endif /* HAVE_IPV6 */
 218
 219 /* The following for loop allows to iterate over the nexthop
 220  * structure of routes.
 221  *
 222  * We have to maintain quite a bit of state:
 223  *
 224  * nexthop:   The pointer to the current nexthop, either in the
 225  *            top-level chain or in the resolved chain of ni.
 226  * tnexthop:  The pointer to the current nexthop in the top-level
 227  *            nexthop chain.
 228  * recursing: Information if nh currently is in the top-level chain
 229  *            (0) or in a resolved chain (1).
 230  *
 231  * Initialization: Set `nexthop' and `tnexthop' to the head of the
 232  * top-level chain. As nexthop is in the top level chain, set recursing
 233  * to 0.
 234  *
 235  * Iteration check: Check that the `nexthop' pointer is not NULL.
 236  *
 237  * Iteration step: This is the tricky part. Check if `nexthop' has
 238  * NEXTHOP_FLAG_RECURSIVE set. If yes, this implies that `nexthop' is in
 239  * the top level chain and has at least one nexthop attached to
 240  * `nexthop->resolved'. As we want to descend into `nexthop->resolved',
 241  * set `recursing' to 1 and set `nexthop' to `nexthop->resolved'.
 242  * `tnexthop' is left alone in that case so we can remember which nexthop
 243  * in the top level chain we are currently handling.
 244  *
 245  * If NEXTHOP_FLAG_RECURSIVE is not set, `nexthop' will progress in its
 246  * current chain. If we are recursing, `nexthop' will be set to
 247  * `nexthop->next' and `tnexthop' will be left alone. If we are not
 248  * recursing, both `tnexthop' and `nexthop' will be set to `nexthop->next'
 249  * as we are progressing in the top level chain.
 250  *   If we encounter `nexthop->next == NULL', we will clear the `recursing'
 251  * flag as we arived either at the end of the resolved chain or at the end
 252  * of the top level chain. In both cases, we set `tnexthop' and `nexthop'
 253  * to `tnexthop->next', progressing to the next position in the top-level
 254  * chain and possibly to its end marked by NULL.
 255  */
 256 #define ALL_NEXTHOPS_RO(head, nexthop, tnexthop, recursing) \
 257   (tnexthop) = (nexthop) = (head), (recursing) = 0; \
 258   (nexthop); \
 259   (nexthop) = CHECK_FLAG((nexthop)->flags, NEXTHOP_FLAG_RECURSIVE) \
 260     ? (((recursing) = 1), (nexthop)->resolved) \
 261     : ((nexthop)->next ? ((recursing) ? (nexthop)->next \
 262                                       : ((tnexthop) = (nexthop)->next)) \
 263                        : (((recursing) = 0),((tnexthop) = (tnexthop)->next)))
 264
 265 /* Routing table instance.  */
 266 struct vrf
 267 {
 268   /* Identifier.  This is same as routing table vector index.  */
 269   u_int32_t id;
 270
 271   /* Routing table name.  */
 272   char *name;
 273
 274   /* Description.  */
 275   char *desc;
 276
 277   /* FIB identifier.  */
 278   u_char fib_id;
 279
 280   /* Routing table.  */
 281   struct route_table *table[AFI_MAX][SAFI_MAX];
 282
 283   /* Static route configuration.  */
 284   struct route_table *stable[AFI_MAX][SAFI_MAX];
 285
 286   /* Recursive Nexthop table */
 287   struct route_table *rnh_table[AFI_MAX];
 288 };
 289
 290 /*
 291  * rib_table_info_t
 292  *
 293  * Structure that is hung off of a route_table that holds information about
 294  * the table.
 295  */
 296 typedef struct rib_table_info_t_
 297 {
 298
 299   /*
 300    * Back pointer to vrf.
 301    */
 302   struct vrf *vrf;
 303   afi_t afi;
 304   safi_t safi;
 305
 306 } rib_table_info_t;
 307
 308 typedef enum
 309 {
 310   RIB_TABLES_ITER_S_INIT,
 311   RIB_TABLES_ITER_S_ITERATING,
 312   RIB_TABLES_ITER_S_DONE
 313 } rib_tables_iter_state_t;
 314
 315 /*
 316  * Structure that holds state for iterating over all tables in the
 317  * Routing Information Base.
 318  */
 319 typedef struct rib_tables_iter_t_
 320 {
 321   uint32_t vrf_id;
 322   int afi_safi_ix;
 323
 324   rib_tables_iter_state_t state;
 325 } rib_tables_iter_t;
 326
 327 extern struct nexthop *nexthop_ifindex_add (struct rib *, unsigned int);
 328 extern struct nexthop *nexthop_ifname_add (struct rib *, char *);
 329 extern struct nexthop *nexthop_blackhole_add (struct rib *);
 330 extern struct nexthop *nexthop_ipv4_add (struct rib *, struct in_addr *,
 331                                          struct in_addr *);
 332 extern struct nexthop *nexthop_ipv4_ifindex_add (struct rib *,
 333                                                  struct in_addr *,
 334                                                  struct in_addr *,
 335                                                  unsigned int);
 336 extern void nexthop_free (struct nexthop *nexthop);
 337 extern void nexthops_free (struct nexthop *nexthop);
 338 extern void nexthop_add (struct rib *rib, struct nexthop *nexthop);
 339
 340 extern int nexthop_has_fib_child(struct nexthop *);
 341 extern void rib_lookup_and_dump (struct prefix_ipv4 *);
 342 extern void rib_lookup_and_pushup (struct prefix_ipv4 *);
 343 #define rib_dump(prefix ,rib) _rib_dump(__func__, prefix, rib)
 344 extern void _rib_dump (const char *,
 345                        union prefix46constptr, const struct rib *);
 346 extern int rib_lookup_ipv4_route (struct prefix_ipv4 *, union sockunion *);
 347 #define ZEBRA_RIB_LOOKUP_ERROR -1
 348 #define ZEBRA_RIB_FOUND_EXACT 0
 349 #define ZEBRA_RIB_FOUND_NOGATE 1
 350 #define ZEBRA_RIB_FOUND_CONNECTED 2
 351 #define ZEBRA_RIB_NOTFOUND 3
 352
 353 #ifdef HAVE_IPV6
 354 extern struct nexthop *nexthop_ipv6_add (struct rib *, struct in6_addr *);
 355 extern struct nexthop *nexthop_ipv6_ifindex_add (struct rib *rib,
 356                         struct in6_addr *ipv6, unsigned int ifindex);
 357 extern struct nexthop *nexthop_ipv6_ifname_add (struct rib *rib,
 358                                                 struct in6_addr *ipv6,
 359                                                 char *ifname);
 360 extern int
 361 rib_bogus_ipv6 (int type, struct prefix_ipv6 *p,
 362                 struct in6_addr *gate, unsigned int ifindex, int table);
 363 #endif /* HAVE_IPV6 */
 364
 365 extern struct vrf *vrf_lookup (u_int32_t);
 366 extern struct route_table *vrf_table (afi_t afi, safi_t safi, u_int32_t id);
 367 extern struct route_table *vrf_static_table (afi_t afi, safi_t safi, u_int32_t id);
 368
 369 /* NOTE:
 370  * All rib_add_ipv[46]* functions will not just add prefix into RIB, but
 371  * also implicitly withdraw equal prefix of same type. */
 372 extern int rib_add_ipv4 (int type, int flags, struct prefix_ipv4 *p,
 373                          struct in_addr *gate, struct in_addr *src,
 374                          unsigned int ifindex, u_int32_t vrf_id,
 375                          u_int32_t, u_char, safi_t);
 376
 377 extern int rib_add_ipv4_multipath (struct prefix_ipv4 *, struct rib *, safi_t);
 378
 379 extern int rib_delete_ipv4 (int type, int flags, struct prefix_ipv4 *p,
 380                             struct in_addr *gate, unsigned int ifindex,
 381                             u_int32_t, safi_t safi);
 382
 383 extern struct rib *rib_match_ipv4 (struct in_addr);
 384
 385 extern struct rib *rib_lookup_ipv4 (struct prefix_ipv4 *);
 386
 387 extern void rib_update (void);
 388 extern void rib_weed_tables (void);
 389 extern void rib_sweep_route (void);
 390 extern void rib_close (void);
 391 extern void rib_init (void);
 392 extern unsigned long rib_score_proto (u_char proto);
 393
 394 extern int
 395 static_add_ipv4 (struct prefix *p, struct in_addr *gate, const char *ifname,
 396        u_char flags, u_char distance, u_int32_t vrf_id);
 397
 398 extern int
 399 static_delete_ipv4 (struct prefix *p, struct in_addr *gate, const char *ifname,
 400                     u_char distance, u_int32_t vrf_id);
 401
 402 #ifdef HAVE_IPV6
 403 extern int
 404 rib_add_ipv6 (int type, int flags, struct prefix_ipv6 *p,
 405               struct in6_addr *gate, unsigned int ifindex, u_int32_t vrf_id,
 406               u_int32_t metric, u_char distance, safi_t safi);
 407
 408 extern int
 409 rib_delete_ipv6 (int type, int flags, struct prefix_ipv6 *p,
 410                  struct in6_addr *gate, unsigned int ifindex, u_int32_t vrf_id, safi_t safi);
 411
 412 extern struct rib *rib_lookup_ipv6 (struct in6_addr *);
 413
 414 extern struct rib *rib_match_ipv6 (struct in6_addr *);
 415
 416 extern struct route_table *rib_table_ipv6;
 417
 418 extern int
 419 static_add_ipv6 (struct prefix *p, u_char type, struct in6_addr *gate,
 420                  const char *ifname, u_char flags, u_char distance,
 421                  u_int32_t vrf_id);
 422
 423 extern int
 424 rib_add_ipv6_multipath (struct prefix_ipv6 *, struct rib *, safi_t,
 425                         unsigned long);
 426
 427 extern int
 428 static_delete_ipv6 (struct prefix *p, u_char type, struct in6_addr *gate,
 429                     const char *ifname, u_char distance, u_int32_t vrf_id);
 430
 431 #endif /* HAVE_IPV6 */
 432
 433 extern int rib_gc_dest (struct route_node *rn);
 434 extern struct route_table *rib_tables_iter_next (rib_tables_iter_t *iter);
 435
 436 /*
 437  * Inline functions.
 438  */
 439
 440 /*
 441  * rib_table_info
 442  */
 443 static inline rib_table_info_t *
 444 rib_table_info (struct route_table *table)
 445 {
 446   return (rib_table_info_t *) table->info;
 447 }
 448
 449 /*
 450  * rib_dest_from_rnode
 451  */
 452 static inline rib_dest_t *
 453 rib_dest_from_rnode (struct route_node *rn)
 454 {
 455   return (rib_dest_t *) rn->info;
 456 }
 457
 458 /*
 459  * rnode_to_ribs
 460  *
 461  * Returns a pointer to the list of routes corresponding to the given
 462  * route_node.
 463  */
 464 static inline struct rib *
 465 rnode_to_ribs (struct route_node *rn)
 466 {
 467   rib_dest_t *dest;
 468
 469   dest = rib_dest_from_rnode (rn);
 470   if (!dest)
 471     return NULL;
 472
 473   return dest->routes;
 474 }
 475
 476 /*
 477  * rib_dest_prefix
 478  */
 479 static inline struct prefix *
 480 rib_dest_prefix (rib_dest_t *dest)
 481 {
 482   return &dest->rnode->p;
 483 }
 484
 485 /*
 486  * rib_dest_af
 487  *
 488  * Returns the address family that the destination is for.
 489  */
 490 static inline u_char
 491 rib_dest_af (rib_dest_t *dest)
 492 {
 493   return dest->rnode->p.family;
 494 }
 495
 496 /*
 497  * rib_dest_table
 498  */
 499 static inline struct route_table *
 500 rib_dest_table (rib_dest_t *dest)
 501 {
 502   return dest->rnode->table;
 503 }
 504
 505 /*
 506  * rib_dest_vrf
 507  */
 508 static inline struct vrf *
 509 rib_dest_vrf (rib_dest_t *dest)
 510 {
 511   return rib_table_info (rib_dest_table (dest))->vrf;
 512 }
 513
 514 /*
 515  * rib_tables_iter_init
 516  */
 517 static inline void
 518 rib_tables_iter_init (rib_tables_iter_t *iter)
 519
 520 {
 521   memset (iter, 0, sizeof (*iter));
 522   iter->state = RIB_TABLES_ITER_S_INIT;
 523 }
 524
 525 /*
 526  * rib_tables_iter_started
 527  *
 528  * Returns TRUE if this iterator has started iterating over the set of
 529  * tables.
 530  */
 531 static inline int
 532 rib_tables_iter_started (rib_tables_iter_t *iter)
 533 {
 534   return iter->state != RIB_TABLES_ITER_S_INIT;
 535 }
 536
 537 /*
 538  * rib_tables_iter_cleanup
 539  */
 540 static inline void
 541 rib_tables_iter_cleanup (rib_tables_iter_t *iter)
 542 {
 543   iter->state = RIB_TABLES_ITER_S_DONE;
 544 }
 545
 546 #endif /*_ZEBRA_RIB_H */