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 237868281 : #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 868158 : #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 : ulong excluded_stake;
70 :
71 : pubkey_to_idx_t * pubkey_to_idx_map; /* maps pubkey -> [0, staked_cnt+unstaked_cnt) */
72 :
73 : ulong source_validator_orig_idx; /* in [0, staked_cnt+unstaked_cnt) */
74 : /* Struct followed by:
75 : * pubkey_to_idx map
76 : * all_destinations
77 : * staked
78 : * unstaked
79 : */
80 : };
81 : typedef struct fd_shred_dest_private fd_shred_dest_t;
82 :
83 :
84 : /* fd_shred_dest_{align, footprint} return the alignment and footprint
85 : (respectively) required of a region of memory to format it as an
86 : fd_shred_dest_t object. staked_cnt is the number of destinations
87 : with positive stake while unstaked_cnt is the number of destinations
88 : with zero stake that this object can store. */
89 868158 : static inline ulong fd_shred_dest_align ( void ) { return FD_SHRED_DEST_ALIGN; }
90 : /* */ ulong fd_shred_dest_footprint( ulong staked_cnt, ulong unstaked_cnt );
91 :
92 : /* fd_shred_dest_new formats a region of memory for use as an
93 : fd_shred_dest_t object. mem points to the first byte of a region of
94 : memory with the required footprint and alignment. info points to the
95 : first of cnt destinations that the fd_shred_dest_t will be aware of.
96 : info must be sorted in the typical Solana stake weighted way: largest
97 : stake to smallest stake, with ties broken by pubkey (again, largest
98 : to smallest lexicographically). info must not omit staked validators
99 : just because they do not have contact info; rather, those should be
100 : represented with ip set to 0. info may include unstaked validators,
101 : which, given the sort order, will be at the end of the list. If the
102 : number of staked validators exceeds the caller's maximum list
103 : capacity, the list can be truncated, with excluded_stake set to the
104 : sum of the excluded staked validators. In that case, info should not
105 : contain any unstaked validators.
106 :
107 : Each fd_shred_dest_t object is tied to a specific epoch, and so the
108 : stake weights are constant within the epoch. The information in info
109 : will be copied, and no read interest in info will be retained.
110 : lsched points to a local join of an fd_epoch_leaders_t object with
111 : the leader information for the slots when the shreds for which this
112 : shred dest object computes destinations were produced. This function
113 : retains a read interest in lsched that persists until the memory is
114 : unformatted. `source` points to the public key of the identity key
115 : of the current validator, i.e. the one who sends out the shreds
116 : computed by this object. info must contain contact info for
117 : `source,` although it will never be returned as a destination.
118 :
119 : Returns mem on success and NULL on errors. Logs a warning with
120 : details on errors. */
121 : void *
122 : fd_shred_dest_new( void * mem,
123 : fd_shred_dest_weighted_t const * info, /* Accessed [0, cnt) */
124 : ulong cnt,
125 : fd_epoch_leaders_t const * lsched,
126 : fd_pubkey_t const * source,
127 : ulong excluded_stake );
128 :
129 : /* fd_shred_dest_join joins the caller to a region of memory formatted
130 : as an fd_shred_dest_t. fd_shred_dest_leave does the opposite.
131 : fd_shred_dest_delete unformats a region of memory. */
132 : fd_shred_dest_t * fd_shred_dest_join( void * mem );
133 : void * fd_shred_dest_leave( fd_shred_dest_t * sdest );
134 : void * fd_shred_dest_delete( void * mem );
135 :
136 : /* fd_shred_dest_cnt_{staked, unstaked, all} returns the number of known
137 : destination that are staked, unstaked, or either, respectively. The
138 : staked destinations have index [0, fd_shred_dest_cnt_staked()) and
139 : the unstaked destinations have index [fd_shred_dest_cnt_staked(),
140 : fd_shred_dest_cnt_all() ). fd_shred_dest_cnt_all() ==
141 : fd_shred_dest_cnt_staked() + fd_shred_dest_cnt_unstaked(). */
142 783 : static inline ulong fd_shred_dest_cnt_staked ( fd_shred_dest_t * sdest ) { return sdest->staked_cnt ; }
143 438 : static inline ulong fd_shred_dest_cnt_unstaked( fd_shred_dest_t * sdest ) { return sdest->unstaked_cnt; }
144 402 : static inline ulong fd_shred_dest_cnt_all ( fd_shred_dest_t * sdest ) { return sdest->staked_cnt + sdest->unstaked_cnt; }
145 :
146 : /* fd_shred_dest_compute_first computes the root of the Turbine tree for
147 : each of the provided shreds. All the provided shreds must come from
148 : the same slot (and thus have the same leader). This should only be
149 : called for shreds from a slot in which the source validator provided
150 : in _new is the leader (determined using the leader schedule provided
151 : in _new). shred_cnt specifies the number of shreds for which
152 : destinations should be computes. input_shreds is accessed
153 : input_shreds[i] for i in [0, shred_cnt). shred_cnt must be in [0,
154 : 67]. The destination index for input_shreds[i] is stored at out[i].
155 : input_shreds==NULL is fine if shred_cnt==0, in which case this
156 : function is a no-op.
157 : Returns out on success and NULL on failure.
158 : This function uses the sha256 batch API internally for performance,
159 : which is why it operates on several shreds at the same time as
160 : opposed to one at a time. */
161 : fd_shred_dest_idx_t *
162 : fd_shred_dest_compute_first( fd_shred_dest_t * sdest,
163 : fd_shred_t const * const * input_shreds,
164 : ulong shred_cnt,
165 : fd_shred_dest_idx_t * out );
166 :
167 : /* fd_shred_dest_compute_children computes the source validator's
168 : children in the Turbine tree for each of the provided shreds.
169 : Although Solana has the concept of "neighborhoods" in Turbine, we
170 : treat it as a standard high-radix tree, and a child is any validator
171 : to which the source validator should send the shred directly.
172 : All provided shreds must be from the same slot, and that leader for
173 : that slot must be known by the leader schedule. As in
174 : fd_shred_dest_compute_first, shred_cnt specifies the number of
175 : shreds, input_shreds is accessed input_shreds[i] for i in [0,
176 : shred_cnt), and 0<=shred_cnt<=67. Computes the first dest_cnt
177 : destinations for each shred, using a tree with fanout `fanout`.
178 : Exactly dest_cnt destination indices will be written for each shreds,
179 : so if that is more than the number of destinations that the source
180 : validator needs to send to, it will be padded out with
181 : FD_SHRED_DEST_NO_DEST. The typical case is to pass dest_cnt==fanout.
182 : Results are stored in out, but there's some awkwardness associated
183 : with something that's logically a 2d array, so out_stride specifies
184 : the number of elements in each logical row of the output.
185 : Precisely, destination j for shred i is written to out[ j*out_stride
186 : + i ]. Graphically:
187 : [ shred0 dest0, shred1 dest0, shred2 dest0, ... (skip until stride)
188 : shred0 dest1, shred1 dest1, shred2 dest1, ... (skip until 2stride)
189 : ...
190 : shred0 dest dest_cnt-1, ... ].
191 : out_stride must be at least shred_cnt.
192 : If opt_max_dest_cnt is non-NULL, the maximum number of real
193 : destinations for any of the provided shreds will be stored in
194 : opt_max_dest_cnt. This value is always <= dest_cnt, but in many
195 : cases may be much lower (especially if the source validator has low
196 : stake).
197 :
198 : Returns out on success and NULL on failure. */
199 : /* TODO: Would it be better if out were transposed? Should I get rid of
200 : stride? */
201 : fd_shred_dest_idx_t *
202 : fd_shred_dest_compute_children( fd_shred_dest_t * sdest,
203 : fd_shred_t const * const * input_shreds,
204 : ulong shred_cnt,
205 : fd_shred_dest_idx_t * out,
206 : ulong out_stride,
207 : ulong fanout,
208 : ulong dest_cnt,
209 : ulong * opt_max_dest_cnt );
210 :
211 : /* fd_shred_dest_idx_to_dest maps a destination index (as produced by
212 : fd_shred_dest_compute_children or fd_shred_dest_compute_first) to an
213 : actual destination. The lifetime of the returned pointer is the same
214 : as the lifetime of sdest. idx==FD_SHRED_DEST_NO_DEST is fine, and
215 : this will return a pointer to a destination with all fields set to 0.
216 : It's safe for the caller to update the IP, port, and mac fields of
217 : the returned struct, although the caller must not modify the weight
218 : or pubkey fields. The caller can use this to update contact info for
219 : a validator. */
220 : static inline fd_shred_dest_weighted_t *
221 7974777 : fd_shred_dest_idx_to_dest( fd_shred_dest_t * sdest, fd_shred_dest_idx_t idx ) {
222 7974777 : return fd_ptr_if( idx!=FD_SHRED_DEST_NO_DEST, sdest->all_destinations + idx, sdest->null_dest );
223 7974777 : }
224 :
225 : /* fd_shred_dest_idx_t maps a pubkey to a destination index, if the
226 : pubkey is known as a destination. If the pubkey is not know, returns
227 : FD_SHRED_DEST_NO_DEST. */
228 : fd_shred_dest_idx_t fd_shred_dest_pubkey_to_idx( fd_shred_dest_t * sdest, fd_pubkey_t const * pubkey );
229 :
230 : /* fd_shred_dest_update_source changes the shred destination
231 : computation's notion of source. sdest must be a valid local join.
232 : idx must be in [0, staked_cnt+unstaked_cnt). In particular, idx must
233 : not be FD_SHRED_DEST_NO_DEST. idx is as returned from
234 : fd_shred_dest_pubkey_to_idx. */
235 : static inline void
236 18 : fd_shred_dest_update_source( fd_shred_dest_t * sdest, fd_shred_dest_idx_t idx ) {
237 18 : sdest->source_validator_orig_idx = idx;
238 18 : }
239 :
240 : #endif /* HEADER_fd_src_disco_shred_fd_shred_dest_h */
|
