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