[PATCH] deflate inflate_dynamic too

[PATCH] deflate inflate_dynamic too

[Jeremy Fitzhardinge]

inflate_dynamic() has piggy stack usage too, so heap allocate it too.
I'm not sure it actually gets used, but it shows up large in "make
checkstack".

Signed-off-by: Jeremy Fitzhardinge <jeremy@xensource.com>

---
 lib/inflate.c |   63 ++++++++++++++++++++++++++++++++++++++-------------------
 1 file changed, 42 insertions(+), 21 deletions(-)

===================================================================
--- a/lib/inflate.c
+++ b/lib/inflate.c
@@ -798,15 +798,18 @@ STATIC int noinline INIT inflate_dynamic
   unsigned nb;          /* number of bit length codes */
   unsigned nl;          /* number of literal/length codes */
   unsigned nd;          /* number of distance codes */
-#ifdef PKZIP_BUG_WORKAROUND
-  unsigned ll[288+32];  /* literal/length and distance code lengths */
-#else
-  unsigned ll[286+30];  /* literal/length and distance code lengths */
-#endif
+  unsigned *ll;         /* literal/length and distance code lengths */
   register ulg b;       /* bit buffer */
   register unsigned k;  /* number of bits in bit buffer */
+  int ret;
 
 DEBG("<dyn");
+
+#ifdef PKZIP_BUG_WORKAROUND
+  ll = malloc(sizeof(*ll) * (288+32));  /* literal/length and distance code lengths */
+#else
+  ll = malloc(sizeof(*ll) * (286+30));  /* literal/length and distance code lengths */
+#endif
 
   /* make local bit buffer */
   b = bb;
@@ -828,7 +831,10 @@ DEBG("<dyn");
 #else
   if (nl > 286 || nd > 30)
 #endif
-    return 1;                   /* bad lengths */
+  {
+    ret = 1;             /* bad lengths */
+    goto out;
+  }
 
 DEBG("dyn1 ");
 
@@ -850,7 +856,8 @@ DEBG("dyn2 ");
   {
     if (i == 1)
       huft_free(tl);
-    return i;                   /* incomplete code set */
+    ret = i;                   /* incomplete code set */
+    goto out;
   }
 
 DEBG("dyn3 ");
@@ -872,8 +879,10 @@ DEBG("dyn3 ");
       NEEDBITS(2)
       j = 3 + ((unsigned)b & 3);
       DUMPBITS(2)
-      if ((unsigned)i + j > n)
-        return 1;
+      if ((unsigned)i + j > n) {
+        ret = 1;
+	goto out;
+      }
       while (j--)
         ll[i++] = l;
     }
@@ -882,8 +891,10 @@ DEBG("dyn3 ");
       NEEDBITS(3)
       j = 3 + ((unsigned)b & 7);
       DUMPBITS(3)
-      if ((unsigned)i + j > n)
-        return 1;
+      if ((unsigned)i + j > n) {
+        ret = 1;
+	goto out;
+      }
       while (j--)
         ll[i++] = 0;
       l = 0;
@@ -893,8 +904,10 @@ DEBG("dyn3 ");
       NEEDBITS(7)
       j = 11 + ((unsigned)b & 0x7f);
       DUMPBITS(7)
-      if ((unsigned)i + j > n)
-        return 1;
+      if ((unsigned)i + j > n) {
+        ret = 1;
+	goto out;
+      }
       while (j--)
         ll[i++] = 0;
       l = 0;
@@ -923,7 +936,8 @@ DEBG("dyn5b ");
       error("incomplete literal tree");
       huft_free(tl);
     }
-    return i;                   /* incomplete code set */
+    ret = i;                   /* incomplete code set */
+    goto out;
   }
 DEBG("dyn5c ");
   bd = dbits;
@@ -939,15 +953,18 @@ DEBG("dyn5d ");
       huft_free(td);
     }
     huft_free(tl);
-    return i;                   /* incomplete code set */
+    ret = i;                   /* incomplete code set */
+    goto out;
 #endif
   }
 
 DEBG("dyn6 ");
 
   /* decompress until an end-of-block code */
-  if (inflate_codes(tl, td, bl, bd))
-    return 1;
+  if (inflate_codes(tl, td, bl, bd)) {
+    ret = 1;
+    goto out;
+  }
 
 DEBG("dyn7 ");
 
@@ -956,10 +973,14 @@ DEBG("dyn7 ");
   huft_free(td);
 
   DEBG(">");
-  return 0;
-
- underrun:
-  return 4;			/* Input underrun */
+  ret = 0;
+out:
+  free(ll);
+  return ret;
+
+underrun:
+  ret = 4;			/* Input underrun */
+  goto out;
 }
 
 

Re: [PATCH] deflate inflate_dynamic too

[Matt Mackall]

On Fri, Apr 27, 2007 at 07:20:07PM -0700, Jeremy Fitzhardinge wrote:
> inflate_dynamic() has piggy stack usage too, so heap allocate it too.
> I'm not sure it actually gets used, but it shows up large in "make
> checkstack".

Might as well drop the PKZIP bit while we're at it. No one's ever
built a zimage with PKZIP.

> Signed-off-by: Jeremy Fitzhardinge <jeremy@xensource.com>
> 
> ---
>  lib/inflate.c |   63 ++++++++++++++++++++++++++++++++++++++-------------------
>  1 file changed, 42 insertions(+), 21 deletions(-)
> 
> ===================================================================
> --- a/lib/inflate.c
> +++ b/lib/inflate.c
> @@ -798,15 +798,18 @@ STATIC int noinline INIT inflate_dynamic
>    unsigned nb;          /* number of bit length codes */
>    unsigned nl;          /* number of literal/length codes */
>    unsigned nd;          /* number of distance codes */
> -#ifdef PKZIP_BUG_WORKAROUND
> -  unsigned ll[288+32];  /* literal/length and distance code lengths */
> -#else
> -  unsigned ll[286+30];  /* literal/length and distance code lengths */
> -#endif
> +  unsigned *ll;         /* literal/length and distance code lengths */
>    register ulg b;       /* bit buffer */
>    register unsigned k;  /* number of bits in bit buffer */
> +  int ret;
>  
>  DEBG("<dyn");
> +
> +#ifdef PKZIP_BUG_WORKAROUND
> +  ll = malloc(sizeof(*ll) * (288+32));  /* literal/length and distance code lengths */
> +#else
> +  ll = malloc(sizeof(*ll) * (286+30));  /* literal/length and distance code lengths */
> +#endif
>  
>    /* make local bit buffer */
>    b = bb;
> @@ -828,7 +831,10 @@ DEBG("<dyn");
>  #else
>    if (nl > 286 || nd > 30)
>  #endif
> -    return 1;                   /* bad lengths */
> +  {
> +    ret = 1;             /* bad lengths */
> +    goto out;
> +  }
>  
>  DEBG("dyn1 ");
>  
> @@ -850,7 +856,8 @@ DEBG("dyn2 ");
>    {
>      if (i == 1)
>        huft_free(tl);
> -    return i;                   /* incomplete code set */
> +    ret = i;                   /* incomplete code set */
> +    goto out;
>    }
>  
>  DEBG("dyn3 ");
> @@ -872,8 +879,10 @@ DEBG("dyn3 ");
>        NEEDBITS(2)
>        j = 3 + ((unsigned)b & 3);
>        DUMPBITS(2)
> -      if ((unsigned)i + j > n)
> -        return 1;
> +      if ((unsigned)i + j > n) {
> +        ret = 1;
> +	goto out;

Heh. Anti-tab damage.

-- 
Mathematics is the supreme nostalgia of our time.

Re: [PATCH] deflate inflate_dynamic too

[H. Peter Anvin]

Jeremy Fitzhardinge wrote:
> inflate_dynamic() has piggy stack usage too, so heap allocate it too.
> I'm not sure it actually gets used, but it shows up large in "make
> checkstack".

It might be worth reverting some of the code back to the zlib original.
 The use of stack allocations here is actually a Linux divergence from
zlib (done by Linus), in order to reduce the number of dynamic allocations.

In general, the use of dynamic allocations is highly dangerous, because
any time you have dynamic allocations you have the choice of either
sleeping or failing, unless you have a pre-reserved memory pool.

	-hpa

Re: [PATCH] deflate inflate_dynamic too

[Jeremy Fitzhardinge]

H. Peter Anvin wrote:
> It might be worth reverting some of the code back to the zlib original.
>  The use of stack allocations here is actually a Linux divergence from
> zlib (done by Linus), in order to reduce the number of dynamic allocations.
>
> In general, the use of dynamic allocations is highly dangerous, because
> any time you have dynamic allocations you have the choice of either
> sleeping or failing, unless you have a pre-reserved memory pool.
>   

Well, every time this code is instantiated, it gets its own malloc/free
definitions, so they can decide how to handle the dynamic allocations. 
Seems better than assuming that every caller will have enough stack
space.  If you want to approximate that, it would be easy enough to have
a stack-like malloc/free, in which freeing the last allocation will
always release space.

    J

Re: [PATCH] deflate inflate_dynamic too

[H. Peter Anvin]

Jeremy Fitzhardinge wrote:
> H. Peter Anvin wrote:
>> It might be worth reverting some of the code back to the zlib original.
>>  The use of stack allocations here is actually a Linux divergence from
>> zlib (done by Linus), in order to reduce the number of dynamic allocations.
>>
>> In general, the use of dynamic allocations is highly dangerous, because
>> any time you have dynamic allocations you have the choice of either
>> sleeping or failing, unless you have a pre-reserved memory pool.
>>   
> 
> Well, every time this code is instantiated, it gets its own malloc/free
> definitions, so they can decide how to handle the dynamic allocations. 
> Seems better than assuming that every caller will have enough stack
> space.  If you want to approximate that, it would be easy enough to have
> a stack-like malloc/free, in which freeing the last allocation will
> always release space.

Indeed, however, the point still holds:

- Going to something more like the upstream zlib code makes it
worthwhile to see whatever else should be merged;
- Users must be audited for correctness.

In particular, it would be good to have a "preallocate me enough memory
so it can be guaranteed that this will succeed" operation.

	-hpa