Logo AND Algorithmique Numérique Distribuée

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