Line data Source code
1 : #include "fd_fib4.h"
2 : #include "fd_fib4_private.h"
3 : #include "../../util/net/fd_ip4.h" /* for printing ip4 addrs */
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 45 : fd_fib4_align( void ) {
12 45 : return alignof(fd_fib4_t);
13 45 : }
14 :
15 : FD_FN_CONST ulong
16 : fd_fib4_footprint( ulong route_max,
17 45 : ulong route_peer_max ) {
18 45 : if( route_max==0 || route_max>UINT_MAX ||
19 45 : route_peer_max==0 || route_peer_max>UINT_MAX ) return 0UL;
20 36 : ulong elem_max = fd_fib4_hmap_get_ele_max( route_peer_max );
21 36 : ulong probe_max = fd_fib4_hmap_get_probe_max( elem_max );
22 36 : ulong lock_cnt = fd_fib4_hmap_get_lock_cnt( elem_max );
23 36 : ulong hmap_footprint = fd_fib4_hmap_footprint( elem_max, lock_cnt, probe_max );
24 36 : if( !hmap_footprint ) return 0UL;
25 :
26 36 : return FD_LAYOUT_FINI( FD_LAYOUT_APPEND( FD_LAYOUT_APPEND( FD_LAYOUT_APPEND( FD_LAYOUT_APPEND( FD_LAYOUT_APPEND( FD_LAYOUT_INIT,
27 36 : alignof(fd_fib4_t), sizeof(fd_fib4_t) ),
28 36 : alignof(fd_fib4_key_t), route_max*sizeof(fd_fib4_key_t) ),
29 36 : alignof(fd_fib4_hop_t), route_max*sizeof(fd_fib4_hop_t) ),
30 36 : fd_fib4_hmap_align(), hmap_footprint ),
31 36 : alignof(fd_fib4_hmap_entry_t), elem_max*sizeof(fd_fib4_hmap_entry_t) ),
32 36 : alignof(fd_fib4_t) );
33 36 : }
34 :
35 : void *
36 : fd_fib4_new( void * mem,
37 : ulong route_max,
38 : ulong route_peer_max,
39 24 : ulong route_peer_seed ) {
40 :
41 24 : if( FD_UNLIKELY( !mem ) ) {
42 0 : FD_LOG_WARNING(( "NULL mem" ));
43 0 : return NULL;
44 0 : }
45 24 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)mem, fd_fib4_align() ) ) ) {
46 0 : FD_LOG_WARNING(( "unaligned mem" ));
47 0 : return NULL;
48 0 : }
49 24 : if( FD_UNLIKELY( route_max==0 || route_max>UINT_MAX ) ) {
50 0 : FD_LOG_WARNING(( "invalid route_max" ));
51 0 : return NULL;
52 0 : }
53 24 : if( FD_UNLIKELY( route_peer_max==0 || route_peer_max>UINT_MAX ) ) {
54 0 : FD_LOG_WARNING(( "invalid route_peer_max" ));
55 0 : return NULL;
56 0 : }
57 :
58 24 : FD_SCRATCH_ALLOC_INIT( l, mem );
59 24 : fd_fib4_t * fib4 = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_fib4_t), sizeof(fd_fib4_t) );
60 24 : fd_fib4_key_t * keys = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_fib4_key_t), route_max*sizeof(fd_fib4_key_t) );
61 24 : fd_fib4_hop_t * vals = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_fib4_hop_t), route_max*sizeof(fd_fib4_hop_t) );
62 0 : ulong hmap_elem_max = fd_fib4_hmap_get_ele_max( route_peer_max );
63 24 : ulong hmap_probe_max = fd_fib4_hmap_get_probe_max( hmap_elem_max );
64 24 : ulong hmap_lock_cnt = fd_fib4_hmap_get_lock_cnt( hmap_elem_max );
65 24 : ulong hmap_footprint = fd_fib4_hmap_footprint( hmap_elem_max, hmap_lock_cnt, hmap_probe_max );
66 24 : FD_TEST( hmap_footprint );
67 24 : void * fib4_hmap_mem = FD_SCRATCH_ALLOC_APPEND( l, fd_fib4_hmap_align(), hmap_footprint );
68 24 : void * fib4_hmap_ele_mem = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_fib4_hmap_entry_t), hmap_elem_max*sizeof(fd_fib4_hmap_entry_t) );
69 24 : FD_TEST( fib4_hmap_mem );
70 24 : FD_TEST( fib4_hmap_ele_mem );
71 24 : FD_SCRATCH_ALLOC_FINI( l, alignof(fd_fib4_t) );
72 :
73 24 : fd_memset( fib4, 0, sizeof(fd_fib4_t) );
74 24 : fd_memset( keys, 0, route_max*sizeof(fd_fib4_key_t) );
75 24 : fd_memset( vals, 0, route_max*sizeof(fd_fib4_hop_t) );
76 24 : fd_memset( fib4_hmap_ele_mem, 0, hmap_elem_max*sizeof(fd_fib4_hmap_entry_t) );
77 :
78 24 : FD_TEST( fd_fib4_hmap_new( fib4_hmap_mem, hmap_elem_max, hmap_lock_cnt, hmap_probe_max, route_peer_seed ) );
79 :
80 24 : fib4->cnt = 1UL; // first route entry is 0.0.0.0/0
81 24 : fib4->max = route_max;
82 24 : fib4->hop_off = (ulong)vals - (ulong)fib4;
83 24 : fib4->hmap_offset = (ulong)fib4_hmap_mem - (ulong)fib4;
84 24 : fib4->hmap_elem_offset = (ulong)fib4_hmap_ele_mem - (ulong)fib4;
85 24 : fib4->hmap_max = route_peer_max;
86 24 : fib4->hmap_cnt = 0;
87 24 : keys[0].prio = UINT_MAX;
88 24 : vals[0].rtype = FD_FIB4_RTYPE_THROW;
89 :
90 24 : return fib4;
91 24 : }
92 :
93 : fd_fib4_t *
94 24 : fd_fib4_join( void * mem ) {
95 24 : return (fd_fib4_t *)mem;
96 24 : }
97 :
98 : void *
99 12 : fd_fib4_leave( fd_fib4_t * fib4 ) {
100 12 : return fib4;
101 12 : }
102 :
103 : void *
104 12 : fd_fib4_delete( void * mem ) {
105 12 : return mem;
106 12 : }
107 :
108 : void
109 69 : fd_fib4_clear( fd_fib4_t * fib4 ) {
110 69 : fib4->cnt = 1UL;
111 :
112 69 : if( fib4->hmap_cnt==0 ) return;
113 :
114 45 : fd_fib4_hmap_t hmap[1];
115 45 : FD_TEST( fd_fib4_hmap_join( hmap, fd_fib4_hmap_mem( fib4 ), fd_fib4_hmap_ele_mem( fib4 ) ) );
116 :
117 45 : fib4->hmap_cnt = 0;
118 45 : ulong elem_max = fd_fib4_hmap_get_ele_max( fib4->hmap_max );
119 45 : ulong probe_max = fd_fib4_hmap_get_probe_max( elem_max );
120 45 : ulong lock_cnt = fd_fib4_hmap_get_lock_cnt( elem_max );
121 45 : ulong seed = fd_fib4_hmap_seed( hmap );
122 45 : ulong ignored[ fd_fib4_hmap_lock_max( ) ];
123 45 : FD_TEST( fd_fib4_hmap_lock_range( hmap, 0, lock_cnt, FD_MAP_FLAG_BLOCKING, ignored )==FD_MAP_SUCCESS );
124 45 : FD_TEST( fd_fib4_hmap_new( fd_fib4_hmap_mem( fib4 ), elem_max, lock_cnt, probe_max, seed ) );
125 45 : fd_memset( fd_fib4_hmap_ele_mem( fib4 ), 0, elem_max*sizeof(fd_fib4_hmap_entry_t) );
126 45 : }
127 :
128 : FD_FN_PURE ulong
129 6 : fd_fib4_max( fd_fib4_t const * fib ) {
130 6 : return fib->max;
131 6 : }
132 :
133 : FD_FN_PURE ulong
134 6 : fd_fib4_peer_max( fd_fib4_t const * fib ) {
135 6 : return fib->hmap_max;
136 6 : }
137 :
138 : FD_FN_PURE ulong
139 39 : fd_fib4_cnt( fd_fib4_t const * fib ) {
140 39 : return fib->cnt+fib->hmap_cnt;
141 39 : }
142 :
143 : /* fd_fib4_hmap_insert adds a new entry (key=ip4_dst, value=hop) to the fib4
144 : hmap. Assume the netmask for the ip4_dst entry is 32, and ip4_dst is not 0.
145 : The insertion to fib->hmap is blocking. Return FD_MAP_SUCCESS on success,
146 : FD_MAP_ERR_FULL if the hmap is full.
147 : */
148 :
149 : static int
150 : fd_fib4_hmap_insert( fd_fib4_t * fib,
151 : uint ip4_dst,
152 285 : fd_fib4_hop_t * hop ) {
153 :
154 285 : if( FD_UNLIKELY( fib->hmap_cnt>=fib->hmap_max ) ) return FD_MAP_ERR_FULL;
155 :
156 279 : fd_fib4_hmap_t hmap[1];
157 279 : FD_TEST( fd_fib4_hmap_join( hmap, fd_fib4_hmap_mem( fib ), fd_fib4_hmap_ele_mem( fib ) ) );
158 :
159 279 : uint key = ip4_dst;
160 279 : fd_fib4_hmap_query_t query[1];
161 279 : fd_fib4_hmap_entry_t sentinel[1];
162 279 : int err = fd_fib4_hmap_prepare( hmap, &key, sentinel, query, FD_MAP_FLAG_BLOCKING );
163 279 : if( FD_UNLIKELY( err==FD_MAP_ERR_FULL ) ) return FD_MAP_ERR_FULL;
164 279 : else if ( FD_UNLIKELY( err ) ) FD_LOG_ERR(( "fd_fib4_hmap_insert failed. err: %d", err ));
165 :
166 279 : fd_fib4_hmap_entry_t * ele = fd_fib4_hmap_query_ele( query );
167 279 : ele->dst_addr = ip4_dst;
168 279 : FD_TEST( hop );
169 279 : ele->next_hop = *hop;
170 279 : fib->hmap_cnt++;
171 :
172 279 : fd_fib4_hmap_publish( query );
173 :
174 279 : return FD_MAP_SUCCESS;
175 279 : }
176 :
177 : int
178 : fd_fib4_insert( fd_fib4_t * fib,
179 : uint ip4_dst,
180 : int prefix,
181 : uint prio,
182 447 : fd_fib4_hop_t * hop ) {
183 :
184 447 : if( ip4_dst!=0 && prefix==32 ) {
185 285 : if( fd_fib4_hmap_insert( fib, ip4_dst, hop )==FD_MAP_SUCCESS ) return 1;
186 6 : FD_LOG_WARNING(( "Failed to insert /32 route " FD_IP4_ADDR_FMT " into fib4 hashmap", FD_IP4_ADDR_FMT_ARGS(ip4_dst) ));
187 6 : return 0;
188 285 : }
189 :
190 162 : ulong const generation = fib->generation;
191 :
192 162 : if( FD_UNLIKELY( fib->cnt>=fib->max ) ) {
193 6 : FD_LOG_WARNING(( "Failed to insert route " FD_IP4_ADDR_FMT ", route table is full (%lu max)", FD_IP4_ADDR_FMT_ARGS(ip4_dst), fib->max ));
194 6 : return 0;
195 6 : }
196 :
197 156 : FD_COMPILER_MFENCE();
198 156 : fib->generation = generation+1UL;
199 156 : FD_COMPILER_MFENCE();
200 :
201 156 : ulong idx = fib->cnt;
202 156 : fib->cnt = idx+1UL;
203 :
204 156 : fd_fib4_key_t * key = fd_fib4_key_tbl( fib ) + idx;
205 156 : *key = (fd_fib4_key_t) {
206 156 : .addr = fd_uint_bswap( ip4_dst ),
207 156 : .mask = prefix>0 ? fd_uint_mask( 32-prefix, 31 ) : 0U,
208 156 : .prio = prio
209 156 : };
210 156 : fd_fib4_hop_t * entry = fd_fib4_hop_tbl( fib ) + idx;
211 :
212 156 : FD_COMPILER_MFENCE();
213 156 : fib->generation = generation+2UL;
214 156 : FD_COMPILER_MFENCE();
215 :
216 156 : FD_TEST( hop );
217 156 : *entry = *hop;
218 :
219 156 : return 1;
220 156 : }
221 :
222 : fd_fib4_hop_t const *
223 : fd_fib4_lookup( fd_fib4_t const * fib,
224 : fd_fib4_hop_t * out,
225 : uint ip4_dst,
226 1476 : ulong flags ) {
227 1476 : if( FD_UNLIKELY( flags ) ) {
228 0 : return fd_fib4_hop_tbl_const( fib ) + 0; /* dead route */
229 0 : }
230 :
231 1476 : FD_TEST( out );
232 :
233 1476 : if( fib->hmap_cnt>0 ) {
234 1422 : fd_fib4_hmap_t hmap[1];
235 1422 : FD_TEST( fd_fib4_hmap_join( hmap, fd_fib4_hmap_mem( (void *)fib ), fd_fib4_hmap_ele_mem( (void *)fib ) ) );
236 1422 : uint key = ip4_dst;
237 1422 : fd_fib4_hmap_query_t query[1];
238 1422 : fd_fib4_hmap_entry_t sentinel[1];
239 1422 : int find_err = fd_fib4_hmap_query_try( hmap, &key, sentinel, query, 0 );
240 1422 : if( find_err==FD_MAP_SUCCESS ) {
241 603 : fd_fib4_hmap_entry_t const * ele = fd_fib4_hmap_query_ele_const( query );
242 603 : fd_fib4_hop_t next_hop = ele->next_hop; // speculatively save the next hop
243 603 : find_err = fd_fib4_hmap_query_test( query ); // test again
244 603 : if( FD_UNLIKELY( find_err ) ) {
245 0 : return &fd_fib4_hop_blackhole;
246 0 : }
247 603 : *out = next_hop;
248 603 : return out;
249 819 : } else if( FD_UNLIKELY( find_err!=FD_MAP_ERR_KEY ) ) {
250 0 : return &fd_fib4_hop_blackhole;
251 0 : }
252 : // Can't find a match in the fib4 hashmap. Look up in the routing table.
253 1422 : }
254 :
255 873 : ip4_dst = fd_uint_bswap( ip4_dst );
256 873 : fd_fib4_key_t const * keys = fd_fib4_key_tbl_const( fib );
257 :
258 873 : ulong generation = FD_VOLATILE_CONST( fib->generation );
259 873 : FD_COMPILER_MFENCE();
260 :
261 873 : ulong best_idx = 0UL; /* dead route */
262 873 : int best_mask = 32; /* least specific mask (/0) */
263 873 : ulong cnt = fib->cnt;
264 2964 : for( ulong j=0UL; j<cnt; j++ ) {
265 : /* FIXME consider branch variant? */
266 2091 : int match = (ip4_dst & keys[j].mask)==keys[j].addr;
267 2091 : int mask_bits = fd_uint_find_lsb_w_default( keys[j].mask, 32 );
268 2091 : int more_specific = mask_bits< best_mask;
269 2091 : int less_costly = mask_bits==best_mask && keys[j].prio<keys[best_idx].prio;
270 2091 : int better = match && (more_specific || less_costly);
271 2091 : if( better ) {
272 288 : best_idx = j;
273 288 : best_mask = mask_bits;
274 288 : }
275 2091 : }
276 873 : *out = fd_fib4_hop_tbl_const( fib )[ best_idx ];
277 :
278 873 : FD_COMPILER_MFENCE();
279 873 : if( FD_UNLIKELY( FD_VOLATILE_CONST( fib->generation )!=generation ) ) {
280 0 : return &fd_fib4_hop_blackhole; /* torn read */
281 0 : }
282 873 : return out;
283 873 : }
284 :
285 : #if FD_HAS_HOSTED
286 :
287 : #include <errno.h>
288 : #include <stdio.h>
289 : #include "../../util/net/fd_ip4.h"
290 :
291 159 : #define WRAP_PRINT(file,str) if( FD_UNLIKELY( fputs( (str), (file) )<0 ) ) return errno
292 231 : #define WRAP_PRINTF(file,...) if( FD_UNLIKELY( fprintf( (file), __VA_ARGS__ )<0 ) ) return errno
293 :
294 : static int
295 : fd_fib4_fprintf_route( fd_fib4_key_t const * key,
296 : fd_fib4_hop_t const * hop,
297 66 : FILE * file ) {
298 :
299 66 : switch( hop->rtype ) {
300 0 : case FD_FIB4_RTYPE_UNSPEC:
301 0 : WRAP_PRINT( file, "unspecified " );
302 0 : break;
303 15 : case FD_FIB4_RTYPE_UNICAST:
304 15 : break;
305 21 : case FD_FIB4_RTYPE_LOCAL:
306 21 : WRAP_PRINT( file, "local " );
307 21 : break;
308 21 : case FD_FIB4_RTYPE_BROADCAST:
309 18 : WRAP_PRINT( file, "broadcast " );
310 18 : break;
311 18 : case FD_FIB4_RTYPE_MULTICAST:
312 0 : WRAP_PRINT( file, "multicast " );
313 0 : break;
314 0 : case FD_FIB4_RTYPE_BLACKHOLE:
315 0 : WRAP_PRINT( file, "blackhole " );
316 0 : break;
317 12 : case FD_FIB4_RTYPE_THROW:
318 12 : WRAP_PRINT( file, "throw " );
319 12 : break;
320 12 : default:
321 0 : WRAP_PRINTF( file, "invalid (%u) ", hop->rtype );
322 0 : break;
323 66 : }
324 :
325 66 : if( key->mask==0 ) {
326 18 : WRAP_PRINT( file, "default" );
327 48 : } else {
328 48 : WRAP_PRINTF( file, FD_IP4_ADDR_FMT, FD_IP4_ADDR_FMT_ARGS( fd_uint_bswap( key->addr ) ) );
329 48 : if( key->mask!=UINT_MAX ) {
330 48 : WRAP_PRINTF( file, "/%u", 32U-(uint)fd_uint_find_lsb_w_default( key->mask, 32 ) );
331 48 : }
332 48 : }
333 :
334 66 : if( hop->ip4_gw ) {
335 6 : WRAP_PRINTF( file, " via " FD_IP4_ADDR_FMT, FD_IP4_ADDR_FMT_ARGS( hop->ip4_gw ) );
336 6 : }
337 :
338 66 : if( hop->if_idx ) {
339 54 : WRAP_PRINTF( file, " dev %u", hop->if_idx );
340 54 : }
341 :
342 66 : switch( hop->scope ) {
343 42 : case 0:
344 42 : break;
345 0 : case 200:
346 0 : WRAP_PRINT( file, " scope site" );
347 0 : break;
348 15 : case 253:
349 15 : WRAP_PRINT( file, " scope link" );
350 15 : break;
351 15 : case 254:
352 9 : WRAP_PRINT( file, " scope host" );
353 9 : break;
354 9 : default:
355 0 : WRAP_PRINTF( file, " scope %u", hop->scope );
356 0 : break;
357 66 : }
358 :
359 66 : if( hop->ip4_src ) {
360 54 : WRAP_PRINTF( file, " src " FD_IP4_ADDR_FMT, FD_IP4_ADDR_FMT_ARGS( hop->ip4_src ) );
361 54 : }
362 :
363 66 : if( key->prio ) {
364 21 : WRAP_PRINTF( file, " metric %u", key->prio );
365 21 : }
366 :
367 66 : WRAP_PRINT( file, "\n" );
368 :
369 66 : return 0;
370 66 : }
371 :
372 : int
373 : fd_fib4_fprintf( fd_fib4_t const * fib,
374 12 : void * file_ ) {
375 12 : FILE * file = file_;
376 12 : fd_fib4_key_t const * key_tbl = fd_fib4_key_tbl_const( fib );
377 12 : fd_fib4_hop_t const * hop_tbl = fd_fib4_hop_tbl_const( fib );
378 :
379 12 : FD_COMPILER_MFENCE();
380 12 : ulong cnt = fib->cnt;
381 12 : ulong generation = fib->generation;
382 12 : FD_COMPILER_MFENCE();
383 :
384 51 : for( ulong j=0UL; j<cnt; j++ ) {
385 39 : FD_COMPILER_MFENCE();
386 39 : fd_fib4_key_t key = key_tbl[j];
387 39 : fd_fib4_hop_t hop = hop_tbl[j];
388 39 : FD_COMPILER_MFENCE();
389 39 : ulong cur_gen = FD_VOLATILE_CONST( fib->generation );
390 39 : FD_COMPILER_MFENCE();
391 39 : if( FD_UNLIKELY( cur_gen!=generation ) ) {
392 0 : WRAP_PRINT( file, "=== TORN READ ===\n" );
393 0 : return 0;
394 0 : }
395 39 : fd_fib4_fprintf_route( &key, &hop, file );
396 39 : }
397 :
398 : /* Attempt to print the hashmap. */
399 12 : fd_fib4_hmap_t hmap[1];
400 12 : fd_fib4_hmap_entry_t * elems = fd_fib4_hmap_ele_mem( (fd_fib4_t *)fib );
401 12 : FD_TEST( fd_fib4_hmap_join( hmap, fd_fib4_hmap_mem( (fd_fib4_t *)fib ), elems ) );
402 12 : ulong elem_max = fd_fib4_hmap_get_ele_max( fib->hmap_max );
403 3276 : for( ulong i=0; i<elem_max; i++ ) {
404 3264 : ulong * lock = hmap->lock+fd_fib4_hmap_ele_lock( hmap, i );
405 3264 : fd_fib4_hmap_entry_t e;
406 3264 : for(;;) {
407 3264 : ulong ver = fd_fib4_hmap_private_try( lock );
408 3264 : e = FD_VOLATILE_CONST( elems[ i ] );
409 3264 : if( FD_LIKELY( fd_fib4_hmap_private_test( lock, 1UL, &ver, 0UL, 1UL )==FD_MAP_SUCCESS ) ) break;
410 3264 : }
411 3264 : if( e.dst_addr!=0 ) {
412 27 : fd_fib4_key_t key;
413 27 : key.addr = fd_uint_bswap( e.dst_addr );
414 27 : key.mask = 31;
415 27 : key.prio = 0;
416 27 : fd_fib4_fprintf_route( &key, &e.next_hop, file );
417 27 : }
418 3264 : }
419 :
420 12 : return 0;
421 12 : }
422 :
423 : #undef WRAP_PRINT
424 : #undef WRAP_PRINTF
425 :
426 : #endif /* FD_HAS_HOSTED */
|
