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

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

(1.4x libT) backport handshake, peer, bandwidth, peer-io to 1.4x.

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