source: trunk/libtransmission/bandwidth.c @ 7579

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

(trunk libT) inline parts of peer-io and bandwidth, too

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