source: trunk/libtransmission/peer-mgr.c @ 12249

Last change on this file since 12249 was 12249, checked in by jordan, 11 years ago

(trunk libT) whoops, remove 4 debugging fprintf()'s from the previous commit

  • Property svn:keywords set to Date Rev Author Id
File size: 114.3 KB
Line 
1/*
2 * This file Copyright (C) Mnemosyne LLC
3 *
4 * This file is licensed by the GPL version 2. Works owned by the
5 * Transmission project are granted a special exemption to clause 2(b)
6 * so that the bulk of its code can remain under the MIT license.
7 * This exemption does not extend to derived works not owned by
8 * the Transmission project.
9 *
10 * $Id: peer-mgr.c 12249 2011-03-28 16:33:40Z jordan $
11 */
12
13#include <assert.h>
14#include <errno.h> /* error codes ERANGE, ... */
15#include <limits.h> /* INT_MAX */
16#include <string.h> /* memcpy, memcmp, strstr */
17#include <stdlib.h> /* qsort */
18
19#include <event2/event.h>
20#include <libutp/utp.h>
21
22#include "transmission.h"
23#include "announcer.h"
24#include "bandwidth.h"
25#include "blocklist.h"
26#include "cache.h"
27#include "clients.h"
28#include "completion.h"
29#include "crypto.h"
30#include "handshake.h"
31#include "net.h"
32#include "peer-io.h"
33#include "peer-mgr.h"
34#include "peer-msgs.h"
35#include "ptrarray.h"
36#include "session.h"
37#include "stats.h" /* tr_statsAddUploaded, tr_statsAddDownloaded */
38#include "torrent.h"
39#include "utils.h"
40#include "webseed.h"
41
42enum
43{
44    /* how frequently to cull old atoms */
45    ATOM_PERIOD_MSEC = ( 60 * 1000 ),
46
47    /* how frequently to change which peers are choked */
48    RECHOKE_PERIOD_MSEC = ( 10 * 1000 ),
49
50    /* an optimistically unchoked peer is immune from rechoking
51       for this many calls to rechokeUploads(). */
52    OPTIMISTIC_UNCHOKE_MULTIPLIER = 4,
53
54    /* how frequently to reallocate bandwidth */
55    BANDWIDTH_PERIOD_MSEC = 500,
56
57    /* how frequently to age out old piece request lists */
58    REFILL_UPKEEP_PERIOD_MSEC = ( 10 * 1000 ),
59
60    /* how frequently to decide which peers live and die */
61    RECONNECT_PERIOD_MSEC = 500,
62
63    /* when many peers are available, keep idle ones this long */
64    MIN_UPLOAD_IDLE_SECS = ( 60 ),
65
66    /* when few peers are available, keep idle ones this long */
67    MAX_UPLOAD_IDLE_SECS = ( 60 * 5 ),
68
69    /* max number of peers to ask for per second overall.
70     * this throttle is to avoid overloading the router */
71    MAX_CONNECTIONS_PER_SECOND = 12,
72
73    MAX_CONNECTIONS_PER_PULSE = (int)(MAX_CONNECTIONS_PER_SECOND * (RECONNECT_PERIOD_MSEC/1000.0)),
74
75    /* number of bad pieces a peer is allowed to send before we ban them */
76    MAX_BAD_PIECES_PER_PEER = 5,
77
78    /* amount of time to keep a list of request pieces lying around
79       before it's considered too old and needs to be rebuilt */
80    PIECE_LIST_SHELF_LIFE_SECS = 60,
81
82    /* use for bitwise operations w/peer_atom.flags2 */
83    MYFLAG_BANNED = 1,
84
85    /* use for bitwise operations w/peer_atom.flags2 */
86    /* unreachable for now... but not banned.
87     * if they try to connect to us it's okay */
88    MYFLAG_UNREACHABLE = 2,
89
90    /* the minimum we'll wait before attempting to reconnect to a peer */
91    MINIMUM_RECONNECT_INTERVAL_SECS = 5,
92
93    /** how long we'll let requests we've made linger before we cancel them */
94    REQUEST_TTL_SECS = 120,
95
96    NO_BLOCKS_CANCEL_HISTORY = 120,
97
98    CANCEL_HISTORY_SEC = 60
99};
100
101const tr_peer_event TR_PEER_EVENT_INIT = { 0, 0, NULL, 0, 0, 0, false, 0 };
102
103/**
104***
105**/
106
107/**
108 * Peer information that should be kept even before we've connected and
109 * after we've disconnected. These are kept in a pool of peer_atoms to decide
110 * which ones would make good candidates for connecting to, and to watch out
111 * for banned peers.
112 *
113 * @see tr_peer
114 * @see tr_peermsgs
115 */
116struct peer_atom
117{
118    uint8_t     fromFirst;          /* where the peer was first found */
119    uint8_t     fromBest;           /* the "best" value of where the peer has been found */
120    uint8_t     flags;              /* these match the added_f flags */
121    uint8_t     flags2;             /* flags that aren't defined in added_f */
122    int8_t      seedProbability;    /* how likely is this to be a seed... [0..100] or -1 for unknown */
123    int8_t      blocklisted;        /* -1 for unknown, true for blocklisted, false for not blocklisted */
124
125    tr_port     port;
126    bool        utp_failed;         /* We recently failed to connect over uTP */
127    uint16_t    numFails;
128    time_t      time;               /* when the peer's connection status last changed */
129    time_t      piece_data_time;
130
131    time_t      lastConnectionAttemptAt;
132    time_t      lastConnectionAt;
133
134    /* similar to a TTL field, but less rigid --
135     * if the swarm is small, the atom will be kept past this date. */
136    time_t      shelf_date;
137    tr_peer   * peer;               /* will be NULL if not connected */
138    tr_address  addr;
139};
140
141#ifdef NDEBUG
142#define tr_isAtom(a) (TRUE)
143#else
144static bool
145tr_isAtom( const struct peer_atom * atom )
146{
147    return ( atom != NULL )
148        && ( atom->fromFirst < TR_PEER_FROM__MAX )
149        && ( atom->fromBest < TR_PEER_FROM__MAX )
150        && ( tr_address_is_valid( &atom->addr ) );
151}
152#endif
153
154static const char*
155tr_atomAddrStr( const struct peer_atom * atom )
156{
157    return atom ? tr_peerIoAddrStr( &atom->addr, atom->port ) : "[no atom]";
158}
159
160struct block_request
161{
162    tr_block_index_t block;
163    tr_peer * peer;
164    time_t sentAt;
165};
166
167struct weighted_piece
168{
169    tr_piece_index_t index;
170    int16_t salt;
171    int16_t requestCount;
172};
173
174enum piece_sort_state
175{
176    PIECES_UNSORTED,
177    PIECES_SORTED_BY_INDEX,
178    PIECES_SORTED_BY_WEIGHT
179};
180
181/** @brief Opaque, per-torrent data structure for peer connection information */
182typedef struct tr_torrent_peers
183{
184    tr_ptrArray                outgoingHandshakes; /* tr_handshake */
185    tr_ptrArray                pool; /* struct peer_atom */
186    tr_ptrArray                peers; /* tr_peer */
187    tr_ptrArray                webseeds; /* tr_webseed */
188
189    tr_torrent               * tor;
190    struct tr_peerMgr        * manager;
191
192    tr_peer                  * optimistic; /* the optimistic peer, or NULL if none */
193    int                        optimisticUnchokeTimeScaler;
194
195    bool                       isRunning;
196    bool                       needsCompletenessCheck;
197
198    struct block_request     * requests;
199    int                        requestCount;
200    int                        requestAlloc;
201
202    struct weighted_piece    * pieces;
203    int                        pieceCount;
204    enum piece_sort_state      pieceSortState;
205
206    /* An array of pieceCount items stating how many peers have each piece.
207       This is used to help us for downloading pieces "rarest first."
208       This may be NULL if we don't have metainfo yet, or if we're not
209       downloading and don't care about rarity */
210    uint16_t                 * pieceReplication;
211    size_t                     pieceReplicationSize;
212
213    int                        interestedCount;
214    int                        maxPeers;
215    time_t                     lastCancel;
216
217    /* Before the endgame this should be 0. In endgame, is contains the average
218     * number of pending requests per peer. Only peers which have more pending
219     * requests are considered 'fast' are allowed to request a block that's
220     * already been requested from another (slower?) peer. */
221    int                        endgame;
222}
223Torrent;
224
225struct tr_peerMgr
226{
227    tr_session    * session;
228    tr_ptrArray     incomingHandshakes; /* tr_handshake */
229    struct event  * bandwidthTimer;
230    struct event  * rechokeTimer;
231    struct event  * refillUpkeepTimer;
232    struct event  * atomTimer;
233};
234
235#define tordbg( t, ... ) \
236    do { \
237        if( tr_deepLoggingIsActive( ) ) \
238            tr_deepLog( __FILE__, __LINE__, tr_torrentName( t->tor ), __VA_ARGS__ ); \
239    } while( 0 )
240
241#define dbgmsg( ... ) \
242    do { \
243        if( tr_deepLoggingIsActive( ) ) \
244            tr_deepLog( __FILE__, __LINE__, NULL, __VA_ARGS__ ); \
245    } while( 0 )
246
247/**
248***
249**/
250
251static inline void
252managerLock( const struct tr_peerMgr * manager )
253{
254    tr_sessionLock( manager->session );
255}
256
257static inline void
258managerUnlock( const struct tr_peerMgr * manager )
259{
260    tr_sessionUnlock( manager->session );
261}
262
263static inline void
264torrentLock( Torrent * torrent )
265{
266    managerLock( torrent->manager );
267}
268
269static inline void
270torrentUnlock( Torrent * torrent )
271{
272    managerUnlock( torrent->manager );
273}
274
275static inline int
276torrentIsLocked( const Torrent * t )
277{
278    return tr_sessionIsLocked( t->manager->session );
279}
280
281/**
282***
283**/
284
285static int
286handshakeCompareToAddr( const void * va, const void * vb )
287{
288    const tr_handshake * a = va;
289
290    return tr_address_compare( tr_handshakeGetAddr( a, NULL ), vb );
291}
292
293static int
294handshakeCompare( const void * a, const void * b )
295{
296    return handshakeCompareToAddr( a, tr_handshakeGetAddr( b, NULL ) );
297}
298
299static inline tr_handshake*
300getExistingHandshake( tr_ptrArray * handshakes, const tr_address * addr )
301{
302    if( tr_ptrArrayEmpty( handshakes ) )
303        return NULL;
304
305    return tr_ptrArrayFindSorted( handshakes, addr, handshakeCompareToAddr );
306}
307
308static int
309comparePeerAtomToAddress( const void * va, const void * vb )
310{
311    const struct peer_atom * a = va;
312
313    return tr_address_compare( &a->addr, vb );
314}
315
316static int
317compareAtomsByAddress( const void * va, const void * vb )
318{
319    const struct peer_atom * b = vb;
320
321    assert( tr_isAtom( b ) );
322
323    return comparePeerAtomToAddress( va, &b->addr );
324}
325
326/**
327***
328**/
329
330const tr_address *
331tr_peerAddress( const tr_peer * peer )
332{
333    return &peer->atom->addr;
334}
335
336static Torrent*
337getExistingTorrent( tr_peerMgr *    manager,
338                    const uint8_t * hash )
339{
340    tr_torrent * tor = tr_torrentFindFromHash( manager->session, hash );
341
342    return tor == NULL ? NULL : tor->torrentPeers;
343}
344
345static int
346peerCompare( const void * a, const void * b )
347{
348    return tr_address_compare( tr_peerAddress( a ), tr_peerAddress( b ) );
349}
350
351static struct peer_atom*
352getExistingAtom( const Torrent    * t,
353                 const tr_address * addr )
354{
355    Torrent * tt = (Torrent*)t;
356    assert( torrentIsLocked( t ) );
357    return tr_ptrArrayFindSorted( &tt->pool, addr, comparePeerAtomToAddress );
358}
359
360static bool
361peerIsInUse( const Torrent * ct, const struct peer_atom * atom )
362{
363    Torrent * t = (Torrent*) ct;
364
365    assert( torrentIsLocked ( t ) );
366
367    return ( atom->peer != NULL )
368        || getExistingHandshake( &t->outgoingHandshakes, &atom->addr )
369        || getExistingHandshake( &t->manager->incomingHandshakes, &atom->addr );
370}
371
372void
373tr_peerConstruct( tr_peer * peer )
374{
375    memset( peer, 0, sizeof( tr_peer ) );
376
377    peer->have = TR_BITFIELD_INIT;
378
379    tr_historyConstruct( &peer->blocksSentToClient,  CANCEL_HISTORY_SEC, ( RECHOKE_PERIOD_MSEC / 1000 ) );
380    tr_historyConstruct( &peer->blocksSentToPeer,    CANCEL_HISTORY_SEC, ( RECHOKE_PERIOD_MSEC / 1000 ) );
381    tr_historyConstruct( &peer->cancelsSentToClient, CANCEL_HISTORY_SEC, ( RECHOKE_PERIOD_MSEC / 1000 ) );
382    tr_historyConstruct( &peer->cancelsSentToPeer,   CANCEL_HISTORY_SEC, ( REFILL_UPKEEP_PERIOD_MSEC / 1000 ) );
383}
384
385static tr_peer*
386peerNew( struct peer_atom * atom )
387{
388    tr_peer * peer = tr_new( tr_peer, 1 );
389    tr_peerConstruct( peer );
390
391    peer->atom = atom;
392    atom->peer = peer;
393
394    return peer;
395}
396
397static tr_peer*
398getPeer( Torrent * torrent, struct peer_atom * atom )
399{
400    tr_peer * peer;
401
402    assert( torrentIsLocked( torrent ) );
403
404    peer = atom->peer;
405
406    if( peer == NULL )
407    {
408        peer = peerNew( atom );
409        tr_bitfieldConstruct( &peer->have, torrent->tor->blockCount );
410        tr_bitfieldConstruct( &peer->blame, torrent->tor->blockCount );
411        tr_ptrArrayInsertSorted( &torrent->peers, peer, peerCompare );
412    }
413
414    return peer;
415}
416
417static void peerDeclinedAllRequests( Torrent *, const tr_peer * );
418
419void
420tr_peerDestruct( tr_torrent * tor, tr_peer * peer )
421{
422    assert( peer != NULL );
423
424    if( tor->torrentPeers->isRunning )
425        peerDeclinedAllRequests( tor->torrentPeers, peer );
426
427    if( peer->msgs != NULL )
428        tr_peerMsgsFree( peer->msgs );
429
430    if( peer->io ) {
431        tr_peerIoClear( peer->io );
432        tr_peerIoUnref( peer->io ); /* balanced by the ref in handshakeDoneCB() */
433    }
434
435    tr_historyDestruct( &peer->blocksSentToClient  );
436    tr_historyDestruct( &peer->blocksSentToPeer    );
437    tr_historyDestruct( &peer->cancelsSentToClient );
438    tr_historyDestruct( &peer->cancelsSentToPeer   );
439
440    tr_bitfieldDestruct( &peer->have );
441    tr_bitfieldDestruct( &peer->blame );
442    tr_free( peer->client );
443
444    if( peer->atom )
445        peer->atom->peer = NULL;
446}
447
448static void
449peerDelete( Torrent * t, tr_peer * peer )
450{
451    tr_peerDestruct( t->tor, peer );
452    tr_free( peer );
453}
454
455static bool
456replicationExists( const Torrent * t )
457{
458    return t->pieceReplication != NULL;
459}
460
461static void
462replicationFree( Torrent * t )
463{
464    tr_free( t->pieceReplication );
465    t->pieceReplication = NULL;
466    t->pieceReplicationSize = 0;
467}
468
469static void
470replicationNew( Torrent * t )
471{
472    tr_piece_index_t piece_i;
473    const tr_piece_index_t piece_count = t->tor->info.pieceCount;
474    tr_peer ** peers = (tr_peer**) tr_ptrArrayBase( &t->peers );
475    const int peer_count = tr_ptrArraySize( &t->peers );
476
477    assert( !replicationExists( t ) );
478
479    t->pieceReplicationSize = piece_count;
480    t->pieceReplication = tr_new0( uint16_t, piece_count );
481
482    for( piece_i=0; piece_i<piece_count; ++piece_i )
483    {
484        int peer_i;
485        uint16_t r = 0;
486
487        for( peer_i=0; peer_i<peer_count; ++peer_i )
488            if( tr_bitfieldHas( &peers[peer_i]->have, piece_i ) )
489                ++r;
490
491        t->pieceReplication[piece_i] = r;
492    }
493}
494
495static void
496torrentFree( void * vt )
497{
498    Torrent * t = vt;
499
500    assert( t );
501    assert( !t->isRunning );
502    assert( torrentIsLocked( t ) );
503    assert( tr_ptrArrayEmpty( &t->outgoingHandshakes ) );
504    assert( tr_ptrArrayEmpty( &t->peers ) );
505
506    tr_ptrArrayDestruct( &t->webseeds, (PtrArrayForeachFunc)tr_webseedFree );
507    tr_ptrArrayDestruct( &t->pool, (PtrArrayForeachFunc)tr_free );
508    tr_ptrArrayDestruct( &t->outgoingHandshakes, NULL );
509    tr_ptrArrayDestruct( &t->peers, NULL );
510
511    replicationFree( t );
512
513    tr_free( t->requests );
514    tr_free( t->pieces );
515    tr_free( t );
516}
517
518static void peerCallbackFunc( tr_peer *, const tr_peer_event *, void * );
519
520static Torrent*
521torrentNew( tr_peerMgr * manager, tr_torrent * tor )
522{
523    int       i;
524    Torrent * t;
525
526    t = tr_new0( Torrent, 1 );
527    t->manager = manager;
528    t->tor = tor;
529    t->pool = TR_PTR_ARRAY_INIT;
530    t->peers = TR_PTR_ARRAY_INIT;
531    t->webseeds = TR_PTR_ARRAY_INIT;
532    t->outgoingHandshakes = TR_PTR_ARRAY_INIT;
533
534    for( i = 0; i < tor->info.webseedCount; ++i )
535    {
536        tr_webseed * w =
537            tr_webseedNew( tor, tor->info.webseeds[i], peerCallbackFunc, t );
538        tr_ptrArrayAppend( &t->webseeds, w );
539    }
540
541    return t;
542}
543
544tr_peerMgr*
545tr_peerMgrNew( tr_session * session )
546{
547    tr_peerMgr * m = tr_new0( tr_peerMgr, 1 );
548    m->session = session;
549    m->incomingHandshakes = TR_PTR_ARRAY_INIT;
550    return m;
551}
552
553static void
554deleteTimer( struct event ** t )
555{
556    if( *t != NULL )
557    {
558        event_free( *t );
559        *t = NULL;
560    }
561}
562
563static void
564deleteTimers( struct tr_peerMgr * m )
565{
566    deleteTimer( &m->atomTimer );
567    deleteTimer( &m->bandwidthTimer );
568    deleteTimer( &m->rechokeTimer );
569    deleteTimer( &m->refillUpkeepTimer );
570}
571
572void
573tr_peerMgrFree( tr_peerMgr * manager )
574{
575    managerLock( manager );
576
577    deleteTimers( manager );
578
579    /* free the handshakes. Abort invokes handshakeDoneCB(), which removes
580     * the item from manager->handshakes, so this is a little roundabout... */
581    while( !tr_ptrArrayEmpty( &manager->incomingHandshakes ) )
582        tr_handshakeAbort( tr_ptrArrayNth( &manager->incomingHandshakes, 0 ) );
583
584    tr_ptrArrayDestruct( &manager->incomingHandshakes, NULL );
585
586    managerUnlock( manager );
587    tr_free( manager );
588}
589
590static int
591clientIsDownloadingFrom( const tr_torrent * tor, const tr_peer * peer )
592{
593    if( !tr_torrentHasMetadata( tor ) )
594        return true;
595
596    return peer->clientIsInterested && !peer->clientIsChoked;
597}
598
599static int
600clientIsUploadingTo( const tr_peer * peer )
601{
602    return peer->peerIsInterested && !peer->peerIsChoked;
603}
604
605/***
606****
607***/
608
609void
610tr_peerMgrOnBlocklistChanged( tr_peerMgr * mgr )
611{
612    tr_torrent * tor = NULL;
613    tr_session * session = mgr->session;
614
615    /* we cache whether or not a peer is blocklisted...
616       since the blocklist has changed, erase that cached value */
617    while(( tor = tr_torrentNext( session, tor )))
618    {
619        int i;
620        Torrent * t = tor->torrentPeers;
621        const int n = tr_ptrArraySize( &t->pool );
622        for( i=0; i<n; ++i ) {
623            struct peer_atom * atom = tr_ptrArrayNth( &t->pool, i );
624            atom->blocklisted = -1;
625        }
626    }
627}
628
629static bool
630isAtomBlocklisted( tr_session * session, struct peer_atom * atom )
631{
632    if( atom->blocklisted < 0 )
633        atom->blocklisted = tr_sessionIsAddressBlocked( session, &atom->addr );
634
635    assert( tr_isBool( atom->blocklisted ) );
636    return atom->blocklisted;
637}
638
639
640/***
641****
642***/
643
644static void
645atomSetSeedProbability( struct peer_atom * atom, int seedProbability )
646{
647    assert( atom != NULL );
648    assert( -1<=seedProbability && seedProbability<=100 );
649
650    atom->seedProbability = seedProbability;
651
652    if( seedProbability == 100 )
653        atom->flags |= ADDED_F_SEED_FLAG;
654    else if( seedProbability != -1 )
655        atom->flags &= ~ADDED_F_SEED_FLAG;
656}
657
658static inline bool
659atomIsSeed( const struct peer_atom * atom )
660{
661    return atom->seedProbability == 100;
662}
663
664static void
665atomSetSeed( const Torrent * t, struct peer_atom * atom )
666{
667    if( !atomIsSeed( atom ) )
668    {
669        tordbg( t, "marking peer %s as a seed", tr_atomAddrStr( atom ) );
670
671        atomSetSeedProbability( atom, 100 );
672    }
673}
674
675
676bool
677tr_peerMgrPeerIsSeed( const tr_torrent  * tor,
678                      const tr_address  * addr )
679{
680    bool isSeed = false;
681    const Torrent * t = tor->torrentPeers;
682    const struct peer_atom * atom = getExistingAtom( t, addr );
683
684    if( atom )
685        isSeed = atomIsSeed( atom );
686
687    return isSeed;
688}
689
690void
691tr_peerMgrSetUtpSupported( tr_torrent * tor, const tr_address * addr )
692{
693    struct peer_atom * atom = getExistingAtom( tor->torrentPeers, addr );
694
695    if( atom )
696        atom->flags |= ADDED_F_UTP_FLAGS;
697}
698
699void
700tr_peerMgrSetUtpFailed( tr_torrent *tor, const tr_address *addr, bool failed )
701{
702    struct peer_atom * atom = getExistingAtom( tor->torrentPeers, addr );
703
704    if( atom )
705        atom->utp_failed = failed;
706}
707
708
709/**
710***  REQUESTS
711***
712*** There are two data structures associated with managing block requests:
713***
714*** 1. Torrent::requests, an array of "struct block_request" which keeps
715***    track of which blocks have been requested, and when, and by which peers.
716***    This is list is used for (a) cancelling requests that have been pending
717***    for too long and (b) avoiding duplicate requests before endgame.
718***
719*** 2. Torrent::pieces, an array of "struct weighted_piece" which lists the
720***    pieces that we want to request. It's used to decide which blocks to
721***    return next when tr_peerMgrGetBlockRequests() is called.
722**/
723
724/**
725*** struct block_request
726**/
727
728static int
729compareReqByBlock( const void * va, const void * vb )
730{
731    const struct block_request * a = va;
732    const struct block_request * b = vb;
733
734    /* primary key: block */
735    if( a->block < b->block ) return -1;
736    if( a->block > b->block ) return 1;
737
738    /* secondary key: peer */
739    if( a->peer < b->peer ) return -1;
740    if( a->peer > b->peer ) return 1;
741
742    return 0;
743}
744
745static void
746requestListAdd( Torrent * t, tr_block_index_t block, tr_peer * peer )
747{
748    struct block_request key;
749
750    /* ensure enough room is available... */
751    if( t->requestCount + 1 >= t->requestAlloc )
752    {
753        const int CHUNK_SIZE = 128;
754        t->requestAlloc += CHUNK_SIZE;
755        t->requests = tr_renew( struct block_request,
756                                t->requests, t->requestAlloc );
757    }
758
759    /* populate the record we're inserting */
760    key.block = block;
761    key.peer = peer;
762    key.sentAt = tr_time( );
763
764    /* insert the request to our array... */
765    {
766        bool exact;
767        const int pos = tr_lowerBound( &key, t->requests, t->requestCount,
768                                       sizeof( struct block_request ),
769                                       compareReqByBlock, &exact );
770        assert( !exact );
771        memmove( t->requests + pos + 1,
772                 t->requests + pos,
773                 sizeof( struct block_request ) * ( t->requestCount++ - pos ) );
774        t->requests[pos] = key;
775    }
776
777    if( peer != NULL )
778    {
779        ++peer->pendingReqsToPeer;
780        assert( peer->pendingReqsToPeer >= 0 );
781    }
782
783    /*fprintf( stderr, "added request of block %lu from peer %s... "
784                       "there are now %d block\n",
785                       (unsigned long)block, tr_atomAddrStr( peer->atom ), t->requestCount );*/
786}
787
788static struct block_request *
789requestListLookup( Torrent * t, tr_block_index_t block, const tr_peer * peer )
790{
791    struct block_request key;
792    key.block = block;
793    key.peer = (tr_peer*) peer;
794
795    return bsearch( &key, t->requests, t->requestCount,
796                    sizeof( struct block_request ),
797                    compareReqByBlock );
798}
799
800/**
801 * Find the peers are we currently requesting the block
802 * with index @a block from and append them to @a peerArr.
803 */
804static void
805getBlockRequestPeers( Torrent * t, tr_block_index_t block,
806                      tr_ptrArray * peerArr )
807{
808    bool exact;
809    int i, pos;
810    struct block_request key;
811
812    key.block = block;
813    key.peer = NULL;
814    pos = tr_lowerBound( &key, t->requests, t->requestCount,
815                         sizeof( struct block_request ),
816                         compareReqByBlock, &exact );
817
818    assert( !exact ); /* shouldn't have a request with .peer == NULL */
819
820    for( i = pos; i < t->requestCount; ++i )
821    {
822        if( t->requests[i].block != block )
823            break;
824        tr_ptrArrayAppend( peerArr, t->requests[i].peer );
825    }
826}
827
828static void
829decrementPendingReqCount( const struct block_request * b )
830{
831    if( b->peer != NULL )
832        if( b->peer->pendingReqsToPeer > 0 )
833            --b->peer->pendingReqsToPeer;
834}
835
836static void
837requestListRemove( Torrent * t, tr_block_index_t block, const tr_peer * peer )
838{
839    const struct block_request * b = requestListLookup( t, block, peer );
840    if( b != NULL )
841    {
842        const int pos = b - t->requests;
843        assert( pos < t->requestCount );
844
845        decrementPendingReqCount( b );
846
847        tr_removeElementFromArray( t->requests,
848                                   pos,
849                                   sizeof( struct block_request ),
850                                   t->requestCount-- );
851
852        /*fprintf( stderr, "removing request of block %lu from peer %s... "
853                           "there are now %d block requests left\n",
854                           (unsigned long)block, tr_atomAddrStr( peer->atom ), t->requestCount );*/
855    }
856}
857
858static int
859countActiveWebseeds( const Torrent * t )
860{
861    int activeCount = 0;
862    const tr_webseed ** w = (const tr_webseed **) tr_ptrArrayBase( &t->webseeds );
863    const tr_webseed ** const wend = w + tr_ptrArraySize( &t->webseeds );
864
865    for( ; w!=wend; ++w )
866        if( tr_webseedIsActive( *w ) )
867            ++activeCount;
868
869    return activeCount;
870}
871
872static bool
873testForEndgame( const Torrent * t )
874{
875    /* we consider ourselves to be in endgame if the number of bytes
876       we've got requested is >= the number of bytes left to download */
877    return ( t->requestCount * t->tor->blockSize )
878               <= tr_cpLeftUntilDone( &t->tor->completion );
879}
880
881static void
882updateEndgame( Torrent * t )
883{
884    assert( t->requestCount >= 0 );
885
886    if( !testForEndgame( t ) )
887    {
888        /* not in endgame */
889        t->endgame = 0;
890    }
891    else if( !t->endgame ) /* only recalculate when endgame first begins */
892    {
893        int numDownloading = 0;
894        const tr_peer ** p = (const tr_peer **) tr_ptrArrayBase( &t->peers );
895        const tr_peer ** const pend = p + tr_ptrArraySize( &t->peers );
896
897        /* add the active bittorrent peers... */
898        for( ; p!=pend; ++p )
899            if( (*p)->pendingReqsToPeer > 0 )
900                ++numDownloading;
901
902        /* add the active webseeds... */
903        numDownloading += countActiveWebseeds( t );
904
905        /* average number of pending requests per downloading peer */
906        t->endgame = t->requestCount / MAX( numDownloading, 1 );
907    }
908}
909
910
911/****
912*****
913*****  Piece List Manipulation / Accessors
914*****
915****/
916
917static inline void
918invalidatePieceSorting( Torrent * t )
919{
920    t->pieceSortState = PIECES_UNSORTED;
921}
922
923static const tr_torrent * weightTorrent;
924
925static const uint16_t * weightReplication;
926
927static void
928setComparePieceByWeightTorrent( Torrent * t )
929{
930    if( !replicationExists( t ) )
931        replicationNew( t );
932
933    weightTorrent = t->tor;
934    weightReplication = t->pieceReplication;
935}
936
937/* we try to create a "weight" s.t. high-priority pieces come before others,
938 * and that partially-complete pieces come before empty ones. */
939static int
940comparePieceByWeight( const void * va, const void * vb )
941{
942    const struct weighted_piece * a = va;
943    const struct weighted_piece * b = vb;
944    int ia, ib, missing, pending;
945    const tr_torrent * tor = weightTorrent;
946    const uint16_t * rep = weightReplication;
947
948    /* primary key: weight */
949    missing = tr_cpMissingBlocksInPiece( &tor->completion, a->index );
950    pending = a->requestCount;
951    ia = missing > pending ? missing - pending : (tor->blockCountInPiece + pending);
952    missing = tr_cpMissingBlocksInPiece( &tor->completion, b->index );
953    pending = b->requestCount;
954    ib = missing > pending ? missing - pending : (tor->blockCountInPiece + pending);
955    if( ia < ib ) return -1;
956    if( ia > ib ) return 1;
957
958    /* secondary key: higher priorities go first */
959    ia = tor->info.pieces[a->index].priority;
960    ib = tor->info.pieces[b->index].priority;
961    if( ia > ib ) return -1;
962    if( ia < ib ) return 1;
963
964    /* tertiary key: rarest first. */
965    ia = rep[a->index];
966    ib = rep[b->index];
967    if( ia < ib ) return -1;
968    if( ia > ib ) return 1;
969
970    /* quaternary key: random */
971    if( a->salt < b->salt ) return -1;
972    if( a->salt > b->salt ) return 1;
973
974    /* okay, they're equal */
975    return 0;
976}
977
978static int
979comparePieceByIndex( const void * va, const void * vb )
980{
981    const struct weighted_piece * a = va;
982    const struct weighted_piece * b = vb;
983    if( a->index < b->index ) return -1;
984    if( a->index > b->index ) return 1;
985    return 0;
986}
987
988static void
989pieceListSort( Torrent * t, enum piece_sort_state state )
990{
991    assert( state==PIECES_SORTED_BY_INDEX
992         || state==PIECES_SORTED_BY_WEIGHT );
993
994
995    if( state == PIECES_SORTED_BY_WEIGHT )
996    {
997        setComparePieceByWeightTorrent( t );
998        qsort( t->pieces, t->pieceCount, sizeof( struct weighted_piece ), comparePieceByWeight );
999    }
1000    else
1001        qsort( t->pieces, t->pieceCount, sizeof( struct weighted_piece ), comparePieceByIndex );
1002
1003    t->pieceSortState = state;
1004}
1005
1006/**
1007 * These functions are useful for testing, but too expensive for nightly builds.
1008 * let's leave it disabled but add an easy hook to compile it back in
1009 */
1010#if 1
1011#define assertWeightedPiecesAreSorted(t)
1012#define assertReplicationCountIsExact(t)
1013#else
1014static void
1015assertWeightedPiecesAreSorted( Torrent * t )
1016{
1017    if( !t->endgame )
1018    {
1019        int i;
1020        setComparePieceByWeightTorrent( t );
1021        for( i=0; i<t->pieceCount-1; ++i )
1022            assert( comparePieceByWeight( &t->pieces[i], &t->pieces[i+1] ) <= 0 );
1023    }
1024}
1025static void
1026assertReplicationCountIsExact( Torrent * t )
1027{
1028    /* This assert might fail due to errors of implementations in other
1029     * clients. It happens when receiving duplicate bitfields/HaveAll/HaveNone
1030     * from a client. If a such a behavior is noticed,
1031     * a bug report should be filled to the faulty client. */
1032
1033    size_t piece_i;
1034    const uint16_t * rep = t->pieceReplication;
1035    const size_t piece_count = t->pieceReplicationSize;
1036    const tr_peer ** peers = (const tr_peer**) tr_ptrArrayBase( &t->peers );
1037    const int peer_count = tr_ptrArraySize( &t->peers );
1038
1039    assert( piece_count == t->tor->info.pieceCount );
1040
1041    for( piece_i=0; piece_i<piece_count; ++piece_i )
1042    {
1043        int peer_i;
1044        uint16_t r = 0;
1045
1046        for( peer_i=0; peer_i<peer_count; ++peer_i )
1047            if( tr_bitsetHas( &peers[peer_i]->have, piece_i ) )
1048                ++r;
1049
1050        assert( rep[piece_i] == r );
1051    }
1052}
1053#endif
1054
1055static struct weighted_piece *
1056pieceListLookup( Torrent * t, tr_piece_index_t index )
1057{
1058    int i;
1059
1060    for( i=0; i<t->pieceCount; ++i )
1061        if( t->pieces[i].index == index )
1062            return &t->pieces[i];
1063
1064    return NULL;
1065}
1066
1067static void
1068pieceListRebuild( Torrent * t )
1069{
1070
1071    if( !tr_torrentIsSeed( t->tor ) )
1072    {
1073        tr_piece_index_t i;
1074        tr_piece_index_t * pool;
1075        tr_piece_index_t poolCount = 0;
1076        const tr_torrent * tor = t->tor;
1077        const tr_info * inf = tr_torrentInfo( tor );
1078        struct weighted_piece * pieces;
1079        int pieceCount;
1080
1081        /* build the new list */
1082        pool = tr_new( tr_piece_index_t, inf->pieceCount );
1083        for( i=0; i<inf->pieceCount; ++i )
1084            if( !inf->pieces[i].dnd )
1085                if( !tr_cpPieceIsComplete( &tor->completion, i ) )
1086                    pool[poolCount++] = i;
1087        pieceCount = poolCount;
1088        pieces = tr_new0( struct weighted_piece, pieceCount );
1089        for( i=0; i<poolCount; ++i ) {
1090            struct weighted_piece * piece = pieces + i;
1091            piece->index = pool[i];
1092            piece->requestCount = 0;
1093            piece->salt = tr_cryptoWeakRandInt( 4096 );
1094        }
1095
1096        /* if we already had a list of pieces, merge it into
1097         * the new list so we don't lose its requestCounts */
1098        if( t->pieces != NULL )
1099        {
1100            struct weighted_piece * o = t->pieces;
1101            struct weighted_piece * oend = o + t->pieceCount;
1102            struct weighted_piece * n = pieces;
1103            struct weighted_piece * nend = n + pieceCount;
1104
1105            pieceListSort( t, PIECES_SORTED_BY_INDEX );
1106
1107            while( o!=oend && n!=nend ) {
1108                if( o->index < n->index )
1109                    ++o;
1110                else if( o->index > n->index )
1111                    ++n;
1112                else
1113                    *n++ = *o++;
1114            }
1115
1116            tr_free( t->pieces );
1117        }
1118
1119        t->pieces = pieces;
1120        t->pieceCount = pieceCount;
1121
1122        pieceListSort( t, PIECES_SORTED_BY_WEIGHT );
1123
1124        /* cleanup */
1125        tr_free( pool );
1126    }
1127}
1128
1129static void
1130pieceListRemovePiece( Torrent * t, tr_piece_index_t piece )
1131{
1132    struct weighted_piece * p;
1133
1134    if(( p = pieceListLookup( t, piece )))
1135    {
1136        const int pos = p - t->pieces;
1137
1138        tr_removeElementFromArray( t->pieces,
1139                                   pos,
1140                                   sizeof( struct weighted_piece ),
1141                                   t->pieceCount-- );
1142
1143        if( t->pieceCount == 0 )
1144        {
1145            tr_free( t->pieces );
1146            t->pieces = NULL;
1147        }
1148    }
1149}
1150
1151static void
1152pieceListResortPiece( Torrent * t, struct weighted_piece * p )
1153{
1154    int pos;
1155    bool isSorted = true;
1156
1157    if( p == NULL )
1158        return;
1159
1160    /* is the torrent already sorted? */
1161    pos = p - t->pieces;
1162    setComparePieceByWeightTorrent( t );
1163    if( isSorted && ( pos > 0 ) && ( comparePieceByWeight( p-1, p ) > 0 ) )
1164        isSorted = false;
1165    if( isSorted && ( pos < t->pieceCount - 1 ) && ( comparePieceByWeight( p, p+1 ) > 0 ) )
1166        isSorted = false;
1167
1168    if( t->pieceSortState != PIECES_SORTED_BY_WEIGHT )
1169    {
1170       pieceListSort( t, PIECES_SORTED_BY_WEIGHT);
1171       isSorted = true;
1172    }
1173
1174    /* if it's not sorted, move it around */
1175    if( !isSorted )
1176    {
1177        bool exact;
1178        const struct weighted_piece tmp = *p;
1179
1180        tr_removeElementFromArray( t->pieces,
1181                                   pos,
1182                                   sizeof( struct weighted_piece ),
1183                                   t->pieceCount-- );
1184
1185        pos = tr_lowerBound( &tmp, t->pieces, t->pieceCount,
1186                             sizeof( struct weighted_piece ),
1187                             comparePieceByWeight, &exact );
1188
1189        memmove( &t->pieces[pos + 1],
1190                 &t->pieces[pos],
1191                 sizeof( struct weighted_piece ) * ( t->pieceCount++ - pos ) );
1192
1193        t->pieces[pos] = tmp;
1194    }
1195
1196    assertWeightedPiecesAreSorted( t );
1197}
1198
1199static void
1200pieceListRemoveRequest( Torrent * t, tr_block_index_t block )
1201{
1202    struct weighted_piece * p;
1203    const tr_piece_index_t index = tr_torBlockPiece( t->tor, block );
1204
1205    if( ((p = pieceListLookup( t, index ))) && ( p->requestCount > 0 ) )
1206    {
1207        --p->requestCount;
1208        pieceListResortPiece( t, p );
1209    }
1210}
1211
1212
1213/****
1214*****
1215*****  Replication count ( for rarest first policy )
1216*****
1217****/
1218
1219/**
1220 * Increase the replication count of this piece and sort it if the
1221 * piece list is already sorted
1222 */
1223static void
1224tr_incrReplicationOfPiece( Torrent * t, const size_t index )
1225{
1226    assert( replicationExists( t ) );
1227    assert( t->pieceReplicationSize == t->tor->info.pieceCount );
1228
1229    /* One more replication of this piece is present in the swarm */
1230    ++t->pieceReplication[index];
1231
1232    /* we only resort the piece if the list is already sorted */
1233    if( t->pieceSortState == PIECES_SORTED_BY_WEIGHT )
1234        pieceListResortPiece( t, pieceListLookup( t, index ) );
1235}
1236
1237/**
1238 * Increases the replication count of pieces present in the bitfield
1239 */
1240static void
1241tr_incrReplicationFromBitfield( Torrent * t, const tr_bitfield * b )
1242{
1243    size_t i;
1244    uint16_t * rep = t->pieceReplication;
1245    const size_t n = t->tor->info.pieceCount;
1246
1247    assert( replicationExists( t ) );
1248    assert( n == t->pieceReplicationSize );
1249    assert( tr_bitfieldTestFast( b, n-1 ) );
1250
1251    for( i=0; i<n; ++i )
1252        if( tr_bitfieldHas( b, i ) )
1253            ++rep[i];
1254
1255    if( t->pieceSortState == PIECES_SORTED_BY_WEIGHT )
1256        invalidatePieceSorting( t );
1257}
1258
1259/**
1260 * Increase the replication count of every piece
1261 */
1262static void
1263tr_incrReplication( Torrent * t )
1264{
1265    int i;
1266    const int n = t->pieceReplicationSize;
1267
1268    assert( replicationExists( t ) );
1269    assert( t->pieceReplicationSize == t->tor->info.pieceCount );
1270
1271    for( i=0; i<n; ++i )
1272        ++t->pieceReplication[i];
1273}
1274
1275/**
1276 * Decrease the replication count of pieces present in the bitset.
1277 */
1278static void
1279tr_decrReplicationFromBitfield( Torrent * t, const tr_bitfield * b )
1280{
1281    int i;
1282    const int n = t->pieceReplicationSize;
1283
1284    assert( replicationExists( t ) );
1285    assert( t->pieceReplicationSize == t->tor->info.pieceCount );
1286
1287    if( tr_bitfieldHasAll( b ) )
1288    {
1289        for( i=0; i<n; ++i )
1290            --t->pieceReplication[i];
1291    }
1292    else if ( !tr_bitfieldHasNone( b ) )
1293    {
1294        for( i=0; i<n; ++i )
1295            if( tr_bitfieldHas( b, i ) )
1296                --t->pieceReplication[i];
1297
1298        if( t->pieceSortState == PIECES_SORTED_BY_WEIGHT )
1299            invalidatePieceSorting( t );
1300    }
1301}
1302
1303/**
1304***
1305**/
1306
1307void
1308tr_peerMgrRebuildRequests( tr_torrent * tor )
1309{
1310    assert( tr_isTorrent( tor ) );
1311
1312    pieceListRebuild( tor->torrentPeers );
1313}
1314
1315void
1316tr_peerMgrGetNextRequests( tr_torrent           * tor,
1317                           tr_peer              * peer,
1318                           int                    numwant,
1319                           tr_block_index_t     * setme,
1320                           int                  * numgot )
1321{
1322    int i;
1323    int got;
1324    Torrent * t;
1325    struct weighted_piece * pieces;
1326    const tr_bitfield * const have = &peer->have;
1327
1328    /* sanity clause */
1329    assert( tr_isTorrent( tor ) );
1330    assert( peer->clientIsInterested );
1331    assert( !peer->clientIsChoked );
1332    assert( numwant > 0 );
1333
1334    /* walk through the pieces and find blocks that should be requested */
1335    got = 0;
1336    t = tor->torrentPeers;
1337
1338    /* prep the pieces list */
1339    if( t->pieces == NULL )
1340        pieceListRebuild( t );
1341
1342    if( t->pieceSortState != PIECES_SORTED_BY_WEIGHT )
1343        pieceListSort( t, PIECES_SORTED_BY_WEIGHT );
1344
1345    assertReplicationCountIsExact( t );
1346    assertWeightedPiecesAreSorted( t );
1347
1348    updateEndgame( t );
1349    pieces = t->pieces;
1350    for( i=0; i<t->pieceCount && got<numwant; ++i )
1351    {
1352        struct weighted_piece * p = pieces + i;
1353
1354        /* if the peer has this piece that we want... */
1355        if( tr_bitfieldHas( have, p->index ) )
1356        {
1357            tr_block_index_t b;
1358            tr_block_index_t first;
1359            tr_block_index_t last;
1360            tr_ptrArray peerArr = TR_PTR_ARRAY_INIT;
1361
1362            tr_torGetPieceBlockRange( tor, p->index, &first, &last );
1363
1364            for( b=first; b<=last && got<numwant; ++b )
1365            {
1366                int peerCount;
1367                tr_peer ** peers;
1368
1369                /* don't request blocks we've already got */
1370                if( tr_cpBlockIsComplete( &tor->completion, b ) )
1371                    continue;
1372
1373                /* always add peer if this block has no peers yet */
1374                tr_ptrArrayClear( &peerArr );
1375                getBlockRequestPeers( t, b, &peerArr );
1376                peers = (tr_peer **) tr_ptrArrayPeek( &peerArr, &peerCount );
1377                if( peerCount != 0 )
1378                {
1379                    /* don't make a second block request until the endgame */
1380                    if( !t->endgame )
1381                        continue;
1382
1383                    /* don't have more than two peers requesting this block */
1384                    if( peerCount > 1 )
1385                        continue;
1386
1387                    /* don't send the same request to the same peer twice */
1388                    if( peer == peers[0] )
1389                        continue;
1390
1391                    /* in the endgame allow an additional peer to download a
1392                       block but only if the peer seems to be handling requests
1393                       relatively fast */
1394                    if( peer->pendingReqsToPeer + numwant - got < t->endgame )
1395                        continue;
1396                }
1397
1398                /* update the caller's table */
1399                setme[got++] = b;
1400
1401                /* update our own tables */
1402                requestListAdd( t, b, peer );
1403                ++p->requestCount;
1404            }
1405
1406            tr_ptrArrayDestruct( &peerArr, NULL );
1407        }
1408    }
1409
1410    /* In most cases we've just changed the weights of a small number of pieces.
1411     * So rather than qsort()ing the entire array, it's faster to apply an
1412     * adaptive insertion sort algorithm. */
1413    if( got > 0 )
1414    {
1415        /* not enough requests || last piece modified */
1416        if ( i == t->pieceCount ) --i;
1417
1418        setComparePieceByWeightTorrent( t );
1419        while( --i >= 0 )
1420        {
1421            bool exact;
1422
1423            /* relative position! */
1424            const int newpos = tr_lowerBound( &t->pieces[i], &t->pieces[i + 1],
1425                                              t->pieceCount - (i + 1),
1426                                              sizeof( struct weighted_piece ),
1427                                              comparePieceByWeight, &exact );
1428            if( newpos > 0 )
1429            {
1430                const struct weighted_piece piece = t->pieces[i];
1431                memmove( &t->pieces[i],
1432                         &t->pieces[i + 1],
1433                         sizeof( struct weighted_piece ) * ( newpos ) );
1434                t->pieces[i + newpos] = piece;
1435            }
1436        }
1437    }
1438
1439    assertWeightedPiecesAreSorted( t );
1440    *numgot = got;
1441}
1442
1443bool
1444tr_peerMgrDidPeerRequest( const tr_torrent  * tor,
1445                          const tr_peer     * peer,
1446                          tr_block_index_t    block )
1447{
1448    const Torrent * t = tor->torrentPeers;
1449    return requestListLookup( (Torrent*)t, block, peer ) != NULL;
1450}
1451
1452/* cancel requests that are too old */
1453static void
1454refillUpkeep( int foo UNUSED, short bar UNUSED, void * vmgr )
1455{
1456    time_t now;
1457    time_t too_old;
1458    tr_torrent * tor;
1459    tr_peerMgr * mgr = vmgr;
1460    managerLock( mgr );
1461
1462    now = tr_time( );
1463    too_old = now - REQUEST_TTL_SECS;
1464
1465    tor = NULL;
1466    while(( tor = tr_torrentNext( mgr->session, tor )))
1467    {
1468        Torrent * t = tor->torrentPeers;
1469        const int n = t->requestCount;
1470        if( n > 0 )
1471        {
1472            int keepCount = 0;
1473            int cancelCount = 0;
1474            struct block_request * cancel = tr_new( struct block_request, n );
1475            const struct block_request * it;
1476            const struct block_request * end;
1477
1478            for( it=t->requests, end=it+n; it!=end; ++it )
1479            {
1480                if( ( it->sentAt <= too_old ) && it->peer->msgs && !tr_peerMsgsIsReadingBlock( it->peer->msgs, it->block ) )
1481                    cancel[cancelCount++] = *it;
1482                else
1483                {
1484                    if( it != &t->requests[keepCount] )
1485                        t->requests[keepCount] = *it;
1486                    keepCount++;
1487                }
1488            }
1489
1490            /* prune out the ones we aren't keeping */
1491            t->requestCount = keepCount;
1492
1493            /* send cancel messages for all the "cancel" ones */
1494            for( it=cancel, end=it+cancelCount; it!=end; ++it ) {
1495                if( ( it->peer != NULL ) && ( it->peer->msgs != NULL ) ) {
1496                    tr_historyAdd( &it->peer->cancelsSentToPeer, now, 1 );
1497                    tr_peerMsgsCancel( it->peer->msgs, it->block );
1498                    decrementPendingReqCount( it );
1499                }
1500            }
1501
1502            /* decrement the pending request counts for the timed-out blocks */
1503            for( it=cancel, end=it+cancelCount; it!=end; ++it )
1504                pieceListRemoveRequest( t, it->block );
1505
1506            /* cleanup loop */
1507            tr_free( cancel );
1508        }
1509    }
1510
1511    tr_timerAddMsec( mgr->refillUpkeepTimer, REFILL_UPKEEP_PERIOD_MSEC );
1512    managerUnlock( mgr );
1513}
1514
1515static void
1516addStrike( Torrent * t, tr_peer * peer )
1517{
1518    tordbg( t, "increasing peer %s strike count to %d",
1519            tr_atomAddrStr( peer->atom ), peer->strikes + 1 );
1520
1521    if( ++peer->strikes >= MAX_BAD_PIECES_PER_PEER )
1522    {
1523        struct peer_atom * atom = peer->atom;
1524        atom->flags2 |= MYFLAG_BANNED;
1525        peer->doPurge = 1;
1526        tordbg( t, "banning peer %s", tr_atomAddrStr( atom ) );
1527    }
1528}
1529
1530static void
1531gotBadPiece( Torrent * t, tr_piece_index_t pieceIndex )
1532{
1533    tr_torrent *   tor = t->tor;
1534    const uint32_t byteCount = tr_torPieceCountBytes( tor, pieceIndex );
1535
1536    tor->corruptCur += byteCount;
1537    tor->downloadedCur -= MIN( tor->downloadedCur, byteCount );
1538
1539    tr_announcerAddBytes( tor, TR_ANN_CORRUPT, byteCount );
1540}
1541
1542static void
1543peerSuggestedPiece( Torrent            * t UNUSED,
1544                    tr_peer            * peer UNUSED,
1545                    tr_piece_index_t     pieceIndex UNUSED,
1546                    int                  isFastAllowed UNUSED )
1547{
1548#if 0
1549    assert( t );
1550    assert( peer );
1551    assert( peer->msgs );
1552
1553    /* is this a valid piece? */
1554    if(  pieceIndex >= t->tor->info.pieceCount )
1555        return;
1556
1557    /* don't ask for it if we've already got it */
1558    if( tr_cpPieceIsComplete( t->tor->completion, pieceIndex ) )
1559        return;
1560
1561    /* don't ask for it if they don't have it */
1562    if( !tr_bitfieldHas( peer->have, pieceIndex ) )
1563        return;
1564
1565    /* don't ask for it if we're choked and it's not fast */
1566    if( !isFastAllowed && peer->clientIsChoked )
1567        return;
1568
1569    /* request the blocks that we don't have in this piece */
1570    {
1571        tr_block_index_t b;
1572        tr_block_index_t first;
1573        tr_block_index_t last;
1574        const tr_torrent * tor = t->tor;
1575
1576        tr_torGetPieceBlockRange( t->tor, pieceIndex, &first, &last );
1577
1578        for( b=first; b<=last; ++b )
1579        {
1580            if( !tr_cpBlockIsComplete( tor->completion, b ) )
1581            {
1582                const uint32_t offset = getBlockOffsetInPiece( tor, b );
1583                const uint32_t length = tr_torBlockCountBytes( tor, b );
1584                tr_peerMsgsAddRequest( peer->msgs, pieceIndex, offset, length );
1585                incrementPieceRequests( t, pieceIndex );
1586            }
1587        }
1588    }
1589#endif
1590}
1591
1592static void
1593removeRequestFromTables( Torrent * t, tr_block_index_t block, const tr_peer * peer )
1594{
1595    requestListRemove( t, block, peer );
1596    pieceListRemoveRequest( t, block );
1597}
1598
1599/* peer choked us, or maybe it disconnected.
1600   either way we need to remove all its requests */
1601static void
1602peerDeclinedAllRequests( Torrent * t, const tr_peer * peer )
1603{
1604    int i, n;
1605    tr_block_index_t * blocks = tr_new( tr_block_index_t, t->requestCount );
1606
1607    for( i=n=0; i<t->requestCount; ++i )
1608        if( peer == t->requests[i].peer )
1609            blocks[n++] = t->requests[i].block;
1610
1611    for( i=0; i<n; ++i )
1612        removeRequestFromTables( t, blocks[i], peer );
1613
1614    tr_free( blocks );
1615}
1616
1617static void tr_peerMgrSetBlame( tr_torrent *, tr_piece_index_t, int );
1618
1619static void
1620peerCallbackFunc( tr_peer * peer, const tr_peer_event * e, void * vt )
1621{
1622    Torrent * t = vt;
1623
1624    torrentLock( t );
1625
1626    assert( peer != NULL );
1627
1628    switch( e->eventType )
1629    {
1630        case TR_PEER_PEER_GOT_DATA:
1631        {
1632            const time_t now = tr_time( );
1633            tr_torrent * tor = t->tor;
1634
1635            if( e->wasPieceData )
1636            {
1637                tor->uploadedCur += e->length;
1638                tr_announcerAddBytes( tor, TR_ANN_UP, e->length );
1639                tr_torrentSetActivityDate( tor, now );
1640                tr_torrentSetDirty( tor );
1641            }
1642
1643            /* update the stats */
1644            if( e->wasPieceData )
1645                tr_statsAddUploaded( tor->session, e->length );
1646
1647            /* update our atom */
1648            if( peer->atom && e->wasPieceData )
1649                peer->atom->piece_data_time = now;
1650
1651            break;
1652        }
1653
1654        case TR_PEER_CLIENT_GOT_HAVE:
1655            if( replicationExists( t ) ) {
1656                tr_incrReplicationOfPiece( t, e->pieceIndex );
1657                assertReplicationCountIsExact( t );
1658            }
1659            break;
1660
1661        case TR_PEER_CLIENT_GOT_HAVE_ALL:
1662            if( replicationExists( t ) ) {
1663                tr_incrReplication( t );
1664                assertReplicationCountIsExact( t );
1665            }
1666            break;
1667
1668        case TR_PEER_CLIENT_GOT_HAVE_NONE:
1669            /* noop */
1670            break;
1671
1672        case TR_PEER_CLIENT_GOT_BITFIELD:
1673            assert( e->bitfield != NULL );
1674            if( replicationExists( t ) ) {
1675                tr_incrReplicationFromBitfield( t, e->bitfield );
1676                assertReplicationCountIsExact( t );
1677            }
1678            break;
1679
1680        case TR_PEER_CLIENT_GOT_REJ: {
1681            tr_block_index_t b = _tr_block( t->tor, e->pieceIndex, e->offset );
1682            if( b < t->tor->blockCount )
1683                removeRequestFromTables( t, b, peer );
1684            else
1685                tordbg( t, "Peer %s sent an out-of-range reject message",
1686                           tr_atomAddrStr( peer->atom ) );
1687            break;
1688        }
1689
1690        case TR_PEER_CLIENT_GOT_CHOKE:
1691            peerDeclinedAllRequests( t, peer );
1692            break;
1693
1694        case TR_PEER_CLIENT_GOT_PORT:
1695            if( peer->atom )
1696                peer->atom->port = e->port;
1697            break;
1698
1699        case TR_PEER_CLIENT_GOT_SUGGEST:
1700            peerSuggestedPiece( t, peer, e->pieceIndex, false );
1701            break;
1702
1703        case TR_PEER_CLIENT_GOT_ALLOWED_FAST:
1704            peerSuggestedPiece( t, peer, e->pieceIndex, true );
1705            break;
1706
1707        case TR_PEER_CLIENT_GOT_DATA:
1708        {
1709            const time_t now = tr_time( );
1710            tr_torrent * tor = t->tor;
1711
1712            if( e->wasPieceData )
1713            {
1714                tor->downloadedCur += e->length;
1715                tr_torrentSetActivityDate( tor, now );
1716                tr_torrentSetDirty( tor );
1717            }
1718
1719            /* update the stats */
1720            if( e->wasPieceData )
1721                tr_statsAddDownloaded( tor->session, e->length );
1722
1723            /* update our atom */
1724            if( peer->atom && e->wasPieceData )
1725                peer->atom->piece_data_time = now;
1726
1727            break;
1728        }
1729
1730        case TR_PEER_CLIENT_GOT_BLOCK:
1731        {
1732            tr_torrent * tor = t->tor;
1733            tr_block_index_t block = _tr_block( tor, e->pieceIndex, e->offset );
1734            int i, peerCount;
1735            tr_peer ** peers;
1736            tr_ptrArray peerArr = TR_PTR_ARRAY_INIT;
1737
1738            removeRequestFromTables( t, block, peer );
1739            getBlockRequestPeers( t, block, &peerArr );
1740            peers = (tr_peer **) tr_ptrArrayPeek( &peerArr, &peerCount );
1741
1742            /* remove additional block requests and send cancel to peers */
1743            for( i=0; i<peerCount; i++ ) {
1744                tr_peer * p = peers[i];
1745                assert( p != peer );
1746                if( p->msgs ) {
1747                    tr_historyAdd( &p->cancelsSentToPeer, tr_time( ), 1 );
1748                    tr_peerMsgsCancel( p->msgs, block );
1749                }
1750                removeRequestFromTables( t, block, p );
1751            }
1752
1753            tr_ptrArrayDestruct( &peerArr, false );
1754
1755            tr_historyAdd( &peer->blocksSentToClient, tr_time( ), 1 );
1756
1757            if( tr_cpBlockIsComplete( &tor->completion, block ) )
1758            {
1759                /* we already have this block... */
1760                const uint32_t n = tr_torBlockCountBytes( tor, block );
1761                tor->downloadedCur -= MIN( tor->downloadedCur, n );
1762                tordbg( t, "we have this block already..." );
1763            }
1764            else
1765            {
1766                tr_cpBlockAdd( &tor->completion, block );
1767                pieceListResortPiece( t, pieceListLookup( t, e->pieceIndex ) );
1768                tr_torrentSetDirty( tor );
1769
1770                if( tr_cpPieceIsComplete( &tor->completion, e->pieceIndex ) )
1771                {
1772                    const tr_piece_index_t p = e->pieceIndex;
1773                    const bool ok = tr_torrentCheckPiece( tor, p );
1774
1775                    tordbg( t, "[LAZY] checked just-completed piece %zu", (size_t)p );
1776
1777                    if( !ok )
1778                    {
1779                        tr_torerr( tor, _( "Piece %lu, which was just downloaded, failed its checksum test" ),
1780                                   (unsigned long)p );
1781                    }
1782
1783                    tr_peerMgrSetBlame( tor, p, ok );
1784
1785                    if( !ok )
1786                    {
1787                        gotBadPiece( t, p );
1788                    }
1789                    else
1790                    {
1791                        int i;
1792                        int peerCount;
1793                        tr_peer ** peers;
1794                        tr_file_index_t fileIndex;
1795
1796                        /* only add this to downloadedCur if we got it from a peer --
1797                         * webseeds shouldn't count against our ratio. As one tracker
1798                         * admin put it, "Those pieces are downloaded directly from the
1799                         * content distributor, not the peers, it is the tracker's job
1800                         * to manage the swarms, not the web server and does not fit
1801                         * into the jurisdiction of the tracker." */
1802                        if( peer->msgs != NULL ) {
1803                            const uint32_t n = tr_torPieceCountBytes( tor, p );
1804                            tr_announcerAddBytes( tor, TR_ANN_DOWN, n );
1805                        }
1806
1807                        peerCount = tr_ptrArraySize( &t->peers );
1808                        peers = (tr_peer**) tr_ptrArrayBase( &t->peers );
1809                        for( i=0; i<peerCount; ++i )
1810                            tr_peerMsgsHave( peers[i]->msgs, p );
1811
1812                        for( fileIndex=0; fileIndex<tor->info.fileCount; ++fileIndex ) {
1813                            const tr_file * file = &tor->info.files[fileIndex];
1814                            if( ( file->firstPiece <= p ) && ( p <= file->lastPiece ) ) {
1815                                if( tr_cpFileIsComplete( &tor->completion, fileIndex ) ) {
1816                                    tr_cacheFlushFile( tor->session->cache, tor, fileIndex );
1817                                    tr_torrentFileCompleted( tor, fileIndex );
1818                                }
1819                            }
1820                        }
1821
1822                        pieceListRemovePiece( t, p );
1823                    }
1824                }
1825
1826                t->needsCompletenessCheck = true;
1827            }
1828            break;
1829        }
1830
1831        case TR_PEER_ERROR:
1832            if( ( e->err == ERANGE ) || ( e->err == EMSGSIZE ) || ( e->err == ENOTCONN ) )
1833            {
1834                /* some protocol error from the peer */
1835                peer->doPurge = 1;
1836                tordbg( t, "setting %s doPurge flag because we got an ERANGE, EMSGSIZE, or ENOTCONN error",
1837                        tr_atomAddrStr( peer->atom ) );
1838            }
1839            else
1840            {
1841                tordbg( t, "unhandled error: %s", tr_strerror( e->err ) );
1842            }
1843            break;
1844
1845        default:
1846            assert( 0 );
1847    }
1848
1849    torrentUnlock( t );
1850}
1851
1852static int
1853getDefaultShelfLife( uint8_t from )
1854{
1855    /* in general, peers obtained from firsthand contact
1856     * are better than those from secondhand, etc etc */
1857    switch( from )
1858    {
1859        case TR_PEER_FROM_INCOMING : return 60 * 60 * 6;
1860        case TR_PEER_FROM_LTEP     : return 60 * 60 * 6;
1861        case TR_PEER_FROM_TRACKER  : return 60 * 60 * 3;
1862        case TR_PEER_FROM_DHT      : return 60 * 60 * 3;
1863        case TR_PEER_FROM_PEX      : return 60 * 60 * 2;
1864        case TR_PEER_FROM_RESUME   : return 60 * 60;
1865        case TR_PEER_FROM_LPD      : return 10 * 60;
1866        default                    : return 60 * 60;
1867    }
1868}
1869
1870static void
1871ensureAtomExists( Torrent           * t,
1872                  const tr_address  * addr,
1873                  const tr_port       port,
1874                  const uint8_t       flags,
1875                  const int8_t        seedProbability,
1876                  const uint8_t       from )
1877{
1878    struct peer_atom * a;
1879
1880    assert( tr_address_is_valid( addr ) );
1881    assert( from < TR_PEER_FROM__MAX );
1882
1883    a = getExistingAtom( t, addr );
1884
1885    if( a == NULL )
1886    {
1887        const int jitter = tr_cryptoWeakRandInt( 60*10 );
1888        a = tr_new0( struct peer_atom, 1 );
1889        a->addr = *addr;
1890        a->port = port;
1891        a->flags = flags;
1892        a->fromFirst = from;
1893        a->fromBest = from;
1894        a->shelf_date = tr_time( ) + getDefaultShelfLife( from ) + jitter;
1895        a->blocklisted = -1;
1896        atomSetSeedProbability( a, seedProbability );
1897        tr_ptrArrayInsertSorted( &t->pool, a, compareAtomsByAddress );
1898
1899        tordbg( t, "got a new atom: %s", tr_atomAddrStr( a ) );
1900    }
1901    else
1902    {
1903        if( from < a->fromBest )
1904            a->fromBest = from;
1905
1906        if( a->seedProbability == -1 )
1907            atomSetSeedProbability( a, seedProbability );
1908
1909        a->flags |= flags;
1910    }
1911}
1912
1913static int
1914getMaxPeerCount( const tr_torrent * tor )
1915{
1916    return tor->maxConnectedPeers;
1917}
1918
1919static int
1920getPeerCount( const Torrent * t )
1921{
1922    return tr_ptrArraySize( &t->peers );/* + tr_ptrArraySize( &t->outgoingHandshakes ); */
1923}
1924
1925/* FIXME: this is kind of a mess. */
1926static bool
1927myHandshakeDoneCB( tr_handshake  * handshake,
1928                   tr_peerIo     * io,
1929                   bool            readAnythingFromPeer,
1930                   bool            isConnected,
1931                   const uint8_t * peer_id,
1932                   void          * vmanager )
1933{
1934    bool               ok = isConnected;
1935    bool               success = false;
1936    tr_port            port;
1937    const tr_address * addr;
1938    tr_peerMgr       * manager = vmanager;
1939    Torrent          * t;
1940    tr_handshake     * ours;
1941
1942    assert( io );
1943    assert( tr_isBool( ok ) );
1944
1945    t = tr_peerIoHasTorrentHash( io )
1946        ? getExistingTorrent( manager, tr_peerIoGetTorrentHash( io ) )
1947        : NULL;
1948
1949    if( tr_peerIoIsIncoming ( io ) )
1950        ours = tr_ptrArrayRemoveSorted( &manager->incomingHandshakes,
1951                                        handshake, handshakeCompare );
1952    else if( t )
1953        ours = tr_ptrArrayRemoveSorted( &t->outgoingHandshakes,
1954                                        handshake, handshakeCompare );
1955    else
1956        ours = handshake;
1957
1958    assert( ours );
1959    assert( ours == handshake );
1960
1961    if( t )
1962        torrentLock( t );
1963
1964    addr = tr_peerIoGetAddress( io, &port );
1965
1966    if( !ok || !t || !t->isRunning )
1967    {
1968        if( t )
1969        {
1970            struct peer_atom * atom = getExistingAtom( t, addr );
1971            if( atom )
1972            {
1973                ++atom->numFails;
1974
1975                if( !readAnythingFromPeer )
1976                {
1977                    tordbg( t, "marking peer %s as unreachable... numFails is %d", tr_atomAddrStr( atom ), (int)atom->numFails );
1978                    atom->flags2 |= MYFLAG_UNREACHABLE;
1979                }
1980            }
1981        }
1982    }
1983    else /* looking good */
1984    {
1985        struct peer_atom * atom;
1986
1987        ensureAtomExists( t, addr, port, 0, -1, TR_PEER_FROM_INCOMING );
1988        atom = getExistingAtom( t, addr );
1989        atom->time = tr_time( );
1990        atom->piece_data_time = 0;
1991        atom->lastConnectionAt = tr_time( );
1992
1993        if( !tr_peerIoIsIncoming( io ) )
1994        {
1995            atom->flags |= ADDED_F_CONNECTABLE;
1996            atom->flags2 &= ~MYFLAG_UNREACHABLE;
1997        }
1998
1999        /* In principle, this flag specifies whether the peer groks uTP,
2000           not whether it's currently connected over uTP. */
2001        if( io->utp_socket )
2002            atom->flags |= ADDED_F_UTP_FLAGS;
2003
2004        if( atom->flags2 & MYFLAG_BANNED )
2005        {
2006            tordbg( t, "banned peer %s tried to reconnect",
2007                    tr_atomAddrStr( atom ) );
2008        }
2009        else if( tr_peerIoIsIncoming( io )
2010               && ( getPeerCount( t ) >= getMaxPeerCount( t->tor ) ) )
2011
2012        {
2013        }
2014        else
2015        {
2016            tr_peer * peer = atom->peer;
2017
2018            if( peer ) /* we already have this peer */
2019            {
2020            }
2021            else
2022            {
2023                peer = getPeer( t, atom );
2024                tr_free( peer->client );
2025
2026                if( !peer_id )
2027                    peer->client = NULL;
2028                else {
2029                    char client[128];
2030                    tr_clientForId( client, sizeof( client ), peer_id );
2031                    peer->client = tr_strdup( client );
2032                }
2033
2034                peer->io = tr_handshakeStealIO( handshake ); /* this steals its refcount too, which is
2035                                                                balanced by our unref in peerDelete()  */
2036                tr_peerIoSetParent( peer->io, t->tor->bandwidth );
2037                tr_peerMsgsNew( t->tor, peer, peerCallbackFunc, t );
2038
2039                success = true;
2040            }
2041        }
2042    }
2043
2044    if( t )
2045        torrentUnlock( t );
2046
2047    return success;
2048}
2049
2050void
2051tr_peerMgrAddIncoming( tr_peerMgr * manager,
2052                       tr_address * addr,
2053                       tr_port      port,
2054                       int          socket,
2055                       struct UTPSocket * utp_socket )
2056{
2057    tr_session * session;
2058
2059    managerLock( manager );
2060
2061    assert( tr_isSession( manager->session ) );
2062    session = manager->session;
2063
2064    if( tr_sessionIsAddressBlocked( session, addr ) )
2065    {
2066        tr_dbg( "Banned IP address \"%s\" tried to connect to us", tr_address_to_string( addr ) );
2067        if(socket >= 0)
2068            tr_netClose( session, socket );
2069        else
2070            UTP_Close( utp_socket );
2071    }
2072    else if( getExistingHandshake( &manager->incomingHandshakes, addr ) )
2073    {
2074        if(socket >= 0)
2075            tr_netClose( session, socket );
2076        else
2077            UTP_Close( utp_socket );
2078    }
2079    else /* we don't have a connection to them yet... */
2080    {
2081        tr_peerIo *    io;
2082        tr_handshake * handshake;
2083
2084        io = tr_peerIoNewIncoming( session, session->bandwidth, addr, port, socket, utp_socket );
2085
2086        handshake = tr_handshakeNew( io,
2087                                     session->encryptionMode,
2088                                     myHandshakeDoneCB,
2089                                     manager );
2090
2091        tr_peerIoUnref( io ); /* balanced by the implicit ref in tr_peerIoNewIncoming() */
2092
2093        tr_ptrArrayInsertSorted( &manager->incomingHandshakes, handshake,
2094                                 handshakeCompare );
2095    }
2096
2097    managerUnlock( manager );
2098}
2099
2100void
2101tr_peerMgrAddPex( tr_torrent * tor, uint8_t from,
2102                  const tr_pex * pex, int8_t seedProbability )
2103{
2104    if( tr_isPex( pex ) ) /* safeguard against corrupt data */
2105    {
2106        Torrent * t = tor->torrentPeers;
2107        managerLock( t->manager );
2108
2109        if( !tr_sessionIsAddressBlocked( t->manager->session, &pex->addr ) )
2110            if( tr_address_is_valid_for_peers( &pex->addr, pex->port ) )
2111                ensureAtomExists( t, &pex->addr, pex->port, pex->flags, seedProbability, from );
2112
2113        managerUnlock( t->manager );
2114    }
2115}
2116
2117void
2118tr_peerMgrMarkAllAsSeeds( tr_torrent * tor )
2119{
2120    Torrent * t = tor->torrentPeers;
2121    const int n = tr_ptrArraySize( &t->pool );
2122    struct peer_atom ** it = (struct peer_atom**) tr_ptrArrayBase( &t->pool );
2123    struct peer_atom ** end = it + n;
2124
2125    while( it != end )
2126        atomSetSeed( t, *it++ );
2127}
2128
2129tr_pex *
2130tr_peerMgrCompactToPex( const void *    compact,
2131                        size_t          compactLen,
2132                        const uint8_t * added_f,
2133                        size_t          added_f_len,
2134                        size_t *        pexCount )
2135{
2136    size_t          i;
2137    size_t          n = compactLen / 6;
2138    const uint8_t * walk = compact;
2139    tr_pex *        pex = tr_new0( tr_pex, n );
2140
2141    for( i = 0; i < n; ++i )
2142    {
2143        pex[i].addr.type = TR_AF_INET;
2144        memcpy( &pex[i].addr.addr, walk, 4 ); walk += 4;
2145        memcpy( &pex[i].port, walk, 2 ); walk += 2;
2146        if( added_f && ( n == added_f_len ) )
2147            pex[i].flags = added_f[i];
2148    }
2149
2150    *pexCount = n;
2151    return pex;
2152}
2153
2154tr_pex *
2155tr_peerMgrCompact6ToPex( const void    * compact,
2156                         size_t          compactLen,
2157                         const uint8_t * added_f,
2158                         size_t          added_f_len,
2159                         size_t        * pexCount )
2160{
2161    size_t          i;
2162    size_t          n = compactLen / 18;
2163    const uint8_t * walk = compact;
2164    tr_pex *        pex = tr_new0( tr_pex, n );
2165
2166    for( i = 0; i < n; ++i )
2167    {
2168        pex[i].addr.type = TR_AF_INET6;
2169        memcpy( &pex[i].addr.addr.addr6.s6_addr, walk, 16 ); walk += 16;
2170        memcpy( &pex[i].port, walk, 2 ); walk += 2;
2171        if( added_f && ( n == added_f_len ) )
2172            pex[i].flags = added_f[i];
2173    }
2174
2175    *pexCount = n;
2176    return pex;
2177}
2178
2179tr_pex *
2180tr_peerMgrArrayToPex( const void * array,
2181                      size_t       arrayLen,
2182                      size_t      * pexCount )
2183{
2184    size_t          i;
2185    size_t          n = arrayLen / ( sizeof( tr_address ) + 2 );
2186    /*size_t          n = arrayLen / sizeof( tr_peerArrayElement );*/
2187    const uint8_t * walk = array;
2188    tr_pex        * pex = tr_new0( tr_pex, n );
2189
2190    for( i = 0 ; i < n ; i++ ) {
2191        memcpy( &pex[i].addr, walk, sizeof( tr_address ) );
2192        memcpy( &pex[i].port, walk + sizeof( tr_address ), 2 );
2193        pex[i].flags = 0x00;
2194        walk += sizeof( tr_address ) + 2;
2195    }
2196
2197    *pexCount = n;
2198    return pex;
2199}
2200
2201/**
2202***
2203**/
2204
2205static void
2206tr_peerMgrSetBlame( tr_torrent     * tor,
2207                    tr_piece_index_t pieceIndex,
2208                    int              success )
2209{
2210    if( !success )
2211    {
2212        int        peerCount, i;
2213        Torrent *  t = tor->torrentPeers;
2214        tr_peer ** peers;
2215
2216        assert( torrentIsLocked( t ) );
2217
2218        peers = (tr_peer **) tr_ptrArrayPeek( &t->peers, &peerCount );
2219        for( i = 0; i < peerCount; ++i )
2220        {
2221            tr_peer * peer = peers[i];
2222            if( tr_bitfieldHas( &peer->blame, pieceIndex ) )
2223            {
2224                tordbg( t, "peer %s contributed to corrupt piece (%d); now has %d strikes",
2225                        tr_atomAddrStr( peer->atom ),
2226                        pieceIndex, (int)peer->strikes + 1 );
2227                addStrike( t, peer );
2228            }
2229        }
2230    }
2231}
2232
2233int
2234tr_pexCompare( const void * va, const void * vb )
2235{
2236    const tr_pex * a = va;
2237    const tr_pex * b = vb;
2238    int i;
2239
2240    assert( tr_isPex( a ) );
2241    assert( tr_isPex( b ) );
2242
2243    if(( i = tr_address_compare( &a->addr, &b->addr )))
2244        return i;
2245
2246    if( a->port != b->port )
2247        return a->port < b->port ? -1 : 1;
2248
2249    return 0;
2250}
2251
2252#if 0
2253static int
2254peerPrefersCrypto( const tr_peer * peer )
2255{
2256    if( peer->encryption_preference == ENCRYPTION_PREFERENCE_YES )
2257        return true;
2258
2259    if( peer->encryption_preference == ENCRYPTION_PREFERENCE_NO )
2260        return false;
2261
2262    return tr_peerIoIsEncrypted( peer->io );
2263}
2264#endif
2265
2266/* better goes first */
2267static int
2268compareAtomsByUsefulness( const void * va, const void *vb )
2269{
2270    const struct peer_atom * a = * (const struct peer_atom**) va;
2271    const struct peer_atom * b = * (const struct peer_atom**) vb;
2272
2273    assert( tr_isAtom( a ) );
2274    assert( tr_isAtom( b ) );
2275
2276    if( a->piece_data_time != b->piece_data_time )
2277        return a->piece_data_time > b->piece_data_time ? -1 : 1;
2278    if( a->fromBest != b->fromBest )
2279        return a->fromBest < b->fromBest ? -1 : 1;
2280    if( a->numFails != b->numFails )
2281        return a->numFails < b->numFails ? -1 : 1;
2282
2283    return 0;
2284}
2285
2286int
2287tr_peerMgrGetPeers( tr_torrent   * tor,
2288                    tr_pex      ** setme_pex,
2289                    uint8_t        af,
2290                    uint8_t        list_mode,
2291                    int            maxCount )
2292{
2293    int i;
2294    int n;
2295    int count = 0;
2296    int atomCount = 0;
2297    const Torrent * t = tor->torrentPeers;
2298    struct peer_atom ** atoms = NULL;
2299    tr_pex * pex;
2300    tr_pex * walk;
2301
2302    assert( tr_isTorrent( tor ) );
2303    assert( setme_pex != NULL );
2304    assert( af==TR_AF_INET || af==TR_AF_INET6 );
2305    assert( list_mode==TR_PEERS_CONNECTED || list_mode==TR_PEERS_ALL );
2306
2307    managerLock( t->manager );
2308
2309    /**
2310    ***  build a list of atoms
2311    **/
2312
2313    if( list_mode == TR_PEERS_CONNECTED ) /* connected peers only */
2314    {
2315        int i;
2316        const tr_peer ** peers = (const tr_peer **) tr_ptrArrayBase( &t->peers );
2317        atomCount = tr_ptrArraySize( &t->peers );
2318        atoms = tr_new( struct peer_atom *, atomCount );
2319        for( i=0; i<atomCount; ++i )
2320            atoms[i] = peers[i]->atom;
2321    }
2322    else /* TR_PEERS_ALL */
2323    {
2324        const struct peer_atom ** atomsBase = (const struct peer_atom**) tr_ptrArrayBase( &t->pool );
2325        atomCount = tr_ptrArraySize( &t->pool );
2326        atoms = tr_memdup( atomsBase, atomCount * sizeof( struct peer_atom * ) );
2327    }
2328
2329    qsort( atoms, atomCount, sizeof( struct peer_atom * ), compareAtomsByUsefulness );
2330
2331    /**
2332    ***  add the first N of them into our return list
2333    **/
2334
2335    n = MIN( atomCount, maxCount );
2336    pex = walk = tr_new0( tr_pex, n );
2337
2338    for( i=0; i<atomCount && count<n; ++i )
2339    {
2340        const struct peer_atom * atom = atoms[i];
2341        if( atom->addr.type == af )
2342        {
2343            assert( tr_address_is_valid( &atom->addr ) );
2344            walk->addr = atom->addr;
2345            walk->port = atom->port;
2346            walk->flags = atom->flags;
2347            ++count;
2348            ++walk;
2349        }
2350    }
2351
2352    qsort( pex, count, sizeof( tr_pex ), tr_pexCompare );
2353
2354    assert( ( walk - pex ) == count );
2355    *setme_pex = pex;
2356
2357    /* cleanup */
2358    tr_free( atoms );
2359    managerUnlock( t->manager );
2360    return count;
2361}
2362
2363static void atomPulse      ( int, short, void * );
2364static void bandwidthPulse ( int, short, void * );
2365static void rechokePulse   ( int, short, void * );
2366static void reconnectPulse ( int, short, void * );
2367
2368static struct event *
2369createTimer( tr_session * session, int msec, void (*callback)(int, short, void *), void * cbdata )
2370{
2371    struct event * timer = evtimer_new( session->event_base, callback, cbdata );
2372    tr_timerAddMsec( timer, msec );
2373    return timer;
2374}
2375
2376static void
2377ensureMgrTimersExist( struct tr_peerMgr * m )
2378{
2379    if( m->atomTimer == NULL )
2380        m->atomTimer = createTimer( m->session, ATOM_PERIOD_MSEC, atomPulse, m );
2381
2382    if( m->bandwidthTimer == NULL )
2383        m->bandwidthTimer = createTimer( m->session, BANDWIDTH_PERIOD_MSEC, bandwidthPulse, m );
2384
2385    if( m->rechokeTimer == NULL )
2386        m->rechokeTimer = createTimer( m->session, RECHOKE_PERIOD_MSEC, rechokePulse, m );
2387
2388    if( m->refillUpkeepTimer == NULL )
2389        m->refillUpkeepTimer = createTimer( m->session, REFILL_UPKEEP_PERIOD_MSEC, refillUpkeep, m );
2390}
2391
2392void
2393tr_peerMgrStartTorrent( tr_torrent * tor )
2394{
2395    Torrent * t = tor->torrentPeers;
2396
2397    assert( tr_isTorrent( tor ) );
2398    assert( tr_torrentIsLocked( tor ) );
2399
2400    ensureMgrTimersExist( t->manager );
2401
2402    t->isRunning = true;
2403    t->maxPeers = t->tor->maxConnectedPeers;
2404    t->pieceSortState = PIECES_UNSORTED;
2405
2406    rechokePulse( 0, 0, t->manager );
2407}
2408
2409static void
2410stopTorrent( Torrent * t )
2411{
2412    tr_peer * peer;
2413
2414    t->isRunning = false;
2415
2416    replicationFree( t );
2417    invalidatePieceSorting( t );
2418
2419    /* disconnect the peers. */
2420    while(( peer = tr_ptrArrayPop( &t->peers )))
2421        peerDelete( t, peer );
2422
2423    /* disconnect the handshakes. handshakeAbort calls handshakeDoneCB(),
2424     * which removes the handshake from t->outgoingHandshakes... */
2425    while( !tr_ptrArrayEmpty( &t->outgoingHandshakes ) )
2426        tr_handshakeAbort( tr_ptrArrayNth( &t->outgoingHandshakes, 0 ) );
2427}
2428
2429void
2430tr_peerMgrStopTorrent( tr_torrent * tor )
2431{
2432    assert( tr_isTorrent( tor ) );
2433    assert( tr_torrentIsLocked( tor ) );
2434
2435    stopTorrent( tor->torrentPeers );
2436}
2437
2438void
2439tr_peerMgrAddTorrent( tr_peerMgr * manager, tr_torrent * tor )
2440{
2441    assert( tr_isTorrent( tor ) );
2442    assert( tr_torrentIsLocked( tor ) );
2443    assert( tor->torrentPeers == NULL );
2444
2445    tor->torrentPeers = torrentNew( manager, tor );
2446}
2447
2448void
2449tr_peerMgrRemoveTorrent( tr_torrent * tor )
2450{
2451    assert( tr_isTorrent( tor ) );
2452    assert( tr_torrentIsLocked( tor ) );
2453
2454    stopTorrent( tor->torrentPeers );
2455    torrentFree( tor->torrentPeers );
2456}
2457
2458void
2459tr_peerUpdateProgress( tr_torrent * tor, tr_peer * peer )
2460{
2461    const tr_bitfield * have = &peer->have;
2462
2463    if( tr_bitfieldHasAll( have ) )
2464    {
2465        peer->progress = 1.0;
2466    }
2467    else if( tr_bitfieldHasNone( have ) )
2468    {
2469        peer->progress = 0.0;
2470    }
2471    else
2472    {
2473        const float true_count = tr_bitfieldCountTrueBits( have );
2474
2475        if( tr_torrentHasMetadata( tor ) )
2476            peer->progress = true_count / tor->info.pieceCount;
2477        else /* without pieceCount, this result is only a best guess... */
2478            peer->progress = true_count / ( have->bit_count + 1 );
2479    }
2480
2481    if( peer->atom && ( peer->progress >= 1.0 ) )
2482        atomSetSeed( tor->torrentPeers, peer->atom );
2483}
2484
2485void
2486tr_peerMgrOnTorrentGotMetainfo( tr_torrent * tor )
2487{
2488    int i;
2489    const int peerCount = tr_ptrArraySize( &tor->torrentPeers->peers );
2490    tr_peer ** peers = (tr_peer**) tr_ptrArrayBase( &tor->torrentPeers->peers );
2491
2492    /* some peer_msgs' progress fields may not be accurate if we
2493       didn't have the metadata before now... so refresh them all... */
2494    for( i=0; i<peerCount; ++i )
2495        tr_peerUpdateProgress( tor, peers[i] );
2496}
2497
2498void
2499tr_peerMgrTorrentAvailability( const tr_torrent * tor, int8_t * tab, unsigned int tabCount )
2500{
2501    assert( tr_isTorrent( tor ) );
2502    assert( torrentIsLocked( tor->torrentPeers ) );
2503    assert( tab != NULL );
2504    assert( tabCount > 0 );
2505
2506    memset( tab, 0, tabCount );
2507
2508    if( tr_torrentHasMetadata( tor ) )
2509    {
2510        tr_piece_index_t i;
2511        const int peerCount = tr_ptrArraySize( &tor->torrentPeers->peers );
2512        const tr_peer ** peers = (const tr_peer**) tr_ptrArrayBase( &tor->torrentPeers->peers );
2513        const float interval = tor->info.pieceCount / (float)tabCount;
2514        const bool isSeed = tr_cpGetStatus( &tor->completion ) == TR_SEED;
2515
2516        for( i=0; i<tabCount; ++i )
2517        {
2518            const int piece = i * interval;
2519
2520            if( isSeed || tr_cpPieceIsComplete( &tor->completion, piece ) )
2521                tab[i] = -1;
2522            else if( peerCount ) {
2523                int j;
2524                for( j=0; j<peerCount; ++j )
2525                    if( tr_bitfieldHas( &peers[j]->have, piece ) )
2526                        ++tab[i];
2527            }
2528        }
2529    }
2530}
2531
2532static bool
2533peerIsSeed( const tr_peer * peer )
2534{
2535    if( peer->progress >= 1.0 )
2536        return true;
2537
2538    if( peer->atom && atomIsSeed( peer->atom ) )
2539        return true;
2540
2541    return false;
2542}
2543
2544/* count how many pieces we want that connected peers have */
2545uint64_t
2546tr_peerMgrGetDesiredAvailable( const tr_torrent * tor )
2547{
2548    size_t i;
2549    size_t n;
2550    uint64_t desiredAvailable;
2551    const Torrent * t = tor->torrentPeers;
2552
2553    /* common shortcuts... */
2554
2555    if( tr_torrentIsSeed( t->tor ) )
2556        return 0;
2557
2558    if( !tr_torrentHasMetadata( tor ) )
2559        return 0;
2560
2561    n = tr_ptrArraySize( &t->peers );
2562    if( n == 0 )
2563        return 0;
2564    else {
2565        const tr_peer ** peers = (const tr_peer**) tr_ptrArrayBase( &t->peers );
2566        for( i=0; i<n; ++i )
2567            if( peers[i]->atom && atomIsSeed( peers[i]->atom ) )
2568                return tr_cpLeftUntilDone( &tor->completion );
2569    }
2570
2571    if( !t->pieceReplication || !t->pieceReplicationSize )
2572        return 0;
2573
2574    /* do it the hard way */
2575
2576    desiredAvailable = 0;
2577    for( i=0, n=tor->info.pieceCount; i<n; ++i )
2578    {
2579        if( tor->info.pieces[i].dnd )
2580            continue;
2581        if( t->pieceReplicationSize >= i )
2582            continue;
2583        if( t->pieceReplication[i] == 0 )
2584            continue;
2585
2586        desiredAvailable += tr_cpMissingBytesInPiece( &t->tor->completion, i );
2587    }
2588
2589    return desiredAvailable;
2590}
2591
2592void
2593tr_peerMgrTorrentStats( tr_torrent  * tor,
2594                        int         * setmePeersConnected,
2595                        int         * setmeWebseedsSendingToUs,
2596                        int         * setmePeersSendingToUs,
2597                        int         * setmePeersGettingFromUs,
2598                        int         * setmePeersFrom )
2599{
2600    int i, size;
2601    const Torrent * t = tor->torrentPeers;
2602    const tr_peer ** peers;
2603
2604    assert( tr_torrentIsLocked( tor ) );
2605
2606    peers = (const tr_peer **) tr_ptrArrayBase( &t->peers );
2607    size = tr_ptrArraySize( &t->peers );
2608
2609    *setmePeersConnected       = 0;
2610    *setmePeersGettingFromUs   = 0;
2611    *setmePeersSendingToUs     = 0;
2612    *setmeWebseedsSendingToUs  = 0;
2613
2614    for( i=0; i<TR_PEER_FROM__MAX; ++i )
2615        setmePeersFrom[i] = 0;
2616
2617    for( i=0; i<size; ++i )
2618    {
2619        const tr_peer * peer = peers[i];
2620        const struct peer_atom * atom = peer->atom;
2621
2622        if( peer->io == NULL ) /* not connected */
2623            continue;
2624
2625        ++*setmePeersConnected;
2626
2627        ++setmePeersFrom[atom->fromFirst];
2628
2629        if( clientIsDownloadingFrom( tor, peer ) )
2630            ++*setmePeersSendingToUs;
2631
2632        if( clientIsUploadingTo( peer ) )
2633            ++*setmePeersGettingFromUs;
2634    }
2635
2636    *setmeWebseedsSendingToUs = countActiveWebseeds( t );
2637}
2638
2639double*
2640tr_peerMgrWebSpeeds_KBps( const tr_torrent * tor )
2641{
2642    int i;
2643    const Torrent * t = tor->torrentPeers;
2644    const int webseedCount = tr_ptrArraySize( &t->webseeds );
2645    const tr_webseed ** webseeds = (const tr_webseed**) tr_ptrArrayBase( &t->webseeds );
2646    const uint64_t now = tr_time_msec( );
2647    double * ret = tr_new0( double, webseedCount );
2648
2649    assert( tr_isTorrent( tor ) );
2650    assert( tr_torrentIsLocked( tor ) );
2651    assert( t->manager != NULL );
2652    assert( webseedCount == tor->info.webseedCount );
2653
2654    for( i=0; i<webseedCount; ++i ) {
2655        int Bps;
2656        if( tr_webseedGetSpeed_Bps( webseeds[i], now, &Bps ) )
2657            ret[i] = Bps / (double)tr_speed_K;
2658        else
2659            ret[i] = -1.0;
2660    }
2661
2662    return ret;
2663}
2664
2665int
2666tr_peerGetPieceSpeed_Bps( const tr_peer * peer, uint64_t now, tr_direction direction )
2667{
2668    return peer->io ? tr_peerIoGetPieceSpeed_Bps( peer->io, now, direction ) : 0.0;
2669}
2670
2671struct tr_peer_stat *
2672tr_peerMgrPeerStats( const tr_torrent * tor, int * setmeCount )
2673{
2674    int i;
2675    const Torrent * t = tor->torrentPeers;
2676    const int size = tr_ptrArraySize( &t->peers );
2677    const tr_peer ** peers = (const tr_peer**) tr_ptrArrayBase( &t->peers );
2678    const uint64_t now_msec = tr_time_msec( );
2679    const time_t now = tr_time();
2680    tr_peer_stat * ret = tr_new0( tr_peer_stat, size );
2681
2682    assert( tr_isTorrent( tor ) );
2683    assert( tr_torrentIsLocked( tor ) );
2684    assert( t->manager );
2685
2686    for( i=0; i<size; ++i )
2687    {
2688        char *                   pch;
2689        const tr_peer *          peer = peers[i];
2690        const struct peer_atom * atom = peer->atom;
2691        tr_peer_stat *           stat = ret + i;
2692
2693        tr_address_to_string_with_buf( &atom->addr, stat->addr, sizeof( stat->addr ) );
2694        tr_strlcpy( stat->client, ( peer->client ? peer->client : "" ),
2695                   sizeof( stat->client ) );
2696        stat->port                = ntohs( peer->atom->port );
2697        stat->from                = atom->fromFirst;
2698        stat->progress            = peer->progress;
2699        stat->isUTP               = peer->io->utp_socket != NULL;
2700        stat->isEncrypted         = tr_peerIoIsEncrypted( peer->io ) ? 1 : 0;
2701        stat->rateToPeer_KBps     = toSpeedKBps( tr_peerGetPieceSpeed_Bps( peer, now_msec, TR_CLIENT_TO_PEER ) );
2702        stat->rateToClient_KBps   = toSpeedKBps( tr_peerGetPieceSpeed_Bps( peer, now_msec, TR_PEER_TO_CLIENT ) );
2703        stat->peerIsChoked        = peer->peerIsChoked;
2704        stat->peerIsInterested    = peer->peerIsInterested;
2705        stat->clientIsChoked      = peer->clientIsChoked;
2706        stat->clientIsInterested  = peer->clientIsInterested;
2707        stat->isIncoming          = tr_peerIoIsIncoming( peer->io );
2708        stat->isDownloadingFrom   = clientIsDownloadingFrom( tor, peer );
2709        stat->isUploadingTo       = clientIsUploadingTo( peer );
2710        stat->isSeed              = peerIsSeed( peer );
2711
2712        stat->blocksToPeer        = tr_historyGet( &peer->blocksSentToPeer,    now, CANCEL_HISTORY_SEC );
2713        stat->blocksToClient      = tr_historyGet( &peer->blocksSentToClient,  now, CANCEL_HISTORY_SEC );
2714        stat->cancelsToPeer       = tr_historyGet( &peer->cancelsSentToPeer,   now, CANCEL_HISTORY_SEC );
2715        stat->cancelsToClient     = tr_historyGet( &peer->cancelsSentToClient, now, CANCEL_HISTORY_SEC );
2716
2717        stat->pendingReqsToPeer   = peer->pendingReqsToPeer;
2718        stat->pendingReqsToClient = peer->pendingReqsToClient;
2719
2720        pch = stat->flagStr;
2721        if( stat->isUTP ) *pch++ = 'T';
2722        if( t->optimistic == peer ) *pch++ = 'O';
2723        if( stat->isDownloadingFrom ) *pch++ = 'D';
2724        else if( stat->clientIsInterested ) *pch++ = 'd';
2725        if( stat->isUploadingTo ) *pch++ = 'U';
2726        else if( stat->peerIsInterested ) *pch++ = 'u';
2727        if( !stat->clientIsChoked && !stat->clientIsInterested ) *pch++ = 'K';
2728        if( !stat->peerIsChoked && !stat->peerIsInterested ) *pch++ = '?';
2729        if( stat->isEncrypted ) *pch++ = 'E';
2730        if( stat->from == TR_PEER_FROM_DHT ) *pch++ = 'H';
2731        else if( stat->from == TR_PEER_FROM_PEX ) *pch++ = 'X';
2732        if( stat->isIncoming ) *pch++ = 'I';
2733        *pch = '\0';
2734    }
2735
2736    *setmeCount = size;
2737
2738    return ret;
2739}
2740
2741/**
2742***
2743**/
2744
2745void
2746tr_peerMgrClearInterest( tr_torrent * tor )
2747{
2748    int i;
2749    Torrent * t = tor->torrentPeers;
2750    const int peerCount = tr_ptrArraySize( &t->peers );
2751
2752    assert( tr_isTorrent( tor ) );
2753    assert( tr_torrentIsLocked( tor ) );
2754
2755    for( i=0; i<peerCount; ++i )
2756    {
2757        const tr_peer * peer = tr_ptrArrayNth( &t->peers, i );
2758        tr_peerMsgsSetInterested( peer->msgs, false );
2759    }
2760}
2761
2762/* do we still want this piece and does the peer have it? */
2763static bool
2764isPieceInteresting( const tr_torrent * tor, const tr_peer * peer, tr_piece_index_t index )
2765{
2766    return ( !tor->info.pieces[index].dnd ) /* we want it */
2767        && ( !tr_cpPieceIsComplete( &tor->completion, index ) )  /* we don't have it */
2768        && ( tr_bitfieldHas( &peer->have, index ) ); /* peer has it */
2769}
2770
2771/* does this peer have any pieces that we want? */
2772static bool
2773isPeerInteresting( const tr_torrent * tor, const tr_peer * peer )
2774{
2775    tr_piece_index_t i, n;
2776
2777    if ( tr_torrentIsSeed( tor ) )
2778        return false;
2779
2780    if( !tr_torrentIsPieceTransferAllowed( tor, TR_PEER_TO_CLIENT ) )
2781        return false;
2782
2783    for( i=0, n=tor->info.pieceCount; i<n; ++i )
2784        if( isPieceInteresting( tor, peer, i ) )
2785            return true;
2786
2787    return false;
2788}
2789
2790/* determines who we send "interested" messages to */
2791static void
2792rechokeDownloads( Torrent * t )
2793{
2794    int i;
2795    const time_t now = tr_time( );
2796    const int MIN_INTERESTING_PEERS = 5;
2797    const int peerCount = tr_ptrArraySize( &t->peers );
2798    int maxPeers;
2799
2800    int badCount         = 0;
2801    int goodCount        = 0;
2802    int untestedCount    = 0;
2803    tr_peer ** bad       = tr_new( tr_peer*, peerCount );
2804    tr_peer ** good      = tr_new( tr_peer*, peerCount );
2805    tr_peer ** untested  = tr_new( tr_peer*, peerCount );
2806
2807    /* decide how many peers to be interested in */
2808    {
2809        int blocks = 0;
2810        int cancels = 0;
2811        time_t timeSinceCancel;
2812
2813        /* Count up how many blocks & cancels each peer has.
2814         *
2815         * There are two situations where we send out cancels --
2816         *
2817         * 1. We've got unresponsive peers, which is handled by deciding
2818         *    -which- peers to be interested in.
2819         *
2820         * 2. We've hit our bandwidth cap, which is handled by deciding
2821         *    -how many- peers to be interested in.
2822         *
2823         * We're working on 2. here, so we need to ignore unresponsive
2824         * peers in our calculations lest they confuse Transmission into
2825         * thinking it's hit its bandwidth cap.
2826         */
2827        for( i=0; i<peerCount; ++i )
2828        {
2829            const tr_peer * peer = tr_ptrArrayNth( &t->peers, i );
2830            const int b = tr_historyGet( &peer->blocksSentToClient, now, CANCEL_HISTORY_SEC );
2831            const int c = tr_historyGet( &peer->cancelsSentToPeer, now, CANCEL_HISTORY_SEC );
2832
2833            if( b == 0 ) /* ignore unresponsive peers, as described above */
2834                continue;
2835
2836            blocks += b;
2837            cancels += c;
2838        }
2839
2840        if( cancels > 0 )
2841        {
2842            /* cancelRate: of the block requests we've recently made, the percentage we cancelled.
2843             * higher values indicate more congestion. */
2844            const double cancelRate = cancels / (double)(cancels + blocks);
2845            const double mult = 1 - MIN( cancelRate, 0.5 );
2846            maxPeers = t->interestedCount * mult;
2847            tordbg( t, "cancel rate is %.3f -- reducing the "
2848                       "number of peers we're interested in by %.0f percent",
2849                       cancelRate, mult * 100 );
2850            t->lastCancel = now;
2851        }
2852
2853        timeSinceCancel = now - t->lastCancel;
2854        if( timeSinceCancel )
2855        {
2856            const int maxIncrease = 15;
2857            const time_t maxHistory = 2 * CANCEL_HISTORY_SEC;
2858            const double mult = MIN( timeSinceCancel, maxHistory ) / (double) maxHistory;
2859            const int inc = maxIncrease * mult;
2860            maxPeers = t->maxPeers + inc;
2861            tordbg( t, "time since last cancel is %li -- increasing the "
2862                       "number of peers we're interested in by %d",
2863                       timeSinceCancel, inc );
2864        }
2865    }
2866
2867    /* don't let the previous section's number tweaking go too far... */
2868    if( maxPeers < MIN_INTERESTING_PEERS )
2869        maxPeers = MIN_INTERESTING_PEERS;
2870    if( maxPeers > t->tor->maxConnectedPeers )
2871        maxPeers = t->tor->maxConnectedPeers;
2872
2873    t->maxPeers = maxPeers;
2874
2875    /* separate the peers into "good" (ones with a low cancel-to-block ratio),
2876     * untested peers, and "bad" (ones with a high cancel-to-block ratio).
2877     * That's the order in which we'll choose who to show interest in */
2878    {
2879        /* Randomize the peer array so the peers in the three groups will be unsorted... */
2880        int n = peerCount;
2881        tr_peer ** peers = tr_memdup( tr_ptrArrayBase( &t->peers ), n * sizeof( tr_peer * ) );
2882
2883        while( n > 0 )
2884        {
2885            const int i = tr_cryptoWeakRandInt( n );
2886            tr_peer * peer = tr_ptrArrayNth( &t->peers, i );
2887
2888            if( !isPeerInteresting( t->tor, peer ) )
2889            {
2890                tr_peerMsgsSetInterested( peer->msgs, false );
2891            }
2892            else
2893            {
2894                const int blocks = tr_historyGet( &peer->blocksSentToClient, now, CANCEL_HISTORY_SEC );
2895                const int cancels = tr_historyGet( &peer->cancelsSentToPeer, now, CANCEL_HISTORY_SEC );
2896
2897                if( !blocks && !cancels )
2898                    untested[untestedCount++] = peer;
2899                else if( !cancels )
2900                    good[goodCount++] = peer;
2901                else if( !blocks )
2902                    bad[badCount++] = peer;
2903                else if( ( cancels * 10 ) < blocks )
2904                    good[goodCount++] = peer;
2905                else
2906                    bad[badCount++] = peer;
2907            }
2908
2909            tr_removeElementFromArray( peers, i, sizeof(tr_peer*), n-- );
2910        }
2911
2912        tr_free( peers );
2913    }
2914
2915    t->interestedCount = 0;
2916
2917    /* We've decided (1) how many peers to be interested in,
2918     * and (2) which peers are the best candidates,
2919     * Now it's time to update our `interest' flags. */
2920    for( i=0; i<goodCount; ++i ) {
2921        const bool b = t->interestedCount < maxPeers;
2922        tr_peerMsgsSetInterested( good[i]->msgs, b );
2923        if( b )
2924            ++t->interestedCount;
2925    }
2926    for( i=0; i<untestedCount; ++i ) {
2927        const bool b = t->interestedCount < maxPeers;
2928        tr_peerMsgsSetInterested( untested[i]->msgs, b );
2929        if( b )
2930            ++t->interestedCount;
2931    }
2932    for( i=0; i<badCount; ++i ) {
2933        const bool b = t->interestedCount < maxPeers;
2934        tr_peerMsgsSetInterested( bad[i]->msgs, b );
2935        if( b )
2936            ++t->interestedCount;
2937    }
2938
2939/*fprintf( stderr, "num interested: %d\n", t->interestedCount );*/
2940
2941    /* cleanup */
2942    tr_free( untested );
2943    tr_free( good );
2944    tr_free( bad );
2945}
2946
2947/**
2948***
2949**/
2950
2951struct ChokeData
2952{
2953    bool            isInterested;
2954    bool            wasChoked;
2955    bool            isChoked;
2956    int             rate;
2957    int             salt;
2958    tr_peer *       peer;
2959};
2960
2961static int
2962compareChoke( const void * va, const void * vb )
2963{
2964    const struct ChokeData * a = va;
2965    const struct ChokeData * b = vb;
2966
2967    if( a->rate != b->rate ) /* prefer higher overall speeds */
2968        return a->rate > b->rate ? -1 : 1;
2969
2970    if( a->wasChoked != b->wasChoked ) /* prefer unchoked */
2971        return a->wasChoked ? 1 : -1;
2972
2973    if( a->salt != b->salt ) /* random order */
2974        return a->salt - b->salt;
2975
2976    return 0;
2977}
2978
2979/* is this a new connection? */
2980static int
2981isNew( const tr_peer * peer )
2982{
2983    return peer && peer->io && tr_peerIoGetAge( peer->io ) < 45;
2984}
2985
2986/* get a rate for deciding which peers to choke and unchoke. */
2987static int
2988getRate( const tr_torrent * tor, struct peer_atom * atom, uint64_t now )
2989{
2990    int Bps;
2991
2992    if( tr_torrentIsSeed( tor ) )
2993        Bps = tr_peerGetPieceSpeed_Bps( atom->peer, now, TR_CLIENT_TO_PEER );
2994
2995    /* downloading a private torrent... take upload speed into account
2996     * because there may only be a small window of opportunity to share */
2997    else if( tr_torrentIsPrivate( tor ) )
2998        Bps = tr_peerGetPieceSpeed_Bps( atom->peer, now, TR_PEER_TO_CLIENT )
2999            + tr_peerGetPieceSpeed_Bps( atom->peer, now, TR_CLIENT_TO_PEER );
3000
3001    /* downloading a public torrent */
3002    else
3003        Bps = tr_peerGetPieceSpeed_Bps( atom->peer, now, TR_PEER_TO_CLIENT );
3004
3005    /* convert it to bytes per second */
3006    return Bps;
3007}
3008
3009static inline bool
3010isBandwidthMaxedOut( const tr_bandwidth * b,
3011                     const uint64_t now_msec, tr_direction dir )
3012{
3013    if( !tr_bandwidthIsLimited( b, dir ) )
3014        return false;
3015    else {
3016        const int got = tr_bandwidthGetPieceSpeed_Bps( b, now_msec, dir );
3017        const int want = tr_bandwidthGetDesiredSpeed_Bps( b, dir );
3018        return got >= want;
3019    }
3020}
3021
3022static void
3023rechokeUploads( Torrent * t, const uint64_t now )
3024{
3025    int i, size, unchokedInterested;
3026    const int peerCount = tr_ptrArraySize( &t->peers );
3027    tr_peer ** peers = (tr_peer**) tr_ptrArrayBase( &t->peers );
3028    struct ChokeData * choke = tr_new0( struct ChokeData, peerCount );
3029    const tr_session * session = t->manager->session;
3030    const int chokeAll = !tr_torrentIsPieceTransferAllowed( t->tor, TR_CLIENT_TO_PEER );
3031    const bool isMaxedOut = isBandwidthMaxedOut( t->tor->bandwidth, now, TR_UP );
3032
3033    assert( torrentIsLocked( t ) );
3034
3035    /* an optimistic unchoke peer's "optimistic"
3036     * state lasts for N calls to rechokeUploads(). */
3037    if( t->optimisticUnchokeTimeScaler > 0 )
3038        t->optimisticUnchokeTimeScaler--;
3039    else
3040        t->optimistic = NULL;
3041
3042    /* sort the peers by preference and rate */
3043    for( i = 0, size = 0; i < peerCount; ++i )
3044    {
3045        tr_peer * peer = peers[i];
3046        struct peer_atom * atom = peer->atom;
3047
3048        if( peerIsSeed( peer ) ) /* choke seeds and partial seeds */
3049        {
3050            tr_peerMsgsSetChoke( peer->msgs, true );
3051        }
3052        else if( chokeAll ) /* choke everyone if we're not uploading */
3053        {
3054            tr_peerMsgsSetChoke( peer->msgs, true );
3055        }
3056        else if( peer != t->optimistic )
3057        {
3058            struct ChokeData * n = &choke[size++];
3059            n->peer         = peer;
3060            n->isInterested = peer->peerIsInterested;
3061            n->wasChoked    = peer->peerIsChoked;
3062            n->rate         = getRate( t->tor, atom, now );
3063            n->salt         = tr_cryptoWeakRandInt( INT_MAX );
3064            n->isChoked     = true;
3065        }
3066    }
3067
3068    qsort( choke, size, sizeof( struct ChokeData ), compareChoke );
3069
3070    /**
3071     * Reciprocation and number of uploads capping is managed by unchoking
3072     * the N peers which have the best upload rate and are interested.
3073     * This maximizes the client's download rate. These N peers are
3074     * referred to as downloaders, because they are interested in downloading
3075     * from the client.
3076     *
3077     * Peers which have a better upload rate (as compared to the downloaders)
3078     * but aren't interested get unchoked. If they become interested, the
3079     * downloader with the worst upload rate gets choked. If a client has
3080     * a complete file, it uses its upload rate rather than its download
3081     * rate to decide which peers to unchoke.
3082     *
3083     * If our bandwidth is maxed out, don't unchoke any more peers.
3084     */
3085    unchokedInterested = 0;
3086    for( i=0; i<size && unchokedInterested<session->uploadSlotsPerTorrent; ++i ) {
3087        choke[i].isChoked = isMaxedOut ? choke[i].wasChoked : false;
3088        if( choke[i].isInterested )
3089            ++unchokedInterested;
3090    }
3091
3092    /* optimistic unchoke */
3093    if( !t->optimistic && !isMaxedOut && (i<size) )
3094    {
3095        int n;
3096        struct ChokeData * c;
3097        tr_ptrArray randPool = TR_PTR_ARRAY_INIT;
3098
3099        for( ; i<size; ++i )
3100        {
3101            if( choke[i].isInterested )
3102            {
3103                const tr_peer * peer = choke[i].peer;
3104                int x = 1, y;
3105                if( isNew( peer ) ) x *= 3;
3106                for( y=0; y<x; ++y )
3107                    tr_ptrArrayAppend( &randPool, &choke[i] );
3108            }
3109        }
3110
3111        if(( n = tr_ptrArraySize( &randPool )))
3112        {
3113            c = tr_ptrArrayNth( &randPool, tr_cryptoWeakRandInt( n ));
3114            c->isChoked = false;
3115            t->optimistic = c->peer;
3116            t->optimisticUnchokeTimeScaler = OPTIMISTIC_UNCHOKE_MULTIPLIER;
3117        }
3118
3119        tr_ptrArrayDestruct( &randPool, NULL );
3120    }
3121
3122    for( i=0; i<size; ++i )
3123        tr_peerMsgsSetChoke( choke[i].peer->msgs, choke[i].isChoked );
3124
3125    /* cleanup */
3126    tr_free( choke );
3127}
3128
3129static void
3130rechokePulse( int foo UNUSED, short bar UNUSED, void * vmgr )
3131{
3132    tr_torrent * tor = NULL;
3133    tr_peerMgr * mgr = vmgr;
3134    const uint64_t now = tr_time_msec( );
3135
3136    managerLock( mgr );
3137
3138    while(( tor = tr_torrentNext( mgr->session, tor ))) {
3139        if( tor->isRunning ) {
3140            rechokeUploads( tor->torrentPeers, now );
3141            if( !tr_torrentIsSeed( tor ) )
3142                rechokeDownloads( tor->torrentPeers );
3143        }
3144    }
3145
3146    tr_timerAddMsec( mgr->rechokeTimer, RECHOKE_PERIOD_MSEC );
3147    managerUnlock( mgr );
3148}
3149
3150/***
3151****
3152****  Life and Death
3153****
3154***/
3155
3156static bool
3157shouldPeerBeClosed( const Torrent    * t,
3158                    const tr_peer    * peer,
3159                    int                peerCount,
3160                    const time_t       now )
3161{
3162    const tr_torrent *       tor = t->tor;
3163    const struct peer_atom * atom = peer->atom;
3164
3165    /* if it's marked for purging, close it */
3166    if( peer->doPurge )
3167    {
3168        tordbg( t, "purging peer %s because its doPurge flag is set",
3169                tr_atomAddrStr( atom ) );
3170        return true;
3171    }
3172
3173    /* disconnect if we're both seeds and enough time has passed for PEX */
3174    if( tr_torrentIsSeed( tor ) && peerIsSeed( peer ) )
3175        return !tr_torrentAllowsPex(tor) || (now-atom->time>=30);
3176
3177    /* disconnect if it's been too long since piece data has been transferred.
3178     * this is on a sliding scale based on number of available peers... */
3179    {
3180        const int relaxStrictnessIfFewerThanN = (int)( ( getMaxPeerCount( tor ) * 0.9 ) + 0.5 );
3181        /* if we have >= relaxIfFewerThan, strictness is 100%.
3182         * if we have zero connections, strictness is 0% */
3183        const float strictness = peerCount >= relaxStrictnessIfFewerThanN
3184                               ? 1.0
3185                               : peerCount / (float)relaxStrictnessIfFewerThanN;
3186        const int lo = MIN_UPLOAD_IDLE_SECS;
3187        const int hi = MAX_UPLOAD_IDLE_SECS;
3188        const int limit = hi - ( ( hi - lo ) * strictness );
3189        const int idleTime = now - MAX( atom->time, atom->piece_data_time );
3190/*fprintf( stderr, "strictness is %.3f, limit is %d seconds... time since connect is %d, time since piece is %d ... idleTime is %d, doPurge is %d\n", (double)strictness, limit, (int)(now - atom->time), (int)(now - atom->piece_data_time), idleTime, idleTime > limit );*/
3191        if( idleTime > limit ) {
3192            tordbg( t, "purging peer %s because it's been %d secs since we shared anything",
3193                       tr_atomAddrStr( atom ), idleTime );
3194            return true;
3195        }
3196    }
3197
3198    return false;
3199}
3200
3201static tr_peer **
3202getPeersToClose( Torrent * t, const time_t now_sec, int * setmeSize )
3203{
3204    int i, peerCount, outsize;
3205    tr_peer ** peers = (tr_peer**) tr_ptrArrayPeek( &t->peers, &peerCount );
3206    struct tr_peer ** ret = tr_new( tr_peer *, peerCount );
3207
3208    assert( torrentIsLocked( t ) );
3209
3210    for( i = outsize = 0; i < peerCount; ++i )
3211        if( shouldPeerBeClosed( t, peers[i], peerCount, now_sec ) )
3212            ret[outsize++] = peers[i];
3213
3214    *setmeSize = outsize;
3215    return ret;
3216}
3217
3218static int
3219getReconnectIntervalSecs( const struct peer_atom * atom, const time_t now )
3220{
3221    int sec;
3222
3223    /* if we were recently connected to this peer and transferring piece
3224     * data, try to reconnect to them sooner rather that later -- we don't
3225     * want network troubles to get in the way of a good peer. */
3226    if( ( now - atom->piece_data_time ) <= ( MINIMUM_RECONNECT_INTERVAL_SECS * 2 ) )
3227        sec = MINIMUM_RECONNECT_INTERVAL_SECS;
3228
3229    /* don't allow reconnects more often than our minimum */
3230    else if( ( now - atom->time ) < MINIMUM_RECONNECT_INTERVAL_SECS )
3231        sec = MINIMUM_RECONNECT_INTERVAL_SECS;
3232
3233    /* otherwise, the interval depends on how many times we've tried
3234     * and failed to connect to the peer */
3235    else switch( atom->numFails ) {
3236        case 0: sec = 0; break;
3237        case 1: sec = 5; break;
3238        case 2: sec = 2 * 60; break;
3239        case 3: sec = 15 * 60; break;
3240        case 4: sec = 30 * 60; break;
3241        case 5: sec = 60 * 60; break;
3242        default: sec = 120 * 60; break;
3243    }
3244
3245    /* penalize peers that were unreachable the last time we tried */
3246    if( atom->flags2 & MYFLAG_UNREACHABLE )
3247        sec += sec;
3248
3249    dbgmsg( "reconnect interval for %s is %d seconds", tr_atomAddrStr( atom ), sec );
3250    return sec;
3251}
3252
3253static void
3254removePeer( Torrent * t, tr_peer * peer )
3255{
3256    tr_peer * removed;
3257    struct peer_atom * atom = peer->atom;
3258
3259    assert( torrentIsLocked( t ) );
3260    assert( atom );
3261
3262    atom->time = tr_time( );
3263
3264    removed = tr_ptrArrayRemoveSorted( &t->peers, peer, peerCompare );
3265
3266    if( replicationExists( t ) )
3267        tr_decrReplicationFromBitfield( t, &peer->have );
3268
3269    assert( removed == peer );
3270    peerDelete( t, removed );
3271}
3272
3273static void
3274closePeer( Torrent * t, tr_peer * peer )
3275{
3276    struct peer_atom * atom;
3277
3278    assert( t != NULL );
3279    assert( peer != NULL );
3280
3281    atom = peer->atom;
3282
3283    /* if we transferred piece data, then they might be good peers,
3284       so reset their `numFails' weight to zero. otherwise we connected
3285       to them fruitlessly, so mark it as another fail */
3286    if( atom->piece_data_time ) {
3287        tordbg( t, "resetting atom %s numFails to 0", tr_atomAddrStr(atom) );
3288        atom->numFails = 0;
3289    } else {
3290        ++atom->numFails;
3291        tordbg( t, "incremented atom %s numFails to %d", tr_atomAddrStr(atom), (int)atom->numFails );
3292    }
3293
3294    tordbg( t, "removing bad peer %s", tr_peerIoGetAddrStr( peer->io ) );
3295    removePeer( t, peer );
3296}
3297
3298static void
3299removeAllPeers( Torrent * t )
3300{
3301    while( !tr_ptrArrayEmpty( &t->peers ) )
3302        removePeer( t, tr_ptrArrayNth( &t->peers, 0 ) );
3303}
3304
3305static void
3306closeBadPeers( Torrent * t, const time_t now_sec )
3307{
3308    int i;
3309    int peerCount;
3310    struct tr_peer ** peers = getPeersToClose( t, now_sec, &peerCount );
3311    for( i=0; i<peerCount; ++i )
3312        closePeer( t, peers[i] );
3313    tr_free( peers );
3314}
3315
3316struct peer_liveliness
3317{
3318    tr_peer * peer;
3319    void * clientData;
3320    time_t pieceDataTime;
3321    time_t time;
3322    int speed;
3323    bool doPurge;
3324};
3325
3326static int
3327comparePeerLiveliness( const void * va, const void * vb )
3328{
3329    const struct peer_liveliness * a = va;
3330    const struct peer_liveliness * b = vb;
3331
3332    if( a->doPurge != b->doPurge )
3333        return a->doPurge ? 1 : -1;
3334
3335    if( a->speed != b->speed ) /* faster goes first */
3336        return a->speed > b->speed ? -1 : 1;
3337
3338    /* the one to give us data more recently goes first */
3339    if( a->pieceDataTime != b->pieceDataTime )
3340        return a->pieceDataTime > b->pieceDataTime ? -1 : 1;
3341
3342    /* the one we connected to most recently goes first */
3343    if( a->time != b->time )
3344        return a->time > b->time ? -1 : 1;
3345
3346    return 0;
3347}
3348
3349static void
3350sortPeersByLivelinessImpl( tr_peer  ** peers,
3351                           void     ** clientData,
3352                           int         n,
3353                           uint64_t    now,
3354                           int (*compare) ( const void *va, const void *vb ) )
3355{
3356    int i;
3357    struct peer_liveliness *lives, *l;
3358
3359    /* build a sortable array of peer + extra info */
3360    lives = l = tr_new0( struct peer_liveliness, n );
3361    for( i=0; i<n; ++i, ++l )
3362    {
3363        tr_peer * p = peers[i];
3364        l->peer = p;
3365        l->doPurge = p->doPurge;
3366        l->pieceDataTime = p->atom->piece_data_time;
3367        l->time = p->atom->time;
3368        l->speed = tr_peerGetPieceSpeed_Bps( p, now, TR_UP )
3369                 + tr_peerGetPieceSpeed_Bps( p, now, TR_DOWN );
3370        if( clientData )
3371            l->clientData = clientData[i];
3372    }
3373
3374    /* sort 'em */
3375    assert( n == ( l - lives ) );
3376    qsort( lives, n, sizeof( struct peer_liveliness ), compare );
3377
3378    /* build the peer array */
3379    for( i=0, l=lives; i<n; ++i, ++l ) {
3380        peers[i] = l->peer;
3381        if( clientData )
3382            clientData[i] = l->clientData;
3383    }
3384    assert( n == ( l - lives ) );
3385
3386    /* cleanup */
3387    tr_free( lives );
3388}
3389
3390static void
3391sortPeersByLiveliness( tr_peer ** peers, void ** clientData, int n, uint64_t now )
3392{
3393    sortPeersByLivelinessImpl( peers, clientData, n, now, comparePeerLiveliness );
3394}
3395
3396
3397static void
3398enforceTorrentPeerLimit( Torrent * t, uint64_t now )
3399{
3400    int n = tr_ptrArraySize( &t->peers );
3401    const int max = tr_torrentGetPeerLimit( t->tor );
3402    if( n > max )
3403    {
3404        void * base = tr_ptrArrayBase( &t->peers );
3405        tr_peer ** peers = tr_memdup( base, n*sizeof( tr_peer* ) );
3406        sortPeersByLiveliness( peers, NULL, n, now );
3407        while( n > max )
3408            closePeer( t, peers[--n] );
3409        tr_free( peers );
3410    }
3411}
3412
3413static void
3414enforceSessionPeerLimit( tr_session * session, uint64_t now )
3415{
3416    int n = 0;
3417    tr_torrent * tor = NULL;
3418    const int max = tr_sessionGetPeerLimit( session );
3419
3420    /* count the total number of peers */
3421    while(( tor = tr_torrentNext( session, tor )))
3422        n += tr_ptrArraySize( &tor->torrentPeers->peers );
3423
3424    /* if there are too many, prune out the worst */
3425    if( n > max )
3426    {
3427        tr_peer ** peers = tr_new( tr_peer*, n );
3428        Torrent ** torrents = tr_new( Torrent*, n );
3429
3430        /* populate the peer array */
3431        n = 0;
3432        tor = NULL;
3433        while(( tor = tr_torrentNext( session, tor ))) {
3434            int i;
3435            Torrent * t = tor->torrentPeers;
3436            const int tn = tr_ptrArraySize( &t->peers );
3437            for( i=0; i<tn; ++i, ++n ) {
3438                peers[n] = tr_ptrArrayNth( &t->peers, i );
3439                torrents[n] = t;
3440            }
3441        }
3442
3443        /* sort 'em */
3444        sortPeersByLiveliness( peers, (void**)torrents, n, now );
3445
3446        /* cull out the crappiest */
3447        while( n-- > max )
3448            closePeer( torrents[n], peers[n] );
3449
3450        /* cleanup */
3451        tr_free( torrents );
3452        tr_free( peers );
3453    }
3454}
3455
3456static void makeNewPeerConnections( tr_peerMgr * mgr, const int max );
3457
3458static void
3459reconnectPulse( int foo UNUSED, short bar UNUSED, void * vmgr )
3460{
3461    tr_torrent * tor;
3462    tr_peerMgr * mgr = vmgr;
3463    const time_t now_sec = tr_time( );
3464    const uint64_t now_msec = tr_time_msec( );
3465
3466    /**
3467    ***  enforce the per-session and per-torrent peer limits
3468    **/
3469
3470    /* if we're over the per-torrent peer limits, cull some peers */
3471    tor = NULL;
3472    while(( tor = tr_torrentNext( mgr->session, tor )))
3473        if( tor->isRunning )
3474            enforceTorrentPeerLimit( tor->torrentPeers, now_msec );
3475
3476    /* if we're over the per-session peer limits, cull some peers */
3477    enforceSessionPeerLimit( mgr->session, now_msec );
3478
3479    /* remove crappy peers */
3480    tor = NULL;
3481    while(( tor = tr_torrentNext( mgr->session, tor )))
3482        if( !tor->torrentPeers->isRunning )
3483            removeAllPeers( tor->torrentPeers );
3484        else
3485            closeBadPeers( tor->torrentPeers, now_sec );
3486
3487    /* try to make new peer connections */
3488    makeNewPeerConnections( mgr, MAX_CONNECTIONS_PER_PULSE );
3489}
3490
3491/****
3492*****
3493*****  BANDWIDTH ALLOCATION
3494*****
3495****/
3496
3497static void
3498pumpAllPeers( tr_peerMgr * mgr )
3499{
3500    tr_torrent * tor = NULL;
3501
3502    while(( tor = tr_torrentNext( mgr->session, tor )))
3503    {
3504        int j;
3505        Torrent * t = tor->torrentPeers;
3506
3507        for( j=0; j<tr_ptrArraySize( &t->peers ); ++j )
3508        {
3509            tr_peer * peer = tr_ptrArrayNth( &t->peers, j );
3510            tr_peerMsgsPulse( peer->msgs );
3511        }
3512    }
3513}
3514
3515static void
3516bandwidthPulse( int foo UNUSED, short bar UNUSED, void * vmgr )
3517{
3518    tr_torrent * tor;
3519    tr_peerMgr * mgr = vmgr;
3520    managerLock( mgr );
3521
3522    /* FIXME: this next line probably isn't necessary... */
3523    pumpAllPeers( mgr );
3524
3525    /* allocate bandwidth to the peers */
3526    tr_bandwidthAllocate( mgr->session->bandwidth, TR_UP, BANDWIDTH_PERIOD_MSEC );
3527    tr_bandwidthAllocate( mgr->session->bandwidth, TR_DOWN, BANDWIDTH_PERIOD_MSEC );
3528
3529    /* possibly stop torrents that have seeded enough */
3530    tor = NULL;
3531    while(( tor = tr_torrentNext( mgr->session, tor )))
3532        tr_torrentCheckSeedLimit( tor );
3533
3534    /* run the completeness check for any torrents that need it */
3535    tor = NULL;
3536    while(( tor = tr_torrentNext( mgr->session, tor ))) {
3537        if( tor->torrentPeers->needsCompletenessCheck ) {
3538            tor->torrentPeers->needsCompletenessCheck  = false;
3539            tr_torrentRecheckCompleteness( tor );
3540        }
3541    }
3542
3543    /* stop torrents that are ready to stop, but couldn't be stopped earlier
3544     * during the peer-io callback call chain */
3545    tor = NULL;
3546    while(( tor = tr_torrentNext( mgr->session, tor )))
3547        if( tor->isStopping )
3548            tr_torrentStop( tor );
3549
3550    reconnectPulse( 0, 0, mgr );
3551
3552    tr_timerAddMsec( mgr->bandwidthTimer, BANDWIDTH_PERIOD_MSEC );
3553    managerUnlock( mgr );
3554}
3555
3556/***
3557****
3558***/
3559
3560static int
3561compareAtomPtrsByAddress( const void * va, const void *vb )
3562{
3563    const struct peer_atom * a = * (const struct peer_atom**) va;
3564    const struct peer_atom * b = * (const struct peer_atom**) vb;
3565
3566    assert( tr_isAtom( a ) );
3567    assert( tr_isAtom( b ) );
3568
3569    return tr_address_compare( &a->addr, &b->addr );
3570}
3571
3572/* best come first, worst go last */
3573static int
3574compareAtomPtrsByShelfDate( const void * va, const void *vb )
3575{
3576    time_t atime;
3577    time_t btime;
3578    const struct peer_atom * a = * (const struct peer_atom**) va;
3579    const struct peer_atom * b = * (const struct peer_atom**) vb;
3580    const int data_time_cutoff_secs = 60 * 60;
3581    const time_t tr_now = tr_time( );
3582
3583    assert( tr_isAtom( a ) );
3584    assert( tr_isAtom( b ) );
3585
3586    /* primary key: the last piece data time *if* it was within the last hour */
3587    atime = a->piece_data_time; if( atime + data_time_cutoff_secs < tr_now ) atime = 0;
3588    btime = b->piece_data_time; if( btime + data_time_cutoff_secs < tr_now ) btime = 0;
3589    if( atime != btime )
3590        return atime > btime ? -1 : 1;
3591
3592    /* secondary key: shelf date. */
3593    if( a->shelf_date != b->shelf_date )
3594        return a->shelf_date > b->shelf_date ? -1 : 1;
3595
3596    return 0;
3597}
3598
3599static int
3600getMaxAtomCount( const tr_torrent * tor )
3601{
3602    const int n = tor->maxConnectedPeers;
3603    /* approximate fit of the old jump discontinuous function */
3604    if( n >= 55 ) return     n + 150;
3605    if( n >= 20 ) return 2 * n + 95;
3606    return               4 * n + 55;
3607}
3608
3609static void
3610atomPulse( int foo UNUSED, short bar UNUSED, void * vmgr )
3611{
3612    tr_torrent * tor = NULL;
3613    tr_peerMgr * mgr = vmgr;
3614    managerLock( mgr );
3615
3616    while(( tor = tr_torrentNext( mgr->session, tor )))
3617    {
3618        int atomCount;
3619        Torrent * t = tor->torrentPeers;
3620        const int maxAtomCount = getMaxAtomCount( tor );
3621        struct peer_atom ** atoms = (struct peer_atom**) tr_ptrArrayPeek( &t->pool, &atomCount );
3622
3623        if( atomCount > maxAtomCount ) /* we've got too many atoms... time to prune */
3624        {
3625            int i;
3626            int keepCount = 0;
3627            int testCount = 0;
3628            struct peer_atom ** keep = tr_new( struct peer_atom*, atomCount );
3629            struct peer_atom ** test = tr_new( struct peer_atom*, atomCount );
3630
3631            /* keep the ones that are in use */
3632            for( i=0; i<atomCount; ++i ) {
3633                struct peer_atom * atom = atoms[i];
3634                if( peerIsInUse( t, atom ) )
3635                    keep[keepCount++] = atom;
3636                else
3637                    test[testCount++] = atom;
3638            }
3639
3640            /* if there's room, keep the best of what's left */
3641            i = 0;
3642            if( keepCount < maxAtomCount ) {
3643                qsort( test, testCount, sizeof( struct peer_atom * ), compareAtomPtrsByShelfDate );
3644                while( i<testCount && keepCount<maxAtomCount )
3645                    keep[keepCount++] = test[i++];
3646            }
3647
3648            /* free the culled atoms */
3649            while( i<testCount )
3650                tr_free( test[i++] );
3651
3652            /* rebuild Torrent.pool with what's left */
3653            tr_ptrArrayDestruct( &t->pool, NULL );
3654            t->pool = TR_PTR_ARRAY_INIT;
3655            qsort( keep, keepCount, sizeof( struct peer_atom * ), compareAtomPtrsByAddress );
3656            for( i=0; i<keepCount; ++i )
3657                tr_ptrArrayAppend( &t->pool, keep[i] );
3658
3659            tordbg( t, "max atom count is %d... pruned from %d to %d\n", maxAtomCount, atomCount, keepCount );
3660
3661            /* cleanup */
3662            tr_free( test );
3663            tr_free( keep );
3664        }
3665    }
3666
3667    tr_timerAddMsec( mgr->atomTimer, ATOM_PERIOD_MSEC );
3668    managerUnlock( mgr );
3669}
3670
3671/***
3672****
3673****
3674****
3675***/
3676
3677/* is this atom someone that we'd want to initiate a connection to? */
3678static bool
3679isPeerCandidate( const tr_torrent * tor, struct peer_atom * atom, const time_t now )
3680{
3681    /* not if we're both seeds */
3682    if( tr_torrentIsSeed( tor ) && atomIsSeed( atom ) )
3683        return false;
3684
3685    /* not if we've already got a connection to them... */
3686    if( peerIsInUse( tor->torrentPeers, atom ) )
3687        return false;
3688
3689    /* not if we just tried them already */
3690    if( ( now - atom->time ) < getReconnectIntervalSecs( atom, now ) )
3691        return false;
3692
3693    /* not if they're blocklisted */
3694    if( isAtomBlocklisted( tor->session, atom ) )
3695        return false;
3696
3697    /* not if they're banned... */
3698    if( atom->flags2 & MYFLAG_BANNED )
3699        return false;
3700
3701    return true;
3702}
3703
3704struct peer_candidate
3705{
3706    uint64_t score;
3707    tr_torrent * tor;
3708    struct peer_atom * atom;
3709};
3710
3711static bool
3712torrentWasRecentlyStarted( const tr_torrent * tor )
3713{
3714    return difftime( tr_time( ), tor->startDate ) < 120;
3715}
3716
3717static inline uint64_t
3718addValToKey( uint64_t value, int width, uint64_t addme )
3719{
3720    value = (value << (uint64_t)width);
3721    value |= addme;
3722    return value;
3723}
3724
3725/* smaller value is better */
3726static uint64_t
3727getPeerCandidateScore( const tr_torrent * tor, const struct peer_atom * atom, uint8_t salt  )
3728{
3729    uint64_t i;
3730    uint64_t score = 0;
3731    const bool failed = atom->lastConnectionAt < atom->lastConnectionAttemptAt;
3732
3733    /* prefer peers we've connected to, or never tried, over peers we failed to connect to. */
3734    i = failed ? 1 : 0;
3735    score = addValToKey( score, 1, i );
3736
3737    /* prefer the one we attempted least recently (to cycle through all peers) */
3738    i = atom->lastConnectionAttemptAt;
3739    score = addValToKey( score, 32, i );
3740
3741    /* prefer peers belonging to a torrent of a higher priority */
3742    switch( tr_torrentGetPriority( tor ) ) {
3743        case TR_PRI_HIGH:    i = 0; break;
3744        case TR_PRI_NORMAL:  i = 1; break;
3745        case TR_PRI_LOW:     i = 2; break;
3746    }
3747    score = addValToKey( score, 4, i );
3748
3749    /* prefer recently-started torrents */
3750    i = torrentWasRecentlyStarted( tor ) ? 0 : 1;
3751    score = addValToKey( score, 1, i );
3752
3753    /* prefer torrents we're downloading with */
3754    i = tr_torrentIsSeed( tor ) ? 1 : 0;
3755    score = addValToKey( score, 1, i );
3756
3757    /* prefer peers that are known to be connectible */
3758    i = ( atom->flags & ADDED_F_CONNECTABLE ) ? 0 : 1;
3759    score = addValToKey( score, 1, i );
3760
3761    /* prefer peers that we might have a chance of uploading to...
3762       so lower seed probability is better */
3763    if( atom->seedProbability == 100 ) i = 101;
3764    else if( atom->seedProbability == -1 ) i = 100;
3765    else i = atom->seedProbability;
3766    score = addValToKey( score, 8, i );
3767
3768    /* Prefer peers that we got from more trusted sources.
3769     * lower `fromBest' values indicate more trusted sources */
3770    score = addValToKey( score, 4, atom->fromBest );
3771
3772    /* salt */
3773    score = addValToKey( score, 8, salt );
3774
3775    return score;
3776}
3777
3778/* sort an array of peer candidates */
3779static int
3780comparePeerCandidates( const void * va, const void * vb )
3781{
3782    const struct peer_candidate * a = va;
3783    const struct peer_candidate * b = vb;
3784
3785    if( a->score < b->score ) return -1;
3786    if( a->score > b->score ) return 1;
3787
3788    return 0;
3789}
3790
3791/** @return an array of all the atoms we might want to connect to */
3792static struct peer_candidate*
3793getPeerCandidates( tr_session * session, int * candidateCount )
3794{
3795    int n;
3796    tr_torrent * tor;
3797    struct peer_candidate * candidates;
3798    struct peer_candidate * walk;
3799    const time_t now = tr_time( );
3800    const uint64_t now_msec = tr_time_msec( );
3801    /* leave 5% of connection slots for incoming connections -- ticket #2609 */
3802    const int maxCandidates = tr_sessionGetPeerLimit( session ) * 0.95;
3803
3804    /* don't start any new handshakes if we're full up */
3805    n = 0;
3806    tor= NULL;
3807    while(( tor = tr_torrentNext( session, tor )))
3808        n += tr_ptrArraySize( &tor->torrentPeers->peers );
3809    if( maxCandidates <= n ) {
3810        *candidateCount = 0;
3811        return NULL;
3812    }
3813
3814    /* allocate an array of candidates */
3815    n = 0;
3816    tor= NULL;
3817    while(( tor = tr_torrentNext( session, tor )))
3818        n += tr_ptrArraySize( &tor->torrentPeers->pool );
3819    walk = candidates = tr_new( struct peer_candidate, n );
3820
3821    /* populate the candidate array */
3822    tor = NULL;
3823    while(( tor = tr_torrentNext( session, tor )))
3824    {
3825        int i, nAtoms;
3826        struct peer_atom ** atoms;
3827
3828        if( !tor->torrentPeers->isRunning )
3829            continue;
3830
3831        /* if we've already got enough peers in this torrent... */
3832        if( tr_torrentGetPeerLimit( tor ) <= tr_ptrArraySize( &tor->torrentPeers->peers ) )
3833            continue;
3834
3835        /* if we've already got enough speed in this torrent... */
3836        if( tr_torrentIsSeed( tor ) && isBandwidthMaxedOut( tor->bandwidth, now_msec, TR_UP ) )
3837            continue;
3838
3839        atoms = (struct peer_atom**) tr_ptrArrayPeek( &tor->torrentPeers->pool, &nAtoms );
3840        for( i=0; i<nAtoms; ++i )
3841        {
3842            struct peer_atom * atom = atoms[i];
3843
3844            if( isPeerCandidate( tor, atom, now ) )
3845            {
3846                const uint8_t salt = tr_cryptoWeakRandInt( 1024 );
3847                walk->tor = tor;
3848                walk->atom = atom;
3849                walk->score = getPeerCandidateScore( tor, atom, salt );
3850                ++walk;
3851            }
3852        }
3853    }
3854
3855    *candidateCount = walk - candidates;
3856    if( *candidateCount > 1 )
3857        qsort( candidates, *candidateCount, sizeof( struct peer_candidate ), comparePeerCandidates );
3858    return candidates;
3859}
3860
3861static void
3862initiateConnection( tr_peerMgr * mgr, Torrent * t, struct peer_atom * atom )
3863{
3864    tr_peerIo * io;
3865    const time_t now = tr_time( );
3866    bool utp = tr_sessionIsUTPEnabled(mgr->session) && !atom->utp_failed;
3867
3868    if( atom->fromFirst == TR_PEER_FROM_PEX )
3869        /* PEX has explicit signalling for uTP support.  If an atom
3870           originally came from PEX and doesn't have the uTP flag, skip the
3871           uTP connection attempt.  Are we being optimistic here? */
3872        utp = utp && (atom->flags & ADDED_F_UTP_FLAGS);
3873
3874    tordbg( t, "Starting an OUTGOING%s connection with %s",
3875            utp ? " µTP" : "",
3876            tr_atomAddrStr( atom ) );
3877
3878    io = tr_peerIoNewOutgoing( mgr->session,
3879                               mgr->session->bandwidth,
3880                               &atom->addr,
3881                               atom->port,
3882                               t->tor->info.hash,
3883                               t->tor->completeness == TR_SEED,
3884                               utp );
3885
3886    if( io == NULL )
3887    {
3888        tordbg( t, "peerIo not created; marking peer %s as unreachable",
3889                tr_atomAddrStr( atom ) );
3890        atom->flags2 |= MYFLAG_UNREACHABLE;
3891        atom->numFails++;
3892    }
3893    else
3894    {
3895        tr_handshake * handshake = tr_handshakeNew( io,
3896                                                    mgr->session->encryptionMode,
3897                                                    myHandshakeDoneCB,
3898                                                    mgr );
3899
3900        assert( tr_peerIoGetTorrentHash( io ) );
3901
3902        tr_peerIoUnref( io ); /* balanced by the initial ref
3903                                 in tr_peerIoNewOutgoing() */
3904
3905        tr_ptrArrayInsertSorted( &t->outgoingHandshakes, handshake,
3906                                 handshakeCompare );
3907    }
3908
3909    atom->lastConnectionAttemptAt = now;
3910    atom->time = now;
3911}
3912
3913static void
3914initiateCandidateConnection( tr_peerMgr * mgr, struct peer_candidate * c )
3915{
3916#if 0
3917    fprintf( stderr, "Starting an OUTGOING connection with %s - [%s] seedProbability==%d; %s, %s\n",
3918             tr_atomAddrStr( c->atom ),
3919             tr_torrentName( c->tor ),
3920             (int)c->atom->seedProbability,
3921             tr_torrentIsPrivate( c->tor ) ? "private" : "public",
3922             tr_torrentIsSeed( c->tor ) ? "seed" : "downloader" );
3923#endif
3924
3925    initiateConnection( mgr, c->tor->torrentPeers, c->atom );
3926}
3927
3928static void
3929makeNewPeerConnections( struct tr_peerMgr * mgr, const int max )
3930{
3931    int i, n;
3932    struct peer_candidate * candidates;
3933
3934    candidates = getPeerCandidates( mgr->session, &n );
3935
3936    for( i=0; i<n && i<max; ++i )
3937        initiateCandidateConnection( mgr, &candidates[i] );
3938
3939    tr_free( candidates );
3940}
Note: See TracBrowser for help on using the repository browser.