source: trunk/libtransmission/choking.c @ 179

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

Adds a real test for lrintf because some Linux systems, like BeOS, seem
to provide a non-working lrintf implementation
(Patch from Henner Sudek, modified)

File size: 10.7 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#ifndef HAVE_LRINTF
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 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( tor = c->h->torrentList; tor; tor = tor->next )
156    {
157        tr_lockLock( &tor->lock );
158        peersTotalCount += tor->peerCount;
159    }
160
161    canChoke   = malloc( peersTotalCount * sizeof( tr_peer_t * ) );
162    canUnchoke = malloc( peersTotalCount * sizeof( tr_peer_t * ) );
163    canChokeCount   = 0;
164    canUnchokeCount = 0;
165    unchoked        = 0;
166
167    for( tor = c->h->torrentList; tor; tor = tor->next )
168    {
169        tr_peer_t * peer;
170        int i;
171
172        for( i = 0; i < tor->peerCount; i++ )
173        {
174            peer = tor->peers[i];
175
176            if( !tr_peerIsConnected( peer ) )
177                continue;
178
179            /* Choke peers who have lost their interest in us */
180            if( !tr_peerIsInterested( peer ) )
181            {
182                if( tr_peerIsUnchoked( peer ) )
183                {
184                    tr_peerChoke( peer );
185                    tr_peerSetOptimistic( peer, 0 );
186                }
187                continue;
188            }
189
190            /* Build two lists of interested peers: those we may choke,
191               those we may unchoke. Whatever happens, we never choke a
192               peer less than 10 seconds after the time we unchoked him
193               (or the other way around). */
194            if( tr_peerIsUnchoked( peer ) )
195            {
196                if( tr_peerIsOptimistic( peer ) )
197                {
198                    if( tr_peerLastChoke( peer ) + 30000 < now )
199                    {
200                        /* He got his 30 seconds, now we see him like
201                           any other unchoked peer */
202                        tr_peerSetOptimistic( peer, 0 );
203                    }
204                    else
205                    {
206                        /* Keep him unchoked for 30 seconds */
207                        mustOptimistic = 0;
208                        continue;
209                    }
210                }
211
212                unchoked++;
213                if( tr_peerLastChoke( peer ) + 10000 < now )
214                    canChoke[canChokeCount++] = peer;
215            }
216            else
217            {
218                if( tr_peerLastChoke( peer ) + 10000 < now )
219                    canUnchoke[canUnchokeCount++] = peer;
220            }
221        }
222    }
223
224    canChokeZero      = malloc( canChokeCount * sizeof( tr_peer_t * ) );
225    canChokeNonZero   = malloc( canChokeCount * sizeof( tr_peer_t * ) );
226    canUnchokeZero    = malloc( canUnchokeCount * sizeof( tr_peer_t * ) );
227    canUnchokeNonZero = malloc( canUnchokeCount * sizeof( tr_peer_t * ) );
228
229    sortPeersDescending( canChoke, canChokeCount,
230                         canChokeZero, &canChokeZeroCount,
231                         canChokeNonZero, &canChokeNonZeroCount);
232    sortPeersAscending( canUnchoke, canUnchokeCount,
233                        canUnchokeZero, &canUnchokeZeroCount,
234                        canUnchokeNonZero, &canUnchokeNonZeroCount);
235
236    free( canChoke );
237    free( canUnchoke );
238
239    if( mustOptimistic )
240    {
241        tr_peer_t * peer;
242
243        /* Open an extra slot for optimistic choking */
244        if( canUnchokeZeroCount )
245        {
246            /* TODO: prefer peers with no pieces at all */
247            peer = canUnchokeZero[--canUnchokeZeroCount];
248            tr_peerUnchoke( peer );
249            tr_peerSetOptimistic( peer, 1 );
250        }
251        else if( canUnchokeNonZeroCount )
252        {
253            peer = canUnchokeNonZero[--canUnchokeNonZeroCount];
254            tr_peerUnchoke( peer );
255            tr_peerSetOptimistic( peer, 1 );
256        }
257    }
258
259    /* If we have more open slots than what we should have (the user has
260       just lowered his upload limit), we need to choke some of the
261       peers we are uploading to. We start with the peers who aren't
262       uploading to us, then those we upload the least. */
263    while( unchoked > c->slots && canChokeZeroCount > 0 )
264    {
265        tr_peerChoke( canChokeZero[--canChokeZeroCount] );
266        unchoked--;
267    }
268    while( unchoked > c->slots && canChokeNonZeroCount > 0 )
269    {
270        tr_peerChoke( canChokeNonZero[--canChokeNonZeroCount] );
271        unchoked--;
272    }
273
274    /* If we have unused open slots, let's unchoke some people. We start
275       with the peers who are uploading to us the most. */
276    while( unchoked < c->slots && canUnchokeNonZeroCount > 0 )
277    {
278        tr_peerUnchoke( canUnchokeNonZero[--canUnchokeNonZeroCount] );
279        unchoked++;
280    }
281    while( unchoked < c->slots && canUnchokeZeroCount > 0 )
282    {
283        tr_peerUnchoke( canUnchokeZero[--canUnchokeZeroCount] );
284        unchoked++;
285    }
286
287    /* Choke peers who aren't uploading if there are good peers waiting
288       for an unchoke */
289    while( canChokeZeroCount > 0 && canUnchokeNonZeroCount > 0 )
290    {
291        tr_peerChoke( canChokeZero[--canChokeZeroCount] );
292        tr_peerUnchoke( canUnchokeNonZero[--canUnchokeNonZeroCount] );
293    }
294
295    /* Choke peers who aren't uploading that much if there are choked
296       peers who are uploading more */
297    while( canChokeNonZeroCount > 0 && canUnchokeNonZeroCount > 0 )
298    {
299        if( tr_peerDownloadRate( canUnchokeNonZero[canUnchokeNonZeroCount - 1] )
300            < tr_peerDownloadRate( canChokeNonZero[canChokeNonZeroCount - 1] ) )
301            break;
302
303        tr_peerChoke( canChokeNonZero[--canChokeNonZeroCount] );
304        tr_peerUnchoke( canUnchokeNonZero[--canUnchokeNonZeroCount] );
305    }
306
307    /* Some unchoked peers still aren't uploading to us, let's give a
308       chance to other non-uploaders */
309    while( canChokeZeroCount > 0 && canUnchokeZeroCount > 0 )
310    {
311        tr_peerChoke( canChokeZero[--canChokeZeroCount] );
312        tr_peerUnchoke( canUnchokeZero[--canUnchokeZeroCount] );
313    }
314
315    free( canChokeZero );
316    free( canChokeNonZero );
317    free( canUnchokeZero );
318    free( canUnchokeNonZero );
319
320    /* Unlock all torrents */
321    for( tor = c->h->torrentList; tor; tor = tor->next )
322    {
323        tr_lockUnlock( &tor->lock );
324    }
325
326    tr_lockUnlock( &c->lock );
327}
328
329void tr_chokingClose( tr_choking_t * c )
330{
331    tr_lockClose( &c->lock );
332    free( c );
333}
Note: See TracBrowser for help on using the repository browser.