Improved cache management for movie clips from tomato branch

Replace pseudo-LRU approach of determining which buffer
to remove when running out of space allowed for cache
with approach which would remove the frame which is most
far away from newly added frame.

This is still a bit tricky because it's impossible to
distinguish which frame to delete in situation of:

        CCCC...CC
           ^

it's either user wants to extend left segment of cached
frames and buffers from right segment should be removed
or he wants to join this two segments and in that case
buffers from right segment should be removed.

Would need a bit more investigation which situation
is more common in general usecase.

Additional changes:

- Cleanup some memutil files (which are familiar to cache limiter)

- Add option to make moviecache verbose. If DEBUG_MESSAGES is
  defined in moviecache.c detailed logs would be printed to the
  console.

- Movie caches are now named which helps reading debug messages.

1 files changed, 107 insertions, 9 deletions

diff --git a/source/blender/imbuf/intern/moviecache.c b/source/blender/imbuf/intern/moviecache.c
index 2992e4a0aa7..e398d1c7b16 100644
--- a/source/blender/imbuf/intern/moviecache.c
+++ b/source/blender/imbuf/intern/moviecache.c
@@ -29,12 +29,15 @@
  *  \ingroup bke
  */
 
+#undef DEBUG_MESSAGES
+
 #include <stdlib.h> /* for qsort */
 #include <memory.h>
 
 #include "MEM_guardedalloc.h"
 #include "MEM_CacheLimiterC-Api.h"
 
+#include "BLI_string.h"
 #include "BLI_utildefines.h"
 #include "BLI_ghash.h"
 #include "BLI_mempool.h"
@@ -44,20 +47,37 @@
 #include "IMB_imbuf_types.h"
 #include "IMB_imbuf.h"
 
+#ifdef DEBUG_MESSAGES
+#  if defined __GNUC__ || defined __sun
+#    define PRINT(format, args ...) printf(format, ##args)
+#  else
+#    define PRINT(format, ...) printf(__VA_ARGS__)
+#  endif
+#else
+#  define PRINT(format, ...)
+#endif
+
 static MEM_CacheLimiterC *limitor = NULL;
 
 typedef struct MovieCache {
+	char name[64];
+
 	GHash *hash;
 	GHashHashFP hashfp;
 	GHashCmpFP cmpfp;
 	MovieCacheGetKeyDataFP getdatafp;
 
+	MovieCacheGetPriorityDataFP getprioritydatafp;
+	MovieCacheGetItemPriorityFP getitempriorityfp;
+	MovieCachePriorityDeleterFP prioritydeleterfp;
+
 	struct BLI_mempool *keys_pool;
 	struct BLI_mempool *items_pool;
 	struct BLI_mempool *userkeys_pool;
 
 	int keysize;
-	unsigned long curtime;
+
+	void *last_userkey;
 
 	int totseg, *points, proxy, render_flags;  /* for visual statistics optimization */
 	int pad;
@@ -72,7 +92,7 @@ typedef struct MovieCacheItem {
 	MovieCache *cache_owner;
 	ImBuf *ibuf;
 	MEM_CacheLimiterHandleC *c_handle;
-	unsigned long last_access;
+	void *priority_data;
 } MovieCacheItem;
 
 static unsigned int moviecache_hashhash(const void *keyv)
@@ -94,18 +114,27 @@ static void moviecache_keyfree(void *val)
 {
 	MovieCacheKey *key = (MovieCacheKey *)val;
 
+	BLI_mempool_free(key->cache_owner->userkeys_pool, key->userkey);
+
 	BLI_mempool_free(key->cache_owner->keys_pool, key);
 }
 
 static void moviecache_valfree(void *val)
 {
 	MovieCacheItem *item = (MovieCacheItem *)val;
+	MovieCache *cache = item->cache_owner;
+
+	PRINT("%s: cache '%s' free item %p buffer %p\n", __func__, cache->name, item, item->ibuf);
 
 	if (item->ibuf) {
 		MEM_CacheLimiter_unmanage(item->c_handle);
 		IMB_freeImBuf(item->ibuf);
 	}
 
+	if (item->priority_data && cache->prioritydeleterfp) {
+		cache->prioritydeleterfp(item->priority_data);
+	}
+
 	BLI_mempool_free(item->cache_owner->items_pool, item);
 }
 
@@ -117,10 +146,16 @@ static void check_unused_keys(MovieCache *cache)
 	while (!BLI_ghashIterator_isDone(iter)) {
 		MovieCacheKey *key = BLI_ghashIterator_getKey(iter);
 		MovieCacheItem *item = BLI_ghashIterator_getValue(iter);
+		int remove = 0;
 
 		BLI_ghashIterator_step(iter);
 
-		if (!item->ibuf)
+		remove = !item->ibuf;
+
+		if (remove)
+			PRINT("%s: cache '%s' remove item %p without buffer\n", __func__, cache->name, item);
+
+		if (remove)
 			BLI_ghash_remove(cache->hash, key, moviecache_keyfree, moviecache_valfree);
 	}
 
@@ -137,12 +172,21 @@ static int compare_int(const void *av, const void *bv)
 static void IMB_moviecache_destructor(void *p)
 {
 	MovieCacheItem *item = (MovieCacheItem *) p;
+	MovieCache *cache = item->cache_owner;
+
+	PRINT("%s: cache '%s' destroy item %p buffer %p\n", __func__, cache->name, item, item->ibuf);
 
 	if (item && item->ibuf) {
 		IMB_freeImBuf(item->ibuf);
 
 		item->ibuf = NULL;
 		item->c_handle = NULL;
+
+		/* force cached segments to be updated */
+		if (cache->points) {
+			MEM_freeN(cache->points);
+			cache->points = NULL;
+		}
 	}
 }
 
@@ -187,9 +231,30 @@ static size_t get_item_size(void *p)
 	return size;
 }
 
+static int get_item_priority(void *item_v, int default_priority)
+{
+	MovieCacheItem *item = (MovieCacheItem *) item_v;
+	MovieCache *cache = item->cache_owner;
+	int priority;
+
+	if (!cache->getitempriorityfp) {
+		PRINT("%s: cache '%s' item %p use default priority %d\n", __func__, cache-> name, item, default_priority);
+
+		return default_priority;
+	}
+
+	priority = cache->getitempriorityfp(cache->last_userkey, item->priority_data);
+
+	PRINT("%s: cache '%s' item %p priority %d\n", __func__, cache-> name, item, priority);
+
+	return priority;
+}
+
 void IMB_moviecache_init(void)
 {
 	limitor = new_MEM_CacheLimiter(IMB_moviecache_destructor, get_item_size);
+
+	MEM_CacheLimiter_ItemPriority_Func_set(limitor, get_item_priority);
 }
 
 void IMB_moviecache_destruct(void)
@@ -198,12 +263,16 @@ void IMB_moviecache_destruct(void)
 		delete_MEM_CacheLimiter(limitor);
 }
 
-MovieCache *IMB_moviecache_create(int keysize, GHashHashFP hashfp, GHashCmpFP cmpfp,
-                                  MovieCacheGetKeyDataFP getdatafp)
+MovieCache *IMB_moviecache_create(const char *name, int keysize, GHashHashFP hashfp, GHashCmpFP cmpfp)
 {
 	MovieCache *cache;
 
+	PRINT("%s: cache '%s' create\n", __func__, name);
+
 	cache = MEM_callocN(sizeof(MovieCache), "MovieCache");
+
+	BLI_strncpy(cache->name, name, sizeof(cache->name));
+
 	cache->keys_pool = BLI_mempool_create(sizeof(MovieCacheKey), 64, 64, 0);
 	cache->items_pool = BLI_mempool_create(sizeof(MovieCacheItem), 64, 64, 0);
 	cache->userkeys_pool = BLI_mempool_create(keysize, 64, 64, 0);
@@ -212,12 +281,27 @@ MovieCache *IMB_moviecache_create(int keysize, GHashHashFP hashfp, GHashCmpFP cm
 	cache->keysize = keysize;
 	cache->hashfp = hashfp;
 	cache->cmpfp = cmpfp;
-	cache->getdatafp = getdatafp;
 	cache->proxy = -1;
 
 	return cache;
 }
 
+void IMB_moviecache_set_getdata_callback(MovieCache *cache, MovieCacheGetKeyDataFP getdatafp)
+{
+	cache->getdatafp = getdatafp;
+}
+
+void IMB_moviecache_set_priority_callback(struct MovieCache *cache, MovieCacheGetPriorityDataFP getprioritydatafp,
+                                          MovieCacheGetItemPriorityFP getitempriorityfp,
+                                          MovieCachePriorityDeleterFP prioritydeleterfp)
+{
+	cache->last_userkey = MEM_mallocN(cache->keysize, "movie cache last user key");
+
+	cache->getprioritydatafp = getprioritydatafp;
+	cache->getitempriorityfp = getitempriorityfp;
+	cache->prioritydeleterfp = prioritydeleterfp;
+}
+
 void IMB_moviecache_put(MovieCache *cache, void *userkey, ImBuf *ibuf)
 {
 	MovieCacheKey *key;
@@ -234,16 +318,27 @@ void IMB_moviecache_put(MovieCache *cache, void *userkey, ImBuf *ibuf)
 	memcpy(key->userkey, userkey, cache->keysize);
 
 	item = BLI_mempool_alloc(cache->items_pool);
+
+	PRINT("%s: cache '%s' put %p, item %p\n", __func__, cache-> name, ibuf, item);
+
 	item->ibuf = ibuf;
 	item->cache_owner = cache;
-	item->last_access = cache->curtime++;
 	item->c_handle = NULL;
+	item->priority_data = NULL;
+
+	if (cache->getprioritydatafp) {
+		item->priority_data = cache->getprioritydatafp(userkey);
+	}
 
 	BLI_ghash_remove(cache->hash, key, moviecache_keyfree, moviecache_valfree);
 	BLI_ghash_insert(cache->hash, key, item);
 
 	item->c_handle = MEM_CacheLimiter_insert(limitor, item);
 
+	if (cache->last_userkey) {
+		memcpy(cache->last_userkey, userkey, cache->keysize);
+	}
+
 	MEM_CacheLimiter_ref(item->c_handle);
 	MEM_CacheLimiter_enforce_limits(limitor);
 	MEM_CacheLimiter_unref(item->c_handle);
@@ -267,8 +362,6 @@ ImBuf *IMB_moviecache_get(MovieCache *cache, void *userkey)
 	item = (MovieCacheItem *)BLI_ghash_lookup(cache->hash, &key);
 
 	if (item) {
-		item->last_access = cache->curtime++;
-
 		if (item->ibuf) {
 			MEM_CacheLimiter_touch(item->c_handle);
 			IMB_refImBuf(item->ibuf);
@@ -282,6 +375,8 @@ ImBuf *IMB_moviecache_get(MovieCache *cache, void *userkey)
 
 void IMB_moviecache_free(MovieCache *cache)
 {
+	PRINT("%s: create '%s' free\n", __func__, cache->name);
+
 	BLI_ghash_free(cache->hash, moviecache_keyfree, moviecache_valfree);
 
 	BLI_mempool_destroy(cache->keys_pool);
@@ -291,6 +386,9 @@ void IMB_moviecache_free(MovieCache *cache)
 	if (cache->points)
 		MEM_freeN(cache->points);
 
+	if (cache->last_userkey)
+		MEM_freeN(cache->last_userkey);
+
 	MEM_freeN(cache);
 }