solana_program_runtime/
executor_cache.rs

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
20/// Program executor
21pub trait Executor: Debug + Send + Sync {
22    /// Execute the program
23    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    /// Executor was already in the cache, no update needed
36    Cached,
37    /// Executor was missing from the cache, but not updated
38    Missing,
39    /// Executor is for an updated program
40    Updated,
41}
42
43/// Tracks whether a given executor is "dirty" and needs to updated in the
44/// executors cache
45#[derive(Debug)]
46pub struct TransactionExecutor {
47    pub(crate) executor: Arc<dyn Executor>,
48    status: TransactionExecutorStatus,
49}
50
51impl TransactionExecutor {
52    /// Wraps an executor and tracks that it doesn't need to be updated in the
53    /// executors cache.
54    pub fn new_cached(executor: Arc<dyn Executor>) -> Self {
55        Self {
56            executor,
57            status: TransactionExecutorStatus::Cached,
58        }
59    }
60
61    /// Wraps an executor and tracks that it needs to be updated in the
62    /// executors cache.
63    pub fn new_miss(executor: Arc<dyn Executor>) -> Self {
64        Self {
65            executor,
66            status: TransactionExecutorStatus::Missing,
67        }
68    }
69
70    /// Wraps an executor and tracks that it needs to be updated in the
71    /// executors cache only if the transaction succeeded.
72    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
92/// Capacity of `CachedExecutors`
93pub const MAX_CACHED_EXECUTORS: usize = 256;
94
95/// An `Executor` and its statistics tracked in `CachedExecutors`
96#[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/// LFU Cache of executors with single-epoch memory of usage counts
116#[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        // Delegate AbiExample impl to Default before going deep and stuck with
139        // not easily impl-able Arc<dyn Executor> due to rust's coherence issue
140        // This is safe because CachedExecutors isn't serializable by definition.
141        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        // Executor use-frequencies are assumed to fit a Pareto distribution.  Choose an
277        // upper-bound for our primer count as the actual count at the target rank to avoid
278        // an upward bias
279
280        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); // switch to u64::saturating_div once stable
286                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/// Statistics of the entrie `CachedExecutors`
307#[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    /// Logs the measurement values
319    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        // make key1's use-count for sure greater than key2's
482        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        // make sure we're starting from where we think we are
506        assert_eq!(cache.stats.one_hit_wonders.load(Relaxed), 0);
507
508        // add our one-hit-wonder
509        cache.put(&[(&one_hit_wonder, executor.clone())]);
510        assert_eq!(cache.executors[&one_hit_wonder].hit_count.load(Relaxed), 1);
511        // displace the one-hit-wonder with "popular program"
512        cache.put(&[(&popular, executor.clone())]);
513        assert_eq!(cache.executors[&popular].hit_count.load(Relaxed), 1);
514
515        // one-hit-wonder counter incremented
516        assert_eq!(cache.stats.one_hit_wonders.load(Relaxed), 1);
517
518        // make "popular program" popular
519        cache.get(&popular).unwrap();
520        assert_eq!(cache.executors[&popular].hit_count.load(Relaxed), 2);
521
522        // evict "popular program"
523        cache.put(&[(&one_hit_wonder, executor.clone())]);
524        assert_eq!(cache.executors[&one_hit_wonder].hit_count.load(Relaxed), 1);
525
526        // one-hit-wonder counter not incremented
527        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        // make sure we're starting from where we think we are
591        assert_eq!(ComparableStats::from(&cache.stats), expected_stats,);
592
593        // insert some executors
594        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        // replace a one-hit-wonder executor
600        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        // hit some executors
606        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        // miss an executor
613        cache.get(&Pubkey::new_unique());
614        expected_stats.misses += 1;
615        assert_eq!(ComparableStats::from(&cache.stats), expected_stats);
616
617        // evict an executor
618        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        // make sure stats are cleared in new_from_parent
624        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}
solana_program_runtime/executor_cache.rs

solana_program_runtime/
executor_cache.rs
