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             :    A fib4 always has a dummy route at index 0.
      13             : 
      14             :    FIXME: CONSIDER TRIE BASED DATA STRUCTURE
      15             : 
      16             :    Trivia: https://en.wikipedia.org/wiki/Forwarding_information_base */
      17             : 
      18             : #include "../../util/fd_util_base.h"
      19             : 
      20             : #define FD_FIB4_ALIGN (128UL)
      21             : 
      22             : /* FD_FIB4_RTYPE_{...} enumerate route types.
      23             :    These match Linux RTN_UNICAST, etc. */
      24             : 
      25        5364 : #define FD_FIB4_RTYPE_UNSPEC    (0) /* invalid */
      26         168 : #define FD_FIB4_RTYPE_UNICAST   (1) /* "normal" path */
      27          45 : #define FD_FIB4_RTYPE_LOCAL     (2) /* address on local host */
      28          72 : #define FD_FIB4_RTYPE_BROADCAST (3) /* reserved for future use */
      29           0 : #define FD_FIB4_RTYPE_MULTICAST (5) /* reserved for future use */
      30           3 : #define FD_FIB4_RTYPE_BLACKHOLE (6) /* drop packet */
      31          78 : #define FD_FIB4_RTYPE_THROW     (9) /* continue in next table */
      32             : 
      33             : /* fd_fib4_t is a local handle to a fib4 object. Use fd_fib4_{join,leave}
      34             :    to join the fd_fib4_t to the shmem fib4. A fd_fib4_t can be stack declared,
      35             :    e.g. fd_fib4_t fib4[1]; */
      36             : 
      37             : struct fd_fib4_priv;
      38             : typedef struct fd_fib4_priv fd_fib4_priv_t;
      39             : struct fd_fib4 {
      40             :    /* local ptr to shared fib4_priv_t */
      41             :    fd_fib4_priv_t * priv;
      42             : 
      43             :    /* local join to the hmap - punned internally */
      44             :    uchar            hmap_join[64] __attribute__((aligned(8)));
      45             :  };
      46             : typedef struct fd_fib4 fd_fib4_t;
      47             : 
      48             : /* fd_fib4_hop_t holds a FIB lookup result (see fd_fib4_lookup) */
      49             : 
      50             : struct __attribute__((aligned(16))) fd_fib4_hop {
      51             :   uint  ip4_gw;   /* gateway address (big endian) */
      52             :   uint  if_idx;   /* output interface index */
      53             :   uint  ip4_src;  /* override source address (big endian). 0 implies unset */
      54             :   uchar rtype;    /* route type (e.g. FD_FIB4_RTYPE_UNICAST) */
      55             :   uchar scope;    /* used to select source address */
      56             :   uchar flags;    /* app-specific flags */
      57             : };
      58             : 
      59           0 : #define FD_FIB4_FLAG_RTA_UNSUPPORTED   ((uchar)0x01U) /* unsupported route attribute */
      60           0 : #define FD_FIB4_FLAG_RTA_PARSE_ERR     ((uchar)0x02U) /* failed to interpret route attribute */
      61           0 : #define FD_FIB4_FLAG_RTYPE_UNSUPPORTED ((uchar)0x03U) /* unsupported route type */
      62             : 
      63             : typedef struct fd_fib4_hop fd_fib4_hop_t;
      64             : 
      65             : FD_PROTOTYPES_BEGIN
      66             : 
      67             : /* Constructor APIs ******************************************************/
      68             : 
      69             : FD_FN_CONST ulong
      70             : fd_fib4_align( void );
      71             : 
      72             : FD_FN_CONST ulong
      73             : fd_fib4_footprint( ulong route_max,
      74             :                    ulong route_peer_max );
      75             : 
      76             : /* fd_fib4_new formats a shared memory region mem with alignment and footprint
      77             :    suitable for a fib4. It expects at most route_peer_max /32 routes, and
      78             :    at most route_max non-/32 routes. Returns mem on success and NULL on failure.
      79             :    Takes seed to be used for the hashmap. */
      80             : 
      81             : void *
      82             : fd_fib4_new( void * mem,
      83             :              ulong  route_max,
      84             :              ulong  route_peer_max,
      85             :              ulong  route_peer_seed );
      86             : 
      87             : /* fd_fib4_join joins the caller to a shared memory region shmem holding a fib4.
      88             :    fib4 should be a pointer to the local join to populate, and shmem should be a
      89             :    pointer in the caller's address space to the shared memory region formatted
      90             :    using fd_fib4_new. Returns fib4 on success and NULL on failure. */
      91             : 
      92             : fd_fib4_t *
      93             : fd_fib4_join( fd_fib4_t * fib4,
      94             :               void *      shmem );
      95             : 
      96             : void *
      97             : fd_fib4_leave( fd_fib4_t * fib4 );
      98             : 
      99             : void *
     100             : fd_fib4_delete( void * mem );
     101             : 
     102             : /* Write APIs ************************************************************/
     103             : 
     104             : /* fd_fib4_clear removes all route table entries but the first. Remove all
     105             :    entries in the route hmap. Sets the first route table entry to
     106             :    "throw 0.0.0.0/0 metric ((2<<32)-1)". */
     107             : 
     108             : void
     109             : fd_fib4_clear( fd_fib4_t * fib );
     110             : 
     111             : /* fd_fib4_insert attempts to add a new route entry to the FIB routing table.
     112             :    Routes with /32 netmask prefix are stored in hashmap for faster lookup.
     113             :    Other routes use the main table.  A route with the same destination,
     114             :    prefix, and priority replaces the existing route.  Returns 1 on success,
     115             :    0 if the internal data structures are full (logs warning in that case). */
     116             : 
     117             : int
     118             : fd_fib4_insert( fd_fib4_t *           fib,
     119             :                 uint                  ip4_dst,
     120             :                 int                   prefix,
     121             :                 uint                  prio,
     122             :                 fd_fib4_hop_t const * hop );
     123             : 
     124             : /* fd_fib4_remove removes the route identified by destination, prefix, and
     125             :    priority.  Returns 1 if a route was removed and 0 if no exact match exists. */
     126             : 
     127             : int
     128             : fd_fib4_remove( fd_fib4_t * fib,
     129             :                 uint        ip4_dst,
     130             :                 int         prefix,
     131             :                 uint        prio );
     132             : 
     133             : /* Read APIs *************************************************************/
     134             : 
     135             : /* fd_fib4_lookup resolves the next hop for an arbitrary IPv4 address.
     136             :    If multiple /32 routes match, selects the route with the lowest
     137             :    priority value. If route was not found, retval.rtype is set to
     138             :    FD_FIB4_RTYPE_THROW. */
     139             : 
     140             : fd_fib4_hop_t
     141             : fd_fib4_lookup( fd_fib4_t const * fib,
     142             :                 uint              ip4_dst,
     143             :                 ulong             flags );
     144             : 
     145             : /* fd_fib4_hop_or is a helper to chain together multiple FIB lookups. */
     146             : 
     147             : FD_FN_PURE static inline fd_fib4_hop_t const *
     148             : fd_fib4_hop_or( fd_fib4_hop_t const * left,
     149          48 :                 fd_fib4_hop_t const * right ) {
     150          48 :   return left->rtype!=FD_FIB4_RTYPE_THROW ? left : right;
     151          48 : }
     152             : 
     153             : /* fd_fib4_max returns the max number of routes in the table. */
     154             : 
     155             : FD_FN_PURE ulong
     156             : fd_fib4_max( fd_fib4_t const * fib );
     157             : 
     158             : /* fd_fib4_peer_max returns the max number of /32 routes (backed by a hashmap). */
     159             : 
     160             : FD_FN_PURE ulong
     161             : fd_fib4_peer_max( fd_fib4_t const * fib );
     162             : 
     163             : /* fd_fib4_cnt returns the total number of routes stored in the fib4.
     164             :    This also includes /32 routes. */
     165             : 
     166             : FD_FN_PURE ulong
     167             : fd_fib4_cnt( fd_fib4_t const * fib );
     168             : 
     169             : #if FD_HAS_HOSTED
     170             : 
     171             : /* fd_fib4_fprintf prints the routing table and hash map to the given FILE *
     172             :    pointer (or target equivalent).  Order of routes is undefined but
     173             :    guaranteed to be stable between calls.  Outputs ASCII encoding with LF
     174             :    newlines.  Returns errno on failure and 0 on success. */
     175             : 
     176             : int
     177             : fd_fib4_fprintf( fd_fib4_t const * fib,
     178             :                  void *            file );
     179             : 
     180             : #endif
     181             : 
     182             : FD_PROTOTYPES_END
     183             : 
     184             : #endif /* HEADER_fd_src_waltz_ip_fd_fib4_h */