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 200 destinations for each
14 : 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 2 B, since currently Turbine doesn't work with
17 : more than fanout^2 nodes which is less than USHORT_MAX. Thus, we go
18 : with the index, which can cheaply be mapped to the full information
19 : using fd_shred_dest_idx_to_dest below. */
20 : typedef ushort fd_shred_dest_idx_t;
21 :
22 :
23 : #define FD_SHRED_DEST_MAX_SHRED_CNT (134UL) /* DATA_SHREDS_MAX+PARITY_SHREDS_MAX */
24 777739035 : #define FD_SHRED_DEST_NO_DEST (USHORT_MAX)
25 :
26 : /* fd_shred_dest_weighted_t specifies a destination to which a shred might be
27 : sent. The information comes from Gossip typically. */
28 : struct fd_shred_dest_weighted {
29 : fd_pubkey_t pubkey; /* The validator's identity key */
30 : ulong stake_lamports; /* Stake, measured in lamports, or 0 for an unstaked validator */
31 : uint ip4; /* The validator's IP address, in host byte order */
32 : ushort port; /* The TVU port, in host byte order */
33 : };
34 : typedef struct fd_shred_dest_weighted fd_shred_dest_weighted_t;
35 :
36 : /* Internal type, forward declared to be able to declare the struct
37 : here. */
38 : struct pubkey_to_idx;
39 : typedef struct pubkey_to_idx pubkey_to_idx_t;
40 :
41 1180029 : #define FD_SHRED_DEST_ALIGN (128UL)
42 : FD_STATIC_ASSERT( FD_SHRED_DEST_ALIGN>=FD_SHA256_BATCH_ALIGN, fd_shred_dest_private_align );
43 :
44 : struct __attribute__((aligned(FD_SHRED_DEST_ALIGN))) fd_shred_dest_private {
45 : uchar _sha256_batch[ FD_SHA256_BATCH_FOOTPRINT ] __attribute__((aligned(FD_SHA256_BATCH_ALIGN)));
46 : fd_chacha20rng_t rng[1];
47 :
48 : /* null_dest is initialized to all zeros. Returned when the destination
49 : doesn't exist (e.g. you've asked for the 5th destination, but you only
50 : need to send to 4 recipients. */
51 : fd_shred_dest_weighted_t null_dest[1];
52 :
53 : fd_epoch_leaders_t const * lsched;
54 :
55 : ulong cnt;
56 : fd_shred_dest_weighted_t * all_destinations; /* a local copy, points to memory after the struct */
57 :
58 : fd_wsample_t * staked;
59 : struct {
60 : /* These two variables are maintained by the unstaked sampling functions. */
61 : ulong * unstaked;
62 : ulong unstaked_unremoved_cnt;
63 : };
64 : ulong staked_cnt;
65 : ulong unstaked_cnt;
66 :
67 : ulong excluded_stake;
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 1180029 : 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. If the
100 : number of staked validators exceeds the caller's maximum list
101 : capacity, the list can be truncated, with excluded_stake set to the
102 : sum of the excluded staked validators. In that case, info should not
103 : contain any unstaked validators.
104 :
105 : Each fd_shred_dest_t object is tied to a specific epoch, and so the
106 : stake weights are constant within the epoch. The information in info
107 : will be copied, and no read interest in info will be retained.
108 : lsched points to a local join of an fd_epoch_leaders_t object with
109 : the leader information for the slots when the shreds for which this
110 : shred dest object computes destinations were produced. This function
111 : retains a read interest in lsched that persists until the memory is
112 : unformatted. `source` points to the public key of the identity key
113 : of the current validator, i.e. the one who sends out the shreds
114 : computed by this object. info must contain contact info for
115 : `source,` although it will never be returned as a destination.
116 :
117 : Returns mem on success and NULL on errors. Logs a warning with
118 : details on errors. */
119 : void *
120 : fd_shred_dest_new( void * mem,
121 : fd_shred_dest_weighted_t const * info, /* Accessed [0, cnt) */
122 : ulong cnt,
123 : fd_epoch_leaders_t const * lsched,
124 : fd_pubkey_t const * source,
125 : ulong excluded_stake );
126 :
127 : /* fd_shred_dest_join joins the caller to a region of memory formatted
128 : as an fd_shred_dest_t. fd_shred_dest_leave does the opposite.
129 : fd_shred_dest_delete unformats a region of memory. */
130 : fd_shred_dest_t * fd_shred_dest_join( void * mem );
131 : void * fd_shred_dest_leave( fd_shred_dest_t * sdest );
132 : void * fd_shred_dest_delete( void * mem );
133 :
134 : /* fd_shred_dest_cnt_{staked, unstaked, all} returns the number of known
135 : destination that are staked, unstaked, or either, respectively. The
136 : staked destinations have index [0, fd_shred_dest_cnt_staked()) and
137 : the unstaked destinations have index [fd_shred_dest_cnt_staked(),
138 : fd_shred_dest_cnt_all() ). fd_shred_dest_cnt_all() ==
139 : fd_shred_dest_cnt_staked() + fd_shred_dest_cnt_unstaked(). */
140 345 : static inline ulong fd_shred_dest_cnt_staked ( fd_shred_dest_t * sdest ) { return sdest->staked_cnt ; }
141 234 : static inline ulong fd_shred_dest_cnt_unstaked( fd_shred_dest_t * sdest ) { return sdest->unstaked_cnt; }
142 90 : static inline ulong fd_shred_dest_cnt_all ( fd_shred_dest_t * sdest ) { return sdest->staked_cnt + sdest->unstaked_cnt; }
143 :
144 : /* fd_shred_dest_compute_first computes the root of the Turbine tree for
145 : each of the provided shreds. All the provided shreds must come from
146 : the same slot (and thus have the same leader). This should only be
147 : called for shreds from a slot in which the source validator provided
148 : in _new is the leader (determined using the leader schedule provided
149 : in _new). shred_cnt specifies the number of shreds for which
150 : destinations should be computes. input_shreds is accessed
151 : input_shreds[i] for i in [0, shred_cnt). shred_cnt must be in [0,
152 : 67]. The destination index for input_shreds[i] is stored at out[i].
153 : input_shreds==NULL is fine if shred_cnt==0, in which case this
154 : function is a no-op. Returns out on success and NULL on failure.
155 : This function uses the sha256 batch API internally for performance,
156 : which is why it operates on several shreds at the same time as
157 : opposed to one at a time. */
158 : fd_shred_dest_idx_t *
159 : fd_shred_dest_compute_first( fd_shred_dest_t * sdest,
160 : fd_shred_t const * const * input_shreds,
161 : ulong shred_cnt,
162 : fd_shred_dest_idx_t * out );
163 :
164 : /* fd_shred_dest_compute_children computes the source validator's
165 : children in the Turbine tree for each of the provided shreds.
166 : Although Solana has the concept of "neighborhoods" in Turbine, we
167 : treat it as a standard high-radix tree, and a child is any validator
168 : to which the source validator should send the shred directly.
169 : All provided shreds must be from the same slot, and that leader for
170 : that slot must be known by the leader schedule. As in
171 : fd_shred_dest_compute_first, shred_cnt specifies the number of
172 : shreds, input_shreds is accessed input_shreds[i] for i in [0,
173 : shred_cnt), and 0<=shred_cnt<=67. Computes the first dest_cnt
174 : destinations for each shred, using a tree with fanout `fanout`.
175 : Exactly dest_cnt destination indices will be written for each shreds,
176 : so if that is more than the number of destinations that the source
177 : validator needs to send to, it will be padded out with
178 : FD_SHRED_DEST_NO_DEST. The typical case is to pass dest_cnt==fanout.
179 : Results are stored in out, but there's some awkwardness associated
180 : with something that's logically a 2d array, so out_stride specifies
181 : the number of elements in each logical row of the output.
182 : Precisely, destination j for shred i is written to out[ j*out_stride
183 : + i ]. Graphically:
184 : [ shred0 dest0, shred1 dest0, shred2 dest0, ... (skip until stride)
185 : shred0 dest1, shred1 dest1, shred2 dest1, ... (skip until 2stride)
186 : ...
187 : shred0 dest dest_cnt-1, ... ].
188 : out_stride must be at least shred_cnt.
189 : If opt_max_dest_cnt is non-NULL, the maximum number of real
190 : destinations for any of the provided shreds will be stored in
191 : opt_max_dest_cnt. This value is always <= dest_cnt, but in many
192 : cases may be much lower (especially if the source validator has low
193 : stake).
194 :
195 : Returns out on success and NULL on failure. */
196 : /* TODO: Would it be better if out were transposed? Should I get rid of
197 : stride? */
198 : fd_shred_dest_idx_t *
199 : fd_shred_dest_compute_children( fd_shred_dest_t * sdest,
200 : fd_shred_t const * const * input_shreds,
201 : ulong shred_cnt,
202 : fd_shred_dest_idx_t * out,
203 : ulong out_stride,
204 : ulong fanout,
205 : ulong dest_cnt,
206 : ulong * opt_max_dest_cnt );
207 :
208 : /* fd_shred_dest_idx_to_dest maps a destination index (as produced by
209 : fd_shred_dest_compute_children or fd_shred_dest_compute_first) to an
210 : actual destination. The lifetime of the returned pointer is the same
211 : as the lifetime of sdest. idx==FD_SHRED_DEST_NO_DEST is fine, and
212 : this will return a pointer to a destination with all fields set to 0.
213 : It's safe for the caller to update the IP, port, and mac fields of
214 : the returned struct, although the caller must not modify the weight
215 : or pubkey fields. The caller can use this to update contact info for
216 : a validator. */
217 : static inline fd_shred_dest_weighted_t *
218 6282771 : fd_shred_dest_idx_to_dest( fd_shred_dest_t * sdest, fd_shred_dest_idx_t idx ) {
219 6282771 : return fd_ptr_if( idx!=FD_SHRED_DEST_NO_DEST, sdest->all_destinations + idx, sdest->null_dest );
220 6282771 : }
221 :
222 : /* fd_shred_dest_idx_t maps a pubkey to a destination index, if the
223 : pubkey is known as a destination. If the pubkey is not know, returns
224 : FD_SHRED_DEST_NO_DEST. */
225 : fd_shred_dest_idx_t fd_shred_dest_pubkey_to_idx( fd_shred_dest_t * sdest, fd_pubkey_t const * pubkey );
226 :
227 : /* fd_shred_dest_update_source changes the shred destination
228 : computation's notion of source. sdest must be a valid local join.
229 : idx must be in [0, staked_cnt+unstaked_cnt). In particular, idx must
230 : not be FD_SHRED_DEST_NO_DEST. idx is as returned from
231 : fd_shred_dest_pubkey_to_idx. */
232 : static inline void
233 18 : fd_shred_dest_update_source( fd_shred_dest_t * sdest, fd_shred_dest_idx_t idx ) {
234 18 : sdest->source_validator_orig_idx = idx;
235 18 : }
236 :
237 : #endif /* HEADER_fd_src_disco_shred_fd_shred_dest_h */
|
