[PATCH] deflate stack usage in lib/inflate.c

External Since: Nov 08, 2006 Posts: 1199

inflate_fixed() and huft_build() together use around 2.7k of stack. When
using 4k stacks, I saw stack overflows from interrupts arriving while
unpacking the root initrd:

do_IRQ: stack overflow: 384
[<c0106b64>] show_trace_log_lvl+0x1a/0x30
[<c01075e6>] show_trace+0x12/0x14
[<c010763f>] dump_stack+0x16/0x18
[<c0107ca4>] do_IRQ+0x6d/0xd9
[<c010202b>] xen_evtchn_do_upcall+0x6e/0xa2
[<c0106781>] xen_hypervisor_callback+0x25/0x2c
[<c010116c>] xen_restore_fl+0x27/0x29
[<c0330f63>] _spin_unlock_irqrestore+0x4a/0x50
[<c0117aab>] change_page_attr+0x577/0x584
[<c0117b45>] kernel_map_pages+0x8d/0xb4
[<c016a314>] cache_alloc_refill+0x53f/0x632
[<c016a6c2>] __kmalloc+0xc1/0x10d
[<c0463d34>] malloc+0x10/0x12
[<c04641c1>] huft_build+0x2a7/0x5fa
[<c04645a5>] inflate_fixed+0x91/0x136
[<c04657e2>] unpack_to_rootfs+0x5f2/0x8c1
[<c0465acf>] populate_rootfs+0x1e/0xe4

(This was under Xen, but there's no reason it couldn't happen on bare
hardware.)

This patch mallocs the local variables, thereby reducing the stack
usage to sane levels.

Signed-off-by: Jeremy Fitzhardinge <jeremy DeleteThis @xensource.com>
Cc: Tim Yamin <plasmaroo DeleteThis @gentoo.org>

diff -r 4a30275bd596 lib/inflate.c
--- a/lib/inflate.c Wed Apr 11 17:28:10 2007 -0700
+++ b/lib/inflate.c Thu Apr 12 00:45:35 2007 -0700
@@ -292,7 +292,6 @@ STATIC int INIT huft_build(
oversubscribed set of lengths), and three if not enough memory. */
{
unsigned a; /* counter for codes of length k */
- unsigned c[BMAX+1]; /* bit length count table */
unsigned f; /* i repeats in table every f entries */
int g; /* maximum code length */
int h; /* table level */
@@ -303,18 +302,33 @@ STATIC int INIT huft_build(
register unsigned *p; /* pointer into c[], b[], or v[] */
register struct huft *q; /* points to current table */
struct huft r; /* table entry for structure assignment */
- struct huft *u[BMAX]; /* table stack */
- unsigned v[N_MAX]; /* values in order of bit length */
register int w; /* bits before this table == (l * h) */
- unsigned x[BMAX+1]; /* bit offsets, then code stack */
unsigned *xp; /* pointer into x */
int y; /* number of dummy codes added */
unsigned z; /* number of entries in current table */
+ struct {
+ unsigned c[BMAX+1]; /* bit length count table */
+ struct huft *u[BMAX]; /* table stack */
+ unsigned v[N_MAX]; /* values in order of bit length */
+ unsigned x[BMAX+1]; /* bit offsets, then code stack */
+ } *stk;
+ unsigned *c, *v, *x;
+ struct huft **u;
+ int ret;

DEBG("huft1 ");

+ stk = malloc(sizeof(*stk));
+ if (stk == NULL)
+ return 3; /* out of memory */
+
+ c = stk->c;
+ v = stk->v;
+ x = stk->x;
+ u = stk->u;
+
/* Generate counts for each bit length */
- memzero(c, sizeof(c));
+ memzero(stk->c, sizeof(stk->c));
p = b; i = n;
do {
Tracecv(*p, (stderr, (n-i >= ' ' && n-i <= '~' ? "%c %d\n" : "0x%x %d\n"),
@@ -326,7 +340,8 @@ DEBG("huft1 ");
{
*t = (struct huft *)NULL;
*m = 0;
- return 2;
+ ret = 2;
+ goto out;
}

DEBG("huft2 ");
@@ -351,10 +366,14 @@ DEBG("huft3 ");

/* Adjust last length count to fill out codes, if needed */
for (y = 1 << j; j < i; j++, y <<= 1)
- if ((y -= c[j]) < 0)
- return 2; /* bad input: more codes than bits */
- if ((y -= c[i]) < 0)
- return 2;
+ if ((y -= c[j]) < 0) {
+ ret = 2; /* bad input: more codes than bits */
+ goto out;
+ }
+ if ((y -= c[i]) < 0) {
+ ret = 2;
+ goto out;
+ }
c[i] += y;

DEBG("huft4 ");
@@ -428,7 +447,8 @@ DEBG1("3 ");
{
if (h)
huft_free(u[0]);
- return 3; /* not enough memory */
+ ret = 3; /* not enough memory */
+ goto out;
}
DEBG1("4 ");
hufts += z + 1; /* track memory usage */
@@ -492,7 +512,11 @@ DEBG("huft7 ");
DEBG("huft7 ");

/* Return true (1) if we were given an incomplete table */
- return y != 0 && g != 1;
+ ret = y != 0 && g != 1;
+
+ out:
+ free(stk);
+ return ret;
}

@@ -705,9 +729,13 @@ STATIC int noinline INIT inflate_fixed(v
struct huft *td; /* distance code table */
int bl; /* lookup bits for tl */
int bd; /* lookup bits for td */
- unsigned l[288]; /* length list for huft_build */
+ unsigned *l; /* length list for huft_build */

DEBG("<fix");
+
+ l = malloc(sizeof(*l) * 288);
+ if (l == NULL)
+ return 3; /* out of memory */

/* set up literal table */
for (i = 0; i < 144; i++)
@@ -719,9 +747,10 @@ DEBG("<fix");
for (; i < 288; i++) /* make a complete, but wrong code set */
l[i] = 8;
bl = 7;
- if ((i = huft_build(l, 288, 257, cplens, cplext, &tl, &bl)) != 0)
+ if ((i = huft_build(l, 288, 257, cplens, cplext, &tl, &bl)) != 0) {
+ free(l);
return i;
-
+ }

/* set up distance table */
for (i = 0; i < 30; i++) /* make an incomplete code set */
@@ -730,6 +759,7 @@ DEBG("<fix");
if ((i = huft_build(l, 30, 0, cpdist, cpdext, &td, &bd)) > 1)
{
huft_free(tl);
+ free(l);

DEBG(">");
return i;
@@ -737,11 +767,13 @@ DEBG("<fix");

/* decompress until an end-of-block code */
- if (inflate_codes(tl, td, bl, bd))
+ if (inflate_codes(tl, td, bl, bd)) {
+ free(l);
return 1;
-
+ }

/* free the decoding tables, return */
+ free(l);
huft_free(tl);
huft_free(td);
return 0;

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo DeleteThis @vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

External Since: Oct 30, 2006 Posts: 1072

> (This was under Xen, but there's no reason it couldn't happen on bare
> hardware.)

Hmm, does Xen perhaps not use interrupt stacks? Normally 2.7k should be still
green as long as there are not too many functions above/below it.

-Andi
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo.RemoveThis@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/