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 (16UL) 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 39 : #define FD_FIB4_RTYPE_UNICAST (1) /* "normal" path */ 31 54 : #define FD_FIB4_RTYPE_LOCAL (2) /* address on local host */ 32 78 : #define FD_FIB4_RTYPE_BROADCAST (3) /* reserved for future use */ 33 0 : #define FD_FIB4_RTYPE_MULTICAST (5) /* reserved for future use */ 34 0 : #define FD_FIB4_RTYPE_BLACKHOLE (6) /* drop packet */ 35 39 : #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 : 70 : void * 71 : fd_fib4_new( void * mem, 72 : ulong route_max ); 73 : 74 : fd_fib4_t * 75 : fd_fib4_join( void * mem ); 76 : 77 : void * 78 : fd_fib4_leave( fd_fib4_t * fib4 ); 79 : 80 : void * 81 : fd_fib4_delete( void * mem ); 82 : 83 : /* Write APIs ************************************************************* 84 : 85 : Currently, any updates to a fib4 require a full rewrite (incremental 86 : updates are not supported). During an update, fd_fib4_lookup calls 87 : temporarily return a route entry with FD_FIB4_RTYPE_BLACKHOLE, which 88 : means outgoing packets get dropped. (This is preferable to potentially 89 : making an incorrect routing decision based on a partial route table.) */ 90 : 91 : /* fd_fib4_clear removes all route table entries but the first. Sets 92 : the first route table entry to "throw 0.0.0.0/0 metric ((2<<32)-1)". */ 93 : 94 : void 95 : fd_fib4_clear( fd_fib4_t * fib ); 96 : 97 : /* fd_fib4_append attempts to add a new route entry. If 98 : fd_fib4_free_cnt(fib) returned non-zero immediately prior to calling 99 : append, then append is guaranteed to succeed. 100 : 101 : Returns a hop object to be filled by the caller on success. On 102 : failure, returns NULL and logs warning. */ 103 : 104 : fd_fib4_hop_t * 105 : fd_fib4_append( fd_fib4_t * fib, 106 : uint ip4_dst, 107 : int prefix, 108 : uint prio ); 109 : 110 : /* Read APIs *************************************************************/ 111 : 112 : /* fd_fib4_lookup resolves the next hop for an arbitrary IPv4 address. 113 : If route was not found, retval->rtype is set to FD_FIB4_RTYPE_THROW. 114 : 115 : Thread safe: Multiple threads can use the read API concurrently without 116 : affecting each other. If a write by one thread is in progress, all 117 : other threads calling fd_fib4_lookup may briefly see a blackhole route 118 : being returned. (Until of the effects of the write become visible to 119 : all CPUs in the system) */ 120 : 121 : fd_fib4_hop_t const * 122 : fd_fib4_lookup( fd_fib4_t const * fib, 123 : fd_fib4_hop_t * out, 124 : uint ip4_dst, 125 : ulong flags ); 126 : 127 : /* fd_fib4_hop_or is a helper to chain together multiple FIB lookups. */ 128 : 129 : FD_FN_PURE static inline fd_fib4_hop_t const * 130 : fd_fib4_hop_or( fd_fib4_hop_t const * left, 131 15 : fd_fib4_hop_t const * right ) { 132 15 : return left->rtype!=FD_FIB4_RTYPE_THROW ? left : right; 133 15 : } 134 : 135 : /* fd_fib4_max returns the max number of routes in the table. */ 136 : 137 : FD_FN_PURE ulong 138 : fd_fib4_max( fd_fib4_t const * fib ); 139 : 140 : /* fd_fib4_cnt returns the number of routes in the table. */ 141 : 142 : FD_FN_PURE ulong 143 : fd_fib4_cnt( fd_fib4_t const * fib ); 144 : 145 : /* fd_fib4_free_cnt returns the number of fd_fib4_append calls that are 146 : guaranteed to succeed. */ 147 : 148 : ulong 149 : fd_fib4_free_cnt( fd_fib4_t const * fib ); 150 : 151 : #if FD_HAS_HOSTED 152 : 153 : /* fd_fib4_fprintf prints the routing table to the given FILE * pointer (or 154 : target equivalent). Order of routes is undefined but guaranteed to be 155 : stable between calls. Outputs ASCII encoding with LF newlines. Returns 156 : errno on failure and 0 on success. */ 157 : 158 : int 159 : fd_fib4_fprintf( fd_fib4_t const * fib, 160 : void * file ); 161 : 162 : #endif 163 : 164 : FD_PROTOTYPES_END 165 : 166 : #endif /* HEADER_fd_src_waltz_ip_fd_fib4_h */
