git.sesse.net Git - mlt/blob - src/framework/mlt_cache.c

   1 /**
   2  * \file mlt_cache.c
   3  * \brief least recently used cache
   4  * \see mlt_profile_s
   5  *
   6  * Copyright (C) 2007-2012 Ushodaya Enterprises Limited
   7  * \author Dan Dennedy <dan@dennedy.org>
   8  *
   9  * This library is free software; you can redistribute it and/or
  10  * modify it under the terms of the GNU Lesser General Public
  11  * License as published by the Free Software Foundation; either
  12  * version 2.1 of the License, or (at your option) any later version.
  13  *
  14  * This library is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  17  * Lesser General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU Lesser General Public
  20  * License along with this library; if not, write to the Free Software
  21  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  22  */
  23
  24 #include "mlt_types.h"
  25 #include "mlt_log.h"
  26 #include "mlt_properties.h"
  27 #include "mlt_cache.h"
  28 #include "mlt_frame.h"
  29
  30 #include <stdlib.h>
  31 #include <pthread.h>
  32
  33 /** the maximum number of data objects to cache per line */
  34 #define MAX_CACHE_SIZE (200)
  35
  36 /** the default number of data objects to cache per line */
  37 #define DEFAULT_CACHE_SIZE (4)
  38
  39 /** \brief Cache item class
  40  *
  41  * A cache item is a structure holding information about a data object including
  42  * a reference count that is used to control its lifetime. When you get a
  43  * a cache item from the cache, you hold a reference that prevents the data
  44  * from being released when the cache is full and something new is added.
  45  * When you close the cache item, the reference count is decremented.
  46  * The data object is destroyed when all cache items are closed and the cache
  47  * releases its reference.
  48  */
  49
  50 typedef struct mlt_cache_item_s
  51 {
  52         mlt_cache cache;           /**< a reference to the cache to which this belongs */
  53         void *object;              /**< a parent object to the cache data that uniquely identifies this cached item */
  54         void *data;                /**< the opaque pointer to the cached data */
  55         int size;                  /**< the size of the cached data */
  56         int refcount;              /**< a reference counter to control when destructor is called */
  57         mlt_destructor destructor; /**< a function to release or destroy the cached data */
  58 } mlt_cache_item_s;
  59
  60 /** \brief Cache class
  61  *
  62  * This is a utility class for implementing a Least Recently Used (LRU) cache
  63  * of data blobs indexed by the address of some other object (e.g., a service).
  64  * Instead of sorting and manipulating linked lists, it tries to be simple and
  65  * elegant by copying pointers between two arrays of fixed size to shuffle the
  66  * order of elements.
  67  *
  68  * This class is useful if you have a service that wants to cache something
  69  * somewhat large, but will not scale if there are many instances of the service.
  70  * Of course, the service will need to know how to recreate the cached element
  71  * if it gets flushed from the cache,
  72  *
  73  * The most obvious examples are the pixbuf and qimage producers that cache their
  74  * respective objects representing a picture read from a file. If the picture
  75  * is no longer in the cache, it can simply re-read it from file. However, a
  76  * picture is often repeated over many frames and makes sense to cache instead
  77  * of continually reading, parsing, and decoding. On the other hand, you might
  78  * want to load hundreds of pictures as individual producers, which would use
  79  * a lot of memory if every picture is held in memory!
  80  */
  81
  82 struct mlt_cache_s
  83 {
  84         int count;             /**< the number of items currently in the cache */
  85         int size;              /**< the maximum number of items permitted in the cache <= \p MAX_CACHE_SIZE */
  86         int is_frames;         /**< indicates if this cache is used to cache frames */
  87         void* *current;        /**< pointer to the current array of pointers */
  88         void* A[ MAX_CACHE_SIZE ];
  89         void* B[ MAX_CACHE_SIZE ];
  90         pthread_mutex_t mutex; /**< a mutex to prevent multi-threaded race conditions */
  91         mlt_properties active; /**< a list of cache items some of which may no longer
  92                                     be in \p current but to which there are
  93                                     outstanding references */
  94         mlt_properties garbage;/**< a list cache items pending release. A cache item
  95                                     is copied to this list when it is updated but there
  96                                     are outstanding references to the old data object. */
  97 };
  98
  99 /** Get the data pointer from the cache item.
 100  *
 101  * \public \memberof mlt_cache_s
 102  * \param item a cache item
 103  * \param[out] size the number of bytes pointed at, if supplied when putting the data into the cache
 104  * \return the data pointer
 105  */
 106
 107 void *mlt_cache_item_data( mlt_cache_item item, int *size )
 108 {
 109         if ( size && item )
 110                 *size = item->size;
 111         return item? item->data : NULL;
 112 }
 113
 114 /** Close a cache item given its parent object pointer.
 115  *
 116  * \private \memberof mlt_cache_s
 117  * \param cache a cache
 118  * \param object the object to which the data object belongs
 119  * \param data the data object, which might be in the garbage list (optional)
 120  */
 121
 122 static void cache_object_close( mlt_cache cache, void *object, void* data )
 123 {
 124         char key[19];
 125
 126         if ( cache->is_frames )
 127         {
 128                 // Frame caches are easy - just close the object as mlt_frame.
 129                 mlt_frame_close( object );
 130                 return;
 131         }
 132
 133         // Fetch the cache item from the active list by its owner's address
 134         sprintf( key, "%p", object );
 135         mlt_cache_item item = mlt_properties_get_data( cache->active, key, NULL );
 136         if ( item )
 137         {
 138                 mlt_log( NULL, MLT_LOG_DEBUG, "%s: item %p object %p data %p refcount %d\n", __FUNCTION__,
 139                         item, item->object, item->data, item->refcount );
 140                 if ( item->destructor && --item->refcount <= 0 )
 141                 {
 142                         // Destroy the data object
 143                         item->destructor( item->data );
 144                         item->data = NULL;
 145                         item->destructor = NULL;
 146                         // Do not dispose of the cache item because it could likely be used
 147                         // again.
 148                 }
 149         }
 150
 151         // Fetch the cache item from the garbage collection by its data address
 152         if ( data )
 153         {
 154                 sprintf( key, "%p", data );
 155                 item = mlt_properties_get_data( cache->garbage, key, NULL );
 156                 if ( item )
 157                 {
 158                         mlt_log( NULL, MLT_LOG_DEBUG, "collecting garbage item %p object %p data %p refcount %d\n",
 159                                 item, item->object, item->data, item->refcount );
 160                         if ( item->destructor && --item->refcount <= 0 )
 161                         {
 162                                 item->destructor( item->data );
 163                                 item->data = NULL;
 164                                 item->destructor = NULL;
 165                                 // We do not need the garbage-collected cache item
 166                                 mlt_properties_set_data( cache->garbage, key, NULL, 0, NULL, NULL );
 167                         }
 168                 }
 169         }
 170 }
 171
 172 /** Close a cache item.
 173  *
 174  * Release a reference and call the destructor on the data object when all
 175  * references are released.
 176  *
 177  * \public \memberof mlt_cache_item_s
 178  * \param item a cache item
 179  */
 180
 181 void mlt_cache_item_close( mlt_cache_item item )
 182 {
 183         if ( item )
 184         {
 185                 pthread_mutex_lock( &item->cache->mutex );
 186                 cache_object_close( item->cache, item->object, item->data );
 187                 pthread_mutex_unlock( &item->cache->mutex );
 188         }
 189 }
 190
 191 /** Create a new cache.
 192  *
 193  * The default size is \p DEFAULT_CACHE_SIZE.
 194  * \public \memberof mlt_cache_s
 195  * \return a new cache or NULL if there was an error
 196  */
 197
 198 mlt_cache mlt_cache_init()
 199 {
 200         mlt_cache result = calloc( 1, sizeof( struct mlt_cache_s ) );
 201         if ( result )
 202         {
 203                 result->size = DEFAULT_CACHE_SIZE;
 204                 result->current = result->A;
 205                 pthread_mutex_init( &result->mutex, NULL );
 206                 result->active = mlt_properties_new();
 207                 result->garbage = mlt_properties_new();
 208         }
 209         return result;
 210 }
 211
 212 /** Set the numer of items to cache.
 213  *
 214  * This must be called before using the cache. The size can not be more
 215  * than \p MAX_CACHE_SIZE.
 216  * \public \memberof mlt_cache_s
 217  * \param cache the cache to adjust
 218  * \param size the new size of the cache
 219  */
 220
 221 void mlt_cache_set_size( mlt_cache cache, int size )
 222 {
 223         if ( size <= MAX_CACHE_SIZE )
 224                 cache->size = size;
 225 }
 226
 227 /** Get the numer of possible cache items.
 228  *
 229  * \public \memberof mlt_cache_s
 230  * \param cache the cache to check
 231  * \return the current maximum size of the cache
 232  */
 233
 234 int mlt_cache_get_size( mlt_cache cache )
 235 {
 236     return cache->size;
 237 }
 238
 239 /** Destroy a cache.
 240  *
 241  * \public \memberof mlt_cache_s
 242  * \param cache the cache to destroy
 243  */
 244
 245 void mlt_cache_close( mlt_cache cache )
 246 {
 247         if ( cache )
 248         {
 249                 while ( cache->count-- )
 250                 {
 251                         void *object = cache->current[ cache->count ];
 252                         mlt_log( NULL, MLT_LOG_DEBUG, "%s: %d = %p\n", __FUNCTION__, cache->count, object );
 253                         cache_object_close( cache, object, NULL );
 254                 }
 255                 mlt_properties_close( cache->active );
 256                 mlt_properties_close( cache->garbage );
 257                 pthread_mutex_destroy( &cache->mutex );
 258                 free( cache );
 259         }
 260 }
 261
 262 /** Remove cache entries for an object.
 263  *
 264  * \public \memberof mlt_cache_s
 265  * \param cache a cache
 266  * \param object the object that owns the cached data
 267  */
 268
 269 void mlt_cache_purge( mlt_cache cache, void *object )
 270 {
 271         if (!cache) return;
 272         pthread_mutex_lock( &cache->mutex );
 273         if ( cache && object )
 274         {
 275                 int i, j;
 276                 void **alt = cache->current == cache->A ? cache->B : cache->A;
 277
 278                 for ( i = 0, j = 0; i < cache->count; i++ )
 279                 {
 280                         void *o = cache->current[ i ];
 281
 282                         if ( o == object )
 283                         {
 284                                 cache_object_close( cache, o, NULL );
 285                         }
 286                         else
 287                         {
 288                                 alt[ j++ ] = o;
 289                         }
 290                 }
 291                 cache->count = j;
 292                 cache->current = alt;
 293         }
 294         pthread_mutex_unlock( &cache->mutex );
 295 }
 296
 297 /** Shuffle the cache entries between the two arrays and return the cache entry for an object.
 298  *
 299  * \private \memberof mlt_cache_s
 300  * \param cache a cache object
 301  * \param object the object that owns the cached data
 302  * \return a cache entry if there was a hit or NULL for a miss
 303  */
 304
 305 static void** shuffle_get_hit( mlt_cache cache, void *object )
 306 {
 307         int i = cache->count;
 308         int j = cache->count - 1;
 309         void **hit = NULL;
 310         void **alt = cache->current == cache->A ? cache->B : cache->A;
 311
 312         if ( cache->count > 0 && cache->count < cache->size )
 313         {
 314                 // first determine if we have a hit
 315                 while ( i-- && !hit )
 316                 {
 317                         void **o = &cache->current[ i ];
 318                         if ( *o == object )
 319                                 hit = o;
 320                 }
 321                 // if there was no hit, we will not be shuffling out an entry
 322                 // and are still filling the cache
 323                 if ( !hit )
 324                         ++j;
 325                 // reset these
 326                 i = cache->count;
 327                 hit = NULL;
 328         }
 329
 330         // shuffle the existing entries to the alternate array
 331         while ( i-- )
 332         {
 333                 void **o = &cache->current[ i ];
 334
 335                 if ( !hit && *o == object )
 336                 {
 337                         hit = o;
 338                 }
 339                 else if ( j > 0 )
 340                 {
 341                         alt[ --j ] = *o;
 342 //                      mlt_log( NULL, MLT_LOG_DEBUG, "%s: shuffle %d = %p\n", __FUNCTION__, j, alt[j] );
 343                 }
 344         }
 345         return hit;
 346 }
 347
 348 /** Put a chunk of data in the cache.
 349  *
 350  * This function and mlt_cache_get() are not scalable with a large volume
 351  * of unique \p object paramter values. Therefore, it does not make sense
 352  * to use it for a frame/image cache using the frame position for \p object.
 353  * Instead, use mlt_cache_put_frame() for that.
 354  *
 355  * \public \memberof mlt_cache_s
 356  * \param cache a cache object
 357  * \param object the object to which this data belongs
 358  * \param data an opaque pointer to the data to cache
 359  * \param size the size of the data in bytes
 360  * \param destructor a pointer to a function that can destroy or release a reference to the data.
 361  */
 362
 363 void mlt_cache_put( mlt_cache cache, void *object, void* data, int size, mlt_destructor destructor )
 364 {
 365         pthread_mutex_lock( &cache->mutex );
 366         void **hit = shuffle_get_hit( cache, object );
 367         void **alt = cache->current == cache->A ? cache->B : cache->A;
 368
 369         // add the object to the cache
 370         if ( hit )
 371         {
 372                 // release the old data
 373                 cache_object_close( cache, *hit, NULL );
 374                 // the MRU end gets the updated data
 375                 hit = &alt[ cache->count - 1 ];
 376         }
 377         else if ( cache->count < cache->size )
 378         {
 379                 // more room in cache, add it to MRU end
 380                 hit = &alt[ cache->count++ ];
 381         }
 382         else
 383         {
 384                 // release the entry at the LRU end
 385                 cache_object_close( cache, cache->current[0], NULL );
 386
 387                 // The MRU end gets the new item
 388                 hit = &alt[ cache->count - 1 ];
 389         }
 390         *hit = object;
 391         mlt_log( NULL, MLT_LOG_DEBUG, "%s: put %d = %p, %p\n", __FUNCTION__, cache->count - 1, object, data );
 392
 393         // Fetch the cache item
 394         char key[19];
 395         sprintf( key, "%p", object );
 396         mlt_cache_item item = mlt_properties_get_data( cache->active, key, NULL );
 397         if ( !item )
 398         {
 399                 item = calloc( 1, sizeof( mlt_cache_item_s ) );
 400                 if ( item )
 401                         mlt_properties_set_data( cache->active, key, item, 0, free, NULL );
 402         }
 403         if ( item )
 404         {
 405                 // If updating the cache item but not all references are released
 406                 // copy the item to the garbage collection.
 407                 if ( item->refcount > 0 && item->data )
 408                 {
 409                         mlt_cache_item orphan = calloc( 1, sizeof( mlt_cache_item_s ) );
 410                         if ( orphan )
 411                         {
 412                                 mlt_log( NULL, MLT_LOG_DEBUG, "adding to garbage collection object %p data %p\n", item->object, item->data );
 413                                 *orphan = *item;
 414                                 sprintf( key, "%p", orphan->data );
 415                                 // We store in the garbage collection by data address, not the owner's!
 416                                 mlt_properties_set_data( cache->garbage, key, orphan, 0, free, NULL );
 417                         }
 418                 }
 419
 420                 // Set/update the cache item
 421                 item->cache = cache;
 422                 item->object = object;
 423                 item->data = data;
 424                 item->size = size;
 425                 item->destructor = destructor;
 426                 item->refcount = 1;
 427         }
 428
 429         // swap the current array
 430         cache->current = alt;
 431         pthread_mutex_unlock( &cache->mutex );
 432 }
 433
 434 /** Get a chunk of data from the cache.
 435  *
 436  * \public \memberof mlt_cache_s
 437  * \param cache a cache object
 438  * \param object the object for which you are trying to locate the data
 439  * \return a mlt_cache_item if found or NULL if not found or has been flushed from the cache
 440  */
 441
 442 mlt_cache_item mlt_cache_get( mlt_cache cache, void *object )
 443 {
 444         mlt_cache_item result = NULL;
 445         pthread_mutex_lock( &cache->mutex );
 446         void **hit = shuffle_get_hit( cache, object );
 447         void **alt = cache->current == cache->A ? cache->B : cache->A;
 448
 449         if ( hit )
 450         {
 451                 // copy the hit to the MRU end
 452                 alt[ cache->count - 1 ] = *hit;
 453                 hit = &alt[ cache->count - 1 ];
 454
 455                 char key[19];
 456                 sprintf( key, "%p", *hit );
 457                 result = mlt_properties_get_data( cache->active, key, NULL );
 458                 if ( result && result->data )
 459                 {
 460                         result->refcount++;
 461                         mlt_log( NULL, MLT_LOG_DEBUG, "%s: get %d = %p, %p\n", __FUNCTION__, cache->count - 1, *hit, result->data );
 462                 }
 463
 464                 // swap the current array
 465                 cache->current = alt;
 466         }
 467         pthread_mutex_unlock( &cache->mutex );
 468
 469         return result;
 470 }
 471
 472 /** Shuffle the cache entries between the two arrays and return the frame for a position.
 473  *
 474  * \private \memberof mlt_cache_s
 475  * \param cache a cache object
 476  * \param position the position of the frame that you want
 477  * \return a frame if there was a hit or NULL for a miss
 478  */
 479
 480 static mlt_frame* shuffle_get_frame( mlt_cache cache, mlt_position position )
 481 {
 482         int i = cache->count;
 483         int j = cache->count - 1;
 484         mlt_frame *hit = NULL;
 485         mlt_frame *alt = (mlt_frame*) ( cache->current == cache->A ? cache->B : cache->A );
 486
 487         if ( cache->count > 0 && cache->count < cache->size )
 488         {
 489                 // first determine if we have a hit
 490                 while ( i-- && !hit )
 491                 {
 492                         mlt_frame *o = (mlt_frame*) &cache->current[ i ];
 493                         if ( mlt_frame_original_position( *o ) == position )
 494                                 hit = o;
 495                 }
 496                 // if there was no hit, we will not be shuffling out an entry
 497                 // and are still filling the cache
 498                 if ( !hit )
 499                         ++j;
 500                 // reset these
 501                 i = cache->count;
 502                 hit = NULL;
 503         }
 504
 505         // shuffle the existing entries to the alternate array
 506         while ( i-- )
 507         {
 508                 mlt_frame *o = (mlt_frame*) &cache->current[ i ];
 509
 510                 if ( !hit && mlt_frame_original_position( *o ) == position )
 511                 {
 512                         hit = o;
 513                 }
 514                 else if ( j > 0 )
 515                 {
 516                         alt[ --j ] = *o;
 517 //                      mlt_log( NULL, MLT_LOG_DEBUG, "%s: shuffle %d = %p\n", __FUNCTION__, j, alt[j] );
 518                 }
 519         }
 520         return hit;
 521 }
 522
 523 /** Put a frame in the cache.
 524  *
 525  * Unlike mlt_cache_put() this version is more suitable for caching frames
 526  * and their data - like images. However, this version does not use reference
 527  * counting and garbage collection. Rather, frames are cloned with deep copy
 528  * to avoid those things.
 529  *
 530  * \public \memberof mlt_cache_s
 531  * \param cache a cache object
 532  * \param frame the frame to cache
 533  * \see mlt_frame_get_frame
 534  */
 535
 536 void mlt_cache_put_frame( mlt_cache cache, mlt_frame frame )
 537 {
 538         pthread_mutex_lock( &cache->mutex );
 539         mlt_frame *hit = shuffle_get_frame( cache, mlt_frame_original_position( frame ) );
 540         mlt_frame *alt = (mlt_frame*) ( cache->current == cache->A ? cache->B : cache->A );
 541
 542         // add the frame to the cache
 543         if ( hit )
 544         {
 545                 // release the old data
 546                 mlt_frame_close( *hit );
 547                 // the MRU end gets the updated data
 548                 hit = &alt[ cache->count - 1 ];
 549         }
 550         else if ( cache->count < cache->size )
 551         {
 552                 // more room in cache, add it to MRU end
 553                 hit = &alt[ cache->count++ ];
 554         }
 555         else
 556         {
 557                 // release the entry at the LRU end
 558                 mlt_frame_close( cache->current[0] );
 559
 560                 // The MRU end gets the new item
 561                 hit = &alt[ cache->count - 1 ];
 562         }
 563         *hit = mlt_frame_clone( frame, 1 );
 564         mlt_log( NULL, MLT_LOG_DEBUG, "%s: put %d = %p\n", __FUNCTION__, cache->count - 1, frame );
 565
 566         // swap the current array
 567         cache->current = (void**) alt;
 568         cache->is_frames = 1;
 569         pthread_mutex_unlock( &cache->mutex );
 570 }
 571
 572 /** Get a frame from the cache.
 573  *
 574  * You must call mlt_frame_close() on the frame you receive from this.
 575  *
 576  * \public \memberof mlt_cache_s
 577  * \param cache a cache object
 578  * \param position the position of the frame that you want
 579  * \return a frame if found or NULL if not found or has been flushed from the cache
 580  * \see mlt_frame_put_frame
 581  */
 582
 583 mlt_frame mlt_cache_get_frame( mlt_cache cache, mlt_position position )
 584 {
 585         mlt_frame result = NULL;
 586         pthread_mutex_lock( &cache->mutex );
 587         mlt_frame *hit = shuffle_get_frame( cache, position );
 588         mlt_frame *alt = (mlt_frame*) ( cache->current == cache->A ? cache->B : cache->A );
 589
 590         if ( hit )
 591         {
 592                 // copy the hit to the MRU end
 593                 alt[ cache->count - 1 ] = *hit;
 594                 hit = &alt[ cache->count - 1 ];
 595
 596                 result = mlt_frame_clone( *hit, 1 );
 597                 mlt_log( NULL, MLT_LOG_DEBUG, "%s: get %d = %p\n", __FUNCTION__, cache->count - 1, *hit );
 598
 599                 // swap the current array
 600                 cache->current = (void**) alt;
 601         }
 602         pthread_mutex_unlock( &cache->mutex );
 603
 604         return result;
 605 }