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 27 : fd_fib4_align( void ) {
12 27 : return alignof(fd_fib4_t);
13 27 : }
14 :
15 : FD_FN_CONST ulong
16 : fd_fib4_footprint( ulong route_max,
17 33 : ulong route_peer_max ) {
18 33 : if( route_max==0 || route_max>UINT_MAX ||
19 33 : route_peer_max==0 || route_peer_max>UINT_MAX ) return 0UL;
20 24 : ulong elem_max = fd_fib4_hmap_get_ele_max( route_peer_max );
21 24 : ulong probe_max = fd_fib4_hmap_get_probe_max( elem_max );
22 24 : ulong lock_cnt = fd_fib4_hmap_get_lock_cnt( elem_max );
23 24 : ulong hmap_footprint = fd_fib4_hmap_footprint( elem_max, lock_cnt, probe_max );
24 24 : if( !hmap_footprint ) return 0UL;
25 :
26 24 : return FD_LAYOUT_FINI( FD_LAYOUT_APPEND( FD_LAYOUT_APPEND( FD_LAYOUT_APPEND( FD_LAYOUT_APPEND( FD_LAYOUT_APPEND( FD_LAYOUT_INIT,
27 24 : alignof(fd_fib4_t), sizeof(fd_fib4_t) ),
28 24 : alignof(fd_fib4_key_t), route_max*sizeof(fd_fib4_key_t) ),
29 24 : alignof(fd_fib4_hop_t), route_max*sizeof(fd_fib4_hop_t) ),
30 24 : fd_fib4_hmap_align(), hmap_footprint ),
31 24 : alignof(fd_fib4_hmap_entry_t), elem_max*sizeof(fd_fib4_hmap_entry_t) ),
32 24 : alignof(fd_fib4_t) );
33 24 : }
34 :
35 : void *
36 : fd_fib4_new( void * mem,
37 : ulong route_max,
38 : ulong route_peer_max,
39 18 : ulong route_peer_seed ) {
40 :
41 18 : if( FD_UNLIKELY( !mem ) ) {
42 0 : FD_LOG_WARNING(( "NULL mem" ));
43 0 : return NULL;
44 0 : }
45 18 : 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 18 : 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 18 : 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 18 : FD_SCRATCH_ALLOC_INIT( l, mem );
59 18 : fd_fib4_t * fib4 = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_fib4_t), sizeof(fd_fib4_t) );
60 18 : fd_fib4_key_t * keys = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_fib4_key_t), route_max*sizeof(fd_fib4_key_t) );
61 18 : 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 18 : ulong hmap_probe_max = fd_fib4_hmap_get_probe_max( hmap_elem_max );
64 18 : ulong hmap_lock_cnt = fd_fib4_hmap_get_lock_cnt( hmap_elem_max );
65 18 : ulong hmap_footprint = fd_fib4_hmap_footprint( hmap_elem_max, hmap_lock_cnt, hmap_probe_max );
66 18 : FD_TEST( hmap_footprint );
67 18 : void * fib4_hmap_mem = FD_SCRATCH_ALLOC_APPEND( l, fd_fib4_hmap_align(), hmap_footprint );
68 18 : 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 18 : FD_TEST( fib4_hmap_mem );
70 18 : FD_TEST( fib4_hmap_ele_mem );
71 18 : FD_SCRATCH_ALLOC_FINI( l, alignof(fd_fib4_t) );
72 :
73 18 : fd_memset( fib4, 0, sizeof(fd_fib4_t) );
74 18 : fd_memset( keys, 0, route_max*sizeof(fd_fib4_key_t) );
75 18 : fd_memset( vals, 0, route_max*sizeof(fd_fib4_hop_t) );
76 18 : fd_memset( fib4_hmap_ele_mem, 0, hmap_elem_max*sizeof(fd_fib4_hmap_entry_t) );
77 :
78 18 : FD_TEST( fd_fib4_hmap_new( fib4_hmap_mem, hmap_elem_max, hmap_lock_cnt, hmap_probe_max, route_peer_seed ) );
79 :
80 18 : fib4->cnt = 1UL; // first route entry is 0.0.0.0/0
81 18 : fib4->max = route_max;
82 18 : fib4->hop_off = (ulong)vals - (ulong)fib4;
83 18 : fib4->hmap_offset = (ulong)fib4_hmap_mem - (ulong)fib4;
84 18 : fib4->hmap_elem_offset = (ulong)fib4_hmap_ele_mem - (ulong)fib4;
85 18 : fib4->hmap_max = route_peer_max;
86 18 : fib4->hmap_cnt = 0;
87 18 : keys[0].prio = UINT_MAX;
88 18 : vals[0].rtype = FD_FIB4_RTYPE_THROW;
89 :
90 18 : return fib4;
91 18 : }
92 :
93 : fd_fib4_t *
94 18 : fd_fib4_join( void * mem ) {
95 18 : return (fd_fib4_t *)mem;
96 18 : }
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 255 : fd_fib4_hop_t * hop ) {
153 :
154 255 : if( FD_UNLIKELY( fib->hmap_cnt>=fib->hmap_max ) ) return FD_MAP_ERR_FULL;
155 :
156 249 : fd_fib4_hmap_t hmap[1];
157 249 : FD_TEST( fd_fib4_hmap_join( hmap, fd_fib4_hmap_mem( fib ), fd_fib4_hmap_ele_mem( fib ) ) );
158 :
159 249 : uint key = ip4_dst;
160 249 : fd_fib4_hmap_query_t query[1];
161 249 : fd_fib4_hmap_entry_t sentinel[1];
162 249 : int err = fd_fib4_hmap_prepare( hmap, &key, sentinel, query, FD_MAP_FLAG_BLOCKING );
163 249 : if( FD_UNLIKELY( err==FD_MAP_ERR_FULL ) ) return FD_MAP_ERR_FULL;
164 249 : else if ( FD_UNLIKELY( err ) ) FD_LOG_ERR(( "fd_fib4_hmap_insert failed. err: %d", err ));
165 :
166 249 : fd_fib4_hmap_entry_t * ele = fd_fib4_hmap_query_ele( query );
167 249 : ele->dst_addr = ip4_dst;
168 249 : FD_TEST( hop );
169 249 : fd_memcpy( &ele->next_hop, hop, sizeof(fd_fib4_hop_t) );
170 249 : fib->hmap_cnt += 1;
171 :
172 249 : fd_fib4_hmap_publish( query );
173 :
174 249 : return FD_MAP_SUCCESS;
175 249 : }
176 :
177 : int
178 : fd_fib4_insert( fd_fib4_t * fib,
179 : uint ip4_dst,
180 : int prefix,
181 : uint prio,
182 411 : fd_fib4_hop_t * hop ) {
183 :
184 411 : if( ip4_dst!=0 && prefix==32 ) {
185 255 : 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 255 : }
189 :
190 156 : ulong const generation = fib->generation;
191 :
192 156 : 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 150 : FD_COMPILER_MFENCE();
198 150 : fib->generation = generation+1UL;
199 150 : FD_COMPILER_MFENCE();
200 :
201 150 : ulong idx = fib->cnt;
202 150 : fib->cnt = idx+1UL;
203 :
204 150 : fd_fib4_key_t * key = fd_fib4_key_tbl( fib ) + idx;
205 150 : *key = (fd_fib4_key_t) {
206 150 : .addr = fd_uint_bswap( ip4_dst ),
207 150 : .mask = prefix>0 ? fd_uint_mask( 32-prefix, 31 ) : 0U,
208 150 : .prio = prio
209 150 : };
210 150 : fd_fib4_hop_t * entry = fd_fib4_hop_tbl( fib ) + idx;
211 :
212 150 : FD_COMPILER_MFENCE();
213 150 : fib->generation = generation+2UL;
214 150 : FD_COMPILER_MFENCE();
215 :
216 150 : FD_TEST( hop );
217 150 : fd_memcpy( entry, hop, sizeof(fd_fib4_hop_t) );
218 :
219 150 : return 1;
220 150 : }
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 438 : ulong flags ) {
227 438 : if( FD_UNLIKELY( flags ) ) {
228 0 : return fd_fib4_hop_tbl_const( fib ) + 0; /* dead route */
229 0 : }
230 :
231 438 : FD_TEST( out );
232 :
233 438 : if( fib->hmap_cnt>0 ) {
234 390 : fd_fib4_hmap_t hmap[1];
235 390 : FD_TEST( fd_fib4_hmap_join( hmap, fd_fib4_hmap_mem( (void *)fib ), fd_fib4_hmap_ele_mem( (void *)fib ) ) );
236 390 : uint key = ip4_dst;
237 390 : fd_fib4_hmap_query_t query[1];
238 390 : fd_fib4_hmap_entry_t sentinel[1];
239 390 : int find_err = fd_fib4_hmap_query_try( hmap, &key, sentinel, query, 0 );
240 390 : if( find_err==FD_MAP_SUCCESS ) {
241 213 : fd_fib4_hmap_entry_t const * ele = fd_fib4_hmap_query_ele_const( query );
242 213 : fd_fib4_hop_t next_hop = ele->next_hop; // speculatively save the next hop
243 213 : find_err = fd_fib4_hmap_query_test( query ); // test again
244 213 : if( FD_UNLIKELY( find_err ) ) {
245 0 : return &fd_fib4_hop_blackhole;
246 0 : }
247 213 : fd_memcpy( out, &next_hop, sizeof( fd_fib4_hop_t ) );
248 213 : return out;
249 213 : } 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 390 : }
254 :
255 225 : ip4_dst = fd_uint_bswap( ip4_dst );
256 225 : fd_fib4_key_t const * keys = fd_fib4_key_tbl_const( fib );
257 :
258 225 : ulong generation = FD_VOLATILE_CONST( fib->generation );
259 225 : FD_COMPILER_MFENCE();
260 :
261 225 : ulong best_idx = 0UL; /* dead route */
262 225 : int best_mask = 32; /* least specific mask (/0) */
263 225 : ulong cnt = fib->cnt;
264 1479 : for( ulong j=0UL; j<cnt; j++ ) {
265 : /* FIXME consider branch variant? */
266 1254 : int match = (ip4_dst & keys[j].mask)==keys[j].addr;
267 1254 : int mask_bits = fd_uint_find_lsb_w_default( keys[j].mask, 32 );
268 1254 : int more_specific = mask_bits< best_mask;
269 1254 : int less_costly = mask_bits==best_mask && keys[j].prio<keys[best_idx].prio;
270 1254 : int better = match && (more_specific || less_costly);
271 1254 : if( better ) {
272 162 : best_idx = j;
273 162 : best_mask = mask_bits;
274 162 : }
275 1254 : }
276 225 : *out = fd_fib4_hop_tbl_const( fib )[ best_idx ];
277 :
278 225 : FD_COMPILER_MFENCE();
279 225 : if( FD_UNLIKELY( FD_VOLATILE_CONST( fib->generation )!=generation ) ) {
280 0 : return &fd_fib4_hop_blackhole; /* torn read */
281 0 : }
282 225 : return out;
283 225 : }
284 :
285 : #if FD_HAS_HOSTED
286 :
287 : #include <errno.h>
288 : #include <stdio.h>
289 : #include "../../util/net/fd_ip4.h"
290 :
291 171 : #define WRAP_PRINT(file,str) if( FD_UNLIKELY( fputs( (str), (file) )<0 ) ) return errno
292 255 : #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 72 : FILE * file ) {
298 :
299 72 : 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 24 : case FD_FIB4_RTYPE_BROADCAST:
309 24 : WRAP_PRINT( file, "broadcast " );
310 24 : break;
311 24 : 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 72 : }
324 :
325 72 : if( key->mask==0 ) {
326 18 : WRAP_PRINT( file, "default" );
327 54 : } else {
328 54 : WRAP_PRINTF( file, FD_IP4_ADDR_FMT, FD_IP4_ADDR_FMT_ARGS( fd_uint_bswap( key->addr ) ) );
329 54 : if( key->mask!=UINT_MAX ) {
330 54 : WRAP_PRINTF( file, "/%u", 32U-(uint)fd_uint_find_lsb_w_default( key->mask, 32 ) );
331 54 : }
332 54 : }
333 :
334 72 : 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 72 : if( hop->if_idx ) {
339 60 : WRAP_PRINTF( file, " dev %u", hop->if_idx );
340 60 : }
341 :
342 72 : switch( hop->scope ) {
343 48 : case 0:
344 48 : 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 72 : }
358 :
359 72 : if( hop->ip4_src ) {
360 60 : WRAP_PRINTF( file, " src " FD_IP4_ADDR_FMT, FD_IP4_ADDR_FMT_ARGS( hop->ip4_src ) );
361 60 : }
362 :
363 72 : if( key->prio ) {
364 21 : WRAP_PRINTF( file, " metric %u", key->prio );
365 21 : }
366 :
367 72 : WRAP_PRINT( file, "\n" );
368 :
369 72 : return 0;
370 72 : }
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 12 : ulong lock_cnt = fd_fib4_hmap_get_lock_cnt( elem_max );
404 12 : ulong ignored[ fd_fib4_hmap_lock_max( ) ];
405 12 : FD_TEST( fd_fib4_hmap_lock_range( hmap, 0, lock_cnt, FD_MAP_FLAG_BLOCKING | FD_MAP_FLAG_RDONLY, ignored )==FD_MAP_SUCCESS );
406 :
407 : // loop through the hmap elements
408 3276 : for( ulong i=0; i<elem_max; i++ ) {
409 3264 : if( elems[i].dst_addr!=0 ) {
410 33 : fd_fib4_key_t key;
411 33 : key.addr = fd_uint_bswap( elems[i].dst_addr );
412 33 : key.mask = 31;
413 33 : key.prio = 0;
414 33 : fd_fib4_fprintf_route( &key, &elems[i].next_hop, file );
415 33 : }
416 3264 : }
417 :
418 12 : fd_fib4_hmap_unlock_range( hmap, 0, lock_cnt, ignored );
419 :
420 12 : return 0;
421 12 : }
422 :
423 : #undef WRAP_PRINT
424 : #undef WRAP_PRINTF
425 :
426 : #endif /* FD_HAS_HOSTED */
|
