Line data Source code
1 : #ifndef HEADER_fd_src_disco_shred_fd_shred_dest_h
2 : #define HEADER_fd_src_disco_shred_fd_shred_dest_h
3 :
4 : #include "../../ballet/shred/fd_shred.h"
5 : #include "../../ballet/sha256/fd_sha256.h"
6 : #include "../../ballet/wsample/fd_wsample.h"
7 : #include "../../flamenco/leaders/fd_leaders.h"
8 :
9 : /* This header defines a collection of methods for using stake weights
10 : to compute the destination of a specific shred for the leader and
11 : non-leader. This is where the Turbine tree logic is implemented. */
12 :
13 : /* For a given FEC, we might need to produce "fanout" destinations for
14 : each of 134 shreds, which is a lot of destinations! Full destination
15 : information (ip, port, mac) is 12 B. A pointer is 8 B, but an index
16 : can be as small as 4 B, since currently Turbine doesn't work with
17 : more than fanout^2 nodes, which is less than UINT_MAX for a maximum
18 : fanout of 1536 (the fanout is dependent on feature activation). Thus,
19 : we go with the index, which can cheaply be mapped to the full
20 : information using fd_shred_dest_idx_to_dest below. */
21 : typedef uint fd_shred_dest_idx_t;
22 :
23 :
24 : #define FD_SHRED_DEST_MAX_SHRED_CNT (134UL) /* DATA_SHREDS_MAX+PARITY_SHREDS_MAX */
25 230183496 : #define FD_SHRED_DEST_NO_DEST (UINT_MAX)
26 : #define FD_SHRED_DEST_MAX_FANOUT (1536UL)
27 :
28 : /* fd_shred_dest_weighted_t specifies a destination to which a shred might be
29 : sent. The information comes from Gossip typically. */
30 : struct fd_shred_dest_weighted {
31 : fd_pubkey_t pubkey; /* The validator's identity key */
32 : ulong stake_lamports; /* Stake, measured in lamports, or 0 for an unstaked validator */
33 : uint ip4; /* The validator's IP address, in network byte order */
34 : ushort port; /* The TVU port, in host byte order */
35 : }; /* be careful ip and host are in different byte order */
36 : typedef struct fd_shred_dest_weighted fd_shred_dest_weighted_t;
37 :
38 : /* Internal type, forward declared to be able to declare the struct
39 : here. */
40 : struct pubkey_to_idx;
41 : typedef struct pubkey_to_idx pubkey_to_idx_t;
42 :
43 808020 : #define FD_SHRED_DEST_ALIGN (128UL)
44 : FD_STATIC_ASSERT( FD_SHRED_DEST_ALIGN>=FD_SHA256_BATCH_ALIGN, fd_shred_dest_private_align );
45 :
46 : struct __attribute__((aligned(FD_SHRED_DEST_ALIGN))) fd_shred_dest_private {
47 : uchar _sha256_batch[ FD_SHA256_BATCH_FOOTPRINT ] __attribute__((aligned(FD_SHA256_BATCH_ALIGN)));
48 : fd_chacha_rng_t rng[1];
49 :
50 : /* null_dest is initialized to all zeros. Returned when the destination
51 : doesn't exist (e.g. you've asked for the 5th destination, but you only
52 : need to send to 4 recipients. */
53 : fd_shred_dest_weighted_t null_dest[1];
54 :
55 : fd_epoch_leaders_t const * lsched;
56 :
57 : ulong cnt;
58 : fd_shred_dest_weighted_t * all_destinations; /* a local copy, points to memory after the struct */
59 :
60 : fd_wsample_t * staked;
61 : struct {
62 : /* These two variables are maintained by the unstaked sampling functions. */
63 : ulong * unstaked;
64 : ulong unstaked_unremoved_cnt;
65 : };
66 : ulong staked_cnt;
67 : ulong unstaked_cnt;
68 :
69 : pubkey_to_idx_t * pubkey_to_idx_map; /* maps pubkey -> [0, staked_cnt+unstaked_cnt) */
70 :
71 : ulong source_validator_orig_idx; /* in [0, staked_cnt+unstaked_cnt) */
72 : /* Struct followed by:
73 : * pubkey_to_idx map
74 : * all_destinations
75 : * staked
76 : * unstaked
77 : */
78 : };
79 : typedef struct fd_shred_dest_private fd_shred_dest_t;
80 :
81 :
82 : /* fd_shred_dest_{align, footprint} return the alignment and footprint
83 : (respectively) required of a region of memory to format it as an
84 : fd_shred_dest_t object. staked_cnt is the number of destinations
85 : with positive stake while unstaked_cnt is the number of destinations
86 : with zero stake that this object can store. */
87 808020 : static inline ulong fd_shred_dest_align ( void ) { return FD_SHRED_DEST_ALIGN; }
88 : /* */ ulong fd_shred_dest_footprint( ulong staked_cnt, ulong unstaked_cnt );
89 :
90 : /* fd_shred_dest_new formats a region of memory for use as an
91 : fd_shred_dest_t object. mem points to the first byte of a region of
92 : memory with the required footprint and alignment. info points to the
93 : first of cnt destinations that the fd_shred_dest_t will be aware of.
94 : info must be sorted in the typical Solana stake weighted way: largest
95 : stake to smallest stake, with ties broken by pubkey (again, largest
96 : to smallest lexicographically). info must not omit staked validators
97 : just because they do not have contact info; rather, those should be
98 : represented with ip set to 0. info may include unstaked validators,
99 : which, given the sort order, will be at the end of the list.
100 :
101 : Each fd_shred_dest_t object is tied to a specific epoch, and so the
102 : stake weights are constant within the epoch. The information in info
103 : will be copied, and no read interest in info will be retained.
104 : lsched points to a local join of an fd_epoch_leaders_t object with
105 : the leader information for the slots when the shreds for which this
106 : shred dest object computes destinations were produced. This function
107 : retains a read interest in lsched that persists until the memory is
108 : unformatted. `source` points to the public key of the identity key
109 : of the current validator, i.e. the one who sends out the shreds
110 : computed by this object. info must contain contact info for
111 : `source,` although it will never be returned as a destination.
112 : `seed` is the hash seed for an internal pubkey lookup hash map; this
113 : value should be generated using a random number generator.
114 :
115 : Returns mem on success and NULL on errors. Logs a warning with
116 : details on errors. */
117 : void *
118 : fd_shred_dest_new( void * mem,
119 : fd_shred_dest_weighted_t const * info, /* Accessed [0, cnt) */
120 : ulong cnt,
121 : fd_epoch_leaders_t const * lsched,
122 : fd_pubkey_t const * source,
123 : ulong seed );
124 :
125 : /* fd_shred_dest_join joins the caller to a region of memory formatted
126 : as an fd_shred_dest_t. fd_shred_dest_leave does the opposite.
127 : fd_shred_dest_delete unformats a region of memory. */
128 : fd_shred_dest_t * fd_shred_dest_join( void * mem );
129 : void * fd_shred_dest_leave( fd_shred_dest_t * sdest );
130 : void * fd_shred_dest_delete( void * mem );
131 :
132 : /* fd_shred_dest_cnt_{staked, unstaked, all} returns the number of known
133 : destination that are staked, unstaked, or either, respectively. The
134 : staked destinations have index [0, fd_shred_dest_cnt_staked()) and
135 : the unstaked destinations have index [fd_shred_dest_cnt_staked(),
136 : fd_shred_dest_cnt_all() ). fd_shred_dest_cnt_all() ==
137 : fd_shred_dest_cnt_staked() + fd_shred_dest_cnt_unstaked(). */
138 756 : static inline ulong fd_shred_dest_cnt_staked ( fd_shred_dest_t * sdest ) { return sdest->staked_cnt ; }
139 474 : static inline ulong fd_shred_dest_cnt_unstaked( fd_shred_dest_t * sdest ) { return sdest->unstaked_cnt; }
140 378 : static inline ulong fd_shred_dest_cnt_all ( fd_shred_dest_t * sdest ) { return sdest->staked_cnt + sdest->unstaked_cnt; }
141 :
142 : /* fd_shred_dest_compute_first computes the root of the Turbine tree for
143 : each of the provided shreds. All the provided shreds must come from
144 : the same slot (and thus have the same leader). This should only be
145 : called for shreds from a slot in which the source validator provided
146 : in _new is the leader (determined using the leader schedule provided
147 : in _new). shred_cnt specifies the number of shreds for which
148 : destinations should be computes. input_shreds is accessed
149 : input_shreds[i] for i in [0, shred_cnt). shred_cnt must be in [0,
150 : 67]. The destination index for input_shreds[i] is stored at out[i].
151 : input_shreds==NULL is fine if shred_cnt==0, in which case this
152 : function is a no-op.
153 : Returns out on success and NULL on failure.
154 : This function uses the sha256 batch API internally for performance,
155 : which is why it operates on several shreds at the same time as
156 : opposed to one at a time. */
157 : fd_shred_dest_idx_t *
158 : fd_shred_dest_compute_first( fd_shred_dest_t * sdest,
159 : fd_shred_t const * const * input_shreds,
160 : ulong shred_cnt,
161 : fd_shred_dest_idx_t * out );
162 :
163 : /* fd_shred_dest_compute_children computes the source validator's
164 : children in the Turbine tree for each of the provided shreds.
165 : Although Solana has the concept of "neighborhoods" in Turbine, we
166 : treat it as a standard high-radix tree, and a child is any validator
167 : to which the source validator should send the shred directly.
168 : All provided shreds must be from the same slot, and that leader for
169 : that slot must be known by the leader schedule. As in
170 : fd_shred_dest_compute_first, shred_cnt specifies the number of
171 : shreds, input_shreds is accessed input_shreds[i] for i in [0,
172 : shred_cnt), and 0<=shred_cnt<=67. Computes the first dest_cnt
173 : destinations for each shred, using a tree with fanout `fanout`.
174 : Exactly dest_cnt destination indices will be written for each shreds,
175 : so if that is more than the number of destinations that the source
176 : validator needs to send to, it will be padded out with
177 : FD_SHRED_DEST_NO_DEST. The typical case is to pass dest_cnt==fanout.
178 : Results are stored in out, but there's some awkwardness associated
179 : with something that's logically a 2d array, so out_stride specifies
180 : the number of elements in each logical row of the output.
181 : Precisely, destination j for shred i is written to out[ j*out_stride
182 : + i ]. Graphically:
183 : [ shred0 dest0, shred1 dest0, shred2 dest0, ... (skip until stride)
184 : shred0 dest1, shred1 dest1, shred2 dest1, ... (skip until 2stride)
185 : ...
186 : shred0 dest dest_cnt-1, ... ].
187 : out_stride must be at least shred_cnt.
188 : If opt_max_dest_cnt is non-NULL, the maximum number of real
189 : destinations for any of the provided shreds will be stored in
190 : opt_max_dest_cnt. This value is always <= dest_cnt, but in many
191 : cases may be much lower (especially if the source validator has low
192 : stake).
193 :
194 : Returns out on success and NULL on failure. */
195 : /* TODO: Would it be better if out were transposed? Should I get rid of
196 : stride? */
197 : fd_shred_dest_idx_t *
198 : fd_shred_dest_compute_children( fd_shred_dest_t * sdest,
199 : fd_shred_t const * const * input_shreds,
200 : ulong shred_cnt,
201 : fd_shred_dest_idx_t * out,
202 : ulong out_stride,
203 : ulong fanout,
204 : ulong dest_cnt,
205 : ulong * opt_max_dest_cnt );
206 :
207 : /* fd_shred_dest_idx_to_dest maps a destination index (as produced by
208 : fd_shred_dest_compute_children or fd_shred_dest_compute_first) to an
209 : actual destination. The lifetime of the returned pointer is the same
210 : as the lifetime of sdest. idx==FD_SHRED_DEST_NO_DEST is fine, and
211 : this will return a pointer to a destination with all fields set to 0.
212 : It's safe for the caller to update the IP, port, and mac fields of
213 : the returned struct, although the caller must not modify the weight
214 : or pubkey fields. The caller can use this to update contact info for
215 : a validator. */
216 : static inline fd_shred_dest_weighted_t *
217 3457938 : fd_shred_dest_idx_to_dest( fd_shred_dest_t * sdest, fd_shred_dest_idx_t idx ) {
218 3457938 : return fd_ptr_if( idx!=FD_SHRED_DEST_NO_DEST, sdest->all_destinations + idx, sdest->null_dest );
219 3457938 : }
220 :
221 : /* fd_shred_dest_idx_t maps a pubkey to a destination index, if the
222 : pubkey is known as a destination. If the pubkey is not know, returns
223 : FD_SHRED_DEST_NO_DEST. */
224 : fd_shred_dest_idx_t fd_shred_dest_pubkey_to_idx( fd_shred_dest_t * sdest, fd_pubkey_t const * pubkey );
225 :
226 : /* fd_shred_dest_update_source changes the shred destination
227 : computation's notion of source. sdest must be a valid local join.
228 : idx must be in [0, staked_cnt+unstaked_cnt). In particular, idx must
229 : not be FD_SHRED_DEST_NO_DEST. idx is as returned from
230 : fd_shred_dest_pubkey_to_idx. */
231 : static inline void
232 18 : fd_shred_dest_update_source( fd_shred_dest_t * sdest, fd_shred_dest_idx_t idx ) {
233 18 : sdest->source_validator_orig_idx = idx;
234 18 : }
235 :
236 : #endif /* HEADER_fd_src_disco_shred_fd_shred_dest_h */
|
