test/test_piece_picker.cpp

   1 /*
   2
   3 Copyright (c) 2008, 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/piece_picker.hpp"
  34 #include "libtorrent/policy.hpp"
  35 #include "libtorrent/bitfield.hpp"
  36 #include <boost/shared_ptr.hpp>
  37 #include <boost/bind.hpp>
  38 #include <algorithm>
  39 #include <vector>
  40 #include <set>
  41
  42 #include "test.hpp"
  43
  44 using namespace libtorrent;
  45
  46 const int blocks_per_piece = 4;
  47
  48 bitfield string2vec(char const* have_str)
  49 {
  50         const int num_pieces = strlen(have_str);
  51         bitfield have(num_pieces, false);
  52         for (int i = 0; i < num_pieces; ++i)
  53                 if (have_str[i] != ' ')  have.set_bit(i);
  54         return have;
  55 }
  56
  57 // availability is a string where each character is the
  58 // availability of that piece, '1', '2' etc.
  59 // have_str is a string where each character represents a
  60 // piece, ' ' means we don't have the piece and any other
  61 // character means we have it
  62 boost::shared_ptr<piece_picker> setup_picker(
  63         char const* availability
  64         , char const* have_str
  65         , char const* priority
  66         , char const* partial)
  67 {
  68         const int num_pieces = strlen(availability);
  69         assert(int(strlen(have_str)) == num_pieces);
  70
  71         boost::shared_ptr<piece_picker> p(new piece_picker);
  72         p->init(blocks_per_piece, num_pieces * blocks_per_piece);
  73
  74         bitfield have = string2vec(have_str);
  75
  76         for (int i = 0; i < num_pieces; ++i)
  77         {
  78                 if (partial[i] == 0) break;
  79
  80                 if (partial[i] == ' ') continue;
  81
  82                 int blocks = 0;
  83                 if (partial[i] >= '0' && partial[i] <= '9')
  84                         blocks = partial[i] - '0';
  85                 else
  86                         blocks = partial[i] - 'a' + 10;
  87
  88                 int counter = 0;
  89                 if (blocks & 1)
  90                 {
  91                         ++counter;
  92                         p->mark_as_finished(piece_block(i, 0), 0);
  93                 }
  94                 if (blocks & 2)
  95                 {
  96                         ++counter;
  97                         p->mark_as_finished(piece_block(i, 1), 0);
  98                 }
  99                 if (blocks & 4)
 100                 {
 101                         ++counter;
 102                         p->mark_as_finished(piece_block(i, 2), 0);
 103                 }
 104                 if (blocks & 8)
 105                 {
 106                         ++counter;
 107                         p->mark_as_finished(piece_block(i, 3), 0);
 108                 }
 109
 110                 piece_picker::downloading_piece st;
 111                 p->piece_info(i, st);
 112                 TEST_CHECK(st.writing == 0);
 113                 TEST_CHECK(st.requested == 0);
 114                 TEST_CHECK(st.index == i);
 115
 116                 TEST_CHECK(st.finished == counter);
 117         }
 118
 119         for (int i = 0; i < num_pieces; ++i)
 120         {
 121                 if (priority[i] == 0) break;
 122                 const int prio = priority[i] - '0';
 123                 assert(prio >= 0);
 124                 p->set_piece_priority(i, prio);
 125
 126                 TEST_CHECK(p->piece_priority(i) == prio);
 127         }
 128
 129         for (int i = 0; i < num_pieces; ++i)
 130         {
 131                 if (!have[i]) continue;
 132                 p->we_have(i);
 133                 for (int j = 0; j < blocks_per_piece; ++j)
 134                         TEST_CHECK(p->is_finished(piece_block(i, j)));
 135         }
 136
 137         for (int i = 0; i < num_pieces; ++i)
 138         {
 139                 const int avail = availability[i] - '0';
 140                 assert(avail >= 0);
 141
 142                 for (int j = 0; j < avail; ++j) p->inc_refcount(i);
 143         }
 144
 145         std::vector<int> availability_vec;
 146         p->get_availability(availability_vec);
 147         for (int i = 0; i < num_pieces; ++i)
 148         {
 149                 const int avail = availability[i] - '0';
 150                 assert(avail >= 0);
 151                 TEST_CHECK(avail == availability_vec[i]);
 152         }
 153
 154 #ifndef NDEBUG
 155         p->check_invariant();
 156 #endif
 157         return p;
 158 }
 159
 160 bool verify_pick(boost::shared_ptr<piece_picker> p
 161         , std::vector<piece_block> const& picked)
 162 {
 163 #ifndef NDEBUG
 164         p->check_invariant();
 165 #endif
 166         for (std::vector<piece_block>::const_iterator i = picked.begin()
 167                 , end(picked.end()); i != end; ++i)
 168         {
 169                 if (p->num_peers(*i) > 0) return false;
 170         }
 171
 172         // make sure there are no duplicated
 173         std::set<piece_block> blocks;
 174         std::copy(picked.begin(), picked.end(), std::insert_iterator<std::set<piece_block> >(blocks, blocks.end()));
 175         return picked.size() == blocks.size();
 176 }
 177
 178 void print_pick(std::vector<piece_block> const& picked)
 179 {
 180         for (int i = 0; i < int(picked.size()); ++i)
 181         {
 182                 std::cout << "(" << picked[i].piece_index << ", " << picked[i].block_index << ") ";
 183         }
 184         std::cout << std::endl;
 185 }
 186
 187 void print_title(char const* name)
 188 {
 189         std::cerr << "==== " << name << " ====\n";
 190 }
 191
 192 int test_pick(boost::shared_ptr<piece_picker> const& p)
 193 {
 194         std::vector<piece_block> picked;
 195         const std::vector<int> empty_vector;
 196         p->pick_pieces(string2vec("*******"), picked, 1, false, 0, piece_picker::fast, true, false, empty_vector);
 197         print_pick(picked);
 198         TEST_CHECK(verify_pick(p, picked));
 199         TEST_CHECK(int(picked.size()) == 1);
 200         return picked[0].piece_index;
 201 }
 202
 203 int test_main()
 204 {
 205
 206         tcp::endpoint endp;
 207         policy::peer peer_struct(endp, policy::peer::connectable, 0);
 208         std::vector<piece_block> picked;
 209         boost::shared_ptr<piece_picker> p;
 210         const std::vector<int> empty_vector;
 211
 212         // make sure the block that is picked is from piece 1, since it
 213         // it is the piece with the lowest availability
 214         print_title("test pick lowest availability");
 215         p = setup_picker("2223333", "* * *  ", "", "");
 216         picked.clear();
 217         p->pick_pieces(string2vec("*******"), picked, 1, false, 0, piece_picker::fast, true, false, empty_vector);
 218         TEST_CHECK(verify_pick(p, picked));
 219         TEST_CHECK(int(picked.size()) > 0);
 220         TEST_CHECK(picked.front().piece_index == 1);
 221
 222 // ========================================================
 223
 224         // make sure the block that is picked is from piece 5, since it
 225         // has the highest priority among the available pieces
 226         print_title("test pick highest priority");
 227         p = setup_picker("1111111", "* * *  ", "1111122", "");
 228         picked.clear();
 229         p->pick_pieces(string2vec("****** "), picked, 1, false, 0, piece_picker::fast, true, false, empty_vector);
 230         TEST_CHECK(verify_pick(p, picked));
 231         TEST_CHECK(int(picked.size()) > 0);
 232         TEST_CHECK(picked.front().piece_index == 5);
 233
 234 // ========================================================
 235
 236         // make sure the 4 blocks are picked from the same piece if
 237         // whole pieces are preferred. The only whole piece is 1.
 238         print_title("test pick whole pieces");
 239         p = setup_picker("1111111", "       ", "1111111", "1023460");
 240         picked.clear();
 241         p->pick_pieces(string2vec("****** "), picked, 1, 1, &peer_struct, piece_picker::fast, true, true, empty_vector);
 242         TEST_CHECK(verify_pick(p, picked));
 243         TEST_CHECK(int(picked.size()) >= blocks_per_piece);
 244         for (int i = 0; i < blocks_per_piece && i < int(picked.size()); ++i)
 245                 TEST_CHECK(picked[i].piece_index == 1);
 246
 247 // ========================================================
 248
 249         // test the distributed copies function. It should include ourself
 250         // in the availability. i.e. piece 0 has availability 2.
 251         // there are 2 pieces with availability 2 and 5 with availability 3
 252         print_title("test distributed copies");
 253         p = setup_picker("1233333", "*      ", "", "");
 254         float dc = p->distributed_copies();
 255         TEST_CHECK(fabs(dc - (2.f + 5.f / 7.f)) < 0.01f);
 256
 257 // ========================================================
 258
 259         // make sure filtered pieces are ignored
 260         print_title("test filtered pieces");
 261         p = setup_picker("1111111", "       ", "0010000", "");
 262         picked.clear();
 263         p->pick_pieces(string2vec("*** ** "), picked, 1, false, 0, piece_picker::fast, true, false, empty_vector);
 264         TEST_CHECK(verify_pick(p, picked));
 265         TEST_CHECK(int(picked.size()) > 0);
 266         TEST_CHECK(picked.front().piece_index == 2);
 267
 268 // ========================================================
 269
 270         // make sure we_dont_have works
 271         print_title("test we_dont_have");
 272         p = setup_picker("1111111", "*******", "0100000", "");
 273         picked.clear();
 274         p->we_dont_have(1);
 275         p->we_dont_have(2);
 276         p->pick_pieces(string2vec("*** ** "), picked, 1, false, 0, piece_picker::fast, true, false, empty_vector);
 277         TEST_CHECK(verify_pick(p, picked));
 278         TEST_CHECK(int(picked.size()) > 0);
 279         TEST_CHECK(picked.front().piece_index == 1);
 280
 281 // ========================================================
 282
 283         // make sure requested blocks aren't picked
 284         print_title("test don't pick requested blocks");
 285         p = setup_picker("1234567", "       ", "", "");
 286         picked.clear();
 287         p->pick_pieces(string2vec("*******"), picked, 1, false, 0, piece_picker::fast, true, false, empty_vector);
 288         TEST_CHECK(verify_pick(p, picked));
 289         TEST_CHECK(int(picked.size()) > 0);
 290         TEST_CHECK(picked.front().piece_index == 0);
 291         piece_block first = picked.front();
 292         p->mark_as_downloading(picked.front(), &peer_struct, piece_picker::fast);
 293         TEST_CHECK(p->num_peers(picked.front()) == 1);
 294         picked.clear();
 295         p->pick_pieces(string2vec("*******"), picked, 1, false, 0, piece_picker::fast, true, false, empty_vector);
 296         TEST_CHECK(verify_pick(p, picked));
 297         TEST_CHECK(int(picked.size()) > 0);
 298         TEST_CHECK(picked.front() != first);
 299         TEST_CHECK(picked.front().piece_index == 0);
 300
 301 // ========================================================
 302 /*
 303         // test sequenced download
 304         p = setup_picker("7654321", "       ", "", "");
 305         picked.clear();
 306         p->set_sequenced_download_threshold(3);
 307         p->pick_pieces(string2vec("*****  "), picked, 5 * blocks_per_piece, false, 0, piece_picker::fast, true, false, empty_vector);
 308         print_pick(picked);
 309         TEST_CHECK(verify_pick(p, picked));
 310         TEST_CHECK(int(picked.size()) == 5 * blocks_per_piece);
 311         for (int i = 0; i < 5 * blocks_per_piece && i < int(picked.size()); ++i)
 312                 TEST_CHECK(picked[i].piece_index == i / blocks_per_piece);
 313
 314         picked.clear();
 315         p->set_sequenced_download_threshold(4);
 316         p->pick_pieces(string2vec("****   "), picked, 5 * blocks_per_piece, false, 0, piece_picker::fast, true, false, empty_vector);
 317         print_pick(picked);
 318         TEST_CHECK(verify_pick(p, picked));
 319         TEST_CHECK(int(picked.size()) == 4 * blocks_per_piece);
 320         for (int i = 0; i < 4 * blocks_per_piece && i < int(picked.size()); ++i)
 321                 TEST_CHECK(picked[i].piece_index == i / blocks_per_piece);
 322
 323         picked.clear();
 324         p->set_sequenced_download_threshold(2);
 325         p->pick_pieces(string2vec("****** "), picked, 6 * blocks_per_piece, false, 0, piece_picker::fast, true, false, empty_vector);
 326         print_pick(picked);
 327         TEST_CHECK(verify_pick(p, picked));
 328         TEST_CHECK(int(picked.size()) == 6 * blocks_per_piece);
 329         for (int i = 0; i < 6 * blocks_per_piece && i < int(picked.size()); ++i)
 330                 TEST_CHECK(picked[i].piece_index == i / blocks_per_piece);
 331
 332         picked.clear();
 333         p->set_piece_priority(0, 0);
 334         p->pick_pieces(string2vec("****** "), picked, 6 * blocks_per_piece, false, 0, piece_picker::fast, true, false, empty_vector);
 335         print_pick(picked);
 336         TEST_CHECK(verify_pick(p, picked));
 337         TEST_CHECK(int(picked.size()) == 5 * blocks_per_piece);
 338         for (int i = 0; i < 5 * blocks_per_piece && i < int(picked.size()); ++i)
 339                 TEST_CHECK(picked[i].piece_index == i / blocks_per_piece + 1);
 340
 341         picked.clear();
 342         p->set_piece_priority(0, 1);
 343         p->pick_pieces(string2vec("****** "), picked, 6 * blocks_per_piece, false, 0, piece_picker::fast, true, false, empty_vector);
 344         print_pick(picked);
 345         TEST_CHECK(verify_pick(p, picked));
 346         TEST_CHECK(int(picked.size()) == 6 * blocks_per_piece);
 347         for (int i = 0; i < 6 * blocks_per_piece && i < int(picked.size()); ++i)
 348                 TEST_CHECK(picked[i].piece_index == i / blocks_per_piece);
 349 */
 350 // ========================================================
 351
 352         // test piece priorities
 353         print_title("test piece priorities");
 354         p = setup_picker("5555555", "       ", "3214576", "");
 355         TEST_CHECK(p->num_filtered() == 0);
 356         TEST_CHECK(p->num_have_filtered() == 0);
 357         p->set_piece_priority(0, 0);
 358         TEST_CHECK(p->num_filtered() == 1);
 359         TEST_CHECK(p->num_have_filtered() == 0);
 360         p->mark_as_finished(piece_block(0,0), 0);
 361         p->we_have(0);
 362         TEST_CHECK(p->num_filtered() == 0);
 363         TEST_CHECK(p->num_have_filtered() == 1);
 364
 365         picked.clear();
 366         p->pick_pieces(string2vec("*******"), picked, 6 * blocks_per_piece, false, 0, piece_picker::fast, true, false, empty_vector);
 367         print_pick(picked);
 368         TEST_CHECK(verify_pick(p, picked));
 369         TEST_CHECK(int(picked.size()) == 6 * blocks_per_piece);
 370         TEST_CHECK(picked[0 * blocks_per_piece].piece_index == 5);
 371         // priority 5 and 6 is currently the same
 372         TEST_CHECK(picked[1 * blocks_per_piece].piece_index == 6 || picked[1 * blocks_per_piece].piece_index == 4);
 373         TEST_CHECK(picked[2 * blocks_per_piece].piece_index == 6 || picked[2 * blocks_per_piece].piece_index == 4);
 374         TEST_CHECK(picked[3 * blocks_per_piece].piece_index == 3);
 375         TEST_CHECK(picked[4 * blocks_per_piece].piece_index == 1);
 376         TEST_CHECK(picked[5 * blocks_per_piece].piece_index == 2);
 377
 378         std::vector<int> prios;
 379         p->piece_priorities(prios);
 380         TEST_CHECK(prios.size() == 7);
 381         int prio_comp[] = {0, 2, 1, 4, 5, 7, 6};
 382         TEST_CHECK(std::equal(prios.begin(), prios.end(), prio_comp));
 383
 384 // ========================================================
 385
 386         // test restore_piece
 387         print_title("test restore piece");
 388         p = setup_picker("1234567", "       ", "", "");
 389         p->mark_as_finished(piece_block(0,0), 0);
 390         p->mark_as_finished(piece_block(0,1), 0);
 391         p->mark_as_finished(piece_block(0,2), 0);
 392         p->mark_as_finished(piece_block(0,3), 0);
 393
 394         picked.clear();
 395         p->pick_pieces(string2vec("*******"), picked, 1, false, 0, piece_picker::fast, true, false, empty_vector);
 396         print_pick(picked);
 397         TEST_CHECK(verify_pick(p, picked));
 398         TEST_CHECK(int(picked.size()) >= 1);
 399         TEST_CHECK(picked.front().piece_index == 1);
 400
 401         p->restore_piece(0);
 402         picked.clear();
 403         p->pick_pieces(string2vec("*******"), picked, 1, false, 0, piece_picker::fast, true, false, empty_vector);
 404         print_pick(picked);
 405         TEST_CHECK(verify_pick(p, picked));
 406         TEST_CHECK(int(picked.size()) >= 1);
 407         TEST_CHECK(picked.front().piece_index == 0);
 408
 409         p->mark_as_finished(piece_block(0,0), 0);
 410         p->mark_as_finished(piece_block(0,1), 0);
 411         p->mark_as_finished(piece_block(0,2), 0);
 412         p->mark_as_finished(piece_block(0,3), 0);
 413         p->set_piece_priority(0, 0);
 414
 415         picked.clear();
 416         p->pick_pieces(string2vec("*******"), picked, 1, false, 0, piece_picker::fast, true, false, empty_vector);
 417         print_pick(picked);
 418         TEST_CHECK(verify_pick(p, picked));
 419         TEST_CHECK(int(picked.size()) >= 1);
 420         TEST_CHECK(picked.front().piece_index == 1);
 421
 422         p->restore_piece(0);
 423         picked.clear();
 424         p->pick_pieces(string2vec("*******"), picked, 1, false, 0, piece_picker::fast, true, false, empty_vector);
 425         print_pick(picked);
 426         TEST_CHECK(verify_pick(p, picked));
 427         TEST_CHECK(int(picked.size()) >= 1);
 428         TEST_CHECK(picked.front().piece_index == 1);
 429
 430         p->set_piece_priority(0, 1);
 431         picked.clear();
 432         p->pick_pieces(string2vec("*******"), picked, 1, false, 0, piece_picker::fast, true, false, empty_vector);
 433         print_pick(picked);
 434         TEST_CHECK(verify_pick(p, picked));
 435         TEST_CHECK(int(picked.size()) >= 1);
 436         TEST_CHECK(picked.front().piece_index == 0);
 437
 438 // ========================================================
 439
 440         // test non-rarest-first mode
 441         print_title("test not rarest first");
 442         p = setup_picker("1234567", "* * *  ", "1111122", "");
 443         picked.clear();
 444         p->pick_pieces(string2vec("****** "), picked, 5 * blocks_per_piece, false, 0, piece_picker::fast, false, false, empty_vector);
 445         print_pick(picked);
 446         TEST_CHECK(verify_pick(p, picked));
 447         TEST_CHECK(int(picked.size()) == 3 * blocks_per_piece);
 448
 449         for (int i = 0; i < 4 * blocks_per_piece && i < int(picked.size()); ++i)
 450         {
 451                 TEST_CHECK(picked[i].piece_index != 0);
 452                 TEST_CHECK(picked[i].piece_index != 2);
 453                 TEST_CHECK(picked[i].piece_index != 4);
 454         }
 455
 456 // ========================================================
 457
 458         // test have_all and have_none
 459         print_title("test have_all and have_none");
 460         p = setup_picker("0123333", "*      ", "", "");
 461         dc = p->distributed_copies();
 462         std::cout << "distributed copies: " << dc << std::endl;
 463         TEST_CHECK(fabs(dc - (1.f + 5.f / 7.f)) < 0.01f);
 464         p->inc_refcount_all();
 465         dc = p->distributed_copies();
 466         std::cout << "distributed copies: " << dc << std::endl;
 467         TEST_CHECK(fabs(dc - (2.f + 5.f / 7.f)) < 0.01f);
 468         p->dec_refcount_all();
 469         dc = p->distributed_copies();
 470         std::cout << "distributed copies: " << dc << std::endl;
 471         TEST_CHECK(fabs(dc - (1.f + 5.f / 7.f)) < 0.01f);
 472         p->inc_refcount(0);
 473         p->dec_refcount_all();
 474         dc = p->distributed_copies();
 475         std::cout << "distributed copies: " << dc << std::endl;
 476         TEST_CHECK(fabs(dc - (0.f + 6.f / 7.f)) < 0.01f);
 477         TEST_CHECK(test_pick(p) == 2);
 478
 479 // ========================================================
 480
 481         // test have_all and have_none with sequential download
 482         print_title("test have_all and have_none with sequential download");
 483         p = setup_picker("0123333", "*      ", "", "");
 484         dc = p->distributed_copies();
 485         std::cout << "distributed copies: " << dc << std::endl;
 486         TEST_CHECK(fabs(dc - (1.f + 5.f / 7.f)) < 0.01f);
 487         p->inc_refcount_all();
 488         dc = p->distributed_copies();
 489         std::cout << "distributed copies: " << dc << std::endl;
 490         TEST_CHECK(fabs(dc - (2.f + 5.f / 7.f)) < 0.01f);
 491         p->sequential_download(true);
 492         p->dec_refcount_all();
 493         dc = p->distributed_copies();
 494         std::cout << "distributed copies: " << dc << std::endl;
 495         TEST_CHECK(fabs(dc - (1.f + 5.f / 7.f)) < 0.01f);
 496         p->inc_refcount(0);
 497         p->dec_refcount_all();
 498         dc = p->distributed_copies();
 499         std::cout << "distributed copies: " << dc << std::endl;
 500         TEST_CHECK(fabs(dc - (0.f + 6.f / 7.f)) < 0.01f);
 501         p->inc_refcount(1);
 502         TEST_CHECK(test_pick(p) == 1);
 503
 504 // ========================================================
 505
 506         // test inc_ref and dec_ref
 507         print_title("test inc_ref dec_ref");
 508         p = setup_picker("1233333", "     * ", "", "");
 509         TEST_CHECK(test_pick(p) == 0);
 510
 511         p->dec_refcount(0);
 512         TEST_CHECK(test_pick(p) == 1);
 513
 514         p->dec_refcount(4);
 515         p->dec_refcount(4);
 516         TEST_CHECK(test_pick(p) == 4);
 517
 518         // decrease refcount on something that's not in the piece list
 519         p->dec_refcount(5);
 520         p->inc_refcount(5);
 521
 522         p->inc_refcount(0);
 523         p->dec_refcount(4);
 524         TEST_CHECK(test_pick(p) == 0);
 525
 526 // ========================================================
 527 /*
 528         // test have_all and have_none, with a sequenced download threshold
 529         p = setup_picker("1233333", "*      ", "", "");
 530         p->set_sequenced_download_threshold(3);
 531         p->inc_refcount_all();
 532         dc = p->distributed_copies();
 533         TEST_CHECK(fabs(dc - (3.f + 5.f / 7.f)) < 0.01f);
 534         p->dec_refcount_all();
 535         dc = p->distributed_copies();
 536         TEST_CHECK(fabs(dc - (2.f + 5.f / 7.f)) < 0.01f);
 537         p->dec_refcount(2);
 538         dc = p->distributed_copies();
 539         TEST_CHECK(fabs(dc - (2.f + 4.f / 7.f)) < 0.01f);
 540         p->mark_as_downloading(piece_block(1,0), &peer_struct, piece_picker::fast);
 541         p->mark_as_downloading(piece_block(1,1), &peer_struct, piece_picker::fast);
 542         p->we_have(1);
 543         dc = p->distributed_copies();
 544         TEST_CHECK(fabs(dc - (2.f + 5.f / 7.f)) < 0.01f);
 545         picked.clear();
 546         // make sure it won't pick the piece we just got
 547         p->pick_pieces(string2vec(" * ****"), picked, 100, false, 0, piece_picker::fast, true, false, empty_vector);
 548         print_pick(picked);
 549         TEST_CHECK(verify_pick(p, picked));
 550         TEST_CHECK(int(picked.size()) >= 4 * blocks_per_piece);
 551         TEST_CHECK(picked[0 * blocks_per_piece].piece_index == 3);
 552         TEST_CHECK(picked[1 * blocks_per_piece].piece_index == 4);
 553         TEST_CHECK(picked[2 * blocks_per_piece].piece_index == 5);
 554         TEST_CHECK(picked[3 * blocks_per_piece].piece_index == 6);
 555 */
 556 // ========================================================
 557
 558         // test unverified_blocks, marking blocks and get_downloader
 559         print_title("test unverified blocks");
 560         p = setup_picker("1111111", "       ", "", "0300700");
 561         TEST_CHECK(p->unverified_blocks() == 2 + 3);
 562         TEST_CHECK(p->get_downloader(piece_block(4, 0)) == 0);
 563         TEST_CHECK(p->get_downloader(piece_block(4, 1)) == 0);
 564         TEST_CHECK(p->get_downloader(piece_block(4, 2)) == 0);
 565         TEST_CHECK(p->get_downloader(piece_block(4, 3)) == 0);
 566         p->mark_as_downloading(piece_block(4, 3), &peer_struct, piece_picker::fast);
 567         TEST_CHECK(p->get_downloader(piece_block(4, 3)) == &peer_struct);
 568         piece_picker::downloading_piece st;
 569         p->piece_info(4, st);
 570         TEST_CHECK(st.requested == 1);
 571         TEST_CHECK(st.writing == 0);
 572         TEST_CHECK(st.finished == 3);
 573         TEST_CHECK(p->unverified_blocks() == 2 + 3);
 574         p->mark_as_writing(piece_block(4, 3), &peer_struct);
 575         TEST_CHECK(p->get_downloader(piece_block(4, 3)) == &peer_struct);
 576         p->piece_info(4, st);
 577         TEST_CHECK(st.requested == 0);
 578         TEST_CHECK(st.writing == 1);
 579         TEST_CHECK(st.finished == 3);
 580         TEST_CHECK(p->unverified_blocks() == 2 + 3);
 581         p->mark_as_finished(piece_block(4, 3), &peer_struct);
 582         TEST_CHECK(p->get_downloader(piece_block(4, 3)) == &peer_struct);
 583         p->piece_info(4, st);
 584         TEST_CHECK(st.requested == 0);
 585         TEST_CHECK(st.writing == 0);
 586         TEST_CHECK(st.finished == 4);
 587         TEST_CHECK(p->unverified_blocks() == 2 + 4);
 588         p->we_have(4);
 589         p->piece_info(4, st);
 590         TEST_CHECK(st.requested == 0);
 591         TEST_CHECK(st.writing == 0);
 592         TEST_CHECK(st.finished == 4);
 593         TEST_CHECK(p->get_downloader(piece_block(4, 3)) == 0);
 594         TEST_CHECK(p->unverified_blocks() == 2);
 595
 596 // ========================================================
 597
 598         // test prefer_whole_pieces
 599         print_title("test prefer whole pieces");
 600         p = setup_picker("1111111", "       ", "", "");
 601         picked.clear();
 602         p->pick_pieces(string2vec("*******"), picked, 1, 3, 0, piece_picker::fast, true, false, empty_vector);
 603         print_pick(picked);
 604         TEST_CHECK(verify_pick(p, picked));
 605         TEST_CHECK(int(picked.size()) >= 3 * blocks_per_piece);
 606         piece_block b = picked.front();
 607         for (int i = 1; i < int(picked.size()); ++i)
 608         {
 609                 TEST_CHECK(picked[i].piece_index * blocks_per_piece + picked[i].block_index
 610                         == b.piece_index * blocks_per_piece + b.block_index + 1);
 611                 b = picked[i];
 612         }
 613
 614         picked.clear();
 615         p->pick_pieces(string2vec("*******"), picked, 1, 3, 0, piece_picker::fast, false, false, empty_vector);
 616         print_pick(picked);
 617         TEST_CHECK(verify_pick(p, picked));
 618         TEST_CHECK(int(picked.size()) >= 3 * blocks_per_piece);
 619         b = picked.front();
 620         for (int i = 1; i < int(picked.size()); ++i)
 621         {
 622                 TEST_CHECK(picked[i].piece_index * blocks_per_piece + picked[i].block_index
 623                         == b.piece_index * blocks_per_piece + b.block_index + 1);
 624                 b = picked[i];
 625         }
 626
 627 // ========================================================
 628
 629         // test parole mode
 630         print_title("test parole mode");
 631         p = setup_picker("3333133", "       ", "", "");
 632         p->mark_as_finished(piece_block(0, 0), 0);
 633         picked.clear();
 634         p->pick_pieces(string2vec("*******"), picked, 1, 1, 0, piece_picker::fast, true, true, empty_vector);
 635         print_pick(picked);
 636         TEST_CHECK(verify_pick(p, picked));
 637         TEST_CHECK(int(picked.size()) >= blocks_per_piece - 1);
 638         for (int i = 1; i < int(picked.size()); ++i)
 639         {
 640                 TEST_CHECK(picked[i].piece_index == 0);
 641                 TEST_CHECK(picked[i].block_index == i + 1);
 642         }
 643
 644         //      make sure that the partial piece is not picked by a
 645         // peer that is has not downloaded/requested the other blocks
 646         picked.clear();
 647         p->pick_pieces(string2vec("*******"), picked, 1, 1, &peer_struct, piece_picker::fast, true, true, empty_vector);
 648         print_pick(picked);
 649         TEST_CHECK(int(picked.size()) >= blocks_per_piece);
 650         for (int i = 1; i < int(picked.size()); ++i)
 651         {
 652                 TEST_CHECK(picked[i].piece_index == 4);
 653                 TEST_CHECK(picked[i].block_index == i);
 654         }
 655
 656 // ========================================================
 657
 658         // test suggested pieces
 659         print_title("test suggested pieces");
 660         p = setup_picker("1111222233334444", "                ", "", "");
 661         int v[] = {1, 5};
 662         std::vector<int> suggested_pieces(v, v + 2);
 663
 664         picked.clear();
 665         p->pick_pieces(string2vec("****************"), picked, 1, 1, 0, piece_picker::fast, true, true, suggested_pieces);
 666         print_pick(picked);
 667         TEST_CHECK(verify_pick(p, picked));
 668         TEST_CHECK(int(picked.size()) >= blocks_per_piece);
 669         for (int i = 1; i < int(picked.size()); ++i)
 670         {
 671                 TEST_CHECK(picked[i].piece_index == 1);
 672                 TEST_CHECK(picked[i].block_index == i);
 673         }
 674         p->set_piece_priority(0, 0);
 675         p->set_piece_priority(1, 0);
 676         p->set_piece_priority(2, 0);
 677         p->set_piece_priority(3, 0);
 678
 679         picked.clear();
 680         p->pick_pieces(string2vec("****************"), picked, 1, 1, 0, piece_picker::fast, true, true, suggested_pieces);
 681         print_pick(picked);
 682         TEST_CHECK(verify_pick(p, picked));
 683         TEST_CHECK(int(picked.size()) >= blocks_per_piece);
 684         for (int i = 1; i < int(picked.size()); ++i)
 685         {
 686                 TEST_CHECK(picked[i].piece_index == 5);
 687                 TEST_CHECK(picked[i].block_index == i);
 688         }
 689
 690         p = setup_picker("1111222233334444", "****            ", "", "");
 691         picked.clear();
 692         p->pick_pieces(string2vec("****************"), picked, 1, 1, 0, piece_picker::fast, true, true, suggested_pieces);
 693         print_pick(picked);
 694         TEST_CHECK(verify_pick(p, picked));
 695         TEST_CHECK(int(picked.size()) >= blocks_per_piece);
 696         for (int i = 1; i < int(picked.size()); ++i)
 697         {
 698                 TEST_CHECK(picked[i].piece_index == 5);
 699                 TEST_CHECK(picked[i].block_index == i);
 700         }
 701
 702 // MISSING TESTS:
 703 // 2. inc_ref() from 0 to 1 while sequenced download threshold is 1
 704 // 4. filtered_pieces
 705 // 5. clear peer
 706 // 6. pick_pieces with prefer whole pieces
 707 // 7. is_requested
 708 // 8. is_downloaded
 709 // 9. get_downloaders
 710 // 10. abort_download
 711
 712 /*
 713
 714         p.pick_pieces(peer1, picked, 1, false, 0, piece_picker::fast, true);
 715         TEST_CHECK(int(picked.size()) == 1);
 716         TEST_CHECK(picked.front().piece_index == 2);
 717
 718         // now pick a piece from peer2. The block is supposed to be
 719         // from piece 3, since it is the rarest piece that peer has.
 720         picked.clear();
 721         p.pick_pieces(peer2, picked, 1, false, 0, piece_picker::fast, true);
 722         TEST_CHECK(int(picked.size()) == 1);
 723         TEST_CHECK(picked.front().piece_index == 3);
 724
 725         // same thing for peer3.
 726
 727         picked.clear();
 728         p.pick_pieces(peer3, picked, 1, false, 0, piece_picker::fast, true);
 729         TEST_CHECK(int(picked.size()) == 1);
 730         TEST_CHECK(picked.front().piece_index == 5);
 731
 732         // now, if all peers would have piece 1 (the piece we have partially)
 733         // it should be prioritized over picking a completely new piece.
 734         peer3[1] = true;
 735         p.inc_refcount(1);
 736
 737         picked.clear();
 738         p.pick_pieces(peer3, picked, 1, false, 0, piece_picker::fast, true);
 739         TEST_CHECK(int(picked.size()) == 1);
 740         TEST_CHECK(picked.front().piece_index == 1);
 741         // and the block picked should not be 0 or 2
 742         // since we already have those blocks
 743
 744         TEST_CHECK(picked.front().block_index != 0);
 745         TEST_CHECK(picked.front().block_index != 2);
 746
 747         // now, if we mark piece 1 and block 0 in piece 2
 748         // as being downloaded and picks a block from peer1,
 749         // it should pick a block from piece 2. But since
 750         // block 0 is marked as requested from another peer,
 751         // the piece_picker will continue to pick blocks
 752         // until it can return at least 1 block (since we
 753         // tell it we want one block) that is not being
 754         // downloaded from anyone else. This is to make it
 755         // possible for us to determine if we want to request
 756         // the block from more than one peer.
 757         // Both piece 1 and 2 are partial pieces, but pice
 758         // 2 is the rarest, so that's why it is picked.
 759
 760         // we have block 0 and 2 already, so we can't mark
 761         // them as begin downloaded.
 762         p.mark_as_downloading(piece_block(1, 1), &peer_struct, piece_picker::fast);
 763         p.mark_as_downloading(piece_block(1, 3), &peer_struct, piece_picker::fast);
 764         p.mark_as_downloading(piece_block(2, 0), &peer_struct, piece_picker::fast);
 765
 766         std::vector<piece_picker::downloading_piece> const& downloads = p.get_download_queue();
 767         TEST_CHECK(downloads.size() == 2);
 768         TEST_CHECK(downloads[0].index == 1);
 769         TEST_CHECK(downloads[0].info[0].state == piece_picker::block_info::state_finished);
 770         TEST_CHECK(downloads[0].info[1].state == piece_picker::block_info::state_requested);
 771         TEST_CHECK(downloads[0].info[2].state == piece_picker::block_info::state_finished);
 772         TEST_CHECK(downloads[0].info[3].state == piece_picker::block_info::state_requested);
 773
 774         TEST_CHECK(downloads[1].index == 2);
 775         TEST_CHECK(downloads[1].info[0].state == piece_picker::block_info::state_requested);
 776         TEST_CHECK(downloads[1].info[1].state == piece_picker::block_info::state_none);
 777         TEST_CHECK(downloads[1].info[2].state == piece_picker::block_info::state_none);
 778         TEST_CHECK(downloads[1].info[3].state == piece_picker::block_info::state_none);
 779
 780         TEST_CHECK(p.is_requested(piece_block(1, 1)));
 781         TEST_CHECK(p.is_requested(piece_block(1, 3)));
 782         TEST_CHECK(p.is_requested(piece_block(2, 0)));
 783         TEST_CHECK(!p.is_requested(piece_block(2, 1)));
 784
 785         picked.clear();
 786         p.pick_pieces(peer1, picked, 1, false, 0, piece_picker::fast, true);
 787         TEST_CHECK(int(picked.size()) == 2);
 788
 789         piece_block expected3[] = { piece_block(2, 0), piece_block(2, 1) };
 790         TEST_CHECK(std::equal(picked.begin()
 791                 , picked.end(), expected3));
 792
 793         // now, if we assume we're downloading at such a speed that
 794         // we might prefer to download whole pieces at a time from
 795         // this peer. It should not pick piece 1 or 2 (since those are
 796         // partially selected)
 797
 798         picked.clear();
 799         p.pick_pieces(peer1, picked, 1, true, 0, piece_picker::fast, true);
 800
 801         // it will pick 4 blocks, since we said we
 802         // wanted whole pieces.
 803         TEST_CHECK(int(picked.size()) == 4);
 804
 805         piece_block expected4[] =
 806         {
 807                 piece_block(3, 0), piece_block(3, 1)
 808                 , piece_block(3, 2), piece_block(3, 3)
 809         };
 810
 811         TEST_CHECK(std::equal(picked.begin()
 812                 , picked.end(), expected4));
 813
 814         // now, try the same thing, but pick as many pieces as possible
 815         // to make sure it can still fall back on partial pieces
 816
 817         picked.clear();
 818         p.pick_pieces(peer1, picked, 100, true, 0, piece_picker::fast, true);
 819
 820         TEST_CHECK(int(picked.size()) == 12);
 821
 822         piece_block expected5[] =
 823         {
 824                 piece_block(3, 0), piece_block(3, 1)
 825                 , piece_block(3, 2), piece_block(3, 3)
 826                 , piece_block(5, 0), piece_block(5, 1)
 827                 , piece_block(5, 2), piece_block(5, 3)
 828                 , piece_block(2, 0), piece_block(2, 1)
 829                 , piece_block(2, 2), piece_block(2, 3)
 830         };
 831
 832         TEST_CHECK(std::equal(picked.begin()
 833                 , picked.end(), expected5));
 834
 835         // now, try the same thing, but pick as many pieces as possible
 836         // to make sure it can still fall back on partial pieces
 837
 838         picked.clear();
 839         p.pick_pieces(peer1, picked, 100, true, &peer_struct, piece_picker::fast, true);
 840
 841         TEST_CHECK(int(picked.size()) == 11);
 842
 843         piece_block expected6[] =
 844         {
 845                 piece_block(2, 1), piece_block(2, 2)
 846                 , piece_block(2, 3)
 847                 , piece_block(3, 0), piece_block(3, 1)
 848                 , piece_block(3, 2), piece_block(3, 3)
 849                 , piece_block(5, 0), piece_block(5, 1)
 850                 , piece_block(5, 2), piece_block(5, 3)
 851         };
 852
 853         TEST_CHECK(std::equal(picked.begin()
 854                 , picked.end(), expected6));
 855
 856         // make sure the piece picker allows filtered pieces
 857         // to become available
 858         p.mark_as_finished(piece_block(4, 2), 0);
 859 */
 860         return 0;
 861 }
 862