Line data    Source code

       1             : #include "fd_store.h"
       2             : #include "../../flamenco/fd_flamenco_base.h"
       3             : 
       4             : void *
       5           3 : fd_store_new( void * shmem, ulong fec_max, ulong seed ) {
       6             : 
       7           3 :   if( FD_UNLIKELY( !shmem ) ) {
       8           0 :     FD_LOG_WARNING(( "NULL mem" ));
       9           0 :     return NULL;
      10           0 :   }
      11             : 
      12           3 :   if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_store_align() ) ) ) {
      13           0 :     FD_LOG_WARNING(( "misaligned mem" ));
      14           0 :     return NULL;
      15           0 :   }
      16             : 
      17           3 :   ulong footprint = fd_store_footprint( fec_max );
      18           3 :   if( FD_UNLIKELY( !footprint ) ) {
      19           0 :     FD_LOG_WARNING(( "bad fec_max (%lu)", fec_max ));
      20           0 :     return NULL;
      21           0 :   }
      22             : 
      23           3 :   fd_wksp_t * wksp = fd_wksp_containing( shmem );
      24           3 :   if( FD_UNLIKELY( !wksp ) ) {
      25           0 :     FD_LOG_WARNING(( "shmem must be part of a workspace" ));
      26           0 :     return NULL;
      27           0 :   }
      28             : 
      29           3 :   fd_memset( shmem, 0, footprint );
      30             : 
      31           3 :   FD_SCRATCH_ALLOC_INIT( l, shmem );
      32           3 :   fd_store_t * store = FD_SCRATCH_ALLOC_APPEND( l, fd_store_align(),      sizeof( fd_store_t )               );
      33           3 :   void *       pool  = FD_SCRATCH_ALLOC_APPEND( l, fd_store_pool_align(), fd_store_pool_footprint( fec_max ) );
      34           3 :   void *       map   = FD_SCRATCH_ALLOC_APPEND( l, fd_store_map_align(),  fd_store_map_footprint ( fec_max ) );
      35           3 :   FD_TEST( FD_SCRATCH_ALLOC_FINI( l, fd_store_align() ) == (ulong)shmem + footprint );
      36             : 
      37           3 :   store->seed        = seed;
      38           3 :   store->root        = ULONG_MAX;
      39           3 :   store->store_gaddr = fd_wksp_gaddr_fast( wksp, store                                                         );
      40           3 :   store->pool_gaddr  = fd_wksp_gaddr_fast( wksp, fd_store_pool_join( fd_store_pool_new( pool, fec_max      ) ) );
      41           3 :   store->map_gaddr   = fd_wksp_gaddr_fast( wksp, fd_store_map_join ( fd_store_map_new ( map, fec_max, seed ) ) );
      42             : 
      43           3 :   FD_COMPILER_MFENCE();
      44           3 :   FD_VOLATILE( store->magic ) = FD_STORE_MAGIC;
      45           3 :   FD_COMPILER_MFENCE();
      46             : 
      47           3 :   return shmem;
      48           3 : }
      49             : 
      50             : fd_store_t *
      51           3 : fd_store_join( void * shstore ) {
      52           3 :   fd_store_t * store = (fd_store_t *)shstore;
      53             : 
      54           3 :   if( FD_UNLIKELY( !store ) ) {
      55           0 :     FD_LOG_WARNING(( "NULL store" ));
      56           0 :     return NULL;
      57           0 :   }
      58             : 
      59           3 :   if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)store, fd_store_align() ) ) ) {
      60           0 :     FD_LOG_WARNING(( "misaligned store" ));
      61           0 :     return NULL;
      62           0 :   }
      63             : 
      64           3 :   fd_wksp_t * wksp = fd_wksp_containing( store );
      65           3 :   if( FD_UNLIKELY( !wksp ) ) {
      66           0 :     FD_LOG_WARNING(( "store must be part of a workspace" ));
      67           0 :     return NULL;
      68           0 :   }
      69             : 
      70           3 :   if( FD_UNLIKELY( store->magic!=FD_STORE_MAGIC ) ) {
      71           0 :     FD_LOG_WARNING(( "bad magic" ));
      72           0 :     return NULL;
      73           0 :   }
      74             : 
      75           3 :   return store;
      76           3 : }
      77             : 
      78             : void *
      79           3 : fd_store_leave( fd_store_t const * store ) {
      80             : 
      81           3 :   if( FD_UNLIKELY( !store ) ) {
      82           0 :     FD_LOG_WARNING(( "NULL store" ));
      83           0 :     return NULL;
      84           0 :   }
      85             : 
      86           3 :   return (void *)store;
      87           3 : }
      88             : 
      89             : void *
      90           3 : fd_store_delete( void * store ) {
      91             : 
      92           3 :   if( FD_UNLIKELY( !store ) ) {
      93           0 :     FD_LOG_WARNING(( "NULL store" ));
      94           0 :     return NULL;
      95           0 :   }
      96             : 
      97           3 :   if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)store, fd_store_align() ) ) ) {
      98           0 :     FD_LOG_WARNING(( "misaligned store" ));
      99           0 :     return NULL;
     100           0 :   }
     101             : 
     102           3 :   return store;
     103           3 : }
     104             : 
     105             : fd_store_fec_t *
     106             : fd_store_insert( fd_store_t * store,
     107             :                  fd_hash_t  * merkle_root,
     108             :                  uchar      * data,
     109          21 :                  ulong        data_sz ) {
     110             : 
     111             : # if FD_STORE_USE_HANDHOLDING /* FIXME eviction? max bound guaranteed for worst-case? */
     112          21 :   if( FD_UNLIKELY( !fd_store_pool_free( fd_store_pool( store ) ) ) ) { FD_LOG_WARNING(( "store full"                                                              )); return NULL; }
     113          21 :   if( FD_UNLIKELY( data_sz > FD_STORE_DATA_MAX                   ) ) { FD_LOG_WARNING(( "data_sz %lu > FD_STORE_DATA_MAX", data_sz                                )); return NULL; }
     114          21 :   if( FD_UNLIKELY( fd_store_query_const( store, merkle_root )    ) ) { FD_LOG_WARNING(( "merkle root %s already in store", FD_BASE58_ENC_32_ALLOCA( merkle_root ) )); return NULL; }
     115          21 : # endif
     116             : 
     117          21 :   fd_store_fec_t * pool = fd_store_pool( store );
     118          21 :   ulong            null = fd_store_pool_idx_null( pool );
     119          21 :   fd_store_fec_t * fec  = fd_store_pool_ele_acquire( pool );
     120          21 :   fec->key              = *merkle_root;
     121          21 :   fec->next             = null;
     122          21 :   fec->parent           = null;
     123          21 :   fec->child            = null;
     124          21 :   fec->sibling          = null;
     125          21 :   fec->data_sz          = data_sz;
     126          21 :   memcpy( fec->data, data, data_sz );
     127          21 :   fd_store_map_ele_insert( fd_store_map( store ), fec, fd_store_pool( store ) );
     128          21 :   if( FD_UNLIKELY( store->root == null ) ) store->root = fd_store_pool_idx( pool, fec );
     129          21 :   return fec;
     130          21 : }
     131             : 
     132             : fd_store_fec_t *
     133          18 : fd_store_link( fd_store_t * store, fd_hash_t * merkle_root, fd_hash_t * chained_merkle_root ) {
     134             : 
     135          18 : # if FD_STORE_USE_HANDHOLDING
     136          18 :   if( FD_UNLIKELY( !fd_store_query_const( store, merkle_root         ) ) ) { FD_LOG_WARNING(( "missing merkle root %s",         FD_BASE58_ENC_32_ALLOCA( merkle_root         ) ) ); return NULL; }
     137          18 :   if( FD_UNLIKELY( !fd_store_query_const( store, chained_merkle_root ) ) ) { FD_LOG_WARNING(( "missing chained merkle root %s", FD_BASE58_ENC_32_ALLOCA( chained_merkle_root ) ) ); return NULL; }
     138          18 : # endif
     139             : 
     140          18 :   fd_store_map_t * map    = fd_store_map( store );
     141          18 :   fd_store_fec_t * pool   = fd_store_pool( store );
     142          18 :   ulong            null   = fd_store_pool_idx_null( pool );
     143          18 :   fd_store_fec_t * parent = fd_store_map_ele_query( map, chained_merkle_root, NULL, pool );
     144          18 :   fd_store_fec_t * child  = fd_store_map_ele_query( map, merkle_root, NULL, pool );
     145             : 
     146          18 :   child->parent = fd_store_pool_idx( pool, parent );
     147          18 :   if( FD_LIKELY( parent->child == null ) ) {
     148          15 :     parent->child = fd_store_pool_idx( pool, child ); /* set as left-child. */
     149          15 :   } else {
     150           3 :     fd_store_fec_t * curr = fd_store_pool_ele( pool, parent->child );
     151           3 :     while( curr->sibling != null ) curr = fd_store_pool_ele( pool, curr->sibling );
     152           3 :     curr->sibling = fd_store_pool_idx( pool, child ); /* set as right-sibling. */
     153           3 :   }
     154          18 :   return child;
     155          18 : }
     156             : 
     157             : fd_store_fec_t *
     158             : fd_store_publish( fd_store_t  * store,
     159           3 :                   fd_hash_t   * merkle_root ) {
     160             : 
     161           3 :   fd_store_map_t * map  = fd_store_map( store );
     162           3 :   fd_store_fec_t * pool = fd_store_pool( store );
     163           3 :   ulong            null = fd_store_pool_idx_null( pool );
     164           3 :   fd_store_fec_t * oldr = fd_store_root( store );
     165           3 :   fd_store_fec_t * newr = fd_store_map_ele_query( map, merkle_root, NULL, pool );
     166             : 
     167           3 : # if FD_STORE_USE_HANDHOLDING
     168           3 :   if( FD_UNLIKELY( !newr ) ) { FD_LOG_WARNING(( "merkle root %s not found", FD_BASE58_ENC_32_ALLOCA( merkle_root ) )); return NULL; }
     169           3 : # endif
     170             : 
     171             :   /* First, remove the previous root, and push it as the first element
     172             :      of the BFS queue. */
     173             : 
     174           3 :   fd_store_fec_t * head = fd_store_map_ele_remove( map, &oldr->key, NULL, pool );
     175           3 :   head->next            = null; /* clear map next */
     176           3 :   fd_store_fec_t * tail = head; /* tail of BFS queue */
     177             : 
     178             :   /* Second, BFS down the tree, pruning all of root's ancestors and also
     179             :      any descendants of those ancestors. */
     180             : 
     181          18 :   while( FD_LIKELY( head ) ) {
     182          15 :     fd_store_fec_t * child = fd_store_pool_ele( pool, head->child );          /* left-child */
     183          30 :     while( FD_LIKELY( child ) ) {                                             /* iterate over children */
     184          15 :       if( FD_LIKELY( child != newr ) ) {                                      /* stop at new root */
     185          12 :         tail->next = fd_store_map_idx_remove( map, &child->key, null, pool ); /* remove node from map to reuse `.next` */
     186          12 :         tail       = fd_store_pool_ele( pool, tail->next );                   /* push onto BFS queue (so descendants can be pruned) */
     187          12 :         tail->next = null;                                                    /* clear map next */
     188          12 :       }
     189          15 :       child = fd_store_pool_ele( pool, child->sibling ); /* right-sibling */
     190          15 :     }
     191          15 :     fd_store_fec_t * next = fd_store_pool_ele( pool, head->next ); /* pophead */
     192          15 :     fd_store_pool_ele_release( pool, head );                       /* release */
     193          15 :     head = next;                                                   /* advance */
     194          15 :   }
     195           3 :   newr->parent = null;                            /* unlink old root */
     196           3 :   store->root  = fd_store_pool_idx( pool, newr ); /* replace with new root */
     197           3 :   return newr;
     198           3 : }