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 777739035 : #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 1180029 : #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_chacha20rng_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 1180029 : 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 345 : static inline ulong fd_shred_dest_cnt_staked ( fd_shred_dest_t * sdest ) { return sdest->staked_cnt ; }
143 234 : static inline ulong fd_shred_dest_cnt_unstaked( fd_shred_dest_t * sdest ) { return sdest->unstaked_cnt; }
144 90 : 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. Returns out on success and NULL on failure.
157 : This function uses the sha256 batch API internally for performance,
158 : which is why it operates on several shreds at the same time as
159 : opposed to one at a time. */
160 : fd_shred_dest_idx_t *
161 : fd_shred_dest_compute_first( fd_shred_dest_t * sdest,
162 : fd_shred_t const * const * input_shreds,
163 : ulong shred_cnt,
164 : fd_shred_dest_idx_t * out );
165 :
166 : /* fd_shred_dest_compute_children computes the source validator's
167 : children in the Turbine tree for each of the provided shreds.
168 : Although Solana has the concept of "neighborhoods" in Turbine, we
169 : treat it as a standard high-radix tree, and a child is any validator
170 : to which the source validator should send the shred directly.
171 : All provided shreds must be from the same slot, and that leader for
172 : that slot must be known by the leader schedule. As in
173 : fd_shred_dest_compute_first, shred_cnt specifies the number of
174 : shreds, input_shreds is accessed input_shreds[i] for i in [0,
175 : shred_cnt), and 0<=shred_cnt<=67. Computes the first dest_cnt
176 : destinations for each shred, using a tree with fanout `fanout`.
177 : Exactly dest_cnt destination indices will be written for each shreds,
178 : so if that is more than the number of destinations that the source
179 : validator needs to send to, it will be padded out with
180 : FD_SHRED_DEST_NO_DEST. The typical case is to pass dest_cnt==fanout.
181 : Results are stored in out, but there's some awkwardness associated
182 : with something that's logically a 2d array, so out_stride specifies
183 : the number of elements in each logical row of the output.
184 : Precisely, destination j for shred i is written to out[ j*out_stride
185 : + i ]. Graphically:
186 : [ shred0 dest0, shred1 dest0, shred2 dest0, ... (skip until stride)
187 : shred0 dest1, shred1 dest1, shred2 dest1, ... (skip until 2stride)
188 : ...
189 : shred0 dest dest_cnt-1, ... ].
190 : out_stride must be at least shred_cnt.
191 : If opt_max_dest_cnt is non-NULL, the maximum number of real
192 : destinations for any of the provided shreds will be stored in
193 : opt_max_dest_cnt. This value is always <= dest_cnt, but in many
194 : cases may be much lower (especially if the source validator has low
195 : stake).
196 :
197 : Returns out on success and NULL on failure. */
198 : /* TODO: Would it be better if out were transposed? Should I get rid of
199 : stride? */
200 : fd_shred_dest_idx_t *
201 : fd_shred_dest_compute_children( fd_shred_dest_t * sdest,
202 : fd_shred_t const * const * input_shreds,
203 : ulong shred_cnt,
204 : fd_shred_dest_idx_t * out,
205 : ulong out_stride,
206 : ulong fanout,
207 : ulong dest_cnt,
208 : ulong * opt_max_dest_cnt );
209 :
210 : /* fd_shred_dest_idx_to_dest maps a destination index (as produced by
211 : fd_shred_dest_compute_children or fd_shred_dest_compute_first) to an
212 : actual destination. The lifetime of the returned pointer is the same
213 : as the lifetime of sdest. idx==FD_SHRED_DEST_NO_DEST is fine, and
214 : this will return a pointer to a destination with all fields set to 0.
215 : It's safe for the caller to update the IP, port, and mac fields of
216 : the returned struct, although the caller must not modify the weight
217 : or pubkey fields. The caller can use this to update contact info for
218 : a validator. */
219 : static inline fd_shred_dest_weighted_t *
220 6282771 : fd_shred_dest_idx_to_dest( fd_shred_dest_t * sdest, fd_shred_dest_idx_t idx ) {
221 6282771 : return fd_ptr_if( idx!=FD_SHRED_DEST_NO_DEST, sdest->all_destinations + idx, sdest->null_dest );
222 6282771 : }
223 :
224 : /* fd_shred_dest_idx_t maps a pubkey to a destination index, if the
225 : pubkey is known as a destination. If the pubkey is not know, returns
226 : FD_SHRED_DEST_NO_DEST. */
227 : fd_shred_dest_idx_t fd_shred_dest_pubkey_to_idx( fd_shred_dest_t * sdest, fd_pubkey_t const * pubkey );
228 :
229 : /* fd_shred_dest_update_source changes the shred destination
230 : computation's notion of source. sdest must be a valid local join.
231 : idx must be in [0, staked_cnt+unstaked_cnt). In particular, idx must
232 : not be FD_SHRED_DEST_NO_DEST. idx is as returned from
233 : fd_shred_dest_pubkey_to_idx. */
234 : static inline void
235 18 : fd_shred_dest_update_source( fd_shred_dest_t * sdest, fd_shred_dest_idx_t idx ) {
236 18 : sdest->source_validator_orig_idx = idx;
237 18 : }
238 :
239 : #endif /* HEADER_fd_src_disco_shred_fd_shred_dest_h */
|
