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

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