source: trunk/libtransmission/peerutils.h @ 1534

Last change on this file since 1534 was 1534, checked in by joshe, 15 years ago

Do bounds checking on bitfields.

  • Property svn:keywords set to Date Rev Author Id
File size: 8.7 KB
Line 
1/******************************************************************************
2 * $Id: peerutils.h 1534 2007-03-05 23:03:38Z joshe $
3 *
4 * Copyright (c) 2005-2006 Transmission authors and contributors
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a
7 * copy of this software and associated documentation files (the "Software"),
8 * to deal in the Software without restriction, including without limitation
9 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
10 * and/or sell copies of the Software, and to permit persons to whom the
11 * Software is furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be included in
14 * all copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
22 * DEALINGS IN THE SOFTWARE.
23 *****************************************************************************/
24
25static void updateInterest( tr_torrent_t * tor, tr_peer_t * peer );
26
27/***********************************************************************
28 * peerInit
29 ***********************************************************************
30 * Allocates a new tr_peer_t and returns a pointer to it.
31 **********************************************************************/
32static tr_peer_t * peerInit()
33{
34    tr_peer_t * peer;
35
36    peer              = calloc( sizeof( tr_peer_t ), 1 );
37    peer->amChoking   = 1;
38    peer->peerChoking = 1;
39    peer->date        = tr_date();
40    peer->keepAlive   = peer->date;
41    peer->download    = tr_rcInit();
42    peer->upload      = tr_rcInit();
43
44    return peer;
45}
46
47static int peerCmp( tr_peer_t * peer1, tr_peer_t * peer2 )
48{
49    /* Wait until we got the peers' ids */
50    if( peer1->status < PEER_STATUS_CONNECTED ||
51        peer2->status < PEER_STATUS_CONNECTED )
52    {
53        return 1;
54    }
55
56    return memcmp( peer1->id, peer2->id, 20 );
57}
58
59static int checkPeer( tr_peer_t * peer )
60{
61    if( peer->status < PEER_STATUS_CONNECTED &&
62        tr_date() > peer->date + 8000 )
63    {
64        /* If it has been too long, don't wait for the socket
65           to timeout - forget about it now */
66        peer_dbg( "connection timeout" );
67        return TR_ERROR;
68    }
69
70    /* Drop peers who haven't even sent a keep-alive within the
71       last 3 minutes */
72    if( tr_date() > peer->date + 180000 )
73    {
74        peer_dbg( "read timeout" );
75        return TR_ERROR;
76    }
77
78    /* Drop peers which are supposed to upload but actually
79       haven't sent anything within the last minute */
80    if( peer->inRequestCount && tr_date() > peer->date + 60000 )
81    {
82        peer_dbg( "bad uploader" );
83        return TR_ERROR;
84    }
85
86    if( peer->status & PEER_STATUS_CONNECTED )
87    {
88        /* Send keep-alive every 2 minutes */
89        if( tr_date() > peer->keepAlive + 120000 )
90        {
91            sendKeepAlive( peer );
92            peer->keepAlive = tr_date();
93        }
94    }
95
96    return TR_OK;
97}
98
99/***********************************************************************
100 * isInteresting
101 ***********************************************************************
102 * Returns 1 if 'peer' has at least one piece that we haven't completed,
103 * or 0 otherwise.
104 **********************************************************************/
105static int isInteresting( tr_torrent_t * tor, tr_peer_t * peer )
106{
107    int ii;
108    tr_bitfield_t * bitfield = tr_cpPieceBitfield( tor->completion );
109
110    if( !peer->bitfield )
111    {
112        /* We don't know what this peer has */
113        return 0;
114    }
115
116    assert( bitfield->len == peer->bitfield->len );
117    for( ii = 0; ii < bitfield->len; ii++ )
118    {
119        if( ( peer->bitfield->bits[ii] & ~(bitfield->bits[ii]) ) & 0xFF )
120        {
121            return 1;
122        }
123    }
124
125    return 0;
126}
127static void updateInterest( tr_torrent_t * tor, tr_peer_t * peer )
128{
129    int interested = isInteresting( tor, peer );
130
131    if( interested && !peer->amInterested )
132    {
133        sendInterest( peer, 1 );
134    }
135    if( !interested && peer->amInterested )
136    {
137        sendInterest( peer, 0 );
138    }
139}
140
141/***********************************************************************
142 * chooseBlock
143 ***********************************************************************
144 * At this point, we know the peer has at least one block we have an
145 * interest in. If he has more than one, we choose which one we are
146 * going to ask first.
147 * Our main goal is to complete pieces, so we look the pieces which are
148 * missing less blocks.
149 **********************************************************************/
150static inline int chooseBlock( tr_torrent_t * tor, tr_peer_t * peer )
151{
152    tr_info_t * inf = &tor->info;
153
154    int i;
155    int missingBlocks, minMissing;
156    int poolSize, * pool;
157    int block, minDownloading;
158
159    /* Choose a piece */
160    pool       = malloc( inf->pieceCount * sizeof( int ) );
161    poolSize   = 0;
162    minMissing = tor->blockCount + 1;
163    for( i = 0; i < inf->pieceCount; i++ )
164    {
165        missingBlocks = tr_cpMissingBlocksForPiece( tor->completion, i );
166        if( missingBlocks < 1 )
167        {
168            /* We already have or are downloading all blocks */
169            continue;
170        }
171        if( !tr_bitfieldHas( peer->bitfield, i ) )
172        {
173            /* The peer doesn't have this piece */
174            continue;
175        }
176        if( peer->banfield && tr_bitfieldHas( peer->banfield, i ) )
177        {
178            /* The peer is banned for this piece */
179            continue;
180        }
181
182        /* We are interested in this piece, remember it */
183        if( missingBlocks < minMissing )
184        {
185            minMissing = missingBlocks;
186            poolSize   = 0;
187        }
188        if( missingBlocks <= minMissing )
189        {
190            pool[poolSize++] = i;
191        }
192    }
193
194    if( poolSize )
195    {
196        /* All pieces in 'pool' have 'minMissing' missing blocks. Find
197           the rarest ones. */
198        tr_bitfield_t * bitfield;
199        int piece;
200        int min, foo, j;
201        int * pool2;
202        int   pool2Size;
203
204        pool2     = malloc( poolSize * sizeof( int ) );
205        pool2Size = 0;
206        min       = TR_MAX_PEER_COUNT + 1;
207        for( i = 0; i < poolSize; i++ )
208        {
209            foo = 0;
210            for( j = 0; j < tor->peerCount; j++ )
211            {
212                bitfield = tor->peers[j]->bitfield;
213                if( bitfield && tr_bitfieldHas( bitfield, pool[i] ) )
214                {
215                    foo++;
216                }
217            }
218            if( foo < min )
219            {
220                min       = foo;
221                pool2Size = 0;
222            }
223            if( foo <= min )
224            {
225                pool2[pool2Size++] = pool[i];
226            }
227        }
228        free( pool );
229
230        if( pool2Size < 1 )
231        {
232            /* Shouldn't happen */
233            free( pool2 );
234            return -1;
235        }
236
237        /* All pieces in pool2 have the same number of missing blocks,
238           and are availabme from the same number of peers. Pick a
239           random one */
240        piece = pool2[tr_rand(pool2Size)];
241        free( pool2 );
242
243        /* Pick a block in this piece */
244        block = tr_cpMissingBlockInPiece( tor->completion, piece );
245        goto check;
246    }
247
248    free( pool );
249
250    /* "End game" mode */
251    minDownloading = 255;
252    block = -1;
253    for( i = 0; i < inf->pieceCount; i++ )
254    {
255        int downloaders, block2;
256        if( !tr_bitfieldHas( peer->bitfield, i ) )
257        {
258            /* The peer doesn't have this piece */
259            continue;
260        }
261        if( peer->banfield && tr_bitfieldHas( peer->banfield, i ) )
262        {
263            /* The peer is banned for this piece */
264            continue;
265        }
266        if( tr_cpPieceIsComplete( tor->completion, i ) )
267        {
268            /* We already have it */
269            continue;
270        }
271        block2 = tr_cpMostMissingBlockInPiece( tor->completion, i, &downloaders );
272        if( block2 > -1 && downloaders < minDownloading )
273        {
274            block = block2;
275            minDownloading = downloaders;
276        }
277    }
278
279check:
280    if( block < 0 )
281    {
282        /* Shouldn't happen */
283        return -1;
284    }
285
286    for( i = 0; i < peer->inRequestCount; i++ )
287    {
288        tr_request_t * r;
289        r = &peer->inRequests[i];
290        if( tr_block( r->index, r->begin ) == block )
291        {
292            /* We are already asking this peer for this block */
293            return -1;
294        }
295    }
296
297    return block;
298}
Note: See TracBrowser for help on using the repository browser.