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