1use {
2 crate::invoke_context::InvokeContext,
3 log::*,
4 rand::Rng,
5 solana_sdk::{
6 instruction::InstructionError, pubkey::Pubkey, saturating_add_assign, slot_history::Slot,
7 stake_history::Epoch,
8 },
9 std::{
10 collections::HashMap,
11 fmt::Debug,
12 ops::Div,
13 sync::{
14 atomic::{AtomicU64, Ordering::Relaxed},
15 Arc,
16 },
17 },
18};
19
20pub trait Executor: Debug + Send + Sync {
22 fn execute(
24 &self,
25 first_instruction_account: usize,
26 invoke_context: &mut InvokeContext,
27 ) -> Result<(), InstructionError>;
28}
29
30pub type Executors = HashMap<Pubkey, TransactionExecutor>;
31
32#[repr(u8)]
33#[derive(PartialEq, Debug)]
34enum TransactionExecutorStatus {
35 Cached,
37 Missing,
39 Updated,
41}
42
43#[derive(Debug)]
46pub struct TransactionExecutor {
47 pub(crate) executor: Arc<dyn Executor>,
48 status: TransactionExecutorStatus,
49}
50
51impl TransactionExecutor {
52 pub fn new_cached(executor: Arc<dyn Executor>) -> Self {
55 Self {
56 executor,
57 status: TransactionExecutorStatus::Cached,
58 }
59 }
60
61 pub fn new_miss(executor: Arc<dyn Executor>) -> Self {
64 Self {
65 executor,
66 status: TransactionExecutorStatus::Missing,
67 }
68 }
69
70 pub fn new_updated(executor: Arc<dyn Executor>) -> Self {
73 Self {
74 executor,
75 status: TransactionExecutorStatus::Updated,
76 }
77 }
78
79 pub fn is_missing(&self) -> bool {
80 self.status == TransactionExecutorStatus::Missing
81 }
82
83 pub fn is_updated(&self) -> bool {
84 self.status == TransactionExecutorStatus::Updated
85 }
86
87 pub fn get(&self) -> Arc<dyn Executor> {
88 self.executor.clone()
89 }
90}
91
92pub const MAX_CACHED_EXECUTORS: usize = 256;
94
95#[derive(Debug)]
97pub struct CachedExecutorsEntry {
98 prev_epoch_count: u64,
99 epoch_count: AtomicU64,
100 executor: Arc<dyn Executor>,
101 pub hit_count: AtomicU64,
102}
103
104impl Clone for CachedExecutorsEntry {
105 fn clone(&self) -> Self {
106 Self {
107 prev_epoch_count: self.prev_epoch_count,
108 epoch_count: AtomicU64::new(self.epoch_count.load(Relaxed)),
109 executor: self.executor.clone(),
110 hit_count: AtomicU64::new(self.hit_count.load(Relaxed)),
111 }
112 }
113}
114
115#[derive(Debug)]
117pub struct CachedExecutors {
118 capacity: usize,
119 current_epoch: Epoch,
120 pub executors: HashMap<Pubkey, CachedExecutorsEntry>,
121 pub stats: Stats,
122}
123
124impl Default for CachedExecutors {
125 fn default() -> Self {
126 Self {
127 capacity: MAX_CACHED_EXECUTORS,
128 current_epoch: Epoch::default(),
129 executors: HashMap::default(),
130 stats: Stats::default(),
131 }
132 }
133}
134
135#[cfg(RUSTC_WITH_SPECIALIZATION)]
136impl safecoin_frozen_abi::abi_example::AbiExample for CachedExecutors {
137 fn example() -> Self {
138 Self::default()
142 }
143}
144
145impl CachedExecutors {
146 pub fn new(max_capacity: usize, current_epoch: Epoch) -> Self {
147 Self {
148 capacity: max_capacity,
149 current_epoch,
150 executors: HashMap::new(),
151 stats: Stats::default(),
152 }
153 }
154
155 pub fn new_from_parent_bank_executors(
156 parent_bank_executors: &CachedExecutors,
157 current_epoch: Epoch,
158 ) -> Self {
159 let executors = if parent_bank_executors.current_epoch == current_epoch {
160 parent_bank_executors.executors.clone()
161 } else {
162 parent_bank_executors
163 .executors
164 .iter()
165 .map(|(&key, entry)| {
166 let entry = CachedExecutorsEntry {
167 prev_epoch_count: entry.epoch_count.load(Relaxed),
168 epoch_count: AtomicU64::default(),
169 executor: entry.executor.clone(),
170 hit_count: AtomicU64::new(entry.hit_count.load(Relaxed)),
171 };
172 (key, entry)
173 })
174 .collect()
175 };
176
177 Self {
178 capacity: parent_bank_executors.capacity,
179 current_epoch,
180 executors,
181 stats: Stats::default(),
182 }
183 }
184
185 pub fn get(&self, pubkey: &Pubkey) -> Option<Arc<dyn Executor>> {
186 if let Some(entry) = self.executors.get(pubkey) {
187 self.stats.hits.fetch_add(1, Relaxed);
188 entry.epoch_count.fetch_add(1, Relaxed);
189 entry.hit_count.fetch_add(1, Relaxed);
190 Some(entry.executor.clone())
191 } else {
192 self.stats.misses.fetch_add(1, Relaxed);
193 None
194 }
195 }
196
197 pub fn put(&mut self, executors: &[(&Pubkey, Arc<dyn Executor>)]) {
198 let mut new_executors: Vec<_> = executors
199 .iter()
200 .filter_map(|(key, executor)| {
201 if let Some(mut entry) = self.remove(key) {
202 self.stats.replacements.fetch_add(1, Relaxed);
203 entry.executor = executor.clone();
204 let _ = self.executors.insert(**key, entry);
205 None
206 } else {
207 self.stats.insertions.fetch_add(1, Relaxed);
208 Some((*key, executor))
209 }
210 })
211 .collect();
212
213 if !new_executors.is_empty() {
214 let mut counts = self
215 .executors
216 .iter()
217 .map(|(key, entry)| {
218 let count = entry
219 .prev_epoch_count
220 .saturating_add(entry.epoch_count.load(Relaxed));
221 (key, count)
222 })
223 .collect::<Vec<_>>();
224 counts.sort_unstable_by_key(|(_, count)| *count);
225
226 let primer_counts = Self::get_primer_counts(counts.as_slice(), new_executors.len());
227
228 if self.executors.len() >= self.capacity {
229 let mut least_keys = counts
230 .iter()
231 .take(new_executors.len())
232 .map(|least| *least.0)
233 .collect::<Vec<_>>();
234 for least_key in least_keys.drain(..) {
235 let _ = self.remove(&least_key);
236 self.stats
237 .evictions
238 .entry(least_key)
239 .and_modify(|c| saturating_add_assign!(*c, 1))
240 .or_insert(1);
241 }
242 }
243
244 for ((key, executor), primer_count) in new_executors.drain(..).zip(primer_counts) {
245 let entry = CachedExecutorsEntry {
246 prev_epoch_count: 0,
247 epoch_count: AtomicU64::new(primer_count),
248 executor: executor.clone(),
249 hit_count: AtomicU64::new(1),
250 };
251 let _ = self.executors.insert(*key, entry);
252 }
253 }
254 }
255
256 pub fn remove(&mut self, pubkey: &Pubkey) -> Option<CachedExecutorsEntry> {
257 let maybe_entry = self.executors.remove(pubkey);
258 if let Some(entry) = maybe_entry.as_ref() {
259 if entry.hit_count.load(Relaxed) == 1 {
260 self.stats.one_hit_wonders.fetch_add(1, Relaxed);
261 }
262 }
263 maybe_entry
264 }
265
266 pub fn clear(&mut self) {
267 *self = CachedExecutors::default();
268 }
269
270 pub fn get_primer_count_upper_bound_inclusive(counts: &[(&Pubkey, u64)]) -> u64 {
271 const PRIMER_COUNT_TARGET_PERCENTILE: u64 = 85;
272 #[allow(clippy::assertions_on_constants)]
273 {
274 assert!(PRIMER_COUNT_TARGET_PERCENTILE <= 100);
275 }
276 let target_index = u64::try_from(counts.len().saturating_sub(1))
281 .ok()
282 .and_then(|counts| {
283 let index = counts
284 .saturating_mul(PRIMER_COUNT_TARGET_PERCENTILE)
285 .div(100); usize::try_from(index).ok()
287 })
288 .unwrap_or(0);
289
290 counts
291 .get(target_index)
292 .map(|(_, count)| *count)
293 .unwrap_or(0)
294 }
295
296 pub fn get_primer_counts(counts: &[(&Pubkey, u64)], num_counts: usize) -> Vec<u64> {
297 let max_primer_count = Self::get_primer_count_upper_bound_inclusive(counts);
298 let mut rng = rand::thread_rng();
299
300 (0..num_counts)
301 .map(|_| rng.gen_range(0, max_primer_count.saturating_add(1)))
302 .collect::<Vec<_>>()
303 }
304}
305
306#[derive(Debug, Default)]
308pub struct Stats {
309 pub hits: AtomicU64,
310 pub misses: AtomicU64,
311 pub evictions: HashMap<Pubkey, u64>,
312 pub insertions: AtomicU64,
313 pub replacements: AtomicU64,
314 pub one_hit_wonders: AtomicU64,
315}
316
317impl Stats {
318 pub fn submit(&self, slot: Slot) {
320 let hits = self.hits.load(Relaxed);
321 let misses = self.misses.load(Relaxed);
322 let insertions = self.insertions.load(Relaxed);
323 let replacements = self.replacements.load(Relaxed);
324 let one_hit_wonders = self.one_hit_wonders.load(Relaxed);
325 let evictions: u64 = self.evictions.values().sum();
326 datapoint_info!(
327 "bank-executor-cache-stats",
328 ("slot", slot, i64),
329 ("hits", hits, i64),
330 ("misses", misses, i64),
331 ("evictions", evictions, i64),
332 ("insertions", insertions, i64),
333 ("replacements", replacements, i64),
334 ("one_hit_wonders", one_hit_wonders, i64),
335 );
336 debug!(
337 "Executor Cache Stats -- Hits: {}, Misses: {}, Evictions: {}, Insertions: {}, Replacements: {}, One-Hit-Wonders: {}",
338 hits, misses, evictions, insertions, replacements, one_hit_wonders,
339 );
340 if log_enabled!(log::Level::Trace) && !self.evictions.is_empty() {
341 let mut evictions = self.evictions.iter().collect::<Vec<_>>();
342 evictions.sort_by_key(|e| e.1);
343 let evictions = evictions
344 .into_iter()
345 .rev()
346 .map(|(program_id, evictions)| {
347 format!(" {:<44} {}", program_id.to_string(), evictions)
348 })
349 .collect::<Vec<_>>();
350 let evictions = evictions.join("\n");
351 trace!(
352 "Eviction Details:\n {:<44} {}\n{}",
353 "Program",
354 "Count",
355 evictions
356 );
357 }
358 }
359}
360
361#[allow(clippy::indexing_slicing)]
362#[cfg(test)]
363mod tests {
364 use {
365 super::*, crate::invoke_context::InvokeContext, solana_sdk::instruction::InstructionError,
366 };
367
368 #[derive(Debug)]
369 struct TestExecutor {}
370 impl Executor for TestExecutor {
371 fn execute(
372 &self,
373 _first_instruction_account: usize,
374 _invoke_context: &mut InvokeContext,
375 ) -> std::result::Result<(), InstructionError> {
376 Ok(())
377 }
378 }
379
380 #[test]
381 fn test_cached_executors() {
382 let key1 = solana_sdk::pubkey::new_rand();
383 let key2 = solana_sdk::pubkey::new_rand();
384 let key3 = solana_sdk::pubkey::new_rand();
385 let key4 = solana_sdk::pubkey::new_rand();
386 let executor: Arc<dyn Executor> = Arc::new(TestExecutor {});
387 let mut cache = CachedExecutors::new(3, 0);
388
389 cache.put(&[(&key1, executor.clone())]);
390 cache.put(&[(&key2, executor.clone())]);
391 cache.put(&[(&key3, executor.clone())]);
392 assert!(cache.get(&key1).is_some());
393 assert!(cache.get(&key2).is_some());
394 assert!(cache.get(&key3).is_some());
395
396 assert!(cache.get(&key1).is_some());
397 assert!(cache.get(&key1).is_some());
398 assert!(cache.get(&key2).is_some());
399 cache.put(&[(&key4, executor.clone())]);
400 assert!(cache.get(&key4).is_some());
401 let num_retained = [&key1, &key2, &key3]
402 .iter()
403 .filter_map(|key| cache.get(key))
404 .count();
405 assert_eq!(num_retained, 2);
406
407 assert!(cache.get(&key4).is_some());
408 assert!(cache.get(&key4).is_some());
409 assert!(cache.get(&key4).is_some());
410 cache.put(&[(&key3, executor.clone())]);
411 assert!(cache.get(&key3).is_some());
412 let num_retained = [&key1, &key2, &key4]
413 .iter()
414 .filter_map(|key| cache.get(key))
415 .count();
416 assert_eq!(num_retained, 2);
417 }
418
419 #[test]
420 fn test_cached_executor_eviction() {
421 let key1 = solana_sdk::pubkey::new_rand();
422 let key2 = solana_sdk::pubkey::new_rand();
423 let key3 = solana_sdk::pubkey::new_rand();
424 let key4 = solana_sdk::pubkey::new_rand();
425 let executor: Arc<dyn Executor> = Arc::new(TestExecutor {});
426 let mut cache = CachedExecutors::new(3, 0);
427 assert!(cache.current_epoch == 0);
428
429 cache.put(&[(&key1, executor.clone())]);
430 cache.put(&[(&key2, executor.clone())]);
431 cache.put(&[(&key3, executor.clone())]);
432 assert!(cache.get(&key1).is_some());
433 assert!(cache.get(&key1).is_some());
434 assert!(cache.get(&key1).is_some());
435
436 let mut cache = CachedExecutors::new_from_parent_bank_executors(&cache, 1);
437 assert!(cache.current_epoch == 1);
438
439 assert!(cache.get(&key2).is_some());
440 assert!(cache.get(&key2).is_some());
441 assert!(cache.get(&key3).is_some());
442 cache.put(&[(&key4, executor.clone())]);
443
444 assert!(cache.get(&key4).is_some());
445 let num_retained = [&key1, &key2, &key3]
446 .iter()
447 .filter_map(|key| cache.get(key))
448 .count();
449 assert_eq!(num_retained, 2);
450
451 cache.put(&[(&key1, executor.clone())]);
452 cache.put(&[(&key3, executor.clone())]);
453 assert!(cache.get(&key1).is_some());
454 assert!(cache.get(&key3).is_some());
455 let num_retained = [&key2, &key4]
456 .iter()
457 .filter_map(|key| cache.get(key))
458 .count();
459 assert_eq!(num_retained, 1);
460
461 cache = CachedExecutors::new_from_parent_bank_executors(&cache, 2);
462 assert!(cache.current_epoch == 2);
463
464 cache.put(&[(&key3, executor.clone())]);
465 assert!(cache.get(&key3).is_some());
466 }
467
468 #[test]
469 fn test_cached_executors_evicts_smallest() {
470 let key1 = solana_sdk::pubkey::new_rand();
471 let key2 = solana_sdk::pubkey::new_rand();
472 let key3 = solana_sdk::pubkey::new_rand();
473 let executor: Arc<dyn Executor> = Arc::new(TestExecutor {});
474 let mut cache = CachedExecutors::new(2, 0);
475
476 cache.put(&[(&key1, executor.clone())]);
477 for _ in 0..5 {
478 let _ = cache.get(&key1);
479 }
480 cache.put(&[(&key2, executor.clone())]);
481 let _ = cache.get(&key1);
483
484 let mut entries = cache
485 .executors
486 .iter()
487 .map(|(k, v)| (*k, v.epoch_count.load(Relaxed)))
488 .collect::<Vec<_>>();
489 entries.sort_by_key(|(_, v)| *v);
490 assert!(entries[0].1 < entries[1].1);
491
492 cache.put(&[(&key3, executor.clone())]);
493 assert!(cache.get(&entries[0].0).is_none());
494 assert!(cache.get(&entries[1].0).is_some());
495 }
496
497 #[test]
498 fn test_cached_executors_one_hit_wonder_counter() {
499 let mut cache = CachedExecutors::new(1, 0);
500
501 let one_hit_wonder = Pubkey::new_unique();
502 let popular = Pubkey::new_unique();
503 let executor: Arc<dyn Executor> = Arc::new(TestExecutor {});
504
505 assert_eq!(cache.stats.one_hit_wonders.load(Relaxed), 0);
507
508 cache.put(&[(&one_hit_wonder, executor.clone())]);
510 assert_eq!(cache.executors[&one_hit_wonder].hit_count.load(Relaxed), 1);
511 cache.put(&[(&popular, executor.clone())]);
513 assert_eq!(cache.executors[&popular].hit_count.load(Relaxed), 1);
514
515 assert_eq!(cache.stats.one_hit_wonders.load(Relaxed), 1);
517
518 cache.get(&popular).unwrap();
520 assert_eq!(cache.executors[&popular].hit_count.load(Relaxed), 2);
521
522 cache.put(&[(&one_hit_wonder, executor.clone())]);
524 assert_eq!(cache.executors[&one_hit_wonder].hit_count.load(Relaxed), 1);
525
526 assert_eq!(cache.stats.one_hit_wonders.load(Relaxed), 1);
528 }
529
530 #[test]
531 fn test_executor_cache_get_primer_count_upper_bound_inclusive() {
532 let pubkey = Pubkey::default();
533 let v = [];
534 assert_eq!(
535 CachedExecutors::get_primer_count_upper_bound_inclusive(&v),
536 0
537 );
538 let v = [(&pubkey, 1)];
539 assert_eq!(
540 CachedExecutors::get_primer_count_upper_bound_inclusive(&v),
541 1
542 );
543 let v = (0u64..10).map(|i| (&pubkey, i)).collect::<Vec<_>>();
544 assert_eq!(
545 CachedExecutors::get_primer_count_upper_bound_inclusive(v.as_slice()),
546 7
547 );
548 }
549
550 #[test]
551 fn test_cached_executors_stats() {
552 #[derive(Debug, Default, PartialEq)]
553 struct ComparableStats {
554 hits: u64,
555 misses: u64,
556 evictions: HashMap<Pubkey, u64>,
557 insertions: u64,
558 replacements: u64,
559 one_hit_wonders: u64,
560 }
561 impl From<&Stats> for ComparableStats {
562 fn from(stats: &Stats) -> Self {
563 let Stats {
564 hits,
565 misses,
566 evictions,
567 insertions,
568 replacements,
569 one_hit_wonders,
570 } = stats;
571 ComparableStats {
572 hits: hits.load(Relaxed),
573 misses: misses.load(Relaxed),
574 evictions: evictions.clone(),
575 insertions: insertions.load(Relaxed),
576 replacements: replacements.load(Relaxed),
577 one_hit_wonders: one_hit_wonders.load(Relaxed),
578 }
579 }
580 }
581
582 const CURRENT_EPOCH: Epoch = 0;
583 let mut cache = CachedExecutors::new(2, CURRENT_EPOCH);
584 let mut expected_stats = ComparableStats::default();
585
586 let program_id1 = Pubkey::new_unique();
587 let program_id2 = Pubkey::new_unique();
588 let executor: Arc<dyn Executor> = Arc::new(TestExecutor {});
589
590 assert_eq!(ComparableStats::from(&cache.stats), expected_stats,);
592
593 cache.put(&[(&program_id1, executor.clone())]);
595 cache.put(&[(&program_id2, executor.clone())]);
596 expected_stats.insertions += 2;
597 assert_eq!(ComparableStats::from(&cache.stats), expected_stats);
598
599 cache.put(&[(&program_id1, executor.clone())]);
601 expected_stats.replacements += 1;
602 expected_stats.one_hit_wonders += 1;
603 assert_eq!(ComparableStats::from(&cache.stats), expected_stats);
604
605 cache.get(&program_id1);
607 cache.get(&program_id1);
608 cache.get(&program_id2);
609 expected_stats.hits += 3;
610 assert_eq!(ComparableStats::from(&cache.stats), expected_stats);
611
612 cache.get(&Pubkey::new_unique());
614 expected_stats.misses += 1;
615 assert_eq!(ComparableStats::from(&cache.stats), expected_stats);
616
617 cache.put(&[(&Pubkey::new_unique(), executor.clone())]);
619 expected_stats.insertions += 1;
620 expected_stats.evictions.insert(program_id2, 1);
621 assert_eq!(ComparableStats::from(&cache.stats), expected_stats);
622
623 assert_eq!(
625 ComparableStats::from(
626 &CachedExecutors::new_from_parent_bank_executors(&cache, CURRENT_EPOCH).stats
627 ),
628 ComparableStats::default()
629 );
630 assert_eq!(
631 ComparableStats::from(
632 &CachedExecutors::new_from_parent_bank_executors(&cache, CURRENT_EPOCH + 1).stats
633 ),
634 ComparableStats::default()
635 );
636 }
637}