source: trunk/libtransmission/bandwidth.c @ 8483

Last change on this file since 8483 was 8483, checked in by charles, 13 years ago

(trunk libT) fix a couple of dead assignments, and a possible null pointer dereference, found by clang

  • Property svn:keywords set to Date Rev Author Id
File size: 10.4 KB
Line 
1/*
2 * This file Copyright (C) 2008-2009 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 8483 2009-05-22 19:03:00Z 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, uint64_t now )
37{
38    uint64_t       bytes = 0;
39    const uint64_t cutoff = (now?now: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( const uint64_t now, struct bratecontrol * r, size_t size )
58{
59    if( r->transfers[r->newest].date + GRANULARITY_MSEC >= now )
60        r->transfers[r->newest].size += size;
61    else
62    {
63        if( ++r->newest == HISTORY_SIZE ) r->newest = 0;
64        r->transfers[r->newest].date = now;
65        r->transfers[r->newest].size = size;
66    }
67}
68
69/******
70*******
71*******
72******/
73
74static TR_INLINE int
75comparePointers( const void * a, const void * b )
76{
77    if( a != b )
78        return a < b ? -1 : 1;
79
80    return 0;
81}
82
83/***
84****
85***/
86
87tr_bandwidth*
88tr_bandwidthConstruct( tr_bandwidth * b, tr_session * session, tr_bandwidth * parent )
89{
90    b->session = session;
91    b->children = TR_PTR_ARRAY_INIT;
92    b->magicNumber = MAGIC_NUMBER;
93    b->band[TR_UP].honorParentLimits = TRUE;
94    b->band[TR_DOWN].honorParentLimits = TRUE;
95    tr_bandwidthSetParent( b, parent );
96    return b;
97}
98
99tr_bandwidth*
100tr_bandwidthDestruct( tr_bandwidth * b )
101{
102    assert( tr_isBandwidth( b ) );
103
104    tr_bandwidthSetParent( b, NULL );
105    tr_ptrArrayDestruct( &b->children, NULL );
106
107    memset( b, ~0, sizeof( tr_bandwidth ) );
108    return b;
109}
110
111/***
112****
113***/
114
115void
116tr_bandwidthSetParent( tr_bandwidth  * b,
117                       tr_bandwidth  * parent )
118{
119    assert( tr_isBandwidth( b ) );
120    assert( b != parent );
121
122    if( b->parent )
123    {
124        assert( tr_isBandwidth( b->parent ) );
125
126        tr_ptrArrayRemoveSorted( &b->parent->children, b, comparePointers );
127        b->parent = NULL;
128    }
129
130    if( parent )
131    {
132        assert( tr_isBandwidth( parent ) );
133        assert( parent->parent != b );
134
135        tr_ptrArrayInsertSorted( &parent->children, b, comparePointers );
136        b->parent = parent;
137    }
138}
139
140/***
141****
142***/
143
144#if 0
145#warning do not check the code in with this enabled
146#define DEBUG_DIRECTION TR_UP
147#endif
148
149static void
150allocateBandwidth( tr_bandwidth  * b,
151                   tr_priority_t   parent_priority,
152                   tr_direction    dir,
153                   int             period_msec,
154                   tr_ptrArray   * peer_pool )
155{
156    tr_priority_t priority;
157
158    assert( tr_isBandwidth( b ) );
159    assert( tr_isDirection( dir ) );
160
161    /* set the available bandwidth */
162    if( b->band[dir].isLimited )
163    {
164        const double desiredSpeed = b->band[dir].desiredSpeed;
165        const double nextPulseSpeed = desiredSpeed;
166        b->band[dir].bytesLeft = MAX( 0.0, nextPulseSpeed * 1024.0 * period_msec / 1000.0 );
167
168#ifdef DEBUG_DIRECTION
169        if( dir == DEBUG_DIRECTION )
170                fprintf( stderr, "bandwidth %p currentPieceSpeed(%5.2f of %5.2f) desiredSpeed(%5.2f), allocating %5.2f\n",
171                         b, currentSpeed, tr_bandwidthGetRawSpeed( b, dir ), desiredSpeed,
172                         b->band[dir].bytesLeft/1024.0 );
173#endif
174    }
175
176    priority = MAX( parent_priority, b->priority );
177
178    /* add this bandwidth's peer, if any, to the peer pool */
179    if( b->peer != NULL ) {
180        b->peer->priority = priority;
181        tr_ptrArrayAppend( peer_pool, b->peer );
182    }
183
184#ifdef DEBUG_DIRECTION
185if( ( dir == DEBUG_DIRECTION ) && ( n > 1 ) )
186fprintf( stderr, "bandwidth %p has %d peers\n", b, n );
187#endif
188
189    /* traverse & repeat for the subtree */
190    if( 1 ) {
191        int i;
192        struct tr_bandwidth ** children = (struct tr_bandwidth**) tr_ptrArrayBase( &b->children );
193        const int n = tr_ptrArraySize( &b->children );
194        for( i=0; i<n; ++i )
195            allocateBandwidth( children[i], priority, dir, period_msec, peer_pool );
196    }
197}
198
199static void
200phaseOne( tr_ptrArray * peerArray, tr_direction dir )
201{
202    int i, n;
203    int peerCount = tr_ptrArraySize( peerArray );
204    struct tr_peerIo ** peers = (struct tr_peerIo**) tr_ptrArrayBase( peerArray );
205
206    /* First phase of IO.  Tries to distribute bandwidth fairly to keep faster
207     * peers from starving the others.  Loop through the peers, giving each a
208     * small chunk of bandwidth.  Keep looping until we run out of bandwidth
209     * and/or peers that can use it */
210    n = peerCount;
211    dbgmsg( "%d peers to go round-robin for %s", n, (dir==TR_UP?"upload":"download") );
212    i = n ? tr_cryptoWeakRandInt( n ) : 0; /* pick a random starting point */
213    while( n > 1 )
214    {
215        const size_t increment = 1024;
216        const int bytesUsed = tr_peerIoFlush( peers[i], dir, increment );
217
218        dbgmsg( "peer #%d of %d used %d bytes in this pass", i, n, bytesUsed );
219
220        if( bytesUsed == (int)increment )
221            ++i;
222        else {
223            /* peer is done writing for now; move it to the end of the list */
224            tr_peerIo * pio = peers[i];
225            peers[i] = peers[n-1];
226            peers[n-1] = pio;
227            --n;
228        }
229
230        if( i == n )
231            i = 0;
232    }
233}
234
235void
236tr_bandwidthAllocate( tr_bandwidth  * b,
237                      tr_direction    dir,
238                      int             period_msec )
239{
240    int i, peerCount;
241    tr_ptrArray tmp = TR_PTR_ARRAY_INIT;
242    tr_ptrArray low = TR_PTR_ARRAY_INIT;
243    tr_ptrArray high = TR_PTR_ARRAY_INIT;
244    tr_ptrArray normal = TR_PTR_ARRAY_INIT;
245    struct tr_peerIo ** peers;
246
247    /* allocateBandwidth() is a helper function with two purposes:
248     * 1. allocate bandwidth to b and its subtree
249     * 2. accumulate an array of all the peerIos from b and its subtree. */
250    allocateBandwidth( b, TR_PRI_LOW, dir, period_msec, &tmp );
251    peers = (struct tr_peerIo**) tr_ptrArrayBase( &tmp );
252    peerCount = tr_ptrArraySize( &tmp );
253
254    for( i=0; i<peerCount; ++i )
255    {
256        tr_peerIo * io = peers[i];
257        tr_peerIoRef( io );
258
259        tr_peerIoFlushOutgoingProtocolMsgs( io );
260
261        switch( io->priority ) {
262            case TR_PRI_HIGH: tr_ptrArrayAppend( &high,   io ); break;
263            case TR_PRI_LOW:  tr_ptrArrayAppend( &low,    io ); break;
264            default:          tr_ptrArrayAppend( &normal, io ); break;
265        }
266    }
267
268    /* First phase of IO.  Tries to distribute bandwidth fairly to keep faster
269     * peers from starving the others.  Loop through the peers, giving each a
270     * small chunk of bandwidth.  Keep looping until we run out of bandwidth
271     * and/or peers that can use it */
272    phaseOne( &high, dir );
273    phaseOne( &normal, dir );
274    phaseOne( &low, dir );
275
276    /* Second phase of IO.  To help us scale in high bandwidth situations,
277     * enable on-demand IO for peers with bandwidth left to burn.
278     * This on-demand IO is enabled until (1) the peer runs out of bandwidth,
279     * or (2) the next tr_bandwidthAllocate() call, when we start over again. */
280    for( i=0; i<peerCount; ++i )
281        tr_peerIoSetEnabled( peers[i], dir, tr_peerIoHasBandwidthLeft( peers[i], dir ) );
282
283    for( i=0; i<peerCount; ++i )
284        tr_peerIoUnref( peers[i] );
285
286    /* cleanup */
287    tr_ptrArrayDestruct( &normal, NULL );
288    tr_ptrArrayDestruct( &high, NULL );
289    tr_ptrArrayDestruct( &low, NULL );
290    tr_ptrArrayDestruct( &tmp, NULL );
291}
292
293void
294tr_bandwidthSetPeer( tr_bandwidth * b, tr_peerIo * peer )
295{
296    assert( tr_isBandwidth( b ) );
297    assert( ( peer == NULL ) || tr_isPeerIo( peer ) );
298
299    b->peer = peer;
300}
301
302/***
303****
304***/
305
306size_t
307tr_bandwidthClamp( const tr_bandwidth  * b,
308                   tr_direction          dir,
309                   size_t                byteCount )
310{
311    assert( tr_isBandwidth( b ) );
312    assert( tr_isDirection( dir ) );
313
314    if( b )
315    {
316        if( b->band[dir].isLimited )
317            byteCount = MIN( byteCount, b->band[dir].bytesLeft );
318
319        if( b->parent && b->band[dir].honorParentLimits )
320            byteCount = tr_bandwidthClamp( b->parent, dir, byteCount );
321    }
322
323    return byteCount;
324}
325
326double
327tr_bandwidthGetRawSpeed( const tr_bandwidth * b, const uint64_t now, const tr_direction dir )
328{
329    assert( tr_isBandwidth( b ) );
330    assert( tr_isDirection( dir ) );
331
332    return getSpeed( &b->band[dir].raw, HISTORY_MSEC, now );
333}
334
335double
336tr_bandwidthGetPieceSpeed( const tr_bandwidth * b, const uint64_t now, const tr_direction dir )
337{
338    assert( tr_isBandwidth( b ) );
339    assert( tr_isDirection( dir ) );
340
341    return getSpeed( &b->band[dir].piece, HISTORY_MSEC, now );
342}
343
344static void
345bandwidthUsedImpl( tr_bandwidth  * b,
346                   tr_direction    dir,
347                   size_t          byteCount,
348                   tr_bool         isPieceData,
349                   uint64_t        now )
350{
351    struct tr_band * band;
352
353    assert( tr_isBandwidth( b ) );
354    assert( tr_isDirection( dir ) );
355
356    band = &b->band[dir];
357
358    if( band->isLimited && isPieceData )
359        band->bytesLeft -= MIN( band->bytesLeft, byteCount );
360
361#ifdef DEBUG_DIRECTION
362if( ( dir == DEBUG_DIRECTION ) && ( band->isLimited ) )
363fprintf( stderr, "%p consumed %5zu bytes of %5s data... was %6zu, now %6zu left\n",
364         b, byteCount, (isPieceData?"piece":"raw"), oldBytesLeft, band->bytesLeft );
365#endif
366
367    bytesUsed( now, &band->raw, byteCount );
368
369    if( isPieceData )
370        bytesUsed( now, &band->piece, byteCount );
371
372    if( b->parent != NULL )
373        bandwidthUsedImpl( b->parent, dir, byteCount, isPieceData, now );
374}
375
376void
377tr_bandwidthUsed( tr_bandwidth  * b,
378                  tr_direction    dir,
379                  size_t          byteCount,
380                  tr_bool         isPieceData )
381{
382    bandwidthUsedImpl( b, dir, byteCount, isPieceData, tr_date( ) );
383}
Note: See TracBrowser for help on using the repository browser.