14 ms·

Why does calloc exist? (2016)

• ksherlock 4y ago
  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.
• cptroot 4y ago
  FYI this should have (2016) in the title. The first paragraph talking about HN appears to be referring to some old moderation drama that was recent when posted.
  • Mathnerd314 4y ago
    And all the publications he links to have stopped publishing.
  • travisgriggs 4y ago
    I was about to comment that “this reminds me of the old internet where people took time to write papers online”. Apparently I was more correct than I realized.
    • pbininda 4y ago
      Wow. 2016 ist "the old internet"? Kids these days! To me "the old internet" ist the one before the web.
  • bigDinosaur 4y ago
    And by goodness, I almost stopped reading, because what a whiny rant.
    • throwawaaarrgh 4y ago
      It seemed dispassionate, reasoned and positive to me, but then again HN has never been a good place for discussions of ethics
      • bigDinosaur 4y ago
        I can't wait to read about the ethics and lack of political discussion around malloc, next.
• kevin_thibedeau 4y ago
  There is a simpler explanation. On 16-bit systems SIZE_MAX is often 65535. You can't allocate a 64K (65536) block with malloc() but you can with calloc().
  • loeg 4y ago
    I'm not confident it's valid to allocate objects larger than SIZE_MAX/2 on any platform.
    • klodolph 4y ago
      Why not? The first argument that comes to mind is the existence of ptrdiff_t, but you’re not guaranteed to get a valid ptrdiff_t just by subtracting two pointers in the same array!
    • teo_zero 4y ago
      Not objects but memory. It was common in 16-bit era. And you would access it through memory segmentation, with two registers: one pointing at the segment beginning, the other being the offset. In code: addr = base << 4 + offset
    • jwilk 4y ago
      As a data point, C23 added explicit wording about overflow handling in calloc(): > The calloc function returns […] a null pointer […] if the mathematical product of nmemb * size is not representable as a value of type size_t. So apparently the Committee is OK with allocating more than SIZE_MAX/2 (but not more than SIZE_MAX).
  • klodolph 4y ago
    Does such a system exist?
    • Retr0id 4y ago
      8086 (and any subsequent intel chip, running in real mode)
• deleted 4y ago
  [deleted]
• altmind 4y ago
  Would be nice to see how hugepages and THP affect performance too
  • unsafecast 4y ago
    For big pieces memory at least, a lot. I was talking to someone the other day about this, they said that in their kernel, switching to huge pages for mapping physical memory made the boot faster by a factor of 10000. I don't have the measurements though.
• LukeShu 4y ago
  Regurgitating from an older comment of mine: https://news.ycombinator.com/item?id=13110538 https://news.ycombinator.com/item?id=13110538 ---- The first version of UNIX to include `calloc` was Research UNIX V6, and here's how it was implemented: https://github.com/dspinellis/unix-history-repo/blob/Research-V6/usr/source/iolib/calloc.c https://github.com/dspinellis/unix-history-repo/blob/Researc... calloc(n, s) { return(alloc(n*s)); } There are several interesting things we learn from poking around V6: - `calloc` originated not on UNIX, but as part of Mike Lesk's "iolib", which was written to make it easier to write C programs portable across PDP 11 UNIX, Honeywell 6000 GCOS, and IBM 370 OS[0]. Presumably the reason calloc is the-way-it-is is hidden in the history of the implementation for GCOS or IBM 370 OS, not UNIX. Unfortunately, I can't seem to track down a copy of Bell Labs "Computing Science Technical Report #31", which seems to be the appropriate reference. - `calloc` predates `malloc`. As you can see in the above code, there was a `malloc`-like function called just `alloc` (though there were also several other functions named `alloc` that allocated things other than memory). (Ok, fine, since V5 the kernel's internal memory allocator happened to be named `malloc`, but it worked differently[1]). [0]: https://github.com/dspinellis/unix-history-repo/blob/Research-V6/usr/doc/iolib/iolib https://github.com/dspinellis/unix-history-repo/blob/Researc... (format with `nroff -ms usr/doc/iolib/iolib`) [1]: https://github.com/dspinellis/unix-history-repo/blob/Research-V6/usr/sys/ken/malloc.c https://github.com/dspinellis/unix-history-repo/blob/Researc...
  • aap_ 4y ago
    I think the `m` in `malloc` and `mfree` in the kernel means `map` as opposed to `memory` in libc. It allocates both core memory and swap memory and uses a `map` struct for this.
  • rightbyte 4y ago
    Nice read. Oh I wish the register keyword was actually honored in today's compilers. I am tired of compilers thinking they are smarter than me and having too trust their fancy register allocator algorithm.
  • __turbobrew__ 4y ago
    At 4:10 in this video there is some interesting history on alloc and malloc, by the original author them self! https://youtu.be/Xe5ffO6Ouwg https://youtu.be/Xe5ffO6Ouwg
• joosters 4y ago
  Does anyone know if this is actually true? By that, I mean the title of this article, 'Why does calloc exist?'. My guess would be that back in the origins of the C library: 1) Few cared about automatic overflow checks, that was a job for the programmer, so it seems unlikely the creators added calloc() specifically so that it could check if m * n overflowed (after all, there are loads of libc calls that will shoot you in the foot if you don't do overflow/buffer size checks) 2) calloc() is ancient, probably pre-dating many virtual memory optimisations, and back then, memory was relatively fast vs instruction execution, so adding calloc() to speed up giant memory allocations would be less impactful. But that's just a hunch, and I'm often surprised by just how sophisticated early UNIX code was. Early computing was slow, every performance gain you could squeeze out of the system mattered and if there were VMs that could defer zeroing memory until it was really needed then people would probably try to do that. But my guess is, calloc() was simply a helper function, added because it was very common to malloc() some memory and then zero it straight away. Does anyone know the actual history?
  • jwilk 4y ago
    As others pointed out elsewhere, as as you suspected, early calloc() implementations didn't zero memory or check for overflow. "Why is calloc useful?" would be probably a better title.
• dang 4y ago
  Discussed at the time: Why does calloc exist? - https://news.ycombinator.com/item?id=13108434 https://news.ycombinator.com/item?id=13108434 - Dec 2016 (132 comments)
• kart23 4y ago
  I remember asking my systems prof this question in class (I can't remember exactly what her answer was), but it was along the lines of is that it's more efficient due to OS+hardware optimizations. basically: use it when you need zeroed out memory!
• notorandit 4y ago
  Nooo! Again? > if we really cared about security we wouldn't be writing in C. If we really cared about security we would definitely be writing in C. If we really cared about security but would prefer not to think about it we wouldn'd be really caring about security, no matter the language. Caring is done by little details. You don't want to risk with dangling pointers, do you? Then you either rely on someone else's work (garbage collector?) embedded in some "secure" language or you do your homework with careful memory allocation. What about buffer/stack overflows? Same. Finally, have you asked yourself with which language your "secure" stack (kernel, userland, compiler/ interpreter etc.) has been written? I bet a huge part is in C.
  • butlerm 4y ago
    If it were remotely feasible to create a competitive operating system kernel in a memory safe language with a tracing garbage collector, a kernel written in something like Java or C# would have taken over the world by now.
  • kelnos 4y ago
    Sure, but I expect that many many many more people have read and run and tested and hardened my kernel, userland, compiler/interpreter than have done so for the code I am just now writing. I have a lot more faith in the correctness of all that other code than I do in the code that I'm about to write, at least not until the code I'm about to write has seen similar scrutiny and usage -- which it likely never will. Put another way, I trust the Rust code I write to be free of memory errors much more than I trust the C code that I write (despite having much more experience writing C than Rust). And yes, that's even accounting for the possibility of bugs in the Rust compiler that cause my program to do unsafe things with memory. Assuming I could actually maintain the focus and discipline to be my absolute most careful self every moment while writing C (which I, in reality, cannot), I still think the Rust compiler is safer than I am. Frankly, I would consider nearly anyone (and possibly just an unqualified "anyone") who believes otherwise about their own abilities to be naive at best, and actively arrogant at worst.
  • avgcorrection 4y ago
    I play rugby without a mouthguard because it keeps me disciplined and I care about my own safety. /s
• 63 4y ago
  So this is probably a silly question, but I'm curious. Why is it important to initialize memory to 0's before we use it? I know rust considers uninitialized memory unsafe but I don't get why. All that really matters is that we initialize it to something. Why can't we wait and let that be the first value that's actually meaningful instead of wasting time writing 0's?
  • londgine 4y ago
    If the memory had the value of a password and was then unallocated, the value would still be there. Then when allocating the memory again, the value would be there. If you initialize it to something and then print it, there is no security issue. but if you print it before, then you just printed a password.
    • stingraycharles 4y ago
      Wouldn’t clearing the memory upon free() be a more reliable way to deal with this, though?
      • Denvercoder9 4y ago
        No, as not all memory is free()'d, think e.g. of crashes and buffer overflows.
      • moffkalast 4y ago
        You could try having the OS guarantee zero initialized memory for all blocks that your program gets, but that's hard to enforce as a standard I imagine.
        • stingraycharles 4y ago
          So if it’s hard to enforce, what’s the reason we go through the effort of zeroing anyway? Isn’t this one of those things that either need to be 100% reliable to be useful? Or is this more about preventing escalation in case someone finds an exploit in your code?
• pjmlp 4y ago
  This is the analysis of one specific implementation of calloc() in one specific operating system, nothing can be extrapolated from that.
• vmilner 4y ago
  I encountered problems on some platforms in the 90s where zeroing the bits of an array of pointers or floats/doubles did not give you an array of NULL pointers or 0.0 values. The comp.lang.c FAQ file discussed this in detail.
  • debugnik 4y ago
    Yeah, C doesn't require null pointers to be represented as 0, even if its constant is written 0, nor does it require floats/doubles to be represented as per IEEE-754. Or at least it didn't use to.
  • deleted 4y ago
    [deleted]
  • mgaunard 4y ago
    I don't think that's standards compliant. At least for floating-point, not entirely sure about pointers.
    • vmilner 4y ago
      Yes. I was porting code to new machines and programmers had assumed it was compliant but it wasn’t.
    • leni536 4y ago
      floats being IEEE compliant is optional by the language standards. Otherwise the bit representation is not specified.
      • deleted 4y ago
        [deleted]
      • mgaunard 4y ago
        It still requires 0 to be represented as all bits set to zero.
        • 4y ago
• Traubenfuchs 4y ago
  So when would you ever use malloc? calloc appears to be superior.
  • saagarjha 4y ago
    Not having to zero out allocations can mean that malloc runs slightly faster.
• heckelson 4y ago
  Another context calloc is useful is in NUMA systems because of the first touch policy, right?
• throwaway2037 4y ago
  Did anyone else notice (and read) the "Welcome Hacker News readers" section? It is weird. Example: <<I hope the HN moderators find a way to step up to the responsibility their position entails>> What does this mean?
  • quickthrower2 4y ago
    Clicking the links makes it clearer. Back in 2016 there seems to have been a politics free week on HN. (Hmm… 2016… I wonder why!). Anyway he sort of implies it is our duty to discuss politics on HN to avoid maybe the next Hitler or other such bad things happening.
  • unfamiliar 4y ago
• jwilk 4y ago
  Some of the links in the paragraph about python-requests have bitrotted. Fixed links: https://github.com/psf/requests/issues/3729 https://github.com/psf/requests/issues/3729 https://foss.heptapod.net/pypy/cffi/-/issues/295 https://foss.heptapod.net/pypy/cffi/-/issues/295
• deleted 4y ago
  [deleted]
• maxnoe 4y ago
  Minor nitpick: on my mobile view there is a linebreak between base and exponent, that's a bit irritating. 2 63
• hasmanean 4y ago
  C++ has entered the chat. T *foo = new T(1000);
• einpoklum 4y ago
  Reason #2 at the link is why we absolute must have a reallocate-and-move primitive - because it could be much faster than allocating and copying: It would have a higher chance for copying by virtual memory page remapping. Of course, just plain copying might also use virtual memory page tricks; I wonder which platforms do that (if any).
• DubiousPusher 4y ago
  Discontinuity between hairlines.