CppCon 2016: Chandler Carruth “Garbage In, Garbage Out: Arguing about Undefined Behavior..."

all right so we're going to talk about undefined behavior my name is Chandler Carruth I work at Google I were calling C++ for Google I work on clang and LVM the compilers and one things I've done recently is I've you know started to try and talk with people about undefined behavior and so how many folks here are a little bit afraid of undefined behavior in their source code everybody how many folks here think that this font is too small when it comes to talking about undefined behavior and how scared they are that is that getting closer alright still too small I mean there's a lot of there are a lot of issues here right people are actually really kind of afraid of this and and I think it's something that you know we as a community need to try and deal with better so that's what this talk is is about this talk is not going to try and justify all forms of undefined behavior it's not going to try and you know remove all undefined behavior the primary goal of this talk is to help us actually think about undefined behavior in a more productive way now the number one thing I dislike about an undefined behavior is this obsession with nasal demons ok anyone recognize this by the way from the infernal dictionary this is a demon anyways so I really don't like the idea of nasal demons because it gives the wrong idea ok and I understand where it came from we wanted to convince people how serious the issue was so we spoke and hyperbole right and and the unfortunate thing is we've ended up in an argument about nasal demons with our users and if you remember the keynote right when we're arguing we're losing and so the first thing that we need to do is we need to kind of dispense with all of this and actually have a discussion in practical terms and have an explanation instead of an argument right and actually you know learn something about how this should work rather than just fighting and and you can see this I think best on Twitter actually so so on Twitter you know I've got all these game programmers complaining that you know we hear there's undefined behavior in Lib C somewhere right and then and then this escalates rapidly into you know let's let's remove files with the hard drive right with the idea that this is somehow legal and an interesting example of undefined behavior this isn't okay the compiler is not going to magically cause your program to suddenly make system calls that it never made before right this is it's actually a very very problematic kind of straw man that is put up and and of course it's now kind of derailed the entire discussion how can you argue with you know so you know not removing files from your hard drive okay its framing again a reference to the keynote so this continues to happen all over twitter james whitman is really upset he even kind of sent me a lot of tweets when i said i was going to give this talk the idea is that like so Marshall Clow has a comment about a male cat getting pregnant I don't know what that's about again your program can't do this no amount of undefined behavior is going to cause that to change right any more than your program can scribe a summoning circle and like raise a nasal demon that actually can't happen we do not in fact need an anti nasal demon League um then there's this email and this is actually the email that really got me involved in this because this one is actually very serious this is from Dan Bernstein all right and here he says that you know as a boring platform and he's talking about the boring crypto platform that Dan Bernstein and several other cryptographers are driving right now you know we need a C compiler that actually doesn't have undefined behavior right and he's really serious about this he's much more serious and I think anyone else who's arguing in the spaces because when he says doesn't have undefined behavior he means it he means all undefined behavior he needs all implementation defined behavior he means all portability differences between all platforms in the world I actually got to sit down with Dan and argue with him about it and and really he wants a virtual machine which behaves precisely the way an old 32-bit x86 Linux machine behaves today and he wants that behavior forever so they can run secure code on it now that might actually be an interesting thing to build right and in fact they're a bunch of programming languages that aim to provide this kind of portability is kind of abstraction from the hardware but I don't think that C++ right we're actually in the business of exposing the hardware not abstracting the hardware completely away we give you abstractions but not that level of abstractions I think this really starts to underlying the the underline the difference of perspectives that are actually happening here and then you get to see some other fun things I like so for example Jonathan Blow is a game developer you may have heard of he's very famous game developer you built witness you built braid before that and he's actually making a different argument he's arguing that you don't need to work on undefined behavior sanitizers or other tools to help me with undefined behavior because it's your platform you literally define the behavior and in fact you you have to define some behavior for everything so why are you dealing with undefined behavior just define it for your platform the way you have to and give me access to it right and this is this is a very interesting perspective because we've now gotten so lost in this undefined behavior that we're talking about Hardware semantics and platform construction and we've lost all side of the programming language right we need to do something this discussion to bring it back up to the programming language so what are we even talking about with you be what what's what is you be in a really like a really well express way and unfortunately there's like a light right on my slide but hopefully guys can see this so so here is some you be we have an integer pointer we make it know and we dereference it and read an integer out of it this is undefined behavior it's not particularly scary it's not particularly interesting but it's really boring okay now what I really like about this is that you know we can check for this kind of error right this isn't hard to show that you've got a bug in your program in fact if you compile this code with claim or GCC you get warnings right they tell you I don't know what you're trying to do but it's not going to go well okay and they're even platforms which can check for this dynamically this is a particular example of behavior that there are platforms which can give you a defined behavior for example on Windows this this this code can be run with you know appropriate settings in your compiler and it will produce very well-defined behavior we'll throw an exception right it's not nothing it's not rocket science not the end of the world the interesting thing is that there are platforms which have no mechanism for detecting this at runtime there are even platforms where this is well defined behavior at runtime okay they're embedded platforms which have memory at address zero and they let you dereference it which is really concerning right so they may have no reasonable way to surface this very high level undefined behavior to you on top of their low level platform and that makes it really challenging for the language to try and define this behavior because we may not we may be you know excluding ourselves from certain platforms the moment we do that so the way I like to think about this is that this is actually a programming error the language told me when you're going to dereference a pointer it better not be no and then me the programmer went and dereference to null pointer that's my bug okay I should not have done that this is just like calling an API out of contract right it's an API right if you have this API and the contract says hey look your pointer must not be null and I call that function with a null pointer I deserve exactly what I get and I have no way of predicting what I will get we're even going to standardize hopefully something that makes this even more explicit right we can spell this out this API must not be called with a null pointer okay and once it spell it out in programmatic terms we can build tools and other infrastructure to help check for any code I write which is out of contract all right now this is a really important thing this means that my code is incorrect right programming errors result in incorrect programs and we can't define the behavior for all incorrect programs like this isn't in this isn't in the cards we could try but we will fail okay now I don't affect you just to believe me that's lame that's boring okay so let me try and convince you that we cannot define the behavior for all incorrect programs let's look at this program we have a node okay so so noted a directed graph it's very boring okay this is extraordinarily boring we have a note it has outgoing edges we have a routine this routine finds a sink in a directed graph but it will only work to find a second a directed acyclic graph and it says so since they're right there it must be a cyclic you cannot pass a graph with cycles to it all right it's really this is a fundamental thing you can write this code in Java you can write it in C++ you can write it in any programming language of your heart's desire I don't care how much behavior it defines if I pass a node to a directed graph with cycles my program is incorrect I have a programming error and you cannot necessarily define its behavior let's look at the implementation to see why this is so hard to define behavior maybe I I define this implementation by recursive call this is a valid and correct implementation of fine sync it will find a sync in the graph if the graph is a cyclic if the graph is not a cyclic this will do something very very strange okay depending on your platform depending on you know various other things this can do anything ranging from crashing your program due to running out of stack throwing an exception due to encountering a guard page on a platform that can transform guard page violations into exceptions okay or this could actually run forever you actually just never halt all right and if you want if you want to guarantee from the implementation that you know this is going to actually be produced some defined behave you're going to have a very hard time so I've produced a directed graph how many folks here know how to find a cycle in a directed graph hopefully a few people know how to find a cycle on director graph right we can we keep stack right keep a set of things right look we see if we encounter something we've already visited before haha it's a cycle we're done but that's a lot of memory that this program doesn't use currently okay that's a lot of operations this program doesn't make that might be completely unacceptable from a performance trade-off and what's worse I've chosen a very simple example I can put in a slide right and I've even got the of you got the iterative example which will definitively run forever all right this will just never hold right but what if this work just a directed graph and what if it weren't just finding a sink what if this were evaluating a regular expression could we detect can we determine this they detect all errors in a regular expression probably it gets harder but probably what if it's an extended regular expression that has a stack attached to it that's called a pushdown automata we're now very close to needing a Turing machine to figure out if it halts okay like you cannot actually do this you will run out of the ability to detect errors and the trade-offs you're making in performance are insane here okay so what I want to point out is that we're not going to detect all errors in programs like we can't and what we're actually talking about when we see you be coming out of this programming error that we failed to detect somehow is a symptom okay that's all UV is it's just a symptom okay it's like a headache it's not the thing that's wrong it's a symptom of the thing that's wrong right we need to talk to dr. house about what you do with symptoms I mean sure sometimes you treat the symptom and it's important to have medications that treat symptoms but you don't stop by treating the symptom you need to understand what the underlying issue is all right and what I want to repeat over and over and over again the underlying issue is not undefined behavior okay it's not undefined behavior there's a programming error of somewhere that we were unable to detect that's the underlying issue I'm not trying to say that it isn't an issue it is it's absolutely a critical problem in software that we have programming errors we can't detect but it's not undefined behavior that's the problem here that's just the symptom okay so the other kind of key realization is it comes from this idea of contracts so we have code it's using some C++ language feature out of contract now what is what do we what do we usually call things which can be used out of contract we say that they have a narrow contract the statement library has been doing this for years and years and for decades now herb I think I don't remember when our contract went into the standard library I haven't been on the committee that long it's been in there for so long we understand how to deal with wide contract and narrow contract ap is what we need to do is start thinking about language features using the exact same terminology the exact same methodology we have a choice you can make narrow contract feature which may cause problems or why'd contract feature which may have cost but this doesn't explain one other kind of important thing here why is everyone so angry all right all I've given us is Nelson terminology and we can talk about things differently but why are people still upset the reason they're upset is because these contract violations that are kind of in their program are latent they don't cause any problems for them right now and I think that is actually our fault okay the problem the fundamental thing that we the Standards Committee and we the implementers and and we kind of library vendors who have done that have worsened this is is leaving these things as latent problems rather than making them manifest right rather than making them actually patent problems visible to the developers because now right they look at this and they think like well look I wrote my code all right I tested the daylights out of my code I actually did my engineering job I made sure I made certain that it worked it worked so many times it worked on different platforms it worked everywhere and then five years later all of a sudden something changes some piece of infrastructure changes and suddenly my code stops working I used every tool you gave me to evaluate the correctness of my program and every single one of them agreed that my software was correct all right give me I had no indication what I had was a signal that the behavior of the software is predictable and I assumed that minute was correct all right that doesn't actually follow and that's that's why it's frustrating because they put in this effort they have this kind of belief but it isn't actually backed up by by a strong commitment from the tooling all right so what can we do about this so that's all kind of depressing and sad what can we actually do to change things here I mean the obvious thing that about 18 million people on Twitter are asking me to do every single time I go in there just fine all behavior let's define all of it so this is going to be really challenging remember that that that example with like the graph thing I don't know how to define that behavior necessarily without an unacceptable performance trade-off and if you give me you know a turing-complete language to interpret I'm going to very hard time defining all the behaviors that will be extraordinarily challenging so this is a tricky request it also has kind of an unseen cost because if we if we go and define all the behaviors here we're going to inherently pick some behavior that works well on some platform like maybe I go off and I go to the Standards Committee I write a really nice paper and I say we're gonna define all the behaviors and the definition I give them is what is really wonderful for me on my platform unfortunately that is going to pesum eyes the behavior for a large number of C++ users C++ is just a very diverse language right when when I say that like so we're going to define all the behaviors exactly the way they work on x86 64-bit processors some of my my wonderful colleagues who work on the ARM processors they look at me and they're they're not really happy about this ok they're really not happy about this okay so so what this really comes down to is can we make every language feature have a wide contract that's what we're actually saying we're saying define all the behaviors because we're not going to define the behavior of a Turing complete language being interpreted that's hard but we could try and make all these language features wide right and and this is this is this is the only response I'm going to get from a portability perspective when I try and do this and it really comes down to a fundamental aspect of C++ right C++ is supposed to make you pay for what you use and so if we define particular behavior on one platform that personalizes another platform and the users on that platform aren't even benefiting from it they're going to be very very unhappy and it's going to kind of undermine a core strength of C++ right and what this really means is that you know this is a language which should not try and define all behavior it can't because doing so will pesum eyes some large body of its users ok so what we really want to do is we want to look at individual features and we want to have a kind of careful evaluation should this feature have a wide contract this feature have a narrow contract right like what are the trade-offs that we should actually be using to make these assessments the other kind of interesting question I get from a lot of people is can we we just at least can constrain the undefined behavior that comes out right I don't want my files on my harddrive to be you know removed I don't want you know any kind of change to the the the you know nature of my cats um I don't even want a inner life change the nature of my cats so so can we at least kind of narrow the scope of what's going to go wrong here well the problem with that idea is that this isn't about undefined behavior right I mean we could try and do this right and to a certain extent we have as I said I can assure you your software is not going to change the state of your cats okay that's actually not in the cards that's a straw man but this isn't a valentine behavior this is about how we define the semantics contracts for the programming language all right and so trying to focus overly much on constraining undefined behavior I think misses the point what people kind of want to do is they want to have some of the behavior defined when we're out of contract it's very like wishy-washy thing and it always comes down to we have to pick what we're going to define and our different users like they want different things for example my users whenever whenever something's out of contract they usually want the program to stop immediately and to tell them that they've got a bug right that's because my users can tolerate their programs doing that I've got a bunch of other users right who are like you cannot stop my program if you stop my program playing falls out of the sky don't do that okay and so there they're in a very different situation they can't afford for me to make the same kinds of trade-offs this all comes back to the fundamental idea of C++ right we're going to make trade-offs if you're very very careful they don't pesum eyes users so maybe what we really can focus on is this when is it actually appropriate have an arrow contract for a language feature if we can't we can't make undefined behavior somehow constrain we can't have all wide contracts then we're going to need to think really carefully every time we add a language feature and we give it a narrow programming contract right why would we even give programming language a narrow programming contract well it's simpler right if you have a narrow contract you actually have a simpler semantic model it's easier to reason about it's easier for Hugh to reason about it's easier for static analysis tools to reason about it's even easier to implement right this is one of the classic reasons why the standard library has some narrow contract api's they're much easier to implement than a wide contract API if you have a wide contract you have to have a way without hurting performance in an unacceptable fashion to check every single possible erroneous input to that API and a language feature you have the same problem right you have to be able to check every possible misuse of that language feature and produce a defined error it's very very challenging and what's worse to me is that it also won't match expectations right this is the other challenge we have here is that if programmers expect a particular language feature to work a particular way but they can abuse it and as a consequence of that in this use of the language feature we cannot give them the expected behavior if we define a wide API a wide contract we have to give them some behavior but it's not going to be something that they expect right and we remove the ability to say no look this is a programming error you simply should not have done that that that's a really kind of big loss for our programmers so it was our question No okay so we need some principles these principles for how we want to do kind of narrow language contracts yes question there's question I not only can I give you an example I have a whole host of slides giving you those examples about about half of this talk is going to be staring at really complicated examples in thinking about how this applies to them okay so we need the principles though to actually to actually do that to do that analysis I mean some principles for making kind of narrow language constructs my first kind of dominant principle is it must be checkable does have to be deterministic checkable right there are things we cannot you know we cannot check in a reasonable amount of time it may not be checkable for all users or on all platforms but we need to have some mechanism for actually checking whether programming errors are in the software because that goes to the latent bugs that's what goes to the anger and resentment and the frustration of our users when we give them a checkable tool they can start to push back that they may still disagree with the trade-off between a narrow and a wide contract but they're going to have that disagreement upfront rather than it building into anger and resentment okay that's the very first requirement for me second thing we need to have is we need to provide significant value not just some value but significant value now this is always tricky okay because different users just like different users have different constraints different users have different value functions right for some users optimization is incredibly valuable for other users it's not the most important thing their code is already running fast enough but we need at least some body of users that are benefiting from it we can't just have narrow contracts because we want to okay we have to have a reason we have to have some group we're helping by doing this and it's not just about optimizations I want to emphasize bug finding and simplification are good motivations to narrow a contract on a language feature if we can find bugs in software we will be doing everyone a service the third constraint for me is that it needs to be easily explained we need to have some rational model for telling our users hey look here's the narrow contract on this API here's what you're going to go outside of that contract here's how to deal with that here's how to mentally model this language feature if if the mental model for the language feature ends up in direct contradiction to kind of the the contract we give the language feature our users are lost they have no hope okay they have no hope and finally we can't have these narrow contracts when the entire world of software has already decided that that is an acceptable code pattern we cannot just take widely violated principles of software and suddenly decide you know what we believe that there's a principled reason why all of that code is bundi right because that that isn't actually productive we actually need to keep software that exists working okay and I'm going to give examples that kind of touch on a lot of these different principles and show how they can apply and change things make sense questions before I go into examples I really do want to emphasize when we get into the examples please ask questions these examples are sadly there as simple as I would like because we I wanted to give you guys examples that actually come up all right so the very first example this one is at least fairly simple okay so I've got a bunch of volatile and other stuff in here this is so that if you go home and you like copy paste this into into a compiler and run it you will actually be able to see things happen otherwise you get like compiler error messages because we statically prove that you have undefined behavior and we like throughout your program from the beginning but this way you can actually kind of see what's going to happen when it executes so we have an unsigned integer an unsigned integer not a scientific okay and we have one of them value one and one of them at the value of 33 and we are going to shift that one 33 places now unsigned on my platform is 32 bits and so this shifts the value by more bits than we have available C++ says this is undefined behavior this is undefined paper even for an unsigned integer and a lot of people are surprised by this undefined behavior they don't understand like why why does people's ples need this to be undefined this is actually undefined for portability reasons we don't have a good way and hardware of implementing this operation in a portable predictable fashion across platforms PowerPC x86 and arm all implement shift left with a larger than bit with value differently okay which can be very surprising okay very very surprising and so we actually made this undefined because whether or not you intended this to be a programming error or intended this to do something useful we believe it will be a programming error now there are some platforms that have tried to define the behavior of this and for example the web assembly platform actually allows you to execute this code the actual actual underlying hardware hardware in the web is only kind of virtual machine says that shifts left shifts by more than the number of bits is fine and as a consequence shifting left by about an unknown value is twice as expensive as it would be on the hardware because they have to pedantically check every single shift left on essentially every architecture in order to get the same behavior across them all right and and this is really problematic yes the question the questions why don't you call it implementation to find it's a great question one problem of calling this implementation to find is because if the Cullen implementation defined then I can't tell my users that this code is a buck because my users might say like no I want it to work I'm just relying on a particular implementation by saying it's undefined behavior we actually free the compiler vendors right to actually say no the contract this end of this operation is narrower because that's what we can implement efficiently and portably across architectures and if you're outside of that it is actually an error and we can tell you about it it's not that we don't give you the expressive power to write the extra code necessary to get portable behavior right you can you can mask the right-hand side of this if you want but we don't want you to pay for something you're not using right and if we did it aa priori we'd have you'd have to pay for it does that make sense okay and I'm sorry I'm going to try but I understand okay so then we have a more complicated example this is actually like five examples don't don't panic there's actually just five different examples were going to step through this so the question that I have in this example is what is the how do I explain signed integer left shift to my users right because sign integer left shift has a narrow contract in C++ all right you're not allowed to shift things off the top of a signed integer it's just like integer overflow so I need some way of explaining this to my users so that they understand how it works the way I came up with in a way several other people would that work with me came up with was okay signed left shift is precisely analogous to multiplying by a power of two with one small caveat in there cases where you can't form that power of two in the bit with that you're actually doing the shift left and we can just make that work no problem okay that it's just shorthand for a sign multiplication so we have on the Left I shift left by 31 and on the right we do a multiply so one shifted left by 31 is two to the 31 right so this is the same this is multiplying by a power of two this is shifting and the ideas we want these to be the same thing okay now the C++ standards committee set has chosen to actually define the result on the left-hand side here which is really problematic because you like you actually have to use extra precision to get this and now here we're actually doing a truncation from a value that changes its its value before we actually assign this to a 32-bit integer on the right hand side we have a positive number and after we assign it we have a negative number okay so the right hand side here should be a bug in users code the left hand side should be as well if we're using this as our mental model but we've defined the left hand side we've even gone further we've also defined the right hand side for reasons I can't understand I still have to complain to Richard Smith about this but we don't even we don't even produce an error on the right hand side right now okay but that's a little concerning but let's keep going maybe maybe this gets better maybe this gets better so let the second example here we have we have two bits set in our initial value and we're going to shift it by 30 and we think okay okay so this should be equivalent to the same value multiplied by 2 to the 30 right that's the mathematical model I'm supposed to be using and ah I know okay that overflows a 32-bit integer right that's that's not going to be safe so the shift left is also not going to be safe and that's true today okay then the third example we have more bits alright and this one is interesting because we're actually shifting off the top of the value all right add this one again right we move it over to be multiplication by a power of two we note that that multiplication by a power of two causes signed overflow right it exceeds the amount of precision we have available and indeed the left hand side is also invalid so this this mental model works so far then we get to have some problems here so what happens if I have negative 1 and I shift it left by 31 this is just completely undefined behavior there's no there's nothing here at all and I find this really frustrating because well I have to extend I have to have a larger integer in order to represent 2 to the 31 in a positive number once I multiply that by negative 1 I get a value which can be stored without loss of precision in a 32-bit signed integer right it's int men it's nothing crazy here all right and so I have no idea why the left-hand side is not good and the right-hand side is good if absolutely no idea why this is the case it breaks all of my mental model and if you think that's bad the second one is much worse or the last is much worse because here I have negative 2 all right I don't even - you supposed to be 0 b11 suppose to be negative 3 all right and and if I shift this left by 30 bits I should be multiplying you know negative 2 by 2 to the 30 okay and negative 2 times 2 to the 30 is a perfectly valid integer right I can do all of that and 32-bit edgers it produces exactly the result I would expect there's no overflow there's nothing wrong here but the left-hand side is undefined behavior the right-hand side is defined behavior so I don't have a mental model to explain this to my users this is a really bad narrow contract in the language okay if we want this sign shift left to be an arrow contract my suggestion is we make it work the way it works on the right hand side precisely okay and that may mean removing something we actually defined in order to allow you to compute int min but it will also mean adding back something x4 which is a much more in my opinion mathematically saying way to commute compute int min and it is exactly one character longer so I think that's an acceptable trade-off but unfortunately the committee actually looked at this and we got it wrong all right and it wasn't our fault it wasn't that we didn't try very hard we tried very hard there were hours and hours and hours of debate on this in the committee lots of people sat and looked at this we all missed it a large part of why we miss it is we weren't thinking about what's the contract of integer shift left sign under shift but what does the API what how do we explain this to users we instead we're just looking at that top example and wondering whether we should make it well-defined so I think I think this explanation thing is really important questions about these examples all right so this is a one of one of my favorite examples this code comes out of a very old version of GCC that is part of spec you got everyone here familiar with spec and we're not familiar with spec cool suspect is this huge benchmarking package right a group of people collect open source programs and and kind of like refine them into very predictable forms and package them as a set of correctness tests for compilers and benchmarks for optimizing compilers that are common across the industry lots of people use them all right and several several academic researchers including a you know will Dietz John Reger their chrome admin and and one of the person whose name eludes me at the moment did a wonderful piece of research about integer overflow and the the body of software they looked at was actually all the the software packages in this spec benchmark library they weren't benchmarking they were looking at correctness issues an insight and JCC an old version of GCC was actually added to this benchmark library and and this is this is some code from GCC it's an allocation routine ok and so I tried to give you some hints about how to interpret this we have two structures here RTF and r2 Union the size of RT of struck RT Beck def is 16 the size of r2 Union is 8 ok now this is only using undefined integer arithmetic here there's no sorry unsigned integer arithmetic here there no signed integers there's no sign integer overflow here this this has well-defined behavior for every execution that occurs in spec but it isn't correct for every execution that occurs in spec so one of the spec tests actually calls this routine with the value of 0 for in and if you call this routine with the value of 0 for in you get a very surprising result it took them a lot of time to understand what was going on here so the key thing is the inside of this structure we have one element of an array of RT unions already inside the structure so this this allocation routine is trying to allocate the remaining elements in that array ok but if you only need if you don't need any elements if you the size you need is 0 and that actually happens in like the run of GCC inside of spec then you come down here and you take 0 minus 1 and that's negative one okay that's not that's fine but then you multiply by it unsigned integer because size of produces an unsigned integer and the result that is very surprising because the first thing we do is we convert negative one to an unsigned integer and that doesn't produce the unsigned integer that essentially anyone wants it to okay produces enormous unsigned integer we multiply it by the size of our to union now you might expect this to kind of fail catastrophically and immediately but it doesn't because you see unsigned integer multiplication is well defined on overflow a negative one produces a very large unsigned number and so when we multiply it by eight it immediately overflows okay it produces a very small number which is which is quite unfortunate and we add the other size this goes on to actually create a memory safety error in this program okay and this is despite the fact that this only has defined integer arithmetic and this goes to a point about now contracts okay sometimes why contract isn't what you the programmer wanted right if we had narrow contract here I could build you a tool okay I could build you a tool that would tell you hey you have a programming error here there is no way you intended n minus one times sizeof to overflow an unsigned integer wraparound and produce a small value like there is no way that was a correct thing you were expecting basic like infinitely precise integer arithmetic to hold and instead you've got modular arithmetic on a modulus you never saw coming okay like there's none even like we didn't even write an unsigned type in this function it just snuck in and bit us so narrow contracts actually have their purpose for but finding right they actually help us identify software bugs and and one thing that I've talked about elsewhere is Google actually looked very carefully at our source code and considered defining signed integer arithmetic and one thing we did was it when we're like just like before we define it we can we can turn it into a checked integer with Metacritic and look at all the places that check fires and we can see if defining the behavior some way would cause the code to be correct and there were places where it would cause the code to be correct but there were also hundreds and hundreds and hundreds of basic arithmetic errors just like this which if we give them defined behavior will stay bugs in the code forever and we will have no way of finding them all right I'd give you a very precise idea of how I powerful having these narrow contracts and checking them can be the Android the Android folks have now actually released a version of Android which turns on signed integer OpenFlow checking in a large number of the software packages on it so that your phone actually is checking this because they decide they looked at the performance numbers and they looked at the security risks and they're like oh no this is a clear this is a clear win we aren't we aren't you know having really huge problems with our integer arithmetic throughput on the processor we are having really huge security problems this is a no-brainer we're going to turn on check-in and because you can turn it on inside the tool chain because it's a narrow contract that we can systematically enforce across the entire program we it's very easy to kind of get rigid checking that checks every single overflow chance we don't have to teach programmers how to do correct overflow checking which is proven to be very very hard all right any questions about this example all right next example I also want to give an example of optimization there's a whole talk earlier this week about kind of optimizations that the fall out of kind of narrow contracts that the compiler can make very profitable transformations based on this one though is is my personal pet favorite because it's one that every single compiler and optimizer engineer I have talked to never saw coming they all knew about all the other optimization things there's like it's you know it's like well studied this one they did not see coming and this is also fairly real code so I mentioned spec earlier one of the applications in spec is actually fairly widely known how many folks here have heard of B's it anyway cool this is a function in BC it's actually a really like tiny snippet of a function in B's it but this actually comes out of Pisa okay and this is actually in a very hot part of visa it's part of a quadratic algorithm inside of B zip that it tries to do for a little while because it's very profitable for compression but very expensive okay and so this is a very important performance sensitive piece of code and visa I also have these dots here an important thing to realize is that this goes on this this one and then two we get up to twelve and then we start looping okay and then we have another twelve inside the loop and we loop for a long time so I'm just showing two examples here but this is actually a repeated pattern that happens throughout this entire function okay and what we're doing is we're extracting two characters right to two bytes of data we are comparing them and you know if they're not equal then we've determined that this is greater than and we return the greater than state this is just comparison function all of this is the implementation of a sort algorithm all right and you wouldn't expect a sort algorithm to really suffer from like optimization challenges to do with you know narrow contracts versus wide contracts but this code is written using unsigned integers and one of the reasons it was probably written using unsigned integers is to get that wide contract okay to get like no any value we use here it'll be well-defined we don't have negative numbers we don't want undefined behavior we're gonna use an unsigned integer and as a consequence we get this code on the right-hand side here this code the right-hand side I don't know if you guys read a lot of x86 assembly but the code on the right hand side is terrible like atrociously bad so I'm going to skip right ahead and show you what the code should look like so if we just take these two use out of this signature and make them sign 32-bit integers we get this instruction sequence this instruction sequence versus that one there's a small difference here okay now then what happened that's that's that was the immediate question people ask me when I when I showed them this they couldn't believe that this is actually that big of a problem so it's actually going on here is that we have these 32-bit integers and the 30 bit integers are used as array indices here okay when you use a thirty two integers array index right what you're actually doing is you're you're taking the array which is actually a pointer right hardware-level here this is a pointer alright and and you're taking this this index and you're going to scale that index by some value okay in this case for alright or so I start in this case one so it's easy some cases you have two or three or four and then you're going to add that scaled value to your pointer and then you're going to dereference that to loads of value that make sense as it's so common that x86 has a special hardware feature to do precisely this ok and in fact the other thing that's so common is that you do first one and then you add one to each index here and you do it again and to that adds one more and then we do it again and again twelve times and we do another twelve inside of a loop so common x86 has lots of features to help you with this you can actually add a constant offset you can you can you can scale things you do all of this very nicely but there's one problem here if for any reason this this plus one down here overflows okay in 32-bit it has to wrap has to wrap to a 32-bit number and if that happens right it's going to be a very different value but this is a 64-bit architecture that I compile the code on so the pointers are 64 bits but the indices are 32 bits this happens all the time in real code right because you know you don't need 64 bits of index you only need 32 bits it makes your data structure smaller it happens very very frequently in real code and so in order to implement that in x86 we actually have to use a different set of instructions this le al alright and what this L over here means is that we're restricting this to a 32-bit computation so I put it into EAX 32-bit register alright this gets us the 32-bit wrapping behavior that's all it's doing is getting us a 32-bit wrapping behavior because if we got the instruction we wanted down here if we just folded this into the address computation to load the value out of memory we wouldn't wrap it 32 bits we would wrap it 64 bits because it's a 64 bit pointer okay and we get a completely different answer now it happens that in this program the programmer didn't need to like you know two to the 31 modulus behavior that wasn't what they were interested in right they were actually interested in just like having an integer and so this actually slows down this actually causes the this inner loop of bees up to to have over twice as many instructions as it needs to just because we used an unsigned integer when we didn't need you know that extra precision we didn't need modular arithmetic but we were a little bit worried about an arrow contract right narrow contracts are simpler they do actually allow you to make very impactful transformations it's not just about loop analysis or other things all right you start any questions about this this crazy example yes can you repeat that one more time for me in this industry so the question is where where is i1 and i2 being increased this one right here adds one I understand the syntax of one outside of a parentheses is very strange syntax for addition but I assure you that that's adding one this is adding one and if I if I kept going past two you would see a two outside the parenthesis and a 3 and then a 4 and a 5 yeah we just essentially like delay actually modifying the right to stir because we can which also makes this much more out of order currently we can we can we can execute this in parallel another question at the back I think why is why a size T unsigned um that sir is is is a story of much sorrow so a long time ago we didn't have enough bits and we saw there was one bit we could steal and so we did it was important it was probably the right call at the top right today we have a lot more bits it's not clear that that was the right call now also at the time there was a lot of thought around you know there aren't negative sizes it doesn't make sense to actually have a type of negative sizes I can actually see a pretty compelling argument for having an unsigned integer type which has undefined behavior sorry you know which has an arrow contract there we go she's an arrow contract on overflow and underflow and a separate unsigned type which has a wide contract and provides modular arithmetic I think they're both reasonable things to want to have the value of having the unsigned type separate from the signs type both of them with that narrow you know mathematically derived of contract I think is much smaller today than it was a long time ago because today it's fairly easy to get enough bits well without having to use the sign bit yes yes if you size T that will also also avoid the problem on the gallon side using size T is that if this parameter isn't a function parameter but it's in fact in a data structure it uses more space and in this particular case I didn't show the caller in the particular case we get these indices out of a data structure and so they are actually small values in that data structure we could extend them to 64 bits ahead of time but that's really just moving the narrow contract assumption from from this code to the caller right it's not changing the trade-off there yes no this we cannot we cannot produce this assembly for this function it is incorrect is invalid absolutely invalid because this might actually wrap this 32 bit I won from from a very large number from from you nth max to 0 and and we have to use this this instruction to get that wrapping behavior if we use this instruction we will not get that wrapping behavior there are different they're semantically different no this rats 64-bits not at 32 bits that doesn't yes this is this is why it has to be assigned 32-bit integer so so this is still 32-bit integer but we take advantage of the fact we know it doesn't wrap to promote it to a 64-bit integer and use it as an as an operand to a 64-bit addressing mode this is a 64-bit address this is a 64-bit extension of that integer so we've changed the semantics here and the only reason these cement the semantics change is legal is because it was signed and it has a narrow contract which says it doesn't wrap otherwise we would give you the wrong answer having to step through this again okay yes another question is it one more time how would I recommend that we avoid problems like this if you have an integer which you want to which you want to treat arithmetic alee as opposed to in some modular space on to some power on some tower of to make it signed if you need more bits get more bits keep it signed it's very straightforward say it's a more time the the comment is that this will have the same behavior if we just use int and sidon 32t i kept it at 32 T to kind of show that it's still a 32-bit integer just now signed and that frees us in the implementation yes yes so so you have two choices here one of them is you can let someone like Titus do it who enjoys losing the other alternative is that I don't think this is an argument right I only say this when someone asked me the question how can I avoid this performance problem well here's how we can fix the performance problem we can do it in a safe systematic way make sense so that's the best advice I have and it's the same advice we got at the keynote is you know start with the discussion surface right till there's a problem surfaced provide you know constructive suggestion rather than an argument more questions about this I'll take one more so the question here is what if once you compile on a platform where a signed integer actually has the performance problem this is not platform specific the opportunity to make the code faster is platform specific but the the nature of the change is actually platform independent every platform signed will be the fastest alternative like you've got like a compiler author guarantee their compilers which are stronger or weaker but I don't know of any compiler which which fails to optimize a signed integer but successfully optimizes an unsigned integer it doesn't make sense because it's always valid just like like it's a strictly more constrained a strictly narrower contract something sense all right let's people I want to at least talk about one more example here because I don't actually think C++ is getting all of this right ok so here's an example that I think is really bad because C++ gets this one wrong in my opinion so here we have a signed integer and again I've put the 32 in here just to make it incredibly explicit that there's a very specific bit width taking place here and I would like to shift right now what does this mean how many folks think this is well-defined behavior you're all wrong okay you've got a couple hands good this is well-defined behavior how many people know what this does knowing that one person I don't know what this does this is implementation defined behavior to the comment earlier this is actually implementation defined behavior but I don't know which implementation to find behavior okay I have no idea which implementation to find behavior I get and that's very frustrating for me because what I'm trying to do is a very specific very well-documented operation I would like to do an arithmetic shift to the right which a lot which on a two's complement machine leaves the sign bit in place and copies it downward through my bits okay so this creates for example a 8-bit mask at the top of my 32-bit integer this is incredibly useful in fact essentially every cryptographic algorithm in the world has this code in it hundreds and hundreds and hundreds of time and every single one of them I don't know what the semantics of that algorithm is because there's implementation defined behavior we are allowed to implement this using sign-magnitude signed integers instead of two's complement and I have no idea what shifting right on a sign man go to denature does I literally have no idea and no one else does either no one on the committee knows how this is supposed to work either we just have this implementation defined behavior rather than actually giving it defined behavior this is a really big problem with our kind of persistent attachment to supporting more than two's complement arithmetic it is not really compatible we need to pick a single mathematical model for arithmetic here I think the obvious choice in this day and age is two's complement and with two's complement this has very clear semantics it should be well-defined and should give me an arithmetic shift every single processor every single processor that I use today has an arithmetic shift right it is unacceptable that there is no way in portable conforming C++ code to produce an arithmetic shift right instruction on a processor think about that for a minute there is a there's an instruction you cannot produce using portable conforming C++ code on every single architecture in the world today it's mind-blowing and and and and this is this is this is the problem right that people are having the su plus plus is narrow contracts right it's not actually that they're opposed to the idea of an arrow contract it's that we've got a bunch of narrow contracts there are really bad ideas okay this one is probably the worst example I have how many folks recognize this example so this is the subject of I don't know how many security vulnerability reports over the last five years here we have two null pointers and a zero size pass to mem copy I am not aware of a single mem copy implementation in the world on any platform on any hardware architecture and any Litzy anywhere that doesn't implement this correctly however the C standard says that the destination and the source shall not be null so it says in the standard can't argue with that it's been there for decades however people didn't really notice for a long time and I mean like really didn't notice for a long time okay about about ten years ago uh one platform started annotating their header file to say hey by the way you can't put a null pointer here and that was fine no one paid any attention to it because they didn't do anything it was just it was just some text and a header file that no one read and then you know a few years later this got released or white label release more widely and eventually some compilers started seeing this annotation and they're like hey you narrow the contract cool that's awesome I'll help you out right sometimes the compiler would insert trap if you send a null pointer through that thing other times it would delete all of the null checks further down the code all of them okay this was a really bad idea it's not a bad idea because having this narrow contract is fundamentally a bad idea this is a plausible narrow contract if there's some huge reason it's because this satisfies not one of our principles for a narrow contract okay it may be check a bull but it was unchecked forever okay so so that that means that everyone was like well my code seems correct number two this provides no value every implementation despite mem copy being one of the hottest pieces of code ever executed on any CPU no one ever needed to leverage this narrow contract to make anything faster I'm not aware of any bugs caught by this I'm not aware of any value whatsoever that this narrow contract provides uh it it also is very hard to explain because it doesn't actually make sense you get it at zero you're not going to read the memory I don't know why it matters what pointers you get okay and in fact it violates the last principle of every piece of code everywhere did this like why are we why are we changing it okay and so we do get it wrong sometimes but I think it becomes a lot more clear that we get it wrong when you explain things in terms of narrow contracts and wide contracts you take a very principled approach to how you justify your narrow contracts with that I am one and a half minutes over time but I'll happily stick around for some questions or or see you outside thank you very much

Channel: CppCon

Views: 63,158

Rating: 4.7447915 out of 5

Keywords: Chandler Carruth, CppCon 2016, Computer Science (Field), + C (Programming Language), Bash Films, conference video recording services, conference recording services, nationwide conference recording services, conference videography services, conference video recording, conference filming services, conference services, conference recording, conference live streaming, event videographers, capture presentation slides, record presentation slides, event video recording

Id: yG1OZ69H_-o

Length: 57min 39sec (3459 seconds)

Published: Thu Oct 06 2016

Reddit Comments

[u/bames53]

At around 48 minutes someone asks why they can't produce the fast code for the function with unsigned 32 bit integers and Chandler explains that that would be incorrect because the code would do different things if the indices actually were close enough to INT_MAX to cause wrapping.

However there's a way around that: the compiler could generate the fast code and then also generate code to check the arguments. Then have a second, slow code path that gets used with the check sees that wrapping would occur. In practice you'd always get the fast code path and all you'd have to pay is for the extra checking up front to ensure the fast path is okay, and the extra code size hopefully in some far away and very cold place in the executable.

[u/vlovich]

Here's the part I don't understand about UB that I didn't even know I didn't understand until Chandler mentioned it @ ~6:33 (still at the beginning of the video so maybe this is addressed later).

Standard C++ defines dereferencing a nullptr as UB. He mentions the reason for this is that on some platforms dereferencing 0x0 is not possible to detect at runtime on some platforms and on some platforms it's defined behaviour. He then makes the case that we don't want to exclude C++ from those platforms (which makes sense).

However, aren't we now in a contradictory state? Dereferencing nullptr is UB that the optimizer exploits to generate unexpected code (e.g. a typical optimization the compiler does is prune codepaths that dereference nullptr), which is now invalid code on the platform we wanted to support where dereferencing nullptr is well-defined. How is this contradiction resolved? Does the optimizer conspire with the platform-specific codegen layer to figure out if a given behaviour is UB on a given platform or not?

[u/CenterOfMultiverse]

So, is there a proposal for unsigned types with undefined overflow?

[u/bitshifternz]

Kind of disappointed by him about dragging up old out of context tweets to try to make some point. "If you're arguing, you're losing", well guess what...