source: trunk/libtransmission/bandwidth.c @ 7586

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

(trunk libT) commit some debugging messages that were added to trackdown the multicast filter issue

  • Property svn:keywords set to Date Rev Author Id
File size: 8.7 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: bandwidth.c 7586 2009-01-02 21:50:51Z charles $
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#define dbgmsg( ... ) \
26    do { \
27        if( tr_deepLoggingIsActive( ) ) \
28            tr_deepLog( __FILE__, __LINE__, NULL, __VA_ARGS__ ); \
29    } while( 0 )
30
31/***
32****
33***/
34
35static float
36getSpeed( const struct bratecontrol * r, int interval_msec )
37{
38    uint64_t       bytes = 0;
39    const uint64_t cutoff = tr_date ( ) - interval_msec;
40    int            i = r->newest;
41
42    for( ;; )
43    {
44        if( r->transfers[i].date <= cutoff )
45            break;
46
47        bytes += r->transfers[i].size;
48
49        if( --i == -1 ) i = HISTORY_SIZE - 1; /* circular history */
50        if( i == r->newest ) break; /* we've come all the way around */
51    }
52
53    return ( bytes / 1024.0 ) * ( 1000.0 / interval_msec );
54}
55
56static void
57bytesUsed( struct bratecontrol * r, size_t size )
58{
59    const uint64_t now = tr_date ( );
60
61    if( r->transfers[r->newest].date + GRANULARITY_MSEC >= now )
62        r->transfers[r->newest].size += size;
63    else
64    {
65        if( ++r->newest == HISTORY_SIZE ) r->newest = 0;
66        r->transfers[r->newest].date = now;
67        r->transfers[r->newest].size = size;
68    }
69}
70
71/******
72*******
73*******
74******/
75
76static inline int
77comparePointers( const void * a, const void * b )
78{
79    if( a != b )
80        return a < b ? -1 : 1;
81
82    return 0;
83}
84
85/***
86****
87***/
88
89tr_bandwidth*
90tr_bandwidthConstruct( tr_bandwidth * b, tr_session * session, tr_bandwidth * parent )
91{
92    b->session = session;
93    b->children = TR_PTR_ARRAY_INIT;
94    b->magicNumber = MAGIC_NUMBER;
95    b->band[TR_UP].honorParentLimits = TRUE;
96    b->band[TR_DOWN].honorParentLimits = TRUE;
97    tr_bandwidthSetParent( b, parent );
98    return b;
99}
100
101tr_bandwidth*
102tr_bandwidthDestruct( tr_bandwidth * b )
103{
104    assert( tr_isBandwidth( b ) );
105
106    tr_bandwidthSetParent( b, NULL );
107    tr_ptrArrayDestruct( &b->children, NULL );
108    b->magicNumber = 0xDEAD;
109
110    return b;
111}
112
113/***
114****
115***/
116
117void
118tr_bandwidthSetParent( tr_bandwidth  * b,
119                       tr_bandwidth  * parent )
120{
121    assert( tr_isBandwidth( b ) );
122    assert( b != parent );
123
124    if( b->parent )
125    {
126        assert( tr_isBandwidth( b->parent ) );
127
128        tr_ptrArrayRemoveSorted( &b->parent->children, b, comparePointers );
129        b->parent = NULL;
130    }
131
132    if( parent )
133    {
134        assert( tr_isBandwidth( parent ) );
135        assert( parent->parent != b );
136
137        tr_ptrArrayInsertSorted( &parent->children, b, comparePointers );
138        b->parent = parent;
139    }
140}
141
142/***
143****
144***/
145
146#if 0
147#warning do not check the code in with this enabled
148#define DEBUG_DIRECTION TR_UP
149#endif
150
151static void
152allocateBandwidth( tr_bandwidth  * b,
153                   tr_direction    dir,
154                   int             period_msec,
155                   tr_ptrArray   * peer_pool )
156{
157    assert( tr_isBandwidth( b ) );
158    assert( tr_isDirection( dir ) );
159
160    /* set the available bandwidth */
161    if( b->band[dir].isLimited )
162    {
163        const double desiredSpeed = b->band[dir].desiredSpeed;
164        const double nextPulseSpeed = desiredSpeed;
165        b->band[dir].bytesLeft = MAX( 0.0, nextPulseSpeed * 1024.0 * period_msec / 1000.0 );
166
167#ifdef DEBUG_DIRECTION
168        if( dir == DEBUG_DIRECTION )
169                fprintf( stderr, "bandwidth %p currentPieceSpeed(%5.2f of %5.2f) desiredSpeed(%5.2f), allocating %5.2f\n",
170                         b, currentSpeed, tr_bandwidthGetRawSpeed( b, dir ), desiredSpeed,
171                         b->band[dir].bytesLeft/1024.0 );
172#endif
173    }
174
175    /* add this bandwidth's peer, if any, to the peer pool */
176    if( b->peer != NULL )
177        tr_ptrArrayAppend( peer_pool, b->peer );
178
179#ifdef DEBUG_DIRECTION
180if( ( dir == DEBUG_DIRECTION ) && ( n > 1 ) )
181fprintf( stderr, "bandwidth %p has %d peers\n", b, n );
182#endif
183
184    /* traverse & repeat for the subtree */
185    if( 1 ) {
186        int i;
187        struct tr_bandwidth ** children = (struct tr_bandwidth**) TR_PTR_ARRAY_DATA( &b->children );
188        const int n = TR_PTR_ARRAY_LENGTH( &b->children );
189        for( i=0; i<n; ++i )
190            allocateBandwidth( children[i], dir, period_msec, peer_pool );
191    }
192}
193
194void
195tr_bandwidthAllocate( tr_bandwidth  * b,
196                      tr_direction    dir,
197                      int             period_msec )
198{
199    int i, n, peerCount;
200    tr_ptrArray tmp = TR_PTR_ARRAY_INIT;
201    struct tr_peerIo ** peers;
202
203
204    /* allocateBandwidth() is a helper function with two purposes:
205     * 1. allocate bandwidth to b and its subtree
206     * 2. accumulate an array of all the peerIos from b and its subtree. */
207    allocateBandwidth( b, dir, period_msec, &tmp );
208    peers = (struct tr_peerIo**) TR_PTR_ARRAY_DATA( &tmp );
209    peerCount = TR_PTR_ARRAY_LENGTH( &tmp );
210
211    /* Stop all peers from listening for the socket to be ready for IO.
212     * See "Second phase of IO" lower in this function for more info. */
213    for( i=0; i<peerCount; ++i )
214        tr_peerIoSetEnabled( peers[i], dir, FALSE );
215
216    /* First phase of IO.  Tries to distribute bandwidth fairly to keep faster
217     * peers from starving the others.  Loop through the peers, giving each a
218     * small chunk of bandwidth.  Keep looping until we run out of bandwidth
219     * and/or peers that can use it */
220    n = peerCount;
221    dbgmsg( "direction %s ... %d pees to go round-robin", (dir==TR_UP?"UP":"DOWN"), n );
222    i = n ? tr_cryptoWeakRandInt( n ) : 0; /* pick a random starting point */
223    while( n > 1 )
224    {
225        const int increment = 1024;
226        const int bytesUsed = tr_peerIoFlush( peers[i], dir, increment );
227
228        if( bytesUsed == increment )
229            ++i;
230        else {
231            /* peer is done writing for now; move it to the end of the list */
232            tr_peerIo * pio = peers[i];
233            peers[i] = peers[n-1];
234            peers[n-1] = pio;
235            --n;
236        }
237
238        if( i == n )
239            i = 0;
240    }
241
242    /* Second phase of IO.  To help us scale in high bandwidth situations,
243     * enable on-demand IO for peers with bandwidth left to burn.
244     * This on-demand IO is enabled until (1) the peer runs out of bandwidth,
245     * or (2) the next tr_bandwidthAllocate() call, when we start over again. */
246    for( i=0; i<peerCount; ++i )
247        if( tr_peerIoHasBandwidthLeft( peers[i], dir ) )
248            tr_peerIoSetEnabled( peers[i], dir, TRUE );
249
250    /* cleanup */
251    tr_ptrArrayDestruct( &tmp, NULL );
252}
253
254void
255tr_bandwidthSetPeer( tr_bandwidth * b, tr_peerIo * peer )
256{
257    assert( tr_isBandwidth( b ) );
258    assert( ( peer == NULL ) || tr_isPeerIo( peer ) );
259
260    b->peer = peer;
261}
262
263/***
264****
265***/
266
267size_t
268tr_bandwidthClamp( const tr_bandwidth  * b,
269                   tr_direction          dir,
270                   size_t                byteCount )
271{
272    assert( tr_isBandwidth( b ) );
273    assert( tr_isDirection( dir ) );
274
275    if( b )
276    {
277        if( b->band[dir].isLimited )
278            byteCount = MIN( byteCount, b->band[dir].bytesLeft );
279
280        if( b->parent && b->band[dir].honorParentLimits )
281            byteCount = tr_bandwidthClamp( b->parent, dir, byteCount );
282    }
283
284    return byteCount;
285}
286
287double
288tr_bandwidthGetRawSpeed( const tr_bandwidth * b, tr_direction dir )
289{
290    assert( tr_isBandwidth( b ) );
291    assert( tr_isDirection( dir ) );
292
293    return getSpeed( &b->band[dir].raw, HISTORY_MSEC );
294}
295
296double
297tr_bandwidthGetPieceSpeed( const tr_bandwidth * b, tr_direction dir )
298{
299    assert( tr_isBandwidth( b ) );
300    assert( tr_isDirection( dir ) );
301
302    return getSpeed( &b->band[dir].piece, HISTORY_MSEC );
303}
304
305void
306tr_bandwidthUsed( tr_bandwidth  * b,
307                  tr_direction    dir,
308                  size_t          byteCount,
309                  tr_bool         isPieceData )
310{
311    struct tr_band * band;
312    size_t oldBytesLeft;
313
314    assert( tr_isBandwidth( b ) );
315    assert( tr_isDirection( dir ) );
316
317    band = &b->band[dir];
318
319    oldBytesLeft = band->bytesLeft;
320
321    if( band->isLimited && isPieceData )
322        band->bytesLeft -= MIN( band->bytesLeft, byteCount );
323
324#ifdef DEBUG_DIRECTION
325if( ( dir == DEBUG_DIRECTION ) && ( band->isLimited ) )
326fprintf( stderr, "%p consumed %5zu bytes of %5s data... was %6zu, now %6zu left\n",
327         b, byteCount, (isPieceData?"piece":"raw"), oldBytesLeft, band->bytesLeft );
328#endif
329
330    bytesUsed( &band->raw, byteCount );
331
332    if( isPieceData )
333        bytesUsed( &band->piece, byteCount );
334
335    if( b->parent != NULL )
336        tr_bandwidthUsed( b->parent, dir, byteCount, isPieceData );
337}
Note: See TracBrowser for help on using the repository browser.