source: trunk/libtransmission/bandwidth.c @ 7441

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

try to rework the bandwidth code yet again s.t. it satisfies all three: (1) fairly distributes bandwidth across all peers, (2) scales well in high-bandwidth situations, (3) is good at hitting and staying at bandwidth limits/goals

File size: 11.1 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    return a - b;
113}
114
115static int
116isBandwidth( const tr_bandwidth * b )
117{
118    return ( b != NULL ) && ( b->magicNumber == MAGIC_NUMBER );
119}
120
121static int
122isDirection( const tr_direction dir )
123{
124    return ( dir == TR_UP ) || ( dir == TR_DOWN );
125}
126
127/***
128****
129***/
130
131tr_bandwidth*
132tr_bandwidthNew( tr_session * session, tr_bandwidth * parent )
133{
134    tr_bandwidth * b = tr_new0( tr_bandwidth, 1 );
135    b->session = session;
136    b->children = tr_ptrArrayNew( );
137    b->peers = tr_ptrArrayNew( );
138    b->magicNumber = MAGIC_NUMBER;
139    b->band[TR_UP].honorParentLimits = 1;
140    b->band[TR_DOWN].honorParentLimits = 1;
141    tr_bandwidthSetParent( b, parent );
142    return b;
143}
144
145void
146tr_bandwidthFree( tr_bandwidth * b )
147{
148    assert( isBandwidth( b ) );
149
150    tr_bandwidthSetParent( b, NULL );
151    tr_ptrArrayFree( b->peers, NULL );
152    tr_ptrArrayFree( b->children, NULL );
153    b->magicNumber = 0xDEAD;
154    tr_free( b );
155}
156
157/***
158****
159***/
160
161void
162tr_bandwidthSetParent( tr_bandwidth  * b,
163                       tr_bandwidth  * parent )
164{
165    assert( isBandwidth( b ) );
166    assert( b != parent );
167
168    if( b->parent )
169    {
170        assert( isBandwidth( b->parent ) );
171
172        tr_ptrArrayRemoveSorted( b->parent->children, b, comparePointers );
173        b->parent= NULL;
174    }
175
176    if( parent )
177    {
178        assert( isBandwidth( parent ) );
179        assert( parent->parent != b );
180
181        tr_ptrArrayInsertSorted( parent->children, b, comparePointers );
182        b->parent = parent;
183    }
184}
185
186void
187tr_bandwidthHonorParentLimits( tr_bandwidth  * b,
188                               tr_direction    dir,
189                               int             honorParentLimits )
190{
191    assert( isBandwidth( b ) );
192    assert( isDirection( dir ) );
193
194    b->band[dir].honorParentLimits = honorParentLimits != 0;
195}
196
197/***
198****
199***/
200
201void
202tr_bandwidthSetDesiredSpeed( tr_bandwidth  * b,
203                             tr_direction    dir,
204                             double          desiredSpeed )
205{
206    assert( isBandwidth( b ) );
207    assert( isDirection( dir ) );
208
209    b->band[dir].desiredSpeed = desiredSpeed; 
210}
211
212double
213tr_bandwidthGetDesiredSpeed( const tr_bandwidth  * b,
214                             tr_direction          dir )
215{
216    assert( isBandwidth( b ) );
217    assert( isDirection( dir ) );
218
219    return b->band[dir].desiredSpeed;
220}
221
222void
223tr_bandwidthSetLimited( tr_bandwidth  * b,
224                        tr_direction    dir,
225                        int             isLimited )
226{
227    assert( isBandwidth( b ) );
228    assert( isDirection( dir ) );
229
230    b->band[dir].isLimited = isLimited != 0;
231}
232
233int
234tr_bandwidthIsLimited( const tr_bandwidth  * b,
235                       tr_direction          dir )
236{
237    assert( isBandwidth( b ) );
238    assert( isDirection( dir ) );
239
240    return b->band[dir].isLimited != 0;
241}
242
243#if 0
244#warning do not check the code in with this enabled
245#define DEBUG_DIRECTION TR_UP
246#endif
247
248static void
249allocateBandwidth( tr_bandwidth  * b,
250                   tr_direction    dir,
251                   int             period_msec,
252                   tr_ptrArray   * peer_pool )
253{
254    assert( isBandwidth( b ) );
255    assert( isDirection( dir ) );
256
257    if( b->band[dir].isLimited )
258    {
259        const double desiredSpeed = b->band[dir].desiredSpeed;
260        const double nextPulseSpeed = desiredSpeed;
261        b->band[dir].bytesLeft = MAX( 0.0, nextPulseSpeed * 1024.0 * period_msec / 1000.0 );
262
263#ifdef DEBUG_DIRECTION
264        if( dir == DEBUG_DIRECTION )
265                fprintf( stderr, "bandwidth %p currentPieceSpeed(%5.2f of %5.2f) desiredSpeed(%5.2f), allocating %5.2f\n",
266                         b, currentSpeed, tr_bandwidthGetRawSpeed( b, dir ), desiredSpeed,
267                         b->band[dir].bytesLeft/1024.0 );
268#endif
269    }
270
271    {
272        int i;
273        const int n = tr_ptrArraySize( b->peers );
274        for( i=0; i<n; ++i )
275            tr_ptrArrayAppend( peer_pool, tr_ptrArrayNth( b->peers, i ) );
276    }
277
278#ifdef DEBUG_DIRECTION
279if( ( dir == DEBUG_DIRECTION ) && ( n > 1 ) )
280fprintf( stderr, "bandwidth %p has %d peers\n", b, n );
281#endif
282
283    /* all children should reallocate too */
284    if( 1 ) {
285        int i, n=0;
286        struct tr_bandwidth ** children = (struct tr_bandwidth**) tr_ptrArrayPeek( b->children, &n );
287        for( i=0; i<n; ++i )
288            allocateBandwidth( children[i], dir, period_msec, peer_pool );
289    }
290}
291
292void
293tr_bandwidthAllocate( tr_bandwidth  * b,
294                      tr_direction    dir,
295                      int             period_msec )
296{
297    int i, n, peerCount;
298    tr_ptrArray * tmp;
299    struct tr_peerIo ** peers;
300
301    /* allocateBandwidth() is a helper function with two purposes:
302     * 1. allocate bandwidth to b and its subtree
303     * 2. accumulate an array of all the peerIos from b and its subtree. */
304    tmp = tr_ptrArrayNew( );
305    allocateBandwidth( b, dir, period_msec, tmp );
306    peers = (struct tr_peerIo**) tr_ptrArrayPeek( tmp, &peerCount );
307
308    /* Stop all peers from listening for the socket to be ready for IO.
309     * See "Second phase of IO" lower in this function for more info. */
310    for( i=0; i<peerCount; ++i )
311        tr_peerIoSetEnabled( peers[i], dir, FALSE );
312
313    /* First phase of IO.  Tries to distribute bandwidth in a fair/even manner
314     * to avoid "greedy peers" from starving out the other peers: loop through
315     * peers in a round-robin fashion, giving each one of them them small chunks
316     * of bandwidth to use.  (It's small to conserve some of the bandwidth
317     * until the end of the loop).  Keep looping until we run out of bandwidth
318     * or peers that are ready to use it. */
319    n = peerCount;
320    i = n ? tr_cryptoWeakRandInt( n ) : 0; /* pick a random starting point */
321    for( ; n>0; )
322    {
323        const int increment = n==1 ? 4096 : 1024;
324        const int byteCount = tr_peerIoFlush( peers[i], dir, increment);
325
326        if( byteCount == increment )
327            ++i;
328        else {
329            /* peer is done writing for now; move it to the end of the list */
330            tr_peerIo * tmp = peers[i];
331            peers[i] = peers[n-1];
332            peers[n-1] = tmp;
333            --n;
334        }
335
336        assert( i <= n );
337        if( i == n )
338            i = 0;
339    }
340
341    /* Second phase of IO.  To help us scale well in high bandiwdth situations
342     * such as LANs, enable on-demand IO for peers with bandwidth left to burn.
343     * This on-demand IO for a peer is enabled until either (1) the peer runs
344     * out of bandwidth, or (2) the next tr_bandwidthAllocate() call, when we
345     * start all over again. */
346    for( i=0; i<peerCount; ++i )
347        if( tr_peerIoHasBandwidthLeft( peers[i], dir ) )
348            tr_peerIoSetEnabled( peers[i], dir, TRUE );
349
350    /* cleanup */
351    tr_ptrArrayFree( tmp, NULL );
352}
353
354/***
355****
356***/
357
358void
359tr_bandwidthAddPeer( tr_bandwidth   * b,
360                     tr_peerIo      * peerIo )
361{
362    assert( isBandwidth( b ) );
363    assert( peerIo );
364
365    tr_ptrArrayInsertSorted( b->peers, peerIo, comparePointers );
366}
367
368void
369tr_bandwidthRemovePeer( tr_bandwidth  * b,
370                        tr_peerIo     * peerIo )
371{
372    assert( isBandwidth( b ) );
373    assert( peerIo );
374
375    tr_ptrArrayRemoveSorted( b->peers, peerIo, comparePointers );
376}
377
378/***
379****
380***/
381
382size_t
383tr_bandwidthClamp( const tr_bandwidth  * b,
384                   tr_direction          dir,
385                   size_t                byteCount )
386{
387    assert( isBandwidth( b ) );
388    assert( isDirection( dir ) );
389
390    if( b )
391    {
392        if( b->band[dir].isLimited )
393            byteCount = MIN( byteCount, b->band[dir].bytesLeft );
394
395        if( b->parent && b->band[dir].honorParentLimits )
396            byteCount = tr_bandwidthClamp( b->parent, dir, byteCount );
397    }
398
399    return byteCount;
400}
401
402double
403tr_bandwidthGetRawSpeed( const tr_bandwidth * b, tr_direction dir )
404{
405    assert( isBandwidth( b ) );
406    assert( isDirection( dir ) );
407
408    return getSpeed( &b->band[dir].raw, HISTORY_MSEC );
409}
410
411double
412tr_bandwidthGetPieceSpeed( const tr_bandwidth * b, tr_direction dir )
413{
414    assert( isBandwidth( b ) );
415    assert( isDirection( dir ) );
416
417    return getSpeed( &b->band[dir].piece, HISTORY_MSEC );
418}
419
420void
421tr_bandwidthUsed( tr_bandwidth  * b,
422                  tr_direction    dir,
423                  size_t          byteCount,
424                  int             isPieceData )
425{
426    struct tr_band * band;
427    size_t oldBytesLeft;
428
429    assert( isBandwidth( b ) );
430    assert( isDirection( dir ) );
431
432    band = &b->band[dir];
433
434    oldBytesLeft = band->bytesLeft;
435
436    if( band->isLimited && isPieceData )
437        band->bytesLeft -= MIN( band->bytesLeft, byteCount );
438
439#ifdef DEBUG_DIRECTION
440if( ( dir == DEBUG_DIRECTION ) && ( band->isLimited ) )
441fprintf( stderr, "%p consumed %5zu bytes of %5s data... was %6zu, now %6zu left\n",
442         b, byteCount, (isPieceData?"piece":"raw"), oldBytesLeft, band->bytesLeft );
443#endif
444
445    bytesUsed( &band->raw, byteCount );
446
447    if( isPieceData )
448        bytesUsed( &band->piece, byteCount );
449
450    if( b->parent != NULL )
451        tr_bandwidthUsed( b->parent, dir, byteCount, isPieceData );
452}
Note: See TracBrowser for help on using the repository browser.