source: trunk/libtransmission/bandwidth.c @ 7580

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

(trunk libT) avoid some unnecessary memory fragmentation... for composited objects that have a tr_bandwidth, contain the it directly rather than a pointer to one allocated elsewhere on the heap.

  • Property svn:keywords set to Date Rev Author Id
File size: 8.6 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 7580 2009-01-02 19:56:06Z 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_bandwidthConstruct( tr_bandwidth * b, tr_session * session, tr_bandwidth * parent )
85{
86    b->session = session;
87    b->children = TR_PTR_ARRAY_INIT;
88    b->magicNumber = MAGIC_NUMBER;
89    b->band[TR_UP].honorParentLimits = TRUE;
90    b->band[TR_DOWN].honorParentLimits = TRUE;
91    tr_bandwidthSetParent( b, parent );
92    return b;
93}
94
95tr_bandwidth*
96tr_bandwidthDestruct( tr_bandwidth * b )
97{
98    assert( tr_isBandwidth( b ) );
99
100    tr_bandwidthSetParent( b, NULL );
101    tr_ptrArrayDestruct( &b->children, NULL );
102    b->magicNumber = 0xDEAD;
103
104    return b;
105}
106
107/***
108****
109***/
110
111void
112tr_bandwidthSetParent( tr_bandwidth  * b,
113                       tr_bandwidth  * parent )
114{
115    assert( tr_isBandwidth( b ) );
116    assert( b != parent );
117
118    if( b->parent )
119    {
120        assert( tr_isBandwidth( b->parent ) );
121
122        tr_ptrArrayRemoveSorted( &b->parent->children, b, comparePointers );
123        b->parent = NULL;
124    }
125
126    if( parent )
127    {
128        assert( tr_isBandwidth( parent ) );
129        assert( parent->parent != b );
130
131        tr_ptrArrayInsertSorted( &parent->children, b, comparePointers );
132        b->parent = parent;
133    }
134}
135
136/***
137****
138***/
139
140#if 0
141#warning do not check the code in with this enabled
142#define DEBUG_DIRECTION TR_UP
143#endif
144
145static void
146allocateBandwidth( tr_bandwidth  * b,
147                   tr_direction    dir,
148                   int             period_msec,
149                   tr_ptrArray   * peer_pool )
150{
151    assert( tr_isBandwidth( b ) );
152    assert( tr_isDirection( dir ) );
153
154    /* set the available bandwidth */
155    if( b->band[dir].isLimited )
156    {
157        const double desiredSpeed = b->band[dir].desiredSpeed;
158        const double nextPulseSpeed = desiredSpeed;
159        b->band[dir].bytesLeft = MAX( 0.0, nextPulseSpeed * 1024.0 * period_msec / 1000.0 );
160
161#ifdef DEBUG_DIRECTION
162        if( dir == DEBUG_DIRECTION )
163                fprintf( stderr, "bandwidth %p currentPieceSpeed(%5.2f of %5.2f) desiredSpeed(%5.2f), allocating %5.2f\n",
164                         b, currentSpeed, tr_bandwidthGetRawSpeed( b, dir ), desiredSpeed,
165                         b->band[dir].bytesLeft/1024.0 );
166#endif
167    }
168
169    /* add this bandwidth's peer, if any, to the peer pool */
170    if( b->peer != NULL )
171        tr_ptrArrayAppend( peer_pool, b->peer );
172
173#ifdef DEBUG_DIRECTION
174if( ( dir == DEBUG_DIRECTION ) && ( n > 1 ) )
175fprintf( stderr, "bandwidth %p has %d peers\n", b, n );
176#endif
177
178    /* traverse & repeat for the subtree */
179    if( 1 ) {
180        int i;
181        struct tr_bandwidth ** children = (struct tr_bandwidth**) TR_PTR_ARRAY_DATA( &b->children );
182        const int n = TR_PTR_ARRAY_LENGTH( &b->children );
183        for( i=0; i<n; ++i )
184            allocateBandwidth( children[i], dir, period_msec, peer_pool );
185    }
186}
187
188void
189tr_bandwidthAllocate( tr_bandwidth  * b,
190                      tr_direction    dir,
191                      int             period_msec )
192{
193    int i, n, peerCount;
194    tr_ptrArray tmp = TR_PTR_ARRAY_INIT;
195    struct tr_peerIo ** peers;
196
197
198    /* allocateBandwidth() is a helper function with two purposes:
199     * 1. allocate bandwidth to b and its subtree
200     * 2. accumulate an array of all the peerIos from b and its subtree. */
201    allocateBandwidth( b, dir, period_msec, &tmp );
202    peers = (struct tr_peerIo**) TR_PTR_ARRAY_DATA( &tmp );
203    peerCount = TR_PTR_ARRAY_LENGTH( &tmp );
204
205    /* Stop all peers from listening for the socket to be ready for IO.
206     * See "Second phase of IO" lower in this function for more info. */
207    for( i=0; i<peerCount; ++i )
208        tr_peerIoSetEnabled( peers[i], dir, FALSE );
209
210    /* First phase of IO.  Tries to distribute bandwidth fairly to keep faster
211     * peers from starving the others.  Loop through the peers, giving each a
212     * small chunk of bandwidth.  Keep looping until we run out of bandwidth
213     * and/or peers that can use it */
214    n = peerCount;
215#ifdef DEBUG_DIRECTION
216if( dir == DEBUG_DIRECTION ) fprintf( stderr, "bandwidth.c: allocate: number of peerIos to go round-robin: %d\n", n );
217#endif
218    i = n ? tr_cryptoWeakRandInt( n ) : 0; /* pick a random starting point */
219    while( n > 1 )
220    {
221        const int increment = 1024;
222        const int bytesUsed = tr_peerIoFlush( peers[i], dir, increment );
223
224        if( bytesUsed == increment )
225            ++i;
226        else {
227            /* peer is done writing for now; move it to the end of the list */
228            tr_peerIo * pio = peers[i];
229            peers[i] = peers[n-1];
230            peers[n-1] = pio;
231            --n;
232        }
233
234        if( i == n )
235            i = 0;
236    }
237
238    /* Second phase of IO.  To help us scale in high bandwidth situations,
239     * enable on-demand IO for peers with bandwidth left to burn.
240     * This on-demand IO is enabled until (1) the peer runs out of bandwidth,
241     * or (2) the next tr_bandwidthAllocate() call, when we start over again. */
242    for( i=0; i<peerCount; ++i )
243        if( tr_peerIoHasBandwidthLeft( peers[i], dir ) )
244            tr_peerIoSetEnabled( peers[i], dir, TRUE );
245
246    /* cleanup */
247    tr_ptrArrayDestruct( &tmp, NULL );
248}
249
250void
251tr_bandwidthSetPeer( tr_bandwidth * b, tr_peerIo * peer )
252{
253    assert( tr_isBandwidth( b ) );
254    assert( ( peer == NULL ) || tr_isPeerIo( peer ) );
255
256    b->peer = peer;
257}
258
259/***
260****
261***/
262
263size_t
264tr_bandwidthClamp( const tr_bandwidth  * b,
265                   tr_direction          dir,
266                   size_t                byteCount )
267{
268    assert( tr_isBandwidth( b ) );
269    assert( tr_isDirection( dir ) );
270
271    if( b )
272    {
273        if( b->band[dir].isLimited )
274            byteCount = MIN( byteCount, b->band[dir].bytesLeft );
275
276        if( b->parent && b->band[dir].honorParentLimits )
277            byteCount = tr_bandwidthClamp( b->parent, dir, byteCount );
278    }
279
280    return byteCount;
281}
282
283double
284tr_bandwidthGetRawSpeed( const tr_bandwidth * b, tr_direction dir )
285{
286    assert( tr_isBandwidth( b ) );
287    assert( tr_isDirection( dir ) );
288
289    return getSpeed( &b->band[dir].raw, HISTORY_MSEC );
290}
291
292double
293tr_bandwidthGetPieceSpeed( const tr_bandwidth * b, tr_direction dir )
294{
295    assert( tr_isBandwidth( b ) );
296    assert( tr_isDirection( dir ) );
297
298    return getSpeed( &b->band[dir].piece, HISTORY_MSEC );
299}
300
301void
302tr_bandwidthUsed( tr_bandwidth  * b,
303                  tr_direction    dir,
304                  size_t          byteCount,
305                  tr_bool         isPieceData )
306{
307    struct tr_band * band;
308    size_t oldBytesLeft;
309
310    assert( tr_isBandwidth( b ) );
311    assert( tr_isDirection( dir ) );
312
313    band = &b->band[dir];
314
315    oldBytesLeft = band->bytesLeft;
316
317    if( band->isLimited && isPieceData )
318        band->bytesLeft -= MIN( band->bytesLeft, byteCount );
319
320#ifdef DEBUG_DIRECTION
321if( ( dir == DEBUG_DIRECTION ) && ( band->isLimited ) )
322fprintf( stderr, "%p consumed %5zu bytes of %5s data... was %6zu, now %6zu left\n",
323         b, byteCount, (isPieceData?"piece":"raw"), oldBytesLeft, band->bytesLeft );
324#endif
325
326    bytesUsed( &band->raw, byteCount );
327
328    if( isPieceData )
329        bytesUsed( &band->piece, byteCount );
330
331    if( b->parent != NULL )
332        tr_bandwidthUsed( b->parent, dir, byteCount, isPieceData );
333}
Note: See TracBrowser for help on using the repository browser.