source: trunk/libtransmission/peerutils.h @ 2

Last change on this file since 2 was 2, checked in by root, 16 years ago

Update 2005-11-01

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 * Returns NULL if we reached the maximum authorized number of peers.
29 * Otherwise, allocates a new tr_peer_t, add it to the peers list and
30 * returns a pointer to it.
31 **********************************************************************/
32static tr_peer_t * peerInit( tr_torrent_t * tor )
33{
34    tr_peer_t * peer;
35
36    if( tor->peerCount >= TR_MAX_PEER_COUNT )
37    {
38        return NULL;
39    }
40
41    peer              = calloc( sizeof( tr_peer_t ), 1 );
42    peer->amChoking   = 1;
43    peer->peerChoking = 1;
44    peer->date        = tr_date();
45    peer->keepAlive   = peer->date;
46
47    tor->peers[tor->peerCount++] = peer;
48    return peer;
49}
50
51static int peerCmp( tr_peer_t * peer1, tr_peer_t * peer2 )
52{
53    /* Wait until we got the peers' ids */
54    if( peer1->status < PEER_STATUS_CONNECTED ||
55        peer2->status < PEER_STATUS_CONNECTED )
56    {
57        return 1;
58    }
59
60    return memcmp( peer1->id, peer2->id, 20 );
61}
62
63/***********************************************************************
64 * addWithAddr
65 ***********************************************************************
66 * Does nothing if we already have a peer matching 'addr' and 'port'.
67 * Otherwise adds such a new peer.
68 **********************************************************************/
69static void addWithAddr( tr_torrent_t * tor, struct in_addr addr,
70                         in_port_t port )
71{
72    int i;
73    tr_peer_t * peer;
74
75    for( i = 0; i < tor->peerCount; i++ )
76    {
77        peer = tor->peers[i];
78        if( peer->addr.s_addr == addr.s_addr &&
79            peer->port        == port )
80        {
81            /* We are already connected to this peer */
82            return;
83        }
84    }
85
86    if( !( peer = peerInit( tor ) ) )
87    {
88        return;
89    }
90
91    peer->addr   = addr;
92    peer->port   = port;
93    peer->status = PEER_STATUS_IDLE;
94}
95
96static int checkPeer( tr_torrent_t * tor, int i )
97{
98    tr_peer_t * peer = tor->peers[i];
99
100    if( peer->status < PEER_STATUS_CONNECTED &&
101        tr_date() > peer->date + 8000 )
102    {
103        /* If it has been too long, don't wait for the socket
104           to timeout - forget about it now */
105        peer_dbg( "connection timeout" );
106        return 1;
107    }
108
109    /* Drop peers who haven't even sent a keep-alive within the
110       last 3 minutes */
111    if( tr_date() > peer->date + 180000 )
112    {
113        peer_dbg( "read timeout" );
114        return 1;
115    }
116
117    /* Drop peers which are supposed to upload but actually
118       haven't sent anything within the last minute */
119    if( peer->inRequestCount && tr_date() > peer->date + 60000 )
120    {
121        peer_dbg( "bad uploader" );
122        return 1;
123    }
124
125    /* TODO: check for bad downloaders */
126
127#if 0
128    /* Choke unchoked peers we are not sending anything to */
129    if( !peer->amChoking && tr_date() > peer->outDate + 10000 )
130    {
131        peer_dbg( "not worth the unchoke" );
132        if( sendChoke( peer, 1 ) )
133        {
134            goto dropPeer;
135        }
136        peer->outSlow = 1;
137        tr_uploadChoked( tor->upload );
138    }
139#endif
140
141    if( peer->status & PEER_STATUS_CONNECTED )
142    {
143        /* Send keep-alive every 2 minutes */
144        if( tr_date() > peer->keepAlive + 120000 )
145        {
146            sendKeepAlive( peer );
147            peer->keepAlive = tr_date();
148        }
149
150        /* Choke or unchoke some people */
151        /* TODO: prefer people who upload to us */
152        if( !peer->amChoking && !peer->peerInterested )
153        {
154            /* He doesn't need us */
155            sendChoke( peer, 1 );
156            tr_uploadChoked( tor->upload );
157        }
158        if( peer->amChoking && peer->peerInterested &&
159            !peer->outSlow && tr_uploadCanUnchoke( tor->upload ) )
160        {
161            sendChoke( peer, 0 );
162            tr_uploadUnchoked( tor->upload );
163        }
164    }
165
166    return 0;
167}
168
169/***********************************************************************
170 * isInteresting
171 ***********************************************************************
172 * Returns 1 if 'peer' has at least one piece that we haven't completed,
173 * or 0 otherwise.
174 **********************************************************************/
175static int isInteresting( tr_torrent_t * tor, tr_peer_t * peer )
176{
177    tr_info_t * inf = &tor->info;
178
179    int i;
180    int bitfieldSize = ( inf->pieceCount + 7 ) / 8;
181
182    if( !peer->bitfield )
183    {
184        /* We don't know what this peer has */
185        return 0;
186    }
187
188    for( i = 0; i < bitfieldSize; i++ )
189    {
190        if( ( peer->bitfield[i] & ~(tor->bitfield[i]) ) & 0xFF )
191        {
192            return 1;
193        }
194    }
195
196    return 0;
197}
198static void updateInterest( tr_torrent_t * tor, tr_peer_t * peer )
199{
200    int interested = isInteresting( tor, peer );
201
202    if( interested && !peer->amInterested )
203    {
204        sendInterest( peer, 1 );
205    }
206    if( !interested && peer->amInterested )
207    {
208        sendInterest( peer, 0 );
209    }
210}
211
212/***********************************************************************
213 * chooseBlock
214 ***********************************************************************
215 * At this point, we know the peer has at least one block we have an
216 * interest in. If he has more than one, we choose which one we are
217 * going to ask first.
218 * Our main goal is to complete pieces, so we look the pieces which are
219 * missing less blocks.
220 **********************************************************************/
221static inline int chooseBlock( tr_torrent_t * tor, tr_peer_t * peer )
222{
223    tr_info_t * inf = &tor->info;
224
225    int i, j;
226    int startBlock, endBlock, countBlocks;
227    int missingBlocks, minMissing;
228    int poolSize, * pool;
229    int block, minDownloading;
230
231    /* Choose a piece */
232    pool       = malloc( inf->pieceCount * sizeof( int ) );
233    poolSize   = 0;
234    minMissing = tor->blockCount + 1;
235    for( i = 0; i < inf->pieceCount; i++ )
236    {
237        if( !tr_bitfieldHas( peer->bitfield, i ) )
238        {
239            /* The peer doesn't have this piece */
240            continue;
241        }
242        if( tr_bitfieldHas( tor->bitfield, i ) )
243        {
244            /* We already have it */
245            continue;
246        }
247
248        /* Count how many blocks from this piece are missing */
249        startBlock    = tr_pieceStartBlock( i );
250        countBlocks   = tr_pieceCountBlocks( i );
251        endBlock      = startBlock + countBlocks;
252        missingBlocks = countBlocks;
253        for( j = startBlock; j < endBlock; j++ )
254        {
255            /* TODO: optimize */
256            if( tor->blockHave[j] )
257            {
258                missingBlocks--;
259            }
260            if( missingBlocks > minMissing )
261            {
262                break;
263            }
264        }
265
266        if( missingBlocks < 1 )
267        {
268            /* We are already downloading all blocks */
269            continue;
270        }
271
272        /* We are interested in this piece, remember it */
273        if( missingBlocks < minMissing )
274        {
275            minMissing = missingBlocks;
276            poolSize   = 0;
277        }
278        if( missingBlocks <= minMissing )
279        {
280            pool[poolSize++] = i;
281        }
282    }
283
284    if( poolSize )
285    {
286        /* All pieces in 'pool' have 'minMissing' missing blocks. Find
287           the rarest ones. */
288        uint8_t * bitfield;
289        int piece;
290        int min, foo, j;
291        int * pool2;
292        int   pool2Size;
293
294        pool2     = malloc( poolSize * sizeof( int ) );
295        pool2Size = 0;
296        min       = TR_MAX_PEER_COUNT + 1;
297        for( i = 0; i < poolSize; i++ )
298        {
299            foo = 0;
300            for( j = 0; j < tor->peerCount; j++ )
301            {
302                bitfield = tor->peers[j]->bitfield;
303                if( bitfield && tr_bitfieldHas( bitfield, pool[i] ) )
304                {
305                    foo++;
306                }
307            }
308            if( foo < min )
309            {
310                min       = foo;
311                pool2Size = 0;
312            }
313            if( foo <= min )
314            {
315                pool2[pool2Size++] = pool[i];
316            }
317        }
318        free( pool );
319
320        if( pool2Size < 1 )
321        {
322            /* Shouldn't happen */
323            free( pool2 );
324            return -1;
325        }
326
327        /* All pieces in pool2 have the same number of missing blocks,
328           and are availabme from the same number of peers. Pick a
329           random one */
330        piece = pool2[tr_rand(pool2Size)];
331        free( pool2 );
332
333        /* Pick a block in this piece */
334        startBlock = tr_pieceStartBlock( piece );
335        endBlock   = startBlock + tr_pieceCountBlocks( piece );
336        for( i = startBlock; i < endBlock; i++ )
337        {
338            if( !tor->blockHave[i] )
339            {
340                block = i;
341                goto check;
342            }
343        }
344
345        /* Shouldn't happen */
346        return -1;
347    }
348
349    free( pool );
350
351    /* "End game" mode */
352    block          = -1;
353    minDownloading = TR_MAX_PEER_COUNT + 1;
354    for( i = 0; i < tor->blockCount; i++ )
355    {
356        /* TODO: optimize */
357        if( tr_bitfieldHas( peer->bitfield, tr_blockPiece( i ) ) &&
358            tor->blockHave[i] >= 0 && tor->blockHave[i] < minDownloading )
359        {
360            block          = i;
361            minDownloading = tor->blockHave[i];
362        }
363    }
364
365    if( block < 0 )
366    {
367        /* Shouldn't happen */
368        return -1;
369    }
370
371check:
372    for( i = 0; i < peer->inRequestCount; i++ )
373    {
374        tr_request_t * r;
375        r = &peer->inRequests[i];
376        if( tr_block( r->index, r->begin ) == block )
377        {
378            /* We are already asking this peer for this block */
379            return -1;
380        }
381    }
382
383    return block;
384}
Note: See TracBrowser for help on using the repository browser.