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                         hasher h;
 164                         h.update(&m_metadata[0], m_metadata_size);
 165                         sha1_hash info_hash = h.final();
 166
 167                         if (info_hash != m_torrent.torrent_file().info_hash())
 168                         {
 169                                 std::fill(
 170                                         m_have_metadata.begin()
 171                                         , m_have_metadata.begin() + req.first + req.second
 172                                         , false);
 173                                 m_metadata_progress = 0;
 174                                 m_metadata_size = 0;
 175
 176                                 if (m_torrent.alerts().should_post<metadata_failed_alert>())
 177                                 {
 178                                         m_torrent.alerts().post_alert(metadata_failed_alert(
 179                                                 m_torrent.get_handle()));
 180                                 }
 181
 182                                 return false;
 183                         }
 184
 185                         lazy_entry e;
 186                         lazy_bdecode(m_metadata.get(), m_metadata.get() + m_metadata_size, e);
 187                         std::string error;
 188                         if (!m_torrent.set_metadata(e, error))
 189                         {
 190                                 // this means the metadata is correct, since we
 191                                 // verified it against the info-hash, but we
 192                                 // failed to parse it. Pause the torrent
 193                                 // TODO: Post an alert!
 194                                 m_torrent.pause();
 195                                 return false;
 196                         }
 197
 198                         // clear the storage for the bitfield
 199                         std::vector<bool>().swap(m_have_metadata);
 200                         std::vector<int>().swap(m_requested_metadata);
 201
 202                         return true;
 203                 }
 204
 205                 // returns a range of the metadata that
 206                 // we should request.
 207                 std::pair<int, int> metadata_request();
 208
 209                 void cancel_metadata_request(std::pair<int, int> req)
 210                 {
 211                         for (int i = req.first; i < req.first + req.second; ++i)
 212                         {
 213                                 TORRENT_ASSERT(m_requested_metadata[i] > 0);
 214                                 if (m_requested_metadata[i] > 0)
 215                                         --m_requested_metadata[i];
 216                         }
 217                 }
 218
 219                 // this is called from the peer_connection for
 220                 // each piece of metadata it receives
 221                 void metadata_progress(int total_size, int received)
 222                 {
 223                         m_metadata_progress += received;
 224                         m_metadata_size = total_size;
 225                 }
 226
 227                 void on_piece_pass(int)
 228                 {
 229                         // if we became a seed, copy the metadata from
 230                         // the torrent before it is deallocated
 231                         if (m_torrent.is_seed())
 232                                 metadata();
 233                 }
 234
 235         private:
 236                 torrent& m_torrent;
 237
 238                 // this buffer is filled with the info-section of
 239                 // the metadata file while downloading it from
 240                 // peers, and while sending it.
 241                 // it is mutable because it's generated lazily
 242                 mutable boost::shared_array<char> m_metadata;
 243
 244                 int m_metadata_progress;
 245                 mutable int m_metadata_size;
 246
 247                 // this is a bitfield of size 256, each bit represents
 248                 // a piece of the metadata. It is set to one if we
 249                 // have that piece. This vector may be empty
 250                 // (size 0) if we haven't received any metadata
 251                 // or if we already have all metadata
 252                 std::vector<bool> m_have_metadata;
 253                 // this vector keeps track of how many times each meatdata
 254                 // block has been requested
 255                 std::vector<int> m_requested_metadata;
 256         };
 257
 258
 259         struct metadata_peer_plugin : peer_plugin
 260         {
 261                 metadata_peer_plugin(torrent& t, peer_connection& pc
 262                         , metadata_plugin& tp)
 263                         : m_waiting_metadata_request(false)
 264                         , m_message_index(0)
 265                         , m_metadata_progress(0)
 266                         , m_no_metadata(min_time())
 267                         , m_metadata_request(min_time())
 268                         , m_torrent(t)
 269                         , m_pc(pc)
 270                         , m_tp(tp)
 271                 {}
 272
 273                 // can add entries to the extension handshake
 274                 virtual void add_handshake(entry& h)
 275                 {
 276                         entry& messages = h["m"];
 277                         messages["LT_metadata"] = 14;
 278                 }
 279
 280                 // called when the extension handshake from the other end is received
 281                 virtual bool on_extension_handshake(lazy_entry const& h)
 282                 {
 283                         m_message_index = 0;
 284                         if (h.type() != lazy_entry::dict_t) return false;
 285                         lazy_entry const* messages = h.dict_find("m");
 286                         if (!messages || messages->type() != lazy_entry::dict_t) return false;
 287
 288                         int index = messages->dict_find_int_value("LT_metadata", -1);
 289                         if (index == -1) return false;
 290                         m_message_index = index;
 291                         return true;
 292                 }
 293
 294                 void write_metadata_request(std::pair<int, int> req)
 295                 {
 296                         TORRENT_ASSERT(req.first >= 0);
 297                         TORRENT_ASSERT(req.second > 0);
 298                         TORRENT_ASSERT(req.first + req.second <= 256);
 299                         TORRENT_ASSERT(!m_pc.associated_torrent().expired());
 300                         TORRENT_ASSERT(!m_pc.associated_torrent().lock()->valid_metadata());
 301
 302                         int start = req.first;
 303                         int size = req.second;
 304
 305                         // abort if the peer doesn't support the metadata extension
 306                         if (m_message_index == 0) return;
 307
 308                         buffer::interval i = m_pc.allocate_send_buffer(9);
 309
 310                         detail::write_uint32(1 + 1 + 3, i.begin);
 311                         detail::write_uint8(bt_peer_connection::msg_extended, i.begin);
 312                         detail::write_uint8(m_message_index, i.begin);
 313                         // means 'request data'
 314                         detail::write_uint8(0, i.begin);
 315                         detail::write_uint8(start, i.begin);
 316                         detail::write_uint8(size - 1, i.begin);
 317                         TORRENT_ASSERT(i.begin == i.end);
 318                         m_pc.setup_send();
 319                 }
 320
 321                 void write_metadata(std::pair<int, int> req)
 322                 {
 323                         TORRENT_ASSERT(req.first >= 0);
 324                         TORRENT_ASSERT(req.second > 0);
 325                         TORRENT_ASSERT(req.second <= 256);
 326                         TORRENT_ASSERT(req.first + req.second <= 256);
 327                         TORRENT_ASSERT(!m_pc.associated_torrent().expired());
 328
 329                         // abort if the peer doesn't support the metadata extension
 330                         if (m_message_index == 0) return;
 331
 332                         // only send metadata if the torrent is non-private
 333                         if (m_torrent.valid_metadata() && !m_torrent.torrent_file().priv())
 334                         {
 335                                 std::pair<int, int> offset
 336                                         = req_to_offset(req, (int)m_tp.metadata().left());
 337
 338                                 buffer::interval i = m_pc.allocate_send_buffer(15 + offset.second);
 339
 340                                 // yes, we have metadata, send it
 341                                 detail::write_uint32(11 + offset.second, i.begin);
 342                                 detail::write_uint8(bt_peer_connection::msg_extended, i.begin);
 343                                 detail::write_uint8(m_message_index, i.begin);
 344                                 // means 'data packet'
 345                                 detail::write_uint8(1, i.begin);
 346                                 detail::write_uint32((int)m_tp.metadata().left(), i.begin);
 347                                 detail::write_uint32(offset.first, i.begin);
 348                                 char const* metadata = m_tp.metadata().begin;
 349                                 std::copy(metadata + offset.first
 350                                         , metadata + offset.first + offset.second, i.begin);
 351                                 i.begin += offset.second;
 352                                 TORRENT_ASSERT(i.begin == i.end);
 353                         }
 354                         else
 355                         {
 356                                 buffer::interval i = m_pc.allocate_send_buffer(4 + 3);
 357                                 // we don't have the metadata, reply with
 358                                 // don't have-message
 359                                 detail::write_uint32(1 + 2, i.begin);
 360                                 detail::write_uint8(bt_peer_connection::msg_extended, i.begin);
 361                                 detail::write_uint8(m_message_index, i.begin);
 362                                 // means 'have no data'
 363                                 detail::write_uint8(2, i.begin);
 364                                 TORRENT_ASSERT(i.begin == i.end);
 365                         }
 366                         m_pc.setup_send();
 367                 }
 368
 369                 virtual bool on_extended(int length
 370                         , int msg, buffer::const_interval body)
 371                 {
 372                         if (msg != 14) return false;
 373                         if (m_message_index == 0) return false;
 374
 375                         if (length > 500 * 1024)
 376                         {
 377                                 m_pc.disconnect("LT_metadata message larger than 500 kB");
 378                                 return true;
 379                         }
 380
 381                         if (body.left() < 1) return true;
 382                         int type = detail::read_uint8(body.begin);
 383
 384                         switch (type)
 385                         {
 386                         case 0: // request
 387                                 {
 388                                         if (body.left() < 2) return true;
 389                                         int start = detail::read_uint8(body.begin);
 390                                         int size = detail::read_uint8(body.begin) + 1;
 391
 392                                         if (length != 3)
 393                                         {
 394                                                 // invalid metadata request
 395                                                 m_pc.disconnect("invalid metadata request");
 396                                                 return true;
 397                                         }
 398
 399                                         write_metadata(std::make_pair(start, size));
 400                                 }
 401                                 break;
 402                         case 1: // data
 403                                 {
 404                                         if (body.left() < 8) return true;
 405
 406                                         int total_size = detail::read_int32(body.begin);
 407                                         int offset = detail::read_int32(body.begin);
 408                                         int data_size = length - 9;
 409
 410                                         if (total_size > 500 * 1024)
 411                                         {
 412                                                 m_pc.disconnect("metadata size larger than 500 kB");
 413                                                 return true;
 414                                         }
 415                                         if (total_size <= 0)
 416                                         {
 417                                                 m_pc.disconnect("invalid metadata size");
 418                                                 return true;
 419                                         }
 420                                         if (offset > total_size || offset < 0)
 421                                         {
 422                                                 m_pc.disconnect("invalid metadata offset");
 423                                                 return true;
 424                                         }
 425                                         if (offset + data_size > total_size)
 426                                         {
 427                                                 m_pc.disconnect("invalid metadata message");
 428                                                 return true;
 429                                         }
 430
 431                                         m_tp.metadata_progress(total_size
 432                                                 , body.left() - m_metadata_progress);
 433                                         m_metadata_progress = body.left();
 434
 435                                         if (body.left() < data_size) return true;
 436
 437                                         m_waiting_metadata_request = false;
 438                                         m_tp.received_metadata(body.begin, data_size
 439                                                 , offset, total_size);
 440                                         m_metadata_progress = 0;
 441                                 }
 442                                 break;
 443                         case 2: // have no data
 444                                 m_no_metadata = time_now();
 445                                 if (m_waiting_metadata_request)
 446                                         m_tp.cancel_metadata_request(m_last_metadata_request);
 447                                 m_waiting_metadata_request = false;
 448                                 break;
 449                         default:
 450                                 {
 451                                         std::stringstream msg;
 452                                         msg << "unknown metadata extension message: " << type;
 453                                         m_pc.disconnect(msg.str().c_str());
 454                                 }
 455                         }
 456                         return true;
 457                 }
 458
 459                 virtual void tick()
 460                 {
 461                         // if we don't have any metadata, and this peer
 462                         // supports the request metadata extension
 463                         // and we aren't currently waiting for a request
 464                         // reply. Then, send a request for some metadata.
 465                         if (!m_torrent.valid_metadata()
 466                                 && m_message_index != 0
 467                                 && !m_waiting_metadata_request
 468                                 && has_metadata())
 469                         {
 470                                 m_last_metadata_request = m_tp.metadata_request();
 471                                 write_metadata_request(m_last_metadata_request);
 472                                 m_waiting_metadata_request = true;
 473                                 m_metadata_request = time_now();
 474                         }
 475                 }
 476
 477                 bool has_metadata() const
 478                 {
 479                         return time_now() - m_no_metadata > minutes(5);
 480                 }
 481
 482         private:
 483
 484                 // this is set to true when we send a metadata
 485                 // request to this peer, and reset to false when
 486                 // we receive a reply to our request.
 487                 bool m_waiting_metadata_request;
 488
 489                 // this is the message index the remote peer uses
 490                 // for metadata extension messages.
 491                 int m_message_index;
 492
 493                 // the number of bytes of metadata we have received
 494                 // so far from this per, only counting the current
 495                 // request. Any previously finished requests
 496                 // that have been forwarded to the torrent object
 497                 // do not count.
 498                 int m_metadata_progress;
 499
 500                 // this is set to the current time each time we get a
 501                 // "I don't have metadata" message.
 502                 ptime m_no_metadata;
 503
 504                 // this is set to the time when we last sent
 505                 // a request for metadata to this peer
 506                 ptime m_metadata_request;
 507
 508                 // if we're waiting for a metadata request
 509                 // this was the request we sent
 510                 std::pair<int, int> m_last_metadata_request;
 511
 512                 torrent& m_torrent;
 513                 peer_connection& m_pc;
 514                 metadata_plugin& m_tp;
 515         };
 516
 517         boost::shared_ptr<peer_plugin> metadata_plugin::new_connection(
 518                 peer_connection* pc)
 519         {
 520                 bt_peer_connection* c = dynamic_cast<bt_peer_connection*>(pc);
 521                 if (!c) return boost::shared_ptr<peer_plugin>();
 522                 return boost::shared_ptr<peer_plugin>(new metadata_peer_plugin(m_torrent, *pc, *this));
 523         }
 524
 525         std::pair<int, int> metadata_plugin::metadata_request()
 526         {
 527                 // count the number of peers that supports the
 528                 // extension and that has metadata
 529                 int peers = 0;
 530 #ifndef TORRENT_DISABLE_EXTENSIONS
 531                 for (torrent::peer_iterator i = m_torrent.begin()
 532                         , end(m_torrent.end()); i != end; ++i)
 533                 {
 534                         bt_peer_connection* c = dynamic_cast<bt_peer_connection*>(*i);
 535                         if (c == 0) continue;
 536                         metadata_peer_plugin* p
 537                                 = c->supports_extension<metadata_peer_plugin>();
 538                         if (p == 0) continue;
 539                         if (!p->has_metadata()) continue;
 540                         ++peers;
 541                 }
 542 #endif
 543
 544                 // the number of blocks to request
 545                 int num_blocks = 256 / (peers + 1);
 546                 if (num_blocks < 1) num_blocks = 1;
 547                 TORRENT_ASSERT(num_blocks <= 128);
 548
 549                 int min_element = (std::numeric_limits<int>::max)();
 550                 int best_index = 0;
 551                 for (int i = 0; i < 256 - num_blocks + 1; ++i)
 552                 {
 553                         int min = *std::min_element(m_requested_metadata.begin() + i
 554                                 , m_requested_metadata.begin() + i + num_blocks);
 555                         min += std::accumulate(m_requested_metadata.begin() + i
 556                                 , m_requested_metadata.begin() + i + num_blocks, (int)0);
 557
 558                         if (min_element > min)
 559                         {
 560                                 best_index = i;
 561                                 min_element = min;
 562                         }
 563                 }
 564
 565                 std::pair<int, int> ret(best_index, num_blocks);
 566                 for (int i = ret.first; i < ret.first + ret.second; ++i)
 567                         m_requested_metadata[i]++;
 568
 569                 TORRENT_ASSERT(ret.first >= 0);
 570                 TORRENT_ASSERT(ret.second > 0);
 571                 TORRENT_ASSERT(ret.second <= 256);
 572                 TORRENT_ASSERT(ret.first + ret.second <= 256);
 573
 574                 return ret;
 575         }
 576
 577 } }
 578
 579 namespace libtorrent
 580 {
 581
 582         boost::shared_ptr<torrent_plugin> create_metadata_plugin(torrent* t, void*)
 583         {
 584                 return boost::shared_ptr<torrent_plugin>(new metadata_plugin(*t));
 585         }
 586
 587 }
 588
 589