Is there really no standard-conforming function pointer equivalent of void*

[Jakob Bohm]

Inspired by the mega-thread about all and sundry that began with a
critique of declare-before-use, here is a question which seems open:

What (if anything) is the type for an arbitrary (but not directly
invokable) function pointer which can safely be cast to and from a
known correct function pointer type (in other words which type is to
function pointers what "void*" is to data pointers).

Some preliminary observations:

1. It is pretty clear that standard C allows implementations where
function pointers are fundamentally different from data pointers (e.g.
different number of bits, different encoding, different address space
etc.), so plain void* is out.

2. Choosing any arbitrary function pointer type such as void (*)(void)
fails because it can be invoked accidentally and cannot be assigned
from any other concrete function pointer type.

3. Choosing the old-style function pointer type void (*)() might still
be bad because it is more like void (*)(...).

So I kind of wonder what would be the "proper" standards-conforming
type for this.

Note: I am perfectly capable of using the imperfect fallback choices
done by a number of OS APIs for this, but they all seem a bit kludgy
compared to the elegance that "void*" brings to data pointers, a bit
like the historic use of "char*" before "void*" was added to C89.


Enjoy

Jakob
--
Jakob Bohm, CIO, Partner, WiseMo A/S. https://www.wisemo.com
Transformervej 29, 2860 Søborg, Denmark. Direct +45 31 13 16 10
This public discussion message is non-binding and may contain errors.
WiseMo - Remote Service Management for PCs, Phones and Embedded

[Ben Bacarisse]

Jakob Bohm <jb-u...@wisemo.com> writes:

> Inspired by the mega-thread about all and sundry that began with a
> critique of declare-before-use, here is a question which seems open:
>
> What (if anything) is the type for an arbitrary (but not directly
> invokable) function pointer which can safely be cast to and from a
> known correct function pointer type (in other words which type is to
> function pointers what "void*" is to data pointers).
>
> Some preliminary observations:
>
> 1. It is pretty clear that standard C allows implementations where
> function pointers are fundamentally different from data pointers (e.g.
> different number of bits, different encoding, different address space
> etc.), so plain void* is out.
>
> 2. Choosing any arbitrary function pointer type such as void (*)(void)
> fails because it can be invoked accidentally and cannot be assigned
> from any other concrete function pointer type.
>
> 3. Choosing the old-style function pointer type void (*)() might still
> be bad because it is more like void (*)(...).
>
> So I kind of wonder what would be the "proper" standards-conforming
> type for this.
>
> Note: I am perfectly capable of using the imperfect fallback choices
> done by a number of OS APIs for this, but they all seem a bit kludgy
> compared to the elegance that "void*" brings to data pointers, a bit
> like the historic use of "char*" before "void*" was added to C89.

I use void (*)(void) just because it looks like the void * for the
function world, but there's no function pointer type that permits an
implicit conversion like void *. As you say, it's more like char * then
void *.

You can get half of your point 2 by making the type invalid. That way
you catch accidental use before conversion, but it's not much of an
advance on using any old type.

typedef struct d_u_m_m_y (*fptr)(struct d_u_m_m_y);

(By defining the struct type in the parameter list you make it
impossible to ever define it, and by making it also the return type you
eliminate a warning from gcc.)

--
Ben.

[James Kuyper]

On 12/04/2015 02:13 AM, Jakob Bohm wrote:
> Inspired by the mega-thread about all and sundry that began with a
> critique of declare-before-use, here is a question which seems open:
>
> What (if anything) is the type for an arbitrary (but not directly
> invokable) function pointer which can safely be cast to and from a
> known correct function pointer type (in other words which type is to
> function pointers what "void*" is to data pointers).
>
> Some preliminary observations:
>
> 1. It is pretty clear that standard C allows implementations where
> function pointers are fundamentally different from data pointers (e.g.
> different number of bits, different encoding, different address space
> etc.), so plain void* is out.
>
> 2. Choosing any arbitrary function pointer type such as void (*)(void)
> fails because it can be invoked accidentally and cannot be assigned
> from any other concrete function pointer type.
>
> 3. Choosing the old-style function pointer type void (*)() might still
> be bad because it is more like void (*)(...).
>
> So I kind of wonder what would be the "proper" standards-conforming
> type for this.
>
> Note: I am perfectly capable of using the imperfect fallback choices
> done by a number of OS APIs for this, but they all seem a bit kludgy
> compared to the elegance that "void*" brings to data pointers, a bit
> like the historic use of "char*" before "void*" was added to C89.

void * has several important properties:

1. Any pointer to an object type can be converted to void* and back
again; the result must compare equal to the original pointer
(6.3.2.3p1), which means it can be used anywhere that the original
pointer could be used.

ALL function pointers share this property - any function pointer type
may be converted to any other function pointer type and back again. The
result must compare equal to the original. (6.3.2.3p8)

2. Conversions to and from void* can occur implicitly, with no cast
required. This occurs in simple assignment (6.5.16.1p2), and in two
other cases where the standard uses the phrase "as if by assignment":
arguments passed to a function that has a prototype in scope
(6.5.2.2p7), and the return statement (6.8.6.4p3)

NO function pointer type shares this property, because if the two
function pointer types differ, the constraints on simple assignment
(6.5.16.1p1) are violated. The fourth item in that constraint is an
exception for void*; there's no corresponding function pointer exception.

3. Using the value of *p has undefined behavior if p has the type void*
(6.3.2.2). Note that &*p is defined as being the equivalent of p, so it
is not considered to have used the value of *p.
I expected this to be a constraint violation, since it's trivially
diagnosable at compile time - but I can't find the constraint. I've made
a lot of mistakes lately due to lack of sleep - I hope this is one of
them, because it seems to me that it should be a constraint violation.

There is no function pointer type that shares this property with void*,
but if there were, it would provide no protection against accidentally
using that function pointer to call the function. That's because no
diagnostic is required, and if the function's definition is not
compatible with the function pointer type, the behavior was already
undefined.

Conclusion: there's no function pointer type that shares all of void*'s
useful properties. The best you can do is get property #1 above, which
is shared by ALL function pointer types. Therefore, use whichever one
you want - I usually use void (*)(void) for this purpose.
--
James Kuyper

[Jakob Bohm]

OK, I take it from both responses that such a type is missing from the
current standard (and thus most implementations) and we all just have
to live with the extra casts to an from the chosen "dummy function
pointer typedef" and hope we don't get bitten by various forms of
"strict aliasing" optimizations.

Some common uses of such a void function pointer:

- As the return value of run-time DLL function lookup by name
(e.g. pPluginAction2 = dlfunc(hPlugin, "Action2"); ).

- As element type in an array of API functions declared as a simply
(extensible) array type rather than a very specific structure of
specific pointer types.

- As a less specific (underspecified) argument type to functions such
as qsort (with the actual callback taking the specific element pointer
type, not void* as its arguments).

[Kaz Kylheku]

On 2015-12-04, Jakob Bohm <jb-u...@wisemo.com> wrote:
> Inspired by the mega-thread about all and sundry that began with a
> critique of declare-before-use, here is a question which seems open:
>
> What (if anything) is the type for an arbitrary (but not directly
> invokable) function pointer which can safely be cast to and from a
> known correct function pointer type (in other words which type is to
> function pointers what "void*" is to data pointers).

void (*)(int, int, int, int, ... repeated 128 times */)

This is callable, but only in theory, since nobody makes a typo which
calls a function with 128 arguments, in a system in which the maximum
number of arguments seen in any library is say, twelve.
If the function pointer is dereferenced other than with exactly 128
arguments, a diagnostic is required.

Another idea is to declare a type in the parameter list:

void (*)(struct u_n_i_q_u_e)

This struct is not seen anywhere else, and so the function cannot
be passed, because nothing outside of that argument list can instantiate
a struct type compatible with the parameter. This, though, elicits a
warning from your local GCC and possibly other compilers.

[Hans-Bernhard Bröker]

Am 04.12.2015 um 08:13 schrieb Jakob Bohm:

> What (if anything) is the type for an arbitrary (but not directly
> invokable) function pointer which can safely be cast to and from a
> known correct function pointer type (in other words which type is to
> function pointers what "void*" is to data pointers).

I agree with previous observations: there isn't one. I disagree with
the conclusion that this means such a thing is missing from the
standard; IMHO it's actually needed.

The concept of "just some data" is useful and necessary. There are
functions that have to deal with data of unknown, even unknowable,
structure, and they can do useful work with them, primarily by moving it
across external interfaces of the program.

I don't think the same would apply to the concept of "just some
function". In particular there's no remotely portable use for moving a
C function's contents (i.e. the machine code) by something like memcpy()
or fwrite().

Nor is there really any other useful thing you can ever do with a
function of unknown type, because can never actually call it without
causing undefined behaviour.

That makes idea of actually using something like an "arbitrary function
pointer" a non-starter. Any design that appears to need such a thing
has already failed several stages before that point. At the most, one
can handle a function pointer that is actually one out of a strictly
finite set of types, accompanied by an enumerated value that tells you
which of those types it is, so you can switch() to a case that applies a
cast to the right function pointer type, and calls the function. A
generic function pointer would not really help with that.

I am convinced that allowing the kind of silent, implicit cast to/from
the supposed "function void *" that we have for (void *) would be a
Spectacularly Bad Decision. Function pointer conversions are
_dangerous_; they should _never_ happen silently.

[Hans-Bernhard Bröker]

Am 04.12.2015 um 08:13 schrieb Jakob Bohm:

> What (if anything) is the type for an arbitrary (but not directly
> invokable) function pointer which can safely be cast to and from a
> known correct function pointer type (in other words which type is to
> function pointers what "void*" is to data pointers).

I agree with previous observations: there isn't one. I disagree with
the conclusion that this means such a thing is missing from the

standard; IMHO it's not actually needed.

[Kaz Kylheku]

On 2015-12-04, Hans-Bernhard Bröker <HBBr...@t-online.de> wrote:
> Am 04.12.2015 um 08:13 schrieb Jakob Bohm:
>
>> What (if anything) is the type for an arbitrary (but not directly
>> invokable) function pointer which can safely be cast to and from a
>> known correct function pointer type (in other words which type is to
>> function pointers what "void*" is to data pointers).
>
> I agree with previous observations: there isn't one. I disagree with
> the conclusion that this means such a thing is missing from the
> standard; IMHO it's actually needed.
>
> The concept of "just some data" is useful and necessary. There are
> functions that have to deal with data of unknown, even unknowable,
> structure, and they can do useful work with them, primarily by moving it
> across external interfaces of the program.
>
> I don't think the same would apply to the concept of "just some
> function". In particular there's no remotely portable use for moving a
> C function's contents (i.e. the machine code) by something like memcpy()
> or fwrite().
>
> Nor is there really any other useful thing you can ever do with a
> function of unknown type, because can never actually call it without
> causing undefined behaviour.

An unknown function type has to be converted to some known function
types to be called. In C, this is static. This means that the
possibilities are finite (since programs are finite) and thus
enumerable.

Which means that you can store the function in an union discriminated
by an enumeration:

struct fun {
func_type type;
union {
func_type_0 f0;
func_type_1 f1;
func_type_2 f2;
/* ... */
} f;
}

When you construct this object, at that time you know what function
you're dealing with and thus store an appropriate value into
type, and store the function pointer into the appropriate member
of the f union.

When calling it, you switch on type, dispatching to a function
call which calls the correct union member with the correct
number and types arguments.

The union answers the question "how do we store any one of a number
of different kinds of pointers in the same space", and also addresses
the requirement "... and safely use it".

For anything more dynamic, you need something like Brun Haible's
avcall library:

http://www.gnu.org/software/libffcall/

[Jakob Bohm]

On 04/12/2015 21:42, Hans-Bernhard Bröker wrote:
> Am 04.12.2015 um 08:13 schrieb Jakob Bohm:
>
>> What (if anything) is the type for an arbitrary (but not directly
>> invokable) function pointer which can safely be cast to and from a
>> known correct function pointer type (in other words which type is to
>> function pointers what "void*" is to data pointers).
>
> I agree with previous observations: there isn't one. I disagree with
> the conclusion that this means such a thing is missing from the
> standard; IMHO it's not actually needed.
>
> The concept of "just some data" is useful and necessary. There are
> functions that have to deal with data of unknown, even unknowable,
> structure, and they can do useful work with them, primarily by moving it
> across external interfaces of the program.
>
> I don't think the same would apply to the concept of "just some
> function". In particular there's no remotely portable use for moving a
> C function's contents (i.e. the machine code) by something like memcpy()
> or fwrite().

Indeed, functions are not data (especially on Harvard architectures),
but the function pointers themselves are data that can usefully be
transported between different code layers in a well-structured system
design.

>
> Nor is there really any other useful thing you can ever do with a
> function of unknown type, because can never actually call it without
> causing undefined behaviour.

As I explained earlier, the most common use would be to pass function
pointer objects through library interfaces which are naturally
indifferent to the (exact) nature of the function pointer passing
through them.

The semi-portable (POSIX etc.) APIs for accessing functions in shared
libraries and plugins is a prime example. These don't care what
function pointer is being published by a shared library or plugin, just
the name. The code that calls such an API (or a wrapper around it)
generally has this knowledge from shared library documentation, but the
function lookup API has no way to enumerate the infinity of function
types that future libraries may expose.

The "data" void pointer type uses that compares the closest is probably
malloc/free. Those typically don't do anything useful to the data
either, they just create/destroy unique pointer values (conceptually
speaking).

>
> That makes idea of actually using something like an "arbitrary function
> pointer" a non-starter. Any design that appears to need such a thing
> has already failed several stages before that point. At the most, one
> can handle a function pointer that is actually one out of a strictly
> finite set of types, accompanied by an enumerated value that tells you
> which of those types it is, so you can switch() to a case that applies a
> cast to the right function pointer type, and calls the function. A
> generic function pointer would not really help with that.
>
> I am convinced that allowing the kind of silent, implicit cast to/from
> the supposed "function void *" that we have for (void *) would be a
> Spectacularly Bad Decision. Function pointer conversions are
> _dangerous_; they should _never_ happen silently.

There would still be 3 safeties:

1. Unlike arbitrary "dummy" function pointer types, the "void" function
pointer type cannot be invoked by accident, which is a major type
safety.

2. Implicit conversions TO "void" function pointers don't create an
instant danger because of 1, and explicitly marks the type as lacking
the removed detailed type information.

3. Implicit conversions FROM "void" function pointers only happen when
a very specific function pointer type is specified, typically as the
type of a target variable or function argument. This significantly
limits the danger.

[Jakob Bohm]

I haven't studied the ffcall library implementation closely, but I
strongly suspect it makes pretty heavy use of "void like" function
pointers, at least internally.

And once again, look at the basic dynamic library APIs (dlfcn.h on
*N*X, mach-o/dyld.h on OS/X, GetProcAddress() on Windows,
DosGetProcAddr() on OS/2 etc.) They all need this type and use various
vendor-specific arbitrary type as a substitute.

[Wojtek Lerch]

On 07-Dec-15 7:45 AM, Jakob Bohm wrote:
> And once again, look at the basic dynamic library APIs (dlfcn.h on
> *N*X, mach-o/dyld.h on OS/X, GetProcAddress() on Windows,
> DosGetProcAddr() on OS/2 etc.) They all need this type and use various
> vendor-specific arbitrary type as a substitute.

The POSIX dlsym() returns void*, and POSIX requires implementations to
safely convert it to the correct pointer type, even if the correct type
is a pointer to function.

"Upon successful completion, if /name/ names a function identifier,
dlsym() shall return the address of the function converted from type
pointer to function to type pointer to void; otherwise, dlsym() shall
return the address of the data object associated with the data object
identifier named by /name/ converted from a pointer to the type of the
data object to a pointer to void."

...

"Note that conversion from a void * pointer to a function pointer as in:

fptr = (int (*)(int))dlsym(handle, "my_function");

is not defined by the ISO C standard. This standard requires this
conversion to work correctly on conforming implementations."


http://pubs.opengroup.org/onlinepubs/9699919799/functions/dlsym.html

[supe...@casperkitty.com]

Most of the situations I can see which would require code to work with
function pointers without caring what kind of function they identified
would need to work an extra level of indirection down, and to make that
work one would also need a generalized concept of a "pointer to unknown
thing of some general kind". All pointers to structures have the same
representation, all pointers to unions have the same representation, and
all pointers to functions have the same representation, so it would be
very useful if C had types for "pointer to some kind of struct", and
likewise for unions and functions, and [most importantly], a pointer to
such a pointer could be used to alias any such pointer with the same
level of indirection, so as to make it possible to e.g. have a version of
qsort() which is optimized for e.g. sorting pointers to structures.
While one wouldn't terribly often need the ability to operate in type-
agnostic fashion on an array of pointers to functions, such an ability
could be incorporated at the same time as the means of operating in type-
agnostic fashion on an array of pointers to unions or an array of pointers
to structures.

[Jakob Bohm]

Another use for pointer to unknown thing of some general kind would be
for "out" parameters, aka function arguments that are pointers to
variables to fill with the result (e.g. because the function needs to
return 2 or more typed values).

For example:

rc = malloc_r(void**ptrptr, size_t siz);
// Like *ptrptr = malloc(); return errno;
freepointer(void**ptrptr);
// Combines free(*ptrptr) and *ptrptr= NULL;

libhdl_t loadandgetfunc(anyfunc**ptrptrFunc, const char*libnam, const
char**fnnam);

Or how about:

void qsort_structs(anystruc*pData, size_t cnt, size_t elemSiz,
anyfunc*cmpfunc);
// Alias for qsort() with more friendly argument types.
// Note that this will not object to getting passed a cmpfunc
// completely dissimilar to what is needed, but will probably
// crash and burn if that happens.
// C++ could use its complex template notation to prevent this
// ambiguity and mixed C/C++ runtime library headers could do
// so during C++ compiles.

e.g.

typedef struct {
// ...
} foo_t;

int foocmp(const foo_t*p1, const foo_t*p2)
{
// No casts of p1 and p2 needed
// ...
}

void bar(foo_t *arr, size_t cnt)
{
// ...
// Look Ma, no casts, ...
qsort_structs(arr, cnt, sizeof(*arr), foocmp);
// ...

[supe...@casperkitty.com]

On Tuesday, December 8, 2015 at 3:44:52 PM UTC-6, Jakob Bohm wrote:
> Another use for pointer to unknown thing of some general kind would be
> for "out" parameters, aka function arguments that are pointers to
> variables to fill with the result (e.g. because the function needs to
> return 2 or more typed values).
>
> For example:
>
> rc = malloc_r(void**ptrptr, size_t siz);
> // Like *ptrptr = malloc(); return errno;
> freepointer(void**ptrptr);
> // Combines free(*ptrptr) and *ptrptr= NULL;

Better yet, realloc_struct_ptr(__ANY_STRUCT **ptr, size_t new_size);

Actually, since the vast majority of C implementations use the same
representation for many kinds of pointers, it would be helpful to have
pre-defined macros that would identify what sorts of pointers use the
same representations as a char*, and be able to use a function like the
above with any kind of pointer to allocated storage. Much cleaner than
having to store the return from realloc into a temporary, check that it's
not null, and only update the pointer if that's the case, *especially*
if it could then provide a three-state return value:

-- Block was moved; existing pointers to it are no longer valid.
-- Block resized but not moved; *existing pointers remain valid*.
-- Block couldn't be resized.

There are some situations where a realloc isn't particularly expected to
move a block (e.g. the block was over-allocated and then shrunk), and where
code would be able to regenerate pointers into the allocated storage if it
needed to, but would be faster if it didn't need to do that. On many
implementations, it would be possible to do:

temp = realloc(old_ptr, new_size);
if (!temp) GAAAAH();
if (temp != old_ptr)
{
old_ptr = temp;
recalculate_ptrs();
}

but Standard C would require that the program waste time calling
recalculate_ptrs() even when the block doesn't move.

[Jakob Bohm]

On 08/12/2015 23:13, supe...@casperkitty.com wrote:
> On Tuesday, December 8, 2015 at 3:44:52 PM UTC-6, Jakob Bohm wrote:

> ...

> There are some situations where a realloc isn't particularly expected to
> move a block (e.g. the block was over-allocated and then shrunk), and where
> code would be able to regenerate pointers into the allocated storage if it
> needed to, but would be faster if it didn't need to do that. On many
> implementations, it would be possible to do:
>
> temp = realloc(old_ptr, new_size);
> if (!temp) GAAAAH();
> if (temp != old_ptr)
> {
> old_ptr = temp;
> recalculate_ptrs();
> }
>
> but Standard C would require that the program waste time calling
> recalculate_ptrs() even when the block doesn't move.
>

Really, what aspect of the standard would require that, after a test
has clearly proven equality?

Besides, the rules for shrinking and non-moving could do with either:

- Stronger limits on implementations (shrink never moves)
OR
- A standard function for "resize if possible, but do not move" .

Also a standard version of the common msize() function (it has a longer
name in GNU libc) would also be nice.

[supe...@casperkitty.com]

On Tuesday, December 8, 2015 at 4:50:58 PM UTC-6, Jakob Bohm wrote:
> Really, what aspect of the standard would require that, after a test
> has clearly proven equality?

Unless realloc returns null, doing rvalue conversion on the old pointer
will invoke Undefined Behavior. Using memcmp to compare the old pointer
and the new one would not invoke Undefined Behavior, but the Standard
allows for the possibility that pointers may compare bitwise equal without
being semantically equivalent (e.g. given

int hey(int x)
{
int foo[4][4];
int *p1 = foo[0]+4;
int *p2 = foo[1];
if (x > 10)
printf("Wow!");
if (x < 23)
*p2 = *p1;
return memcmp(p1,p2);
}

the two pointers would likely compare bitwise-equal, but a compiler would
be allowed to make the call to "printf" unconditional.

> Besides, the rules for shrinking and non-moving could do with either:
>
> - Stronger limits on implementations (shrink never moves)
> OR
> - A standard function for "resize if possible, but do not move" .

I'd go for the latter, as well as a function to which code could pass a
list of pointers to allocated blocks which the library could move around
if fragmentation was an issue (provided that it updated the pointers in
the list).

> Also a standard version of the common msize() function (it has a longer
> name in GNU libc) would also be nice.

On some platforms it would be hard to guarantee anything useful about the
semantics; a solution to that would be to have a return value that means
"who knows"?

[Kaz Kylheku]

On 2015-12-09, supe...@casperkitty.com <supe...@casperkitty.com> wrote:
> On Tuesday, December 8, 2015 at 4:50:58 PM UTC-6, Jakob Bohm wrote:
>> Really, what aspect of the standard would require that, after a test
>> has clearly proven equality?
>
> Unless realloc returns null, doing rvalue conversion on the old pointer
> will invoke Undefined Behavior. Using memcmp to compare the old pointer
> and the new one would not invoke Undefined Behavior, but the Standard
> allows for the possibility that pointers may compare bitwise equal without
> being semantically equivalent (e.g. given
>
> int hey(int x)
> {
> int foo[4][4];
> int *p1 = foo[0]+4;
> int *p2 = foo[1];
> if (x > 10)
> printf("Wow!");
> if (x < 23)
> *p2 = *p1;
> return memcmp(p1,p2);
> }
>
> the two pointers would likely compare bitwise-equal, but a compiler would
> be allowed to make the call to "printf" unconditional.

Although undefined behavior leaves a great deal of latitude, the object
of x is simply not involved in the issue of the pointer arithmetic.

There is no honest translation and execution model in which
that could be the actual behavior; that hey(4) is called, and Wow!
is printed anyway.

The behavior would have to be contrived in a dishonest way; that is to
say, the implementation detects the undefined behavior and contains any
ill-effects which that behavior might directly cause. But then, instead
of providing a useful, documented extension or else diagnosing the
problem, for either of which it has an excellent opportunity, it instead
deliberately perturbs the values of objects not involved in the
undefined behavior situation, and/or arbitrarily alters the program's
subsequent control flow.

There is simply no need to take seriously such a "bad faith"
implementation.

The standard doesn't need to prohibit "bad faith" implementations
because it is unnecessary to spell this out.

The reason it is not necessary is that there is an unwritten assumption
is that everyone in engineering works in good faith, and that precludes
using the absence of a requirement as an excuse to introduce harm.

Some developers are actual engineers that belong to societies which
have codes of ethics, such as this:

http://www.nspe.org/resources/ethics/code-ethics/engineers-creed

"As a Professional Engineer, I dedicate my professional knowledge and
skill to the advancement and betterment of human welfare.

I pledge:

* To give the utmost of performance;
* To participate in none but honest enterprise;
* To live and work according to the laws of man and the
highest standards of professional conduct;
* To place service before profit, the honor and standing
of the profession before personal advantage, and the
public welfare above all other considerations."

[Wojtek Lerch]

On 08/12/2015 10:15 PM, Kaz Kylheku wrote:
> On 2015-12-09, supe...@casperkitty.com <supe...@casperkitty.com> wrote:
>> On Tuesday, December 8, 2015 at 4:50:58 PM UTC-6, Jakob Bohm wrote:

...

>> int hey(int x)
>> {
>> int foo[4][4];
>> int *p1 = foo[0]+4;
>> int *p2 = foo[1];
>> if (x > 10)
>> printf("Wow!");
>> if (x < 23)
>> *p2 = *p1;
>> return memcmp(p1,p2);

I assume this was supposed to be "memcmp(&p1,&p2,sizeof p1)"?

>> }
>>
>> the two pointers would likely compare bitwise-equal, but a compiler would
>> be allowed to make the call to "printf" unconditional.
>
> Although undefined behavior leaves a great deal of latitude, the object
> of x is simply not involved in the issue of the pointer arithmetic.
>
> There is no honest translation and execution model in which
> that could be the actual behavior; that hey(4) is called, and Wow!
> is printed anyway.
>
> The behavior would have to be contrived in a dishonest way; that is to
> say, the implementation detects the undefined behavior and contains any
> ill-effects which that behavior might directly cause. But then, instead
> of providing a useful, documented extension or else diagnosing the
> problem, for either of which it has an excellent opportunity, it instead
> deliberately perturbs the values of objects not involved in the
> undefined behavior situation, and/or arbitrarily alters the program's
> subsequent control flow.

I don't think it would necessarily be dishonest, or "perturb" the values
of objects. The implementation simply needs to notice that the function
has undefined behaviour when x is less than 23, assume that the
programmer will make sure never to call it with an argument that leads
to undefined behaviour, and perform optimizations based on that
assumption. I would be surprised if existing compilers didn't take
advantage of those types of optimization opportunities.

[Jakob Bohm]

On 09/12/2015 02:06, supe...@casperkitty.com wrote:
> On Tuesday, December 8, 2015 at 4:50:58 PM UTC-6, Jakob Bohm wrote:
>> Really, what aspect of the standard would require that, after a test
>> has clearly proven equality?
>
> Unless realloc returns null, doing rvalue conversion on the old pointer
> will invoke Undefined Behavior. Using memcmp to compare the old pointer
> and the new one would not invoke Undefined Behavior, but the Standard
> allows for the possibility that pointers may compare bitwise equal without
> being semantically equivalent (e.g. given
>
> int hey(int x)
> {
> int foo[4][4];
> int *p1 = foo[0]+4;
> int *p2 = foo[1];
> if (x > 10)
> printf("Wow!");
> if (x < 23)
> *p2 = *p1;
> return memcmp(p1,p2);
> }
>
> the two pointers would likely compare bitwise-equal, but a compiler would
> be allowed to make the call to "printf" unconditional.
>

I don't see where the undefined behavior is (other than calling memcmp
with the wrong number of arguments and thus probably no relevant
prototype).

If the standard allows foo[0] + 4 to point somewhere other than foo[1],
then the assignment to *p2 would be undefined, otherwise a clearly
defined NOP.

Unless there is a clear linguistical defect in the text of the
standard, the bitwise unequalness undefinedness should be formally and
officially limited to the return value of memcmp(&p1, &p2, sizeof(p1))
in the same way that other arithmetic corner cases may have undefined
or implementation defined values, but not be "undefined behavior".

For example if the last line was changed to

return (x++) - (x++);

the value of that subtraction has always been undefined, but no
implementation that should be considered compliant would trigger
undefined random execution, just unpredictable value. It could even
vary between executions if the result ends up depending on picosecond
variations in the propagation of incremented x values in a RISC CPU
that normally requires delay slots between the two increments. However
the compiler would not be allowed to generate machine code that crashes
the CPU or triggers an invalid operation exception if that is what the
CPU specification says that too close accesses of the same register can
do.

>> Besides, the rules for shrinking and non-moving could do with either:
>>
>> - Stronger limits on implementations (shrink never moves)
>> OR
>> - A standard function for "resize if possible, but do not move" .
>
> I'd go for the latter, as well as a function to which code could pass a
> list of pointers to allocated blocks which the library could move around
> if fragmentation was an issue (provided that it updated the pointers in
> the list).

The specification for such a "defrag_allocs()" should be written to
allow a trivial NOP implementation, since an actual implementation is
going to be very non-trivial.

>
>> Also a standard version of the common msize() function (it has a longer
>> name in GNU libc) would also be nice.
>
> On some platforms it would be hard to guarantee anything useful about the
> semantics; a solution to that would be to have a return value that means
> "who knows"?
>

Any platform where free() is not a NOP should be able to look at what
free() would do if presented with that same pointer and conclude a size
from that. If the heap code was optimized for the absence of an
msize() function, implementing an msize() function might involve a
costly search of the data that malloc() would use to determine if there
is a malloc-consumable memory address before the free-extending to
address that free() would calculate if freeing the pointer being
queried.

But I fail to see how, in practical terms, one could implement malloc()
and free() without holding enough data to implement msize().

[supe...@casperkitty.com]

On Wednesday, December 9, 2015 at 12:26:28 AM UTC-6, Jakob Bohm wrote:
> I don't see where the undefined behavior is (other than calling memcmp
> with the wrong number of arguments and thus probably no relevant
> prototype).

Mea culpa on the memcmp, but the Undefined Behavior lies in the aliasing
of foo[0][4] with foo[1][0]. A compiler given the code:

void hey(int x)
{
int foo[4][4];
foo[1][0] = x;
foo[0][x] = 23;
return foo[1][0];
}

would be entitled to assume that the write to foo[0][x] cannot affect
foo[1][0] and thus simply return x. N1570 is very clear on that; I
haven't checked other versions, but I believe they are too. That same
inference would apply to:

void hey(int x)
{
int foo[4][4];
int *p = foo[0]+x;
foo[1][0] = x;
*p = 23;
return foo[1][0];
}

since *(foo[0]+x) is equivalent to foo[0][x].

> If the standard allows foo[0] + 4 to point somewhere other than foo[1],
> then the assignment to *p2 would be undefined, otherwise a clearly
> defined NOP.

The standard makes clear that foo[0]+4 is a one-past pointer for foo[0][3].
It will likely hold the same bits as the address of foo[1][0], but that
does not make them interchangeable.

> Unless there is a clear linguistical defect in the text of the
> standard, the bitwise unequalness undefinedness should be formally and
> officially limited to the return value of memcmp(&p1, &p2, sizeof(p1))
> in the same way that other arithmetic corner cases may have undefined
> or implementation defined values, but not be "undefined behavior".

> return (x++) - (x++);
>
> the value of that subtraction has always been undefined, but no
> implementation that should be considered compliant would trigger
> undefined random execution, just unpredictable value. It could even
> vary between executions if the result ends up depending on picosecond
> variations in the propagation of incremented x values in a RISC CPU
> that normally requires delay slots between the two increments. However
> the compiler would not be allowed to generate machine code that crashes
> the CPU or triggers an invalid operation exception if that is what the
> CPU specification says that too close accesses of the same register can
> do.

The Standard is very clear that two or more unsequenced operations to the
same object will invoke Undefined Behavior unless none of the operations is
a write.

> > I'd go for the latter, as well as a function to which code could pass a
> > list of pointers to allocated blocks which the library could move around
> > if fragmentation was an issue (provided that it updated the pointers in
> > the list).
>
> The specification for such a "defrag_allocs()" should be written to
> allow a trivial NOP implementation, since an actual implementation is
> going to be very non-trivial.

Naturally. IMHO, the Standard should define a lot of things which could on
many implementations be nops, but which on some implementations would block
compilation altogether (because they would assert some condition that the
implementation cannot satisfy), and on some would trigger an effects. For
example, given:

int foo(int *ip, float *fp)
{
*ip = 123;
__full_type_alias_barrier();
*fp = 12.0f;
__full_type_alias_barrier();
return *ip;
}

If the function is passed pointers to the same suitably-aligned storage,
regardless of its underlying type, I would suggest that it should be
required to return the integer representation of the bits in 12.0f; on
compilers which would not perform type-based aliasing analysis, the
directives could be ignored. On compilers that have no means of overriding
such analysis, the directives should force a compilation error. On
compilers that would normally perform such analysis but are capable of
overriding it, the directives should force the compiler to behave as though
it commits both writes to memory in the indicated sequence and then reads
the integer pointer (if a compiler in-lines the functions and knows that
the pointers will alias, it could skip the write to *ip and possibly the
read of *ip as well if it knows how 12.0f will be represented; if it knows
that the object whose address was passed will never be used again, it could
skip the write to *fp as well).

> > On some platforms it would be hard to guarantee anything useful about the
> > semantics; a solution to that would be to have a return value that means
> > "who knows"?

> But I fail to see how, in practical terms, one could implement malloc()
> and free() without holding enough data to implement msize().

As one possibility, a C implementation might invoke outside OS functions
which manage the heap in a fashion unknown to the C implementation; if the
OS doesn't include a "msize" function, there's no way the C implementation
could do so unless it preceded each allocation with its own record of the
size. If e.g. ZebraDOS 2.0 and ZebraDOS 3.0 manage memory differently, and
some code which requires ZebraDOS 3.0 relies upon its own knowledge of where
ZebraDOS 3.0 heap records are stored relative to malloc'ed pointers, adding
such information to the C implementation could be a breaking change.

Not a terribly *likely* possibility, to be sure, but my point is that rather
than saying that a C implementation must make the indicated change which
would make things less efficient and break some code, it would be better to
have a means via which the implementation can indicate that its msize
function can't do anything useful.

[Keith Thompson]

Jakob Bohm <jb-u...@wisemo.com> writes:
[...]

> For example if the last line was changed to
>
> return (x++) - (x++);
>
> the value of that subtraction has always been undefined, but no
> implementation that should be considered compliant would trigger
> undefined random execution, just unpredictable value. It could even
> vary between executions if the result ends up depending on picosecond
> variations in the propagation of incremented x values in a RISC CPU
> that normally requires delay slots between the two increments. However
> the compiler would not be allowed to generate machine code that crashes
> the CPU or triggers an invalid operation exception if that is what the
> CPU specification says that too close accesses of the same register can
> do.

It's not 100% clear (at least to me) whether you're discussing what you
think the standard *should* say, or what it actually *does* say.

In the current C standard (and all previous versions of it back to
C89/C90), the behavior of

return (x++) - (x++);

is undefined. That absolutely means that it can trigger undefined
random execution, anything from quietly returning whatever value you
think it should, to crashing the program, to setting the CPU on fire.

Are you suggesting that the behavior shouldn't be undefined, but
rather limited to returning some unspecified value? (I doubt that
the committee would approve such a change, but that doesn't keep
us from discussing it.)

[...]

> But I fail to see how, in practical terms, one could implement malloc()
> and free() without holding enough data to implement msize().

Suppose the implementation maintains a collection of doubly linked
lists of allocated memory chunks, one list for each allocatable
size (perhaps limited to powers of 2 starting at, say, 64 bytes).
malloc() could round the requested size up to the next power of 2
and allocate a new block in the appropriate list. free(), given
the address of the block, could remove it from the linked list
without having to know which list it's in.

Or suppose malloc() and free() are implemented on top of some similar
lower-level system calls. Perhaps the OS internally keeps track
of the size of each allocation, but doesn't make that information
available to the caller.

I'm not saying these are plausible implementations, but they're
possible and they could be conforming.

--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Jakob Bohm]

On 09/12/2015 17:39, Keith Thompson wrote:
> Jakob Bohm <jb-u...@wisemo.com> writes:
> [...]
>> For example if the last line was changed to
>>
>> return (x++) - (x++);
>>
>> the value of that subtraction has always been undefined, but no
>> implementation that should be considered compliant would trigger
>> undefined random execution, just unpredictable value. It could even
>> vary between executions if the result ends up depending on picosecond
>> variations in the propagation of incremented x values in a RISC CPU
>> that normally requires delay slots between the two increments. However
>> the compiler would not be allowed to generate machine code that crashes
>> the CPU or triggers an invalid operation exception if that is what the
>> CPU specification says that too close accesses of the same register can
>> do.
>
> It's not 100% clear (at least to me) whether you're discussing what you
> think the standard *should* say, or what it actually *does* say.
>

Here I was discussing what the standard should be saying unless
something is very very wrong (which you say it is then). It would
violate so many basic principles of computer behavior and techniques
for reasoning (formally or informally) about programs if unspecified
arithmetic results are allowed to promote to arbitrary side effects,
especially where a formal proof of program correctness eliminates the
value undefined expression via logic reasoning, while base criteria for
the language specify that the expression has no side effect on
variables the proof cares about.

> In the current C standard (and all previous versions of it back to
> C89/C90), the behavior of
>
> return (x++) - (x++);
>
> is undefined. That absolutely means that it can trigger undefined
> random execution, anything from quietly returning whatever value you
> think it should, to crashing the program, to setting the CPU on fire.

Which I think is insanely dangerous to the nth degree.

>
> Are you suggesting that the behavior shouldn't be undefined, but
> rather limited to returning some unspecified value? (I doubt that
> the committee would approve such a change, but that doesn't keep
> us from discussing it.)
>

Yes, or rather to making an unspecified change to the value of x and
resulting in an unspecified value, both within the limits of what an
uninitialized variable of type typeof(x) is allowed to hold.

Put another way, the undefined behavior should not extend beyond the
variables and values explicitly affected by the expression as written,
thus ensuring that any correctness proof of a program can safely use
the general property that a statement affects only that which the code
says it affects. Not providing this property makes reasoning about
program behavior an order of magnitude more complex, while providing it
would generally be zero cost for the implementer.

> [...]
>
>> But I fail to see how, in practical terms, one could implement malloc()
>> and free() without holding enough data to implement msize().
>
> Suppose the implementation maintains a collection of doubly linked
> lists of allocated memory chunks, one list for each allocatable
> size (perhaps limited to powers of 2 starting at, say, 64 bytes).
> malloc() could round the requested size up to the next power of 2
> and allocate a new block in the appropriate list. free(), given
> the address of the block, could remove it from the linked list
> without having to know which list it's in.

Indeed, that is why I said that msize() would not always be fast, as in
such an implementation, it would have to walk the list to find the list
head in order to decide which value to return.

>
> Or suppose malloc() and free() are implemented on top of some similar
> lower-level system calls. Perhaps the OS internally keeps track
> of the size of each allocation, but doesn't make that information
> available to the caller.

That, so far, is the only new hard case I have seen. However given the
importance of the C language, most platforms are likely to correct this
during the time it takes C libraries to implement the rest of the new
standard. Otherwise there could be a define:

__STDC__HAS__msize__

Which an implementation of <stdlib.h> must define as 1 if msize() is
fully implemented, 2 if msize() is implemented but unusually slow
undefined if msize() is not available.

There is also the other hard case mentioned in my first post on this:
An implementation where free() is a NOP and malloc() just keeps raising
the top of heap memory until it hits the OS/hardware ceiling.

>
> I'm not saying these are plausible implementations, but they're
> possible and they could be conforming.
>

[Tim Rentsch]

Hans-Bernhard Broeker <HBBr...@t-online.de> writes:

> Am 04.12.2015 um 08:13 schrieb Jakob Bohm:
>
>> What (if anything) is the type for an arbitrary (but not directly
>> invokable) function pointer which can safely be cast to and from a
>> known correct function pointer type (in other words which type is
>> to function pointers what "void*" is to data pointers).
>
> I agree with previous observations: there isn't one. I disagree
> with the conclusion that this means such a thing is missing from
> the standard; IMHO it's not actually needed.
>
> The concept of "just some data" is useful and necessary. There
> are functions that have to deal with data of unknown, even
> unknowable, structure, and they can do useful work with them,
> primarily by moving it across external interfaces of the program.
>
> I don't think the same would apply to the concept of "just some
> function". In particular there's no remotely portable use for
> moving a C function's contents (i.e. the machine code) by
> something like memcpy() or fwrite().

That is true, but that isn't the only way (void*) is used.

> Nor is there really any other useful thing you can ever do with a
> function of unknown type, because can never actually call it

> without causing undefined behaviour. [...]

I think it is worth pointing out that there are several things
that one might portably (or semi-portably) do with an arbitrary
function pointer:

* convert to an integer type
* test for equality with another function pointer
* compare to 0

Some example uses:

* A "dictionary" of function pointers, which includes for
each function some encoding of its type

* A set of function pointers kept as a linked list, where
all functions in a given list have the same type (known
externally, but not known to the linked list code,
which is generic).

Whether these (or other) examples are compelling enough to be
worth adding a (void*)-like analog for function pointers is still
IMO open to debate. But I think the statement "Nor is there

really any other useful thing you can ever do with a function of

unknown type" falls short of being completely accurate. There
are some useful things; the question is how useful are they,
and are the potential gains worth the (not yet specified) costs?

[Kaz Kylheku]

On 2015-12-09, Jakob Bohm <jb-u...@wisemo.com> wrote:
> On 09/12/2015 17:39, Keith Thompson wrote:
>> In the current C standard (and all previous versions of it back to
>> C89/C90), the behavior of
>>
>> return (x++) - (x++);
>>
>> is undefined. That absolutely means that it can trigger undefined
>> random execution, anything from quietly returning whatever value you
>> think it should, to crashing the program, to setting the CPU on fire.
>
> Which I think is insanely dangerous to the nth degree.

Indeed, it is illogical.

Just because an ISO document *allows* something (or, rather, *doesn't
disallow*, that doesn't mean it's *possible*.

Setting the CPU on fire certainly doesn't violate any stated requirement
in ISO C.

However, it violates requirements given elsewhere, pertaining to the
system as a whole.

A machine which somehow catches fire because of undefined behavior in a
C program would certainly violate some safety requirements, and the
actual problem will be traceable to something other than the C undefined
behavior, like some ill-designed circuitry which allows a runaway
temperature rise.

Standards are written with the good faith that the engineers
implementing them are competent and ethical.

[Tim Rentsch]

Jakob Bohm <jb-u...@wisemo.com> writes:

> On 09/12/2015 02:06, supe...@casperkitty.com wrote:
>> On Tuesday, December 8, 2015 at 4:50:58 PM UTC-6, Jakob Bohm wrote:

> [...]

>>> Also a standard version of the common msize() function (it has a
>>> longer name in GNU libc) would also be nice.
>>
>> On some platforms it would be hard to guarantee anything useful
>> about the semantics; a solution to that would be to have a
>> return value that means "who knows"?
>
> Any platform where free() is not a NOP should be able to look at
> what free() would do if presented with that same pointer and
> conclude a size from that. If the heap code was optimized for the
> absence of an msize() function, implementing an msize() function
> might involve a costly search of the data that malloc() would use
> to determine if there is a malloc-consumable memory address before
> the free-extending to address that free() would calculate if
> freeing the pointer being queried.
>
> But I fail to see how, in practical terms, one could implement
> malloc() and free() without holding enough data to implement
> msize().

I think you are making assumptions about how these would be
implemented that may not hold in general. In effect you want to
ask about how much adjacent unallocated space there is. Note
however a significant difference with respect to free(). During
a call to free(), normally we expect it can discover how much
adjacent unallocated space there is, at the moment of the free()
call. But what msize() does isn't that; for msize() to be
useful, it has to know how much adjacent unallocated space there
is /that also will not be allocated in the future/. This extra
requirement imposes additional constraints on how malloc() and
free() may be implemented. Those constraints may be overly
limiting, or they may not be, but I don't think they can be
dismissed out of hand.

[James Kuyper]

On 12/09/2015 01:26 AM, Jakob Bohm wrote:
> On 09/12/2015 02:06, supe...@casperkitty.com wrote:
>> On Tuesday, December 8, 2015 at 4:50:58 PM UTC-6, Jakob Bohm wrote:
>>> Really, what aspect of the standard would require that, after a test
>>> has clearly proven equality?
>>
>> Unless realloc returns null, doing rvalue conversion on the old pointer
>> will invoke Undefined Behavior. Using memcmp to compare the old pointer
>> and the new one would not invoke Undefined Behavior, but the Standard
>> allows for the possibility that pointers may compare bitwise equal without
>> being semantically equivalent (e.g. given
>>
>> int hey(int x)
>> {
>> int foo[4][4];
>> int *p1 = foo[0]+4;
>> int *p2 = foo[1];
>> if (x > 10)
>> printf("Wow!");
>> if (x < 23)
>> *p2 = *p1;
>> return memcmp(p1,p2);
>> }
>>
>> the two pointers would likely compare bitwise-equal, but a compiler would
>> be allowed to make the call to "printf" unconditional.
>>
>
> I don't see where the undefined behavior is (other than calling memcmp
> with the wrong number of arguments and thus probably no relevant
> prototype).

The array pointed at by p1 is foo[0], and has a length of only 4.
Therefore, p1 points one past the end of that array. Such a pointer can
be compared for equality or relative order with other pointers, but
dereferencing such a pointer has undefined behavior. Because of the
contiguity requirements imposed by the C standard on arrays, p1 should
be pointing at the same location at p2, but because dereferencing p1 has
undefined behavior, an implementation could implement run-time pointer
validity tests that would fail upon the execution of *p1 in any context
other than &*p1.

That's not very likely in real life - run-time pointer validity tests
are expensive, and likely only to be implemented for debugging runs. A
more realistic possibility is that an optimizer could see (in a similar
program, not this one) the expressions p1[i] and p2[j], and notice that
since they refer to elements of two different non-overlapping arrays
(foo[0] and foo[1], respectively), will conclude that there is no need
to check for the possibility that p1[i] and p2[j] are aliases for each
other - any values for i and j that make them aliases would render the
behavior of any code that cares about whether they alias each other
undefined.

> If the standard allows foo[0] + 4 to point somewhere other than foo[1],
> then the assignment to *p2 would be undefined, otherwise a clearly
> defined NOP.

No, it's undefined behavior, not a NOP.

...

> For example if the last line was changed to
>
> return (x++) - (x++);
>
> the value of that subtraction has always been undefined, but no
> implementation that should be considered compliant would trigger

> undefined random execution, just unpredictable value. ...

I've seen an explanation how code like that could fail in ways other
than simply returning an unpredictable value, though this explanation is
more likely to apply if x is a large type, such as long double.

Basically, implementation of x++ requires the issuing of multiple
machine instructions. There might be some reason why (x++) - (y++) could
be optimized by interleaving the instructions for x++ with those for
y++, which would not be problematic. The result of interleaving the
instructions for x++ and a second x++, however, could be catastrophic,
and not simply an unexpected value, because of the way those
instructions interact with each other.

Note: I'm describing from memory an explanation provided by someone else
a long time ago - I cannot provide an example of a specific platform for
which these things are all true - but it seems entirely plausible to me
that there could be such a platform, which is all that matters as far as
explaining why the standard was written this way.

Because the behavior of such code is undefined, the optimizer is NOT
required to make sure to avoid that problem. Would you consider such an
implementation to be non-compliant? If so, on what grounds? "undefined
behavior" means that "this standard imposes no requirements" - which is
a pretty comprehensive statement.

> ... It could even

> vary between executions if the result ends up depending on picosecond
> variations in the propagation of incremented x values in a RISC CPU

> that normally requires delay slots between the two increments. ...

That sounds like it might be precisely the kind of catastrophic
consequence that other person was talking about.

> ... However

> the compiler would not be allowed to generate machine code that crashes
> the CPU or triggers an invalid operation exception if that is what the
> CPU specification says that too close accesses of the same register can
> do.

When the behavior is undefined, the C implementation is, by definition,
unconstrained by any requirements imposed by the C standard. It is, in
particular, not constrained to generate code which avoids causing a
crash or an invalid operation exception. A C implementation is normally
so constrained, when any other requirement is applicable, because that
other requirement cannot, in general, be met if there's a crash or an
invalid operation exception.

>>> Also a standard version of the common msize() function (it has a longer
>>> name in GNU libc) would also be nice.
>>
>> On some platforms it would be hard to guarantee anything useful about the
>> semantics; a solution to that would be to have a return value that means
>> "who knows"?
>>
>
> Any platform where free() is not a NOP should be able to look at what
> free() would do if presented with that same pointer and conclude a size
> from that. If the heap code was optimized for the absence of an
> msize() function, implementing an msize() function might involve a
> costly search of the data that malloc() would use to determine if there
> is a malloc-consumable memory address before the free-extending to
> address that free() would calculate if freeing the pointer being
> queried.
>
> But I fail to see how, in practical terms, one could implement malloc()
> and free() without holding enough data to implement msize().

That depends upon what msize() is defined as doing. There's no man page
for any such function on my system, so I can't be sure. If it's defined
as returning the actual size of the allocated block of memory, I have to
agree with you. However, an implementation is free to allocate more
memory than requested, and as I understand it, most implementations
routinely do so, and the malloc() family of functions has no need to
keep track of any number other than the the amount of memory actually
allocated. So being unable to return the requested size seems entirely
reasonable to me.

[supe...@casperkitty.com]

On Wednesday, December 9, 2015 at 10:39:17 AM UTC-6, Keith Thompson wrote:
> Are you suggesting that the behavior shouldn't be undefined, but
> rather limited to returning some unspecified value? (I doubt that
> the committee would approve such a change, but that doesn't keep
> us from discussing it.)

I would like to see many things that are presently Undefined Behavior changed
to Testably-Constrained Behavior, and Implementation-Defined Behavior likewise
changed to Testably-Specified Behavior.

The difference between Testably-Constrained/Specified Behavior (collectively,
TCSB) and UB/IB would be that the Standard would specify certain optional
behavioral guarantees, and standard means would exist via which code could
specify guarantees that it needs or could test for guarantees that an
implementation may or may not support [the difference between the two
approaches would be that an implementation could change its behaviors based
upon stated requirements and code could adapt its actions to accommodate
the available guarantees.

For example, a function which is supposed to add multi-precision integers
stored in two "unsigned" arrays and store the sum into a third might
specify that it will work correctly in all cases where the destination
partially or fully overlaps the source. One way to achieve that would be
to allocate a temporary buffer, perform the computation with that buffer
as the destination, and then copy it to the destination pointer, but that
would likely be sub-optimal if none of the pointers overlap. If, however,
an implementation can guarantee that a relational comparison between two
pointers that are unrelated will never do anything other than yield a zero
or yield a one, it may be able to avoid the redundant copy in most cases
where the pointers don't alias. The function wouldn't *require* that a
compiler be able to guarantee that comparing unrelated pointers wouldn't
set the CPU on fire, but it would be able to work more efficiently on
compilers that *could* guarantee that.

With regard to the indicated expression, I'd suggest that the "normative"
semantics for improperly-sequenced reads and writes should be that writes
that are Unsequenced with regard to other writes set the variable to
Indeterminate Value, and reads that are unsequenced with regard to writes
yield Indeterminate Value; the normative behavior for Indeterminate Value
should be that unless an implementation specifies that reading IV of some
type will do something else, reading an IV will simply yield an IV, and
unless arithmetic on an IV is specified as doing something else, it will
simply yield another IV. Thus, unless an implementation indicates
otherwise, given:

uint32_t x=0,y1,y2,z1,z2;
++x + ++x; // Make X hold indeterminate value
y1=x;
z1=y1;
__SOLIDIFY_LVAUE(y1);
y2=y1;
__SOLIDIFY_LVALUE(z1);
z2=z1;

y1 would be assigned Indeterminate Value. Variable z1 would likewise be
assigned Indeterminate Value. __SOLIDIFY_LVALUE() would be a directive
which does nothing unless the lvalue holds Indeterminate Value, in which
case it would replace it with an Unspecified Value. After the above code
executes, y1 and y2 would hold the same arbitrary value as each other,
and z1 and z2 would hold the same arbitrary value as each other, but the
values in y2 and z2 may arbitrarily match or not.

Note that under such an interpretation, if no code ever examined the value
of x after it was made Indeterminate, such action would be effectively a
no-op except on implementations which specify that unsequenced writes may
have effects beyond setting the target to Indeterminate Value.

[Kaz Kylheku]

It is irresponsible to do so. The fact that undefined behavior occurs
whenever x < 23 holds must be deemed to be an accident.

When I'm programming a computer, I'm having a conversation with a
machine.

The machine must assume that I'm adhering to the conversational maxims:

- the maxim of quantity: I am not being excessively verbose
(the x < 23 test I wrote isn't useless verbiage; I intend to have
x tested).

- the maxim of quality: I am not encoding undefined behaviors, or
the threat of undefined behaviors, on purpose; I *believe* the
code to be correct for all possible inputs.

- the maxim of relevance: I am not introducing the threat of undefined
behavior in order to express the wish to influence the translation
of something else.

In turn, the machine violates the quality maxim by acting in the
following way. The optimized translation is a conversational utterance
(the machine's reply to me) and it is falsely based on inadequate
evidence of its correctness (unwarranted assumptions of my intent).
The machine knows that the behavior is not defined whenever x < 24,
yes. However, the machine does not know that *I* know it. For that it
has inadequate evidence. Yet it is proceeding dishonestly on that
assumption.

The proper, responsible way to have this optimization is to issue a
diagnostic: "You have undefined behavior here if x < 24, so I'm making
the assumption that x >= 24 and optimizing accordingly".

Merely by not informing me of this important fact which it knows;
it violates the quantity maxim: its utterance is not adequately
informative.

[Keith Thompson]

Ok. That's a valid opinion (not that you need me to tell you that),
though not one that I share.

I'll just mention that this is not a mistake in the standard. The C
standard very deliberately does not define the behavior of `x++ - x++`,
which means that it imposes no requirements on how that expression
behaves when evaluated.

Personally I don't find that "insanely dangerous". It's easy in this
particular case, and not too difficult in general, to avoid writing code
that modifies an object twice between sequence points.

Even if the behavior were well defined, whatever
return (x++) - (x++);
is intended to do, there is certainly a clearer way to express that
intent.

IIRC Java defines a strict left-to-right order of evaluation; the above
would would have well defined behavior in Java, but it still would not
survive a code review.

[...]

[supe...@casperkitty.com]

On Wednesday, December 9, 2015 at 12:51:23 PM UTC-6, Kaz Kylheku wrote:
> - the maxim of quality: I am not encoding undefined behaviors, or
> the threat of undefined behaviors, on purpose; I *believe* the
> code to be correct for all possible inputs.

That could be flipped around: you believe that the program will never
receive any inputs for which the code would be incorrect. The problem
is that the compiler is regarding such a belief as a certainty.

> The proper, responsible way to have this optimization is to issue a
> diagnostic: "You have undefined behavior here if x < 24, so I'm making
> the assumption that x >= 24 and optimizing accordingly".

Difficulties arise if a function gets inline-expanded multiple times and
different parts get eliminated on different expansions. Such scenarios
represent the major situation where this kind of optimization is most
useful, but diagnostic messages would be useless unless there were a means
of telling the compiler "Yes, I know this code will generate UB if x has
this value, but I want you to silently optimize based upon that"; IMHO,
if a directive would be necessary to usefully disable the warnings in such
cases, there's no reason to have the compiler perform the optimization
without such a directive. Instead have the compiler say "If y will always
be less than 23, efficiency may be improved by adding a ___ directive here;
otherwise a ___ directive may be added to stifle this message without the
optimization".

[Kaz Kylheku]

On 2015-12-09, Keith Thompson <ks...@mib.org> wrote:
> Even if the behavior were well defined, whatever
> return (x++) - (x++);
> is intended to do, there is certainly a clearer way to express that
> intent.
>
> IIRC Java defines a strict left-to-right order of evaluation; the above
> would would have well defined behavior in Java, but it still would not
> survive a code review.

That depends on the relationship of that statement to the scope
and objectives of the code review.

If it is in newly introduced code which is being reviewed before
a merge to the product stream, almost certainly would not pass.

If it is spotted in existing code being reviewed for real run-time
issues, it might well surivive. Everyone would likely agree that it is
code stink, but if it is actually correct, it doesn't call for an
immediate fix. All changes carry risk.

Even if a decision is made to change it, it can just be dumped
into a bug database as a new task, and marked postponed to a future
project milestone.

The same reasoning and latitude couldn't, of course, be applied if it
were C or C++.

[Keith Thompson]

Kaz Kylheku <k...@kylheku.com> writes:
[...]

> The proper, responsible way to have this optimization is to issue a
> diagnostic: "You have undefined behavior here if x < 24, so I'm making
> the assumption that x >= 24 and optimizing accordingly".
>
> Merely by not informing me of this important fact which it knows;
> it violates the quantity maxim: its utterance is not adequately
> informative.

I recently read an article by the authors of llvm/clang explaining
that issuing such diagnostics is actually extremely difficult.
I think I posted the link here, or in comp.lang.c, but I haven't
found it. I'll try to find it and post it later.

[Wojtek Lerch]

On 09/12/2015 1:51 PM, Kaz Kylheku wrote:
> On 2015-12-09, Wojtek Lerch <wojt...@yahoo.ca> wrote:
>> On 08/12/2015 10:15 PM, Kaz Kylheku wrote:
>>> On 2015-12-09, supe...@casperkitty.com <supe...@casperkitty.com> wrote:
>>>> On Tuesday, December 8, 2015 at 4:50:58 PM UTC-6, Jakob Bohm wrote:
>> ...
>>>> int hey(int x)
>>>> {
>>>> int foo[4][4];
>>>> int *p1 = foo[0]+4;
>>>> int *p2 = foo[1];
>>>> if (x > 10)
>>>> printf("Wow!");
>>>> if (x < 23)
>>>> *p2 = *p1;
>>>> return memcmp(p1,p2);
>>>> }

...
>> [...] The implementation simply needs to notice that the function

>> has undefined behaviour when x is less than 23, assume that the
>> programmer will make sure never to call it with an argument that leads
>> to undefined behaviour, and perform optimizations based on that
>> assumption. I would be surprised if existing compilers didn't take
>> advantage of those types of optimization opportunities.
>
> It is irresponsible to do so. The fact that undefined behavior occurs
> whenever x < 23 holds must be deemed to be an accident.

Do you mean in general, or just in this silly little example? Because
in the real life, a lot of functions are implemented in a way that may
lead to undefined behaviour if the arguments do not meet some
requirements. Documenting the requirements is often deemed good enough.
The standard C library is full of functions like that.

Sometimes it is desirable for a function to perform a complete sanity
check on its parameters. Sometimes it may be too expensive,
unnecessary, or impossible. For instance, any function that takes a
pointer has no way to find out whether the pointer points to an object
or past the end of an array, or how many objects there are in front of
and behind what it points to.

> When I'm programming a computer, I'm having a conversation with a
> machine.
>
> The machine must assume that I'm adhering to the conversational maxims:
>
> - the maxim of quantity: I am not being excessively verbose
> (the x < 23 test I wrote isn't useless verbiage; I intend to have
> x tested).

No, a C compiler can't assume that. It could be that part of the
function was produced by expanding a macro. Perhaps the author of the
macro put a sanity check in it but the check is redundant because the
caller of the macro also wrote his own check. Perhaps the macro has a
documented requirement that p1 and p2 must be safe to dereference when
x<23, but the person who wrote the function didn't care about that
requirement because he knew that the function would never be called with
x<23.

> - the maxim of quality: I am not encoding undefined behaviors, or
> the threat of undefined behaviors, on purpose; I *believe* the
> code to be correct for all possible inputs.

Those are two different things. I agree that people generally don't put
undefined behaviour in their programs on purpose; but I doubt there are
many non-trivial programs that don't have any functions that could
possibly be abused in a way leading to undefined behaviour.

> - the maxim of relevance: I am not introducing the threat of undefined
> behavior in order to express the wish to influence the translation
> of something else.

Personally, I would find it useful to have an explicit macro, similar to
assert(), that would trigger undefined behaviour when invoked with its
argument set to zero. This way I could indicate to the compiler that
certain combinations of values are expected to be impossible, and to
perform any optimisations based on that.

> In turn, the machine violates the quality maxim by acting in the
> following way. The optimized translation is a conversational utterance
> (the machine's reply to me) and it is falsely based on inadequate
> evidence of its correctness (unwarranted assumptions of my intent).
> The machine knows that the behavior is not defined whenever x < 24,
> yes. However, the machine does not know that *I* know it. For that it
> has inadequate evidence. Yet it is proceeding dishonestly on that
> assumption.

The whole design of C was based on the assumption that the compiler
should trust that the programmer knows what he's doing. I don't think I
know of another language (apart from assemblers) that would give the
programmer a comparable number of opportunities to invoke undefined
behaviour. With your expectations, you have picked absolutely the worst
language.

> The proper, responsible way to have this optimization is to issue a
> diagnostic: "You have undefined behavior here if x < 24, so I'm making
> the assumption that x >= 24 and optimizing accordingly".

Pretty much any arithmetic on signed integers can have undefined
behaviour, if the operands have values that lead to an overflow. Would
you really want a diagnostic every time you do math on ints, except when
there's an explicit test nearby (right on the previous line of code?)
that verifies that there's absolutely no chance of an overflow?

What about "You have undefined behaviour here unless ptr and ptr+n-1
point to elements of the same array, so I'm making the assumption that
they do and optimizing accordingly"?

[supe...@casperkitty.com]

On Wednesday, December 9, 2015 at 10:16:35 PM UTC-6, Wojtek Lerch wrote:
> Personally, I would find it useful to have an explicit macro, similar to
> assert(), that would trigger undefined behaviour when invoked with its
> argument set to zero. This way I could indicate to the compiler that
> certain combinations of values are expected to be impossible, and to
> perform any optimisations based on that.

What I'd rather have in many cases would be macros/intrinsics which would
indicate that a compiler may at its leisure either trap in an implementation-
defined fashion if a condition does not (or, depending upon the macro, will
not hold true or did not hold true) or ignore the macro, with other macros
or intrinsics being available to mark blocks within which outside "checked
assumption" macros are not allowed to fire. Such macros would make it
possible for code to *safely* give compilers a lot of freedom without
creating security holes.

> The whole design of C was based on the assumption that the compiler
> should trust that the programmer knows what he's doing. I don't think I
> know of another language (apart from assemblers) that would give the
> programmer a comparable number of opportunities to invoke undefined
> behaviour. With your expectations, you have picked absolutely the worst
> language.

The design of C was based on the idea that programmers who knew how a
particular implementation did certain things could and should take advantage
of such knowledge. The use of the langauge for systems programming--which
was its original intended purpose--would be impossible without making use
of such knowledge.

> Pretty much any arithmetic on signed integers can have undefined
> behaviour, if the operands have values that lead to an overflow. Would
> you really want a diagnostic every time you do math on ints, except when
> there's an explicit test nearby (right on the previous line of code?)
> that verifies that there's absolutely no chance of an overflow?

On most platforms, overflow would historically have one of two effects:
either computations would trap, or they would wrap. There are a fair
number of situations where either behavior would be acceptable, but modern
UB would not be. Note, btw, that code like:

uint16_t x = 65533;
uint16_t y=x*x;

yields a fully-defined result on platforms where "int" is 16 bits, or where
it is 33 bits or larger, but Undefined Behavior on those where it is 32 bits,
but 32-bit platforms where such a computation wraps will yield the same
behavior as those where "int" is 16 bits or 33+ bits.

[martin...@yahoo.co.uk]

But such machines have existed. (For example: http://trixter.oldskool.org/2006/02/02/computing-myth-1-software-cannot-damage-hardware/ )

[Jakob Bohm]

What would be much more useful than allowing implementations to run off
on a tangent based on overinterpretation of the term "undefined
behavior" would be to have the standard equivalent of Microsoft's
__assume keyword. For those unfamiliar with it, it can be described as
follows:

The expression __assume(condition) has the following effect:
The value is always void.
The condition is *not* evaluated at runtime (and no code is
generated to do so).
If a hypothetical evaluation of (condition) would be true, nothing
happens, though the program might run faster.
If a hypothetical evaluation of (condition) would be false, the
compiler is free to optimize away any code that would be execute
after or lead to execution for such a case.

As a corollary, the expression __assume(1) is a NOP.
As a corollary, the expression __assume(0) tells the compile that
any code path that would unconditionally lead to execution of the
expression can be optimized away.

In other words, the ability to tell the compiler that some condition is
impossible and can be optimized away is entirely separate from any
"undefined" cases the compiler might spot.

Thus the compiler remains obliged to do what it is explicitly told to
do, and is not encouraged to do things that may constitute a complete
misunderstanding of programmer intent.

>> When I'm programming a computer, I'm having a conversation with a
>> machine.
>>
>> The machine must assume that I'm adhering to the conversational maxims:
>>
>> - the maxim of quantity: I am not being excessively verbose
>> (the x < 23 test I wrote isn't useless verbiage; I intend to have
>> x tested).
>
> No, a C compiler can't assume that. It could be that part of the
> function was produced by expanding a macro. Perhaps the author of the
> macro put a sanity check in it but the check is redundant because the
> caller of the macro also wrote his own check. Perhaps the macro has a
> documented requirement that p1 and p2 must be safe to dereference when
> x<23, but the person who wrote the function didn't care about that
> requirement because he knew that the function would never be called with
> x<23.

The compiler could just as easily assume that dereferencing p1 and p2
*is* safe, despite its own guesses to the contrary. Perhaps the person
who wrote the program knows more about the machines innards than the
compiler author and wants to access whatever "invalid" location they
point to, perhaps to access some hidden metadata, perhaps to take
advantage of the implementation following standard memory layout (where
p1==p2 in the example), perhaps to deliberately trigger the invalid
memory access response from the MMU.

Discarding input (in this case code) in favor of a machine guess is the
fundamental mistake that leads to widespread disdain for "DWIM",
"Autocorrect" etc.

>
>> - the maxim of quality: I am not encoding undefined behaviors, or
>> the threat of undefined behaviors, on purpose; I *believe* the
>> code to be correct for all possible inputs.
>
> Those are two different things. I agree that people generally don't put
> undefined behaviour in their programs on purpose; but I doubt there are
> many non-trivial programs that don't have any functions that could
> possibly be abused in a way leading to undefined behaviour.

Indeed, but optimizing away entire code paths because they would lead
to such "undefined" corner cases makes a compiler completely unsuited
to be allowed anywhere near programs of non-trivial size, because the
only way to use such a compiler is to constantly mistrust not only the
input (in case it might be malicious) but also the compiler itself
(because it is positively known to be *deliberately* malicious).

>
>> - the maxim of relevance: I am not introducing the threat of undefined
>> behavior in order to express the wish to influence the translation
>> of something else.
>
> Personally, I would find it useful to have an explicit macro, similar to
> assert(), that would trigger undefined behaviour when invoked with its
> argument set to zero. This way I could indicate to the compiler that
> certain combinations of values are expected to be impossible, and to
> perform any optimisations based on that.

See my summary of Microsoft's __assume keyword above.

>
>> In turn, the machine violates the quality maxim by acting in the
>> following way. The optimized translation is a conversational utterance
>> (the machine's reply to me) and it is falsely based on inadequate
>> evidence of its correctness (unwarranted assumptions of my intent).
>> The machine knows that the behavior is not defined whenever x < 24,
>> yes. However, the machine does not know that *I* know it. For that it
>> has inadequate evidence. Yet it is proceeding dishonestly on that
>> assumption.
>
> The whole design of C was based on the assumption that the compiler
> should trust that the programmer knows what he's doing. I don't think I
> know of another language (apart from assemblers) that would give the
> programmer a comparable number of opportunities to invoke undefined
> behaviour. With your expectations, you have picked absolutely the worst
> language.

Indeed, and basing a C compiler on the assumption that the programmer
doesn't mean what he actually says is going against that principle in
the worst possible way. It's an oxymoron on par with an "optimizing
assembler".

>
>> The proper, responsible way to have this optimization is to issue a
>> diagnostic: "You have undefined behavior here if x < 24, so I'm making
>> the assumption that x >= 24 and optimizing accordingly".
>
> Pretty much any arithmetic on signed integers can have undefined
> behaviour, if the operands have values that lead to an overflow. Would
> you really want a diagnostic every time you do math on ints, except when
> there's an explicit test nearby (right on the previous line of code?)
> that verifies that there's absolutely no chance of an overflow?
>
> What about "You have undefined behaviour here unless ptr and ptr+n-1
> point to elements of the same array, so I'm making the assumption that
> they do and optimizing accordingly"?

What about assuming that the programmer knows what pointers and pointer
subtraction really is at the machine level, and then doing what the
programmer asks even in cases not covered by the imprecise expressions
of these facts in the language standard?

>
>> Merely by not informing me of this important fact which it knows;
>> it violates the quantity maxim: its utterance is not adequately
>> informative.
>>
>

I would rephrase this argument under another single maxim:

* The maxim of obedience: The machine must obey the human if at all
possible.

[martin...@yahoo.co.uk]

On Thursday, 10 December 2015 14:06:01 UTC+1, Jakob Bohm wrote:
> On 10/12/2015 05:16, Wojtek Lerch wrote:
> > Those are two different things. I agree that people generally don't put
> > undefined behaviour in their programs on purpose; but I doubt there are
> > many non-trivial programs that don't have any functions that could
> > possibly be abused in a way leading to undefined behaviour.
>
> Indeed, but optimizing away entire code paths because they would lead
> to such "undefined" corner cases makes a compiler completely unsuited
> to be allowed anywhere near programs of non-trivial size, because the
> only way to use such a compiler is to constantly mistrust not only the
> input (in case it might be malicious) but also the compiler itself
> (because it is positively known to be *deliberately* malicious).

You have a problem then, because I believe all popular compilers *do*
do optimize away entire code paths.

My favourite example is where GCC turned what looked like valid code
to fill a table into an infinite loop which overwrote all memory:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=33498

I expect to find similar optimizations in all other compilers.

[Jakob Bohm]

A safer alternative would be to specify as a mandatory standard
requirement, that "indeterminate values" and "uninitialized values" are
arbitrary (unspecified and possibly invocation specific) values within
the representable set of values for the type in question. Thus for
example the following would lead to a guaranteed 0:

int x,y;
long z;
...
y = x++ + x++; // Indeterminate value
z = y; // z has an indeterminate value in the int range, but is
// not any other long value.

if (y <= MININT) // This may or may not be true depending on the
// runtime choice of y
y = 0;
// It is now true that y > MININT, but is otherwise indeterminate
x = y - 1; // This is not indeterminate because y > MININT
y -= x; // y is now 1.
// x is less that MAXINT, but is otherwise indeterminate
--y; // y is now 0

> uint32_t x=0,y1,y2,z1,z2;
> ++x + ++x; // Make X hold indeterminate value
> y1=x;
> z1=y1;
> __SOLIDIFY_LVAUE(y1);
> y2=y1;
> __SOLIDIFY_LVALUE(z1);
> z2=z1;
>
> y1 would be assigned Indeterminate Value. Variable z1 would likewise be
> assigned Indeterminate Value. __SOLIDIFY_LVALUE() would be a directive
> which does nothing unless the lvalue holds Indeterminate Value, in which
> case it would replace it with an Unspecified Value. After the above code
> executes, y1 and y2 would hold the same arbitrary value as each other,
> and z1 and z2 would hold the same arbitrary value as each other, but the
> values in y2 and z2 may arbitrarily match or not.
>
> Note that under such an interpretation, if no code ever examined the value
> of x after it was made Indeterminate, such action would be effectively a
> no-op except on implementations which specify that unsequenced writes may
> have effects beyond setting the target to Indeterminate Value.
>

[supe...@casperkitty.com]

On Thursday, December 10, 2015 at 7:26:19 AM UTC-6, Jakob Bohm wrote:
> A safer alternative would be to specify as a mandatory standard
> requirement, that "indeterminate values" and "uninitialized values" are
> arbitrary (unspecified and possibly invocation specific) values within
> the representable set of values for the type in question. Thus for
> example the following would lead to a guaranteed 0:

Allowing indeterminate values makes possible some significant optimizations
that are not otherwise possible; having ways of "solidifying" such values
makes it possible for programmers to actually *let* compilers make such
optimizations in useful code paths. You're correct that Unspecified Value
is safer than Indeterminate Value, and IMHO compilers should have options to
automatically convert Unspecified Values to Indeterminate Values, but as
with aliasing what's really necessary to make code safe isn't a sledge-
hammer to stomp out all optimizations, but rather well-defined means of
precisely specifying semantics at those few places in the code where it
actually matters.

Many programs may be viewed as having a separate "data path" and "control
path", with most calculations being on the data path. Often some parts of
the data will be merged into the control path (e.g. many file formats
include information about the file size), and it's very important to
tightly guard all the places where that happens, but in many cases
guarding those will suffice to meet application requirements. If someone
feeds a corrupt graphics file into a program, it may be acceptable to have
it yield an arbitrary pattern of pixel data as output provided that it does
not expose any security vulnerabilities. Letting Indeterminate Values
into the control path would risk such vulnerabilities, but it should be
possible for a programmer to safely ignore errant calculations which are
confined to the data path.

[Jakob Bohm]

That is why I framed it as "malloc-consumable memory" not
"unallocated memory". Regardless of how it is implemented, malloc()
must know how not to overwrite the memory that was returned by previous
malloc() and not yet passed to free(). While free() must know not to
release memory belonging to the nearest higher address returned by a
different call to malloc();

As I mentioned, these two requirements (but not msize()) could be
trivially provided by the following silly allocator:

char *pNxtFree;
char *const pEndOfMem;

void *malloc(size_t siz) {
void *p = pNxtFree;
if (siz > pEndOfMem - p) {
errno = ENOMEM;
return NULL;
}
pNxtFree = p + siz;
return p;
}

void free(void* p) {
}

void *realloc(void *pold, size_t siz) {
void *p;
if (!siz)
return NULL;
p = malloc(siz);
if (pold)
memmove(p, pold, siz); // Overlaps if growing and pold is close
// Copies unrelated data to uninit bytes
// if growing.
return p;
}

void *calloc(size_t siz1, size_t siz2) {
size_t siz;
void *p;
siz = siz1 * siz2;
if (siz2 && siz / siz2 != siz1)
return NULL; // Overflow
p = malloc(siz);
if (p)
memset(p, 0, siz);
return p;

[Jakob Bohm]

That bug is almost the canonical example of why that is a *horrible*
way to implement a C compiler.

Skilled C programmers are almost by definition low level programmers,
who usually know the exact behavior of their hardware when faced with
numeric overflow (on most hardware it wraps within the signed int
encoding). It is *normal* for C programs to actively use the resulting
wrapped values. To most people outside the C committee, signed
overflow is implementation defined, not undefined, and in the absence of
a different definition in the compiler manual, the definition in the
CPU manual is used.

In digital signal processing, standard algorithms are commonly designed
to respond in well specified and controlled way to integer overflow
handling in normal CPUs, and to contain the resulting noise in the
output signal. Compiling such algorithms with a crazy compiler like
that version of GCC would break horribly.

[Jakob Bohm]

On 10/12/2015 14:47, supe...@casperkitty.com wrote:
> On Thursday, December 10, 2015 at 7:26:19 AM UTC-6, Jakob Bohm wrote:
>> A safer alternative would be to specify as a mandatory standard
>> requirement, that "indeterminate values" and "uninitialized values" are
>> arbitrary (unspecified and possibly invocation specific) values within
>> the representable set of values for the type in question. Thus for
>> example the following would lead to a guaranteed 0:
>
> Allowing indeterminate values makes possible some significant optimizations
> that are not otherwise possible; having ways of "solidifying" such values
> makes it possible for programmers to actually *let* compilers make such
> optimizations in useful code paths. You're correct that Unspecified Value
> is safer than Indeterminate Value, and IMHO compilers should have options to
> automatically convert Unspecified Values to Indeterminate Values, but as
> with aliasing what's really necessary to make code safe isn't a sledge-
> hammer to stomp out all optimizations, but rather well-defined means of
> precisely specifying semantics at those few places in the code where it
> actually matters.
>

I am not looking to stomp out all optimizations. I am looking to stomp
out the crazy belief that vagueness in specifications justifies
creating optimization techniques that amplify minor, hypothetical, uses
of corner cases into gigantic failures.

Real optimization techniques behave *as if* they work on the result of
a naive unoptimized translation to the final machine code, with all its
known ways of handling cases not covered by the language standard.
Where more than one naive unoptimized translation is possible (e.g.
different ordering of operations), the optimizer is free to choose one
or the other for the optimized code to act *as if*. None of this of
cause precludes actually using a more complex internal representation
such as a tree or graph of abstracted operations, as long as it is
understood that this is a *technique* not a *definition* of what the
optimizer is allowed to do.

> Many programs may be viewed as having a separate "data path" and "control
> path", with most calculations being on the data path. Often some parts of
> the data will be merged into the control path (e.g. many file formats
> include information about the file size), and it's very important to
> tightly guard all the places where that happens, but in many cases
> guarding those will suffice to meet application requirements. If someone
> feeds a corrupt graphics file into a program, it may be acceptable to have
> it yield an arbitrary pattern of pixel data as output provided that it does
> not expose any security vulnerabilities. Letting Indeterminate Values
> into the control path would risk such vulnerabilities, but it should be
> possible for a programmer to safely ignore errant calculations which are
> confined to the data path.
>

One problem here is that data that is not coming from an untrusted
source (such as data generated internally by calculations) should not
need to be checked for maliciousness before entering the control path.

For example the loop control variable in a loop transitions between the
data and control plane on each iteration and it would be a nightmare if
programmers should now be required to operate under the assumption that
the compiler/machine might maliciously manipulate it (as happened in
that infamous GCC bug).

Another problem is that misbehavior entirely in the data path can still
be disastrous, for example if an incorrect output causes (or induces
depending if there is a human element) an incorrect real world action.

[supe...@casperkitty.com]

On Thursday, December 10, 2015 at 8:03:03 AM UTC-6, Jakob Bohm wrote:
> Skilled C programmers are almost by definition low level programmers,
> who usually know the exact behavior of their hardware when faced with
> numeric overflow (on most hardware it wraps within the signed int
> encoding). It is *normal* for C programs to actively use the resulting
> wrapped values. To most people outside the C committee, signed
> overflow is implementation defined, not undefined, and in the absence of
> a different definition in the compiler manual, the definition in the
> CPU manual is used.

C is really two very different languages; the amount of overlap between them
has been decreasing over the years, since jobs which used to fall within
areas of overlap are nowadays better handled using other languages. For some
reason, users of each language are totally oblivious to the existence of the
other.

The C language which is used by members of the committee is a language for
high-performance computing, and its users neither know nor care about low-
level CPU details. Requiring that program behavior follow the rules of a
particular CPU--even the one on which code is actually running(!)--would
impair many useful optimizations and could in some cases cause a 100%
slowdown. K&R never intended their language to be used for such purposes,
but some people figured that adapting C for such purposes would yield a
language which could serve such purposes better than than existing ones.

I personally think the language could be made even more suitable for such
purposes by recognizing that rather than trying to have one form of
semantics which are suitable for 99% of usage cases and simply putting up
with the fact that 1% of usage cases cannot be reasonably accommodated,
it would be much more useful to come up with looser semantics which are
directly suitable for 95% of usage cases, and add directives that can allow
the other 5% to be handled.

> In digital signal processing, standard algorithms are commonly designed
> to respond in well specified and controlled way to integer overflow
> handling in normal CPUs, and to contain the resulting noise in the
> output signal. Compiling such algorithms with a crazy compiler like
> that version of GCC would break horribly.

The authors of GCC inhabit a totally different universe from low-level
programmers. Their vision of C is suitable for their purposes (though IMHO
not as much so as it could be), but totally unsuitable for low-level
programming; managed platforms like Java and C# have taken over everything
that doesn't need the top performance only C can provide, and doesn't need
the low-level access only C can provide.

[Keith Thompson]

Jakob Bohm <jb-u...@wisemo.com> writes:
[...]

> Skilled C programmers are almost by definition low level programmers,
> who usually know the exact behavior of their hardware when faced with
> numeric overflow (on most hardware it wraps within the signed int
> encoding). It is *normal* for C programs to actively use the resulting
> wrapped values. To most people outside the C committee, signed
> overflow is implementation defined, not undefined, and in the absence of
> a different definition in the compiler manual, the definition in the
> CPU manual is used.

I disagree. I like to think of myself as a skilled C programmer.
Having read the standard, I'm aware that unsigned "overflow" wraps
around, and signed overflow is undefined. The only reason I'd use the
result of an overflowing is to diagnose the bug in the code that
permitted the overflow to happen.

I don't think I even have copies of the CPU manuals for the several
targets I use.

If you want signed integer overflow to be well defined, you want some
language other than C.

[James Kuyper]

On 12/10/2015 08:14 AM, martin...@yahoo.co.uk wrote:
...

> My favourite example is where GCC turned what looked like valid code
> to fill a table into an infinite loop which overwrote all memory:
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=33498

It doesn't look like valid code to me - it looks like code that can
produce signed integer overflow, depending upon the value of INT_MAX;
and the case where it actually caused a problem was one where INT_MAX
was small enough to trigger the defect.

[Keith Thompson]

Keith Thompson <ks...@mib.org> writes:
> Kaz Kylheku <k...@kylheku.com> writes:
> [...]
>> The proper, responsible way to have this optimization is to issue a
>> diagnostic: "You have undefined behavior here if x < 24, so I'm making
>> the assumption that x >= 24 and optimizing accordingly".
>>
>> Merely by not informing me of this important fact which it knows;
>> it violates the quantity maxim: its utterance is not adequately
>> informative.
>
> I recently read an article by the authors of llvm/clang explaining
> that issuing such diagnostics is actually extremely difficult.
> I think I posted the link here, or in comp.lang.c, but I haven't
> found it. I'll try to find it and post it later.

I found it:

http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_21.html

I previously posted the URL two months ago in the "definition of
implementation-defined behavior" thread, Message-Id
<lnzixjl...@kst-u.example.com>.

An excerpt:

Why can't you warn when optimizing based on undefined behavior?


People often ask why the compiler doesn't produce warnings
when it is taking advantage of undefined behavior to do an
optimization, since any such case might actually be a bug in
the user code. The challenges with this approach are that it
is 1) likely to generate far too many warnings to be useful -
because these optimizations kick in all the time when there is
no bug, 2) it is really tricky to generate these warnings only
when people want them, and 3) we have no good way to express
(to the user) how a series of optimizations combined to expose
the opportunity being optimized. Lets take each of these in turn:
[...]

[supe...@casperkitty.com]

On Friday, December 11, 2015 at 1:41:27 PM UTC-6, Keith Thompson wrote:
> I found it:
>
> http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_21.html
>

> An excerpt:

> People often ask why the compiler doesn't produce warnings
> when it is taking advantage of undefined behavior to do an
> optimization, since any such case might actually be a bug in
> the user code.

I think a bigger issue, which that blog didn't call attention to, is simply
that if a class of optimization were performed rarely enough that an ability
to perform it would be suspicious, it wouldn't be useful enough to be worth
bothering with. One of the most useful forms of optimization is elimination
of needless code from an in-line function expansion; if a function is invoked
50 times, a piece of code within that function is only intended to be
relevant in three of them, and a compiler determines that it's irrelevant in
48, there's no way a compiler can warn that the code is useless (since it
it's relevant in two cases), nor is there any way for it to directly identify
whether its inferences line up with programmer expectation.

On the other hand, I would think that in cases where programmers care about
execution speed, I would think that adding directives to let them *say* what
things they do and don't care about would be much cleaner than assuming a
1:1 correspondence between the cases they care about and the ones that don't
invoke Undefined Behavior. Further, I would suggest that there are a lot of
cases where it would be useful to have a means of saying "I want the product
of two values x and y if it's representable, or else an Indeterminate Value",
along with a directive which, given an lvalue, would replace it with an
Unspecified Value if it holds Indeterminate Value, or else leave it alone,
and a guarantee that reading an Indeterminate Value for purposes of copying
it another storage location of the same type will have no effect beyond
writing an Indeterminate Value to the destination.

Historically, programmers could get by without such things on compilers where
overflow simply yielded some kind of (possibly-indeterminate) value, but
if overflow is used to infer that things can't happen, some other means will
become necessary. Unfortunately, trying to determine whether such a function
would be required to return a particular value would on most platforms be
more expensive than simply having code perform a multiply instruction and
ignore overflow.

[Francis Glassborow]

I think that much of what you are asking for are QoI issues. Yes we
would all to increase portability but this is far from cost free. I am
much happier with compiler specific extensions, warnings etc. because
good implementers know that what they are providing is supportable
within their implementation. Some facilities are much easier to provide
for some implementation strategies than they are for others. All you get
for having Standard requirements that are hard to implement on some
compilers is that those compilers stop attempting to meet the standard.

In addition some of what you are asking for can only be determined at
run time. For example the result of x * y overflowing can only be known
at run time so strategies for handling overflow are inherently runtime
and would impact all code.

There are two facilities that I would like to see:

1) An access to the overflow bit for systems where that is available
(together with a way that the compiler can be informed that it is
available so that it can warn if the programmer tries to use it on a
system where it is not available. We already have ways of dealing with
attempts to access a machine clock when none is available)

2) A way to determine how the implementation deals with integer overflow
(wrap, saturation or trap)

Francis

[supe...@casperkitty.com]

On Saturday, December 12, 2015 at 6:36:08 AM UTC-6, Francis Glassborow wrote:
> I think that much of what you are asking for are QoI issues. Yes we
> would all to increase portability but this is far from cost free. I am
> much happier with compiler specific extensions, warnings etc. because
> good implementers know that what they are providing is supportable
> within their implementation. Some facilities are much easier to provide
> for some implementation strategies than they are for others. All you get
> for having Standard requirements that are hard to implement on some
> compilers is that those compilers stop attempting to meet the standard.

What I want is not a mandate that all compilers support features, but merely
that means be specified via which programs can specify what features they
require, and compilers be obligated to, at their option, either support
features or refuse compilation of programs whose requirements they cannot
meet.

> In addition some of what you are asking for can only be determined at
> run time. For example the result of x * y overflowing can only be known
> at run time so strategies for handling overflow are inherently runtime
> and would impact all code.

If programs state their requirements statically, then compilers would have
three options:

1. Perform arithmetic in a manner which would always meet a certain
requirement, in which case a directive specifying that requirement could
be ignored.

2. Decline to provide support for the requirement, in which case the compiler
must refuse programs that specify it.

3. Vary behavior according to the presence of the directive.

A lot of requirements are *already* satisfied by many existing compilers,
at least when used with certain command-line options, and even in cases where
enabling such options imposes a significant run-time costs, that cost may
still be below the cost of anything user code could do to meet the same
requirements.

> There are two facilities that I would like to see:
>
> 1) An access to the overflow bit for systems where that is available
> (together with a way that the compiler can be informed that it is
> available so that it can warn if the programmer tries to use it on a
> system where it is not available. We already have ways of dealing with
> attempts to access a machine clock when none is available)
>
> 2) A way to determine how the implementation deals with integer overflow
> (wrap, saturation or trap)

Rather than having access to the overflow bit, I'd rather have a means of
specifying that a compiler which accepts a program must notify a program if
an overflow within a block of code (not counting nested subroutines!) may
have caused the code to produce incorrect results. While errno is clunky,
it might work for the purpose, and it would provide a mechanism by which
a called subroutine (which was itself marked for overflow detection) could
relay that information back to the caller.

A key point with the way I would define the semantics would be that a
loop to e.g. produce a 32-bit total of a bunch of 32-bit numbers would be
free to arbitrarily report overflow or not in cases where the mathematical
total of all the numbers was representable as a 32-bit integer but some of
the partial sums were not. This would give compilers the freedom to either
check overflow with every computation, or use larger numeric types that
wouldn't overflow and check whether the result was in range. Further, if
some callers don't use all the computations performed by a function, a
compiler would not be obligated to keep the overflow checking associated
with functions whose results weren't going to be used anyway.

Because most programs need overflow checking with some calculations and not
others, I'd like to see separate numeric types for different behaviors.
Such a thing might have been too expensive in 1975, but this isn't 1975
anymore.

[Jakob Bohm]

The code in question would reliably init an array of 256 bytes with the
byte sequence 0x00..0xFF (reordered if machine is not strictly little
endian) provided the following is true:

1. int is 32 bits (program may check this by compiling different code
otherwise via ifdef or different source files).

2. int overflow beyond int-max produces the same bit patterns as
unsigned int non-overflow (true on most platforms, again the program
can provide different code for platforms with different int type
implementations.

3. The compiler does not regard the final step from 0xFFFEFDFC to
0x03020100 as relevant since its value will not be used.

4. The compiler does not participate in the malpractice of "undefined
by C standard==permission to optimize away"

Issues #1 and #2 could have been avoided by declaring the vars unsigned
int or even uint32_t.

Issue #3 is relevant only if the compiler has opinions on numeric
overflow.

Issue #4 is the kicker and the reason why the person closing this bug
should not be allowed to make compilers.

[supe...@casperkitty.com]

On Monday, December 14, 2015 at 10:25:26 AM UTC-6, Jakob Bohm wrote:
> Issue #4 is the kicker and the reason why the person closing this bug
> should not be allowed to make compilers.

IMHO, C would greatly benefit from having defined means for programs to specify
their requirements for integer overflow, with a proviso that a standards-
conforming compiler will be free to reject any program which specified any
requirements beyond the standard, but will be required to produce code which
met the requirements of any program it does not reject; IMHO, there should be
ways of specifying such requirements for variables of both signed types and
unsigned types.

There are times when even weak guarantees about numeric overflow can be
very useful [e.g. even if overflow yields Indeterminate Value, and any
tests on things of Indeterminate Value yield Undefined Behavior rather
than just unspecified results, being able to ignore overflow in
computations whose results will end up being *totally ignored* may allow
code to be cleaner and more efficient than otherwise possible].

Further, allowing programmers to request stronger guarantees may enable
optimizations which could not be achieved any other way. For example, if
code could require that any overflow which might cause a program to
generate numerically-incorrect results occurs between two accesses to
"errno" must set it to __STDC_OVERFLOW_ERRNO, and there was a lot of code
between two such accesses, a compiler could use whatever mixture of
extended-precision math and overflow checking would yield best performance;
a compiler could also omit overflow checking for any expression whose result
would end up being ignored--something it can't do if overflow checking is
done in user code.

BTW, one semantic requirement I'd allow programs to specify would be that
overflows of variables not directly involved in "for" loop execution may
allow loops to exit *early* but not allow extra iterations. There are many
cases where the computations performed by a loop would be meaningless if
overflow occurs, but shouldn't disrupt other operations. Having loops
performing such computations exit early would often be, if anything, a
slight benefit, but having them run extra iterations would be far more
dangerous.

[James Kuyper]

On 12/14/2015 11:25 AM, Jakob Bohm wrote:
> On 11/12/2015 19:32, James Kuyper wrote:
>> On 12/10/2015 08:14 AM, martin...@yahoo.co.uk wrote:
>> ...
>>> My favourite example is where GCC turned what looked like valid code
>>> to fill a table into an infinite loop which overwrote all memory:
>>> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=33498
>>
>> It doesn't look like valid code to me - it looks like code that can
>> produce signed integer overflow, depending upon the value of INT_MAX;
>> and the case where it actually caused a problem was one where INT_MAX
>> was small enough to trigger the defect.
>>
>
> The code in question would reliably init an array of 256 bytes with the
> byte sequence 0x00..0xFF (reordered if machine is not strictly little
> endian) provided the following is true:

...

> 2. int overflow beyond int-max produces the same bit patterns as
> unsigned int non-overflow (true on most platforms, again the program
> can provide different code for platforms with different int type
> implementations.

That's not guaranteed by the standard, so this should only be done in
code intended to be non-portable, and even then, such code should be at
least commented to indicated the dependence. Preferably, it should be
rewritten to use an unsigned type for which the desired behavior is
guaranteed by the standard.

Eric Dumazet wrote "This code is valid. Integer overflows of a counter
may happen in any program.", so it's quite clear that he wrote the
defective code due to ignorance of the rule he was violating, and not
because he knew the rule and thought that it shouldn't be a problem in
this particular case. He would not have inserted the comment, because he
was unaware of the issue that the comment should have highlighted. He
didn't choose the safer alternative because he was unaware of the danger.

> 4. The compiler does not participate in the malpractice of "undefined
> by C standard==permission to optimize away"

An implementation which detects the fact that code has undefined
behavior should always warn about that fact, in addition to any
optimizations it makes to take advantage of that fact - not because it's
required to do so, but merely as a matter of QoI. However, it's entirely
possible to write the safety checks for a optimization in such a way as
to guarantee that it never gets used in a context where it would break
code with defined behavior, without positively determining whether or
not the behavior is actually defined. That's because they're testing
something that is only indirectly linked to the definedness of the
behavior. I would not consider that malpractice (I'm not sure whether
that applies in this case).

Undefined behavior is generally labeled as such by the standard
precisely because it cannot be guaranteed to be reliably detectable in
all contexts on all platforms - if it could, it would be a constraint
violation, not just undefined behavior. Identifying the fact that code
has undefined behavior is the programmer's responsibility, not the
implementation's.

[Jakob Bohm]

I wrote that to highlight an assumption made by the author. An
assumption which used to be true in the vast majority of
implementations on two's complement hardware.

> Eric Dumazet wrote "This code is valid. Integer overflows of a counter
> may happen in any program.", so it's quite clear that he wrote the
> defective code due to ignorance of the rule he was violating, and not
> because he knew the rule and thought that it shouldn't be a problem in
> this particular case. He would not have inserted the comment, because he
> was unaware of the issue that the comment should have highlighted. He
> didn't choose the safer alternative because he was unaware of the danger.
>

Precisely. This highlights the fact that the C language as understood
outside the compiler-writing / standards-editing community is believed
to provide this guarantee on any hardware not specifically designed not
to do so easily (such as 1's complement hardware and/or saturation
clipping hardware).

>> 4. The compiler does not participate in the malpractice of "undefined
>> by C standard==permission to optimize away"
>
> An implementation which detects the fact that code has undefined
> behavior should always warn about that fact, in addition to any
> optimizations it makes to take advantage of that fact - not because it's
> required to do so, but merely as a matter of QoI. However, it's entirely
> possible to write the safety checks for a optimization in such a way as
> to guarantee that it never gets used in a context where it would break
> code with defined behavior, without positively determining whether or
> not the behavior is actually defined. That's because they're testing
> something that is only indirectly linked to the definedness of the
> behavior. I would not consider that malpractice (I'm not sure whether
> that applies in this case).

Not much. One part of the compiler changed the loop condition to use a
variable other than the loop control variable, and in doing so
correctly calculated the new test value based on the same wraparound
assumption made by the code author. Then another part of the compiler
used the "wrap around is not defined in the standard so is allowed to
do crazy things" interpretation to change the (compiler generated) new
loop end condition into an infinite loop.

No direct side effect of the overflow could have caused such looping
(other than hypothetically jumping to a random code address and/or
arbitrarily changing unrelated variables).

Any interpretation which would require the output to be "as-if" each
statement and each expression was executed separately within its
separately permitted semantics would not have created this bad result.

>
> Undefined behavior is generally labeled as such by the standard
> precisely because it cannot be guaranteed to be reliably detectable in
> all contexts on all platforms - if it could, it would be a constraint
> violation, not just undefined behavior. Identifying the fact that code
> has undefined behavior is the programmer's responsibility, not the
> implementation's.
>

But it seems to have done so in many cases that should have been
labeled as "implementation defined, possibly with implementation
defined variations in outcome", or some other notion less extreme than
"the implementation is allowed to cause infinite damage to the computer
and to any real world objects it can harm, including people and
property".

For example, the standard could have said that signed integer overflow
not resulting from the division (/) operator shall have one of the
following effects (and which one shall be implementation defined, hence
documented):

- The program is terminated with an error indication.
- A signal() handler is invoked (it is implementation defined which
one).
- An implementation defined error handling mechanism shall be invoked
(such as an implementation provided non-standard exception mechanism).
- The result shall be INT_MAX or INT_MIN according to the direction of
overflow.
- The result shall wrap around modulo (INT_MAX - INT_MIN + 1).
- The result shall wrap around modulo (INT_MAX - INT_MIN).
- The result shall wrap around modulo INT_MAX or -INT_MIN but retain
its sign.
- Some other implementation defined but valid integer value shall
result.
- Where the above refers to INT_MAX or INT_MIN, substitute the
equivalent constants for other signed integral types as applicable.

Signed integer overflow from using the "/" operator with a non-zero
divisor shall have either of those same results, but an implementation
may define that result differently (for example it may define it to
have the same result as division by 0).

I think every practical implementation should be trivially able to
provide at least one of these with no extra code for error checking and
the only new requirement being that the optimizer must now remain
consistent with the implementation-defined result rather than assuming
"undefined".

Similar can be done for most other cases currently declared "undefined".

In fact the only truly undefined case should be "calling a function
pointer whose value does not refer to any actual function in the
program" (This phrasing intentionally allows the set of actual
functions in the programs to vary during runtime, as is the case with
some system facilities in many implementations).

[Kaz Kylheku]

On 2015-12-14, James Kuyper <james...@verizon.net> wrote:
> On 12/14/2015 11:25 AM, Jakob Bohm wrote:
>> On 11/12/2015 19:32, James Kuyper wrote:
>>> On 12/10/2015 08:14 AM, martin...@yahoo.co.uk wrote:
>>> ...
>>>> My favourite example is where GCC turned what looked like valid code
>>>> to fill a table into an infinite loop which overwrote all memory:
>>>> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=33498
>>>
>>> It doesn't look like valid code to me - it looks like code that can
>>> produce signed integer overflow, depending upon the value of INT_MAX;
>>> and the case where it actually caused a problem was one where INT_MAX
>>> was small enough to trigger the defect.
>>>
>>
>> The code in question would reliably init an array of 256 bytes with the
>> byte sequence 0x00..0xFF (reordered if machine is not strictly little
>> endian) provided the following is true:
> ...
>> 2. int overflow beyond int-max produces the same bit patterns as
>> unsigned int non-overflow (true on most platforms, again the program
>> can provide different code for platforms with different int type
>> implementations.
>
> That's not guaranteed by the standard, so this should only be done in

It's not guaranteed by the standard because on some machines it can
trigger an overflow. If the behavior were defined in such a way that
it coincides with ignored overflow on a two's complement machine, then
compilers for other machines would have to emit grotty code in order
to conform.

An implementor who frowns on programs which depend on the hardware's
interpretation of integer overflow should provide a trap for it,
as a code generation option.

There is no excuse to just assume it doesn't happen, and then do some
optmizations accordingly.

Doing so precisely fits the term "malpractice" as used by Jakob Bohm.

Some code relies on overflow behavior as an extension. It is not
necessarily written in ignorance.

C compiler shave traditionally exposed the machine semantics to the
programmer. When C was standardized, then quite arbitrarily, some
of the nonportable machine aspects were turned into an "implementation
defined result" and others into "undefined behavior". This was probably
done by surveying the actual behavior: if some operation didn't actually
fail on most systems but the result differed, it became an
"implementation-defined result". Operations which failed on some machines
became "undefined behavior".

If you're writing code for a particular machine or class of machines,
you don't care whether some of the operations are "undefined behavior"
or whether they are "implementation-defined result".

This classification is only meaningful with regard to portability; what
the code does, currently or historically, on machines you *are not*
using.
On th emachine *you are* using, arithmetic is supposed to be more
or less according to the architecture manual.

/De facto/, incrementing an int beyond INT_MAX is a wide-spread
extension that has worked for decades on a large number of compilers.
Including GCC!

Quiz: what instruction does GCC use for adding two signed ints on 32 bit
MIPS? Answer: ADDU. Add Unsigned: the non-overflowing one. Not ADD,
the one which generates an overflow trap.

This is so that the expected wraparound occurs for code which expects
it. There is no added cost; if you use ADD, you get the overflow trap
for free. It doesn't take more cycles or make the program longer.

The compiler is deliberately avoiding the feature of having overflow
diagnosed by the hardware, which is precisely because it provides
the wraparound as an extension.

> Eric Dumazet wrote "This code is valid. Integer overflows of a counter
> may happen in any program.", so it's quite clear that he wrote the
> defective code due to ignorance of the rule he was violating, and not
> because he knew the rule and thought that it shouldn't be a problem in
> this particular case. He would not have inserted the comment, because he
> was unaware of the issue that the comment should have highlighted. He
> didn't choose the safer alternative because he was unaware of the danger.
>
>> 4. The compiler does not participate in the malpractice of "undefined
>> by C standard==permission to optimize away"
>
> An implementation which detects the fact that code has undefined
> behavior should always warn about that fact, in addition to any
> optimizations it makes to take advantage of that fact - not because it's
> required to do so, but merely as a matter of QoI. However, it's entirely
> possible to write the safety checks for a optimization in such a way as
> to guarantee that it never gets used in a context where it would break
> code with defined behavior, without positively determining whether or
> not the behavior is actually defined. That's because they're testing
> something that is only indirectly linked to the definedness of the
> behavior. I would not consider that malpractice (I'm not sure whether
> that applies in this case).

The indirect linkage in the faulty inference is the malpractice:

The optimization rests on the predicate that the programmer

- never makes mistakes that lead to undefined behavior

(nonsense: undefined behavior happens by accident, as well
as via the deliberate use of an extension, or possibly the mistaken
reliance on an extension which exists in one implementation
but not another)

- wraparound for signed number is not a wide-spread extension in C

(nonsense)

- wraparound for signed numbers has never been an extension in GCC

(sheer bullshit)

[Kaz Kylheku]

In essence, ISO C isn't all that defines the C language. The C language
is defined by the expectations encoded in the wild and wooly code bases
in the world.

You don't just mess around inside GCC like some coding cowboy! Someone's
going to take that GCC and compile an entire Linux distro (or whatever)
and your ignorant holier-than-though ISO C bullshit is causing bugs and
security holes to the generated machine code.

Even if some code is not defined according to ISO C, the responsible
party in the actual manifestation of a problem is the ignorant dickhead
who fucked with the compiler, thinking that the only thing that matters
in the world is that some ISO committee lacks an opinion about the
behavior of some construct (and therefore, what is left there is a
complete vacuum in which all that matter's is the cowboy's own opinion).

[supe...@casperkitty.com]

On Monday, December 14, 2015 at 1:59:42 PM UTC-6, Jakob Bohm wrote:
> For example, the standard could have said that signed integer overflow
> not resulting from the division (/) operator shall have one of the
> following effects (and which one shall be implementation defined, hence
> documented):
>
> - The program is terminated with an error indication.
> - A signal() handler is invoked (it is implementation defined which
> one).
> - An implementation defined error handling mechanism shall be invoked
> (such as an implementation provided non-standard exception mechanism).
> - The result shall be INT_MAX or INT_MIN according to the direction of
> overflow.
> - The result shall wrap around modulo (INT_MAX - INT_MIN + 1).
> - The result shall wrap around modulo (INT_MAX - INT_MIN).
> - The result shall wrap around modulo INT_MAX or -INT_MIN but retain
> its sign.
> - Some other implementation defined but valid integer value shall
> result.
> - Where the above refers to INT_MAX or INT_MIN, substitute the
> equivalent constants for other signed integral types as applicable.

I'd allow another possibility: implementations may indicate that overflow
may have arbitrary and unpredictable effects, in which case they would be
under no further obligation, but implementations which better characterize
their behavior would be regarded as being of higher quality. Such a rule
would make it possible to implement C even on hardware whose overflow
semantics were sufficiently broken that e.g. an overflow which occurred at
the exact moment an external interrupt arrived might cause the system to
jump to an incorrect interrupt vector, start to dispatch to the interrupt
vector before recognizing the overflow and then treat the overflow as
having happened during the interrupt, etc. It would also allow for the
possibility that an overflow might jump to an interrupt vector which is not
loaded by default (to allow for the possibility that the calling environment
might have set it to something useful).

> Similar can be done for most other cases currently declared "undefined".

I'd agree if one added a proviso that implementations may do anything they
provide a means by which applications which require more precise semantics
can refuse compilation.

> In fact the only truly undefined case should be "calling a function
> pointer whose value does not refer to any actual function in the
> program" (This phrasing intentionally allows the set of actual
> functions in the programs to vary during runtime, as is the case with
> some system facilities in many implementations).

Accessing memory which a program doesn't own should also qualify.

[supe...@casperkitty.com]

On Monday, December 14, 2015 at 1:12:39 PM UTC-6, James Kuyper wrote:
> Undefined behavior is generally labeled as such by the standard
> precisely because it cannot be guaranteed to be reliably detectable in
> all contexts on all platforms - if it could, it would be a constraint
> violation, not just undefined behavior. Identifying the fact that code
> has undefined behavior is the programmer's responsibility, not the
> implementation's.

The difference between Implementation-Defined Behavior and Undefined
Behavior is that the former requires that implementations document
precisely what will happen, while the latter does not. From what I can
tell, the determining factor for whether behaviors should be classified
as IDB or UB was generally whether implementations *might plausibly
exist* where the effects of the action would be essentially unpredictable;
the only exceptions I know of are actions whose consequences are
inherently system-specific; even though the effects of such actions may
not always be predictable, those are labeled as IDB rather than UB
because doing otherwise would imply that the Standard was defining
meaningless constructs; that philosophy does not seem to have extended
to #pragma directives, however, which are considered UB.

IMHO, C would be a much more useful language if most of the behaviors that
are classififed as UB had instead been classified as Optionally-Constrained
Behavior: quality implementations should describe the consequences of
certain actions to the extent practical; the documentation for a conforming
compiler must be *accurate* but need not be *precise*.

[supe...@casperkitty.com]

On Monday, December 14, 2015 at 2:14:09 PM UTC-6, Kaz Kylheku wrote:
> The optimization rests on the predicate that the programmer
>
> - never makes mistakes that lead to undefined behavior
>
> (nonsense: undefined behavior happens by accident, as well
> as via the deliberate use of an extension, or possibly the mistaken
> reliance on an extension which exists in one implementation
> but not another)

I'd word it slightly differently: it assumes that programs will never
receive input which would lead to Undefined Behavior. Users of the C
language fall into two increasingly-divergent camps: those who need to
do high-end computing on internally-generated data, and those who need
to do operations more akin to embedded or systems programming, and who
often need to process data received from untrustworthy sources. I
suspect most of the people in each camp are essentially blind to the
needs of people in the other, which is unfortunate because I think the
language could be made much more useful to people in both camps if it
allowed programmers to specify precise or loose semantics for things
like integer overflow.

[supe...@casperkitty.com]

On Monday, December 14, 2015 at 1:59:42 PM UTC-6, Jakob Bohm wrote:
> Precisely. This highlights the fact that the C language as understood
> outside the compiler-writing / standards-editing community is believed
> to provide this guarantee on any hardware not specifically designed not
> to do so easily (such as 1's complement hardware and/or saturation
> clipping hardware).

I would not regard an expectation that integer overflows always wrap as
normative; given something like:

long long muladd(int x, int y, long long z) { return x*y+z; }

there are many processors where it would be faster to compute
z+(long long)x*y than to compute z+(int)((long long)x*y) and I don't see
much benefit to forbidding compilers from computing the arithmetically-
correct result.

On the other hand, I think it is crazy that a piece of code like:

uint32_t pow_mod_2p32(uint32_t value, uint32_t exponent)
{
uint32_t result=1, subprod=value;
while(exponent)
{
if (exponent & 1)
result *= subprod;
exponent >>= 1;
subprod *= subprod;
}
}

may misbehave in arbitrary fashion on systems where "int" is 33 to 64 bits,
even though it would have the same defined behavior on all systems where
int is less than 33 or greater than 64 bits. Even if the Standard says
nothing about the upper-bit behavior if the product of two promoted
uint32_t values exceeds the range of "int", it should require that the
lower bits behave as they would with unsigned types.

[Jakob Bohm]

On 14/12/2015 23:06, supe...@casperkitty.com wrote:
> On Monday, December 14, 2015 at 1:59:42 PM UTC-6, Jakob Bohm wrote:
>> Precisely. This highlights the fact that the C language as understood
>> outside the compiler-writing / standards-editing community is believed
>> to provide this guarantee on any hardware not specifically designed not
>> to do so easily (such as 1's complement hardware and/or saturation
>> clipping hardware).
>
> I would not regard an expectation that integer overflows always wrap as
> normative; given something like:
>
> long long muladd(int x, int y, long long z) { return x*y+z; }
>
> there are many processors where it would be faster to compute
> z+(long long)x*y than to compute z+(int)((long long)x*y) and I don't see
> much benefit to forbidding compilers from computing the arithmetically-
> correct result.
>

Consistently and correctly applying the type promotion rules is already
a normative requirement. Allowing implementations to break that as an
optimization would be a bad idea and in this case would mask a bug that
would happen on any compiler not taking this specific shortcut.

> On the other hand, I think it is crazy that a piece of code like:
>
> uint32_t pow_mod_2p32(uint32_t value, uint32_t exponent)
> {
> uint32_t result=1, subprod=value;
> while(exponent)
> {
> if (exponent & 1)
> result *= subprod;
> exponent >>= 1;
> subprod *= subprod;
> }
> }
>
> may misbehave in arbitrary fashion on systems where "int" is 33 to 64 bits,
> even though it would have the same defined behavior on all systems where
> int is less than 33 or greater than 64 bits. Even if the Standard says
> nothing about the upper-bit behavior if the product of two promoted
> uint32_t values exceeds the range of "int", it should require that the
> lower bits behave as they would with unsigned types.
>

This is because that code relies on multiplication to wrap and/or
uncast assignment to a smaller unsigned type to wrap. It would be
potentially more portable to do the masking/modulo explicitly:
result = (uint32_t)((result * (uint64_t)subprod) & 0xFFFFFFFF);
subprod = (uint32_t)((subprod * (uint64_t)subprod) & 0xFFFFFFFF);
Then any decent optimizer should recognize and apply any machine
specific shortcuts for 32bit*32bit to 32bit multiplication with
overflow wrap.

(I don't know if there already is a normative requirement that unsigned
multiplication wraps and/or that assignment to a smaller unsigned type
wraps).

However this particular case could be equally well resolved (assuming
unsigned operations wrap) by making a special rule for unsigned values
implicitly promoted to a larger int value then assigned back to an
unsigned type smaller than int. Such a rule would also promote
optimizations by freeing implementations from the requirement to
formally operate on the larger int type in such cases.

A case in point where this rule would be generally better would be a
machine with 64 bit 1's complement integers (or 64 bit integers with
sign bit and 63 bit absvalue). Such machines cannot naturally make
signed values wrap modulo (1 << bitcount), but can wrap modulo ((1 <<
bitcount) - 1) or (1 << (bitcount - 1)) depending on the hardware (some
hardware may prefer to raise a signal or use saturation however).

I am unsure if this happens to describe some IBM machines and/or other
real hardware.

[Kaz Kylheku]

On 2015-12-14, supe...@casperkitty.com <supe...@casperkitty.com> wrote:
> On Monday, December 14, 2015 at 1:12:39 PM UTC-6, James Kuyper wrote:
>> Undefined behavior is generally labeled as such by the standard
>> precisely because it cannot be guaranteed to be reliably detectable in
>> all contexts on all platforms - if it could, it would be a constraint
>> violation, not just undefined behavior. Identifying the fact that code
>> has undefined behavior is the programmer's responsibility, not the
>> implementation's.
>
> The difference between Implementation-Defined Behavior and Undefined
> Behavior is that the former requires that implementations document
> precisely what will happen, while the latter does not.

Plus, the difference is largely for shit in the real world, because
implementations document things what happen for all kinds of undefined
behavior also: they are just doing that without it being required.

Moreover, their documentation isn't required to spell out which
description is there because it's required, and which is an extension;
you have to have your nose in the standard for that.

The documentation might also neglect to tell you that what is being
described is nonportable --- in both cases.

A C compiler could have defined left-to-right evaluation order and just
say that in its documentation without mentioning anything about other
compilers.

The difference between "unspecified", "undefined" and
"implementation-defined" has no practical value to the average coder,
who can safely ignore the standard and just follow the docs for the
implementations which are being targeted, and not care about anything
else.

> From what I can
> tell, the determining factor for whether behaviors should be classified
> as IDB or UB was generally whether implementations *might plausibly
> exist* where the effects of the action would be essentially unpredictable;

Mereover, this was at a partciular point in the history of C. These
decisions live on for years and decades, even though if their rationale
were re-evaluated today, the classification might be different.

Thirty years ago, something had to be "undefined behavior" because it
broke on some weird machines that were still in deployment.

Today, they are only in a museum; the construct actually works
"everywhere".

Maybe it's time to make it a "implementation-defined result",
or maybe even well-defined.

Basically it's just vendor politics. If you have clout in ISO and
something doesn't work in your system, you can throw your weight around
to have it "undefined" in everyone else's system where it fscking works.

[Jakob Bohm]

One thing with this point that you may miss is that there is a 3rd,
larger class of programs:

Programs that need to be portable to a majority of common machines and
which do high performance computing on bit patterns of various kinds,
such as compressed data and/or data transmissions. Such programs have
historically been able to be written in C with a build time tool
detecting if the target falls into one of a few classes of machines,
each with consistent semantics across all such machines.

Typical classes of machines considered by such software include:

- Machines with little endian two's complement integer representation
and available types for each of 8,16,32 and maybe 64 bit values.
- Machines with big endian two's complement integer representation
and available types for each of 8,16,32 and maybe 64 bit values.
- Machines with 32 bit int
- Machines with 64 bit int
- A few important "special case" machines such as IBM-360+ and PDP-11.

Such software rarely deals specifically with CPU specifications, it
simply tries to classify the abstract machines presented by C
implementations into common categories and then take advantage of the
common properties of those categories.

[martin...@yahoo.co.uk]

On Monday, 14 December 2015 17:25:26 UTC+1, Jakob Bohm wrote:
> > On 12/10/2015 08:14 AM, martin...@yahoo.co.uk wrote:
> > ...
> >> My favourite example is where GCC turned what looked like valid code
> >> to fill a table into an infinite loop which overwrote all memory:
> >> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=33498
>

> The code in question would reliably init an array of 256 bytes with the
> byte sequence 0x00..0xFF (reordered if machine is not strictly little
> endian) provided the following is true:
>

[snip]

>
> 4. The compiler does not participate in the malpractice of "undefined
> by C standard==permission to optimize away"
>
> Issues #1 and #2 could have been avoided by declaring the vars unsigned
> int or even uint32_t.
>
> Issue #3 is relevant only if the compiler has opinions on numeric
> overflow.
>
> Issue #4 is the kicker and the reason why the person closing this bug
> should not be allowed to make compilers.

So which C compiler(s) *do* you use? Clearly GCC will be unacceptable.

[Kaz Kylheku]

Exactly; idiots being at the helm of GCC development is a grave issue.

[supe...@casperkitty.com]

On Monday, December 14, 2015 at 4:43:06 PM UTC-6, Jakob Bohm wrote:

> On 14/12/2015 23:06, supercat wrote:
> > I would not regard an expectation that integer overflows always wrap as
> > normative; given something like:
> >
> > long long muladd(int x, int y, long long z) { return x*y+z; }
> >
> > there are many processors where it would be faster to compute
> > z+(long long)x*y than to compute z+(int)((long long)x*y) and I don't see
> > much benefit to forbidding compilers from computing the arithmetically-
> > correct result.
>
> Consistently and correctly applying the type promotion rules is already
> a normative requirement. Allowing implementations to break that as an
> optimization would be a bad idea and in this case would mask a bug that
> would happen on any compiler not taking this specific shortcut.

Signed integer overflow is Undefined Behavior. For an implementation to
return the arithmetically-correct result is well within the realm of
allowable behavior.

Personally I'd like to see C add parameterized integer types, so that one
could specify what behaviors one required with out-of-range values,
independent of signedness. While it's useful to have types that wrap, I
think wrapping should be specifiable independent of size and signedness.

> This is because that code relies on multiplication to wrap and/or
> uncast assignment to a smaller unsigned type to wrap. It would be
> potentially more portable to do the masking/modulo explicitly:
> result = (uint32_t)((result * (uint64_t)subprod) & 0xFFFFFFFF);
> subprod = (uint32_t)((subprod * (uint64_t)subprod) & 0xFFFFFFFF);
> Then any decent optimizer should recognize and apply any machine
> specific shortcuts for 32bit*32bit to 32bit multiplication with
> overflow wrap.

A lot of code written for 32-bit machines assumes that the assigning the
product of two uint32_t values to a uint32_t will perform the multiply
mod 2^32; that's what will happen on any machine where "int" is 32 bits
or smaller, or where "int" is 65 bits or larger.

> (I don't know if there already is a normative requirement that unsigned
> multiplication wraps and/or that assignment to a smaller unsigned type
> wraps).

There is a requirement with operations performed as unsigned. The wrinkle
is that unsigned types whose values are all representable as "int" may get
promoted to "int" before the multiply, even if the results would not all
be representable as "int".

> However this particular case could be equally well resolved (assuming
> unsigned operations wrap) by making a special rule for unsigned values
> implicitly promoted to a larger int value then assigned back to an
> unsigned type smaller than int. Such a rule would also promote
> optimizations by freeing implementations from the requirement to
> formally operate on the larger int type in such cases.

IMHO there should be such a rule. I think the main reason there isn't is
that compilers have historically done the right thing, even if by accident,
in its absence.

[supe...@casperkitty.com]

On Monday, December 14, 2015 at 4:56:37 PM UTC-6, Jakob Bohm wrote:

> On 10/12/2015 15:24, supercat wrote:

> > C is really two very different languages; the amount of overlap between them
> > has been decreasing over the years, since jobs which used to fall within
> > areas of overlap are nowadays better handled using other languages. For some
> > reason, users of each language are totally oblivious to the existence of the
> > other.
> >
> > The C language which is used by members of the committee is a language for
> > high-performance computing, and its users neither know nor care about low-
> > level CPU details. Requiring that program behavior follow the rules of a
> > particular CPU--even the one on which code is actually running(!)--would
> > impair many useful optimizations and could in some cases cause a 100%
> > slowdown. K&R never intended their language to be used for such purposes,
> > but some people figured that adapting C for such purposes would yield a
> > language which could serve such purposes better than than existing ones.
> >
> > I personally think the language could be made even more suitable for such
> > purposes by recognizing that rather than trying to have one form of
> > semantics which are suitable for 99% of usage cases and simply putting up
> > with the fact that 1% of usage cases cannot be reasonably accommodated,
> > it would be much more useful to come up with looser semantics which are
> > directly suitable for 95% of usage cases, and add directives that can allow
> > the other 5% to be handled.
> >
>
> One thing with this point that you may miss is that there is a 3rd,
> larger class of programs:

I should have said that it has diverged into two distinct languages, and
should also have used the term "low-level" rather than "embedded/systems".
I am well aware of the class of programs you described, and historically
I'd say that was the dominant role for C, but modern architectures, to an
increasing degree, require that compilers perform some rather intricate
transforms on code to yield maximum performance. This creates a split,
then, between a language which is expected to perform operations in the
manner stated, with the semantics resulting therefrom, and a language
where the compiler is allowed to transform code in any fashion which is
consistent with standard-defined behaviors, even if such transform
changes behaviors in the corner cases not defined by the Standard.
I don't think a lot of C programmers appreciate the importance of such
transforms or the extent to which maintaining the normal C guarantees
would impair optimization for modern hardware.

I would really like to see the C Standard acknowledge normative behaviors
of the type you describe and provide ways by which programmers can indicate
when they are and are not required. I would posit that in 95% of the
places where optimizers would be inclined to perform certain optimizations
they would allow a great improvement in speed without adversely affecting
correctness. I would further posit that giving programmers more abilities
to indicate when optimizations must not be performed would allow compilers
more opportunities at optimization.

For example, given:

void hey(float *fp, int *ip)
{
for (int i=0; i<100; i++)
fp[i] = someFloatCalculation();
for (int i=0; i<100; i++)
ip[i] = someIntCalculation();
}

If either fp or ip is known to point to something of static or automatic
duration, a compiler could interleave the operations on *fp and *ip. If
they are not known to do so, a compiler can't. Some people think that
compilers should be able to perform that transformation regardless of
what fp and ip might point to, and 90% of the time they'd be right. If
there was a directive that a program could use to specify that things
might alias despite their types, that would both facilitate the kinds
of low-level code that rely upon aliasing, and also mean that (provided
that code indicated that it wasn't relying upon older semantics) there
would be less need for compilers to refrain from useful optimizations
for fear that code might expect ordered behavior.

[Kaz Kylheku]

On 2015-12-15, supe...@casperkitty.com <supe...@casperkitty.com> wrote:
> For example, given:
>
> void hey(float *fp, int *ip)
> {
> for (int i=0; i<100; i++)
> fp[i] = someFloatCalculation();
> for (int i=0; i<100; i++)
> ip[i] = someIntCalculation();
> }
>
> If either fp or ip is known to point to something of static or automatic
> duration, a compiler could interleave the operations on *fp and *ip. If

To be able to scramble the order in which the arrays are assigned and/or
the order in which the functions are called, the compiler has to be sure
of facts like that the functions don't have any side effects, and the
functions cannot inspect the values in the array, nor modify them.

The storage duration of the arrays is not relevant.

For all the possible C storage durations, we can complete the program
around "hey" with the arrays being of that duration, such that the
behavior will change if the loop is rearranged, and we can complete it
such that the behavior will not change if the loop is rearranged.

> what fp and ip might point to, and 90% of the time they'd be right. If
> there was a directive that a program could use to specify that things
> might alias despite their types

volatile float *fp, volatile int *ip

If your compiler has a properly working volatile, the assignments
to the array elements have to actually happen, and in the order in
which they appear to happen.

If you want to optimize in the face of aliasing between unlike types,
what you can do is write that part of the code in assembly language,
and keep the slow C version for reference. (Noting in the documentation
or comments that aliasing ints and floats is not well-defined according
to ISO C, but that the volatile at least makes the translation obey the
programmer's intent on such and such compilers.)

[Jakob Bohm]

Just noting that rewriting in assembler for umpteen different
architectures is not an alternative to making high level compilers do
the right thing in terms of assigning semantics to otherwise portable
source code, which is why we are having these discussions.

Also noting that I am sorry that my original, very narrowly scoped
question thread has been hijacked by other interesting issues in the
standard and its interpretation.

[supe...@casperkitty.com]

On Tuesday, December 15, 2015 at 1:26:05 PM UTC-6, Kaz Kylheku wrote:
> The storage duration of the arrays is not relevant.

Storage locations of static or automatic duration represent named objects
whose effective type cannot change. Any code which attempts to read or
write such a storage location using an lvalue of a contrary type invokes
Undefined Behavior. Thus, if at least one of the pointers is known to
identify something of static or automatic duration and the other pointer
is of a contrary type, a compiler may assume that accesses made using the
sets of objects accessed using each pointer will be disjoint, since
otherwise code would have had to access a named object with something of
a contrary type, thus invoking Undefined Behavior.

If the storage locations identify heap storage, then it is permissible (to
the chagrin of some) to write a given location as one type and later write
it as another, provided that no location is read using anything type that
is not compatible with the type last used to write it. The fact that
behavior would be defined if the pointers identify overlapping regions of
allocated storage thus limits optimizations compared with the scenario
where at least one pointer was known to identify a named object.

> For all the possible C storage durations, we can complete the program
> around "hey" with the arrays being of that duration, such that the
> behavior will change if the loop is rearranged, and we can complete it
> such that the behavior will not change if the loop is rearranged.

If either of the arguments to hey is a named object the other will not
be able to alias it without invoking Undefined Behavior, and in that
scenario any kind of rearrangement would be legitimate regardless of the
behavioral consequences.

> If your compiler has a properly working volatile, the assignments
> to the array elements have to actually happen, and in the order in
> which they appear to happen.

It might make sense for the Standard to require compilers allow variable-
qualified lvalues to process reads or writes of any type in terms of the
underlying storage, but nothing in the Standard actually says that. Even
for single-threaded code, it would be helpful to be able to request two
forms of semantics:

1. Volatile-qualified accesses are sequenced with respect to other
such accesses, but unsequenced with regard to non-qualified
accesses.

2. Some particular access is sequenced with respect to all other
accesses to anything other than restrict-qualified pointers.

In some cases, strictly sequencing volatile accesses with respect to all
other accesses could be needlessly expensive, but on many systems there
will be many times when loose sequencing is acceptable but a few times
where rigid sequencing is required.

> If you want to optimize in the face of aliasing between unlike types,
> what you can do is write that part of the code in assembly language,
> and keep the slow C version for reference. (Noting in the documentation
> or comments that aliasing ints and floats is not well-defined according
> to ISO C, but that the volatile at least makes the translation obey the
> programmer's intent on such and such compilers.)

I have a better idea: how about replacing most uses of assembly language
with a language which uses memory accesses rather than register transfers
as its primary abstraction level, allows slightly higher-level constructs
than assembly language, and can replace assembly language for things that
don't need register-level control. I think a couple guys came up with
such a language in the 1970s as a successor to BCPL and B; I think it's
call "C" or something like that.

[martin...@yahoo.co.uk]

I really am interested to know which compilers you use.

[Jakob Bohm]

Whatever the platform dictates. Which in a few unfortunate cases is
some specific version of GCC.

[Tim Rentsch]

Jakob Bohm <jb-u...@wisemo.com> writes:

> On 09/12/2015 18:59, Tim Rentsch wrote:
>> Jakob Bohm <jb-u...@wisemo.com> writes:
>>
>>> On 09/12/2015 02:06, supe...@casperkitty.com wrote:
>>>> On Tuesday, December 8, 2015 at 4:50:58 PM UTC-6, Jakob Bohm wrote:
>>>
>>> [...]
>>>
>>>>> Also a standard version of the common msize() function (it has a
>>>>> longer name in GNU libc) would also be nice.
>>>>
>>>> On some platforms it would be hard to guarantee anything useful
>>>> about the semantics; a solution to that would be to have a
>>>> return value that means "who knows"?
>>>
>>> Any platform where free() is not a NOP should be able to look at
>>> what free() would do if presented with that same pointer and
>>> conclude a size from that. If the heap code was optimized for the
>>> absence of an msize() function, implementing an msize() function
>>> might involve a costly search of the data that malloc() would use
>>> to determine if there is a malloc-consumable memory address before
>>> the free-extending to address that free() would calculate if
>>> freeing the pointer being queried.
>>>
>>> But I fail to see how, in practical terms, one could implement
>>> malloc() and free() without holding enough data to implement
>>> msize().
>>
>> I think you are making assumptions about how these would be
>> implemented that may not hold in general. In effect you want to
>> ask about how much adjacent unallocated space there is. Note
>> however a significant difference with respect to free(). During
>> a call to free(), normally we expect it can discover how much
>> adjacent unallocated space there is, at the moment of the free()
>> call. But what msize() does isn't that; for msize() to be
>> useful, it has to know how much adjacent unallocated space there
>> is /that also will not be allocated in the future/. This extra
>> requirement imposes additional constraints on how malloc() and
>> free() may be implemented. Those constraints may be overly
>> limiting, or they may not be, but I don't think they can be
>> dismissed out of hand.
>
> That is why I framed it as "malloc-consumable memory" not
> "unallocated memory". Regardless of how it is implemented, malloc()
> must know how not to overwrite the memory that was returned by previous
> malloc() and not yet passed to free(). While free() must know not to
> release memory belonging to the nearest higher address returned by a
> different call to malloc(); [...]

Re-reading your comments, I'm not sure whether you are implicitly
assuming the point I mentioned before, or if you already conceded
the point that msize() does have implications for how malloc() and
friends can be implemented. In any case msize() is a bad idea,
even if it happens to be easy to define in many or most existing
schemes for doing malloc()/free().

[Jakob Bohm]

I was arguing that it would be (near) impossible to create a conforming
malloc() implementation for which a working (though not necessarily
fast) msize() cannot be implemented without changing the malloc/free
implementation code.

I was also arguing that a suitably defined msize() is a very useful and
good idea, which has been repeatedly added as a vendor extension.

But this malloc/msize discussion really should have its own thread.

[supe...@casperkitty.com]

On Thursday, January 28, 2016 at 6:42:25 PM UTC-6, Jakob Bohm wrote:
> I was arguing that it would be (near) impossible to create a conforming
> malloc() implementation for which a working (though not necessarily
> fast) msize() cannot be implemented without changing the malloc/free
> implementation code.

Depending upon how msize is defined, it may be possible for every possible
malloc implementation to implement it, though the usefulness of such
implementations could vary.

Consider, for example, the following definition:

size_t msize(void *p)

When given either a pointer returned from a malloc-family routine or a
null pointer, returns any value x such that for every value y in the
range 0 to x-1, ((char*)p)[y] will identify valid storage owned by p.

Note that the return value may be arbitrarily larger or smaller than the
size of the allocation that had been requested, provided that it is no
larger than the size of the allocation which has been granted.

The function must return zero if passed a null argument. Passing any
non-null pointer other than a valid one returned by a malloc-family
routine will invoke Undefined Behavior.

A typical usage could be:

void expand_if_needed(size_t new_size)
{
if (msize(my_thing) < new_size)
{
... prepare to realloc
void *temp = realloc(my_thing, new_size);
if (temp)
... update pointers for new allocation
else
... handle failure
}
}

Note that any malloc() implementation could define a conforming msize() as

size_t msize(void *p) { return 0; }

and that the sample usage code would work without having to handle the
inability of msize() to return more useful information. On implementations
where malloc() often allocated more storage than requested, however, the
msize() function may allow better performance than would be available even
from a malloc wrappers which kept track of the requested size.

[Jakob Bohm]

On 29/01/2016 20:42, supe...@casperkitty.com wrote:
> On Thursday, January 28, 2016 at 6:42:25 PM UTC-6, Jakob Bohm wrote:
>> I was arguing that it would be (near) impossible to create a conforming
>> malloc() implementation for which a working (though not necessarily
>> fast) msize() cannot be implemented without changing the malloc/free
>> implementation code.
>

As I said, this really belongs in its own thread.

That definition is too weak as your dummy implementation shows.

Here is an msize() definition I had in mind:

size_t msize(const void *p);

When given a pointer returned from a malloc-family function and not
yet freed with such a function, this returns a value x having the
following properties:
It is >= the allocation size passed to the allocation function.
It will not change until p is passed to a malloc-family function
For every value y in the range 0 to x-1, ((char*)p)[y] is a valid
rvalue.
When passing p to realloc(), data up to the smaller of offset
x and the size passed to realloc() will be preserved if
successful and data up to offset x will be preserved if
unsuccessful.
In general, the value x can be used as if that was the size
passed to the allocation function.

When passed a null pointer, msize() returns 0 if calling free() on
a null pointer is defined to do nothing (this property of free()
may be implementation defined under some variants of the
standard).

In all other cases, the effect of calling msize() may return
arbitrary values or raise the SIGBUS signal or terminate
the program.


The argument from last year that you snipped was about the near
impossibility of making a conforming implementation of the existing
malloc-family functions without maintaining enough state to allow
implementing this form of the msize() function.

A very slow hypothetical implementation could do this:

1. Simulate a call to realloc((void*)p, LARGE_NUMBER) where
LARGE_NUMBER is large enough to make the implementation return
a non-NULL pointer different from p, and note the amount of
memory copied from p to the new location. None of the side
effects of the realloc() call are allowed to actually occur, even
in a multithreaded program.

2. Simulate a call to free((void*)p) and note the amount of memory
added to the internal pool of memory that future calls to
malloc() may reuse. None of the side effects of the free() call
are allowed to actually occur, even in a multithreaded program.

3. Simulate every possible sequence of calls to malloc() and note
the closest higher address that malloc() might return or
overwrite. Note the amount of memory between p and that address.

4. The result is the lowest of the results from steps 1, 2 and 3.

Note that the only requirement of this hypothetical implementation is
that memory passed to free() can be returned by later calls to malloc().

In practice, the internal malloc state accessed during the hypothetical
slow implementation will usually provide a correct and usable result
much faster than that. This value may be different from what the slow
implementation would return, as long as it satisfies the msize()
definition.

[James Kuyper]

On 02/01/2016 02:19 PM, Jakob Bohm wrote:
...

> When passed a null pointer, msize() returns 0 if calling free() on
> a null pointer is defined to do nothing (this property of free()
> may be implementation defined under some variants of the
> standard).

C2011 says: "If ptr is a null pointer, no action occurs." (7.22.3.3p2)
As far as I know, no previous version of the standard has said anything
different about the matter. Are you aware of any such "variant"?

[Jakob Bohm]

I recall lots of older C89 code that wraps an explicit if() around
calls to free() just to avoid calling free(NULL). From that I assume
that at least some compilers didn't always do this, and that there must
thus have existed a standard/specification not requiring free() to
check for NULL before doing its thing.

The language I wrote was intended to cover any such specification, even
if never actually released as an ISO standard.

[James Kuyper]

On 02/01/2016 03:35 PM, Jakob Bohm wrote:
> On 01/02/2016 20:45, James Kuyper wrote:
>> On 02/01/2016 02:19 PM, Jakob Bohm wrote:
>> ...
>>> When passed a null pointer, msize() returns 0 if calling free() on
>>> a null pointer is defined to do nothing (this property of free()
>>> may be implementation defined under some variants of the
>>> standard).
>>
>> C2011 says: "If ptr is a null pointer, no action occurs." (7.22.3.3p2)
>> As far as I know, no previous version of the standard has said anything
>> different about the matter. Are you aware of any such "variant"?
>>
>>
>
> I recall lots of older C89 code that wraps an explicit if() around
> calls to free() just to avoid calling free(NULL). From that I assume
> that at least some compilers didn't always do this, and that there must
> thus have existed a standard/specification not requiring free() to
> check for NULL before doing its thing.

That's one possible explanation. Another is that the person writing the
code was unaware of the fact that free(NULL) was allowed, and equivalent
to a no-op. A third possibility was that they (rightly or wrongly)
expected it to save time: a pointer comparison takes a lot less time to
execute than a function call. The statement

if(p)
free(p);

saves time by not performing a function call if p is null, and wastes
time with a pointer comparison that must also be carried out inside
free() itself, if p is not null. Overall, that approach saves time if p
has a sufficiently high likelihood of being null at that point.
I frequently write code like the following to achieve a similar effect
at no extra cost:

p = malloc(n * sizeof *p);
if(p==NULL)
{
// Error handling
}
else
{
// Code that uses *p
free(p);
}

So free() only called if it needs to be called, yet I don't pay any
extra cost checking whether it needs to be called.

[Jakob Bohm]

On 01/02/2016 21:58, James Kuyper wrote:
> On 02/01/2016 03:35 PM, Jakob Bohm wrote:
>> On 01/02/2016 20:45, James Kuyper wrote:
>>> On 02/01/2016 02:19 PM, Jakob Bohm wrote:
>>> ...
>>>> When passed a null pointer, msize() returns 0 if calling free() on
>>>> a null pointer is defined to do nothing (this property of free()
>>>> may be implementation defined under some variants of the
>>>> standard).
>>>
>>> C2011 says: "If ptr is a null pointer, no action occurs." (7.22.3.3p2)
>>> As far as I know, no previous version of the standard has said anything
>>> different about the matter. Are you aware of any such "variant"?
>>>
>>>
>>
>> I recall lots of older C89 code that wraps an explicit if() around
>> calls to free() just to avoid calling free(NULL). From that I assume
>> that at least some compilers didn't always do this, and that there must
>> thus have existed a standard/specification not requiring free() to
>> check for NULL before doing its thing.
>

> <snipped guesswork>

The language I provided was just to cater to the possibility that such
alternative specifications might exist, not to actually sidetrack the
discussion.

[Randy Howard]

On 2/1/16 2:35 PM, Jakob Bohm wrote:
> I recall lots of older C89 code that wraps an explicit if() around
> calls to free() just to avoid calling free(NULL). From that I assume
> that at least some compilers didn't always do this, and that there must
> thus have existed a standard/specification not requiring free() to
> check for NULL before doing its thing.

Very true, and it's because some implementations (note I didn't say
anything about a standard) would segfault if you called free on a null
pointer. It's protection against bad implementations, not conformance
with any standard I'm aware of.

--
Randy Howard
(replace the obvious text in the obvious way if you wish to contact me
directly)

[Kaz Kylheku]

On 2016-02-01, Jakob Bohm <jb-u...@wisemo.com> wrote:
> On 01/02/2016 20:45, James Kuyper wrote:
>> On 02/01/2016 02:19 PM, Jakob Bohm wrote:
>> ...
>>> When passed a null pointer, msize() returns 0 if calling free() on
>>> a null pointer is defined to do nothing (this property of free()
>>> may be implementation defined under some variants of the
>>> standard).
>>
>> C2011 says: "If ptr is a null pointer, no action occurs." (7.22.3.3p2)
>> As far as I know, no previous version of the standard has said anything
>> different about the matter. Are you aware of any such "variant"?
>>
>>
>
> I recall lots of older C89 code that wraps an explicit if() around
> calls to free() just to avoid calling free(NULL).

You will also see it in some new code written in 2016 (to some
unspecified standard).

> From that I assume
> that at least some compilers didn't always do this, and that there must
> thus have existed a standard/specification not requiring free() to
> check for NULL before doing its thing.

Or the programmer didn't know and couldn't be bothered to look it up.
Many library functions do not accept NULL; the default assumption is that they
don't. For instance, fclose(NULL) isn't defined, though it easily and
usefully could be.

[Richard Damon]

On 2/1/16 3:35 PM, Jakob Bohm wrote:
> On 01/02/2016 20:45, James Kuyper wrote:
>> On 02/01/2016 02:19 PM, Jakob Bohm wrote:
>> ...
>>> When passed a null pointer, msize() returns 0 if calling free() on
>>> a null pointer is defined to do nothing (this property of free()
>>> may be implementation defined under some variants of the
>>> standard).
>>
>> C2011 says: "If ptr is a null pointer, no action occurs." (7.22.3.3p2)
>> As far as I know, no previous version of the standard has said anything
>> different about the matter. Are you aware of any such "variant"?
>>
>>
>
> I recall lots of older C89 code that wraps an explicit if() around
> calls to free() just to avoid calling free(NULL). From that I assume
> that at least some compilers didn't always do this, and that there must
> thus have existed a standard/specification not requiring free() to
> check for NULL before doing its thing.
>
> The language I wrote was intended to cover any such specification, even
> if never actually released as an ISO standard.
>
> Enjoy
>
> Jakob

My recollection is that the K&R 'Standard' didn't define the effect of
free(NULL), so the code is likely harking back to those days (or habits
harking back to them). I think the first C Standards body decided that
there was enough usefulness, and small enough cost, to require the free
function to make the NULL test, as it is about as close to free as could
be (test the point just before first use and return it 0, in assembly
code it just adds a test and conditional jump to the return code).

[supe...@casperkitty.com]

On Thursday, February 4, 2016 at 5:18:30 PM UTC-6, Richard Damon wrote:
> My recollection is that the K&R 'Standard' didn't define the effect of
> free(NULL), so the code is likely harking back to those days (or habits
> harking back to them). I think the first C Standards body decided that
> there was enough usefulness, and small enough cost, to require the free
> function to make the NULL test, as it is about as close to free as could
> be (test the point just before first use and return it 0, in assembly
> code it just adds a test and conditional jump to the return code).

It's too bad that standards bodies haven't taken a similar attitude with
some other corner cases, e.g. saying that the semantics of memcpy must
be equivalent to [with do_memcpy being a function that behaves as memcpy
does in all cases that are defined in C99]:

void *restrict memcpy(void * restrict dest, void const * restrict src,
size_t n)
{
if (!n) return dest;
if (src == dest)
return ARBITRARY_VALUE ? memmove(dest, dest, n) : dest;
return memcpy(dest, src, n);
}

There are many APIs which can accept optional data, and allow programmers
to indicate the lack of data by passing a null pointer and specifying a
length of zero. A memcpy which returned when the size is zero regardless
of the passed-in pointers would eliminate the need to special case that.

Further, some kinds of data-permutation code will perform a lot of swaps
which will usually exchange disjoint elements but may sometimes "swap" an
element with itself. If 99.9% of swaps are of disjoint elements, the time
required to test all swaps to skip the self-swaps might take more time
than would be required to perform the swaps blindly *if* the behavior of
using memcpy to copy a block to itself were defined as arbitrarily copying
the block to itself or skipping the copy. Given that using the same source
and destination to memcpy invokes Undefined Behavior, however, code may
have no choice but to test for the self-swap; unless the compiler can show
that the pointers cannot both be null, it cannot eliminate that test (if
code skips copy operations when source and destination match, skipping an
attempt to copy data from null to null would yield defined behavior, but
actually trying to copy the data would not).

[Keith Thompson]

Richard Damon <Ric...@Damon-Family.org> writes:
> On 2/1/16 3:35 PM, Jakob Bohm wrote:
>> On 01/02/2016 20:45, James Kuyper wrote:
>>> On 02/01/2016 02:19 PM, Jakob Bohm wrote:
>>> ...
>>>> When passed a null pointer, msize() returns 0 if calling free() on
>>>> a null pointer is defined to do nothing (this property of free()
>>>> may be implementation defined under some variants of the
>>>> standard).
>>>
>>> C2011 says: "If ptr is a null pointer, no action occurs." (7.22.3.3p2)
>>> As far as I know, no previous version of the standard has said anything
>>> different about the matter. Are you aware of any such "variant"?
>>>
>>>
>>
>> I recall lots of older C89 code that wraps an explicit if() around
>> calls to free() just to avoid calling free(NULL). From that I assume
>> that at least some compilers didn't always do this, and that there must
>> thus have existed a standard/specification not requiring free() to
>> check for NULL before doing its thing.
>>
>> The language I wrote was intended to cover any such specification, even
>> if never actually released as an ISO standard.
>

> My recollection is that the K&R 'Standard' didn't define the effect of
> free(NULL), so the code is likely harking back to those days (or habits
> harking back to them). I think the first C Standards body decided that
> there was enough usefulness, and small enough cost, to require the free
> function to make the NULL test, as it is about as close to free as could
> be (test the point just before first use and return it 0, in assembly
> code it just adds a test and conditional jump to the return code).

K&R1 has a couple of sample implementations of a free() function, but
they're not presented as part of the standard library. Neither
specifically checks for a null pointer, though as I recall at least one
of them would likely do nothing with a null pointer argument if pointer
comparisons behave "sensibly".

--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Richard Kettlewell]

Keith Thompson <ks...@mib.org> writes:

> Richard Damon <Ric...@Damon-Family.org> writes:
>> My recollection is that the K&R 'Standard' didn't define the effect
>> of free(NULL), so the code is likely harking back to those days (or
>> habits harking back to them). I think the first C Standards body
>> decided that there was enough usefulness, and small enough cost, to
>> require the free function to make the NULL test, as it is about as
>> close to free as could be (test the point just before first use and
>> return it 0, in assembly code it just adds a test and conditional
>> jump to the return code).
>
> K&R1 has a couple of sample implementations of a free() function, but
> they're not presented as part of the standard library. Neither
> specifically checks for a null pointer, though as I recall at least
> one of them would likely do nothing with a null pointer argument if
> pointer comparisons behave "sensibly".

V6 and V7’s free() implementations don’t check for a null pointer.

They don’t have the “malloc(0) can return NULL even when there’s plenty
of memory available” behavior either; I think that’s a (bad) C89
innovation too.

--
http://www.greenend.org.uk/rjk/

[Richard Damon]

I think the difference is that free() is normally a somewhat expensive
function, taking a moderate number of cycles to execute. memcpy() on the
other hand can often be very quick (for small blocks which may be
common) and even done inline, where adding the test might add a cost
significant to the cost of the operation.

[Richard Damon]

It wasn't an 'Innovation' of the committee. At the time there were
significant implementations, and programs depending on the
implementation, for both possibilities of malloc(0). Some promised a
NULL return, and some promised a valid pointer, and there were
significant applications depending on that behavior. To force
implementation to all adopt the same decision here would have broken a
number of programs, which is one thing the standard committee strove to
avoid.

Their only really option was to make it Implementation Defined, that way
the Implementation could continue to support the programs that depended
on their previous decision.

This says that such programs were now depending on Implementation
Defined behavior, which is really ok, as long as you know it. It really
is very hard to write a significant program that doesn't depend on ANY
Implementation Defined behavior.

[supe...@casperkitty.com]

On Friday, February 5, 2016 at 6:15:06 AM UTC-6, Richard Damon wrote:
> I think the difference is that free() is normally a somewhat expensive
> function, taking a moderate number of cycles to execute. memcpy() on the
> other hand can often be very quick (for small blocks which may be
> common) and even done inline, where adding the test might add a cost
> significant to the cost of the operation.

Most memcpy() implementations don't perform arithmetic upon the supplied
pointers until they've determined that they're going to move at least one
byte. Even implementations which may perform arithmetic before they move
data generally only do so if they've determined that the number of bytes
to be copied is sufficient to justify doing extra setup work in order to
save time in the loop.

The only situations I'm aware of where compilers would need to do anything
to address the corner cases I've added are those where--in the absence of
such a requirement--a compiler might propagate assumptions about the pointers
outside the function call (e.g. given:

memcpy(dest, src, n);
if (src != null) {do_something(); }

some compilers may omit the "if" test on the basis that the memcpy implies
that "src" can't be null). I would posit that the value gained by allowing
such inferences is outweighed by the need for code to add extra handling for
things that would otherwise not need to be "special" cases.

[Tim Rentsch]

Jakob Bohm <jb-u...@wisemo.com> writes:

> On 27/01/2016 20:52, Tim Rentsch wrote:
>> Jakob Bohm <jb-u...@wisemo.com> writes:
>>
>>> On 09/12/2015 18:59, Tim Rentsch wrote:
>>>> Jakob Bohm <jb-u...@wisemo.com> writes:
>>>>
>>>>> On 09/12/2015 02:06, supe...@casperkitty.com wrote:
>>>>>> On Tuesday, December 8, 2015 at 4:50:58 PM UTC-6, Jakob Bohm wrote:
>>>>>

>>>>> [.. should a msize() function be added to the standard C? ..]

>>
>> Re-reading your comments, I'm not sure whether you are implicitly
>> assuming the point I mentioned before, or if you already conceded
>> the point that msize() does have implications for how malloc() and
>> friends can be implemented. In any case msize() is a bad idea,
>> even if it happens to be easy to define in many or most existing
>> schemes for doing malloc()/free().
>
> I was arguing that it would be (near) impossible to create a conforming
> malloc() implementation for which a working (though not necessarily
> fast) msize() cannot be implemented without changing the malloc/free
> implementation code.
>
> I was also arguing that a suitably defined msize() is a very useful and
> good idea, which has been repeatedly added as a vendor extension.

I get that. I just don't find your arguments convincing.