source: trunk/libtransmission/cache.c @ 12204

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

(trunk) #4138 "use stdbool.h instead of tr_bool" -- done.

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