From 35c7422649ee7a3d0eb4ebd32c997eeb45f81046 Mon Sep 17 00:00:00 2001 From: Jeremy Fitzhardinge Date: Wed, 2 May 2007 19:27:15 +0200 Subject: [PATCH] x86: deflate stack usage in lib/inflate.c 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 [] show_trace_log_lvl+0x1a/0x30 [] show_trace+0x12/0x14 [] dump_stack+0x16/0x18 [] do_IRQ+0x6d/0xd9 [] xen_evtchn_do_upcall+0x6e/0xa2 [] xen_hypervisor_callback+0x25/0x2c [] xen_restore_fl+0x27/0x29 [] _spin_unlock_irqrestore+0x4a/0x50 [] change_page_attr+0x577/0x584 [] kernel_map_pages+0x8d/0xb4 [] cache_alloc_refill+0x53f/0x632 [] __kmalloc+0xc1/0x10d [] malloc+0x10/0x12 [] huft_build+0x2a7/0x5fa [] inflate_fixed+0x91/0x136 [] unpack_to_rootfs+0x5f2/0x8c1 [] 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. Also, up the heap size for the kernel decompressor to deal with the extra allocation. Signed-off-by: Jeremy Fitzhardinge Signed-off-by: Andi Kleen Cc: Tim Yamin Cc: Andi Kleen Cc: Matt Mackall Cc: Ivan Kokshaysky Cc: Richard Henderson Cc: Russell King Cc: Ian Molton --- lib/inflate.c | 66 ++++++++++++++++++++++++++++++++++++++++++++--------------- 1 file changed, 49 insertions(+), 17 deletions(-) (limited to 'lib/inflate.c') diff --git a/lib/inflate.c b/lib/inflate.c index 6db6e98..88a22f4 100644 --- a/lib/inflate.c +++ b/lib/inflate.c @@ -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("h6f "); 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,10 +729,14 @@ STATIC int noinline INIT inflate_fixed(void) 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(" 1) { huft_free(tl); + free(l); DEBG(">"); return i; @@ -737,11 +767,13 @@ DEBG(" Date: Wed, 2 May 2007 19:27:15 +0200 Subject: [PATCH] x86-64: 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 Signed-off-by: Andi Kleen --- lib/inflate.c | 61 +++++++++++++++++++++++++++++++++++++++-------------------- 1 file changed, 41 insertions(+), 20 deletions(-) (limited to 'lib/inflate.c') diff --git a/lib/inflate.c b/lib/inflate.c index 88a22f4..845f91d 100644 --- a/lib/inflate.c +++ b/lib/inflate.c @@ -798,16 +798,19 @@ STATIC int noinline INIT inflate_dynamic(void) 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(" 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; + ret = 0; +out: + free(ll); + return ret; - underrun: - return 4; /* Input underrun */ +underrun: + ret = 4; /* Input underrun */ + goto out; } -- cgit v1.1