?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
file_progress fix
[libtorrent.git] / src / piece_picker.cpp
blob9e62e637965f57a0b8467d471c911276bd155425
1 /*
2
3 Copyright (c) 2003, Arvid Norberg
4 All rights reserved.
5
6 Redistribution and use in source and binary forms, with or without
7 modification, are permitted provided that the following conditions
8 are met:
9
10 * Redistributions of source code must retain the above copyright
11 notice, this list of conditions and the following disclaimer.
12 * Redistributions in binary form must reproduce the above copyright
13 notice, this list of conditions and the following disclaimer in
14 the documentation and/or other materials provided with the distribution.
15 * Neither the name of the author nor the names of its
16 contributors may be used to endorse or promote products derived
17 from this software without specific prior written permission.
18
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
23 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 POSSIBILITY OF SUCH DAMAGE.
30
31 */
32
33 #include "libtorrent/pch.hpp"
34
35 #include <vector>
36 #include <cmath>
37 #include <algorithm>
38 #include <numeric>
39
40 #include "libtorrent/piece_picker.hpp"
41 #include "libtorrent/aux_/session_impl.hpp"
42 #include "libtorrent/bitfield.hpp"
43
44 #ifndef NDEBUG
45 #include "libtorrent/peer_connection.hpp"
46 #include "libtorrent/torrent.hpp"
47 #endif
48
49 //#define TORRENT_PIECE_PICKER_INVARIANT_CHECK INVARIANT_CHECK
50 //#define TORRENT_NO_EXPENSIVE_INVARIANT_CHECK
51 #define TORRENT_PIECE_PICKER_INVARIANT_CHECK
52
53 //#define TORRENT_PICKER_LOG
54
55 namespace libtorrent
56 {
57
58 piece_picker::piece_picker()
59 : m_seeds(0)
60 , m_priority_boundries(1, int(m_pieces.size()))
61 , m_num_filtered(0)
62 , m_num_have_filtered(0)
63 , m_num_have(0)
64 , m_sequential_download(-1)
65 , m_dirty(false)
66 {
67 #ifdef TORRENT_PICKER_LOG
68 std::cerr << "new piece_picker" << std::endl;
69 #endif
70 #ifndef NDEBUG
71 check_invariant();
72 #endif
73 }
74
75 void piece_picker::init(int blocks_per_piece, int total_num_blocks)
76 {
77 TORRENT_ASSERT(blocks_per_piece > 0);
78 TORRENT_ASSERT(total_num_blocks >= 0);
79
80 // allocate the piece_map to cover all pieces
81 // and make them invalid (as if we don't have a single piece)
82 m_piece_map.resize((total_num_blocks + blocks_per_piece-1) / blocks_per_piece
83 , piece_pos(0, 0));
84
85 // the piece index is stored in 20 bits, which limits the allowed
86 // number of pieces somewhat
87 if (m_piece_map.size() >= piece_pos::we_have_index)
88 throw std::runtime_error("too many pieces in torrent");
89
90 m_blocks_per_piece = blocks_per_piece;
91 m_blocks_in_last_piece = total_num_blocks % blocks_per_piece;
92 if (m_blocks_in_last_piece == 0) m_blocks_in_last_piece = blocks_per_piece;
93
94 TORRENT_ASSERT(m_blocks_in_last_piece <= m_blocks_per_piece);
95 }
96
97 void piece_picker::sequential_download(bool sd)
98 {
99 if (sd == sequential_download()) return;
100
101 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
102
103 if (sd)
104 {
105 std::vector<int>().swap(m_pieces);
106 std::vector<int>().swap(m_priority_boundries);
107
108 // initialize m_sdquential_download
109 m_sequential_download = 0;
110 for (std::vector<piece_pos>::const_iterator i = m_piece_map.begin()
111 , end(m_piece_map.end()); i != end && (i->have() || i->filtered());
112 ++i, ++m_sequential_download);
113 }
114 else
115 {
116 m_sequential_download = -1;
117 m_dirty = true;
118 }
119 }
120
121 void piece_picker::piece_info(int index, piece_picker::downloading_piece& st) const
122 {
123 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
124
125 TORRENT_ASSERT(index >= 0);
126 TORRENT_ASSERT(index < int(m_piece_map.size()));
127
128 if (m_piece_map[index].downloading)
129 {
130 std::vector<downloading_piece>::const_iterator piece = std::find_if(
131 m_downloads.begin(), m_downloads.end()
132 , bind(&downloading_piece::index, _1) == index);
133 TORRENT_ASSERT(piece != m_downloads.end());
134 st = *piece;
135 st.info = 0;
136 return;
137 }
138 st.info = 0;
139 st.index = index;
140 st.writing = 0;
141 st.requested = 0;
142 if (m_piece_map[index].have())
143 {
144 st.finished = blocks_in_piece(index);
145 return;
146 }
147 st.finished = 0;
148 }
149
150 piece_picker::downloading_piece& piece_picker::add_download_piece()
151 {
152 int num_downloads = m_downloads.size();
153 int block_index = num_downloads * m_blocks_per_piece;
154 if (int(m_block_info.size()) < block_index + m_blocks_per_piece)
155 {
156 block_info* base = 0;
157 if (!m_block_info.empty()) base = &m_block_info[0];
158 m_block_info.resize(block_index + m_blocks_per_piece);
159 if (!m_downloads.empty() && &m_block_info[0] != base)
160 {
161 // this means the memory was reallocated, update the pointers
162 for (int i = 0; i < int(m_downloads.size()); ++i)
163 m_downloads[i].info = &m_block_info[m_downloads[i].info - base];
164 }
165 }
166 m_downloads.push_back(downloading_piece());
167 downloading_piece& ret = m_downloads.back();
168 ret.info = &m_block_info[block_index];
169 for (int i = 0; i < m_blocks_per_piece; ++i)
170 {
171 ret.info[i].num_peers = 0;
172 ret.info[i].state = block_info::state_none;
173 ret.info[i].peer = 0;
174 }
175 return ret;
176 }
177
178 void piece_picker::erase_download_piece(std::vector<downloading_piece>::iterator i)
179 {
180 std::vector<downloading_piece>::iterator other = std::find_if(
181 m_downloads.begin(), m_downloads.end()
182 , bind(&downloading_piece::info, _1)
183 == &m_block_info[(m_downloads.size() - 1) * m_blocks_per_piece]);
184 TORRENT_ASSERT(other != m_downloads.end());
185
186 if (i != other)
187 {
188 std::copy(other->info, other->info + m_blocks_per_piece, i->info);
189 other->info = i->info;
190 }
191 m_downloads.erase(i);
192 }
193
194 #ifndef NDEBUG
195
196 void piece_picker::verify_pick(std::vector<piece_block> const& picked
197 , bitfield const& bits) const
198 {
199 TORRENT_ASSERT(bits.size() == m_piece_map.size());
200 for (std::vector<piece_block>::const_iterator i = picked.begin()
201 , end(picked.end()); i != end; ++i)
202 {
203 TORRENT_ASSERT(i->piece_index >= 0);
204 TORRENT_ASSERT(i->piece_index < int(bits.size()));
205 TORRENT_ASSERT(bits[i->piece_index]);
206 TORRENT_ASSERT(!m_piece_map[i->piece_index].have());
207 }
208 }
209
210 void piece_picker::verify_priority(int range_start, int range_end, int prio) const
211 {
212 TORRENT_ASSERT(range_start <= range_end);
213 TORRENT_ASSERT(range_end <= int(m_pieces.size()));
214 for (std::vector<int>::const_iterator i = m_pieces.begin() + range_start
215 , end(m_pieces.begin() + range_end); i != end; ++i)
216 {
217 int index = *i;
218 TORRENT_ASSERT(index >= 0);
219 TORRENT_ASSERT(index < int(m_piece_map.size()));
220 int p = m_piece_map[index].priority(this);
221 TORRENT_ASSERT(p == prio);
222 }
223 }
224
225 void piece_picker::print_pieces() const
226 {
227 for (std::vector<int>::const_iterator i = m_priority_boundries.begin()
228 , end(m_priority_boundries.end()); i != end; ++i)
229 {
230 std::cerr << *i << " ";
231 }
232 std::cout << std::endl;
233 int index = 0;
234 std::vector<int>::const_iterator j = m_priority_boundries.begin();
235 for (std::vector<int>::const_iterator i = m_pieces.begin()
236 , end(m_pieces.end()); i != end; ++i, ++index)
237 {
238 if (*i == -1) break;
239 while (j != m_priority_boundries.end() && *j <= index)
240 {
241 std::cerr << "| ";
242 ++j;
243 }
244 std::cerr << *i << "(" << m_piece_map[*i].index << ") ";
245 }
246 std::cerr << std::endl;
247 }
248
249 void piece_picker::check_invariant(const torrent* t) const
250 {
251 TORRENT_ASSERT(sizeof(piece_pos) == 4);
252 TORRENT_ASSERT(m_num_have >= 0);
253 TORRENT_ASSERT(m_num_have_filtered >= 0);
254 TORRENT_ASSERT(m_num_filtered >= 0);
255 TORRENT_ASSERT(m_seeds >= 0);
256
257 if (!m_downloads.empty())
258 {
259 for (std::vector<downloading_piece>::const_iterator i = m_downloads.begin();
260 i != m_downloads.end() - 1; ++i)
261 {
262 downloading_piece const& dp = *i;
263 downloading_piece const& next = *(i + 1);
264 TORRENT_ASSERT(dp.finished + dp.writing >= next.finished + next.writing);
265 }
266 }
267
268 if (t != 0)
269 TORRENT_ASSERT((int)m_piece_map.size() == t->torrent_file().num_pieces());
270
271 for (std::vector<downloading_piece>::const_iterator i = m_downloads.begin()
272 , end(m_downloads.end()); i != end; ++i)
273 {
274 bool blocks_requested = false;
275 int num_blocks = blocks_in_piece(i->index);
276 int num_requested = 0;
277 int num_finished = 0;
278 int num_writing = 0;
279 for (int k = 0; k < num_blocks; ++k)
280 {
281 if (i->info[k].state == block_info::state_finished)
282 {
283 ++num_finished;
284 TORRENT_ASSERT(i->info[k].num_peers == 0);
285 }
286 else if (i->info[k].state == block_info::state_requested)
287 {
288 ++num_requested;
289 blocks_requested = true;
290 TORRENT_ASSERT(i->info[k].num_peers > 0);
291 }
292 else if (i->info[k].state == block_info::state_writing)
293 {
294 ++num_writing;
295 TORRENT_ASSERT(i->info[k].num_peers == 0);
296 }
297 }
298 TORRENT_ASSERT(blocks_requested == (i->state != none));
299 TORRENT_ASSERT(num_requested == i->requested);
300 TORRENT_ASSERT(num_writing == i->writing);
301 TORRENT_ASSERT(num_finished == i->finished);
302 }
303 #ifdef TORRENT_NO_EXPENSIVE_INVARIANT_CHECK
304 return;
305 #endif
306
307 if (m_sequential_download == -1 && !m_dirty)
308 {
309 TORRENT_ASSERT(!m_priority_boundries.empty());
310 int prio = 0;
311 int start = 0;
312 for (std::vector<int>::const_iterator i = m_priority_boundries.begin()
313 , end(m_priority_boundries.end()); i != end; ++i)
314 {
315 verify_priority(start, *i, prio);
316 ++prio;
317 start = *i;
318 }
319 TORRENT_ASSERT(m_priority_boundries.back() == int(m_pieces.size()));
320 }
321 else if (m_sequential_download >= 0)
322 {
323 int index = 0;
324 for (std::vector<piece_pos>::const_iterator i = m_piece_map.begin()
325 , end(m_piece_map.end()); i != end && (i->have() || i->filtered());
326 ++i, ++index);
327 TORRENT_ASSERT(m_sequential_download == index);
328 }
329
330 int num_filtered = 0;
331 int num_have_filtered = 0;
332 int num_have = 0;
333 for (std::vector<piece_pos>::const_iterator i = m_piece_map.begin();
334 i != m_piece_map.end(); ++i)
335 {
336 int index = static_cast<int>(i - m_piece_map.begin());
337 piece_pos const& p = *i;
338
339 if (p.filtered())
340 {
341 if (p.index != piece_pos::we_have_index)
342 ++num_filtered;
343 else
344 ++num_have_filtered;
345 }
346 if (p.index == piece_pos::we_have_index)
347 ++num_have;
348
349 #if 0
350 if (t != 0)
351 {
352 int actual_peer_count = 0;
353 for (torrent::const_peer_iterator peer = t->begin();
354 peer != t->end(); ++peer)
355 {
356 if (peer->second->has_piece(index)) actual_peer_count++;
357 }
358
359 TORRENT_ASSERT((int)i->peer_count == actual_peer_count);
360 /*
361 int num_downloaders = 0;
362 for (std::vector<peer_connection*>::const_iterator peer = t->begin();
363 peer != t->end();
364 ++peer)
365 {
366 const std::vector<piece_block>& queue = (*peer)->download_queue();
367 if (std::find_if(queue.begin(), queue.end(), has_index(index)) == queue.end()) continue;
368
369 ++num_downloaders;
370 }
371
372 if (i->downloading)
373 {
374 TORRENT_ASSERT(num_downloaders == 1);
375 }
376 else
377 {
378 TORRENT_ASSERT(num_downloaders == 0);
379 }
380 */
381 }
382 #endif
383
384 if (p.index == piece_pos::we_have_index)
385 {
386 TORRENT_ASSERT(t == 0 || t->have_piece(index));
387 TORRENT_ASSERT(p.downloading == 0);
388 }
389
390 if (t != 0)
391 TORRENT_ASSERT(!t->have_piece(index));
392
393 if (m_sequential_download == -1 && !m_dirty)
394 {
395 int prio = p.priority(this);
396 TORRENT_ASSERT(prio < int(m_priority_boundries.size())
397 || m_dirty);
398 if (prio >= 0)
399 {
400 TORRENT_ASSERT(p.index < m_pieces.size());
401 TORRENT_ASSERT(m_pieces[p.index] == index);
402 }
403 else
404 {
405 TORRENT_ASSERT(prio == -1);
406 // make sure there's no entry
407 // with this index. (there shouldn't
408 // be since the priority is -1)
409 TORRENT_ASSERT(std::find(m_pieces.begin(), m_pieces.end(), index)
410 == m_pieces.end());
411 }
412 }
413 else if (m_sequential_download >= 0)
414 {
415 TORRENT_ASSERT(m_pieces.empty());
416 TORRENT_ASSERT(m_priority_boundries.empty());
417 }
418
419 int count = std::count_if(m_downloads.begin(), m_downloads.end()
420 , has_index(index));
421 if (i->downloading == 1)
422 {
423 TORRENT_ASSERT(count == 1);
424 }
425 else
426 {
427 TORRENT_ASSERT(count == 0);
428 }
429 }
430 TORRENT_ASSERT(num_have == m_num_have);
431 TORRENT_ASSERT(num_filtered == m_num_filtered);
432 TORRENT_ASSERT(num_have_filtered == m_num_have_filtered);
433
434 if (!m_dirty)
435 {
436 for (std::vector<int>::const_iterator i = m_pieces.begin()
437 , end(m_pieces.end()); i != end; ++i)
438 {
439 TORRENT_ASSERT(m_piece_map[*i].priority(this) >= 0);
440 }
441 }
442 }
443 #endif
444
445 float piece_picker::distributed_copies() const
446 {
447 TORRENT_ASSERT(m_seeds >= 0);
448 const float num_pieces = static_cast<float>(m_piece_map.size());
449
450 int min_availability = piece_pos::max_peer_count;
451 // find the lowest availability count
452 // count the number of pieces that have that availability
453 // and also the number of pieces that have more than that.
454 int integer_part = 0;
455 int fraction_part = 0;
456 for (std::vector<piece_pos>::const_iterator i = m_piece_map.begin()
457 , end(m_piece_map.end()); i != end; ++i)
458 {
459 int peer_count = int(i->peer_count);
460 // take ourself into account
461 if (i->have()) ++peer_count;
462 if (min_availability > peer_count)
463 {
464 min_availability = peer_count;
465 fraction_part += integer_part;
466 integer_part = 1;
467 }
468 else if (peer_count == min_availability)
469 {
470 ++integer_part;
471 }
472 else
473 {
474 TORRENT_ASSERT(peer_count > min_availability);
475 ++fraction_part;
476 }
477 }
478 TORRENT_ASSERT(integer_part + fraction_part == num_pieces);
479 return float(min_availability + m_seeds) + (fraction_part / num_pieces);
480 }
481
482 void piece_picker::priority_range(int prio, int* start, int* end)
483 {
484 TORRENT_ASSERT(prio >= 0);
485 TORRENT_ASSERT(prio < int(m_priority_boundries.size())
486 || m_dirty);
487 if (prio == 0) *start = 0;
488 else *start = m_priority_boundries[prio - 1];
489 *end = m_priority_boundries[prio];
490 TORRENT_ASSERT(*start <= *end);
491 }
492
493 void piece_picker::add(int index)
494 {
495 TORRENT_ASSERT(!m_dirty);
496 TORRENT_ASSERT(index >= 0);
497 TORRENT_ASSERT(index < int(m_piece_map.size()));
498 piece_pos& p = m_piece_map[index];
499 TORRENT_ASSERT(!p.filtered());
500 TORRENT_ASSERT(!p.have());
501 TORRENT_ASSERT(m_sequential_download == -1);
502
503 int priority = p.priority(this);
504 TORRENT_ASSERT(priority >= 0);
505 if (int(m_priority_boundries.size()) <= priority)
506 m_priority_boundries.resize(priority + 1, m_pieces.size());
507
508 TORRENT_ASSERT(int(m_priority_boundries.size()) >= priority);
509
510 int range_start, range_end;
511 priority_range(priority, &range_start, &range_end);
512 int new_index;
513 if (range_end == range_start) new_index = range_start;
514 else new_index = rand() % (range_end - range_start) + range_start;
515
516 #ifdef TORRENT_PICKER_LOG
517 std::cerr << "add " << index << " (" << priority << ")" << std::endl;
518 print_pieces();
519 #endif
520 m_pieces.push_back(-1);
521
522 for (;;)
523 {
524 TORRENT_ASSERT(new_index < int(m_pieces.size()));
525 int temp = m_pieces[new_index];
526 m_pieces[new_index] = index;
527 m_piece_map[index].index = new_index;
528 index = temp;
529 do
530 {
531 temp = m_priority_boundries[priority]++;
532 ++priority;
533 } while (temp == new_index && priority < int(m_priority_boundries.size()));
534 new_index = temp;
535 #ifdef TORRENT_PICKER_LOG
536 print_pieces();
537 std::cerr << " index: " << index
538 << " prio: " << priority
539 << " new_index: " << new_index
540 << std::endl;
541 #endif
542 if (priority >= int(m_priority_boundries.size())) break;
543 TORRENT_ASSERT(temp >= 0);
544 }
545 if (index != -1)
546 {
547 TORRENT_ASSERT(new_index == int(m_pieces.size() - 1));
548 m_pieces[new_index] = index;
549 m_piece_map[index].index = new_index;
550
551 #ifdef TORRENT_PICKER_LOG
552 print_pieces();
553 #endif
554 }
555 }
556
557 void piece_picker::remove(int priority, int elem_index)
558 {
559 TORRENT_ASSERT(!m_dirty);
560 TORRENT_ASSERT(priority >= 0);
561 TORRENT_ASSERT(m_sequential_download == -1);
562
563 #ifdef TORRENT_PICKER_LOG
564 std::cerr << "remove " << m_pieces[elem_index] << " (" << priority << ")" << std::endl;
565 #endif
566 int next_index = elem_index;
567 TORRENT_ASSERT(m_piece_map[m_pieces[elem_index]].priority(this) == -1);
568 for (;;)
569 {
570 #ifdef TORRENT_PICKER_LOG
571 print_pieces();
572 #endif
573 TORRENT_ASSERT(elem_index < int(m_pieces.size()));
574 int temp;
575 do
576 {
577 temp = --m_priority_boundries[priority];
578 ++priority;
579 } while (next_index == temp && priority < int(m_priority_boundries.size()));
580 if (next_index == temp) break;
581 next_index = temp;
582
583 int piece = m_pieces[next_index];
584 m_pieces[elem_index] = piece;
585 m_piece_map[piece].index = elem_index;
586 TORRENT_ASSERT(m_piece_map[piece].priority(this) == priority - 1);
587 TORRENT_ASSERT(elem_index < int(m_pieces.size() - 1));
588 elem_index = next_index;
589
590 if (priority == int(m_priority_boundries.size()))
591 break;
592 }
593 m_pieces.pop_back();
594 TORRENT_ASSERT(next_index == int(m_pieces.size()));
595 #ifdef TORRENT_PICKER_LOG
596 print_pieces();
597 #endif
598 }
599
600 // will update the piece with the given properties (priority, elem_index)
601 // to place it at the correct position
602 void piece_picker::update(int priority, int elem_index)
603 {
604 TORRENT_ASSERT(!m_dirty);
605 TORRENT_ASSERT(priority >= 0);
606 TORRENT_ASSERT(elem_index >= 0);
607 TORRENT_ASSERT(m_sequential_download == -1);
608
609 TORRENT_ASSERT(int(m_priority_boundries.size()) > priority);
610
611 int index = m_pieces[elem_index];
612 // update the piece_map
613 piece_pos& p = m_piece_map[index];
614 TORRENT_ASSERT(int(p.index) == elem_index || p.have());
615
616 int new_priority = p.priority(this);
617
618 if (new_priority == priority) return;
619
620 if (new_priority == -1)
621 {
622 remove(priority, elem_index);
623 return;
624 }
625
626 if (int(m_priority_boundries.size()) <= new_priority)
627 m_priority_boundries.resize(new_priority + 1, m_pieces.size());
628
629 #ifdef TORRENT_PICKER_LOG
630 std::cerr << "update " << index << " (" << priority << "->" << new_priority << ")" << std::endl;
631 #endif
632 if (priority > new_priority)
633 {
634 int new_index;
635 int temp = index;
636 for (;;)
637 {
638 #ifdef TORRENT_PICKER_LOG
639 print_pieces();
640 #endif
641 --priority;
642 new_index = m_priority_boundries[priority]++;
643 TORRENT_ASSERT(new_index < int(m_pieces.size()));
644 if (temp != m_pieces[new_index])
645 {
646 temp = m_pieces[new_index];
647 m_pieces[elem_index] = temp;
648 m_piece_map[temp].index = elem_index;
649 TORRENT_ASSERT(elem_index < int(m_pieces.size()));
650 }
651 elem_index = new_index;
652 if (priority == new_priority) break;
653 }
654 #ifdef TORRENT_PICKER_LOG
655 print_pieces();
656 #endif
657 m_pieces[elem_index] = index;
658 m_piece_map[index].index = elem_index;
659 TORRENT_ASSERT(elem_index < int(m_pieces.size()));
660 #ifdef TORRENT_PICKER_LOG
661 print_pieces();
662 #endif
663 shuffle(priority, elem_index);
664 #ifdef TORRENT_PICKER_LOG
665 print_pieces();
666 #endif
667 TORRENT_ASSERT(m_piece_map[index].priority(this) == priority);
668 }
669 else
670 {
671 int new_index;
672 int temp = index;
673 for (;;)
674 {
675 #ifdef TORRENT_PICKER_LOG
676 print_pieces();
677 #endif
678 new_index = --m_priority_boundries[priority];
679 TORRENT_ASSERT(new_index < int(m_pieces.size()));
680 if (temp != m_pieces[new_index])
681 {
682 temp = m_pieces[new_index];
683 m_pieces[elem_index] = temp;
684 m_piece_map[temp].index = elem_index;
685 TORRENT_ASSERT(elem_index < int(m_pieces.size()));
686 }
687 elem_index = new_index;
688 ++priority;
689 if (priority == new_priority) break;
690 }
691 #ifdef TORRENT_PICKER_LOG
692 print_pieces();
693 #endif
694 m_pieces[elem_index] = index;
695 m_piece_map[index].index = elem_index;
696 TORRENT_ASSERT(elem_index < int(m_pieces.size()));
697 #ifdef TORRENT_PICKER_LOG
698 print_pieces();
699 #endif
700 shuffle(priority, elem_index);
701 #ifdef TORRENT_PICKER_LOG
702 print_pieces();
703 #endif
704 TORRENT_ASSERT(m_piece_map[index].priority(this) == priority);
705 }
706 }
707
708 void piece_picker::shuffle(int priority, int elem_index)
709 {
710 TORRENT_ASSERT(!m_dirty);
711 TORRENT_ASSERT(priority >= 0);
712 TORRENT_ASSERT(elem_index >= 0);
713 TORRENT_ASSERT(m_sequential_download == -1);
714
715 int range_start, range_end;
716 priority_range(priority, &range_start, &range_end);
717 TORRENT_ASSERT(range_start < range_end);
718 int other_index = rand() % (range_end - range_start) + range_start;
719
720 if (other_index == elem_index) return;
721
722 // swap other_index with elem_index
723 piece_pos& p1 = m_piece_map[m_pieces[other_index]];
724 piece_pos& p2 = m_piece_map[m_pieces[elem_index]];
725
726 int temp = p1.index;
727 p1.index = p2.index;
728 p2.index = temp;
729 std::swap(m_pieces[other_index], m_pieces[elem_index]);
730 }
731
732 void piece_picker::sort_piece(std::vector<downloading_piece>::iterator dp)
733 {
734 TORRENT_ASSERT(m_piece_map[dp->index].downloading);
735 if (dp == m_downloads.begin()) return;
736 int complete = dp->writing + dp->finished;
737 for (std::vector<downloading_piece>::iterator i = dp, j(dp-1);
738 i != m_downloads.begin(); --i, --j)
739 {
740 TORRENT_ASSERT(j >= m_downloads.begin());
741 if (j->finished + j->writing >= complete) return;
742 using std::swap;
743 swap(*j, *i);
744 if (j == m_downloads.begin()) break;
745 }
746 }
747
748 void piece_picker::restore_piece(int index)
749 {
750 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
751
752 TORRENT_ASSERT(index >= 0);
753 TORRENT_ASSERT(index < (int)m_piece_map.size());
754
755 TORRENT_ASSERT(m_piece_map[index].downloading == 1);
756
757 std::vector<downloading_piece>::iterator i
758 = std::find_if(m_downloads.begin(), m_downloads.end()
759 , has_index(index));
760
761 TORRENT_ASSERT(i != m_downloads.end());
762 erase_download_piece(i);
763
764 piece_pos& p = m_piece_map[index];
765 int prev_priority = p.priority(this);
766 p.downloading = 0;
767 int new_priority = p.priority(this);
768
769 if (new_priority == prev_priority) return;
770 if (m_dirty) return;
771 if (m_sequential_download >= 0)
772 {
773 m_dirty = true;
774 return;
775 }
776 if (prev_priority == -1)
777 {
778 add(index);
779 }
780 else
781 {
782 update(prev_priority, p.index);
783 }
784 }
785
786 void piece_picker::inc_refcount_all()
787 {
788 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
789 ++m_seeds;
790 if (m_seeds == 1)
791 {
792 // when m_seeds is increased from 0 to 1
793 // we may have to add pieces that previously
794 // didn't have any peers
795 m_dirty = true;
796 }
797 }
798
799 void piece_picker::dec_refcount_all()
800 {
801 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
802
803 if (m_seeds > 0)
804 {
805 --m_seeds;
806 if (m_seeds == 0)
807 {
808 // when m_seeds is decreased from 1 to 0
809 // we may have to remove pieces that previously
810 // didn't have any peers
811 m_dirty = true;
812 }
813 return;
814 }
815 TORRENT_ASSERT(m_seeds == 0);
816
817 for (std::vector<piece_pos>::iterator i = m_piece_map.begin()
818 , end(m_piece_map.end()); i != end; ++i)
819 {
820 TORRENT_ASSERT(i->peer_count > 0);
821 --i->peer_count;
822 }
823
824 m_dirty = true;
825 }
826
827 void piece_picker::inc_refcount(int index)
828 {
829 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
830
831 piece_pos& p = m_piece_map[index];
832 if (m_sequential_download >= 0)
833 {
834 ++p.peer_count;
835 m_dirty = true;
836 return;
837 }
838
839 int prev_priority = p.priority(this);
840 ++p.peer_count;
841 if (m_dirty) return;
842 int new_priority = p.priority(this);
843 if (prev_priority == new_priority) return;
844 if (prev_priority == -1)
845 add(index);
846 else
847 update(prev_priority, p.index);
848 }
849
850 void piece_picker::dec_refcount(int index)
851 {
852 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
853
854 piece_pos& p = m_piece_map[index];
855 if (m_sequential_download >= 0)
856 {
857 TORRENT_ASSERT(p.peer_count > 0);
858 --p.peer_count;
859 m_dirty = true;
860 return;
861 }
862 int prev_priority = p.priority(this);
863 TORRENT_ASSERT(p.peer_count > 0);
864 --p.peer_count;
865 if (m_dirty) return;
866 if (prev_priority >= 0) update(prev_priority, p.index);
867 }
868
869 void piece_picker::inc_refcount(bitfield const& bitmask)
870 {
871 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
872 TORRENT_ASSERT(bitmask.size() == m_piece_map.size());
873
874 int index = 0;
875 bool updated = false;
876 for (bitfield::const_iterator i = bitmask.begin()
877 , end(bitmask.end()); i != end; ++i, ++index)
878 {
879 if (*i)
880 {
881 ++m_piece_map[index].peer_count;
882 updated = true;
883 }
884 }
885
886 if (updated && m_sequential_download == -1) m_dirty = true;
887 }
888
889 void piece_picker::dec_refcount(bitfield const& bitmask)
890 {
891 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
892 TORRENT_ASSERT(bitmask.size() == m_piece_map.size());
893
894 int index = 0;
895 bool updated = false;
896 for (bitfield::const_iterator i = bitmask.begin()
897 , end(bitmask.end()); i != end; ++i, ++index)
898 {
899 if (*i)
900 {
901 --m_piece_map[index].peer_count;
902 updated = true;
903 }
904 }
905
906 if (updated && m_sequential_download == -1) m_dirty = true;
907 }
908
909 void piece_picker::update_pieces() const
910 {
911 TORRENT_ASSERT(m_dirty);
912 TORRENT_ASSERT(m_sequential_download == -1);
913 if (m_priority_boundries.empty()) m_priority_boundries.resize(1, 0);
914 #ifdef TORRENT_PICKER_LOG
915 std::cerr << "update_pieces" << std::endl;
916 #endif
917 std::fill(m_priority_boundries.begin(), m_priority_boundries.end(), 0);
918 for (std::vector<piece_pos>::iterator i = m_piece_map.begin()
919 , end(m_piece_map.end()); i != end; ++i)
920 {
921 int prio = i->priority(this);
922 if (prio == -1) continue;
923 if (prio >= int(m_priority_boundries.size()))
924 m_priority_boundries.resize(prio + 1, 0);
925 i->index = m_priority_boundries[prio];
926 ++m_priority_boundries[prio];
927 }
928
929 #ifdef TORRENT_PICKER_LOG
930 print_pieces();
931 #endif
932
933 int index = 0;
934 for (std::vector<int>::iterator i = m_priority_boundries.begin()
935 , end(m_priority_boundries.end()); i != end; ++i)
936 {
937 *i += index;
938 index = *i;
939 }
940 m_pieces.resize(index, 0);
941
942 #ifdef TORRENT_PICKER_LOG
943 print_pieces();
944 #endif
945
946 index = 0;
947 for (std::vector<piece_pos>::iterator i = m_piece_map.begin()
948 , end(m_piece_map.end()); i != end; ++i, ++index)
949 {
950 piece_pos& p = *i;
951 int prio = p.priority(this);
952 if (prio == -1) continue;
953 int new_index = (prio == 0 ? 0 : m_priority_boundries[prio - 1]) + p.index;
954 m_pieces[new_index] = index;
955 }
956
957 int start = 0;
958 for (std::vector<int>::iterator i = m_priority_boundries.begin()
959 , end(m_priority_boundries.end()); i != end; ++i)
960 {
961 if (start == *i) continue;
962 std::random_shuffle(&m_pieces[0] + start, &m_pieces[0] + *i);
963 start = *i;
964 }
965
966 index = 0;
967 for (std::vector<int>::const_iterator i = m_pieces.begin()
968 , end(m_pieces.end()); i != end; ++i, ++index)
969 {
970 TORRENT_ASSERT(*i >= 0 && *i < int(m_piece_map.size()));
971 m_piece_map[*i].index = index;
972 }
973
974 m_dirty = false;
975 #ifdef TORRENT_PICKER_LOG
976 print_pieces();
977 #endif
978
979 #ifndef NDEBUG
980 check_invariant();
981 #endif
982 }
983
984 void piece_picker::we_dont_have(int index)
985 {
986 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
987 TORRENT_ASSERT(index >= 0);
988 TORRENT_ASSERT(index < (int)m_piece_map.size());
989
990 piece_pos& p = m_piece_map[index];
991 TORRENT_ASSERT(p.downloading == 0);
992
993 if (!p.have()) return;
994
995 if (m_sequential_download > index)
996 m_sequential_download = index;
997
998 if (p.filtered())
999 {
1000 ++m_num_filtered;
1001 --m_num_have_filtered;
1002 }
1003
1004 --m_num_have;
1005 p.set_not_have();
1006
1007 if (m_dirty) return;
1008 if (p.priority(this) >= 0) add(index);
1009 }
1010
1011 // this is used to indicate that we succesfully have
1012 // downloaded a piece, and that no further attempts
1013 // to pick that piece should be made. The piece will
1014 // be removed from the available piece list.
1015 void piece_picker::we_have(int index)
1016 {
1017 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
1018 TORRENT_ASSERT(index >= 0);
1019 TORRENT_ASSERT(index < (int)m_piece_map.size());
1020
1021 piece_pos& p = m_piece_map[index];
1022 int info_index = p.index;
1023 int priority = p.priority(this);
1024 TORRENT_ASSERT(priority < int(m_priority_boundries.size()));
1025
1026 if (p.downloading)
1027 {
1028 std::vector<downloading_piece>::iterator i
1029 = std::find_if(m_downloads.begin()
1030 , m_downloads.end()
1031 , has_index(index));
1032 TORRENT_ASSERT(i != m_downloads.end());
1033 erase_download_piece(i);
1034 p.downloading = 0;
1035 }
1036
1037 TORRENT_ASSERT(std::find_if(m_downloads.begin(), m_downloads.end()
1038 , has_index(index)) == m_downloads.end());
1039
1040 if (m_sequential_download == index)
1041 {
1042 ++m_sequential_download;
1043 for (std::vector<piece_pos>::const_iterator i = m_piece_map.begin() + m_sequential_download
1044 , end(m_piece_map.end()); i != end && (i->have() || i->filtered());
1045 ++i, ++m_sequential_download);
1046 }
1047 if (p.have()) return;
1048 if (p.filtered())
1049 {
1050 --m_num_filtered;
1051 ++m_num_have_filtered;
1052 }
1053 ++m_num_have;
1054 p.set_have();
1055 if (priority == -1) return;
1056 if (m_dirty) return;
1057 remove(priority, info_index);
1058 TORRENT_ASSERT(p.priority(this) == -1);
1059 }
1060
1061 bool piece_picker::set_piece_priority(int index, int new_piece_priority)
1062 {
1063 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
1064 TORRENT_ASSERT(new_piece_priority >= 0);
1065 TORRENT_ASSERT(new_piece_priority <= 7);
1066 TORRENT_ASSERT(index >= 0);
1067 TORRENT_ASSERT(index < (int)m_piece_map.size());
1068
1069 piece_pos& p = m_piece_map[index];
1070
1071 // if the priority isn't changed, don't do anything
1072 if (new_piece_priority == int(p.piece_priority)) return false;
1073
1074 int prev_priority = p.priority(this);
1075 TORRENT_ASSERT(prev_priority < int(m_priority_boundries.size()));
1076
1077 bool ret = false;
1078 if (new_piece_priority == piece_pos::filter_priority
1079 && p.piece_priority != piece_pos::filter_priority)
1080 {
1081 // the piece just got filtered
1082 if (p.have()) ++m_num_have_filtered;
1083 else ++m_num_filtered;
1084 ret = true;
1085 }
1086 else if (new_piece_priority != piece_pos::filter_priority
1087 && p.piece_priority == piece_pos::filter_priority)
1088 {
1089 // the piece just got unfiltered
1090 if (p.have()) --m_num_have_filtered;
1091 else --m_num_filtered;
1092 ret = true;
1093 }
1094 TORRENT_ASSERT(m_num_filtered >= 0);
1095 TORRENT_ASSERT(m_num_have_filtered >= 0);
1096
1097 p.piece_priority = new_piece_priority;
1098 int new_priority = p.priority(this);
1099
1100 if (prev_priority == new_priority) return false;
1101
1102 TORRENT_ASSERT(prev_priority < int(m_priority_boundries.size()));
1103
1104 if (m_dirty) return ret;
1105 if (prev_priority == -1)
1106 {
1107 add(index);
1108 }
1109 else
1110 {
1111 update(prev_priority, p.index);
1112 }
1113 return ret;
1114 }
1115
1116 int piece_picker::piece_priority(int index) const
1117 {
1118 TORRENT_ASSERT(index >= 0);
1119 TORRENT_ASSERT(index < (int)m_piece_map.size());
1120
1121 return m_piece_map[index].piece_priority;
1122 }
1123
1124 void piece_picker::piece_priorities(std::vector<int>& pieces) const
1125 {
1126 pieces.resize(m_piece_map.size());
1127 std::vector<int>::iterator j = pieces.begin();
1128 for (std::vector<piece_pos>::const_iterator i = m_piece_map.begin(),
1129 end(m_piece_map.end()); i != end; ++i, ++j)
1130 {
1131 *j = i->piece_priority;
1132 }
1133 }
1134
1135 // ============ start deprecation ==============
1136
1137 void piece_picker::filtered_pieces(std::vector<bool>& mask) const
1138 {
1139 mask.resize(m_piece_map.size());
1140 std::vector<bool>::iterator j = mask.begin();
1141 for (std::vector<piece_pos>::const_iterator i = m_piece_map.begin(),
1142 end(m_piece_map.end()); i != end; ++i, ++j)
1143 {
1144 *j = i->filtered();
1145 }
1146 }
1147
1148 // ============ end deprecation ==============
1149
1150 // pieces describes which pieces the peer we're requesting from
1151 // has.
1152 // interesting_blocks is an out parameter, and will be filled
1153 // with (up to) num_blocks of interesting blocks that the peer has.
1154 // prefer_whole_pieces can be set if this peer should download
1155 // whole pieces rather than trying to download blocks from the
1156 // same piece as other peers.
1157 // the void* is the pointer to the policy::peer of the peer we're
1158 // picking pieces from. This is used when downloading whole pieces,
1159 // to only pick from the same piece the same peer is downloading
1160 // from. state is supposed to be set to fast if the peer is downloading
1161 // relatively fast, by some notion. Slow peers will prefer not
1162 // to pick blocks from the same pieces as fast peers, and vice
1163 // versa. Downloading pieces are marked as being fast, medium
1164 // or slow once they're started.
1165 void piece_picker::pick_pieces(bitfield const& pieces
1166 , std::vector<piece_block>& interesting_blocks
1167 , int num_blocks, int prefer_whole_pieces
1168 , void* peer, piece_state_t speed, bool rarest_first
1169 , bool on_parole, std::vector<int> const& suggested_pieces) const
1170 {
1171 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
1172 TORRENT_ASSERT(num_blocks > 0);
1173 TORRENT_ASSERT(pieces.size() == m_piece_map.size());
1174
1175 TORRENT_ASSERT(!m_priority_boundries.empty()
1176 || m_sequential_download >= 0
1177 || m_dirty);
1178
1179 // this will be filled with blocks that we should not request
1180 // unless we can't find num_blocks among the other ones.
1181 // blocks that belong to pieces with a mismatching speed
1182 // category for instance, or if we prefer whole pieces,
1183 // blocks belonging to a piece that others have
1184 // downloaded to
1185 std::vector<piece_block> backup_blocks;
1186 const std::vector<int> empty_vector;
1187
1188 // When prefer_whole_pieces is set (usually set when downloading from
1189 // fast peers) the partial pieces will not be prioritized, but actually
1190 // ignored as long as possible. All blocks found in downloading
1191 // pieces are regarded as backup blocks
1192
1193 num_blocks = add_blocks_downloading(pieces
1194 , interesting_blocks, backup_blocks, num_blocks
1195 , prefer_whole_pieces, peer, speed, on_parole);
1196
1197 if (num_blocks <= 0) return;
1198
1199 if (!suggested_pieces.empty())
1200 {
1201 num_blocks = add_blocks(suggested_pieces, pieces
1202 , interesting_blocks, num_blocks
1203 , prefer_whole_pieces, peer, empty_vector);
1204 if (num_blocks == 0) return;
1205 }
1206
1207 if (m_sequential_download >= 0)
1208 {
1209 for (int i = m_sequential_download;
1210 i < int(m_piece_map.size()) && num_blocks > 0; ++i)
1211 {
1212 if (!can_pick(i, pieces)) continue;
1213 int num_blocks_in_piece = blocks_in_piece(i);
1214 if (prefer_whole_pieces == 0 && num_blocks_in_piece > num_blocks)
1215 num_blocks_in_piece = num_blocks;
1216 for (int j = 0; j < num_blocks_in_piece; ++j)
1217 {
1218 interesting_blocks.push_back(piece_block(i, j));
1219 --num_blocks;
1220 }
1221 }
1222 }
1223 else if (rarest_first)
1224 {
1225 if (m_dirty) update_pieces();
1226 num_blocks = add_blocks(m_pieces, pieces
1227 , interesting_blocks, num_blocks
1228 , prefer_whole_pieces, peer, suggested_pieces);
1229 TORRENT_ASSERT(num_blocks >= 0);
1230 }
1231 else
1232 {
1233 // we're not using rarest first (only for the first
1234 // bucket, since that's where the currently downloading
1235 // pieces are)
1236 int start_piece = rand() % m_piece_map.size();
1237
1238 // if we have suggested pieces, try to find one of those instead
1239 for (std::vector<int>::const_iterator i = suggested_pieces.begin()
1240 , end(suggested_pieces.end()); i != end; ++i)
1241 {
1242 if (!can_pick(*i, pieces)) continue;
1243 start_piece = *i;
1244 break;
1245 }
1246 int piece = start_piece;
1247 while (num_blocks > 0)
1248 {
1249 while (!can_pick(piece, pieces))
1250 {
1251 ++piece;
1252 if (piece == int(m_piece_map.size())) piece = 0;
1253 // could not find any more pieces
1254 if (piece == start_piece) return;
1255 }
1256
1257 int start, end;
1258 boost::tie(start, end) = expand_piece(piece, prefer_whole_pieces, pieces);
1259 for (int k = start; k < end; ++k)
1260 {
1261 TORRENT_ASSERT(m_piece_map[piece].downloading == false);
1262 TORRENT_ASSERT(m_piece_map[k].priority(this) >= 0);
1263 int num_blocks_in_piece = blocks_in_piece(k);
1264 if (prefer_whole_pieces == 0 && num_blocks_in_piece > num_blocks)
1265 num_blocks_in_piece = num_blocks;
1266 for (int j = 0; j < num_blocks_in_piece; ++j)
1267 {
1268 interesting_blocks.push_back(piece_block(k, j));
1269 --num_blocks;
1270 }
1271 }
1272 piece = end;
1273 if (piece == int(m_piece_map.size())) piece = 0;
1274 // could not find any more pieces
1275 if (piece == start_piece) return;
1276 }
1277
1278 }
1279
1280 if (num_blocks <= 0) return;
1281
1282 if (!backup_blocks.empty())
1283 interesting_blocks.insert(interesting_blocks.end()
1284 , backup_blocks.begin(), backup_blocks.end());
1285 }
1286
1287 bool piece_picker::can_pick(int piece, bitfield const& bitmask) const
1288 {
1289 TORRENT_ASSERT(piece >= 0 && piece < int(m_piece_map.size()));
1290 return bitmask[piece]
1291 && !m_piece_map[piece].have()
1292 && !m_piece_map[piece].downloading
1293 && !m_piece_map[piece].filtered();
1294 }
1295
1296 void piece_picker::clear_peer(void* peer)
1297 {
1298 for (std::vector<block_info>::iterator i = m_block_info.begin()
1299 , end(m_block_info.end()); i != end; ++i)
1300 if (i->peer == peer) i->peer = 0;
1301 }
1302
1303 namespace
1304 {
1305 // the first bool is true if this is the only peer that has requested and downloaded
1306 // blocks from this piece.
1307 // the second bool is true if this is the only active peer that is requesting
1308 // and downloading blocks from this piece. Active means having a connection.
1309 boost::tuple<bool, bool> requested_from(piece_picker::downloading_piece const& p
1310 , int num_blocks_in_piece, void* peer)
1311 {
1312 bool exclusive = true;
1313 bool exclusive_active = true;
1314 for (int j = 0; j < num_blocks_in_piece; ++j)
1315 {
1316 piece_picker::block_info const& info = p.info[j];
1317 if (info.state != piece_picker::block_info::state_none
1318 && info.peer != peer)
1319 {
1320 exclusive = false;
1321 if (info.state == piece_picker::block_info::state_requested
1322 && info.peer != 0)
1323 {
1324 exclusive_active = false;
1325 return boost::make_tuple(exclusive, exclusive_active);
1326 }
1327 }
1328 }
1329 return boost::make_tuple(exclusive, exclusive_active);
1330 }
1331 }
1332
1333 int piece_picker::add_blocks(std::vector<int> const& piece_list
1334 , bitfield const& pieces
1335 , std::vector<piece_block>& interesting_blocks
1336 , int num_blocks, int prefer_whole_pieces
1337 , void* peer, std::vector<int> const& ignore) const
1338 {
1339 for (std::vector<int>::const_iterator i = piece_list.begin();
1340 i != piece_list.end(); ++i)
1341 {
1342 TORRENT_ASSERT(*i >= 0);
1343 TORRENT_ASSERT(*i < (int)m_piece_map.size());
1344
1345 // if the peer doesn't have the piece
1346 // or if it's set to 0 priority
1347 // skip it
1348 if (!can_pick(*i, pieces)) continue;
1349
1350 // ignore pieces found in the ignore list
1351 if (std::find(ignore.begin(), ignore.end(), *i) != ignore.end()) continue;
1352
1353 TORRENT_ASSERT(m_piece_map[*i].priority(this) >= 0);
1354 TORRENT_ASSERT(m_piece_map[*i].downloading == 0);
1355
1356 int num_blocks_in_piece = blocks_in_piece(*i);
1357
1358 // pick a new piece
1359 if (prefer_whole_pieces == 0)
1360 {
1361 if (num_blocks_in_piece > num_blocks)
1362 num_blocks_in_piece = num_blocks;
1363 for (int j = 0; j < num_blocks_in_piece; ++j)
1364 interesting_blocks.push_back(piece_block(*i, j));
1365 num_blocks -= num_blocks_in_piece;
1366 }
1367 else
1368 {
1369 int start, end;
1370 boost::tie(start, end) = expand_piece(*i, prefer_whole_pieces, pieces);
1371 for (int k = start; k < end; ++k)
1372 {
1373 TORRENT_ASSERT(m_piece_map[k].priority(this) > 0);
1374 num_blocks_in_piece = blocks_in_piece(k);
1375 for (int j = 0; j < num_blocks_in_piece; ++j)
1376 {
1377 interesting_blocks.push_back(piece_block(k, j));
1378 --num_blocks;
1379 }
1380 }
1381 }
1382 if (num_blocks <= 0)
1383 {
1384 #ifndef NDEBUG
1385 verify_pick(interesting_blocks, pieces);
1386 #endif
1387 return 0;
1388 }
1389 }
1390 #ifndef NDEBUG
1391 verify_pick(interesting_blocks, pieces);
1392 #endif
1393 return num_blocks;
1394 }
1395
1396 int piece_picker::add_blocks_downloading(bitfield const& pieces
1397 , std::vector<piece_block>& interesting_blocks
1398 , std::vector<piece_block>& backup_blocks
1399 , int num_blocks, int prefer_whole_pieces
1400 , void* peer, piece_state_t speed, bool on_parole) const
1401 {
1402 for (std::vector<downloading_piece>::const_iterator i = m_downloads.begin()
1403 , end(m_downloads.end()); i != end; ++i)
1404 {
1405 if (!pieces[i->index]) continue;
1406
1407 int num_blocks_in_piece = blocks_in_piece(i->index);
1408
1409 // is true if all the other pieces that are currently
1410 // requested from this piece are from the same
1411 // peer as 'peer'.
1412 bool exclusive;
1413 bool exclusive_active;
1414 boost::tie(exclusive, exclusive_active)
1415 = requested_from(*i, num_blocks_in_piece, peer);
1416
1417 // peers on parole are only allowed to pick blocks from
1418 // pieces that only they have downloaded/requested from
1419 if (on_parole && !exclusive) continue;
1420
1421 if (prefer_whole_pieces > 0 && !exclusive_active) continue;
1422
1423 // don't pick too many back-up blocks
1424 if (i->state != none
1425 && i->state != speed
1426 && !exclusive_active
1427 && int(backup_blocks.size()) >= num_blocks)
1428 continue;
1429
1430 for (int j = 0; j < num_blocks_in_piece; ++j)
1431 {
1432 // ignore completed blocks and already requested blocks
1433 block_info const& info = i->info[j];
1434 if (info.state != block_info::state_none)
1435 continue;
1436
1437 TORRENT_ASSERT(i->info[j].state == block_info::state_none);
1438
1439 // if the piece is fast and the peer is slow, or vice versa,
1440 // add the block as a backup.
1441 // override this behavior if all the other blocks
1442 // have been requested from the same peer or
1443 // if the state of the piece is none (the
1444 // piece will in that case change state).
1445 if (i->state != none && i->state != speed
1446 && !exclusive_active)
1447 {
1448 backup_blocks.push_back(piece_block(i->index, j));
1449 continue;
1450 }
1451
1452 // this block is interesting (we don't have it
1453 // yet).
1454 interesting_blocks.push_back(piece_block(i->index, j));
1455 // we have found a block that's free to download
1456 num_blocks--;
1457 // if we prefer whole pieces, continue picking from this
1458 // piece even though we have num_blocks
1459 if (prefer_whole_pieces > 0) continue;
1460 TORRENT_ASSERT(num_blocks >= 0);
1461 if (num_blocks <= 0) break;
1462 }
1463 if (num_blocks <= 0) break;
1464 }
1465
1466 TORRENT_ASSERT(num_blocks >= 0 || prefer_whole_pieces > 0);
1467
1468 #ifndef NDEBUG
1469 verify_pick(interesting_blocks, pieces);
1470 verify_pick(backup_blocks, pieces);
1471 #endif
1472
1473 if (num_blocks <= 0) return 0;
1474 if (on_parole) return num_blocks;
1475
1476 int to_copy;
1477 if (prefer_whole_pieces == 0)
1478 to_copy = (std::min)(int(backup_blocks.size()), num_blocks);
1479 else
1480 to_copy = int(backup_blocks.size());
1481
1482 interesting_blocks.insert(interesting_blocks.end()
1483 , backup_blocks.begin(), backup_blocks.begin() + to_copy);
1484 num_blocks -= to_copy;
1485 backup_blocks.clear();
1486
1487 if (num_blocks <= 0) return 0;
1488
1489 if (prefer_whole_pieces > 0)
1490 {
1491 for (std::vector<downloading_piece>::const_iterator i = m_downloads.begin()
1492 , end(m_downloads.end()); i != end; ++i)
1493 {
1494 if (!pieces[i->index]) continue;
1495 int num_blocks_in_piece = blocks_in_piece(i->index);
1496 bool exclusive;
1497 bool exclusive_active;
1498 boost::tie(exclusive, exclusive_active)
1499 = requested_from(*i, num_blocks_in_piece, peer);
1500
1501 if (exclusive_active) continue;
1502
1503 for (int j = 0; j < num_blocks_in_piece; ++j)
1504 {
1505 block_info const& info = i->info[j];
1506 if (info.state != block_info::state_none) continue;
1507 backup_blocks.push_back(piece_block(i->index, j));
1508 }
1509 }
1510 }
1511
1512 if (int(backup_blocks.size()) >= num_blocks) return num_blocks;
1513
1514
1515 #ifndef NDEBUG
1516 // make sure that we at this point has added requests to all unrequested blocks
1517 // in all downloading pieces
1518
1519 for (std::vector<downloading_piece>::const_iterator i = m_downloads.begin()
1520 , end(m_downloads.end()); i != end; ++i)
1521 {
1522 if (!pieces[i->index]) continue;
1523
1524 int num_blocks_in_piece = blocks_in_piece(i->index);
1525 for (int j = 0; j < num_blocks_in_piece; ++j)
1526 {
1527 block_info const& info = i->info[j];
1528 if (info.state != block_info::state_none) continue;
1529 std::vector<piece_block>::iterator k = std::find(
1530 interesting_blocks.begin(), interesting_blocks.end()
1531 , piece_block(i->index, j));
1532 if (k != interesting_blocks.end()) continue;
1533
1534 k = std::find(backup_blocks.begin()
1535 , backup_blocks.end(), piece_block(i->index, j));
1536 if (k != backup_blocks.end()) continue;
1537
1538 std::cerr << "interesting blocks:" << std::endl;
1539 for (k = interesting_blocks.begin(); k != interesting_blocks.end(); ++k)
1540 std::cerr << "(" << k->piece_index << ", " << k->block_index << ") ";
1541 std::cerr << std::endl;
1542 std::cerr << "backup blocks:" << std::endl;
1543 for (k = backup_blocks.begin(); k != backup_blocks.end(); ++k)
1544 std::cerr << "(" << k->piece_index << ", " << k->block_index << ") ";
1545 std::cerr << std::endl;
1546 std::cerr << "num_blocks: " << num_blocks << std::endl;
1547
1548 for (std::vector<downloading_piece>::const_iterator l = m_downloads.begin()
1549 , end(m_downloads.end()); l != end; ++l)
1550 {
1551 std::cerr << l->index << " : ";
1552 int num_blocks_in_piece = blocks_in_piece(l->index);
1553 for (int m = 0; m < num_blocks_in_piece; ++m)
1554 std::cerr << l->info[m].state;
1555 std::cerr << std::endl;
1556 }
1557
1558 TORRENT_ASSERT(false);
1559 }
1560 }
1561 #endif
1562
1563 for (std::vector<downloading_piece>::const_iterator i = m_downloads.begin()
1564 , end(m_downloads.end()); i != end; ++i)
1565 {
1566 if (!pieces[i->index]) continue;
1567
1568 int num_blocks_in_piece = blocks_in_piece(i->index);
1569
1570 // fill in with blocks requested from other peers
1571 // as backups
1572 for (int j = 0; j < num_blocks_in_piece; ++j)
1573 {
1574 block_info const& info = i->info[j];
1575 if (info.state != block_info::state_requested
1576 || info.peer == peer)
1577 continue;
1578 backup_blocks.push_back(piece_block(i->index, j));
1579 }
1580 }
1581 #ifndef NDEBUG
1582 verify_pick(backup_blocks, pieces);
1583 #endif
1584 return num_blocks;
1585 }
1586
1587 std::pair<int, int> piece_picker::expand_piece(int piece, int whole_pieces
1588 , bitfield const& have) const
1589 {
1590 if (whole_pieces == 0) return std::make_pair(piece, piece + 1);
1591
1592 int start = piece - 1;
1593 int lower_limit = piece - whole_pieces;
1594 if (lower_limit < -1) lower_limit = -1;
1595 while (start > lower_limit
1596 && can_pick(start, have))
1597 --start;
1598 ++start;
1599 TORRENT_ASSERT(start >= 0);
1600 int end = piece + 1;
1601 int upper_limit = start + whole_pieces;
1602 if (upper_limit > int(m_piece_map.size())) upper_limit = int(m_piece_map.size());
1603 while (end < upper_limit
1604 && can_pick(end, have))
1605 ++end;
1606 return std::make_pair(start, end);
1607 }
1608
1609 bool piece_picker::is_piece_finished(int index) const
1610 {
1611 TORRENT_ASSERT(index < (int)m_piece_map.size());
1612 TORRENT_ASSERT(index >= 0);
1613
1614 if (m_piece_map[index].downloading == 0)
1615 {
1616 TORRENT_ASSERT(std::find_if(m_downloads.begin(), m_downloads.end()
1617 , has_index(index)) == m_downloads.end());
1618 return false;
1619 }
1620 std::vector<downloading_piece>::const_iterator i
1621 = std::find_if(m_downloads.begin(), m_downloads.end(), has_index(index));
1622 TORRENT_ASSERT(i != m_downloads.end());
1623 TORRENT_ASSERT((int)i->finished <= m_blocks_per_piece);
1624 int max_blocks = blocks_in_piece(index);
1625 if ((int)i->finished < max_blocks) return false;
1626
1627 #ifndef NDEBUG
1628 for (int k = 0; k < max_blocks; ++k)
1629 {
1630 TORRENT_ASSERT(i->info[k].state == block_info::state_finished);
1631 }
1632 #endif
1633
1634 TORRENT_ASSERT((int)i->finished == max_blocks);
1635 return true;
1636 }
1637
1638 bool piece_picker::is_requested(piece_block block) const
1639 {
1640 TORRENT_ASSERT(block.piece_index >= 0);
1641 TORRENT_ASSERT(block.block_index >= 0);
1642 TORRENT_ASSERT(block.piece_index < (int)m_piece_map.size());
1643
1644 if (m_piece_map[block.piece_index].downloading == 0) return false;
1645 std::vector<downloading_piece>::const_iterator i
1646 = std::find_if(
1647 m_downloads.begin()
1648 , m_downloads.end()
1649 , has_index(block.piece_index));
1650
1651 TORRENT_ASSERT(i != m_downloads.end());
1652 return i->info[block.block_index].state == block_info::state_requested;
1653 }
1654
1655 bool piece_picker::is_downloaded(piece_block block) const
1656 {
1657 TORRENT_ASSERT(block.piece_index >= 0);
1658 TORRENT_ASSERT(block.block_index >= 0);
1659 TORRENT_ASSERT(block.piece_index < (int)m_piece_map.size());
1660
1661 if (m_piece_map[block.piece_index].index == piece_pos::we_have_index) return true;
1662 if (m_piece_map[block.piece_index].downloading == 0) return false;
1663 std::vector<downloading_piece>::const_iterator i
1664 = std::find_if(m_downloads.begin(), m_downloads.end(), has_index(block.piece_index));
1665 TORRENT_ASSERT(i != m_downloads.end());
1666 return i->info[block.block_index].state == block_info::state_finished
1667 || i->info[block.block_index].state == block_info::state_writing;
1668 }
1669
1670 bool piece_picker::is_finished(piece_block block) const
1671 {
1672 TORRENT_ASSERT(block.piece_index >= 0);
1673 TORRENT_ASSERT(block.block_index >= 0);
1674 TORRENT_ASSERT(block.piece_index < (int)m_piece_map.size());
1675
1676 if (m_piece_map[block.piece_index].index == piece_pos::we_have_index) return true;
1677 if (m_piece_map[block.piece_index].downloading == 0) return false;
1678 std::vector<downloading_piece>::const_iterator i
1679 = std::find_if(m_downloads.begin(), m_downloads.end(), has_index(block.piece_index));
1680 TORRENT_ASSERT(i != m_downloads.end());
1681 return i->info[block.block_index].state == block_info::state_finished;
1682 }
1683
1684 bool piece_picker::mark_as_downloading(piece_block block
1685 , void* peer, piece_state_t state)
1686 {
1687 TORRENT_ASSERT(block.piece_index >= 0);
1688 TORRENT_ASSERT(block.block_index >= 0);
1689 TORRENT_ASSERT(block.piece_index < (int)m_piece_map.size());
1690 TORRENT_ASSERT(block.block_index < blocks_in_piece(block.piece_index));
1691 TORRENT_ASSERT(!m_piece_map[block.piece_index].have());
1692
1693 piece_pos& p = m_piece_map[block.piece_index];
1694 if (p.downloading == 0)
1695 {
1696 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
1697 int prio = p.priority(this);
1698 TORRENT_ASSERT(prio < int(m_priority_boundries.size())
1699 || m_sequential_download >= 0
1700 || m_dirty);
1701 TORRENT_ASSERT(prio > 0);
1702 p.downloading = 1;
1703 if (prio >= 0 && m_sequential_download == -1 && !m_dirty) update(prio, p.index);
1704
1705 downloading_piece& dp = add_download_piece();
1706 dp.state = state;
1707 dp.index = block.piece_index;
1708 block_info& info = dp.info[block.block_index];
1709 info.state = block_info::state_requested;
1710 info.peer = peer;
1711 info.num_peers = 1;
1712 ++dp.requested;
1713 }
1714 else
1715 {
1716 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
1717 std::vector<downloading_piece>::iterator i
1718 = std::find_if(m_downloads.begin(), m_downloads.end(), has_index(block.piece_index));
1719 TORRENT_ASSERT(i != m_downloads.end());
1720 block_info& info = i->info[block.block_index];
1721 if (info.state == block_info::state_writing
1722 || info.state == block_info::state_finished)
1723 return false;
1724 TORRENT_ASSERT(info.state == block_info::state_none
1725 || (info.state == block_info::state_requested
1726 && (info.num_peers > 0)));
1727 info.peer = peer;
1728 if (info.state != block_info::state_requested)
1729 {
1730 info.state = block_info::state_requested;
1731 ++i->requested;
1732 }
1733 ++info.num_peers;
1734 if (i->state == none) i->state = state;
1735 }
1736 return true;
1737 }
1738
1739 int piece_picker::num_peers(piece_block block) const
1740 {
1741 TORRENT_ASSERT(block.piece_index >= 0);
1742 TORRENT_ASSERT(block.block_index >= 0);
1743 TORRENT_ASSERT(block.piece_index < (int)m_piece_map.size());
1744 TORRENT_ASSERT(block.block_index < blocks_in_piece(block.piece_index));
1745
1746 piece_pos const& p = m_piece_map[block.piece_index];
1747 if (!p.downloading) return 0;
1748
1749 std::vector<downloading_piece>::const_iterator i
1750 = std::find_if(m_downloads.begin(), m_downloads.end(), has_index(block.piece_index));
1751 TORRENT_ASSERT(i != m_downloads.end());
1752
1753 block_info const& info = i->info[block.block_index];
1754 return info.num_peers;
1755 }
1756
1757 void piece_picker::get_availability(std::vector<int>& avail) const
1758 {
1759 TORRENT_ASSERT(m_seeds >= 0);
1760 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
1761
1762 avail.resize(m_piece_map.size());
1763 std::vector<int>::iterator j = avail.begin();
1764 for (std::vector<piece_pos>::const_iterator i = m_piece_map.begin()
1765 , end(m_piece_map.end()); i != end; ++i, ++j)
1766 *j = i->peer_count + m_seeds;
1767 }
1768
1769 void piece_picker::mark_as_writing(piece_block block, void* peer)
1770 {
1771 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
1772
1773 TORRENT_ASSERT(block.piece_index >= 0);
1774 TORRENT_ASSERT(block.block_index >= 0);
1775 TORRENT_ASSERT(block.piece_index < (int)m_piece_map.size());
1776 TORRENT_ASSERT(block.block_index < blocks_in_piece(block.piece_index));
1777
1778 TORRENT_ASSERT(m_piece_map[block.piece_index].downloading);
1779
1780 std::vector<downloading_piece>::iterator i
1781 = std::find_if(m_downloads.begin(), m_downloads.end(), has_index(block.piece_index));
1782 TORRENT_ASSERT(i != m_downloads.end());
1783 block_info& info = i->info[block.block_index];
1784
1785 info.peer = peer;
1786 TORRENT_ASSERT(info.state == block_info::state_requested);
1787 if (info.state == block_info::state_requested) --i->requested;
1788 TORRENT_ASSERT(i->requested >= 0);
1789 TORRENT_ASSERT(info.state != block_info::state_writing);
1790 ++i->writing;
1791 info.state = block_info::state_writing;
1792 TORRENT_ASSERT(info.num_peers > 0);
1793 info.num_peers = 0;
1794
1795 if (i->requested == 0)
1796 {
1797 // there are no blocks requested in this piece.
1798 // remove the fast/slow state from it
1799 i->state = none;
1800 }
1801 sort_piece(i);
1802 }
1803
1804 void piece_picker::write_failed(piece_block block)
1805 {
1806 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
1807
1808 std::vector<downloading_piece>::iterator i
1809 = std::find_if(m_downloads.begin(), m_downloads.end(), has_index(block.piece_index));
1810 TORRENT_ASSERT(i != m_downloads.end());
1811 block_info& info = i->info[block.block_index];
1812 TORRENT_ASSERT(info.state == block_info::state_writing);
1813
1814 --i->writing;
1815 if (info.num_peers > 0)
1816 {
1817 // there are other peers on this block
1818 // turn it back into requested
1819 ++i->requested;
1820 info.state = block_info::state_requested;
1821 }
1822 else
1823 {
1824 info.state = block_info::state_none;
1825 }
1826 info.peer = 0;
1827 }
1828
1829 void piece_picker::mark_as_finished(piece_block block, void* peer)
1830 {
1831 TORRENT_ASSERT(block.piece_index >= 0);
1832 TORRENT_ASSERT(block.block_index >= 0);
1833 TORRENT_ASSERT(block.piece_index < (int)m_piece_map.size());
1834 TORRENT_ASSERT(block.block_index < blocks_in_piece(block.piece_index));
1835
1836 piece_pos& p = m_piece_map[block.piece_index];
1837
1838 if (p.downloading == 0)
1839 {
1840 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
1841
1842 TORRENT_ASSERT(peer == 0);
1843 int prio = p.priority(this);
1844 TORRENT_ASSERT(prio < int(m_priority_boundries.size())
1845 || m_dirty);
1846 p.downloading = 1;
1847 if (prio >= 0 && !m_dirty) update(prio, p.index);
1848
1849 downloading_piece& dp = add_download_piece();
1850 dp.state = none;
1851 dp.index = block.piece_index;
1852 block_info& info = dp.info[block.block_index];
1853 info.peer = peer;
1854 TORRENT_ASSERT(info.state == block_info::state_none);
1855 TORRENT_ASSERT(info.num_peers == 0);
1856 if (info.state != block_info::state_finished)
1857 {
1858 ++dp.finished;
1859 sort_piece(m_downloads.end() - 1);
1860 }
1861 info.state = block_info::state_finished;
1862 }
1863 else
1864 {
1865 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
1866
1867 std::vector<downloading_piece>::iterator i
1868 = std::find_if(m_downloads.begin(), m_downloads.end(), has_index(block.piece_index));
1869 TORRENT_ASSERT(i != m_downloads.end());
1870 block_info& info = i->info[block.block_index];
1871 TORRENT_ASSERT(info.num_peers == 0);
1872 info.peer = peer;
1873 TORRENT_ASSERT(info.state == block_info::state_writing
1874 || peer == 0);
1875 TORRENT_ASSERT(i->writing >= 0);
1876 ++i->finished;
1877 if (info.state == block_info::state_writing)
1878 {
1879 --i->writing;
1880 info.state = block_info::state_finished;
1881 }
1882 else
1883 {
1884 info.state = block_info::state_finished;
1885 sort_piece(i);
1886 }
1887 }
1888 }
1889
1890 void piece_picker::get_downloaders(std::vector<void*>& d, int index) const
1891 {
1892 TORRENT_ASSERT(index >= 0 && index <= (int)m_piece_map.size());
1893 std::vector<downloading_piece>::const_iterator i
1894 = std::find_if(m_downloads.begin(), m_downloads.end(), has_index(index));
1895 TORRENT_ASSERT(i != m_downloads.end());
1896
1897 d.clear();
1898 for (int j = 0; j < blocks_in_piece(index); ++j)
1899 {
1900 d.push_back(i->info[j].peer);
1901 }
1902 }
1903
1904 void* piece_picker::get_downloader(piece_block block) const
1905 {
1906 std::vector<downloading_piece>::const_iterator i = std::find_if(
1907 m_downloads.begin()
1908 , m_downloads.end()
1909 , has_index(block.piece_index));
1910
1911 if (i == m_downloads.end()) return 0;
1912
1913 TORRENT_ASSERT(block.block_index >= 0);
1914
1915 if (i->info[block.block_index].state == block_info::state_none)
1916 return 0;
1917
1918 return i->info[block.block_index].peer;
1919 }
1920
1921 // this is called when a request is rejected or when
1922 // a peer disconnects. The piece might be in any state
1923 void piece_picker::abort_download(piece_block block)
1924 {
1925 TORRENT_PIECE_PICKER_INVARIANT_CHECK;
1926
1927 TORRENT_ASSERT(block.piece_index >= 0);
1928 TORRENT_ASSERT(block.block_index >= 0);
1929 TORRENT_ASSERT(block.piece_index < (int)m_piece_map.size());
1930 TORRENT_ASSERT(block.block_index < blocks_in_piece(block.piece_index));
1931
1932 if (m_piece_map[block.piece_index].downloading == 0)
1933 {
1934 TORRENT_ASSERT(std::find_if(m_downloads.begin(), m_downloads.end()
1935 , has_index(block.piece_index)) == m_downloads.end());
1936 return;
1937 }
1938
1939 std::vector<downloading_piece>::iterator i = std::find_if(m_downloads.begin()
1940 , m_downloads.end(), has_index(block.piece_index));
1941 TORRENT_ASSERT(i != m_downloads.end());
1942
1943 block_info& info = i->info[block.block_index];
1944
1945 if (i->info[block.block_index].state != block_info::state_requested)
1946 return;
1947
1948 if (info.num_peers > 0) --info.num_peers;
1949
1950 TORRENT_ASSERT(block.block_index < blocks_in_piece(block.piece_index));
1951
1952 // if there are other peers, leave the block requested
1953 if (info.num_peers > 0) return;
1954
1955 // clear the downloader of this block
1956 info.peer = 0;
1957
1958 // clear this block as being downloaded
1959 info.state = block_info::state_none;
1960 --i->requested;
1961
1962 // if there are no other blocks in this piece
1963 // that's being downloaded, remove it from the list
1964 if (i->requested + i->finished + i->writing == 0)
1965 {
1966 erase_download_piece(i);
1967 piece_pos& p = m_piece_map[block.piece_index];
1968 int prev_prio = p.priority(this);
1969 TORRENT_ASSERT(prev_prio < int(m_priority_boundries.size())
1970 || m_dirty);
1971 p.downloading = 0;
1972 if (m_sequential_download == -1 && !m_dirty)
1973 {
1974 int prio = p.priority(this);
1975 if (prev_prio == -1 && prio >= 0) add(block.piece_index);
1976 else if (prev_prio >= 0) update(prev_prio, p.index);
1977 }
1978
1979 TORRENT_ASSERT(std::find_if(m_downloads.begin(), m_downloads.end()
1980 , has_index(block.piece_index)) == m_downloads.end());
1981 }
1982 else if (i->requested == 0)
1983 {
1984 // there are no blocks requested in this piece.
1985 // remove the fast/slow state from it
1986 i->state = none;
1987 }
1988 }
1989
1990 int piece_picker::unverified_blocks() const
1991 {
1992 int counter = 0;
1993 for (std::vector<downloading_piece>::const_iterator i = m_downloads.begin();
1994 i != m_downloads.end(); ++i)
1995 {
1996 counter += (int)i->finished;
1997 }
1998 return counter;
1999 }
2000
2001 }
2002
libtorrent fork