libtorrent/src/metadata_transfer.cpp

   1 /*
   2
   3 Copyright (c) 2006, Arvid Norberg
   4 All rights reserved.
   5
   6 Redistribution and use in source and binary forms, with or without
   7 modification, are permitted provided that the following conditions
   8 are met:
   9
  10     * Redistributions of source code must retain the above copyright
  11       notice, this list of conditions and the following disclaimer.
  12     * Redistributions in binary form must reproduce the above copyright
  13       notice, this list of conditions and the following disclaimer in
  14       the documentation and/or other materials provided with the distribution.
  15     * Neither the name of the author nor the names of its
  16       contributors may be used to endorse or promote products derived
  17       from this software without specific prior written permission.
  18
  19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  22 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  23 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  24 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  25 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  26 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  27 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  28 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  29 POSSIBILITY OF SUCH DAMAGE.
  30
  31 */
  32
  33 #include "libtorrent/pch.hpp"
  34
  35 #ifdef _MSC_VER
  36 #pragma warning(push, 1)
  37 #endif
  38
  39 #include <boost/shared_ptr.hpp>
  40 #include <boost/lexical_cast.hpp>
  41
  42 #ifdef _MSC_VER
  43 #pragma warning(pop)
  44 #endif
  45
  46 #include <vector>
  47 #include <utility>
  48 #include <numeric>
  49
  50 #include "libtorrent/peer_connection.hpp"
  51 #include "libtorrent/bt_peer_connection.hpp"
  52 #include "libtorrent/hasher.hpp"
  53 #include "libtorrent/bencode.hpp"
  54 #include "libtorrent/torrent.hpp"
  55 #include "libtorrent/extensions.hpp"
  56 #include "libtorrent/extensions/metadata_transfer.hpp"
  57 #include "libtorrent/alert_types.hpp"
  58 #include "libtorrent/buffer.hpp"
  59
  60 namespace libtorrent { namespace
  61 {
  62         int div_round_up(int numerator, int denominator)
  63         {
  64                 return (numerator + denominator - 1) / denominator;
  65         }
  66
  67         std::pair<int, int> req_to_offset(std::pair<int, int> req, int total_size)
  68         {
  69                 TORRENT_ASSERT(req.first >= 0);
  70                 TORRENT_ASSERT(req.second > 0);
  71                 TORRENT_ASSERT(req.second <= 256);
  72                 TORRENT_ASSERT(req.first + req.second <= 256);
  73
  74                 int start = div_round_up(req.first * total_size, 256);
  75                 int size = div_round_up((req.first + req.second) * total_size, 256) - start;
  76                 return std::make_pair(start, size);
  77         }
  78
  79         std::pair<int, int> offset_to_req(std::pair<int, int> offset, int total_size)
  80         {
  81                 int start = offset.first * 256 / total_size;
  82                 int size = (offset.first + offset.second) * 256 / total_size - start;
  83
  84                 std::pair<int, int> ret(start, size);
  85
  86                 TORRENT_ASSERT(start >= 0);
  87                 TORRENT_ASSERT(size > 0);
  88                 TORRENT_ASSERT(start <= 256);
  89                 TORRENT_ASSERT(start + size <= 256);
  90
  91                 // assert the identity of this function
  92 #ifndef NDEBUG
  93                 std::pair<int, int> identity = req_to_offset(ret, total_size);
  94                 TORRENT_ASSERT(offset == identity);
  95 #endif
  96                 return ret;
  97         }
  98
  99         struct metadata_plugin : torrent_plugin
 100         {
 101                 metadata_plugin(torrent& t)
 102                         : m_torrent(t)
 103                         , m_metadata_progress(0)
 104                         , m_metadata_size(0)
 105                 {
 106                         m_requested_metadata.resize(256, 0);
 107                 }
 108
 109                 virtual void on_files_checked()
 110                 {
 111                         // if the torrent is a seed, make a reference to
 112                         // the metadata from the torrent before it is deallocated
 113                         if (m_torrent.is_seed()) metadata();
 114                 }
 115
 116                 virtual boost::shared_ptr<peer_plugin> new_connection(
 117                         peer_connection* pc);
 118
 119                 buffer::const_interval metadata() const
 120                 {
 121                         if (!m_metadata)
 122                         {
 123                                 m_metadata = m_torrent.torrent_file().metadata();
 124                                 m_metadata_size = m_torrent.torrent_file().metadata_size();
 125                                 TORRENT_ASSERT(hasher(m_metadata.get(), m_metadata_size).final()
 126                                         == m_torrent.torrent_file().info_hash());
 127                         }
 128                         return buffer::const_interval(m_metadata.get(), m_metadata.get()
 129                                 + m_metadata_size);
 130                 }
 131
 132                 bool received_metadata(char const* buf, int size, int offset, int total_size)
 133                 {
 134                         if (m_torrent.valid_metadata()) return false;
 135
 136                         if (!m_metadata || m_metadata_size < total_size)
 137                         {
 138                                 m_metadata.reset(new char[total_size]);
 139                                 m_metadata_size = total_size;
 140                         }
 141                         std::copy(buf, buf + size, &m_metadata[offset]);
 142
 143                         if (m_have_metadata.empty())
 144                                 m_have_metadata.resize(256, false);
 145
 146                         std::pair<int, int> req = offset_to_req(std::make_pair(offset, size)
 147                                 , total_size);
 148
 149                         TORRENT_ASSERT(req.first + req.second <= (int)m_have_metadata.size());
 150
 151                         std::fill(
 152                                 m_have_metadata.begin() + req.first
 153                                 , m_have_metadata.begin() + req.first + req.second
 154                                 , true);
 155
 156                         bool have_all = std::count(
 157                                 m_have_metadata.begin()
 158                                 , m_have_metadata.end()
 159                                 , true) == 256;
 160
 161                         if (!have_all) return false;
 162
 163                         if (!m_torrent.set_metadata(&m_metadata[0], m_metadata_size))
 164                         {
 165                                 std::fill(
 166                                         m_have_metadata.begin()
 167                                         , m_have_metadata.begin() + req.first + req.second
 168                                         , false);
 169                                 m_metadata_progress = 0;
 170                                 m_metadata_size = 0;
 171                                 return false;
 172                         }
 173
 174                         // clear the storage for the bitfield
 175                         std::vector<bool>().swap(m_have_metadata);
 176                         std::vector<int>().swap(m_requested_metadata);
 177
 178                         return true;
 179                 }
 180
 181                 // returns a range of the metadata that
 182                 // we should request.
 183                 std::pair<int, int> metadata_request();
 184
 185                 void cancel_metadata_request(std::pair<int, int> req)
 186                 {
 187                         for (int i = req.first; i < req.first + req.second; ++i)
 188                         {
 189                                 TORRENT_ASSERT(m_requested_metadata[i] > 0);
 190                                 if (m_requested_metadata[i] > 0)
 191                                         --m_requested_metadata[i];
 192                         }
 193                 }
 194
 195                 // this is called from the peer_connection for
 196                 // each piece of metadata it receives
 197                 void metadata_progress(int total_size, int received)
 198                 {
 199                         m_metadata_progress += received;
 200                         m_metadata_size = total_size;
 201                 }
 202
 203                 void on_piece_pass(int)
 204                 {
 205                         // if we became a seed, copy the metadata from
 206                         // the torrent before it is deallocated
 207                         if (m_torrent.is_seed())
 208                                 metadata();
 209                 }
 210
 211         private:
 212                 torrent& m_torrent;
 213
 214                 // this buffer is filled with the info-section of
 215                 // the metadata file while downloading it from
 216                 // peers, and while sending it.
 217                 // it is mutable because it's generated lazily
 218                 mutable boost::shared_array<char> m_metadata;
 219
 220                 int m_metadata_progress;
 221                 mutable int m_metadata_size;
 222
 223                 // this is a bitfield of size 256, each bit represents
 224                 // a piece of the metadata. It is set to one if we
 225                 // have that piece. This vector may be empty
 226                 // (size 0) if we haven't received any metadata
 227                 // or if we already have all metadata
 228                 std::vector<bool> m_have_metadata;
 229                 // this vector keeps track of how many times each meatdata
 230                 // block has been requested
 231                 std::vector<int> m_requested_metadata;
 232         };
 233
 234
 235         struct metadata_peer_plugin : peer_plugin
 236         {
 237                 metadata_peer_plugin(torrent& t, peer_connection& pc
 238                         , metadata_plugin& tp)
 239                         : m_waiting_metadata_request(false)
 240                         , m_message_index(0)
 241                         , m_metadata_progress(0)
 242                         , m_no_metadata(min_time())
 243                         , m_metadata_request(min_time())
 244                         , m_torrent(t)
 245                         , m_pc(pc)
 246                         , m_tp(tp)
 247                 {}
 248
 249                 // can add entries to the extension handshake
 250                 virtual void add_handshake(entry& h)
 251                 {
 252                         entry& messages = h["m"];
 253                         messages["LT_metadata"] = 14;
 254                 }
 255
 256                 // called when the extension handshake from the other end is received
 257                 virtual bool on_extension_handshake(lazy_entry const& h)
 258                 {
 259                         m_message_index = 0;
 260                         if (h.type() != lazy_entry::dict_t) return false;
 261                         lazy_entry const* messages = h.dict_find("m");
 262                         if (!messages || messages->type() != lazy_entry::dict_t) return false;
 263
 264                         int index = messages->dict_find_int_value("LT_metadata", -1);
 265                         if (index == -1) return false;
 266                         m_message_index = index;
 267                         return true;
 268                 }
 269
 270                 void write_metadata_request(std::pair<int, int> req)
 271                 {
 272                         TORRENT_ASSERT(req.first >= 0);
 273                         TORRENT_ASSERT(req.second > 0);
 274                         TORRENT_ASSERT(req.first + req.second <= 256);
 275                         TORRENT_ASSERT(!m_pc.associated_torrent().expired());
 276                         TORRENT_ASSERT(!m_pc.associated_torrent().lock()->valid_metadata());
 277
 278                         int start = req.first;
 279                         int size = req.second;
 280
 281                         // abort if the peer doesn't support the metadata extension
 282                         if (m_message_index == 0) return;
 283
 284 #ifdef TORRENT_VERBOSE_LOGGING
 285                         (*m_pc.m_logger) << time_now_string()
 286                                 << " ==> METADATA_REQUEST  [ start: " << start << " | size: " << size << " ]\n";
 287 #endif
 288
 289                         buffer::interval i = m_pc.allocate_send_buffer(9);
 290
 291                         detail::write_uint32(1 + 1 + 3, i.begin);
 292                         detail::write_uint8(bt_peer_connection::msg_extended, i.begin);
 293                         detail::write_uint8(m_message_index, i.begin);
 294                         // means 'request data'
 295                         detail::write_uint8(0, i.begin);
 296                         detail::write_uint8(start, i.begin);
 297                         detail::write_uint8(size - 1, i.begin);
 298                         TORRENT_ASSERT(i.begin == i.end);
 299                         m_pc.setup_send();
 300                 }
 301
 302                 void write_metadata(std::pair<int, int> req)
 303                 {
 304                         TORRENT_ASSERT(req.first >= 0);
 305                         TORRENT_ASSERT(req.second > 0);
 306                         TORRENT_ASSERT(req.second <= 256);
 307                         TORRENT_ASSERT(req.first + req.second <= 256);
 308                         TORRENT_ASSERT(!m_pc.associated_torrent().expired());
 309
 310                         // abort if the peer doesn't support the metadata extension
 311                         if (m_message_index == 0) return;
 312
 313                         // only send metadata if the torrent is non-private
 314                         if (m_torrent.valid_metadata() && !m_torrent.torrent_file().priv())
 315                         {
 316                                 std::pair<int, int> offset
 317                                         = req_to_offset(req, (int)m_tp.metadata().left());
 318
 319                                 // TODO: don't allocate send buffer for the metadata part
 320                                 // just tag it on as a separate buffer like ut_metadata
 321                                 buffer::interval i = m_pc.allocate_send_buffer(15 + offset.second);
 322
 323 #ifdef TORRENT_VERBOSE_LOGGING
 324                                 (*m_pc.m_logger) << time_now_string()
 325                                         << " ==> METADATA [ start: " << req.first
 326                                         << " | size: " << req.second
 327                                         << " | offset: " << offset.first
 328                                         << " | byte_size: " << offset.second
 329                                         << " ]\n";
 330 #endif
 331                                 // yes, we have metadata, send it
 332                                 detail::write_uint32(11 + offset.second, i.begin);
 333                                 detail::write_uint8(bt_peer_connection::msg_extended, i.begin);
 334                                 detail::write_uint8(m_message_index, i.begin);
 335                                 // means 'data packet'
 336                                 detail::write_uint8(1, i.begin);
 337                                 detail::write_uint32((int)m_tp.metadata().left(), i.begin);
 338                                 detail::write_uint32(offset.first, i.begin);
 339                                 char const* metadata = m_tp.metadata().begin;
 340                                 std::copy(metadata + offset.first
 341                                         , metadata + offset.first + offset.second, i.begin);
 342                                 i.begin += offset.second;
 343                                 TORRENT_ASSERT(i.begin == i.end);
 344                         }
 345                         else
 346                         {
 347 #ifdef TORRENT_VERBOSE_LOGGING
 348                                 (*m_pc.m_logger) << time_now_string()
 349                                         << " ==> DONT HAVE METADATA\n";
 350 #endif
 351                                 buffer::interval i = m_pc.allocate_send_buffer(4 + 3);
 352                                 // we don't have the metadata, reply with
 353                                 // don't have-message
 354                                 detail::write_uint32(1 + 2, i.begin);
 355                                 detail::write_uint8(bt_peer_connection::msg_extended, i.begin);
 356                                 detail::write_uint8(m_message_index, i.begin);
 357                                 // means 'have no data'
 358                                 detail::write_uint8(2, i.begin);
 359                                 TORRENT_ASSERT(i.begin == i.end);
 360                         }
 361                         m_pc.setup_send();
 362                 }
 363
 364                 virtual bool on_extended(int length
 365                         , int msg, buffer::const_interval body)
 366                 {
 367                         if (msg != 14) return false;
 368                         if (m_message_index == 0) return false;
 369
 370                         if (length > 500 * 1024)
 371                         {
 372                                 m_pc.disconnect("LT_metadata message larger than 500 kB");
 373                                 return true;
 374                         }
 375
 376                         if (body.left() < 1) return true;
 377                         int type = detail::read_uint8(body.begin);
 378
 379                         switch (type)
 380                         {
 381                         case 0: // request
 382                                 {
 383                                         if (body.left() < 2) return true;
 384                                         int start = detail::read_uint8(body.begin);
 385                                         int size = detail::read_uint8(body.begin) + 1;
 386
 387 #ifdef TORRENT_VERBOSE_LOGGING
 388                                         (*m_pc.m_logger) << time_now_string()
 389                                                 << " <== METADATA_REQUEST [ start: " << start
 390                                                 << " | size: " << size
 391                                                 << " ]\n";
 392 #endif
 393
 394                                         if (length != 3)
 395                                         {
 396                                                 // invalid metadata request
 397                                                 m_pc.disconnect("invalid metadata request");
 398                                                 return true;
 399                                         }
 400
 401                                         write_metadata(std::make_pair(start, size));
 402                                 }
 403                                 break;
 404                         case 1: // data
 405                                 {
 406                                         if (body.left() < 8) return true;
 407
 408                                         int total_size = detail::read_int32(body.begin);
 409                                         int offset = detail::read_int32(body.begin);
 410                                         int data_size = length - 9;
 411
 412 #ifdef TORRENT_VERBOSE_LOGGING
 413                                         (*m_pc.m_logger) << time_now_string()
 414                                                 << " <== METADATA [ total_size: " << total_size
 415                                                 << " | offset: " << offset
 416                                                 << " | data_size: " << data_size
 417                                                 << " ]\n";
 418 #endif
 419
 420                                         if (total_size > 500 * 1024)
 421                                         {
 422                                                 m_pc.disconnect("metadata size larger than 500 kB");
 423                                                 return true;
 424                                         }
 425                                         if (total_size <= 0)
 426                                         {
 427                                                 m_pc.disconnect("invalid metadata size");
 428                                                 return true;
 429                                         }
 430                                         if (offset > total_size || offset < 0)
 431                                         {
 432                                                 m_pc.disconnect("invalid metadata offset");
 433                                                 return true;
 434                                         }
 435                                         if (offset + data_size > total_size)
 436                                         {
 437                                                 m_pc.disconnect("invalid metadata message");
 438                                                 return true;
 439                                         }
 440
 441                                         m_tp.metadata_progress(total_size
 442                                                 , body.left() - m_metadata_progress);
 443                                         m_metadata_progress = body.left();
 444
 445                                         if (body.left() < data_size) return true;
 446
 447                                         m_waiting_metadata_request = false;
 448                                         m_tp.received_metadata(body.begin, data_size
 449                                                 , offset, total_size);
 450                                         m_metadata_progress = 0;
 451                                 }
 452                                 break;
 453                         case 2: // have no data
 454                                 m_no_metadata = time_now();
 455                                 if (m_waiting_metadata_request)
 456                                         m_tp.cancel_metadata_request(m_last_metadata_request);
 457                                 m_waiting_metadata_request = false;
 458 #ifdef TORRENT_VERBOSE_LOGGING
 459                                 (*m_pc.m_logger) << time_now_string()
 460                                         << " <== DONT HAVE METADATA\n";
 461 #endif
 462                                 break;
 463                         default:
 464                                 {
 465                                         std::stringstream msg;
 466                                         msg << "unknown metadata extension message: " << type;
 467                                         m_pc.disconnect(msg.str().c_str());
 468                                 }
 469                         }
 470                         return true;
 471                 }
 472
 473                 virtual void tick()
 474                 {
 475                         // if we don't have any metadata, and this peer
 476                         // supports the request metadata extension
 477                         // and we aren't currently waiting for a request
 478                         // reply. Then, send a request for some metadata.
 479                         if (!m_torrent.valid_metadata()
 480                                 && m_message_index != 0
 481                                 && !m_waiting_metadata_request
 482                                 && has_metadata())
 483                         {
 484                                 m_last_metadata_request = m_tp.metadata_request();
 485                                 write_metadata_request(m_last_metadata_request);
 486                                 m_waiting_metadata_request = true;
 487                                 m_metadata_request = time_now();
 488                         }
 489                 }
 490
 491                 bool has_metadata() const
 492                 {
 493                         return time_now() - m_no_metadata > minutes(5);
 494                 }
 495
 496         private:
 497
 498                 // this is set to true when we send a metadata
 499                 // request to this peer, and reset to false when
 500                 // we receive a reply to our request.
 501                 bool m_waiting_metadata_request;
 502
 503                 // this is the message index the remote peer uses
 504                 // for metadata extension messages.
 505                 int m_message_index;
 506
 507                 // the number of bytes of metadata we have received
 508                 // so far from this per, only counting the current
 509                 // request. Any previously finished requests
 510                 // that have been forwarded to the torrent object
 511                 // do not count.
 512                 int m_metadata_progress;
 513
 514                 // this is set to the current time each time we get a
 515                 // "I don't have metadata" message.
 516                 ptime m_no_metadata;
 517
 518                 // this is set to the time when we last sent
 519                 // a request for metadata to this peer
 520                 ptime m_metadata_request;
 521
 522                 // if we're waiting for a metadata request
 523                 // this was the request we sent
 524                 std::pair<int, int> m_last_metadata_request;
 525
 526                 torrent& m_torrent;
 527                 peer_connection& m_pc;
 528                 metadata_plugin& m_tp;
 529         };
 530
 531         boost::shared_ptr<peer_plugin> metadata_plugin::new_connection(
 532                 peer_connection* pc)
 533         {
 534                 bt_peer_connection* c = dynamic_cast<bt_peer_connection*>(pc);
 535                 if (!c) return boost::shared_ptr<peer_plugin>();
 536                 return boost::shared_ptr<peer_plugin>(new metadata_peer_plugin(m_torrent, *pc, *this));
 537         }
 538
 539         std::pair<int, int> metadata_plugin::metadata_request()
 540         {
 541                 // count the number of peers that supports the
 542                 // extension and that has metadata
 543                 int peers = 0;
 544 #ifndef TORRENT_DISABLE_EXTENSIONS
 545                 for (torrent::peer_iterator i = m_torrent.begin()
 546                         , end(m_torrent.end()); i != end; ++i)
 547                 {
 548                         bt_peer_connection* c = dynamic_cast<bt_peer_connection*>(*i);
 549                         if (c == 0) continue;
 550                         metadata_peer_plugin* p
 551                                 = c->supports_extension<metadata_peer_plugin>();
 552                         if (p == 0) continue;
 553                         if (!p->has_metadata()) continue;
 554                         ++peers;
 555                 }
 556 #endif
 557
 558                 // the number of blocks to request
 559                 int num_blocks = 256 / (peers + 1);
 560                 if (num_blocks < 1) num_blocks = 1;
 561                 TORRENT_ASSERT(num_blocks <= 128);
 562
 563                 int min_element = (std::numeric_limits<int>::max)();
 564                 int best_index = 0;
 565                 for (int i = 0; i < 256 - num_blocks + 1; ++i)
 566                 {
 567                         int min = *std::min_element(m_requested_metadata.begin() + i
 568                                 , m_requested_metadata.begin() + i + num_blocks);
 569                         min += std::accumulate(m_requested_metadata.begin() + i
 570                                 , m_requested_metadata.begin() + i + num_blocks, (int)0);
 571
 572                         if (min_element > min)
 573                         {
 574                                 best_index = i;
 575                                 min_element = min;
 576                         }
 577                 }
 578
 579                 std::pair<int, int> ret(best_index, num_blocks);
 580                 for (int i = ret.first; i < ret.first + ret.second; ++i)
 581                         m_requested_metadata[i]++;
 582
 583                 TORRENT_ASSERT(ret.first >= 0);
 584                 TORRENT_ASSERT(ret.second > 0);
 585                 TORRENT_ASSERT(ret.second <= 256);
 586                 TORRENT_ASSERT(ret.first + ret.second <= 256);
 587
 588                 return ret;
 589         }
 590
 591 } }
 592
 593 namespace libtorrent
 594 {
 595
 596         boost::shared_ptr<torrent_plugin> create_metadata_plugin(torrent* t, void*)
 597         {
 598                 return boost::shared_ptr<torrent_plugin>(new metadata_plugin(*t));
 599         }
 600
 601 }
 602
 603