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