source: trunk/libtransmission/bandwidth.c @ 7592

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

(trunk libT) add "deep log" message to help track down freeze reported by the|Navigator. also, small + cheap speedup in tr_deepLoggingIsActive()

  • Property svn:keywords set to Date Rev Author Id
File size: 9.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: bandwidth.c 7592 2009-01-03 02:43:17Z 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( 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 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    b->magicNumber = 0xDEAD;
107
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_direction    dir,
152                   int             period_msec,
153                   tr_ptrArray   * peer_pool )
154{
155    assert( tr_isBandwidth( b ) );
156    assert( tr_isDirection( dir ) );
157
158    /* set the available bandwidth */
159    if( b->band[dir].isLimited )
160    {
161        const double desiredSpeed = b->band[dir].desiredSpeed;
162        const double nextPulseSpeed = desiredSpeed;
163        b->band[dir].bytesLeft = MAX( 0.0, nextPulseSpeed * 1024.0 * period_msec / 1000.0 );
164
165#ifdef DEBUG_DIRECTION
166        if( dir == DEBUG_DIRECTION )
167                fprintf( stderr, "bandwidth %p currentPieceSpeed(%5.2f of %5.2f) desiredSpeed(%5.2f), allocating %5.2f\n",
168                         b, currentSpeed, tr_bandwidthGetRawSpeed( b, dir ), desiredSpeed,
169                         b->band[dir].bytesLeft/1024.0 );
170#endif
171    }
172
173    /* add this bandwidth's peer, if any, to the peer pool */
174    if( b->peer != NULL )
175        tr_ptrArrayAppend( peer_pool, b->peer );
176
177#ifdef DEBUG_DIRECTION
178if( ( dir == DEBUG_DIRECTION ) && ( n > 1 ) )
179fprintf( stderr, "bandwidth %p has %d peers\n", b, n );
180#endif
181
182    /* traverse & repeat for the subtree */
183    if( 1 ) {
184        int i;
185        struct tr_bandwidth ** children = (struct tr_bandwidth**) TR_PTR_ARRAY_DATA( &b->children );
186        const int n = TR_PTR_ARRAY_LENGTH( &b->children );
187        for( i=0; i<n; ++i )
188            allocateBandwidth( children[i], dir, period_msec, peer_pool );
189    }
190}
191
192void
193tr_bandwidthAllocate( tr_bandwidth  * b,
194                      tr_direction    dir,
195                      int             period_msec )
196{
197    int i, n, peerCount;
198    tr_ptrArray tmp = TR_PTR_ARRAY_INIT;
199    struct tr_peerIo ** peers;
200
201    /* allocateBandwidth() is a helper function with two purposes:
202     * 1. allocate bandwidth to b and its subtree
203     * 2. accumulate an array of all the peerIos from b and its subtree. */
204    allocateBandwidth( b, dir, period_msec, &tmp );
205    peers = (struct tr_peerIo**) TR_PTR_ARRAY_DATA( &tmp );
206    peerCount = TR_PTR_ARRAY_LENGTH( &tmp );
207
208    /* Stop all peers from listening for the socket to be ready for IO.
209     * See "Second phase of IO" lower in this function for more info. */
210    for( i=0; i<peerCount; ++i )
211        tr_peerIoSetEnabled( peers[i], dir, FALSE );
212
213    /* First phase of IO.  Tries to distribute bandwidth fairly to keep faster
214     * peers from starving the others.  Loop through the peers, giving each a
215     * small chunk of bandwidth.  Keep looping until we run out of bandwidth
216     * and/or peers that can use it */
217    n = peerCount;
218    dbgmsg( "%d peers to go round-robin for %s", n, (dir==TR_UP?"upload":"download") );
219    i = n ? tr_cryptoWeakRandInt( n ) : 0; /* pick a random starting point */
220    while( n > 1 )
221    {
222        const int increment = 1024;
223        const int bytesUsed = tr_peerIoFlush( peers[i], dir, increment );
224
225        dbgmsg( "peer #%d of %d used %.2f KiB in this pass", i, n, bytesUsed/1024.0 );
226
227        if( bytesUsed == increment )
228            ++i;
229        else {
230            /* peer is done writing for now; move it to the end of the list */
231            tr_peerIo * pio = peers[i];
232            peers[i] = peers[n-1];
233            peers[n-1] = pio;
234            --n;
235        }
236
237        if( i == n )
238            i = 0;
239    }
240
241    /* Second phase of IO.  To help us scale in high bandwidth situations,
242     * enable on-demand IO for peers with bandwidth left to burn.
243     * This on-demand IO is enabled until (1) the peer runs out of bandwidth,
244     * or (2) the next tr_bandwidthAllocate() call, when we start over again. */
245    for( i=0; i<peerCount; ++i )
246        if( tr_peerIoHasBandwidthLeft( peers[i], dir ) )
247            tr_peerIoSetEnabled( peers[i], dir, TRUE );
248
249    /* cleanup */
250    tr_ptrArrayDestruct( &tmp, NULL );
251}
252
253void
254tr_bandwidthSetPeer( tr_bandwidth * b, tr_peerIo * peer )
255{
256    assert( tr_isBandwidth( b ) );
257    assert( ( peer == NULL ) || tr_isPeerIo( peer ) );
258
259    b->peer = peer;
260}
261
262/***
263****
264***/
265
266size_t
267tr_bandwidthClamp( const tr_bandwidth  * b,
268                   tr_direction          dir,
269                   size_t                byteCount )
270{
271    assert( tr_isBandwidth( b ) );
272    assert( tr_isDirection( dir ) );
273
274    if( b )
275    {
276        if( b->band[dir].isLimited )
277            byteCount = MIN( byteCount, b->band[dir].bytesLeft );
278
279        if( b->parent && b->band[dir].honorParentLimits )
280            byteCount = tr_bandwidthClamp( b->parent, dir, byteCount );
281    }
282
283    return byteCount;
284}
285
286double
287tr_bandwidthGetRawSpeed( const tr_bandwidth * b, tr_direction dir )
288{
289    assert( tr_isBandwidth( b ) );
290    assert( tr_isDirection( dir ) );
291
292    return getSpeed( &b->band[dir].raw, HISTORY_MSEC );
293}
294
295double
296tr_bandwidthGetPieceSpeed( const tr_bandwidth * b, tr_direction dir )
297{
298    assert( tr_isBandwidth( b ) );
299    assert( tr_isDirection( dir ) );
300
301    return getSpeed( &b->band[dir].piece, HISTORY_MSEC );
302}
303
304static void
305bandwidthUsedImpl( tr_bandwidth  * b,
306                   tr_direction    dir,
307                   size_t          byteCount,
308                   tr_bool         isPieceData,
309                   uint64_t        now )
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( now, &band->raw, byteCount );
331
332    if( isPieceData )
333        bytesUsed( now, &band->piece, byteCount );
334
335    if( b->parent != NULL )
336        bandwidthUsedImpl( b->parent, dir, byteCount, isPieceData, now );
337}
338
339void
340tr_bandwidthUsed( tr_bandwidth  * b,
341                  tr_direction    dir,
342                  size_t          byteCount,
343                  tr_bool         isPieceData )
344{
345    bandwidthUsedImpl( b, dir, byteCount, isPieceData, tr_date( ) );
346}
Note: See TracBrowser for help on using the repository browser.