CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 5 of 7 · 3 min read

Memory returned to the allocator

In plain words: When a shop sells an item back, the item goes on the shelf, not back to the wholesaler. The same holds for free: it returns the piece to the allocator's list, and the kernel is told only if a whole region at the end of the heap can be given back. The measurement below shows the effect, in resident set size (RSS, the pages of the process that are in memory now):

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static long rss_kb(void){ long p=0,r=0; FILE*f=fopen("/proc/self/statm","r");
  if(fscanf(f,"%ld %ld",&p,&r)!=2) r=0; fclose(f); return r*4; }
#define N 100000
int main(void){
  static char *a[N];
  for(int i=0;i<N;i++){ a[i]=malloc(1000); memset(a[i],1,1000); }
  printf("after 100,000 mallocs:      %ld kB\n", rss_kb());
  for(int i=0;i<N-1;i++) free(a[i]);            /* free all but the last */
  printf("after freeing all but one:  %ld kB\n", rss_kb());
  free(a[N-1]);
  printf("after freeing the last:     %ld kB\n", rss_kb());
  return 0; }
Moment RSS
Start 1,532 kB
After 100,000 allocations of 1,000 bytes 100,996 kB
After freeing every other block 100,996 kB
After freeing all blocks but the last 100,996 kB
After freeing the last block too 2,700 kB

Nearly all memory was free after the third step, and still the process held 100 MB. The one block at the top of the heap pinned the break: the break can move down only to the end of the last block in use. When that block was freed, the allocator saw a large free piece at the top, and trimmed the heap with brk.

The effect is a form of fragmentation at the level of the heap. Free space exists, and it is not at the end, so it cannot go back to the kernel. It is not lost, since a later malloc can reuse it. A long-running server that allocates and frees blocks of changing sizes can still end up with a heap much larger than the data it holds. Page 8 of this level shows how to measure this on a live process.

Heap fragmentation

Heap fragmentation is the state in which a heap contains much free space that cannot be returned to the kernel, or cannot serve a request, because it is spread among blocks that are still in use.

Example: a process that holds one live block at the top of a 100 MB heap keeps all 100 MB resident, though 99.999 MB is free.

Check yourself: 1. Why did RSS not fall when the first 99,999 blocks were freed? 2. Why did RSS fall at the last free? 3. Is the free space in the middle of the heap lost for the program?