source: trunk/libtransmission/choking.c @ 109

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

Added optimistic choking

File size: 10.8 KB
Line 
1/******************************************************************************
2 * Copyright (c) 2006 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
23#include <math.h>
24#include "transmission.h"
25
26#ifdef SYS_BEOS
27#define lrintf(a) ((int)(0.5+(a)))
28#endif
29
30/* We may try to allocate and free tables of size 0. Quick and dirty
31   way to handle it... */
32void * __malloc( int size )
33{
34    if( !size )
35        return NULL;
36    return malloc( size );
37}
38void __free( void * p )
39{
40    if( p )
41        free( p );
42}
43#define malloc __malloc
44#define free   __free
45
46struct tr_choking_s
47{
48    tr_lock_t     lock;
49    tr_handle_t * h;
50    int           slots;
51};
52
53tr_choking_t * tr_chokingInit( tr_handle_t * h )
54{
55    tr_choking_t * c;
56
57    c        = calloc( sizeof( tr_choking_t ), 1 );
58    c->h     = h;
59    c->slots = 4242;
60    tr_lockInit( &c->lock );
61
62    return c;
63}
64
65void tr_chokingSetLimit( tr_choking_t * c, int limit )
66{
67    tr_lockLock( &c->lock );
68    if( limit < 0 )
69        c->slots = 4242;
70    else
71        /* Reckon a number of slots from the upload limit. There is no
72           official right way to do this, the formula below e.g. gives:
73            10  KB/s -> 4  * 2.50 KB/s
74            20  KB/s -> 6  * 3.33 KB/s
75            50  KB/s -> 10 * 5.00 KB/s
76            100 KB/s -> 14 * 7.14 KB/s */
77        c->slots = lrintf( sqrt( 2 * limit ) );
78    tr_lockUnlock( &c->lock );
79}
80
81#define sortPeersAscending(a,ac,z,zc,n,nc)  sortPeers(a,ac,z,zc,n,nc,0)
82#define sortPeersDescending(a,ac,z,zc,n,nc) sortPeers(a,ac,z,zc,n,nc,1)
83static inline void sortPeers( tr_peer_t ** all, int allCount,
84                              tr_peer_t ** zero, int * zeroCount,
85                              tr_peer_t ** nonZero, int * nonZeroCount,
86                              int order )
87{
88    int i, shuffle;
89
90    /* Seperate uploaders from non-uploaders */
91    *zeroCount    = 0;
92    *nonZeroCount = 0;
93    for( i = 0; i < allCount; i++ )
94    {
95        if( tr_peerDownloadRate( all[i] ) < 0.1 )
96            zero[(*zeroCount)++] = all[i];
97        else
98            nonZero[(*nonZeroCount)++] = all[i];
99    }
100
101    /* Randomly shuffle non-uploaders, so they are treated equally */
102    if( *zeroCount && ( shuffle = tr_rand( *zeroCount ) ) )
103    {
104        tr_peer_t ** bak;
105        bak = malloc( shuffle * sizeof( tr_peer_t * ) );
106        memcpy( bak, zero, shuffle * sizeof( tr_peer_t * ) );
107        memmove( zero, &zero[shuffle],
108                 ( *zeroCount - shuffle ) * sizeof( tr_peer_t * ) );
109        memcpy( &zero[*zeroCount - shuffle], bak,
110                 shuffle * sizeof( tr_peer_t * ) );
111        free( bak );
112    }
113
114    /* Sort uploaders by download rate */
115    for( i = *nonZeroCount - 1; i > 0; i-- )
116    {
117        float rate1, rate2;
118        tr_peer_t * tmp;
119        int j, sorted;
120
121        sorted = 1;
122        for( j = 0; j < i; j++ )
123        {
124            rate1 = tr_peerDownloadRate( nonZero[j] );
125            rate2 = tr_peerDownloadRate( nonZero[j+1] );
126            if( order ? ( rate1 < rate2 ) : ( rate1 > rate2 ) )
127            {
128                tmp          = nonZero[j];
129                nonZero[j]   = nonZero[j+1];
130                nonZero[j+1] = tmp;
131                sorted       = 0;
132            }
133        }
134        if( sorted )
135            break;
136    }
137}
138
139void tr_chokingPulse( tr_choking_t * c )
140{
141    int i, peersTotalCount, unchoked, mustOptimistic = 1;
142    tr_peer_t ** canChoke, ** canUnchoke;
143    tr_peer_t ** canChokeZero, ** canUnchokeZero;
144    tr_peer_t ** canChokeNonZero, ** canUnchokeNonZero;
145    int canChokeCount, canUnchokeCount;
146    int canChokeZeroCount, canUnchokeZeroCount;
147    int canChokeNonZeroCount, canUnchokeNonZeroCount;
148    tr_torrent_t * tor;
149    uint64_t now = tr_date();
150
151    tr_lockLock( &c->lock );
152
153    /* Lock all torrents and get the total number of peers */
154    peersTotalCount = 0;
155    for( i = 0; i < c->h->torrentCount; i++ )
156    {
157        tor = c->h->torrents[i];
158        tr_lockLock( &tor->lock );
159        peersTotalCount += tor->peerCount;
160    }
161
162    canChoke   = malloc( peersTotalCount * sizeof( tr_peer_t * ) );
163    canUnchoke = malloc( peersTotalCount * sizeof( tr_peer_t * ) );
164    canChokeCount   = 0;
165    canUnchokeCount = 0;
166    unchoked        = 0;
167
168    for( i = 0; i < c->h->torrentCount; i++ )
169    {
170        tr_peer_t * peer;
171        int j;
172
173        tor = c->h->torrents[i];
174        for( j = 0; j < tor->peerCount; j++ )
175        {
176            peer = tor->peers[j];
177
178            if( !tr_peerIsConnected( peer ) )
179                continue;
180
181            /* Choke peers who have lost their interest in us */
182            if( !tr_peerIsInterested( peer ) )
183            {
184                if( tr_peerIsUnchoked( peer ) )
185                {
186                    tr_peerChoke( peer );
187                    tr_peerSetOptimistic( peer, 0 );
188                }
189                continue;
190            }
191
192            /* Build two lists of interested peers: those we may choke,
193               those we may unchoke. Whatever happens, we never choke a
194               peer less than 10 seconds after the time we unchoked him
195               (or the other way around). */
196            if( tr_peerIsUnchoked( peer ) )
197            {
198                if( tr_peerIsOptimistic( peer ) )
199                {
200                    if( tr_peerLastChoke( peer ) + 30000 < now )
201                    {
202                        /* He got his 30 seconds, now we see him like
203                           any other unchoked peer */
204                        tr_peerSetOptimistic( peer, 0 );
205                    }
206                    else
207                    {
208                        /* Keep him unchoked for 30 seconds */
209                        mustOptimistic = 0;
210                        continue;
211                    }
212                }
213
214                unchoked++;
215                if( tr_peerLastChoke( peer ) + 10000 < now )
216                    canChoke[canChokeCount++] = peer;
217            }
218            else
219            {
220                if( tr_peerLastChoke( peer ) + 10000 < now )
221                    canUnchoke[canUnchokeCount++] = peer;
222            }
223        }
224    }
225
226    canChokeZero      = malloc( canChokeCount * sizeof( tr_peer_t * ) );
227    canChokeNonZero   = malloc( canChokeCount * sizeof( tr_peer_t * ) );
228    canUnchokeZero    = malloc( canUnchokeCount * sizeof( tr_peer_t * ) );
229    canUnchokeNonZero = malloc( canUnchokeCount * sizeof( tr_peer_t * ) );
230
231    sortPeersDescending( canChoke, canChokeCount,
232                         canChokeZero, &canChokeZeroCount,
233                         canChokeNonZero, &canChokeNonZeroCount);
234    sortPeersAscending( canUnchoke, canUnchokeCount,
235                        canUnchokeZero, &canUnchokeZeroCount,
236                        canUnchokeNonZero, &canUnchokeNonZeroCount);
237
238    free( canChoke );
239    free( canUnchoke );
240
241    if( mustOptimistic )
242    {
243        tr_peer_t * peer;
244
245        /* Open an extra slot for optimistic choking */
246        if( canUnchokeZeroCount )
247        {
248            /* TODO: prefer peers with no pieces at all */
249            peer = canUnchokeZero[--canUnchokeZeroCount];
250            tr_peerUnchoke( peer );
251            tr_peerSetOptimistic( peer, 1 );
252        }
253        else if( canUnchokeNonZeroCount )
254        {
255            peer = canUnchokeNonZero[--canUnchokeNonZeroCount];
256            tr_peerUnchoke( peer );
257            tr_peerSetOptimistic( peer, 1 );
258        }
259    }
260
261    /* If we have more open slots than what we should have (the user has
262       just lowered his upload limit), we need to choke some of the
263       peers we are uploading to. We start with the peers who aren't
264       uploading to us, then those we upload the least. */
265    while( unchoked > c->slots && canChokeZeroCount > 0 )
266    {
267        tr_peerChoke( canChokeZero[--canChokeZeroCount] );
268        unchoked--;
269    }
270    while( unchoked > c->slots && canChokeNonZeroCount > 0 )
271    {
272        tr_peerChoke( canChokeNonZero[--canChokeNonZeroCount] );
273        unchoked--;
274    }
275
276    /* If we have unused open slots, let's unchoke some people. We start
277       with the peers who are uploading to us the most. */
278    while( unchoked < c->slots && canUnchokeNonZeroCount > 0 )
279    {
280        tr_peerUnchoke( canUnchokeNonZero[--canUnchokeNonZeroCount] );
281        unchoked++;
282    }
283    while( unchoked < c->slots && canUnchokeZeroCount > 0 )
284    {
285        tr_peerUnchoke( canUnchokeZero[--canUnchokeZeroCount] );
286        unchoked++;
287    }
288
289    /* Choke peers who aren't uploading if there are good peers waiting
290       for an unchoke */
291    while( canChokeZeroCount > 0 && canUnchokeNonZeroCount > 0 )
292    {
293        tr_peerChoke( canChokeZero[--canChokeZeroCount] );
294        tr_peerUnchoke( canUnchokeNonZero[--canUnchokeNonZeroCount] );
295    }
296
297    /* Choke peers who aren't uploading that much if there are choked
298       peers who are uploading more */
299    while( canChokeNonZeroCount > 0 && canUnchokeNonZeroCount > 0 )
300    {
301        if( tr_peerDownloadRate( canUnchokeNonZero[canUnchokeNonZeroCount - 1] )
302            < tr_peerDownloadRate( canChokeNonZero[canChokeNonZeroCount - 1] ) )
303            break;
304
305        tr_peerChoke( canChokeNonZero[--canChokeNonZeroCount] );
306        tr_peerUnchoke( canUnchokeNonZero[--canUnchokeNonZeroCount] );
307    }
308
309    /* Some unchoked peers still aren't uploading to us, let's give a
310       chance to other non-uploaders */
311    while( canChokeZeroCount > 0 && canUnchokeZeroCount > 0 )
312    {
313        tr_peerChoke( canChokeZero[--canChokeZeroCount] );
314        tr_peerUnchoke( canUnchokeZero[--canUnchokeZeroCount] );
315    }
316
317    free( canChokeZero );
318    free( canChokeNonZero );
319    free( canUnchokeZero );
320    free( canUnchokeNonZero );
321
322    /* Unlock all torrents */
323    for( i = 0; i < c->h->torrentCount; i++ )
324    {
325        tr_lockUnlock( &c->h->torrents[i]->lock );
326    }
327
328    tr_lockUnlock( &c->lock );
329}
330
331void tr_chokingClose( tr_choking_t * c )
332{
333    tr_lockClose( &c->lock );
334    free( c );
335}
Note: See TracBrowser for help on using the repository browser.