source: branches/1.4x/libtransmission/bandwidth.c @ 7494

Last change on this file since 7494 was 7494, checked in by livings124, 12 years ago

set missing properties

  • Property svn:keywords set to Date Rev Author Id
File size: 11.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:$
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
29enum
30{
31    HISTORY_MSEC = 2000,
32    INTERVAL_MSEC = HISTORY_MSEC,
33    GRANULARITY_MSEC = 50,
34    HISTORY_SIZE = ( INTERVAL_MSEC / GRANULARITY_MSEC ),
35    MAGIC_NUMBER = 43143
36};
37
38struct bratecontrol
39{
40    int newest;
41    struct { uint64_t date, size; } transfers[HISTORY_SIZE];
42};
43
44static float
45getSpeed( const struct bratecontrol * r, int interval_msec )
46{
47    uint64_t       bytes = 0;
48    const uint64_t cutoff = tr_date ( ) - interval_msec;
49    int            i = r->newest;
50
51    for( ;; )
52    {
53        if( r->transfers[i].date <= cutoff )
54            break;
55
56        bytes += r->transfers[i].size;
57
58        if( --i == -1 ) i = HISTORY_SIZE - 1; /* circular history */
59        if( i == r->newest ) break; /* we've come all the way around */
60    }
61
62    return ( bytes / 1024.0 ) * ( 1000.0 / interval_msec );
63}
64
65static void
66bytesUsed( struct bratecontrol * r, size_t size )
67{
68    const uint64_t now = tr_date ( );
69
70    if( r->transfers[r->newest].date + GRANULARITY_MSEC >= now )
71        r->transfers[r->newest].size += size;
72    else
73    {
74        if( ++r->newest == HISTORY_SIZE ) r->newest = 0;
75        r->transfers[r->newest].date = now;
76        r->transfers[r->newest].size = size;
77    }
78}
79
80/******
81*******
82*******
83******/
84
85struct tr_band
86{
87    tr_bool isLimited;
88    tr_bool honorParentLimits;
89    size_t bytesLeft;
90    double desiredSpeed;
91    struct bratecontrol raw;
92    struct bratecontrol piece;
93};
94
95struct tr_bandwidth
96{
97    struct tr_band band[2];
98    struct tr_bandwidth * parent;
99    int magicNumber;
100    tr_session * session;
101    tr_ptrArray * children; /* struct tr_bandwidth */
102    tr_ptrArray * peers; /* tr_peerIo */
103};
104
105/***
106****
107***/
108
109static int
110comparePointers( const void * a, const void * b )
111{
112    if( a != b )
113        return a < b ? -1 : 1;
114
115    return 0;
116}
117
118tr_bool
119tr_isBandwidth( const tr_bandwidth * b )
120{
121    return ( b != NULL ) && ( b->magicNumber == MAGIC_NUMBER );
122}
123
124/***
125****
126***/
127
128tr_bandwidth*
129tr_bandwidthNew( tr_session * session, tr_bandwidth * parent )
130{
131    tr_bandwidth * b = tr_new0( tr_bandwidth, 1 );
132    b->session = session;
133    b->children = tr_ptrArrayNew( );
134    b->peers = tr_ptrArrayNew( );
135    b->magicNumber = MAGIC_NUMBER;
136    b->band[TR_UP].honorParentLimits = TRUE;
137    b->band[TR_DOWN].honorParentLimits = TRUE;
138    tr_bandwidthSetParent( b, parent );
139    return b;
140}
141
142void
143tr_bandwidthFree( tr_bandwidth * b )
144{
145    assert( tr_isBandwidth( b ) );
146
147    tr_bandwidthSetParent( b, NULL );
148    tr_ptrArrayFree( b->peers, NULL );
149    tr_ptrArrayFree( b->children, NULL );
150    b->magicNumber = 0xDEAD;
151    tr_free( b );
152}
153
154/***
155****
156***/
157
158void
159tr_bandwidthSetParent( tr_bandwidth  * b,
160                       tr_bandwidth  * parent )
161{
162    assert( tr_isBandwidth( b ) );
163    assert( b != parent );
164
165    if( b->parent )
166    {
167        assert( tr_isBandwidth( b->parent ) );
168
169        tr_ptrArrayRemoveSorted( b->parent->children, b, comparePointers );
170        b->parent = NULL;
171    }
172
173    if( parent )
174    {
175        assert( tr_isBandwidth( parent ) );
176        assert( parent->parent != b );
177
178        tr_ptrArrayInsertSorted( parent->children, b, comparePointers );
179        b->parent = parent;
180    }
181}
182
183void
184tr_bandwidthHonorParentLimits( tr_bandwidth  * b,
185                               tr_direction    dir,
186                               tr_bool         honorParentLimits )
187{
188    assert( tr_isBandwidth( b ) );
189    assert( tr_isDirection( dir ) );
190
191    b->band[dir].honorParentLimits = honorParentLimits;
192}
193
194/***
195****
196***/
197
198void
199tr_bandwidthSetDesiredSpeed( tr_bandwidth  * b,
200                             tr_direction    dir,
201                             double          desiredSpeed )
202{
203    assert( tr_isBandwidth( b ) );
204    assert( tr_isDirection( dir ) );
205
206    b->band[dir].desiredSpeed = desiredSpeed; 
207}
208
209double
210tr_bandwidthGetDesiredSpeed( const tr_bandwidth  * b,
211                             tr_direction          dir )
212{
213    assert( tr_isBandwidth( b ) );
214    assert( tr_isDirection( dir ) );
215
216    return b->band[dir].desiredSpeed;
217}
218
219void
220tr_bandwidthSetLimited( tr_bandwidth  * b,
221                        tr_direction    dir,
222                        tr_bool         isLimited )
223{
224    assert( tr_isBandwidth( b ) );
225    assert( tr_isDirection( dir ) );
226
227    b->band[dir].isLimited = isLimited;
228}
229
230tr_bool
231tr_bandwidthIsLimited( const tr_bandwidth  * b,
232                       tr_direction          dir )
233{
234    assert( tr_isBandwidth( b ) );
235    assert( tr_isDirection( dir ) );
236
237    return b->band[dir].isLimited;
238}
239
240#if 0
241#warning do not check the code in with this enabled
242#define DEBUG_DIRECTION TR_UP
243#endif
244
245static void
246allocateBandwidth( tr_bandwidth  * b,
247                   tr_direction    dir,
248                   int             period_msec,
249                   tr_ptrArray   * peer_pool )
250{
251    assert( tr_isBandwidth( b ) );
252    assert( tr_isDirection( dir ) );
253
254    /* set the available bandwidth */
255    if( b->band[dir].isLimited )
256    {
257        const double desiredSpeed = b->band[dir].desiredSpeed;
258        const double nextPulseSpeed = desiredSpeed;
259        b->band[dir].bytesLeft = MAX( 0.0, nextPulseSpeed * 1024.0 * period_msec / 1000.0 );
260
261#ifdef DEBUG_DIRECTION
262        if( dir == DEBUG_DIRECTION )
263                fprintf( stderr, "bandwidth %p currentPieceSpeed(%5.2f of %5.2f) desiredSpeed(%5.2f), allocating %5.2f\n",
264                         b, currentSpeed, tr_bandwidthGetRawSpeed( b, dir ), desiredSpeed,
265                         b->band[dir].bytesLeft/1024.0 );
266#endif
267    }
268
269    /* traverse & repeat for the subtree */
270    {
271        int i;
272        const int n = tr_ptrArraySize( b->peers );
273        for( i=0; i<n; ++i )
274            tr_ptrArrayAppend( peer_pool, tr_ptrArrayNth( b->peers, i ) );
275    }
276
277#ifdef DEBUG_DIRECTION
278if( ( dir == DEBUG_DIRECTION ) && ( n > 1 ) )
279fprintf( stderr, "bandwidth %p has %d peers\n", b, n );
280#endif
281
282    /* all children should reallocate too */
283    if( 1 ) {
284        int i, n=0;
285        struct tr_bandwidth ** children = (struct tr_bandwidth**) tr_ptrArrayPeek( b->children, &n );
286        for( i=0; i<n; ++i )
287            allocateBandwidth( children[i], dir, period_msec, peer_pool );
288    }
289}
290
291void
292tr_bandwidthAllocate( tr_bandwidth  * b,
293                      tr_direction    dir,
294                      int             period_msec )
295{
296    int i, n, peerCount;
297    tr_ptrArray * tmp;
298    struct tr_peerIo ** peers;
299    const uint64_t now = tr_date( );
300    const uint64_t cutoff = now + 100; /* 1/10th of a second */
301
302
303    /* allocateBandwidth() is a helper function with two purposes:
304     * 1. allocate bandwidth to b and its subtree
305     * 2. accumulate an array of all the peerIos from b and its subtree. */
306    tmp = tr_ptrArrayNew( );
307    allocateBandwidth( b, dir, period_msec, tmp );
308    peers = (struct tr_peerIo**) tr_ptrArrayPeek( tmp, &peerCount );
309
310    /* Stop all peers from listening for the socket to be ready for IO.
311     * See "Second phase of IO" lower in this function for more info. */
312    for( i=0; i<peerCount; ++i )
313        tr_peerIoSetEnabled( peers[i], dir, FALSE );
314
315    /* First phase of IO.  Tries to distribute bandwidth fairly to keep faster
316     * peers from starving the others.  Loop through the peers, giving each a
317     * small chunk of bandwidth.  Keep looping until we run out of bandwidth
318     * or peers that can use it */
319    n = peerCount;
320    i = n ? tr_cryptoWeakRandInt( n ) : 0; /* pick a random starting point */
321    for( ; n>0 && tr_date()<=cutoff; )
322    {
323        const int increment = n==1 ? 4096 : 1024;
324        const int byteCount = tr_peerIoFlush( peers[i], dir, increment);
325
326        if( byteCount == increment )
327            ++i;
328        else {
329            /* peer is done writing for now; move it to the end of the list */
330            tr_peerIo * tmp = peers[i];
331            peers[i] = peers[n-1];
332            peers[n-1] = tmp;
333            --n;
334        }
335
336        assert( i <= n );
337        if( i == n )
338            i = 0;
339    }
340
341    /* Second phase of IO.  To help us scale in high bandwidth situations,
342     * enable on-demand IO for peers with bandwidth left to burn.
343     * This on-demand IO is enabled until (1) the peer runs out of bandwidth,
344     * or (2) the next tr_bandwidthAllocate() call, when we start over again. */
345    for( i=0; i<peerCount; ++i )
346        if( tr_peerIoHasBandwidthLeft( peers[i], dir ) )
347            tr_peerIoSetEnabled( peers[i], dir, TRUE );
348
349    /* cleanup */
350    tr_ptrArrayFree( tmp, NULL );
351}
352
353/***
354****
355***/
356
357void
358tr_bandwidthAddPeer( tr_bandwidth   * b,
359                     tr_peerIo      * peerIo )
360{
361    assert( tr_isBandwidth( b ) );
362    assert( tr_isPeerIo( peerIo ) );
363
364    tr_ptrArrayInsertSorted( b->peers, peerIo, comparePointers );
365}
366
367void
368tr_bandwidthRemovePeer( tr_bandwidth  * b,
369                        tr_peerIo     * peerIo )
370{
371    assert( tr_isBandwidth( b ) );
372    assert( tr_isPeerIo( peerIo ) );
373
374    tr_ptrArrayRemoveSorted( b->peers, peerIo, comparePointers );
375}
376
377/***
378****
379***/
380
381size_t
382tr_bandwidthClamp( const tr_bandwidth  * b,
383                   tr_direction          dir,
384                   size_t                byteCount )
385{
386    assert( tr_isBandwidth( b ) );
387    assert( tr_isDirection( dir ) );
388
389    if( b )
390    {
391        if( b->band[dir].isLimited )
392            byteCount = MIN( byteCount, b->band[dir].bytesLeft );
393
394        if( b->parent && b->band[dir].honorParentLimits )
395            byteCount = tr_bandwidthClamp( b->parent, dir, byteCount );
396    }
397
398    return byteCount;
399}
400
401double
402tr_bandwidthGetRawSpeed( const tr_bandwidth * b, tr_direction dir )
403{
404    assert( tr_isBandwidth( b ) );
405    assert( tr_isDirection( dir ) );
406
407    return getSpeed( &b->band[dir].raw, HISTORY_MSEC );
408}
409
410double
411tr_bandwidthGetPieceSpeed( const tr_bandwidth * b, tr_direction dir )
412{
413    assert( tr_isBandwidth( b ) );
414    assert( tr_isDirection( dir ) );
415
416    return getSpeed( &b->band[dir].piece, HISTORY_MSEC );
417}
418
419void
420tr_bandwidthUsed( tr_bandwidth  * b,
421                  tr_direction    dir,
422                  size_t          byteCount,
423                  tr_bool         isPieceData )
424{
425    struct tr_band * band;
426    size_t oldBytesLeft;
427
428    assert( tr_isBandwidth( b ) );
429    assert( tr_isDirection( dir ) );
430
431    band = &b->band[dir];
432
433    oldBytesLeft = band->bytesLeft;
434
435    if( band->isLimited && isPieceData )
436        band->bytesLeft -= MIN( band->bytesLeft, byteCount );
437
438#ifdef DEBUG_DIRECTION
439if( ( dir == DEBUG_DIRECTION ) && ( band->isLimited ) )
440fprintf( stderr, "%p consumed %5zu bytes of %5s data... was %6zu, now %6zu left\n",
441         b, byteCount, (isPieceData?"piece":"raw"), oldBytesLeft, band->bytesLeft );
442#endif
443
444    bytesUsed( &band->raw, byteCount );
445
446    if( isPieceData )
447        bytesUsed( &band->piece, byteCount );
448
449    if( b->parent != NULL )
450        tr_bandwidthUsed( b->parent, dir, byteCount, isPieceData );
451}
Note: See TracBrowser for help on using the repository browser.