Bug 88147 - ICE in linemap_line_start, at libcpp/line-map.c:781 starting from r265875
Summary: ICE in linemap_line_start, at libcpp/line-map.c:781 starting from r265875
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: lto (show other bugs)
Version: 9.0
: P1 normal
Target Milestone: 9.0
Assignee: Martin Liška
URL:
Keywords: ice-on-valid-code
Depends on:
Blocks:
 
Reported: 2018-11-22 09:03 UTC by Martin Liška
Modified: 2019-03-11 11:19 UTC (History)
4 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail: 7.4.1, 8.3.1, 9.0
Last reconfirmed: 2018-11-22 00:00:00


Attachments
test-case (784.97 KB, application/x-xz)
2018-11-22 09:03 UTC, Martin Liška
Details
Partially reduced testcase (67.69 KB, application/x-xz)
2019-02-05 21:08 UTC, David Malcolm
Details
Patch candidate (529 bytes, patch)
2019-02-11 10:37 UTC, Martin Liška
Details | Diff
Selftest coverage (922 bytes, patch)
2019-02-11 17:17 UTC, David Malcolm
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Martin Liška 2018-11-22 09:03:42 UTC
Created attachment 45064 [details]
test-case

Following is causing ICE:

$ g++ -pthread -shared -flto -o coin.so -O2 coin.ii
...
lto1: internal compiler error: in linemap_line_start, at libcpp/line-map.c:781
0x1559c2b linemap_line_start(line_maps*, unsigned int, unsigned int)
	/home/marxin/Programming/gcc/libcpp/line-map.c:781
0xabe713 lto_location_cache::apply_location_cache()
	/home/marxin/Programming/gcc/gcc/lto-streamer-in.c:194
0xabe801 stream_input_location_now(bitpack_d*, data_in*)
	/home/marxin/Programming/gcc/gcc/lto-streamer-in.c:304
0x140e0bb input_gimple_stmt
	/home/marxin/Programming/gcc/gcc/gimple-streamer-in.c:111
0x140e0bb input_bb(lto_input_block*, LTO_tags, data_in*, function*, int)
	/home/marxin/Programming/gcc/gcc/gimple-streamer-in.c:283
0xac179e input_function
	/home/marxin/Programming/gcc/gcc/lto-streamer-in.c:1092
0xac179e lto_read_body_or_constructor
	/home/marxin/Programming/gcc/gcc/lto-streamer-in.c:1295
0x819ac4 cgraph_node::get_untransformed_body()
	/home/marxin/Programming/gcc/gcc/cgraph.c:3545
0x825ba9 cgraph_node::expand()
	/home/marxin/Programming/gcc/gcc/cgraphunit.c:2166
0x826c43 expand_all_functions
	/home/marxin/Programming/gcc/gcc/cgraphunit.c:2334
0x826c43 symbol_table::compile()
	/home/marxin/Programming/gcc/gcc/cgraphunit.c:2685
0x78e4e9 lto_main()
	/home/marxin/Programming/gcc/gcc/lto/lto.c:3429

Note that the test case is ~15MB big, reduction is very problematic.
Comment 1 Jan Hubicka 2018-11-22 14:34:00 UTC
Hmm, this looks like another overfow in line map - my understanding is that the assert checks that correct line number is added.  I am not quite line_map expert :)
Comment 2 Martin Liška 2018-11-22 15:05:56 UTC
(In reply to Jan Hubicka from comment #1)
> Hmm, this looks like another overfow in line map - my understanding is that
> the assert checks that correct line number is added.  I am not quite
> line_map expert :)

Well, I'll try to run the creduce over weekend, hopefully we'll end up with a smaller test-case.
Comment 3 Jan Hubicka 2018-11-22 16:05:39 UTC
If it is simply location overflow it likely won't reduce into something simple :(
Comment 4 Jan Hubicka 2018-11-22 23:50:51 UTC
Unassigning myself for now since I have other PRs to track on the horizont and hopefully linemap gurus will chime in :))
Comment 5 Martin Liška 2018-11-23 12:23:24 UTC
Can't reduce that, not a surprise.
Comment 6 Martin Liška 2019-01-02 13:09:13 UTC
David can you please help us with that? Would it be possible to write a sanitization patch will catch an overflow?
Comment 7 David Malcolm 2019-01-02 21:42:38 UTC
I've been trying to reproduce this, but failing - I tried with today's trunk, and with a build from 2018-11-16.

Do you have a revision that is known to trigger the ICE?
Comment 8 Martin Liška 2019-01-03 08:36:19 UTC
(In reply to David Malcolm from comment #7)
> I've been trying to reproduce this, but failing - I tried with today's
> trunk, and with a build from 2018-11-16.
> 
> Do you have a revision that is known to trigger the ICE?

Started with r265875 and is gone with r266395 where Honza removed sorting of ODR types during LTO streaming in. Maybe one can't use expand_location before all stuff is read in LTO stream in?
Comment 9 Jakub Jelinek 2019-01-30 17:03:56 UTC
Doesn't ICE for me even if I (on current trunk) revert the r266395 change.
Do we need this as a P1 regression when it doesn't reproduce anymore?
Comment 10 David Malcolm 2019-02-02 12:46:59 UTC
FWIW I'm able to reproduce this with r265875 and am running a reduction script over this weekend to see if I can isolate what the issue is/was.
Comment 11 David Malcolm 2019-02-05 21:08:12 UTC
Created attachment 45610 [details]
Partially reduced testcase

This is 975366 bytes (decompressed) and takes 0.3-0.4 seconds to crash r265875's lto1, as compared to the ~15MB and 2.5 minutes it took for the original attachment.
Comment 12 Martin Liška 2019-02-08 12:42:35 UTC
Let me work on that..
Comment 13 Martin Liška 2019-02-11 10:20:00 UTC
I hope I understand the failure. So what happens:

- first a new map is created with to_line: 2578 (with m_column_and_range_bits == 13)
- then a new request comes with to_line: 404198, m_column_and_range_bits is extended to 15 and we decide to reuse the existing map.
- as seen the line difference is huge, ORDINARY_MAP_STARTING_LINE_NUMBER (map) - to_line == 401620
- that would require 18 bits to represent

I'm going to append a patch candidate.
Comment 14 Martin Liška 2019-02-11 10:37:23 UTC
Created attachment 45653 [details]
Patch candidate

Patch candidate that survives both reduced and not reduced test-cases.
David does the patch make sense?
Comment 15 Martin Liška 2019-02-11 11:24:14 UTC
During the bug investigation I noticed a strange thing in line-map.c:

   700    if (line_delta < 0
   701        || (line_delta > 10
   702            && line_delta * map->m_column_and_range_bits > 1000)
   703        || (max_column_hint >= (1U << effective_column_bits))
   704        || (max_column_hint <= 80 && effective_column_bits >= 10)
   705        || (highest > LINE_MAP_MAX_LOCATION_WITH_PACKED_RANGES
   706            && map->m_range_bits > 0)
   707        || (highest > LINE_MAP_MAX_LOCATION_WITH_COLS
   708            && (set->max_column_hint || highest >= LINE_MAP_MAX_LOCATION)))
   709      add_map = true;

m_column_and_range_bits > 1000 is always false as:

  /* Number of the low-order source_location bits used for column numbers
     and ranges.  */
  unsigned int m_column_and_range_bits : 8;

and the sub-expression on lines 701 and 702 is ugly as well.
What's the purpose of the check?
Comment 16 Martin Liška 2019-02-11 15:54:59 UTC
(In reply to Martin Liška from comment #14)
> Created attachment 45653 [details]
> Patch candidate
> 
> Patch candidate that survives both reduced and not reduced test-cases.
> David does the patch make sense?

It survives regression tests and bootstrap on x86_64-linux-gnu.
Comment 17 David Malcolm 2019-02-11 17:17:53 UTC
Created attachment 45660 [details]
Selftest coverage

The attached reproduces the problem via a minimal selftest, and is also fixed by attachment 45653 [details].
Comment 18 David Malcolm 2019-02-11 17:23:50 UTC
(In reply to Martin Liška from comment #15)
> During the bug investigation I noticed a strange thing in line-map.c:
> 
>    700    if (line_delta < 0
>    701        || (line_delta > 10
>    702            && line_delta * map->m_column_and_range_bits > 1000)
>    703        || (max_column_hint >= (1U << effective_column_bits))
>    704        || (max_column_hint <= 80 && effective_column_bits >= 10)
>    705        || (highest > LINE_MAP_MAX_LOCATION_WITH_PACKED_RANGES
>    706            && map->m_range_bits > 0)
>    707        || (highest > LINE_MAP_MAX_LOCATION_WITH_COLS
>    708            && (set->max_column_hint || highest >=
> LINE_MAP_MAX_LOCATION)))
>    709      add_map = true;
> 
> m_column_and_range_bits > 1000 is always false as:
> 
>   /* Number of the low-order source_location bits used for column numbers
>      and ranges.  */
>   unsigned int m_column_and_range_bits : 8;
> 
> and the sub-expression on lines 701 and 702 is ugly as well.
> What's the purpose of the check?

It's not:
  m_column_and_range_bits > 1000
it's:
  line_delta * map->m_column_and_range_bits > 1000

where line_delta is an int; presumably the 8 bits of the field get widened.

The purpose of the check is impose a limit on the size of the jumps that occur within the location_t representation, so that if there's a big jump in line numbers, we start a linemap, where big is "> 1000" within the location_t value.  The idea is to avoid wasting location_t values, without creating too many linemap instances.
Comment 19 David Malcolm 2019-02-11 17:27:40 UTC
(In reply to David Malcolm from comment #17)
> Created attachment 45660 [details]
> Selftest coverage
> 
> The attached reproduces the problem via a minimal selftest, and is also
> fixed by attachment 45653 [details].

Thanks for creating this patch.  I like that it imposes an upper limit on the value of a line number within an ordinary linemap relative to the line map's starting line, but I wonder if that upper limit needs to be lower than the one in your patch (e.g. what happens if the resulting location_t value hit limits like LINE_MAP_MAX_LOCATION etc).
Comment 20 David Malcolm 2019-02-11 19:55:01 UTC
(In reply to David Malcolm from comment #19)
> (In reply to David Malcolm from comment #17)
> > Created attachment 45660 [details]
> > Selftest coverage
> > 
> > The attached reproduces the problem via a minimal selftest, and is also
> > fixed by attachment 45653 [details].
> 
> Thanks for creating this patch.  I like that it imposes an upper limit on
> the value of a line number within an ordinary linemap relative to the line
> map's starting line, but I wonder if that upper limit needs to be lower than
> the one in your patch (e.g. what happens if the resulting location_t value
> hit limits like LINE_MAP_MAX_LOCATION etc).

I constructed a selftest that does that, but it doesn't lead to corrupt location_t values: it hits this check, and returns 0 (aka UNKNOWN_LOCATION):

771	  /* Locations of ordinary tokens are always lower than locations of
772	     macro tokens.  */
773	  if (r >= LINE_MAP_MAX_LOCATION)
774	    return 0;

So I think your fix is the one we should use.  I'm testing a combined patch with your fix + my selftest.
Comment 21 David Malcolm 2019-02-12 01:10:02 UTC
Author: dmalcolm
Date: Tue Feb 12 01:09:31 2019
New Revision: 268789

URL: https://gcc.gnu.org/viewcvs?rev=268789&root=gcc&view=rev
Log:
linemap_line_start: protect against location_t overflow (PR lto/88147)

PR lto/88147 reports an assertion failure due to a bogus location_t value
when adding a line to a pre-existing line map, when there's a large
difference between the two line numbers.

For some "large differences", this leads to a location_t value that exceeds
LINE_MAP_MAX_LOCATION, in which case linemap_line_start returns 0.  This
isn't ideal, but at least should lead to safe degradation of location
information.

However, if the difference is very large, it's possible for the line
number offset (relative to the start of the map) to be sufficiently large
that overflow occurs when left-shifted by the column-bits, and hence
the check against the LINE_MAP_MAX_LOCATION limit fails, leading to
a seemingly-valid location_t value, but encoding the wrong location.  This
triggers the assertion failure:
  linemap_assert (SOURCE_LINE (map, r) == to_line);

The fix (thanks to Martin) is to check for overflow when determining
whether to reuse an existing map, and to not reuse it if it would occur.

gcc/ChangeLog: David Malcolm  <dmalcolm@redhat.com>
	PR lto/88147
	* input.c (selftest::test_line_offset_overflow): New selftest.
	(selftest::input_c_tests): Call it.

libcpp/ChangeLog: Martin Liska  <mliska@suse.cz>
	PR lto/88147
	* line-map.c (linemap_line_start): Don't reuse the existing line
	map if the line offset is sufficiently large to cause overflow
	when computing location_t values.


Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/input.c
    trunk/libcpp/ChangeLog
    trunk/libcpp/line-map.c
Comment 22 David Malcolm 2019-02-12 01:14:31 UTC
Should be fixed by r268789.
Comment 23 Martin Liška 2019-02-12 08:30:13 UTC
> 
> The purpose of the check is impose a limit on the size of the jumps that
> occur within the location_t representation, so that if there's a big jump in
> line numbers, we start a linemap, where big is "> 1000" within the
> location_t value.  The idea is to avoid wasting location_t values, without
> creating too many linemap instances.

Ah, I see, thanks for clarification!
Comment 24 Martin Liška 2019-02-12 08:31:10 UTC
(In reply to David Malcolm from comment #22)
> Should be fixed by r268789.

Nice, thanks for test and cooperation.
Comment 25 Martin Liška 2019-03-11 09:38:12 UTC
Author: marxin
Date: Mon Mar 11 09:37:41 2019
New Revision: 269570

URL: https://gcc.gnu.org/viewcvs?rev=269570&root=gcc&view=rev
Log:
Backport r268789

2019-03-11  Martin Liska  <mliska@suse.cz>

	Backport from mainline
	2019-02-11  David Malcolm  <dmalcolm@redhat.com>

	PR lto/88147
	* input.c (selftest::test_line_offset_overflow): New selftest.
	(selftest::input_c_tests): Call it.
2019-03-11  Martin Liska  <mliska@suse.cz>

	Backport from mainline
	2019-02-11  Martin Liska  <mliska@suse.cz>

	PR lto/88147
	* line-map.c (linemap_line_start): Don't reuse the existing line
	map if the line offset is sufficiently large to cause overflow
	when computing location_t values.

Modified:
    branches/gcc-8-branch/gcc/ChangeLog
    branches/gcc-8-branch/gcc/input.c
    branches/gcc-8-branch/libcpp/ChangeLog
    branches/gcc-8-branch/libcpp/line-map.c
Comment 26 Martin Liška 2019-03-11 11:18:39 UTC
Author: marxin
Date: Mon Mar 11 11:18:08 2019
New Revision: 269576

URL: https://gcc.gnu.org/viewcvs?rev=269576&root=gcc&view=rev
Log:
Backport r268789

2019-03-11  Martin Liska  <mliska@suse.cz>

	Backport from mainline
	2019-02-11  David Malcolm  <dmalcolm@redhat.com>

	PR lto/88147
	* input.c (selftest::test_line_offset_overflow): New selftest.
	(selftest::input_c_tests): Call it.
2019-03-11  Martin Liska  <mliska@suse.cz>

	Backport from mainline
	2019-02-11  Martin Liska  <mliska@suse.cz>

	PR lto/88147
	* line-map.c (linemap_line_start): Don't reuse the existing line
	map if the line offset is sufficiently large to cause overflow
	when computing location_t values.

Modified:
    branches/gcc-7-branch/gcc/ChangeLog
    branches/gcc-7-branch/gcc/input.c
    branches/gcc-7-branch/libcpp/ChangeLog
    branches/gcc-7-branch/libcpp/line-map.c