1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
use core::iter::Peekable;
use alloc::vec::Vec;
use crate::{
transaction::{Signed, TransactionKind, Transaction},
Block,
};
use super::Usize2;
struct PerSigner<T> {
signer: Option<[u8; 32]>,
/// The sum size of all transactions' sizes.
size: usize,
/// Each transaction and its size.
transactions: Vec<(usize, T)>,
}
impl<T: Transaction> PerSigner<T> {
const EMPTY: Self = Self { signer: None, size: 0, transactions: alloc::vec![] };
/// Pop a transaction from this signer.
///
/// This will not affect the validity of this signer's ordering.
fn pop(&mut self) -> Option<(usize, T)> {
let (transaction_size, transaction) = self.transactions.pop()?;
self.size -= transaction_size;
Some((transaction_size, transaction))
}
fn iter(&self) -> impl Iterator<Item = &T> {
self.transactions.iter().map(|(_transaction_size, transaction)| transaction)
}
fn collect(transactions: &mut Peekable<impl Iterator<Item = T>>) -> Option<Self> {
let signer = |transaction: &T| match transaction.kind() {
TransactionKind::Signed { scope: _, signed: Signed { signer, .. } } => Some(signer),
TransactionKind::Provided { .. } | TransactionKind::Unsigned => None,
};
let target_signer = signer(transactions.peek()?);
let mut result = Self { signer: target_signer, size: 0, transactions: Vec::with_capacity(1) };
let mut full = false;
while let Some(transaction) =
transactions.next_if(|transaction| signer(transaction) == target_signer)
{
// If this signer is full, simply drain the rest of their transactions from this iterator
if full {
continue;
}
/*
Calculate this transaction's size.
If we can't determine this transaction's size, for whatever reason, we skip it.
However, as it may be a required predecessor to a following transaction, we mark this
signer as 'full'.
*/
let Ok(transaction_size) = crate::serialized_len(&transaction) else {
full = true;
continue;
};
// Determine the new size of this signer's transactions
let Some(new_signer_size) = result.size.checked_add(transaction_size) else {
full = true;
continue;
};
result.size = new_signer_size;
result.transactions.push((transaction_size, transaction));
}
Some(result)
}
}
pub(super) struct Transactions<T> {
non_signed: PerSigner<T>,
per_signer: Vec<PerSigner<T>>,
}
impl<T: Transaction> Transactions<T> {
pub(super) const EMPTY: Self = Self { non_signed: PerSigner::EMPTY, per_signer: alloc::vec![] };
/// Instance `Transactions` from an iterator of transactions (presumably from the mempool).
///
/// This assumes the iterator is _sorted_, as necessary for these transactions to be included in
/// a block.
///
/// This function will provide a first pass to attempt to fairly trim transactions if the block's
/// size limit would be violated. However, the result is not guaranteed to fit within the block's
/// size limit.
pub(super) fn from_iter(slashes_size: usize, transactions: impl IntoIterator<Item = T>) -> Self {
let mut transactions = transactions.into_iter().peekable();
/*
Organize the transactions by their signer.
This is correct by the requirement the iterator be sorted, causing each signer's transactions
to be sequential.
*/
let mut per_signer = alloc::vec![];
while let Some(transactions) = PerSigner::collect(&mut transactions) {
per_signer.push(transactions);
}
// Separate out the non-signed transactions
let mut non_signed = if per_signer.first().is_some_and(|per_signer| per_signer.signer.is_none())
{
per_signer.remove(0)
} else {
PerSigner::EMPTY
};
let Some(capacity) = T::BLOCK_SIZE_LIMIT else {
// If there's no block size limit, this does no further work
return Self { non_signed, per_signer };
};
let Some(mut capacity) = capacity
.checked_sub(Block::<T>::EMPTY_BLOCK_SIZE)
.and_then(|capacity| capacity.checked_sub(slashes_size))
else {
// If the size limit is less than a block with just its slashes, truncate all transactions
return Self::EMPTY;
};
// If there's non-signed transactions, ensure they fit within the block's size limit
{
if non_signed.size > capacity {
// If we can't fit all the non-signed transactions, we can't fit any signed transactions
per_signer.clear();
}
while non_signed.size > capacity {
let _ = non_signed.pop();
}
capacity -= non_signed.size;
}
/*
This is guaranteed to not overflow as we're summing at most `u16::MAX` values,
and `usize` is at least `u16`.
*/
let signed_transactions_size = per_signer
.iter()
.map(|per_signer| per_signer.size)
.fold(Usize2::ZERO, |accum, size| accum + size);
if let Some(mut size_to_trim) = signed_transactions_size
.checked_sub(capacity)
.filter(|size_to_trim| *size_to_trim != Usize2::ZERO)
{
let target_size_per_signer = capacity / per_signer.len();
/*
Remove transactions until either:
- This signer only has one transaction left
- This signer's transactions' size are less than the amortized capacity per signer
- All transactions are less than the block's size limit
This does not consider the block header's size, nor the size of the slashes. This isn't
meant to ensure the resulting block is less than the block's size limit, solely to be a
rough first pass which does _most_ of the work in a sufficiently fair manner.
*/
'outer: for per_signer in &mut per_signer {
while (per_signer.transactions.len() > 1) && (per_signer.size > target_size_per_signer) {
let (transaction_size, _transaction) = per_signer.pop().unwrap();
match size_to_trim
.checked_sub(transaction_size)
.filter(|size_to_trim| *size_to_trim != Usize2::ZERO)
{
Some(new_size_to_trim) => size_to_trim = new_size_to_trim,
None => break 'outer,
}
}
}
}
Self { non_signed, per_signer }
}
}
impl<T: Transaction> Transactions<T> {
pub(super) fn iter(&self) -> impl Iterator<Item = &T> {
self.non_signed.iter().chain(self.per_signer.iter().flat_map(PerSigner::iter))
}
/// Pop a transaction.
///
/// This will not affect the validity of the transactions' ordering.
///
/// The value `i` is used to decide _a_ collection to remove from but it is not the index of the
/// collection to remove from. This function will mutate `i` such that on successive calls,
/// the collection removed from is rotated.
pub(super) fn pop(&mut self, i: &mut u16) -> Option<(usize, T)> {
if let Some(signer_to_remove_from) = usize::from(*i).checked_rem(self.per_signer.len()) {
let popped = self.per_signer[signer_to_remove_from]
.pop()
.expect("`per_signer`'s elements are non-empty");
if self.per_signer[signer_to_remove_from].transactions.is_empty() {
self.per_signer.remove(signer_to_remove_from);
} else {
/*
If we removed this signer's collection, this index (once reduced) will inherently point
to the next signer's collection. It's only if we didn't remove this signer's collection
we need to increment the index such that it points to the next signer's collection.
*/
*i = i.wrapping_add(1);
}
Some(popped)
} else {
self.non_signed.pop()
}
}
}