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

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

(trunk) #4138 "use stdbool.h instead of tr_bool" -- done.

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