It’s been a few years since realloc was fixed but occasionally things change, so it’s good to check up on them to make sure there aren’t any regressions. In fact, at the time of the fix, I didn’t even have a complete test case. Now I do.

I wanted to verify two things. First, that separate malloc calls would be randomly spaced. We don’t want them getting all bunched up together or running consecutively in memory. Second, that realloc would be able to grow regions instead of continuously allocating new ones and copying data around.

The test consists of allocating an array of pointers, then randomly picking one pointer and growing it by a random amount.

#include <stdlib.h>
#include <stdio.h>

int
main(int argc, char **argv)
{
        int numptrs = 16;
        if (argc > 1)
                if (!(numptrs = strtonum(argv[1], 4, 256, NULL)))
                        return 1;
        const size_t initsize = 65536;
        void *ptrs[numptrs];
        size_t sizes[numptrs];

        for (int i =0; i < numptrs; i++) {
                ptrs[i] = malloc(initsize);
                sizes[i] = initsize;
                printf("%.3d initial alloc at %p\n", i, ptrs[i]);
        }
        int64_t numreallocs = 0;
        int64_t nummoves = 0;
        while (1) {
                int idx = arc4random_uniform(numptrs);
                size_t newsize = sizes[idx] + arc4random_uniform(sizes[idx]) + 8192;
                void *p = realloc(ptrs[idx], newsize);
                if (!p) {
                        printf("realloc from %zu to %zu failed\n", sizes[idx], newsize);
                        break;
                }
                numreallocs++;
                if (p != ptrs[idx]) {
                        nummoves++;
                        printf("%.3d had to move to grow %zu to %zu\n", idx, sizes[idx], newsize);
                }
                ptrs[idx] = p;
                sizes[idx] = newsize;
        }
        printf("total %lld reallocs with %lld moves\n", numreallocs, nummoves);
        return 0;
}

A trial run.

> ./realloctest 8   
000 initial alloc at 0x5cb0b7b7000
001 initial alloc at 0x5cb010b5000
002 initial alloc at 0x5cb419c1000
003 initial alloc at 0x5cbdf4e8000
004 initial alloc at 0x5cb44fed000
005 initial alloc at 0x5cbf7f67000
006 initial alloc at 0x5cb98019000
007 initial alloc at 0x5cba60a4000
004 had to move to grow 8390702 to 11188998
003 had to move to grow 108406007 to 192003896
005 had to move to grow 11831077 to 12428520
005 had to move to grow 45823520 to 89713487
005 had to move to grow 89713487 to 173832622
004 had to move to grow 86835507 to 115926720
007 had to move to grow 128672932 to 154890077
005 had to move to grow 173832622 to 321367370
005 had to move to grow 321367370 to 544200769
007 had to move to grow 154890077 to 273278833
007 had to move to grow 273278833 to 333822723
003 had to move to grow 367737608 to 475129835
realloc from 802150924 to 1254185101 failed
total 139 reallocs with 12 moves

I guess that’s reasonable. The initial allocations all have the same prefix, but are spread out more than the initial size of 64k would require. And we can see from the reallocations that all of the regions were able to grow substantially before they needed to be relocated. Finally, we ran out of memory trying to go from 800M to 1.2G, but we successfully performed 139 realloc operations with only 12 moves.

Try again with more regions.

> ./realloctest 142 > reallocdata
> head -4 reallocdata
000 initial alloc at 0x37a48111000
001 initial alloc at 0x37a5e251000
002 initial alloc at 0x37abb71e000
003 initial alloc at 0x37a73f0d000
> grep grow reallocdata | sort -n -k 7 | head -1
037 had to move to grow 332913 to 600818
> tail -1 reallocdata
total 1450 reallocs with 75 moves

Even better. We get more reallocs done because the regions don’t grow to enormous sizes quite so quickly. The first time we needed to reallocate was at 600K, about ten times our initial allocation. We can also verify that uvm has picked a different starting point for this process; the addresses have a different prefix.

We usually tout address space randomization as a security measure, but a sparse address space also has performance benefits. By giving regions room to grow, we don’t need to copy them around quite so often.