Skip to content

Commit 35c7422

Browse files
jsgfAndi Kleen
jsgf
authored and
Andi Kleen
committed
[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 [<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. Also, up the heap size for the kernel decompressor to deal with the extra allocation. Signed-off-by: Jeremy Fitzhardinge <jeremy@xensource.com> Signed-off-by: Andi Kleen <ak@suse.de> Cc: Tim Yamin <plasmaroo@gentoo.org> Cc: Andi Kleen <ak@suse.de> Cc: Matt Mackall <mpm@selenic.com> Cc: Ivan Kokshaysky <ink@jurassic.park.msu.ru> Cc: Richard Henderson <rth@twiddle.net> Cc: Russell King <rmk@arm.linux.org.uk> Cc: Ian Molton <spyro@f2s.com>
1 parent 4cdd9c8 commit 35c7422

6 files changed

Lines changed: 54 additions & 22 deletions

File tree

‎arch/alpha/boot/misc.c‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -98,7 +98,7 @@ extern int end;
9898
static ulg free_mem_ptr;
9999
static ulg free_mem_ptr_end;
100100

101-
#define HEAP_SIZE 0x2000
101+
#define HEAP_SIZE 0x3000
102102

103103
#include "../../../lib/inflate.c"
104104

‎arch/arm/boot/compressed/misc.c‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -239,7 +239,7 @@ extern int end;
239239
static ulg free_mem_ptr;
240240
static ulg free_mem_ptr_end;
241241

242-
#define HEAP_SIZE 0x2000
242+
#define HEAP_SIZE 0x3000
243243

244244
#include "../../../../lib/inflate.c"
245245

‎arch/arm26/boot/compressed/misc.c‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -182,7 +182,7 @@ extern int end;
182182
static ulg free_mem_ptr;
183183
static ulg free_mem_ptr_end;
184184

185-
#define HEAP_SIZE 0x2000
185+
#define HEAP_SIZE 0x3000
186186

187187
#include "../../../../lib/inflate.c"
188188

‎arch/i386/boot/compressed/misc.c‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -189,7 +189,7 @@ static void putstr(const char *);
189189
static unsigned long free_mem_ptr;
190190
static unsigned long free_mem_end_ptr;
191191

192-
#define HEAP_SIZE 0x3000
192+
#define HEAP_SIZE 0x4000
193193

194194
static char *vidmem = (char *)0xb8000;
195195
static int vidport;

‎arch/x86_64/boot/compressed/misc.c‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -189,7 +189,7 @@ static void putstr(const char *);
189189
static long free_mem_ptr;
190190
static long free_mem_end_ptr;
191191

192-
#define HEAP_SIZE 0x6000
192+
#define HEAP_SIZE 0x7000
193193

194194
static char *vidmem = (char *)0xb8000;
195195
static int vidport;

‎lib/inflate.c‎

Lines changed: 49 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -292,7 +292,6 @@ STATIC int INIT huft_build(
292292
oversubscribed set of lengths), and three if not enough memory. */
293293
{
294294
unsigned a; /* counter for codes of length k */
295-
unsigned c[BMAX+1]; /* bit length count table */
296295
unsigned f; /* i repeats in table every f entries */
297296
int g; /* maximum code length */
298297
int h; /* table level */
@@ -303,18 +302,33 @@ STATIC int INIT huft_build(
303302
register unsigned *p; /* pointer into c[], b[], or v[] */
304303
register struct huft *q; /* points to current table */
305304
struct huft r; /* table entry for structure assignment */
306-
struct huft *u[BMAX]; /* table stack */
307-
unsigned v[N_MAX]; /* values in order of bit length */
308305
register int w; /* bits before this table == (l * h) */
309-
unsigned x[BMAX+1]; /* bit offsets, then code stack */
310306
unsigned *xp; /* pointer into x */
311307
int y; /* number of dummy codes added */
312308
unsigned z; /* number of entries in current table */
309+
struct {
310+
unsigned c[BMAX+1]; /* bit length count table */
311+
struct huft *u[BMAX]; /* table stack */
312+
unsigned v[N_MAX]; /* values in order of bit length */
313+
unsigned x[BMAX+1]; /* bit offsets, then code stack */
314+
} *stk;
315+
unsigned *c, *v, *x;
316+
struct huft **u;
317+
int ret;
313318

314319
DEBG("huft1 ");
315320

321+
stk = malloc(sizeof(*stk));
322+
if (stk == NULL)
323+
return 3; /* out of memory */
324+
325+
c = stk->c;
326+
v = stk->v;
327+
x = stk->x;
328+
u = stk->u;
329+
316330
/* Generate counts for each bit length */
317-
memzero(c, sizeof(c));
331+
memzero(stk->c, sizeof(stk->c));
318332
p = b; i = n;
319333
do {
320334
Tracecv(*p, (stderr, (n-i >= ' ' && n-i <= '~' ? "%c %d\n" : "0x%x %d\n"),
@@ -326,7 +340,8 @@ DEBG("huft1 ");
326340
{
327341
*t = (struct huft *)NULL;
328342
*m = 0;
329-
return 2;
343+
ret = 2;
344+
goto out;
330345
}
331346

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

352367
/* Adjust last length count to fill out codes, if needed */
353368
for (y = 1 << j; j < i; j++, y <<= 1)
354-
if ((y -= c[j]) < 0)
355-
return 2; /* bad input: more codes than bits */
356-
if ((y -= c[i]) < 0)
357-
return 2;
369+
if ((y -= c[j]) < 0) {
370+
ret = 2; /* bad input: more codes than bits */
371+
goto out;
372+
}
373+
if ((y -= c[i]) < 0) {
374+
ret = 2;
375+
goto out;
376+
}
358377
c[i] += y;
359378

360379
DEBG("huft4 ");
@@ -428,7 +447,8 @@ DEBG1("3 ");
428447
{
429448
if (h)
430449
huft_free(u[0]);
431-
return 3; /* not enough memory */
450+
ret = 3; /* not enough memory */
451+
goto out;
432452
}
433453
DEBG1("4 ");
434454
hufts += z + 1; /* track memory usage */
@@ -492,7 +512,11 @@ DEBG("h6f ");
492512
DEBG("huft7 ");
493513

494514
/* Return true (1) if we were given an incomplete table */
495-
return y != 0 && g != 1;
515+
ret = y != 0 && g != 1;
516+
517+
out:
518+
free(stk);
519+
return ret;
496520
}
497521

498522

@@ -705,10 +729,14 @@ STATIC int noinline INIT inflate_fixed(void)
705729
struct huft *td; /* distance code table */
706730
int bl; /* lookup bits for tl */
707731
int bd; /* lookup bits for td */
708-
unsigned l[288]; /* length list for huft_build */
732+
unsigned *l; /* length list for huft_build */
709733

710734
DEBG("<fix");
711735

736+
l = malloc(sizeof(*l) * 288);
737+
if (l == NULL)
738+
return 3; /* out of memory */
739+
712740
/* set up literal table */
713741
for (i = 0; i < 144; i++)
714742
l[i] = 8;
@@ -719,9 +747,10 @@ DEBG("<fix");
719747
for (; i < 288; i++) /* make a complete, but wrong code set */
720748
l[i] = 8;
721749
bl = 7;
722-
if ((i = huft_build(l, 288, 257, cplens, cplext, &tl, &bl)) != 0)
750+
if ((i = huft_build(l, 288, 257, cplens, cplext, &tl, &bl)) != 0) {
751+
free(l);
723752
return i;
724-
753+
}
725754

726755
/* set up distance table */
727756
for (i = 0; i < 30; i++) /* make an incomplete code set */
@@ -730,18 +759,21 @@ DEBG("<fix");
730759
if ((i = huft_build(l, 30, 0, cpdist, cpdext, &td, &bd)) > 1)
731760
{
732761
huft_free(tl);
762+
free(l);
733763

734764
DEBG(">");
735765
return i;
736766
}
737767

738768

739769
/* decompress until an end-of-block code */
740-
if (inflate_codes(tl, td, bl, bd))
770+
if (inflate_codes(tl, td, bl, bd)) {
771+
free(l);
741772
return 1;
742-
773+
}
743774

744775
/* free the decoding tables, return */
776+
free(l);
745777
huft_free(tl);
746778
huft_free(td);
747779
return 0;

0 commit comments

Comments
 (0)