source: trunk/libtransmission/peerutils.h @ 65

Last change on this file since 65 was 65, checked in by titer, 16 years ago

New choking algorithm (still needs work, it's inefficient, untested and
misses optimistic choking)

File size: 10.9 KB
Line 
1/******************************************************************************
2 * Copyright (c) 2005 Eric Petit
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
13 *
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
20 * DEALINGS IN THE SOFTWARE.
21 *****************************************************************************/
22
23static void updateInterest( tr_torrent_t * tor, tr_peer_t * peer );
24
25/***********************************************************************
26 * peerInit
27 ***********************************************************************
28 * Allocates a new tr_peer_t and returns a pointer to it.
29 **********************************************************************/
30static tr_peer_t * peerInit()
31{
32    tr_peer_t * peer;
33
34    peer              = calloc( sizeof( tr_peer_t ), 1 );
35    peer->amChoking   = 1;
36    peer->peerChoking = 1;
37    peer->date        = tr_date();
38    peer->keepAlive   = peer->date;
39    peer->download    = tr_rcInit();
40
41    return peer;
42}
43
44/***********************************************************************
45 * peerAttach
46 ***********************************************************************
47 * Deallocates the tr_peer_t and returns 0 if we reached the maximum
48 * authorized number of peers. Otherwise, adds the tr_peer_t to the
49 * peers list.
50 **********************************************************************/
51static int peerAttach( tr_torrent_t * tor, tr_peer_t * peer )
52{
53    if( tor->peerCount >= TR_MAX_PEER_COUNT )
54    {
55        tr_peerDestroy( tor->fdlimit, peer );
56        return 0;
57    }
58
59    tor->peers[tor->peerCount++] = peer;
60    return 1;
61}
62
63static int peerCmp( tr_peer_t * peer1, tr_peer_t * peer2 )
64{
65    /* Wait until we got the peers' ids */
66    if( peer1->status < PEER_STATUS_CONNECTED ||
67        peer2->status < PEER_STATUS_CONNECTED )
68    {
69        return 1;
70    }
71
72    return memcmp( peer1->id, peer2->id, 20 );
73}
74
75/***********************************************************************
76 * addWithAddr
77 ***********************************************************************
78 * Does nothing if we already have a peer matching 'addr' and 'port'.
79 * Otherwise adds such a new peer.
80 **********************************************************************/
81static void addWithAddr( tr_torrent_t * tor, struct in_addr addr,
82                         in_port_t port )
83{
84    int i;
85    tr_peer_t * peer;
86
87    for( i = 0; i < tor->peerCount; i++ )
88    {
89        peer = tor->peers[i];
90        if( peer->addr.s_addr == addr.s_addr &&
91            peer->port        == port )
92        {
93            /* We are already connected to this peer */
94            return;
95        }
96    }
97
98    peer = peerInit();
99    if( !peerAttach( tor, peer ) )
100    {
101        return;
102    }
103
104    peer->addr   = addr;
105    peer->port   = port;
106    peer->status = PEER_STATUS_IDLE;
107}
108
109static int checkPeer( tr_torrent_t * tor, int i )
110{
111    tr_peer_t * peer = tor->peers[i];
112
113    if( peer->status < PEER_STATUS_CONNECTED &&
114        tr_date() > peer->date + 8000 )
115    {
116        /* If it has been too long, don't wait for the socket
117           to timeout - forget about it now */
118        peer_dbg( "connection timeout" );
119        return 1;
120    }
121
122    /* Drop peers who haven't even sent a keep-alive within the
123       last 3 minutes */
124    if( tr_date() > peer->date + 180000 )
125    {
126        peer_dbg( "read timeout" );
127        return 1;
128    }
129
130    /* Drop peers which are supposed to upload but actually
131       haven't sent anything within the last minute */
132    if( peer->inRequestCount && tr_date() > peer->date + 60000 )
133    {
134        peer_dbg( "bad uploader" );
135        return 1;
136    }
137
138    if( peer->status & PEER_STATUS_CONNECTED )
139    {
140        /* Send keep-alive every 2 minutes */
141        if( tr_date() > peer->keepAlive + 120000 )
142        {
143            sendKeepAlive( peer );
144            peer->keepAlive = tr_date();
145        }
146    }
147
148    /* Connect */
149    if( ( peer->status & PEER_STATUS_IDLE ) &&
150        !tr_fdSocketWillCreate( tor->fdlimit, 0 ) )
151    {
152        peer->socket = tr_netOpen( peer->addr, peer->port );
153        if( peer->socket < 0 )
154        {
155            peer_dbg( "connection failed" );
156            tr_fdSocketClosed( tor->fdlimit, 0 );
157            return 1;
158        }
159        peer->status = PEER_STATUS_CONNECTING;
160    }
161
162    /* Try to send handshake */
163    if( peer->status & PEER_STATUS_CONNECTING )
164    {
165        uint8_t buf[68];
166        tr_info_t * inf = &tor->info;
167        int ret;
168
169        buf[0] = 19;
170        memcpy( &buf[1], "BitTorrent protocol", 19 );
171        memset( &buf[20], 0, 8 );
172        memcpy( &buf[28], inf->hash, 20 );
173        memcpy( &buf[48], tor->id, 20 );
174
175        ret = tr_netSend( peer->socket, buf, 68 );
176        if( ret & TR_NET_CLOSE )
177        {
178            peer_dbg( "connection closed" );
179            return 1;
180        }
181        else if( !( ret & TR_NET_BLOCK ) )
182        {
183            peer_dbg( "SEND handshake" );
184            peer->status = PEER_STATUS_HANDSHAKE;
185        }
186    }
187
188    return 0;
189}
190
191/***********************************************************************
192 * isInteresting
193 ***********************************************************************
194 * Returns 1 if 'peer' has at least one piece that we haven't completed,
195 * or 0 otherwise.
196 **********************************************************************/
197static int isInteresting( tr_torrent_t * tor, tr_peer_t * peer )
198{
199    tr_info_t * inf = &tor->info;
200
201    int i;
202    int bitfieldSize = ( inf->pieceCount + 7 ) / 8;
203    uint8_t * bitfield = tr_cpPieceBitfield( tor->completion );
204
205    if( !peer->bitfield )
206    {
207        /* We don't know what this peer has */
208        return 0;
209    }
210
211    for( i = 0; i < bitfieldSize; i++ )
212    {
213        if( ( peer->bitfield[i] & ~(bitfield[i]) ) & 0xFF )
214        {
215            return 1;
216        }
217    }
218
219    return 0;
220}
221static void updateInterest( tr_torrent_t * tor, tr_peer_t * peer )
222{
223    int interested = isInteresting( tor, peer );
224
225    if( interested && !peer->amInterested )
226    {
227        sendInterest( peer, 1 );
228    }
229    if( !interested && peer->amInterested )
230    {
231        sendInterest( peer, 0 );
232    }
233}
234
235/***********************************************************************
236 * chooseBlock
237 ***********************************************************************
238 * At this point, we know the peer has at least one block we have an
239 * interest in. If he has more than one, we choose which one we are
240 * going to ask first.
241 * Our main goal is to complete pieces, so we look the pieces which are
242 * missing less blocks.
243 **********************************************************************/
244static inline int chooseBlock( tr_torrent_t * tor, tr_peer_t * peer )
245{
246    tr_info_t * inf = &tor->info;
247
248    int i;
249    int missingBlocks, minMissing;
250    int poolSize, * pool;
251    int block, minDownloading;
252
253    /* Choose a piece */
254    pool       = malloc( inf->pieceCount * sizeof( int ) );
255    poolSize   = 0;
256    minMissing = tor->blockCount + 1;
257    for( i = 0; i < inf->pieceCount; i++ )
258    {
259        missingBlocks = tr_cpMissingBlocksForPiece( tor->completion, i );
260        if( missingBlocks < 1 )
261        {
262            /* We already have or are downloading all blocks */
263            continue;
264        }
265        if( !tr_bitfieldHas( peer->bitfield, i ) )
266        {
267            /* The peer doesn't have this piece */
268            continue;
269        }
270
271        /* We are interested in this piece, remember it */
272        if( missingBlocks < minMissing )
273        {
274            minMissing = missingBlocks;
275            poolSize   = 0;
276        }
277        if( missingBlocks <= minMissing )
278        {
279            pool[poolSize++] = i;
280        }
281    }
282
283    if( poolSize )
284    {
285        /* All pieces in 'pool' have 'minMissing' missing blocks. Find
286           the rarest ones. */
287        uint8_t * bitfield;
288        int piece;
289        int min, foo, j;
290        int * pool2;
291        int   pool2Size;
292
293        pool2     = malloc( poolSize * sizeof( int ) );
294        pool2Size = 0;
295        min       = TR_MAX_PEER_COUNT + 1;
296        for( i = 0; i < poolSize; i++ )
297        {
298            foo = 0;
299            for( j = 0; j < tor->peerCount; j++ )
300            {
301                bitfield = tor->peers[j]->bitfield;
302                if( bitfield && tr_bitfieldHas( bitfield, pool[i] ) )
303                {
304                    foo++;
305                }
306            }
307            if( foo < min )
308            {
309                min       = foo;
310                pool2Size = 0;
311            }
312            if( foo <= min )
313            {
314                pool2[pool2Size++] = pool[i];
315            }
316        }
317        free( pool );
318
319        if( pool2Size < 1 )
320        {
321            /* Shouldn't happen */
322            free( pool2 );
323            return -1;
324        }
325
326        /* All pieces in pool2 have the same number of missing blocks,
327           and are availabme from the same number of peers. Pick a
328           random one */
329        piece = pool2[tr_rand(pool2Size)];
330        free( pool2 );
331
332        /* Pick a block in this piece */
333        block = tr_cpMissingBlockInPiece( tor->completion, piece );
334        goto check;
335    }
336
337    free( pool );
338
339    /* "End game" mode */
340    minDownloading = 255;
341    block = -1;
342    for( i = 0; i < inf->pieceCount; i++ )
343    {
344        int downloaders, block2;
345        if( !tr_bitfieldHas( peer->bitfield, i ) )
346        {
347            /* The peer doesn't have this piece */
348            continue;
349        }
350        if( tr_cpPieceIsComplete( tor->completion, i ) )
351        {
352            /* We already have it */
353            continue;
354        }
355        block2 = tr_cpMostMissingBlockInPiece( tor->completion, i, &downloaders );
356        if( block2 > -1 && downloaders < minDownloading )
357        {
358            block = block2;
359            minDownloading = downloaders;
360        }
361    }
362
363check:
364    if( block < 0 )
365    {
366        /* Shouldn't happen */
367        return -1;
368    }
369
370    for( i = 0; i < peer->inRequestCount; i++ )
371    {
372        tr_request_t * r;
373        r = &peer->inRequests[i];
374        if( tr_block( r->index, r->begin ) == block )
375        {
376            /* We are already asking this peer for this block */
377            return -1;
378        }
379    }
380
381    return block;
382}
Note: See TracBrowser for help on using the repository browser.