Changeset 65


Ignore:
Timestamp:
Jan 30, 2006, 6:54:31 AM (15 years ago)
Author:
titer
Message:

New choking algorithm (still needs work, it's inefficient, untested and
misses optimistic choking)

Location:
trunk/libtransmission
Files:
7 edited

Legend:

Unmodified
Added
Removed
  • trunk/libtransmission/Jamfile

    r60 r65  
    44    transmission.c bencode.c net.c tracker.c peer.c inout.c
    55    metainfo.c sha1.c utils.c fdlimit.c clients.c completion.c
    6     platform.c ratecontrol.c ;
     6    platform.c ratecontrol.c choking.c ;
    77
    88Library       libtransmission.a       : $(LIBTRANSMISSION_SRC) ;
  • trunk/libtransmission/choking.c

    r62 r65  
    2121 *****************************************************************************/
    2222
     23#include <math.h>
    2324#include "transmission.h"
    24 
    25 #define MAX_HISTORY 30
    2625
    2726struct tr_choking_s
     
    2928    tr_lock_t     lock;
    3029    tr_handle_t * h;
    31     int           slotsMax;
    32     int           slotsUsed;
     30    int           slots;
    3331};
    3432
     
    3735    tr_choking_t * c;
    3836
    39     c           = calloc( sizeof( tr_choking_t ), 1 );
    40     c->h        = h;
    41     c->slotsMax = 4242;
     37    c        = calloc( sizeof( tr_choking_t ), 1 );
     38    c->h     = h;
     39    c->slots = 4242;
    4240    tr_lockInit( &c->lock );
    4341
     
    4947    tr_lockLock( &c->lock );
    5048    if( limit < 0 )
    51         c->slotsMax = 4242;
     49        c->slots = 4242;
    5250    else
    53         c->slotsMax = lrintf( sqrt( 2 * limit ) );
     51        c->slots = lrintf( sqrt( 2 * limit ) );
    5452    tr_lockUnlock( &c->lock );
     53}
     54
     55static inline void sortPeers( tr_peer_t ** peers, int count )
     56{
     57    int i, j;
     58    tr_peer_t * tmp;
     59
     60    for( i = count - 1; i > 0; i-- )
     61        for( j = 0; j < i; j++ )
     62        {
     63            if( tr_peerDownloadRate( peers[j] ) >
     64                    tr_peerDownloadRate( peers[j+1] ) )
     65            {
     66                tmp        = peers[j];
     67                peers[j]   = peers[j+1];
     68                peers[j+1] = tmp;
     69            }
     70        }
    5571}
    5672
    5773void tr_chokingPulse( tr_choking_t * c )
    5874{
     75    int i, j, peersTotalCount;
     76    tr_peer_t * peer;
     77    tr_peer_t ** peersCanChoke, ** peersCanUnchoke;
     78    int peersCanChokeCount, peersCanUnchokeCount, unchokedCount;
     79    tr_torrent_t * tor;
     80    uint64_t now = tr_date();
     81
    5982    tr_lockLock( &c->lock );
     83
     84    /* Lock all torrents and get the total number of peers */
     85    peersTotalCount = 0;
     86    for( i = 0; i < c->h->torrentCount; i++ )
     87    {
     88        tor = c->h->torrents[i];
     89        tr_lockLock( &tor->lock );
     90        peersTotalCount += tor->peerCount;
     91    }
     92
     93    peersCanChoke   = malloc( peersTotalCount * sizeof( tr_peer_t * ) );
     94    peersCanUnchoke = malloc( peersTotalCount * sizeof( tr_peer_t * ) );
     95    peersCanChokeCount   = 0;
     96    peersCanUnchokeCount = 0;
     97    unchokedCount        = 0;
     98
     99    /* Build two lists of interested peers: those who may choke,
     100       those who may unchoke */
     101    for( i = 0; i < c->h->torrentCount; i++ )
     102    {
     103        tor = c->h->torrents[i];
     104        for( j = 0; j < tor->peerCount; j++ )
     105        {
     106            peer = tor->peers[j];
     107
     108            if( !tr_peerIsConnected( peer ) )
     109                continue;
     110
     111            if( !tr_peerIsInterested( peer ) )
     112            {
     113                if( tr_peerIsUnchoked( peer ) )
     114                    tr_peerChoke( peer );
     115                continue;
     116            }
     117
     118            if( tr_peerIsUnchoked( peer ) )
     119            {
     120                unchokedCount++;
     121                if( tr_peerLastChoke( peer ) + 10000 < now )
     122                    peersCanChoke[peersCanChokeCount++] = peer;
     123            }
     124            else
     125            {
     126                if( tr_peerLastChoke( peer ) + 10000 < now )
     127                    peersCanUnchoke[peersCanUnchokeCount++] = peer;
     128            }
     129        }
     130    }
     131
     132    sortPeers( peersCanChoke, peersCanChokeCount );
     133    sortPeers( peersCanUnchoke, peersCanUnchokeCount );
     134
     135    if( unchokedCount > c->slots )
     136    {
     137        int willChoke;
     138        willChoke = MIN( peersCanChokeCount, unchokedCount - c->slots );
     139        for( i = 0; i < willChoke; i++ )
     140            tr_peerChoke( peersCanChoke[i] );
     141        peersCanChokeCount -= willChoke;
     142        memmove( &peersCanChoke[0], &peersCanChoke[willChoke],
     143                 peersCanChokeCount );
     144    }
     145    else if( unchokedCount < c->slots )
     146    {
     147        int willUnchoke;
     148        willUnchoke = MIN( peersCanUnchokeCount, c->slots - unchokedCount );
     149        for( i = 0; i < willUnchoke; i++ )
     150            tr_peerUnchoke( peersCanUnchoke[peersCanUnchokeCount - i - 1] );
     151        peersCanUnchokeCount -= willUnchoke;
     152    }
     153
     154    while( peersCanChokeCount > 0 && peersCanUnchokeCount > 0 )
     155    {
     156        if( tr_peerDownloadRate( peersCanUnchoke[peersCanUnchokeCount - 1] )
     157                > tr_peerDownloadRate( peersCanChoke[0] ) )
     158            break;
     159
     160        tr_peerChoke( peersCanChoke[0] );
     161        tr_peerUnchoke( peersCanUnchoke[peersCanUnchokeCount - 1] );
     162        peersCanChokeCount--;
     163        peersCanUnchokeCount--;
     164        memmove( &peersCanChoke[0], &peersCanChoke[1], peersCanChokeCount );
     165    }
     166
     167    free( peersCanChoke );
     168    free( peersCanUnchoke );
     169
     170    /* Unlock all torrents */
     171    for( i = 0; i < c->h->torrentCount; i++ )
     172    {
     173        tr_lockUnlock( &c->h->torrents[i]->lock );
     174    }
     175
    60176    tr_lockUnlock( &c->lock );
    61177}
  • trunk/libtransmission/internal.h

    r62 r65  
    164164    tr_ratecontrol_t * download;
    165165    tr_fd_t      * fdlimit;
     166    tr_choking_t * choking;
    166167
    167168    int            bindPort;
  • trunk/libtransmission/peer.c

    r62 r65  
    5454    char           peerInterested;
    5555
     56    uint64_t       lastChoke;
     57
    5658    uint8_t        id[20];
    5759
     
    199201        tr_cpDownloaderRem( tor->completion, block );
    200202    }
    201     if( !peer->amChoking )
    202     {
    203         //tr_uploadChoked( tor->upload );
    204     }
    205203    tr_peerDestroy( tor->fdlimit, peer );
    206204    tor->peerCount--;
     
    465463    return tr_rcRate( peer->download );
    466464}
     465
     466int tr_peerIsUnchoked( tr_peer_t * peer )
     467{
     468    return !peer->amChoking;
     469}
     470
     471int tr_peerIsInterested  ( tr_peer_t * peer )
     472{
     473    return peer->peerInterested;
     474}
     475
     476void tr_peerChoke( tr_peer_t * peer )
     477{
     478    sendChoke( peer, 1 );
     479    peer->lastChoke = tr_date();
     480}
     481
     482void tr_peerUnchoke( tr_peer_t * peer )
     483{
     484    sendChoke( peer, 0 );
     485    peer->lastChoke = tr_date();
     486}
     487
     488uint64_t tr_peerLastChoke( tr_peer_t * peer )
     489{
     490    return peer->lastChoke;
     491}
  • trunk/libtransmission/peer.h

    r62 r65  
    4040uint8_t *   tr_peerBitfield      ( tr_peer_t * );
    4141float       tr_peerDownloadRate  ( tr_peer_t * );
     42int         tr_peerIsUnchoked    ( tr_peer_t * );
     43int         tr_peerIsInterested  ( tr_peer_t * );
     44void        tr_peerChoke         ( tr_peer_t * );
     45void        tr_peerUnchoke       ( tr_peer_t * );
     46uint64_t    tr_peerLastChoke     ( tr_peer_t * );
    4247
    4348#endif
  • trunk/libtransmission/peerutils.h

    r62 r65  
    136136    }
    137137
    138     /* TODO: check for bad downloaders */
    139 
    140 #if 0
    141     /* Choke unchoked peers we are not sending anything to */
    142     if( !peer->amChoking && tr_date() > peer->outDate + 10000 )
    143     {
    144         peer_dbg( "not worth the unchoke" );
    145         if( sendChoke( peer, 1 ) )
    146         {
    147             goto dropPeer;
    148         }
    149         peer->outSlow = 1;
    150         tr_uploadChoked( tor->upload );
    151     }
    152 #endif
    153 
    154138    if( peer->status & PEER_STATUS_CONNECTED )
    155139    {
     
    159143            sendKeepAlive( peer );
    160144            peer->keepAlive = tr_date();
    161         }
    162 
    163         /* Choke or unchoke some people */
    164         /* TODO: prefer people who upload to us */
    165         if( !peer->amChoking && !peer->peerInterested )
    166         {
    167             /* He doesn't need us */
    168             sendChoke( peer, 1 );
    169             //tr_uploadChoked( tor->upload );
    170         }
    171         if( peer->amChoking && peer->peerInterested /* &&
    172             !peer->outSlow && tr_uploadCanUnchoke( tor->upload ) */ )
    173         {
    174             sendChoke( peer, 0 );
    175             //tr_uploadUnchoked( tor->upload );
    176145        }
    177146    }
  • trunk/libtransmission/transmission.c

    r64 r65  
    6767    h->download = tr_rcInit();
    6868    h->fdlimit  = tr_fdInit();
     69    h->choking  = tr_chokingInit( h );
    6970
    7071    h->bindPort = TR_DEFAULT_PORT;
     
    146147{
    147148    tr_rcSetLimit( h->upload, limit );
     149    tr_chokingSetLimit( h->choking, limit );
    148150}
    149151
     
    500502{
    501503    acceptStop( h );
     504    tr_chokingClose( h->choking );
    502505    tr_fdClose( h->fdlimit );
    503506    tr_rcClose( h->upload );
     
    581584    int           ii, jj;
    582585    uint8_t     * hash;
    583     //tr_choking_t * choking = tr_chokingInit( h );
    584586
    585587    tr_dbg( "Accept thread started" );
     
    650652        if( date1 > lastchoke + 2000 )
    651653        {
    652             //tr_chokingPulse( choking );
     654            tr_chokingPulse( h->choking );
    653655            lastchoke = date1;
    654656        }
     
    665667
    666668    tr_lockUnlock( &h->acceptLock );
    667     //tr_chokingClose( choking );
    668669
    669670    tr_dbg( "Accept thread exited" );
Note: See TracChangeset for help on using the changeset viewer.