9 ms·

It may be true today that calloc checks for multiplication overflow and doesn't zero memory if it doesn't need to, that's modern revisionism. Historically, ca

It may be true today that calloc checks for multiplication overflow and doesn't zero memory if it doesn't need to, that's modern revisionism. Historically, calloc did not do either of those things. eg, from the 4.4 BSD, circa 1993: https://minnie.tuhs.org/cgi-bin/utree.pl?file=4.4BSD/usr/src/lib/libc/stdlib/calloc.c https://minnie.tuhs.org/cgi-bin/utree.pl?file=4.4BSD/usr/src... void * calloc(num, size) size_t num; register size_t size; { register void *p; size *= num; if (p = malloc(size)) bzero(p, size); return(p); }

warmwaffles 4y ago
I don't believe the spec ever calls out what is exactly supposed to happen for multiplication overflow, and this was left up to the implementation to decide what to do. That being said, libmusl implemented a short but sweet check [1]. Fun stuff. [1]: https://github.com/rofl0r/musl/blob/d05aaedaabd4f5472c233dbbd1ff4bb9c9c99794/src/malloc/calloc.c#L8-L11 https://github.com/rofl0r/musl/blob/d05aaedaabd4f5472c233dbb...
- haberman 4y ago
  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 https://godbolt.org/z/r6cxo8vc7
  - sltkr 4y ago
    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.
    - rightbyte 4y ago
      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?
      - Someone 4y ago
        It is undefined behavior. The undefined behavior rules for pointers boil down to (https://stackoverflow.com/questions/56360316/c-standard-regarding-pointer-arithmetic-outside-arrays 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)
        twoodfin 4y ago
        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.
        wizeman 4y ago
        > 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)?
- noncoml 4y ago
  > 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.
  - haberman 4y ago
    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-Overflow-Builtins.html 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))
    - saagarjha 4y ago
      C23 has ckd_mul.
      - jwilk 4y ago
        https://thephd.dev/c-the-improvements-june-september-virtual-c-meeting#n2683---towards-integer-safety https://thephd.dev/c-the-improvements-june-september-virtual...
    - raverbashing 4y ago
      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)
      - klodolph 4y ago
        > 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).
- ainar-g 4y ago
  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 https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3054.pdf
  - kelnos 4y ago
    > 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.
    - jwilk 4y ago
      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
      - Dylan16807 4y ago
        That's not what the objection is. Your quote is clearly defining a noun.
    - someweirdperson 4y ago
      If it is like overflow, it should indeed be "aroundwrap".
    - Someone 4y ago
      Verbing weirds language (https://www.gocomics.com/calvinandhobbes/1993/01/25 https://www.gocomics.com/calvinandhobbes/1993/01/25), but in English, you can verb (https://en.wikipedia.org/wiki/Conversion_(word_formation)#Verbing https://en.wikipedia.org/wiki/Conversion_(word_formation)#Ve...) a lot of phrases.
    - gnubison 4y ago
      Prescriptivism much? :p
- bornfreddy 4y ago
  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.
  - SAI_Peregrinus 4y ago
    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).
- deleted 4y ago
  [deleted]
tedunangst 4y ago
Yes, it is possible for implementations to be non compliant with the specification.
- pwdisswordfish9 4y ago
  Was there a specification back when this was written? Did it specify what it does now?
  - tedunangst 4y ago
    Yes, the function is defined to either return enough memory for the requested number of objects, or null. Returning less than enough memory is clearly out of spec. This was later stated explicitly, but at no time was it ever permitted.
kdbg 4y ago
Its not just historically (atleast if you include IoT/Industrial/Medical devices) Microsoft's "Section 52" (IoT security research group) called out this issue in several allocators used in IoT in April 2021 [0][1]. [0] https://msrc-blog.microsoft.com/2021/04/29/badalloc-memory-allocation-vulnerabilities-could-affect-wide-range-of-iot-and-ot-devices-in-industrial-medical-and-enterprise-networks/ https://msrc-blog.microsoft.com/2021/04/29/badalloc-memory-a... [1] Full list: https://www.cisa.gov/uscert/ics/advisories/icsa-21-119-04 https://www.cisa.gov/uscert/ics/advisories/icsa-21-119-04
asveikau 4y ago
I feel like in the mid 2000s there was an effort to raise awareness of the "multiply sizes and pass to allocator" class of vulnerability. That was when calloc implementations started checking for overflow. OpenBSD was vocal about it. And they introduced reallocarray in 2014.

warmwaffles 4y ago

I don't believe the spec ever calls out what is exactly supposed to happen for multiplication overflow, and this was left up to the implementation to decide what to do. That being said, libmusl implemented a short but sweet check [1]. Fun stuff. [1]: https://github.com/rofl0r/musl/blob/d05aaedaabd4f5472c233dbbd1ff4bb9c9c99794/src/malloc/calloc.c#L8-L11 https://github.com/rofl0r/musl/blob/d05aaedaabd4f5472c233dbb...

haberman 4y ago
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 https://godbolt.org/z/r6cxo8vc7
- sltkr 4y ago
  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.
  - rightbyte 4y ago
    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?
    - Someone 4y ago
      It is undefined behavior. The undefined behavior rules for pointers boil down to (https://stackoverflow.com/questions/56360316/c-standard-regarding-pointer-arithmetic-outside-arrays 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)
      - twoodfin 4y ago
        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.
        wizeman 4y ago
        > 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)?
noncoml 4y ago
> 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.
- haberman 4y ago
  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-Overflow-Builtins.html 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))
  - saagarjha 4y ago
    C23 has ckd_mul.
    - jwilk 4y ago
      https://thephd.dev/c-the-improvements-june-september-virtual-c-meeting#n2683---towards-integer-safety https://thephd.dev/c-the-improvements-june-september-virtual...
  - raverbashing 4y ago
    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)
    - klodolph 4y ago
      > 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).
ainar-g 4y ago
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 https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3054.pdf
- kelnos 4y ago
  > 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.
  - jwilk 4y ago
    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
    - Dylan16807 4y ago
      That's not what the objection is. Your quote is clearly defining a noun.
  - someweirdperson 4y ago
    If it is like overflow, it should indeed be "aroundwrap".
  - Someone 4y ago
    Verbing weirds language (https://www.gocomics.com/calvinandhobbes/1993/01/25 https://www.gocomics.com/calvinandhobbes/1993/01/25), but in English, you can verb (https://en.wikipedia.org/wiki/Conversion_(word_formation)#Verbing https://en.wikipedia.org/wiki/Conversion_(word_formation)#Ve...) a lot of phrases.
  - gnubison 4y ago
    Prescriptivism much? :p
bornfreddy 4y ago
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.
- SAI_Peregrinus 4y ago
  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).
deleted 4y ago
[deleted]

tedunangst 4y ago

Yes, it is possible for implementations to be non compliant with the specification.

pwdisswordfish9 4y ago
Was there a specification back when this was written? Did it specify what it does now?
- tedunangst 4y ago
  Yes, the function is defined to either return enough memory for the requested number of objects, or null. Returning less than enough memory is clearly out of spec. This was later stated explicitly, but at no time was it ever permitted.

kdbg 4y ago

Its not just historically (atleast if you include IoT/Industrial/Medical devices) Microsoft's "Section 52" (IoT security research group) called out this issue in several allocators used in IoT in April 2021 [0][1]. [0] https://msrc-blog.microsoft.com/2021/04/29/badalloc-memory-allocation-vulnerabilities-could-affect-wide-range-of-iot-and-ot-devices-in-industrial-medical-and-enterprise-networks/ https://msrc-blog.microsoft.com/2021/04/29/badalloc-memory-a... [1] Full list: https://www.cisa.gov/uscert/ics/advisories/icsa-21-119-04 https://www.cisa.gov/uscert/ics/advisories/icsa-21-119-04

asveikau 4y ago

I feel like in the mid 2000s there was an effort to raise awareness of the "multiply sizes and pass to allocator" class of vulnerability. That was when calloc implementations started checking for overflow. OpenBSD was vocal about it. And they introduced reallocarray in 2014.