Line data Source code
1 : #include "fd_fib4.h"
2 : #include "fd_fib4_private.h"
3 : #include "../../util/fd_util.h"
4 :
5 : static const fd_fib4_hop_t
6 : fd_fib4_hop_blackhole = {
7 : .rtype = FD_FIB4_RTYPE_BLACKHOLE
8 : };
9 :
10 : FD_FN_CONST ulong
11 9 : fd_fib4_align( void ) {
12 9 : return alignof(fd_fib4_t);
13 9 : }
14 :
15 : FD_FN_CONST ulong
16 15 : fd_fib4_footprint( ulong route_max ) {
17 15 : if( route_max==0 || route_max>UINT_MAX ) return 0UL;
18 15 : return FD_LAYOUT_FINI( FD_LAYOUT_APPEND( FD_LAYOUT_APPEND( FD_LAYOUT_APPEND( FD_LAYOUT_INIT,
19 15 : alignof(fd_fib4_t), sizeof(fd_fib4_t) ),
20 15 : alignof(fd_fib4_key_t), route_max*sizeof(fd_fib4_key_t) ),
21 15 : alignof(fd_fib4_hop_t), route_max*sizeof(fd_fib4_hop_t) ),
22 15 : alignof(fd_fib4_t) );
23 15 : }
24 :
25 : void *
26 : fd_fib4_new( void * mem,
27 12 : ulong route_max ) {
28 :
29 12 : if( FD_UNLIKELY( !mem ) ) {
30 0 : FD_LOG_WARNING(( "NULL mem" ));
31 0 : return NULL;
32 0 : }
33 12 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)mem, fd_fib4_align() ) ) ) {
34 0 : FD_LOG_WARNING(( "unaligned mem" ));
35 0 : return NULL;
36 0 : }
37 12 : if( FD_UNLIKELY( route_max==0 || route_max>UINT_MAX ) ) {
38 0 : FD_LOG_WARNING(( "invalid route_max" ));
39 0 : return NULL;
40 0 : }
41 :
42 12 : FD_SCRATCH_ALLOC_INIT( l, mem );
43 12 : fd_fib4_t * fib4 = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_fib4_t), sizeof(fd_fib4_t) );
44 12 : fd_fib4_key_t * keys = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_fib4_key_t), route_max*sizeof(fd_fib4_key_t) );
45 12 : fd_fib4_hop_t * vals = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_fib4_hop_t), route_max*sizeof(fd_fib4_hop_t) );
46 12 : FD_SCRATCH_ALLOC_FINI( l, alignof(fd_fib4_t) );
47 :
48 12 : fd_memset( fib4, 0, sizeof(fd_fib4_t) );
49 12 : fd_memset( keys, 0, route_max*sizeof(fd_fib4_key_t) );
50 12 : fd_memset( vals, 0, route_max*sizeof(fd_fib4_hop_t) );
51 12 : fib4->max = route_max;
52 12 : fib4->hop_off = (ulong)vals - (ulong)fib4;
53 12 : keys[0].prio = UINT_MAX;
54 12 : vals[0].rtype = FD_FIB4_RTYPE_THROW;
55 :
56 12 : fd_fib4_clear( fib4 );
57 :
58 12 : return fib4;
59 12 : }
60 :
61 : fd_fib4_t *
62 12 : fd_fib4_join( void * mem ) {
63 12 : return (fd_fib4_t *)mem;
64 12 : }
65 :
66 : void *
67 12 : fd_fib4_leave( fd_fib4_t * fib4 ) {
68 12 : return fib4;
69 12 : }
70 :
71 : void *
72 12 : fd_fib4_delete( void * mem ) {
73 12 : return mem;
74 12 : }
75 :
76 : void
77 27 : fd_fib4_clear( fd_fib4_t * fib4 ) {
78 27 : fib4->cnt = 1UL;
79 27 : }
80 :
81 : FD_FN_PURE ulong
82 0 : fd_fib4_max( fd_fib4_t const * fib ) {
83 0 : return fib->max;
84 0 : }
85 :
86 : FD_FN_PURE ulong
87 0 : fd_fib4_cnt( fd_fib4_t const * fib ) {
88 0 : return fib->cnt;
89 0 : }
90 :
91 : ulong
92 45 : fd_fib4_free_cnt( fd_fib4_t const * fib ) {
93 45 : if( FD_UNLIKELY( fib->cnt > fib->max ) ) FD_LOG_ERR(( "invalid fib4 state: cnt>max" ));
94 45 : return fib->max - fib->cnt;
95 45 : }
96 :
97 : fd_fib4_hop_t *
98 : fd_fib4_append( fd_fib4_t * fib,
99 : uint ip4_dst,
100 : int prefix,
101 66 : uint prio ) {
102 :
103 66 : ulong const generation = fib->generation;
104 :
105 66 : if( FD_UNLIKELY( fib->cnt>=fib->max ) ) {
106 0 : FD_LOG_WARNING(( "Failed to insert route, route table is full (%lu max)", fib->max ));
107 0 : return NULL;
108 0 : }
109 :
110 66 : FD_COMPILER_MFENCE();
111 66 : fib->generation = generation+1UL;
112 66 : FD_COMPILER_MFENCE();
113 :
114 66 : ulong idx = fib->cnt;
115 66 : fib->cnt = idx+1UL;
116 :
117 66 : fd_fib4_key_t * key = fd_fib4_key_tbl( fib ) + idx;
118 66 : *key = (fd_fib4_key_t) {
119 66 : .addr = fd_uint_bswap( ip4_dst ),
120 66 : .mask = prefix>0 ? fd_uint_mask( 32-prefix, 31 ) : 0U,
121 66 : .prio = prio
122 66 : };
123 66 : fd_fib4_hop_t * entry = fd_fib4_hop_tbl( fib ) + idx;
124 :
125 66 : FD_COMPILER_MFENCE();
126 66 : fib->generation = generation+2UL;
127 66 : FD_COMPILER_MFENCE();
128 :
129 66 : return entry;
130 66 : }
131 :
132 : fd_fib4_hop_t const *
133 : fd_fib4_lookup( fd_fib4_t const * fib,
134 : fd_fib4_hop_t * out,
135 : uint ip4_dst,
136 36 : ulong flags ) {
137 36 : if( FD_UNLIKELY( flags ) ) {
138 0 : return fd_fib4_hop_tbl_const( fib ) + 0; /* dead route */
139 0 : }
140 36 : ip4_dst = fd_uint_bswap( ip4_dst );
141 36 : fd_fib4_key_t const * keys = fd_fib4_key_tbl_const( fib );
142 :
143 36 : ulong generation = FD_VOLATILE_CONST( fib->generation );
144 36 : FD_COMPILER_MFENCE();
145 :
146 36 : ulong best_idx = 0UL; /* dead route */
147 36 : int best_mask = 32; /* least specific mask (/0) */
148 36 : ulong cnt = fib->cnt;
149 228 : for( ulong j=0UL; j<cnt; j++ ) {
150 : /* FIXME consider branch variant? */
151 192 : int match = (ip4_dst & keys[j].mask)==keys[j].addr;
152 192 : int mask_bits = fd_uint_find_lsb_w_default( keys[j].mask, 32 );
153 192 : int more_specific = mask_bits< best_mask;
154 192 : int less_costly = mask_bits==best_mask && keys[j].prio<keys[best_idx].prio;
155 192 : int better = match && (more_specific || less_costly);
156 192 : if( better ) {
157 27 : best_idx = j;
158 27 : best_mask = mask_bits;
159 27 : }
160 192 : }
161 36 : *out = fd_fib4_hop_tbl_const( fib )[ best_idx ];
162 :
163 36 : FD_COMPILER_MFENCE();
164 36 : if( FD_UNLIKELY( FD_VOLATILE_CONST( fib->generation )!=generation ) ) {
165 0 : return &fd_fib4_hop_blackhole; /* torn read */
166 0 : }
167 36 : return out;
168 36 : }
169 :
170 : #if FD_HAS_HOSTED
171 :
172 : #include <errno.h>
173 : #include <stdio.h>
174 : #include "../../util/net/fd_ip4.h"
175 :
176 183 : #define WRAP_PRINT(file,str) if( FD_UNLIKELY( fputs( (str), (file) )<0 ) ) return errno
177 234 : #define WRAP_PRINTF(file,...) if( FD_UNLIKELY( fprintf( (file), __VA_ARGS__ )<0 ) ) return errno
178 :
179 : static int
180 : fd_fib4_fprintf_route( fd_fib4_key_t const * key,
181 : fd_fib4_hop_t const * hop,
182 78 : FILE * file ) {
183 :
184 78 : switch( hop->rtype ) {
185 0 : case FD_FIB4_RTYPE_UNSPEC:
186 0 : WRAP_PRINT( file, "unspecified " );
187 0 : break;
188 15 : case FD_FIB4_RTYPE_UNICAST:
189 15 : break;
190 21 : case FD_FIB4_RTYPE_LOCAL:
191 21 : WRAP_PRINT( file, "local " );
192 21 : break;
193 30 : case FD_FIB4_RTYPE_BROADCAST:
194 30 : WRAP_PRINT( file, "broadcast " );
195 30 : break;
196 30 : case FD_FIB4_RTYPE_MULTICAST:
197 0 : WRAP_PRINT( file, "multicast " );
198 0 : break;
199 0 : case FD_FIB4_RTYPE_BLACKHOLE:
200 0 : WRAP_PRINT( file, "blackhole " );
201 0 : break;
202 12 : case FD_FIB4_RTYPE_THROW:
203 12 : WRAP_PRINT( file, "throw " );
204 12 : break;
205 12 : default:
206 0 : WRAP_PRINTF( file, "invalid (%u) ", hop->rtype );
207 0 : break;
208 78 : }
209 :
210 78 : if( key->mask==0 ) {
211 18 : WRAP_PRINT( file, "default" );
212 60 : } else {
213 60 : WRAP_PRINTF( file, FD_IP4_ADDR_FMT, FD_IP4_ADDR_FMT_ARGS( fd_uint_bswap( key->addr ) ) );
214 60 : if( key->mask!=UINT_MAX ) {
215 15 : WRAP_PRINTF( file, "/%u", 32U-(uint)fd_uint_find_lsb_w_default( key->mask, 32 ) );
216 15 : }
217 60 : }
218 :
219 78 : if( hop->ip4_gw ) {
220 6 : WRAP_PRINTF( file, " via " FD_IP4_ADDR_FMT, FD_IP4_ADDR_FMT_ARGS( hop->ip4_gw ) );
221 6 : }
222 :
223 78 : if( hop->if_idx ) {
224 66 : WRAP_PRINTF( file, " dev %u", hop->if_idx );
225 66 : }
226 :
227 78 : switch( hop->scope ) {
228 54 : case 0:
229 54 : break;
230 0 : case 200:
231 0 : WRAP_PRINT( file, " scope site" );
232 0 : break;
233 15 : case 253:
234 15 : WRAP_PRINT( file, " scope link" );
235 15 : break;
236 15 : case 254:
237 9 : WRAP_PRINT( file, " scope host" );
238 9 : break;
239 9 : default:
240 0 : WRAP_PRINTF( file, " scope %u", hop->scope );
241 0 : break;
242 78 : }
243 :
244 78 : if( hop->ip4_src ) {
245 63 : WRAP_PRINTF( file, " src " FD_IP4_ADDR_FMT, FD_IP4_ADDR_FMT_ARGS( hop->ip4_src ) );
246 63 : }
247 :
248 78 : if( key->prio ) {
249 24 : WRAP_PRINTF( file, " metric %u", key->prio );
250 24 : }
251 :
252 78 : WRAP_PRINT( file, "\n" );
253 :
254 78 : return 0;
255 78 : }
256 :
257 : int
258 : fd_fib4_fprintf( fd_fib4_t const * fib,
259 12 : void * file_ ) {
260 12 : FILE * file = file_;
261 12 : fd_fib4_key_t const * key_tbl = fd_fib4_key_tbl_const( fib );
262 12 : fd_fib4_hop_t const * hop_tbl = fd_fib4_hop_tbl_const( fib );
263 :
264 12 : FD_COMPILER_MFENCE();
265 12 : ulong cnt = fib->cnt;
266 12 : ulong generation = fib->generation;
267 12 : FD_COMPILER_MFENCE();
268 :
269 90 : for( ulong j=0UL; j<cnt; j++ ) {
270 78 : FD_COMPILER_MFENCE();
271 78 : fd_fib4_key_t key = key_tbl[j];
272 78 : fd_fib4_hop_t hop = hop_tbl[j];
273 78 : FD_COMPILER_MFENCE();
274 78 : ulong cur_gen = FD_VOLATILE_CONST( fib->generation );
275 78 : FD_COMPILER_MFENCE();
276 78 : if( FD_UNLIKELY( cur_gen!=generation ) ) {
277 0 : WRAP_PRINT( file, "=== TORN READ ===\n" );
278 0 : return 0;
279 0 : }
280 78 : fd_fib4_fprintf_route( &key, &hop, file );
281 78 : }
282 :
283 12 : return 0;
284 12 : }
285 :
286 : #undef WRAP_PRINT
287 : #undef WRAP_PRINTF
288 :
289 : #endif /* FD_HAS_HOSTED */
|