release/src/router/transmission/libtransmission/cache.c

   1 /*
   2  * This file Copyright (C) 2010 Mnemosyne LLC
   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: cache.c 11398 2010-11-11 15:31:11Z charles $
  11  */
  12
  13 #include "transmission.h"
  14 #include "cache.h"
  15 #include "inout.h"
  16 #include "peer-common.h" /* MAX_BLOCK_SIZE */
  17 #include "ptrarray.h"
  18 #include "torrent.h"
  19 #include "utils.h"
  20
  21 #define MY_NAME "Cache"
  22
  23 #define dbgmsg( ... ) \
  24     do { \
  25         if( tr_deepLoggingIsActive( ) ) \
  26             tr_deepLog( __FILE__, __LINE__, MY_NAME, __VA_ARGS__ ); \
  27     } while( 0 )
  28
  29
  30 /****
  31 *****
  32 ****/
  33
  34 struct cache_block
  35 {
  36     tr_torrent * tor;
  37
  38     tr_piece_index_t piece;
  39     uint32_t offset;
  40     uint32_t length;
  41
  42     time_t time;
  43     tr_block_index_t block;
  44
  45     uint8_t * buf;
  46 };
  47
  48 struct tr_cache
  49 {
  50     tr_ptrArray blocks;
  51     int max_blocks;
  52     size_t max_bytes;
  53
  54     size_t disk_writes;
  55     size_t disk_write_bytes;
  56     size_t cache_writes;
  57     size_t cache_write_bytes;
  58 };
  59
  60 /****
  61 *****
  62 ****/
  63
  64 struct run_info
  65 {
  66   int       pos;
  67   int       rank;
  68   time_t    last_block_time;
  69   tr_bool   is_multi_piece;
  70   tr_bool   is_piece_done;
  71   unsigned  len;
  72 };
  73
  74
  75 /* return a count of how many contiguous blocks there are starting at this pos */
  76 static int
  77 getBlockRun( const tr_cache * cache, int pos, struct run_info * info )
  78 {
  79     int i;
  80     const int n = tr_ptrArraySize( &cache->blocks );
  81     const struct cache_block ** blocks = (const struct cache_block**) tr_ptrArrayBase( &cache->blocks );
  82     const struct cache_block * ref = blocks[pos];
  83     tr_block_index_t block = ref->block;
  84
  85     for( i=pos; i<n; ++i, ++block ) {
  86         const struct cache_block * b = blocks[i];
  87         if( b->block != block ) break;
  88         if( b->tor != ref->tor ) break;
  89 //fprintf( stderr, "pos %d tor %d block %zu time %zu\n", i, b->tor->uniqueId, (size_t)b->block, (size_t)b->time );
  90     }
  91
  92 //fprintf( stderr, "run is %d long from [%d to %d)\n", (int)(i-pos), i, (int)pos );
  93     if( info != NULL ) {
  94         const struct cache_block * b = blocks[i-1];
  95         info->last_block_time = b->time;
  96         info->is_piece_done = tr_cpPieceIsComplete( &b->tor->completion, b->piece );
  97         info->is_multi_piece = b->piece != blocks[pos]->piece ? TRUE : FALSE;
  98         info->len = i - pos;
  99         info->pos = pos;
 100     }
 101
 102     return i-pos;
 103 }
 104
 105 static int
 106 compareRuns( const void * va, const void * vb )
 107 {
 108     const struct run_info a = *(const struct run_info*)va;
 109     const struct run_info b = *(const struct run_info*)vb;
 110     return b.rank - a.rank;
 111 }
 112
 113 enum
 114 {
 115     MULTIFLAG   = 0x1000,
 116     DONEFLAG    = 0x2000,
 117     SESSIONFLAG = 0x4000
 118 };
 119 /* Calculte runs
 120  *   - Stale runs, runs sitting in cache for a long time or runs not growing, get priority.
 121  *     Returns number of runs.
 122  */
 123 static int
 124 calcRuns( tr_cache * cache, struct run_info * runs )
 125 {
 126     const int n = tr_ptrArraySize( &cache->blocks );
 127     int i = 0, pos;
 128     const time_t now = tr_time();
 129
 130     for( pos = 0; pos < n; pos += runs[i++].len )
 131     {
 132         int rank = getBlockRun( cache, pos, &runs[i] );
 133
 134         /* This adds ~2 to the relative length of a run for every minute it has
 135          * languished in the cache. */
 136         rank += ( now - runs[i].last_block_time ) / 32;
 137
 138         /* Flushing stale blocks should be a top priority as the probability of them
 139          * growing is very small, for blocks on piece boundaries, and nonexistant for
 140          * blocks inside pieces. */
 141         rank |= runs[i].is_piece_done ? DONEFLAG : 0;
 142
 143         /* Move the multi piece runs higher */
 144         rank |= runs[i].is_multi_piece ? MULTIFLAG : 0;
 145
 146         runs[i].rank = rank;
 147 //fprintf(stderr,"block run at pos %d of length %d and age %ld adjusted +%d\n",runs[i].pos,runs[i].len,now-runs[i].last_block_time,rank-runs[i].len);
 148     }
 149
 150     //fprintf( stderr, "%d block runs\n", i );
 151     qsort( runs, i, sizeof( struct run_info ), compareRuns );
 152     return i;
 153 }
 154
 155 static int
 156 flushContiguous( tr_cache * cache, int pos, int n )
 157 {
 158     int i;
 159     int err = 0;
 160     uint8_t * buf = tr_new( uint8_t, n * MAX_BLOCK_SIZE );
 161     uint8_t * walk = buf;
 162     struct cache_block ** blocks = (struct cache_block**) tr_ptrArrayBase( &cache->blocks );
 163
 164     struct cache_block * b = blocks[pos];
 165     tr_torrent * tor             = b->tor;
 166     const tr_piece_index_t piece = b->piece;
 167     const uint32_t offset        = b->offset;
 168
 169 //fprintf( stderr, "flushing %d contiguous blocks [%d-%d) from cache to disk\n", n, pos, n+pos );
 170
 171     for( i=pos; i<pos+n; ++i ) {
 172         b = blocks[i];
 173         memcpy( walk, b->buf, b->length );
 174         walk += b->length;
 175         tr_free( b->buf );
 176         tr_free( b );
 177     }
 178     tr_ptrArrayErase( &cache->blocks, pos, pos+n );
 179
 180 #if 0
 181     tr_tordbg( tor, "Writing to disk piece %d, offset %d, len %d", (int)piece, (int)offset, (int)(walk-buf) );
 182     tr_ndbg( MY_NAME, "Removing %d blocks from cache, rank: %d - %d left", n, rank, tr_ptrArraySize(&cache->blocks) );
 183     fprintf( stderr, "%s - Writing to disk piece %d, offset %d, len %d\n", tr_torrentName(tor), (int)piece, (int)offset, (int)(walk-buf) );
 184     fprintf( stderr, "%s - Removing %d blocks from cache; %d left\n", MY_NAME, n, tr_ptrArraySize(&cache->blocks) );
 185 #endif
 186
 187     err = tr_ioWrite( tor, piece, offset, walk-buf, buf );
 188     tr_free( buf );
 189
 190     ++cache->disk_writes;
 191     cache->disk_write_bytes += walk-buf;
 192     return err;
 193 }
 194
 195 static int
 196 flushRuns( tr_cache * cache, struct run_info * runs, int n )
 197 {
 198     int i, j, err = 0;
 199
 200     for( i = 0; !err && i < n; ++i )
 201     {
 202         err = flushContiguous( cache, runs[i].pos, runs[i].len );
 203         for( j = i + 1; j < n; ++j )
 204             if( runs[j].pos > runs[i].pos )
 205                 runs[j].pos -= runs[i].len;
 206     }
 207
 208     return err;
 209 }
 210
 211 static int
 212 cacheTrim( tr_cache * cache )
 213 {
 214     int err = 0;
 215
 216     if( tr_ptrArraySize( &cache->blocks ) > cache->max_blocks )
 217     {
 218         /* Amount of cache that should be removed by the flush. This influences how large
 219          * runs can grow as well as how often flushes will happen. */
 220         const int cacheCutoff = 1 + cache->max_blocks / 4;
 221         struct run_info * runs = tr_new( struct run_info, tr_ptrArraySize( &cache->blocks ) );
 222         int i = 0, j = 0;
 223
 224         calcRuns( cache, runs );
 225         while( j < cacheCutoff )
 226             j += runs[i++].len;
 227         err = flushRuns( cache, runs, i );
 228         tr_free( runs );
 229     }
 230
 231     return err;
 232 }
 233
 234 /***
 235 ****
 236 ***/
 237
 238 static int
 239 getMaxBlocks( int64_t max_bytes )
 240 {
 241     return max_bytes / (double)MAX_BLOCK_SIZE;
 242 }
 243
 244 int
 245 tr_cacheSetLimit( tr_cache * cache, int64_t max_bytes )
 246 {
 247     char buf[128];
 248
 249     cache->max_bytes = max_bytes;
 250     cache->max_blocks = getMaxBlocks( max_bytes );
 251
 252     tr_formatter_mem_B( buf, cache->max_bytes, sizeof( buf ) );
 253     tr_ndbg( MY_NAME, "Maximum cache size set to %s (%d blocks)", buf, cache->max_blocks );
 254
 255     return cacheTrim( cache );
 256 }
 257
 258 int64_t
 259 tr_cacheGetLimit( const tr_cache * cache )
 260 {
 261     return cache->max_bytes;
 262 }
 263
 264 tr_cache *
 265 tr_cacheNew( int64_t max_bytes )
 266 {
 267     tr_cache * cache = tr_new0( tr_cache, 1 );
 268     cache->blocks = TR_PTR_ARRAY_INIT;
 269     cache->max_bytes = max_bytes;
 270     cache->max_blocks = getMaxBlocks( max_bytes );
 271     return cache;
 272 }
 273
 274 void
 275 tr_cacheFree( tr_cache * cache )
 276 {
 277     assert( tr_ptrArrayEmpty( &cache->blocks ) );
 278     tr_ptrArrayDestruct( &cache->blocks, NULL );
 279     tr_free( cache );
 280 }
 281
 282 /***
 283 ****
 284 ***/
 285
 286 static int
 287 cache_block_compare( const void * va, const void * vb )
 288 {
 289     const struct cache_block * a = va;
 290     const struct cache_block * b = vb;
 291
 292     /* primary key: torrent id */
 293     if( a->tor->uniqueId != b->tor->uniqueId )
 294         return a->tor->uniqueId < b->tor->uniqueId ? -1 : 1;
 295
 296     /* secondary key: block # */
 297     if( a->block != b->block )
 298         return a->block < b->block ? -1 : 1;
 299
 300     /* they're equal */
 301     return 0;
 302 }
 303
 304 static struct cache_block *
 305 findBlock( tr_cache           * cache,
 306            tr_torrent         * torrent,
 307            tr_piece_index_t     piece,
 308            uint32_t             offset )
 309 {
 310     struct cache_block key;
 311     key.tor = torrent;
 312     key.block = _tr_block( torrent, piece, offset );
 313     return tr_ptrArrayFindSorted( &cache->blocks, &key, cache_block_compare );
 314 }
 315
 316 int
 317 tr_cacheWriteBlock( tr_cache         * cache,
 318                     tr_torrent       * torrent,
 319                     tr_piece_index_t   piece,
 320                     uint32_t           offset,
 321                     uint32_t           length,
 322                     const uint8_t    * writeme )
 323 {
 324     struct cache_block * cb = findBlock( cache, torrent, piece, offset );
 325
 326     if( cb == NULL )
 327     {
 328         cb = tr_new( struct cache_block, 1 );
 329         cb->tor = torrent;
 330         cb->piece = piece;
 331         cb->offset = offset;
 332         cb->length = length;
 333         cb->block = _tr_block( torrent, piece, offset );
 334         cb->buf = NULL;
 335         tr_ptrArrayInsertSorted( &cache->blocks, cb, cache_block_compare );
 336     }
 337
 338     cb->time = tr_time();
 339
 340     tr_free( cb->buf );
 341     cb->buf = tr_memdup( writeme, cb->length );
 342
 343     ++cache->cache_writes;
 344     cache->cache_write_bytes += cb->length;
 345
 346     return cacheTrim( cache );
 347 }
 348
 349 int
 350 tr_cacheReadBlock( tr_cache         * cache,
 351                    tr_torrent       * torrent,
 352                    tr_piece_index_t   piece,
 353                    uint32_t           offset,
 354                    uint32_t           len,
 355                    uint8_t          * setme )
 356 {
 357     int err = 0;
 358     struct cache_block * cb = findBlock( cache, torrent, piece, offset );
 359
 360     if( cb )
 361         memcpy( setme, cb->buf, len );
 362     else
 363         err = tr_ioRead( torrent, piece, offset, len, setme );
 364
 365     return err;
 366 }
 367
 368 int
 369 tr_cachePrefetchBlock( tr_cache         * cache,
 370                        tr_torrent       * torrent,
 371                        tr_piece_index_t   piece,
 372                        uint32_t           offset,
 373                        uint32_t           len )
 374 {
 375     int err = 0;
 376     struct cache_block * cb = findBlock( cache, torrent, piece, offset );
 377
 378     if( cb == NULL )
 379         err = tr_ioPrefetch( torrent, piece, offset, len );
 380
 381     return err;
 382 }
 383
 384 /***
 385 ****
 386 ***/
 387
 388 static int
 389 findPiece( tr_cache * cache, tr_torrent * torrent, tr_piece_index_t piece )
 390 {
 391     struct cache_block key;
 392     key.tor = torrent;
 393     key.block = tr_torPieceFirstBlock( torrent, piece );
 394     return tr_ptrArrayLowerBound( &cache->blocks, &key, cache_block_compare, NULL );
 395 }
 396
 397 int tr_cacheFlushDone( tr_cache * cache )
 398 {
 399     int err = 0;
 400
 401     if( tr_ptrArraySize( &cache->blocks ) > 0 )
 402     {
 403         struct run_info * runs = tr_new( struct run_info, tr_ptrArraySize( &cache->blocks ) );
 404         int i = 0, n;
 405
 406         n = calcRuns( cache, runs );
 407         while( i < n && ( runs[i].is_piece_done || runs[i].is_multi_piece ) )
 408             runs[i++].rank |= SESSIONFLAG;
 409         err = flushRuns( cache, runs, i );
 410         tr_free( runs );
 411     }
 412
 413     return err;
 414 }
 415
 416 int
 417 tr_cacheFlushFile( tr_cache * cache, tr_torrent * torrent, tr_file_index_t i )
 418 {
 419     int err = 0;
 420     const tr_file * file = &torrent->info.files[i];
 421     const tr_block_index_t begin = tr_torPieceFirstBlock( torrent, file->firstPiece );
 422     const tr_block_index_t end  = tr_torPieceFirstBlock( torrent, file->lastPiece ) + tr_torPieceCountBlocks( torrent, file->lastPiece );
 423     const int pos = findPiece( cache, torrent, file->firstPiece );
 424     dbgmsg( "flushing file %d from cache to disk: blocks [%zu...%zu)", (int)i, (size_t)begin, (size_t)end );
 425
 426     /* flush out all the blocks in that file */
 427     while( !err && ( pos < tr_ptrArraySize( &cache->blocks ) ) )
 428     {
 429         const struct cache_block * b = tr_ptrArrayNth( &cache->blocks, pos );
 430         if( b->tor != torrent ) break;
 431         if( ( b->block < begin ) || ( b->block >= end ) ) break;
 432         err = flushContiguous( cache, pos, getBlockRun( cache, pos, NULL ) );
 433     }
 434
 435     return err;
 436 }
 437
 438 int
 439 tr_cacheFlushTorrent( tr_cache * cache, tr_torrent * torrent )
 440 {
 441     int err = 0;
 442     const int pos = findPiece( cache, torrent, 0 );
 443
 444     /* flush out all the blocks in that torrent */
 445     while( !err && ( pos < tr_ptrArraySize( &cache->blocks ) ) )
 446     {
 447         const struct cache_block * b = tr_ptrArrayNth( &cache->blocks, pos );
 448         if( b->tor != torrent ) break;
 449         err = flushContiguous( cache, pos, getBlockRun( cache, pos, NULL ) );
 450     }
 451
 452     return err;
 453 }