LCOV - code coverage report
Current view: top level - waltz/ip - fd_fib4.c (source / functions) Hit Total Coverage
Test: cov.lcov Lines: 163 203 80.3 %
Date: 2025-03-20 12:08:36 Functions: 12 14 85.7 %

          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 */

Generated by: LCOV version 1.14