source: trunk/libtransmission/choking.c @ 346

Last change on this file since 346 was 261, checked in by titer, 15 years ago

Updated svn:keywords

  • Property svn:keywords set to Date Rev Author Id
File size: 10.8 KB
Line 
1/******************************************************************************
2 * $Id: choking.c 261 2006-05-29 21:27:31Z titer $
3 *
4 * Copyright (c) 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
25#include <math.h>
26#include "transmission.h"
27
28#ifndef HAVE_LRINTF
29#  define lrintf(a) ((int)(0.5+(a)))
30#endif
31
32/* We may try to allocate and free tables of size 0. Quick and dirty
33   way to handle it... */
34void * __malloc( int size )
35{
36    if( !size )
37        return NULL;
38    return malloc( size );
39}
40void __free( void * p )
41{
42    if( p )
43        free( p );
44}
45#define malloc __malloc
46#define free   __free
47
48struct tr_choking_s
49{
50    tr_lock_t     lock;
51    tr_handle_t * h;
52    int           slots;
53};
54
55tr_choking_t * tr_chokingInit( tr_handle_t * h )
56{
57    tr_choking_t * c;
58
59    c        = calloc( sizeof( tr_choking_t ), 1 );
60    c->h     = h;
61    c->slots = 4242;
62    tr_lockInit( &c->lock );
63
64    return c;
65}
66
67void tr_chokingSetLimit( tr_choking_t * c, int limit )
68{
69    tr_lockLock( &c->lock );
70    if( limit < 0 )
71        c->slots = 4242;
72    else
73        /* Reckon a number of slots from the upload limit. There is no
74           official right way to do this, the formula below e.g. gives:
75            10  KB/s -> 4  * 2.50 KB/s
76            20  KB/s -> 6  * 3.33 KB/s
77            50  KB/s -> 10 * 5.00 KB/s
78            100 KB/s -> 14 * 7.14 KB/s */
79        c->slots = lrintf( sqrt( 2 * limit ) );
80    tr_lockUnlock( &c->lock );
81}
82
83#define sortPeersAscending(a,ac,z,zc,n,nc)  sortPeers(a,ac,z,zc,n,nc,0)
84#define sortPeersDescending(a,ac,z,zc,n,nc) sortPeers(a,ac,z,zc,n,nc,1)
85static inline void sortPeers( tr_peer_t ** all, int allCount,
86                              tr_peer_t ** zero, int * zeroCount,
87                              tr_peer_t ** nonZero, int * nonZeroCount,
88                              int order )
89{
90    int i, shuffle;
91
92    /* Seperate uploaders from non-uploaders */
93    *zeroCount    = 0;
94    *nonZeroCount = 0;
95    for( i = 0; i < allCount; i++ )
96    {
97        if( tr_peerDownloadRate( all[i] ) < 0.1 )
98            zero[(*zeroCount)++] = all[i];
99        else
100            nonZero[(*nonZeroCount)++] = all[i];
101    }
102
103    /* Randomly shuffle non-uploaders, so they are treated equally */
104    if( *zeroCount && ( shuffle = tr_rand( *zeroCount ) ) )
105    {
106        tr_peer_t ** bak;
107        bak = malloc( shuffle * sizeof( tr_peer_t * ) );
108        memcpy( bak, zero, shuffle * sizeof( tr_peer_t * ) );
109        memmove( zero, &zero[shuffle],
110                 ( *zeroCount - shuffle ) * sizeof( tr_peer_t * ) );
111        memcpy( &zero[*zeroCount - shuffle], bak,
112                 shuffle * sizeof( tr_peer_t * ) );
113        free( bak );
114    }
115
116    /* Sort uploaders by download rate */
117    for( i = *nonZeroCount - 1; i > 0; i-- )
118    {
119        float rate1, rate2;
120        tr_peer_t * tmp;
121        int j, sorted;
122
123        sorted = 1;
124        for( j = 0; j < i; j++ )
125        {
126            rate1 = tr_peerDownloadRate( nonZero[j] );
127            rate2 = tr_peerDownloadRate( nonZero[j+1] );
128            if( order ? ( rate1 < rate2 ) : ( rate1 > rate2 ) )
129            {
130                tmp          = nonZero[j];
131                nonZero[j]   = nonZero[j+1];
132                nonZero[j+1] = tmp;
133                sorted       = 0;
134            }
135        }
136        if( sorted )
137            break;
138    }
139}
140
141void tr_chokingPulse( tr_choking_t * c )
142{
143    int peersTotalCount, unchoked, mustOptimistic = 1;
144    tr_peer_t ** canChoke, ** canUnchoke;
145    tr_peer_t ** canChokeZero, ** canUnchokeZero;
146    tr_peer_t ** canChokeNonZero, ** canUnchokeNonZero;
147    int canChokeCount, canUnchokeCount;
148    int canChokeZeroCount, canUnchokeZeroCount;
149    int canChokeNonZeroCount, canUnchokeNonZeroCount;
150    tr_torrent_t * tor;
151    uint64_t now = tr_date();
152
153    tr_lockLock( &c->lock );
154
155    /* Lock all torrents and get the total number of peers */
156    peersTotalCount = 0;
157    for( tor = c->h->torrentList; tor; tor = tor->next )
158    {
159        tr_lockLock( &tor->lock );
160        peersTotalCount += tor->peerCount;
161    }
162
163    canChoke   = malloc( peersTotalCount * sizeof( tr_peer_t * ) );
164    canUnchoke = malloc( peersTotalCount * sizeof( tr_peer_t * ) );
165    canChokeCount   = 0;
166    canUnchokeCount = 0;
167    unchoked        = 0;
168
169    for( tor = c->h->torrentList; tor; tor = tor->next )
170    {
171        tr_peer_t * peer;
172        int i;
173
174        for( i = 0; i < tor->peerCount; i++ )
175        {
176            peer = tor->peers[i];
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( tor = c->h->torrentList; tor; tor = tor->next )
324    {
325        tr_lockUnlock( &tor->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.