solana_accounts_db/
accounts_partition.rs

1//! Partitioning of the accounts into chunks for rent collection
2use {
3    itertools::Itertools,
4    log::trace,
5    solana_pubkey::Pubkey,
6    solana_sdk::{
7        clock::{Slot, SlotCount, SlotIndex},
8        stake_history::Epoch,
9        sysvar::epoch_schedule::EpochSchedule,
10    },
11    std::{collections::HashSet, mem, ops::RangeInclusive},
12};
13
14// Eager rent collection repeats in cyclic manner.
15// Each cycle is composed of <partition_count> number of tiny pubkey subranges
16// to scan, which is always multiple of the number of slots in epoch.
17pub type PartitionIndex = u64;
18type PartitionsPerCycle = u64;
19pub type Partition = (PartitionIndex, PartitionIndex, PartitionsPerCycle);
20type RentCollectionCycleParams = (
21    Epoch,
22    SlotCount,
23    bool,
24    Epoch,
25    EpochCount,
26    PartitionsPerCycle,
27);
28type EpochCount = u64;
29
30fn partition_index_from_slot_index(
31    slot_index_in_epoch: SlotIndex,
32    (
33        epoch,
34        slot_count_per_epoch,
35        _,
36        base_epoch,
37        epoch_count_per_cycle,
38        _,
39    ): RentCollectionCycleParams,
40) -> PartitionIndex {
41    let epoch_offset = epoch - base_epoch;
42    let epoch_index_in_cycle = epoch_offset % epoch_count_per_cycle;
43    slot_index_in_epoch + epoch_index_in_cycle * slot_count_per_epoch
44}
45
46pub fn get_partition_from_slot_indexes(
47    cycle_params: RentCollectionCycleParams,
48    start_slot_index: SlotIndex,
49    end_slot_index: SlotIndex,
50    generated_for_gapped_epochs: bool,
51) -> Partition {
52    let (_, _, in_multi_epoch_cycle, _, _, partition_count) = cycle_params;
53
54    // use common codepath for both very likely and very unlikely for the sake of minimized
55    // risk of any miscalculation instead of negligibly faster computation per slot for the
56    // likely case.
57    let mut start_partition_index = partition_index_from_slot_index(start_slot_index, cycle_params);
58    let mut end_partition_index = partition_index_from_slot_index(end_slot_index, cycle_params);
59
60    // Adjust partition index for some edge cases
61    let is_special_new_epoch = start_slot_index == 0 && end_slot_index != 1;
62    let in_middle_of_cycle = start_partition_index > 0;
63    if in_multi_epoch_cycle && is_special_new_epoch && in_middle_of_cycle {
64        // Adjust slot indexes so that the final partition ranges are continuous!
65        // This is need because the caller gives us off-by-one indexes when
66        // an epoch boundary is crossed.
67        // Usually there is no need for this adjustment because cycles are aligned
68        // with epochs. But for multi-epoch cycles, adjust the indexes if it
69        // happens in the middle of a cycle for both gapped and not-gapped cases:
70        //
71        // epoch (slot range)|slot idx.*1|raw part. idx.|adj. part. idx.|epoch boundary
72        // ------------------+-----------+--------------+---------------+--------------
73        // 3 (20..30)        | [7..8]    |   7.. 8      |   7.. 8
74        //                   | [8..9]    |   8.. 9      |   8.. 9
75        // 4 (30..40)        | [0..0]    |<10>..10      | <9>..10      <--- not gapped
76        //                   | [0..1]    |  10..11      |  10..12
77        //                   | [1..2]    |  11..12      |  11..12
78        //                   | [2..9   *2|  12..19      |  12..19      <-+
79        // 5 (40..50)        |  0..0   *2|<20>..<20>    |<19>..<19> *3 <-+- gapped
80        //                   |  0..4]    |<20>..24      |<19>..24      <-+
81        //                   | [4..5]    |  24..25      |  24..25
82        //                   | [5..6]    |  25..26      |  25..26
83        //
84        // NOTE: <..> means the adjusted slots
85        //
86        // *1: The range of parent_bank.slot() and current_bank.slot() is firstly
87        //     split by the epoch boundaries and then the split ones are given to us.
88        //     The original ranges are denoted as [...]
89        // *2: These are marked with generated_for_gapped_epochs = true.
90        // *3: This becomes no-op partition
91        start_partition_index -= 1;
92        if generated_for_gapped_epochs {
93            assert_eq!(start_slot_index, end_slot_index);
94            end_partition_index -= 1;
95        }
96    }
97
98    (start_partition_index, end_partition_index, partition_count)
99}
100
101/// return all end partition indexes for the given partition
102/// partition could be (0, 1, N). In this case we only return [1]
103///  the single 'end_index' that covers this partition.
104/// partition could be (0, 2, N). In this case, we return [1, 2], which are all
105/// the 'end_index' values contained in that range.
106/// (0, 0, N) returns [0] as a special case.
107/// There is a relationship between
108/// 1. 'pubkey_range_from_partition'
109/// 2. 'partition_from_pubkey'
110/// 3. this function
111pub fn get_partition_end_indexes(partition: &Partition) -> Vec<PartitionIndex> {
112    if partition.0 == partition.1 && partition.0 == 0 {
113        // special case for start=end=0. ie. (0, 0, N). This returns [0]
114        vec![0]
115    } else {
116        // normal case of (start, end, N)
117        // so, we want [start+1, start+2, ..=end]
118        // if start == end, then return []
119        (partition.0..partition.1).map(|index| index + 1).collect()
120    }
121}
122
123pub fn rent_single_epoch_collection_cycle_params(
124    epoch: Epoch,
125    slot_count_per_epoch: SlotCount,
126) -> RentCollectionCycleParams {
127    (
128        epoch,
129        slot_count_per_epoch,
130        false,
131        0,
132        1,
133        slot_count_per_epoch,
134    )
135}
136
137pub fn rent_multi_epoch_collection_cycle_params(
138    epoch: Epoch,
139    slot_count_per_epoch: SlotCount,
140    first_normal_epoch: Epoch,
141    epoch_count_in_cycle: Epoch,
142) -> RentCollectionCycleParams {
143    let partition_count = slot_count_per_epoch * epoch_count_in_cycle;
144    (
145        epoch,
146        slot_count_per_epoch,
147        true,
148        first_normal_epoch,
149        epoch_count_in_cycle,
150        partition_count,
151    )
152}
153
154pub fn get_partitions(
155    slot: Slot,
156    parent_slot: Slot,
157    slot_count_in_two_day: SlotCount,
158) -> Vec<Partition> {
159    let parent_cycle = parent_slot / slot_count_in_two_day;
160    let current_cycle = slot / slot_count_in_two_day;
161    let mut parent_cycle_index = parent_slot % slot_count_in_two_day;
162    let current_cycle_index = slot % slot_count_in_two_day;
163    let mut partitions = vec![];
164    if parent_cycle < current_cycle {
165        if current_cycle_index > 0 {
166            // generate and push gapped partitions because some slots are skipped
167            let parent_last_cycle_index = slot_count_in_two_day - 1;
168
169            // ... for parent cycle
170            partitions.push((
171                parent_cycle_index,
172                parent_last_cycle_index,
173                slot_count_in_two_day,
174            ));
175
176            // ... for current cycle
177            partitions.push((0, 0, slot_count_in_two_day));
178        }
179        parent_cycle_index = 0;
180    }
181
182    partitions.push((
183        parent_cycle_index,
184        current_cycle_index,
185        slot_count_in_two_day,
186    ));
187
188    partitions
189}
190
191// Mostly, the pair (start_index & end_index) is equivalent to this range:
192// start_index..=end_index. But it has some exceptional cases, including
193// this important and valid one:
194//   0..=0: the first partition in the new epoch when crossing epochs
195pub fn pubkey_range_from_partition(
196    (start_index, end_index, partition_count): Partition,
197) -> RangeInclusive<Pubkey> {
198    assert!(start_index <= end_index);
199    assert!(start_index < partition_count);
200    assert!(end_index < partition_count);
201    assert!(0 < partition_count);
202
203    type Prefix = u64;
204    const PREFIX_SIZE: usize = mem::size_of::<Prefix>();
205    const PREFIX_MAX: Prefix = Prefix::MAX;
206
207    let mut start_pubkey = [0x00u8; 32];
208    let mut end_pubkey = [0xffu8; 32];
209
210    if partition_count == 1 {
211        assert_eq!(start_index, 0);
212        assert_eq!(end_index, 0);
213        return Pubkey::new_from_array(start_pubkey)..=Pubkey::new_from_array(end_pubkey);
214    }
215
216    // not-overflowing way of `(Prefix::max_value() + 1) / partition_count`
217    let partition_width = (PREFIX_MAX - partition_count + 1) / partition_count + 1;
218    let mut start_key_prefix = if start_index == 0 && end_index == 0 {
219        0
220    } else if start_index + 1 == partition_count {
221        PREFIX_MAX
222    } else {
223        (start_index + 1) * partition_width
224    };
225
226    let mut end_key_prefix = if end_index + 1 == partition_count {
227        PREFIX_MAX
228    } else {
229        (end_index + 1) * partition_width - 1
230    };
231
232    if start_index != 0 && start_index == end_index {
233        // n..=n (n != 0): a noop pair across epochs without a gap under
234        // multi_epoch_cycle, just nullify it.
235        if end_key_prefix == PREFIX_MAX {
236            start_key_prefix = end_key_prefix;
237            start_pubkey = end_pubkey;
238        } else {
239            end_key_prefix = start_key_prefix;
240            end_pubkey = start_pubkey;
241        }
242    }
243
244    start_pubkey[0..PREFIX_SIZE].copy_from_slice(&start_key_prefix.to_be_bytes());
245    end_pubkey[0..PREFIX_SIZE].copy_from_slice(&end_key_prefix.to_be_bytes());
246    let start_pubkey_final = Pubkey::new_from_array(start_pubkey);
247    let end_pubkey_final = Pubkey::new_from_array(end_pubkey);
248    trace!(
249        "pubkey_range_from_partition: ({}-{})/{} [{}]: {}-{}",
250        start_index,
251        end_index,
252        partition_count,
253        (end_key_prefix - start_key_prefix),
254        start_pubkey.iter().map(|x| format!("{x:02x}")).join(""),
255        end_pubkey.iter().map(|x| format!("{x:02x}")).join(""),
256    );
257    #[cfg(test)]
258    if start_index != end_index {
259        assert_eq!(
260            if start_index == 0 && end_index == 0 {
261                0
262            } else {
263                start_index + 1
264            },
265            partition_from_pubkey(&start_pubkey_final, partition_count),
266            "{start_index}, {end_index}, start_key_prefix: {start_key_prefix}, {start_pubkey_final}, {partition_count}"
267        );
268        assert_eq!(
269            end_index,
270            partition_from_pubkey(&end_pubkey_final, partition_count),
271            "{start_index}, {end_index}, {end_pubkey_final}, {partition_count}"
272        );
273        if start_index != 0 {
274            start_pubkey[0..PREFIX_SIZE]
275                .copy_from_slice(&start_key_prefix.saturating_sub(1).to_be_bytes());
276            let pubkey_test = Pubkey::new_from_array(start_pubkey);
277            assert_eq!(
278                start_index,
279                partition_from_pubkey(&pubkey_test, partition_count),
280                "{}, {}, start_key_prefix-1: {}, {}, {}",
281                start_index,
282                end_index,
283                start_key_prefix.saturating_sub(1),
284                pubkey_test,
285                partition_count
286            );
287        }
288        if end_index != partition_count - 1 && end_index != 0 {
289            end_pubkey[0..PREFIX_SIZE]
290                .copy_from_slice(&end_key_prefix.saturating_add(1).to_be_bytes());
291            let pubkey_test = Pubkey::new_from_array(end_pubkey);
292            assert_eq!(
293                end_index.saturating_add(1),
294                partition_from_pubkey(&pubkey_test, partition_count),
295                "start: {}, end: {}, pubkey: {}, partition_count: {}, prefix_before_addition: {}, prefix after: {}",
296                start_index,
297                end_index,
298                pubkey_test,
299                partition_count,
300                end_key_prefix,
301                end_key_prefix.saturating_add(1),
302            );
303        }
304    }
305    // should be an inclusive range (a closed interval) like this:
306    // [0xgg00-0xhhff], [0xii00-0xjjff], ... (where 0xii00 == 0xhhff + 1)
307    start_pubkey_final..=end_pubkey_final
308}
309
310pub fn prefix_from_pubkey(pubkey: &Pubkey) -> u64 {
311    const PREFIX_SIZE: usize = mem::size_of::<u64>();
312    u64::from_be_bytes(pubkey.as_ref()[0..PREFIX_SIZE].try_into().unwrap())
313}
314
315/// This is the inverse of pubkey_range_from_partition.
316/// return the lowest end_index which would contain this pubkey
317pub fn partition_from_pubkey(
318    pubkey: &Pubkey,
319    partition_count: PartitionsPerCycle,
320) -> PartitionIndex {
321    type Prefix = u64;
322    const PREFIX_MAX: Prefix = Prefix::MAX;
323
324    if partition_count == 1 {
325        return 0;
326    }
327
328    // not-overflowing way of `(Prefix::max_value() + 1) / partition_count`
329    let partition_width = (PREFIX_MAX - partition_count + 1) / partition_count + 1;
330
331    let prefix = prefix_from_pubkey(pubkey);
332    if prefix == 0 {
333        return 0;
334    }
335
336    if prefix == PREFIX_MAX {
337        return partition_count - 1;
338    }
339
340    let mut result = (prefix + 1) / partition_width;
341    if (prefix + 1) % partition_width == 0 {
342        // adjust for integer divide
343        result = result.saturating_sub(1);
344    }
345    result
346}
347
348lazy_static! {
349    static ref EMPTY_HASHSET: HashSet<Pubkey> = HashSet::default();
350}
351
352/// populated at startup with the accounts that were found that are rent paying.
353/// These are the 'possible' rent paying accounts.
354/// This set can never grow during runtime since it is not possible to create rent paying accounts now.
355/// It can shrink during execution if a rent paying account is dropped to lamports=0 or is topped off.
356/// The next time the validator restarts, it will remove the account from this list.
357#[derive(Debug, Default)]
358pub struct RentPayingAccountsByPartition {
359    /// 1st index is partition end index, 0..=432_000
360    /// 2nd dimension is list of pubkeys which were identified at startup to be rent paying
361    /// At the moment, we use this data structure to verify all rent paying accounts are expected.
362    /// When we stop iterating the accounts index to FIND rent paying accounts, we will no longer need this to be a hashset.
363    /// It can just be a vec.
364    pub accounts: Vec<HashSet<Pubkey>>,
365    partition_count: PartitionsPerCycle,
366}
367
368impl RentPayingAccountsByPartition {
369    /// create new struct. Need slots per epoch from 'epoch_schedule'
370    pub fn new(epoch_schedule: &EpochSchedule) -> Self {
371        let partition_count = epoch_schedule.slots_per_epoch;
372        Self {
373            partition_count,
374            accounts: (0..=partition_count)
375                .map(|_| HashSet::<Pubkey>::default())
376                .collect(),
377        }
378    }
379    /// Remember that 'pubkey' can possibly be rent paying.
380    pub fn add_account(&mut self, pubkey: &Pubkey) {
381        let partition_end_index = partition_from_pubkey(pubkey, self.partition_count);
382        let list = &mut self.accounts[partition_end_index as usize];
383
384        list.insert(*pubkey);
385    }
386    /// return all pubkeys that can possibly be rent paying with this partition end_index
387    pub fn get_pubkeys_in_partition_index(
388        &self,
389        partition_end_index: PartitionIndex,
390    ) -> &HashSet<Pubkey> {
391        self.accounts
392            .get(partition_end_index as usize)
393            .unwrap_or(&EMPTY_HASHSET)
394    }
395    pub fn is_initialized(&self) -> bool {
396        self.partition_count != 0
397    }
398}
399
400#[cfg(test)]
401pub(crate) mod tests {
402    use {super::*, std::str::FromStr};
403
404    #[test]
405    fn test_get_partition_end_indexes() {
406        for n in 5..7 {
407            assert_eq!(vec![0], get_partition_end_indexes(&(0, 0, n)));
408            assert!(get_partition_end_indexes(&(1, 1, n)).is_empty());
409            assert_eq!(vec![1], get_partition_end_indexes(&(0, 1, n)));
410            assert_eq!(vec![1, 2], get_partition_end_indexes(&(0, 2, n)));
411            assert_eq!(vec![3, 4], get_partition_end_indexes(&(2, 4, n)));
412        }
413    }
414
415    #[test]
416    fn test_rent_pubkey_range_max() {
417        // start==end && start != 0 is curious behavior. Verifying it here.
418        solana_logger::setup();
419        let range = pubkey_range_from_partition((1, 1, 3));
420        let p = partition_from_pubkey(range.start(), 3);
421        assert_eq!(p, 2);
422        let range = pubkey_range_from_partition((1, 2, 3));
423        let p = partition_from_pubkey(range.start(), 3);
424        assert_eq!(p, 2);
425        let range = pubkey_range_from_partition((2, 2, 3));
426        let p = partition_from_pubkey(range.start(), 3);
427        assert_eq!(p, 2);
428        let range = pubkey_range_from_partition((1, 1, 16));
429        let p = partition_from_pubkey(range.start(), 16);
430        assert_eq!(p, 2);
431        let range = pubkey_range_from_partition((1, 2, 16));
432        let p = partition_from_pubkey(range.start(), 16);
433        assert_eq!(p, 2);
434        let range = pubkey_range_from_partition((2, 2, 16));
435        let p = partition_from_pubkey(range.start(), 16);
436        assert_eq!(p, 3);
437        let range = pubkey_range_from_partition((15, 15, 16));
438        let p = partition_from_pubkey(range.start(), 16);
439        assert_eq!(p, 15);
440    }
441
442    #[test]
443    fn test_rent_eager_pubkey_range_minimal() {
444        let range = pubkey_range_from_partition((0, 0, 1));
445        assert_eq!(
446            range,
447            Pubkey::new_from_array([0x00; 32])..=Pubkey::new_from_array([0xff; 32])
448        );
449    }
450
451    #[test]
452    fn test_rent_eager_pubkey_range_maximum() {
453        let max = !0;
454
455        let range = pubkey_range_from_partition((0, 0, max));
456        assert_eq!(
457            range,
458            Pubkey::new_from_array([0x00; 32])
459                ..=Pubkey::new_from_array([
460                    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff, 0xff,
461                    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
462                    0xff, 0xff, 0xff, 0xff, 0xff, 0xff
463                ])
464        );
465        let range = pubkey_range_from_partition((0, 1, max));
466        const ONE: u8 = 0x01;
467        assert_eq!(
468            range,
469            Pubkey::new_from_array([
470                0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, ONE, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
471                0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
472                0x00, 0x00, 0x00, 0x00,
473            ])
474                ..=Pubkey::new_from_array([
475                    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0xff, 0xff, 0xff, 0xff, 0xff,
476                    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
477                    0xff, 0xff, 0xff, 0xff, 0xff, 0xff
478                ])
479        );
480        let range = pubkey_range_from_partition((max - 3, max - 2, max));
481        const FD: u8 = 0xfd;
482        assert_eq!(
483            range,
484            Pubkey::new_from_array([
485                0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfd, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
486                0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
487                0x00, 0x00, 0x00, 0x00,
488            ])
489                ..=Pubkey::new_from_array([
490                    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, FD, 0xff, 0xff, 0xff, 0xff, 0xff,
491                    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
492                    0xff, 0xff, 0xff, 0xff, 0xff, 0xff
493                ])
494        );
495        let range = pubkey_range_from_partition((max - 2, max - 1, max));
496        assert_eq!(
497            range,
498            Pubkey::new_from_array([
499                0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
500                0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
501                0x00, 0x00, 0x00, 0x00,
502            ])..=pubkey_max_value()
503        );
504
505        fn should_cause_overflow(partition_count: u64) -> bool {
506            // Check `partition_width = (u64::MAX + 1) / partition_count` is exact and
507            // does not have a remainder.
508            // This way, `partition_width * partition_count == (u64::MAX + 1)`,
509            // so the test actually tests for overflow
510            (u64::MAX - partition_count + 1) % partition_count == 0
511        }
512
513        let max_exact = 64;
514        // Make sure `max_exact` divides evenly when calculating `calculate_partition_width`
515        assert!(should_cause_overflow(max_exact));
516        // Make sure `max_inexact` doesn't divide evenly when calculating `calculate_partition_width`
517        let max_inexact = 10;
518        assert!(!should_cause_overflow(max_inexact));
519
520        for max in &[max_exact, max_inexact] {
521            let range = pubkey_range_from_partition((max - 1, max - 1, *max));
522            assert_eq!(range, pubkey_max_value()..=pubkey_max_value());
523        }
524    }
525
526    #[test]
527    fn test_rent_eager_pubkey_range_noop_range() {
528        let test_map = map_to_test_bad_range();
529
530        let range = pubkey_range_from_partition((0, 0, 3));
531        assert_eq!(
532            range,
533            Pubkey::new_from_array([0x00; 32])
534                ..=Pubkey::new_from_array([
535                    0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x54, 0xff, 0xff, 0xff, 0xff, 0xff,
536                    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
537                    0xff, 0xff, 0xff, 0xff, 0xff, 0xff
538                ])
539        );
540        let _ = test_map.range(range);
541
542        let range = pubkey_range_from_partition((1, 1, 3));
543        let same = Pubkey::new_from_array([
544            0xaa, 0xaa, 0xaa, 0xaa, 0xaa, 0xaa, 0xaa, 0xaa, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
545            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
546            0x00, 0x00, 0x00, 0x00,
547        ]);
548        assert_eq!(range, same..=same);
549        let _ = test_map.range(range);
550
551        let range = pubkey_range_from_partition((2, 2, 3));
552        assert_eq!(range, pubkey_max_value()..=pubkey_max_value());
553        let _ = test_map.range(range);
554    }
555
556    fn map_to_test_bad_range() -> std::collections::BTreeMap<Pubkey, i8> {
557        let mut map = std::collections::BTreeMap::new();
558        // when empty, std::collections::BTreeMap doesn't sanitize given range...
559        map.insert(solana_pubkey::new_rand(), 1);
560        map
561    }
562
563    #[test]
564    #[should_panic(expected = "range start is greater than range end in BTreeMap")]
565    fn test_rent_eager_bad_range() {
566        let test_map = map_to_test_bad_range();
567        let _ = test_map.range(
568            Pubkey::new_from_array([
569                0xaa, 0xaa, 0xaa, 0xaa, 0xaa, 0xaa, 0xaa, 0xaa, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
570                0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
571                0x00, 0x00, 0x00, 0x01,
572            ])
573                ..=Pubkey::new_from_array([
574                    0xaa, 0xaa, 0xaa, 0xaa, 0xaa, 0xaa, 0xaa, 0xaa, 0x00, 0x00, 0x00, 0x00, 0x00,
575                    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
576                    0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
577                ]),
578        );
579    }
580
581    fn pubkey_max_value() -> Pubkey {
582        let highest = Pubkey::from_str("JEKNVnkbo3jma5nREBBJCDoXFVeKkD56V3xKrvRmWxFG").unwrap();
583        let arr = Pubkey::new_from_array([0xff; 32]);
584        assert_eq!(highest, arr);
585        arr
586    }
587
588    #[test]
589    fn test_rent_eager_pubkey_range_dividable() {
590        let test_map = map_to_test_bad_range();
591        let range = pubkey_range_from_partition((0, 0, 2));
592
593        assert_eq!(
594            range,
595            Pubkey::new_from_array([0x00; 32])
596                ..=Pubkey::new_from_array([
597                    0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
598                    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
599                    0xff, 0xff, 0xff, 0xff, 0xff, 0xff
600                ])
601        );
602        let _ = test_map.range(range);
603
604        let range = pubkey_range_from_partition((0, 1, 2));
605        assert_eq!(
606            range,
607            Pubkey::new_from_array([
608                0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
609                0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
610                0x00, 0x00, 0x00, 0x00
611            ])
612                ..=Pubkey::new_from_array([
613                    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
614                    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
615                    0xff, 0xff, 0xff, 0xff, 0xff, 0xff
616                ])
617        );
618        let _ = test_map.range(range);
619    }
620
621    #[test]
622    fn test_rent_eager_pubkey_range_not_dividable() {
623        solana_logger::setup();
624
625        let test_map = map_to_test_bad_range();
626        let range = pubkey_range_from_partition((0, 0, 3));
627        assert_eq!(
628            range,
629            Pubkey::new_from_array([0x00; 32])
630                ..=Pubkey::new_from_array([
631                    0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x54, 0xff, 0xff, 0xff, 0xff, 0xff,
632                    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
633                    0xff, 0xff, 0xff, 0xff, 0xff, 0xff
634                ])
635        );
636        let _ = test_map.range(range);
637
638        let range = pubkey_range_from_partition((0, 1, 3));
639        assert_eq!(
640            range,
641            Pubkey::new_from_array([
642                0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
643                0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
644                0x00, 0x00, 0x00, 0x00
645            ])
646                ..=Pubkey::new_from_array([
647                    0xaa, 0xaa, 0xaa, 0xaa, 0xaa, 0xaa, 0xaa, 0xa9, 0xff, 0xff, 0xff, 0xff, 0xff,
648                    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
649                    0xff, 0xff, 0xff, 0xff, 0xff, 0xff
650                ])
651        );
652        let _ = test_map.range(range);
653
654        let range = pubkey_range_from_partition((1, 2, 3));
655        assert_eq!(
656            range,
657            Pubkey::new_from_array([
658                0xaa, 0xaa, 0xaa, 0xaa, 0xaa, 0xaa, 0xaa, 0xaa, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
659                0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
660                0x00, 0x00, 0x00, 0x00
661            ])
662                ..=Pubkey::new_from_array([
663                    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
664                    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
665                    0xff, 0xff, 0xff, 0xff, 0xff, 0xff
666                ])
667        );
668        let _ = test_map.range(range);
669    }
670
671    #[test]
672    fn test_rent_eager_pubkey_range_gap() {
673        solana_logger::setup();
674
675        let test_map = map_to_test_bad_range();
676        let range = pubkey_range_from_partition((120, 1023, 12345));
677        assert_eq!(
678            range,
679            Pubkey::new_from_array([
680                0x02, 0x82, 0x5a, 0x89, 0xd1, 0xac, 0x58, 0x9c, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
681                0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
682                0x00, 0x00, 0x00, 0x00
683            ])
684                ..=Pubkey::new_from_array([
685                    0x15, 0x3c, 0x1d, 0xf1, 0xc6, 0x39, 0xef, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
686                    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
687                    0xff, 0xff, 0xff, 0xff, 0xff, 0xff
688                ])
689        );
690        let _ = test_map.range(range);
691    }
692
693    #[test]
694    fn test_add() {
695        let mut test = RentPayingAccountsByPartition::new(&EpochSchedule::custom(32, 0, false));
696        let pk = Pubkey::from([1; 32]);
697        test.add_account(&pk);
698        // make sure duplicate adds only result in a single item
699        test.add_account(&pk);
700        assert_eq!(test.get_pubkeys_in_partition_index(0).len(), 1);
701        assert!(test.get_pubkeys_in_partition_index(1).is_empty());
702        assert!(test.is_initialized());
703        let test = RentPayingAccountsByPartition::default();
704        assert!(!test.is_initialized());
705    }
706}
solana_accounts_db/accounts_partition.rs

solana_accounts_db/
accounts_partition.rs
