coin_age_priority.cpp raw
1 // Copyright (c) 2012-2017 The Limenka developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4
5 #include <policy/coin_age_priority.h>
6
7 #include <coins.h>
8 #include <common/args.h>
9 #include <consensus/validation.h>
10 #include <node/miner.h>
11 #include <policy/policy.h>
12 #include <primitives/transaction.h>
13 #include <txmempool.h>
14 #include <util/check.h>
15 #include <validation.h>
16
17 using node::BlockAssembler;
18
19 unsigned int CalculateModifiedSize(const CTransaction& tx, unsigned int nTxSize)
20 {
21 // In order to avoid disincentivizing cleaning up the UTXO set we don't count
22 // the constant overhead for each txin and up to 110 bytes of scriptSig (which
23 // is enough to cover a compressed pubkey p2sh redemption) for priority.
24 // Providing any more cleanup incentive than making additional inputs free would
25 // risk encouraging people to create junk outputs to redeem later.
26 Assert(nTxSize > 0);
27 for (std::vector<CTxIn>::const_iterator it(tx.vin.begin()); it != tx.vin.end(); ++it)
28 {
29 unsigned int offset = 41U + std::min(110U, (unsigned int)it->scriptSig.size());
30 if (nTxSize > offset)
31 nTxSize -= offset;
32 }
33 return nTxSize;
34 }
35
36 double ComputePriority2(uint64_t inputs_coin_age, unsigned int mod_vsize)
37 {
38 if (mod_vsize == 0) return 0.0;
39
40 return static_cast<double>(inputs_coin_age) / mod_vsize;
41 }
42
43 double ReversePriority2(const double coin_age_priority, const unsigned int mod_vsize)
44 {
45 return coin_age_priority * mod_vsize;
46 }
47
48 CoinAgeCache GetCoinAge(const CTransaction &tx, const CCoinsViewCache& view, int nHeight)
49 {
50 CoinAgeCache r{COIN_AGE_CACHE_ZERO};
51 if (tx.IsCoinBase()) {
52 return r;
53 }
54 for (const CTxIn& txin : tx.vin)
55 {
56 const Coin& coin = view.AccessCoin(txin.prevout);
57 if (coin.IsSpent()) {
58 continue;
59 }
60 if (coin.nHeight <= nHeight) {
61 r.inputs_coin_age += static_cast<uint64_t>(coin.out.nValue) * static_cast<uint64_t>(nHeight - coin.nHeight);
62 r.in_chain_input_value += coin.out.nValue;
63 }
64 }
65 return r;
66 }
67
68 void CTxMemPoolEntry::UpdateCachedPriority(unsigned int currentHeight, CAmount valueInCurrentBlock)
69 {
70 int heightDiff = int(currentHeight) - int(cachedHeight);
71 double deltaPriority = (static_cast<double>(inChainInputValue) / nModSize) * static_cast<double>(heightDiff);
72 cachedPriority += deltaPriority;
73 cachedHeight = currentHeight;
74 inChainInputValue += valueInCurrentBlock;
75 assert(MoneyRange(inChainInputValue));
76 }
77
78 struct update_priority
79 {
80 update_priority(unsigned int _height, CAmount _value) :
81 height(_height), value(_value)
82 {}
83
84 void operator() (CTxMemPoolEntry &e)
85 { e.UpdateCachedPriority(height, value); }
86
87 private:
88 unsigned int height;
89 CAmount value;
90 };
91
92 void CTxMemPool::UpdateDependentPriorities(const CTransaction &tx, unsigned int nBlockHeight, bool addToChain)
93 {
94 LOCK(cs);
95 for (unsigned int i = 0; i < tx.vout.size(); i++) {
96 auto it = mapNextTx.find(COutPoint(tx.GetHash(), i));
97 if (it == mapNextTx.end())
98 continue;
99 uint256 hash = it->second->GetHash();
100 txiter iter = mapTx.find(hash);
101 mapTx.modify(iter, update_priority(nBlockHeight, addToChain ? tx.vout[i].nValue : -tx.vout[i].nValue));
102 }
103 }
104
105 double
106 CTxMemPoolEntry::GetPriority(unsigned int currentHeight) const
107 {
108 // This will only return accurate results when the difference between
109 // cachedHeight and currentHeight does not cross any blocks where the
110 // inputs of the tx are included.
111 // Typical usage of GetPriority with chainActive.Height() will ensure this,
112 // but it's possible that a reorg leaves unaffected mempool entries with a
113 // higher cachedHeight if and only if the below math is safe.
114 int heightDiff = int(currentHeight) - int(cachedHeight);
115 double deltaPriority = (static_cast<double>(inChainInputValue) / nModSize) * static_cast<double>(heightDiff);
116 double dResult = cachedPriority + deltaPriority;
117 if (dResult < 0) { // Small floating point rounding can potentially add up
118 dResult = 0;
119 }
120 return dResult;
121 }
122
123 #ifndef BUILDING_FOR_LIBLIMENKAKERNEL
124 // We want to sort transactions by coin age priority
125 typedef std::pair<double, CTxMemPool::txiter> TxCoinAgePriority;
126
127 struct TxCoinAgePriorityCompare
128 {
129 bool operator()(const TxCoinAgePriority& a, const TxCoinAgePriority& b)
130 {
131 if (a.first == b.first)
132 return CompareTxMemPoolEntryByScore()(*(b.second), *(a.second)); //Reverse order to make sort less than
133 return a.first < b.first;
134 }
135 };
136
137 bool BlockAssembler::isStillDependent(const CTxMemPool& mempool, CTxMemPool::txiter iter)
138 {
139 assert(iter != mempool.mapTx.end());
140 for (const auto& parent : iter->GetMemPoolParentsConst()) {
141 auto parent_it = mempool.mapTx.iterator_to(parent);
142 if (!inBlock.count(parent_it)) {
143 return true;
144 }
145 }
146 return false;
147 }
148
149 bool BlockAssembler::TestForBlock(CTxMemPool::txiter iter)
150 {
151 uint64_t packageSize = iter->GetSizeWithAncestors();
152 int64_t packageSigOps = iter->GetSigOpCostWithAncestors();
153 if (!TestPackage(packageSize, packageSigOps)) {
154 // If the block is so close to full that no more txs will fit
155 // or if we've tried more than 50 times to fill remaining space
156 // then flag that the block is finished
157 if (nBlockWeight > m_options.nBlockMaxWeight - 400 || nBlockSigOpsCost > MAX_BLOCK_SIGOPS_COST - 8 || lastFewTxs > 50) {
158 blockFinished = true;
159 return false;
160 }
161 // Once we're within 4000 weight of a full block, only look at 50 more txs
162 // to try to fill the remaining space.
163 if (nBlockWeight > m_options.nBlockMaxWeight - 4000) {
164 ++lastFewTxs;
165 }
166 return false;
167 }
168
169 CTxMemPool::setEntries package;
170 package.insert(iter);
171 if (!TestPackageTransactions(package)) {
172 if (nBlockSize > m_options.nBlockMaxSize - 100 || lastFewTxs > 50) {
173 blockFinished = true;
174 return false;
175 }
176 if (nBlockSize > m_options.nBlockMaxSize - 1000) {
177 ++lastFewTxs;
178 }
179 return false;
180 }
181
182 return true;
183 }
184
185 void BlockAssembler::addPriorityTxs(const CTxMemPool& mempool, int &nPackagesSelected)
186 {
187 AssertLockHeld(mempool.cs);
188
189 // How much of the block should be dedicated to high-priority transactions,
190 // included regardless of the fees they pay
191 uint64_t nBlockPrioritySize = gArgs.GetIntArg("-blockprioritysize", DEFAULT_BLOCK_PRIORITY_SIZE);
192 if (m_options.nBlockMaxSize < nBlockPrioritySize) {
193 nBlockPrioritySize = m_options.nBlockMaxSize;
194 }
195
196 if (nBlockPrioritySize <= 0) {
197 return;
198 }
199
200 bool fSizeAccounting = fNeedSizeAccounting;
201 fNeedSizeAccounting = true;
202
203 // This vector will be sorted into a priority queue:
204 std::vector<TxCoinAgePriority> vecPriority;
205 TxCoinAgePriorityCompare pricomparer;
206 std::map<CTxMemPool::txiter, double, CompareIteratorByHash> waitPriMap;
207 typedef std::map<CTxMemPool::txiter, double, CompareIteratorByHash>::iterator waitPriIter;
208 double actualPriority = -1;
209
210 vecPriority.reserve(mempool.mapTx.size());
211 for (auto mi = mempool.mapTx.begin(); mi != mempool.mapTx.end(); ++mi) {
212 double dPriority = mi->GetPriority(nHeight);
213 CAmount dummy;
214 mempool.ApplyDeltas(mi->GetTx().GetHash(), dPriority, dummy);
215 vecPriority.emplace_back(dPriority, mi);
216 }
217 std::make_heap(vecPriority.begin(), vecPriority.end(), pricomparer);
218
219 CTxMemPool::txiter iter;
220 while (!vecPriority.empty() && !blockFinished) { // add a tx from priority queue to fill the blockprioritysize
221 iter = vecPriority.front().second;
222 actualPriority = vecPriority.front().first;
223 std::pop_heap(vecPriority.begin(), vecPriority.end(), pricomparer);
224 vecPriority.pop_back();
225
226 // If tx already in block, skip
227 if (inBlock.count(iter)) {
228 assert(false); // shouldn't happen for priority txs
229 continue;
230 }
231
232 // If tx is dependent on other mempool txs which haven't yet been included
233 // then put it in the waitSet
234 if (isStillDependent(mempool, iter)) {
235 waitPriMap.insert(std::make_pair(iter, actualPriority));
236 continue;
237 }
238
239 // If this tx fits in the block add it, otherwise keep looping
240 if (TestForBlock(iter)) {
241 AddToBlock(mempool, iter);
242
243 ++nPackagesSelected;
244
245 // If now that this txs is added we've surpassed our desired priority size
246 // or have dropped below the minimum priority threshold, then we're done adding priority txs
247 if (nBlockSize >= nBlockPrioritySize || actualPriority <= MINIMUM_TX_PRIORITY) {
248 break;
249 }
250
251 // This tx was successfully added, so
252 // add transactions that depend on this one to the priority queue to try again
253 for (const auto& child : iter->GetMemPoolChildrenConst())
254 {
255 auto child_it = mempool.mapTx.iterator_to(child);
256 waitPriIter wpiter = waitPriMap.find(child_it);
257 if (wpiter != waitPriMap.end()) {
258 vecPriority.emplace_back(wpiter->second, child_it);
259 std::push_heap(vecPriority.begin(), vecPriority.end(), pricomparer);
260 waitPriMap.erase(wpiter);
261 }
262 }
263 }
264 }
265 fNeedSizeAccounting = fSizeAccounting;
266 }
267 #endif
268