_ Git - rust-lightning/blob - lightning/src/util/hash_tables.rs

   1 //! Generally LDK uses `std`'s `HashMap`s, however when building for no-std, LDK uses `hashbrown`'s
   2 //! `HashMap`s with the `std` `SipHasher` and uses `getrandom` to opportunistically randomize it,
   3 //! if randomization is available.
   4 //!
   5 //! This module simply re-exports the `HashMap` used in LDK for public consumption.
   6
   7 #[cfg(feature = "hashbrown")]
   8 extern crate hashbrown;
   9 #[cfg(feature = "possiblyrandom")]
  10 extern crate possiblyrandom;
  11
  12 // For no-std builds, we need to use hashbrown, however, by default, it doesn't randomize the
  13 // hashing and is vulnerable to HashDoS attacks. Thus, we use the core SipHasher when not using
  14 // std, but use `getrandom` to randomize it if its available.
  15
  16 #[cfg(not(feature = "hashbrown"))]
  17 mod std_hashtables {
  18         pub use std::collections::HashMap;
  19         pub use std::collections::hash_map::RandomState;
  20
  21         pub(crate) use std::collections::{HashSet, hash_map};
  22
  23         pub(crate) type OccupiedHashMapEntry<'a, K, V> =
  24                 std::collections::hash_map::OccupiedEntry<'a, K, V>;
  25         pub(crate) type VacantHashMapEntry<'a, K, V> =
  26                 std::collections::hash_map::VacantEntry<'a, K, V>;
  27
  28         /// Builds a new [`HashMap`].
  29         pub fn new_hash_map<K, V>() -> HashMap<K, V> { HashMap::new() }
  30         /// Builds a new [`HashMap`] with the given capacity.
  31         pub fn hash_map_with_capacity<K, V>(cap: usize) -> HashMap<K, V> {
  32                 HashMap::with_capacity(cap)
  33         }
  34         pub(crate) fn hash_map_from_iter<K: core::hash::Hash + Eq, V, I: IntoIterator<Item=(K, V)>>(iter: I) -> HashMap<K, V> {
  35                 HashMap::from_iter(iter)
  36         }
  37
  38         pub(crate) fn new_hash_set<K>() -> HashSet<K> { HashSet::new() }
  39         pub(crate) fn hash_set_with_capacity<K>(cap: usize) -> HashSet<K> {
  40                 HashSet::with_capacity(cap)
  41         }
  42         pub(crate) fn hash_set_from_iter<K: core::hash::Hash + Eq, I: IntoIterator<Item=K>>(iter: I) -> HashSet<K> {
  43                 HashSet::from_iter(iter)
  44         }
  45 }
  46 #[cfg(not(feature = "hashbrown"))]
  47 pub use std_hashtables::*;
  48
  49 #[cfg(feature = "hashbrown")]
  50 pub(crate) use self::hashbrown::hash_map;
  51
  52 #[cfg(feature = "hashbrown")]
  53 mod hashbrown_tables {
  54         #[cfg(feature = "std")]
  55         mod hasher {
  56                 pub use std::collections::hash_map::RandomState;
  57         }
  58         #[cfg(not(feature = "std"))]
  59         mod hasher {
  60                 #![allow(deprecated)] // hash::SipHasher was deprecated in favor of something only in std.
  61                 use core::hash::{BuildHasher, SipHasher};
  62
  63                 #[derive(Clone, Copy)]
  64                 /// A simple implementation of [`BuildHasher`] that uses `getrandom` to opportunistically
  65                 /// randomize, if the platform supports it.
  66                 pub struct RandomState {
  67                         k0: u64, k1: u64,
  68                 }
  69
  70                 impl RandomState {
  71                         /// Constructs a new [`RandomState`] which may or may not be random, depending on the
  72                         /// target platform.
  73                         pub fn new() -> RandomState {
  74                                 let (k0, k1);
  75                                 #[cfg(all(not(fuzzing), feature = "possiblyrandom"))] {
  76                                         let mut keys = [0; 16];
  77                                         possiblyrandom::getpossiblyrandom(&mut keys);
  78
  79                                         let mut k0_bytes = [0; 8];
  80                                         let mut k1_bytes = [0; 8];
  81                                         k0_bytes.copy_from_slice(&keys[..8]);
  82                                         k1_bytes.copy_from_slice(&keys[8..]);
  83                                         k0 = u64::from_le_bytes(k0_bytes);
  84                                         k1 = u64::from_le_bytes(k1_bytes);
  85                                 }
  86                                 #[cfg(any(fuzzing, not(feature = "possiblyrandom")))] {
  87                                         k0 = 0;
  88                                         k1 = 0;
  89                                 }
  90                                 RandomState { k0, k1 }
  91                         }
  92                 }
  93
  94                 impl Default for RandomState {
  95                         fn default() -> RandomState { RandomState::new() }
  96                 }
  97
  98                 impl BuildHasher for RandomState {
  99                         type Hasher = SipHasher;
 100                         fn build_hasher(&self) -> SipHasher {
 101                                 SipHasher::new_with_keys(self.k0, self.k1)
 102                         }
 103                 }
 104         }
 105
 106         pub use hasher::*;
 107         use super::*;
 108
 109         /// The HashMap type used in LDK.
 110         pub type HashMap<K, V> = hashbrown::HashMap<K, V, RandomState>;
 111         pub(crate) type HashSet<K> = hashbrown::HashSet<K, RandomState>;
 112
 113         pub(crate) type OccupiedHashMapEntry<'a, K, V> =
 114                 hashbrown::hash_map::OccupiedEntry<'a, K, V, RandomState>;
 115         pub(crate) type VacantHashMapEntry<'a, K, V> =
 116                 hashbrown::hash_map::VacantEntry<'a, K, V, RandomState>;
 117
 118         /// Builds a new [`HashMap`].
 119         pub fn new_hash_map<K, V>() -> HashMap<K, V> {
 120                 HashMap::with_hasher(RandomState::new())
 121         }
 122         /// Builds a new [`HashMap`] with the given capacity.
 123         pub fn hash_map_with_capacity<K, V>(cap: usize) -> HashMap<K, V> {
 124                 HashMap::with_capacity_and_hasher(cap, RandomState::new())
 125         }
 126         pub(crate) fn hash_map_from_iter<K: core::hash::Hash + Eq, V, I: IntoIterator<Item=(K, V)>>(iter: I) -> HashMap<K, V> {
 127                 let iter = iter.into_iter();
 128                 let min_size = iter.size_hint().0;
 129                 let mut res = HashMap::with_capacity_and_hasher(min_size, RandomState::new());
 130                 res.extend(iter);
 131                 res
 132         }
 133
 134         pub(crate) fn new_hash_set<K>() -> HashSet<K> {
 135                 HashSet::with_hasher(RandomState::new())
 136         }
 137         pub(crate) fn hash_set_with_capacity<K>(cap: usize) -> HashSet<K> {
 138                 HashSet::with_capacity_and_hasher(cap, RandomState::new())
 139         }
 140         pub(crate) fn hash_set_from_iter<K: core::hash::Hash + Eq, I: IntoIterator<Item=K>>(iter: I) -> HashSet<K> {
 141                 let iter = iter.into_iter();
 142                 let min_size = iter.size_hint().0;
 143                 let mut res = HashSet::with_capacity_and_hasher(min_size, RandomState::new());
 144                 res.extend(iter);
 145                 res
 146         }
 147 }
 148 #[cfg(feature = "hashbrown")]
 149 pub use hashbrown_tables::*;