source: trunk/libtransmission/bandwidth.c @ 11599

Last change on this file since 11599 was 11599, checked in by charles, 11 years ago

(trunk) Join the 21st century and use only 1 space at the end sentences. This commit is nearly as important as the semi-annual ones that remove trailing spaces from the ends of lines of code... :)

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