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

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

(trunk libT) when reading piece data in from a socket, avoid two unnecessary calls to memcpy()

  • Property svn:keywords set to Date Rev Author Id
File size: 114.7 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 12303 2011-04-04 04:45:41Z 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            tr_removeElementFromArray( peers, i, sizeof(tr_peer*), n-- );
2929        }
2930
2931        tr_free( peers );
2932    }
2933
2934    t->interestedCount = 0;
2935
2936    /* We've decided (1) how many peers to be interested in,
2937     * and (2) which peers are the best candidates,
2938     * Now it's time to update our `interest' flags. */
2939    for( i=0; i<goodCount; ++i ) {
2940        const bool b = t->interestedCount < maxPeers;
2941        tr_peerMsgsSetInterested( good[i]->msgs, b );
2942        if( b )
2943            ++t->interestedCount;
2944    }
2945    for( i=0; i<untestedCount; ++i ) {
2946        const bool b = t->interestedCount < maxPeers;
2947        tr_peerMsgsSetInterested( untested[i]->msgs, b );
2948        if( b )
2949            ++t->interestedCount;
2950    }
2951    for( i=0; i<badCount; ++i ) {
2952        const bool b = t->interestedCount < maxPeers;
2953        tr_peerMsgsSetInterested( bad[i]->msgs, b );
2954        if( b )
2955            ++t->interestedCount;
2956    }
2957
2958/*fprintf( stderr, "num interested: %d\n", t->interestedCount );*/
2959
2960    /* cleanup */
2961    tr_free( untested );
2962    tr_free( good );
2963    tr_free( bad );
2964}
2965
2966/**
2967***
2968**/
2969
2970struct ChokeData
2971{
2972    bool            isInterested;
2973    bool            wasChoked;
2974    bool            isChoked;
2975    int             rate;
2976    int             salt;
2977    tr_peer *       peer;
2978};
2979
2980static int
2981compareChoke( const void * va, const void * vb )
2982{
2983    const struct ChokeData * a = va;
2984    const struct ChokeData * b = vb;
2985
2986    if( a->rate != b->rate ) /* prefer higher overall speeds */
2987        return a->rate > b->rate ? -1 : 1;
2988
2989    if( a->wasChoked != b->wasChoked ) /* prefer unchoked */
2990        return a->wasChoked ? 1 : -1;
2991
2992    if( a->salt != b->salt ) /* random order */
2993        return a->salt - b->salt;
2994
2995    return 0;
2996}
2997
2998/* is this a new connection? */
2999static int
3000isNew( const tr_peer * peer )
3001{
3002    return peer && peer->io && tr_peerIoGetAge( peer->io ) < 45;
3003}
3004
3005/* get a rate for deciding which peers to choke and unchoke. */
3006static int
3007getRate( const tr_torrent * tor, struct peer_atom * atom, uint64_t now )
3008{
3009    int Bps;
3010
3011    if( tr_torrentIsSeed( tor ) )
3012        Bps = tr_peerGetPieceSpeed_Bps( atom->peer, now, TR_CLIENT_TO_PEER );
3013
3014    /* downloading a private torrent... take upload speed into account
3015     * because there may only be a small window of opportunity to share */
3016    else if( tr_torrentIsPrivate( tor ) )
3017        Bps = tr_peerGetPieceSpeed_Bps( atom->peer, now, TR_PEER_TO_CLIENT )
3018            + tr_peerGetPieceSpeed_Bps( atom->peer, now, TR_CLIENT_TO_PEER );
3019
3020    /* downloading a public torrent */
3021    else
3022        Bps = tr_peerGetPieceSpeed_Bps( atom->peer, now, TR_PEER_TO_CLIENT );
3023
3024    /* convert it to bytes per second */
3025    return Bps;
3026}
3027
3028static inline bool
3029isBandwidthMaxedOut( const tr_bandwidth * b,
3030                     const uint64_t now_msec, tr_direction dir )
3031{
3032    if( !tr_bandwidthIsLimited( b, dir ) )
3033        return false;
3034    else {
3035        const int got = tr_bandwidthGetPieceSpeed_Bps( b, now_msec, dir );
3036        const int want = tr_bandwidthGetDesiredSpeed_Bps( b, dir );
3037        return got >= want;
3038    }
3039}
3040
3041static void
3042rechokeUploads( Torrent * t, const uint64_t now )
3043{
3044    int i, size, unchokedInterested;
3045    const int peerCount = tr_ptrArraySize( &t->peers );
3046    tr_peer ** peers = (tr_peer**) tr_ptrArrayBase( &t->peers );
3047    struct ChokeData * choke = tr_new0( struct ChokeData, peerCount );
3048    const tr_session * session = t->manager->session;
3049    const int chokeAll = !tr_torrentIsPieceTransferAllowed( t->tor, TR_CLIENT_TO_PEER );
3050    const bool isMaxedOut = isBandwidthMaxedOut( &t->tor->bandwidth, now, TR_UP );
3051
3052    assert( torrentIsLocked( t ) );
3053
3054    /* an optimistic unchoke peer's "optimistic"
3055     * state lasts for N calls to rechokeUploads(). */
3056    if( t->optimisticUnchokeTimeScaler > 0 )
3057        t->optimisticUnchokeTimeScaler--;
3058    else
3059        t->optimistic = NULL;
3060
3061    /* sort the peers by preference and rate */
3062    for( i = 0, size = 0; i < peerCount; ++i )
3063    {
3064        tr_peer * peer = peers[i];
3065        struct peer_atom * atom = peer->atom;
3066
3067        if( peerIsSeed( peer ) ) /* choke seeds and partial seeds */
3068        {
3069            tr_peerMsgsSetChoke( peer->msgs, true );
3070        }
3071        else if( chokeAll ) /* choke everyone if we're not uploading */
3072        {
3073            tr_peerMsgsSetChoke( peer->msgs, true );
3074        }
3075        else if( peer != t->optimistic )
3076        {
3077            struct ChokeData * n = &choke[size++];
3078            n->peer         = peer;
3079            n->isInterested = peer->peerIsInterested;
3080            n->wasChoked    = peer->peerIsChoked;
3081            n->rate         = getRate( t->tor, atom, now );
3082            n->salt         = tr_cryptoWeakRandInt( INT_MAX );
3083            n->isChoked     = true;
3084        }
3085    }
3086
3087    qsort( choke, size, sizeof( struct ChokeData ), compareChoke );
3088
3089    /**
3090     * Reciprocation and number of uploads capping is managed by unchoking
3091     * the N peers which have the best upload rate and are interested.
3092     * This maximizes the client's download rate. These N peers are
3093     * referred to as downloaders, because they are interested in downloading
3094     * from the client.
3095     *
3096     * Peers which have a better upload rate (as compared to the downloaders)
3097     * but aren't interested get unchoked. If they become interested, the
3098     * downloader with the worst upload rate gets choked. If a client has
3099     * a complete file, it uses its upload rate rather than its download
3100     * rate to decide which peers to unchoke.
3101     *
3102     * If our bandwidth is maxed out, don't unchoke any more peers.
3103     */
3104    unchokedInterested = 0;
3105    for( i=0; i<size && unchokedInterested<session->uploadSlotsPerTorrent; ++i ) {
3106        choke[i].isChoked = isMaxedOut ? choke[i].wasChoked : false;
3107        if( choke[i].isInterested )
3108            ++unchokedInterested;
3109    }
3110
3111    /* optimistic unchoke */
3112    if( !t->optimistic && !isMaxedOut && (i<size) )
3113    {
3114        int n;
3115        struct ChokeData * c;
3116        tr_ptrArray randPool = TR_PTR_ARRAY_INIT;
3117
3118        for( ; i<size; ++i )
3119        {
3120            if( choke[i].isInterested )
3121            {
3122                const tr_peer * peer = choke[i].peer;
3123                int x = 1, y;
3124                if( isNew( peer ) ) x *= 3;
3125                for( y=0; y<x; ++y )
3126                    tr_ptrArrayAppend( &randPool, &choke[i] );
3127            }
3128        }
3129
3130        if(( n = tr_ptrArraySize( &randPool )))
3131        {
3132            c = tr_ptrArrayNth( &randPool, tr_cryptoWeakRandInt( n ));
3133            c->isChoked = false;
3134            t->optimistic = c->peer;
3135            t->optimisticUnchokeTimeScaler = OPTIMISTIC_UNCHOKE_MULTIPLIER;
3136        }
3137
3138        tr_ptrArrayDestruct( &randPool, NULL );
3139    }
3140
3141    for( i=0; i<size; ++i )
3142        tr_peerMsgsSetChoke( choke[i].peer->msgs, choke[i].isChoked );
3143
3144    /* cleanup */
3145    tr_free( choke );
3146}
3147
3148static void
3149rechokePulse( int foo UNUSED, short bar UNUSED, void * vmgr )
3150{
3151    tr_torrent * tor = NULL;
3152    tr_peerMgr * mgr = vmgr;
3153    const uint64_t now = tr_time_msec( );
3154
3155    managerLock( mgr );
3156
3157    while(( tor = tr_torrentNext( mgr->session, tor ))) {
3158        if( tor->isRunning ) {
3159            Torrent * t = tor->torrentPeers;
3160            if( tr_ptrArrayEmpty( &t->peers ) )
3161                continue;
3162            rechokeUploads( t, now );
3163            if( !tr_torrentIsSeed( tor ) )
3164                rechokeDownloads( t );
3165        }
3166    }
3167
3168    tr_timerAddMsec( mgr->rechokeTimer, RECHOKE_PERIOD_MSEC );
3169    managerUnlock( mgr );
3170}
3171
3172/***
3173****
3174****  Life and Death
3175****
3176***/
3177
3178static bool
3179shouldPeerBeClosed( const Torrent    * t,
3180                    const tr_peer    * peer,
3181                    int                peerCount,
3182                    const time_t       now )
3183{
3184    const tr_torrent *       tor = t->tor;
3185    const struct peer_atom * atom = peer->atom;
3186
3187    /* if it's marked for purging, close it */
3188    if( peer->doPurge )
3189    {
3190        tordbg( t, "purging peer %s because its doPurge flag is set",
3191                tr_atomAddrStr( atom ) );
3192        return true;
3193    }
3194
3195    /* disconnect if we're both seeds and enough time has passed for PEX */
3196    if( tr_torrentIsSeed( tor ) && peerIsSeed( peer ) )
3197        return !tr_torrentAllowsPex(tor) || (now-atom->time>=30);
3198
3199    /* disconnect if it's been too long since piece data has been transferred.
3200     * this is on a sliding scale based on number of available peers... */
3201    {
3202        const int relaxStrictnessIfFewerThanN = (int)( ( getMaxPeerCount( tor ) * 0.9 ) + 0.5 );
3203        /* if we have >= relaxIfFewerThan, strictness is 100%.
3204         * if we have zero connections, strictness is 0% */
3205        const float strictness = peerCount >= relaxStrictnessIfFewerThanN
3206                               ? 1.0
3207                               : peerCount / (float)relaxStrictnessIfFewerThanN;
3208        const int lo = MIN_UPLOAD_IDLE_SECS;
3209        const int hi = MAX_UPLOAD_IDLE_SECS;
3210        const int limit = hi - ( ( hi - lo ) * strictness );
3211        const int idleTime = now - MAX( atom->time, atom->piece_data_time );
3212/*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 );*/
3213        if( idleTime > limit ) {
3214            tordbg( t, "purging peer %s because it's been %d secs since we shared anything",
3215                       tr_atomAddrStr( atom ), idleTime );
3216            return true;
3217        }
3218    }
3219
3220    return false;
3221}
3222
3223static tr_peer **
3224getPeersToClose( Torrent * t, const time_t now_sec, int * setmeSize )
3225{
3226    int i, peerCount, outsize;
3227    tr_peer ** peers = (tr_peer**) tr_ptrArrayPeek( &t->peers, &peerCount );
3228    struct tr_peer ** ret = tr_new( tr_peer *, peerCount );
3229
3230    assert( torrentIsLocked( t ) );
3231
3232    for( i = outsize = 0; i < peerCount; ++i )
3233        if( shouldPeerBeClosed( t, peers[i], peerCount, now_sec ) )
3234            ret[outsize++] = peers[i];
3235
3236    *setmeSize = outsize;
3237    return ret;
3238}
3239
3240static int
3241getReconnectIntervalSecs( const struct peer_atom * atom, const time_t now )
3242{
3243    int sec;
3244
3245    /* if we were recently connected to this peer and transferring piece
3246     * data, try to reconnect to them sooner rather that later -- we don't
3247     * want network troubles to get in the way of a good peer. */
3248    if( ( now - atom->piece_data_time ) <= ( MINIMUM_RECONNECT_INTERVAL_SECS * 2 ) )
3249        sec = MINIMUM_RECONNECT_INTERVAL_SECS;
3250
3251    /* don't allow reconnects more often than our minimum */
3252    else if( ( now - atom->time ) < MINIMUM_RECONNECT_INTERVAL_SECS )
3253        sec = MINIMUM_RECONNECT_INTERVAL_SECS;
3254
3255    /* otherwise, the interval depends on how many times we've tried
3256     * and failed to connect to the peer */
3257    else switch( atom->numFails ) {
3258        case 0: sec = 0; break;
3259        case 1: sec = 5; break;
3260        case 2: sec = 2 * 60; break;
3261        case 3: sec = 15 * 60; break;
3262        case 4: sec = 30 * 60; break;
3263        case 5: sec = 60 * 60; break;
3264        default: sec = 120 * 60; break;
3265    }
3266
3267    /* penalize peers that were unreachable the last time we tried */
3268    if( atom->flags2 & MYFLAG_UNREACHABLE )
3269        sec += sec;
3270
3271    dbgmsg( "reconnect interval for %s is %d seconds", tr_atomAddrStr( atom ), sec );
3272    return sec;
3273}
3274
3275static void
3276removePeer( Torrent * t, tr_peer * peer )
3277{
3278    tr_peer * removed;
3279    struct peer_atom * atom = peer->atom;
3280
3281    assert( torrentIsLocked( t ) );
3282    assert( atom );
3283
3284    atom->time = tr_time( );
3285
3286    removed = tr_ptrArrayRemoveSorted( &t->peers, peer, peerCompare );
3287
3288    if( replicationExists( t ) )
3289        tr_decrReplicationFromBitfield( t, &peer->have );
3290
3291    assert( removed == peer );
3292    peerDelete( t, removed );
3293}
3294
3295static void
3296closePeer( Torrent * t, tr_peer * peer )
3297{
3298    struct peer_atom * atom;
3299
3300    assert( t != NULL );
3301    assert( peer != NULL );
3302
3303    atom = peer->atom;
3304
3305    /* if we transferred piece data, then they might be good peers,
3306       so reset their `numFails' weight to zero. otherwise we connected
3307       to them fruitlessly, so mark it as another fail */
3308    if( atom->piece_data_time ) {
3309        tordbg( t, "resetting atom %s numFails to 0", tr_atomAddrStr(atom) );
3310        atom->numFails = 0;
3311    } else {
3312        ++atom->numFails;
3313        tordbg( t, "incremented atom %s numFails to %d", tr_atomAddrStr(atom), (int)atom->numFails );
3314    }
3315
3316    tordbg( t, "removing bad peer %s", tr_peerIoGetAddrStr( peer->io ) );
3317    removePeer( t, peer );
3318}
3319
3320static void
3321removeAllPeers( Torrent * t )
3322{
3323    while( !tr_ptrArrayEmpty( &t->peers ) )
3324        removePeer( t, tr_ptrArrayNth( &t->peers, 0 ) );
3325}
3326
3327static void
3328closeBadPeers( Torrent * t, const time_t now_sec )
3329{
3330    int i;
3331    int peerCount;
3332    struct tr_peer ** peers = getPeersToClose( t, now_sec, &peerCount );
3333    for( i=0; i<peerCount; ++i )
3334        closePeer( t, peers[i] );
3335    tr_free( peers );
3336}
3337
3338struct peer_liveliness
3339{
3340    tr_peer * peer;
3341    void * clientData;
3342    time_t pieceDataTime;
3343    time_t time;
3344    int speed;
3345    bool doPurge;
3346};
3347
3348static int
3349comparePeerLiveliness( const void * va, const void * vb )
3350{
3351    const struct peer_liveliness * a = va;
3352    const struct peer_liveliness * b = vb;
3353
3354    if( a->doPurge != b->doPurge )
3355        return a->doPurge ? 1 : -1;
3356
3357    if( a->speed != b->speed ) /* faster goes first */
3358        return a->speed > b->speed ? -1 : 1;
3359
3360    /* the one to give us data more recently goes first */
3361    if( a->pieceDataTime != b->pieceDataTime )
3362        return a->pieceDataTime > b->pieceDataTime ? -1 : 1;
3363
3364    /* the one we connected to most recently goes first */
3365    if( a->time != b->time )
3366        return a->time > b->time ? -1 : 1;
3367
3368    return 0;
3369}
3370
3371static void
3372sortPeersByLivelinessImpl( tr_peer  ** peers,
3373                           void     ** clientData,
3374                           int         n,
3375                           uint64_t    now,
3376                           int (*compare) ( const void *va, const void *vb ) )
3377{
3378    int i;
3379    struct peer_liveliness *lives, *l;
3380
3381    /* build a sortable array of peer + extra info */
3382    lives = l = tr_new0( struct peer_liveliness, n );
3383    for( i=0; i<n; ++i, ++l )
3384    {
3385        tr_peer * p = peers[i];
3386        l->peer = p;
3387        l->doPurge = p->doPurge;
3388        l->pieceDataTime = p->atom->piece_data_time;
3389        l->time = p->atom->time;
3390        l->speed = tr_peerGetPieceSpeed_Bps( p, now, TR_UP )
3391                 + tr_peerGetPieceSpeed_Bps( p, now, TR_DOWN );
3392        if( clientData )
3393            l->clientData = clientData[i];
3394    }
3395
3396    /* sort 'em */
3397    assert( n == ( l - lives ) );
3398    qsort( lives, n, sizeof( struct peer_liveliness ), compare );
3399
3400    /* build the peer array */
3401    for( i=0, l=lives; i<n; ++i, ++l ) {
3402        peers[i] = l->peer;
3403        if( clientData )
3404            clientData[i] = l->clientData;
3405    }
3406    assert( n == ( l - lives ) );
3407
3408    /* cleanup */
3409    tr_free( lives );
3410}
3411
3412static void
3413sortPeersByLiveliness( tr_peer ** peers, void ** clientData, int n, uint64_t now )
3414{
3415    sortPeersByLivelinessImpl( peers, clientData, n, now, comparePeerLiveliness );
3416}
3417
3418
3419static void
3420enforceTorrentPeerLimit( Torrent * t, uint64_t now )
3421{
3422    int n = tr_ptrArraySize( &t->peers );
3423    const int max = tr_torrentGetPeerLimit( t->tor );
3424    if( n > max )
3425    {
3426        void * base = tr_ptrArrayBase( &t->peers );
3427        tr_peer ** peers = tr_memdup( base, n*sizeof( tr_peer* ) );
3428        sortPeersByLiveliness( peers, NULL, n, now );
3429        while( n > max )
3430            closePeer( t, peers[--n] );
3431        tr_free( peers );
3432    }
3433}
3434
3435static void
3436enforceSessionPeerLimit( tr_session * session, uint64_t now )
3437{
3438    int n = 0;
3439    tr_torrent * tor = NULL;
3440    const int max = tr_sessionGetPeerLimit( session );
3441
3442    /* count the total number of peers */
3443    while(( tor = tr_torrentNext( session, tor )))
3444        n += tr_ptrArraySize( &tor->torrentPeers->peers );
3445
3446    /* if there are too many, prune out the worst */
3447    if( n > max )
3448    {
3449        tr_peer ** peers = tr_new( tr_peer*, n );
3450        Torrent ** torrents = tr_new( Torrent*, n );
3451
3452        /* populate the peer array */
3453        n = 0;
3454        tor = NULL;
3455        while(( tor = tr_torrentNext( session, tor ))) {
3456            int i;
3457            Torrent * t = tor->torrentPeers;
3458            const int tn = tr_ptrArraySize( &t->peers );
3459            for( i=0; i<tn; ++i, ++n ) {
3460                peers[n] = tr_ptrArrayNth( &t->peers, i );
3461                torrents[n] = t;
3462            }
3463        }
3464
3465        /* sort 'em */
3466        sortPeersByLiveliness( peers, (void**)torrents, n, now );
3467
3468        /* cull out the crappiest */
3469        while( n-- > max )
3470            closePeer( torrents[n], peers[n] );
3471
3472        /* cleanup */
3473        tr_free( torrents );
3474        tr_free( peers );
3475    }
3476}
3477
3478static void makeNewPeerConnections( tr_peerMgr * mgr, const int max );
3479
3480static void
3481reconnectPulse( int foo UNUSED, short bar UNUSED, void * vmgr )
3482{
3483    tr_torrent * tor;
3484    tr_peerMgr * mgr = vmgr;
3485    const time_t now_sec = tr_time( );
3486    const uint64_t now_msec = tr_time_msec( );
3487
3488    /**
3489    ***  enforce the per-session and per-torrent peer limits
3490    **/
3491
3492    /* if we're over the per-torrent peer limits, cull some peers */
3493    tor = NULL;
3494    while(( tor = tr_torrentNext( mgr->session, tor )))
3495        if( tor->isRunning )
3496            enforceTorrentPeerLimit( tor->torrentPeers, now_msec );
3497
3498    /* if we're over the per-session peer limits, cull some peers */
3499    enforceSessionPeerLimit( mgr->session, now_msec );
3500
3501    /* remove crappy peers */
3502    tor = NULL;
3503    while(( tor = tr_torrentNext( mgr->session, tor )))
3504        if( !tor->torrentPeers->isRunning )
3505            removeAllPeers( tor->torrentPeers );
3506        else
3507            closeBadPeers( tor->torrentPeers, now_sec );
3508
3509    /* try to make new peer connections */
3510    makeNewPeerConnections( mgr, MAX_CONNECTIONS_PER_PULSE );
3511}
3512
3513/****
3514*****
3515*****  BANDWIDTH ALLOCATION
3516*****
3517****/
3518
3519static void
3520pumpAllPeers( tr_peerMgr * mgr )
3521{
3522    tr_torrent * tor = NULL;
3523
3524    while(( tor = tr_torrentNext( mgr->session, tor )))
3525    {
3526        int j;
3527        Torrent * t = tor->torrentPeers;
3528
3529        for( j=0; j<tr_ptrArraySize( &t->peers ); ++j )
3530        {
3531            tr_peer * peer = tr_ptrArrayNth( &t->peers, j );
3532            tr_peerMsgsPulse( peer->msgs );
3533        }
3534    }
3535}
3536
3537static void
3538bandwidthPulse( int foo UNUSED, short bar UNUSED, void * vmgr )
3539{
3540    tr_torrent * tor;
3541    tr_peerMgr * mgr = vmgr;
3542    managerLock( mgr );
3543
3544    /* FIXME: this next line probably isn't necessary... */
3545    pumpAllPeers( mgr );
3546
3547    /* allocate bandwidth to the peers */
3548    tr_bandwidthAllocate( &mgr->session->bandwidth, TR_UP, BANDWIDTH_PERIOD_MSEC );
3549    tr_bandwidthAllocate( &mgr->session->bandwidth, TR_DOWN, BANDWIDTH_PERIOD_MSEC );
3550
3551    /* possibly stop torrents that have seeded enough */
3552    tor = NULL;
3553    while(( tor = tr_torrentNext( mgr->session, tor )))
3554        tr_torrentCheckSeedLimit( tor );
3555
3556    /* run the completeness check for any torrents that need it */
3557    tor = NULL;
3558    while(( tor = tr_torrentNext( mgr->session, tor ))) {
3559        if( tor->torrentPeers->needsCompletenessCheck ) {
3560            tor->torrentPeers->needsCompletenessCheck  = false;
3561            tr_torrentRecheckCompleteness( tor );
3562        }
3563    }
3564
3565    /* stop torrents that are ready to stop, but couldn't be stopped earlier
3566     * during the peer-io callback call chain */
3567    tor = NULL;
3568    while(( tor = tr_torrentNext( mgr->session, tor )))
3569        if( tor->isStopping )
3570            tr_torrentStop( tor );
3571
3572    reconnectPulse( 0, 0, mgr );
3573
3574    tr_timerAddMsec( mgr->bandwidthTimer, BANDWIDTH_PERIOD_MSEC );
3575    managerUnlock( mgr );
3576}
3577
3578/***
3579****
3580***/
3581
3582static int
3583compareAtomPtrsByAddress( const void * va, const void *vb )
3584{
3585    const struct peer_atom * a = * (const struct peer_atom**) va;
3586    const struct peer_atom * b = * (const struct peer_atom**) vb;
3587
3588    assert( tr_isAtom( a ) );
3589    assert( tr_isAtom( b ) );
3590
3591    return tr_address_compare( &a->addr, &b->addr );
3592}
3593
3594/* best come first, worst go last */
3595static int
3596compareAtomPtrsByShelfDate( const void * va, const void *vb )
3597{
3598    time_t atime;
3599    time_t btime;
3600    const struct peer_atom * a = * (const struct peer_atom**) va;
3601    const struct peer_atom * b = * (const struct peer_atom**) vb;
3602    const int data_time_cutoff_secs = 60 * 60;
3603    const time_t tr_now = tr_time( );
3604
3605    assert( tr_isAtom( a ) );
3606    assert( tr_isAtom( b ) );
3607
3608    /* primary key: the last piece data time *if* it was within the last hour */
3609    atime = a->piece_data_time; if( atime + data_time_cutoff_secs < tr_now ) atime = 0;
3610    btime = b->piece_data_time; if( btime + data_time_cutoff_secs < tr_now ) btime = 0;
3611    if( atime != btime )
3612        return atime > btime ? -1 : 1;
3613
3614    /* secondary key: shelf date. */
3615    if( a->shelf_date != b->shelf_date )
3616        return a->shelf_date > b->shelf_date ? -1 : 1;
3617
3618    return 0;
3619}
3620
3621static int
3622getMaxAtomCount( const tr_torrent * tor )
3623{
3624    const int n = tor->maxConnectedPeers;
3625    /* approximate fit of the old jump discontinuous function */
3626    if( n >= 55 ) return     n + 150;
3627    if( n >= 20 ) return 2 * n + 95;
3628    return               4 * n + 55;
3629}
3630
3631static void
3632atomPulse( int foo UNUSED, short bar UNUSED, void * vmgr )
3633{
3634    tr_torrent * tor = NULL;
3635    tr_peerMgr * mgr = vmgr;
3636    managerLock( mgr );
3637
3638    while(( tor = tr_torrentNext( mgr->session, tor )))
3639    {
3640        int atomCount;
3641        Torrent * t = tor->torrentPeers;
3642        const int maxAtomCount = getMaxAtomCount( tor );
3643        struct peer_atom ** atoms = (struct peer_atom**) tr_ptrArrayPeek( &t->pool, &atomCount );
3644
3645        if( atomCount > maxAtomCount ) /* we've got too many atoms... time to prune */
3646        {
3647            int i;
3648            int keepCount = 0;
3649            int testCount = 0;
3650            struct peer_atom ** keep = tr_new( struct peer_atom*, atomCount );
3651            struct peer_atom ** test = tr_new( struct peer_atom*, atomCount );
3652
3653            /* keep the ones that are in use */
3654            for( i=0; i<atomCount; ++i ) {
3655                struct peer_atom * atom = atoms[i];
3656                if( peerIsInUse( t, atom ) )
3657                    keep[keepCount++] = atom;
3658                else
3659                    test[testCount++] = atom;
3660            }
3661
3662            /* if there's room, keep the best of what's left */
3663            i = 0;
3664            if( keepCount < maxAtomCount ) {
3665                qsort( test, testCount, sizeof( struct peer_atom * ), compareAtomPtrsByShelfDate );
3666                while( i<testCount && keepCount<maxAtomCount )
3667                    keep[keepCount++] = test[i++];
3668            }
3669
3670            /* free the culled atoms */
3671            while( i<testCount )
3672                tr_free( test[i++] );
3673
3674            /* rebuild Torrent.pool with what's left */
3675            tr_ptrArrayDestruct( &t->pool, NULL );
3676            t->pool = TR_PTR_ARRAY_INIT;
3677            qsort( keep, keepCount, sizeof( struct peer_atom * ), compareAtomPtrsByAddress );
3678            for( i=0; i<keepCount; ++i )
3679                tr_ptrArrayAppend( &t->pool, keep[i] );
3680
3681            tordbg( t, "max atom count is %d... pruned from %d to %d\n", maxAtomCount, atomCount, keepCount );
3682
3683            /* cleanup */
3684            tr_free( test );
3685            tr_free( keep );
3686        }
3687    }
3688
3689    tr_timerAddMsec( mgr->atomTimer, ATOM_PERIOD_MSEC );
3690    managerUnlock( mgr );
3691}
3692
3693/***
3694****
3695****
3696****
3697***/
3698
3699/* is this atom someone that we'd want to initiate a connection to? */
3700static bool
3701isPeerCandidate( const tr_torrent * tor, struct peer_atom * atom, const time_t now )
3702{
3703    /* not if we're both seeds */
3704    if( tr_torrentIsSeed( tor ) && atomIsSeed( atom ) )
3705        return false;
3706
3707    /* not if we've already got a connection to them... */
3708    if( peerIsInUse( tor->torrentPeers, atom ) )
3709        return false;
3710
3711    /* not if we just tried them already */
3712    if( ( now - atom->time ) < getReconnectIntervalSecs( atom, now ) )
3713        return false;
3714
3715    /* not if they're blocklisted */
3716    if( isAtomBlocklisted( tor->session, atom ) )
3717        return false;
3718
3719    /* not if they're banned... */
3720    if( atom->flags2 & MYFLAG_BANNED )
3721        return false;
3722
3723    return true;
3724}
3725
3726struct peer_candidate
3727{
3728    uint64_t score;
3729    tr_torrent * tor;
3730    struct peer_atom * atom;
3731};
3732
3733static bool
3734torrentWasRecentlyStarted( const tr_torrent * tor )
3735{
3736    return difftime( tr_time( ), tor->startDate ) < 120;
3737}
3738
3739static inline uint64_t
3740addValToKey( uint64_t value, int width, uint64_t addme )
3741{
3742    value = (value << (uint64_t)width);
3743    value |= addme;
3744    return value;
3745}
3746
3747/* smaller value is better */
3748static uint64_t
3749getPeerCandidateScore( const tr_torrent * tor, const struct peer_atom * atom, uint8_t salt  )
3750{
3751    uint64_t i;
3752    uint64_t score = 0;
3753    const bool failed = atom->lastConnectionAt < atom->lastConnectionAttemptAt;
3754
3755    /* prefer peers we've connected to, or never tried, over peers we failed to connect to. */
3756    i = failed ? 1 : 0;
3757    score = addValToKey( score, 1, i );
3758
3759    /* prefer the one we attempted least recently (to cycle through all peers) */
3760    i = atom->lastConnectionAttemptAt;
3761    score = addValToKey( score, 32, i );
3762
3763    /* prefer peers belonging to a torrent of a higher priority */
3764    switch( tr_torrentGetPriority( tor ) ) {
3765        case TR_PRI_HIGH:    i = 0; break;
3766        case TR_PRI_NORMAL:  i = 1; break;
3767        case TR_PRI_LOW:     i = 2; break;
3768    }
3769    score = addValToKey( score, 4, i );
3770
3771    /* prefer recently-started torrents */
3772    i = torrentWasRecentlyStarted( tor ) ? 0 : 1;
3773    score = addValToKey( score, 1, i );
3774
3775    /* prefer torrents we're downloading with */
3776    i = tr_torrentIsSeed( tor ) ? 1 : 0;
3777    score = addValToKey( score, 1, i );
3778
3779    /* prefer peers that are known to be connectible */
3780    i = ( atom->flags & ADDED_F_CONNECTABLE ) ? 0 : 1;
3781    score = addValToKey( score, 1, i );
3782
3783    /* prefer peers that we might have a chance of uploading to...
3784       so lower seed probability is better */
3785    if( atom->seedProbability == 100 ) i = 101;
3786    else if( atom->seedProbability == -1 ) i = 100;
3787    else i = atom->seedProbability;
3788    score = addValToKey( score, 8, i );
3789
3790    /* Prefer peers that we got from more trusted sources.
3791     * lower `fromBest' values indicate more trusted sources */
3792    score = addValToKey( score, 4, atom->fromBest );
3793
3794    /* salt */
3795    score = addValToKey( score, 8, salt );
3796
3797    return score;
3798}
3799
3800/* sort an array of peer candidates */
3801static int
3802comparePeerCandidates( const void * va, const void * vb )
3803{
3804    const struct peer_candidate * a = va;
3805    const struct peer_candidate * b = vb;
3806
3807    if( a->score < b->score ) return -1;
3808    if( a->score > b->score ) return 1;
3809
3810    return 0;
3811}
3812
3813/** @return an array of all the atoms we might want to connect to */
3814static struct peer_candidate*
3815getPeerCandidates( tr_session * session, int * candidateCount )
3816{
3817    int n;
3818    tr_torrent * tor;
3819    struct peer_candidate * candidates;
3820    struct peer_candidate * walk;
3821    const time_t now = tr_time( );
3822    const uint64_t now_msec = tr_time_msec( );
3823    /* leave 5% of connection slots for incoming connections -- ticket #2609 */
3824    const int maxCandidates = tr_sessionGetPeerLimit( session ) * 0.95;
3825
3826    /* don't start any new handshakes if we're full up */
3827    n = 0;
3828    tor= NULL;
3829    while(( tor = tr_torrentNext( session, tor )))
3830        n += tr_ptrArraySize( &tor->torrentPeers->peers );
3831    if( maxCandidates <= n ) {
3832        *candidateCount = 0;
3833        return NULL;
3834    }
3835
3836    /* allocate an array of candidates */
3837    n = 0;
3838    tor= NULL;
3839    while(( tor = tr_torrentNext( session, tor )))
3840        n += tr_ptrArraySize( &tor->torrentPeers->pool );
3841    walk = candidates = tr_new( struct peer_candidate, n );
3842
3843    /* populate the candidate array */
3844    tor = NULL;
3845    while(( tor = tr_torrentNext( session, tor )))
3846    {
3847        int i, nAtoms;
3848        struct peer_atom ** atoms;
3849
3850        if( !tor->torrentPeers->isRunning )
3851            continue;
3852
3853        /* if we've already got enough peers in this torrent... */
3854        if( tr_torrentGetPeerLimit( tor ) <= tr_ptrArraySize( &tor->torrentPeers->peers ) )
3855            continue;
3856
3857        /* if we've already got enough speed in this torrent... */
3858        if( tr_torrentIsSeed( tor ) && isBandwidthMaxedOut( &tor->bandwidth, now_msec, TR_UP ) )
3859            continue;
3860
3861        atoms = (struct peer_atom**) tr_ptrArrayPeek( &tor->torrentPeers->pool, &nAtoms );
3862        for( i=0; i<nAtoms; ++i )
3863        {
3864            struct peer_atom * atom = atoms[i];
3865
3866            if( isPeerCandidate( tor, atom, now ) )
3867            {
3868                const uint8_t salt = tr_cryptoWeakRandInt( 1024 );
3869                walk->tor = tor;
3870                walk->atom = atom;
3871                walk->score = getPeerCandidateScore( tor, atom, salt );
3872                ++walk;
3873            }
3874        }
3875    }
3876
3877    *candidateCount = walk - candidates;
3878    if( *candidateCount > 1 )
3879        qsort( candidates, *candidateCount, sizeof( struct peer_candidate ), comparePeerCandidates );
3880    return candidates;
3881}
3882
3883static void
3884initiateConnection( tr_peerMgr * mgr, Torrent * t, struct peer_atom * atom )
3885{
3886    tr_peerIo * io;
3887    const time_t now = tr_time( );
3888    bool utp = tr_sessionIsUTPEnabled(mgr->session) && !atom->utp_failed;
3889
3890    if( atom->fromFirst == TR_PEER_FROM_PEX )
3891        /* PEX has explicit signalling for uTP support.  If an atom
3892           originally came from PEX and doesn't have the uTP flag, skip the
3893           uTP connection attempt.  Are we being optimistic here? */
3894        utp = utp && (atom->flags & ADDED_F_UTP_FLAGS);
3895
3896    tordbg( t, "Starting an OUTGOING%s connection with %s",
3897            utp ? " µTP" : "",
3898            tr_atomAddrStr( atom ) );
3899
3900    io = tr_peerIoNewOutgoing( mgr->session,
3901                               &mgr->session->bandwidth,
3902                               &atom->addr,
3903                               atom->port,
3904                               t->tor->info.hash,
3905                               t->tor->completeness == TR_SEED,
3906                               utp );
3907
3908    if( io == NULL )
3909    {
3910        tordbg( t, "peerIo not created; marking peer %s as unreachable",
3911                tr_atomAddrStr( atom ) );
3912        atom->flags2 |= MYFLAG_UNREACHABLE;
3913        atom->numFails++;
3914    }
3915    else
3916    {
3917        tr_handshake * handshake = tr_handshakeNew( io,
3918                                                    mgr->session->encryptionMode,
3919                                                    myHandshakeDoneCB,
3920                                                    mgr );
3921
3922        assert( tr_peerIoGetTorrentHash( io ) );
3923
3924        tr_peerIoUnref( io ); /* balanced by the initial ref
3925                                 in tr_peerIoNewOutgoing() */
3926
3927        tr_ptrArrayInsertSorted( &t->outgoingHandshakes, handshake,
3928                                 handshakeCompare );
3929    }
3930
3931    atom->lastConnectionAttemptAt = now;
3932    atom->time = now;
3933}
3934
3935static void
3936initiateCandidateConnection( tr_peerMgr * mgr, struct peer_candidate * c )
3937{
3938#if 0
3939    fprintf( stderr, "Starting an OUTGOING connection with %s - [%s] seedProbability==%d; %s, %s\n",
3940             tr_atomAddrStr( c->atom ),
3941             tr_torrentName( c->tor ),
3942             (int)c->atom->seedProbability,
3943             tr_torrentIsPrivate( c->tor ) ? "private" : "public",
3944             tr_torrentIsSeed( c->tor ) ? "seed" : "downloader" );
3945#endif
3946
3947    initiateConnection( mgr, c->tor->torrentPeers, c->atom );
3948}
3949
3950static void
3951makeNewPeerConnections( struct tr_peerMgr * mgr, const int max )
3952{
3953    int i, n;
3954    struct peer_candidate * candidates;
3955
3956    candidates = getPeerCandidates( mgr->session, &n );
3957
3958    for( i=0; i<n && i<max; ++i )
3959        initiateCandidateConnection( mgr, &candidates[i] );
3960
3961    tr_free( candidates );
3962}
Note: See TracBrowser for help on using the repository browser.