ksh very slow compared to bash when running ghostscript's ./configure script

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

ksh very slow compared to bash when running ghostscript's ./configure script

Julian Smith
It looks like ksh runs much slower than bash with current Ghostscript's
./configure script - for me it takes 20m, compared with 45s under bash.

This is on OpenBSD 6.7 GENERIC.MP#1 amd64. [This kernel has visa@'s
wait4() patch (see recent 'gdb in uninterruptible wait' thread), but
the same problem also occurred last week with the release kernel,
GENERIC.MP#182).]

To reproduce:

    git clone https://git.ghostscript.com/ghostpdl.git
    cd ghostpdl
    AUTOCONF_VERSION=2.69 AUTOMAKE_VERSION=1.16 CONFIGURE_STYLE=gnu ./autogen.sh

This runs things like autoreconf, then does ./configure. It takes 20m
on my machine, seemingly getting stuck for a a long time after
outputting 'checking compiler/linker address santizer build warnings
support...' and consuming 80% cpu.


Modifying autogen.sh to use /usr/local/bin/bash instead of ksh when
running ./configure, like this:

====
diff --git a/autogen.sh b/autogen.sh
index 7a0783623..2f6624b10 100755
--- a/autogen.sh
+++ b/autogen.sh
@@ -50,4 +50,4 @@ else
        echo "running ./configure $@"
 fi
 
-$srcdir/configure "$@" && echo
+/usr/local/bin/bash $srcdir/configure "$@" && echo
====

- results in the above ./autogen.sh command completing in about 45s for
me. (this is with a clean tree again.)

I don't know what's causing this. Is there some algorithm inside ksh
that could be running into complexity issues somehow?


[A colleague reports that ksh on Linux doesn't run slowly. But i guess
ksh has diverged a lot on OpenBSD/Linux, so that's perhaps not too
surprising.]


Thanks,

- Jules


--
http://op59.net

Reply | Threaded
Open this post in threaded view
|

Re: ksh very slow compared to bash when running ghostscript's ./configure script

Theo Buehler-3
> I don't know what's causing this. Is there some algorithm inside ksh
> that could be running into complexity issues somehow?

Likely glob. Many glob implementations were found to suffer from
complexity issues: https://research.swtch.com/glob

The glob(3) in libc was fixed
https://github.com/openbsd/src/commit/5c36dd0c22429e7b00ed5df80ed1383807532b59
but ksh's builtin glog still has the issue.

A quick ktrace seems to confirm that (I terminated the shell after it
hung a while):

 58829 sh       5.883025 RET   getdents 1832/0x728
 58829 sh       40.637429 PSIG  SIGTERM caught handler=0x64287f47850 mask=0<>

This likely points to the readdir call in globit() before globit() recurses:
https://github.com/openbsd/src/blob/master/bin/ksh/eval.c#L1089-L1102

Reply | Threaded
Open this post in threaded view
|

Re: ksh very slow compared to bash when running ghostscript's ./configure script

Theo Buehler-3
On Wed, Jul 22, 2020 at 06:38:42PM +0200, Theo Buehler wrote:

> > I don't know what's causing this. Is there some algorithm inside ksh
> > that could be running into complexity issues somehow?
>
> Likely glob. Many glob implementations were found to suffer from
> complexity issues: https://research.swtch.com/glob
>
> The glob(3) in libc was fixed
> https://github.com/openbsd/src/commit/5c36dd0c22429e7b00ed5df80ed1383807532b59
> but ksh's builtin glog still has the issue.
>
> A quick ktrace seems to confirm that (I terminated the shell after it
> hung a while):
>
>  58829 sh       5.883025 RET   getdents 1832/0x728
>  58829 sh       40.637429 PSIG  SIGTERM caught handler=0x64287f47850 mask=0<>
>
> This likely points to the readdir call in globit() before globit() recurses:
> https://github.com/openbsd/src/blob/master/bin/ksh/eval.c#L1089-L1102

Well:

AC_LINK_IFELSE(
  [AC_LANG_PROGRAM([#include <stdio.h>], [
  return(0);
  ])],
  [CFLAGS_SANITIZE="$CFLAGS"], [CFLAGS_SANITIZE="****************ADDRESS_SANITIZER_NOT_SUPPORTED*********************"])

This works around the bug:

diff --git configure.ac configure.ac
index 0d22ad59b..f670bde1b 100644
--- configure.ac
+++ configure.ac
@@ -495,7 +495,7 @@ dnl check for sanitize build warnings support
 dnl ----------------------------
 AC_MSG_CHECKING([compiler/linker address santizer build warnings support])
 
-CFLAGS_SANITIZE_TRY="$CFLAGS_SANITIZE -W -Wall -Wno-unused-parameter -Wno-sign-compare -Wno-implicit-fallthrough -Wno-missing-field-initializers -Wno-shift-negative-value -Wno-old-style-declaration -Wno-unused-but-set-parameter"
+CFLAGS_SANITIZE_TRY="'$CFLAGS_SANITIZE' -W -Wall -Wno-unused-parameter -Wno-sign-compare -Wno-implicit-fallthrough -Wno-missing-field-initializers -Wno-shift-negative-value -Wno-old-style-declaration -Wno-unused-but-set-parameter"
 CFLAGS_SAVED="$CFLAGS"
 CFLAGS="$CFLAGS_SANITIZE_TRY"
 

Reply | Threaded
Open this post in threaded view
|

Re: ksh very slow compared to bash when running ghostscript's ./configure script

Theo Buehler-3
On Wed, Jul 22, 2020 at 07:05:31PM +0200, Theo Buehler wrote:
> This works around the bug:

And this might even be a correct fix:

diff --git configure.ac configure.ac
index 0d22ad59b..d27222459 100644
--- configure.ac
+++ configure.ac
@@ -483,7 +483,7 @@ AC_LINK_IFELSE(
   [AC_LANG_PROGRAM([#include <stdio.h>], [
   return(0);
   ])],
-  [CFLAGS_SANITIZE="$CFLAGS"], [CFLAGS_SANITIZE="****************ADDRESS_SANITIZER_NOT_SUPPORTED*********************"])
+  [CFLAGS_SANITIZE="$CFLAGS"], [CFLAGS_SANITIZE="'****************ADDRESS_SANITIZER_NOT_SUPPORTED*********************'"])
 
 CFLAGS="$CFLAGS_SAVED"
 

Reply | Threaded
Open this post in threaded view
|

Re: ksh very slow compared to bash when running ghostscript's ./configure script

Theo de Raadt-2
Wow.

We really don't live in the best of possible worlds.

Theo Buehler <[hidden email]> wrote:

> On Wed, Jul 22, 2020 at 07:05:31PM +0200, Theo Buehler wrote:
> > This works around the bug:
>
> And this might even be a correct fix:
>
> diff --git configure.ac configure.ac
> index 0d22ad59b..d27222459 100644
> --- configure.ac
> +++ configure.ac
> @@ -483,7 +483,7 @@ AC_LINK_IFELSE(
>    [AC_LANG_PROGRAM([#include <stdio.h>], [
>    return(0);
>    ])],
> -  [CFLAGS_SANITIZE="$CFLAGS"], [CFLAGS_SANITIZE="****************ADDRESS_SANITIZER_NOT_SUPPORTED*********************"])
> +  [CFLAGS_SANITIZE="$CFLAGS"], [CFLAGS_SANITIZE="'****************ADDRESS_SANITIZER_NOT_SUPPORTED*********************'"])
>  
>  CFLAGS="$CFLAGS_SAVED"
>  
>

Reply | Threaded
Open this post in threaded view
|

Re: ksh very slow compared to bash when running ghostscript's ./configure script

Todd C. Miller-3
In reply to this post by Theo Buehler-3
On Wed, 22 Jul 2020 18:38:42 +0200, Theo Buehler wrote:

> Likely glob. Many glob implementations were found to suffer from
> complexity issues: https://research.swtch.com/glob
>
> The glob(3) in libc was fixed
> https://github.com/openbsd/src/commit/5c36dd0c22429e7b00ed5df80ed1383807532b5
> 9
> but ksh's builtin glog still has the issue.

At the very least we should collapse consecutive stars.  This is a
separate issue from making gmatch() iterative.

 - todd

Index: bin/ksh/misc.c
===================================================================
RCS file: /cvs/src/bin/ksh/misc.c,v
retrieving revision 1.74
diff -u -p -u -r1.74 misc.c
--- bin/ksh/misc.c 7 Jul 2020 10:33:58 -0000 1.74
+++ bin/ksh/misc.c 22 Jul 2020 19:08:20 -0000
@@ -615,6 +615,9 @@ do_gmatch(const unsigned char *s, const
  break;
 
  case '*':
+ /* collapse consecutive stars */
+ while (ISMAGIC(p[0]) && p[1] == '*')
+ p += 2;
  if (p == pe)
  return 1;
  s--;

Reply | Threaded
Open this post in threaded view
|

Re: ksh very slow compared to bash when running ghostscript's ./configure script

Theo Buehler-3
On Wed, Jul 22, 2020 at 01:10:38PM -0600, Todd C. Miller wrote:

> On Wed, 22 Jul 2020 18:38:42 +0200, Theo Buehler wrote:
>
> > Likely glob. Many glob implementations were found to suffer from
> > complexity issues: https://research.swtch.com/glob
> >
> > The glob(3) in libc was fixed
> > https://github.com/openbsd/src/commit/5c36dd0c22429e7b00ed5df80ed1383807532b5
> > 9
> > but ksh's builtin glog still has the issue.
>
> At the very least we should collapse consecutive stars.  This is a
> separate issue from making gmatch() iterative.

Yes. This makes sense and fixes this issue.

ok tb

>
>  - todd
>
> Index: bin/ksh/misc.c
> ===================================================================
> RCS file: /cvs/src/bin/ksh/misc.c,v
> retrieving revision 1.74
> diff -u -p -u -r1.74 misc.c
> --- bin/ksh/misc.c 7 Jul 2020 10:33:58 -0000 1.74
> +++ bin/ksh/misc.c 22 Jul 2020 19:08:20 -0000
> @@ -615,6 +615,9 @@ do_gmatch(const unsigned char *s, const
>   break;
>  
>   case '*':
> + /* collapse consecutive stars */
> + while (ISMAGIC(p[0]) && p[1] == '*')
> + p += 2;
>   if (p == pe)
>   return 1;
>   s--;

Reply | Threaded
Open this post in threaded view
|

Re: ksh very slow compared to bash when running ghostscript's ./configure script

Julian Smith
In reply to this post by Theo Buehler-3
On Wed, 22 Jul 2020 19:09:41 +0200
Theo Buehler <[hidden email]> wrote:

> On Wed, Jul 22, 2020 at 07:05:31PM +0200, Theo Buehler wrote:
> > This works around the bug:  
>
> And this might even be a correct fix:
>
> diff --git configure.ac configure.ac
> index 0d22ad59b..d27222459 100644
> --- configure.ac
> +++ configure.ac
> @@ -483,7 +483,7 @@ AC_LINK_IFELSE(
>    [AC_LANG_PROGRAM([#include <stdio.h>], [
>    return(0);
>    ])],
> -  [CFLAGS_SANITIZE="$CFLAGS"],
> [CFLAGS_SANITIZE="****************ADDRESS_SANITIZER_NOT_SUPPORTED*********************"])
> +  [CFLAGS_SANITIZE="$CFLAGS"],
> [CFLAGS_SANITIZE="'****************ADDRESS_SANITIZER_NOT_SUPPORTED*********************'"])
>  CFLAGS="$CFLAGS_SAVED"


Ah yes, great, that fixes it independently of any improvement to ksh's
glob code. Many thanks.

I'll try to make this change to ghostpdl's main git repository in the
next few days.


Thanks,

- Jules

--
http://op59.net