Skip to content
This repository has been archived by the owner. It is now read-only.

no_sanitize("unsigned-integer-overflow") annotation for decremented size_type in __hash_table #38606

Closed
FlashSheridan opened this issue Aug 16, 2018 · 6 comments
Assignees

Comments

@FlashSheridan
Copy link

@FlashSheridan FlashSheridan commented Aug 16, 2018

Bugzilla Link 38606
Resolution FIXED
Resolved on Feb 07, 2019 10:54
Version unspecified
OS MacOS X
CC @FlashSheridan,@mclow

Extended Description

The Undefined Behavior Sanitizer with unsigned-integer-overflow enabled complains about the following code in https://llvm.org/viewvc/llvm-project/libcxx/trunk/include/__hash_table:

2251 __hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n)

2255 else if (__n & (__n - 1))

The bit-wise rather than logical ‘and’, to produce a Boolean, on an unsigned value which is being decremented, strikes me as poor style if not simply a mistake. It also prevents short-circiting, which might mitigate any performance hit to correcting this.
This is of course not actually undefined behavior, since decrementing an unsigned zero is defined to be a large positive value. But I’ve seen dozens of incorrect unsigned decrementing bugs detected by static analysis, and never a serious need to use unsigneds as elements of modular arithmetic rather than as a risky approximation to genuine integers. So this sanitizer option strikes me as worthwhile, but silencing the warning for this usage was fairly inconvenient for our build system.
This would not have inconvenienced us if PR 25706 had been implemented, but it seems not to have been, despite the resolution.

@FlashSheridan
Copy link
Author

@FlashSheridan FlashSheridan commented Aug 16, 2018

assigned to @mclow

Loading

@mclow
Copy link

@mclow mclow commented Aug 16, 2018

What do you think this code does?
(and what would you suggest replacing it with?)

Loading

@FlashSheridan
Copy link
Author

@FlashSheridan FlashSheridan commented Aug 17, 2018

Second question first: The minimal change would be to replace the “&” with “&&”, which silenced the warning, obviously has the same effect, and might be what the author originally intended. I hesitated to suggest a change of more than a single character change because I don’t understand why the author wrote it this way; e.g., there may be performance issues I’m not aware of.
I think the intent was just:
else if (__n != 0 && __n != 1)
which is what I would prefer if there’s no reason not to make the code clear.

Loading

@mclow
Copy link

@mclow mclow commented Aug 17, 2018

Second question first: The minimal change would be to replace the “&” with
“&&”, which silenced the warning, obviously has the same effect, and might
be what the author originally intended.

Sorry; that is incorrect.

I think the intent was just:
else if (__n != 0 && __n != 1)
which is what I would prefer if there’s no reason not to make the code clear.

This is incorrect as well.

Consider the following code:

#include

bool foo(unsigned x) { return x & x - 1; }
bool bar(unsigned x) { return x && x - 1; }

int main(int, char*[])
{
for (unsigned i = 1; i < 20; ++i)
if (!foo(i))
std::cout << i << " ";
std::cout << std::endl;
for (unsigned i = 1; i < 20; ++i)
if (!bar(i))
std::cout << i << " ";
std::cout << std::endl;
}

Does this print the same sequence twice? (Answer: No)

The expression (__n & __n - 1) is a check to see if n is not a power of two.
See http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2.

Loading

@FlashSheridan
Copy link
Author

@FlashSheridan FlashSheridan commented Aug 17, 2018

Duh, in that case all I ask is an annotation as in PR 25706.

Loading

@mclow
Copy link

@mclow mclow commented Feb 7, 2019

Annotation added in revision 353448.

Loading

This issue was closed.
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
2 participants