Memory Pages

Last time I talked about how, under Linux, a malloc call (or things based on malloc calls) might appear to succeed when they really should have failed. This leads to nasty runtime exceptions when you try to actually use the memory you requested.

If that seemed complicated, it turns out to actually be worse. The malloc and related calls have to get their memory from somewhere, and on modern systems that can lead to an entirely different set of problems.

Traditionally, a program had an sbrk value that was the “high water mark” for its code and static data. Everything from the sbrk location to the top of memory was fair game (remember, this is address space or logical addresses; no physical pages are used until you really try to do something). The system would typically set the stack to the top of memory and let it grow down. The heap (where malloc and friends get memory) would start at sbrk and grow up. You didn’t want these two regions to overlap, of course.

In these classic systems, allocating memory would cause the runtime library to increase the sbrk value by some fixed amount, and malloc then returns some part of that memory to the calling program. Future malloc calls will use more of the block until there is no more. At that point, the malloc call would further increase sbrk.

Today, things are often more complicated. The GNU library (common on desktop systems, but not universally used on embedded systems) has several tunable parameters (see The aim of most of these parameters is to avoid a common problem.

Suppose your malloc implementation grows the heap 1MB at a time. You merrily allocate 1MB and the library adds another 1MB to the heap (for a total of 2MB). In an ideal world, your program might release all of the memory it is using in that second megabyte and the library could return it to the operating system for use by other programs (or at least, to keep it from swapping out; see last week’s discussion about swapping dirty data pages).

How likely is that, though? If you have even a small allocation in that upper MB it will stop the library from returning all that memory to the operating system. The library parameters set how much memory malloc will try to grow (or shrink) the heap when necessary. It also defines M_MMAP_THRESHOLD. Any allocation above this size will not be put in the heap at all. At least, not in the classic sense. If you ask for a block of memory larger than this threshold, the system will allocate its own block big enough to fit the request using the mmap system call. When you free this memory block it will always go back to the operating system. This is mildly expensive in terms of speed, so you don’t want that threshold to be, say, one byte.

You can set these parameters using the library call mallopt. Changing them can make allocations faster or friendlier to the operating system, depending on your allocation patterns.

Notice that the heap allocations are still broken up (invisibly) into pages (normally 4K in length). The operating system won’t find physical pages until you actually use a page. Assume a 4K page size and consider the following call:

char *p=(char *)malloc(4096*10);

This nominally allocated 10 pages from the heap (and that may or may not cause the heap to grow). Of course, if the threshold is low enough, it could result in an mmap allocation, too. You don’t know and usually don’t care.

However, the kernel won’t actually back those pages up until you hit them as the code from last week demonstrated. So consider:


This code will cause two real pages to materialize, but the other eight pages are still theoretical (until you touch them). That’s why a comment in last week’s code:

#include <stdio.h>
#include <stdlib.h>
#define TOUCH 1       // 0 to not touch memory, 1 to touch
#define SIZE 1024     // bytes to allocate at once (assume <1 page)
int main(int argc, char *argv)
  unsigned i;
  char *p;
  do {
      p=(char *)malloc(SIZE);
      if (p) printf("%u\r", ++i);
          printf("Malloc failed after %u calls\n",i);
      } while (p);
   return 0;

mentions the test size is assumed to be less than one page in size.

Still not complicated enough? There is another wrinkle. The kernel normally has an OOM (Out of Memory) killer. When the kernel decides it is low on memory, the OOM killer swings into action and uses some heuristics to decide what process it should kill. This is usually bad when your X server or your web server gets the axe.

However, Android – based, of course, on Linux – uses a sophisticated OOM mechanism that is more suitable for small devices. It categorizes processes into several distinct groups and when memory starts getting low, the lowest priority processes get the axe. This is somewhat more predictable than the standard kernel’s algorithm.

I’ll talk more about the OOM killers next time. But the point this week is this: Know your library. It is easy to treat abstractions like malloc as “magic” – especially when you use them via another abstraction (like Java, for example). However, understanding what’s happening is often the difference between a system that works and performs well and one that doesn’t.