source: trunk/libtransmission/cache.c @ 10937

Last change on this file since 10937 was 10937, checked in by charles, 12 years ago

(trunk) #3045 "speed units" -- change the public API of libtransmission based on feedback from livings

File size: 10.8 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$
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  time_t  last_block_time;
67  tr_bool is_aligned;
68};
69
70
71/* return a count of how many contiguous blocks there are starting at this pos */
72static int
73getBlockRun( const tr_cache * cache, int pos, struct run_info * info )
74{
75    int i;
76    const int n = tr_ptrArraySize( &cache->blocks );
77    const struct cache_block ** blocks = (const struct cache_block**) tr_ptrArrayBase( &cache->blocks );
78    const struct cache_block * ref = blocks[pos];
79    tr_block_index_t block = ref->block;
80
81    for( i=pos; i<n; ++i, ++block ) {
82        const struct cache_block * b = blocks[i];
83        if( b->block != block ) break;
84        if( b->tor != ref->tor ) break;
85//fprintf( stderr, "pos %d tor %d block %zu time %zu\n", i, b->tor->uniqueId, (size_t)b->block, (size_t)b->time );
86    }
87
88//fprintf( stderr, "run is %d long from [%d to %d)\n", (int)(i-pos), i, (int)pos );
89    if( info != NULL ) {
90        info->last_block_time = blocks[i-1]->time;
91        info->is_aligned = (blocks[pos]->block % 2 == 0) ? TRUE : FALSE;
92    }
93
94    return i-pos;
95}
96
97/* return the starting index of the longest contiguous run of blocks BUT:
98 *   - Run should begin with a even block and length of run should be even.
99 *   - Oldest run is preferred.
100 */
101static int
102findChunk2Discard( tr_cache * cache, int * setme_n )
103{
104    const int n = tr_ptrArraySize( &cache->blocks );
105    int pos;
106    int bestpos = 0;
107    unsigned bestlen = 1;
108    unsigned jump;
109    time_t oldest_time = tr_time() + 1;
110    struct run_info run;
111
112    for( pos=0; pos<n; pos+=jump )
113    {
114        unsigned len = getBlockRun( cache, pos, &run );
115        jump = len;
116
117        /* shortcut */
118        if( len < bestlen )
119            continue;
120
121        /* check alignment */
122        if( len % 2 == 0 ) {
123            if( !run.is_aligned ) {
124                /* Let it grow. Otherwise we contribute to fragmentation */
125                if( bestlen == 1) {
126                    /* But if all other blocks are non-contiguous, we prefer this one */
127                    bestpos = pos;
128                    oldest_time = cache->max_blocks - len;
129                }
130                continue;
131            }
132        } else {
133            if( len != 1 ) {
134                --len;
135                if( !run.is_aligned ) {
136                    ++pos;
137                    --jump;
138                }
139            }
140        }
141
142        if( bestlen < len ) {
143            bestlen = len;
144            bestpos = pos;
145            oldest_time = run.last_block_time;
146        } else if( (bestlen == len) && (oldest_time > run.last_block_time) ) {
147            bestpos = pos;
148            oldest_time = run.last_block_time;
149        }
150    }
151
152//fprintf( stderr, "DISCARDED run is %d long from [%d to %d)\n", bestlen, bestpos, bestpos+bestlen );
153    *setme_n = bestlen;
154    return bestpos;
155}
156
157static int
158flushContiguous( tr_cache * cache, int pos, int n )
159{
160    int i;
161    int err = 0;
162    uint8_t * buf = tr_new( uint8_t, n * MAX_BLOCK_SIZE );
163    uint8_t * walk = buf;
164    struct cache_block ** blocks = (struct cache_block**) tr_ptrArrayBase( &cache->blocks );
165
166    struct cache_block * b = blocks[pos];
167    tr_torrent * tor             = b->tor;
168    const tr_piece_index_t piece = b->piece;
169    const uint32_t offset        = b->offset;
170
171//fprintf( stderr, "flushing %d contiguous blocks [%d-%d) from cache to disk\n", n, pos, n+pos );
172
173    for( i=pos; i<pos+n; ++i ) {
174        b = blocks[i];
175        memcpy( walk, b->buf, b->length );
176        walk += b->length;
177        tr_free( b->buf );
178        tr_free( b );
179    }
180    tr_ptrArrayErase( &cache->blocks, pos, pos+n );
181
182    tr_tordbg( tor, "Writing to disk piece %d, offset %d, len %d", (int)piece, (int)offset, (int)(walk-buf) );
183    tr_ndbg( MY_NAME, "Removing %d blocks from cache; %d left", n, tr_ptrArraySize(&cache->blocks) );
184    //fprintf( stderr, "%s - Writing to disk piece %d, offset %d, len %d\n", tr_torrentName(tor), (int)piece, (int)offset, (int)(walk-buf) );
185    //fprintf( stderr, "%s - Removing %d blocks from cache; %d left\n", MY_NAME, n, tr_ptrArraySize(&cache->blocks) );
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
196cacheTrim( tr_cache * cache )
197{
198    int err = 0;
199
200    while( !err && ( tr_ptrArraySize( &cache->blocks ) > cache->max_blocks ) )
201    {
202        int n;
203        const int i = findChunk2Discard( cache, &n );
204        err = flushContiguous( cache, i, n );
205    }
206
207    return err;
208}
209
210/***
211****
212***/
213
214static int
215getMaxBlocks( int64_t max_bytes )
216{
217    return max_bytes / (double)MAX_BLOCK_SIZE;
218}
219
220int
221tr_cacheSetLimit( tr_cache * cache, int64_t max_bytes )
222{
223    char buf[128];
224
225    cache->max_bytes = max_bytes;
226    cache->max_blocks = getMaxBlocks( max_bytes );
227
228    tr_formatter_mem_B( buf, cache->max_bytes, sizeof( buf ) );
229    tr_ndbg( MY_NAME, "Maximum cache size set to %s (%d blocks)", buf, cache->max_blocks );
230
231    return cacheTrim( cache );
232}
233
234int64_t
235tr_cacheGetLimit( const tr_cache * cache )
236{
237    return cache->max_bytes;
238}
239
240tr_cache *
241tr_cacheNew( int64_t max_bytes )
242{
243    tr_cache * cache = tr_new0( tr_cache, 1 );
244    cache->blocks = TR_PTR_ARRAY_INIT;
245    cache->max_bytes = max_bytes;
246    cache->max_blocks = getMaxBlocks( max_bytes );
247    return cache;
248}
249
250void
251tr_cacheFree( tr_cache * cache )
252{
253    assert( tr_ptrArrayEmpty( &cache->blocks ) );
254    tr_ptrArrayDestruct( &cache->blocks, NULL );
255    tr_free( cache );
256}
257
258/***
259****
260***/
261
262static int
263cache_block_compare( const void * va, const void * vb )
264{
265    const struct cache_block * a = va;
266    const struct cache_block * b = vb;
267
268    /* primary key: torrent id */
269    if( a->tor->uniqueId != b->tor->uniqueId )
270        return a->tor->uniqueId < b->tor->uniqueId ? -1 : 1;
271
272    /* secondary key: block # */
273    if( a->block != b->block )
274        return a->block < b->block ? -1 : 1;
275
276    /* they're equal */
277    return 0;
278}
279
280static struct cache_block *
281findBlock( tr_cache           * cache,
282           tr_torrent         * torrent, 
283           tr_piece_index_t     piece,
284           uint32_t             offset )
285{
286    struct cache_block key;
287    key.tor = torrent;
288    key.block = _tr_block( torrent, piece, offset );
289    return tr_ptrArrayFindSorted( &cache->blocks, &key, cache_block_compare );
290}
291
292int
293tr_cacheWriteBlock( tr_cache         * cache,
294                    tr_torrent       * torrent,
295                    tr_piece_index_t   piece,
296                    uint32_t           offset,
297                    uint32_t           length,
298                    const uint8_t    * writeme )
299{
300    struct cache_block * cb = findBlock( cache, torrent, piece, offset );
301
302    if( cb == NULL )
303    {
304        cb = tr_new( struct cache_block, 1 );
305        cb->tor = torrent;
306        cb->piece = piece;
307        cb->offset = offset;
308        cb->length = length;
309        cb->block = _tr_block( torrent, piece, offset );
310        cb->buf = NULL;
311        tr_ptrArrayInsertSorted( &cache->blocks, cb, cache_block_compare );
312    }
313
314    cb->time = tr_time();
315
316    tr_free( cb->buf );
317    cb->buf = tr_memdup( writeme, cb->length );
318
319    ++cache->cache_writes;
320    cache->cache_write_bytes += cb->length;
321
322    return cacheTrim( cache );
323}
324
325int
326tr_cacheReadBlock( tr_cache         * cache,
327                   tr_torrent       * torrent,
328                   tr_piece_index_t   piece,
329                   uint32_t           offset,
330                   uint32_t           len,
331                   uint8_t          * setme )
332{
333    int err = 0;
334    struct cache_block * cb = findBlock( cache, torrent, piece, offset );
335
336    if( cb )
337        memcpy( setme, cb->buf, len );
338    else
339        err = tr_ioRead( torrent, piece, offset, len, setme );
340
341    return err;
342}
343
344int
345tr_cachePrefetchBlock( tr_cache         * cache,
346                       tr_torrent       * torrent,
347                       tr_piece_index_t   piece,
348                       uint32_t           offset,
349                       uint32_t           len )
350{
351    int err = 0;
352    struct cache_block * cb = findBlock( cache, torrent, piece, offset );
353
354    if( cb == NULL )
355        err = tr_ioPrefetch( torrent, piece, offset, len );
356
357    return err;
358}
359
360/***
361****
362***/
363
364static int
365findPiece( tr_cache * cache, tr_torrent * torrent, tr_piece_index_t piece )
366{
367    struct cache_block key;
368    key.tor = torrent;
369    key.block = tr_torPieceFirstBlock( torrent, piece );
370    return tr_ptrArrayLowerBound( &cache->blocks, &key, cache_block_compare, NULL );
371}
372
373int
374tr_cacheFlushFile( tr_cache * cache, tr_torrent * torrent, tr_file_index_t i )
375{
376    int err = 0;
377    const tr_file * file = &torrent->info.files[i];
378    const tr_block_index_t begin = tr_torPieceFirstBlock( torrent, file->firstPiece );
379    const tr_block_index_t end  = tr_torPieceFirstBlock( torrent, file->lastPiece ) + tr_torPieceCountBlocks( torrent, file->lastPiece );
380    const int pos = findPiece( cache, torrent, file->firstPiece );
381    dbgmsg( "flushing file %d from cache to disk: blocks [%zu...%zu)", (int)i, (size_t)begin, (size_t)end );
382
383    /* flush out all the blocks in that file */
384    while( !err && ( pos < tr_ptrArraySize( &cache->blocks ) ) )
385    {
386        const struct cache_block * b = tr_ptrArrayNth( &cache->blocks, pos );
387        if( b->tor != torrent ) break;
388        if( ( b->block < begin ) || ( b->block >= end ) ) break;
389        err = flushContiguous( cache, pos, getBlockRun( cache, pos, NULL ) );
390    }
391
392    return err;
393}
394
395int
396tr_cacheFlushTorrent( tr_cache * cache, tr_torrent * torrent )
397{
398    int err = 0;
399    const int pos = findPiece( cache, torrent, 0 );
400
401    /* flush out all the blocks in that torrent */
402    while( !err && ( pos < tr_ptrArraySize( &cache->blocks ) ) )
403    {
404        const struct cache_block * b = tr_ptrArrayNth( &cache->blocks, pos );
405        if( b->tor != torrent ) break;
406        err = flushContiguous( cache, pos, getBlockRun( cache, pos, NULL ) );
407    }
408
409    return err;
410}
Note: See TracBrowser for help on using the repository browser.