← Back to branch summary

~ubuntu-branches/ubuntu/maverick/libtorrent-rasterbar/maverick

« back to all changes in this revision

Viewing changes to src/kademlia/routing_table.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Christophe Sauthier
  • Date: 2010-08-10 12:59:37 UTC
  • mfrom: (1.3.7 upstream)
  • Revision ID: james.westby@ubuntu.com-20100810125937-jbcmmf17y8yo9hgz
Tags: 0.15.0-0ubuntu1
* New upstream version.
* debian/patches/100_fix_html_docs.patch: refreshed.
* debian/control: bump up standards-version to 3.9.1 (no changes).

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/kademlia/routing_table.cpp
33
33
#include "libtorrent/pch.hpp"
34
34
 
35
35
#include <vector>
36
 
#include <deque>
37
36
#include <algorithm>
38
37
#include <functional>
39
38
#include <numeric>
41
40
#include <boost/bind.hpp>
42
41
 
43
42
#include "libtorrent/kademlia/routing_table.hpp"
 
43
#include "libtorrent/session_status.hpp"
44
44
#include "libtorrent/kademlia/node_id.hpp"
45
45
#include "libtorrent/session_settings.hpp"
46
46
 
59
59
        : m_bucket_size(bucket_size)
60
60
        , m_settings(settings)
61
61
        , m_id(id)
 
62
        , m_last_bootstrap(min_time())
62
63
        , m_lowest_active_bucket(160)
63
64
{
64
65
        // distribute the refresh times for the buckets in an
65
 
        // attempt do even out the network load
 
66
        // attempt to even out the network load
66
67
        for (int i = 0; i < 160; ++i)
67
68
                m_bucket_activity[i] = time_now() - milliseconds(i*5625);
68
69
        m_bucket_activity[0] = time_now() - minutes(15);
69
70
}
70
71
 
 
72
void routing_table::status(session_status& s) const
 
73
{
 
74
        boost::tie(s.dht_nodes, s.dht_node_cache) = size();
 
75
        s.dht_global_nodes = num_global_nodes();
 
76
}
 
77
 
71
78
boost::tuple<int, int> routing_table::size() const
72
79
{
73
80
        int nodes = 0;
142
149
        for (table_t::const_iterator i = m_buckets.begin(), end(m_buckets.end());
143
150
                i != end; ++i)
144
151
        {
 
152
                if (i->first.empty()) continue;
145
153
                int bucket_index = int(i - m_buckets.begin());
146
154
                os << "=== BUCKET = " << bucket_index
147
155
                        << " = " << (bucket_index >= m_lowest_active_bucket?"active":"inactive")
148
156
                        << " = " << total_seconds(time_now() - m_bucket_activity[bucket_index])
149
 
                        << " s ago ===== \n";
 
157
                        << " seconds ago ===== \n";
150
158
                for (bucket_t::const_iterator j = i->first.begin()
151
159
                        , end(i->first.end()); j != end; ++j)
152
160
                {
153
 
                        os << "ip: " << j->addr << "    fails: " << j->fail_count
154
 
                                << "    id: " << j->id << "\n";
 
161
                        os << " id: " << j->id
 
162
                                << " ip: " << j->ep()
 
163
                                << " fails: " << j->fail_count()
 
164
                                << " pinged: " << j->pinged()
 
165
                                << "\n";
155
166
                }
156
167
        }
157
168
}
184
195
        }
185
196
}
186
197
 
187
 
bool routing_table::need_node(node_id const& id)
 
198
void routing_table::heard_about(node_id const& id, udp::endpoint const& ep)
188
199
{
189
200
        int bucket_index = distance_exp(m_id, id);
190
201
        TORRENT_ASSERT(bucket_index < (int)m_buckets.size());
195
206
        // if the replacement cache is full, we don't
196
207
        // need another node. The table is fine the
197
208
        // way it is.
198
 
        if ((int)rb.size() >= m_bucket_size) return false;
 
209
        if ((int)rb.size() >= m_bucket_size) return;
199
210
        
200
211
        // if the node already exists, we don't need it
201
212
        if (std::find_if(b.begin(), b.end(), bind(&node_entry::id, _1) == id)
202
 
                != b.end()) return false;
 
213
                != b.end()) return;
203
214
 
204
215
        if (std::find_if(rb.begin(), rb.end(), bind(&node_entry::id, _1) == id)
205
 
                != rb.end()) return false;
206
 
 
207
 
        return true;
 
216
                != rb.end()) return;
 
217
 
 
218
        if (b.size() < m_bucket_size)
 
219
        {
 
220
                if (bucket_index < m_lowest_active_bucket
 
221
                        && bucket_index > 0)
 
222
                        m_lowest_active_bucket = bucket_index;
 
223
                b.push_back(node_entry(id, ep, false));
 
224
                return;
 
225
        }
 
226
 
 
227
        if (rb.size() < m_bucket_size)
 
228
                rb.push_back(node_entry(id, ep, false));
208
229
}
209
230
 
210
231
void routing_table::node_failed(node_id const& id)
225
246
 
226
247
        if (rb.empty())
227
248
        {
228
 
                ++i->fail_count;
 
249
                i->timed_out();
229
250
 
230
251
#ifdef TORRENT_DHT_VERBOSE_LOGGING
231
252
                TORRENT_LOG(table) << " NODE FAILED"
232
253
                        " id: " << id <<
233
 
                        " ip: " << i->addr <<
234
 
                        " fails: " << i->fail_count <<
 
254
                        " ip: " << i->ep() <<
 
255
                        " fails: " << i->fail_count() <<
 
256
                        " pinged: " << i->pinged() <<
235
257
                        " up-time: " << total_seconds(time_now() - i->first_seen);
236
258
#endif
237
259
 
238
 
                if (i->fail_count >= m_settings.max_fail_count)
 
260
                // if this node has failed too many times, or if this node
 
261
                // has never responded at all, remove it
 
262
                if (i->fail_count() >= m_settings.max_fail_count || !i->pinged())
239
263
                {
240
264
                        b.erase(i);
241
265
                        TORRENT_ASSERT(m_lowest_active_bucket <= bucket_index);
249
273
        }
250
274
 
251
275
        b.erase(i);
252
 
        b.push_back(rb.back());
253
 
        rb.erase(rb.end() - 1);
 
276
 
 
277
        i = std::find_if(rb.begin(), rb.end(), bind(&node_entry::pinged, _1) == true);
 
278
        if (i == rb.end()) i = rb.begin();
 
279
        b.push_back(*i);
 
280
        rb.erase(i);
254
281
}
255
282
 
256
283
void routing_table::add_router_node(udp::endpoint router)
282
309
 
283
310
        if (i != b.end())
284
311
        {
285
 
                // TODO: what do we do if we see a node with
286
 
                // the same id as a node at a different address?
287
 
//              TORRENT_ASSERT(i->addr == addr);
288
 
 
289
312
                // we already have the node in our bucket
290
313
                // just move it to the back since it was
291
314
                // the last node we had any contact with
292
315
                // in this bucket
293
 
                b.erase(i);
294
 
                b.push_back(node_entry(id, addr));
295
 
//              TORRENT_LOG(table) << "replacing node: " << id << " " << addr;
 
316
                i->set_pinged();
 
317
                i->reset_fail_count();
 
318
                i->addr = addr.address();
 
319
                i->port = addr.port();
 
320
//              TORRENT_LOG(table) << "updating node: " << id << " " << addr;
296
321
                return ret;
297
322
        }
298
323
 
303
328
        if ((int)b.size() < m_bucket_size)
304
329
        {
305
330
                if (b.empty()) b.reserve(m_bucket_size);
306
 
                b.push_back(node_entry(id, addr));
 
331
                b.push_back(node_entry(id, addr, true));
307
332
                // if bucket index is 0, the node is ourselves
308
333
                // don't updated m_lowest_active_bucket
309
334
                if (bucket_index < m_lowest_active_bucket
313
338
                return ret;
314
339
        }
315
340
 
316
 
        // if there is no room, we look for nodes marked as stale
 
341
        // if there is no room, we look for nodes that are not 'pinged',
 
342
        // i.e. we haven't confirmed that they respond to messages.
 
343
        // Then we look for nodes marked as stale
317
344
        // in the k-bucket. If we find one, we can replace it.
 
345
        
 
346
        i = std::find_if(b.begin(), b.end(), bind(&node_entry::pinged, _1) == false);
 
347
 
 
348
        if (i != b.end() && !i->pinged())
 
349
        {
 
350
                // i points to a node that has not been pinged.
 
351
                // Replace it with this new one
 
352
                b.erase(i);
 
353
                b.push_back(node_entry(id, addr, true));
 
354
//              TORRENT_LOG(table) << "replacing unpinged node: " << id << " " << addr;
 
355
                return ret;
 
356
        }
 
357
 
318
358
        // A node is considered stale if it has failed at least one
319
359
        // time. Here we choose the node that has failed most times.
320
360
        // If we don't find one, place this node in the replacement-
325
365
                , bind(&node_entry::fail_count, _1)
326
366
                < bind(&node_entry::fail_count, _2));
327
367
 
328
 
        if (i != b.end() && i->fail_count > 0)
 
368
        if (i != b.end() && i->fail_count() > 0)
329
369
        {
330
370
                // i points to a node that has been marked
331
371
                // as stale. Replace it with this new one
332
372
                b.erase(i);
333
 
                b.push_back(node_entry(id, addr));
 
373
                b.push_back(node_entry(id, addr, true));
334
374
//              TORRENT_LOG(table) << "replacing stale node: " << id << " " << addr;
335
375
                return ret;
336
376
        }
347
387
 
348
388
        // if the node is already in the replacement bucket
349
389
        // just return.
350
 
        if (i != rb.end()) return ret;
 
390
        if (i != rb.end())
 
391
        {
 
392
                // make sure we mark this node as pinged
 
393
                // and if its address has changed, update
 
394
                // that as well
 
395
                i->set_pinged();
 
396
                i->reset_fail_count();
 
397
                i->addr = addr.address();
 
398
                i->port = addr.port();
 
399
                return ret;
 
400
        }
351
401
        
352
 
        if ((int)rb.size() > m_bucket_size) rb.erase(rb.begin());
 
402
        if ((int)rb.size() >= m_bucket_size)
 
403
        {
 
404
                // if the replacement bucket is full, remove the oldest entry
 
405
                // but prefer nodes that haven't been pinged, since they are
 
406
                // less reliable than this one, that has been pinged
 
407
                i = std::find_if(rb.begin(), rb.end(), bind(&node_entry::pinged, _1) == false);
 
408
                rb.erase(i != rb.end() ? i : rb.begin());
 
409
        }
353
410
        if (rb.empty()) rb.reserve(m_bucket_size);
354
 
        rb.push_back(node_entry(id, addr));
 
411
        rb.push_back(node_entry(id, addr, true));
355
412
//      TORRENT_LOG(table) << "inserting node in replacement cache: " << id << " " << addr;
356
413
        return ret;
357
414
}
358
415
 
359
416
bool routing_table::need_bootstrap() const
360
417
{
 
418
        ptime now = time_now();
 
419
        if (now - m_last_bootstrap < seconds(30)) return false;
 
420
 
361
421
        for (const_iterator i = begin(); i != end(); ++i)
362
422
        {
363
 
                if (i->fail_count == 0) return false;
 
423
                if (i->confirmed()) return false;
364
424
        }
 
425
        m_last_bootstrap = now;
365
426
        return true;
366
427
}
367
428
 
378
439
        return target;
379
440
}
380
441
 
 
442
template <class SrcIter, class DstIter>
 
443
DstIter copy_n(SrcIter begin, SrcIter end, DstIter target, size_t n)
 
444
{
 
445
        for (; n > 0 && begin != end; ++begin)
 
446
        {
 
447
                *target = *begin;
 
448
                --n;
 
449
                ++target;
 
450
        }
 
451
        return target;
 
452
}
 
453
 
381
454
// fills the vector with the k nodes from our buckets that
382
455
// are nearest to the given id.
383
456
void routing_table::find_node(node_id const& target
384
 
        , std::vector<node_entry>& l, bool include_self, int count)
 
457
        , std::vector<node_entry>& l, int options, int count)
385
458
{
386
459
        l.clear();
387
460
        if (count == 0) count = m_bucket_size;
392
465
 
393
466
        // copy all nodes that hasn't failed into the target
394
467
        // vector.
395
 
        copy_if_n(b.begin(), b.end(), std::back_inserter(l)
396
 
                , (std::min)(size_t(count), b.size()), bind(&node_entry::fail_count, _1) == 0);
 
468
        if (options & include_failed)
 
469
        {
 
470
                copy_n(b.begin(), b.end(), std::back_inserter(l)
 
471
                        , (std::min)(size_t(count), b.size()));
 
472
        }
 
473
        else
 
474
        {
 
475
                copy_if_n(b.begin(), b.end(), std::back_inserter(l)
 
476
                        , (std::min)(size_t(count), b.size())
 
477
                        , bind(&node_entry::confirmed, _1));
 
478
        }
397
479
        TORRENT_ASSERT((int)l.size() <= count);
398
480
 
399
 
        if ((int)l.size() == count)
 
481
        if (int(l.size()) == count)
400
482
        {
401
 
                TORRENT_ASSERT(std::count_if(l.begin(), l.end()
402
 
                        , boost::bind(&node_entry::fail_count, _1) != 0) == 0);
 
483
                TORRENT_ASSERT((options & include_failed)
 
484
                        || std::count_if(l.begin(), l.end()
 
485
                        , !boost::bind(&node_entry::confirmed, _1)) == 0);
403
486
                return;
404
487
        }
405
488
 
409
492
        // [0, bucket_index) if we are to include ourself
410
493
        // or [1, bucket_index) if not.
411
494
        bucket_t tmpb;
412
 
        for (int i = include_self?0:1; i < bucket_index; ++i)
 
495
        for (int i = (options & include_self)?0:1; i < bucket_index; ++i)
413
496
        {
414
497
                bucket_t& b = m_buckets[i].first;
415
 
                std::remove_copy_if(b.begin(), b.end(), std::back_inserter(tmpb)
416
 
                        , bind(&node_entry::fail_count, _1));
 
498
                if (options & include_failed)
 
499
                {
 
500
                        copy(b.begin(), b.end(), std::back_inserter(tmpb));
 
501
                }
 
502
                else
 
503
                {
 
504
                        std::remove_copy_if(b.begin(), b.end(), std::back_inserter(tmpb)
 
505
                                , !bind(&node_entry::confirmed, _1));
 
506
                }
417
507
        }
418
508
 
419
509
        if (count - l.size() < tmpb.size())
432
522
        // return if we have enough nodes or if the bucket index
433
523
        // is the biggest index available (there are no more buckets)
434
524
        // to look in.
435
 
        if ((int)l.size() == count)
 
525
        if (int(l.size()) == count)
436
526
        {
437
 
                TORRENT_ASSERT(std::count_if(l.begin(), l.end()
438
 
                        , boost::bind(&node_entry::fail_count, _1) != 0) == 0);
 
527
                TORRENT_ASSERT((options & include_failed)
 
528
                        || std::count_if(l.begin(), l.end()
 
529
                                , !boost::bind(&node_entry::confirmed, _1)) == 0);
439
530
                return;
440
531
        }
441
532
 
444
535
                bucket_t& b = m_buckets[i].first;
445
536
        
446
537
                size_t to_copy = (std::min)(count - l.size(), b.size());
447
 
                copy_if_n(b.begin(), b.end(), std::back_inserter(l)
448
 
                        , to_copy, bind(&node_entry::fail_count, _1) == 0);
 
538
                if (options & include_failed)
 
539
                {
 
540
                        copy_n(b.begin(), b.end(), std::back_inserter(l), to_copy);
 
541
                }
 
542
                else
 
543
                {
 
544
                        copy_if_n(b.begin(), b.end(), std::back_inserter(l)
 
545
                                , to_copy, bind(&node_entry::confirmed, _1));
 
546
                }
449
547
                TORRENT_ASSERT((int)l.size() <= count);
450
 
                if ((int)l.size() == count)
 
548
                if (int(l.size()) == count)
451
549
                {
452
 
                        TORRENT_ASSERT(std::count_if(l.begin(), l.end()
453
 
                                , boost::bind(&node_entry::fail_count, _1) != 0) == 0);
 
550
                        TORRENT_ASSERT((options & include_failed)
 
551
                                || std::count_if(l.begin(), l.end()
 
552
                                        , !boost::bind(&node_entry::confirmed, _1)) == 0);
454
553
                        return;
455
554
                }
456
555
        }
457
556
        TORRENT_ASSERT((int)l.size() <= count);
458
557
 
459
 
        TORRENT_ASSERT(std::count_if(l.begin(), l.end()
460
 
                , boost::bind(&node_entry::fail_count, _1) != 0) == 0);
 
558
        TORRENT_ASSERT((options & include_failed)
 
559
                || std::count_if(l.begin(), l.end()
 
560
                        , !boost::bind(&node_entry::confirmed, _1)) == 0);
461
561
}
462
562
 
463
563
routing_table::iterator routing_table::begin() const