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