1c0aa63f590202afa21d6533430a7077e8110f9c
[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 cfra;
94   float nfra;
95   float cost;
96   bool is_temp_cache;
97   short creator_id;
98   int type;
99 } SeqCacheKey;
100
101 static ThreadMutex cache_create_lock = BLI_MUTEX_INITIALIZER;
102
103 static bool seq_cmp_render_data(const SeqRenderData *a, const SeqRenderData *b)
104 {
105   return ((a->preview_render_size != b->preview_render_size) || (a->rectx != b->rectx) ||
106           (a->recty != b->recty) || (a->bmain != b->bmain) || (a->scene != b->scene) ||
107           (a->motion_blur_shutter != b->motion_blur_shutter) ||
108           (a->motion_blur_samples != b->motion_blur_samples) ||
109           (a->scene->r.views_format != b->scene->r.views_format) || (a->view_id != b->view_id));
110 }
111
112 static unsigned int seq_hash_render_data(const SeqRenderData *a)
113 {
114   unsigned int rval = a->rectx + a->recty;
115
116   rval ^= a->preview_render_size;
117   rval ^= ((intptr_t)a->bmain) << 6;
118   rval ^= ((intptr_t)a->scene) << 6;
119   rval ^= (int)(a->motion_blur_shutter * 100.0f) << 10;
120   rval ^= a->motion_blur_samples << 16;
121   rval ^= ((a->scene->r.views_format * 2) + a->view_id) << 24;
122
123   return rval;
124 }
125
126 static unsigned int seq_cache_hashhash(const void *key_)
127 {
128   const SeqCacheKey *key = key_;
129   unsigned int rval = seq_hash_render_data(&key->context);
130
131   rval ^= *(const unsigned int *)&key->nfra;
132   rval += key->type;
133   rval ^= ((intptr_t)key->seq) << 6;
134
135   return rval;
136 }
137
138 static bool seq_cache_hashcmp(const void *a_, const void *b_)
139 {
140   const SeqCacheKey *a = a_;
141   const SeqCacheKey *b = b_;
142
143   return ((a->seq != b->seq) || (a->nfra != b->nfra) || (a->type != b->type) ||
144           seq_cmp_render_data(&a->context, &b->context));
145 }
146
147 static SeqCache *seq_cache_get_from_scene(Scene *scene)
148 {
149   if (scene && scene->ed && scene->ed->cache) {
150     return scene->ed->cache;
151   }
152
153   return NULL;
154 }
155
156 static void seq_cache_lock(Scene *scene)
157 {
158   SeqCache *cache = seq_cache_get_from_scene(scene);
159
160   if (cache) {
161     BLI_mutex_lock(&cache->iterator_mutex);
162   }
163 }
164
165 static void seq_cache_unlock(Scene *scene)
166 {
167   SeqCache *cache = seq_cache_get_from_scene(scene);
168
169   if (cache) {
170     BLI_mutex_unlock(&cache->iterator_mutex);
171   }
172 }
173
174 static void seq_cache_keyfree(void *val)
175 {
176   SeqCacheKey *key = val;
177   BLI_mempool_free(key->cache_owner->keys_pool, key);
178 }
179
180 static void seq_cache_valfree(void *val)
181 {
182   SeqCacheItem *item = (SeqCacheItem *)val;
183   SeqCache *cache = item->cache_owner;
184
185   if (item->ibuf) {
186     cache->memory_used -= IMB_get_size_in_memory(item->ibuf);
187     IMB_freeImBuf(item->ibuf);
188   }
189
190   BLI_mempool_free(item->cache_owner->items_pool, item);
191 }
192
193 static void seq_cache_put(SeqCache *cache, SeqCacheKey *key, ImBuf *ibuf)
194 {
195   SeqCacheItem *item;
196   item = BLI_mempool_alloc(cache->items_pool);
197   item->cache_owner = cache;
198   item->ibuf = ibuf;
199
200   if (BLI_ghash_reinsert(cache->hash, key, item, seq_cache_keyfree, seq_cache_valfree)) {
201     IMB_refImBuf(ibuf);
202     cache->last_key = key;
203     cache->memory_used += IMB_get_size_in_memory(ibuf);
204   }
205 }
206
207 static ImBuf *seq_cache_get(SeqCache *cache, void *key)
208 {
209   SeqCacheItem *item = BLI_ghash_lookup(cache->hash, key);
210
211   if (item && item->ibuf) {
212     IMB_refImBuf(item->ibuf);
213
214     return item->ibuf;
215   }
216
217   return NULL;
218 }
219
220 static void seq_cache_relink_keys(SeqCacheKey *link_next, SeqCacheKey *link_prev)
221 {
222   if (link_next) {
223     link_next->link_prev = link_prev;
224   }
225   if (link_prev) {
226     link_prev->link_next = link_next;
227   }
228 }
229
230 static SeqCacheKey *seq_cache_choose_key(Scene *scene, SeqCacheKey *lkey, SeqCacheKey *rkey)
231 {
232   SeqCacheKey *finalkey = NULL;
233
234   if (rkey && lkey) {
235     if (lkey->cfra > rkey->cfra) {
236       SeqCacheKey *swapkey = lkey;
237       lkey = rkey;
238       rkey = swapkey;
239     }
240
241     int l_diff = scene->r.cfra - lkey->cfra;
242     int r_diff = rkey->cfra - scene->r.cfra;
243
244     if (l_diff > r_diff) {
245       finalkey = lkey;
246     }
247     else {
248       finalkey = rkey;
249     }
250   }
251   else {
252     if (lkey) {
253       finalkey = lkey;
254     }
255     else {
256       finalkey = rkey;
257     }
258   }
259   return finalkey;
260 }
261
262 static void seq_cache_recycle_linked(Scene *scene, SeqCacheKey *base)
263 {
264   SeqCache *cache = seq_cache_get_from_scene(scene);
265   if (!cache) {
266     return;
267   }
268
269   SeqCacheKey *next = base->link_next;
270
271   while (base) {
272     SeqCacheKey *prev = base->link_prev;
273     BLI_ghash_remove(cache->hash, base, seq_cache_keyfree, seq_cache_valfree);
274     base = prev;
275   }
276
277   base = next;
278   while (base) {
279     next = base->link_next;
280     BLI_ghash_remove(cache->hash, base, seq_cache_keyfree, seq_cache_valfree);
281     base = next;
282   }
283 }
284
285 static SeqCacheKey *seq_cache_get_item_for_removal(Scene *scene)
286 {
287   SeqCache *cache = seq_cache_get_from_scene(scene);
288   SeqCacheKey *finalkey = NULL;
289   /*leftmost key*/
290   SeqCacheKey *lkey = NULL;
291   /*rightmost key*/
292   SeqCacheKey *rkey = NULL;
293   SeqCacheKey *key = NULL;
294
295   GHashIterator gh_iter;
296   BLI_ghashIterator_init(&gh_iter, cache->hash);
297   int total_count = 0;
298   int cheap_count = 0;
299
300   while (!BLI_ghashIterator_done(&gh_iter)) {
301     key = BLI_ghashIterator_getKey(&gh_iter);
302     SeqCacheItem *item = BLI_ghashIterator_getValue(&gh_iter);
303     BLI_ghashIterator_step(&gh_iter);
304
305     /* this shouldn't happen, but better be safe than sorry */
306     if (!item->ibuf) {
307       seq_cache_recycle_linked(scene, key);
308       /* can not continue iterating after linked remove */
309       BLI_ghashIterator_init(&gh_iter, cache->hash);
310       continue;
311     }
312
313     if (key->is_temp_cache || key->link_next != NULL) {
314       continue;
315     }
316
317     total_count++;
318
319     if (key->cost <= scene->ed->recycle_max_cost) {
320       cheap_count++;
321       if (lkey) {
322         if (key->cfra < lkey->cfra) {
323           lkey = key;
324         }
325       }
326       else {
327         lkey = key;
328       }
329       if (rkey) {
330         if (key->cfra > rkey->cfra) {
331           rkey = key;
332         }
333       }
334       else {
335         rkey = key;
336       }
337     }
338   }
339
340   finalkey = seq_cache_choose_key(scene, lkey, rkey);
341   return finalkey;
342 }
343
344 /* Find only "base" keys
345  * Sources(other types) for a frame must be freed all at once
346  */
347 static bool seq_cache_recycle_item(Scene *scene)
348 {
349   size_t memory_total = ((size_t)U.memcachelimit) * 1024 * 1024;
350   SeqCache *cache = seq_cache_get_from_scene(scene);
351   if (!cache) {
352     return false;
353   }
354
355   seq_cache_lock(scene);
356
357   while (cache->memory_used > memory_total) {
358     SeqCacheKey *finalkey = seq_cache_get_item_for_removal(scene);
359
360     if (finalkey) {
361       seq_cache_recycle_linked(scene, finalkey);
362     }
363     else {
364       seq_cache_unlock(scene);
365       return false;
366     }
367   }
368   seq_cache_unlock(scene);
369   return true;
370 }
371
372 static void seq_cache_set_temp_cache_linked(Scene *scene, SeqCacheKey *base)
373 {
374   SeqCache *cache = seq_cache_get_from_scene(scene);
375
376   if (!cache || !base) {
377     return;
378   }
379
380   SeqCacheKey *next = base->link_next;
381
382   while (base) {
383     SeqCacheKey *prev = base->link_prev;
384     base->is_temp_cache = true;
385     base = prev;
386   }
387
388   base = next;
389   while (base) {
390     next = base->link_next;
391     base->is_temp_cache = true;
392     base = next;
393   }
394 }
395
396 static void BKE_sequencer_cache_create(Scene *scene)
397 {
398   BLI_mutex_lock(&cache_create_lock);
399   if (scene->ed->cache == NULL) {
400     SeqCache *cache = MEM_callocN(sizeof(SeqCache), "SeqCache");
401     cache->keys_pool = BLI_mempool_create(sizeof(SeqCacheKey), 0, 64, BLI_MEMPOOL_NOP);
402     cache->items_pool = BLI_mempool_create(sizeof(SeqCacheItem), 0, 64, BLI_MEMPOOL_NOP);
403     cache->hash = BLI_ghash_new(seq_cache_hashhash, seq_cache_hashcmp, "SeqCache hash");
404     cache->last_key = NULL;
405     BLI_mutex_init(&cache->iterator_mutex);
406     scene->ed->cache = cache;
407   }
408   BLI_mutex_unlock(&cache_create_lock);
409 }
410
411 /* ***************************** API ****************************** */
412
413 void BKE_sequencer_cache_free_temp_cache(Scene *scene, short id, int cfra)
414 {
415   SeqCache *cache = seq_cache_get_from_scene(scene);
416   if (!cache) {
417     return;
418   }
419
420   seq_cache_lock(scene);
421
422   GHashIterator gh_iter;
423   BLI_ghashIterator_init(&gh_iter, cache->hash);
424   while (!BLI_ghashIterator_done(&gh_iter)) {
425     SeqCacheKey *key = BLI_ghashIterator_getKey(&gh_iter);
426     BLI_ghashIterator_step(&gh_iter);
427
428     if (key->is_temp_cache && key->creator_id == id && key->cfra != cfra) {
429       BLI_ghash_remove(cache->hash, key, seq_cache_keyfree, seq_cache_valfree);
430     }
431   }
432   seq_cache_unlock(scene);
433 }
434
435 void BKE_sequencer_cache_destruct(Scene *scene)
436 {
437   SeqCache *cache = seq_cache_get_from_scene(scene);
438   if (!cache) {
439     return;
440   }
441
442   BLI_ghash_free(cache->hash, seq_cache_keyfree, seq_cache_valfree);
443   BLI_mempool_destroy(cache->keys_pool);
444   BLI_mempool_destroy(cache->items_pool);
445   BLI_mutex_end(&cache->iterator_mutex);
446   MEM_freeN(cache);
447   scene->ed->cache = NULL;
448 }
449
450 void BKE_sequencer_cache_cleanup_all(Main *bmain)
451 {
452   for (Scene *scene = bmain->scenes.first; scene != NULL; scene = scene->id.next) {
453     BKE_sequencer_cache_cleanup(scene);
454   }
455 }
456 void BKE_sequencer_cache_cleanup(Scene *scene)
457 {
458   SeqCache *cache = seq_cache_get_from_scene(scene);
459   if (!cache) {
460     return;
461   }
462
463   seq_cache_lock(scene);
464
465   GHashIterator gh_iter;
466   BLI_ghashIterator_init(&gh_iter, cache->hash);
467   while (!BLI_ghashIterator_done(&gh_iter)) {
468     SeqCacheKey *key = BLI_ghashIterator_getKey(&gh_iter);
469
470     BLI_ghashIterator_step(&gh_iter);
471     BLI_ghash_remove(cache->hash, key, seq_cache_keyfree, seq_cache_valfree);
472   }
473   cache->last_key = NULL;
474   seq_cache_unlock(scene);
475 }
476
477 void BKE_sequencer_cache_cleanup_sequence(Scene *scene, Sequence *seq)
478 {
479   SeqCache *cache = seq_cache_get_from_scene(scene);
480   if (!cache) {
481     return;
482   }
483
484   seq_cache_lock(scene);
485
486   GHashIterator gh_iter;
487   BLI_ghashIterator_init(&gh_iter, cache->hash);
488   while (!BLI_ghashIterator_done(&gh_iter)) {
489     SeqCacheKey *key = BLI_ghashIterator_getKey(&gh_iter);
490     BLI_ghashIterator_step(&gh_iter);
491
492     if (key->seq == seq) {
493       /* Relink keys, so we don't end up with orphaned keys */
494       if (key->link_next || key->link_prev) {
495         seq_cache_relink_keys(key->link_next, key->link_prev);
496       }
497
498       BLI_ghash_remove(cache->hash, key, seq_cache_keyfree, seq_cache_valfree);
499     }
500   }
501   cache->last_key = NULL;
502   seq_cache_unlock(scene);
503 }
504
505 struct ImBuf *BKE_sequencer_cache_get(const SeqRenderData *context,
506                                       Sequence *seq,
507                                       float cfra,
508                                       int type)
509 {
510   Scene *scene = context->scene;
511
512   if (!scene->ed->cache) {
513     BKE_sequencer_cache_create(scene);
514     return NULL;
515   }
516
517   seq_cache_lock(scene);
518   SeqCache *cache = seq_cache_get_from_scene(scene);
519   ImBuf *ibuf = NULL;
520
521   if (cache && seq) {
522     SeqCacheKey key;
523
524     key.seq = seq;
525     key.context = *context;
526     key.nfra = cfra - seq->start;
527     key.type = type;
528
529     ibuf = seq_cache_get(cache, &key);
530   }
531   seq_cache_unlock(scene);
532
533   return ibuf;
534 }
535
536 bool BKE_sequencer_cache_put_if_possible(
537     const SeqRenderData *context, Sequence *seq, float cfra, int type, ImBuf *ibuf, float cost)
538 {
539   Scene *scene = context->scene;
540
541   if (seq_cache_recycle_item(scene)) {
542     BKE_sequencer_cache_put(context, seq, cfra, type, ibuf, cost);
543     return true;
544   }
545   else {
546     seq_cache_set_temp_cache_linked(scene, scene->ed->cache->last_key);
547     scene->ed->cache->last_key = NULL;
548     return false;
549   }
550 }
551
552 void BKE_sequencer_cache_put(
553     const SeqRenderData *context, Sequence *seq, float cfra, int type, ImBuf *i, float cost)
554 {
555   Scene *scene = context->scene;
556   short creator_id = 0;
557
558   if (i == NULL || context->skip_cache || context->is_proxy_render || !seq) {
559     return;
560   }
561
562   /* Prevent reinserting, it breaks cache key linking */
563   ImBuf *test = BKE_sequencer_cache_get(context, seq, cfra, type);
564   if (test) {
565     IMB_freeImBuf(test);
566     return;
567   }
568
569   if (!scene->ed->cache) {
570     BKE_sequencer_cache_create(scene);
571   }
572
573   seq_cache_lock(scene);
574
575   SeqCache *cache = seq_cache_get_from_scene(scene);
576   int flag;
577
578   if (seq->cache_flag & SEQ_CACHE_OVERRIDE) {
579     flag = seq->cache_flag;
580     flag |= scene->ed->cache_flag & SEQ_CACHE_STORE_FINAL_OUT;
581   }
582   else {
583     flag = scene->ed->cache_flag;
584   }
585
586   if (cost > SEQ_CACHE_COST_MAX) {
587     cost = SEQ_CACHE_COST_MAX;
588   }
589
590   SeqCacheKey *key;
591   key = BLI_mempool_alloc(cache->keys_pool);
592   key->cache_owner = cache;
593   key->seq = seq;
594   key->context = *context;
595   key->cfra = cfra;
596   key->nfra = cfra - seq->start;
597   key->type = type;
598   key->cost = cost;
599   key->cache_owner = cache;
600   key->link_prev = NULL;
601   key->link_next = NULL;
602   key->is_temp_cache = true;
603   key->creator_id = creator_id;
604
605   /* Item stored for later use */
606   if (flag & type) {
607     key->is_temp_cache = false;
608     key->link_prev = cache->last_key;
609   }
610
611   SeqCacheKey *temp_last_key = cache->last_key;
612   seq_cache_put(cache, key, i);
613
614   /* Restore pointer to previous item as this one will be freed when stack is rendered */
615   if (key->is_temp_cache) {
616     cache->last_key = temp_last_key;
617   }
618
619   /* Set last_key's reference to this key so we can look up chain backwards
620    * Item is already put in cache, so cache->last_key points to current key;
621    */
622   if (flag & type && temp_last_key) {
623     temp_last_key->link_next = cache->last_key;
624   }
625
626   /* Reset linking */
627   if (key->type == SEQ_CACHE_STORE_FINAL_OUT) {
628     cache->last_key = NULL;
629   }
630
631   seq_cache_unlock(scene);
632 }
633
634 void BKE_sequencer_cache_iterate(
635     struct Scene *scene,
636     void *userdata,
637     bool callback(void *userdata, struct Sequence *seq, int cfra, int cache_type, float cost))
638 {
639   SeqCache *cache = seq_cache_get_from_scene(scene);
640   if (!cache) {
641     return;
642   }
643
644   seq_cache_lock(scene);
645   GHashIterator gh_iter;
646   BLI_ghashIterator_init(&gh_iter, cache->hash);
647   bool interrupt = false;
648
649   while (!BLI_ghashIterator_done(&gh_iter) && !interrupt) {
650     SeqCacheKey *key = BLI_ghashIterator_getKey(&gh_iter);
651     BLI_ghashIterator_step(&gh_iter);
652
653     interrupt = callback(userdata, key->seq, key->cfra, key->type, key->cost);
654   }
655
656   cache->last_key = NULL;
657   seq_cache_unlock(scene);
658 }