4 ms·

That's a nice alternative history fiction. Here's an early implementation: https://github.com/dspinellis/unix-history-repo/blob/Research-V7/usr/src/libc/gen/ca

by bluefox 10y ago

That's a nice alternative history fiction. Here's an early implementation: https://github.com/dspinellis/unix-history-repo/blob/Research-V7/usr/src/libc/gen/calloc.c https://github.com/dspinellis/unix-history-repo/blob/Researc...

colanderman 10y ago
It's a good explanation of why calloc still exists and is useful. Otherwise it would have been dropped from the standard like cfree was.
- viraptor 10y ago
  I think there's a big difference between "why does ... exist" and "why does ... still exist". calloc() may be useful today for reasons completely different from why it existed in the first place. And the difference #2 is just an implementation-specific optimisation. There's nothing in the standard that forces calloc to use lazy allocation / virtual memory. Actually, it may be implemented on platforms which can't provide this.
  - greglindahl 10y ago
    Thank you for bringing up the implementation-specific nature of #2! If the author is running Linux, then perhaps they've never checked out overcommit vs. not overcommit.
    - mikeash 10y ago
      You're likely to still see a performance improvement without overcommit. The OS will try to zero free pages in the background, so there's a good chance that it'll have pre-zeroed pages to hand you when you ask for them, rather than making you wait for them to be zeroed on demand. Of course, there are plenty of systems where this doesn't happen, or there are no pages in the first place, or there's no kernel zeroing stuff for you.
    - Someone 10y ago
      The way malloc, calloc, and memset are implemented all are implementation specific. For example, memset, when asked to zero memory, may use cache control instructions such as https://en.wikipedia.org/wiki/Cache_control_instruction#Data_cache_block_allocate_zero https://en.wikipedia.org/wiki/Cache_control_instruction#Data.... That tells your cache "pretend that you read all zeroes into the cache line at this address, and mark it as dirty (that guarantees the zeroes will be written out, even if the caller doesn't write to the cache line) For small amounts of memory that will be written to soon, that's as good as free since it doesn't have to read from memory (the naive loop will, as it has to bring in an entire cache line before it can zero out its first byte or word)
    - dagw 10y ago
      For what it's worth, the numpy 'trick' he used to demonstrate that feature also works on windows.
aap_ 10y ago
Good point, and it makes we wonder why the code is attributed to dmr...it looks like written by ken. I suppose recreating such a repo can only be so accurate.
LukeShu 10y ago
You haven't proven it wrong. Here's the earliest implementation in that repo (in Research UNIX V6; your link in V7): 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 though: - `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, 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...
- saretired 10y ago
  It appears that only calloc was in Lesk's Portable C Library [0] while malloc was the name Thompson gave the kernel's memory allocator in V6 [1]. When Ritchie rewrote Lesk's library for V7, he may have simply retained calloc for backward compatibility with existing user space code. [0] http://roguelife.org/~fujita/COOKIES/HISTORY/V6/iolib.html http://roguelife.org/~fujita/COOKIES/HISTORY/V6/iolib.html [1] https://github.com/hephaex/unix-v6/blob/master/ken/malloc.c https://github.com/hephaex/unix-v6/blob/master/ken/malloc.c
- ksherlock 10y ago
  OpenBSD added calloc overflow checking on July 29th, 2002. glibc added calloc overflow checking on August 1, 2002. Probably not a coincidence. I'm going to say nobody checked for overflow prior to the August 2002 security advisory. https://github.com/openbsd/src/commit/c7b2af4b3f7e78424f8943119b1397773e619e77 https://github.com/openbsd/src/commit/c7b2af4b3f7e78424f8943... https://github.com/bminor/glibc/commit/0950889b810736fe7ad340a13a5ecf76672e1a84 https://github.com/bminor/glibc/commit/0950889b810736fe7ad34... http://cert.uni-stuttgart.de/ticker/advisories/calloc.html http://cert.uni-stuttgart.de/ticker/advisories/calloc.html

by bluefox 10y ago

colanderman 10y ago

It's a good explanation of why calloc still exists and is useful. Otherwise it would have been dropped from the standard like cfree was.

viraptor 10y ago
I think there's a big difference between "why does ... exist" and "why does ... still exist". calloc() may be useful today for reasons completely different from why it existed in the first place. And the difference #2 is just an implementation-specific optimisation. There's nothing in the standard that forces calloc to use lazy allocation / virtual memory. Actually, it may be implemented on platforms which can't provide this.
- greglindahl 10y ago
  Thank you for bringing up the implementation-specific nature of #2! If the author is running Linux, then perhaps they've never checked out overcommit vs. not overcommit.
  - mikeash 10y ago
    You're likely to still see a performance improvement without overcommit. The OS will try to zero free pages in the background, so there's a good chance that it'll have pre-zeroed pages to hand you when you ask for them, rather than making you wait for them to be zeroed on demand. Of course, there are plenty of systems where this doesn't happen, or there are no pages in the first place, or there's no kernel zeroing stuff for you.
  - Someone 10y ago
    The way malloc, calloc, and memset are implemented all are implementation specific. For example, memset, when asked to zero memory, may use cache control instructions such as https://en.wikipedia.org/wiki/Cache_control_instruction#Data_cache_block_allocate_zero https://en.wikipedia.org/wiki/Cache_control_instruction#Data.... That tells your cache "pretend that you read all zeroes into the cache line at this address, and mark it as dirty (that guarantees the zeroes will be written out, even if the caller doesn't write to the cache line) For small amounts of memory that will be written to soon, that's as good as free since it doesn't have to read from memory (the naive loop will, as it has to bring in an entire cache line before it can zero out its first byte or word)
  - dagw 10y ago
    For what it's worth, the numpy 'trick' he used to demonstrate that feature also works on windows.

aap_ 10y ago

Good point, and it makes we wonder why the code is attributed to dmr...it looks like written by ken. I suppose recreating such a repo can only be so accurate.

LukeShu 10y ago

You haven't proven it wrong. Here's the earliest implementation in that repo (in Research UNIX V6; your link in V7): 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 though: - `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, 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...

saretired 10y ago
It appears that only calloc was in Lesk's Portable C Library [0] while malloc was the name Thompson gave the kernel's memory allocator in V6 [1]. When Ritchie rewrote Lesk's library for V7, he may have simply retained calloc for backward compatibility with existing user space code. [0] http://roguelife.org/~fujita/COOKIES/HISTORY/V6/iolib.html http://roguelife.org/~fujita/COOKIES/HISTORY/V6/iolib.html [1] https://github.com/hephaex/unix-v6/blob/master/ken/malloc.c https://github.com/hephaex/unix-v6/blob/master/ken/malloc.c
ksherlock 10y ago
OpenBSD added calloc overflow checking on July 29th, 2002. glibc added calloc overflow checking on August 1, 2002. Probably not a coincidence. I'm going to say nobody checked for overflow prior to the August 2002 security advisory. https://github.com/openbsd/src/commit/c7b2af4b3f7e78424f8943119b1397773e619e77 https://github.com/openbsd/src/commit/c7b2af4b3f7e78424f8943... https://github.com/bminor/glibc/commit/0950889b810736fe7ad340a13a5ecf76672e1a84 https://github.com/bminor/glibc/commit/0950889b810736fe7ad34... http://cert.uni-stuttgart.de/ticker/advisories/calloc.html http://cert.uni-stuttgart.de/ticker/advisories/calloc.html