A4. Your own allocator

intermediatebuilds on module 10, module 12

Goal

Module 10 claims that in practice “best fit” doesn’t beat “first fit” on density but loses to it on speed. You’ll write your own malloc on top of mmap, implement both strategies, and test this on three request profiles. Along the way you’ll see that physical memory appears in a process only on the first write, as described in module 12.

After this lab you will be able to:

• write an allocator with block headers, a free list, and coalescing of neighbors that passes integrity checks and AddressSanitizer;
• explain why an address from malloc is a multiple of alignof(max_align_t) and what happens otherwise;
• compute external and internal fragmentation from heap_stats and say which one grows on which profile;
• show with VmSize and VmRSS why malloc(8 GiB) succeeds on a machine with four gigabytes of memory;
• justify the choice between “first fit” and “best fit” with numbers.

The same headers, free lists, and coalescing are inside the system malloc, and analyzing fragmentation in a service that runs for weeks starts with them.

Task

Write my_alloc.c against the interface in my_alloc.h, and a test bench that runs the allocator on three request profiles and prints the fragmentation.

void *my_malloc(size_t size);
void  my_free(void *ptr);
void *my_realloc(void *ptr, size_t size);
void  my_heap_stats(struct heap_stats *out);
void  my_set_fit(int best_fit);   // 0 = first fit, 1 = best fit

my_heap_stats fills six fields of struct heap_stats: bytes requested, bytes obtained from the system, bytes in use including headers, the total of free blocks, their count, and the largest of them. Fragmentation is computed from these numbers. The strategy is switched with my_set_fit or the environment variable MY_ALLOC_FIT=first|best.

What it must do:

1. my_malloc returns memory that can be written and read back; my_free(NULL) and my_malloc(0) don’t crash.
2. Addresses are multiples of alignof(max_align_t) for any size.
3. 64 blocks of different sizes don’t overwrite each other.
4. my_realloc preserves the contents both when growing and when shrinking.
5. Coalescing neighbors: after all 64 blocks are freed, a contiguous block of half the free memory can be allocated, and there are no more than four free blocks left.
6. The statistics are consistent: requested ≤ obtained, free_bytes ≤ obtained, largest_free ≤ free_bytes.
7. 5000 random allocations and frees of up to 1 KiB don’t corrupt a single block.
8. Both placement strategies, differing only in the search function.

Constraints. C11 only. Memory is obtained from the system with mmap or sbrk; don’t call libc’s malloc inside the allocator. tests.c and my_alloc.h are not modified: the check builds them from its own directory.

What you don’t need to do. Thread safety isn’t required: tests.c is single-threaded. Size classes as in a slab allocator, and replacing the system malloc via LD_PRELOAD, are left for “Further, if you’re curious”.

What to write in the report:

• VmSize and VmRSS from /proc/self/status before and after the first write to a large region from mmap;
• a “strategy × profile → external and internal fragmentation, search time” table for the profiles: uniform sizes, two sharply different sizes, heavy tail;
• a conclusion on which strategy won on which profile; if “best fit” won, an explanation of why.

Done when:

• ./check.sh my_alloc.c: fifteen checks pass, AddressSanitizer stays silent;
• the bench prints both fragmentation figures for each strategy on each profile;
• the report has the table and the conclusion.

Before you start

• Read the sections “Contiguous allocation” and “External fragmentation” in module 10, and the sections “Demand paging” and “How it actually works in Linux” in module 12.
• Unpack the course archive: labs/a4-allocator/ contains my_alloc.h, tests.c, and check.sh; the script builds your my_alloc.c together with tests.c.
• You’ll need gcc with -fsanitize=address, man 2 mmap, and man 5 proc (the VmSize and VmRSS fields). Any Linux will do, including a container and WSL2.

Stages

1. Memory from the system.

   Get it with mmap and MAP_ANONYMOUS, in large chunks (say, 1 MiB each), and carve them up yourself. sbrk works too, but mmap is closer to how modern allocators work.

   Note that mmap hands out addresses instantly regardless of size. Physical pages appear on the first write; check this by comparing VmSize and VmRSS in /proc/self/status.

2. A free list and “first fit”.

   Each block has a header with its size and an in-use flag. my_free returns the block to the list.

3. Coalescing neighbors.

   Without it, fragmentation grows without bound: freed adjacent blocks stay separate and none of them fits a larger request.

   The simplest way is boundary tags: the size is duplicated at the end of the block so you can look at the neighbor on the left.

4. The second strategy: “best fit”.

   The strategy is selected by a flag or an environment variable. The code is shared; the difference is in a single search function.

5. Measurement.

   The bench generates a sequence of allocations and frees with a given distribution of sizes and lifetimes, then prints the statistics.

   Three profiles are required: uniform sizes (almost no fragmentation), two sharply different sizes (the worst case), a heavy-tailed size distribution (similar to real programs).

6. Conclusion.

   A “strategy × profile → fragmentation, search time” table. If “best fit” won for you, describe on which profile and why: that’s also a valid result, but it needs to be explained.

How to compute fragmentation

External: 1 − largest_free_block / total_free_memory. A value of one means free memory is scattered into tiny pieces.

Internal: (handed_out − requested) / handed_out. This includes headers and alignment.

Print them separately: they behave in opposite ways, which is why people confuse them.

Automated check

The check is in the archive with the course files, and the commands below are run from the unpacked directory.

cd labs/a4-allocator
./check.sh my_alloc.c

The script builds your my_alloc.c together with tests.c and runs fifteen checks: sequences of allocations and frees with integrity checks (written data isn’t corrupted, blocks don’t overlap), alignment, realloc, coalescing of neighbors, and statistics. Then the same thing is repeated under AddressSanitizer.

Common mistakes

No alignment. The address malloc returns must be aligned for the strictest type, that is alignof(max_align_t), usually 16 bytes. Otherwise SSE instructions on such a pointer will fault.

The header gets corrupted. Writing one byte past the end of a block overwrites the neighbor’s header. Canaries protect against this (module 16); you can add them to yours too.

free(NULL) crashes. According to the standard, this is a perfectly valid operation that does nothing.

Coalescing only to the right. Half of the adjacent pairs stay uncoalesced, and fragmentation grows twice as fast as it should.

Comparing without warm-up. The first mmap brings page faults with it, so do several repetitions.

Further, if you’re curious

Add size classes as in a slab allocator and compare them with your two strategies. Or replace the system malloc via LD_PRELOAD and run a real program on it.