source: trunk/libtransmission/cache.c @ 11709

Last change on this file since 11709 was 11709, checked in by jordan, 11 years ago

Update the copyright year in the source code comments.

The Berne Convention says that the copyright year is moot, so instead of adding another year to each file as in previous years, I've removed the year altogether from the source code comments in libtransmission, gtk, qt, utils, daemon, and cli.

Juliusz's copyright notice in tr-dht and Johannes' copyright notice in tr-lpd have been left alone; it didn't seem appropriate to modify them.

  • Property svn:keywords set to Date Rev Author Id
File size: 12.1 KB
Line 
1/*
2 * This file Copyright (C) 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 11709 2011-01-19 13:48:47Z jordan $
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
34struct 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
48struct 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
64struct 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 */
76static int
77getBlockRun( 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
105static int
106compareRuns( 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
113enum
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 */
123static int
124calcRuns( 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
155static int
156flushContiguous( 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
195static int
196flushRuns( 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
211static int
212cacheTrim( 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
238static int
239getMaxBlocks( int64_t max_bytes )
240{
241    return max_bytes / (double)MAX_BLOCK_SIZE;
242}
243
244int
245tr_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
258int64_t
259tr_cacheGetLimit( const tr_cache * cache )
260{
261    return cache->max_bytes;
262}
263
264tr_cache *
265tr_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
274void
275tr_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
286static int
287cache_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
304static struct cache_block *
305findBlock( 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
316int
317tr_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
349int
350tr_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
368int
369tr_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
388static int
389findPiece( 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
397int 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
416int
417tr_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
438int
439tr_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}
Note: See TracBrowser for help on using the repository browser.