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.

4 files changed, 161 insertions, 16 deletions

diff --git a/source/blender/blenkernel/intern/movieclip.c b/source/blender/blenkernel/intern/movieclip.c
index 2d83a748767..de367b6b4d0 100644
--- a/source/blender/blenkernel/intern/movieclip.c
+++ b/source/blender/blenkernel/intern/movieclip.c
@@ -340,6 +340,10 @@ typedef struct MovieClipImBufCacheKey {
 	short render_flag;
 } MovieClipImBufCacheKey;
 
+typedef struct MovieClipCachePriorityData {
+	int framenr;
+} MovieClipCachePriorityData;
+
 static void moviecache_keydata(void *userkey, int *framenr, int *proxy, int *render_flags)
 {
 	MovieClipImBufCacheKey *key = (MovieClipImBufCacheKey *)userkey;
@@ -380,6 +384,32 @@ static int moviecache_hashcmp(const void *av, const void *bv)
 	return 0;
 }
 
+void *moviecache_getprioritydata(void *key_v)
+{
+	MovieClipImBufCacheKey *key = (MovieClipImBufCacheKey *) key_v;
+	MovieClipCachePriorityData *priority_data;
+
+	priority_data = MEM_callocN(sizeof(priority_data), "movie cache clip priority data");
+	priority_data->framenr = key->framenr;
+
+	return priority_data;
+}
+
+int moviecache_getitempriority(void *last_userkey_v, void *priority_data_v)
+{
+	MovieClipImBufCacheKey *last_userkey = (MovieClipImBufCacheKey *) last_userkey_v;
+	MovieClipCachePriorityData *priority_data = (MovieClipCachePriorityData *) priority_data_v;
+
+	return -abs(last_userkey->framenr - priority_data->framenr);
+}
+
+void moviecache_prioritydeleter(void *priority_data_v)
+{
+	MovieClipCachePriorityData *priority_data = (MovieClipCachePriorityData *) priority_data_v;
+
+	MEM_freeN(priority_data);
+}
+
 static ImBuf *get_imbuf_cache(MovieClip *clip, MovieClipUser *user, int flag)
 {
 	if (clip->cache) {
@@ -407,10 +437,20 @@ static void put_imbuf_cache(MovieClip *clip, MovieClipUser *user, ImBuf *ibuf, i
 	MovieClipImBufCacheKey key;
 
 	if (!clip->cache) {
+		struct MovieCache *moviecache;
+
+		// char cache_name[64];
+		// BLI_snprintf(cache_name, sizeof(cache_name), "movie %s", clip->id.name);
+
 		clip->cache = MEM_callocN(sizeof(MovieClipCache), "movieClipCache");
 
-		clip->cache->moviecache = IMB_moviecache_create(sizeof(MovieClipImBufCacheKey), moviecache_hashhash,
-		                                                moviecache_hashcmp, moviecache_keydata);
+		moviecache = IMB_moviecache_create("movieclip", sizeof(MovieClipImBufCacheKey), moviecache_hashhash, moviecache_hashcmp);
+
+		IMB_moviecache_set_getdata_callback(moviecache, moviecache_keydata);
+		IMB_moviecache_set_priority_callback(moviecache, moviecache_getprioritydata, moviecache_getitempriority,
+		                                     moviecache_prioritydeleter);
+
+		clip->cache->moviecache = moviecache;
 	}
 
 	key.framenr = user->framenr;
diff --git a/source/blender/blenkernel/intern/seqcache.c b/source/blender/blenkernel/intern/seqcache.c
index 582034ae623..0d91dcb7faa 100644
--- a/source/blender/blenkernel/intern/seqcache.c
+++ b/source/blender/blenkernel/intern/seqcache.c
@@ -98,8 +98,7 @@ void seq_stripelem_cache_cleanup(void)
 {
 	if (moviecache) {
 		IMB_moviecache_free(moviecache);
-		moviecache = IMB_moviecache_create(sizeof(SeqCacheKey), seqcache_hashhash,
-		                                   seqcache_hashcmp, NULL);
+		moviecache = IMB_moviecache_create("seqcache", sizeof(SeqCacheKey), seqcache_hashhash, seqcache_hashcmp);
 	}
 }
 
@@ -133,8 +132,7 @@ void seq_stripelem_cache_put(
 	}
 
 	if (!moviecache) {
-		moviecache = IMB_moviecache_create(sizeof(SeqCacheKey), seqcache_hashhash,
-		                                   seqcache_hashcmp, NULL);
+		moviecache = IMB_moviecache_create("seqcache", sizeof(SeqCacheKey), seqcache_hashhash, seqcache_hashcmp);
 	}
 
 	key.seq = seq;
diff --git a/source/blender/imbuf/IMB_moviecache.h b/source/blender/imbuf/IMB_moviecache.h
index f6927d4f31d..d1d34a01433 100644
--- a/source/blender/imbuf/IMB_moviecache.h
+++ b/source/blender/imbuf/IMB_moviecache.h
@@ -44,10 +44,19 @@ struct MovieCache;
 
 typedef void (*MovieCacheGetKeyDataFP) (void *userkey, int *framenr, int *proxy, int *render_flags);
 
+typedef void  *(*MovieCacheGetPriorityDataFP) (void *userkey);
+typedef int    (*MovieCacheGetItemPriorityFP) (void *last_userkey, void *priority_data);
+typedef void   (*MovieCachePriorityDeleterFP) (void *priority_data);
+
 void IMB_moviecache_init(void);
 void IMB_moviecache_destruct(void);
 
-struct MovieCache *IMB_moviecache_create(int keysize, GHashHashFP hashfp, GHashCmpFP cmpfp, MovieCacheGetKeyDataFP getdatafp);
+struct MovieCache *IMB_moviecache_create(const char *name, int keysize, GHashHashFP hashfp, GHashCmpFP cmpfp);
+void IMB_moviecache_set_getdata_callback(struct MovieCache *cache, MovieCacheGetKeyDataFP getdatafp);
+void IMB_moviecache_set_priority_callback(struct MovieCache *cache, MovieCacheGetPriorityDataFP getprioritydatafp,
+                                          MovieCacheGetItemPriorityFP getitempriorityfp,
+                                          MovieCachePriorityDeleterFP prioritydeleterfp);
+
 void IMB_moviecache_put(struct MovieCache *cache, void *userkey, struct ImBuf *ibuf);
 struct ImBuf* IMB_moviecache_get(struct MovieCache *cache, void *userkey);
 void IMB_moviecache_free(struct MovieCache *cache);
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);
 }