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 0 : ulong seed ) {
7 0 : if( FD_UNLIKELY( !shmem ) ) {
8 0 : FD_LOG_WARNING(( "NULL mem" ));
9 0 : return NULL;
10 0 : }
11 :
12 0 : ulong footprint = fd_tower_blocks_footprint( slot_max );
13 0 : if( FD_UNLIKELY( !footprint ) ) {
14 0 : FD_LOG_WARNING(( "bad slot_max (%lu)", slot_max ));
15 0 : return NULL;
16 0 : }
17 :
18 0 : 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 0 : int lg_slot_max = fd_ulong_find_msb( fd_ulong_pow2_up( slot_max ) ) + 1;
24 :
25 0 : FD_SCRATCH_ALLOC_INIT( l, shmem );
26 0 : fd_tower_blocks_t * blocks = FD_SCRATCH_ALLOC_APPEND( l, fd_tower_blocks_align(), sizeof(fd_tower_blocks_t) );
27 0 : void * map = FD_SCRATCH_ALLOC_APPEND( l, fd_tower_blk_align(), fd_tower_blk_footprint( lg_slot_max ) );
28 0 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, fd_tower_blocks_align() ) == (ulong)shmem + footprint );
29 :
30 0 : blocks->blk_map = fd_tower_blk_new( map, lg_slot_max, seed );
31 0 : FD_TEST( blocks->blk_map );
32 :
33 0 : return shmem;
34 0 : }
35 :
36 : fd_tower_blocks_t *
37 0 : fd_tower_blocks_join( void * shblocks ) {
38 0 : fd_tower_blocks_t * blocks = (fd_tower_blocks_t *)shblocks;
39 :
40 0 : if( FD_UNLIKELY( !blocks ) ) {
41 0 : FD_LOG_WARNING(( "NULL tower_blocks" ));
42 0 : return NULL;
43 0 : }
44 :
45 0 : 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 0 : blocks->blk_map = fd_tower_blk_join( blocks->blk_map );
51 0 : FD_TEST( blocks->blk_map );
52 :
53 0 : return blocks;
54 0 : }
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 0 : ulong ancestor_slot ) {
87 0 : fd_tower_blk_t * anc = fd_tower_blk_query( forks, slot, NULL );
88 0 : while( FD_LIKELY( anc ) ) {
89 0 : if( FD_LIKELY( anc->parent_slot == ancestor_slot ) ) return 1;
90 0 : anc = anc->parent_slot == ULONG_MAX ? NULL : fd_tower_blk_query( forks, anc->parent_slot, NULL );
91 0 : }
92 0 : return 0;
93 0 : }
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 0 : ulong descendant_slot ) {
106 0 : return is_ancestor( forks->blk_map, descendant_slot, ancestor_slot );
107 0 : }
108 :
109 : ulong
110 : fd_tower_blocks_lowest_common_ancestor( fd_tower_blocks_t * forks,
111 : ulong slot1,
112 0 : ulong slot2 ) {
113 :
114 0 : fd_tower_blk_t * fork1 = fd_tower_blk_query( forks->blk_map, slot1, NULL );
115 0 : fd_tower_blk_t * fork2 = fd_tower_blk_query( forks->blk_map, slot2, NULL );
116 :
117 0 : if( FD_UNLIKELY( !fork1 )) FD_LOG_CRIT(( "slot1 %lu not found", slot1 ));
118 0 : if( FD_UNLIKELY( !fork2 )) FD_LOG_CRIT(( "slot2 %lu not found", slot2 ));
119 :
120 0 : while( FD_LIKELY( fork1 && fork2 ) ) {
121 0 : if( FD_UNLIKELY( fork1->slot == fork2->slot ) ) return fork1->slot;
122 0 : if( fork1->slot > fork2->slot ) fork1 = fd_tower_blk_query( forks->blk_map, fork1->parent_slot, NULL );
123 0 : else fork2 = fd_tower_blk_query( forks->blk_map, fork2->parent_slot, NULL );
124 0 : }
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 0 : }
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 0 : fd_tower_blocks_query( fd_tower_blocks_t * forks, ulong slot ) {
145 0 : return fd_tower_blk_query( forks->blk_map, slot, NULL );
146 0 : }
147 :
148 : fd_tower_blk_t *
149 : fd_tower_blocks_insert( fd_tower_blocks_t * forks,
150 : ulong slot,
151 0 : ulong parent_slot ) {
152 0 : fd_tower_blk_t * fork = fd_tower_blk_insert( forks->blk_map, slot );
153 0 : if( FD_UNLIKELY( !fork ) ) return NULL;
154 :
155 0 : memset( fork, 0, sizeof(fd_tower_blk_t) );
156 0 : fork->parent_slot = parent_slot;
157 0 : fork->slot = slot;
158 0 : fork->confirmed = 0;
159 0 : fork->voted = 0;
160 0 : return fork;
161 0 : }
162 :
163 : void
164 : fd_tower_blocks_remove( fd_tower_blocks_t * forks,
165 0 : ulong slot ) {
166 0 : fd_tower_blk_t * blk = fd_tower_blk_query( forks->blk_map, slot, NULL ); /* validate slot exists before removing */
167 0 : if( FD_LIKELY( blk ) ) fd_tower_blk_remove( forks->blk_map, blk );
168 0 : }
|
