Upcoming /bin/sh (mostly internal) change

[Robert Elz <kre%munnari.OZ.AU@localhost>]

I am planning on changing the implementation of sh's $(( ))
(arithmetic expression evaluation) from our current (and original)
yacc/lex version, to (more or less) the code that FreeBSD use
these days (which their repo says that they took from dash) which is
a hand written recursive descent parser & evaluator.

Doing this will give us full posix conformance (which means adding the
assignment operators to what we have now - closing PR bin/50958).

It also turns out to make the shell noticeably smaller ...  (on amd64)

   text    data     bss     dec     hex filename
 147030    5628    8800  161458   276b2 /bin/sh-new1
 147094    5628    8800  161522   276f2 /bin/sh-new2
 157835    5664    9032  172531   2a1f3 /bin/sh-old

I'll explain new1 vs new2 a little lower, but they're both the new code,
sh-old is what is in current right now.

The file sizes also get smaller...  (still amd64)

netbsd# ls -ls /bin/sh-*
192 -r-xr-xr-x  2 root  wheel  181360 Mar 16 19:11 /bin/sh-new1
192 -r-xr-xr-x  1 root  wheel  181360 Mar 16 19:33 /bin/sh-new2
200 -r-xr-xr-x  1 root  wheel  196256 Mar 16 17:35 /bin/sh-old

I didn't look to see how much smaller /rescue/whatever gets, nor what
difference it makes to the SMALL sh's that are on the ramdisks, but I'd
expect something similar (there's nothing in any of this that could be
shared with anything else, and none of it is affected by SMALL.)

I did some basic timing tests to see if the new code was faster/slower/...
to what we have now.   These run on an amd64 XEN DomU (7.99.65 kernel)
with the rest of the system running background noise (munnari.OZ.AU runs
its mailer, and DNS server, on another DomU on the same system).  The test
system was doing nothing else at all (and probably had at least one
core cpu to itself.)

For a run of the sh ATF tests, there is no noticeable difference

sh-new2 atf-run time (all sh tests)

       68.14 real         8.86 user         9.63 sys
       67.88 real         9.00 user         9.58 sys
       67.87 real         8.88 user         9.74 sys
       67.83 real         8.81 user         9.77 sys
       67.90 real         8.96 user         9.67 sys

sh-new1 atf-run time (all sh tests)

       67.87 real         9.03 user         9.58 sys
       67.85 real         8.89 user         9.71 sys
       67.86 real         8.91 user         9.69 sys
       67.85 real         8.81 user         9.79 sys
       67.84 real         8.86 user         9.72 sys

sh-old atf-run time (all sh tests)

       67.85 real         8.69 user         9.89 sys
       67.85 real         8.81 user         9.77 sys
       67.84 real         8.90 user         9.68 sys
       67.84 real         8.87 user         9.71 sys
       67.88 real         9.12 user         9.51 sys

(That is time results from the full sh ATF tests (tests/bin/sh) run 5 times
for each shell version, in each case the shell being tested was used to both
run the ATF scripts, and to be tested - it was installed as /bin/sh.)

sh-new1 and sh-new2 both average out to 8.90 user seconds, sh-old is 8.87
but that one can't hack the (new - not yet committed, but included here)
sh arith tests for the assignment operators, so fails out of that test-case
on the first internal test (of 22 that exist).   That means 21 invocations
of the shell don't happen, so some time is going to be saved.   Note that
this whole test case (on this system, and when it works fully) takes just
about 0.2 seconds, so skipping 21/22 of that isn't really saving a lot.

[Aside: the long elapsed times are because many of the sh tests involve
executing programs - very often sleep - which consume time doing nothing.]

I also ran the following (totally meaningless, but much more concentrated
arithmetic) 20 times with each shell...

i=0
while [ $i -lt 500000 ]
do
        i=$(( i + 1 ))
        j=$(( 3000 - i + (200 << (i % 3)) / i ))
        k=$(( (i % 4)&1 ? 10 * j + (i*i)%7 : j - (j >> 3) + (i << 2) ))
done

Note no assignment ops in this so it works the same in all versions.

The (averaged, over the 20 runs) timing results for that are 

 Real  User   Sys
2.2575 2.256  0	     new1
2.246  2.2455 0      new2
6.6825 4.6615 2.0125 old

Clearly the new code consumes much less user time (just over 50%) of what
the old code used (of course, almost no real applocation will see that kind
of change.)

I really couldn't believe the 2 seconds of system time for the old (which
means, NetBSD current) shell, there should be nothing in there that could
rationally consume any system time - the 0 results for the new code are what
I'd expect, the only system time is loading the shell (once) and reading the
script (once) which should be (and apparently is) too little to register.

So, I ran the 20 iterations of the (same) old shell again ..

6.6835 4.5775 2.1005 old2

If anyone wants to figure out wtf that is actually doing, all you need to
do is run that script (just above) on a current /bin/sh and see if you
observe the same thing as I did, and then if you do, work out why...

I haven't (yet) done a full build using this modified shell, but I would
not expect any noticeable difference - system builds should use even less
shell arithmetic than the ATF tests do, so if the difference is measurable
I'd be astounded.

Needless to say all the (current, and new) sh ATF tests pass with the
modified shell (both variants), all but the new test which tests $(())
assignment operators (unimplemented there) succeed for the old (current) shell.

The difference between new1 and new2 is that I modified the lexical scanner
compared with the FreeBSD version (more or less new1) a little to procduce
new2.  I was expecting it to get a little smaller, and perhaps be fractionally
slower.   INstead it got just a tiny bit bigger, and runs a tiny smidgen
faster!

The new version (new2) is something like ( where p is a pointer to the string
containing the expression that was within the $(( )) )...

	c = *p++;
	if (isdigit(c)) {
		/* scan & eval number and return ARITH_NUM */
	} else if (isname(c)) {
		/* scan and save var name, and return ARITH_VAR */
	} else switch (c) {
	case '+':	/* handle all the rest of everything in a big switch */
	}

isname() is a macro that exxentially tests isalpha(c) || c == '_'
(true if the arg is one of the characters which can be the leading
character of a sh variable name .. there is also is_in_name() which
is true for the subsequent chars of names .. adds digits to what isname()
allows, that is used in both versions.)

The older (FreeBSD, and probably dash) version (new1) is more like

	c = *p++;
	switch (c) {
	case '0': case '1': case '2': ... case '9':
		/* scan & eval number and return ARITH_NUM */
		return ARITH_NUM;
	case 'A': case 'B': ... case 'Z':
	case '_':
	case 'a': case 'b': ... case 'z':
		/* scan and save var name, and return ARITH_VAR */
		return ARITH_VAR;
	case '+':
		/* deal with + ++ += etc - unchanged in the new2 vers */
	case all the rest:
		/* also unchanged */
	}

The commented out code is the same in both versions (just moved.)

I like the first (new2) one, because it doesn't have the (ugly) long
list of case labels (in the FreeBSD version thay're one to a line,
I altered that to avoid being violently ill - but that's just a textual
change in the source, no difference once compiled).   The new2 version
also avoids open coding isdigit() and isname() so should they ever change,
the arith lex scanner will change along with them (though that is
unbelievably unlikely.)

Unless there are objections in the next few days, I plan on committing this
update, probably before the end of the weekend (I will be doing more
testing in the interim, including builds for more than amd64 - at least
a couple of others)

I will probably use the new2 version, but I'm open to opinions on that.

For anyone who wants to look a the modified sources, I have put the
full current sh source (with the proposed modifications) in
	ftp://munnari.oz.au/kre/sh.tgz
(note: no ~ in there anywhere).   If you use an "unusual" arch, like
mips, vax, anything 68k, I'd appreciate you giving it a test, confirm
that it works OK (just unpack it - it will make a "sh" sub-dir, enter
that and "make" should produce ./sh on any NetBSD system with the comp
set (compilers, headers, etc) installed.)

In that the difference between new1 and new2 is which file is used as
arith_token.c - the one that is currently there with that name produces
what I have called new1 above, by moving arith_token2.c to arith_token.c
(nothing with the name arith_token2.c is used anywhere) you will get the
version I call new2 above (the version I prefer, slightly.)   Remember to
touch arith_token.c after the move, so its mod date gets updated before
"make" again (or you could "make clean" or just rm arith_token.o.)

Note, if you want to look look in the FreeBSD SVN (or whatever) repo, the
files have been renamed for NetBSD - I did that to avoid problems with
update (-u) builds (build.sh -u) - FreeBSD have arith.c - but that used
to be generated from arith.y and so (if you have a populated obj dir)
there will be an arith.c in the obj dir.  With the new Makefile, arith.c
doesn't depend upon anything, so make just sees the already existing arith.c
in the obj directory, and uses that one, rather than the one in the source
directory.   To circumvent that, I renamed the NetBSD version to arithmetic.c

The same is true of arith_token.c which is, in FreeBSD, arith_lex.c,
which was generated before from arith_lex.l.   For completeness, though
it might not have mattered, I renamed arith.h (which used to be a by
product of running yacc on arith.y) to be arithmetic.h.   (The file
arith_tokens.h is new, and has the same name in FreeBSD and NetBSD).
Note there are also (necessary) minor changes to expand.h and expand.c
and of course, to Makefile (nothing else should be changed from current sh.)

There are not yet any sh.1 updates, but there will be.

Other changes I made from the FreeBSD version, are to completely delete
any suggestion that yacc/lex are in any way involved - their function in
their arith_lex,c is yylex(), and stores its value in a variable called
yylval.  There are a couple more similar yacc/lex related names, those
are all gone in the proposed NetBSD version.

There are a few other source cleanups (including some KNF) in the NetBSD
version compared to FreeBSD's (and no, I do not expect to ever have to update
this code from their version, ever again, so maintaining source compat
is not an issue - while our shells come from the same origins, and have a
lot in common, they have also diverged quite a lot.)

Neither version implements the (optional in posix) ++ or -- operators,
both attempt to recognise them and generate an error, rather than just
doing the wrong thing, I think the NetBSD version generates a better error
than FreeBSD do:

NetBSD$ echo $(( x++ ))
sh: arithmetic: ++ operator unsupported

FreeBSD$ echo $(( x++ ))
fbsh: arithmetic expression: expecting EOF: " x++ "

(Their version looks as if it is parsing it as x + + ???, though the source
looks like it is not supposed to do that.)

Opinions/comments accepted, in the next couple of days please.

And while I am here, POSIX sh arithmetic is derived from C arithmetic, with
the ++ and -- operators optional, sizeof() not included at all, and no
control statements of any kind (of course.).   The ',' operator is not
even in the list (and is not implemented here (or in FreeBSD) - though it
is implemented in bash, zsh, mksh, and /bin/ksh (in NetBSD, that ancient
bug ridden thing), but not in yash or dash.  I assume it probably exists
in ksh88 and ksh93 but have not checked.

POSIX allows arithmetic to be extended if implementors want, and I'm
thinking that including the ',' operator would be useful, so after the
current changes are committed, I will probably add that, unless there
are objections.

I'm not sure whether attempting ++ or -- is worth the effort:
(x+=1) works, as does ((x+=1)-1) (for ++x and x++ resp).

kre