source: trunk/libtransmission/bandwidth.c @ 7460

Last change on this file since 7460 was 7460, checked in by charles, 12 years ago

(trunk libT) fix a Windows portability bug reported by Alexey

File size: 11.0 KB
Line 
1/*
2 * This file Copyright (C) 2008 Charles Kerr <charles@transmissionbt.com>
3 *
4 * This file is licensed by the GPL version 2.  Works owned by the
5 * Transmission project are granted a special exemption to clause 2(b)
6 * so that the bulk of its code can remain under the MIT license.
7 * This exemption does not extend to derived works not owned by
8 * the Transmission project.
9 *
10 * $Id:$
11 */
12
13#include <assert.h>
14#include <limits.h>
15
16#include "event.h"
17
18#include "transmission.h"
19#include "bandwidth.h"
20#include "crypto.h"
21#include "peer-io.h"
22#include "ptrarray.h"
23#include "utils.h"
24
25/***
26****
27***/
28
29enum
30{
31    HISTORY_MSEC = 2000,
32    INTERVAL_MSEC = HISTORY_MSEC,
33    GRANULARITY_MSEC = 50,
34    HISTORY_SIZE = ( INTERVAL_MSEC / GRANULARITY_MSEC ),
35    MAGIC_NUMBER = 43143
36};
37
38struct bratecontrol
39{
40    int newest;
41    struct { uint64_t date, size; } transfers[HISTORY_SIZE];
42};
43
44static float
45getSpeed( const struct bratecontrol * r, int interval_msec )
46{
47    uint64_t       bytes = 0;
48    const uint64_t cutoff = tr_date ( ) - interval_msec;
49    int            i = r->newest;
50
51    for( ;; )
52    {
53        if( r->transfers[i].date <= cutoff )
54            break;
55
56        bytes += r->transfers[i].size;
57
58        if( --i == -1 ) i = HISTORY_SIZE - 1; /* circular history */
59        if( i == r->newest ) break; /* we've come all the way around */
60    }
61
62    return ( bytes / 1024.0 ) * ( 1000.0 / interval_msec );
63}
64
65static void
66bytesUsed( struct bratecontrol * r, size_t size )
67{
68    const uint64_t now = tr_date ( );
69
70    if( r->transfers[r->newest].date + GRANULARITY_MSEC >= now )
71        r->transfers[r->newest].size += size;
72    else
73    {
74        if( ++r->newest == HISTORY_SIZE ) r->newest = 0;
75        r->transfers[r->newest].date = now;
76        r->transfers[r->newest].size = size;
77    }
78}
79
80/******
81*******
82*******
83******/
84
85struct tr_band
86{
87    tr_bool isLimited;
88    tr_bool honorParentLimits;
89    size_t bytesLeft;
90    double desiredSpeed;
91    struct bratecontrol raw;
92    struct bratecontrol piece;
93};
94
95struct tr_bandwidth
96{
97    struct tr_band band[2];
98    struct tr_bandwidth * parent;
99    int magicNumber;
100    tr_session * session;
101    tr_ptrArray * children; /* struct tr_bandwidth */
102    tr_ptrArray * peers; /* tr_peerIo */
103};
104
105/***
106****
107***/
108
109static int
110comparePointers( const void * a, const void * b )
111{
112    if( a != b )
113        return a < b ? -1 : 1;
114
115    return 0;
116}
117
118tr_bool
119tr_isBandwidth( const tr_bandwidth * b )
120{
121    return ( b != NULL ) && ( b->magicNumber == MAGIC_NUMBER );
122}
123
124/***
125****
126***/
127
128tr_bandwidth*
129tr_bandwidthNew( tr_session * session, tr_bandwidth * parent )
130{
131    tr_bandwidth * b = tr_new0( tr_bandwidth, 1 );
132    b->session = session;
133    b->children = tr_ptrArrayNew( );
134    b->peers = tr_ptrArrayNew( );
135    b->magicNumber = MAGIC_NUMBER;
136    b->band[TR_UP].honorParentLimits = TRUE;
137    b->band[TR_DOWN].honorParentLimits = TRUE;
138    tr_bandwidthSetParent( b, parent );
139    return b;
140}
141
142void
143tr_bandwidthFree( tr_bandwidth * b )
144{
145    assert( tr_isBandwidth( b ) );
146
147    tr_bandwidthSetParent( b, NULL );
148    tr_ptrArrayFree( b->peers, NULL );
149    tr_ptrArrayFree( b->children, NULL );
150    b->magicNumber = 0xDEAD;
151    tr_free( b );
152}
153
154/***
155****
156***/
157
158void
159tr_bandwidthSetParent( tr_bandwidth  * b,
160                       tr_bandwidth  * parent )
161{
162    assert( tr_isBandwidth( b ) );
163    assert( b != parent );
164
165    if( b->parent )
166    {
167        assert( tr_isBandwidth( b->parent ) );
168
169        tr_ptrArrayRemoveSorted( b->parent->children, b, comparePointers );
170        b->parent = NULL;
171    }
172
173    if( parent )
174    {
175        assert( tr_isBandwidth( parent ) );
176        assert( parent->parent != b );
177
178        tr_ptrArrayInsertSorted( parent->children, b, comparePointers );
179        b->parent = parent;
180    }
181}
182
183void
184tr_bandwidthHonorParentLimits( tr_bandwidth  * b,
185                               tr_direction    dir,
186                               tr_bool         honorParentLimits )
187{
188    assert( tr_isBandwidth( b ) );
189    assert( tr_isDirection( dir ) );
190
191    b->band[dir].honorParentLimits = honorParentLimits;
192}
193
194/***
195****
196***/
197
198void
199tr_bandwidthSetDesiredSpeed( tr_bandwidth  * b,
200                             tr_direction    dir,
201                             double          desiredSpeed )
202{
203    assert( tr_isBandwidth( b ) );
204    assert( tr_isDirection( dir ) );
205
206    b->band[dir].desiredSpeed = desiredSpeed; 
207}
208
209double
210tr_bandwidthGetDesiredSpeed( const tr_bandwidth  * b,
211                             tr_direction          dir )
212{
213    assert( tr_isBandwidth( b ) );
214    assert( tr_isDirection( dir ) );
215
216    return b->band[dir].desiredSpeed;
217}
218
219void
220tr_bandwidthSetLimited( tr_bandwidth  * b,
221                        tr_direction    dir,
222                        tr_bool         isLimited )
223{
224    assert( tr_isBandwidth( b ) );
225    assert( tr_isDirection( dir ) );
226
227    b->band[dir].isLimited = isLimited;
228}
229
230tr_bool
231tr_bandwidthIsLimited( const tr_bandwidth  * b,
232                       tr_direction          dir )
233{
234    assert( tr_isBandwidth( b ) );
235    assert( tr_isDirection( dir ) );
236
237    return b->band[dir].isLimited;
238}
239
240#if 0
241#warning do not check the code in with this enabled
242#define DEBUG_DIRECTION TR_UP
243#endif
244
245static void
246allocateBandwidth( tr_bandwidth  * b,
247                   tr_direction    dir,
248                   int             period_msec,
249                   tr_ptrArray   * peer_pool )
250{
251    assert( tr_isBandwidth( b ) );
252    assert( tr_isDirection( dir ) );
253
254    /* set the available bandwidth */
255    if( b->band[dir].isLimited )
256    {
257        const double desiredSpeed = b->band[dir].desiredSpeed;
258        const double nextPulseSpeed = desiredSpeed;
259        b->band[dir].bytesLeft = MAX( 0.0, nextPulseSpeed * 1024.0 * period_msec / 1000.0 );
260
261#ifdef DEBUG_DIRECTION
262        if( dir == DEBUG_DIRECTION )
263                fprintf( stderr, "bandwidth %p currentPieceSpeed(%5.2f of %5.2f) desiredSpeed(%5.2f), allocating %5.2f\n",
264                         b, currentSpeed, tr_bandwidthGetRawSpeed( b, dir ), desiredSpeed,
265                         b->band[dir].bytesLeft/1024.0 );
266#endif
267    }
268
269    /* traverse & repeat for the subtree */
270    {
271        int i;
272        const int n = tr_ptrArraySize( b->peers );
273        for( i=0; i<n; ++i )
274            tr_ptrArrayAppend( peer_pool, tr_ptrArrayNth( b->peers, i ) );
275    }
276
277#ifdef DEBUG_DIRECTION
278if( ( dir == DEBUG_DIRECTION ) && ( n > 1 ) )
279fprintf( stderr, "bandwidth %p has %d peers\n", b, n );
280#endif
281
282    /* all children should reallocate too */
283    if( 1 ) {
284        int i, n=0;
285        struct tr_bandwidth ** children = (struct tr_bandwidth**) tr_ptrArrayPeek( b->children, &n );
286        for( i=0; i<n; ++i )
287            allocateBandwidth( children[i], dir, period_msec, peer_pool );
288    }
289}
290
291void
292tr_bandwidthAllocate( tr_bandwidth  * b,
293                      tr_direction    dir,
294                      int             period_msec )
295{
296    int i, n, peerCount;
297    tr_ptrArray * tmp;
298    struct tr_peerIo ** peers;
299
300    /* allocateBandwidth() is a helper function with two purposes:
301     * 1. allocate bandwidth to b and its subtree
302     * 2. accumulate an array of all the peerIos from b and its subtree. */
303    tmp = tr_ptrArrayNew( );
304    allocateBandwidth( b, dir, period_msec, tmp );
305    peers = (struct tr_peerIo**) tr_ptrArrayPeek( tmp, &peerCount );
306
307    /* Stop all peers from listening for the socket to be ready for IO.
308     * See "Second phase of IO" lower in this function for more info. */
309    for( i=0; i<peerCount; ++i )
310        tr_peerIoSetEnabled( peers[i], dir, FALSE );
311
312    /* First phase of IO.  Tries to distribute bandwidth fairly to keep faster
313     * peers from starving the others.  Loop through the peers, giving each a
314     * small chunk of bandwidth.  Keep looping until we run out of bandwidth
315     * or pweers that can use it */
316    n = peerCount;
317    i = n ? tr_cryptoWeakRandInt( n ) : 0; /* pick a random starting point */
318    for( ; n>0; )
319    {
320        const int increment = n==1 ? 4096 : 1024;
321        const int byteCount = tr_peerIoFlush( peers[i], dir, increment);
322
323        if( byteCount == increment )
324            ++i;
325        else {
326            /* peer is done writing for now; move it to the end of the list */
327            tr_peerIo * tmp = peers[i];
328            peers[i] = peers[n-1];
329            peers[n-1] = tmp;
330            --n;
331        }
332
333        assert( i <= n );
334        if( i == n )
335            i = 0;
336    }
337
338    /* Second phase of IO.  To help us scale in high bandwidth situations,
339     * enable on-demand IO for peers with bandwidth left to burn.
340     * This on-demand IO is enabled until (1) the peer runs out of bandwidth,
341     * or (2) the next tr_bandwidthAllocate() call, when we start over again. */
342    for( i=0; i<peerCount; ++i )
343        if( tr_peerIoHasBandwidthLeft( peers[i], dir ) )
344            tr_peerIoSetEnabled( peers[i], dir, TRUE );
345
346    /* cleanup */
347    tr_ptrArrayFree( tmp, NULL );
348}
349
350/***
351****
352***/
353
354void
355tr_bandwidthAddPeer( tr_bandwidth   * b,
356                     tr_peerIo      * peerIo )
357{
358    assert( tr_isBandwidth( b ) );
359    assert( tr_isPeerIo( peerIo ) );
360
361    tr_ptrArrayInsertSorted( b->peers, peerIo, comparePointers );
362}
363
364void
365tr_bandwidthRemovePeer( tr_bandwidth  * b,
366                        tr_peerIo     * peerIo )
367{
368    assert( tr_isBandwidth( b ) );
369    assert( tr_isPeerIo( peerIo ) );
370
371    tr_ptrArrayRemoveSorted( b->peers, peerIo, comparePointers );
372}
373
374/***
375****
376***/
377
378size_t
379tr_bandwidthClamp( const tr_bandwidth  * b,
380                   tr_direction          dir,
381                   size_t                byteCount )
382{
383    assert( tr_isBandwidth( b ) );
384    assert( tr_isDirection( dir ) );
385
386    if( b )
387    {
388        if( b->band[dir].isLimited )
389            byteCount = MIN( byteCount, b->band[dir].bytesLeft );
390
391        if( b->parent && b->band[dir].honorParentLimits )
392            byteCount = tr_bandwidthClamp( b->parent, dir, byteCount );
393    }
394
395    return byteCount;
396}
397
398double
399tr_bandwidthGetRawSpeed( const tr_bandwidth * b, tr_direction dir )
400{
401    assert( tr_isBandwidth( b ) );
402    assert( tr_isDirection( dir ) );
403
404    return getSpeed( &b->band[dir].raw, HISTORY_MSEC );
405}
406
407double
408tr_bandwidthGetPieceSpeed( const tr_bandwidth * b, tr_direction dir )
409{
410    assert( tr_isBandwidth( b ) );
411    assert( tr_isDirection( dir ) );
412
413    return getSpeed( &b->band[dir].piece, HISTORY_MSEC );
414}
415
416void
417tr_bandwidthUsed( tr_bandwidth  * b,
418                  tr_direction    dir,
419                  size_t          byteCount,
420                  tr_bool         isPieceData )
421{
422    struct tr_band * band;
423    size_t oldBytesLeft;
424
425    assert( tr_isBandwidth( b ) );
426    assert( tr_isDirection( dir ) );
427
428    band = &b->band[dir];
429
430    oldBytesLeft = band->bytesLeft;
431
432    if( band->isLimited && isPieceData )
433        band->bytesLeft -= MIN( band->bytesLeft, byteCount );
434
435#ifdef DEBUG_DIRECTION
436if( ( dir == DEBUG_DIRECTION ) && ( band->isLimited ) )
437fprintf( stderr, "%p consumed %5zu bytes of %5s data... was %6zu, now %6zu left\n",
438         b, byteCount, (isPieceData?"piece":"raw"), oldBytesLeft, band->bytesLeft );
439#endif
440
441    bytesUsed( &band->raw, byteCount );
442
443    if( isPieceData )
444        bytesUsed( &band->piece, byteCount );
445
446    if( b->parent != NULL )
447        tr_bandwidthUsed( b->parent, dir, byteCount, isPieceData );
448}
Note: See TracBrowser for help on using the repository browser.