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