source: trunk/libtransmission/cache.c @ 11599

Last change on this file since 11599 was 11599, checked in by charles, 11 years ago

(trunk) Join the 21st century and use only 1 space at the end sentences. This commit is nearly as important as the semi-annual ones that remove trailing spaces from the ends of lines of code... :)

  • Property svn:keywords set to Date Rev Author Id
File size: 12.1 KB
Line 
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 11599 2010-12-27 19:18:17Z 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
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.