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

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

(trunk libT) remove unnecessary memmove()s from rechokeDownloads()

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