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

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

(trunk libT) use aggregation for the tr_bandwidth objects owned by tr_session and tr_torrent

  • 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 12280 2011-03-31 14:53:22Z 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            rechokeUploads( tor->torrentPeers, now );
3160            if( !tr_torrentIsSeed( tor ) )
3161                rechokeDownloads( tor->torrentPeers );
3162        }
3163    }
3164
3165    tr_timerAddMsec( mgr->rechokeTimer, RECHOKE_PERIOD_MSEC );
3166    managerUnlock( mgr );
3167}
3168
3169/***
3170****
3171****  Life and Death
3172****
3173***/
3174
3175static bool
3176shouldPeerBeClosed( const Torrent    * t,
3177                    const tr_peer    * peer,
3178                    int                peerCount,
3179                    const time_t       now )
3180{
3181    const tr_torrent *       tor = t->tor;
3182    const struct peer_atom * atom = peer->atom;
3183
3184    /* if it's marked for purging, close it */
3185    if( peer->doPurge )
3186    {
3187        tordbg( t, "purging peer %s because its doPurge flag is set",
3188                tr_atomAddrStr( atom ) );
3189        return true;
3190    }
3191
3192    /* disconnect if we're both seeds and enough time has passed for PEX */
3193    if( tr_torrentIsSeed( tor ) && peerIsSeed( peer ) )
3194        return !tr_torrentAllowsPex(tor) || (now-atom->time>=30);
3195
3196    /* disconnect if it's been too long since piece data has been transferred.
3197     * this is on a sliding scale based on number of available peers... */
3198    {
3199        const int relaxStrictnessIfFewerThanN = (int)( ( getMaxPeerCount( tor ) * 0.9 ) + 0.5 );
3200        /* if we have >= relaxIfFewerThan, strictness is 100%.
3201         * if we have zero connections, strictness is 0% */
3202        const float strictness = peerCount >= relaxStrictnessIfFewerThanN
3203                               ? 1.0
3204                               : peerCount / (float)relaxStrictnessIfFewerThanN;
3205        const int lo = MIN_UPLOAD_IDLE_SECS;
3206        const int hi = MAX_UPLOAD_IDLE_SECS;
3207        const int limit = hi - ( ( hi - lo ) * strictness );
3208        const int idleTime = now - MAX( atom->time, atom->piece_data_time );
3209/*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 );*/
3210        if( idleTime > limit ) {
3211            tordbg( t, "purging peer %s because it's been %d secs since we shared anything",
3212                       tr_atomAddrStr( atom ), idleTime );
3213            return true;
3214        }
3215    }
3216
3217    return false;
3218}
3219
3220static tr_peer **
3221getPeersToClose( Torrent * t, const time_t now_sec, int * setmeSize )
3222{
3223    int i, peerCount, outsize;
3224    tr_peer ** peers = (tr_peer**) tr_ptrArrayPeek( &t->peers, &peerCount );
3225    struct tr_peer ** ret = tr_new( tr_peer *, peerCount );
3226
3227    assert( torrentIsLocked( t ) );
3228
3229    for( i = outsize = 0; i < peerCount; ++i )
3230        if( shouldPeerBeClosed( t, peers[i], peerCount, now_sec ) )
3231            ret[outsize++] = peers[i];
3232
3233    *setmeSize = outsize;
3234    return ret;
3235}
3236
3237static int
3238getReconnectIntervalSecs( const struct peer_atom * atom, const time_t now )
3239{
3240    int sec;
3241
3242    /* if we were recently connected to this peer and transferring piece
3243     * data, try to reconnect to them sooner rather that later -- we don't
3244     * want network troubles to get in the way of a good peer. */
3245    if( ( now - atom->piece_data_time ) <= ( MINIMUM_RECONNECT_INTERVAL_SECS * 2 ) )
3246        sec = MINIMUM_RECONNECT_INTERVAL_SECS;
3247
3248    /* don't allow reconnects more often than our minimum */
3249    else if( ( now - atom->time ) < MINIMUM_RECONNECT_INTERVAL_SECS )
3250        sec = MINIMUM_RECONNECT_INTERVAL_SECS;
3251
3252    /* otherwise, the interval depends on how many times we've tried
3253     * and failed to connect to the peer */
3254    else switch( atom->numFails ) {
3255        case 0: sec = 0; break;
3256        case 1: sec = 5; break;
3257        case 2: sec = 2 * 60; break;
3258        case 3: sec = 15 * 60; break;
3259        case 4: sec = 30 * 60; break;
3260        case 5: sec = 60 * 60; break;
3261        default: sec = 120 * 60; break;
3262    }
3263
3264    /* penalize peers that were unreachable the last time we tried */
3265    if( atom->flags2 & MYFLAG_UNREACHABLE )
3266        sec += sec;
3267
3268    dbgmsg( "reconnect interval for %s is %d seconds", tr_atomAddrStr( atom ), sec );
3269    return sec;
3270}
3271
3272static void
3273removePeer( Torrent * t, tr_peer * peer )
3274{
3275    tr_peer * removed;
3276    struct peer_atom * atom = peer->atom;
3277
3278    assert( torrentIsLocked( t ) );
3279    assert( atom );
3280
3281    atom->time = tr_time( );
3282
3283    removed = tr_ptrArrayRemoveSorted( &t->peers, peer, peerCompare );
3284
3285    if( replicationExists( t ) )
3286        tr_decrReplicationFromBitfield( t, &peer->have );
3287
3288    assert( removed == peer );
3289    peerDelete( t, removed );
3290}
3291
3292static void
3293closePeer( Torrent * t, tr_peer * peer )
3294{
3295    struct peer_atom * atom;
3296
3297    assert( t != NULL );
3298    assert( peer != NULL );
3299
3300    atom = peer->atom;
3301
3302    /* if we transferred piece data, then they might be good peers,
3303       so reset their `numFails' weight to zero. otherwise we connected
3304       to them fruitlessly, so mark it as another fail */
3305    if( atom->piece_data_time ) {
3306        tordbg( t, "resetting atom %s numFails to 0", tr_atomAddrStr(atom) );
3307        atom->numFails = 0;
3308    } else {
3309        ++atom->numFails;
3310        tordbg( t, "incremented atom %s numFails to %d", tr_atomAddrStr(atom), (int)atom->numFails );
3311    }
3312
3313    tordbg( t, "removing bad peer %s", tr_peerIoGetAddrStr( peer->io ) );
3314    removePeer( t, peer );
3315}
3316
3317static void
3318removeAllPeers( Torrent * t )
3319{
3320    while( !tr_ptrArrayEmpty( &t->peers ) )
3321        removePeer( t, tr_ptrArrayNth( &t->peers, 0 ) );
3322}
3323
3324static void
3325closeBadPeers( Torrent * t, const time_t now_sec )
3326{
3327    int i;
3328    int peerCount;
3329    struct tr_peer ** peers = getPeersToClose( t, now_sec, &peerCount );
3330    for( i=0; i<peerCount; ++i )
3331        closePeer( t, peers[i] );
3332    tr_free( peers );
3333}
3334
3335struct peer_liveliness
3336{
3337    tr_peer * peer;
3338    void * clientData;
3339    time_t pieceDataTime;
3340    time_t time;
3341    int speed;
3342    bool doPurge;
3343};
3344
3345static int
3346comparePeerLiveliness( const void * va, const void * vb )
3347{
3348    const struct peer_liveliness * a = va;
3349    const struct peer_liveliness * b = vb;
3350
3351    if( a->doPurge != b->doPurge )
3352        return a->doPurge ? 1 : -1;
3353
3354    if( a->speed != b->speed ) /* faster goes first */
3355        return a->speed > b->speed ? -1 : 1;
3356
3357    /* the one to give us data more recently goes first */
3358    if( a->pieceDataTime != b->pieceDataTime )
3359        return a->pieceDataTime > b->pieceDataTime ? -1 : 1;
3360
3361    /* the one we connected to most recently goes first */
3362    if( a->time != b->time )
3363        return a->time > b->time ? -1 : 1;
3364
3365    return 0;
3366}
3367
3368static void
3369sortPeersByLivelinessImpl( tr_peer  ** peers,
3370                           void     ** clientData,
3371                           int         n,
3372                           uint64_t    now,
3373                           int (*compare) ( const void *va, const void *vb ) )
3374{
3375    int i;
3376    struct peer_liveliness *lives, *l;
3377
3378    /* build a sortable array of peer + extra info */
3379    lives = l = tr_new0( struct peer_liveliness, n );
3380    for( i=0; i<n; ++i, ++l )
3381    {
3382        tr_peer * p = peers[i];
3383        l->peer = p;
3384        l->doPurge = p->doPurge;
3385        l->pieceDataTime = p->atom->piece_data_time;
3386        l->time = p->atom->time;
3387        l->speed = tr_peerGetPieceSpeed_Bps( p, now, TR_UP )
3388                 + tr_peerGetPieceSpeed_Bps( p, now, TR_DOWN );
3389        if( clientData )
3390            l->clientData = clientData[i];
3391    }
3392
3393    /* sort 'em */
3394    assert( n == ( l - lives ) );
3395    qsort( lives, n, sizeof( struct peer_liveliness ), compare );
3396
3397    /* build the peer array */
3398    for( i=0, l=lives; i<n; ++i, ++l ) {
3399        peers[i] = l->peer;
3400        if( clientData )
3401            clientData[i] = l->clientData;
3402    }
3403    assert( n == ( l - lives ) );
3404
3405    /* cleanup */
3406    tr_free( lives );
3407}
3408
3409static void
3410sortPeersByLiveliness( tr_peer ** peers, void ** clientData, int n, uint64_t now )
3411{
3412    sortPeersByLivelinessImpl( peers, clientData, n, now, comparePeerLiveliness );
3413}
3414
3415
3416static void
3417enforceTorrentPeerLimit( Torrent * t, uint64_t now )
3418{
3419    int n = tr_ptrArraySize( &t->peers );
3420    const int max = tr_torrentGetPeerLimit( t->tor );
3421    if( n > max )
3422    {
3423        void * base = tr_ptrArrayBase( &t->peers );
3424        tr_peer ** peers = tr_memdup( base, n*sizeof( tr_peer* ) );
3425        sortPeersByLiveliness( peers, NULL, n, now );
3426        while( n > max )
3427            closePeer( t, peers[--n] );
3428        tr_free( peers );
3429    }
3430}
3431
3432static void
3433enforceSessionPeerLimit( tr_session * session, uint64_t now )
3434{
3435    int n = 0;
3436    tr_torrent * tor = NULL;
3437    const int max = tr_sessionGetPeerLimit( session );
3438
3439    /* count the total number of peers */
3440    while(( tor = tr_torrentNext( session, tor )))
3441        n += tr_ptrArraySize( &tor->torrentPeers->peers );
3442
3443    /* if there are too many, prune out the worst */
3444    if( n > max )
3445    {
3446        tr_peer ** peers = tr_new( tr_peer*, n );
3447        Torrent ** torrents = tr_new( Torrent*, n );
3448
3449        /* populate the peer array */
3450        n = 0;
3451        tor = NULL;
3452        while(( tor = tr_torrentNext( session, tor ))) {
3453            int i;
3454            Torrent * t = tor->torrentPeers;
3455            const int tn = tr_ptrArraySize( &t->peers );
3456            for( i=0; i<tn; ++i, ++n ) {
3457                peers[n] = tr_ptrArrayNth( &t->peers, i );
3458                torrents[n] = t;
3459            }
3460        }
3461
3462        /* sort 'em */
3463        sortPeersByLiveliness( peers, (void**)torrents, n, now );
3464
3465        /* cull out the crappiest */
3466        while( n-- > max )
3467            closePeer( torrents[n], peers[n] );
3468
3469        /* cleanup */
3470        tr_free( torrents );
3471        tr_free( peers );
3472    }
3473}
3474
3475static void makeNewPeerConnections( tr_peerMgr * mgr, const int max );
3476
3477static void
3478reconnectPulse( int foo UNUSED, short bar UNUSED, void * vmgr )
3479{
3480    tr_torrent * tor;
3481    tr_peerMgr * mgr = vmgr;
3482    const time_t now_sec = tr_time( );
3483    const uint64_t now_msec = tr_time_msec( );
3484
3485    /**
3486    ***  enforce the per-session and per-torrent peer limits
3487    **/
3488
3489    /* if we're over the per-torrent peer limits, cull some peers */
3490    tor = NULL;
3491    while(( tor = tr_torrentNext( mgr->session, tor )))
3492        if( tor->isRunning )
3493            enforceTorrentPeerLimit( tor->torrentPeers, now_msec );
3494
3495    /* if we're over the per-session peer limits, cull some peers */
3496    enforceSessionPeerLimit( mgr->session, now_msec );
3497
3498    /* remove crappy peers */
3499    tor = NULL;
3500    while(( tor = tr_torrentNext( mgr->session, tor )))
3501        if( !tor->torrentPeers->isRunning )
3502            removeAllPeers( tor->torrentPeers );
3503        else
3504            closeBadPeers( tor->torrentPeers, now_sec );
3505
3506    /* try to make new peer connections */
3507    makeNewPeerConnections( mgr, MAX_CONNECTIONS_PER_PULSE );
3508}
3509
3510/****
3511*****
3512*****  BANDWIDTH ALLOCATION
3513*****
3514****/
3515
3516static void
3517pumpAllPeers( tr_peerMgr * mgr )
3518{
3519    tr_torrent * tor = NULL;
3520
3521    while(( tor = tr_torrentNext( mgr->session, tor )))
3522    {
3523        int j;
3524        Torrent * t = tor->torrentPeers;
3525
3526        for( j=0; j<tr_ptrArraySize( &t->peers ); ++j )
3527        {
3528            tr_peer * peer = tr_ptrArrayNth( &t->peers, j );
3529            tr_peerMsgsPulse( peer->msgs );
3530        }
3531    }
3532}
3533
3534static void
3535bandwidthPulse( int foo UNUSED, short bar UNUSED, void * vmgr )
3536{
3537    tr_torrent * tor;
3538    tr_peerMgr * mgr = vmgr;
3539    managerLock( mgr );
3540
3541    /* FIXME: this next line probably isn't necessary... */
3542    pumpAllPeers( mgr );
3543
3544    /* allocate bandwidth to the peers */
3545    tr_bandwidthAllocate( &mgr->session->bandwidth, TR_UP, BANDWIDTH_PERIOD_MSEC );
3546    tr_bandwidthAllocate( &mgr->session->bandwidth, TR_DOWN, BANDWIDTH_PERIOD_MSEC );
3547
3548    /* possibly stop torrents that have seeded enough */
3549    tor = NULL;
3550    while(( tor = tr_torrentNext( mgr->session, tor )))
3551        tr_torrentCheckSeedLimit( tor );
3552
3553    /* run the completeness check for any torrents that need it */
3554    tor = NULL;
3555    while(( tor = tr_torrentNext( mgr->session, tor ))) {
3556        if( tor->torrentPeers->needsCompletenessCheck ) {
3557            tor->torrentPeers->needsCompletenessCheck  = false;
3558            tr_torrentRecheckCompleteness( tor );
3559        }
3560    }
3561
3562    /* stop torrents that are ready to stop, but couldn't be stopped earlier
3563     * during the peer-io callback call chain */
3564    tor = NULL;
3565    while(( tor = tr_torrentNext( mgr->session, tor )))
3566        if( tor->isStopping )
3567            tr_torrentStop( tor );
3568
3569    reconnectPulse( 0, 0, mgr );
3570
3571    tr_timerAddMsec( mgr->bandwidthTimer, BANDWIDTH_PERIOD_MSEC );
3572    managerUnlock( mgr );
3573}
3574
3575/***
3576****
3577***/
3578
3579static int
3580compareAtomPtrsByAddress( const void * va, const void *vb )
3581{
3582    const struct peer_atom * a = * (const struct peer_atom**) va;
3583    const struct peer_atom * b = * (const struct peer_atom**) vb;
3584
3585    assert( tr_isAtom( a ) );
3586    assert( tr_isAtom( b ) );
3587
3588    return tr_address_compare( &a->addr, &b->addr );
3589}
3590
3591/* best come first, worst go last */
3592static int
3593compareAtomPtrsByShelfDate( const void * va, const void *vb )
3594{
3595    time_t atime;
3596    time_t btime;
3597    const struct peer_atom * a = * (const struct peer_atom**) va;
3598    const struct peer_atom * b = * (const struct peer_atom**) vb;
3599    const int data_time_cutoff_secs = 60 * 60;
3600    const time_t tr_now = tr_time( );
3601
3602    assert( tr_isAtom( a ) );
3603    assert( tr_isAtom( b ) );
3604
3605    /* primary key: the last piece data time *if* it was within the last hour */
3606    atime = a->piece_data_time; if( atime + data_time_cutoff_secs < tr_now ) atime = 0;
3607    btime = b->piece_data_time; if( btime + data_time_cutoff_secs < tr_now ) btime = 0;
3608    if( atime != btime )
3609        return atime > btime ? -1 : 1;
3610
3611    /* secondary key: shelf date. */
3612    if( a->shelf_date != b->shelf_date )
3613        return a->shelf_date > b->shelf_date ? -1 : 1;
3614
3615    return 0;
3616}
3617
3618static int
3619getMaxAtomCount( const tr_torrent * tor )
3620{
3621    const int n = tor->maxConnectedPeers;
3622    /* approximate fit of the old jump discontinuous function */
3623    if( n >= 55 ) return     n + 150;
3624    if( n >= 20 ) return 2 * n + 95;
3625    return               4 * n + 55;
3626}
3627
3628static void
3629atomPulse( int foo UNUSED, short bar UNUSED, void * vmgr )
3630{
3631    tr_torrent * tor = NULL;
3632    tr_peerMgr * mgr = vmgr;
3633    managerLock( mgr );
3634
3635    while(( tor = tr_torrentNext( mgr->session, tor )))
3636    {
3637        int atomCount;
3638        Torrent * t = tor->torrentPeers;
3639        const int maxAtomCount = getMaxAtomCount( tor );
3640        struct peer_atom ** atoms = (struct peer_atom**) tr_ptrArrayPeek( &t->pool, &atomCount );
3641
3642        if( atomCount > maxAtomCount ) /* we've got too many atoms... time to prune */
3643        {
3644            int i;
3645            int keepCount = 0;
3646            int testCount = 0;
3647            struct peer_atom ** keep = tr_new( struct peer_atom*, atomCount );
3648            struct peer_atom ** test = tr_new( struct peer_atom*, atomCount );
3649
3650            /* keep the ones that are in use */
3651            for( i=0; i<atomCount; ++i ) {
3652                struct peer_atom * atom = atoms[i];
3653                if( peerIsInUse( t, atom ) )
3654                    keep[keepCount++] = atom;
3655                else
3656                    test[testCount++] = atom;
3657            }
3658
3659            /* if there's room, keep the best of what's left */
3660            i = 0;
3661            if( keepCount < maxAtomCount ) {
3662                qsort( test, testCount, sizeof( struct peer_atom * ), compareAtomPtrsByShelfDate );
3663                while( i<testCount && keepCount<maxAtomCount )
3664                    keep[keepCount++] = test[i++];
3665            }
3666
3667            /* free the culled atoms */
3668            while( i<testCount )
3669                tr_free( test[i++] );
3670
3671            /* rebuild Torrent.pool with what's left */
3672            tr_ptrArrayDestruct( &t->pool, NULL );
3673            t->pool = TR_PTR_ARRAY_INIT;
3674            qsort( keep, keepCount, sizeof( struct peer_atom * ), compareAtomPtrsByAddress );
3675            for( i=0; i<keepCount; ++i )
3676                tr_ptrArrayAppend( &t->pool, keep[i] );
3677
3678            tordbg( t, "max atom count is %d... pruned from %d to %d\n", maxAtomCount, atomCount, keepCount );
3679
3680            /* cleanup */
3681            tr_free( test );
3682            tr_free( keep );
3683        }
3684    }
3685
3686    tr_timerAddMsec( mgr->atomTimer, ATOM_PERIOD_MSEC );
3687    managerUnlock( mgr );
3688}
3689
3690/***
3691****
3692****
3693****
3694***/
3695
3696/* is this atom someone that we'd want to initiate a connection to? */
3697static bool
3698isPeerCandidate( const tr_torrent * tor, struct peer_atom * atom, const time_t now )
3699{
3700    /* not if we're both seeds */
3701    if( tr_torrentIsSeed( tor ) && atomIsSeed( atom ) )
3702        return false;
3703
3704    /* not if we've already got a connection to them... */
3705    if( peerIsInUse( tor->torrentPeers, atom ) )
3706        return false;
3707
3708    /* not if we just tried them already */
3709    if( ( now - atom->time ) < getReconnectIntervalSecs( atom, now ) )
3710        return false;
3711
3712    /* not if they're blocklisted */
3713    if( isAtomBlocklisted( tor->session, atom ) )
3714        return false;
3715
3716    /* not if they're banned... */
3717    if( atom->flags2 & MYFLAG_BANNED )
3718        return false;
3719
3720    return true;
3721}
3722
3723struct peer_candidate
3724{
3725    uint64_t score;
3726    tr_torrent * tor;
3727    struct peer_atom * atom;
3728};
3729
3730static bool
3731torrentWasRecentlyStarted( const tr_torrent * tor )
3732{
3733    return difftime( tr_time( ), tor->startDate ) < 120;
3734}
3735
3736static inline uint64_t
3737addValToKey( uint64_t value, int width, uint64_t addme )
3738{
3739    value = (value << (uint64_t)width);
3740    value |= addme;
3741    return value;
3742}
3743
3744/* smaller value is better */
3745static uint64_t
3746getPeerCandidateScore( const tr_torrent * tor, const struct peer_atom * atom, uint8_t salt  )
3747{
3748    uint64_t i;
3749    uint64_t score = 0;
3750    const bool failed = atom->lastConnectionAt < atom->lastConnectionAttemptAt;
3751
3752    /* prefer peers we've connected to, or never tried, over peers we failed to connect to. */
3753    i = failed ? 1 : 0;
3754    score = addValToKey( score, 1, i );
3755
3756    /* prefer the one we attempted least recently (to cycle through all peers) */
3757    i = atom->lastConnectionAttemptAt;
3758    score = addValToKey( score, 32, i );
3759
3760    /* prefer peers belonging to a torrent of a higher priority */
3761    switch( tr_torrentGetPriority( tor ) ) {
3762        case TR_PRI_HIGH:    i = 0; break;
3763        case TR_PRI_NORMAL:  i = 1; break;
3764        case TR_PRI_LOW:     i = 2; break;
3765    }
3766    score = addValToKey( score, 4, i );
3767
3768    /* prefer recently-started torrents */
3769    i = torrentWasRecentlyStarted( tor ) ? 0 : 1;
3770    score = addValToKey( score, 1, i );
3771
3772    /* prefer torrents we're downloading with */
3773    i = tr_torrentIsSeed( tor ) ? 1 : 0;
3774    score = addValToKey( score, 1, i );
3775
3776    /* prefer peers that are known to be connectible */
3777    i = ( atom->flags & ADDED_F_CONNECTABLE ) ? 0 : 1;
3778    score = addValToKey( score, 1, i );
3779
3780    /* prefer peers that we might have a chance of uploading to...
3781       so lower seed probability is better */
3782    if( atom->seedProbability == 100 ) i = 101;
3783    else if( atom->seedProbability == -1 ) i = 100;
3784    else i = atom->seedProbability;
3785    score = addValToKey( score, 8, i );
3786
3787    /* Prefer peers that we got from more trusted sources.
3788     * lower `fromBest' values indicate more trusted sources */
3789    score = addValToKey( score, 4, atom->fromBest );
3790
3791    /* salt */
3792    score = addValToKey( score, 8, salt );
3793
3794    return score;
3795}
3796
3797/* sort an array of peer candidates */
3798static int
3799comparePeerCandidates( const void * va, const void * vb )
3800{
3801    const struct peer_candidate * a = va;
3802    const struct peer_candidate * b = vb;
3803
3804    if( a->score < b->score ) return -1;
3805    if( a->score > b->score ) return 1;
3806
3807    return 0;
3808}
3809
3810/** @return an array of all the atoms we might want to connect to */
3811static struct peer_candidate*
3812getPeerCandidates( tr_session * session, int * candidateCount )
3813{
3814    int n;
3815    tr_torrent * tor;
3816    struct peer_candidate * candidates;
3817    struct peer_candidate * walk;
3818    const time_t now = tr_time( );
3819    const uint64_t now_msec = tr_time_msec( );
3820    /* leave 5% of connection slots for incoming connections -- ticket #2609 */
3821    const int maxCandidates = tr_sessionGetPeerLimit( session ) * 0.95;
3822
3823    /* don't start any new handshakes if we're full up */
3824    n = 0;
3825    tor= NULL;
3826    while(( tor = tr_torrentNext( session, tor )))
3827        n += tr_ptrArraySize( &tor->torrentPeers->peers );
3828    if( maxCandidates <= n ) {
3829        *candidateCount = 0;
3830        return NULL;
3831    }
3832
3833    /* allocate an array of candidates */
3834    n = 0;
3835    tor= NULL;
3836    while(( tor = tr_torrentNext( session, tor )))
3837        n += tr_ptrArraySize( &tor->torrentPeers->pool );
3838    walk = candidates = tr_new( struct peer_candidate, n );
3839
3840    /* populate the candidate array */
3841    tor = NULL;
3842    while(( tor = tr_torrentNext( session, tor )))
3843    {
3844        int i, nAtoms;
3845        struct peer_atom ** atoms;
3846
3847        if( !tor->torrentPeers->isRunning )
3848            continue;
3849
3850        /* if we've already got enough peers in this torrent... */
3851        if( tr_torrentGetPeerLimit( tor ) <= tr_ptrArraySize( &tor->torrentPeers->peers ) )
3852            continue;
3853
3854        /* if we've already got enough speed in this torrent... */
3855        if( tr_torrentIsSeed( tor ) && isBandwidthMaxedOut( &tor->bandwidth, now_msec, TR_UP ) )
3856            continue;
3857
3858        atoms = (struct peer_atom**) tr_ptrArrayPeek( &tor->torrentPeers->pool, &nAtoms );
3859        for( i=0; i<nAtoms; ++i )
3860        {
3861            struct peer_atom * atom = atoms[i];
3862
3863            if( isPeerCandidate( tor, atom, now ) )
3864            {
3865                const uint8_t salt = tr_cryptoWeakRandInt( 1024 );
3866                walk->tor = tor;
3867                walk->atom = atom;
3868                walk->score = getPeerCandidateScore( tor, atom, salt );
3869                ++walk;
3870            }
3871        }
3872    }
3873
3874    *candidateCount = walk - candidates;
3875    if( *candidateCount > 1 )
3876        qsort( candidates, *candidateCount, sizeof( struct peer_candidate ), comparePeerCandidates );
3877    return candidates;
3878}
3879
3880static void
3881initiateConnection( tr_peerMgr * mgr, Torrent * t, struct peer_atom * atom )
3882{
3883    tr_peerIo * io;
3884    const time_t now = tr_time( );
3885    bool utp = tr_sessionIsUTPEnabled(mgr->session) && !atom->utp_failed;
3886
3887    if( atom->fromFirst == TR_PEER_FROM_PEX )
3888        /* PEX has explicit signalling for uTP support.  If an atom
3889           originally came from PEX and doesn't have the uTP flag, skip the
3890           uTP connection attempt.  Are we being optimistic here? */
3891        utp = utp && (atom->flags & ADDED_F_UTP_FLAGS);
3892
3893    tordbg( t, "Starting an OUTGOING%s connection with %s",
3894            utp ? " µTP" : "",
3895            tr_atomAddrStr( atom ) );
3896
3897    io = tr_peerIoNewOutgoing( mgr->session,
3898                               &mgr->session->bandwidth,
3899                               &atom->addr,
3900                               atom->port,
3901                               t->tor->info.hash,
3902                               t->tor->completeness == TR_SEED,
3903                               utp );
3904
3905    if( io == NULL )
3906    {
3907        tordbg( t, "peerIo not created; marking peer %s as unreachable",
3908                tr_atomAddrStr( atom ) );
3909        atom->flags2 |= MYFLAG_UNREACHABLE;
3910        atom->numFails++;
3911    }
3912    else
3913    {
3914        tr_handshake * handshake = tr_handshakeNew( io,
3915                                                    mgr->session->encryptionMode,
3916                                                    myHandshakeDoneCB,
3917                                                    mgr );
3918
3919        assert( tr_peerIoGetTorrentHash( io ) );
3920
3921        tr_peerIoUnref( io ); /* balanced by the initial ref
3922                                 in tr_peerIoNewOutgoing() */
3923
3924        tr_ptrArrayInsertSorted( &t->outgoingHandshakes, handshake,
3925                                 handshakeCompare );
3926    }
3927
3928    atom->lastConnectionAttemptAt = now;
3929    atom->time = now;
3930}
3931
3932static void
3933initiateCandidateConnection( tr_peerMgr * mgr, struct peer_candidate * c )
3934{
3935#if 0
3936    fprintf( stderr, "Starting an OUTGOING connection with %s - [%s] seedProbability==%d; %s, %s\n",
3937             tr_atomAddrStr( c->atom ),
3938             tr_torrentName( c->tor ),
3939             (int)c->atom->seedProbability,
3940             tr_torrentIsPrivate( c->tor ) ? "private" : "public",
3941             tr_torrentIsSeed( c->tor ) ? "seed" : "downloader" );
3942#endif
3943
3944    initiateConnection( mgr, c->tor->torrentPeers, c->atom );
3945}
3946
3947static void
3948makeNewPeerConnections( struct tr_peerMgr * mgr, const int max )
3949{
3950    int i, n;
3951    struct peer_candidate * candidates;
3952
3953    candidates = getPeerCandidates( mgr->session, &n );
3954
3955    for( i=0; i<n && i<max; ++i )
3956        initiateCandidateConnection( mgr, &candidates[i] );
3957
3958    tr_free( candidates );
3959}
Note: See TracBrowser for help on using the repository browser.