Line data Source code
1 : #include "fd_sysvar.h"
2 : #include "fd_sysvar_clock.h"
3 : #include "fd_sysvar_epoch_schedule.h"
4 : #include "../fd_acc_mgr.h"
5 : #include "../fd_system_ids.h"
6 :
7 : /* Syvar Clock Possible Values:
8 : slot:
9 : [0, ULONG_MAX]
10 :
11 : epoch:
12 : [0, slot/432000UL]
13 :
14 : epoch_start_timestamp:
15 : [0, ULONG_MAX]
16 :
17 : unix_timestamp:
18 : This value is bounded by the slot distance from the
19 : epoch_start_timestamp.
20 : The protocol allows for a maximum drift (either fast or slow) from the
21 : start of the epoch's timestamp. The expected time is called the PoH
22 : offset. This offset is calculated by (epoch_start_timestamp + slots
23 : since epoch * slot_duration). The drift is then bounded by the
24 : max_allowable_drift_{slow,fast}. The stake weighted offset can be
25 : 150% more than the PoH offset and 25% less than the PoH offset.
26 : So, the bounds for the unix_timestamp can be calculated by:
27 : upper bound = epoch_start_timestamp + (slots since epoch * slot_duration) * 2.5
28 : lower bound = epoch_start_timestamp + (slots since epoch * slot_duration) * 0.75
29 :
30 : leader_schedule_epoch:
31 : This is the value of the epoch used for the leader schedule. It is
32 : computed based on the values of the epoch schedule (first_normal_slot,
33 : leader_schedule_slot_offset, slots_per_epoch). It is always equal to
34 : ((slot - first_normal_slot) + leader_schedule_slot_offset) / schedule->slots_per_epoch
35 : */
36 :
37 : /* https://github.com/anza-xyz/agave/blob/v2.3.7/runtime/src/stake_weighted_timestamp.rs#L14 */
38 0 : #define MAX_ALLOWABLE_DRIFT_FAST_PERCENT ( 25U )
39 :
40 : /* https://github.com/anza-xyz/agave/blob/v2.3.7/runtime/src/stake_weighted_timestamp.rs#L15 */
41 0 : #define MAX_ALLOWABLE_DRIFT_SLOW_PERCENT ( 150U )
42 :
43 : /* Do all intermediate calculations at nanosecond precision, to mirror
44 : Solana's behavior. */
45 0 : #define NS_IN_S ((long)1e9)
46 :
47 : /* https://github.com/anza-xyz/agave/blob/v2.3.7/runtime/src/stake_weighted_timestamps.rs#L2110-L2117 */
48 : static inline long
49 0 : unix_timestamp_from_genesis( fd_bank_t * bank ) {
50 : /* TODO: genesis_creation_time needs to be a long in the bank. */
51 0 : return fd_long_sat_add(
52 0 : (long)fd_bank_genesis_creation_time_get( bank ),
53 0 : (long)( fd_uint128_sat_mul( fd_bank_slot_get( bank ), fd_bank_ns_per_slot_get( bank ) ) / NS_IN_S ) );
54 0 : }
55 :
56 : void
57 : fd_sysvar_clock_write( fd_bank_t * bank,
58 : fd_funk_t * funk,
59 : fd_funk_txn_xid_t const * xid,
60 : fd_capture_ctx_t * capture_ctx,
61 0 : fd_sol_sysvar_clock_t * clock ) {
62 0 : uchar enc[ sizeof(fd_sol_sysvar_clock_t) ];
63 0 : fd_bincode_encode_ctx_t ctx = {
64 0 : .data = enc,
65 0 : .dataend = enc + sizeof(fd_sol_sysvar_clock_t),
66 0 : };
67 0 : if( FD_UNLIKELY( fd_sol_sysvar_clock_encode( clock, &ctx ) ) ) {
68 0 : FD_LOG_ERR(( "fd_sol_sysvar_clock_encode failed" ));
69 0 : }
70 :
71 0 : fd_sysvar_account_update( bank, funk, xid, capture_ctx, &fd_sysvar_clock_id, enc, sizeof(fd_sol_sysvar_clock_t) );
72 0 : }
73 :
74 :
75 : fd_sol_sysvar_clock_t *
76 : fd_sysvar_clock_read( fd_funk_t * funk,
77 : fd_funk_txn_xid_t const * xid,
78 0 : fd_sol_sysvar_clock_t * clock ) {
79 0 : FD_TXN_ACCOUNT_DECL( acc );
80 0 : int rc = fd_txn_account_init_from_funk_readonly( acc, &fd_sysvar_clock_id, funk, xid );
81 0 : if( FD_UNLIKELY( rc!=FD_ACC_MGR_SUCCESS ) ) {
82 0 : return NULL;
83 0 : }
84 :
85 : /* This check is needed as a quirk of the fuzzer. If a sysvar account
86 : exists in the accounts database, but doesn't have any lamports,
87 : this means that the account does not exist. This wouldn't happen
88 : in a real execution environment. */
89 0 : if( FD_UNLIKELY( fd_txn_account_get_lamports( acc )==0UL ) ) {
90 0 : return NULL;
91 0 : }
92 :
93 0 : return fd_bincode_decode_static(
94 0 : sol_sysvar_clock, clock,
95 0 : fd_txn_account_get_data( acc ),
96 0 : fd_txn_account_get_data_len( acc ),
97 0 : &err );
98 0 : }
99 :
100 : void
101 : fd_sysvar_clock_init( fd_bank_t * bank,
102 : fd_funk_t * funk,
103 : fd_funk_txn_xid_t const * xid,
104 0 : fd_capture_ctx_t * capture_ctx ) {
105 0 : long timestamp = unix_timestamp_from_genesis( bank );
106 :
107 0 : fd_sol_sysvar_clock_t clock = {
108 0 : .slot = fd_bank_slot_get( bank ),
109 0 : .epoch = 0,
110 0 : .epoch_start_timestamp = timestamp,
111 0 : .leader_schedule_epoch = 1,
112 0 : .unix_timestamp = timestamp,
113 0 : };
114 0 : fd_sysvar_clock_write( bank, funk, xid, capture_ctx, &clock );
115 0 : }
116 :
117 0 : #define CIDX_T ulong
118 : #define VAL_T long
119 : struct stake_ts_ele {
120 : CIDX_T parent_cidx;
121 : CIDX_T left_cidx;
122 : CIDX_T right_cidx;
123 : CIDX_T prio_cidx;
124 : VAL_T timestamp;
125 : uint128 stake;
126 : };
127 :
128 : typedef struct stake_ts_ele stake_ts_ele_t;
129 :
130 : #define POOL_NAME stake_ts_pool
131 0 : #define POOL_T stake_ts_ele_t
132 : #define POOL_IDX_T CIDX_T
133 0 : #define POOL_NEXT parent_cidx
134 : #include "../../../util/tmpl/fd_pool.c"
135 :
136 0 : FD_FN_CONST static inline int valcmp (VAL_T a, VAL_T b) {
137 0 : int val = (a < b) ? -1 : 1;
138 0 : return (a == b) ? 0 : val;
139 0 : }
140 :
141 : #define TREAP_NAME stake_ts_treap
142 : #define TREAP_T stake_ts_ele_t
143 : #define TREAP_QUERY_T VAL_T
144 0 : #define TREAP_CMP(q,e) valcmp(q, e->timestamp)
145 0 : #define TREAP_LT(e0,e1) (((VAL_T)((e0)->timestamp)) < ((VAL_T)((e1)->timestamp)))
146 0 : #define TREAP_IDX_T CIDX_T
147 0 : #define TREAP_PARENT parent_cidx
148 0 : #define TREAP_LEFT left_cidx
149 0 : #define TREAP_RIGHT right_cidx
150 0 : #define TREAP_PRIO prio_cidx
151 : #define TREAP_IMPL_STYLE 0
152 : #include "../../../util/tmpl/fd_treap.c"
153 :
154 : /* get_timestamp_estimate calculates a timestamp estimate. Does not
155 : modify the slot context. Walks all cached vote accounts (from the
156 : "bank") and calculates a unix timestamp estimate. Returns the
157 : timestamp estimate. spad is used for scratch allocations (allocates
158 : a treap of size FD_SYSVAR_CLOCK_STAKE_WEIGHTS_MAX). Crashes the
159 : process with FD_LOG_ERR on failure (e.g. too many vote accounts).
160 :
161 : https://github.com/anza-xyz/agave/blob/v2.3.7/runtime/src/bank.rs#L2563-L2601 */
162 : long
163 : get_timestamp_estimate( fd_bank_t * bank,
164 : fd_sol_sysvar_clock_t * clock,
165 0 : fd_spad_t * spad ) {
166 0 : FD_SPAD_FRAME_BEGIN( spad ) {
167 :
168 0 : fd_epoch_schedule_t const * epoch_schedule = fd_bank_epoch_schedule_query( bank );
169 0 : ulong slot_duration = (ulong)fd_bank_ns_per_slot_get( bank );
170 0 : ulong current_slot = fd_bank_slot_get( bank );
171 :
172 : /* Set up a temporary treap, pool, and rng (required for treap prio).
173 : This is to establish a mapping between each vote timestamp and the
174 : amount of stake associated with each timestamp. */
175 0 : stake_ts_treap_t _treap[1];
176 0 : stake_ts_treap_t * treap = stake_ts_treap_join( stake_ts_treap_new( _treap, FD_RUNTIME_MAX_VOTE_ACCOUNTS ) );
177 0 : uchar * pool_mem = fd_spad_alloc( spad, stake_ts_pool_align(), stake_ts_pool_footprint( FD_RUNTIME_MAX_VOTE_ACCOUNTS ) );
178 0 : stake_ts_ele_t * pool = stake_ts_pool_join( stake_ts_pool_new( pool_mem, FD_RUNTIME_MAX_VOTE_ACCOUNTS ) );
179 0 : uint txn_cnt = (uint)fd_bank_transaction_count_get( bank );
180 :
181 0 : fd_rng_t _rng[1];
182 0 : fd_rng_t * rng = fd_rng_join( fd_rng_new( _rng, txn_cnt, 0UL ) );
183 :
184 : /* https://github.com/anza-xyz/agave/blob/v2.3.7/runtime/src/stake_weighted_timestamp.rs#L41 */
185 0 : uint128 total_stake = 0UL;
186 :
187 : /* A timestamp estimate is calculated at every slot using the most
188 : recent vote states of voting validators. This estimated is based on
189 : a stake weighted median using the stake as of the end of epoch E-2
190 : if we are currently in epoch E. We do not count vote accounts that
191 : have not voted in an epoch's worth of slots (432k). */
192 0 : fd_vote_states_t const * vote_states = fd_bank_vote_states_locking_query( bank );
193 0 : fd_vote_states_t const * vote_states_prev_prev = fd_bank_vote_states_prev_prev_locking_query( bank );
194 :
195 0 : fd_vote_states_iter_t iter_[1];
196 0 : for( fd_vote_states_iter_t * iter = fd_vote_states_iter_init( iter_, vote_states );
197 0 : !fd_vote_states_iter_done( iter );
198 0 : fd_vote_states_iter_next( iter ) ) {
199 0 : fd_vote_state_ele_t const * vote_state = fd_vote_states_iter_ele( iter );
200 :
201 : /* https://github.com/anza-xyz/agave/blob/v3.0.0/runtime/src/bank.rs#L2445 */
202 0 : ulong slot_delta;
203 0 : int err = fd_ulong_checked_sub( current_slot, vote_state->last_vote_slot, &slot_delta );
204 0 : if( FD_UNLIKELY( err ) ) {
205 : /* Don't count vote accounts with a last vote slot that is greater
206 : than the current slot.*/
207 0 : continue;
208 0 : }
209 :
210 0 : fd_vote_state_ele_t const * vote_state_prev = fd_vote_states_query_const( vote_states_prev_prev, &vote_state->vote_account );
211 0 : if( FD_UNLIKELY( !vote_state_prev ) ) {
212 : /* Don't count vote accounts that didn't have stake at the end of
213 : epoch E-2. */
214 0 : continue;
215 0 : }
216 :
217 : /* Don't count vote accounts that haven't voted in the past 432k
218 : slots (length of an epoch).
219 : https://github.com/anza-xyz/agave/blob/v3.0.0/runtime/src/bank.rs#L2446-L2447 */
220 0 : if( FD_UNLIKELY( slot_delta>epoch_schedule->slots_per_epoch ) ) {
221 0 : continue;
222 0 : }
223 :
224 : /* Calculate the timestamp estimate by taking the last vote
225 : timestamp and adding the estimated time since the last vote
226 : (delta from last vote slot to current slot * slot duration).
227 : https://github.com/anza-xyz/agave/blob/v2.3.7/runtime/src/stake_weighted_timestamp.rs#L44-L45 */
228 0 : ulong offset = fd_ulong_sat_mul( slot_duration, slot_delta );
229 0 : long estimate = vote_state->last_vote_timestamp + (long)(offset / NS_IN_S);
230 :
231 : /* For each timestamp, accumulate the stake from E-2. If the entry
232 : for the timestamp doesn't exist yet, insert it. Otherwise,
233 : update the existing entry.
234 : https://github.com/anza-xyz/agave/blob/v2.3.7/runtime/src/stake_weighted_timestamp.rs#L46-L53 */
235 0 : ulong treap_idx = stake_ts_treap_idx_query( treap, estimate, pool );
236 0 : if( FD_LIKELY( treap_idx!=stake_ts_treap_idx_null() ) ) {
237 0 : pool[ treap_idx ].stake += vote_state_prev->stake;
238 0 : } else {
239 0 : if( FD_UNLIKELY( stake_ts_pool_free( pool )==0UL ) ){
240 0 : FD_LOG_ERR(( "stake_ts_pool is empty" ));
241 0 : }
242 0 : ulong idx = stake_ts_pool_idx_acquire( pool );
243 0 : pool[ idx ].prio_cidx = fd_rng_ulong( rng );
244 0 : pool[ idx ].timestamp = estimate;
245 0 : pool[ idx ].stake = vote_state_prev->stake;
246 0 : stake_ts_treap_idx_insert( treap, idx, pool );
247 0 : }
248 :
249 : /* https://github.com/anza-xyz/agave/blob/v2.3.7/runtime/src/stake_weighted_timestamp.rs#L54 */
250 0 : total_stake += vote_state_prev->stake;
251 0 : }
252 0 : fd_bank_vote_states_end_locking_query( bank );
253 0 : fd_bank_vote_states_prev_prev_end_locking_query( bank );
254 :
255 : /* https://github.com/anza-xyz/agave/blob/v2.3.7/runtime/src/stake_weighted_timestamp.rs#L56-L58 */
256 0 : if( FD_UNLIKELY( total_stake==0UL ) ) {
257 0 : return 0L;
258 0 : }
259 :
260 : /* Populate estimate with the stake-weighted median timestamp.
261 : https://github.com/anza-xyz/agave/blob/v2.3.7/runtime/src/stake_weighted_timestamp.rs#L59-L68 */
262 0 : uint128 stake_accumulator = 0;
263 0 : long estimate = 0L;
264 0 : for( stake_ts_treap_fwd_iter_t iter = stake_ts_treap_fwd_iter_init( treap, pool );
265 0 : !stake_ts_treap_fwd_iter_done( iter );
266 0 : iter = stake_ts_treap_fwd_iter_next( iter, pool ) ) {
267 0 : ulong idx = stake_ts_treap_fwd_iter_idx( iter );
268 0 : stake_accumulator = fd_uint128_sat_add( stake_accumulator, pool[ idx ].stake );
269 0 : if( stake_accumulator>(total_stake/2UL) ) {
270 0 : estimate = pool[ idx ].timestamp;
271 0 : break;
272 0 : }
273 0 : }
274 :
275 0 : int const fix_estimate_into_u64 = FD_FEATURE_ACTIVE_BANK( bank, warp_timestamp_again );
276 :
277 : /* Bound estimate by `max_allowable_drift` since the start of the epoch
278 : https://github.com/anza-xyz/agave/blob/v2.3.7/runtime/src/stake_weighted_timestamp.rs#L69-L99 */
279 0 : ulong epoch_start_slot = fd_epoch_slot0( epoch_schedule, clock->epoch );
280 0 : long epoch_start_timestamp = clock->epoch_start_timestamp;
281 :
282 : /* https://github.com/anza-xyz/agave/blob/v2.3.7/runtime/src/stake_weighted_timestamp.rs#L71-L72 */
283 0 : ulong poh_estimate_offset = fd_ulong_sat_mul( slot_duration, fd_ulong_sat_sub( current_slot, epoch_start_slot ) );
284 :
285 : /* https://github.com/anza-xyz/agave/blob/v2.3.7/runtime/src/stake_weighted_timestamp.rs#L73-L77 */
286 0 : ulong estimate_offset;
287 0 : if( fix_estimate_into_u64 ) {
288 0 : estimate_offset = fd_ulong_sat_mul( NS_IN_S, fd_ulong_sat_sub( (ulong)estimate, (ulong)epoch_start_timestamp ) );
289 0 : } else {
290 0 : estimate_offset = fd_ulong_sat_mul( NS_IN_S, (ulong)fd_long_sat_sub( estimate, epoch_start_timestamp ) );
291 0 : }
292 :
293 : /* https://github.com/anza-xyz/agave/blob/v2.3.7/runtime/src/stake_weighted_timestamp.rs#L78-L81 */
294 0 : ulong max_allowable_drift_fast = fd_ulong_sat_mul( poh_estimate_offset, MAX_ALLOWABLE_DRIFT_FAST_PERCENT ) / 100UL;
295 0 : ulong max_allowable_drift_slow = fd_ulong_sat_mul( poh_estimate_offset, MAX_ALLOWABLE_DRIFT_SLOW_PERCENT ) / 100UL;
296 0 : FD_LOG_DEBUG(( "poh offset %lu estimate %lu fast %lu slow %lu", poh_estimate_offset, estimate_offset, max_allowable_drift_fast, max_allowable_drift_slow ));
297 :
298 : /* https://github.com/anza-xyz/agave/blob/v2.3.7/runtime/src/stake_weighted_timestamp.rs#L82-L98 */
299 0 : if( estimate_offset>poh_estimate_offset && fd_ulong_sat_sub( estimate_offset, poh_estimate_offset )>max_allowable_drift_slow ) {
300 0 : estimate = fd_long_sat_add(
301 0 : epoch_start_timestamp,
302 0 : fd_long_sat_add( (long)poh_estimate_offset / NS_IN_S, (long)max_allowable_drift_slow / NS_IN_S ) );
303 0 : } else if( estimate_offset<poh_estimate_offset && fd_ulong_sat_sub( poh_estimate_offset, estimate_offset )>max_allowable_drift_fast ) {
304 0 : estimate = fd_long_sat_sub(
305 0 : fd_long_sat_add( epoch_start_timestamp, (long)poh_estimate_offset / NS_IN_S ),
306 0 : (long)max_allowable_drift_fast / NS_IN_S );
307 0 : }
308 :
309 0 : return estimate;
310 :
311 0 : } FD_SPAD_FRAME_END;
312 0 : }
313 :
314 : /* TODO: This function should be called from genesis bootup as well with
315 : parent_epoch = NULL
316 : https://github.com/anza-xyz/agave/blob/v2.3.7/runtime/src/bank.rs#L2158-L2215 */
317 : void
318 : fd_sysvar_clock_update( fd_bank_t * bank,
319 : fd_funk_t * funk,
320 : fd_funk_txn_xid_t const * xid,
321 : fd_capture_ctx_t * capture_ctx,
322 : fd_spad_t * spad,
323 0 : ulong const * parent_epoch ) {
324 0 : fd_sol_sysvar_clock_t clock_[1];
325 0 : fd_sol_sysvar_clock_t * clock = fd_sysvar_clock_read( funk, xid, clock_ );
326 0 : if( FD_UNLIKELY( !clock ) ) FD_LOG_ERR(( "fd_sysvar_clock_read failed" ));
327 :
328 0 : fd_epoch_schedule_t const * epoch_schedule = fd_bank_epoch_schedule_query( bank );
329 0 : ulong current_slot = fd_bank_slot_get( bank );
330 0 : ulong current_epoch = fd_slot_to_epoch( epoch_schedule, current_slot, NULL );
331 :
332 : /* https://github.com/anza-xyz/agave/blob/v2.3.7/runtime/src/bank.rs#L2159 */
333 0 : long unix_timestamp = clock->unix_timestamp;
334 :
335 : /* https://github.com/anza-xyz/agave/blob/v2.3.7/runtime/src/bank.rs#L2175 */
336 0 : long ancestor_timestamp = clock->unix_timestamp;
337 :
338 : /* TODO: Are we handling slot 0 correctly?
339 : https://github.com/anza-xyz/agave/blob/v2.3.7/runtime/src/bank.rs#L2176-L2183 */
340 0 : long timestamp_estimate = get_timestamp_estimate( bank, clock, spad );
341 :
342 : /* If the timestamp was successfully calculated, use it. It not keep the old one. */
343 0 : if( FD_LIKELY( timestamp_estimate!=0L ) ) {
344 0 : unix_timestamp = timestamp_estimate;
345 :
346 : /* https://github.com/anza-xyz/agave/blob/v2.3.7/runtime/src/bank.rs#L2180-L2182 */
347 0 : if( timestamp_estimate<ancestor_timestamp ) {
348 0 : unix_timestamp = ancestor_timestamp;
349 0 : }
350 0 : }
351 :
352 : /* https://github.com/anza-xyz/agave/blob/v2.3.7/runtime/src/bank.rs#L2191-L2197 */
353 0 : long epoch_start_timestamp = (parent_epoch!=NULL && *parent_epoch!=current_epoch) ?
354 0 : unix_timestamp :
355 0 : clock->epoch_start_timestamp;
356 :
357 : /* https://github.com/anza-xyz/agave/blob/v2.3.7/runtime/src/bank.rs#L2198-L2201 */
358 0 : if( FD_UNLIKELY( current_slot==0UL ) ) {
359 0 : long timestamp_from_genesis = unix_timestamp_from_genesis( bank );
360 0 : unix_timestamp = timestamp_from_genesis;
361 0 : epoch_start_timestamp = timestamp_from_genesis;
362 0 : }
363 :
364 : /* https://github.com/anza-xyz/agave/blob/v2.3.7/runtime/src/bank.rs#L2202-L2208 */
365 0 : *clock = (fd_sol_sysvar_clock_t){
366 0 : .slot = current_slot,
367 0 : .epoch_start_timestamp = epoch_start_timestamp,
368 0 : .epoch = current_epoch,
369 0 : .leader_schedule_epoch = fd_slot_to_leader_schedule_epoch( epoch_schedule, current_slot ),
370 0 : .unix_timestamp = unix_timestamp,
371 0 : };
372 :
373 : /* https://github.com/anza-xyz/agave/blob/v2.3.7/runtime/src/bank.rs#L2209-L2214 */
374 0 : fd_sysvar_clock_write( bank, funk, xid, capture_ctx, clock );
375 0 : }
|
