source: trunk/libtransmission/bandwidth.c @ 7587

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

(trunk libT) fix a typo that made jhujhiti giggle

  • 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 7587 2009-01-02 22:06:11Z 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( "%d peers to go round-robin for %s", n, (dir==TR_UP?"upload":"download") );
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.