VSE: Don't store `cfra` in cache
[blender.git] / source / blender / blenkernel / intern / seqcache.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  *
16  * Peter Schlaile <peter [at] schlaile [dot] de> 2010
17  */
18
19 /** \file
20  * \ingroup bke
21  */
22
23 #include <stddef.h>
24 #include <memory.h>
25
26 #include "MEM_guardedalloc.h"
27
28 #include "DNA_sequence_types.h"
29 #include "DNA_scene_types.h"
30
31 #include "IMB_imbuf.h"
32 #include "IMB_imbuf_types.h"
33
34 #include "BLI_mempool.h"
35 #include "BLI_threads.h"
36 #include "BLI_listbase.h"
37 #include "BLI_ghash.h"
38
39 #include "BKE_sequencer.h"
40 #include "BKE_scene.h"
41 #include "BKE_main.h"
42
43 /* ***************************** Sequencer cache design notes ******************************
44  *
45  * Cache key members:
46  * is_temp_cache - this cache entry will be freed before rendering next frame
47  * creator_id - ID of thread that created entry
48  * cost - In short: render time divided by playback frame rate
49  * link_prev/next - link to another entry created during rendering of the frame
50  *
51  * Linking: We use links to reduce number of iterations needed to manage cache.
52  * Entries are linked in order as they are put into cache.
53  * Only pernament (is_temp_cache = 0) cache entries are linked.
54  * Putting SEQ_CACHE_STORE_FINAL_OUT will reset linking
55  *
56  * Function:
57  * All images created during rendering are added to cache, even if the cache is already full.
58  * This is because:
59  *  - one image may be needed multiple times during rendering.
60  *  - keeping the last rendered frame allows us for faster re-render when user edits strip in stack
61  *  - we can decide if we keep frame only when it's completely rendered. Otherwise we risk having
62  *    "holes" in the cache, which can be annoying
63  * If the cache is full all entries for pending frame will have is_temp_cache set.
64  *
65  * Only entire frame can be freed to release resources for new entries (recycling).
66  * Once again, this is to reduce number of iterations, but also more controllable than removing
67  * entries one by one in reverse order to their creation.
68  *
69  * User can exclude caching of some images. Such entries will have is_temp_cache set.
70  */
71
72 typedef struct SeqCache {
73   struct GHash *hash;
74   ThreadMutex iterator_mutex;
75   struct BLI_mempool *keys_pool;
76   struct BLI_mempool *items_pool;
77   struct SeqCacheKey *last_key;
78   size_t memory_used;
79 } SeqCache;
80
81 typedef struct SeqCacheItem {
82   struct SeqCache *cache_owner;
83   struct ImBuf *ibuf;
84 } SeqCacheItem;
85
86 typedef struct SeqCacheKey {
87   struct SeqCache *cache_owner;
88   void *userkey;
89   struct SeqCacheKey *link_prev; /* Used for linking intermediate items to final frame */
90   struct SeqCacheKey *link_next; /* Used for linking intermediate items to final frame */
91   struct Sequence *seq;
92   SeqRenderData context;
93   float nfra;
94   float cost;
95   bool is_temp_cache;
96   short creator_id;
97   int type;
98 } SeqCacheKey;
99
100 static ThreadMutex cache_create_lock = BLI_MUTEX_INITIALIZER;
101
102 static bool seq_cmp_render_data(const SeqRenderData *a, const SeqRenderData *b)
103 {
104   return ((a->preview_render_size != b->preview_render_size) || (a->rectx != b->rectx) ||
105           (a->recty != b->recty) || (a->bmain != b->bmain) || (a->scene != b->scene) ||
106           (a->motion_blur_shutter != b->motion_blur_shutter) ||
107           (a->motion_blur_samples != b->motion_blur_samples) ||
108           (a->scene->r.views_format != b->scene->r.views_format) || (a->view_id != b->view_id));
109 }
110
111 static unsigned int seq_hash_render_data(const SeqRenderData *a)
112 {
113   unsigned int rval = a->rectx + a->recty;
114
115   rval ^= a->preview_render_size;
116   rval ^= ((intptr_t)a->bmain) << 6;
117   rval ^= ((intptr_t)a->scene) << 6;
118   rval ^= (int)(a->motion_blur_shutter * 100.0f) << 10;
119   rval ^= a->motion_blur_samples << 16;
120   rval ^= ((a->scene->r.views_format * 2) + a->view_id) << 24;
121
122   return rval;
123 }
124
125 static unsigned int seq_cache_hashhash(const void *key_)
126 {
127   const SeqCacheKey *key = key_;
128   unsigned int rval = seq_hash_render_data(&key->context);
129
130   rval ^= *(const unsigned int *)&key->nfra;
131   rval += key->type;
132   rval ^= ((intptr_t)key->seq) << 6;
133
134   return rval;
135 }
136
137 static bool seq_cache_hashcmp(const void *a_, const void *b_)
138 {
139   const SeqCacheKey *a = a_;
140   const SeqCacheKey *b = b_;
141
142   return ((a->seq != b->seq) || (a->nfra != b->nfra) || (a->type != b->type) ||
143           seq_cmp_render_data(&a->context, &b->context));
144 }
145
146 static SeqCache *seq_cache_get_from_scene(Scene *scene)
147 {
148   if (scene && scene->ed && scene->ed->cache) {
149     return scene->ed->cache;
150   }
151
152   return NULL;
153 }
154
155 static void seq_cache_lock(Scene *scene)
156 {
157   SeqCache *cache = seq_cache_get_from_scene(scene);
158
159   if (cache) {
160     BLI_mutex_lock(&cache->iterator_mutex);
161   }
162 }
163
164 static void seq_cache_unlock(Scene *scene)
165 {
166   SeqCache *cache = seq_cache_get_from_scene(scene);
167
168   if (cache) {
169     BLI_mutex_unlock(&cache->iterator_mutex);
170   }
171 }
172
173 static void seq_cache_keyfree(void *val)
174 {
175   SeqCacheKey *key = val;
176   BLI_mempool_free(key->cache_owner->keys_pool, key);
177 }
178
179 static void seq_cache_valfree(void *val)
180 {
181   SeqCacheItem *item = (SeqCacheItem *)val;
182   SeqCache *cache = item->cache_owner;
183
184   if (item->ibuf) {
185     cache->memory_used -= IMB_get_size_in_memory(item->ibuf);
186     IMB_freeImBuf(item->ibuf);
187   }
188
189   BLI_mempool_free(item->cache_owner->items_pool, item);
190 }
191
192 static void seq_cache_put(SeqCache *cache, SeqCacheKey *key, ImBuf *ibuf)
193 {
194   SeqCacheItem *item;
195   item = BLI_mempool_alloc(cache->items_pool);
196   item->cache_owner = cache;
197   item->ibuf = ibuf;
198
199   if (BLI_ghash_reinsert(cache->hash, key, item, seq_cache_keyfree, seq_cache_valfree)) {
200     IMB_refImBuf(ibuf);
201     cache->last_key = key;
202     cache->memory_used += IMB_get_size_in_memory(ibuf);
203   }
204 }
205
206 static ImBuf *seq_cache_get(SeqCache *cache, void *key)
207 {
208   SeqCacheItem *item = BLI_ghash_lookup(cache->hash, key);
209
210   if (item && item->ibuf) {
211     IMB_refImBuf(item->ibuf);
212
213     return item->ibuf;
214   }
215
216   return NULL;
217 }
218
219 static void seq_cache_relink_keys(SeqCacheKey *link_next, SeqCacheKey *link_prev)
220 {
221   if (link_next) {
222     link_next->link_prev = link_prev;
223   }
224   if (link_prev) {
225     link_prev->link_next = link_next;
226   }
227 }
228
229 static SeqCacheKey *seq_cache_choose_key(Scene *scene, SeqCacheKey *lkey, SeqCacheKey *rkey)
230 {
231   SeqCacheKey *finalkey = NULL;
232
233   if (rkey && lkey) {
234     int lkey_cfra = lkey->seq->start + lkey->nfra;
235     int rkey_cfra = rkey->seq->start + rkey->nfra;
236
237     if (lkey_cfra > rkey_cfra) {
238       SeqCacheKey *swapkey = lkey;
239       lkey = rkey;
240       rkey = swapkey;
241     }
242
243     int l_diff = scene->r.cfra - lkey_cfra;
244     int r_diff = rkey_cfra - scene->r.cfra;
245
246     if (l_diff > r_diff) {
247       finalkey = lkey;
248     }
249     else {
250       finalkey = rkey;
251     }
252   }
253   else {
254     if (lkey) {
255       finalkey = lkey;
256     }
257     else {
258       finalkey = rkey;
259     }
260   }
261   return finalkey;
262 }
263
264 static void seq_cache_recycle_linked(Scene *scene, SeqCacheKey *base)
265 {
266   SeqCache *cache = seq_cache_get_from_scene(scene);
267   if (!cache) {
268     return;
269   }
270
271   SeqCacheKey *next = base->link_next;
272
273   while (base) {
274     SeqCacheKey *prev = base->link_prev;
275     BLI_ghash_remove(cache->hash, base, seq_cache_keyfree, seq_cache_valfree);
276     base = prev;
277   }
278
279   base = next;
280   while (base) {
281     next = base->link_next;
282     BLI_ghash_remove(cache->hash, base, seq_cache_keyfree, seq_cache_valfree);
283     base = next;
284   }
285 }
286
287 static SeqCacheKey *seq_cache_get_item_for_removal(Scene *scene)
288 {
289   SeqCache *cache = seq_cache_get_from_scene(scene);
290   SeqCacheKey *finalkey = NULL;
291   /*leftmost key*/
292   SeqCacheKey *lkey = NULL;
293   /*rightmost key*/
294   SeqCacheKey *rkey = NULL;
295   SeqCacheKey *key = NULL;
296
297   GHashIterator gh_iter;
298   BLI_ghashIterator_init(&gh_iter, cache->hash);
299   int total_count = 0;
300   int cheap_count = 0;
301
302   while (!BLI_ghashIterator_done(&gh_iter)) {
303     key = BLI_ghashIterator_getKey(&gh_iter);
304     SeqCacheItem *item = BLI_ghashIterator_getValue(&gh_iter);
305     BLI_ghashIterator_step(&gh_iter);
306
307     /* this shouldn't happen, but better be safe than sorry */
308     if (!item->ibuf) {
309       seq_cache_recycle_linked(scene, key);
310       /* can not continue iterating after linked remove */
311       BLI_ghashIterator_init(&gh_iter, cache->hash);
312       continue;
313     }
314
315     if (key->is_temp_cache || key->link_next != NULL) {
316       continue;
317     }
318
319     total_count++;
320
321     if (key->cost <= scene->ed->recycle_max_cost) {
322       cheap_count++;
323       if (lkey) {
324         if (key->seq->start + key->nfra < lkey->seq->start + lkey->nfra) {
325           lkey = key;
326         }
327       }
328       else {
329         lkey = key;
330       }
331       if (rkey) {
332         if (key->seq->start + key->nfra > rkey->seq->start + rkey->nfra) {
333           rkey = key;
334         }
335       }
336       else {
337         rkey = key;
338       }
339     }
340   }
341
342   finalkey = seq_cache_choose_key(scene, lkey, rkey);
343   return finalkey;
344 }
345
346 /* Find only "base" keys
347  * Sources(other types) for a frame must be freed all at once
348  */
349 static bool seq_cache_recycle_item(Scene *scene)
350 {
351   size_t memory_total = ((size_t)U.memcachelimit) * 1024 * 1024;
352   SeqCache *cache = seq_cache_get_from_scene(scene);
353   if (!cache) {
354     return false;
355   }
356
357   seq_cache_lock(scene);
358
359   while (cache->memory_used > memory_total) {
360     SeqCacheKey *finalkey = seq_cache_get_item_for_removal(scene);
361
362     if (finalkey) {
363       seq_cache_recycle_linked(scene, finalkey);
364     }
365     else {
366       seq_cache_unlock(scene);
367       return false;
368     }
369   }
370   seq_cache_unlock(scene);
371   return true;
372 }
373
374 static void seq_cache_set_temp_cache_linked(Scene *scene, SeqCacheKey *base)
375 {
376   SeqCache *cache = seq_cache_get_from_scene(scene);
377
378   if (!cache || !base) {
379     return;
380   }
381
382   SeqCacheKey *next = base->link_next;
383
384   while (base) {
385     SeqCacheKey *prev = base->link_prev;
386     base->is_temp_cache = true;
387     base = prev;
388   }
389
390   base = next;
391   while (base) {
392     next = base->link_next;
393     base->is_temp_cache = true;
394     base = next;
395   }
396 }
397
398 static void BKE_sequencer_cache_create(Scene *scene)
399 {
400   BLI_mutex_lock(&cache_create_lock);
401   if (scene->ed->cache == NULL) {
402     SeqCache *cache = MEM_callocN(sizeof(SeqCache), "SeqCache");
403     cache->keys_pool = BLI_mempool_create(sizeof(SeqCacheKey), 0, 64, BLI_MEMPOOL_NOP);
404     cache->items_pool = BLI_mempool_create(sizeof(SeqCacheItem), 0, 64, BLI_MEMPOOL_NOP);
405     cache->hash = BLI_ghash_new(seq_cache_hashhash, seq_cache_hashcmp, "SeqCache hash");
406     cache->last_key = NULL;
407     BLI_mutex_init(&cache->iterator_mutex);
408     scene->ed->cache = cache;
409   }
410   BLI_mutex_unlock(&cache_create_lock);
411 }
412
413 /* ***************************** API ****************************** */
414
415 void BKE_sequencer_cache_free_temp_cache(Scene *scene, short id, int cfra)
416 {
417   SeqCache *cache = seq_cache_get_from_scene(scene);
418   if (!cache) {
419     return;
420   }
421
422   seq_cache_lock(scene);
423
424   GHashIterator gh_iter;
425   BLI_ghashIterator_init(&gh_iter, cache->hash);
426   while (!BLI_ghashIterator_done(&gh_iter)) {
427     SeqCacheKey *key = BLI_ghashIterator_getKey(&gh_iter);
428     BLI_ghashIterator_step(&gh_iter);
429
430     if (key->is_temp_cache && key->creator_id == id && key->seq->start + key->nfra != cfra) {
431       BLI_ghash_remove(cache->hash, key, seq_cache_keyfree, seq_cache_valfree);
432     }
433   }
434   seq_cache_unlock(scene);
435 }
436
437 void BKE_sequencer_cache_destruct(Scene *scene)
438 {
439   SeqCache *cache = seq_cache_get_from_scene(scene);
440   if (!cache) {
441     return;
442   }
443
444   BLI_ghash_free(cache->hash, seq_cache_keyfree, seq_cache_valfree);
445   BLI_mempool_destroy(cache->keys_pool);
446   BLI_mempool_destroy(cache->items_pool);
447   BLI_mutex_end(&cache->iterator_mutex);
448   MEM_freeN(cache);
449   scene->ed->cache = NULL;
450 }
451
452 void BKE_sequencer_cache_cleanup_all(Main *bmain)
453 {
454   for (Scene *scene = bmain->scenes.first; scene != NULL; scene = scene->id.next) {
455     BKE_sequencer_cache_cleanup(scene);
456   }
457 }
458 void BKE_sequencer_cache_cleanup(Scene *scene)
459 {
460   SeqCache *cache = seq_cache_get_from_scene(scene);
461   if (!cache) {
462     return;
463   }
464
465   seq_cache_lock(scene);
466
467   GHashIterator gh_iter;
468   BLI_ghashIterator_init(&gh_iter, cache->hash);
469   while (!BLI_ghashIterator_done(&gh_iter)) {
470     SeqCacheKey *key = BLI_ghashIterator_getKey(&gh_iter);
471
472     BLI_ghashIterator_step(&gh_iter);
473     BLI_ghash_remove(cache->hash, key, seq_cache_keyfree, seq_cache_valfree);
474   }
475   cache->last_key = NULL;
476   seq_cache_unlock(scene);
477 }
478
479 void BKE_sequencer_cache_cleanup_sequence(Scene *scene, Sequence *seq)
480 {
481   SeqCache *cache = seq_cache_get_from_scene(scene);
482   if (!cache) {
483     return;
484   }
485
486   seq_cache_lock(scene);
487
488   GHashIterator gh_iter;
489   BLI_ghashIterator_init(&gh_iter, cache->hash);
490   while (!BLI_ghashIterator_done(&gh_iter)) {
491     SeqCacheKey *key = BLI_ghashIterator_getKey(&gh_iter);
492     BLI_ghashIterator_step(&gh_iter);
493
494     if (key->seq == seq) {
495       /* Relink keys, so we don't end up with orphaned keys */
496       if (key->link_next || key->link_prev) {
497         seq_cache_relink_keys(key->link_next, key->link_prev);
498       }
499
500       BLI_ghash_remove(cache->hash, key, seq_cache_keyfree, seq_cache_valfree);
501     }
502   }
503   cache->last_key = NULL;
504   seq_cache_unlock(scene);
505 }
506
507 struct ImBuf *BKE_sequencer_cache_get(const SeqRenderData *context,
508                                       Sequence *seq,
509                                       float cfra,
510                                       int type)
511 {
512   Scene *scene = context->scene;
513
514   if (!scene->ed->cache) {
515     BKE_sequencer_cache_create(scene);
516     return NULL;
517   }
518
519   seq_cache_lock(scene);
520   SeqCache *cache = seq_cache_get_from_scene(scene);
521   ImBuf *ibuf = NULL;
522
523   if (cache && seq) {
524     SeqCacheKey key;
525
526     key.seq = seq;
527     key.context = *context;
528     key.nfra = cfra - seq->start;
529     key.type = type;
530
531     ibuf = seq_cache_get(cache, &key);
532   }
533   seq_cache_unlock(scene);
534
535   return ibuf;
536 }
537
538 bool BKE_sequencer_cache_put_if_possible(
539     const SeqRenderData *context, Sequence *seq, float cfra, int type, ImBuf *ibuf, float cost)
540 {
541   Scene *scene = context->scene;
542
543   if (seq_cache_recycle_item(scene)) {
544     BKE_sequencer_cache_put(context, seq, cfra, type, ibuf, cost);
545     return true;
546   }
547   else {
548     seq_cache_set_temp_cache_linked(scene, scene->ed->cache->last_key);
549     scene->ed->cache->last_key = NULL;
550     return false;
551   }
552 }
553
554 void BKE_sequencer_cache_put(
555     const SeqRenderData *context, Sequence *seq, float cfra, int type, ImBuf *i, float cost)
556 {
557   Scene *scene = context->scene;
558   short creator_id = 0;
559
560   if (i == NULL || context->skip_cache || context->is_proxy_render || !seq) {
561     return;
562   }
563
564   /* Prevent reinserting, it breaks cache key linking */
565   ImBuf *test = BKE_sequencer_cache_get(context, seq, cfra, type);
566   if (test) {
567     IMB_freeImBuf(test);
568     return;
569   }
570
571   if (!scene->ed->cache) {
572     BKE_sequencer_cache_create(scene);
573   }
574
575   seq_cache_lock(scene);
576
577   SeqCache *cache = seq_cache_get_from_scene(scene);
578   int flag;
579
580   if (seq->cache_flag & SEQ_CACHE_OVERRIDE) {
581     flag = seq->cache_flag;
582     flag |= scene->ed->cache_flag & SEQ_CACHE_STORE_FINAL_OUT;
583   }
584   else {
585     flag = scene->ed->cache_flag;
586   }
587
588   if (cost > SEQ_CACHE_COST_MAX) {
589     cost = SEQ_CACHE_COST_MAX;
590   }
591
592   SeqCacheKey *key;
593   key = BLI_mempool_alloc(cache->keys_pool);
594   key->cache_owner = cache;
595   key->seq = seq;
596   key->context = *context;
597   key->nfra = cfra - seq->start;
598   key->type = type;
599   key->cost = cost;
600   key->cache_owner = cache;
601   key->link_prev = NULL;
602   key->link_next = NULL;
603   key->is_temp_cache = true;
604   key->creator_id = creator_id;
605
606   /* Item stored for later use */
607   if (flag & type) {
608     key->is_temp_cache = false;
609     key->link_prev = cache->last_key;
610   }
611
612   SeqCacheKey *temp_last_key = cache->last_key;
613   seq_cache_put(cache, key, i);
614
615   /* Restore pointer to previous item as this one will be freed when stack is rendered */
616   if (key->is_temp_cache) {
617     cache->last_key = temp_last_key;
618   }
619
620   /* Set last_key's reference to this key so we can look up chain backwards
621    * Item is already put in cache, so cache->last_key points to current key;
622    */
623   if (flag & type && temp_last_key) {
624     temp_last_key->link_next = cache->last_key;
625   }
626
627   /* Reset linking */
628   if (key->type == SEQ_CACHE_STORE_FINAL_OUT) {
629     cache->last_key = NULL;
630   }
631
632   seq_cache_unlock(scene);
633 }
634
635 void BKE_sequencer_cache_iterate(
636     struct Scene *scene,
637     void *userdata,
638     bool callback(void *userdata, struct Sequence *seq, int nfra, int cache_type, float cost))
639 {
640   SeqCache *cache = seq_cache_get_from_scene(scene);
641   if (!cache) {
642     return;
643   }
644
645   seq_cache_lock(scene);
646   GHashIterator gh_iter;
647   BLI_ghashIterator_init(&gh_iter, cache->hash);
648   bool interrupt = false;
649
650   while (!BLI_ghashIterator_done(&gh_iter) && !interrupt) {
651     SeqCacheKey *key = BLI_ghashIterator_getKey(&gh_iter);
652     BLI_ghashIterator_step(&gh_iter);
653
654     interrupt = callback(userdata, key->seq, key->nfra, key->type, key->cost);
655   }
656
657   cache->last_key = NULL;
658   seq_cache_unlock(scene);
659 }