]> git.bitcoin.ninja Git - rust-lightning/blob - lightning/src/util/hash_tables.rs
Merge pull request #2845 from wpaulino/decode-htlc-onion-when-committed
[rust-lightning] / 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::*;