From owner-sc22wg14@open-std.org Tue Jul 15 22:53:52 2008 Return-Path: X-Original-To: sc22wg14-domo1 Delivered-To: sc22wg14-domo1@open-std.org Received: by open-std.org (Postfix, from userid 521) id 2D0BBDA1FE; Tue, 15 Jul 2008 22:53:52 +0200 (CET DST) X-Original-To: sc22wg14@open-std.org Delivered-To: sc22wg14@open-std.org Received: from v-smtp-auth-relay-1.gradwell.net (v-smtp-auth-relay-1.gradwell.net [79.135.125.40]) by open-std.org (Postfix) with ESMTP id 82A953850F for ; Tue, 15 Jul 2008 22:53:39 +0200 (CET DST) Received: from digraph.polyomino.org.uk ([81.187.227.50] country=GB ident=postmaster$pop3#polyomino$org#uk) by v-smtp-auth-relay-1.gradwell.net with esmtpa (Gradwell gwh-smtpd 1.290) id 487d0e52.a40.19f for sc22wg14@open-std.org; Tue, 15 Jul 2008 21:53:39 +0100 (envelope-sender ) Received: from jsm28 (helo=localhost) by digraph.polyomino.org.uk with local-esmtp (Exim 4.68) (envelope-from ) id 1KIrWk-0004Ek-Mk for sc22wg14@open-std.org; Tue, 15 Jul 2008 20:53:38 +0000 Date: Tue, 15 Jul 2008 20:53:38 +0000 (UTC) From: "Joseph S. Myers" X-X-Sender: jsm28@digraph.polyomino.org.uk To: WG14 Subject: Re: (SC22WG14.11498) RE: critical undefined behavior In-Reply-To: <20080715182412.4E658D9E48@open-std.org> Message-ID: References: <20080715014235.B13D4D84DD@open-std.org> <20080715121121.BA3BCD86A5@open-std.org> <20080715182412.4E658D9E48@open-std.org> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-sc22wg14@open-std.org Precedence: bulk On Tue, 15 Jul 2008, Thomas Plum wrote: > >It would be helpful if this had a list of all the cases of undefined > >behavior (from Annex J.2) that it's proposed *not* be critical > undefined > >behavior - that is, that it's proposed new restrictions on > implementations > >be added for. > > Thank you, Joseph, for your characteristically detailed and precise > comments. I do agree to post the list you requested - see below. > > >Specific examples I think imposing new requirements for would be a bad > >idea (other than under appropriate profiles defining behavior in such > >cases) include "An exceptional condition occurs during the evaluation > of > >an expression (6.5)." > > Since Delft, we explicitly added "performing a trap is not an improper > control flow". Besides performing a trap, why would your code > generation require the freedom to cause out-of-bounds store or improper > control flow? (Apologies if that sounds argumentative; it's meant > sincerely as a request for information. As per the discussion in Delft, > if anyone has a plausible case for needing a critical u.b., then it > should be on our list.) First, there isn't a clear definition of what the bounds are; if you are trying to bound possible behavior, I think it needs to be clear enough to define a set of possible executions in the abstract machine. One possible set of bounds is "unspecified value" - the expression is evaluated and the value determined has no restrictions, but must be a well-defined value for each evaluation of an expression. For example, this is how Annex F defines out-of-range floating-to-integer conversion. The useful optimizations, however, go well beyond that. Consider the case of integer overflows. Optimizations on the basis of signed integer overflow help in at least two cases: * Optimizing expressions such as (x*10)/10 to x (for signed x) - such expressions typically arising from macros. * Loop optimizations - various optimizations are only value if the compiler can assume that the loop index variable does not wrap around. (I'm told that some implementations even do these by default with unsigned index variables, although that does not conform to the standard, so valuable are the optimizations found in practice.) Now an implementation may optimize (x*10)/10 to x - but in so doing it may be treating x*10 as having a value with properties no valid value of that type has. In the case of loop optimizations, it may do calculations of the number of loop iterations that are only valid if the loop does not wrap around - if those give completely wrong results for the other cases, the control flow may change from that of the abstract machine long before the particular iteration is reached that would have involved the integer overflow, or conversely the loop may carry on longer than it should and so access bytes outside the expected bounds. (For example, if the loop condition tests for exact equality the implementation may deduce that end-start is divisible by the loop stride, and implement division as a multiplication that is only valid for exact division.) "Unspecified value" would not permit such calculations that assume overflow does not occur to be done. Now there are other ways optimization based on integer overflow can lead to non-local effects if you have gone beyond "unspecified value". Suppose you have an if condition involving an expression whose evaluation involved undefined behavior, if (cond) { A; B; } else { C; D; }. Depending on the forms of conditional execution on the target system, the implementation may code it as something like: save = cond; if (save) { A; } else { C; } if (save) { B; } else { D; } For the second if, it may not necessarily reuse the saved value; it might recompute some or all of the expression if that turns out to be more efficient in that particular case ("rematerialization"). And the rematerialization may not involve the same optimizations as done for the first copy of the condition, depending on what values, registers etc. are conveniently available each time. So just as a value resulting from undefined behavior may not have properties consistent with any particular value of that type, so the resulting condition may sometimes act as true and sometimes as false. Clearly executing A; D; or C; B; in the above case would be a problematic control flow effect. Much the same applies with objects accessed through lvalues of types not permitted by 6.5. The implementation knows that accesses of type int do not conflict with those of type double. Sometimes it may reload a value, sometimes not, and this need not be consistent between successive evaluations of the same conditional. If the above falls within the bounds of what's acceptable without being called "critical" undefined behavior, I think those bounds are too wide to be useful. C is a hard language to optimize, so for certain high-performance uses the implementations want all the help they can get from undefined behavior. It's also a hard language to write secure code in, so those uses could do with well-defined (and not so well optimizable) profiles and tools for detecting exceptional conditions. In many cases for security unsigned integer overflow, fully defined by the standard, is just as much a risk as signed overflow (e.g. if a multiplication of two size_t types overflows and so you allocate too little memory). In this area as in others I think we need to avoid invention. Thus before bounding a particular sort of undefined behavior we should ask how implementations handle that particular case - for every such instance in the standard and DRs. Some may give a full definition, some may use unspecified values, some may treat it as critically undefined, some may have an inbetween version. Before using an inbetween version I think we should understandard how that inbetween version has been defined in a particular case in practice, and how the optimizability differs from the other possibilities. > Oh, I see. IIUC you're talking about e.g. the optimization vul note > that CERT posted a couple months ago. I suspect WG14 needs to tackle > that in detail as part of the C1x process ... in any event, I agree that > those issues need to be part of this "critical u.b." discussion. No, the CERT case deals with pointer overflow - adding integers to pointers that take them outside the bounds of an object then expecting to be able to do meaningful comparisons on them. While integer overflow can be effectively profiled in various ways to give it defined results (at the expense of some optimizations), and while the aliasing case can also be profiled with a "bag of bytes" memory model (again at the expense of optimizations), defining anything about pointers once they go outside the object into which they originally pointed is much harder. > At various times in the C1x discussion at meetings, Dave Keaton and I > have suggested that C1x should provide some method to indicate > explicitly that modwrap, or saturation, is used in specific cases; but a > global "profile" is an alternative that should also be on the table. > Again, I agree that it's an issue that does relate to the "critical > u.b." discussion. Again, it also needs existing practice. What practice do we have for marking the arithmetic in particular cases? What practice for profiles? (By way of example, gcc -fwrapv is existing practice for an option for modulo arithmetic, though with the odd bug e.g. not handling INT_MIN / -1 correctly. INT_MIN % -1 is a related case that I believe is well-defined in the present standard to have value 0 without trapping, but lots of implementations get wrong.) > http://wiki.dinkumware.com/twiki/pub/WG14/Documents/tpub5.xls . 60206 - uninitialized values may not act consistently like any particular value, see above. (Can clearly be profiled to initialize local variables.) Related to DR 338. 60208 - trap representations may include e.g. values of bool that act like neither true nor false. 60209 - I have not worked with sign-magnitude or one's complement implementations so cannot comment on what optimizations are useful with them. 60301 - OK. 60302 - OK (with infinities this doesn't really happen anyway now). 60308 - OK, but conversions back from integer to pointer if bits have been lost, or converting back to a pointer not within the original object, should be critical undefined (cf. DR 260 on provenance of values). 60407 - a string literal may share space with a constant pool used for other purposes (and this sharing may be implemented in the linker). If the system on which the program runs lacks memory protection, modification of the string literal may succeed and modify constants used for other purposes, with the same issues above that they may or may not be reloaded at each use. So I think this needs to be critical, but implementations supporting memory protection can guarantee a trap instead. 60501 - the effect may be that the object is seen as having no particular consistent value with consequences as above. Can certainly profile to have a fully-defined order of evaluation where this is not a problem. 60502, 60503 - discussed at length above. 60504 - as with other aliasing issues, though I suspect this case is rather less significant for optimization in practice. 60512 - probably OK. 60513 - probably OK, in that I expect implementations simply not to support objects that large. 60514 - may cause problems with some optimizations that expect to treat a subarray as a unit. 60516 - probably OK. 60517 - probably OK, though undefined if you use the pointer to access anything else. 60518 - OK (was implementation-defined rather than undefined in C90, see DR 081). 60519 - see above on expressions not acting as if they have any consistent value, though this might be less important than some other such cases for optimization in practice. As with other arithmetic cases could readily be profiled, though I don't know about existing practice for such a profile. 60520 - OK, the result is probably even consistent in practice, if totally unspecified by the standard. 60705 - See modifying constants above, but not readily possible to guarantee traps in the case of automatic storage duration. 60709, 60710 - as with other aliasing issues. If code wants to bound the effects of aliasing problems, it should not be using restrict; any relevant profile might define restrict to have no effect. 60714 - will lead to attempts to allocate negative stack space, out of bounds accesses etc. - can certainly be profiled to insert runtime checks and traps, but the cost could be problematic in some cases. 60717 - OK. 60902 - as above uninitialized values may not act like any consistent value; could be profiled to return 0 (or the value of an object of the return type statically initialized) in such cases. 70001 - as with aliasing issues above (remember the functions can be inlined). Can be profiled, but see e.g. memcpy_s in TR 24731 for functions people can use if they want that option. 70108 - if pointers are bad, you get critical behavior, I see no possibility of anything else. 70801-71926 - probably OK. 72004 - as above on uninitialized values (implementations may optimize out calls to malloc and free in some cases), can be profiled. 72005 - likewise. 72007 - as with modifying constants above. 71905, 71924, 71928 - probably OK. 71929 - an fpos_t includes an mbstate_t which may include pointers; I think this is critical. 72001 - this is more or less by definition an out of bounds access. 72003 - stray pointers means critical undefined, detecting them would involve substantial performance cost. The cases marked "ct" may be OK, except that since the standard doesn't define what such programs mean it's up to the implementation to do so, and it may say they are undefined on some or all executions. If you want to constrain them more you need to make clear what such programs mean if accepted. Several "ct" cases would involve heavy cooperation between the compiler and library to diagnose. 60210 - Hard to detect if in different translation units; I think critical undefined at least in that case; all sorts of effects may occur if one translation unit was translated assuming one type for an object and another with another type (one possibly in readonly memory and the other not, so accessed differently, etc.). 60307 - being incorrectly aligned is a property of the execution so can't be a constraint violation. May cause optimization problems in that implementations can use casts to get alignment information at present. 60509 - property of an execution; may be subject to change anyway in some of the sequence point proposals. See modifying constants above anyway for possible effects in some cases. 60713 - property of an execution; if the size specifiers are unequal, either may be used without consistency, leading to out of bounds accesses. 70601 - property of an execution. 60706 - depends on the particular use of volatile, but I think critical undefined for some. 71101, 71102 - critical, as with modifying constants. 71302 - see uninitialized values. 71406 - bad pointers mean critical undefined. 71501-71507 - may all involve stray pointers, depending on the ABI. 71913 - insufficient format arguments means stray pointer accesses in general, and see uninitialized values. > Discussion is sought regarding the 39 cases listed as "?", where I'm > still uncertain about the need to allow critical undefined behavior. I've commented more on the cases marked "loc" than on the "?" cases. In general, if you can't either (a) say exactly what the behavior is, or (b) say exactly what the set is of valid behaviors, that suggests critical undefined. If you can do (a) or (b) then you can consider whether to do so unconditionally, or only under a particular profile. The above comments suggest a lot of cases might profitably be described more specifically as "arithmetic", "alias", "uninitialized" or "order of evaluation" (there are a few others, e.g. checking for negative VLA sizes). In each case you could allow more than one option; implementations could treat them as critical undefined for the reasons discussed above, or they could define the results of all arithmetic operations; define objects to be bags of bytes accessible by any properly aligned pointer to within them; initialize automatic objects and function returns from falling off the end of a function; follow a strictly defined evaluation order without sequence point issues. -- Joseph S. Myers jsm@polyomino.org.uk