Line data Source code
1 : #ifndef HEADER_fd_src_discof_repair_fd_policy_h
2 : #define HEADER_fd_src_discof_repair_fd_policy_h
3 :
4 : /* fd_policy implements the policy of the Repair agent. It determines
5 : what shreds the validator is expecting but has not yet received and
6 : needs to request via repair. It also determines which peer(s) the
7 : validator should request the shred from.
8 :
9 : The default policy implementation is round-robin DFS with time-based
10 : dedup: round-robin through all the repair peers we know about, and
11 : depth-first search down the repair forest (see fd_forest.h). This
12 : policy also dedups identical repair requests that occur within a
13 : specified amount of time window of each other (configurable on init
14 : as a hyperparameter). With the DFS strategy, the smaller the tree,
15 : the sooner an element will be iterated again (when the DFS restarts
16 : from the root of the tree). */
17 :
18 : #include "../../flamenco/types/fd_types_custom.h"
19 : #include "../forest/fd_forest.h"
20 : #include "../../util/net/fd_net_headers.h"
21 : #include "fd_repair.h"
22 :
23 : /* FD_POLICY_PEER_MAX specifies a hard bound for how many peers Policy
24 : needs to track. 4096 is derived from the BLS signature max, which
25 : is the maximum number of staked validators Solana can support. */
26 :
27 : #define FD_POLICY_PEER_MAX (4096UL)
28 :
29 : /* fd_policy_dedup implements a dedup cache for already sent Repair
30 : requests. It is backed by a map and linked list, in which the least
31 : recently used (oldest Repair request) in the map is evicted when the
32 : map is full. */
33 :
34 : typedef struct fd_policy_dedup fd_policy_dedup_t; /* forward decl */
35 :
36 : /* fd_policy_dedup_ele describes an element in the dedup cache. The key
37 : compactly encodes an fd_repair_req_t.
38 :
39 : | kind (2 bits) | slot (32 bits) | shred_idx (15 bits) |
40 : | 0x0 (SHRED) | slot | shred_idx |
41 : | 0x1 (HIGHEST_SHRED) | slot | >=shred_idx |
42 : | 0x2 (ORPHAN) | orphan slot | N/A |
43 :
44 : Note the common header (sig, from, to, ts, nonce) is not included. */
45 :
46 : struct fd_policy_dedup_ele {
47 : ulong key; /* compact encoding of fd_repair_req_t detailed above */
48 : ulong prev; /* reserved by lru */
49 : ulong next;
50 : ulong hash; /* reserved by pool and map_chain */
51 : long req_ts; /* timestamp when the request was sent */
52 : };
53 : typedef struct fd_policy_dedup_ele fd_policy_dedup_ele_t;
54 :
55 : FD_FN_CONST static inline ulong
56 0 : fd_policy_dedup_key( uint kind, ulong slot, uint shred_idx ) {
57 0 : return (ulong)kind << 61 | slot << 30 | shred_idx << 15;
58 0 : }
59 :
60 0 : FD_FN_CONST static inline uint fd_policy_dedup_key_kind ( ulong key ) { return (uint)fd_ulong_extract( key, 62, 63 ); }
61 0 : FD_FN_CONST static inline ulong fd_policy_dedup_key_slot ( ulong key ) { return fd_ulong_extract( key, 30, 61 ); }
62 0 : FD_FN_CONST static inline uint fd_policy_dedup_key_shred_idx( ulong key ) { return (uint)fd_ulong_extract( key, 15, 29 ); }
63 :
64 : #define POOL_NAME fd_policy_dedup_pool
65 0 : #define POOL_T fd_policy_dedup_ele_t
66 0 : #define POOL_NEXT hash
67 : #include "../../util/tmpl/fd_pool.c"
68 :
69 : #define MAP_NAME fd_policy_dedup_map
70 : #define MAP_ELE_T fd_policy_dedup_ele_t
71 0 : #define MAP_NEXT hash
72 : #include "../../util/tmpl/fd_map_chain.c"
73 :
74 : #define DLIST_NAME fd_policy_dedup_lru
75 : #define DLIST_ELE_T fd_policy_dedup_ele_t
76 0 : #define DLIST_NEXT next
77 0 : #define DLIST_PREV prev
78 : #include "../../util/tmpl/fd_dlist.c"
79 : struct fd_policy_dedup {
80 : fd_policy_dedup_map_t * map; /* map of dedup elements */
81 : fd_policy_dedup_ele_t * pool; /* memory pool of dedup elements */
82 : fd_policy_dedup_lru_t * lru; /* singly-linked list of dedup elements by insertion order. TODO: add eviction feature using linkedlist */
83 : };
84 :
85 : /* fd_policy_peer_t describes a peer validator that serves repairs.
86 : Peers are discovered through gossip, via a "ContactInfo" message that
87 : shares the validator's ip and repair server port. */
88 :
89 : struct fd_policy_peer {
90 : fd_pubkey_t key; /* map key, pubkey of the validator */
91 : uint hash; /* reserved for map */
92 : uint ip4; /* ip4 addr of the peer */
93 : ushort port; /* repair server port of the peer */
94 : ulong req_cnt; /* count of requests we've sent to this peer */
95 : ulong res_cnt; /* count of responses we've received from this peer */
96 :
97 : /* below are for measuring bandwidth usage */
98 : long first_req_ts;
99 : long last_req_ts;
100 :
101 : long first_resp_ts;
102 : long last_resp_ts;
103 :
104 : long total_lat; /* total RTT over all responses in ns */
105 : ulong stake;
106 :
107 : ulong pool_idx;
108 : };
109 : typedef struct fd_policy_peer fd_policy_peer_t;
110 :
111 : #define MAP_NAME fd_policy_peer_map
112 0 : #define MAP_T fd_policy_peer_t
113 0 : #define MAP_KEY_T fd_pubkey_t
114 0 : #define MAP_KEY_NULL null_pubkey
115 : #define MAP_KEY_EQUAL_IS_SLOW 1
116 : #define MAP_MEMOIZE 0
117 0 : #define MAP_KEY_INVAL(k) MAP_KEY_EQUAL((k),MAP_KEY_NULL)
118 0 : #define MAP_KEY_EQUAL(k0,k1) (!memcmp( (k0).key, (k1).key, 32UL ))
119 0 : #define MAP_KEY_HASH(key) ((MAP_HASH_T)( (key).ul[1] ))
120 : #include "../../util/tmpl/fd_map_dynamic.c"
121 :
122 : struct fd_peer {
123 : fd_pubkey_t identity;
124 : ulong next;
125 : ulong prev;
126 : };
127 : typedef struct fd_peer fd_peer_t;
128 :
129 : #define POOL_NAME fd_peer_pool
130 0 : #define POOL_T fd_peer_t
131 : #include "../../util/tmpl/fd_pool.c"
132 :
133 : #define DLIST_NAME fd_peer_dlist
134 : #define DLIST_ELE_T fd_peer_t
135 0 : #define DLIST_NEXT next
136 0 : #define DLIST_PREV prev
137 : #include "../../util/tmpl/fd_dlist.c"
138 :
139 : /* fd_policy_peers implements the data structures and bookkeeping for
140 : selecting repair peers via round-robin. */
141 :
142 : struct fd_policy_peers {
143 : fd_peer_t * pool; /* memory pool of repair peer pubkeys, contains entries of both dlist */
144 : fd_peer_dlist_t * fast; /* [0, FD_POLICY_LATENCY_THRESH] ms latency group FD_POLICY_LATENCY_FAST */
145 : fd_peer_dlist_t * slow; /* (FD_POLICY_LATENCY_THRESH, inf) ms latency group FD_POLICY_LATENCY_SLOW */
146 : fd_policy_peer_t * map; /* map dynamic of pubkey->peer data */
147 : struct {
148 : uint stage; /* < sizeof(bucket_stages) */
149 : fd_peer_dlist_iter_t iter; /* round-robin index of next peer */
150 : } select;
151 : };
152 : typedef struct fd_policy_peers fd_policy_peers_t;
153 :
154 0 : #define FD_POLICY_LATENCY_FAST 1
155 : #define FD_POLICY_LATENCY_SLOW 3
156 :
157 : /* Policy parameters start */
158 0 : #define FD_POLICY_LATENCY_THRESH 30e6L /* less than this is a BEST peer, otherwise a WORST peer */
159 : #define FD_POLICY_DEDUP_TIMEOUT 50e6L /* how long wait to request the same shred */
160 :
161 : /* Round robins through ALL the worst peers once, then round robins
162 : through ALL the best peers once, then round robins through ALL the
163 : best peers again, etc. All peers are initially added to the worst
164 : bucket, and moved once round trip times have been recorded. */
165 :
166 : static const uint bucket_stages[7] = {
167 : FD_POLICY_LATENCY_SLOW, /* do a cycle through worst peers 1/7 times to see if any improvements are made */
168 : FD_POLICY_LATENCY_FAST,
169 : FD_POLICY_LATENCY_FAST,
170 : FD_POLICY_LATENCY_FAST,
171 : FD_POLICY_LATENCY_FAST,
172 : FD_POLICY_LATENCY_FAST,
173 : FD_POLICY_LATENCY_FAST,
174 : };
175 : /* Policy parameters end */
176 :
177 : struct fd_policy {
178 : fd_policy_dedup_t dedup; /* dedup cache of already sent requests */
179 : fd_policy_peers_t peers; /* repair peers (strategy & data) */
180 : long tsmax; /* maximum time for an iteration before resetting the DFS to root */
181 : long tsref; /* reference timestamp for resetting DFS */
182 :
183 : fd_forest_iter_t iterf; /* forest iterator */
184 : ulong tsreset; /* ms timestamp of last reset of iterf */
185 :
186 : ulong turbine_slot0;
187 : uint nonce;
188 : };
189 : typedef struct fd_policy fd_policy_t;
190 :
191 : /* Constructors */
192 :
193 : /* fd_policy_{align,footprint} return the required alignment and
194 : footprint of a memory region suitable for use as policy with up to
195 : ele_max eles and vote_max votes. */
196 :
197 : FD_FN_CONST static inline ulong
198 0 : fd_policy_align( void ) {
199 0 : return alignof(fd_policy_t);
200 0 : }
201 :
202 : FD_FN_CONST static inline ulong
203 0 : fd_policy_footprint( ulong dedup_max, ulong peer_max ) {
204 0 : int lg_peer_max = fd_ulong_find_msb( fd_ulong_pow2_up( peer_max ) );
205 0 : return FD_LAYOUT_FINI(
206 0 : FD_LAYOUT_APPEND(
207 0 : FD_LAYOUT_APPEND(
208 0 : FD_LAYOUT_APPEND(
209 0 : FD_LAYOUT_APPEND(
210 0 : FD_LAYOUT_APPEND(
211 0 : FD_LAYOUT_APPEND(
212 0 : FD_LAYOUT_APPEND(
213 0 : FD_LAYOUT_APPEND(
214 0 : FD_LAYOUT_INIT,
215 0 : alignof(fd_policy_t), sizeof(fd_policy_t) ),
216 0 : fd_policy_dedup_map_align(), fd_policy_dedup_map_footprint ( dedup_max ) ),
217 0 : fd_policy_dedup_pool_align(), fd_policy_dedup_pool_footprint( dedup_max ) ),
218 0 : fd_policy_dedup_lru_align(), fd_policy_dedup_lru_footprint() ),
219 0 : fd_policy_peer_map_align(), fd_policy_peer_map_footprint ( lg_peer_max ) ),
220 0 : fd_peer_pool_align(), fd_peer_pool_footprint ( peer_max ) ),
221 0 : fd_peer_dlist_align(), fd_peer_dlist_footprint() ),
222 0 : fd_peer_dlist_align(), fd_peer_dlist_footprint() ),
223 0 : fd_policy_align() );
224 0 : }
225 :
226 : /* fd_policy_new formats an unused memory region for use as a policy.
227 : mem is a non-NULL pointer to this region in the local address space
228 : with the required footprint and alignment. */
229 :
230 : void *
231 : fd_policy_new( void * shmem, ulong dedup_max, ulong peer_max, ulong seed );
232 :
233 : /* fd_policy_join joins the caller to the policy. policy points to the
234 : first byte of the memory region backing the policy in the caller's
235 : address space. Returns a pointer in the local address space to
236 : policy on success. */
237 :
238 : fd_policy_t *
239 : fd_policy_join( void * policy );
240 :
241 : /* fd_policy_leave leaves a current local join. Returns a pointer to
242 : the underlying shared memory region on success and NULL on failure
243 : (logs details). Reasons for failure include policy is NULL. */
244 :
245 : void *
246 : fd_policy_leave( fd_policy_t const * policy );
247 :
248 : /* fd_policy_delete unformats a memory region used as a policy. Assumes
249 : only the nobody is joined to the region. Returns a pointer to the
250 : underlying shared memory region or NULL if used obviously in error
251 : (e.g. policy is obviously not a policy ... logs details). The
252 : ownership of the memory region is transferred to the caller. */
253 :
254 : void *
255 : fd_policy_delete( void * policy );
256 :
257 : /* fd_policy_next returns the next repair request that should be made.
258 : Currently implements the default round-robin DFS strategy. */
259 :
260 : fd_repair_msg_t const *
261 : fd_policy_next( fd_policy_t * policy, fd_forest_t * forest, fd_repair_t * repair, long now, ulong highest_known_slot );
262 :
263 : fd_policy_peer_t const *
264 : fd_policy_peer_insert( fd_policy_t * policy, fd_pubkey_t const * key, fd_ip4_port_t const * addr );
265 :
266 : fd_policy_peer_t *
267 : fd_policy_peer_query( fd_policy_t * policy, fd_pubkey_t const * key );
268 :
269 : int
270 : fd_policy_peer_remove( fd_policy_t * policy, fd_pubkey_t const * key );
271 :
272 : fd_pubkey_t const *
273 : fd_policy_peer_select( fd_policy_t * policy );
274 :
275 : void
276 : fd_policy_peer_request_update( fd_policy_t * policy, fd_pubkey_t const * to );
277 :
278 : static inline fd_peer_dlist_t *
279 0 : fd_policy_peer_latency_bucket( fd_policy_t * policy, long total_rtt /* ns */, ulong res_cnt ) {
280 0 : if( res_cnt == 0 || (long)(total_rtt / (long)res_cnt) > FD_POLICY_LATENCY_THRESH ) return policy->peers.slow;
281 0 : return policy->peers.fast;
282 0 : }
283 :
284 : void
285 : fd_policy_peer_response_update( fd_policy_t * policy, fd_pubkey_t const * to, long rtt );
286 :
287 : void
288 : fd_policy_set_turbine_slot0( fd_policy_t * policy, ulong slot );
289 :
290 : void
291 : fd_policy_reset( fd_policy_t * policy, fd_forest_t * forest );
292 :
293 : #endif /* HEADER_fd_src_discof_repair_fd_policy_h */
|
