[PATCH] reduce large stack usage

[PATCH] reduce large stack usage

[Randy.Dunlap]

[-- Attachment #1: Type: text/plain, Size: 279 bytes --]

Hi,

This patch to 2.5.63 reduces stack usage in generate_default_upcase()
from 0x3d4 bytes to just noise (on x86).

The arrays are static so they are still private (hidden), but
now they aren't allocated on the stack and copied there for
temp use.

Please apply.

Thanks,
~Randy

[-- Attachment #2: ntfs_stack_2563.patch --]
[-- Type: text/plain, Size: 1843 bytes --]

patch_name:	ntfs_stack_2563.patch
patch_version:	2003-02-28.22:42:57
author:		Randy.Dunlap <rddunlap@osdl.org>
description:	ntfs: reduce function local stack usage from 0x3d4 bytes to just noise;
product:	Linux
product_versions: linux-2563
changelog:	_
URL:		_
requires:	_
conflicts:	_
maintainer:	Anton Altaparmakov <aia21@cantab.net>
diffstat:	=
 fs/ntfs/upcase.c |   10 +++++-----
 1 files changed, 5 insertions(+), 5 deletions(-)

diff -Naur ./fs/ntfs/upcase.c%NTSTK ./fs/ntfs/upcase.c
--- ./fs/ntfs/upcase.c%NTSTK	Mon Feb 24 11:05:05 2003
+++ ./fs/ntfs/upcase.c	Fri Feb 28 22:37:32 2003
@@ -26,9 +26,7 @@
 
 #include "ntfs.h"
 
-uchar_t *generate_default_upcase(void)
-{
-	const int uc_run_table[][3] = { /* Start, End, Add */
+static const int uc_run_table[][3] = { /* Start, End, Add */
 	{0x0061, 0x007B,  -32}, {0x0451, 0x045D, -80}, {0x1F70, 0x1F72,  74},
 	{0x00E0, 0x00F7,  -32}, {0x045E, 0x0460, -80}, {0x1F72, 0x1F76,  86},
 	{0x00F8, 0x00FF,  -32}, {0x0561, 0x0587, -48}, {0x1F76, 0x1F78, 100},
@@ -45,7 +43,7 @@
 	{0}
 	};
 
-	const int uc_dup_table[][2] = { /* Start, End */
+static const int uc_dup_table[][2] = { /* Start, End */
 	{0x0100, 0x012F}, {0x01A0, 0x01A6}, {0x03E2, 0x03EF}, {0x04CB, 0x04CC},
 	{0x0132, 0x0137}, {0x01B3, 0x01B7}, {0x0460, 0x0481}, {0x04D0, 0x04EB},
 	{0x0139, 0x0149}, {0x01CD, 0x01DD}, {0x0490, 0x04BF}, {0x04EE, 0x04F5},
@@ -55,7 +53,7 @@
 	{0}
 	};
 
-	const int uc_word_table[][2] = { /* Offset, Value */
+static const int uc_word_table[][2] = { /* Offset, Value */
 	{0x00FF, 0x0178}, {0x01AD, 0x01AC}, {0x01F3, 0x01F1}, {0x0269, 0x0196},
 	{0x0183, 0x0182}, {0x01B0, 0x01AF}, {0x0253, 0x0181}, {0x026F, 0x019C},
 	{0x0185, 0x0184}, {0x01B9, 0x01B8}, {0x0254, 0x0186}, {0x0272, 0x019D},
@@ -67,6 +65,8 @@
 	{0}
 	};
 
+uchar_t *generate_default_upcase(void)
+{
 	int i, r;
 	uchar_t *uc;
 

Re: [Linux-NTFS-Dev] [PATCH] reduce large stack usage

[Andrew Clausen]

Hi Randy,

On Fri, Feb 28, 2003 at 11:06:23PM -0800, Randy.Dunlap wrote:
> This patch to 2.5.63 reduces stack usage in generate_default_upcase()
> from 0x3d4 bytes to just noise (on x86).
> 
> The arrays are static so they are still private (hidden), but
> now they aren't allocated on the stack and copied there for
> temp use.

BTW, you can declare "local" variables inside a function as static,
which makes them "global", but locally scoped.  The code should be
basically equivalent, but perhaps more elegant...

i.e.:

 uchar_t *generate_default_upcase(void)
 {
-	const int uc_run_table[][3] = { /* Start, End, Add */
+static const int uc_run_table[][3] = { /* Start, End, Add */
 	{0x0061, 0x007B,  -32}, {0x0451, 0x045D, -80}, {0x1F70, 0x1F72,  74},
 	{0x00E0, 0x00F7,  -32}, {0x045E, 0x0460, -80}, {0x1F72, 0x1F76,  86},
 	{0x00F8, 0x00FF,  -32}, {0x0561, 0x0587, -48}, {0x1F76, 0x1F78, 100},

Cheers,
Andrew

Re: [Linux-NTFS-Dev] [PATCH] reduce large stack usage

[Randy.Dunlap]

> Hi Randy,
>
> On Fri, Feb 28, 2003 at 11:06:23PM -0800, Randy.Dunlap wrote:
>> This patch to 2.5.63 reduces stack usage in generate_default_upcase() from
>> 0x3d4 bytes to just noise (on x86).
>>
>> The arrays are static so they are still private (hidden), but
>> now they aren't allocated on the stack and copied there for
>> temp use.
>
> BTW, you can declare "local" variables inside a function as static, which
> makes them "global", but locally scoped.  The code should be basically
> equivalent, but perhaps more elegant...
>
> i.e.:
>
>  uchar_t *generate_default_upcase(void)
>  {
> -	const int uc_run_table[][3] = { /* Start, End, Add */
> +static const int uc_run_table[][3] = { /* Start, End, Add */
>  	{0x0061, 0x007B,  -32}, {0x0451, 0x045D, -80}, {0x1F70, 0x1F72,  74},
> {0x00E0, 0x00F7,  -32}, {0x045E, 0x0460, -80}, {0x1F72, 0x1F76,  86},
> {0x00F8, 0x00FF,  -32}, {0x0561, 0x0587, -48}, {0x1F76, 0x1F78, 100},
>
> Cheers,
> Andrew

Yes, of course.  I'll remake the patch unless someone else does.
(-ESLEEPY last night)

Thanks,
~Randy

Re: [PATCH] reduce large stack usage

[Arnd Bergmann]

Randy.Dunlap wrote:

> This patch to 2.5.63 reduces stack usage in generate_default_upcase()
> from 0x3d4 bytes to just noise (on x86).

Since you are already fixing stack usage bugs in several places, maybe
you are interested in this list. I have it from building 2.5.63 with 
allyesconfig on s390x with gcc-2.95.3. The twofish one is obviously
broken, and I suspect huft_build/inflate_dynamic are the cause of the
crashes I'm seeing during unpacking of initramfs.

nfs4 and reiserfs look suspicious as well, but I've never used either
of them on s390x, so I can't tell if they are likely to cause
real problems.

        Arnd <><

8832 twofish_setkey
1696 dohash
1680 huft_build
1680 huft_build
1544 aes_encrypt
1512 inflate_dynamic
1496 inflate_dynamic
1448 device_new_if
1360 inflate_fixed
1360 inflate_fixed
1344 br_ioctl_device
1312 elf_core_dump
1264 sctp_hash_digest
1256 aes_decrypt
1248 gss_pipe_downcall
1248 befs_warning
1248 befs_error
1248 befs_debug
1232 ciGetLeafPrefixKey
1216 nfs4_proc_rename
1192 nfs4_proc_link
1184 root_nfs_name
1184 conmode_default
1136 elf_core_dump
1128 nfsd4_proc_compound
1112 generate_default_upcase
1072 nlmclnt_proc
1016 do_open
1000 reiserfs_rename
992 reiserfs_delete_solid_item
992 nfs4_proc_symlink
992 nfs4_proc_mknod
992 nfs4_proc_mkdir
968 nlmclnt_reclaim
936 reiserfs_delete_item
912 reiserfs_cut_from_item
896 extract_entropy
888 sha512_transform
872 udf_add_entry
840 reiserfs_insert_item
832 tcp_v4_conn_request
832 reiserfs_paste_into_item
824 nfs4_proc_lookup
824 hfs_cat_move
816 udf_load_pvoldesc
816 semctl_main
792 sys_shmctl

generated from:
objdump --disassemble vmlinux |
        grep '\(^0\|aghi.%r15\)' |
        sed -e 's/^0.*<\(.*\)>:/\1/g' -e 's/^ .*-/: /g' |
        while read a b ; do
                if [ $a = : ] ; then
                        echo $b $name
                fi
                name=$a
        done |
        sort -rn |
        head -n 40

Re: [PATCH] reduce large stack usage

[Anders Gustafsson]

On Sun, Mar 02, 2003 at 03:11:40PM +0100, Arnd Bergmann wrote:
> broken, and I suspect huft_build/inflate_dynamic are the cause of the
> crashes I'm seeing during unpacking of initramfs.

I'm also seeing crashes when unpacking the initramfs if I enlarge it so it
takes more than a few (32kb) windows. I get crashes in a copy_from_user deep
down the callchain when it is doing the sys_write to a file in ramfs.

-- 
Anders Gustafsson - andersg@0x63.nu - http://0x63.nu/

Re: [PATCH] reduce large stack usage

[Arnd Bergmann]

On Sunday 02 March 2003 16:38, Anders Gustafsson wrote:

> I'm also seeing crashes when unpacking the initramfs if I enlarge it so it
> takes more than a few (32kb) windows. I get crashes in a copy_from_user
> deep down the callchain when it is doing the sys_write to a file in ramfs.

That's slightly different from what I am experiencing on s390x. Here,
I get a panic 'length error' after initramfs is unzipped. It always
seems like one byte less is counted than actually is inside the
archive.
OTOH, the result of a stack overflow is usually undefined, so it might
also be this problem.

	Arnd <><

Re: [PATCH] reduce large stack usage

[Manfred Spraul]

Arnd wrote:

> The twofish one is obviously
>broken, and I suspect huft_build/inflate_dynamic are the cause of the
>crashes I'm seeing during unpacking of initramfs.
>
What do you mean with broken? On i386, the function needs 32 byte stack 
+ the space for register saving.
It must be either a gcc bug, or a bug in your detection script - I don't 
see anything special in twofish_setkey.

--
    Manfred

Re: [PATCH] reduce large stack usage

[Arnd Bergmann]

On Sunday 02 March 2003 16:26, Manfred Spraul wrote:

> What do you mean with broken? On i386, the function needs 32 byte stack
> + the space for register saving.
> It must be either a gcc bug, or a bug in your detection script - I don't
> see anything special in twofish_setkey.

You are right that the code itself is not broken -- I did not read it 
properly at first. The stack frame gets small if I compile for s390x
with -fno-schedule-insn, so I suppose that optimization does
not work to well on this particular code. I'll try a different compiler
tomorrow.

I can verify the 32 bytes on i386 with both gcc-3.2 and gcc-3.3-snapshot.
However, when compiling i386 twofish with gcc-2.95, I get an 804 bytes
stack frame. Other architectures are probably somewhere in between
i386 and s390x here, so there should be done something about this.

	Arnd <><