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           0 : #define FD_FIB4_RTYPE_UNSPEC    (0) /* invalid */
      26           0 : #define FD_FIB4_RTYPE_UNICAST   (1) /* "normal" path */
      27           0 : #define FD_FIB4_RTYPE_LOCAL     (2) /* address on local host */
      28           0 : #define FD_FIB4_RTYPE_BROADCAST (3) /* reserved for future use */
      29           0 : #define FD_FIB4_RTYPE_MULTICAST (5) /* reserved for future use */
      30           0 : #define FD_FIB4_RTYPE_BLACKHOLE (6) /* drop packet */
      31           0 : #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;    /* reserved; currently unused */
      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)0x04U) /* 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-1 non-/32 routes (one slot is reserved for a throw
      79             :    route). Returns mem on success and NULL on failure.
      80             :    Takes seed to be used for the hashmap. */
      81             : 
      82             : void *
      83             : fd_fib4_new( void * mem,
      84             :              ulong  route_max,
      85             :              ulong  route_peer_max,
      86             :              ulong  route_peer_seed );
      87             : 
      88             : /* fd_fib4_join joins the caller to a shared memory region shmem holding a fib4.
      89             :    fib4 should be a pointer to the local join to populate, and shmem should be a
      90             :    pointer in the caller's address space to the shared memory region formatted
      91             :    using fd_fib4_new. Returns fib4 on success and NULL on failure. */
      92             : 
      93             : fd_fib4_t *
      94             : fd_fib4_join( fd_fib4_t * fib4,
      95             :               void *      shmem );
      96             : 
      97             : void *
      98             : fd_fib4_leave( fd_fib4_t * fib4 );
      99             : 
     100             : void *
     101             : fd_fib4_delete( void * mem );
     102             : 
     103             : /* Write APIs ************************************************************/
     104             : 
     105             : /* fd_fib4_clear removes all route table entries but the first. Remove all
     106             :    entries in the route hmap. Sets the first route table entry to
     107             :    "throw 0.0.0.0/0 metric ((2<<32)-1)". */
     108             : 
     109             : void
     110             : fd_fib4_clear( fd_fib4_t * fib );
     111             : 
     112             : /* fd_fib4_insert attempts to add a new route entry to the FIB routing table.
     113             :    Routes with /32 netmask prefix are stored in hashmap for faster lookup.
     114             :    Other routes use the main table.  A route with the same destination,
     115             :    prefix, and priority replaces the existing route.  Returns 1 on success,
     116             :    0 if the internal data structures are full (logs warning in that case). */
     117             : 
     118             : int
     119             : fd_fib4_insert( fd_fib4_t *           fib,
     120             :                 uint                  ip4_dst,
     121             :                 int                   prefix,
     122             :                 uint                  prio,
     123             :                 fd_fib4_hop_t const * hop );
     124             : 
     125             : /* fd_fib4_remove removes the route identified by destination, prefix, and
     126             :    priority.  Returns 1 if a route was removed and 0 if no exact match exists. */
     127             : 
     128             : int
     129             : fd_fib4_remove( fd_fib4_t * fib,
     130             :                 uint        ip4_dst,
     131             :                 int         prefix,
     132             :                 uint        prio );
     133             : 
     134             : /* Read APIs *************************************************************/
     135             : 
     136             : /* fd_fib4_lookup resolves the next hop for an arbitrary IPv4 address.
     137             :    If multiple /32 routes match, selects the route with the lowest
     138             :    priority value. If route was not found, retval.rtype is set to
     139             :    FD_FIB4_RTYPE_THROW. */
     140             : 
     141             : fd_fib4_hop_t
     142             : fd_fib4_lookup( fd_fib4_t const * fib,
     143             :                 uint              ip4_dst,
     144             :                 ulong             flags );
     145             : 
     146             : /* fd_fib4_hop_or is a helper to chain together multiple FIB lookups. */
     147             : 
     148             : FD_FN_PURE static inline fd_fib4_hop_t const *
     149             : fd_fib4_hop_or( fd_fib4_hop_t const * left,
     150           0 :                 fd_fib4_hop_t const * right ) {
     151           0 :   return left->rtype!=FD_FIB4_RTYPE_THROW ? left : right;
     152           0 : }
     153             : 
     154             : /* fd_fib4_max returns the max number of routes in the table. */
     155             : 
     156             : FD_FN_PURE ulong
     157             : fd_fib4_max( fd_fib4_t const * fib );
     158             : 
     159             : /* fd_fib4_peer_max returns the max number of /32 routes (backed by a hashmap). */
     160             : 
     161             : FD_FN_PURE ulong
     162             : fd_fib4_peer_max( fd_fib4_t const * fib );
     163             : 
     164             : /* fd_fib4_cnt returns the total number of routes stored in the fib4.
     165             :    This also includes /32 routes. */
     166             : 
     167             : FD_FN_PURE ulong
     168             : fd_fib4_cnt( fd_fib4_t const * fib );
     169             : 
     170             : #if FD_HAS_HOSTED
     171             : 
     172             : /* fd_fib4_fprintf prints the routing table and hash map to the given FILE *
     173             :    pointer (or target equivalent).  Order of routes is undefined but
     174             :    guaranteed to be stable between calls.  Outputs ASCII encoding with LF
     175             :    newlines.  Returns errno on failure and 0 on success. */
     176             : 
     177             : int
     178             : fd_fib4_fprintf( fd_fib4_t const * fib,
     179             :                  void *            file );
     180             : 
     181             : #endif
     182             : 
     183             : FD_PROTOTYPES_END
     184             : 
     185             : #endif /* HEADER_fd_src_waltz_ip_fd_fib4_h */