source: trunk/libtransmission/cache.c @ 13868

Last change on this file since 13868 was 13868, checked in by jordan, 8 years ago

make all the log functions/structs/enums use a single 'tr_log' namespace, such as tr_logGetQueue, tr_logAddInfo, tr_logIsLevelActive

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