aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorJeremy Fitzhardinge <jeremy@goop.org>2007-05-02 13:27:15 -0400
committerAndi Kleen <andi@basil.nowhere.org>2007-05-02 13:27:15 -0400
commit35c7422649ee7a3d0eb4ebd32c997eeb45f81046 (patch)
tree8baebdb9aeb46844c7e9becc5a7699c47257f86d
parent4cdd9c8931767e1c56a51a1078d33a8c340f4405 (diff)
[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>
-rw-r--r--arch/alpha/boot/misc.c2
-rw-r--r--arch/arm/boot/compressed/misc.c2
-rw-r--r--arch/arm26/boot/compressed/misc.c2
-rw-r--r--arch/i386/boot/compressed/misc.c2
-rw-r--r--arch/x86_64/boot/compressed/misc.c2
-rw-r--r--lib/inflate.c66
6 files changed, 54 insertions, 22 deletions
diff --git a/arch/alpha/boot/misc.c b/arch/alpha/boot/misc.c
index 1d65adf5691e..c00646b25f6e 100644
--- a/arch/alpha/boot/misc.c
+++ b/arch/alpha/boot/misc.c
@@ -98,7 +98,7 @@ extern int end;
98static ulg free_mem_ptr; 98static ulg free_mem_ptr;
99static ulg free_mem_ptr_end; 99static ulg free_mem_ptr_end;
100 100
101#define HEAP_SIZE 0x2000 101#define HEAP_SIZE 0x3000
102 102
103#include "../../../lib/inflate.c" 103#include "../../../lib/inflate.c"
104 104
diff --git a/arch/arm/boot/compressed/misc.c b/arch/arm/boot/compressed/misc.c
index 283891c736c4..9b444022cb9b 100644
--- a/arch/arm/boot/compressed/misc.c
+++ b/arch/arm/boot/compressed/misc.c
@@ -239,7 +239,7 @@ extern int end;
239static ulg free_mem_ptr; 239static ulg free_mem_ptr;
240static ulg free_mem_ptr_end; 240static ulg free_mem_ptr_end;
241 241
242#define HEAP_SIZE 0x2000 242#define HEAP_SIZE 0x3000
243 243
244#include "../../../../lib/inflate.c" 244#include "../../../../lib/inflate.c"
245 245
diff --git a/arch/arm26/boot/compressed/misc.c b/arch/arm26/boot/compressed/misc.c
index f17f50e5516f..0714d19c5776 100644
--- a/arch/arm26/boot/compressed/misc.c
+++ b/arch/arm26/boot/compressed/misc.c
@@ -182,7 +182,7 @@ extern int end;
182static ulg free_mem_ptr; 182static ulg free_mem_ptr;
183static ulg free_mem_ptr_end; 183static ulg free_mem_ptr_end;
184 184
185#define HEAP_SIZE 0x2000 185#define HEAP_SIZE 0x3000
186 186
187#include "../../../../lib/inflate.c" 187#include "../../../../lib/inflate.c"
188 188
diff --git a/arch/i386/boot/compressed/misc.c b/arch/i386/boot/compressed/misc.c
index 1ce7017fd627..b28505c544c9 100644
--- a/arch/i386/boot/compressed/misc.c
+++ b/arch/i386/boot/compressed/misc.c
@@ -189,7 +189,7 @@ static void putstr(const char *);
189static unsigned long free_mem_ptr; 189static unsigned long free_mem_ptr;
190static unsigned long free_mem_end_ptr; 190static unsigned long free_mem_end_ptr;
191 191
192#define HEAP_SIZE 0x3000 192#define HEAP_SIZE 0x4000
193 193
194static char *vidmem = (char *)0xb8000; 194static char *vidmem = (char *)0xb8000;
195static int vidport; 195static int vidport;
diff --git a/arch/x86_64/boot/compressed/misc.c b/arch/x86_64/boot/compressed/misc.c
index fed1167159c3..f932b0e89096 100644
--- a/arch/x86_64/boot/compressed/misc.c
+++ b/arch/x86_64/boot/compressed/misc.c
@@ -189,7 +189,7 @@ static void putstr(const char *);
189static long free_mem_ptr; 189static long free_mem_ptr;
190static long free_mem_end_ptr; 190static long free_mem_end_ptr;
191 191
192#define HEAP_SIZE 0x6000 192#define HEAP_SIZE 0x7000
193 193
194static char *vidmem = (char *)0xb8000; 194static char *vidmem = (char *)0xb8000;
195static int vidport; 195static int vidport;
diff --git a/lib/inflate.c b/lib/inflate.c
index 6db6e98d1637..88a22f4a49df 100644
--- a/lib/inflate.c
+++ b/lib/inflate.c
@@ -292,7 +292,6 @@ STATIC int INIT huft_build(
292 oversubscribed set of lengths), and three if not enough memory. */ 292 oversubscribed set of lengths), and three if not enough memory. */
293{ 293{
294 unsigned a; /* counter for codes of length k */ 294 unsigned a; /* counter for codes of length k */
295 unsigned c[BMAX+1]; /* bit length count table */
296 unsigned f; /* i repeats in table every f entries */ 295 unsigned f; /* i repeats in table every f entries */
297 int g; /* maximum code length */ 296 int g; /* maximum code length */
298 int h; /* table level */ 297 int h; /* table level */
@@ -303,18 +302,33 @@ STATIC int INIT huft_build(
303 register unsigned *p; /* pointer into c[], b[], or v[] */ 302 register unsigned *p; /* pointer into c[], b[], or v[] */
304 register struct huft *q; /* points to current table */ 303 register struct huft *q; /* points to current table */
305 struct huft r; /* table entry for structure assignment */ 304 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 */
308 register int w; /* bits before this table == (l * h) */ 305 register int w; /* bits before this table == (l * h) */
309 unsigned x[BMAX+1]; /* bit offsets, then code stack */
310 unsigned *xp; /* pointer into x */ 306 unsigned *xp; /* pointer into x */
311 int y; /* number of dummy codes added */ 307 int y; /* number of dummy codes added */
312 unsigned z; /* number of entries in current table */ 308 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;
313 318
314DEBG("huft1 "); 319DEBG("huft1 ");
315 320
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
316 /* Generate counts for each bit length */ 330 /* Generate counts for each bit length */
317 memzero(c, sizeof(c)); 331 memzero(stk->c, sizeof(stk->c));
318 p = b; i = n; 332 p = b; i = n;
319 do { 333 do {
320 Tracecv(*p, (stderr, (n-i >= ' ' && n-i <= '~' ? "%c %d\n" : "0x%x %d\n"), 334 Tracecv(*p, (stderr, (n-i >= ' ' && n-i <= '~' ? "%c %d\n" : "0x%x %d\n"),
@@ -326,7 +340,8 @@ DEBG("huft1 ");
326 { 340 {
327 *t = (struct huft *)NULL; 341 *t = (struct huft *)NULL;
328 *m = 0; 342 *m = 0;
329 return 2; 343 ret = 2;
344 goto out;
330 } 345 }
331 346
332DEBG("huft2 "); 347DEBG("huft2 ");
@@ -351,10 +366,14 @@ DEBG("huft3 ");
351 366
352 /* Adjust last length count to fill out codes, if needed */ 367 /* Adjust last length count to fill out codes, if needed */
353 for (y = 1 << j; j < i; j++, y <<= 1) 368 for (y = 1 << j; j < i; j++, y <<= 1)
354 if ((y -= c[j]) < 0) 369 if ((y -= c[j]) < 0) {
355 return 2; /* bad input: more codes than bits */ 370 ret = 2; /* bad input: more codes than bits */
356 if ((y -= c[i]) < 0) 371 goto out;
357 return 2; 372 }
373 if ((y -= c[i]) < 0) {
374 ret = 2;
375 goto out;
376 }
358 c[i] += y; 377 c[i] += y;
359 378
360DEBG("huft4 "); 379DEBG("huft4 ");
@@ -428,7 +447,8 @@ DEBG1("3 ");
428 { 447 {
429 if (h) 448 if (h)
430 huft_free(u[0]); 449 huft_free(u[0]);
431 return 3; /* not enough memory */ 450 ret = 3; /* not enough memory */
451 goto out;
432 } 452 }
433DEBG1("4 "); 453DEBG1("4 ");
434 hufts += z + 1; /* track memory usage */ 454 hufts += z + 1; /* track memory usage */
@@ -492,7 +512,11 @@ DEBG("h6f ");
492DEBG("huft7 "); 512DEBG("huft7 ");
493 513
494 /* Return true (1) if we were given an incomplete table */ 514 /* 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;
496} 520}
497 521
498 522
@@ -705,10 +729,14 @@ STATIC int noinline INIT inflate_fixed(void)
705 struct huft *td; /* distance code table */ 729 struct huft *td; /* distance code table */
706 int bl; /* lookup bits for tl */ 730 int bl; /* lookup bits for tl */
707 int bd; /* lookup bits for td */ 731 int bd; /* lookup bits for td */
708 unsigned l[288]; /* length list for huft_build */ 732 unsigned *l; /* length list for huft_build */
709 733
710DEBG("<fix"); 734DEBG("<fix");
711 735
736 l = malloc(sizeof(*l) * 288);
737 if (l == NULL)
738 return 3; /* out of memory */
739
712 /* set up literal table */ 740 /* set up literal table */
713 for (i = 0; i < 144; i++) 741 for (i = 0; i < 144; i++)
714 l[i] = 8; 742 l[i] = 8;
@@ -719,9 +747,10 @@ DEBG("<fix");
719 for (; i < 288; i++) /* make a complete, but wrong code set */ 747 for (; i < 288; i++) /* make a complete, but wrong code set */
720 l[i] = 8; 748 l[i] = 8;
721 bl = 7; 749 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);
723 return i; 752 return i;
724 753 }
725 754
726 /* set up distance table */ 755 /* set up distance table */
727 for (i = 0; i < 30; i++) /* make an incomplete code set */ 756 for (i = 0; i < 30; i++) /* make an incomplete code set */
@@ -730,6 +759,7 @@ DEBG("<fix");
730 if ((i = huft_build(l, 30, 0, cpdist, cpdext, &td, &bd)) > 1) 759 if ((i = huft_build(l, 30, 0, cpdist, cpdext, &td, &bd)) > 1)
731 { 760 {
732 huft_free(tl); 761 huft_free(tl);
762 free(l);
733 763
734 DEBG(">"); 764 DEBG(">");
735 return i; 765 return i;
@@ -737,11 +767,13 @@ DEBG("<fix");
737 767
738 768
739 /* decompress until an end-of-block code */ 769 /* 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);
741 return 1; 772 return 1;
742 773 }
743 774
744 /* free the decoding tables, return */ 775 /* free the decoding tables, return */
776 free(l);
745 huft_free(tl); 777 huft_free(tl);
746 huft_free(td); 778 huft_free(td);
747 return 0; 779 return 0;