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         390 : #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          72 : #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_{join,leave}
      38             :    to join the fd_fib4_t to the shmem fib4. A fd_fib4_t can be stack declared,
      39             :    e.g. fd_fib4_t fib4[1]; */
      40             : 
      41             : struct fd_fib4_priv;
      42             : typedef struct fd_fib4_priv fd_fib4_priv_t;
      43             : struct fd_fib4 {
      44             :    /* local ptr to shared fib4_priv_t */
      45             :    fd_fib4_priv_t * priv;
      46             : 
      47             :    /* local join to the hmap - punned internally */
      48             :    uchar            hmap_join[64] __attribute__((aligned(8)));
      49             :  };
      50             : typedef struct fd_fib4 fd_fib4_t;
      51             : 
      52             : /* fd_fib4_hop_t holds a FIB lookup result (see fd_fib4_lookup) */
      53             : 
      54             : struct __attribute__((aligned(16))) fd_fib4_hop {
      55             :   uint  ip4_gw;   /* gateway address (big endian) */
      56             :   uint  if_idx;   /* output interface index */
      57             :   uint  ip4_src;  /* override source address (big endian). 0 implies unset */
      58             :   uchar rtype;    /* route type (e.g. FD_FIB4_RTYPE_UNICAST) */
      59             :   uchar scope;    /* used to select source address */
      60             :   uchar flags;    /* app-specific flags */
      61             : };
      62             : 
      63           0 : #define FD_FIB4_FLAG_RTA_UNSUPPORTED   ((uchar)0x01U) /* unsupported route attribute */
      64           0 : #define FD_FIB4_FLAG_RTA_PARSE_ERR     ((uchar)0x02U) /* failed to interpret route attribute */
      65           0 : #define FD_FIB4_FLAG_RTYPE_UNSUPPORTED ((uchar)0x03U) /* unsupported route type */
      66             : 
      67             : typedef struct fd_fib4_hop fd_fib4_hop_t;
      68             : 
      69             : FD_PROTOTYPES_BEGIN
      70             : 
      71             : /* Constructor APIs ******************************************************/
      72             : 
      73             : FD_FN_CONST ulong
      74             : fd_fib4_align( void );
      75             : 
      76             : FD_FN_CONST ulong
      77             : fd_fib4_footprint( ulong route_max,
      78             :                    ulong route_peer_max );
      79             : 
      80             : /* fd_fib4_new formats a shared memory region mem with alignment and footprint
      81             :    suitable for a fib4. It expects at most route_peer_max /32 routes, and
      82             :    at most route_max non-/32 routes. Returns mem on success and NULL on failure.
      83             :    Takes seed to be used for the hashmap. */
      84             : 
      85             : void *
      86             : fd_fib4_new( void * mem,
      87             :              ulong  route_max,
      88             :              ulong  route_peer_max,
      89             :              ulong  route_peer_seed );
      90             : 
      91             : /* fd_fib4_join joins the caller to a shared memory region shmem holding a fib4.
      92             :    fib4 should be a pointer to the local join to populate, and shmem should be a
      93             :    pointer in the caller's address space to the shared memory region formatted
      94             :    using fd_fib4_new. Returns fib4 on success and NULL on failure. */
      95             : 
      96             : fd_fib4_t *
      97             : fd_fib4_join( fd_fib4_t * fib4,
      98             :               void *      shmem );
      99             : 
     100             : void *
     101             : fd_fib4_leave( fd_fib4_t * fib4 );
     102             : 
     103             : void *
     104             : fd_fib4_delete( void * mem );
     105             : 
     106             : /* Write APIs *************************************************************
     107             : 
     108             :    Currently, any updates to a fib4 require a full rewrite (incremental
     109             :    updates are not supported).  During an update, fd_fib4_lookup calls
     110             :    temporarily return a route entry with FD_FIB4_RTYPE_BLACKHOLE, which
     111             :    means outgoing packets get dropped.  (This is preferable to potentially
     112             :    making an incorrect routing decision based on a partial route table.) */
     113             : 
     114             : /* fd_fib4_clear removes all route table entries but the first. Remove all
     115             :    entries in the route hmap. Sets the first route table entry to
     116             :    "throw 0.0.0.0/0 metric ((2<<32)-1)". */
     117             : 
     118             : void
     119             : fd_fib4_clear( fd_fib4_t * fib );
     120             : 
     121             : /* fd_fib4_insert attempts to add a new route entry to the FIB routing table.
     122             :    Routes with /32 netmask prefix are stored in hashmap for faster lookup. Other
     123             :    routes use the main table. Returns 1 on success, 0 if the internal data
     124             :    structures are full (logs warning in that case).
     125             :    */
     126             : 
     127             : int
     128             : fd_fib4_insert( fd_fib4_t *     fib,
     129             :                 uint            ip4_dst,
     130             :                 int             prefix,
     131             :                 uint            prio,
     132             :                 fd_fib4_hop_t * hop );
     133             : 
     134             : /* Read APIs *************************************************************/
     135             : 
     136             : /* fd_fib4_lookup resolves the next hop for an arbitrary IPv4 address.
     137             :    If route was not found, retval.rtype is set to FD_FIB4_RTYPE_THROW.
     138             : 
     139             :    Thread safe: Multiple threads can use the read API concurrently without
     140             :    affecting each other.  If a write by one thread is in progress, all
     141             :    other threads calling fd_fib4_lookup may briefly see a blackhole route
     142             :    being returned.  (Until of the effects of the write become visible to
     143             :    all CPUs in the system) */
     144             : 
     145             : fd_fib4_hop_t
     146             : fd_fib4_lookup( fd_fib4_t const * fib,
     147             :                 uint              ip4_dst,
     148             :                 ulong             flags );
     149             : 
     150             : /* fd_fib4_hop_or is a helper to chain together multiple FIB lookups. */
     151             : 
     152             : FD_FN_PURE static inline fd_fib4_hop_t const *
     153             : fd_fib4_hop_or( fd_fib4_hop_t const * left,
     154          48 :                 fd_fib4_hop_t const * right ) {
     155          48 :   return left->rtype!=FD_FIB4_RTYPE_THROW ? left : right;
     156          48 : }
     157             : 
     158             : /* fd_fib4_max returns the max number of routes in the table. */
     159             : 
     160             : FD_FN_PURE ulong
     161             : fd_fib4_max( fd_fib4_t const * fib );
     162             : 
     163             : /* fd_fib4_peer_max returns the max number of /32 routes (backed by a hashmap). */
     164             : 
     165             : FD_FN_PURE ulong
     166             : fd_fib4_peer_max( fd_fib4_t const * fib );
     167             : 
     168             : /* fd_fib4_cnt returns the total number of routes stored in the fib4.
     169             :    This also includes /32 routes. */
     170             : 
     171             : FD_FN_PURE ulong
     172             : fd_fib4_cnt( fd_fib4_t const * fib );
     173             : 
     174             : #if FD_HAS_HOSTED
     175             : 
     176             : /* fd_fib4_fprintf prints the routing table and hash map to the given FILE *
     177             :    pointer (or target equivalent).  Order of routes is undefined but
     178             :    guaranteed to be stable between calls.  Outputs ASCII encoding with LF
     179             :    newlines.  Returns errno on failure and 0 on success. */
     180             : 
     181             : int
     182             : fd_fib4_fprintf( fd_fib4_t const * fib,
     183             :                  void *            file );
     184             : 
     185             : #endif
     186             : 
     187             : FD_PROTOTYPES_END
     188             : 
     189             : #endif /* HEADER_fd_src_waltz_ip_fd_fib4_h */