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 (10)
  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         void* *current;        /**< pointer to the current array of pointers */
  87         void* A[ MAX_CACHE_SIZE ];
  88         void* B[ MAX_CACHE_SIZE ];
  89         pthread_mutex_t mutex; /**< a mutex to prevent multi-threaded race conditions */
  90         mlt_properties active; /**< a list of cache items some of which may no longer
  91                                     be in \p current but to which there are
  92                                     outstanding references */
  93         mlt_properties garbage;/**< a list cache items pending release. A cache item
  94                                     is copied to this list when it is updated but there
  95                                     are outstanding references to the old data object. */
  96 };
  97
  98 /** Get the data pointer from the cache item.
  99  *
 100  * \public \memberof mlt_cache_s
 101  * \param item a cache item
 102  * \param[out] size the number of bytes pointed at, if supplied when putting the data into the cache
 103  * \return the data pointer
 104  */
 105
 106 void *mlt_cache_item_data( mlt_cache_item item, int *size )
 107 {
 108         if ( size && item )
 109                 *size = item->size;
 110         return item? item->data : NULL;
 111 }
 112
 113 /** Close a cache item given its parent object pointer.
 114  *
 115  * \private \memberof mlt_cache_s
 116  * \param cache a cache
 117  * \param object the object to which the data object belongs
 118  * \param data the data object, which might be in the garbage list (optional)
 119  */
 120
 121 static void cache_object_close( mlt_cache cache, void *object, void* data )
 122 {
 123         char key[19];
 124
 125         // Fetch the cache item from the active list by its owner's address
 126         sprintf( key, "%p", object );
 127         mlt_cache_item item = mlt_properties_get_data( cache->active, key, NULL );
 128         if ( item )
 129         {
 130                 mlt_log( NULL, MLT_LOG_DEBUG, "%s: item %p object %p data %p refcount %d\n", __FUNCTION__,
 131                         item, item->object, item->data, item->refcount );
 132                 if ( item->destructor && --item->refcount <= 0 )
 133                 {
 134                         // Destroy the data object
 135                         item->destructor( item->data );
 136                         item->data = NULL;
 137                         item->destructor = NULL;
 138                         // Do not dispose of the cache item because it could likely be used
 139                         // again.
 140                 }
 141         }
 142
 143         // Fetch the cache item from the garbage collection by its data address
 144         if ( data )
 145         {
 146                 sprintf( key, "%p", data );
 147                 item = mlt_properties_get_data( cache->garbage, key, NULL );
 148                 if ( item )
 149                 {
 150                         mlt_log( NULL, MLT_LOG_DEBUG, "collecting garbage item %p object %p data %p refcount %d\n",
 151                                 item, item->object, item->data, item->refcount );
 152                         if ( item->destructor && --item->refcount <= 0 )
 153                         {
 154                                 item->destructor( item->data );
 155                                 item->data = NULL;
 156                                 item->destructor = NULL;
 157                                 // We do not need the garbage-collected cache item
 158                                 mlt_properties_set_data( cache->garbage, key, NULL, 0, NULL, NULL );
 159                         }
 160                 }
 161         }
 162 }
 163
 164 /** Close a cache item.
 165  *
 166  * Release a reference and call the destructor on the data object when all
 167  * references are released.
 168  *
 169  * \public \memberof mlt_cache_item_s
 170  * \param item a cache item
 171  */
 172
 173 void mlt_cache_item_close( mlt_cache_item item )
 174 {
 175         if ( item )
 176         {
 177                 pthread_mutex_lock( &item->cache->mutex );
 178                 cache_object_close( item->cache, item->object, item->data );
 179                 pthread_mutex_unlock( &item->cache->mutex );
 180         }
 181 }
 182
 183 /** Create a new cache.
 184  *
 185  * The default size is \p DEFAULT_CACHE_SIZE.
 186  * \public \memberof mlt_cache_s
 187  * \return a new cache or NULL if there was an error
 188  */
 189
 190 mlt_cache mlt_cache_init()
 191 {
 192         mlt_cache result = calloc( 1, sizeof( struct mlt_cache_s ) );
 193         if ( result )
 194         {
 195                 result->size = DEFAULT_CACHE_SIZE;
 196                 result->current = result->A;
 197                 pthread_mutex_init( &result->mutex, NULL );
 198                 result->active = mlt_properties_new();
 199                 result->garbage = mlt_properties_new();
 200         }
 201         return result;
 202 }
 203
 204 /** Set the numer of items to cache.
 205  *
 206  * This must be called before using the cache. The size can not be more
 207  * than \p MAX_CACHE_SIZE.
 208  * \public \memberof mlt_cache_s
 209  * \param cache the cache to adjust
 210  * \param size the new size of the cache
 211  */
 212
 213 void mlt_cache_set_size( mlt_cache cache, int size )
 214 {
 215         if ( size <= MAX_CACHE_SIZE )
 216                 cache->size = size;
 217 }
 218
 219 /** Get the numer of possible cache items.
 220  *
 221  * \public \memberof mlt_cache_s
 222  * \param cache the cache to check
 223  * \return the current maximum size of the cache
 224  */
 225
 226 int mlt_cache_get_size( mlt_cache cache )
 227 {
 228     return cache->size;
 229 }
 230
 231 /** Destroy a cache.
 232  *
 233  * \public \memberof mlt_cache_s
 234  * \param cache the cache to destroy
 235  */
 236
 237 void mlt_cache_close( mlt_cache cache )
 238 {
 239         if ( cache )
 240         {
 241                 while ( cache->count-- )
 242                 {
 243                         void *object = cache->current[ cache->count ];
 244                         mlt_log( NULL, MLT_LOG_DEBUG, "%s: %d = %p\n", __FUNCTION__, cache->count, object );
 245                         cache_object_close( cache, object, NULL );
 246                 }
 247                 mlt_properties_close( cache->active );
 248                 mlt_properties_close( cache->garbage );
 249                 pthread_mutex_destroy( &cache->mutex );
 250                 free( cache );
 251         }
 252 }
 253
 254 /** Remove cache entries for an object.
 255  *
 256  * \public \memberof mlt_cache_s
 257  * \param cache a cache
 258  * \param object the object that owns the cached data
 259  */
 260
 261 void mlt_cache_purge( mlt_cache cache, void *object )
 262 {
 263         if (!cache) return;
 264         pthread_mutex_lock( &cache->mutex );
 265         if ( cache && object )
 266         {
 267                 int i, j;
 268                 void **alt = cache->current == cache->A ? cache->B : cache->A;
 269
 270                 for ( i = 0, j = 0; i < cache->count; i++ )
 271                 {
 272                         void *o = cache->current[ i ];
 273
 274                         if ( o == object )
 275                         {
 276                                 cache_object_close( cache, o, NULL );
 277                         }
 278                         else
 279                         {
 280                                 alt[ j++ ] = o;
 281                         }
 282                 }
 283                 cache->count = j;
 284                 cache->current = alt;
 285         }
 286         pthread_mutex_unlock( &cache->mutex );
 287 }
 288
 289 /** Shuffle the cache entries between the two arrays and return the cache entry for an object.
 290  *
 291  * \private \memberof mlt_cache_s
 292  * \param cache a cache object
 293  * \param object the object that owns the cached data
 294  * \return a cache entry if there was a hit or NULL for a miss
 295  */
 296
 297 static void** shuffle_get_hit( mlt_cache cache, void *object )
 298 {
 299         int i = cache->count;
 300         int j = cache->count - 1;
 301         void **hit = NULL;
 302         void **alt = cache->current == cache->A ? cache->B : cache->A;
 303
 304         if ( cache->count > 0 && cache->count < cache->size )
 305         {
 306                 // first determine if we have a hit
 307                 while ( i-- && !hit )
 308                 {
 309                         void **o = &cache->current[ i ];
 310                         if ( *o == object )
 311                                 hit = o;
 312                 }
 313                 // if there was no hit, we will not be shuffling out an entry
 314                 // and are still filling the cache
 315                 if ( !hit )
 316                         ++j;
 317                 // reset these
 318                 i = cache->count;
 319                 hit = NULL;
 320         }
 321
 322         // shuffle the existing entries to the alternate array
 323         while ( i-- )
 324         {
 325                 void **o = &cache->current[ i ];
 326
 327                 if ( !hit && *o == object )
 328                 {
 329                         hit = o;
 330                 }
 331                 else if ( j > 0 )
 332                 {
 333                         alt[ --j ] = *o;
 334 //                      mlt_log( NULL, MLT_LOG_DEBUG, "%s: shuffle %d = %p\n", __FUNCTION__, j, alt[j] );
 335                 }
 336         }
 337         return hit;
 338 }
 339
 340 /** Put a chunk of data in the cache.
 341  *
 342  * This function and mlt_cache_get() are not scalable with a large volume
 343  * of unique \p object paramter values. Therefore, it does not make sense
 344  * to use it for a frame/image cache using the frame position for \p object.
 345  * Instead, use mlt_cache_put_frame() for that.
 346  *
 347  * \public \memberof mlt_cache_s
 348  * \param cache a cache object
 349  * \param object the object to which this data belongs
 350  * \param data an opaque pointer to the data to cache
 351  * \param size the size of the data in bytes
 352  * \param destructor a pointer to a function that can destroy or release a reference to the data.
 353  */
 354
 355 void mlt_cache_put( mlt_cache cache, void *object, void* data, int size, mlt_destructor destructor )
 356 {
 357         pthread_mutex_lock( &cache->mutex );
 358         void **hit = shuffle_get_hit( cache, object );
 359         void **alt = cache->current == cache->A ? cache->B : cache->A;
 360
 361         // add the object to the cache
 362         if ( hit )
 363         {
 364                 // release the old data
 365                 cache_object_close( cache, *hit, NULL );
 366                 // the MRU end gets the updated data
 367                 hit = &alt[ cache->count - 1 ];
 368         }
 369         else if ( cache->count < cache->size )
 370         {
 371                 // more room in cache, add it to MRU end
 372                 hit = &alt[ cache->count++ ];
 373         }
 374         else
 375         {
 376                 // release the entry at the LRU end
 377                 cache_object_close( cache, cache->current[0], NULL );
 378
 379                 // The MRU end gets the new item
 380                 hit = &alt[ cache->count - 1 ];
 381         }
 382         *hit = object;
 383         mlt_log( NULL, MLT_LOG_DEBUG, "%s: put %d = %p, %p\n", __FUNCTION__, cache->count - 1, object, data );
 384
 385         // Fetch the cache item
 386         char key[19];
 387         sprintf( key, "%p", object );
 388         mlt_cache_item item = mlt_properties_get_data( cache->active, key, NULL );
 389         if ( !item )
 390         {
 391                 item = calloc( 1, sizeof( mlt_cache_item_s ) );
 392                 if ( item )
 393                         mlt_properties_set_data( cache->active, key, item, 0, free, NULL );
 394         }
 395         if ( item )
 396         {
 397                 // If updating the cache item but not all references are released
 398                 // copy the item to the garbage collection.
 399                 if ( item->refcount > 0 && item->data )
 400                 {
 401                         mlt_cache_item orphan = calloc( 1, sizeof( mlt_cache_item_s ) );
 402                         if ( orphan )
 403                         {
 404                                 mlt_log( NULL, MLT_LOG_DEBUG, "adding to garbage collection object %p data %p\n", item->object, item->data );
 405                                 *orphan = *item;
 406                                 sprintf( key, "%p", orphan->data );
 407                                 // We store in the garbage collection by data address, not the owner's!
 408                                 mlt_properties_set_data( cache->garbage, key, orphan, 0, free, NULL );
 409                         }
 410                 }
 411
 412                 // Set/update the cache item
 413                 item->cache = cache;
 414                 item->object = object;
 415                 item->data = data;
 416                 item->size = size;
 417                 item->destructor = destructor;
 418                 item->refcount = 1;
 419         }
 420
 421         // swap the current array
 422         cache->current = alt;
 423         pthread_mutex_unlock( &cache->mutex );
 424 }
 425
 426 /** Get a chunk of data from the cache.
 427  *
 428  * \public \memberof mlt_cache_s
 429  * \param cache a cache object
 430  * \param object the object for which you are trying to locate the data
 431  * \return a mlt_cache_item if found or NULL if not found or has been flushed from the cache
 432  */
 433
 434 mlt_cache_item mlt_cache_get( mlt_cache cache, void *object )
 435 {
 436         mlt_cache_item result = NULL;
 437         pthread_mutex_lock( &cache->mutex );
 438         void **hit = shuffle_get_hit( cache, object );
 439         void **alt = cache->current == cache->A ? cache->B : cache->A;
 440
 441         if ( hit )
 442         {
 443                 // copy the hit to the MRU end
 444                 alt[ cache->count - 1 ] = *hit;
 445                 hit = &alt[ cache->count - 1 ];
 446
 447                 char key[19];
 448                 sprintf( key, "%p", *hit );
 449                 result = mlt_properties_get_data( cache->active, key, NULL );
 450                 if ( result && result->data )
 451                 {
 452                         result->refcount++;
 453                         mlt_log( NULL, MLT_LOG_DEBUG, "%s: get %d = %p, %p\n", __FUNCTION__, cache->count - 1, *hit, result->data );
 454                 }
 455
 456                 // swap the current array
 457                 cache->current = alt;
 458         }
 459         pthread_mutex_unlock( &cache->mutex );
 460
 461         return result;
 462 }
 463
 464 /** Shuffle the cache entries between the two arrays and return the frame for a position.
 465  *
 466  * \private \memberof mlt_cache_s
 467  * \param cache a cache object
 468  * \param position the position of the frame that you want
 469  * \return a frame if there was a hit or NULL for a miss
 470  */
 471
 472 static mlt_frame* shuffle_get_frame( mlt_cache cache, mlt_position position )
 473 {
 474         int i = cache->count;
 475         int j = cache->count - 1;
 476         mlt_frame *hit = NULL;
 477         mlt_frame *alt = (mlt_frame*) ( cache->current == cache->A ? cache->B : cache->A );
 478
 479         if ( cache->count > 0 && cache->count < cache->size )
 480         {
 481                 // first determine if we have a hit
 482                 while ( i-- && !hit )
 483                 {
 484                         mlt_frame *o = (mlt_frame*) &cache->current[ i ];
 485                         if ( mlt_frame_get_position( *o ) == position )
 486                                 hit = o;
 487                 }
 488                 // if there was no hit, we will not be shuffling out an entry
 489                 // and are still filling the cache
 490                 if ( !hit )
 491                         ++j;
 492                 // reset these
 493                 i = cache->count;
 494                 hit = NULL;
 495         }
 496
 497         // shuffle the existing entries to the alternate array
 498         while ( i-- )
 499         {
 500                 mlt_frame *o = (mlt_frame*) &cache->current[ i ];
 501
 502                 if ( !hit && mlt_frame_get_position( *o ) == position )
 503                 {
 504                         hit = o;
 505                 }
 506                 else if ( j > 0 )
 507                 {
 508                         alt[ --j ] = *o;
 509 //                      mlt_log( NULL, MLT_LOG_DEBUG, "%s: shuffle %d = %p\n", __FUNCTION__, j, alt[j] );
 510                 }
 511         }
 512         return hit;
 513 }
 514
 515 /** Put a frame in the cache.
 516  *
 517  * Unlike mlt_cache_put() this version is more suitable for caching frames
 518  * and their data - like images. However, this version does not use reference
 519  * counting and garbage collection. Rather, frames are cloned with deep copy
 520  * to avoid those things.
 521  *
 522  * \public \memberof mlt_cache_s
 523  * \param cache a cache object
 524  * \param frame the frame to cache
 525  * \see mlt_frame_get_frame
 526  */
 527
 528 void mlt_cache_put_frame( mlt_cache cache, mlt_frame frame )
 529 {
 530         pthread_mutex_lock( &cache->mutex );
 531         mlt_frame *hit = shuffle_get_frame( cache, mlt_frame_get_position( frame ) );
 532         mlt_frame *alt = (mlt_frame*) ( cache->current == cache->A ? cache->B : cache->A );
 533
 534         // add the frame to the cache
 535         if ( hit )
 536         {
 537                 // release the old data
 538                 mlt_frame_close( *hit );
 539                 // the MRU end gets the updated data
 540                 hit = &alt[ cache->count - 1 ];
 541         }
 542         else if ( cache->count < cache->size )
 543         {
 544                 // more room in cache, add it to MRU end
 545                 hit = &alt[ cache->count++ ];
 546         }
 547         else
 548         {
 549                 // release the entry at the LRU end
 550                 mlt_frame_close( cache->current[0] );
 551
 552                 // The MRU end gets the new item
 553                 hit = &alt[ cache->count - 1 ];
 554         }
 555         *hit = mlt_frame_clone( frame, 1 );
 556         mlt_log( NULL, MLT_LOG_DEBUG, "%s: put %d = %p\n", __FUNCTION__, cache->count - 1, frame );
 557
 558         // swap the current array
 559         cache->current = (void**) alt;
 560         pthread_mutex_unlock( &cache->mutex );
 561 }
 562
 563 /** Get a frame from the cache.
 564  *
 565  * You must call mlt_frame_close() on the frame you receive from this.
 566  *
 567  * \public \memberof mlt_cache_s
 568  * \param cache a cache object
 569  * \param position the position of the frame that you want
 570  * \return a frame if found or NULL if not found or has been flushed from the cache
 571  * \see mlt_frame_put_frame
 572  */
 573
 574 mlt_frame mlt_cache_get_frame( mlt_cache cache, mlt_position position )
 575 {
 576         mlt_frame result = NULL;
 577         pthread_mutex_lock( &cache->mutex );
 578         mlt_frame *hit = shuffle_get_frame( cache, position );
 579         mlt_frame *alt = (mlt_frame*) ( cache->current == cache->A ? cache->B : cache->A );
 580
 581         if ( hit )
 582         {
 583                 // copy the hit to the MRU end
 584                 alt[ cache->count - 1 ] = *hit;
 585                 hit = &alt[ cache->count - 1 ];
 586
 587                 result = mlt_frame_clone( *hit, 1 );
 588                 mlt_log( NULL, MLT_LOG_DEBUG, "%s: get %d = %p\n", __FUNCTION__, cache->count - 1, *hit );
 589
 590                 // swap the current array
 591                 cache->current = (void**) alt;
 592         }
 593         pthread_mutex_unlock( &cache->mutex );
 594
 595         return result;
 596 }