Line data    Source code

       1             : #ifndef HEADER_fd_src_waltz_ip_fd_fib4_h
       2             : #define HEADER_fd_src_waltz_ip_fd_fib4_h
       3             : 
       4             : /* A fib4 stores IPv4 routes in a query-optimized data structure.
       5             : 
       6             :    fib4 does not scale well to large numbers of routes.  Every route
       7             :    lookup is O(n) where n is the number of routes in the FIB.
       8             : 
       9             :    fib4 only supports a minimal set of features required for end devices
      10             :    to operate.  Packet forwarding is not supported.
      11             : 
      12             :    fib4 supports multi-threaded operation in a x86-TSO like environment.
      13             :    (many reader threads, one writer thread)  Refer to each function for
      14             :    thread safety.
      15             : 
      16             :    A fib4 always has a dummy route at index 0.
      17             : 
      18             :    FIXME: CONSIDER TRIE BASED DATA STRUCTURE
      19             : 
      20             :    Trivia: https://en.wikipedia.org/wiki/Forwarding_information_base */
      21             : 
      22             : #include "../../util/fd_util_base.h"
      23             : 
      24             : #define FD_FIB4_ALIGN (128UL)
      25             : 
      26             : /* FD_FIB4_RTYPE_{...} enumerate route types.
      27             :    These match Linux RTN_UNICAST, etc. */
      28             : 
      29           0 : #define FD_FIB4_RTYPE_UNSPEC    (0) /* invalid */
      30         111 : #define FD_FIB4_RTYPE_UNICAST   (1) /* "normal" path */
      31          45 : #define FD_FIB4_RTYPE_LOCAL     (2) /* address on local host */
      32          84 : #define FD_FIB4_RTYPE_BROADCAST (3) /* reserved for future use */
      33           0 : #define FD_FIB4_RTYPE_MULTICAST (5) /* reserved for future use */
      34           3 : #define FD_FIB4_RTYPE_BLACKHOLE (6) /* drop packet */
      35          78 : #define FD_FIB4_RTYPE_THROW     (9) /* continue in next table */
      36             : 
      37             : /* fd_fib4_t is a local handle to a fib4 object.  Use fd_fib4_{align,
      38             :    footprint,new,delete,join,leave} to construct and join a fib4. */
      39             : 
      40             : struct fd_fib4;
      41             : typedef struct fd_fib4 fd_fib4_t;
      42             : 
      43             : /* fd_fib4_hop_t holds a FIB lookup result (see fd_fib4_lookup) */
      44             : 
      45             : struct __attribute__((aligned(16))) fd_fib4_hop {
      46             :   uint  ip4_gw;   /* gateway address (big endian) */
      47             :   uint  if_idx;   /* output interface index */
      48             :   uint  ip4_src;  /* override source address (big endian). 0 implies unset */
      49             :   uchar rtype;    /* route type (e.g. FD_FIB4_RTYPE_UNICAST) */
      50             :   uchar scope;    /* used to select source address */
      51             :   uchar flags;    /* app-specific flags */
      52             : };
      53             : 
      54           0 : #define FD_FIB4_FLAG_RTA_UNSUPPORTED   ((uchar)0x01U) /* unsupported route attribute */
      55           0 : #define FD_FIB4_FLAG_RTA_PARSE_ERR     ((uchar)0x02U) /* failed to interpret route attribute */
      56           0 : #define FD_FIB4_FLAG_RTYPE_UNSUPPORTED ((uchar)0x03U) /* unsupported route type */
      57             : 
      58             : typedef struct fd_fib4_hop fd_fib4_hop_t;
      59             : 
      60             : FD_PROTOTYPES_BEGIN
      61             : 
      62             : /* Constructor APIs ******************************************************/
      63             : 
      64             : FD_FN_CONST ulong
      65             : fd_fib4_align( void );
      66             : 
      67             : FD_FN_CONST ulong
      68             : fd_fib4_footprint( ulong route_max,
      69             :                    ulong route_peer_max );
      70             : 
      71             : void *
      72             : fd_fib4_new( void * mem,
      73             :              ulong  route_max,
      74             :              ulong  route_peer_max,
      75             :              ulong  route_peer_seed );
      76             : 
      77             : fd_fib4_t *
      78             : fd_fib4_join( void * mem );
      79             : 
      80             : void *
      81             : fd_fib4_leave( fd_fib4_t * fib4 );
      82             : 
      83             : void *
      84             : fd_fib4_delete( void * mem );
      85             : 
      86             : /* Write APIs *************************************************************
      87             : 
      88             :    Currently, any updates to a fib4 require a full rewrite (incremental
      89             :    updates are not supported).  During an update, fd_fib4_lookup calls
      90             :    temporarily return a route entry with FD_FIB4_RTYPE_BLACKHOLE, which
      91             :    means outgoing packets get dropped.  (This is preferable to potentially
      92             :    making an incorrect routing decision based on a partial route table.) */
      93             : 
      94             : /* fd_fib4_clear removes all route table entries but the first. Remove all
      95             :    entries in the route hmap. Sets the first route table entry to
      96             :    "throw 0.0.0.0/0 metric ((2<<32)-1)". */
      97             : 
      98             : void
      99             : fd_fib4_clear( fd_fib4_t * fib );
     100             : 
     101             : /* fd_fib4_insert attempts to add a new route entry to the FIB routing table.
     102             :    Routes with /32 netmask prefix are stored in hashmap for faster lookup. Other
     103             :    routes use the main table. Returns 1 on success, 0 if the internal data
     104             :    structures are full (logs warning in that case).
     105             :    */
     106             : 
     107             : int
     108             : fd_fib4_insert( fd_fib4_t *     fib,
     109             :                 uint            ip4_dst,
     110             :                 int             prefix,
     111             :                 uint            prio,
     112             :                 fd_fib4_hop_t * hop );
     113             : 
     114             : /* Read APIs *************************************************************/
     115             : 
     116             : /* fd_fib4_lookup resolves the next hop for an arbitrary IPv4 address.
     117             :    If route was not found, retval->rtype is set to FD_FIB4_RTYPE_THROW.
     118             : 
     119             :    Thread safe: Multiple threads can use the read API concurrently without
     120             :    affecting each other.  If a write by one thread is in progress, all
     121             :    other threads calling fd_fib4_lookup may briefly see a blackhole route
     122             :    being returned.  (Until of the effects of the write become visible to
     123             :    all CPUs in the system) */
     124             : 
     125             : fd_fib4_hop_t const *
     126             : fd_fib4_lookup( fd_fib4_t const * fib,
     127             :                 fd_fib4_hop_t *   out,
     128             :                 uint              ip4_dst,
     129             :                 ulong             flags );
     130             : 
     131             : /* fd_fib4_hop_or is a helper to chain together multiple FIB lookups. */
     132             : 
     133             : FD_FN_PURE static inline fd_fib4_hop_t const *
     134             : fd_fib4_hop_or( fd_fib4_hop_t const * left,
     135          48 :                 fd_fib4_hop_t const * right ) {
     136          48 :   return left->rtype!=FD_FIB4_RTYPE_THROW ? left : right;
     137          48 : }
     138             : 
     139             : /* fd_fib4_max returns the max number of routes in the table. */
     140             : 
     141             : FD_FN_PURE ulong
     142             : fd_fib4_max( fd_fib4_t const * fib );
     143             : 
     144             : /* fd_fib4_peer_max returns the max number of /32 routes (backed by a hashmap). */
     145             : 
     146             : FD_FN_PURE ulong
     147             : fd_fib4_peer_max( fd_fib4_t const * fib );
     148             : 
     149             : /* fd_fib4_cnt returns the total number of routes stored in the fib4.
     150             :    This also includes /32 routes. */
     151             : 
     152             : FD_FN_PURE ulong
     153             : fd_fib4_cnt( fd_fib4_t const * fib );
     154             : 
     155             : #if FD_HAS_HOSTED
     156             : 
     157             : /* fd_fib4_fprintf prints the routing table and hash map to the given FILE *
     158             :    pointer (or target equivalent).  Order of routes is undefined but
     159             :    guaranteed to be stable between calls.  Outputs ASCII encoding with LF
     160             :    newlines.  Returns errno on failure and 0 on success. */
     161             : 
     162             : int
     163             : fd_fib4_fprintf( fd_fib4_t const * fib,
     164             :                  void *            file );
     165             : 
     166             : #endif
     167             : 
     168             : FD_PROTOTYPES_END
     169             : 
     170             : #endif /* HEADER_fd_src_waltz_ip_fd_fib4_h */