> if (n && m > (size_t)-1/n)

Am I the only one that doesn’t think this is “sweet”?

I mean I know what it does and why and how it works, but IMHO a good language should let you express your intention and algorithm in human terms and logic in which there is no -1 value for an unsigned integer type.

Agreed that it would be better if C had standardized versions of GCC's overflow checking functions: https://gcc.gnu.org/onlinedocs/gcc-9.1.0/gcc/Integer-Overflo...

With these functions, it could be written as: if (__builtin_mul_overflow(n, m, &n))

C23 has ckd_mul.

True.

It seems the C committee at some point makes things harder than they should. And true, the C committee is not preventing anyone from using something else

(Another reason why we should retire C for most projects)

> It seems the C committee at some point makes things harder than they should

This seems like entirely the wrong way of looking at it to me. The C committee is not trying to make things harder than they should be, but they’re really just a committee in charge of C. Their goal isn’t to make C into some kind of beautiful safe language, it’s just to provide incremental improvements to C for the benefit of people stuck using it for whatever reason.

Like, the C committee isn’t trying to stop you from retiring C. They’re just trying to help out the people who aren’t retiring C, for whatever reason—which could be toolchain availability (lots of architectures out there, you may only have a C compiler for some), could be so they can work with a legacy codebase, could be that some other tooling or process they have works with C (the various “safe C” / analyzable subsets or formal verification processes).

I agree that in terms of modern proposals there's a lot of "doing what we can"

However, leaving the overflow check/behavior on the multiplication as "implementation defined" seems like a bad call to me

The fact that signed overflow is undefined is unfortunately something that is necessary for certain optimizations to be valid. You can, for example, try `-fwrapv` or `-ftrapv` on GCC, but if you run through an extensive benchmark suite you’ll see regressions.

Not everyone cares about the benchmarks, but enough do.

...Weren't we talking unsigned though?

WG14 could take care about improving the language gotchas for safer software, something that all other ISO language groups, including WG21 do bother to do.

However in 40 years they already made their point not to care beyond make C a portable macro assembler with more UB issues than writing in raw Assembly.

C is not even remotely like a macro assembler. I get why people make the comparison, but the more I work with C and assembler, the more I realize that the comparison is facile. The relationship between the C code you write and the machine code which the compiler generates is complicated. If you think of C as a portable assembler, it’s easy to draw the wrong conclusion about how your code will behave. You look at some code and think, “I know how the assembly should look,” and at that point you’ve lost, because of the vast gulf between C and assembly semantics.

The UB issues are not going away. Some people who use C need to get good performance out of it. If you try fixing the UB issues, you end up having to remove optimization passes from your C compilers. That’s just not viable—hence, UB issues are here to say.

The correct thing for the C committee is to make slow, careful improvements to C for the people who are stuck using it. And the correct choice for most people is to stop using C in favor of safer languages.

If you try to have the committee fix the safety problems with C, you’re going to end up with something which neither fast nor safe. If you are stuck using C and need it to be safe, you can use formal methods. If you don’t have the budget for formal methods, you need safety, and you’re stuck on a system which only has a C toolchain, then the alternative is to use something which compiles to C.

I've heard them called museum conservators. : p

That language is C99, a now 23-year-old standard dialect of C.

   if (n && m > SIZE_MAX / n)

There's SIZE_MAX constant, I don't know why they didn't use it.

I'd rewrite it as `if (n != 0 && m > SIZE_MAX / n)`. Seems legit to me.

Most likely to get around clever UB optimizations when checking for values beyond max sizes.

No. (size_t)-1 and SIZE_MAX are identical, there is no difference in the two ways of writing that.

Furthermore, optimisation can't bite you if you test the values before you perform the potentially UB operation (and unsigned operations can never overflow anyway, they are always well-defined).

That was just an assumption, far from me to know all UB cases, I leave that for tooling.

But there is no such check here, is there? SIZE_MAX / SIZE_MAX is legally 1.

Maybe it's late but I don't get it. Can someone spell it out for me?

If n != 0 and -1 cast to unsigned size_t divided by n is less than m. So that m times n would be bigger than size_t’s maximum value.

Edit: inverted meaning since check is for error, not for ok case.

You want to evaluate p in:

  p = m n

If that is gonna overflow, p > SIZE_MAX.

Then it would be that (by substitution)

  m n > SIZE_MAX

so

  m > SIZE_MAX/n

except if n = 0. In the latter case, m can be as big as it wants--p will always evaluate to 0.

And (size_t)-1 is a silly way to write SIZE_MAX (but it saves you a dependency).

Thanks! Indeed the `(size_t)-1` threw me off, and the `m && n` was an interesting obfuscation for checking whether either are 0.

> if (n && m > (size_t)-1/n)

Shouldn't the case of wraparound be caught by testing the resulting size as following?

  s = n*m;
  if (n && s >= n && s >= m) /* no overflow */ ...

That doesn't work for multiplication -- e.g. in 8-bit, 20 * 20 wraps to 144.

You are not.

Even more satisfying, I tried this out in godbolt and it appears that compilers are able to optimize that check into a single `mul, jo` (jump on overflow) sequence, which is how you would write it if you were writing assembly directly. It avoids a division instruction (which would be far more expensive) even though the code is written as a division: https://godbolt.org/z/r6cxo8vc7

But less satisfying, it looks like clang optimizes out the entire zero-initialization logic, presumably because it assumes the expression ((size_t *)p)[-1] is undefined behavior.

Makes me wonder what kind of compiler flags muslibc uses to prevent this.

That is not undefined right? As long as p - 1 points into a valid object.

Edit: Maybe Clang abuses the bitand with an int 7 to remove the code?

It is undefined behavior. The undefined behavior rules for pointers boil down to (https://stackoverflow.com/questions/56360316/c-standard-rega...)

“Pointer arithmetic is well defined only on array type and between array[0] and array[array_size+1]”

And it’s even stricter:

- you can create a pointer to array[array_size+1], but dereferencing it invokes undefined behavior.

- changing a pointer that points into an object so that it points into another object invokes undefined behavior. Modern compilers track “pointer provenance” to sometimes speed up code (and occasionally perplex the programmer)

Those rules apply to access to the underlying array, they’re not a constraint on syntax for array expressions. malloc just returns a pointer, which could be in the middle of an array if malloc were an ordinary user-defined function.

It’s only special knowledge of the behavior of standard malloc that allows the compiler to assume that pointer is to offset 0 of an allocated array.

> malloc just returns a pointer, which could be in the middle of an array if malloc were an ordinary user-defined function.

Yes, but even in that case, it would have to be an array of `size_t` objects for the pointer cast `(size_t *)` in the musl code not to trigger undefined behavior (especially if malloc would get inlined), right?

Which means calloc() would trigger undefined behavior as soon as one of its callers used it for allocating a non-size_t array (especially if calloc() would get inlined with link-time optimization)?

You just need certain parts of the returned allocation to be castable to size_t, and there's no way for the compiler to prove that wrong if it doesn't know the internals of the allocator. The underlying allocation could be as big as you want, and can be composed of whatever type you like.

> You just need certain parts of the returned allocation to be castable to size_t, and there's no way for the compiler to prove that wrong if it doesn't know the internals of the allocator. The underlying allocation could be as big as you want, and can be composed of whatever type you like.

  Hmm, I don't think this is true.

  Even if you don't assume special semantics for malloc() and friends (by using the `-ffreestanding` and the `-fno-builtin` flags) and even if the compiler knows nothing about the malloc() implementation, I think if you're doing pointer arithmetic (with a pointer type other than `void *` or `[unsigned] char *`) then the compiler can assume that the pointer is pointing to either: 1) an actual array of objects of the underlying type (or a compatible one), or 2) a pointer to a single object, which is treated as an array with one element.

  So if you do `((size_t *) p)[-1]` within `calloc()`, then the compiler can assume that `*p`, if used, must either be a `size_t` (or a compatible integer) or `p` must be pointing to one past the end of a single-element array (which, since `*p` is a dereference, would trigger undefined behavior).

  Which means that if you call `calloc()` and it returns `p`, then you can only use it to dereference `size_t` objects or compatible ones (otherwise it would trigger undefined behavior). The effects of the undefined behavior would likely be observed if `calloc()` gets inlined into the caller (due to link-time optimization, for instance).

  Or am I wrong?

You say no but then you list exceptions. Compatible integer types is easy. And can't you also have any pointers you want into a char array as long as they are aligned correctly? Also it should work to have a struct with a size_t followed by elements of a different type, shouldn't it?

> You say no but then you list exceptions.

  You said "there's no way for the compiler to prove that wrong if it doesn't know the internals of the allocator" and I tried to reason how the compiler can prove that `*p` must be a `size_t` or compatible integer, even if it knows nothing about malloc() or its implementation. Which would trigger undefined behavior in the caller of calloc() if it weren't trying to allocate a size_t (or size_t array, or of compatible integers). Although normally this would only produce a visible effect if calloc() gets inlined into the caller.

> Compatible integer types is easy.

  What do you mean?

> And can't you also have any pointers you want into a char array as long as they are aligned correctly?

  I think so, but I think the problem is that when you do `(size_t *) p` (or pointer arithmetic with that) then the compiler can assume that p points to something that is not just a char array, which allows it to do more optimizations (due to the undefined behavior rules).

> Also it should work to have a struct with a size_t followed by elements of a different type, shouldn't it?

  I think in general it wouldn't, because structure members are not guaranteed to be contiguous (i.e. they may have padding between them), so you may be triggering undefined behavior as well. However, if your struct has just a `size_t` field followed by a flexible array member then I think it would be OK!

  So I think I was wrong after all!

  Edit: on second thought, even with a flexible array member I'm not sure it doesn't trigger undefined behavior because I think the C standard allows there to be padding at the end of such a struct. So I'm not sure about this.

> I think so, but I think the problem is that when you do `(size_t *) p` (or pointer arithmetic with that) then the compiler can assume that p points to something that is not just a char array, which allows it to do more optimizations (due to the undefined behavior rules).

For the sake of clarity, I'm going to call `(size_t *) p` "q" for the rest of this post.

Pointers usually have the type of what they point to. But pointers that are one past the end don't follow that rule. q-1 is a size_t, which means q is one past the end of an array containing one size_t. Therefore the existence of the q pointer does not tell the compiler what type actually exists at memory address p/q. Is it invalid to construct q from p? I wouldn't think so as long as they are in the same allocation, but maybe I'm forgetting a rule.

> I think in general it wouldn't, because structure members are not guaranteed to be contiguous

Surely there's a way to allocate two different types up against each other, though? Even if you don't make an actual struct, you can grab some char and say that X bytes are size_t and Y bytes are something else, can't you?

> Therefore the existence of the q pointer does not tell the compiler what type actually exists at memory address p/q. Is it invalid to construct q from p? I wouldn't think so as long as they are in the same allocation, but maybe I'm forgetting a rule.

But then the question is, how would you construct an allocation where both q[-1] and *p are guaranteed to be valid objects of their respective types, using standard C? (i.e. without relying on implementation-specific behavior).

> Surely there's a way to allocate two different types up against each other, though?

If by "against each other" you mean without padding between them, then I think the C standard allows that but there's no reliable/portable/guaranteed way to do it (that I know of).

By that I mean that specific implementations can guarantee that, either with struct packing or, in some cases, by carefully aligning them within a struct or a union. But this depends on the implementation/architecture, so it's not strictly portable/standard C, I think.

> Even if you don't make an actual struct, you can grab some char and say that X bytes are size_t and Y bytes are something else, can't you?

I'm not sure that is possible according to the standard, unless they already were objects of those types. See this[0]:

> It is always presumed that a char* may refer to an alias of any object. It is therefore quite safe, if perhaps a bit unoptimal (for architecture with wide loads and stores) to cast any pointer of any type to a char* type.

> The converse is not true. Casting a char* to a pointer of any type other than a char* and dereferencing it is usually in violation of the strict aliasing rule.

> As noted by Pinskla it is not deferencing a char* per se that is specifically recognized as a potential alias of any object, but any address referring to a char object. This includes an array of char objects

That said, I think for converting a bunch of chars to another type it's possible to get around that with memcpy() in some cases, but I'm not sure it would be helpful in this scenario.

[0] https://cellperformance.beyond3d.com/articles/2006/06/unders...

How about this: We can make a struct and then have a function that bails out if for some reason the fields are not adjacent in the struct. Possibly even at compile time. In practice, this will work on basically any compiler.

Once we know we have this struct, are there any remaining barriers to the cast and -1 access?

>> Casting a char* to a pointer of any type other than a char* and dereferencing it is usually in violation of the strict aliasing rule.

How does that logic work with malloc, which unlike calloc takes no item size and simply gives you a specific number of bytes?

> Once we know we have this struct, are there any remaining barriers to the cast and -1 access?

I think the only problem is that malloc() wouldn't know the type of the non-size_t field, so it couldn't construct such a struct to do a conforming allocation which would allow calloc() to do those operations.

But I think that this is actually a consequence of the standard being flawed, in that I think it's not possible to create an implementation of malloc() using strict standard C (but I could be wrong, I'm not exactly an expert on the C standard).

> How does that logic work with malloc, which unlike calloc takes no item size and simply gives you a specific number of bytes?

The return value of malloc() is treated specially by the standard, I believe. Which is why musl has to use the `-ffreestanding` and `-fno-builtin` flags, I think.

I think this is also why GCC provides a "malloc" attribute which you can use in your own functions, so that they are treated specially (like malloc()), but I believe that this is non-standard.

What I mean is that malloc doesn't know the size of any of the fields.

Let's assume for the sake of simplicity that `sizeof element` is the same as `sizeof size_t` or a multiple of it. We don't need to assume this, it just makes the math nicer for the moment.

I do: char* buffer = malloc((count + 1) * sizeof element);

Or I do: char* buffer = calloc(count + 1, sizeof element);

How is C supposed to know what goes in that buffer?

Maybe it's an array of elements. Maybe it's an array of size_t[sizeof element / sizeof size_t].

Maybe it's an array of union { element, size_t[sizeof element / sizeof size_t]}.

If I want to store an `element` at a location `sizeof element` bytes into the buffer, how can it say no? If I want to store a `size_t` at a location `sizeof element - sizeof size_t` bytes into the buffer, how can it say no? If I want to do both, how can it say no?

Read the source.

It returns a pointer to a chunk of memory of sufficent fore size_t (unsigned, positive whole number of elements) where each of those elements is size_t (unsigned, positive whole number) in size within the limits of your computationally representable chunk of numbers.

No code "knows" squat about the implementation. You can know. You're the programmer, you can read the code. The computer just does. Even if that causes demons to fly out your nose.

Friends don't let friends write code without checking whether it'll cause demons to fly out their nose first. If they ain't your friend though, there's always checking ERRNO.

I think you may be right and I was wrong.

I think I was operating under more conservative assumptions about what is actually legal to do in C.

I actually had to go and read the standard because the strict aliasing rules can be very tricky and it's not always clear what is legal to do in every situation. Even then, it's hard to understand the wording of the standard and its implications, especially since there are multiple rules coming into play and there's no clear explanation of how they interact with each other.

In this specific case that we're talking about, I think you can indeed allocate a buffer, store the malloc-returned pointer in a `char *` variable, and then store an element and a size_t wherever you want within the buffer (but if you want to store them or access them using a properly-typed pointer rather than memcpy() then the address needs to respect the alignment of the type, I think).

But I think this is only legal because the addresses within a buffer returned by malloc are not considered to have a declared type and that the type of some address within the buffer becomes established whenever you assign or copy some value to it, so it doesn't actually necessarily become established based on the valid conversions between pointer types like I thought it was.

I'm still not exactly 100% certain about what the expression we're talking about is actually undefined behavior or not, because on one hand, the standard clearly says that dereferencing a pointer which points one past the end of an array is undefined behavior (and `p` could be considered such a pointer), but on the other hand, it's hard to see how this can be the case when `p` can be a perfectly valid pointer to some other value within the same allocation.

The rule which says that it's undefined behavior to dereference a pointer that points one past the end of an array (which can be a single value) is inside the pointer arithmetic section. So my interpretation is that, if there is a valid and properly-typed value stored at the address of a pointer that also points to one past the end of an array, it's only undefined behavior to dereference such a pointer if the address of that pointer was obtained through pointer arithmetic based on a pointer that also pointed to the array.

So, if my interpretation is correct, I think in this case the rules are subtle: it seems that dereferencing `((size_t *) p)[-1]` is legal if there already is a `size_t` stored at that address (I think?). But it doesn't seem to be legal to dereference `(((size_t *) p)[-1])[1]` (unless `p` points to some non-first element of an array). However, it would be legal to dereference `*((size_t *) p)`, but only if the address represented by `p` already contains a `size_t` there, I think (??).

Funnily enough the SO answer has a off by one error. &array[array_size] is the last valid pointer (i.e. the pointer is valid, but can't be dereferenced).

> changing a pointer that points into an object so that it points into another object invokes undefined behavior

Do you have a source for this? Couldn't find anything on it with a quick web search.

https://en.cppreference.com/w/cpp/language/operator_arithmet...:

“If the pointer P points to the ith element of an array, then the expressions P + n, n + P, and P - n are pointers of the same type that point to the i+nth, i+nth, and i-nth element of the same array, respectively. The result of pointer addition may also be a one-past-the-end pointer (that is, pointer P such that the expression P - 1 points to the last element of the array). Any other situations (that is, attempts to generate a pointer that isn't pointing at an element of the same array or one past the end) invoke undefined behavior.”

I think you may have misread my comment, that wasn't the part I was referring to.

In the real world, musl would call its own `malloc` and can presumably trust that `((size_t *)p)[-1]` is valid and contains the block metadata (and the compiler can't assume it isn't valid), whereas the godbolt snippet calls libc's `malloc` which is a black box to outside callers. Or maybe LLVM can even deduce that the low bits are always zero on `libc`?

Tried -fno-builtin-malloc on a hunch and it does seem to prevent the zero-initialisation logic from getting optimised away: https://godbolt.org/z/xWbEqcenn

musl probably uses -fno-builtin to disable any special handling of "builtin" library functions like malloc and memcpy?

> But less satisfying, it looks like clang optimizes out the entire zero-initialization logic, presumably because it assumes the expression ((size_t *)p)[-1] is undefined behavior.

Yeah, I noticed that is undefined behavior too!

> Makes me wonder what kind of compiler flags muslibc uses to prevent this.

As far as I can see, the only related flags are `-ffreestanding`, `-fno-builtin` and `-fno-strict-aliasing` but I think none of these options prevent the undefined behavior if 1) either the malloc() implementation gets inlined into calloc(), or 2) calloc() gets inlined into the caller, so that the compiler realizes that `p` is not actually an array of `size_t` or compatible integers.

So perhaps musl just avoids undefined behavior by forcing `malloc()` and `calloc()` to not be inlined into the caller? Although I'm not entirely sure that actually completely prevents undefined behavior, I think it would just avoid it assuming how compilers usually/currently work?

So, I just checked and it seems that the parent pointed to a musl repository that contains old code.

The current code doesn't contain that undefined behavior-triggering expression: https://git.musl-libc.org/cgit/musl/tree/src/malloc/calloc.c

Try with -ffreestanding. Otherwise clang is allowed to make assumptions about the behavior of "malloc".

It then does the typical unsatisfying clang thing of unrolling and vectorizing a _lot_ with unclear benefits: https://godbolt.org/z/eG33YM7qs

The current C2x (aka C23) draft finally spells the behaviour out explicitly:

> 7.24.3.2 The calloc function

> […]

> Returns

> The calloc function returns either a pointer to the allocated space or a null pointer if the space cannot be allocated or if the product nmemb * size would wraparound size_t.

https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3054.pdf

> if the product nmemb * size would wraparound size_t.

Gah! "Wraparound" is not a verb! You'd think someone writing a computer language specification would try to use (human) language correctly.

If it is like overflow, it should indeed be "aroundwrap".

FWIW, it's a technical term defined as:

> the process by which a value is reduced modulo 2ᴺ, where N is the width of the resulting type

That's not what the objection is. Your quote is clearly defining a noun.

Verbing weirds language (https://www.gocomics.com/calvinandhobbes/1993/01/25), but in English, you can verb (https://en.wikipedia.org/wiki/Conversion_(word_formation)#Ve...) a lot of phrases.

Prescriptivism much? :p

From my (admittedly very limited, and very dated) knowledge of x86 asm, I remember that multiplication sets some flags if there was an overflow. Is there no way to multiply in C so that such an overflow was detected? Or do some CPU architectures not support such flags? It seems inefficient (to me) to do this check before each multiplication.

The C abstract machine does not have such flags. C therefore does not have any support for checking them (from code, the compiler can add checks if the target supports them but doesn't have to).