How to implement calloc

Question

I'm trying to rewrite malloc and calloc, my question is about the implementation of calloc, not how to use it.

One should always use calloc() instead of malloc()+memset(), because it could take advantage of copy-on-write (COW).

Some calloc's are implemented like this:

void * calloc(size_t nelem, size_t elsize)
{
    void *p;

    p = malloc (nelem * elsize);
    if (p == 0)
        return (p);

    bzero (p, nelem * elsize);
    return (p);
}

But they don't use COW at all (and they don't check overflow).

If those implementations don't call bzero(), they must assume that the mmap'ed pages they receive are zero-filled. They probably are because of security reasons, we don't want data from other processes to leak, but I can't find any standard reference about this.

Instead of using MAP_ANON, we could mmap from /dev/zero:

fd = open("/dev/zero", O_RDWR); 
a = mmap (0, 4096e4, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_FILE, fd, 0);

But /dev/zero is not mandated by POSIX, and one could easily do sudo mv /dev/zero /dev/foo, breaking my implementation.

What's the correct way to efficiently re-write calloc(), respecting copy-on-write?

Answer 1

Pure POSIX does not support anonymous memory mappings, and there are no lower-level interfaces than calloc to allocate zeroed memory.

Existing POSIX implementations support anonymous private memory mappings as an extension, via the MAP_ANON or MAP_ANONYMOUS flag (or historically, by mapping from /dev/zero). The kernel makes sure that the application only sees zeroed memory. (There are older interfaces as well, such as brk and sbrk, but they are difficult to use an not thread-safe.)

An implementation of the malloc family of function usually allocates larger blocks using mmap and keeps a watermark pointer for each block which indicates which part has already been allocated to the application at least once (via malloc/realloc/calloc, does not matter). calloc checks the watermark pointer before returning an allocation, and if the memory was used by the application before, it clears it. Otherwise, it is returned directly because it's known that it is fresh and thus has been cleared by the kernel.

Large blocks can be allocated directly using mmap, too. But the kernel has to clear the memory eventually as well (before using it to back mapping that triggered a copy-on-write fault), so this is only a clear win if the allocation is much larger than actually needed, and most parts are never written to.