git.bitcoin.ninja 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::hash_map::RandomState;
  19         pub use std::collections::HashMap;
  20
  21         pub(crate) use std::collections::{hash_map, HashSet};
  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> {
  30                 HashMap::new()
  31         }
  32         /// Builds a new [`HashMap`] with the given capacity.
  33         pub fn hash_map_with_capacity<K, V>(cap: usize) -> HashMap<K, V> {
  34                 HashMap::with_capacity(cap)
  35         }
  36         pub(crate) fn hash_map_from_iter<
  37                 K: core::hash::Hash + Eq,
  38                 V,
  39                 I: IntoIterator<Item = (K, V)>,
  40         >(
  41                 iter: I,
  42         ) -> HashMap<K, V> {
  43                 HashMap::from_iter(iter)
  44         }
  45
  46         pub(crate) fn new_hash_set<K>() -> HashSet<K> {
  47                 HashSet::new()
  48         }
  49         pub(crate) fn hash_set_with_capacity<K>(cap: usize) -> HashSet<K> {
  50                 HashSet::with_capacity(cap)
  51         }
  52         pub(crate) fn hash_set_from_iter<K: core::hash::Hash + Eq, I: IntoIterator<Item = K>>(
  53                 iter: I,
  54         ) -> HashSet<K> {
  55                 HashSet::from_iter(iter)
  56         }
  57 }
  58 #[cfg(not(feature = "hashbrown"))]
  59 pub use std_hashtables::*;
  60
  61 #[cfg(feature = "hashbrown")]
  62 pub(crate) use self::hashbrown::hash_map;
  63
  64 #[cfg(feature = "hashbrown")]
  65 mod hashbrown_tables {
  66         #[cfg(feature = "std")]
  67         mod hasher {
  68                 pub use std::collections::hash_map::RandomState;
  69         }
  70         #[cfg(not(feature = "std"))]
  71         mod hasher {
  72                 #![allow(deprecated)] // hash::SipHasher was deprecated in favor of something only in std.
  73                 use core::hash::{BuildHasher, SipHasher};
  74
  75                 #[derive(Clone, Copy)]
  76                 /// A simple implementation of [`BuildHasher`] that uses `getrandom` to opportunistically
  77                 /// randomize, if the platform supports it.
  78                 pub struct RandomState {
  79                         k0: u64,
  80                         k1: u64,
  81                 }
  82
  83                 impl RandomState {
  84                         /// Constructs a new [`RandomState`] which may or may not be random, depending on the
  85                         /// target platform.
  86                         pub fn new() -> RandomState {
  87                                 let (k0, k1);
  88                                 #[cfg(all(not(fuzzing), feature = "possiblyrandom"))]
  89                                 {
  90                                         let mut keys = [0; 16];
  91                                         possiblyrandom::getpossiblyrandom(&mut keys);
  92
  93                                         let mut k0_bytes = [0; 8];
  94                                         let mut k1_bytes = [0; 8];
  95                                         k0_bytes.copy_from_slice(&keys[..8]);
  96                                         k1_bytes.copy_from_slice(&keys[8..]);
  97                                         k0 = u64::from_le_bytes(k0_bytes);
  98                                         k1 = u64::from_le_bytes(k1_bytes);
  99                                 }
 100                                 #[cfg(any(fuzzing, not(feature = "possiblyrandom")))]
 101                                 {
 102                                         k0 = 0;
 103                                         k1 = 0;
 104                                 }
 105                                 RandomState { k0, k1 }
 106                         }
 107                 }
 108
 109                 impl Default for RandomState {
 110                         fn default() -> RandomState {
 111                                 RandomState::new()
 112                         }
 113                 }
 114
 115                 impl BuildHasher for RandomState {
 116                         type Hasher = SipHasher;
 117                         fn build_hasher(&self) -> SipHasher {
 118                                 SipHasher::new_with_keys(self.k0, self.k1)
 119                         }
 120                 }
 121         }
 122
 123         use super::*;
 124         pub use hasher::*;
 125
 126         /// The HashMap type used in LDK.
 127         pub type HashMap<K, V> = hashbrown::HashMap<K, V, RandomState>;
 128         pub(crate) type HashSet<K> = hashbrown::HashSet<K, RandomState>;
 129
 130         pub(crate) type OccupiedHashMapEntry<'a, K, V> =
 131                 hashbrown::hash_map::OccupiedEntry<'a, K, V, RandomState>;
 132         pub(crate) type VacantHashMapEntry<'a, K, V> =
 133                 hashbrown::hash_map::VacantEntry<'a, K, V, RandomState>;
 134
 135         /// Builds a new [`HashMap`].
 136         pub fn new_hash_map<K, V>() -> HashMap<K, V> {
 137                 HashMap::with_hasher(RandomState::new())
 138         }
 139         /// Builds a new [`HashMap`] with the given capacity.
 140         pub fn hash_map_with_capacity<K, V>(cap: usize) -> HashMap<K, V> {
 141                 HashMap::with_capacity_and_hasher(cap, RandomState::new())
 142         }
 143         pub(crate) fn hash_map_from_iter<
 144                 K: core::hash::Hash + Eq,
 145                 V,
 146                 I: IntoIterator<Item = (K, V)>,
 147         >(
 148                 iter: I,
 149         ) -> HashMap<K, V> {
 150                 let iter = iter.into_iter();
 151                 let min_size = iter.size_hint().0;
 152                 let mut res = HashMap::with_capacity_and_hasher(min_size, RandomState::new());
 153                 res.extend(iter);
 154                 res
 155         }
 156
 157         pub(crate) fn new_hash_set<K>() -> HashSet<K> {
 158                 HashSet::with_hasher(RandomState::new())
 159         }
 160         pub(crate) fn hash_set_with_capacity<K>(cap: usize) -> HashSet<K> {
 161                 HashSet::with_capacity_and_hasher(cap, RandomState::new())
 162         }
 163         pub(crate) fn hash_set_from_iter<K: core::hash::Hash + Eq, I: IntoIterator<Item = K>>(
 164                 iter: I,
 165         ) -> HashSet<K> {
 166                 let iter = iter.into_iter();
 167                 let min_size = iter.size_hint().0;
 168                 let mut res = HashSet::with_capacity_and_hasher(min_size, RandomState::new());
 169                 res.extend(iter);
 170                 res
 171         }
 172 }
 173 #[cfg(feature = "hashbrown")]
 174 pub use hashbrown_tables::*;