diff options
43 files changed, 1224 insertions, 317 deletions
@@ -1,3 +1,5 @@ +The MIT License (MIT) + Copyright (c) 2009-2015 The Bitcoin Core developers Permission is hereby granted, free of charge, to any person obtaining a copy diff --git a/contrib/debian/copyright b/contrib/debian/copyright index 55ebcaab42..d119bbd1d0 100644 --- a/contrib/debian/copyright +++ b/contrib/debian/copyright @@ -5,15 +5,11 @@ Upstream-Contact: Satoshi Nakamoto <satoshin@gmx.com> Source: https://github.com/bitcoin/bitcoin Files: * -Copyright: 2009-2012, Bitcoin Core Developers -License: Expat +Copyright: 2009-2015, Bitcoin Core Developers +License: MIT/Expat Comment: The Bitcoin Core Developers encompasses the current developers listed on bitcoin.org, as well as the numerous contributors to the project. -Files: src/json/* -Copyright: 2007-2009, John W. Wilkinson -License: Expat - Files: debian/* Copyright: 2010-2011, Jonas Smedegaard <dr@jones.dk> 2011, Matt Corallo <matt@bluematt.me> @@ -23,62 +19,68 @@ Files: debian/manpages/* Copyright: Micah Anderson <micah@debian.org> License: GPL-3+ -Files: src/qt/res/icons/clock*.png, src/qt/res/icons/tx*.png, - src/qt/res/src/*.svg -Copyright: Wladimir van der Laan -License: Expat - -Files: src/qt/res/icons/address-book.png, src/qt/res/icons/export.png, - src/qt/res/icons/history.png, src/qt/res/icons/key.png, - src/qt/res/icons/lock_*.png, src/qt/res/icons/overview.png, - src/qt/res/icons/receive.png, src/qt/res/icons/send.png, - src/qt/res/icons/synced.png, src/qt/res/icons/filesave.png -Copyright: David Vignoni (david@icon-king.com) - ICON KING - www.icon-king.com -License: LGPL -Comment: NUVOLA ICON THEME for KDE 3.x - Original icons: kaddressbook, klipper_dock, view-list-text, - key-password, encrypted/decrypted, go-home, go-down, - go-next, dialog-ok - Site: http://www.icon-king.com/projects/nuvola/ +Files: src/qt/res/icons/add.png, + src/qt/res/icons/address-book.png, + src/qt/res/icons/configure.png, + src/qt/res/icons/debugwindow.png, + src/qt/res/icons/edit.png, + src/qt/res/icons/editcopy.png, + src/qt/res/icons/editpaste.png, + src/qt/res/icons/export.png, + src/qt/res/icons/eye.png, + src/qt/res/icons/filesave.png, + src/qt/res/icons/history.png, + src/qt/res/icons/info.png, + src/qt/res/icons/key.png, + src/qt/res/icons/lock_*.png, + src/qt/res/icons/open.png, + src/qt/res/icons/overview.png, + src/qt/res/icons/quit.png, + src/qt/res/icons/receive.png, + src/qt/res/icons/remove.png, + src/qt/res/icons/send.png, + src/qt/res/icons/synced.png, + src/qt/res/icons/transaction*.png, + src/qt/res/icons/tx_output.png, + src/qt/res/icons/warning.png +Copyright: Stephen Hutchings (and more) + http://typicons.com +License: MIT/Expat +Comment: Site: https://github.com/stephenhutchings/typicons.font Files: src/qt/res/icons/connect*.png -Copyright: schollidesign -License: GPL-3+ -Comment: Icon Pack: Human-O2 - Site: http://findicons.com/icon/93743/blocks_gnome_netstatus_0 - -Files: src/qt/res/icons/transaction*.png -Copyright: md2k7 -License: Expat -Comment: Site: https://bitcointalk.org/index.php?topic=15276.0 - -Files: src/qt/res/icons/configure.png, src/qt/res/icons/quit.png, - src/qt/res/icons/editcopy.png, src/qt/res/icons/editpaste.png, - src/qt/res/icons/add.png, src/qt/res/icons/edit.png, - src/qt/res/icons/remove.png -Copyright: http://www.everaldo.com -License: LGPL -Comment: Icon Pack: Crystal SVG + src/qt/res/src/connect-*.svg +Copyright: Marco Falke +License: MIT/Expat +Comment: Inspired by Stephan Hutchings Typicons + +Files: src/qt/res/icons/tx_mined.png + src/qt/res/src/mine.svg +Copyright: Jonas Schnelli +License: MIT/Expat +Comment: -Files: src/qt/res/icons/bitcoin.png, src/qt/res/icons/toolbar.png -Copyright: Bitboy (optimized for 16x16 by Wladimir van der Laan) +Files: src/qt/res/icons/clock*.png + src/qt/res/icons/eye_*.png + src/qt/res/icons/verify.png + src/qt/res/icons/tx_in*.png + src/qt/res/src/clock_*.svg + src/qt/res/src/tx_*.svg + src/qt/res/src/verify.svg +Copyright: Stephan Hutching, Jonas Schnelli +License: MIT/Expat +Comment: Modifications of Stephan Hutchings Typicons + +Files: src/qt/res/icons/about.png + src/qt/res/icons/bitcoin.* + share/pixmaps/bitcoin* + src/qt/res/src/bitcoin.svg +Copyright: Bitboy, Jonas Schnelli License: PUB-DOM Comment: Site: https://bitcointalk.org/?topic=1756.0 -Files: scripts/img/reload.xcf, src/qt/res/movies/*.png -Copyright: Everaldo (Everaldo Coelho) -License: GPL-3+ -Comment: Icon Pack: Kids - Site: http://findicons.com/icon/17102/reload?id=17102 - -Files: src/qt/res/images/splash2.jpg -License: PUB-DOM -Copyright: Crobbo (forum) -Comment: Site: https://bitcointalk.org/index.php?topic=32273.0 - -License: Expat +License: MIT/Expat Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including @@ -98,20 +100,6 @@ License: Expat TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. -License: ISC - Permission to use, copy, modify, and distribute this software for any - purpose with or without fee is hereby granted, provided that the above - copyright notice and this permission notice appear in all copies. - . - THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL - WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED - WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR - BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES - OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, - WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, - ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS - SOFTWARE. - License: GPL-2+ This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the @@ -140,22 +128,5 @@ Comment: You should have received a copy of the GNU General Public License along with this program. If not, see <http://www.gnu.org/licenses/>. -License: LGPL - This program is free software: you can redistribute it and/or modify - it under the terms of the GNU General Public License as published by - the Free Software Foundation, either version 3 of the License, or - (at your option) any later version. - . - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. -Comment: - On Debian systems the GNU Lesser General Public License (LGPL) is - located in '/usr/share/common-licenses/LGPL'. - . - You should have received a copy of the GNU General Public License - along with this program. If not, see <http://www.gnu.org/licenses/>. - License: PUB-DOM This work is in the public domain. diff --git a/contrib/debian/examples/bitcoin.conf b/contrib/debian/examples/bitcoin.conf index 62ffd7123a..2831c07292 100644 --- a/contrib/debian/examples/bitcoin.conf +++ b/contrib/debian/examples/bitcoin.conf @@ -60,7 +60,7 @@ # JSON-RPC options (for controlling a running Bitcoin/bitcoind process) # -# server=1 tells Bitcoin-QT and bitcoind to accept JSON-RPC commands +# server=1 tells Bitcoin-Qt and bitcoind to accept JSON-RPC commands #server=0 # Bind to given address to listen for JSON-RPC connections. Use [host]:port notation for IPv6. @@ -73,7 +73,7 @@ # How many seconds bitcoin will wait for a complete RPC HTTP request. # after the HTTP connection is established. -#rpctimeout=30 +#rpcclienttimeout=30 # By default, only RPC connections from localhost are allowed. # Specify as many rpcallowip= settings as you like to allow connections from other hosts, @@ -82,7 +82,7 @@ # NOTE: opening up the RPC port to hosts outside your local trusted network is NOT RECOMMENDED, # because the rpcpassword is transmitted over the network unencrypted. -# server=1 tells Bitcoin-QT to accept JSON-RPC commands. +# server=1 tells Bitcoin-Qt to accept JSON-RPC commands. # it is also read by bitcoind to determine if RPC should be enabled #rpcallowip=10.1.1.34/255.255.255.0 #rpcallowip=1.2.3.4/24 diff --git a/contrib/devtools/github-merge.sh b/contrib/devtools/github-merge.sh index ec7a1f4c4b..afb53f0390 100755 --- a/contrib/devtools/github-merge.sh +++ b/contrib/devtools/github-merge.sh @@ -161,7 +161,11 @@ if [[ "d$REPLY" =~ ^d[Ss]$ ]]; then cleanup exit 1 else - git commit -q --gpg-sign --amend --no-edit + if ! git commit -q --gpg-sign --amend --no-edit; then + echo "Error signing, exiting." + cleanup + exit 1 + fi fi else echo "Not signing off on merge, exiting." diff --git a/contrib/verify-commits/trusted-git-root b/contrib/verify-commits/trusted-git-root index eb13f8762e..838b8d1ea8 100644 --- a/contrib/verify-commits/trusted-git-root +++ b/contrib/verify-commits/trusted-git-root @@ -1 +1 @@ -053038e5ba116cb319fb85f3cb3e062cf1b3df15 +165e323d851cc87213c7673c6f278e87a6f2e752 diff --git a/doc/assets-attribution.md b/doc/assets-attribution.md index 460c1f8e2e..2dd930d6a4 100644 --- a/doc/assets-attribution.md +++ b/doc/assets-attribution.md @@ -1,70 +1 @@ -The following is a list of assets used in the bitcoin source and their proper attribution. - -[Typicons/Stephen Hutchings](http://typicons.com) ------------------------ - -### Info -* Icon Pack: Typicons (http://typicons.com) -* Designer: Stephen Hutchings (and more) -* License: MIT -* Site: [https://github.com/stephenhutchings/typicons.font](https://github.com/stephenhutchings/typicons.font) - -### Assets Used - src/qt/res/icons/add.png - src/qt/res/icons/address-book.png - src/qt/res/icons/configure.png - src/qt/res/icons/debugwindow.png - src/qt/res/icons/edit.png - src/qt/res/icons/editcopy.png - src/qt/res/icons/editpaste.png - src/qt/res/icons/export.png - src/qt/res/icons/eye.png - src/qt/res/icons/filesave.png - src/qt/res/icons/history.png - src/qt/res/icons/info.png - src/qt/res/icons/key.png - src/qt/res/icons/lock_*.png - src/qt/res/icons/open.png - src/qt/res/icons/overview.png - src/qt/res/icons/quit.png - src/qt/res/icons/receive.png - src/qt/res/icons/remove.png - src/qt/res/icons/send.png - src/qt/res/icons/synced.png - src/qt/res/icons/transaction*.png - src/qt/res/icons/tx_output.png - src/qt/res/icons/warning.png - -Other ------------------------ - -### Info -* Designer: Jonas Schnelli, Bitboy, Stephen Hutchings, Marco Falke -* Bitcoin icon: Based on the original bitcoin logo from Bitboy -* Network connection icons: Marco Falke, inspired by flow-merge.svg from Stephen Hutchings -* Transaction-mined icon: Jonas Schnelli -* Other icons are based on Stephan Hutchings Typicons -* License: MIT - -### Assets Used - src/qt/res/icons/about.png - src/qt/res/icons/about_qt.png - src/qt/res/icons/bitcoin.icns - src/qt/res/icons/bitcoin.ico - src/qt/res/icons/bitcoin.png - src/qt/res/icons/clock*.png - src/qt/res/icons/connect*.png - src/qt/res/icons/eye_minus.png - src/qt/res/icons/eye_plus.png - src/qt/res/icons/verify.png - src/qt/res/icons/tx_inout.png - src/qt/res/icons/tx_input.png - src/qt/res/icons/tx_mined.png - src/qt/res/src/bitcoin.svg - src/qt/res/src/clock_*.svg - src/qt/res/src/connect-*.svg - src/qt/res/src/mine.svg - src/qt/res/src/qt.svg - src/qt/res/src/tx_*.svg - src/qt/res/src/transaction0.svg - src/qt/res/src/verify.svg +The list of assets used in the bitcoin source and their attribution can now be found in [contrib/debian/copyright](../contrib/debian/copyright). diff --git a/doc/release-notes/release-notes-0.10.1.md b/doc/release-notes/release-notes-0.10.1.md index 5e939600a0..8f59f1f68c 100644 --- a/doc/release-notes/release-notes-0.10.1.md +++ b/doc/release-notes/release-notes-0.10.1.md @@ -101,7 +101,7 @@ Tests: Miscellaneous: - `c9e022b` Initialization: set Boost path locale in main thread - `23126a0` Sanitize command strings before logging them. -- `323de27` Initialization: setup environment before starting QT tests +- `323de27` Initialization: setup environment before starting Qt tests - `7494e09` Initialization: setup environment before starting tests - `df45564` Initialization: set fallback locale as environment variable diff --git a/qa/pull-tester/rpc-tests.sh b/qa/pull-tester/rpc-tests.sh index b97d97b553..2e8a7c69ce 100755 --- a/qa/pull-tester/rpc-tests.sh +++ b/qa/pull-tester/rpc-tests.sh @@ -57,6 +57,7 @@ testScriptsExt=( 'invalidblockrequest.py' # 'forknotify.py' 'p2p-acceptblock.py' + 'mempool_packages.py' ); #if [ "x$ENABLE_ZMQ" = "x1" ]; then diff --git a/qa/rpc-tests/mempool_packages.py b/qa/rpc-tests/mempool_packages.py new file mode 100755 index 0000000000..6041f3a3dd --- /dev/null +++ b/qa/rpc-tests/mempool_packages.py @@ -0,0 +1,107 @@ +#!/usr/bin/env python2 +# Copyright (c) 2014-2015 The Bitcoin Core developers +# Distributed under the MIT software license, see the accompanying +# file COPYING or http://www.opensource.org/licenses/mit-license.php. + +# Test descendant package tracking code + +from test_framework.test_framework import BitcoinTestFramework +from test_framework.util import * + +def satoshi_round(amount): + return Decimal(amount).quantize(Decimal('0.00000001'), rounding=ROUND_DOWN) + +class MempoolPackagesTest(BitcoinTestFramework): + + def setup_network(self): + self.nodes = [] + self.nodes.append(start_node(0, self.options.tmpdir, ["-maxorphantx=1000", "-relaypriority=0"])) + self.is_network_split = False + self.sync_all() + + # Build a transaction that spends parent_txid:vout + # Return amount sent + def chain_transaction(self, parent_txid, vout, value, fee, num_outputs): + send_value = satoshi_round((value - fee)/num_outputs) + inputs = [ {'txid' : parent_txid, 'vout' : vout} ] + outputs = {} + for i in xrange(num_outputs): + outputs[self.nodes[0].getnewaddress()] = send_value + rawtx = self.nodes[0].createrawtransaction(inputs, outputs) + signedtx = self.nodes[0].signrawtransaction(rawtx) + txid = self.nodes[0].sendrawtransaction(signedtx['hex']) + fulltx = self.nodes[0].getrawtransaction(txid, 1) + assert(len(fulltx['vout']) == num_outputs) # make sure we didn't generate a change output + return (txid, send_value) + + def run_test(self): + ''' Mine some blocks and have them mature. ''' + self.nodes[0].generate(101) + utxo = self.nodes[0].listunspent(10) + txid = utxo[0]['txid'] + vout = utxo[0]['vout'] + value = utxo[0]['amount'] + + fee = Decimal("0.0001") + # 100 transactions off a confirmed tx should be fine + chain = [] + for i in xrange(100): + (txid, sent_value) = self.chain_transaction(txid, 0, value, fee, 1) + value = sent_value + chain.append(txid) + + # Check mempool has 100 transactions in it, and descendant + # count and fees should look correct + mempool = self.nodes[0].getrawmempool(True) + assert_equal(len(mempool), 100) + descendant_count = 1 + descendant_fees = 0 + descendant_size = 0 + SATOSHIS = 100000000 + + for x in reversed(chain): + assert_equal(mempool[x]['descendantcount'], descendant_count) + descendant_fees += mempool[x]['fee'] + assert_equal(mempool[x]['descendantfees'], SATOSHIS*descendant_fees) + descendant_size += mempool[x]['size'] + assert_equal(mempool[x]['descendantsize'], descendant_size) + descendant_count += 1 + + # Adding one more transaction on to the chain should fail. + try: + self.chain_transaction(txid, vout, value, fee, 1) + except JSONRPCException as e: + print "too-long-ancestor-chain successfully rejected" + + # TODO: test ancestor size limits + + # Now test descendant chain limits + txid = utxo[1]['txid'] + value = utxo[1]['amount'] + vout = utxo[1]['vout'] + + transaction_package = [] + # First create one parent tx with 10 children + (txid, sent_value) = self.chain_transaction(txid, vout, value, fee, 10) + parent_transaction = txid + for i in xrange(10): + transaction_package.append({'txid': txid, 'vout': i, 'amount': sent_value}) + + for i in xrange(1000): + utxo = transaction_package.pop(0) + try: + (txid, sent_value) = self.chain_transaction(utxo['txid'], utxo['vout'], utxo['amount'], fee, 10) + for j in xrange(10): + transaction_package.append({'txid': txid, 'vout': j, 'amount': sent_value}) + if i == 998: + mempool = self.nodes[0].getrawmempool(True) + assert_equal(mempool[parent_transaction]['descendantcount'], 1000) + except JSONRPCException as e: + print e.error['message'] + assert_equal(i, 999) + print "tx that would create too large descendant package successfully rejected" + + # TODO: test descendant size limits + +if __name__ == '__main__': + MempoolPackagesTest().main() diff --git a/qa/rpc-tests/test_framework/authproxy.py b/qa/rpc-tests/test_framework/authproxy.py index bc7d655fdf..33014dc139 100644 --- a/qa/rpc-tests/test_framework/authproxy.py +++ b/qa/rpc-tests/test_framework/authproxy.py @@ -106,6 +106,26 @@ class AuthServiceProxy(object): name = "%s.%s" % (self.__service_name, name) return AuthServiceProxy(self.__service_url, name, connection=self.__conn) + def _request(self, method, path, postdata): + ''' + Do a HTTP request, with retry if we get disconnected (e.g. due to a timeout). + This is a workaround for https://bugs.python.org/issue3566 which is fixed in Python 3.5. + ''' + headers = {'Host': self.__url.hostname, + 'User-Agent': USER_AGENT, + 'Authorization': self.__auth_header, + 'Content-type': 'application/json'} + try: + self.__conn.request(method, path, postdata, headers) + return self._get_response() + except httplib.BadStatusLine as e: + if e.line == "''": # if connection was closed, try again + self.__conn.close() + self.__conn.request(method, path, postdata, headers) + return self._get_response() + else: + raise + def __call__(self, *args): AuthServiceProxy.__id_count += 1 @@ -115,13 +135,7 @@ class AuthServiceProxy(object): 'method': self.__service_name, 'params': args, 'id': AuthServiceProxy.__id_count}, default=EncodeDecimal) - self.__conn.request('POST', self.__url.path, postdata, - {'Host': self.__url.hostname, - 'User-Agent': USER_AGENT, - 'Authorization': self.__auth_header, - 'Content-type': 'application/json'}) - - response = self._get_response() + response = self._request('POST', self.__url.path, postdata) if response['error'] is not None: raise JSONRPCException(response['error']) elif 'result' not in response: @@ -133,13 +147,7 @@ class AuthServiceProxy(object): def _batch(self, rpc_call_list): postdata = json.dumps(list(rpc_call_list), default=EncodeDecimal) log.debug("--> "+postdata) - self.__conn.request('POST', self.__url.path, postdata, - {'Host': self.__url.hostname, - 'User-Agent': USER_AGENT, - 'Authorization': self.__auth_header, - 'Content-type': 'application/json'}) - - return self._get_response() + return self._request('POST', self.__url.path, postdata) def _get_response(self): http_response = self.__conn.getresponse() diff --git a/share/pixmaps/addressbook16.bmp b/share/pixmaps/addressbook16.bmp Binary files differdeleted file mode 100644 index c5576910b1..0000000000 --- a/share/pixmaps/addressbook16.bmp +++ /dev/null diff --git a/share/pixmaps/addressbook16mask.bmp b/share/pixmaps/addressbook16mask.bmp Binary files differdeleted file mode 100644 index d3a478d1ad..0000000000 --- a/share/pixmaps/addressbook16mask.bmp +++ /dev/null diff --git a/share/pixmaps/addressbook20.bmp b/share/pixmaps/addressbook20.bmp Binary files differdeleted file mode 100644 index 2b33b228aa..0000000000 --- a/share/pixmaps/addressbook20.bmp +++ /dev/null diff --git a/share/pixmaps/addressbook20mask.bmp b/share/pixmaps/addressbook20mask.bmp Binary files differdeleted file mode 100644 index 56ce6125db..0000000000 --- a/share/pixmaps/addressbook20mask.bmp +++ /dev/null diff --git a/share/pixmaps/bitcoin-bc.ico b/share/pixmaps/bitcoin-bc.ico Binary files differdeleted file mode 100644 index 88cc240e2d..0000000000 --- a/share/pixmaps/bitcoin-bc.ico +++ /dev/null diff --git a/share/pixmaps/check.ico b/share/pixmaps/check.ico Binary files differdeleted file mode 100644 index 0c4e6e8147..0000000000 --- a/share/pixmaps/check.ico +++ /dev/null diff --git a/share/pixmaps/favicon.ico b/share/pixmaps/favicon.ico Binary files differdeleted file mode 100644 index 754eebc488..0000000000 --- a/share/pixmaps/favicon.ico +++ /dev/null diff --git a/share/pixmaps/send16.bmp b/share/pixmaps/send16.bmp Binary files differdeleted file mode 100644 index 676b5c4b49..0000000000 --- a/share/pixmaps/send16.bmp +++ /dev/null diff --git a/share/pixmaps/send16mask.bmp b/share/pixmaps/send16mask.bmp Binary files differdeleted file mode 100644 index 06c747f934..0000000000 --- a/share/pixmaps/send16mask.bmp +++ /dev/null diff --git a/share/pixmaps/send16masknoshadow.bmp b/share/pixmaps/send16masknoshadow.bmp Binary files differdeleted file mode 100644 index faf24e0d8a..0000000000 --- a/share/pixmaps/send16masknoshadow.bmp +++ /dev/null diff --git a/share/pixmaps/send20.bmp b/share/pixmaps/send20.bmp Binary files differdeleted file mode 100644 index 2b90422b38..0000000000 --- a/share/pixmaps/send20.bmp +++ /dev/null diff --git a/share/pixmaps/send20mask.bmp b/share/pixmaps/send20mask.bmp Binary files differdeleted file mode 100644 index f124d0da08..0000000000 --- a/share/pixmaps/send20mask.bmp +++ /dev/null diff --git a/share/qt/img/reload.png b/share/qt/img/reload.png Binary files differdeleted file mode 100644 index 9068db9a63..0000000000 --- a/share/qt/img/reload.png +++ /dev/null diff --git a/share/qt/img/reload.xcf b/share/qt/img/reload.xcf Binary files differdeleted file mode 100644 index dc8be62831..0000000000 --- a/share/qt/img/reload.xcf +++ /dev/null diff --git a/share/qt/make_spinner.py b/share/qt/make_spinner.py deleted file mode 100755 index bb19e91508..0000000000 --- a/share/qt/make_spinner.py +++ /dev/null @@ -1,38 +0,0 @@ -#!/usr/bin/env python -# W.J. van der Laan, 2011 -# Make spinning animation from a .png -# Requires imagemagick 6.7+ -from __future__ import division -from os import path -from PIL import Image -from subprocess import Popen - -SRC='img/reload.png' -TMPDIR='../../src/qt/res/movies/' -TMPNAME='spinner-%03i.png' -NUMFRAMES=35 -FRAMERATE=10.0 -CONVERT='convert' -CLOCKWISE=True -DSIZE=(16,16) - -im_src = Image.open(SRC) - -if CLOCKWISE: - im_src = im_src.transpose(Image.FLIP_LEFT_RIGHT) - -def frame_to_filename(frame): - return path.join(TMPDIR, TMPNAME % frame) - -frame_files = [] -for frame in xrange(NUMFRAMES): - rotation = (frame + 0.5) / NUMFRAMES * 360.0 - if CLOCKWISE: - rotation = -rotation - im_new = im_src.rotate(rotation, Image.BICUBIC) - im_new.thumbnail(DSIZE, Image.ANTIALIAS) - outfile = frame_to_filename(frame) - im_new.save(outfile, 'png') - frame_files.append(outfile) - - diff --git a/share/ui.rc b/share/ui.rc deleted file mode 100644 index 063641cba2..0000000000 --- a/share/ui.rc +++ /dev/null @@ -1,15 +0,0 @@ -bitcoin ICON "pixmaps/bitcoin.ico"
-
-#include "wx/msw/wx.rc"
-
-check ICON "pixmaps/check.ico"
-send16 BITMAP "pixmaps/send16.bmp"
-send16mask BITMAP "pixmaps/send16mask.bmp"
-send16masknoshadow BITMAP "pixmaps/send16masknoshadow.bmp"
-send20 BITMAP "pixmaps/send20.bmp"
-send20mask BITMAP "pixmaps/send20mask.bmp"
-addressbook16 BITMAP "pixmaps/addressbook16.bmp"
-addressbook16mask BITMAP "pixmaps/addressbook16mask.bmp"
-addressbook20 BITMAP "pixmaps/addressbook20.bmp"
-addressbook20mask BITMAP "pixmaps/addressbook20mask.bmp"
-favicon ICON "pixmaps/favicon.ico"
diff --git a/src/bitcoin-cli.cpp b/src/bitcoin-cli.cpp index 866c6f2d44..7839b3b6b4 100644 --- a/src/bitcoin-cli.cpp +++ b/src/bitcoin-cli.cpp @@ -22,6 +22,8 @@ using namespace std; +static const int DEFAULT_HTTP_CLIENT_TIMEOUT=900; + std::string HelpMessageCli() { string strUsage; @@ -37,6 +39,7 @@ std::string HelpMessageCli() strUsage += HelpMessageOpt("-rpcwait", _("Wait for RPC server to start")); strUsage += HelpMessageOpt("-rpcuser=<user>", _("Username for JSON-RPC connections")); strUsage += HelpMessageOpt("-rpcpassword=<pw>", _("Password for JSON-RPC connections")); + strUsage += HelpMessageOpt("-rpcclienttimeout=<n>", strprintf(_("Timeout during HTTP requests (default: %d)"), DEFAULT_HTTP_CLIENT_TIMEOUT)); return strUsage; } @@ -150,7 +153,7 @@ UniValue CallRPC(const string& strMethod, const UniValue& params) struct evhttp_connection *evcon = evhttp_connection_base_new(base, NULL, host.c_str(), port); // TODO RAII if (evcon == NULL) throw runtime_error("create connection failed"); - evhttp_connection_set_timeout(evcon, GetArg("-rpctimeout", 30)); + evhttp_connection_set_timeout(evcon, GetArg("-rpcclienttimeout", DEFAULT_HTTP_CLIENT_TIMEOUT)); HTTPReply response; struct evhttp_request *req = evhttp_request_new(http_request_done, (void*)&response); // TODO RAII diff --git a/src/httpserver.cpp b/src/httpserver.cpp index baca007571..600e57b7cc 100644 --- a/src/httpserver.cpp +++ b/src/httpserver.cpp @@ -320,6 +320,15 @@ static void HTTPWorkQueueRun(WorkQueue<HTTPClosure>* queue) queue->Run(); } +/** libevent event log callback */ +static void libevent_log_cb(int severity, const char *msg) +{ + if (severity >= EVENT_LOG_WARN) // Log warn messages and higher without debug category + LogPrintf("libevent: %s\n", msg); + else + LogPrint("libevent", "libevent: %s\n", msg); +} + bool InitHTTPServer() { struct evhttp* http = 0; @@ -335,6 +344,16 @@ bool InitHTTPServer() return false; } + // Redirect libevent's logging to our own log + event_set_log_callback(&libevent_log_cb); +#if LIBEVENT_VERSION_NUMBER >= 0x02010100 + // If -debug=libevent, set full libevent debugging. + // Otherwise, disable all libevent debugging. + if (LogAcceptCategory("libevent")) + event_enable_debug_logging(EVENT_DBG_ALL); + else + event_enable_debug_logging(EVENT_DBG_NONE); +#endif #ifdef WIN32 evthread_use_windows_threads(); #else @@ -355,7 +374,7 @@ bool InitHTTPServer() return false; } - evhttp_set_timeout(http, GetArg("-rpctimeout", DEFAULT_HTTP_TIMEOUT)); + evhttp_set_timeout(http, GetArg("-rpcservertimeout", DEFAULT_HTTP_SERVER_TIMEOUT)); evhttp_set_max_body_size(http, MAX_SIZE); evhttp_set_gencb(http, http_request_cb, NULL); diff --git a/src/httpserver.h b/src/httpserver.h index 459c60c047..b377dc19fc 100644 --- a/src/httpserver.h +++ b/src/httpserver.h @@ -13,7 +13,7 @@ static const int DEFAULT_HTTP_THREADS=4; static const int DEFAULT_HTTP_WORKQUEUE=16; -static const int DEFAULT_HTTP_TIMEOUT=30; +static const int DEFAULT_HTTP_SERVER_TIMEOUT=30; struct evhttp_request; struct event_base; diff --git a/src/init.cpp b/src/init.cpp index f03388120c..98834ef010 100644 --- a/src/init.cpp +++ b/src/init.cpp @@ -411,8 +411,12 @@ std::string HelpMessage(HelpMessageMode mode) strUsage += HelpMessageOpt("-fuzzmessagestest=<n>", "Randomly fuzz 1 of every <n> network messages"); strUsage += HelpMessageOpt("-flushwallet", strprintf("Run a thread to flush wallet periodically (default: %u)", 1)); strUsage += HelpMessageOpt("-stopafterblockimport", strprintf("Stop running after importing blocks from disk (default: %u)", 0)); + strUsage += HelpMessageOpt("-limitancestorcount=<n>", strprintf("Do not accept transactions if number of in-mempool ancestors is <n> or more (default: %u)", DEFAULT_ANCESTOR_LIMIT)); + strUsage += HelpMessageOpt("-limitancestorsize=<n>", strprintf("Do not accept transactions whose size with all in-mempool ancestors exceeds <n> kilobytes (default: %u)", DEFAULT_ANCESTOR_SIZE_LIMIT)); + strUsage += HelpMessageOpt("-limitdescendantcount=<n>", strprintf("Do not accept transactions if any ancestor would have <n> or more in-mempool descendants (default: %u)", DEFAULT_DESCENDANT_LIMIT)); + strUsage += HelpMessageOpt("-limitdescendantsize=<n>", strprintf("Do not accept transactions if any ancestor would have more than <n> kilobytes of in-mempool descendants (default: %u).", DEFAULT_DESCENDANT_SIZE_LIMIT)); } - string debugCategories = "addrman, alert, bench, coindb, db, lock, rand, rpc, selectcoins, mempool, mempoolrej, net, proxy, prune, http"; // Don't translate these and qt below + string debugCategories = "addrman, alert, bench, coindb, db, lock, rand, rpc, selectcoins, mempool, mempoolrej, net, proxy, prune, http, libevent"; // Don't translate these and qt below if (mode == HMM_BITCOIN_QT) debugCategories += ", qt"; strUsage += HelpMessageOpt("-debug=<category>", strprintf(_("Output debugging information (default: %u, supplying <category> is optional)"), 0) + ". " + @@ -465,7 +469,7 @@ std::string HelpMessage(HelpMessageMode mode) strUsage += HelpMessageOpt("-rpcthreads=<n>", strprintf(_("Set the number of threads to service RPC calls (default: %d)"), DEFAULT_HTTP_THREADS)); if (showDebug) { strUsage += HelpMessageOpt("-rpcworkqueue=<n>", strprintf("Set the depth of the work queue to service RPC calls (default: %d)", DEFAULT_HTTP_WORKQUEUE)); - strUsage += HelpMessageOpt("-rpctimeout=<n>", strprintf("Timeout during HTTP requests (default: %d)", DEFAULT_HTTP_TIMEOUT)); + strUsage += HelpMessageOpt("-rpcservertimeout=<n>", strprintf("Timeout during HTTP requests (default: %d)", DEFAULT_HTTP_SERVER_TIMEOUT)); } if (mode == HMM_BITCOIN_QT) @@ -712,11 +716,9 @@ bool AppInit2(boost::thread_group& threadGroup, CScheduler& scheduler) sa_hup.sa_flags = 0; sigaction(SIGHUP, &sa_hup, NULL); -#if defined (__SVR4) && defined (__sun) - // ignore SIGPIPE on Solaris + // Ignore SIGPIPE, otherwise it will bring the daemon down if the client closes unexpectedly signal(SIGPIPE, SIG_IGN); #endif -#endif // ********************************************************* Step 2: parameter interactions const CChainParams& chainparams = Params(); diff --git a/src/main.cpp b/src/main.cpp index 27278b977a..2a24d38e52 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -921,6 +921,17 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa REJECT_HIGHFEE, "absurdly-high-fee", strprintf("%d > %d", nFees, ::minRelayTxFee.GetFee(nSize) * 10000)); + // Calculate in-mempool ancestors, up to a limit. + CTxMemPool::setEntries setAncestors; + size_t nLimitAncestors = GetArg("-limitancestorcount", DEFAULT_ANCESTOR_LIMIT); + size_t nLimitAncestorSize = GetArg("-limitancestorsize", DEFAULT_ANCESTOR_SIZE_LIMIT)*1000; + size_t nLimitDescendants = GetArg("-limitdescendantcount", DEFAULT_DESCENDANT_LIMIT); + size_t nLimitDescendantSize = GetArg("-limitdescendantsize", DEFAULT_DESCENDANT_SIZE_LIMIT)*1000; + std::string errString; + if (!pool.CalculateMemPoolAncestors(entry, setAncestors, nLimitAncestors, nLimitAncestorSize, nLimitDescendants, nLimitDescendantSize, errString)) { + return state.DoS(0, false, REJECT_NONSTANDARD, "too-long-mempool-chain", false, errString); + } + // Check against previous transactions // This is done last to help prevent CPU exhaustion denial-of-service attacks. if (!CheckInputs(tx, state, view, true, STANDARD_SCRIPT_VERIFY_FLAGS, true)) @@ -942,7 +953,7 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa } // Store transaction in memory - pool.addUnchecked(hash, entry, !IsInitialBlockDownload()); + pool.addUnchecked(hash, entry, setAncestors, !IsInitialBlockDownload()); } SyncWithWallets(tx, NULL); @@ -2033,13 +2044,23 @@ bool static DisconnectTip(CValidationState &state) { if (!FlushStateToDisk(state, FLUSH_STATE_IF_NEEDED)) return false; // Resurrect mempool transactions from the disconnected block. + std::vector<uint256> vHashUpdate; BOOST_FOREACH(const CTransaction &tx, block.vtx) { // ignore validation errors in resurrected transactions list<CTransaction> removed; CValidationState stateDummy; - if (tx.IsCoinBase() || !AcceptToMemoryPool(mempool, stateDummy, tx, false, NULL)) + if (tx.IsCoinBase() || !AcceptToMemoryPool(mempool, stateDummy, tx, false, NULL)) { mempool.remove(tx, removed, true); + } else if (mempool.exists(tx.GetHash())) { + vHashUpdate.push_back(tx.GetHash()); + } } + // AcceptToMemoryPool/addUnchecked all assume that new mempool entries have + // no in-mempool children, which is generally not true when adding + // previously-confirmed transactions back to the mempool. + // UpdateTransactionsFromBlock finds descendants of any transactions in this + // block that were added back and cleans up the mempool state. + mempool.UpdateTransactionsFromBlock(vHashUpdate); mempool.removeCoinbaseSpends(pcoinsTip, pindexDelete->nHeight); mempool.check(pcoinsTip); // Update chainActive and related variables. @@ -4258,7 +4279,7 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv, LogPrint("mempool", "AcceptToMemoryPool: peer=%d %s: accepted %s (poolsz %u)\n", pfrom->id, pfrom->cleanSubVer, tx.GetHash().ToString(), - mempool.mapTx.size()); + mempool.size()); // Recursively process any orphan transactions that depended on this one set<NodeId> setMisbehaving; diff --git a/src/main.h b/src/main.h index e3479b4b3b..a6001eed8f 100644 --- a/src/main.h +++ b/src/main.h @@ -43,6 +43,14 @@ struct CNodeStateStats; static const bool DEFAULT_ALERTS = true; /** Default for -maxorphantx, maximum number of orphan transactions kept in memory */ static const unsigned int DEFAULT_MAX_ORPHAN_TRANSACTIONS = 100; +/** Default for -limitancestorcount, max number of in-mempool ancestors */ +static const unsigned int DEFAULT_ANCESTOR_LIMIT = 100; +/** Default for -limitancestorsize, maximum kilobytes of tx + all in-mempool ancestors */ +static const unsigned int DEFAULT_ANCESTOR_SIZE_LIMIT = 900; +/** Default for -limitdescendantcount, max number of in-mempool descendants */ +static const unsigned int DEFAULT_DESCENDANT_LIMIT = 1000; +/** Default for -limitdescendantsize, maximum kilobytes of in-mempool descendants */ +static const unsigned int DEFAULT_DESCENDANT_SIZE_LIMIT = 2500; /** The maximum size of a blk?????.dat file (since 0.8) */ static const unsigned int MAX_BLOCKFILE_SIZE = 0x8000000; // 128 MiB /** The pre-allocation chunk size for blk?????.dat files (since 0.8) */ diff --git a/src/memusage.h b/src/memusage.h index be3964df1b..b475c3313b 100644 --- a/src/memusage.h +++ b/src/memusage.h @@ -74,18 +74,30 @@ static inline size_t DynamicUsage(const std::vector<X>& v) return MallocUsage(v.capacity() * sizeof(X)); } -template<typename X> -static inline size_t DynamicUsage(const std::set<X>& s) +template<typename X, typename Y> +static inline size_t DynamicUsage(const std::set<X, Y>& s) { return MallocUsage(sizeof(stl_tree_node<X>)) * s.size(); } template<typename X, typename Y> -static inline size_t DynamicUsage(const std::map<X, Y>& m) +static inline size_t IncrementalDynamicUsage(const std::set<X, Y>& s) +{ + return MallocUsage(sizeof(stl_tree_node<X>)); +} + +template<typename X, typename Y, typename Z> +static inline size_t DynamicUsage(const std::map<X, Y, Z>& m) { return MallocUsage(sizeof(stl_tree_node<std::pair<const X, Y> >)) * m.size(); } +template<typename X, typename Y, typename Z> +static inline size_t IncrementalDynamicUsage(const std::map<X, Y, Z>& m) +{ + return MallocUsage(sizeof(stl_tree_node<std::pair<const X, Y> >)); +} + // Boost data structures template<typename X> diff --git a/src/miner.cpp b/src/miner.cpp index 9dd1d459b5..b2a356e52d 100644 --- a/src/miner.cpp +++ b/src/miner.cpp @@ -158,10 +158,10 @@ CBlockTemplate* CreateNewBlock(const CScript& scriptPubKeyIn) // This vector will be sorted into a priority queue: vector<TxPriority> vecPriority; vecPriority.reserve(mempool.mapTx.size()); - for (map<uint256, CTxMemPoolEntry>::iterator mi = mempool.mapTx.begin(); + for (CTxMemPool::indexed_transaction_set::iterator mi = mempool.mapTx.begin(); mi != mempool.mapTx.end(); ++mi) { - const CTransaction& tx = mi->second.GetTx(); + const CTransaction& tx = mi->GetTx(); if (tx.IsCoinBase() || !IsFinalTx(tx, nHeight, pblock->nTime)) continue; @@ -196,7 +196,7 @@ CBlockTemplate* CreateNewBlock(const CScript& scriptPubKeyIn) } mapDependers[txin.prevout.hash].push_back(porphan); porphan->setDependsOn.insert(txin.prevout.hash); - nTotalIn += mempool.mapTx[txin.prevout.hash].GetTx().vout[txin.prevout.n].nValue; + nTotalIn += mempool.mapTx.find(txin.prevout.hash)->GetTx().vout[txin.prevout.n].nValue; continue; } const CCoins* coins = view.AccessCoins(txin.prevout.hash); @@ -226,7 +226,7 @@ CBlockTemplate* CreateNewBlock(const CScript& scriptPubKeyIn) porphan->feeRate = feeRate; } else - vecPriority.push_back(TxPriority(dPriority, feeRate, &mi->second.GetTx())); + vecPriority.push_back(TxPriority(dPriority, feeRate, &(mi->GetTx()))); } // Collect transactions into block diff --git a/src/qt/guiconstants.h b/src/qt/guiconstants.h index a0a2993ea3..7d3e48ff32 100644 --- a/src/qt/guiconstants.h +++ b/src/qt/guiconstants.h @@ -42,7 +42,7 @@ static const int MAX_URI_LENGTH = 255; #define EXPORT_IMAGE_SIZE 256 /* Number of frames in spinner animation */ -#define SPINNER_FRAMES 35 +#define SPINNER_FRAMES 36 #define QAPP_ORG_NAME "Bitcoin" #define QAPP_ORG_DOMAIN "bitcoin.org" diff --git a/src/qt/guiutil.cpp b/src/qt/guiutil.cpp index 550dbacf93..8917f77f22 100644 --- a/src/qt/guiutil.cpp +++ b/src/qt/guiutil.cpp @@ -404,7 +404,7 @@ void SubstituteFonts(const QString& language) { #if defined(Q_OS_MAC) // Background: -// OSX's default font changed in 10.9 and QT is unable to find it with its +// OSX's default font changed in 10.9 and Qt is unable to find it with its // usual fallback methods when building against the 10.7 sdk or lower. // The 10.8 SDK added a function to let it find the correct fallback font. // If this fallback is not properly loaded, some characters may fail to diff --git a/src/qt/res/movies/makespinner.sh b/src/qt/res/movies/makespinner.sh index 625fb17173..a4c2fddbbf 100755 --- a/src/qt/res/movies/makespinner.sh +++ b/src/qt/res/movies/makespinner.sh @@ -1,6 +1,7 @@ -for i in {1..35} +FRAMEDIR=$(dirname $0) +for i in {0..35} do - value=$(printf "%03d" $i) + frame=$(printf "%03d" $i) angle=$(($i * 10)) - convert spinner-000.png -background "rgba(0,0,0,0.0)" -distort SRT $angle spinner-$value.png + convert $FRAMEDIR/../src/spinner.png -background "rgba(0,0,0,0.0)" -distort SRT $angle $FRAMEDIR/spinner-$frame.png done diff --git a/src/qt/res/movies/spinner-000.png b/src/qt/res/movies/spinner-000.png Binary files differindex 1e92d859da..0dc48d0d8c 100644 --- a/src/qt/res/movies/spinner-000.png +++ b/src/qt/res/movies/spinner-000.png diff --git a/src/qt/res/spinner.png b/src/qt/res/src/spinner.png Binary files differindex b296a58481..b296a58481 100644 --- a/src/qt/res/spinner.png +++ b/src/qt/res/src/spinner.png diff --git a/src/rpcblockchain.cpp b/src/rpcblockchain.cpp index e6751de96b..1c201ef99d 100644 --- a/src/rpcblockchain.cpp +++ b/src/rpcblockchain.cpp @@ -181,10 +181,9 @@ UniValue mempoolToJSON(bool fVerbose = false) { LOCK(mempool.cs); UniValue o(UniValue::VOBJ); - BOOST_FOREACH(const PAIRTYPE(uint256, CTxMemPoolEntry)& entry, mempool.mapTx) + BOOST_FOREACH(const CTxMemPoolEntry& e, mempool.mapTx) { - const uint256& hash = entry.first; - const CTxMemPoolEntry& e = entry.second; + const uint256& hash = e.GetTx().GetHash(); UniValue info(UniValue::VOBJ); info.push_back(Pair("size", (int)e.GetTxSize())); info.push_back(Pair("fee", ValueFromAmount(e.GetFee()))); @@ -192,6 +191,9 @@ UniValue mempoolToJSON(bool fVerbose = false) info.push_back(Pair("height", (int)e.GetHeight())); info.push_back(Pair("startingpriority", e.GetPriority(e.GetHeight()))); info.push_back(Pair("currentpriority", e.GetPriority(chainActive.Height()))); + info.push_back(Pair("descendantcount", e.GetCountWithDescendants())); + info.push_back(Pair("descendantsize", e.GetSizeWithDescendants())); + info.push_back(Pair("descendantfees", e.GetFeesWithDescendants())); const CTransaction& tx = e.GetTx(); set<string> setDepends; BOOST_FOREACH(const CTxIn& txin, tx.vin) @@ -246,6 +248,9 @@ UniValue getrawmempool(const UniValue& params, bool fHelp) " \"height\" : n, (numeric) block height when transaction entered pool\n" " \"startingpriority\" : n, (numeric) priority when transaction entered pool\n" " \"currentpriority\" : n, (numeric) transaction priority now\n" + " \"descendantcount\" : n, (numeric) number of in-mempool descendant transactions (including this one)\n" + " \"descendantsize\" : n, (numeric) size of in-mempool descendants (including this one)\n" + " \"descendantfees\" : n, (numeric) fees of in-mempool descendants (including this one)\n" " \"depends\" : [ (array) unconfirmed transactions used as inputs for this transaction\n" " \"transactionid\", (string) parent transaction id\n" " ... ]\n" diff --git a/src/test/mempool_tests.cpp b/src/test/mempool_tests.cpp index 2439689d7f..5bf1e98e8f 100644 --- a/src/test/mempool_tests.cpp +++ b/src/test/mempool_tests.cpp @@ -9,6 +9,7 @@ #include <boost/test/unit_test.hpp> #include <list> +#include <vector> BOOST_FIXTURE_TEST_SUITE(mempool_tests, TestingSetup) @@ -100,4 +101,184 @@ BOOST_AUTO_TEST_CASE(MempoolRemoveTest) removed.clear(); } +void CheckSort(CTxMemPool &pool, std::vector<std::string> &sortedOrder) +{ + BOOST_CHECK_EQUAL(pool.size(), sortedOrder.size()); + CTxMemPool::indexed_transaction_set::nth_index<1>::type::iterator it = pool.mapTx.get<1>().begin(); + int count=0; + for (; it != pool.mapTx.get<1>().end(); ++it, ++count) { + BOOST_CHECK_EQUAL(it->GetTx().GetHash().ToString(), sortedOrder[count]); + } +} + +BOOST_AUTO_TEST_CASE(MempoolIndexingTest) +{ + CTxMemPool pool(CFeeRate(0)); + + /* 3rd highest fee */ + CMutableTransaction tx1 = CMutableTransaction(); + tx1.vout.resize(1); + tx1.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; + tx1.vout[0].nValue = 10 * COIN; + pool.addUnchecked(tx1.GetHash(), CTxMemPoolEntry(tx1, 10000LL, 0, 10.0, 1, true)); + + /* highest fee */ + CMutableTransaction tx2 = CMutableTransaction(); + tx2.vout.resize(1); + tx2.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; + tx2.vout[0].nValue = 2 * COIN; + pool.addUnchecked(tx2.GetHash(), CTxMemPoolEntry(tx2, 20000LL, 0, 9.0, 1, true)); + + /* lowest fee */ + CMutableTransaction tx3 = CMutableTransaction(); + tx3.vout.resize(1); + tx3.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; + tx3.vout[0].nValue = 5 * COIN; + pool.addUnchecked(tx3.GetHash(), CTxMemPoolEntry(tx3, 0LL, 0, 100.0, 1, true)); + + /* 2nd highest fee */ + CMutableTransaction tx4 = CMutableTransaction(); + tx4.vout.resize(1); + tx4.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; + tx4.vout[0].nValue = 6 * COIN; + pool.addUnchecked(tx4.GetHash(), CTxMemPoolEntry(tx4, 15000LL, 0, 1.0, 1, true)); + + /* equal fee rate to tx1, but newer */ + CMutableTransaction tx5 = CMutableTransaction(); + tx5.vout.resize(1); + tx5.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; + tx5.vout[0].nValue = 11 * COIN; + pool.addUnchecked(tx5.GetHash(), CTxMemPoolEntry(tx5, 10000LL, 1, 10.0, 1, true)); + BOOST_CHECK_EQUAL(pool.size(), 5); + + std::vector<std::string> sortedOrder; + sortedOrder.resize(5); + sortedOrder[0] = tx2.GetHash().ToString(); // 20000 + sortedOrder[1] = tx4.GetHash().ToString(); // 15000 + sortedOrder[2] = tx1.GetHash().ToString(); // 10000 + sortedOrder[3] = tx5.GetHash().ToString(); // 10000 + sortedOrder[4] = tx3.GetHash().ToString(); // 0 + CheckSort(pool, sortedOrder); + + /* low fee but with high fee child */ + /* tx6 -> tx7 -> tx8, tx9 -> tx10 */ + CMutableTransaction tx6 = CMutableTransaction(); + tx6.vout.resize(1); + tx6.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; + tx6.vout[0].nValue = 20 * COIN; + pool.addUnchecked(tx6.GetHash(), CTxMemPoolEntry(tx6, 0LL, 1, 10.0, 1, true)); + BOOST_CHECK_EQUAL(pool.size(), 6); + // Check that at this point, tx6 is sorted low + sortedOrder.push_back(tx6.GetHash().ToString()); + CheckSort(pool, sortedOrder); + + CTxMemPool::setEntries setAncestors; + setAncestors.insert(pool.mapTx.find(tx6.GetHash())); + CMutableTransaction tx7 = CMutableTransaction(); + tx7.vin.resize(1); + tx7.vin[0].prevout = COutPoint(tx6.GetHash(), 0); + tx7.vin[0].scriptSig = CScript() << OP_11; + tx7.vout.resize(2); + tx7.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; + tx7.vout[0].nValue = 10 * COIN; + tx7.vout[1].scriptPubKey = CScript() << OP_11 << OP_EQUAL; + tx7.vout[1].nValue = 1 * COIN; + + CTxMemPool::setEntries setAncestorsCalculated; + std::string dummy; + CTxMemPoolEntry entry7(tx7, 2000000LL, 1, 10.0, 1, true); + BOOST_CHECK_EQUAL(pool.CalculateMemPoolAncestors(entry7, setAncestorsCalculated, 100, 1000000, 1000, 1000000, dummy), true); + BOOST_CHECK(setAncestorsCalculated == setAncestors); + + pool.addUnchecked(tx7.GetHash(), CTxMemPoolEntry(tx7, 2000000LL, 1, 10.0, 1, true), setAncestors); + BOOST_CHECK_EQUAL(pool.size(), 7); + + // Now tx6 should be sorted higher (high fee child): tx7, tx6, tx2, ... + sortedOrder.erase(sortedOrder.end()-1); + sortedOrder.insert(sortedOrder.begin(), tx6.GetHash().ToString()); + sortedOrder.insert(sortedOrder.begin(), tx7.GetHash().ToString()); + CheckSort(pool, sortedOrder); + + /* low fee child of tx7 */ + CMutableTransaction tx8 = CMutableTransaction(); + tx8.vin.resize(1); + tx8.vin[0].prevout = COutPoint(tx7.GetHash(), 0); + tx8.vin[0].scriptSig = CScript() << OP_11; + tx8.vout.resize(1); + tx8.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; + tx8.vout[0].nValue = 10 * COIN; + setAncestors.insert(pool.mapTx.find(tx7.GetHash())); + pool.addUnchecked(tx8.GetHash(), CTxMemPoolEntry(tx8, 0LL, 2, 10.0, 1, true), setAncestors); + + // Now tx8 should be sorted low, but tx6/tx both high + sortedOrder.push_back(tx8.GetHash().ToString()); + CheckSort(pool, sortedOrder); + + /* low fee child of tx7 */ + CMutableTransaction tx9 = CMutableTransaction(); + tx9.vin.resize(1); + tx9.vin[0].prevout = COutPoint(tx7.GetHash(), 1); + tx9.vin[0].scriptSig = CScript() << OP_11; + tx9.vout.resize(1); + tx9.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; + tx9.vout[0].nValue = 1 * COIN; + pool.addUnchecked(tx9.GetHash(), CTxMemPoolEntry(tx9, 0LL, 3, 10.0, 1, true), setAncestors); + + // tx9 should be sorted low + BOOST_CHECK_EQUAL(pool.size(), 9); + sortedOrder.push_back(tx9.GetHash().ToString()); + CheckSort(pool, sortedOrder); + + std::vector<std::string> snapshotOrder = sortedOrder; + + setAncestors.insert(pool.mapTx.find(tx8.GetHash())); + setAncestors.insert(pool.mapTx.find(tx9.GetHash())); + /* tx10 depends on tx8 and tx9 and has a high fee*/ + CMutableTransaction tx10 = CMutableTransaction(); + tx10.vin.resize(2); + tx10.vin[0].prevout = COutPoint(tx8.GetHash(), 0); + tx10.vin[0].scriptSig = CScript() << OP_11; + tx10.vin[1].prevout = COutPoint(tx9.GetHash(), 0); + tx10.vin[1].scriptSig = CScript() << OP_11; + tx10.vout.resize(1); + tx10.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; + tx10.vout[0].nValue = 10 * COIN; + + setAncestorsCalculated.clear(); + CTxMemPoolEntry entry10(tx10, 200000LL, 4, 10.0, 1, true); + BOOST_CHECK_EQUAL(pool.CalculateMemPoolAncestors(entry10, setAncestorsCalculated, 100, 1000000, 1000, 1000000, dummy), true); + BOOST_CHECK(setAncestorsCalculated == setAncestors); + + pool.addUnchecked(tx10.GetHash(), CTxMemPoolEntry(tx10, 200000LL, 4, 10.0, 1, true), setAncestors); + + /** + * tx8 and tx9 should both now be sorted higher + * Final order after tx10 is added: + * + * tx7 = 2.2M (4 txs) + * tx6 = 2.2M (5 txs) + * tx10 = 200k (1 tx) + * tx8 = 200k (2 txs) + * tx9 = 200k (2 txs) + * tx2 = 20000 (1) + * tx4 = 15000 (1) + * tx1 = 10000 (1) + * tx5 = 10000 (1) + * tx3 = 0 (1) + */ + sortedOrder.erase(sortedOrder.end()-2, sortedOrder.end()); // take out tx8, tx9 from the end + sortedOrder.insert(sortedOrder.begin()+2, tx10.GetHash().ToString()); // tx10 is after tx6 + sortedOrder.insert(sortedOrder.begin()+3, tx9.GetHash().ToString()); + sortedOrder.insert(sortedOrder.begin()+3, tx8.GetHash().ToString()); + CheckSort(pool, sortedOrder); + + // there should be 10 transactions in the mempool + BOOST_CHECK_EQUAL(pool.size(), 10); + + // Now try removing tx10 and verify the sort order returns to normal + std::list<CTransaction> removed; + pool.remove(pool.mapTx.find(tx10.GetHash())->GetTx(), removed, true); + CheckSort(pool, snapshotOrder); +} + BOOST_AUTO_TEST_SUITE_END() diff --git a/src/txmempool.cpp b/src/txmempool.cpp index c921dae45d..2f603e3c9f 100644 --- a/src/txmempool.cpp +++ b/src/txmempool.cpp @@ -17,12 +17,6 @@ using namespace std; -CTxMemPoolEntry::CTxMemPoolEntry(): - nFee(0), nTxSize(0), nModSize(0), nUsageSize(0), nTime(0), dPriority(0.0), hadNoDependencies(false) -{ - nHeight = MEMPOOL_HEIGHT; -} - CTxMemPoolEntry::CTxMemPoolEntry(const CTransaction& _tx, const CAmount& _nFee, int64_t _nTime, double _dPriority, unsigned int _nHeight, bool poolHasNoInputsOf): @@ -32,6 +26,10 @@ CTxMemPoolEntry::CTxMemPoolEntry(const CTransaction& _tx, const CAmount& _nFee, nTxSize = ::GetSerializeSize(tx, SER_NETWORK, PROTOCOL_VERSION); nModSize = tx.CalculateModifiedSize(nTxSize); nUsageSize = RecursiveDynamicUsage(tx); + + nCountWithDescendants = 1; + nSizeWithDescendants = nTxSize; + nFeesWithDescendants = nFee; } CTxMemPoolEntry::CTxMemPoolEntry(const CTxMemPoolEntry& other) @@ -48,6 +46,244 @@ CTxMemPoolEntry::GetPriority(unsigned int currentHeight) const return dResult; } +// Update the given tx for any in-mempool descendants. +// Assumes that setMemPoolChildren is correct for the given tx and all +// descendants. +bool CTxMemPool::UpdateForDescendants(txiter updateIt, int maxDescendantsToVisit, cacheMap &cachedDescendants, const std::set<uint256> &setExclude) +{ + // Track the number of entries (outside setExclude) that we'd need to visit + // (will bail out if it exceeds maxDescendantsToVisit) + int nChildrenToVisit = 0; + + setEntries stageEntries, setAllDescendants; + stageEntries = GetMemPoolChildren(updateIt); + + while (!stageEntries.empty()) { + const txiter cit = *stageEntries.begin(); + if (cit->IsDirty()) { + // Don't consider any more children if any descendant is dirty + return false; + } + setAllDescendants.insert(cit); + stageEntries.erase(cit); + const setEntries &setChildren = GetMemPoolChildren(cit); + BOOST_FOREACH(const txiter childEntry, setChildren) { + cacheMap::iterator cacheIt = cachedDescendants.find(childEntry); + if (cacheIt != cachedDescendants.end()) { + // We've already calculated this one, just add the entries for this set + // but don't traverse again. + BOOST_FOREACH(const txiter cacheEntry, cacheIt->second) { + // update visit count only for new child transactions + // (outside of setExclude and stageEntries) + if (setAllDescendants.insert(cacheEntry).second && + !setExclude.count(cacheEntry->GetTx().GetHash()) && + !stageEntries.count(cacheEntry)) { + nChildrenToVisit++; + } + } + } else if (!setAllDescendants.count(childEntry)) { + // Schedule for later processing and update our visit count + if (stageEntries.insert(childEntry).second && !setExclude.count(childEntry->GetTx().GetHash())) { + nChildrenToVisit++; + } + } + if (nChildrenToVisit > maxDescendantsToVisit) { + return false; + } + } + } + // setAllDescendants now contains all in-mempool descendants of updateIt. + // Update and add to cached descendant map + int64_t modifySize = 0; + CAmount modifyFee = 0; + int64_t modifyCount = 0; + BOOST_FOREACH(txiter cit, setAllDescendants) { + if (!setExclude.count(cit->GetTx().GetHash())) { + modifySize += cit->GetTxSize(); + modifyFee += cit->GetFee(); + modifyCount++; + cachedDescendants[updateIt].insert(cit); + } + } + mapTx.modify(updateIt, update_descendant_state(modifySize, modifyFee, modifyCount)); + return true; +} + +// vHashesToUpdate is the set of transaction hashes from a disconnected block +// which has been re-added to the mempool. +// for each entry, look for descendants that are outside hashesToUpdate, and +// add fee/size information for such descendants to the parent. +void CTxMemPool::UpdateTransactionsFromBlock(const std::vector<uint256> &vHashesToUpdate) +{ + LOCK(cs); + // For each entry in vHashesToUpdate, store the set of in-mempool, but not + // in-vHashesToUpdate transactions, so that we don't have to recalculate + // descendants when we come across a previously seen entry. + cacheMap mapMemPoolDescendantsToUpdate; + + // Use a set for lookups into vHashesToUpdate (these entries are already + // accounted for in the state of their ancestors) + std::set<uint256> setAlreadyIncluded(vHashesToUpdate.begin(), vHashesToUpdate.end()); + + // Iterate in reverse, so that whenever we are looking at at a transaction + // we are sure that all in-mempool descendants have already been processed. + // This maximizes the benefit of the descendant cache and guarantees that + // setMemPoolChildren will be updated, an assumption made in + // UpdateForDescendants. + BOOST_REVERSE_FOREACH(const uint256 &hash, vHashesToUpdate) { + // we cache the in-mempool children to avoid duplicate updates + setEntries setChildren; + // calculate children from mapNextTx + txiter it = mapTx.find(hash); + if (it == mapTx.end()) { + continue; + } + std::map<COutPoint, CInPoint>::iterator iter = mapNextTx.lower_bound(COutPoint(hash, 0)); + // First calculate the children, and update setMemPoolChildren to + // include them, and update their setMemPoolParents to include this tx. + for (; iter != mapNextTx.end() && iter->first.hash == hash; ++iter) { + const uint256 &childHash = iter->second.ptx->GetHash(); + txiter childIter = mapTx.find(childHash); + assert(childIter != mapTx.end()); + // We can skip updating entries we've encountered before or that + // are in the block (which are already accounted for). + if (setChildren.insert(childIter).second && !setAlreadyIncluded.count(childHash)) { + UpdateChild(it, childIter, true); + UpdateParent(childIter, it, true); + } + } + if (!UpdateForDescendants(it, 100, mapMemPoolDescendantsToUpdate, setAlreadyIncluded)) { + // Mark as dirty if we can't do the calculation. + mapTx.modify(it, set_dirty()); + } + } +} + +bool CTxMemPool::CalculateMemPoolAncestors(const CTxMemPoolEntry &entry, setEntries &setAncestors, uint64_t limitAncestorCount, uint64_t limitAncestorSize, uint64_t limitDescendantCount, uint64_t limitDescendantSize, std::string &errString) +{ + setEntries parentHashes; + const CTransaction &tx = entry.GetTx(); + + // Get parents of this transaction that are in the mempool + // Entry may or may not already be in the mempool, and GetMemPoolParents() + // is only valid for entries in the mempool, so we iterate mapTx to find + // parents. + // TODO: optimize this so that we only check limits and walk + // tx.vin when called on entries not already in the mempool. + for (unsigned int i = 0; i < tx.vin.size(); i++) { + txiter piter = mapTx.find(tx.vin[i].prevout.hash); + if (piter != mapTx.end()) { + parentHashes.insert(piter); + if (parentHashes.size() + 1 > limitAncestorCount) { + errString = strprintf("too many unconfirmed parents [limit: %u]", limitAncestorCount); + return false; + } + } + } + + size_t totalSizeWithAncestors = entry.GetTxSize(); + + while (!parentHashes.empty()) { + txiter stageit = *parentHashes.begin(); + + setAncestors.insert(stageit); + parentHashes.erase(stageit); + totalSizeWithAncestors += stageit->GetTxSize(); + + if (stageit->GetSizeWithDescendants() + entry.GetTxSize() > limitDescendantSize) { + errString = strprintf("exceeds descendant size limit for tx %s [limit: %u]", stageit->GetTx().GetHash().ToString(), limitDescendantSize); + return false; + } else if (stageit->GetCountWithDescendants() + 1 > limitDescendantCount) { + errString = strprintf("too many descendants for tx %s [limit: %u]", stageit->GetTx().GetHash().ToString(), limitDescendantCount); + return false; + } else if (totalSizeWithAncestors > limitAncestorSize) { + errString = strprintf("exceeds ancestor size limit [limit: %u]", limitAncestorSize); + return false; + } + + const setEntries & setMemPoolParents = GetMemPoolParents(stageit); + BOOST_FOREACH(const txiter &phash, setMemPoolParents) { + // If this is a new ancestor, add it. + if (setAncestors.count(phash) == 0) { + parentHashes.insert(phash); + } + if (parentHashes.size() + setAncestors.size() + 1 > limitAncestorCount) { + errString = strprintf("too many unconfirmed ancestors [limit: %u]", limitAncestorCount); + return false; + } + } + } + + return true; +} + +void CTxMemPool::UpdateAncestorsOf(bool add, txiter it, setEntries &setAncestors) +{ + setEntries parentIters = GetMemPoolParents(it); + // add or remove this tx as a child of each parent + BOOST_FOREACH(txiter piter, parentIters) { + UpdateChild(piter, it, add); + } + const int64_t updateCount = (add ? 1 : -1); + const int64_t updateSize = updateCount * it->GetTxSize(); + const CAmount updateFee = updateCount * it->GetFee(); + BOOST_FOREACH(txiter ancestorIt, setAncestors) { + mapTx.modify(ancestorIt, update_descendant_state(updateSize, updateFee, updateCount)); + } +} + +void CTxMemPool::UpdateChildrenForRemoval(txiter it) +{ + const setEntries &setMemPoolChildren = GetMemPoolChildren(it); + BOOST_FOREACH(txiter updateIt, setMemPoolChildren) { + UpdateParent(updateIt, it, false); + } +} + +void CTxMemPool::UpdateForRemoveFromMempool(const setEntries &entriesToRemove) +{ + // For each entry, walk back all ancestors and decrement size associated with this + // transaction + const uint64_t nNoLimit = std::numeric_limits<uint64_t>::max(); + BOOST_FOREACH(txiter removeIt, entriesToRemove) { + setEntries setAncestors; + const CTxMemPoolEntry &entry = *removeIt; + std::string dummy; + CalculateMemPoolAncestors(entry, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy); + // Note that UpdateAncestorsOf severs the child links that point to + // removeIt in the entries for the parents of removeIt. This is + // fine since we don't need to use the mempool children of any entries + // to walk back over our ancestors (but we do need the mempool + // parents!) + UpdateAncestorsOf(false, removeIt, setAncestors); + } + // After updating all the ancestor sizes, we can now sever the link between each + // transaction being removed and any mempool children (ie, update setMemPoolParents + // for each direct child of a transaction being removed). + BOOST_FOREACH(txiter removeIt, entriesToRemove) { + UpdateChildrenForRemoval(removeIt); + } +} + +void CTxMemPoolEntry::SetDirty() +{ + nCountWithDescendants = 0; + nSizeWithDescendants = nTxSize; + nFeesWithDescendants = nFee; +} + +void CTxMemPoolEntry::UpdateState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount) +{ + if (!IsDirty()) { + nSizeWithDescendants += modifySize; + assert(int64_t(nSizeWithDescendants) > 0); + nFeesWithDescendants += modifyFee; + assert(nFeesWithDescendants >= 0); + nCountWithDescendants += modifyCount; + assert(int64_t(nCountWithDescendants) > 0); + } +} + CTxMemPool::CTxMemPool(const CFeeRate& _minRelayFee) : nTransactionsUpdated(0) { @@ -89,34 +325,103 @@ void CTxMemPool::AddTransactionsUpdated(unsigned int n) nTransactionsUpdated += n; } - -bool CTxMemPool::addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry, bool fCurrentEstimate) +bool CTxMemPool::addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry, setEntries &setAncestors, bool fCurrentEstimate) { // Add to memory pool without checking anything. // Used by main.cpp AcceptToMemoryPool(), which DOES do // all the appropriate checks. LOCK(cs); - mapTx[hash] = entry; - const CTransaction& tx = mapTx[hash].GetTx(); - for (unsigned int i = 0; i < tx.vin.size(); i++) + indexed_transaction_set::iterator newit = mapTx.insert(entry).first; + mapLinks.insert(make_pair(newit, TxLinks())); + + // Update cachedInnerUsage to include contained transaction's usage. + // (When we update the entry for in-mempool parents, memory usage will be + // further updated.) + cachedInnerUsage += entry.DynamicMemoryUsage(); + + const CTransaction& tx = newit->GetTx(); + std::set<uint256> setParentTransactions; + for (unsigned int i = 0; i < tx.vin.size(); i++) { mapNextTx[tx.vin[i].prevout] = CInPoint(&tx, i); + setParentTransactions.insert(tx.vin[i].prevout.hash); + } + // Don't bother worrying about child transactions of this one. + // Normal case of a new transaction arriving is that there can't be any + // children, because such children would be orphans. + // An exception to that is if a transaction enters that used to be in a block. + // In that case, our disconnect block logic will call UpdateTransactionsFromBlock + // to clean up the mess we're leaving here. + + // Update ancestors with information about this tx + BOOST_FOREACH (const uint256 &phash, setParentTransactions) { + txiter pit = mapTx.find(phash); + if (pit != mapTx.end()) { + UpdateParent(newit, pit, true); + } + } + UpdateAncestorsOf(true, newit, setAncestors); + nTransactionsUpdated++; totalTxSize += entry.GetTxSize(); - cachedInnerUsage += entry.DynamicMemoryUsage(); minerPolicyEstimator->processTransaction(entry, fCurrentEstimate); return true; } +void CTxMemPool::removeUnchecked(txiter it) +{ + const uint256 hash = it->GetTx().GetHash(); + BOOST_FOREACH(const CTxIn& txin, it->GetTx().vin) + mapNextTx.erase(txin.prevout); + + totalTxSize -= it->GetTxSize(); + cachedInnerUsage -= it->DynamicMemoryUsage(); + cachedInnerUsage -= memusage::DynamicUsage(mapLinks[it].parents) + memusage::DynamicUsage(mapLinks[it].children); + mapLinks.erase(it); + mapTx.erase(it); + nTransactionsUpdated++; + minerPolicyEstimator->removeTx(hash); +} + +// Calculates descendants of entry that are not already in setDescendants, and adds to +// setDescendants. Assumes entryit is already a tx in the mempool and setMemPoolChildren +// is correct for tx and all descendants. +// Also assumes that if an entry is in setDescendants already, then all +// in-mempool descendants of it are already in setDescendants as well, so that we +// can save time by not iterating over those entries. +void CTxMemPool::CalculateDescendants(txiter entryit, setEntries &setDescendants) +{ + setEntries stage; + if (setDescendants.count(entryit) == 0) { + stage.insert(entryit); + } + // Traverse down the children of entry, only adding children that are not + // accounted for in setDescendants already (because those children have either + // already been walked, or will be walked in this iteration). + while (!stage.empty()) { + txiter it = *stage.begin(); + setDescendants.insert(it); + stage.erase(it); + + const setEntries &setChildren = GetMemPoolChildren(it); + BOOST_FOREACH(const txiter &childiter, setChildren) { + if (!setDescendants.count(childiter)) { + stage.insert(childiter); + } + } + } +} void CTxMemPool::remove(const CTransaction &origTx, std::list<CTransaction>& removed, bool fRecursive) { // Remove transaction from memory pool { LOCK(cs); - std::deque<uint256> txToRemove; - txToRemove.push_back(origTx.GetHash()); - if (fRecursive && !mapTx.count(origTx.GetHash())) { + setEntries txToRemove; + txiter origit = mapTx.find(origTx.GetHash()); + if (origit != mapTx.end()) { + txToRemove.insert(origit); + } else if (fRecursive) { // If recursively removing but origTx isn't in the mempool // be sure to remove any children that are in the pool. This can // happen during chain re-orgs if origTx isn't re-accepted into @@ -125,34 +430,23 @@ void CTxMemPool::remove(const CTransaction &origTx, std::list<CTransaction>& rem std::map<COutPoint, CInPoint>::iterator it = mapNextTx.find(COutPoint(origTx.GetHash(), i)); if (it == mapNextTx.end()) continue; - txToRemove.push_back(it->second.ptx->GetHash()); + txiter nextit = mapTx.find(it->second.ptx->GetHash()); + assert(nextit != mapTx.end()); + txToRemove.insert(nextit); } } - while (!txToRemove.empty()) - { - uint256 hash = txToRemove.front(); - txToRemove.pop_front(); - if (!mapTx.count(hash)) - continue; - const CTransaction& tx = mapTx[hash].GetTx(); - if (fRecursive) { - for (unsigned int i = 0; i < tx.vout.size(); i++) { - std::map<COutPoint, CInPoint>::iterator it = mapNextTx.find(COutPoint(hash, i)); - if (it == mapNextTx.end()) - continue; - txToRemove.push_back(it->second.ptx->GetHash()); - } + setEntries setAllRemoves; + if (fRecursive) { + BOOST_FOREACH(txiter it, txToRemove) { + CalculateDescendants(it, setAllRemoves); } - BOOST_FOREACH(const CTxIn& txin, tx.vin) - mapNextTx.erase(txin.prevout); - - removed.push_back(tx); - totalTxSize -= mapTx[hash].GetTxSize(); - cachedInnerUsage -= mapTx[hash].DynamicMemoryUsage(); - mapTx.erase(hash); - nTransactionsUpdated++; - minerPolicyEstimator->removeTx(hash); + } else { + setAllRemoves.swap(txToRemove); } + BOOST_FOREACH(txiter it, setAllRemoves) { + removed.push_back(it->GetTx()); + } + RemoveStaged(setAllRemoves); } } @@ -161,10 +455,10 @@ void CTxMemPool::removeCoinbaseSpends(const CCoinsViewCache *pcoins, unsigned in // Remove transactions spending a coinbase which are now immature LOCK(cs); list<CTransaction> transactionsToRemove; - for (std::map<uint256, CTxMemPoolEntry>::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) { - const CTransaction& tx = it->second.GetTx(); + for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) { + const CTransaction& tx = it->GetTx(); BOOST_FOREACH(const CTxIn& txin, tx.vin) { - std::map<uint256, CTxMemPoolEntry>::const_iterator it2 = mapTx.find(txin.prevout.hash); + indexed_transaction_set::const_iterator it2 = mapTx.find(txin.prevout.hash); if (it2 != mapTx.end()) continue; const CCoins *coins = pcoins->AccessCoins(txin.prevout.hash); @@ -209,8 +503,10 @@ void CTxMemPool::removeForBlock(const std::vector<CTransaction>& vtx, unsigned i BOOST_FOREACH(const CTransaction& tx, vtx) { uint256 hash = tx.GetHash(); - if (mapTx.count(hash)) - entries.push_back(mapTx[hash]); + + indexed_transaction_set::iterator i = mapTx.find(hash); + if (i != mapTx.end()) + entries.push_back(*i); } BOOST_FOREACH(const CTransaction& tx, vtx) { @@ -226,6 +522,7 @@ void CTxMemPool::removeForBlock(const std::vector<CTransaction>& vtx, unsigned i void CTxMemPool::clear() { LOCK(cs); + mapLinks.clear(); mapTx.clear(); mapNextTx.clear(); totalTxSize = 0; @@ -247,19 +544,25 @@ void CTxMemPool::check(const CCoinsViewCache *pcoins) const LOCK(cs); list<const CTxMemPoolEntry*> waitingOnDependants; - for (std::map<uint256, CTxMemPoolEntry>::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) { + for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) { unsigned int i = 0; - checkTotal += it->second.GetTxSize(); - innerUsage += it->second.DynamicMemoryUsage(); - const CTransaction& tx = it->second.GetTx(); + checkTotal += it->GetTxSize(); + innerUsage += it->DynamicMemoryUsage(); + const CTransaction& tx = it->GetTx(); + txlinksMap::const_iterator linksiter = mapLinks.find(it); + assert(linksiter != mapLinks.end()); + const TxLinks &links = linksiter->second; + innerUsage += memusage::DynamicUsage(links.parents) + memusage::DynamicUsage(links.children); bool fDependsWait = false; + setEntries setParentCheck; BOOST_FOREACH(const CTxIn &txin, tx.vin) { // Check that every mempool transaction's inputs refer to available coins, or other mempool tx's. - std::map<uint256, CTxMemPoolEntry>::const_iterator it2 = mapTx.find(txin.prevout.hash); + indexed_transaction_set::const_iterator it2 = mapTx.find(txin.prevout.hash); if (it2 != mapTx.end()) { - const CTransaction& tx2 = it2->second.GetTx(); + const CTransaction& tx2 = it2->GetTx(); assert(tx2.vout.size() > txin.prevout.n && !tx2.vout[txin.prevout.n].IsNull()); fDependsWait = true; + setParentCheck.insert(it2); } else { const CCoins* coins = pcoins->AccessCoins(txin.prevout.hash); assert(coins && coins->IsAvailable(txin.prevout.n)); @@ -271,8 +574,35 @@ void CTxMemPool::check(const CCoinsViewCache *pcoins) const assert(it3->second.n == i); i++; } + assert(setParentCheck == GetMemPoolParents(it)); + // Check children against mapNextTx + CTxMemPool::setEntries setChildrenCheck; + std::map<COutPoint, CInPoint>::const_iterator iter = mapNextTx.lower_bound(COutPoint(it->GetTx().GetHash(), 0)); + int64_t childSizes = 0; + CAmount childFees = 0; + for (; iter != mapNextTx.end() && iter->first.hash == it->GetTx().GetHash(); ++iter) { + txiter childit = mapTx.find(iter->second.ptx->GetHash()); + assert(childit != mapTx.end()); // mapNextTx points to in-mempool transactions + if (setChildrenCheck.insert(childit).second) { + childSizes += childit->GetTxSize(); + childFees += childit->GetFee(); + } + } + assert(setChildrenCheck == GetMemPoolChildren(it)); + // Also check to make sure size/fees is greater than sum with immediate children. + // just a sanity check, not definitive that this calc is correct... + // also check that the size is less than the size of the entire mempool. + if (!it->IsDirty()) { + assert(it->GetSizeWithDescendants() >= childSizes + it->GetTxSize()); + assert(it->GetFeesWithDescendants() >= childFees + it->GetFee()); + } else { + assert(it->GetSizeWithDescendants() == it->GetTxSize()); + assert(it->GetFeesWithDescendants() == it->GetFee()); + } + assert(it->GetFeesWithDescendants() >= 0); + if (fDependsWait) - waitingOnDependants.push_back(&it->second); + waitingOnDependants.push_back(&(*it)); else { CValidationState state; assert(CheckInputs(tx, state, mempoolDuplicate, false, 0, false, NULL)); @@ -296,8 +626,8 @@ void CTxMemPool::check(const CCoinsViewCache *pcoins) const } for (std::map<COutPoint, CInPoint>::const_iterator it = mapNextTx.begin(); it != mapNextTx.end(); it++) { uint256 hash = it->second.ptx->GetHash(); - map<uint256, CTxMemPoolEntry>::const_iterator it2 = mapTx.find(hash); - const CTransaction& tx = it2->second.GetTx(); + indexed_transaction_set::const_iterator it2 = mapTx.find(hash); + const CTransaction& tx = it2->GetTx(); assert(it2 != mapTx.end()); assert(&tx == it->second.ptx); assert(tx.vin.size() > it->second.n); @@ -314,16 +644,16 @@ void CTxMemPool::queryHashes(vector<uint256>& vtxid) LOCK(cs); vtxid.reserve(mapTx.size()); - for (map<uint256, CTxMemPoolEntry>::iterator mi = mapTx.begin(); mi != mapTx.end(); ++mi) - vtxid.push_back((*mi).first); + for (indexed_transaction_set::iterator mi = mapTx.begin(); mi != mapTx.end(); ++mi) + vtxid.push_back(mi->GetTx().GetHash()); } bool CTxMemPool::lookup(uint256 hash, CTransaction& result) const { LOCK(cs); - map<uint256, CTxMemPoolEntry>::const_iterator i = mapTx.find(hash); + indexed_transaction_set::const_iterator i = mapTx.find(hash); if (i == mapTx.end()) return false; - result = i->second.GetTx(); + result = i->GetTx(); return true; } @@ -429,5 +759,60 @@ bool CCoinsViewMemPool::HaveCoins(const uint256 &txid) const { size_t CTxMemPool::DynamicMemoryUsage() const { LOCK(cs); - return memusage::DynamicUsage(mapTx) + memusage::DynamicUsage(mapNextTx) + memusage::DynamicUsage(mapDeltas) + cachedInnerUsage; + // Estimate the overhead of mapTx to be 9 pointers + an allocation, as no exact formula for boost::multi_index_contained is implemented. + return memusage::MallocUsage(sizeof(CTxMemPoolEntry) + 9 * sizeof(void*)) * mapTx.size() + memusage::DynamicUsage(mapNextTx) + memusage::DynamicUsage(mapDeltas) + memusage::DynamicUsage(mapLinks) + cachedInnerUsage; +} + +void CTxMemPool::RemoveStaged(setEntries &stage) { + AssertLockHeld(cs); + UpdateForRemoveFromMempool(stage); + BOOST_FOREACH(const txiter& it, stage) { + removeUnchecked(it); + } +} + +bool CTxMemPool::addUnchecked(const uint256&hash, const CTxMemPoolEntry &entry, bool fCurrentEstimate) +{ + LOCK(cs); + setEntries setAncestors; + uint64_t nNoLimit = std::numeric_limits<uint64_t>::max(); + std::string dummy; + CalculateMemPoolAncestors(entry, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy); + return addUnchecked(hash, entry, setAncestors, fCurrentEstimate); +} + +void CTxMemPool::UpdateChild(txiter entry, txiter child, bool add) +{ + setEntries s; + if (add && mapLinks[entry].children.insert(child).second) { + cachedInnerUsage += memusage::IncrementalDynamicUsage(s); + } else if (!add && mapLinks[entry].children.erase(child)) { + cachedInnerUsage -= memusage::IncrementalDynamicUsage(s); + } +} + +void CTxMemPool::UpdateParent(txiter entry, txiter parent, bool add) +{ + setEntries s; + if (add && mapLinks[entry].parents.insert(parent).second) { + cachedInnerUsage += memusage::IncrementalDynamicUsage(s); + } else if (!add && mapLinks[entry].parents.erase(parent)) { + cachedInnerUsage -= memusage::IncrementalDynamicUsage(s); + } +} + +const CTxMemPool::setEntries & CTxMemPool::GetMemPoolParents(txiter entry) const +{ + assert (entry != mapTx.end()); + txlinksMap::const_iterator it = mapLinks.find(entry); + assert(it != mapLinks.end()); + return it->second.parents; +} + +const CTxMemPool::setEntries & CTxMemPool::GetMemPoolChildren(txiter entry) const +{ + assert (entry != mapTx.end()); + txlinksMap::const_iterator it = mapLinks.find(entry); + assert(it != mapLinks.end()); + return it->second.children; } diff --git a/src/txmempool.h b/src/txmempool.h index ea36ce1ad5..f0c3f7e0f1 100644 --- a/src/txmempool.h +++ b/src/txmempool.h @@ -7,12 +7,17 @@ #define BITCOIN_TXMEMPOOL_H #include <list> +#include <set> #include "amount.h" #include "coins.h" #include "primitives/transaction.h" #include "sync.h" +#undef foreach +#include "boost/multi_index_container.hpp" +#include "boost/multi_index/ordered_index.hpp" + class CAutoFile; inline double AllowFreeThreshold() @@ -30,9 +35,25 @@ inline bool AllowFree(double dPriority) /** Fake height value used in CCoins to signify they are only in the memory pool (since 0.8) */ static const unsigned int MEMPOOL_HEIGHT = 0x7FFFFFFF; -/** - * CTxMemPool stores these: +class CTxMemPool; + +/** \class CTxMemPoolEntry + * + * CTxMemPoolEntry stores data about the correponding transaction, as well + * as data about all in-mempool transactions that depend on the transaction + * ("descendant" transactions). + * + * When a new entry is added to the mempool, we update the descendant state + * (nCountWithDescendants, nSizeWithDescendants, and nFeesWithDescendants) for + * all ancestors of the newly added transaction. + * + * If updating the descendant state is skipped, we can mark the entry as + * "dirty", and set nSizeWithDescendants/nFeesWithDescendants to equal nTxSize/ + * nTxFee. (This can potentially happen during a reorg, where we limit the + * amount of work we're willing to do to avoid consuming too much CPU.) + * */ + class CTxMemPoolEntry { private: @@ -46,10 +67,18 @@ private: unsigned int nHeight; //! Chain height when entering the mempool bool hadNoDependencies; //! Not dependent on any other txs when it entered the mempool + // Information about descendants of this transaction that are in the + // mempool; if we remove this transaction we must remove all of these + // descendants as well. if nCountWithDescendants is 0, treat this entry as + // dirty, and nSizeWithDescendants and nFeesWithDescendants will not be + // correct. + uint64_t nCountWithDescendants; //! number of descendant transactions + uint64_t nSizeWithDescendants; //! ... and size + CAmount nFeesWithDescendants; //! ... and total fees (all including us) + public: CTxMemPoolEntry(const CTransaction& _tx, const CAmount& _nFee, int64_t _nTime, double _dPriority, unsigned int _nHeight, bool poolHasNoInputsOf = false); - CTxMemPoolEntry(); CTxMemPoolEntry(const CTxMemPoolEntry& other); const CTransaction& GetTx() const { return this->tx; } @@ -60,6 +89,98 @@ public: unsigned int GetHeight() const { return nHeight; } bool WasClearAtEntry() const { return hadNoDependencies; } size_t DynamicMemoryUsage() const { return nUsageSize; } + + // Adjusts the descendant state, if this entry is not dirty. + void UpdateState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount); + + /** We can set the entry to be dirty if doing the full calculation of in- + * mempool descendants will be too expensive, which can potentially happen + * when re-adding transactions from a block back to the mempool. + */ + void SetDirty(); + bool IsDirty() const { return nCountWithDescendants == 0; } + + uint64_t GetCountWithDescendants() const { return nCountWithDescendants; } + uint64_t GetSizeWithDescendants() const { return nSizeWithDescendants; } + CAmount GetFeesWithDescendants() const { return nFeesWithDescendants; } +}; + +// Helpers for modifying CTxMemPool::mapTx, which is a boost multi_index. +struct update_descendant_state +{ + update_descendant_state(int64_t _modifySize, CAmount _modifyFee, int64_t _modifyCount) : + modifySize(_modifySize), modifyFee(_modifyFee), modifyCount(_modifyCount) + {} + + void operator() (CTxMemPoolEntry &e) + { e.UpdateState(modifySize, modifyFee, modifyCount); } + + private: + int64_t modifySize; + CAmount modifyFee; + int64_t modifyCount; +}; + +struct set_dirty +{ + void operator() (CTxMemPoolEntry &e) + { e.SetDirty(); } +}; + +// extracts a TxMemPoolEntry's transaction hash +struct mempoolentry_txid +{ + typedef uint256 result_type; + result_type operator() (const CTxMemPoolEntry &entry) const + { + return entry.GetTx().GetHash(); + } +}; + +/** \class CompareTxMemPoolEntryByFee + * + * Sort an entry by max(feerate of entry's tx, feerate with all descendants). + */ +class CompareTxMemPoolEntryByFee +{ +public: + bool operator()(const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) + { + bool fUseADescendants = UseDescendantFeeRate(a); + bool fUseBDescendants = UseDescendantFeeRate(b); + + double aFees = fUseADescendants ? a.GetFeesWithDescendants() : a.GetFee(); + double aSize = fUseADescendants ? a.GetSizeWithDescendants() : a.GetTxSize(); + + double bFees = fUseBDescendants ? b.GetFeesWithDescendants() : b.GetFee(); + double bSize = fUseBDescendants ? b.GetSizeWithDescendants() : b.GetTxSize(); + + // Avoid division by rewriting (a/b > c/d) as (a*d > c*b). + double f1 = aFees * bSize; + double f2 = aSize * bFees; + + if (f1 == f2) { + return a.GetTime() < b.GetTime(); + } + return f1 > f2; + } + + // Calculate which feerate to use for an entry (avoiding division). + bool UseDescendantFeeRate(const CTxMemPoolEntry &a) + { + double f1 = (double)a.GetFee() * a.GetSizeWithDescendants(); + double f2 = (double)a.GetFeesWithDescendants() * a.GetTxSize(); + return f2 > f1; + } +}; + +class CompareTxMemPoolEntryByEntryTime +{ +public: + bool operator()(const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) + { + return a.GetTime() < b.GetTime(); + } }; class CBlockPolicyEstimator; @@ -87,6 +208,71 @@ public: * are added to the pool: if a new transaction double-spends * an input of a transaction in the pool, it is dropped, * as are non-standard transactions. + * + * CTxMemPool::mapTx, and CTxMemPoolEntry bookkeeping: + * + * mapTx is a boost::multi_index that sorts the mempool on 2 criteria: + * - transaction hash + * - feerate [we use max(feerate of tx, feerate of tx with all descendants)] + * + * Note: the term "descendant" refers to in-mempool transactions that depend on + * this one, while "ancestor" refers to in-mempool transactions that a given + * transaction depends on. + * + * In order for the feerate sort to remain correct, we must update transactions + * in the mempool when new descendants arrive. To facilitate this, we track + * the set of in-mempool direct parents and direct children in mapLinks. Within + * each CTxMemPoolEntry, we track the size and fees of all descendants. + * + * Usually when a new transaction is added to the mempool, it has no in-mempool + * children (because any such children would be an orphan). So in + * addUnchecked(), we: + * - update a new entry's setMemPoolParents to include all in-mempool parents + * - update the new entry's direct parents to include the new tx as a child + * - update all ancestors of the transaction to include the new tx's size/fee + * + * When a transaction is removed from the mempool, we must: + * - update all in-mempool parents to not track the tx in setMemPoolChildren + * - update all ancestors to not include the tx's size/fees in descendant state + * - update all in-mempool children to not include it as a parent + * + * These happen in UpdateForRemoveFromMempool(). (Note that when removing a + * transaction along with its descendants, we must calculate that set of + * transactions to be removed before doing the removal, or else the mempool can + * be in an inconsistent state where it's impossible to walk the ancestors of + * a transaction.) + * + * In the event of a reorg, the assumption that a newly added tx has no + * in-mempool children is false. In particular, the mempool is in an + * inconsistent state while new transactions are being added, because there may + * be descendant transactions of a tx coming from a disconnected block that are + * unreachable from just looking at transactions in the mempool (the linking + * transactions may also be in the disconnected block, waiting to be added). + * Because of this, there's not much benefit in trying to search for in-mempool + * children in addUnchecked(). Instead, in the special case of transactions + * being added from a disconnected block, we require the caller to clean up the + * state, to account for in-mempool, out-of-block descendants for all the + * in-block transactions by calling UpdateTransactionsFromBlock(). Note that + * until this is called, the mempool state is not consistent, and in particular + * mapLinks may not be correct (and therefore functions like + * CalculateMemPoolAncestors() and CalculateDescendants() that rely + * on them to walk the mempool are not generally safe to use). + * + * Computational limits: + * + * Updating all in-mempool ancestors of a newly added transaction can be slow, + * if no bound exists on how many in-mempool ancestors there may be. + * CalculateMemPoolAncestors() takes configurable limits that are designed to + * prevent these calculations from being too CPU intensive. + * + * Adding transactions from a disconnected block can be very time consuming, + * because we don't have a way to limit the number of in-mempool descendants. + * To bound CPU processing, we limit the amount of work we're willing to do + * to properly update the descendant information for a tx being added from + * a disconnected block. If we would exceed the limit, then we instead mark + * the entry as "dirty", and set the feerate for sorting purposes to be equal + * the feerate of the transaction without any descendants. + * */ class CTxMemPool { @@ -99,8 +285,46 @@ private: uint64_t cachedInnerUsage; //! sum of dynamic memory usage of all the map elements (NOT the maps themselves) public: + typedef boost::multi_index_container< + CTxMemPoolEntry, + boost::multi_index::indexed_by< + // sorted by txid + boost::multi_index::ordered_unique<mempoolentry_txid>, + // sorted by fee rate + boost::multi_index::ordered_non_unique< + boost::multi_index::identity<CTxMemPoolEntry>, + CompareTxMemPoolEntryByFee + > + > + > indexed_transaction_set; + mutable CCriticalSection cs; - std::map<uint256, CTxMemPoolEntry> mapTx; + indexed_transaction_set mapTx; + typedef indexed_transaction_set::nth_index<0>::type::iterator txiter; + struct CompareIteratorByHash { + bool operator()(const txiter &a, const txiter &b) const { + return a->GetTx().GetHash() < b->GetTx().GetHash(); + } + }; + typedef std::set<txiter, CompareIteratorByHash> setEntries; + +private: + typedef std::map<txiter, setEntries, CompareIteratorByHash> cacheMap; + + struct TxLinks { + setEntries parents; + setEntries children; + }; + + typedef std::map<txiter, TxLinks, CompareIteratorByHash> txlinksMap; + txlinksMap mapLinks; + + const setEntries & GetMemPoolParents(txiter entry) const; + const setEntries & GetMemPoolChildren(txiter entry) const; + void UpdateParent(txiter entry, txiter parent, bool add); + void UpdateChild(txiter entry, txiter child, bool add); + +public: std::map<COutPoint, CInPoint> mapNextTx; std::map<uint256, std::pair<double, CAmount> > mapDeltas; @@ -116,7 +340,13 @@ public: void check(const CCoinsViewCache *pcoins) const; void setSanityCheck(bool _fSanityCheck) { fSanityCheck = _fSanityCheck; } + // addUnchecked must updated state for all ancestors of a given transaction, + // to track size/count of descendant transactions. First version of + // addUnchecked can be used to have it call CalculateMemPoolAncestors(), and + // then invoke the second version. bool addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry, bool fCurrentEstimate = true); + bool addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry, setEntries &setAncestors, bool fCurrentEstimate = true); + void remove(const CTransaction &tx, std::list<CTransaction>& removed, bool fRecursive = false); void removeCoinbaseSpends(const CCoinsViewCache *pcoins, unsigned int nMemPoolHeight); void removeConflicts(const CTransaction &tx, std::list<CTransaction>& removed); @@ -138,6 +368,33 @@ public: void ApplyDeltas(const uint256 hash, double &dPriorityDelta, CAmount &nFeeDelta); void ClearPrioritisation(const uint256 hash); +public: + /** Remove a set of transactions from the mempool. + * If a transaction is in this set, then all in-mempool descendants must + * also be in the set.*/ + void RemoveStaged(setEntries &stage); + + /** When adding transactions from a disconnected block back to the mempool, + * new mempool entries may have children in the mempool (which is generally + * not the case when otherwise adding transactions). + * UpdateTransactionsFromBlock() will find child transactions and update the + * descendant state for each transaction in hashesToUpdate (excluding any + * child transactions present in hashesToUpdate, which are already accounted + * for). Note: hashesToUpdate should be the set of transactions from the + * disconnected block that have been accepted back into the mempool. + */ + void UpdateTransactionsFromBlock(const std::vector<uint256> &hashesToUpdate); + + /** Try to calculate all in-mempool ancestors of entry. + * (these are all calculated including the tx itself) + * limitAncestorCount = max number of ancestors + * limitAncestorSize = max size of ancestors + * limitDescendantCount = max number of descendants any ancestor can have + * limitDescendantSize = max size of descendants any ancestor can have + * errString = populated with error reason if any limits are hit + */ + bool CalculateMemPoolAncestors(const CTxMemPoolEntry &entry, setEntries &setAncestors, uint64_t limitAncestorCount, uint64_t limitAncestorSize, uint64_t limitDescendantCount, uint64_t limitDescendantSize, std::string &errString); + unsigned long size() { LOCK(cs); @@ -169,6 +426,48 @@ public: bool ReadFeeEstimates(CAutoFile& filein); size_t DynamicMemoryUsage() const; + +private: + /** UpdateForDescendants is used by UpdateTransactionsFromBlock to update + * the descendants for a single transaction that has been added to the + * mempool but may have child transactions in the mempool, eg during a + * chain reorg. setExclude is the set of descendant transactions in the + * mempool that must not be accounted for (because any descendants in + * setExclude were added to the mempool after the transaction being + * updated and hence their state is already reflected in the parent + * state). + * + * If updating an entry requires looking at more than maxDescendantsToVisit + * transactions, outside of the ones in setExclude, then give up. + * + * cachedDescendants will be updated with the descendants of the transaction + * being updated, so that future invocations don't need to walk the + * same transaction again, if encountered in another transaction chain. + */ + bool UpdateForDescendants(txiter updateIt, + int maxDescendantsToVisit, + cacheMap &cachedDescendants, + const std::set<uint256> &setExclude); + /** Update ancestors of hash to add/remove it as a descendant transaction. */ + void UpdateAncestorsOf(bool add, txiter hash, setEntries &setAncestors); + /** For each transaction being removed, update ancestors and any direct children. */ + void UpdateForRemoveFromMempool(const setEntries &entriesToRemove); + /** Sever link between specified transaction and direct children. */ + void UpdateChildrenForRemoval(txiter entry); + /** Populate setDescendants with all in-mempool descendants of hash. + * Assumes that setDescendants includes all in-mempool descendants of anything + * already in it. */ + void CalculateDescendants(txiter it, setEntries &setDescendants); + + /** Before calling removeUnchecked for a given transaction, + * UpdateForRemoveFromMempool must be called on the entire (dependent) set + * of transactions being removed at the same time. We use each + * CTxMemPoolEntry's setMemPoolParents in order to walk ancestors of a + * given transaction that is removed, so we can't remove intermediate + * transactions in a chain before we've updated all the state for the + * removal. + */ + void removeUnchecked(txiter entry); }; /** |