gmake-4.2.90 regression (segmentation fault in sum_up_to_nul )

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

gmake-4.2.90 regression (segmentation fault in sum_up_to_nul )

Gnu - Make - Bugs mailing list
Good morning.

sum_up_to_nul reads 4 bytes starting from the passed string 'p'.
'p' can have fewer than 4 bytes. Usually there more allocated space
after 'p', which prevents this reading from manifesting itself. This
reading manifests itself visibly when 'p' points to the end of the
allocated block of memory, such that p + 3 points to not allocated
memory.
Please have a look at the patch in the attachment.
Tested on both big and little endian, 32 and 64 bit.

regards, Dmitry

_______________________________________________
Bug-make mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/bug-make

fix_sum_up_to_nul.diff (4K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: gmake-4.2.90 regression (segmentation fault in sum_up_to_nul )

Paul Smith-43
On Tue, 2019-09-03 at 04:14 +0000, Dmitry Goncharov via Bug reports and
discussion for GNU make wrote:
> sum_up_to_nul reads 4 bytes starting from the passed string 'p'.
> 'p' can have fewer than 4 bytes. Usually there more allocated space
> after 'p', which prevents this reading from manifesting itself. This
> reading manifests itself visibly when 'p' points to the end of the
> allocated block of memory, such that p + 3 points to not allocated
> memory.
> Please have a look at the patch in the attachment.
> Tested on both big and little endian, 32 and 64 bit.

I understand the issue.  The reason for the "special" code here is
performance, and unfortunately the solution proposed will reduce
performance by a measurable amount (not huge but measurable).

Your subject seems to suggest that you got a coredump: can you clarify
what system / compiler / etc. that was on?  Although obviously it's
technically invalid to access beyond the end of a string, it typically
does work without failure (I see no issues on any of my test systems
for example), unless you're doing something fancy such as shared memory
etc. where accessing even one byte beyond a boundary could give a
segmentation fault.  However, GNU make certainly doesn't do anything
like that.

With "normal" systems it's safe to read (only) memory beyond the end of
an array, at least up to the next word size, which is what this code
does.


_______________________________________________
Bug-make mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/bug-make
Reply | Threaded
Open this post in threaded view
|

Re: gmake-4.2.90 regression (segmentation fault in sum_up_to_nul )

Gnu - Make - Bugs mailing list
It indeed crashes with a core dump. I observed this on sunos/gcc when
p+3 points to the next page.
This should be easy to reproduce with a tool like libefence. Another
way to reproduce is to run $(wildcard hello*) in a directory with
thousands of files.

regards, Dmitry

On Tue, Sep 24, 2019 at 1:01 PM Paul Smith <[hidden email]> wrote:

>
> On Tue, 2019-09-03 at 04:14 +0000, Dmitry Goncharov via Bug reports and
> discussion for GNU make wrote:
> > sum_up_to_nul reads 4 bytes starting from the passed string 'p'.
> > 'p' can have fewer than 4 bytes. Usually there more allocated space
> > after 'p', which prevents this reading from manifesting itself. This
> > reading manifests itself visibly when 'p' points to the end of the
> > allocated block of memory, such that p + 3 points to not allocated
> > memory.
> > Please have a look at the patch in the attachment.
> > Tested on both big and little endian, 32 and 64 bit.
>
> I understand the issue.  The reason for the "special" code here is
> performance, and unfortunately the solution proposed will reduce
> performance by a measurable amount (not huge but measurable).
>
> Your subject seems to suggest that you got a coredump: can you clarify
> what system / compiler / etc. that was on?  Although obviously it's
> technically invalid to access beyond the end of a string, it typically
> does work without failure (I see no issues on any of my test systems
> for example), unless you're doing something fancy such as shared memory
> etc. where accessing even one byte beyond a boundary could give a
> segmentation fault.  However, GNU make certainly doesn't do anything
> like that.
>
> With "normal" systems it's safe to read (only) memory beyond the end of
> an array, at least up to the next word size, which is what this code
> does.
>

_______________________________________________
Bug-make mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/bug-make
Reply | Threaded
Open this post in threaded view
|

Re: gmake-4.2.90 regression (segmentation fault in sum_up_to_nul )

David A. Wheeler
In reply to this post by Paul Smith-43
It is extremely dangerous to dereference outside and allocated range, and it really should never be done today. As you well know, in C that is undefined. However over the last few years the C compilers have been getting increasingly aggressive to implement optimizations that assume that no one would ever do anything undefined. So even if it happens to work on your test systems today, it is increasingly unlikely to work over the next few years. At one time you could call C a high-level assembler, but that is simply no longer the case.

If you want the code to be reliable, and presumably you do, then you really want to avoid this kind of undefined behavior.


--- David A.Wheeler
_______________________________________________
Bug-make mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/bug-make
Reply | Threaded
Open this post in threaded view
|

Re: gmake-4.2.90 regression (segmentation fault in sum_up_to_nul )

Edward Welbourne-3
In reply to this post by Paul Smith-43
On Tue, 2019-09-03 at 04:14 +0000, Dmitry Goncharov wrote:
>> sum_up_to_nul reads 4 bytes starting from the passed string 'p'.  'p'
>> can have fewer than 4 bytes. Usually there more allocated space after
>> 'p', which prevents this reading from manifesting itself.

Usually malloc aligns its allocations on word boundaries, since the
caller typically needs that.  It also typically rounds up all
allocations to a whole number of words, since it can't represent the
residue from a partial word in its free list.  So usually the allocation
ends on a word boundary, even if what was asked for didn't.  Thus if the
iteration that's reading four bytes at a time starts at the allocation's
start, this should usually be safe.

Not that it's good practice to rely on this, though ...

>> This reading manifests itself visibly when 'p' points to the end of
>> the allocated block of memory, such that p + 3 points to not
>> allocated memory.

Did the scan start from part way through an allocated string ?  That
could put it at a non-word-aligned offset from the allocation's start.

>> Please have a look at the patch in the attachment.
>> Tested on both big and little endian, 32 and 64 bit.

Paul Smith (24 September 2019 18:38) replied:
> I understand the issue.  The reason for the "special" code here is
> performance, and unfortunately the solution proposed will reduce
> performance by a measurable amount (not huge but measurable).

[snip]

> With "normal" systems it's safe to read (only) memory beyond the end
> of an array, at least up to the next word size, which is what this
> code does.

If you want to be able to rely on this "normal" behaviour, for the sake
of the performance benefit it gives you, you need to add three to every
call to malloc, so as to make it well-defined.  Of course, that shall
increase memory use by a measurable amount (not huge, but measurable).

        Eddy.

_______________________________________________
Bug-make mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/bug-make
Reply | Threaded
Open this post in threaded view
|

Re: gmake-4.2.90 regression (segmentation fault in sum_up_to_nul )

Paul Smith-20
On Wed, 2019-09-25 at 08:29 +0000, Edward Welbourne wrote:
> > With "normal" systems it's safe to read (only) memory beyond the end
> > of an array, at least up to the next word size, which is what this
> > code does.
>
> If you want to be able to rely on this "normal" behaviour, for the sake
> of the performance benefit it gives you, you need to add three to every
> call to malloc, so as to make it well-defined.  Of course, that shall
> increase memory use by a measurable amount (not huge, but measurable).

I suspect the issue is that sometimes we want to hash constant strings
which are not allocated on the heap and may be placed in memory
segments which fail if read past; it's not really possible to increase
their sizes (I guess I could add "\0\0\0" to the end of all of them
but...)

And of course, sometimes strings are returned by the C runtime, not
allocated by us (dirent etc.) so we'd have to copy them into our own
larger memory before hashing.  Seems not so great.

I will work on avoiding the memory over-read, although Paolo did all
the performance testing/improvements etc. and I don't have his
infrastructure for checking it.


_______________________________________________
Bug-make mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/bug-make
Reply | Threaded
Open this post in threaded view
|

Re: gmake-4.2.90 regression (segmentation fault in sum_up_to_nul )

Gnu - Make - Bugs mailing list
In reply to this post by Paul Smith-43
On Tue, Sep 24, 2019 at 1:01 PM Paul Smith <[hidden email]> wrote:
> The reason for the "special" code here is
> performance, and unfortunately the solution proposed will reduce
> performance by a measurable amount (not huge but measurable).

Paul, is this call to strlen that you are concerned with?
It is possible to optimize somewhat (at the expense of source code
simplicity) by having jhash_string take the length of the string from
the caller.
Atleast some of the callers (e.g. file.c) already call strlen.
Or are you concerned with the computation to update klen?

regards, Dmitry

_______________________________________________
Bug-make mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/bug-make
Reply | Threaded
Open this post in threaded view
|

Re: gmake-4.2.90 regression (segmentation fault in sum_up_to_nul )

Paul Smith-20
In reply to this post by Gnu - Make - Bugs mailing list
On Tue, 2019-09-03 at 04:14 +0000, Dmitry Goncharov via Bug reports and
discussion for GNU make wrote:
> sum_up_to_nul reads 4 bytes starting from the passed string 'p'.
> 'p' can have fewer than 4 bytes. Usually there more allocated space
> after 'p', which prevents this reading from manifesting itself. This
> reading manifests itself visibly when 'p' points to the end of the
> allocated block of memory, such that p + 3 points to not allocated
> memory.
> Please have a look at the patch in the attachment.
> Tested on both big and little endian, 32 and 64 bit.

Thanks Dmitry I applied a patch similar to yours (will push soon).


_______________________________________________
Bug-make mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/bug-make