274391 - GIF Decoder: Convert many malloc's to 1, also remove broken netscape extension

Status: VERIFIED FIXED

(Core :: Graphics: ImageLib, defect)

Description

[Alfred Kayser]

Looking at memory allocaters (specifically the recyclingAllocator), I noticed
that GIF2.cpp allocates in one go, three blocks of fixed size, and releases them
at the same time. So these could also be allocated as one block:

535       if (!gs->prefix)
536         gs->prefix = (PRUint16 *)gif_calloc(sizeof(PRUint16), MAX_BITS);
537       if (!gs->suffix)
538         gs->suffix = ( PRUint8 *)gif_calloc(sizeof(PRUint8),  MAX_BITS);
539       if (!gs->stack)
540         gs->stack  = ( PRUint8 *)gif_calloc(sizeof(PRUint8),  MAX_BITS);

and:

1081   gif_free(gs->prefix);
1082   gif_free(gs->suffix);
1083   gif_free(gs->stack);

Allocating them as one block, saves some memory allocation overhead, also in the
recycler (or even more so!). Instead of 3 blocks of different sizes per decode
run, it allocates always one block of the same size per run.

Comment 1

[Alfred Kayser]

Attachment: Clean and simple patch, increasing memory efficiency of GIF decoder

Comment 2

[Jean-Marc Desperrier]

Well, could we go even further and make them static member of gif_struct ?

Current life span :

- GIFInit : gs is allocated
- first call to 'gif_write' : those static size buffers are allocated
- gif_destroy : gs and the buffers (if present) are disallocated

Will usually GIFInit be called without gif_write being called too soon afterward ?

Of course, that change would need a more careful review than the obvious change
above.

Comment 3

[Alfred Kayser]

Attachment: Merged allocation of GIFStruct and the prefix/stack/suffix

Merged the allocation of GIFStruct and the prefix/suffix/stack buffers, 
also moved this allocation to nsGIFDecoder, so both allocation and free of the
GIFStruct is in one file.
Further, some small cleanups and optimisations in GIF2.cpp.
Sideeffect: some codesize reduction about 700bytes.

Note, it is not clear whether the memset's all required for the prefix/suffix
and stack buffers, but I left them in to be safe.

Comment 4

[Johnny Stenback (:jst)]

Comment on attachment 168690 [details] [diff] [review]
Merged allocation of GIFStruct and the prefix/stack/suffix

+      memset(gs->prefix, 0, sizeof(PRUint16)*MAX_BITS);
+      memset(gs->suffix, 0, sizeof(PRUint8)*MAX_BITS);
+      memset(gs->stack, 0, sizeof(PRUint8)*MAX_BITS);

How about using sizeof(gs->prefix) etc there in stead of hard coding the sizes
here too?

+    PRBool is_transparent;	    /* TRUE, if tpixel is valid */
+    PRBool is_local_colormap_defined;
+    PRBool progressive_display;    /* If TRUE, do Haeberli interlace hack */

These are asking to be changed to PRPackedBool's.

+/*****************************************************************************
**
+ * Gif decoder allocator
+ *
+ * For every image that gets loaded, we allocate
+ *	4097 x 2 : gs->prefix
+ *	4097 x 1 : gs->suffix
+ *	4097 x 1 : gs->stack
+ * for lzw to operate on the data. These are held for a very short interval
+ * and freed. This allocator tries to keep one set of these around
+ * and reuses them; automatically fails over to use calloc/free when all
+ * buckets are full.

That's not exactly true any more, no more separate allocations etc. Update the
comment.

With that, r=jst.

Comment 5

[Alfred Kayser]

Attachment: Incorporated comments from jst.

Note, the free of mGIFStruct in ::Close was missing, so I've added it there.
So save more code bytes, the destructor now calls ::Close (which is save to
do),
and some other small assembly level optimisations in GIF2.cpp.

Fully tested with a wide range of GIF files, very large ones, 'truecolors',
very large interlaced files, etc.

Comment 6

[Darin Fisher]

Comment on attachment 168765 [details] [diff] [review]
Incorporated comments from jst.

>Index: modules/libpr0n/decoders/gif/GIF2.cpp

>+const PRUintn kDup[]    = { 0, 7, 3, 1 }; 
>+const PRUintn kRowInc[] = { 0, 8, 8, 4, 2 }; 
>+const PRUintn kRowTop[] = { 0, 4, 2, 1, 0 }; 

can you add a comment for these?


>Index: modules/libpr0n/decoders/gif/nsGIFDecoder2.cpp

>+  if (!gGifAllocator)
>+    gGifAllocator = new nsRecyclingAllocator(kGifAllocatorNBucket,
>+                                             NS_DEFAULT_RECYCLE_TIMEOUT, "gif");
>+  mGIFStruct = (gif_struct *)(gGifAllocator ?
>+                              gGifAllocator->Calloc(sizeof(gif_struct),1) :
>+                              calloc(sizeof(gif_struct),1))

If |new nsRecyclingAllocator| failed, why do you bother trying to
call |calloc|?	I don't understand.  It seems like you would have
an OOM condition, and would just want to bail.	Surely calloc will
also fail, no?


I think this patch should also be reviewed by one of the ImageLib
peers, preferrably by pavlov.

Comment 7

[Alfred Kayser]

Attachment: Incorporated comments from Darin, and more malloc optimisation.

This version incorporates comments from Darin:
* Added comments to the constant arrays
* I left in the 'calloc' bailout, because it doesn't hurt, and can be be backup
for the RecyclingAllocator...

I've added the following changes:
* removed some unused states from the gif decoder, merged the gif header
parsing into one state.
* changed BlockAllocCat to keep the 'hold' size a multiple of 256 bytes, and to
only resize when it needs to be bigger (it will be at most 1024 bytes anyway).
This saves a malloc and realloc for each 4096 byte crossing (because GifWrite
gets 4K bytes per call), and even for very large animated gifs, now at most one
malloc and one realloc is needed. This makes the loading of those gifs much
faster. (memory usage is still bad because of the 24bit color processing...)
* Renamed functions to be more consistent (GifInit, GifWrite, GifClose)
* Removed gif_write_ready, because it is not needed anymore because of the
streaming (4K per call), and because the parser is not limited to the buffer
size anyway.

Comment 8

[Alfred Kayser]

Attachment: AniGIF: visualisation trick: focus very strongly for at least 10 seconds...

Comment 9

[Alfred Kayser]

Attachment: Another testcase for Anim-gif

Comment 10

[Darin Fisher]

> * I left in the 'calloc' bailout, because it doesn't hurt, and can be be backup
> for the RecyclingAllocator...

on the contrary, it increases codesize even though it will practically never be
used.  seems like a bad choice to me.

be careful about adding more complexity to this patch.  it increases the barrier
to code review.

Comment 11

[Alfred Kayser]

Attachment: Per darin's comment, removed the fallback to 'calloc'

Comment 12

[Alfred Kayser]

Comment on attachment 168941 [details] [diff] [review]
Incorporated comments from Darin, and more malloc optimisation.

See latest patch for the review!

Comment 13

[ArronM (:paper)]

Comment on attachment 169278 [details] [diff] [review]
Per darin's comment, removed the fallback to 'calloc'

GIF2.h:114    int ipass;		  /* Interlace pass; Ranges 1-4 if
interlaced. */

Please modify this comment to explain 0 is non-interlaced.

+      /* Do we already have enough data in the accumulation
+	  buffer to satisfy the request ?  (This can happen
+	  after we transition from the gif_delay state.) */

This comment refers to a const that has been removed.

The memory allocation stuff will take me a bit longer to digest.  

Ultimately pav will have to decide whether it's wise to remove netscape
extension #2.  While I don't fully understand it myself, wouldn't it be
possible right now for a GIF to request that all its data be available before
the images is decoded?	Without the extension, the gif author would lose that
ability.  Please correct me if I misinterpreted what this extension is
accomplishing.

Comment 14

[Alfred Kayser]

Thanks for the review sofar.
I've assimilated the first two comments.

About the Netscape extension:
I've had a lot of thought and research on this.
It seems that there are no GIF images at all using this.
Furthermore, the extension is very rarely described.
No image creation applications are using this.
But the most important reason to remove it, is that
it is 'unsafe'. One can add this extension to an image, requesting
a very large 'read-ahead' (say about 2GB), which then is all allocated
and tried to filled from the stream, which may cause problems in the application
(and even OS).

So, this is a very strong case to remove it. It is not used, doesn't have any
visible impact, and can cause 'buffer overflow / memory overflow', when the
extension is misused. 

Comment 15

[Alfred Kayser]

Attachment: Incorporated comments from ArronM

Comment 16

[Stuart Parmenter]

I don't think we want to remove the netscape extension support.

Comment 17

[tor]

Comment on attachment 171477 [details] [diff] [review]
Incorporated comments from ArronM

Aaron, could you review this and let us know if you feel it might
be too risky to take right now as we're nearing the end of the 1.8 cycle?

Comment 18

[ArronM (:paper)]

Comment on attachment 171477 [details] [diff] [review]
Incorporated comments from ArronM

The sheer size and amount of changes the patch has is reason enough to say it's
definitely not for 1.8.

-r due to pavlov's comments.

Comment 19

[Alfred Kayser]

I can agree with postponing it after 1.8.

However I don't agree with the Netscape extension.
To make the earlier argument against this extension more clear:
using this extension, one can easily create a GIF image with a request to
buffer upto 4GB bytes before decoding it. This means that the GIF decoder will
never end the decoding, and tries to build up an holding buffer of that size.
I have not yet tested this, but it is very likely that this will surely crash
the application.
Furthermore, the net effect of this extension is gone, because of the streaming
towards the decoder. There is no usefull effect of it, and no image creation
program can produce this extension. It is not a standard extension, and only
documented as being proposed by Netscape around version Netscape 2.1, but it is
never formally released.

So, normally when it doesn't harm, we would leave such backwards compatibility
things such as this 'netscape extension' in. However, it can do serious harm, so
let's remove it.

Comment 20

[Christian :Biesinger (don't email me, ping me on IRC)]

>I have not yet tested this, but it is very likely that this will surely crash
>the application.

that would be a bug. mozilla should not crash if a memory allocation fails.

Comment 21

[Alfred Kayser]

Attachment: Test code to generate an GIF image with the NETSCAPE2.0 'wait_for_fullness' extension

Compile and run this. It takes an c:\tmp\error.gif and creates an
c:\tmp\error2.gif with the NETSCAPE2.0 wait_for_fullness extension inserted.

Comment 22

[Alfred Kayser]

Attachment: A GIF image with the NETSCAPE2.0 extension inserted

Comment 23

[Alfred Kayser]

I have tested the support of the NETSCAPE2.0 extension with the old code and the
new code. Luckely it doesn't crash mozilla but mozilla won't display the image
either.
With the new code, mozilla is able to correctly read, parse, and display the image.

IE, IrfanView, PaintshopPro can all load the extended gif image, but
mozilla/firefox refuses to display it at all (it does not even 'broken image' ) 

Further analysis of the code confirms me that the extension is not supported at
all, it doesn't work, and prevents the otherwise valid image to display.

So, let's remove something which is not working anyway, and prevent issues later
with this extension.  Anyway I didn't really remove it, I only changed it into a
'NOP'. 

So, requesting re-review, as all other comments have been incorporated.

Comment 24

[Alfred Kayser]

Comment on attachment 171477 [details] [diff] [review]
Incorporated comments from ArronM

Even not for 1.8, let's still review it.

Comment 25

[ArronM (:paper)]

Comment on attachment 171477 [details] [diff] [review]
Incorporated comments from ArronM

I agree it should be reviewed, but not by me.  This is definitely more of a
Stuart review, since he has concerns about the extension, and knows more about
the decoding process than I do.

Re-assigning review :)

Comment 26

[Alfred Kayser]

Added bug 105370 to the 'block' list, as the identified MLK (the calloc at
GIF2.cpp:1017) is fixed with this patch as well.

Comment 27

[Alfred Kayser]

Attachment: Updated version, using fixed buffer of holding block between GifWrite's

This patch saves even more code (now in total more than 5K on a windows
optimized build for just the GIF decoder).

The main difference with the last one, is that the whole 'gather' construct is
replaced with one 'hold' buffer of fixed size (3*256 bytes), and that instead
of increating the gathering in state engine, the entry and exit points of
GifWrite take care of 'hold' buffer, as the only function is to move not yet
parsed bytes from one GifWrite call to the next.

This also speeds up the parsing as in the old case between each state, the
gather_state was called upon, and now the state engine directly switches from
gif_image_header to the next valid state, if there are enough bytes in the
buffer. If not the remaining bytes are put in the hold, awaiting the next call
to GifWrite.

Also merged consume_comment with skip_block, as they did the same thing:
skipping the blocks... 

Tested with a wide range of static and animated gif files (upto 6MB).

Comment 28

[Alfred Kayser]

To stress the importancy of this patch:
* Not only it saves code and footprint, but it also speeds up the loading of
large animated GIFs.
* But even more importantly it reduces 7 dynamic allocated (and often
reallocated buffers to 3 (rowbuf, global_colormap and local_colormap) once
allocated per image (possibly enlarged for next frames).
* Even more: each GifWrite caused in the old situation at least one malloc and
one realloc for the 'gathering', now it is only one static buffer.
* Even more: local_colormap is now only allocated once and only enlarged when
needed for all frames within an animation.

So, this reduces memory fragmentation a lot, and even reduces the change on
MLK's. With the old code it does seem to happen sometimes (bug 105370).

Comment 29

[Alfred Kayser]

Comment on attachment 175330 [details] [diff] [review]
Updated version, using fixed buffer of holding block between GifWrite's

Moved review request to latest patch version.

Comment 30

[Alfred Kayser]

Attachment: Even more memory and code size optimization

Additional changes:
* Now also global_colormap is a fixed buffer, and directly copied into from the
input stream (saves copy through hold buffer)
* Also local_colormap is directly assembled in its (dynamically allocated)
colormap
* Remove BackgroundColor as it isn't used at all
* Optimized same function signatures

Some statistics:
		    Before			Alloc4
Startup 	    8 allocs, 17424 bytes	4 allocs, 17628 bytes
Loading dir:	    119 allocs, ± 17500 bytes	16 allocs, ±17700 bytes per
image
Loading aniGif.gif: 40 allocs, 17509 bytes	4 allocs, 17843 bytes
Loading tholen.gif  37 allocs, 19285 bytes	3 allocs, 19234 bytes

Note: Each alloc also some overhead, so the actual memory usage is much more 

In summary, each GIF decoding now takes at most 4 allocs (not counting the
allocations by gfxImageFrame and imgContainer), instead of 8 +
2*number_of_4K_input_stream_crossings + number_of_frames.

Some time measurements:
		    Before			Alloc4
Startup (loading throbber.gif):
		    21				6
Loading techno_moogle_dance_party_by_the_darkmoogle.gif:
		    1748			1291
Loading galaxy_anim_short.mov2.gif:	
		    237537			218299

Note, measured with PRTimeInterval on WinXP, so numbers are in itself
meaningless, but the difference is interesting: between 10% and 30% faster
image decoding.

Comment 31

[Alfred Kayser]

Comment on attachment 175923 [details] [diff] [review]
Even more memory and code size optimization

Moving review request to latest patch version. See also the included benchmark
data between the old situation and the latest patch version.

Comment 32

[tor]

Comment on attachment 175923 [details] [diff] [review]
Even more memory and code size optimization

You're combining too many changes into a single patch.	Mozilla's
gif decoder has been battle hardened by years of exposure, so
we take changes to it pretty seriously.  A patch doing lots of
unrelated changes makes it hard to give a full review.	Please
split your work into logical stages.

Comment 33

[Alfred Kayser]

Attachment: Do only the malloc optimisation.

Reverted to the level of 2005-01-17, as reviewed by Darin and ArronM.
This one should be 'easier' to review.

Comment 34

[tor]

Comment on attachment 175938 [details] [diff] [review]
Do only the malloc optimisation.

This version of the patch still combines your allocation changes with
modifications to the state machine and other miscellaneous code
tweaks.  While we like code cleanup, it should be seperated from other
changes.

Please don't feel as though you're being singled out for these sort of
comments; new mozilla contributors often run into this.  Unfortunately
the mozilla review process generates a bit of a viscious cycle -
reviews take a while, so contributors want to put more into their
patch to reduce the number of reviews they need to chase, which slows
the review, etc...

Comment 35

[Alfred Kayser]

Attachment: Now really just the malloc changes

This version only contains the following malloc changes:
* stack, prefix and suffix of the lzw decoding from alloc to array as part of 
gif_struct
* Moved RecyclingAllocator from gif2.cpp to nsGIFdecoder.cpp where it used for
the full gifstruct allocation, instead of three items stack, prefix and suffix.

* global_colormap as an array part of gif_struct: is always used, and never
larger than 768 bytes.
* mRGBLine and mAlphaLine: only REALLOC when it needs to be bigger instead of
always (generally it will be same or smaller (first frame is generally the
largests)).
* Remove 'request_buffer_fullness' as it doesn't work (image will not show up,
and see testcase above, and can potentially generate a very large memory
allocation (as large as the full image source file).
* Removed unused member 'control_extension' (only set once, never used).
* Changed a few bools into PRPackedBools (as asked by jst)

Comment 36

[Alfred Kayser]

Attachment: Two dirty patch lines removed...

Comment 37

[tor]

Comment on attachment 176044 [details] [diff] [review]
Two dirty patch lines removed...

>--- modules/libpr0n/decoders/gif/GIF2.cpp	9 Jun 2004 18:36:25 -0000	1.51
>+++ modules/libpr0n/decoders/gif/GIF2.cpp	2 Mar 2005 15:40:49 -0000
>+  // Clear out the structure, excluding the arrays
>+  memset(gs, 0, (int)((char*)&((gif_struct*)0)->stack) );

Include stddef.h and use "offsetof(gif_struct, stack)".

>@@ -406,20 +422,17 @@
> {
>   nsGIFDecoder2* decoder = NS_STATIC_CAST(nsGIFDecoder2*, aClientData);
>   PRUint32 bpr, abpr;
>+
>   // We have to delay allocation of the image frame until now because
>-  // we won't have control block info (transparency) until now. The conrol
>+  // we won't have control block info (transparency) until now. The control
>   // block of a GIF stream shows up after the image header since transparency
>   // is added in GIF89a and control blocks are how the extensions are done.
>   // How annoying.
>   if(! decoder->mImageFrame) {
>-    gfx_format format = gfxIFormats::RGB;
>-    if (decoder->mGIFStruct->is_transparent) {
>-      format = gfxIFormats::RGB_A1;
>-    }
>-
> #if defined(XP_WIN) || defined(XP_OS2) || defined(XP_BEOS) || defined(MOZ_WIDGET_PHOTON)
>-    // XXX this works...
>-    format += 1; // RGB to BGR
>+    gfx_format format = decoder->mGIFStruct->is_transparent ? gfxIFormats::BGR_A1 : gfxIFormats::BGR;
>+#else
>+    gfx_format format = decoder->mGIFStruct->is_transparent ? gfxIFormats::RGB_A1 : gfxIFormats::RGB;
> #endif
> 
>     // initalize the frame and append it to the container

Remove this chunk from your patch.

Comment 38

[Alfred Kayser]

Attachment: Comments from tor incorporated

Added the use of 'offsetof' (much nicer indeed),
and remove the patch chunk fixing the typo and the 'XXX this works' thing.

Comment 39

[Alfred Kayser]

Comment on attachment 176122 [details] [diff] [review]
Comments from tor incorporated

Note, the removal of '#include "prtypes.h" was not intentional, but it compiles
and work, but may be other platform will still require it?

Comment 40

[tor]

Comment on attachment 176122 [details] [diff] [review]
Comments from tor incorporated

>+    PRUint8   stack[MAX_BITS];      /* Base of decoder stack */
>+    PRUint16  prefix[MAX_BITS];
>+    PRUint8   suffix[MAX_BITS];
>+    PRUint8   global_colormap[3*MAX_COLORS];   /* Default colormap if local not supplied, 3 bytes for each color  */

Since MAX_BITS is odd, for maximum packing this should be reordered prefix,
global_colormap,
stack, suffix (flip last two to taste), with the appropriate corresponding
change to GIFInit.
sr=tor with that change.

Add -p to your diff options in the future.

Comment 41

[Alfred Kayser]

Attachment: With comments from TOR, and using cvs diff -u8pN

Changed order of arrays to: prefix, suffix, stack and global_colormap, as
prefix is the only one with even size, others are all odd.

Comment 42

[tor]

Checking in GIF2.cpp;
/cvsroot/mozilla/modules/libpr0n/decoders/gif/GIF2.cpp,v  <--  GIF2.cpp
new revision: 1.52; previous revision: 1.51
done
Checking in GIF2.h;
/cvsroot/mozilla/modules/libpr0n/decoders/gif/GIF2.h,v  <--  GIF2.h
new revision: 1.20; previous revision: 1.19
done
Checking in nsGIFDecoder2.cpp;
/cvsroot/mozilla/modules/libpr0n/decoders/gif/nsGIFDecoder2.cpp,v  <-- 
nsGIFDecoder2.cpp
new revision: 1.65; previous revision: 1.64
done
Checking in nsGIFDecoder2.h;
/cvsroot/mozilla/modules/libpr0n/decoders/gif/nsGIFDecoder2.h,v  <-- 
nsGIFDecoder2.h
new revision: 1.25; previous revision: 1.24
done

Comment 43

[Alfred Kayser]

Code is committed and verified to be working as designed

Comment 44

[ArronM (:paper)]

Good Job, Alfred Kayser.