Page MenuHomePhabricator

Three new overflow builtins with generic argument types
ClosedPublic

Authored by DavidEGrayson on Sep 10 2015, 9:52 PM.

Details

Summary

This patch adds __builtin_add_overflow, __builtin_sub_overflow, and __builtin_mul_overflow to clang. These are useful functions and are easier to use than the existing overflow builtins because they can accept any type of integer for the inputs and output. GCC 5 already has these functions in it, and I think they should be added to clang.

The need for these built-ins is discussed here:

https://llvm.org/bugs/show_bug.cgi?id=21716

The repository I used to help develop this patch is here:

https://github.com/DavidEGrayson/builtin_overflow

The patch should apply cleanly to revision 248284 of clang. I added these new builtins to the documentation and added tests for them.

I went through some extra effort to support boolean arguments, even though GCC does not support boolean arguments for these functions.

I am new to clang/LLVM development and I am not really sure if I have submitted this patch in the right way. For example, I never found a way to select "clang" as the project that I am submitting this patch to. Please let me know if I there is a better way I can submit patches. I hope someone can review this and commit it to clang. Please let me know if there are any problems with it. Thanks!

Diff Detail

Event Timeline

DavidEGrayson retitled this revision from to Three new security overflow builtins with generic argument types.
DavidEGrayson updated this object.
DavidEGrayson added a reviewer: Restricted Project.
DavidEGrayson set the repository for this revision to rL LLVM.
DavidEGrayson updated this object.
DavidEGrayson updated this object.
DavidEGrayson removed a reviewer: Restricted Project.Sep 10 2015, 10:32 PM
rjmccall edited edge metadata.Sep 21 2015, 8:09 PM

Thanks for doing this; this is a great start.

docs/LanguageExtensions.rst
1720

Hmm. It's not necessarily truncation; you could meaningfully use these intrinsics to add two small signed numbers and store the result in an unsigned number. It's the unique representative value modulo 2^n, where n is the bit-width of the result.

lib/CodeGen/CGBuiltin.cpp
289

This should just take an ArrayRef. Also, please at least introduce a typedef for your pair type, and consider just making a little struct for it.

314

getIntegerWidthAndSignedness, please.

1601

These are not the most evocative names you could have chosen. :)

Also, this strategy is correct, but it produces horrible code when the operands have the same signedness and the result is different, where the result would otherwise be an ordinary operation and a compare. You really want to just merge the two operands and then max with the width of the result type.

1610

These aren't really security-specific; they're just arbitrary-precision.

1630

This is Builder.CreateIntegerCast(X, ELTy, XITy.second).

1667

EmitToMemory.

Thanks for looking at this patch, John! I disagreed with your comment about calculating the encompassing type, but I will incorporate everything else and make a new patch tonight or within a few days.

docs/LanguageExtensions.rst
1720

OK, I'll change the documentation because I like your way of phrasing it, but I think truncation always gives you the unique representative value modulo 2^n. If I'm adding ((int8_t)-1) to ((int8_t)-1), the infinite-width result would be -2, which in infinite-width binary is 11...1111111111110. Then we truncate it to 8 bits to get 11111110, which is 254. And 254 is also the unique representative value of -2 modulo 256.

lib/CodeGen/CGBuiltin.cpp
289

A struct called IntegerWidthAndSignedness sounds good to me, thanks. And I will learn how to use ArrayRef and use it here.

314

Sounds good. That frees up the name IntegerWidthAndSignedness to be used for my new struct.

1601

I don't think that would work. It sounds like you want me to remove RITy from the call to EncompassingIntegerType. That means the ecompassing type could be smaller than the result type, and the arithmetic intrinsic would report an overflow even though the mathematical result is representable in the result type.

For example, if I am multiplying ((uint8_t)100) by ((uint8_t)100) and storing the result in a (uint16_t), the result needs to be 10000 and there is no overflow. To arrive at that result, we need to convert the operands to 16-bit unsigned integers before multiplying them. If we multiply them as 8-bit unsigned integers, the multiplication intrinsic will report an overflow and give a result of 16. That seems like a messy situation and I don't see how a max operation would fix it.

1610

I agree that these functions are not security-specific. I just copied that message from a place a little bit lower in CGBuiltin.cpp where it was used to describe some other overflow builtins. I am happy to remove the word "security" from both places.

1630

Thanks, I thought there had to be a function for that already but just could not find it.

1667

Thanks again, will do.

rjmccall added inline comments.Sep 22 2015, 11:48 AM
docs/LanguageExtensions.rst
1720

When talking about mathematical abstractions, I think it's better to stick with mathematical presentations all the way through instead of mixing in the idea that the universe is 2's-complement. :)

lib/CodeGen/CGBuiltin.cpp
1601

I think I was unclear. I'm not saying that you should do a max as part of computing the dynamic result. I'm saying that, when deciding the encompassing type, it should still be at least as wide as the result, but you should ignore the result type's signedness and then patch it up with a comparison at the end if necessary. (I believe that in both cases, it's a signed comparison against zero.)

That is, when multiplying two uint8_t's and storing the result in an int16_t, we should just do an unsigned 16-bit multiply-with-overflow. The computation overflows if the multiply overflows (which it provably doesn't, but we can let LLVM figure that out for now) or the result is signed-< 0.

DavidEGrayson added a comment.EditedSep 23 2015, 9:34 AM

Hi John. I thought about your comment on line 1601 somewhat carefully and tried to imagine what it would look like. See my inline comment.

Also, by the way, do you know if the results of the LLVM intrinsics like llvm.smul.with.overflow.* are guaranteed to be well-defined when there is an overflow? This whole patch hinges on that, because the results of the builtins are supposed to be well-defined. The documentation _here_ is not so great.

lib/CodeGen/CGBuiltin.cpp
1601

OK, I understand now. As an optimization, you would to like the operation type (the width/signedness that we use to perform the main math operation) to sometimes be the same width as the result type (the type that the third argument points to) but have a different sign.

I'm thinking about how that would work in all the different cases. I have concluded that it would work in 5 out of 6 cases, but we would have to think carefully about each case and it is possible I have made some mistakes. But here are the 6 cases:

  1. __builtin_add_overflow, operation type signed, result type unsigned: It would work but it would be complicated. If the signed addition intrinsic reports an overflow, we need to know whether the result was too big (which is OK) or too small (which is bad). The most extreme underflow would be (-2^(N-1)) + (-2^(N-1)) = 0, so every underflow should give a non-negative result. Similarly, every overflow-proper (case where the result was too big) would result in a negative number. So the overflow bit returned from __builtin_add_overflow should be the overflow bit from the intrinsic XORed with a "less than zero" comparison.
  1. __builtin_add_overflow, operation type unsigned, result type signed: This is easier, because the only possible overflow reported by the unsigned addition intrinsic happens when the result is too big, which means it's definitely too big for the signed type. The overflow bit returned from __builtin_add_overflow in this case would be the overflow bit from the intrinsic ORed with a "less than zero" comparison.
  1. __builtin_sub_overflow, operation type signed, result type unsigned: If the signed subtraction intrinsic reports an overflow, we need to know whether the result was too big (which is OK) or too small (which is bad). The most extreme underflow would be (-2^(N-1)) - (2^(N-1)-1) = 1, so every underflow gives a positive value. The most extreme overflow-proper would be (2^(N-1)-1) - (-2^(N-1)) = -1, so every overflow-proper gives a negative number. Just like case #1, the overflow bit we return shoud be the overflow bit from the intrinsic XORed with a "less than zero" comparison.
  1. __builtin_sub_overflow, operation type unsigned, result type signed: If the unsigned subtraction intrinsic reports an overflow, it simply means Y > X. That is OK as long as Y isn't too much greater than X. The most extreme case is 0 - (2^N-1) = 1. So if the result from the intrinsic is less than zero, then we are OK. So the overflow bit returned from __builtin_sub_overflow should be the overflow bit from the intrinsic XORed with a "less than zero" comparison.
  1. __builtin_mul_overflow, operation type signed, result type unsigned: I don't think this case would work, so we would have to fall back to using an operation type that actually encompasses the result type. For example, if we are multiplying two int16_t and the result is uint16_t, and the intrinsic gives us an overflow, it's really hard to know whether that overflow was OK (200 * 200) or not OK (200 * 527).
  1. __builtin_mul_overflow, operation type unsigned, result type signed: The logic from case 2 applies here.

Do you want the patch to go in this direction? Since we have to consider these 6 cases, I think it would be more complicated than what you were describing.

Yes, the main result is defined to be the true value mod 2^k even when overflow occurs. We do use the intrinsics to implement the existing fixed-width GCC builtins, which are meant to be useful not just for security checking, but for implementing arbitrary-precision arithmetic libraries. (LLVM doesn't seem to reliably do the add/adc peepholes that make that performant, though.)

lib/CodeGen/CGBuiltin.cpp
1601

Oh, I see your point; I wasn't thinking about the fact that some of the overflows aren't necessarily overflows in the result type. Going ahead with your original approach seems reasonable.

scanon added a subscriber: scanon.Sep 23 2015, 1:06 PM
DavidEGrayson edited edge metadata.
DavidEGrayson removed rL LLVM as the repository for this revision.

I have changed the patch to incorporate most of John McCall's feedback. The only thing I didn't act on was the suggestion to change the names of the variables XITy, YITy, RITy, and EITy, because I could not think of anything better.

DavidEGrayson marked 18 inline comments as done.Sep 24 2015, 12:44 AM

X and Y aren't unreasonable for the operands, although you could also use "left" and "right" (or LHS/RHS), especially since it's significant for subtraction. R is short for "result" and should be spelled out. E is presumably short for "encompassing", but that is not immediately obvious even to someone reading your patch; spelling it out wouldn't hurt, or you could at least use a longer abbreviation.

You should also spell out the different *Ty suffixes in some way that differentiates them. I don't think you actually need the *QTy variables. The *ITy variables aren't really types and should not be named that way. *LLVMTy is not unreasonable for the IR types.

I have incorporated John McCall's feedback about variable naming. I was able to remove most of the *QTy variables, but ResultQTy is used in several places and the expression to compute it is pretty long, so I kept it.

I would argue that a struct with a width and signedness does in fact define an integer type. It's not a clang type or an LLVM type though. But that's fine, I renamed those variables to be called *Info.

Is there a better place to stick getIntegerWidthAndSignedness? It seems like a basic feature like this should be part of clang::Type or something.

DavidEGrayson retitled this revision from Three new security overflow builtins with generic argument types to Three new overflow builtins with generic argument types.Sep 28 2015, 8:45 AM
DavidEGrayson updated this object.

LGTM, thanks.

DavidEGrayson added inline comments.Sep 29 2015, 1:38 PM
lib/CodeGen/CGBuiltin.cpp
303

Sorry, I need to fix this incorrect comment. I would probably just remove the second paragraph. After that, the patch is probably good to be committed.

I changed the patch in two ways: it now returns ExprError() is the third argument is wrong (for consistency with the other argument checking code). I removed an outdated comment for EncompassingIntegerType.

Thanks for reviewing this, John! I think it is finally ready to be committed. Please let me know if I have to do anything else to get it committed.

This patch is still based on 248284, which is from 8 days ago. Hopefully it can still be committed cleanly.

DavidEGrayson marked an inline comment as done.Oct 7 2015, 10:37 AM

Well, it has been another week. John, I don't have commit access, so can you commit this? Thanks! Let me know if the patch doesn't apply cleanly or any tests fail.

Sorry for the delay. Committed with a few minor tweaks in r251650.

Thanks, John! Looks like it's actually committed in rL251651. Thanks for handling the volatile pointers correctly (I didn't know I had to do something special for them) and giving me credit in the commit message!

DavidEGrayson accepted this revision.Oct 30 2015, 9:02 AM
DavidEGrayson added a reviewer: DavidEGrayson.
This revision is now accepted and ready to land.Oct 30 2015, 9:02 AM