[PING][PATCH] correct handling of indices into arrays with elements larger than 1 (PR c++/96511)

Martin Sebor msebor@gmail.com
Sun Oct 11 22:45:00 GMT 2020


On 10/9/20 9:13 AM, Jason Merrill wrote:
> On 10/9/20 10:51 AM, Martin Sebor wrote:
>> On 10/8/20 1:40 PM, Jason Merrill wrote:
>>> On 10/8/20 3:18 PM, Martin Sebor wrote:
>>>> On 10/7/20 3:01 PM, Jason Merrill wrote:
>>>>> On 10/7/20 4:11 PM, Martin Sebor wrote:
>>>> ...
>>>>
>>>>>>>>>>>>> For the various member functions, please include the 
>>>>>>>>>>>>> comments with the definition as well as the in-class 
>>>>>>>>>>>>> declaration.
>>>>>>>>>>>>
>>>>>>>>>>>> Only one access_ref member function is defined out-of-line: 
>>>>>>>>>>>> offset_bounded().  I've adjusted the comment and copied it 
>>>>>>>>>>>> above
>>>>>>>>>>>> the function definition.
>>>>>
>>>>> And size_remaining, as quoted above?
>>>>
>>>> I have this in my tree:
>>>>
>>>> /* Return the maximum amount of space remaining and if non-null, set
>>>>     argument to the minimum.  */
>>>>
>>>> I'll add it when I commit the patch.
>>>>
>>>>>
>>>>> I also don't see a comment above the definition of offset_bounded 
>>>>> in the new patch?
>>>>
>>>> There is a comment in the latest patch.
>>>>
>>>> ...
>>>>>>>>>>>> The goal of conditionals is to avoid overwhelming the user with
>>>>>>>>>>>> excessive numbers that may not be meaningful or even relevant
>>>>>>>>>>>> to the warning.  I've corrected the function body, tweaked and
>>>>>>>>>>>> renamed the get_range function to get_offset_range to do a 
>>>>>>>>>>>> better
>>>>>>>>>>>> job of extracting ranges from the types of some nonconstant
>>>>>>>>>>>> expressions the front end passes it, and added a new test for
>>>>>>>>>>>> all this.  Attached is the new revision.
>>>>>
>>>>> offset_bounded looks unchanged in the new patch.  It still returns 
>>>>> true iff either the range is a single value or one of the bounds 
>>>>> are unrepresentable in ptrdiff_t.  I'm still unclear how this 
>>>>> corresponds to "Return true if OFFRNG is bounded to a subrange of 
>>>>> possible offset values."
>>>>
>>>> I don't think you're looking at the latest patch.  It has this:
>>>>
>>>> +/* Return true if OFFRNG is bounded to a subrange of offset values
>>>> +   valid for the largest possible object.  */
>>>> +
>>>>   bool
>>>>   access_ref::offset_bounded () const
>>>>   {
>>>> -  if (offrng[0] == offrng[1])
>>>> -    return false;
>>>> -
>>>>     tree min = TYPE_MIN_VALUE (ptrdiff_type_node);
>>>>     tree max = TYPE_MAX_VALUE (ptrdiff_type_node);
>>>> -  return offrng[0] <= wi::to_offset (min) || offrng[1] >= 
>>>> wi::to_offset (max);
>>>> +  return wi::to_offset (min) <= offrng[0] && offrng[1] <= 
>>>> wi::to_offset (max);
>>>>   }
>>>>
>>>> Here's a link to it in the archive:
>>>>
>>>> https://gcc.gnu.org/pipermail/gcc-patches/2020-September/555019.html
>>>> https://gcc.gnu.org/pipermail/gcc-patches/attachments/20200928/9026783a/attachment-0003.bin 
>>>
>>>
>>>
>>>
>>> Ah, yes, there are two patches in that email; the first introduces 
>>> the broken offset_bounded, and the second one fixes it without 
>>> mentioning that in the ChangeLog.  How about moving the fix to the 
>>> first patch?
>>
>> Sure, I can do that.  Anything else or is the final version okay
>> to commit with this adjustment?
> 
> OK with that adjustment.

I've done more testing and found a bug in the second patch: adding
an offset in an inverted range to an existing offset range isn't as
simple as adding up the bounds because they mean different things:
like an anti-range, an inverted range is a union of two subranges.
Instead, the upper bound needs to be extended to PTRDIFF_MAX because
that is the maximum being added, and the lower bound either reset to
zero if the absolute value of the maximum being added is less than
it, or incremented by the absolute value otherwise.

For example, given:

   char a[8];
   char *pa = a;
   char *p1 = pa + i;   // i's range is [3, 5]
   char *p2 = p1 + j;   // j's range is [1, -4]

the range of p2's offset isn't [4, 1] but [4, PTRDIFF_MAX] (or more
precisely [4, 8] if we assume it's valid).  But the range of p3's
valid offset in this last pointer

   char *p3 = p2 + k;   // k's range is [5, -4]

is all of [0, PTRDIFF_MAX] (or, more accurately, [0, 8]).

This may seem obvious but it took me a while at first to wrap my head
around.

I've tweaked access_ref::add_offset in the patch to handle this
correctly.  The function now ensures that every offset is in
a regular range (and not an inverted one).  That in turn simplifies
access_ref::size_remaining.  Since an inverted range is the same as
an anti-range, there's no reason to exclude the latter anymore(*).
The diff on top of the approved patch is attached.

I've retested this new revision of the patch with Glibc and GDB/
Binutils, (the latter fails due to PR 97360), and the Linux kernel.

Please let me know if you have any questions or concerns with
this change.  If not, I'd like to commit it sometime tomorrow.

Martin

[*] I was curious how often these inverted ranges/anti-ranges come
up in pointer arithmetic to see if handling them is worthwhile.  I
instrumented GCC to print them in get_range() on master where they
are only looked at in calls to built-in functions, and in another
patch I'm working on where they are looked at for every pointer
addition.  They account for 16% to 23% (GCC and Glibc, respectively)
and 22% to 32% (Glibc and GCC).  The detailed results are below.

GCC
   Builtin pointer arithmetic:
     kind         ordinary      inverted
     RANGE        636 (38%)     150 ( 9%)
     ANTI_RANGE    28 ( 1%)      99 ( 6%)
     VARYING      733 (44%)
     total       1397 (84%)     249 (15%)

   All pointer arithmetic:
     kind         ordinary      inverted
     RANGE        4663 (45%)   2945 (28%)
     ANTI_RANGE    134 ( 1%)    119 ( 1%)
     VARYING      2344 (22%)
     total        7141 (69%)   3064 (30%)

Glibc
   Builtin pointer arithmetic:
     kind         ordinary      inverted
     RANGE        488 (37%)     191 (14%)
     ANTI_RANGE    18 ( 1%)     112 ( 8%)
     VARYING      509 (38%)
     total       1015 (77%)     303 (22%)

   All pointer arithmetic:
     kind         ordinary      inverted
     RANGE       1941 (51%)     636 (16%)
     ANTI_RANGE    41 ( 1%)     202 ( 5%)
     VARYING      952 (25%)
     total       2934 (77%)     838 (22%)
-------------- next part --------------
A non-text attachment was scrubbed...
Name: gcc-compute_objsize-tweak.diff
Type: text/x-patch
Size: 8337 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/gcc-patches/attachments/20201011/c81483ef/attachment.bin>


More information about the Gcc-patches mailing list