Skip to contentSkip to conversation

deflate inflate_dynamic too

PATCH In review Jeremy Fitzhardinge 3 participants 5 messages Apr 28, 2007 – May 7, 2007 Library code

lore
Share & tools
lore

Jeremy Fitzhardinge

author
#0 lore raw

PATCH 1/1 deflate inflate_dynamic too

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 <[email protected]>
---
 lib/inflate.c |   63 ++++++++++++++++++++++++++++++++++++++-------------------
 1 file changed, 42 insertions(+), 21 deletions(-)

===================================================================

lib/inflate.c +42 -21
@@ -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;
 }
#1 lore raw
Quoted 3 lines · 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".

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

Quoted 56 lines
Signed-off-by Jeremy Fitzhardinge <[email protected]>
---
 lib/inflate.c |   63 ++++++++++++++++++++++++++++++++++++++-------------------
 1 file changed, 42 insertions(+), 21 deletions(-)

===================================================================

lib/inflate.c +14 -7
@@ -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 ");

lib/inflate.c DEBG("dyn3 "); · line 884

Quoted 8 lines
lib/inflate.c +3 -2
@@ -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.

Signature · 1 line
Mathematics is the supreme nostalgia of our time.
#2 lore raw
In reply to Jeremy Fitzhardinge
Quoted 3 lines · 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".

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

author
#3 lore raw
Quoted 8 lines · H. Peter Anvin

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

#4 lore raw
Quoted 10 lines · Jeremy Fitzhardinge
Quoted 8 lines · H. Peter Anvin

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.

Quoted 6 lines

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