solana_program_runtime/
executor_cache.rs

1use {
2    crate::loaded_programs::LoadedProgram,
3    log::*,
4    rand::Rng,
5    solana_sdk::{pubkey::Pubkey, saturating_add_assign, slot_history::Slot, stake_history::Epoch},
6    std::{
7        collections::HashMap,
8        fmt::Debug,
9        ops::Div,
10        sync::{
11            atomic::{AtomicU64, Ordering::Relaxed},
12            Arc,
13        },
14    },
15};
16
17/// A subset of the BankExecutorCache containing only the executors relevant to one transaction
18///
19/// The BankExecutorCache can not be updated directly as transaction batches are
20/// processed in parallel, which would cause a race condition.
21#[derive(Default, Debug)]
22pub struct TransactionExecutorCache {
23    /// Executors or tombstones which are visible during the transaction
24    pub visible: HashMap<Pubkey, Arc<LoadedProgram>>,
25    /// Executors of programs which were re-/deploymed during the transaction
26    pub deployments: HashMap<Pubkey, Arc<LoadedProgram>>,
27    /// Executors which were missing in the cache and not re-/deploymed during the transaction
28    pub add_to_cache: HashMap<Pubkey, Arc<LoadedProgram>>,
29}
30
31impl TransactionExecutorCache {
32    pub fn new(executable_keys: impl Iterator<Item = (Pubkey, Arc<LoadedProgram>)>) -> Self {
33        Self {
34            visible: executable_keys.collect(),
35            deployments: HashMap::new(),
36            add_to_cache: HashMap::new(),
37        }
38    }
39
40    pub fn get(&self, key: &Pubkey) -> Option<Arc<LoadedProgram>> {
41        self.visible.get(key).cloned()
42    }
43
44    pub fn set_tombstone(&mut self, key: Pubkey) {
45        self.visible
46            .insert(key, Arc::new(LoadedProgram::new_tombstone()));
47    }
48
49    pub fn set(
50        &mut self,
51        key: Pubkey,
52        executor: Arc<LoadedProgram>,
53        upgrade: bool,
54        delay_visibility_of_program_deployment: bool,
55    ) {
56        if upgrade {
57            if delay_visibility_of_program_deployment {
58                // Place a tombstone in the cache so that
59                // we don't load the new version from the database as it should remain invisible
60                self.set_tombstone(key);
61            } else {
62                self.visible.insert(key, executor.clone());
63            }
64            self.deployments.insert(key, executor);
65        } else {
66            self.visible.insert(key, executor.clone());
67            self.add_to_cache.insert(key, executor);
68        }
69    }
70
71    pub fn get_executors_added_to_the_cache(&mut self) -> HashMap<Pubkey, Arc<LoadedProgram>> {
72        let mut executors = HashMap::new();
73        std::mem::swap(&mut executors, &mut self.add_to_cache);
74        executors
75    }
76
77    pub fn get_executors_which_were_deployed(&mut self) -> HashMap<Pubkey, Arc<LoadedProgram>> {
78        let mut executors = HashMap::new();
79        std::mem::swap(&mut executors, &mut self.deployments);
80        executors
81    }
82}
83
84/// Capacity of `BankExecutorCache`
85pub const MAX_CACHED_EXECUTORS: usize = 256;
86
87/// An entry of the BankExecutorCache
88#[derive(Debug)]
89pub struct BankExecutorCacheEntry {
90    prev_epoch_count: u64,
91    epoch_count: AtomicU64,
92    executor: Arc<LoadedProgram>,
93    pub hit_count: AtomicU64,
94}
95
96impl Clone for BankExecutorCacheEntry {
97    fn clone(&self) -> Self {
98        Self {
99            prev_epoch_count: self.prev_epoch_count,
100            epoch_count: AtomicU64::new(self.epoch_count.load(Relaxed)),
101            executor: self.executor.clone(),
102            hit_count: AtomicU64::new(self.hit_count.load(Relaxed)),
103        }
104    }
105}
106
107/// LFU Cache of executors which exists once per bank
108#[derive(Debug)]
109pub struct BankExecutorCache {
110    capacity: usize,
111    current_epoch: Epoch,
112    pub executors: HashMap<Pubkey, BankExecutorCacheEntry>,
113    pub stats: Stats,
114}
115
116impl Default for BankExecutorCache {
117    fn default() -> Self {
118        Self {
119            capacity: MAX_CACHED_EXECUTORS,
120            current_epoch: Epoch::default(),
121            executors: HashMap::default(),
122            stats: Stats::default(),
123        }
124    }
125}
126
127#[cfg(RUSTC_WITH_SPECIALIZATION)]
128impl solana_frozen_abi::abi_example::AbiExample for BankExecutorCache {
129    fn example() -> Self {
130        // Delegate AbiExample impl to Default before going deep and stuck with
131        // not easily impl-able Arc<dyn Executor> due to rust's coherence issue
132        // This is safe because BankExecutorCache isn't serializable by definition.
133        Self::default()
134    }
135}
136
137impl BankExecutorCache {
138    pub fn new(max_capacity: usize, current_epoch: Epoch) -> Self {
139        Self {
140            capacity: max_capacity,
141            current_epoch,
142            executors: HashMap::new(),
143            stats: Stats::default(),
144        }
145    }
146
147    pub fn new_from_parent_bank_executors(
148        parent_bank_executors: &BankExecutorCache,
149        current_epoch: Epoch,
150    ) -> Self {
151        let executors = if parent_bank_executors.current_epoch == current_epoch {
152            parent_bank_executors.executors.clone()
153        } else {
154            parent_bank_executors
155                .executors
156                .iter()
157                .map(|(&key, entry)| {
158                    let entry = BankExecutorCacheEntry {
159                        prev_epoch_count: entry.epoch_count.load(Relaxed),
160                        epoch_count: AtomicU64::default(),
161                        executor: entry.executor.clone(),
162                        hit_count: AtomicU64::new(entry.hit_count.load(Relaxed)),
163                    };
164                    (key, entry)
165                })
166                .collect()
167        };
168
169        Self {
170            capacity: parent_bank_executors.capacity,
171            current_epoch,
172            executors,
173            stats: Stats::default(),
174        }
175    }
176
177    pub fn get(&self, pubkey: &Pubkey) -> Option<Arc<LoadedProgram>> {
178        if let Some(entry) = self.executors.get(pubkey) {
179            self.stats.hits.fetch_add(1, Relaxed);
180            entry.epoch_count.fetch_add(1, Relaxed);
181            entry.hit_count.fetch_add(1, Relaxed);
182            Some(entry.executor.clone())
183        } else {
184            self.stats.misses.fetch_add(1, Relaxed);
185            None
186        }
187    }
188
189    pub fn put(&mut self, executors: impl Iterator<Item = (Pubkey, Arc<LoadedProgram>)>) {
190        let mut new_executors: Vec<_> = executors
191            .filter_map(|(key, executor)| {
192                if let Some(mut entry) = self.remove(&key) {
193                    self.stats.replacements.fetch_add(1, Relaxed);
194                    entry.executor = executor;
195                    let _ = self.executors.insert(key, entry);
196                    None
197                } else {
198                    self.stats.insertions.fetch_add(1, Relaxed);
199                    Some((key, executor))
200                }
201            })
202            .collect();
203
204        if !new_executors.is_empty() {
205            let mut counts = self
206                .executors
207                .iter()
208                .map(|(key, entry)| {
209                    let count = entry
210                        .prev_epoch_count
211                        .saturating_add(entry.epoch_count.load(Relaxed));
212                    (key, count)
213                })
214                .collect::<Vec<_>>();
215            counts.sort_unstable_by_key(|(_, count)| *count);
216
217            let primer_counts = Self::get_primer_counts(counts.as_slice(), new_executors.len());
218
219            if self.executors.len() >= self.capacity {
220                let mut least_keys = counts
221                    .iter()
222                    .take(new_executors.len())
223                    .map(|least| *least.0)
224                    .collect::<Vec<_>>();
225                for least_key in least_keys.drain(..) {
226                    let _ = self.remove(&least_key);
227                    self.stats
228                        .evictions
229                        .entry(least_key)
230                        .and_modify(|c| saturating_add_assign!(*c, 1))
231                        .or_insert(1);
232                }
233            }
234
235            for ((key, executor), primer_count) in new_executors.drain(..).zip(primer_counts) {
236                let entry = BankExecutorCacheEntry {
237                    prev_epoch_count: 0,
238                    epoch_count: AtomicU64::new(primer_count),
239                    executor: executor.clone(),
240                    hit_count: AtomicU64::new(1),
241                };
242                let _ = self.executors.insert(key, entry);
243            }
244        }
245    }
246
247    pub fn remove(&mut self, pubkey: &Pubkey) -> Option<BankExecutorCacheEntry> {
248        let maybe_entry = self.executors.remove(pubkey);
249        if let Some(entry) = maybe_entry.as_ref() {
250            if entry.hit_count.load(Relaxed) == 1 {
251                self.stats.one_hit_wonders.fetch_add(1, Relaxed);
252            }
253        }
254        maybe_entry
255    }
256
257    pub fn clear(&mut self) {
258        *self = BankExecutorCache::default();
259    }
260
261    pub fn get_primer_count_upper_bound_inclusive(counts: &[(&Pubkey, u64)]) -> u64 {
262        const PRIMER_COUNT_TARGET_PERCENTILE: u64 = 85;
263        #[allow(clippy::assertions_on_constants)]
264        {
265            assert!(PRIMER_COUNT_TARGET_PERCENTILE <= 100);
266        }
267        // Executor use-frequencies are assumed to fit a Pareto distribution.  Choose an
268        // upper-bound for our primer count as the actual count at the target rank to avoid
269        // an upward bias
270
271        let target_index = u64::try_from(counts.len().saturating_sub(1))
272            .ok()
273            .and_then(|counts| {
274                let index = counts
275                    .saturating_mul(PRIMER_COUNT_TARGET_PERCENTILE)
276                    .div(100); // switch to u64::saturating_div once stable
277                usize::try_from(index).ok()
278            })
279            .unwrap_or(0);
280
281        counts
282            .get(target_index)
283            .map(|(_, count)| *count)
284            .unwrap_or(0)
285    }
286
287    pub fn get_primer_counts(counts: &[(&Pubkey, u64)], num_counts: usize) -> Vec<u64> {
288        let max_primer_count = Self::get_primer_count_upper_bound_inclusive(counts);
289        let mut rng = rand::thread_rng();
290
291        (0..num_counts)
292            .map(|_| rng.gen_range(0, max_primer_count.saturating_add(1)))
293            .collect::<Vec<_>>()
294    }
295}
296
297/// Statistics of the entire `BankExecutorCache`
298#[derive(Debug, Default)]
299pub struct Stats {
300    pub hits: AtomicU64,
301    pub misses: AtomicU64,
302    pub evictions: HashMap<Pubkey, u64>,
303    pub insertions: AtomicU64,
304    pub replacements: AtomicU64,
305    pub one_hit_wonders: AtomicU64,
306}
307
308impl Stats {
309    /// Logs the measurement values
310    pub fn submit(&self, slot: Slot) {
311        let hits = self.hits.load(Relaxed);
312        let misses = self.misses.load(Relaxed);
313        let insertions = self.insertions.load(Relaxed);
314        let replacements = self.replacements.load(Relaxed);
315        let one_hit_wonders = self.one_hit_wonders.load(Relaxed);
316        let evictions: u64 = self.evictions.values().sum();
317        datapoint_info!(
318            "bank-executor-cache-stats",
319            ("slot", slot, i64),
320            ("hits", hits, i64),
321            ("misses", misses, i64),
322            ("evictions", evictions, i64),
323            ("insertions", insertions, i64),
324            ("replacements", replacements, i64),
325            ("one_hit_wonders", one_hit_wonders, i64),
326        );
327        debug!(
328            "Executor Cache Stats -- Hits: {}, Misses: {}, Evictions: {}, Insertions: {}, Replacements: {}, One-Hit-Wonders: {}",
329            hits, misses, evictions, insertions, replacements, one_hit_wonders,
330        );
331        if log_enabled!(log::Level::Trace) && !self.evictions.is_empty() {
332            let mut evictions = self.evictions.iter().collect::<Vec<_>>();
333            evictions.sort_by_key(|e| e.1);
334            let evictions = evictions
335                .into_iter()
336                .rev()
337                .map(|(program_id, evictions)| {
338                    format!("  {:<44}  {}", program_id.to_string(), evictions)
339                })
340                .collect::<Vec<_>>();
341            let evictions = evictions.join("\n");
342            trace!(
343                "Eviction Details:\n  {:<44}  {}\n{}",
344                "Program",
345                "Count",
346                evictions
347            );
348        }
349    }
350}
351
352#[allow(clippy::indexing_slicing)]
353#[cfg(test)]
354mod tests {
355    use super::*;
356
357    #[test]
358    fn test_executor_cache() {
359        let key1 = solana_sdk::pubkey::new_rand();
360        let key2 = solana_sdk::pubkey::new_rand();
361        let key3 = solana_sdk::pubkey::new_rand();
362        let key4 = solana_sdk::pubkey::new_rand();
363        let executor = Arc::new(LoadedProgram::default());
364        let mut cache = BankExecutorCache::new(3, 0);
365
366        cache.put([(key1, executor.clone())].into_iter());
367        cache.put([(key2, executor.clone())].into_iter());
368        cache.put([(key3, executor.clone())].into_iter());
369        assert!(cache.get(&key1).is_some());
370        assert!(cache.get(&key2).is_some());
371        assert!(cache.get(&key3).is_some());
372
373        assert!(cache.get(&key1).is_some());
374        assert!(cache.get(&key1).is_some());
375        assert!(cache.get(&key2).is_some());
376        cache.put([(key4, executor.clone())].into_iter());
377        assert!(cache.get(&key4).is_some());
378        let num_retained = [&key1, &key2, &key3]
379            .iter()
380            .filter_map(|key| cache.get(key))
381            .count();
382        assert_eq!(num_retained, 2);
383
384        assert!(cache.get(&key4).is_some());
385        assert!(cache.get(&key4).is_some());
386        assert!(cache.get(&key4).is_some());
387        cache.put([(key3, executor)].into_iter());
388        assert!(cache.get(&key3).is_some());
389        let num_retained = [&key1, &key2, &key4]
390            .iter()
391            .filter_map(|key| cache.get(key))
392            .count();
393        assert_eq!(num_retained, 2);
394    }
395
396    #[test]
397    fn test_cached_executor_eviction() {
398        let key1 = solana_sdk::pubkey::new_rand();
399        let key2 = solana_sdk::pubkey::new_rand();
400        let key3 = solana_sdk::pubkey::new_rand();
401        let key4 = solana_sdk::pubkey::new_rand();
402        let executor = Arc::new(LoadedProgram::default());
403        let mut cache = BankExecutorCache::new(3, 0);
404        assert!(cache.current_epoch == 0);
405
406        cache.put([(key1, executor.clone())].into_iter());
407        cache.put([(key2, executor.clone())].into_iter());
408        cache.put([(key3, executor.clone())].into_iter());
409        assert!(cache.get(&key1).is_some());
410        assert!(cache.get(&key1).is_some());
411        assert!(cache.get(&key1).is_some());
412
413        let mut cache = BankExecutorCache::new_from_parent_bank_executors(&cache, 1);
414        assert!(cache.current_epoch == 1);
415
416        assert!(cache.get(&key2).is_some());
417        assert!(cache.get(&key2).is_some());
418        assert!(cache.get(&key3).is_some());
419        cache.put([(key4, executor.clone())].into_iter());
420
421        assert!(cache.get(&key4).is_some());
422        let num_retained = [&key1, &key2, &key3]
423            .iter()
424            .filter_map(|key| cache.get(key))
425            .count();
426        assert_eq!(num_retained, 2);
427
428        cache.put([(key1, executor.clone())].into_iter());
429        cache.put([(key3, executor.clone())].into_iter());
430        assert!(cache.get(&key1).is_some());
431        assert!(cache.get(&key3).is_some());
432        let num_retained = [&key2, &key4]
433            .iter()
434            .filter_map(|key| cache.get(key))
435            .count();
436        assert_eq!(num_retained, 1);
437
438        cache = BankExecutorCache::new_from_parent_bank_executors(&cache, 2);
439        assert!(cache.current_epoch == 2);
440
441        cache.put([(key3, executor)].into_iter());
442        assert!(cache.get(&key3).is_some());
443    }
444
445    #[test]
446    fn test_executor_cache_evicts_smallest() {
447        let key1 = solana_sdk::pubkey::new_rand();
448        let key2 = solana_sdk::pubkey::new_rand();
449        let key3 = solana_sdk::pubkey::new_rand();
450        let executor = Arc::new(LoadedProgram::default());
451        let mut cache = BankExecutorCache::new(2, 0);
452
453        cache.put([(key1, executor.clone())].into_iter());
454        for _ in 0..5 {
455            let _ = cache.get(&key1);
456        }
457        cache.put([(key2, executor.clone())].into_iter());
458        // make key1's use-count for sure greater than key2's
459        let _ = cache.get(&key1);
460
461        let mut entries = cache
462            .executors
463            .iter()
464            .map(|(k, v)| (*k, v.epoch_count.load(Relaxed)))
465            .collect::<Vec<_>>();
466        entries.sort_by_key(|(_, v)| *v);
467        assert!(entries[0].1 < entries[1].1);
468
469        cache.put([(key3, executor)].into_iter());
470        assert!(cache.get(&entries[0].0).is_none());
471        assert!(cache.get(&entries[1].0).is_some());
472    }
473
474    #[test]
475    fn test_executor_cache_one_hit_wonder_counter() {
476        let mut cache = BankExecutorCache::new(1, 0);
477
478        let one_hit_wonder = Pubkey::new_unique();
479        let popular = Pubkey::new_unique();
480        let executor = Arc::new(LoadedProgram::default());
481
482        // make sure we're starting from where we think we are
483        assert_eq!(cache.stats.one_hit_wonders.load(Relaxed), 0);
484
485        // add our one-hit-wonder
486        cache.put([(one_hit_wonder, executor.clone())].into_iter());
487        assert_eq!(cache.executors[&one_hit_wonder].hit_count.load(Relaxed), 1);
488        // displace the one-hit-wonder with "popular program"
489        cache.put([(popular, executor.clone())].into_iter());
490        assert_eq!(cache.executors[&popular].hit_count.load(Relaxed), 1);
491
492        // one-hit-wonder counter incremented
493        assert_eq!(cache.stats.one_hit_wonders.load(Relaxed), 1);
494
495        // make "popular program" popular
496        cache.get(&popular).unwrap();
497        assert_eq!(cache.executors[&popular].hit_count.load(Relaxed), 2);
498
499        // evict "popular program"
500        cache.put([(one_hit_wonder, executor)].into_iter());
501        assert_eq!(cache.executors[&one_hit_wonder].hit_count.load(Relaxed), 1);
502
503        // one-hit-wonder counter not incremented
504        assert_eq!(cache.stats.one_hit_wonders.load(Relaxed), 1);
505    }
506
507    #[test]
508    fn test_executor_cache_get_primer_count_upper_bound_inclusive() {
509        let pubkey = Pubkey::default();
510        let v = [];
511        assert_eq!(
512            BankExecutorCache::get_primer_count_upper_bound_inclusive(&v),
513            0
514        );
515        let v = [(&pubkey, 1)];
516        assert_eq!(
517            BankExecutorCache::get_primer_count_upper_bound_inclusive(&v),
518            1
519        );
520        let v = (0u64..10).map(|i| (&pubkey, i)).collect::<Vec<_>>();
521        assert_eq!(
522            BankExecutorCache::get_primer_count_upper_bound_inclusive(v.as_slice()),
523            7
524        );
525    }
526
527    #[test]
528    fn test_executor_cache_stats() {
529        #[derive(Debug, Default, PartialEq)]
530        struct ComparableStats {
531            hits: u64,
532            misses: u64,
533            evictions: HashMap<Pubkey, u64>,
534            insertions: u64,
535            replacements: u64,
536            one_hit_wonders: u64,
537        }
538        impl From<&Stats> for ComparableStats {
539            fn from(stats: &Stats) -> Self {
540                let Stats {
541                    hits,
542                    misses,
543                    evictions,
544                    insertions,
545                    replacements,
546                    one_hit_wonders,
547                } = stats;
548                ComparableStats {
549                    hits: hits.load(Relaxed),
550                    misses: misses.load(Relaxed),
551                    evictions: evictions.clone(),
552                    insertions: insertions.load(Relaxed),
553                    replacements: replacements.load(Relaxed),
554                    one_hit_wonders: one_hit_wonders.load(Relaxed),
555                }
556            }
557        }
558
559        const CURRENT_EPOCH: Epoch = 0;
560        let mut cache = BankExecutorCache::new(2, CURRENT_EPOCH);
561        let mut expected_stats = ComparableStats::default();
562
563        let program_id1 = Pubkey::new_unique();
564        let program_id2 = Pubkey::new_unique();
565        let executor = Arc::new(LoadedProgram::default());
566
567        // make sure we're starting from where we think we are
568        assert_eq!(ComparableStats::from(&cache.stats), expected_stats,);
569
570        // insert some executors
571        cache.put([(program_id1, executor.clone())].into_iter());
572        cache.put([(program_id2, executor.clone())].into_iter());
573        expected_stats.insertions += 2;
574        assert_eq!(ComparableStats::from(&cache.stats), expected_stats);
575
576        // replace a one-hit-wonder executor
577        cache.put([(program_id1, executor.clone())].into_iter());
578        expected_stats.replacements += 1;
579        expected_stats.one_hit_wonders += 1;
580        assert_eq!(ComparableStats::from(&cache.stats), expected_stats);
581
582        // hit some executors
583        cache.get(&program_id1);
584        cache.get(&program_id1);
585        cache.get(&program_id2);
586        expected_stats.hits += 3;
587        assert_eq!(ComparableStats::from(&cache.stats), expected_stats);
588
589        // miss an executor
590        cache.get(&Pubkey::new_unique());
591        expected_stats.misses += 1;
592        assert_eq!(ComparableStats::from(&cache.stats), expected_stats);
593
594        // evict an executor
595        cache.put([(Pubkey::new_unique(), executor)].into_iter());
596        expected_stats.insertions += 1;
597        expected_stats.evictions.insert(program_id2, 1);
598        assert_eq!(ComparableStats::from(&cache.stats), expected_stats);
599
600        // make sure stats are cleared in new_from_parent
601        assert_eq!(
602            ComparableStats::from(
603                &BankExecutorCache::new_from_parent_bank_executors(&cache, CURRENT_EPOCH).stats
604            ),
605            ComparableStats::default()
606        );
607        assert_eq!(
608            ComparableStats::from(
609                &BankExecutorCache::new_from_parent_bank_executors(&cache, CURRENT_EPOCH + 1).stats
610            ),
611            ComparableStats::default()
612        );
613    }
614}
solana_program_runtime/executor_cache.rs

solana_program_runtime/
executor_cache.rs
