Discussion:
[Toybox] [PATCH] expr
Daniel Verkamp
2013-06-04 08:09:52 UTC
Permalink
This half-baked implementation of expr has been sitting on my disk for
a little while now, but I find myself struggling to find time to
finish it, so I'm posting it in the hopes that someone will pick it
up.

The expression is evaluated using a recursive descent parser; the core
of the evaluator is parse_op(), which uses a table to determine
operator behavior and precedence.

All numeric values are represented as 'long', which is only 32 bits on
32-bit hosts; it may be interesting to use 'long long' instead.

What's left to do:
- Flesh out the help text.
- Write more comprehensive test cases.
- Decide what to do about integer overflow (the current code can
execute undefined signed overflow behavior with large inputs; GNU
coreutils expr detects this and prints an appropriate error).
- Implement the : operator - yes, in fine 'cat -v' tradition, POSIX
expr can match regular expressions.

I have done some minimal testing while writing the command, but it
could use some real-world testing (I think the Linux kernel build
contains a few expr invocations, but I have not tried it with this
implementation).

Feel free to fold, spindle, or mutilate as desired.

Thanks,
-- Daniel Verkamp
-------------- next part --------------
A non-text attachment was scrubbed...
Name: expr.patch
Type: application/octet-stream
Size: 6610 bytes
Desc: not available
URL: <http://lists.landley.net/pipermail/toybox-landley.net/attachments/20130604/0bfe44e3/attachment.obj>
Rob Landley
2013-06-05 06:06:54 UTC
Permalink
Post by Daniel Verkamp
This half-baked implementation of expr has been sitting on my disk for
a little while now, but I find myself struggling to find time to
finish it, so I'm posting it in the hopes that someone will pick it
up.
I know the feeling. :)

That someone is usually me, but finding the time...
Post by Daniel Verkamp
The expression is evaluated using a recursive descent parser; the core
of the evaluator is parse_op(), which uses a table to determine
operator behavior and precedence.
All numeric values are represented as 'long', which is only 32 bits on
32-bit hosts; it may be interesting to use 'long long' instead.
Back when my timeconst perl removal patch was a shell script, it relied
on 64 bit expr support and I got a busybox fix for that. Since then,
I've rewritten it in C (and HPA rewrote it in bc), but it would
probably be best to have it as 64 bit math anyway.
Post by Daniel Verkamp
- Flesh out the help text.
Ironically, the expr implementation I have lying around here was
nothing _but_ help text (that's as far as I got), but I'm not finding
it at the moment...

Ah, no, I was thinking toys/pending/test.c.
Post by Daniel Verkamp
- Write more comprehensive test cases.
- Decide what to do about integer overflow (the current code can
execute undefined signed overflow behavior with large inputs; GNU
coreutils expr detects this and prints an appropriate error).
What does Posix require?
Post by Daniel Verkamp
- Implement the : operator - yes, in fine 'cat -v' tradition, POSIX
expr can match regular expressions.
Oh joy.

I note that part of the reason I've held off with this one is that
(like test.c) it's basically shell behavior. Test is [ ] and expr is
$(( )), and they should eventually share code. I haven't yet studied
_how_ similar they are and how much (if any0 they diverge...

And then there's bc, which thanks to Peter Anvin I now have to
implement to build unmodified linux source. (The Linux From Scratch
guys had to add it to chapter 5. Sigh.) Dunno what overlap's there,
haven't studied it yet...
Post by Daniel Verkamp
I have done some minimal testing while writing the command, but it
could use some real-world testing (I think the Linux kernel build
contains a few expr invocations, but I have not tried it with this
implementation).
Feel free to fold, spindle, or mutilate as desired.
I checked it in and put it on the todo list. Unfortunately, my todo
list has roving packs of archeologists circling it at this point,
looking for an unguarded moment to attack with brush and trowel and
plaster cast...

Thanks,

Rob
Daniel Verkamp
2013-06-06 00:29:38 UTC
Permalink
[...]
Post by Daniel Verkamp
The expression is evaluated using a recursive descent parser; the core
of the evaluator is parse_op(), which uses a table to determine
operator behavior and precedence.
All numeric values are represented as 'long', which is only 32 bits on
32-bit hosts; it may be interesting to use 'long long' instead.
Back when my timeconst perl removal patch was a shell script, it relied on
64 bit expr support and I got a busybox fix for that. Since then, I've
rewritten it in C (and HPA rewrote it in bc), but it would probably be best
to have it as 64 bit math anyway.
Okay, perhaps I will spin a patch for this if nobody else gets to it.

[...]
Post by Daniel Verkamp
- Decide what to do about integer overflow (the current code can
execute undefined signed overflow behavior with large inputs; GNU
coreutils expr detects this and prints an appropriate error).
What does Posix require?
The expr command description doesn't mention anything about integer
overflow at all; I don't know if there is some overall POSIX
requirement that applies.

[...]
I note that part of the reason I've held off with this one is that (like
test.c) it's basically shell behavior. Test is [ ] and expr is $(( )), and
they should eventually share code. I haven't yet studied _how_ similar they
are and how much (if any) they diverge...
In expr's case, at least, there is not much that can be shared. Each
part of the expression in expr must be a separate argument and
properly escaped in the shell, whereas the shell arithmetic expansion
does not have these restrictions, e.g.

expr 5 + 3 \* 10
vs
echo $((5+3*10))

Invocations like `expr 5+3` or `expr "5 + 3"` don't work.

Thanks,
-- Daniel Verkamp
Rob Landley
2013-06-08 18:22:01 UTC
Permalink
Post by Daniel Verkamp
Post by Rob Landley
Post by Daniel Verkamp
- Decide what to do about integer overflow (the current code can
execute undefined signed overflow behavior with large inputs; GNU
coreutils expr detects this and prints an appropriate error).
What does Posix require?
The expr command description doesn't mention anything about integer
overflow at all; I don't know if there is some overall POSIX
requirement that applies.
Well, how did _you_ find out about it?

Absent the standard explicitly requiring something, the next thing I
care about is real world users. Who will _not_ doing it inconvenience?
Post by Daniel Verkamp
[...]
Post by Rob Landley
I note that part of the reason I've held off with this one is that
(like
Post by Rob Landley
test.c) it's basically shell behavior. Test is [ ] and expr is $((
)), and
Post by Rob Landley
they should eventually share code. I haven't yet studied _how_
similar they
Post by Rob Landley
are and how much (if any) they diverge...
In expr's case, at least, there is not much that can be shared. Each
part of the expression in expr must be a separate argument and
properly escaped in the shell, whereas the shell arithmetic expansion
does not have these restrictions, e.g.
expr 5 + 3 \* 10
vs
echo $((5+3*10))
Invocations like `expr 5+3` or `expr "5 + 3"` don't work.
The UI isn't shared, but some of the plumbing behind the scenes might
be. Once you've tokenized the input you have to work out order of
operations and perform the

Last time I did this it had two stacks (one for operators and one for
numbers), I should see if I can dig up my old code on this. It handled
arbitrary (x^(7+2/4)/37) stuff, with variables even. Alas, it was
written in java, and this was 1998, but still...

Or I could just read what you've done. :) (It's on my todo list!)

Rob
Daniel Verkamp
2013-06-11 00:56:17 UTC
Permalink
Post by Rob Landley
Post by Daniel Verkamp
Post by Rob Landley
Post by Daniel Verkamp
- Decide what to do about integer overflow (the current code can
execute undefined signed overflow behavior with large inputs; GNU
coreutils expr detects this and prints an appropriate error).
What does Posix require?
The expr command description doesn't mention anything about integer
overflow at all; I don't know if there is some overall POSIX
requirement that applies.
Well, how did _you_ find out about it?
The C standard says signed integer overflow is undefined behavior, and
a user can trigger such behavior with crafted inputs. Try `expr
9223372036854775807 \* 2`, for example.

Additionally, the GNU Coreutils implementation of expr prints a
specific message on overflow.
Post by Rob Landley
Absent the standard explicitly requiring something, the next thing I care
about is real world users. Who will _not_ doing it inconvenience?
At the very least, it's within the rights of the compiler to generate
code that aborts or crashes on overflow, and the potential for nasal
demons (or at least incorrect results) is probably enough to warrant
fixing it.

I presume most real-world uses of expr don't cause overflow, since it
doesn't produce any useful results, but I suppose there could be
scripts that depend on the "return error on overflow" behavior of GNU
expr in some way.

Perhaps the easiest option would be to enable GCC's -ftrapv option,
which causes signed overflow to abort intentionally; this would not be
very user friendly, but it's probably better than generating wrong
answers. However, this would generate larger and slower code
throughout toybox.

Thanks,
-- Daniel Verkamp
Daniel Verkamp
2013-06-11 00:56:17 UTC
Permalink
Post by Rob Landley
Post by Daniel Verkamp
Post by Rob Landley
Post by Daniel Verkamp
- Decide what to do about integer overflow (the current code can
execute undefined signed overflow behavior with large inputs; GNU
coreutils expr detects this and prints an appropriate error).
What does Posix require?
The expr command description doesn't mention anything about integer
overflow at all; I don't know if there is some overall POSIX
requirement that applies.
Well, how did _you_ find out about it?
The C standard says signed integer overflow is undefined behavior, and
a user can trigger such behavior with crafted inputs. Try `expr
9223372036854775807 \* 2`, for example.

Additionally, the GNU Coreutils implementation of expr prints a
specific message on overflow.
Post by Rob Landley
Absent the standard explicitly requiring something, the next thing I care
about is real world users. Who will _not_ doing it inconvenience?
At the very least, it's within the rights of the compiler to generate
code that aborts or crashes on overflow, and the potential for nasal
demons (or at least incorrect results) is probably enough to warrant
fixing it.

I presume most real-world uses of expr don't cause overflow, since it
doesn't produce any useful results, but I suppose there could be
scripts that depend on the "return error on overflow" behavior of GNU
expr in some way.

Perhaps the easiest option would be to enable GCC's -ftrapv option,
which causes signed overflow to abort intentionally; this would not be
very user friendly, but it's probably better than generating wrong
answers. However, this would generate larger and slower code
throughout toybox.

Thanks,
-- Daniel Verkamp
Rob Landley
2013-06-08 18:22:01 UTC
Permalink
Post by Daniel Verkamp
Post by Rob Landley
Post by Daniel Verkamp
- Decide what to do about integer overflow (the current code can
execute undefined signed overflow behavior with large inputs; GNU
coreutils expr detects this and prints an appropriate error).
What does Posix require?
The expr command description doesn't mention anything about integer
overflow at all; I don't know if there is some overall POSIX
requirement that applies.
Well, how did _you_ find out about it?

Absent the standard explicitly requiring something, the next thing I
care about is real world users. Who will _not_ doing it inconvenience?
Post by Daniel Verkamp
[...]
Post by Rob Landley
I note that part of the reason I've held off with this one is that
(like
Post by Rob Landley
test.c) it's basically shell behavior. Test is [ ] and expr is $((
)), and
Post by Rob Landley
they should eventually share code. I haven't yet studied _how_
similar they
Post by Rob Landley
are and how much (if any) they diverge...
In expr's case, at least, there is not much that can be shared. Each
part of the expression in expr must be a separate argument and
properly escaped in the shell, whereas the shell arithmetic expansion
does not have these restrictions, e.g.
expr 5 + 3 \* 10
vs
echo $((5+3*10))
Invocations like `expr 5+3` or `expr "5 + 3"` don't work.
The UI isn't shared, but some of the plumbing behind the scenes might
be. Once you've tokenized the input you have to work out order of
operations and perform the

Last time I did this it had two stacks (one for operators and one for
numbers), I should see if I can dig up my old code on this. It handled
arbitrary (x^(7+2/4)/37) stuff, with variables even. Alas, it was
written in java, and this was 1998, but still...

Or I could just read what you've done. :) (It's on my todo list!)

Rob
Daniel Verkamp
2013-06-06 00:29:38 UTC
Permalink
[...]
Post by Daniel Verkamp
The expression is evaluated using a recursive descent parser; the core
of the evaluator is parse_op(), which uses a table to determine
operator behavior and precedence.
All numeric values are represented as 'long', which is only 32 bits on
32-bit hosts; it may be interesting to use 'long long' instead.
Back when my timeconst perl removal patch was a shell script, it relied on
64 bit expr support and I got a busybox fix for that. Since then, I've
rewritten it in C (and HPA rewrote it in bc), but it would probably be best
to have it as 64 bit math anyway.
Okay, perhaps I will spin a patch for this if nobody else gets to it.

[...]
Post by Daniel Verkamp
- Decide what to do about integer overflow (the current code can
execute undefined signed overflow behavior with large inputs; GNU
coreutils expr detects this and prints an appropriate error).
What does Posix require?
The expr command description doesn't mention anything about integer
overflow at all; I don't know if there is some overall POSIX
requirement that applies.

[...]
I note that part of the reason I've held off with this one is that (like
test.c) it's basically shell behavior. Test is [ ] and expr is $(( )), and
they should eventually share code. I haven't yet studied _how_ similar they
are and how much (if any) they diverge...
In expr's case, at least, there is not much that can be shared. Each
part of the expression in expr must be a separate argument and
properly escaped in the shell, whereas the shell arithmetic expansion
does not have these restrictions, e.g.

expr 5 + 3 \* 10
vs
echo $((5+3*10))

Invocations like `expr 5+3` or `expr "5 + 3"` don't work.

Thanks,
-- Daniel Verkamp
Rob Landley
2013-06-13 02:43:34 UTC
Permalink
Post by Daniel Verkamp
Post by Rob Landley
On Tue, Jun 4, 2013 at 11:06 PM, Rob Landley <rob at landley.net>
Post by Rob Landley
Post by Daniel Verkamp
- Decide what to do about integer overflow (the current code can
execute undefined signed overflow behavior with large inputs;
GNU
Post by Rob Landley
Post by Rob Landley
Post by Daniel Verkamp
coreutils expr detects this and prints an appropriate error).
What does Posix require?
The expr command description doesn't mention anything about integer
overflow at all; I don't know if there is some overall POSIX
requirement that applies.
Well, how did _you_ find out about it?
The C standard says signed integer overflow is undefined behavior, and
a user can trigger such behavior with crafted inputs. Try `expr
9223372036854775807 \* 2`, for example.
So you've never actually seen any real-world anything be inconvenienced
by this, you're just writing defensive code against a hypothetical the
standard doesn't require you to handle.

By the way, how would you test for overflow? There's no feraiseexcept()
in integer math that I'm aware of...
Post by Daniel Verkamp
Additionally, the GNU Coreutils implementation of expr prints a
specific message on overflow.
Bash is also a GNU program:

landley at driftwood:~/busybox/busybox$ echo
$((1000000*1000000*1000000*1000000))
2003764205206896640
landley at driftwood:~/busybox/busybox$ help | head -n 1
GNU bash, version 4.2.25(1)-release (x86_64-pc-linux-gnu)

The FSF is inconsistent (insane). They write autoconf tests that check
the sizeof uint32_t. Yes really, I was digging up some old autoconf
complaints recently because somebody was insane enough to try to defend
it:

http://landley.net/notes-2010.html#20-08-2010
http://landley.net/notes-2010.html#09-08-2010
http://landley.net/notes-2011.html#26-10-2011
http://landley.net/notes-2011.html#06-09-2011

The reason toybox exists (and busybox before it) is because the GNU
versions are overengineered paranoid crap, punitively licensed. "GNU
does it" is never by itself a reason for anything.
Post by Daniel Verkamp
Post by Rob Landley
Absent the standard explicitly requiring something, the next thing
I care
Post by Rob Landley
about is real world users. Who will _not_ doing it inconvenience?
At the very least, it's within the rights of the compiler to generate
code that aborts or crashes on overflow, and the potential for nasal
demons (or at least incorrect results) is probably enough to warrant
fixing it.
Once the nasal demons get typecast to a 64 bit integer they're unlikely
to go far. And any C environment that crashes on integer overflow can't
run the Linux kernel, so I'm not sure we care? (They intentionally
initialize the timer ticks to overflow around 120 seconds after boot,
to force everything to handle timer wraparound properly.)

Ok, now I'm curious, grep -i overflow in busybox/coreutils/expr.c:

/* Don't interpret the empty string as an integer. */
/* Currently does not worry about overflow or int/long
differences. */
i = STRTOL(v->u.s, &e, 10);

Code has been in the tree for:

commit 1b355ebba68bdd567dd3961a18291dfd9532c2e8
Author: Eric Andersen <andersen at codepoet.org>
Date: Tue Sep 5 17:37:48 2000 +0000

Added expr, from Edward Betts <edward at debian.org>, with some fixups
and docs added by me.
-Erik

Coming up on 13 years. And the closest anybody came to complaining
about "overflow" was:

commit a7f4e4bbd8d7a47a49404d28bc07ab3b5dc1c19b
Author: Denis Vlasenko <vda.linux at googlemail.com>
Date: Wed Apr 2 20:24:09 2008 +0000

expr: fix comparisons 'a < b' where we were overflowing a-b
(not to mention that we used int, not arith_t). closes bug 2744.

Not because they cared about the result of math that overflowed, but
because comparison was producing wrong results on numbers within the
storable range.
Post by Daniel Verkamp
I presume most real-world uses of expr don't cause overflow, since it
doesn't produce any useful results, but I suppose there could be
scripts that depend on the "return error on overflow" behavior of GNU
expr in some way.
There could be scripts that depend on non-posix behavior, yes. And
until I see an example of one, I can't judge whether they should fix
their broken code or we should humor them.
Post by Daniel Verkamp
Perhaps the easiest option would be to enable GCC's -ftrapv option,
which causes signed overflow to abort intentionally;
Hell no.

I'm confused: you list as a potential downside that expr might crash.
So the solutions are to add an error_exit() to force expr to crash, or
to add a compiler flag to force expr to crash. And this improves
matters how?
Post by Daniel Verkamp
this would not be
very user friendly, but it's probably better than generating wrong
answers.
Garbage in, garbage out. They get to keep the pieces.

A couple posts back you were ok with not always doing 64 bit math,
which is easy and known to help produce more right answers. Now you're
advocating for something that isn't necessarily easy (no feraisexcept()
for interger math), doesn't help produce more right answers.

In a larger context, the problem you want to address is that on
overflow it produces incorrect output (because C math does), so you'd
like it to produce a different kind of incorrect output, on the theory
that somebody is going to check the return code of expr in a script.

Here's a cut and paste from the Centos 6.4 kernel's top level Makefile,
which they copied verbatim from the current Red Hat Enterprise:

ifneq (,$(filter $(ARCH), i386 x86_64))
CPP_MAJOR := $(shell $(CPP) -dumpversion 2>&1 | cut -d'.' -f1)
CPP_MINOR := $(shell $(CPP) -dumpversion 2>&1 | cut -d'.' -f2)
CPP_PATCH := $(shell $(CPP) -dumpversion 2>&1 | cut -d'.' -f3)
# Assumes that major, minor, and patch cannot exceed 999
CPP_VERS := $(shell expr $(CPP_MAJOR) \* 1000000 + $(CPP_MINOR)
\* 1000 \
+ $(CPP_PATCH))

# GCC Bugzilla Bug 43949:
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43949
# add -Wno-array-bounds to remove bogus warnings. This flag is present
in
# gcc version 4.4.4 .
ifeq ($(KBUILD_EXTMOD),)
KBUILD_CFLAGS += $(shell if [ $(CPP_VERS) -ge 4004004 ]; then \
echo "-Wno-array-bounds"; else echo ""; fi)

Guess what happens when you build that under SuSE Linux Enterprise
service pack 2, which uses gcc 4.3? (Not "4.3.0", but "4.3", so
CPP_PATCH is blank and the expr ends with a trailing + and throws an
error that isn't checked for instead of producing any output? And then
CPP_VERS is blank so the KBUILD_CFLAGS shell script snippet _also_
doesn't do any error checking on "if [ -ge 4004004 ]", so your make
outputs two syntax errors every time you run it even to do
"menuconfig", but otherwise works fine because all this crap is just to
tell gcc to produce extra warnings?

That's "Enterprise" code. (11a2b, 1b2b3, zero zero destruct zero.) I
hit that bug a few month back, and it was because expr didn't check the
result in any way. (No error exit, no "string is blank", no nothing. It
worked using the Red Hat compiler, which had X.Y.Z, and that's all Red
Hat ever tests.)
Post by Daniel Verkamp
However, this would generate larger and slower code throughout toybox.
See "Hell no.", above.
Post by Daniel Verkamp
Thanks,
-- Daniel Verkamp
I'm not saying I'm against handling it, I'm saying you have yet to make
a compelling case for it.

I note that I probably need to add an arbitrary precision math library
to implement bc, which is in posix and required to build an unmodified
linux kernel, so if we're GOING to care about overflow we could always
just avoid overflowing.

But until them, overflow doesn't really bother me if it doesn't bother
posix, busybox, or bash.

Rob
Daniel Verkamp
2013-06-13 03:56:00 UTC
Permalink
Post by Daniel Verkamp
Post by Rob Landley
Post by Daniel Verkamp
Post by Rob Landley
Post by Daniel Verkamp
- Decide what to do about integer overflow (the current code can
execute undefined signed overflow behavior with large inputs; GNU
coreutils expr detects this and prints an appropriate error).
What does Posix require?
The expr command description doesn't mention anything about integer
overflow at all; I don't know if there is some overall POSIX
requirement that applies.
Well, how did _you_ find out about it?
The C standard says signed integer overflow is undefined behavior, and
a user can trigger such behavior with crafted inputs. Try `expr
9223372036854775807 \* 2`, for example.
So you've never actually seen any real-world anything be inconvenienced by
this, you're just writing defensive code against a hypothetical the standard
doesn't require you to handle.
Yep, I brought it up purely from a language-lawyer perspective, and to
avoid someone coming along later and saying "these fools never thought
about integer overflow!"
By the way, how would you test for overflow? There's no feraiseexcept() in
integer math that I'm aware of...
There's no nice built-in way to do it; you pretty much have to do the
overflow calculations by hand (e.g. for addition, you can do the math
in unsigned integers, which have defined overflow behavior, and
compare the sign bits of the two addends and the result). It's not
pretty.
Post by Daniel Verkamp
Additionally, the GNU Coreutils implementation of expr prints a
specific message on overflow.
landley at driftwood:~/busybox/busybox$ echo
$((1000000*1000000*1000000*1000000))
2003764205206896640
landley at driftwood:~/busybox/busybox$ help | head -n 1
GNU bash, version 4.2.25(1)-release (x86_64-pc-linux-gnu)
The FSF is inconsistent (insane). They write autoconf tests that check the
sizeof uint32_t. Yes really, I was digging up some old autoconf complaints
http://landley.net/notes-2010.html#20-08-2010
http://landley.net/notes-2010.html#09-08-2010
http://landley.net/notes-2011.html#26-10-2011
http://landley.net/notes-2011.html#06-09-2011
The reason toybox exists (and busybox before it) is because the GNU versions
are overengineered paranoid crap, punitively licensed. "GNU does it" is
never by itself a reason for anything.
I hear you. I only brought up the GNU version since it's probably the
only version that any Linux-related scripts have been tested with.

As an example (unrelated to overflow), I grepped through the Linux
kernel source tree and found some uses of the non-POSIX "match" and
"index" operators (e.g. scripts/decodecode), so they're obviously not
too concerned about using behavior outside the standard.
Post by Daniel Verkamp
Post by Rob Landley
Absent the standard explicitly requiring something, the next thing I care
about is real world users. Who will _not_ doing it inconvenience?
At the very least, it's within the rights of the compiler to generate
code that aborts or crashes on overflow, and the potential for nasal
demons (or at least incorrect results) is probably enough to warrant
fixing it.
Once the nasal demons get typecast to a 64 bit integer they're unlikely to
go far. And any C environment that crashes on integer overflow can't run the
Linux kernel, so I'm not sure we care? (They intentionally initialize the
timer ticks to overflow around 120 seconds after boot, to force everything
to handle timer wraparound properly.)
Well, that's probably *unsigned* integer overflow, which is defined in
the C standard to wrap around. In expr's case, we're talking about
signed integer overflow, which is what's undefined in C.

Either way, I don't know of any real machines that can run Linux and
actually crash on integer overflow (though I am only really familiar
with x86).
/* Don't interpret the empty string as an integer. */
/* Currently does not worry about overflow or int/long
differences. */
i = STRTOL(v->u.s, &e, 10);
commit 1b355ebba68bdd567dd3961a18291dfd9532c2e8
Author: Eric Andersen <andersen at codepoet.org>
Date: Tue Sep 5 17:37:48 2000 +0000
Added expr, from Edward Betts <edward at debian.org>, with some fixups
and docs added by me.
-Erik
Coming up on 13 years. And the closest anybody came to complaining about
commit a7f4e4bbd8d7a47a49404d28bc07ab3b5dc1c19b
Author: Denis Vlasenko <vda.linux at googlemail.com>
Date: Wed Apr 2 20:24:09 2008 +0000
expr: fix comparisons 'a < b' where we were overflowing a-b
(not to mention that we used int, not arith_t). closes bug 2744.
Not because they cared about the result of math that overflowed, but because
comparison was producing wrong results on numbers within the storable range.
Post by Daniel Verkamp
I presume most real-world uses of expr don't cause overflow, since it
doesn't produce any useful results, but I suppose there could be
scripts that depend on the "return error on overflow" behavior of GNU
expr in some way.
There could be scripts that depend on non-posix behavior, yes. And until I
see an example of one, I can't judge whether they should fix their broken
code or we should humor them.
Post by Daniel Verkamp
Perhaps the easiest option would be to enable GCC's -ftrapv option,
which causes signed overflow to abort intentionally;
Hell no.
I'm confused: you list as a potential downside that expr might crash. So the
solutions are to add an error_exit() to force expr to crash, or to add a
compiler flag to force expr to crash. And this improves matters how?
Only better in that it will definitely abort rather than doing some
other undefined thing; this is not better than crashing because of
undefined behavior, but at least it would be consistent.
I mostly added this suggestion as a "technically correct" option.
Post by Daniel Verkamp
this would not be
very user friendly, but it's probably better than generating wrong
answers.
Garbage in, garbage out. They get to keep the pieces.
A couple posts back you were ok with not always doing 64 bit math, which is
easy and known to help produce more right answers. Now you're advocating for
something that isn't necessarily easy (no feraisexcept() for integer math),
doesn't help produce more right answers.
That's a fair point. The main reason I used 'long' (rather than
forcing 64-bit math) is that POSIX seemed to indicate that expr need
not support more than the precision of the C 'long' type, and since
64-bit math presumably generates bigger/slower code on 32-bit targets.
In a larger context, the problem you want to address is that on overflow it
produces incorrect output (because C math does), so you'd like it to produce
a different kind of incorrect output, on the theory that somebody is going
to check the return code of expr in a script.
It's definitely a corner case, and the corner is hidden behind some
cobwebs under a staircase in an abandoned house on a hill.

[...]
I'm not saying I'm against handling it, I'm saying you have yet to make a
compelling case for it.
I note that I probably need to add an arbitrary precision math library to
implement bc, which is in posix and required to build an unmodified linux
kernel, so if we're GOING to care about overflow we could always just avoid
overflowing.
But until them, overflow doesn't really bother me if it doesn't bother
posix, busybox, or bash.
I doubt there is a compelling case for it from a user's point of view,
and I'm in agreement that it is probably not worth doing anything
about. I just wanted to be sure there was no false expectation that
this expr implementation did anything useful on overflow, and it
sounds like we've definitely got that covered now. :)

Please find attached the (entirely trivial) patch for 64-bit integers
in expr, which pretty much avoids this problem for all sane users.
Rob
Thanks,
-- Daniel Verkamp
-------------- next part --------------
A non-text attachment was scrubbed...
Name: expr-64bit.patch
Type: application/octet-stream
Size: 1062 bytes
Desc: not available
URL: <http://lists.landley.net/pipermail/toybox-landley.net/attachments/20130612/434c946b/attachment.obj>
Daniel Verkamp
2013-06-13 03:56:00 UTC
Permalink
Post by Daniel Verkamp
Post by Rob Landley
Post by Daniel Verkamp
Post by Rob Landley
Post by Daniel Verkamp
- Decide what to do about integer overflow (the current code can
execute undefined signed overflow behavior with large inputs; GNU
coreutils expr detects this and prints an appropriate error).
What does Posix require?
The expr command description doesn't mention anything about integer
overflow at all; I don't know if there is some overall POSIX
requirement that applies.
Well, how did _you_ find out about it?
The C standard says signed integer overflow is undefined behavior, and
a user can trigger such behavior with crafted inputs. Try `expr
9223372036854775807 \* 2`, for example.
So you've never actually seen any real-world anything be inconvenienced by
this, you're just writing defensive code against a hypothetical the standard
doesn't require you to handle.
Yep, I brought it up purely from a language-lawyer perspective, and to
avoid someone coming along later and saying "these fools never thought
about integer overflow!"
By the way, how would you test for overflow? There's no feraiseexcept() in
integer math that I'm aware of...
There's no nice built-in way to do it; you pretty much have to do the
overflow calculations by hand (e.g. for addition, you can do the math
in unsigned integers, which have defined overflow behavior, and
compare the sign bits of the two addends and the result). It's not
pretty.
Post by Daniel Verkamp
Additionally, the GNU Coreutils implementation of expr prints a
specific message on overflow.
landley at driftwood:~/busybox/busybox$ echo
$((1000000*1000000*1000000*1000000))
2003764205206896640
landley at driftwood:~/busybox/busybox$ help | head -n 1
GNU bash, version 4.2.25(1)-release (x86_64-pc-linux-gnu)
The FSF is inconsistent (insane). They write autoconf tests that check the
sizeof uint32_t. Yes really, I was digging up some old autoconf complaints
http://landley.net/notes-2010.html#20-08-2010
http://landley.net/notes-2010.html#09-08-2010
http://landley.net/notes-2011.html#26-10-2011
http://landley.net/notes-2011.html#06-09-2011
The reason toybox exists (and busybox before it) is because the GNU versions
are overengineered paranoid crap, punitively licensed. "GNU does it" is
never by itself a reason for anything.
I hear you. I only brought up the GNU version since it's probably the
only version that any Linux-related scripts have been tested with.

As an example (unrelated to overflow), I grepped through the Linux
kernel source tree and found some uses of the non-POSIX "match" and
"index" operators (e.g. scripts/decodecode), so they're obviously not
too concerned about using behavior outside the standard.
Post by Daniel Verkamp
Post by Rob Landley
Absent the standard explicitly requiring something, the next thing I care
about is real world users. Who will _not_ doing it inconvenience?
At the very least, it's within the rights of the compiler to generate
code that aborts or crashes on overflow, and the potential for nasal
demons (or at least incorrect results) is probably enough to warrant
fixing it.
Once the nasal demons get typecast to a 64 bit integer they're unlikely to
go far. And any C environment that crashes on integer overflow can't run the
Linux kernel, so I'm not sure we care? (They intentionally initialize the
timer ticks to overflow around 120 seconds after boot, to force everything
to handle timer wraparound properly.)
Well, that's probably *unsigned* integer overflow, which is defined in
the C standard to wrap around. In expr's case, we're talking about
signed integer overflow, which is what's undefined in C.

Either way, I don't know of any real machines that can run Linux and
actually crash on integer overflow (though I am only really familiar
with x86).
/* Don't interpret the empty string as an integer. */
/* Currently does not worry about overflow or int/long
differences. */
i = STRTOL(v->u.s, &e, 10);
commit 1b355ebba68bdd567dd3961a18291dfd9532c2e8
Author: Eric Andersen <andersen at codepoet.org>
Date: Tue Sep 5 17:37:48 2000 +0000
Added expr, from Edward Betts <edward at debian.org>, with some fixups
and docs added by me.
-Erik
Coming up on 13 years. And the closest anybody came to complaining about
commit a7f4e4bbd8d7a47a49404d28bc07ab3b5dc1c19b
Author: Denis Vlasenko <vda.linux at googlemail.com>
Date: Wed Apr 2 20:24:09 2008 +0000
expr: fix comparisons 'a < b' where we were overflowing a-b
(not to mention that we used int, not arith_t). closes bug 2744.
Not because they cared about the result of math that overflowed, but because
comparison was producing wrong results on numbers within the storable range.
Post by Daniel Verkamp
I presume most real-world uses of expr don't cause overflow, since it
doesn't produce any useful results, but I suppose there could be
scripts that depend on the "return error on overflow" behavior of GNU
expr in some way.
There could be scripts that depend on non-posix behavior, yes. And until I
see an example of one, I can't judge whether they should fix their broken
code or we should humor them.
Post by Daniel Verkamp
Perhaps the easiest option would be to enable GCC's -ftrapv option,
which causes signed overflow to abort intentionally;
Hell no.
I'm confused: you list as a potential downside that expr might crash. So the
solutions are to add an error_exit() to force expr to crash, or to add a
compiler flag to force expr to crash. And this improves matters how?
Only better in that it will definitely abort rather than doing some
other undefined thing; this is not better than crashing because of
undefined behavior, but at least it would be consistent.
I mostly added this suggestion as a "technically correct" option.
Post by Daniel Verkamp
this would not be
very user friendly, but it's probably better than generating wrong
answers.
Garbage in, garbage out. They get to keep the pieces.
A couple posts back you were ok with not always doing 64 bit math, which is
easy and known to help produce more right answers. Now you're advocating for
something that isn't necessarily easy (no feraisexcept() for integer math),
doesn't help produce more right answers.
That's a fair point. The main reason I used 'long' (rather than
forcing 64-bit math) is that POSIX seemed to indicate that expr need
not support more than the precision of the C 'long' type, and since
64-bit math presumably generates bigger/slower code on 32-bit targets.
In a larger context, the problem you want to address is that on overflow it
produces incorrect output (because C math does), so you'd like it to produce
a different kind of incorrect output, on the theory that somebody is going
to check the return code of expr in a script.
It's definitely a corner case, and the corner is hidden behind some
cobwebs under a staircase in an abandoned house on a hill.

[...]
I'm not saying I'm against handling it, I'm saying you have yet to make a
compelling case for it.
I note that I probably need to add an arbitrary precision math library to
implement bc, which is in posix and required to build an unmodified linux
kernel, so if we're GOING to care about overflow we could always just avoid
overflowing.
But until them, overflow doesn't really bother me if it doesn't bother
posix, busybox, or bash.
I doubt there is a compelling case for it from a user's point of view,
and I'm in agreement that it is probably not worth doing anything
about. I just wanted to be sure there was no false expectation that
this expr implementation did anything useful on overflow, and it
sounds like we've definitely got that covered now. :)

Please find attached the (entirely trivial) patch for 64-bit integers
in expr, which pretty much avoids this problem for all sane users.
Rob
Thanks,
-- Daniel Verkamp
-------------- next part --------------
A non-text attachment was scrubbed...
Name: expr-64bit.patch
Type: application/octet-stream
Size: 1062 bytes
Desc: not available
URL: <http://lists.landley.net/pipermail/toybox-landley.net/attachments/20130612/434c946b/attachment-0002.obj>
Daniel Verkamp
2013-06-04 08:09:52 UTC
Permalink
This half-baked implementation of expr has been sitting on my disk for
a little while now, but I find myself struggling to find time to
finish it, so I'm posting it in the hopes that someone will pick it
up.

The expression is evaluated using a recursive descent parser; the core
of the evaluator is parse_op(), which uses a table to determine
operator behavior and precedence.

All numeric values are represented as 'long', which is only 32 bits on
32-bit hosts; it may be interesting to use 'long long' instead.

What's left to do:
- Flesh out the help text.
- Write more comprehensive test cases.
- Decide what to do about integer overflow (the current code can
execute undefined signed overflow behavior with large inputs; GNU
coreutils expr detects this and prints an appropriate error).
- Implement the : operator - yes, in fine 'cat -v' tradition, POSIX
expr can match regular expressions.

I have done some minimal testing while writing the command, but it
could use some real-world testing (I think the Linux kernel build
contains a few expr invocations, but I have not tried it with this
implementation).

Feel free to fold, spindle, or mutilate as desired.

Thanks,
-- Daniel Verkamp
-------------- next part --------------
A non-text attachment was scrubbed...
Name: expr.patch
Type: application/octet-stream
Size: 6610 bytes
Desc: not available
URL: <http://lists.landley.net/pipermail/toybox-landley.net/attachments/20130604/0bfe44e3/attachment-0002.obj>
Rob Landley
2013-06-05 06:06:54 UTC
Permalink
Post by Daniel Verkamp
This half-baked implementation of expr has been sitting on my disk for
a little while now, but I find myself struggling to find time to
finish it, so I'm posting it in the hopes that someone will pick it
up.
I know the feeling. :)

That someone is usually me, but finding the time...
Post by Daniel Verkamp
The expression is evaluated using a recursive descent parser; the core
of the evaluator is parse_op(), which uses a table to determine
operator behavior and precedence.
All numeric values are represented as 'long', which is only 32 bits on
32-bit hosts; it may be interesting to use 'long long' instead.
Back when my timeconst perl removal patch was a shell script, it relied
on 64 bit expr support and I got a busybox fix for that. Since then,
I've rewritten it in C (and HPA rewrote it in bc), but it would
probably be best to have it as 64 bit math anyway.
Post by Daniel Verkamp
- Flesh out the help text.
Ironically, the expr implementation I have lying around here was
nothing _but_ help text (that's as far as I got), but I'm not finding
it at the moment...

Ah, no, I was thinking toys/pending/test.c.
Post by Daniel Verkamp
- Write more comprehensive test cases.
- Decide what to do about integer overflow (the current code can
execute undefined signed overflow behavior with large inputs; GNU
coreutils expr detects this and prints an appropriate error).
What does Posix require?
Post by Daniel Verkamp
- Implement the : operator - yes, in fine 'cat -v' tradition, POSIX
expr can match regular expressions.
Oh joy.

I note that part of the reason I've held off with this one is that
(like test.c) it's basically shell behavior. Test is [ ] and expr is
$(( )), and they should eventually share code. I haven't yet studied
_how_ similar they are and how much (if any0 they diverge...

And then there's bc, which thanks to Peter Anvin I now have to
implement to build unmodified linux source. (The Linux From Scratch
guys had to add it to chapter 5. Sigh.) Dunno what overlap's there,
haven't studied it yet...
Post by Daniel Verkamp
I have done some minimal testing while writing the command, but it
could use some real-world testing (I think the Linux kernel build
contains a few expr invocations, but I have not tried it with this
implementation).
Feel free to fold, spindle, or mutilate as desired.
I checked it in and put it on the todo list. Unfortunately, my todo
list has roving packs of archeologists circling it at this point,
looking for an unguarded moment to attack with brush and trowel and
plaster cast...

Thanks,

Rob
Rob Landley
2013-06-13 02:43:34 UTC
Permalink
Post by Daniel Verkamp
Post by Rob Landley
On Tue, Jun 4, 2013 at 11:06 PM, Rob Landley <rob at landley.net>
Post by Rob Landley
Post by Daniel Verkamp
- Decide what to do about integer overflow (the current code can
execute undefined signed overflow behavior with large inputs;
GNU
Post by Rob Landley
Post by Rob Landley
Post by Daniel Verkamp
coreutils expr detects this and prints an appropriate error).
What does Posix require?
The expr command description doesn't mention anything about integer
overflow at all; I don't know if there is some overall POSIX
requirement that applies.
Well, how did _you_ find out about it?
The C standard says signed integer overflow is undefined behavior, and
a user can trigger such behavior with crafted inputs. Try `expr
9223372036854775807 \* 2`, for example.
So you've never actually seen any real-world anything be inconvenienced
by this, you're just writing defensive code against a hypothetical the
standard doesn't require you to handle.

By the way, how would you test for overflow? There's no feraiseexcept()
in integer math that I'm aware of...
Post by Daniel Verkamp
Additionally, the GNU Coreutils implementation of expr prints a
specific message on overflow.
Bash is also a GNU program:

landley at driftwood:~/busybox/busybox$ echo
$((1000000*1000000*1000000*1000000))
2003764205206896640
landley at driftwood:~/busybox/busybox$ help | head -n 1
GNU bash, version 4.2.25(1)-release (x86_64-pc-linux-gnu)

The FSF is inconsistent (insane). They write autoconf tests that check
the sizeof uint32_t. Yes really, I was digging up some old autoconf
complaints recently because somebody was insane enough to try to defend
it:

http://landley.net/notes-2010.html#20-08-2010
http://landley.net/notes-2010.html#09-08-2010
http://landley.net/notes-2011.html#26-10-2011
http://landley.net/notes-2011.html#06-09-2011

The reason toybox exists (and busybox before it) is because the GNU
versions are overengineered paranoid crap, punitively licensed. "GNU
does it" is never by itself a reason for anything.
Post by Daniel Verkamp
Post by Rob Landley
Absent the standard explicitly requiring something, the next thing
I care
Post by Rob Landley
about is real world users. Who will _not_ doing it inconvenience?
At the very least, it's within the rights of the compiler to generate
code that aborts or crashes on overflow, and the potential for nasal
demons (or at least incorrect results) is probably enough to warrant
fixing it.
Once the nasal demons get typecast to a 64 bit integer they're unlikely
to go far. And any C environment that crashes on integer overflow can't
run the Linux kernel, so I'm not sure we care? (They intentionally
initialize the timer ticks to overflow around 120 seconds after boot,
to force everything to handle timer wraparound properly.)

Ok, now I'm curious, grep -i overflow in busybox/coreutils/expr.c:

/* Don't interpret the empty string as an integer. */
/* Currently does not worry about overflow or int/long
differences. */
i = STRTOL(v->u.s, &e, 10);

Code has been in the tree for:

commit 1b355ebba68bdd567dd3961a18291dfd9532c2e8
Author: Eric Andersen <andersen at codepoet.org>
Date: Tue Sep 5 17:37:48 2000 +0000

Added expr, from Edward Betts <edward at debian.org>, with some fixups
and docs added by me.
-Erik

Coming up on 13 years. And the closest anybody came to complaining
about "overflow" was:

commit a7f4e4bbd8d7a47a49404d28bc07ab3b5dc1c19b
Author: Denis Vlasenko <vda.linux at googlemail.com>
Date: Wed Apr 2 20:24:09 2008 +0000

expr: fix comparisons 'a < b' where we were overflowing a-b
(not to mention that we used int, not arith_t). closes bug 2744.

Not because they cared about the result of math that overflowed, but
because comparison was producing wrong results on numbers within the
storable range.
Post by Daniel Verkamp
I presume most real-world uses of expr don't cause overflow, since it
doesn't produce any useful results, but I suppose there could be
scripts that depend on the "return error on overflow" behavior of GNU
expr in some way.
There could be scripts that depend on non-posix behavior, yes. And
until I see an example of one, I can't judge whether they should fix
their broken code or we should humor them.
Post by Daniel Verkamp
Perhaps the easiest option would be to enable GCC's -ftrapv option,
which causes signed overflow to abort intentionally;
Hell no.

I'm confused: you list as a potential downside that expr might crash.
So the solutions are to add an error_exit() to force expr to crash, or
to add a compiler flag to force expr to crash. And this improves
matters how?
Post by Daniel Verkamp
this would not be
very user friendly, but it's probably better than generating wrong
answers.
Garbage in, garbage out. They get to keep the pieces.

A couple posts back you were ok with not always doing 64 bit math,
which is easy and known to help produce more right answers. Now you're
advocating for something that isn't necessarily easy (no feraisexcept()
for interger math), doesn't help produce more right answers.

In a larger context, the problem you want to address is that on
overflow it produces incorrect output (because C math does), so you'd
like it to produce a different kind of incorrect output, on the theory
that somebody is going to check the return code of expr in a script.

Here's a cut and paste from the Centos 6.4 kernel's top level Makefile,
which they copied verbatim from the current Red Hat Enterprise:

ifneq (,$(filter $(ARCH), i386 x86_64))
CPP_MAJOR := $(shell $(CPP) -dumpversion 2>&1 | cut -d'.' -f1)
CPP_MINOR := $(shell $(CPP) -dumpversion 2>&1 | cut -d'.' -f2)
CPP_PATCH := $(shell $(CPP) -dumpversion 2>&1 | cut -d'.' -f3)
# Assumes that major, minor, and patch cannot exceed 999
CPP_VERS := $(shell expr $(CPP_MAJOR) \* 1000000 + $(CPP_MINOR)
\* 1000 \
+ $(CPP_PATCH))

# GCC Bugzilla Bug 43949:
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43949
# add -Wno-array-bounds to remove bogus warnings. This flag is present
in
# gcc version 4.4.4 .
ifeq ($(KBUILD_EXTMOD),)
KBUILD_CFLAGS += $(shell if [ $(CPP_VERS) -ge 4004004 ]; then \
echo "-Wno-array-bounds"; else echo ""; fi)

Guess what happens when you build that under SuSE Linux Enterprise
service pack 2, which uses gcc 4.3? (Not "4.3.0", but "4.3", so
CPP_PATCH is blank and the expr ends with a trailing + and throws an
error that isn't checked for instead of producing any output? And then
CPP_VERS is blank so the KBUILD_CFLAGS shell script snippet _also_
doesn't do any error checking on "if [ -ge 4004004 ]", so your make
outputs two syntax errors every time you run it even to do
"menuconfig", but otherwise works fine because all this crap is just to
tell gcc to produce extra warnings?

That's "Enterprise" code. (11a2b, 1b2b3, zero zero destruct zero.) I
hit that bug a few month back, and it was because expr didn't check the
result in any way. (No error exit, no "string is blank", no nothing. It
worked using the Red Hat compiler, which had X.Y.Z, and that's all Red
Hat ever tests.)
Post by Daniel Verkamp
However, this would generate larger and slower code throughout toybox.
See "Hell no.", above.
Post by Daniel Verkamp
Thanks,
-- Daniel Verkamp
I'm not saying I'm against handling it, I'm saying you have yet to make
a compelling case for it.

I note that I probably need to add an arbitrary precision math library
to implement bc, which is in posix and required to build an unmodified
linux kernel, so if we're GOING to care about overflow we could always
just avoid overflowing.

But until them, overflow doesn't really bother me if it doesn't bother
posix, busybox, or bash.

Rob
Loading...