libdvdnav/read_cache.c

   1 /*
   2  * Copyright (C) 2000 Rich Wareham <richwareham@users.sourceforge.net>
   3  *               2001-2004 the dvdnav project
   4  *
   5  * This file is part of libdvdnav, a DVD navigation library.
   6  *
   7  * libdvdnav is free software; you can redistribute it and/or modify
   8  * it under the terms of the GNU General Public License as published by
   9  * the Free Software Foundation; either version 2 of the License, or
  10  * (at your option) any later version.
  11  *
  12  * libdvdnav is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License along
  18  * with libdvdnav; if not, write to the Free Software Foundation, Inc.,
  19  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  20  */
  21 /*
  22  * There was a multithreaded read ahead cache in here for some time, but
  23  * it had only been used for a short time. If you want to have a look at it,
  24  * search the CVS attic.
  25  */
  26
  27 #ifdef HAVE_CONFIG_H
  28 #include "config.h"
  29 #endif
  30
  31 #include <inttypes.h>
  32 #include <stdlib.h>
  33 #include <limits.h>
  34 #include <sys/time.h>
  35 #include <time.h>
  36 #include "dvdnav/dvdnav.h"
  37 #include <dvdread/nav_types.h>
  38 #include <dvdread/ifo_types.h>
  39 #include "remap.h"
  40 #include "vm/decoder.h"
  41 #include "vm/vm.h"
  42 #include "dvdnav_internal.h"
  43 #include "read_cache.h"
  44
  45 #define READ_CACHE_CHUNKS 10
  46
  47 /* all cache chunks must be memory aligned to allow use of raw devices */
  48 #define ALIGNMENT 2048
  49
  50 #define READ_AHEAD_SIZE_MIN 4
  51 #define READ_AHEAD_SIZE_MAX 512
  52
  53 typedef struct read_cache_chunk_s {
  54   uint8_t     *cache_buffer;
  55   uint8_t     *cache_buffer_base;  /* used in malloc and free for alignment */
  56   int32_t      cache_start_sector; /* -1 means cache invalid */
  57   int32_t      cache_read_count;   /* this many sectors are already read */
  58   size_t       cache_block_count;  /* this many sectors will go in this chunk */
  59   size_t       cache_malloc_size;
  60   int          cache_valid;
  61   int          usage_count;  /* counts how many buffers where issued from this chunk */
  62 } read_cache_chunk_t;
  63
  64 struct read_cache_s {
  65   read_cache_chunk_t  chunk[READ_CACHE_CHUNKS];
  66   int                 current;
  67   int                 freeing;  /* is set to one when we are about to dispose the cache */
  68   uint32_t            read_ahead_size;
  69   int                 read_ahead_incr;
  70   int                 last_sector;
  71   pthread_mutex_t     lock;
  72
  73   /* Bit of strange cross-linking going on here :) -- Gotta love C :) */
  74   dvdnav_t           *dvd_self;
  75 };
  76
  77 /*
  78 #define READ_CACHE_TRACE 0
  79 */
  80
  81 #ifdef __GNUC__
  82 # if READ_CACHE_TRACE
  83 #  define dprintf(fmt, args...) fprintf(MSG_OUT, "libdvdnav: %s: "fmt,  __func__ , ## args)
  84 # else
  85 #  define dprintf(fmt, args...) /* Nowt */
  86 # endif
  87 #else
  88 # if READ_CACHE_TRACE
  89 #  define dprintf(fmt, ...) fprintf(MSG_OUT, "libdvdnav: %s: "fmt,  __func__ , __VA_ARGS__)
  90 # else
  91 #ifdef _MSC_VER
  92 #  define dprintf(fmt, str) /* Nowt */
  93 #else
  94 #  define dprintf(fmt, ...) /* Nowt */
  95 #endif /* _MSC_VER */
  96 # endif
  97 #endif
  98
  99
 100 read_cache_t *dvdnav_read_cache_new(dvdnav_t* dvd_self) {
 101   read_cache_t *self;
 102   int i;
 103
 104   self = (read_cache_t *)malloc(sizeof(read_cache_t));
 105
 106   if(self) {
 107     self->current = 0;
 108     self->freeing = 0;
 109     self->dvd_self = dvd_self;
 110     self->last_sector = 0;
 111     self->read_ahead_size = READ_AHEAD_SIZE_MIN;
 112     self->read_ahead_incr = 0;
 113     pthread_mutex_init(&self->lock, NULL);
 114     dvdnav_read_cache_clear(self);
 115     for (i = 0; i < READ_CACHE_CHUNKS; i++) {
 116       self->chunk[i].cache_buffer = NULL;
 117       self->chunk[i].usage_count = 0;
 118     }
 119   }
 120
 121   return self;
 122 }
 123
 124 void dvdnav_read_cache_free(read_cache_t* self) {
 125   dvdnav_t *tmp;
 126   int i;
 127
 128   pthread_mutex_lock(&self->lock);
 129   self->freeing = 1;
 130   for (i = 0; i < READ_CACHE_CHUNKS; i++)
 131     if (self->chunk[i].cache_buffer && self->chunk[i].usage_count == 0) {
 132       free(self->chunk[i].cache_buffer_base);
 133       self->chunk[i].cache_buffer = NULL;
 134     }
 135   pthread_mutex_unlock(&self->lock);
 136
 137   for (i = 0; i < READ_CACHE_CHUNKS; i++)
 138     if (self->chunk[i].cache_buffer) return;
 139
 140   /* all buffers returned, free everything */
 141   tmp = self->dvd_self;
 142   pthread_mutex_destroy(&self->lock);
 143   free(self);
 144   free(tmp);
 145 }
 146
 147 /* This function MUST be called whenever self->file changes. */
 148 void dvdnav_read_cache_clear(read_cache_t *self) {
 149   int i;
 150
 151   if(!self)
 152    return;
 153
 154   pthread_mutex_lock(&self->lock);
 155   for (i = 0; i < READ_CACHE_CHUNKS; i++)
 156     self->chunk[i].cache_valid = 0;
 157   pthread_mutex_unlock(&self->lock);
 158 }
 159
 160 /* This function is called just after reading the NAV packet. */
 161 void dvdnav_pre_cache_blocks(read_cache_t *self, int sector, size_t block_count) {
 162   int i, use;
 163
 164   if(!self)
 165     return;
 166
 167   if(!self->dvd_self->use_read_ahead)
 168     return;
 169
 170   pthread_mutex_lock(&self->lock);
 171
 172   /* find a free cache chunk that best fits the required size */
 173   use = -1;
 174   for (i = 0; i < READ_CACHE_CHUNKS; i++)
 175     if (self->chunk[i].usage_count == 0 && self->chunk[i].cache_buffer &&
 176         self->chunk[i].cache_malloc_size >= block_count &&
 177         (use == -1 || self->chunk[use].cache_malloc_size > self->chunk[i].cache_malloc_size))
 178       use = i;
 179
 180   if (use == -1) {
 181     /* we haven't found a cache chunk, so we try to reallocate an existing one */
 182     for (i = 0; i < READ_CACHE_CHUNKS; i++)
 183       if (self->chunk[i].usage_count == 0 && self->chunk[i].cache_buffer &&
 184           (use == -1 || self->chunk[use].cache_malloc_size < self->chunk[i].cache_malloc_size))
 185         use = i;
 186     if (use >= 0) {
 187       self->chunk[use].cache_buffer_base = realloc(self->chunk[use].cache_buffer_base,
 188         block_count * DVD_VIDEO_LB_LEN + ALIGNMENT);
 189       self->chunk[use].cache_buffer =
 190         (uint8_t *)(((uintptr_t)self->chunk[use].cache_buffer_base & ~((uintptr_t)(ALIGNMENT - 1))) + ALIGNMENT);
 191       dprintf("pre_cache DVD read realloc happened\n");
 192       self->chunk[use].cache_malloc_size = block_count;
 193     } else {
 194       /* we still haven't found a cache chunk, let's allocate a new one */
 195       for (i = 0; i < READ_CACHE_CHUNKS; i++)
 196         if (!self->chunk[i].cache_buffer) {
 197           use = i;
 198           break;
 199         }
 200       if (use >= 0) {
 201         /* We start with a sensible figure for the first malloc of 500 blocks.
 202          * Some DVDs I have seen venture to 450 blocks.
 203          * This is so that fewer realloc's happen if at all.
 204          */
 205         self->chunk[i].cache_buffer_base =
 206           malloc((block_count > 500 ? block_count : 500) * DVD_VIDEO_LB_LEN + ALIGNMENT);
 207         self->chunk[i].cache_buffer =
 208           (uint8_t *)(((uintptr_t)self->chunk[i].cache_buffer_base & ~((uintptr_t)(ALIGNMENT - 1))) + ALIGNMENT);
 209         self->chunk[i].cache_malloc_size = block_count > 500 ? block_count : 500;
 210         dprintf("pre_cache DVD read malloc %d blocks\n",
 211           (block_count > 500 ? block_count : 500 ));
 212       }
 213     }
 214   }
 215
 216   if (use >= 0) {
 217     self->chunk[use].cache_start_sector = sector;
 218     self->chunk[use].cache_block_count = block_count;
 219     self->chunk[use].cache_read_count = 0;
 220     self->chunk[use].cache_valid = 1;
 221     self->current = use;
 222   } else {
 223     dprintf("pre_caching was impossible, no cache chunk available\n");
 224   }
 225   pthread_mutex_unlock(&self->lock);
 226 }
 227
 228 int dvdnav_read_cache_block(read_cache_t *self, int sector, size_t block_count, uint8_t **buf) {
 229   int i, use;
 230   int start;
 231   int size;
 232   int incr;
 233   uint8_t *read_ahead_buf;
 234   int32_t res;
 235
 236   if(!self)
 237     return 0;
 238
 239   use = -1;
 240
 241   if(self->dvd_self->use_read_ahead) {
 242     /* first check, if sector is in current chunk */
 243     read_cache_chunk_t cur = self->chunk[self->current];
 244     if (cur.cache_valid && sector >= cur.cache_start_sector &&
 245         sector <= (cur.cache_start_sector + cur.cache_read_count) &&
 246         sector + block_count <= cur.cache_start_sector + cur.cache_block_count)
 247       use = self->current;
 248     else
 249       for (i = 0; i < READ_CACHE_CHUNKS; i++)
 250         if (self->chunk[i].cache_valid &&
 251             sector >= self->chunk[i].cache_start_sector &&
 252             sector <= (self->chunk[i].cache_start_sector + self->chunk[i].cache_read_count) &&
 253             sector + block_count <= self->chunk[i].cache_start_sector + self->chunk[i].cache_block_count)
 254             use = i;
 255   }
 256
 257   if (use >= 0) {
 258     read_cache_chunk_t *chunk;
 259
 260     /* Increment read-ahead size if sector follows the last sector */
 261     if (sector == (self->last_sector + 1)) {
 262       if (self->read_ahead_incr < READ_AHEAD_SIZE_MAX)
 263         self->read_ahead_incr++;
 264     } else {
 265       self->read_ahead_size = READ_AHEAD_SIZE_MIN;
 266       self->read_ahead_incr = 0;
 267     }
 268     self->last_sector = sector;
 269
 270     /* The following resources need to be protected by a mutex :
 271      *   self->chunk[*].cache_buffer
 272      *   self->chunk[*].cache_malloc_size
 273      *   self->chunk[*].usage_count
 274      */
 275     pthread_mutex_lock(&self->lock);
 276     chunk = &self->chunk[use];
 277     read_ahead_buf = chunk->cache_buffer + chunk->cache_read_count * DVD_VIDEO_LB_LEN;
 278     *buf = chunk->cache_buffer + (sector - chunk->cache_start_sector) * DVD_VIDEO_LB_LEN;
 279     chunk->usage_count++;
 280     pthread_mutex_unlock(&self->lock);
 281
 282     dprintf("libdvdnav: sector=%d, start_sector=%d, last_sector=%d\n", sector, chunk->cache_start_sector, chunk->cache_start_sector + chunk->cache_block_count);
 283
 284     /* read_ahead_size */
 285     incr = self->read_ahead_incr >> 1;
 286     if ((self->read_ahead_size + incr) > READ_AHEAD_SIZE_MAX) {
 287       self->read_ahead_size = READ_AHEAD_SIZE_MAX;
 288     } else {
 289       self->read_ahead_size += incr;
 290     }
 291
 292     /* real read size */
 293     start = chunk->cache_start_sector + chunk->cache_read_count;
 294     if (chunk->cache_read_count + self->read_ahead_size > chunk->cache_block_count) {
 295       size = chunk->cache_block_count - chunk->cache_read_count;
 296     } else {
 297       size = self->read_ahead_size;
 298       /* ensure that the sector we want will be read */
 299       if (sector >= chunk->cache_start_sector + chunk->cache_read_count + size)
 300         size = sector - chunk->cache_start_sector - chunk->cache_read_count;
 301     }
 302     dprintf("libdvdnav: read_ahead_size=%d, size=%d\n", self->read_ahead_size, size);
 303
 304     if (size)
 305       chunk->cache_read_count += DVDReadBlocks(self->dvd_self->file,
 306                                                start,
 307                                                size,
 308                                                read_ahead_buf);
 309
 310     res = DVD_VIDEO_LB_LEN * block_count;
 311
 312   } else {
 313
 314     if (self->dvd_self->use_read_ahead)
 315       dprintf("cache miss on sector %d\n", sector);
 316
 317     res = DVDReadBlocks(self->dvd_self->file,
 318                         sector,
 319                         block_count,
 320                         *buf) * DVD_VIDEO_LB_LEN;
 321   }
 322
 323   return res;
 324
 325 }
 326
 327 dvdnav_status_t dvdnav_free_cache_block(dvdnav_t *self, unsigned char *buf) {
 328   read_cache_t *cache;
 329   int i;
 330
 331   if (!self)
 332     return DVDNAV_STATUS_ERR;
 333
 334   cache = self->cache;
 335   if (!cache)
 336     return DVDNAV_STATUS_ERR;
 337
 338   pthread_mutex_lock(&cache->lock);
 339   for (i = 0; i < READ_CACHE_CHUNKS; i++) {
 340     if (cache->chunk[i].cache_buffer && buf >= cache->chunk[i].cache_buffer &&
 341         buf < cache->chunk[i].cache_buffer + cache->chunk[i].cache_malloc_size * DVD_VIDEO_LB_LEN) {
 342       cache->chunk[i].usage_count--;
 343     }
 344   }
 345   pthread_mutex_unlock(&cache->lock);
 346
 347   if (cache->freeing)
 348     /* when we want to dispose the cache, try freeing it now */
 349     dvdnav_read_cache_free(cache);
 350
 351   return DVDNAV_STATUS_OK;
 352 }