Line data Source code
1 : #include "fd_tower_forks.h"
2 : #include "fd_tower.h"
3 :
4 : void *
5 9 : fd_forks_new( void * shmem, ulong slot_max, ulong voter_max ) {
6 9 : if( FD_UNLIKELY( !shmem ) ) {
7 0 : FD_LOG_WARNING(( "NULL mem" ));
8 0 : return NULL;
9 0 : }
10 :
11 9 : fd_wksp_t * wksp = fd_wksp_containing( shmem );
12 9 : if( FD_UNLIKELY( !wksp ) ) {
13 0 : FD_LOG_WARNING(( "shmem must be part of a workspace" ));
14 0 : return NULL;
15 0 : }
16 :
17 9 : ulong footprint = fd_forks_footprint( slot_max, voter_max );
18 9 : if( FD_UNLIKELY( !footprint ) ) {
19 0 : FD_LOG_WARNING(( "bad slot_max (%lu)", slot_max ));
20 0 : return NULL;
21 0 : }
22 : /* verify aligned to fd_forks_align() */
23 9 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_forks_align() ) ) ) {
24 0 : FD_LOG_WARNING(( "misaligned mem" ));
25 0 : return NULL;
26 0 : }
27 :
28 9 : ulong interval_max = fd_ulong_pow2_up( FD_LOCKOUT_ENTRY_MAX*slot_max*voter_max );
29 9 : int lg_slot_max = fd_ulong_find_msb( fd_ulong_pow2_up( slot_max ) ) + 1;
30 :
31 9 : FD_SCRATCH_ALLOC_INIT( l, shmem );
32 9 : fd_forks_t * forks = FD_SCRATCH_ALLOC_APPEND( l, fd_forks_align(), sizeof(fd_forks_t) );
33 9 : void * tower_forks = FD_SCRATCH_ALLOC_APPEND( l, fd_tower_forks_align(), fd_tower_forks_footprint ( lg_slot_max ) );
34 9 : void * leaves_map = FD_SCRATCH_ALLOC_APPEND( l, fd_tower_leaves_map_align(), fd_tower_leaves_map_footprint ( slot_max ) );
35 9 : void * leaves_dlist = FD_SCRATCH_ALLOC_APPEND( l, fd_tower_leaves_dlist_align(), fd_tower_leaves_dlist_footprint() );
36 9 : void * leaves_pool = FD_SCRATCH_ALLOC_APPEND( l, fd_tower_leaves_pool_align(), fd_tower_leaves_pool_footprint( slot_max ) );
37 9 : void * lockout_slots_map = FD_SCRATCH_ALLOC_APPEND( l, fd_lockout_slots_map_align(), fd_lockout_slots_map_footprint( slot_max ) );
38 9 : void * lockout_slots_pool = FD_SCRATCH_ALLOC_APPEND( l, fd_lockout_slots_pool_align(), fd_lockout_slots_pool_footprint ( interval_max ) );
39 9 : void * lockout_itrvl_map = FD_SCRATCH_ALLOC_APPEND( l, fd_lockout_intervals_map_align(), fd_lockout_intervals_map_footprint ( interval_max ) );
40 9 : void * lockout_itrvl_pool = FD_SCRATCH_ALLOC_APPEND( l, fd_lockout_intervals_pool_align(), fd_lockout_intervals_pool_footprint( interval_max ) );
41 9 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, fd_forks_align() ) == (ulong)shmem + footprint );
42 :
43 9 : forks->tower_forks = fd_tower_forks_join ( fd_tower_forks_new ( tower_forks, lg_slot_max, 0UL ) ); /* FIXME seed */
44 9 : forks->tower_leaves_map = fd_tower_leaves_map_join ( fd_tower_leaves_map_new ( leaves_map, slot_max, 0 ) );
45 9 : forks->tower_leaves_pool = fd_tower_leaves_pool_join ( fd_tower_leaves_pool_new ( leaves_pool, slot_max ) );
46 9 : forks->tower_leaves_dlist = fd_tower_leaves_dlist_join ( fd_tower_leaves_dlist_new ( leaves_dlist ) );
47 9 : forks->lockout_slots_map = fd_lockout_slots_map_join ( fd_lockout_slots_map_new ( lockout_slots_map, slot_max, 0 ) );
48 9 : forks->lockout_slots_pool = fd_lockout_slots_pool_join ( fd_lockout_slots_pool_new ( lockout_slots_pool, interval_max ) );
49 9 : forks->lockout_intervals_map = fd_lockout_intervals_map_join ( fd_lockout_intervals_map_new ( lockout_itrvl_map, interval_max, 0 ) );
50 9 : forks->lockout_intervals_pool = fd_lockout_intervals_pool_join( fd_lockout_intervals_pool_new( lockout_itrvl_pool, interval_max ) );
51 :
52 9 : FD_TEST( forks->tower_forks );
53 9 : FD_TEST( forks->tower_leaves_map );
54 9 : FD_TEST( forks->tower_leaves_pool );
55 9 : FD_TEST( forks->tower_leaves_dlist );
56 9 : FD_TEST( forks->lockout_slots_map );
57 9 : FD_TEST( forks->lockout_slots_pool );
58 9 : FD_TEST( forks->lockout_intervals_map );
59 9 : FD_TEST( forks->lockout_intervals_pool );
60 9 : return shmem;
61 9 : }
62 :
63 : fd_forks_t *
64 9 : fd_forks_join( void * shforks ) {
65 9 : return shforks;
66 9 : }
67 :
68 :
69 : int
70 : is_ancestor( fd_tower_forks_t * forks,
71 : ulong slot,
72 144 : ulong ancestor_slot ) {
73 144 : fd_tower_forks_t * anc = fd_tower_forks_query( forks, slot, NULL );
74 654 : while( FD_LIKELY( anc ) ) {
75 588 : if( FD_LIKELY( anc->parent_slot == ancestor_slot ) ) return 1;
76 510 : anc = anc->parent_slot == ULONG_MAX ? NULL : fd_tower_forks_query( forks, anc->parent_slot, NULL );
77 510 : }
78 66 : return 0;
79 144 : }
80 :
81 : int
82 : fd_forks_is_slot_ancestor( fd_forks_t * forks,
83 : ulong descendant_slot,
84 0 : ulong ancestor_slot ) {
85 0 : return is_ancestor( forks->tower_forks, descendant_slot, ancestor_slot );
86 0 : }
87 :
88 : int
89 : fd_forks_is_slot_descendant( fd_forks_t * forks,
90 : ulong ancestor_slot,
91 144 : ulong descendant_slot ) {
92 144 : return is_ancestor( forks->tower_forks, descendant_slot, ancestor_slot );
93 144 : }
94 :
95 : ulong
96 : fd_forks_lowest_common_ancestor( fd_forks_t * forks,
97 : ulong slot1,
98 120 : ulong slot2 ) {
99 120 : fd_tower_forks_t * fork1 = fd_tower_forks_query( forks->tower_forks, slot1, NULL );
100 120 : fd_tower_forks_t * fork2 = fd_tower_forks_query( forks->tower_forks, slot2, NULL );
101 :
102 120 : if( FD_UNLIKELY( !fork1 )) FD_LOG_CRIT(( "slot1 %lu not found", slot1 ));
103 120 : if( FD_UNLIKELY( !fork2 )) FD_LOG_CRIT(( "slot2 %lu not found", slot2 ));
104 :
105 :
106 720 : while( FD_LIKELY( fork1 && fork2 ) ) {
107 720 : if( FD_UNLIKELY( fork1->slot == fork2->slot ) ) return fork1->slot;
108 600 : if( fork1->slot > fork2->slot ) fork1 = fd_tower_forks_query( forks->tower_forks, fork1->parent_slot, NULL );
109 369 : else fork2 = fd_tower_forks_query( forks->tower_forks, fork2->parent_slot, NULL );
110 600 : }
111 : /* If we reach here, then one of the slots is on a minority fork who's
112 : ancestor that connected it to the main fork has been pruned (i.e.)
113 : we have a dangling leaf right now! There is no LCA in this case. */
114 0 : return ULONG_MAX;
115 120 : }
116 :
117 : fd_hash_t const *
118 : fd_forks_canonical_block_id( fd_forks_t * forks,
119 0 : ulong slot ) {
120 0 : fd_tower_forks_t * fork = fd_tower_forks_query( forks->tower_forks, slot, NULL );
121 0 : if( FD_UNLIKELY( !fork ) ) return NULL;
122 0 : if ( FD_LIKELY( fork->confirmed ) ) return &fork->confirmed_block_id;
123 0 : else if( FD_LIKELY( fork->voted ) ) return &fork->voted_block_id;
124 0 : else return &fork->replayed_block_id;
125 0 : }
126 :
127 : void
128 0 : fd_forks_link( fd_forks_t * forks, ulong slot, ulong parent_slot ) {
129 0 : fd_tower_forks_t * fork = fd_tower_forks_insert( forks->tower_forks, slot );
130 0 : if( FD_UNLIKELY( !fork ) ) return;
131 0 : fork->parent_slot = parent_slot;
132 0 : fork->slot = slot;
133 0 : }
134 :
135 : fd_tower_forks_t *
136 : fd_forks_confirmed( fd_tower_forks_t * fork,
137 0 : fd_hash_t const * block_id ) {
138 0 : fork->confirmed = 1;
139 0 : fork->confirmed_block_id = *block_id;
140 0 : return fork;
141 0 : }
142 :
143 : fd_tower_forks_t *
144 : fd_forks_voted( fd_tower_forks_t * fork,
145 0 : fd_hash_t const * block_id ) {
146 0 : fork->voted = 1;
147 0 : fork->voted_block_id = *block_id;
148 0 : return fork;
149 0 : }
150 : fd_tower_forks_t *
151 : fd_forks_replayed( fd_forks_t * forks,
152 : fd_tower_forks_t * fork,
153 : ulong bank_idx,
154 117 : fd_hash_t const * block_id ) {
155 117 : fork->bank_idx = bank_idx;
156 117 : fork->replayed_block_id = *block_id;
157 :
158 117 : fd_tower_leaf_t * parent;
159 117 : if( ( parent = fd_tower_leaves_map_ele_remove( forks->tower_leaves_map, &fork->parent_slot, NULL, forks->tower_leaves_pool ) ) ) {
160 84 : fd_tower_leaves_dlist_ele_remove( forks->tower_leaves_dlist, parent, forks->tower_leaves_pool );
161 84 : fd_tower_leaves_pool_ele_release( forks->tower_leaves_pool, parent );
162 84 : }
163 117 : fd_tower_leaf_t * leaf = fd_tower_leaves_pool_ele_acquire( forks->tower_leaves_pool );
164 117 : leaf->slot = fork->slot;
165 117 : fd_tower_leaves_map_ele_insert( forks->tower_leaves_map, leaf, forks->tower_leaves_pool );
166 117 : fd_tower_leaves_dlist_ele_push_tail( forks->tower_leaves_dlist, leaf, forks->tower_leaves_pool );
167 :
168 117 : return fork;
169 117 : }
170 :
171 : fd_tower_forks_t *
172 : fd_forks_insert( fd_forks_t * forks,
173 : ulong slot,
174 117 : ulong parent_slot ) {
175 117 : fd_tower_forks_t * fork = fd_tower_forks_insert( forks->tower_forks, slot );
176 117 : if( FD_UNLIKELY( !fork ) ) return NULL;
177 :
178 117 : memset( fork, 0, sizeof(fd_tower_forks_t) );
179 117 : fork->parent_slot = parent_slot;
180 117 : fork->slot = slot;
181 117 : return fork;
182 117 : }
183 :
184 : fd_tower_forks_t *
185 0 : fd_forks_query( fd_forks_t * forks, ulong slot ) {
186 0 : return fd_tower_forks_query( forks->tower_forks, slot, NULL );
187 0 : }
188 :
189 : int
190 0 : fd_forks_remove( fd_forks_t * forks, ulong slot ) {
191 0 : fd_tower_forks_t * fork = fd_tower_forks_query( forks->tower_forks, slot, NULL );
192 0 : if( FD_UNLIKELY( !fork ) ) return 0;
193 0 : fd_tower_forks_remove( forks->tower_forks, fork );
194 0 : fd_tower_leaf_t * leaf = fd_tower_leaves_map_ele_remove( forks->tower_leaves_map, &slot, NULL, forks->tower_leaves_pool );
195 0 : if( FD_UNLIKELY( leaf ) ) {
196 0 : fd_tower_leaves_dlist_ele_remove( forks->tower_leaves_dlist, leaf, forks->tower_leaves_pool );
197 0 : fd_tower_leaves_pool_ele_release( forks->tower_leaves_pool, leaf );
198 0 : }
199 0 : return 1; /* success */
200 0 : }
201 :
202 : void
203 39 : fd_forks_lockouts_add( fd_forks_t * forks, ulong fork_slot, fd_hash_t const * vote_account_pubkey, fd_tower_accts_t * accts ) {
204 39 : uchar __attribute__((aligned(FD_TOWER_ALIGN))) scratch[ FD_TOWER_FOOTPRINT ];
205 39 : fd_tower_t * scratch_tower = fd_tower_join( fd_tower_new( scratch ) );
206 :
207 39 : fd_tower_from_vote_acc( scratch_tower, accts->data );
208 :
209 39 : for( fd_tower_iter_t iter = fd_tower_iter_init( scratch_tower );
210 78 : !fd_tower_iter_done( scratch_tower, iter );
211 39 : iter = fd_tower_iter_next( scratch_tower, iter ) ) {
212 39 : fd_tower_t * vote = fd_tower_iter_ele( scratch_tower, iter );
213 39 : ulong interval_start = vote->slot;
214 39 : ulong interval_end = vote->slot + (1UL << vote->conf);
215 39 : ulong key = fd_lockout_interval_key( fork_slot, interval_end );
216 :
217 39 : if( !fd_lockout_intervals_map_ele_query( forks->lockout_intervals_map, &key, NULL, forks->lockout_intervals_pool ) ) {
218 : /* No other pubkey has yet created [fork_slot, interval_end], so we can add this interval to the slot map linkedlist */
219 30 : fd_lockout_slots_t * slot = fd_lockout_slots_pool_ele_acquire( forks->lockout_slots_pool );
220 : /* map multi, multiple keys for the same fork_slot */
221 30 : slot->fork_slot = fork_slot;
222 30 : slot->interval_end = interval_end;
223 30 : FD_TEST( fd_lockout_slots_map_ele_insert( forks->lockout_slots_map, slot, forks->lockout_slots_pool ) );
224 30 : }
225 :
226 39 : fd_lockout_intervals_t * interval = fd_lockout_intervals_pool_ele_acquire( forks->lockout_intervals_pool );
227 39 : interval->key = key;
228 39 : interval->vote_account_pubkey = *vote_account_pubkey;
229 39 : interval->interval_start = interval_start;
230 39 : FD_TEST( fd_lockout_intervals_map_ele_insert( forks->lockout_intervals_map, interval, forks->lockout_intervals_pool ) );
231 39 : }
232 39 : }
233 :
234 : void
235 9 : fd_forks_lockouts_clear( fd_forks_t * forks, ulong fork_slot ) {
236 9 : for( fd_lockout_slots_t * slot_interval = fd_lockout_slots_map_ele_remove( forks->lockout_slots_map, &fork_slot, NULL, forks->lockout_slots_pool );
237 18 : slot_interval;
238 9 : slot_interval = fd_lockout_slots_map_ele_remove( forks->lockout_slots_map, &fork_slot, NULL, forks->lockout_slots_pool ) ) {
239 9 : ulong key = fd_lockout_interval_key( fork_slot, slot_interval->interval_end );
240 9 : for( fd_lockout_intervals_t * itrvl = fd_lockout_intervals_map_ele_remove( forks->lockout_intervals_map, &key, NULL, forks->lockout_intervals_pool );
241 18 : itrvl;
242 9 : itrvl = fd_lockout_intervals_map_ele_remove( forks->lockout_intervals_map, &key, NULL, forks->lockout_intervals_pool ) ) {
243 9 : fd_lockout_intervals_pool_ele_release( forks->lockout_intervals_pool, itrvl );
244 9 : }
245 9 : fd_lockout_slots_pool_ele_release( forks->lockout_slots_pool, slot_interval );
246 9 : }
247 9 : }
|
