Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

array index constant folding uses signed bitwise arithmetic #15596

Open
p5pRT opened this issue Sep 10, 2016 · 14 comments
Open

array index constant folding uses signed bitwise arithmetic #15596

p5pRT opened this issue Sep 10, 2016 · 14 comments

Comments

@p5pRT
Copy link

@p5pRT p5pRT commented Sep 10, 2016

Migrated from rt.perl.org#129238 (status was 'open')

Searchable as RT129238$

@p5pRT
Copy link
Author

@p5pRT p5pRT commented Sep 10, 2016

From @mauke

Created by @mauke

#!perl
use strict;
use warnings;

my @​arr = qw(A B C D);

my $index = ~0;

print "index=$index​: $arr[$index]\n";
__END__

Output​:
index=4294967295​: D

Expected output​:
Use of uninitialized value $arr[4294967295] in concatenation (.) or string at bug.pl line 9.
index=4294967295​:

Perl Info

Flags:
    category=core
    severity=low

Site configuration information for perl 5.24.0:

Configured by mauke at Mon May  9 21:21:33 CEST 2016.

Summary of my perl5 (revision 5 version 24 subversion 0) configuration:
   
  Platform:
    osname=linux, osvers=4.4.5-1-arch, archname=i686-linux
    uname='linux simplicio 4.4.5-1-arch #1 smp preempt thu mar 10 07:54:30 cet 2016 i686 gnulinux '
    config_args=''
    hint=previous, useposix=true, d_sigaction=define
    useithreads=undef, usemultiplicity=undef
    use64bitint=undef, use64bitall=undef, uselongdouble=undef
    usemymalloc=n, bincompat5005=undef
  Compiler:
    cc='cc', ccflags ='-fwrapv -fno-strict-aliasing -pipe -fstack-protector-strong -I/usr/local/include -D_LARGEFILE_SOURCE -D_FILE_OFFSET_BITS=64',
    optimize='-O2 -flto',
    cppflags='-fwrapv -fno-strict-aliasing -pipe -fstack-protector-strong -I/usr/local/include'
    ccversion='', gccversion='6.1.1 20160501', gccosandvers=''
    intsize=4, longsize=4, ptrsize=4, doublesize=8, byteorder=1234, doublekind=3
    d_longlong=define, longlongsize=8, d_longdbl=define, longdblsize=12, longdblkind=3
    ivtype='long', ivsize=4, nvtype='double', nvsize=8, Off_t='off_t', lseeksize=8
    alignbytes=4, prototype=define
  Linker and Libraries:
    ld='cc', ldflags ='-fstack-protector-strong -L/usr/local/lib -flto'
    libpth=/usr/local/lib /usr/lib/gcc/i686-pc-linux-gnu/6.1.1/include-fixed /usr/lib /lib /usr/local/lib /usr/lib/gcc/i686-pc-linux-gnu/6.1.1/include-fixed /usr/lib
    libs=-lpthread -lnsl -lgdbm -ldb -ldl -lm -lcrypt -lutil -lc -lgdbm_compat
    perllibs=-lpthread -lnsl -ldl -lm -lcrypt -lutil -lc
    libc=libc-2.23.so, so=so, useshrplib=false, libperl=libperl.a
    gnulibc_version='2.23'
  Dynamic Linking:
    dlsrc=dl_dlopen.xs, dlext=so, d_dlsymun=undef, ccdlflags='-Wl,-E'
    cccdlflags='-fPIC', lddlflags='-shared -O2 -flto -L/usr/local/lib -fstack-protector-strong'



@INC for perl 5.24.0:
    /home/mauke/usr/lib/perl5/site_perl/5.24.0/i686-linux
    /home/mauke/usr/lib/perl5/site_perl/5.24.0
    /home/mauke/usr/lib/perl5/5.24.0/i686-linux
    /home/mauke/usr/lib/perl5/5.24.0
    .


Environment for perl 5.24.0:
    HOME=/home/mauke
    LANG=en_US.UTF-8
    LANGUAGE=en_US
    LC_COLLATE=C
    LC_MONETARY=de_DE.UTF-8
    LC_TIME=de_DE.UTF-8
    LD_LIBRARY_PATH (unset)
    LOGDIR (unset)
    PATH=/home/mauke/perl5/perlbrew/bin:/home/mauke/bin:/usr/local/sbin:/usr/local/bin:/usr/bin:/usr/bin/site_perl:/usr/bin/vendor_perl:/usr/bin/core_perl
    PERLBREW_BASHRC_VERSION=0.73
    PERLBREW_HOME=/home/mauke/.perlbrew
    PERLBREW_ROOT=/home/mauke/perl5/perlbrew
    PERL_BADLANG (unset)
    PERL_UNICODE=SAL
    SHELL=/bin/bash

@p5pRT
Copy link
Author

@p5pRT p5pRT commented Sep 10, 2016

From @mauke

Created by @mauke

$ perl -MO=Deparse -e 'foo(~42, $a[~42])'
foo(4294967253, $a[-43]);
-e syntax OK

$ perl -MO=Deparse -e 'use integer; foo(~42, $a[~42])'
use integer;
foo(-43, $a[-43]);
-e syntax OK

For some reason, array indices behave as if 'use integer' were in effect when
constant folding ~ (bit complement). The first example should say '4294967253'
both times.

Perl Info

Flags:
    category=core
    severity=low

Site configuration information for perl 5.24.0:

Configured by mauke at Mon May  9 21:21:33 CEST 2016.

Summary of my perl5 (revision 5 version 24 subversion 0) configuration:
   
  Platform:
    osname=linux, osvers=4.4.5-1-arch, archname=i686-linux
    uname='linux simplicio 4.4.5-1-arch #1 smp preempt thu mar 10 07:54:30 cet 2016 i686 gnulinux '
    config_args=''
    hint=previous, useposix=true, d_sigaction=define
    useithreads=undef, usemultiplicity=undef
    use64bitint=undef, use64bitall=undef, uselongdouble=undef
    usemymalloc=n, bincompat5005=undef
  Compiler:
    cc='cc', ccflags ='-fwrapv -fno-strict-aliasing -pipe -fstack-protector-strong -I/usr/local/include -D_LARGEFILE_SOURCE -D_FILE_OFFSET_BITS=64',
    optimize='-O2 -flto',
    cppflags='-fwrapv -fno-strict-aliasing -pipe -fstack-protector-strong -I/usr/local/include'
    ccversion='', gccversion='6.1.1 20160501', gccosandvers=''
    intsize=4, longsize=4, ptrsize=4, doublesize=8, byteorder=1234, doublekind=3
    d_longlong=define, longlongsize=8, d_longdbl=define, longdblsize=12, longdblkind=3
    ivtype='long', ivsize=4, nvtype='double', nvsize=8, Off_t='off_t', lseeksize=8
    alignbytes=4, prototype=define
  Linker and Libraries:
    ld='cc', ldflags ='-fstack-protector-strong -L/usr/local/lib -flto'
    libpth=/usr/local/lib /usr/lib/gcc/i686-pc-linux-gnu/6.1.1/include-fixed /usr/lib /lib /usr/local/lib /usr/lib/gcc/i686-pc-linux-gnu/6.1.1/include-fixed /usr/lib
    libs=-lpthread -lnsl -lgdbm -ldb -ldl -lm -lcrypt -lutil -lc -lgdbm_compat
    perllibs=-lpthread -lnsl -ldl -lm -lcrypt -lutil -lc
    libc=libc-2.23.so, so=so, useshrplib=false, libperl=libperl.a
    gnulibc_version='2.23'
  Dynamic Linking:
    dlsrc=dl_dlopen.xs, dlext=so, d_dlsymun=undef, ccdlflags='-Wl,-E'
    cccdlflags='-fPIC', lddlflags='-shared -O2 -flto -L/usr/local/lib -fstack-protector-strong'



@INC for perl 5.24.0:
    /home/mauke/usr/lib/perl5/site_perl/5.24.0/i686-linux
    /home/mauke/usr/lib/perl5/site_perl/5.24.0
    /home/mauke/usr/lib/perl5/5.24.0/i686-linux
    /home/mauke/usr/lib/perl5/5.24.0
    .


Environment for perl 5.24.0:
    HOME=/home/mauke
    LANG=en_US.UTF-8
    LANGUAGE=en_US
    LC_COLLATE=C
    LC_MONETARY=de_DE.UTF-8
    LC_TIME=de_DE.UTF-8
    LD_LIBRARY_PATH (unset)
    LOGDIR (unset)
    PATH=/home/mauke/perl5/perlbrew/bin:/home/mauke/bin:/usr/local/sbin:/usr/local/bin:/usr/bin:/usr/bin/site_perl:/usr/bin/vendor_perl:/usr/bin/core_perl
    PERLBREW_BASHRC_VERSION=0.73
    PERLBREW_HOME=/home/mauke/.perlbrew
    PERLBREW_ROOT=/home/mauke/perl5/perlbrew
    PERL_BADLANG (unset)
    PERL_UNICODE=SAL
    SHELL=/bin/bash

@p5pRT
Copy link
Author

@p5pRT p5pRT commented Sep 10, 2016

From @Tux

On Sat, 10 Sep 2016 02​:10​:05 -0700, "l.mai@​web.de (via RT)"
<perlbug-followup@​perl.org> wrote​:

$ perl -MO=Deparse -e 'foo(~42, $a[~42])'
foo(4294967253, $a[-43]);
-e syntax OK

$ perl -MO=Deparse -e 'use integer; foo(~42, $a[~42])'
use integer;
foo(-43, $a[-43]);
-e syntax OK

For some reason, array indices behave as if 'use integer' were in effect when
constant folding ~ (bit complement). The first example should say '4294967253'
both times.

Ah, very likely the cause of my HP-UX 11.11 fails!

$ calc
Calc > -9223372032559582752
01000000000040000670740 / -9223372032559582752 / 0x80000001000371E0
Calc > 9223372041149968864
01000000000040000670740 / -9223372032559582752 / 0x80000001000371E0

From the logs …

# Multideref
() = "$a[140688675223280]";
EXPECTED​:
ok
Use of uninitialized value $a[140688675223280] in string at - line 15.
GOT​:
-9223372032559582752 != 9223372041149968864
Use of uninitialized value $a[140688675223280] in string at - line 15.
# Failed test 363 - 64-bit array subscripts at lib/warnings/9uninit line 2163
make​: *** [test_harness] Error 1

v5.25.4-21-g51068c1 Configuration (common) none
----------- ---------------------------------------------------------
O O O O O O
F F F F F F -Duse64bitall
O O O O O O -Duseithreads
F F F F F F -Duseithreads -Duse64bitall
| | | | | +- LC_ALL = univ.utf8 -DDEBUGGING
| | | | +--- PERLIO = perlio -DDEBUGGING
| | | +----- PERLIO = stdio -DDEBUGGING
| | +------- LC_ALL = univ.utf8
| +--------- PERLIO = perlio
+----------- PERLIO = stdio

Locally applied patches​:
  SMOKE51068c1406a3db6f7be27d5041ff91444bac8886

Testsuite was run only with 'harness'

Failures​: (common-args) none
[stdio/perlio/univ.utf8] -Duse64bitall
[stdio/perlio/univ.utf8] -DDEBUGGING -Duse64bitall
[stdio] -Duseithreads -Duse64bitall
[stdio] -DDEBUGGING -Duseithreads -Duse64bitall
../lib/warnings.t...........................................FAILED
  363

--
H.Merijn Brand http​://tux.nl Perl Monger http​://amsterdam.pm.org/
using perl5.00307 .. 5.25 porting perl5 on HP-UX, AIX, and openSUSE
http​://mirrors.develooper.com/hpux/ http​://www.test-smoke.org/
http​://qa.perl.org http​://www.goldmark.org/jeff/stupid-disclaimers/

@p5pRT
Copy link
Author

@p5pRT p5pRT commented Sep 10, 2016

The RT System itself - Status changed from 'new' to 'open'

@p5pRT
Copy link
Author

@p5pRT p5pRT commented Sep 11, 2016

From @jkeenan

On Sat Sep 10 02​:03​:48 2016, mauke- wrote​:

This is a bug report for perl from l.mai@​web.de,
generated with the help of perlbug 1.40 running under perl 5.24.0.

-----------------------------------------------------------------
[Please describe your issue here]

#!perl
use strict;
use warnings;

my @​arr = qw(A B C D);

my $index = ~0;

print "index=$index​: $arr[$index]\n";
__END__

Output​:
index=4294967295​: D

Expected output​:
Use of uninitialized value $arr[4294967295] in concatenation (.) or
string at bug.pl line 9.
index=4294967295​:

Is this a different bug from that which you've reported in https://rt-archive.perl.org/perl5/Ticket/Display.html?id=129238 ... or merely similar?

Thank you very much.

--
James E Keenan (jkeenan@​cpan.org)

@p5pRT
Copy link
Author

@p5pRT p5pRT commented Sep 11, 2016

The RT System itself - Status changed from 'new' to 'open'

@p5pRT
Copy link
Author

@p5pRT p5pRT commented Sep 11, 2016

From @mauke

On Sun Sep 11 07​:59​:20 2016, jkeenan wrote​:

On Sat Sep 10 02​:03​:48 2016, mauke- wrote​:

This is a bug report for perl from l.mai@​web.de,
generated with the help of perlbug 1.40 running under perl 5.24.0.

-----------------------------------------------------------------
[Please describe your issue here]

#!perl
use strict;
use warnings;

my @​arr = qw(A B C D);

my $index = ~0;

print "index=$index​: $arr[$index]\n";
__END__

Output​:
index=4294967295​: D

Expected output​:
Use of uninitialized value $arr[4294967295] in concatenation (.) or
string at bug.pl line 9.
index=4294967295​:

Is this a different bug from that which you've reported in
https://rt-archive.perl.org/perl5/Ticket/Display.html?id=129238 ... or merely
similar?

The symptoms are different, at least. The other bug is about constant folding. This one is about actual indexing at runtime ($index has the correct value).

@p5pRT
Copy link
Author

@p5pRT p5pRT commented Sep 12, 2016

From @iabyn

On Sat, Sep 10, 2016 at 02​:10​:05AM -0700, l.mai@​web.de wrote​:

# New Ticket Created by l.mai@​web.de
# Please include the string​: [perl #129238]
# in the subject line of all future correspondence about this issue.
# <URL​: https://rt-archive.perl.org/perl5/Ticket/Display.html?id=129238 >

This is a bug report for perl from l.mai@​web.de,
generated with the help of perlbug 1.40 running under perl 5.24.0.

-----------------------------------------------------------------
[Please describe your issue here]

$ perl -MO=Deparse -e 'foo(~42, $a[~42])'
foo(4294967253, $a[-43]);
-e syntax OK

$ perl -MO=Deparse -e 'use integer; foo(~42, $a[~42])'
use integer;
foo(-43, $a[-43]);
-e syntax OK

For some reason, array indices behave as if 'use integer' were in effect when
constant folding ~ (bit complement). The first example should say '4294967253'
both times.

Its not really to do with constant folding; its more to do with how
SvIsUV() values are treated when used as array indices, e.g.

  @​a = qw(a b c);
  $i = ~1;
  print $a[$i], "\n";

which prints "b".

The difficulty is what to do with an index which is a UV value with a value
greater than IV_MAX, since the array API (av_fetch() et al) take signed
indices.

A similar thing is seen with, e.g. $i = 1E99, where SvIV(sv)
calls Perl_sv_2iv_flags which calls S_sv_2iuv_common().
The latter sets the SV to UV_MAX; then Perl_sv_2iv_flags has to return
an IV arg, so UV_MAX gets wrapped to IV value of -1.

I'm not sure anything sensible can be done with this.

--
"Foul and greedy Dwarf - you have eaten the last candle."
  -- "Hordes of the Things", BBC Radio.

@p5pRT
Copy link
Author

@p5pRT p5pRT commented Sep 12, 2016

From @iabyn

On Mon, Sep 12, 2016 at 09​:29​:43AM +0100, Dave Mitchell wrote​:

I'm not sure anything sensible can be done with this.

Although I suppose that when the index is known at compile-time
(because it's a constant), then when converting it (again at compile time)
into an IV to store in an aelemfast or multideref op, we could
warn that the index is too large.

I'd be reluctant to include such checks at run-time though, due to the
performance hit. So we'd have

  $a[~1] # warns
  $i =~1; $a[$i] # silently treated as $a[-2]

--
print+qq&$}$"$/$s$,$a$d$g$s$@​$.$q$,$​:$.$q$^$,$@​$a$$;$.$q$m&if+map{m,^\d{0\,},,${$​::{$'}}=chr($"+=$&||1)}q&10m22,42}6​:17a22.3@​3;^2dg3q/s"&=~m*\d\*.*g

@p5pRT
Copy link
Author

@p5pRT p5pRT commented Sep 12, 2016

From @iabyn

On Mon, Sep 12, 2016 at 09​:39​:16AM +0100, Dave Mitchell wrote​:

On Mon, Sep 12, 2016 at 09​:29​:43AM +0100, Dave Mitchell wrote​:

I'm not sure anything sensible can be done with this.

Although I suppose that when the index is known at compile-time
(because it's a constant), then when converting it (again at compile time)
into an IV to store in an aelemfast or multideref op, we could
warn that the index is too large.

I'd be reluctant to include such checks at run-time though, due to the
performance hit. So we'd have

$a\[~1\]          \# warns
$i =~1; $a\[$i\]  \# silently treated as $a\[\-2\]

Thinking further.

There are two issues here. The first is that SvIV(sv), when applied to an
SVf_IVisUV SV, just casts the UV value to an IV value, so very large
integers get wrapped to negative integers.

Second, since the AV API functions take SSize_t keys, on platforms where
sizeof(IV) > sizeof(SSize_t) (e.g. a 32-bit platform with -Duse64bitint),
the IV is then cast to SSize_t, involving further potential truncation and
wrapping.

Perhaps we need an SvSSize(sv) function to be used instead of SvIV(sv) by
array access ops, which truncates any out-of-range values to +/-
SSize_t_MAX?

Exactly how this is fixed depends on what semantics we want. I guess the
behaviour we want is that any array index which is too large gets
truncated to SSize_t_MAX​: then for a read, it silently returns undef, and
for a write it dies with "Out of memory".

Similarly, any negative index whose magnitude is too large gets truncated
to -SSize_t_MAX-1, and then typically dies with

  Modification of non-creatable array value attempted

The other question then is whether truncation of the index should
warn or not. My gut feeling is not to warn.

--
But Pity stayed his hand. "It's a pity I've run out of bullets",
he thought. -- "Bored of the Rings"

@p5pRT
Copy link
Author

@p5pRT p5pRT commented Sep 12, 2016

From @iabyn

On Sun, Sep 11, 2016 at 08​:32​:03AM -0700, l.mai@​web.de via RT wrote​:

On Sun Sep 11 07​:59​:20 2016, jkeenan wrote​:

Is this a different bug from that which you've reported in
https://rt-archive.perl.org/perl5/Ticket/Display.html?id=129238 ... or merely
similar?

The symptoms are different, at least. The other bug is about constant
folding. This one is about actual indexing at runtime ($index has the
correct value).

The issue is the same​: the only difference between the two tickets is
whether SvIV() mangles the index at compile time or run time. I'll merge
the tickets, and I suggest any further discussion take place with the
[perl #129238] subject line.

--
Monto Blanco... scorchio!

@p5pRT
Copy link
Author

@p5pRT p5pRT commented Sep 12, 2016

From @dcollinsn

Is this bug also related to https://rt-archive.perl.org/perl5/Ticket/Display.html?id=67424
(RT #67424 perl​: missing / incorrect overflow check when indexing arrays)?

On Mon, Sep 12, 2016 at 6​:25 AM, Dave Mitchell <davem@​iabyn.com> wrote​:

On Mon, Sep 12, 2016 at 09​:39​:16AM +0100, Dave Mitchell wrote​:

On Mon, Sep 12, 2016 at 09​:29​:43AM +0100, Dave Mitchell wrote​:

I'm not sure anything sensible can be done with this.

Although I suppose that when the index is known at compile-time
(because it's a constant), then when converting it (again at compile
time)
into an IV to store in an aelemfast or multideref op, we could
warn that the index is too large.

I'd be reluctant to include such checks at run-time though, due to the
performance hit. So we'd have

$a\[~1\]          \# warns
$i =~1; $a\[$i\]  \# silently treated as $a\[\-2\]

Thinking further.

There are two issues here. The first is that SvIV(sv), when applied to an
SVf_IVisUV SV, just casts the UV value to an IV value, so very large
integers get wrapped to negative integers.

Second, since the AV API functions take SSize_t keys, on platforms where
sizeof(IV) > sizeof(SSize_t) (e.g. a 32-bit platform with -Duse64bitint),
the IV is then cast to SSize_t, involving further potential truncation and
wrapping.

Perhaps we need an SvSSize(sv) function to be used instead of SvIV(sv) by
array access ops, which truncates any out-of-range values to +/-
SSize_t_MAX?

Exactly how this is fixed depends on what semantics we want. I guess the
behaviour we want is that any array index which is too large gets
truncated to SSize_t_MAX​: then for a read, it silently returns undef, and
for a write it dies with "Out of memory".

Similarly, any negative index whose magnitude is too large gets truncated
to -SSize_t_MAX-1, and then typically dies with

Modification of non\-creatable array value attempted

The other question then is whether truncation of the index should
warn or not. My gut feeling is not to warn.

--
But Pity stayed his hand. "It's a pity I've run out of bullets",
he thought. -- "Bored of the Rings"

@p5pRT
Copy link
Author

@p5pRT p5pRT commented Dec 2, 2017

From @Tux

Ping. Any progress? Dave?

I am currently building the HP-UX depots for 5.26.1, and this is still hit.

@p5pRT
Copy link
Author

@p5pRT p5pRT commented Dec 2, 2017

From @iabyn

On Sat, Dec 02, 2017 at 03​:18​:57AM -0800, H. Merijn Brand via RT wrote​:

Ping. Any progress? Dave?

Its on my list, but haven;t looked at it yet.

--
That he said that that that that is is is debatable, is debatable.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
1 participant