source: trunk/libtransmission/cache.c @ 12918

Last change on this file since 12918 was 12653, checked in by jordan, 10 years ago

remove dead code

  • Property svn:keywords set to Date Rev Author Id
File size: 11.6 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 12653 2011-08-08 16:58:29Z 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    for( i=pos; i<pos+n; ++i ) {
175        b = blocks[i];
176        evbuffer_copyout( b->evbuf, walk, b->length );
177        walk += b->length;
178        evbuffer_free( b->evbuf );
179        tr_free( b );
180    }
181    tr_ptrArrayErase( &cache->blocks, pos, pos+n );
182
183    err = tr_ioWrite( tor, piece, offset, walk-buf, buf );
184    tr_free( buf );
185
186    ++cache->disk_writes;
187    cache->disk_write_bytes += walk-buf;
188    return err;
189}
190
191static int
192flushRuns( tr_cache * cache, struct run_info * runs, int n )
193{
194    int i, j, err = 0;
195
196    for( i = 0; !err && i < n; ++i )
197    {
198        err = flushContiguous( cache, runs[i].pos, runs[i].len );
199        for( j = i + 1; j < n; ++j )
200            if( runs[j].pos > runs[i].pos )
201                runs[j].pos -= runs[i].len;
202    }
203
204    return err;
205}
206
207static int
208cacheTrim( tr_cache * cache )
209{
210    int err = 0;
211
212    if( tr_ptrArraySize( &cache->blocks ) > cache->max_blocks )
213    {
214        /* Amount of cache that should be removed by the flush. This influences how large
215         * runs can grow as well as how often flushes will happen. */
216        const int cacheCutoff = 1 + cache->max_blocks / 4;
217        struct run_info * runs = tr_new( struct run_info, tr_ptrArraySize( &cache->blocks ) );
218        int i = 0, j = 0;
219
220        calcRuns( cache, runs );
221        while( j < cacheCutoff )
222            j += runs[i++].len;
223        err = flushRuns( cache, runs, i );
224        tr_free( runs );
225    }
226
227    return err;
228}
229
230/***
231****
232***/
233
234static int
235getMaxBlocks( int64_t max_bytes )
236{
237    return max_bytes / (double)MAX_BLOCK_SIZE;
238}
239
240int
241tr_cacheSetLimit( tr_cache * cache, int64_t max_bytes )
242{
243    char buf[128];
244
245    cache->max_bytes = max_bytes;
246    cache->max_blocks = getMaxBlocks( max_bytes );
247
248    tr_formatter_mem_B( buf, cache->max_bytes, sizeof( buf ) );
249    tr_ndbg( MY_NAME, "Maximum cache size set to %s (%d blocks)", buf, cache->max_blocks );
250
251    return cacheTrim( cache );
252}
253
254int64_t
255tr_cacheGetLimit( const tr_cache * cache )
256{
257    return cache->max_bytes;
258}
259
260tr_cache *
261tr_cacheNew( int64_t max_bytes )
262{
263    tr_cache * cache = tr_new0( tr_cache, 1 );
264    cache->blocks = TR_PTR_ARRAY_INIT;
265    cache->max_bytes = max_bytes;
266    cache->max_blocks = getMaxBlocks( max_bytes );
267    return cache;
268}
269
270void
271tr_cacheFree( tr_cache * cache )
272{
273    assert( tr_ptrArrayEmpty( &cache->blocks ) );
274    tr_ptrArrayDestruct( &cache->blocks, NULL );
275    tr_free( cache );
276}
277
278/***
279****
280***/
281
282static int
283cache_block_compare( const void * va, const void * vb )
284{
285    const struct cache_block * a = va;
286    const struct cache_block * b = vb;
287
288    /* primary key: torrent id */
289    if( a->tor->uniqueId != b->tor->uniqueId )
290        return a->tor->uniqueId < b->tor->uniqueId ? -1 : 1;
291
292    /* secondary key: block # */
293    if( a->block != b->block )
294        return a->block < b->block ? -1 : 1;
295
296    /* they're equal */
297    return 0;
298}
299
300static struct cache_block *
301findBlock( tr_cache           * cache,
302           tr_torrent         * torrent,
303           tr_piece_index_t     piece,
304           uint32_t             offset )
305{
306    struct cache_block key;
307    key.tor = torrent;
308    key.block = _tr_block( torrent, piece, offset );
309    return tr_ptrArrayFindSorted( &cache->blocks, &key, cache_block_compare );
310}
311
312int
313tr_cacheWriteBlock( tr_cache         * cache,
314                    tr_torrent       * torrent,
315                    tr_piece_index_t   piece,
316                    uint32_t           offset,
317                    uint32_t           length,
318                    struct evbuffer  * writeme )
319{
320    struct cache_block * cb = findBlock( cache, torrent, piece, offset );
321
322    if( cb == NULL )
323    {
324        cb = tr_new( struct cache_block, 1 );
325        cb->tor = torrent;
326        cb->piece = piece;
327        cb->offset = offset;
328        cb->length = length;
329        cb->block = _tr_block( torrent, piece, offset );
330        cb->evbuf = evbuffer_new( );
331        tr_ptrArrayInsertSorted( &cache->blocks, cb, cache_block_compare );
332    }
333
334    cb->time = tr_time();
335
336    assert( cb->length == length );
337    evbuffer_drain( cb->evbuf, evbuffer_get_length( cb->evbuf ) );
338    evbuffer_remove_buffer( writeme, cb->evbuf, cb->length );
339
340    ++cache->cache_writes;
341    cache->cache_write_bytes += cb->length;
342
343    return cacheTrim( cache );
344}
345
346int
347tr_cacheReadBlock( tr_cache         * cache,
348                   tr_torrent       * torrent,
349                   tr_piece_index_t   piece,
350                   uint32_t           offset,
351                   uint32_t           len,
352                   uint8_t          * setme )
353{
354    int err = 0;
355    struct cache_block * cb = findBlock( cache, torrent, piece, offset );
356
357    if( cb )
358        evbuffer_copyout( cb->evbuf, setme, len );
359    else
360        err = tr_ioRead( torrent, piece, offset, len, setme );
361
362    return err;
363}
364
365int
366tr_cachePrefetchBlock( tr_cache         * cache,
367                       tr_torrent       * torrent,
368                       tr_piece_index_t   piece,
369                       uint32_t           offset,
370                       uint32_t           len )
371{
372    int err = 0;
373    struct cache_block * cb = findBlock( cache, torrent, piece, offset );
374
375    if( cb == NULL )
376        err = tr_ioPrefetch( torrent, piece, offset, len );
377
378    return err;
379}
380
381/***
382****
383***/
384
385static int
386findBlockPos( tr_cache * cache, tr_torrent * torrent, tr_piece_index_t block )
387{
388    struct cache_block key;
389    key.tor = torrent;
390    key.block = block;
391    return tr_ptrArrayLowerBound( &cache->blocks, &key, cache_block_compare, NULL );
392}
393
394int tr_cacheFlushDone( tr_cache * cache )
395{
396    int err = 0;
397
398    if( tr_ptrArraySize( &cache->blocks ) > 0 )
399    {
400        struct run_info * runs = tr_new( struct run_info, tr_ptrArraySize( &cache->blocks ) );
401        int i = 0, n;
402
403        n = calcRuns( cache, runs );
404        while( i < n && ( runs[i].is_piece_done || runs[i].is_multi_piece ) )
405            runs[i++].rank |= SESSIONFLAG;
406        err = flushRuns( cache, runs, i );
407        tr_free( runs );
408    }
409
410    return err;
411}
412
413int
414tr_cacheFlushFile( tr_cache * cache, tr_torrent * torrent, tr_file_index_t i )
415{
416    int pos;
417    int err = 0;
418    tr_block_index_t first;
419    tr_block_index_t last;
420    tr_torGetFileBlockRange( torrent, i, &first, &last );
421    pos = findBlockPos( cache, torrent, first );
422    dbgmsg( "flushing file %d from cache to disk: blocks [%zu...%zu]", (int)i, (size_t)first, (size_t)last );
423
424    /* flush out all the blocks in that file */
425    while( !err && ( pos < tr_ptrArraySize( &cache->blocks ) ) )
426    {
427        const struct cache_block * b = tr_ptrArrayNth( &cache->blocks, pos );
428        if( b->tor != torrent ) break;
429        if( ( b->block < first ) || ( b->block > last ) ) break;
430        err = flushContiguous( cache, pos, getBlockRun( cache, pos, NULL ) );
431    }
432
433    return err;
434}
435
436int
437tr_cacheFlushTorrent( tr_cache * cache, tr_torrent * torrent )
438{
439    int err = 0;
440    const int pos = findBlockPos( cache, torrent, 0 );
441
442    /* flush out all the blocks in that torrent */
443    while( !err && ( pos < tr_ptrArraySize( &cache->blocks ) ) )
444    {
445        const struct cache_block * b = tr_ptrArrayNth( &cache->blocks, pos );
446        if( b->tor != torrent ) break;
447        err = flushContiguous( cache, pos, getBlockRun( cache, pos, NULL ) );
448    }
449
450    return err;
451}
Note: See TracBrowser for help on using the repository browser.