Line data Source code
1 : #include "fd_tower_blocks.h"
2 :
3 : void *
4 : fd_tower_blocks_new( void * shmem,
5 : ulong slot_max,
6 18 : ulong seed ) {
7 18 : if( FD_UNLIKELY( !shmem ) ) {
8 0 : FD_LOG_WARNING(( "NULL mem" ));
9 0 : return NULL;
10 0 : }
11 :
12 18 : ulong footprint = fd_tower_blocks_footprint( slot_max );
13 18 : if( FD_UNLIKELY( !footprint ) ) {
14 0 : FD_LOG_WARNING(( "bad slot_max (%lu)", slot_max ));
15 0 : return NULL;
16 0 : }
17 :
18 18 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_tower_blocks_align() ) ) ) {
19 0 : FD_LOG_WARNING(( "misaligned mem" ));
20 0 : return NULL;
21 0 : }
22 :
23 18 : int lg_slot_max = fd_ulong_find_msb( fd_ulong_pow2_up( slot_max ) ) + 1;
24 :
25 18 : FD_SCRATCH_ALLOC_INIT( l, shmem );
26 18 : fd_tower_blocks_t * blocks = FD_SCRATCH_ALLOC_APPEND( l, fd_tower_blocks_align(), sizeof(fd_tower_blocks_t) );
27 18 : void * map = FD_SCRATCH_ALLOC_APPEND( l, fd_tower_blk_align(), fd_tower_blk_footprint( lg_slot_max ) );
28 18 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, fd_tower_blocks_align() ) == (ulong)shmem + footprint );
29 :
30 18 : blocks->blk_map = fd_tower_blk_new( map, lg_slot_max, seed );
31 18 : FD_TEST( blocks->blk_map );
32 :
33 18 : return shmem;
34 18 : }
35 :
36 : fd_tower_blocks_t *
37 18 : fd_tower_blocks_join( void * shblocks ) {
38 18 : fd_tower_blocks_t * blocks = (fd_tower_blocks_t *)shblocks;
39 :
40 18 : if( FD_UNLIKELY( !blocks ) ) {
41 0 : FD_LOG_WARNING(( "NULL tower_blocks" ));
42 0 : return NULL;
43 0 : }
44 :
45 18 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)blocks, fd_tower_blocks_align() ) ) ) {
46 0 : FD_LOG_WARNING(( "misaligned tower_blocks" ));
47 0 : return NULL;
48 0 : }
49 :
50 18 : blocks->blk_map = fd_tower_blk_join( blocks->blk_map );
51 18 : FD_TEST( blocks->blk_map );
52 :
53 18 : return blocks;
54 18 : }
55 :
56 : void *
57 0 : fd_tower_blocks_leave( fd_tower_blocks_t const * blocks ) {
58 :
59 0 : if( FD_UNLIKELY( !blocks ) ) {
60 0 : FD_LOG_WARNING(( "NULL blocks" ));
61 0 : return NULL;
62 0 : }
63 :
64 0 : return (void *)blocks;
65 0 : }
66 :
67 : void *
68 0 : fd_tower_blocks_delete( void * blocks ) {
69 :
70 0 : if( FD_UNLIKELY( !blocks ) ) {
71 0 : FD_LOG_WARNING(( "NULL blocks" ));
72 0 : return NULL;
73 0 : }
74 :
75 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)blocks, fd_tower_blocks_align() ) ) ) {
76 0 : FD_LOG_WARNING(( "misaligned blocks" ));
77 0 : return NULL;
78 0 : }
79 :
80 0 : return blocks;
81 0 : }
82 :
83 : int
84 : is_ancestor( fd_tower_blk_t * forks,
85 : ulong slot,
86 150 : ulong ancestor_slot ) {
87 150 : fd_tower_blk_t * anc = fd_tower_blk_query( forks, slot, NULL );
88 546 : while( FD_LIKELY( anc ) ) {
89 495 : if( FD_LIKELY( anc->parent_slot == ancestor_slot ) ) return 1;
90 396 : anc = anc->parent_slot == ULONG_MAX ? NULL : fd_tower_blk_query( forks, anc->parent_slot, NULL );
91 396 : }
92 51 : return 0;
93 150 : }
94 :
95 : int
96 : fd_tower_blocks_is_slot_ancestor( fd_tower_blocks_t * forks,
97 : ulong descendant_slot,
98 0 : ulong ancestor_slot ) {
99 0 : return is_ancestor( forks->blk_map, descendant_slot, ancestor_slot );
100 0 : }
101 :
102 : int
103 : fd_tower_blocks_is_slot_descendant( fd_tower_blocks_t * forks,
104 : ulong ancestor_slot,
105 150 : ulong descendant_slot ) {
106 150 : return is_ancestor( forks->blk_map, descendant_slot, ancestor_slot );
107 150 : }
108 :
109 : ulong
110 : fd_tower_blocks_lowest_common_ancestor( fd_tower_blocks_t * forks,
111 : ulong slot1,
112 129 : ulong slot2 ) {
113 :
114 129 : fd_tower_blk_t * fork1 = fd_tower_blk_query( forks->blk_map, slot1, NULL );
115 129 : fd_tower_blk_t * fork2 = fd_tower_blk_query( forks->blk_map, slot2, NULL );
116 :
117 129 : if( FD_UNLIKELY( !fork1 )) FD_LOG_CRIT(( "slot1 %lu not found", slot1 ));
118 129 : if( FD_UNLIKELY( !fork2 )) FD_LOG_CRIT(( "slot2 %lu not found", slot2 ));
119 :
120 786 : while( FD_LIKELY( fork1 && fork2 ) ) {
121 786 : if( FD_UNLIKELY( fork1->slot == fork2->slot ) ) return fork1->slot;
122 657 : if( fork1->slot > fork2->slot ) fork1 = fd_tower_blk_query( forks->blk_map, fork1->parent_slot, NULL );
123 417 : else fork2 = fd_tower_blk_query( forks->blk_map, fork2->parent_slot, NULL );
124 657 : }
125 :
126 : /* If we reach here, then one of the slots is on a minority fork who's
127 : ancestor that connected it to the main fork has been pruned (i.e.)
128 : we have a dangling leaf right now! There is no LCA in this case. */
129 :
130 0 : return ULONG_MAX;
131 129 : }
132 :
133 : fd_hash_t const *
134 : fd_tower_blocks_canonical_block_id( fd_tower_blocks_t * forks,
135 0 : ulong slot ) {
136 0 : fd_tower_blk_t * fork = fd_tower_blk_query( forks->blk_map, slot, NULL );
137 0 : if( FD_UNLIKELY( !fork ) ) return NULL;
138 0 : if ( FD_LIKELY( fork->confirmed ) ) return &fork->confirmed_block_id;
139 0 : else if( FD_LIKELY( fork->voted ) ) return &fork->voted_block_id;
140 0 : else return &fork->replayed_block_id;
141 0 : }
142 :
143 : fd_tower_blk_t *
144 744 : fd_tower_blocks_query( fd_tower_blocks_t * forks, ulong slot ) {
145 744 : return fd_tower_blk_query( forks->blk_map, slot, NULL );
146 744 : }
147 :
148 : fd_tower_blk_t *
149 : fd_tower_blocks_insert( fd_tower_blocks_t * forks,
150 : ulong slot,
151 264 : ulong parent_slot ) {
152 264 : fd_tower_blk_t * fork = fd_tower_blk_insert( forks->blk_map, slot );
153 264 : if( FD_UNLIKELY( !fork ) ) return NULL;
154 :
155 264 : memset( fork, 0, sizeof(fd_tower_blk_t) );
156 264 : fork->parent_slot = parent_slot;
157 264 : fork->slot = slot;
158 264 : fork->confirmed = 0;
159 264 : fork->voted = 0;
160 264 : fork->prev_leader_slot = ULONG_MAX;
161 264 : fork->leader = 0;
162 264 : fork->propagated = 0;
163 264 : return fork;
164 264 : }
165 :
166 : void
167 : fd_tower_blocks_remove( fd_tower_blocks_t * forks,
168 0 : ulong slot ) {
169 0 : fd_tower_blk_t * blk = fd_tower_blk_query( forks->blk_map, slot, NULL ); /* validate slot exists before removing */
170 0 : if( FD_LIKELY( blk ) ) fd_tower_blk_remove( forks->blk_map, blk );
171 0 : }
|
