examples/s4u/app-bittorrent/s4u-peer.cpp

   1 /* Copyright (c) 2012-2019. The SimGrid Team. All rights reserved.          */
   2
   3 /* This program is free software; you can redistribute it and/or modify it
   4  * under the terms of the license (GNU LGPL) which comes with this package. */
   5
   6 #include <algorithm>
   7 #include <climits>
   8
   9 #include "s4u-peer.hpp"
  10 #include "s4u-tracker.hpp"
  11
  12 XBT_LOG_NEW_DEFAULT_CATEGORY(s4u_bt_peer, "Messages specific for the peers");
  13
  14 /*
  15  * User parameters for transferred file data. For the test, the default values are :
  16  * File size: 10 pieces * 5 blocks/piece * 16384 bytes/block = 819200 bytes
  17  */
  18 constexpr unsigned long FILE_PIECES   = 10UL;
  19 constexpr unsigned long PIECES_BLOCKS = 5UL;
  20 constexpr int BLOCK_SIZE              = 16384;
  21
  22 /** Number of blocks asked by each request */
  23 constexpr unsigned long BLOCKS_REQUESTED = 2UL;
  24
  25 constexpr bool ENABLE_END_GAME_MODE = true;
  26 constexpr double SLEEP_DURATION     = 1.0;
  27 #define BITS_TO_BYTES(x) (((x) / 8 + (x) % 8) ? 1 : 0)
  28
  29 Peer::Peer(std::vector<std::string> args)
  30 {
  31   // Check arguments
  32   xbt_assert(args.size() == 3 || args.size() == 4, "Wrong number of arguments");
  33   try {
  34     id       = std::stoi(args[1]);
  35     mailbox_ = simgrid::s4u::Mailbox::by_name(std::to_string(id));
  36   } catch (std::invalid_argument& ia) {
  37     throw std::invalid_argument(std::string("Invalid ID:") + args[1].c_str());
  38   }
  39
  40   try {
  41     deadline = std::stod(args[2]);
  42   } catch (std::invalid_argument& ia) {
  43     throw std::invalid_argument(std::string("Invalid deadline:") + args[2].c_str());
  44   }
  45   xbt_assert(deadline > 0, "Wrong deadline supplied");
  46
  47   stream = simgrid::s4u::this_actor::get_host()->extension<HostBittorrent>()->getStream();
  48
  49   if (args.size() == 4 && args[3] == "1") {
  50     bitfield_       = (1U << FILE_PIECES) - 1U;
  51     bitfield_blocks = (1ULL << (FILE_PIECES * PIECES_BLOCKS)) - 1ULL;
  52   }
  53   pieces_count = new short[FILE_PIECES]{0};
  54
  55   XBT_INFO("Hi, I'm joining the network with id %d", id);
  56 }
  57
  58 Peer::~Peer()
  59 {
  60   for (auto const& peer : connected_peers)
  61     delete peer.second;
  62   delete[] pieces_count;
  63 }
  64
  65 /** Peer main function */
  66 void Peer::operator()()
  67 {
  68   // Getting peer data from the tracker.
  69   if (getPeersFromTracker()) {
  70     XBT_DEBUG("Got %zu peers from the tracker. Current status is: %s", connected_peers.size(), getStatus().c_str());
  71     begin_receive_time = simgrid::s4u::Engine::get_clock();
  72     mailbox_->set_receiver(simgrid::s4u::Actor::self());
  73     if (hasFinished()) {
  74       sendHandshakeToAllPeers();
  75     } else {
  76       leech();
  77     }
  78     seed();
  79   } else {
  80     XBT_INFO("Couldn't contact the tracker.");
  81   }
  82
  83   XBT_INFO("Here is my current status: %s", getStatus().c_str());
  84 }
  85
  86 bool Peer::getPeersFromTracker()
  87 {
  88   simgrid::s4u::Mailbox* tracker_mailbox = simgrid::s4u::Mailbox::by_name(TRACKER_MAILBOX);
  89   // Build the task to send to the tracker
  90   TrackerQuery* peer_request = new TrackerQuery(id, mailbox_);
  91   try {
  92     XBT_DEBUG("Sending a peer request to the tracker.");
  93     tracker_mailbox->put(peer_request, TRACKER_COMM_SIZE, GET_PEERS_TIMEOUT);
  94   } catch (simgrid::TimeoutError& e) {
  95     XBT_DEBUG("Timeout expired when requesting peers to tracker");
  96     delete peer_request;
  97     return false;
  98   }
  99
 100   try {
 101     TrackerAnswer* answer = static_cast<TrackerAnswer*>(mailbox_->get(GET_PEERS_TIMEOUT));
 102     // Add the peers the tracker gave us to our peer list.
 103     for (auto const& peer_id : *answer->getPeers())
 104       if (id != peer_id)
 105         connected_peers[peer_id] = new Connection(peer_id);
 106     delete answer;
 107   } catch (simgrid::TimeoutError& e) {
 108     XBT_DEBUG("Timeout expired when requesting peers to tracker");
 109     return false;
 110   }
 111   return true;
 112 }
 113
 114 void Peer::sendHandshakeToAllPeers()
 115 {
 116   for (auto const& kv : connected_peers) {
 117     Connection* remote_peer = kv.second;
 118     Message* handshake      = new Message(MESSAGE_HANDSHAKE, id, mailbox_);
 119     remote_peer->mailbox_->put_init(handshake, MESSAGE_HANDSHAKE_SIZE)->detach();
 120     XBT_DEBUG("Sending a HANDSHAKE to %d", remote_peer->id);
 121   }
 122 }
 123
 124 void Peer::sendMessage(simgrid::s4u::Mailbox* mailbox, e_message_type type, uint64_t size)
 125 {
 126   const char* type_names[6] = {"HANDSHAKE", "CHOKE", "UNCHOKE", "INTERESTED", "NOTINTERESTED", "CANCEL"};
 127   XBT_DEBUG("Sending %s to %s", type_names[type], mailbox->get_cname());
 128   mailbox->put_init(new Message(type, id, bitfield_, mailbox_), size)->detach();
 129 }
 130
 131 void Peer::sendBitfield(simgrid::s4u::Mailbox* mailbox)
 132 {
 133   XBT_DEBUG("Sending a BITFIELD to %s", mailbox->get_cname());
 134   mailbox
 135       ->put_init(new Message(MESSAGE_BITFIELD, id, bitfield_, mailbox_),
 136                  MESSAGE_BITFIELD_SIZE + BITS_TO_BYTES(FILE_PIECES))
 137       ->detach();
 138 }
 139
 140 void Peer::sendPiece(simgrid::s4u::Mailbox* mailbox, unsigned int piece, int block_index, int block_length)
 141 {
 142   xbt_assert(not hasNotPiece(piece), "Tried to send a unavailable piece.");
 143   XBT_DEBUG("Sending the PIECE %u (%d,%d) to %s", piece, block_index, block_length, mailbox->get_cname());
 144   mailbox->put_init(new Message(MESSAGE_PIECE, id, mailbox_, piece, block_index, block_length), BLOCK_SIZE)->detach();
 145 }
 146
 147 void Peer::sendHaveToAllPeers(unsigned int piece)
 148 {
 149   XBT_DEBUG("Sending HAVE message to all my peers");
 150   for (auto const& kv : connected_peers) {
 151     Connection* remote_peer = kv.second;
 152     remote_peer->mailbox_->put_init(new Message(MESSAGE_HAVE, id, mailbox_, piece), MESSAGE_HAVE_SIZE)->detach();
 153   }
 154 }
 155
 156 void Peer::sendRequestTo(Connection* remote_peer, unsigned int piece)
 157 {
 158   remote_peer->current_piece = piece;
 159   xbt_assert(remote_peer->hasPiece(piece));
 160   int block_index = getFirstMissingBlockFrom(piece);
 161   if (block_index != -1) {
 162     int block_length = std::min(BLOCKS_REQUESTED, PIECES_BLOCKS - block_index);
 163     XBT_DEBUG("Sending a REQUEST to %s for piece %u (%d,%d)", remote_peer->mailbox_->get_cname(), piece, block_index,
 164               block_length);
 165     remote_peer->mailbox_
 166         ->put_init(new Message(MESSAGE_REQUEST, id, mailbox_, piece, block_index, block_length), MESSAGE_REQUEST_SIZE)
 167         ->detach();
 168   }
 169 }
 170
 171 std::string Peer::getStatus()
 172 {
 173   std::string res = std::string("");
 174   for (int i = FILE_PIECES - 1; i >= 0; i--)
 175     res = std::string((bitfield_ & (1U << i)) ? "1" : "0") + res;
 176   return res;
 177 }
 178
 179 bool Peer::hasFinished()
 180 {
 181   return bitfield_ == (1U << FILE_PIECES) - 1U;
 182 }
 183
 184 /** Indicates if the remote peer has a piece not stored by the local peer */
 185 bool Peer::isInterestedBy(Connection* remote_peer)
 186 {
 187   return remote_peer->bitfield & (bitfield_ ^ ((1 << FILE_PIECES) - 1));
 188 }
 189
 190 bool Peer::isInterestedByFree(Connection* remote_peer)
 191 {
 192   for (unsigned int i = 0; i < FILE_PIECES; i++)
 193     if (hasNotPiece(i) && remote_peer->hasPiece(i) && isNotDownloadingPiece(i))
 194       return true;
 195   return false;
 196 }
 197
 198 void Peer::updatePiecesCountFromBitfield(unsigned int bitfield)
 199 {
 200   for (unsigned int i = 0; i < FILE_PIECES; i++)
 201     if (bitfield & (1U << i))
 202       pieces_count[i]++;
 203 }
 204
 205 unsigned int Peer::countPieces(unsigned int bitfield)
 206 {
 207   unsigned int count = 0U;
 208   unsigned int n     = bitfield;
 209   while (n) {
 210     count += n & 1U;
 211     n >>= 1U;
 212   }
 213   return count;
 214 }
 215
 216 int Peer::nbInterestedPeers()
 217 {
 218   int nb = 0;
 219   for (auto const& kv : connected_peers)
 220     if (kv.second->interested)
 221       nb++;
 222   return nb;
 223 }
 224
 225 void Peer::leech()
 226 {
 227   double next_choked_update = simgrid::s4u::Engine::get_clock() + UPDATE_CHOKED_INTERVAL;
 228   XBT_DEBUG("Start downloading.");
 229
 230   /* Send a "handshake" message to all the peers it got (since it couldn't have gotten more than 50 peers) */
 231   sendHandshakeToAllPeers();
 232   XBT_DEBUG("Starting main leech loop listening on mailbox: %s", mailbox_->get_cname());
 233
 234   void* data = nullptr;
 235   while (simgrid::s4u::Engine::get_clock() < deadline && countPieces(bitfield_) < FILE_PIECES) {
 236     if (comm_received == nullptr) {
 237       comm_received = mailbox_->get_async(&data);
 238     }
 239     if (comm_received->test()) {
 240       message = static_cast<Message*>(data);
 241       handleMessage();
 242       delete message;
 243       comm_received = nullptr;
 244     } else {
 245       // We don't execute the choke algorithm if we don't already have a piece
 246       if (simgrid::s4u::Engine::get_clock() >= next_choked_update && countPieces(bitfield_) > 0) {
 247         updateChokedPeers();
 248         next_choked_update += UPDATE_CHOKED_INTERVAL;
 249       } else {
 250         simgrid::s4u::this_actor::sleep_for(SLEEP_DURATION);
 251       }
 252     }
 253   }
 254   if (hasFinished())
 255     XBT_DEBUG("%d becomes a seeder", id);
 256 }
 257
 258 void Peer::seed()
 259 {
 260   double next_choked_update = simgrid::s4u::Engine::get_clock() + UPDATE_CHOKED_INTERVAL;
 261   XBT_DEBUG("Start seeding.");
 262   // start the main seed loop
 263   void* data = nullptr;
 264   while (simgrid::s4u::Engine::get_clock() < deadline) {
 265     if (comm_received == nullptr) {
 266       comm_received = mailbox_->get_async(&data);
 267     }
 268     if (comm_received->test()) {
 269       message = static_cast<Message*>(data);
 270       handleMessage();
 271       delete message;
 272       comm_received = nullptr;
 273     } else {
 274       if (simgrid::s4u::Engine::get_clock() >= next_choked_update) {
 275         updateChokedPeers();
 276         // TODO: Change the choked peer algorithm when seeding.
 277         next_choked_update += UPDATE_CHOKED_INTERVAL;
 278       } else {
 279         simgrid::s4u::this_actor::sleep_for(SLEEP_DURATION);
 280       }
 281     }
 282   }
 283 }
 284
 285 void Peer::updateActivePeersSet(Connection* remote_peer)
 286 {
 287   if (remote_peer->interested && not remote_peer->choked_upload)
 288     active_peers.insert(remote_peer);
 289   else
 290     active_peers.erase(remote_peer);
 291 }
 292
 293 void Peer::handleMessage()
 294 {
 295   const char* type_names[10] = {"HANDSHAKE", "CHOKE",    "UNCHOKE", "INTERESTED", "NOTINTERESTED",
 296                                 "HAVE",      "BITFIELD", "REQUEST", "PIECE",      "CANCEL"};
 297
 298   XBT_DEBUG("Received a %s message from %s", type_names[message->type], message->return_mailbox->get_cname());
 299
 300   auto known_peer         = connected_peers.find(message->peer_id);
 301   Connection* remote_peer = (known_peer == connected_peers.end()) ? nullptr : known_peer->second;
 302   xbt_assert(remote_peer != nullptr || message->type == MESSAGE_HANDSHAKE,
 303              "The impossible did happened: A not-in-our-list peer sent us a message.");
 304
 305   switch (message->type) {
 306     case MESSAGE_HANDSHAKE:
 307       // Check if the peer is in our connection list.
 308       if (remote_peer == nullptr) {
 309         XBT_DEBUG("This peer %d was unknown, answer to its handshake", message->peer_id);
 310         connected_peers[message->peer_id] = new Connection(message->peer_id);
 311         sendMessage(message->return_mailbox, MESSAGE_HANDSHAKE, MESSAGE_HANDSHAKE_SIZE);
 312       }
 313       // Send our bitfield to the peer
 314       sendBitfield(message->return_mailbox);
 315       break;
 316     case MESSAGE_BITFIELD:
 317       // Update the pieces list
 318       updatePiecesCountFromBitfield(message->bitfield);
 319       // Store the bitfield
 320       remote_peer->bitfield = message->bitfield;
 321       xbt_assert(not remote_peer->am_interested, "Should not be interested at first");
 322       if (isInterestedBy(remote_peer)) {
 323         remote_peer->am_interested = true;
 324         sendMessage(message->return_mailbox, MESSAGE_INTERESTED, MESSAGE_INTERESTED_SIZE);
 325       }
 326       break;
 327     case MESSAGE_INTERESTED:
 328       // Update the interested state of the peer.
 329       remote_peer->interested = true;
 330       updateActivePeersSet(remote_peer);
 331       break;
 332     case MESSAGE_NOTINTERESTED:
 333       remote_peer->interested = false;
 334       updateActivePeersSet(remote_peer);
 335       break;
 336     case MESSAGE_UNCHOKE:
 337       xbt_assert(remote_peer->choked_download);
 338       remote_peer->choked_download = false;
 339       // Send requests to the peer, since it has unchoked us
 340       if (remote_peer->am_interested)
 341         requestNewPieceTo(remote_peer);
 342       break;
 343     case MESSAGE_CHOKE:
 344       xbt_assert(not remote_peer->choked_download);
 345       remote_peer->choked_download = true;
 346       if (remote_peer->current_piece != -1)
 347         removeCurrentPiece(remote_peer, remote_peer->current_piece);
 348       break;
 349     case MESSAGE_HAVE:
 350       XBT_DEBUG("\t for piece %d", message->piece);
 351       xbt_assert((message->piece >= 0 && static_cast<unsigned int>(message->piece) < FILE_PIECES),
 352                  "Wrong HAVE message received");
 353       remote_peer->bitfield = remote_peer->bitfield | (1U << static_cast<unsigned int>(message->piece));
 354       pieces_count[message->piece]++;
 355       // If the piece is in our pieces, we tell the peer that we are interested.
 356       if (not remote_peer->am_interested && hasNotPiece(message->piece)) {
 357         remote_peer->am_interested = true;
 358         sendMessage(message->return_mailbox, MESSAGE_INTERESTED, MESSAGE_INTERESTED_SIZE);
 359         if (not remote_peer->choked_download)
 360           requestNewPieceTo(remote_peer);
 361       }
 362       break;
 363     case MESSAGE_REQUEST:
 364       xbt_assert(remote_peer->interested);
 365       xbt_assert((message->piece >= 0 && static_cast<unsigned int>(message->piece) < FILE_PIECES),
 366                  "Wrong HAVE message received");
 367       if (not remote_peer->choked_upload) {
 368         XBT_DEBUG("\t for piece %d (%d,%d)", message->piece, message->block_index,
 369                   message->block_index + message->block_length);
 370         if (not hasNotPiece(message->piece)) {
 371           sendPiece(message->return_mailbox, message->piece, message->block_index, message->block_length);
 372         }
 373       } else {
 374         XBT_DEBUG("\t for piece %d but he is choked.", message->peer_id);
 375       }
 376       break;
 377     case MESSAGE_PIECE:
 378       XBT_DEBUG(" \t for piece %d (%d,%d)", message->piece, message->block_index,
 379                 message->block_index + message->block_length);
 380       xbt_assert(not remote_peer->choked_download);
 381       xbt_assert(remote_peer->am_interested || ENABLE_END_GAME_MODE,
 382                  "Can't received a piece if I'm not interested without end-game mode!"
 383                  "piece (%d) bitfield (%u) remote bitfield (%u)",
 384                  message->piece, bitfield_, remote_peer->bitfield);
 385       xbt_assert(not remote_peer->choked_download, "Can't received a piece if I'm choked !");
 386       xbt_assert((message->piece >= 0 && static_cast<unsigned int>(message->piece) < FILE_PIECES),
 387                  "Wrong piece received");
 388       // TODO: Execute a computation.
 389       if (hasNotPiece(static_cast<unsigned int>(message->piece))) {
 390         updateBitfieldBlocks(message->piece, message->block_index, message->block_length);
 391         if (hasCompletedPiece(static_cast<unsigned int>(message->piece))) {
 392           // Removing the piece from our piece list
 393           removeCurrentPiece(remote_peer, message->piece);
 394           // Setting the fact that we have the piece
 395           bitfield_ = bitfield_ | (1U << static_cast<unsigned int>(message->piece));
 396           XBT_DEBUG("My status is now %s", getStatus().c_str());
 397           // Sending the information to all the peers we are connected to
 398           sendHaveToAllPeers(message->piece);
 399           // sending UNINTERESTED to peers that do not have what we want.
 400           updateInterestedAfterReceive();
 401         } else {                                      // piece not completed
 402           sendRequestTo(remote_peer, message->piece); // ask for the next block
 403         }
 404       } else {
 405         XBT_DEBUG("However, we already have it");
 406         xbt_assert(ENABLE_END_GAME_MODE, "Should not happen because we don't use end game mode !");
 407         requestNewPieceTo(remote_peer);
 408       }
 409       break;
 410     case MESSAGE_CANCEL:
 411       break;
 412     default:
 413       THROW_IMPOSSIBLE;
 414   }
 415   // Update the peer speed.
 416   if (remote_peer) {
 417     remote_peer->addSpeedValue(1.0 / (simgrid::s4u::Engine::get_clock() - begin_receive_time));
 418   }
 419   begin_receive_time = simgrid::s4u::Engine::get_clock();
 420 }
 421
 422 /** Selects the appropriate piece to download and requests it to the remote_peer */
 423 void Peer::requestNewPieceTo(Connection* remote_peer)
 424 {
 425   int piece = selectPieceToDownload(remote_peer);
 426   if (piece != -1) {
 427     current_pieces |= (1U << (unsigned int)piece);
 428     sendRequestTo(remote_peer, piece);
 429   }
 430 }
 431
 432 void Peer::removeCurrentPiece(Connection* remote_peer, unsigned int current_piece)
 433 {
 434   current_pieces &= ~(1U << current_piece);
 435   remote_peer->current_piece = -1;
 436 }
 437
 438 /** @brief Return the piece to be downloaded
 439  * There are two cases (as described in "Bittorrent Architecture Protocol", Ryan Toole :
 440  * If a piece is partially downloaded, this piece will be selected prioritarily
 441  * If the peer has strictly less than 4 pieces, he chooses a piece at random.
 442  * If the peer has more than pieces, he downloads the pieces that are the less replicated (rarest policy).
 443  * If all pieces have been downloaded or requested, we select a random requested piece (endgame mode).
 444  * @param remote_peer: information about the connection
 445  * @return the piece to download if possible. -1 otherwise
 446  */
 447 int Peer::selectPieceToDownload(Connection* remote_peer)
 448 {
 449   int piece = partiallyDownloadedPiece(remote_peer);
 450   // strict priority policy
 451   if (piece != -1)
 452     return piece;
 453
 454   // end game mode
 455   if (countPieces(current_pieces) >= (FILE_PIECES - countPieces(bitfield_)) && isInterestedBy(remote_peer)) {
 456     if (not ENABLE_END_GAME_MODE)
 457       return -1;
 458     int nb_interesting_pieces = 0;
 459     // compute the number of interesting pieces
 460     for (unsigned int i = 0; i < FILE_PIECES; i++)
 461       if (hasNotPiece(i) && remote_peer->hasPiece(i))
 462         nb_interesting_pieces++;
 463
 464     xbt_assert(nb_interesting_pieces != 0);
 465     // get a random interesting piece
 466     int random_piece_index = RngStream_RandInt(stream, 0, nb_interesting_pieces - 1);
 467     int current_index      = 0;
 468     for (unsigned int i = 0; i < FILE_PIECES; i++) {
 469       if (hasNotPiece(i) && remote_peer->hasPiece(i)) {
 470         if (random_piece_index == current_index) {
 471           piece = i;
 472           break;
 473         }
 474         current_index++;
 475       }
 476     }
 477     xbt_assert(piece != -1);
 478     return piece;
 479   }
 480   // Random first policy
 481   if (countPieces(bitfield_) < 4 && isInterestedByFree(remote_peer)) {
 482     int nb_interesting_pieces = 0;
 483     // compute the number of interesting pieces
 484     for (unsigned int i = 0; i < FILE_PIECES; i++)
 485       if (hasNotPiece(i) && remote_peer->hasPiece(i) && isNotDownloadingPiece(i))
 486         nb_interesting_pieces++;
 487     xbt_assert(nb_interesting_pieces != 0);
 488     // get a random interesting piece
 489     int random_piece_index = RngStream_RandInt(stream, 0, nb_interesting_pieces - 1);
 490     int current_index      = 0;
 491     for (unsigned int i = 0; i < FILE_PIECES; i++) {
 492       if (hasNotPiece(i) && remote_peer->hasPiece(i) && isNotDownloadingPiece(i)) {
 493         if (random_piece_index == current_index) {
 494           piece = i;
 495           break;
 496         }
 497         current_index++;
 498       }
 499     }
 500     xbt_assert(piece != -1);
 501     return piece;
 502   } else { // Rarest first policy
 503     short min         = SHRT_MAX;
 504     int nb_min_pieces = 0;
 505     int current_index = 0;
 506     // compute the smallest number of copies of available pieces
 507     for (unsigned int i = 0; i < FILE_PIECES; i++) {
 508       if (pieces_count[i] < min && hasNotPiece(i) && remote_peer->hasPiece(i) && isNotDownloadingPiece(i))
 509         min = pieces_count[i];
 510     }
 511
 512     xbt_assert(min != SHRT_MAX || not isInterestedByFree(remote_peer));
 513     // compute the number of rarest pieces
 514     for (unsigned int i = 0; i < FILE_PIECES; i++)
 515       if (pieces_count[i] == min && hasNotPiece(i) && remote_peer->hasPiece(i) && isNotDownloadingPiece(i))
 516         nb_min_pieces++;
 517
 518     xbt_assert(nb_min_pieces != 0 || not isInterestedByFree(remote_peer));
 519     // get a random rarest piece
 520     int random_rarest_index = RngStream_RandInt(stream, 0, nb_min_pieces - 1);
 521     for (unsigned int i = 0; i < FILE_PIECES; i++)
 522       if (pieces_count[i] == min && hasNotPiece(i) && remote_peer->hasPiece(i) && isNotDownloadingPiece(i)) {
 523         if (random_rarest_index == current_index) {
 524           piece = i;
 525           break;
 526         }
 527         current_index++;
 528       }
 529
 530     xbt_assert(piece != -1 || not isInterestedByFree(remote_peer));
 531     return piece;
 532   }
 533 }
 534
 535 void Peer::updateChokedPeers()
 536 {
 537   if (nbInterestedPeers() == 0)
 538     return;
 539   XBT_DEBUG("(%d) update_choked peers %zu active peers", id, active_peers.size());
 540   // update the current round
 541   round_                  = (round_ + 1) % 3;
 542   Connection* chosen_peer = nullptr;
 543   // select first active peer and remove it from the set
 544   Connection* choked_peer;
 545   if (active_peers.empty()) {
 546     choked_peer = nullptr;
 547   } else {
 548     choked_peer = *active_peers.begin();
 549     active_peers.erase(choked_peer);
 550   }
 551
 552   /**If we are currently seeding, we unchoke the peer which has been unchoked the last time.*/
 553   if (hasFinished()) {
 554     Connection* remote_peer;
 555     double unchoke_time = simgrid::s4u::Engine::get_clock() + 1;
 556     for (auto const& kv : connected_peers) {
 557       remote_peer = kv.second;
 558       if (remote_peer->last_unchoke < unchoke_time && remote_peer->interested && remote_peer->choked_upload) {
 559         unchoke_time = remote_peer->last_unchoke;
 560         chosen_peer  = remote_peer;
 561       }
 562     }
 563   } else {
 564     // Random optimistic unchoking
 565     if (round_ == 0) {
 566       int j = 0;
 567       do {
 568         // We choose a random peer to unchoke.
 569         std::unordered_map<int, Connection*>::iterator chosen_peer_it = connected_peers.begin();
 570         std::advance(chosen_peer_it, RngStream_RandInt(stream, 0, connected_peers.size() - 1));
 571         chosen_peer = chosen_peer_it->second;
 572         if (chosen_peer == nullptr)
 573           THROWF(unknown_error, 0, "A peer should have be selected at this point");
 574         else if (not chosen_peer->interested || not chosen_peer->choked_upload)
 575           chosen_peer = nullptr;
 576         else
 577           XBT_DEBUG("Nothing to do, keep going");
 578         j++;
 579       } while (chosen_peer == nullptr && j < MAXIMUM_PEERS);
 580     } else {
 581       // Use the "fastest download" policy.
 582       double fastest_speed = 0.0;
 583       for (auto const& kv : connected_peers) {
 584         Connection* remote_peer = kv.second;
 585         if (remote_peer->peer_speed > fastest_speed && remote_peer->choked_upload && remote_peer->interested) {
 586           chosen_peer   = remote_peer;
 587           fastest_speed = remote_peer->peer_speed;
 588         }
 589       }
 590     }
 591   }
 592
 593   if (chosen_peer != nullptr)
 594     XBT_DEBUG("(%d) update_choked peers unchoked (%d) ; int (%d) ; choked (%d) ", id, chosen_peer->id,
 595               chosen_peer->interested, chosen_peer->choked_upload);
 596
 597   if (choked_peer != chosen_peer) {
 598     if (choked_peer != nullptr) {
 599       xbt_assert(not choked_peer->choked_upload, "Tries to choked a choked peer");
 600       choked_peer->choked_upload = true;
 601       updateActivePeersSet(choked_peer);
 602       XBT_DEBUG("(%d) Sending a CHOKE to %d", id, choked_peer->id);
 603       sendMessage(choked_peer->mailbox_, MESSAGE_CHOKE, MESSAGE_CHOKE_SIZE);
 604     }
 605     if (chosen_peer != nullptr) {
 606       xbt_assert((chosen_peer->choked_upload), "Tries to unchoked an unchoked peer");
 607       chosen_peer->choked_upload = false;
 608       active_peers.insert(chosen_peer);
 609       chosen_peer->last_unchoke = simgrid::s4u::Engine::get_clock();
 610       XBT_DEBUG("(%d) Sending a UNCHOKE to %d", id, chosen_peer->id);
 611       updateActivePeersSet(chosen_peer);
 612       sendMessage(chosen_peer->mailbox_, MESSAGE_UNCHOKE, MESSAGE_UNCHOKE_SIZE);
 613     }
 614   }
 615 }
 616
 617 /** @brief Update "interested" state of peers: send "not interested" to peers that don't have any more pieces we want.*/
 618 void Peer::updateInterestedAfterReceive()
 619 {
 620   for (auto const& kv : connected_peers) {
 621     Connection* remote_peer = kv.second;
 622     if (remote_peer->am_interested) {
 623       bool interested = false;
 624       // Check if the peer still has a piece we want.
 625       for (unsigned int i = 0; i < FILE_PIECES; i++)
 626         if (hasNotPiece(i) && remote_peer->hasPiece(i)) {
 627           interested = true;
 628           break;
 629         }
 630
 631       if (not interested) { // no more piece to download from connection
 632         remote_peer->am_interested = false;
 633         sendMessage(remote_peer->mailbox_, MESSAGE_NOTINTERESTED, MESSAGE_NOTINTERESTED_SIZE);
 634       }
 635     }
 636   }
 637 }
 638
 639 void Peer::updateBitfieldBlocks(int piece, int block_index, int block_length)
 640 {
 641   xbt_assert((piece >= 0 && static_cast<unsigned int>(piece) <= FILE_PIECES), "Wrong piece.");
 642   xbt_assert((block_index >= 0 && static_cast<unsigned int>(block_index) <= PIECES_BLOCKS), "Wrong block : %d.",
 643              block_index);
 644   for (int i = block_index; i < (block_index + block_length); i++)
 645     bitfield_blocks |= (1ULL << static_cast<unsigned int>(piece * PIECES_BLOCKS + i));
 646 }
 647
 648 bool Peer::hasCompletedPiece(unsigned int piece)
 649 {
 650   for (unsigned int i = 0; i < PIECES_BLOCKS; i++)
 651     if (not(bitfield_blocks & 1ULL << (piece * PIECES_BLOCKS + i)))
 652       return false;
 653   return true;
 654 }
 655
 656 int Peer::getFirstMissingBlockFrom(int piece)
 657 {
 658   for (unsigned int i = 0; i < PIECES_BLOCKS; i++)
 659     if (not(bitfield_blocks & 1ULL << (piece * PIECES_BLOCKS + i)))
 660       return i;
 661   return -1;
 662 }
 663
 664 /** Returns a piece that is partially downloaded and stored by the remote peer if any -1 otherwise. */
 665 int Peer::partiallyDownloadedPiece(Connection* remote_peer)
 666 {
 667   for (unsigned int i = 0; i < FILE_PIECES; i++)
 668     if (hasNotPiece(i) && remote_peer->hasPiece(i) && isNotDownloadingPiece(i) && getFirstMissingBlockFrom(i) > 0)
 669       return i;
 670   return -1;
 671 }