1 // libTorrent - BitTorrent library
2 // Copyright (C) 2005-2011, Jari Sundell
3 //
4 // This program is free software; you can redistribute it and/or modify
5 // it under the terms of the GNU General Public License as published by
6 // the Free Software Foundation; either version 2 of the License, or
7 // (at your option) any later version.
8 //
9 // This program is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 // GNU General Public License for more details.
13 //
14 // You should have received a copy of the GNU General Public License
15 // along with this program; if not, write to the Free Software
16 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 //
18 // In addition, as a special exception, the copyright holders give
19 // permission to link the code of portions of this program with the
20 // OpenSSL library under certain conditions as described in each
21 // individual source file, and distribute linked combinations
22 // including the two.
23 //
24 // You must obey the GNU General Public License in all respects for
25 // all of the code used other than OpenSSL. If you modify file(s)
26 // with this exception, you may extend this exception to your version
27 // of the file(s), but you are not obligated to do so. If you do not
28 // wish to do so, delete this exception statement from your version.
29 // If you delete this exception statement from all source files in the
30 // program, then also delete it here.
31 //
32 // Contact: Jari Sundell <jaris@ifi.uio.no>
33 //
34 // Skomakerveien 33
35 // 3185 Skoppum, NORWAY
36
37 #include "config.h"
38
39 #include "torrent/exceptions.h"
40 #include "torrent/object_stream.h"
41 #include "tracker/tracker_dht.h"
42
43 #include "dht_bucket.h"
44 #include "dht_transaction.h"
45
46 namespace torrent {
47
DhtSearch(const HashString & target,const DhtBucket & contacts)48 DhtSearch::DhtSearch(const HashString& target, const DhtBucket& contacts)
49 : base_type(dht_compare_closer(target)),
50 m_pending(0),
51 m_contacted(0),
52 m_replied(0),
53 m_concurrency(3),
54 m_restart(false),
55 m_started(false),
56 m_next(end()),
57 m_target(target) {
58
59 add_contacts(contacts);
60 }
61
~DhtSearch()62 DhtSearch::~DhtSearch() {
63 // Make sure transactions were destructed first. Since it is the destruction
64 // of a transaction that triggers this destructor, that should always be the
65 // case.
66 if (m_pending)
67 throw internal_error("DhtSearch::~DhtSearch called with pending transactions.");
68
69 if (m_concurrency != 3)
70 throw internal_error("DhtSearch::~DhtSearch with invalid concurrency limit.");
71
72 for (accessor itr = begin(); itr != end(); ++itr)
73 delete itr.node();
74 }
75
76 bool
add_contact(const HashString & id,const rak::socket_address * sa)77 DhtSearch::add_contact(const HashString& id, const rak::socket_address* sa) {
78 DhtNode* n = new DhtNode(id, sa);
79 bool added = insert(std::make_pair(n, this)).second;
80
81 if (!added)
82 delete n;
83 else
84 m_restart = true;
85
86 return added;
87 }
88
89 void
add_contacts(const DhtBucket & contacts)90 DhtSearch::add_contacts(const DhtBucket& contacts) {
91 DhtBucketChain chain(&contacts);
92
93 // Add max_contacts=18 closest nodes, and fill up so we also have at least 8 good nodes.
94 int needClosest = max_contacts - size();
95 int needGood = DhtBucket::num_nodes;
96
97 for (DhtBucket::const_iterator itr = chain.bucket()->begin(); needClosest > 0 || needGood > 0; ++itr) {
98 while (itr == chain.bucket()->end()) {
99 if (!chain.next())
100 return;
101
102 itr = chain.bucket()->begin();
103 }
104
105 if ((!(*itr)->is_bad() || needClosest > 0) && add_contact((*itr)->id(), (*itr)->address())) {
106 needGood -= !(*itr)->is_bad();
107 needClosest--;
108 }
109 }
110 }
111
112 // Check if a node has been contacted yet. This is the case if it is not currently
113 // being contacted, nor has it been found to be good or bad.
114 bool
node_uncontacted(const DhtNode * node) const115 DhtSearch::node_uncontacted(const DhtNode* node) const {
116 return !node->is_active() && !node->is_good() && !node->is_bad();
117 }
118
119 // After more contacts have been added, discard least closest nodes
120 // except if node has a transaction pending.
121 void
trim(bool final)122 DhtSearch::trim(bool final) {
123
124 // We keep:
125 // - the max_contacts=18 closest good or unknown nodes and all nodes closer
126 // than them (to see if further searches find closer ones)
127 // - for announces, also the 3 closest good nodes (i.e. nodes that have
128 // replied) to have at least that many for the actual announce
129 // - any node that currently has transactions pending
130 //
131 // However, after exhausting all search nodes, we only keep good nodes.
132 //
133 // For our purposes, the node status is as follows:
134 // node is bad (contacted but hasn't replied) if is_bad()
135 // node is good (contacted and replied) if is_good()
136 // node is currently being contacted if is_active()
137 // node is new and unknown otherwise
138
139 int needClosest = final ? 0 : max_contacts;
140 int needGood = is_announce() ? max_announce : 0;
141
142 // We're done if we can't find any more nodes to contact.
143 m_next = end();
144
145 for (accessor itr = base_type::begin(); itr != end(); ) {
146 // If we have all we need, delete current node unless it is
147 // currently being contacted.
148 if (!itr.node()->is_active() && needClosest <= 0 && (!itr.node()->is_good() || needGood <= 0)) {
149 delete itr.node();
150 erase(itr++);
151 continue;
152 }
153
154 // Otherwise adjust needed counts appropriately.
155 needClosest--;
156 needGood -= itr.node()->is_good();
157
158 // Remember the first uncontacted node as the closest one to contact next.
159 if (m_next == end() && node_uncontacted(itr.node()))
160 m_next = const_accessor(itr);
161
162 ++itr;
163 }
164
165 m_restart = false;
166 }
167
168 DhtSearch::const_accessor
get_contact()169 DhtSearch::get_contact() {
170 if (m_pending >= m_concurrency)
171 return end();
172
173 if (m_restart)
174 trim(false);
175
176 const_accessor ret = m_next;
177 if (ret == end())
178 return ret;
179
180 set_node_active(ret, true);
181 m_pending++;
182 m_contacted++;
183
184 // Find next node to contact: any node we haven't contacted yet.
185 while (++m_next != end()) {
186 if (node_uncontacted(m_next.node()))
187 break;
188 }
189
190 return ret;
191 }
192
193 void
node_status(const_accessor & n,bool success)194 DhtSearch::node_status(const_accessor& n, bool success) {
195 if (n == end() || !n.node()->is_active())
196 throw internal_error("DhtSearch::node_status called for invalid/inactive node.");
197
198 if (success) {
199 n.node()->set_good();
200 m_replied++;
201
202 } else {
203 n.node()->set_bad();
204 }
205
206 m_pending--;
207 set_node_active(n, false);
208 }
209
~DhtAnnounce()210 DhtAnnounce::~DhtAnnounce() {
211 if (!complete())
212 throw internal_error("DhtAnnounce::~DhtAnnounce called while announce not complete.");
213
214 const char* failure = NULL;
215
216 if (m_tracker->get_state() != TrackerDht::state_announcing) {
217 if (!m_contacted)
218 failure = "No DHT nodes available for peer search.";
219 else
220 failure = "DHT search unsuccessful.";
221
222 } else {
223 if (!m_contacted)
224 failure = "DHT search unsuccessful.";
225 else if (m_replied == 0 && !m_tracker->has_peers())
226 failure = "Announce failed";
227 }
228
229 if (failure != NULL)
230 m_tracker->receive_failed(failure);
231 else
232 m_tracker->receive_success();
233 }
234
235 DhtSearch::const_accessor
start_announce()236 DhtAnnounce::start_announce() {
237 trim(true);
238
239 if (empty())
240 return end();
241
242 if (!complete() || m_next != end() || size() > DhtBucket::num_nodes)
243 throw internal_error("DhtSearch::start_announce called in inconsistent state.");
244
245 m_contacted = m_pending = size();
246 m_replied = 0;
247 m_tracker->set_state(TrackerDht::state_announcing);
248
249 for (const_accessor itr(begin()); itr != end(); ++itr)
250 set_node_active(itr, true);
251
252 return const_accessor(begin());
253 }
254
255 void
build_buffer(const DhtMessage & msg)256 DhtTransactionPacket::build_buffer(const DhtMessage& msg) {
257 char buffer[1500]; // If the message would exceed an Ethernet frame, something went very wrong.
258 object_buffer_t result = static_map_write_bencode_c(object_write_to_buffer, NULL, std::make_pair(buffer, buffer + sizeof(buffer)), msg);
259
260 m_length = result.second - buffer;
261 m_data = new char[m_length];
262 memcpy(m_data, buffer, m_length);
263 }
264
DhtTransaction(int quick_timeout,int timeout,const HashString & id,const rak::socket_address * sa)265 DhtTransaction::DhtTransaction(int quick_timeout, int timeout, const HashString& id, const rak::socket_address* sa)
266 : m_id(id),
267 m_hasQuickTimeout(quick_timeout > 0),
268 m_sa(*sa),
269 m_timeout(cachedTime.seconds() + timeout),
270 m_quickTimeout(cachedTime.seconds() + quick_timeout),
271 m_packet(NULL) {
272
273 }
274
~DhtTransaction()275 DhtTransaction::~DhtTransaction() {
276 if (m_packet != NULL)
277 m_packet->set_failed();
278 }
279
280 void
set_stalled()281 DhtTransactionSearch::set_stalled() {
282 if (!m_hasQuickTimeout)
283 throw internal_error("DhtTransactionSearch::set_stalled called on already stalled transaction.");
284
285 m_hasQuickTimeout = false;
286 m_search->m_concurrency++;
287 }
288
289 void
complete(bool success)290 DhtTransactionSearch::complete(bool success) {
291 if (m_node == m_search->end())
292 throw internal_error("DhtTransactionSearch::complete called multiple times.");
293
294 if (m_node.search() != m_search)
295 throw internal_error("DhtTransactionSearch::complete called for node from wrong search.");
296
297 if (!m_hasQuickTimeout)
298 m_search->m_concurrency--;
299
300 m_search->node_status(m_node, success);
301 m_node = m_search->end();
302 }
303
~DhtTransactionSearch()304 DhtTransactionSearch::~DhtTransactionSearch() {
305 if (m_node != m_search->end())
306 complete(false);
307
308 if (m_search->complete())
309 delete m_search;
310 }
311
312 }
313