Don't cache GIF frames if it would be too large.

third_party/WebKit/Source/platform/image-decoders/gif/GIFImageDecoder.cpp

 /*
  * Copyright (C) 2006 Apple Computer, Inc.  All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
@@ skipping 16 matching lines @@
 
 #include <limits>
 #include "platform/image-decoders/gif/GIFImageReader.h"
 #include "wtf/NotFound.h"
 #include "wtf/PassOwnPtr.h"
 
 namespace blink {
 
 GIFImageDecoder::GIFImageDecoder(AlphaOption alphaOption, GammaAndColorProfileOption colorOptions, size_t maxDecodedBytes)
     : ImageDecoder(alphaOption, colorOptions, maxDecodedBytes)
+    , m_purgeAggressively(false)
     , m_repetitionCount(cAnimationLoopOnce)
 {
 }
 
 GIFImageDecoder::~GIFImageDecoder()
 {
 }
 
 void GIFImageDecoder::onSetData(SegmentReader* data)
 {
@@ skipping 247 matching lines @@
     buffer->setRequiredPreviousFrameIndex(findRequiredPreviousFrame(index, false));
 }
 
 void GIFImageDecoder::decode(size_t index)
 {
     parse(GIFFrameCountQuery);
 
     if (failed())
         return;
 
+    // We don't want to cache so much that we cause a memory issue.
+    // If we used a LRU cache we would fill it and then on next animation loop
+    // we would need to decode all the frames again -- the LRU would give no
+    // benefit and would consume more memory.
+    // So instead, simply purge unused frames if our image would be too large.
+
+    // As we decode we will learn the total number of frames, and thus total
+    // image memory usage.

[scroggo_chromium, 2016/06/20 17:59:40]

It might be interesting to note that the "MemoryUsage" you count is in units of
pixels (rather than bytes, which might be expected).

[cblume, 2016/06/21 01:00:52]

Oh, oops. I originally wrote this with a * 4 since it becomes 32bpp.
I really want to compare against memory size so I'll make sure to check the size
of the frame.

+    IntSize decodedImageSize = this->decodedSize();
+    unsigned frameMemoryUsage = decodedImageSize.width() * decodedImageSize.height();

[scroggo_chromium, 2016/06/20 17:59:40]

Why is this unsigned? Should we call decodedImageSize.area()? (That method
converts up to uin64_t to protect against overflow.)

[cblume, 2016/06/21 01:00:52]

Hrmmm, the unsigned was a mistake. the .width() and .height() return int.

The unsigned comes from sizeCalculationMayOverflow
https://cs.chromium.org/chromium/src/third_party/WebKit/Source/platform/image...
which is called from ImageDecoder::setSize().
This is also where the (1 << 29) - 1 comes from, which was mentioned in another
comment. The 29 is specifically because there is sometimes width * height * 4.
32-bit * 32bit might consume 64-bit. Multiply that by 4 and you need more bits.

Although, we then (currently) multiply that by the index.

I'll clean this up.

+    unsigned long long imageMemoryUsage = static_cast<unsigned long long>(frameMemoryUsage)

[scroggo_chromium, 2016/06/20 17:59:40]

The meaning of the word "image" here is not entirely obvious to me. Maybe call
this totalMemoryUsage?

On another note, I think this is really the worst case scenario - where we
actually have to store all frames from 0 - index.

If we wanted to be more conservative, we could only purge after we've stored
enough frames to reach the limit. (That would require us to do the check on each
call to decode, which could have an effect on performance. Although as I mention
elsewhere, we're currently always doing this check.)

[cblume, 2016/06/21 01:00:52]

I did not parse what you said very well.
If I understand correctly, are you suggesting that we keep caching frames until
we learn that we have crossed the limit, and then we purge?
That is what this code does. It attempts to keep the benefit of caching until it
learns the the cost of caching would blow our memory budget. It then switches
into purge mode.
Because gif doesn't let you know in advance how many frames there will be while
downloading, we have to do it as we go.

I suppose once we have made a full loop we can not check since we then know it
won't need to purge aggressively.

[scroggo_chromium, 2016/06/21 15:46:08]

Sorry, I'll try to explain it better:

You compute how much memory is cached in the GIFImageDecoder to be |index| *
|frameMemoryUsage|. But as I understand it, it is possible that GIFImageDecoder
has already been told to purge, in which case the actual amount cached is less
than |index| * |frameMemoryUsage|.

If |N| is the number of frames (< |index|) that have already been purged (by the
client calling clearCacheExceptFrame before decoding frame |index|), the memory
cached in GIFImageDecoder is actually (|index| - |N|) * |frameMemoryUsage|. It
sounds like it is possible that GIFImageDecoder will have to decode frames 0 -
|N|, which is the worst case scenario, but we don't know that yet. We'll find
out the actual number down below, at the end of the do while loop.
Almost. It counts frames that we might not actually have to decode.
I agree - if we make a full loop and never set m_purgeAggressively to true
(based on the current computation), the second loop does not need to check.

But once we've set m_purgeAggressively to true, we can also skip the check for
the remainder of the first loop (and for future loops, because again, we
currently never set m_purgeAggressively back to false).

[cblume, 2016/06/22 01:23:06]

Ah, okay. I think I understand better now.

You are correct that we might not have to decode 0-N, or that the current memory
usage is all-the-previous-frames. I think that might be what you meant about the
worst-case scenario.

However, I'm not trying to find the amount of frames we need to decode or the
current amount of memory used.
I'm trying to find the amount of memory we could potentially use if every frame
were cached.

So I'm not bothered by whether previous frames were purged or not.



My reasoning is...

- If we had unlimited memory we would cache all frames.

- If we were tightly memory confined we would only cache what is required to
decode the next frame (so we aren't wasting work).

- We could stay somewhere in the middle and maintain specially-selected frames.
This would require some smarter awareness from the decoder. If we wanted to do
that it should be a separate CL. And it would probably be in the purge function,
which we would need to call anyway. So this portion of the smarts would still be
correct.

So that said, given our current constraint of each image having a separate
budget, ...
- Either we can fit the entire image in cache, or
- We cannot, and we should be purging (the purge can become smarter in the
future)

So that is exactly what my code looks for. Will the whole image fit or not?
Should we purge at all or not?



Although, maybe we should *always* call purge and the purge itself can be smart
about managing the cache size. Maybe this code belongs in the purge function.

[scroggo_chromium, 2016/06/22 15:10:04]

Yes, that is what I mean.
That sounds fine to me. Will you please update the comments to reflect that?
Something like (slightly modifying your comments above):

// So instead, simply purge unused frames if caching all the frames of the image
would
// use too much memory.
// As we decode we will learn the total number of frames, and thus total
// possible image memory usage.
+1
When you say "the purge function", do you mean clearCacheExceptFrame? I think it
makes more sense here, since clearCache means it will clear it, but this code
decides whether to clear it. (Although come to think of it, that method might
decide to keep another frame anyway...)

+        * static_cast<unsigned long long>(index);
+
+    bool overflowed = imageMemoryUsage > ((1 << 29) - 1);

[scroggo_chromium, 2016/06/20 17:59:40]

How'd you pick this number?

+    if (overflowed) {

[scroggo_chromium, 2016/06/20 17:59:40]

It looks like this should be

    if (overflowed || imageMemoryUsage > m_maxDecodedBytes)
        m_purgeAggressively = true;

Maybe it'd be even simpler to say

    if (imageMemoryUsage > min((1 << 29) - 1), m_maxDecodedBytes))
        m_purgeAggressively = true;

+        m_purgeAggressively = true;
+    } else {
+        if (imageMemoryUsage > m_maxDecodedBytes)

[scroggo_chromium, 2016/06/20 17:59:40]

As mentioned above, imageMemoryUsage is in units of pixels. m_maxDecodedBytes is
in bytes, so this seems like an inappropriate comparison.

+            m_purgeAggressively = true;
+    }
+
     Vector<size_t> framesToDecode;
     size_t frameToDecode = index;
     do {
         framesToDecode.append(frameToDecode);
         frameToDecode = m_frameBufferCache[frameToDecode].requiredPreviousFrameIndex();
     } while (frameToDecode != kNotFound && m_frameBufferCache[frameToDecode].getStatus() != ImageFrame::FrameComplete);
 
     for (auto i = framesToDecode.rbegin(); i != framesToDecode.rend(); ++i) {

[scroggo_chromium, 2016/06/21 15:46:08]

At this point, we know the actual amount of data we'll be required to cache -
it's

  framesToDecode.size() * frameMemoryUsage.

         if (!m_reader->decode(*i)) {
             setFailed();
             return;
         }
 
+        if (m_purgeAggressively)

[scroggo_chromium, 2016/06/20 17:59:40]

As written, m_purgeAggressively could be a local variable. The only effect of it
being a member variable is that once it's set to true, it remains true on future
iterations. But you still check the size on future calls in order to decide
whether to set it to true or do nothing.

- If we should continue purging aggressively even if we go back to the first
frame and we are well under the limit, should we skip the calculations to
determine whether to purge if we are already purging? (Or maybe I'm optimizing
prematurely?)
- If we only want to purge aggressively when we're over the limit, we could make
it a local variable.

[cblume, 2016/06/21 01:00:52]

I do not want it to be a local variable.

If it was local we might not purge until we hit frame 20 (for example), but then
we would purge all the unneeded frames and have wasted the memory those frames
consumed.

Keeping the aggressive purge after we loop means we won't have memory spikes for
the first part of the animation.

I'll modify it to skip the calculation if we have already determined we should
purge aggressively.

[scroggo_chromium, 2016/06/21 15:46:08]

But isn't that already true in this patch set, at least on the first iteration
through the loop? I guess your next sentence tells me you're really concerned
about the second iteration. That seems fine to me, but I do think it's a
tradeoff between using memory and having the frames you need. i.e. on the second
iteration, we'll be purging aggressively before frame 20, but isn't it possible
we'll purge frames that we'll need later?

+            this->clearCacheExceptFrame(*i);
+
         // We need more data to continue decoding.
         if (m_frameBufferCache[*i].getStatus() != ImageFrame::FrameComplete)
             break;
     }
 
     // It is also a fatal error if all data is received and we have decoded all
     // frames available but the file is truncated.
     if (index >= m_frameBufferCache.size() - 1 && isAllDataReceived() && m_reader && !m_reader->parseCompleted())
         setFailed();
 }
@@ skipping 41 matching lines @@
 
     // Update our status to be partially complete.
     buffer->setStatus(ImageFrame::FramePartial);
 
     // Reset the alpha pixel tracker for this frame.
     m_currentBufferSawAlpha = false;
     return true;
 }
 
 } // namespace blink