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