Out Of Memory Problems -

C:>VirtualAllocateOneByte
Allocated 32664 bytes.
Last error code 8

Finally, we may actually be out of physical memory. Every byte of physical memory might be in use by some process, device drive or the OS itself. However most operating systems support "memory overcommit" where more memory can be allocated than the machine physically supports. The 'extra' memory is provided by swapping memory out to disk and transparently re-mapping the physical memory addresses freed up to other addresses in the same, or another, application.

So even if we are out of physical memory we might still get something back from an allocation request to the operating system. The OS may swap some existing data out to disk and give us the memory so freed up. Or the OS might reserve some space in the swap file and return us an address range that will only be swapped in when it is accessed. Different operating systems make different decisions on how liberal they are at this point. Each operating system seems to have its own preferred approach and many provide configurable choices!

Windows takes a conservative approach and only returns memory if it either really has the memory or it has successfully reserved space in the swap file; when you hit the swap space limits the allocation fails. This is a conservative policy and means the swap file expands to be bigger than may be strictly necessary but on the positive side you can't get a process failure when you later try to write to the allocated memory. Solaris also uses a conservative ('eager') approach by default but this can be configured (see the 'vm_swap_eager' attribute). Linux takes a more liberal approach (The operating system that likes to say 'Yes') and by default returns allocated memory with only a quick check for 'obvious' overcommitment. This has the advantage that the swap space usage is less but the disadvantage that a subsequent attempt to actually use the memory may fail because there is no room to expand the swap space. Later versions of Linux provide some kernel configuration settings (see vm.overcommit_memory and vm.overcommit_ratio) that allow you to configure the behaviour. You may (or may not) find this extract from the relevant man pages reassuring: "Depending on the percentage you use, in most situations this means a process will not be killed while accessing pages but will receive errors on memory allocation as appropriate."

Lastly, many operating systems allow the user to reserve spaces in the address range and commit and free individual pages in the range as required. Many operating systems also use this technique to manage the stack - the stack is created in an address range of the maximum stack size but marked as 'reserved' and actual pages of memory are only committed to the stack as it grows. This 'lazy allocation' avoids up-front use of megabytes of memory for simple programs that have a shallow stack.

Putting it all together

In the problem cases that inspired the article the limiting factor was the address space, but for slightly different reasons in each case.

In one case the application used a number of vectors internally and, after some analysis, we discovered that the out of memory problem occurred when a large vector had an additional item added. This extra item hit the current capacity of the vector and so required a re-allocation of the underlying memory buffer. The buffer was 100 Mb in size and the vector class used had a simple doubling algorithm when resizing which meant a request was made for 200 Mb of contiguous memory for the new buffer. This request failed because there was no single free section in the address range that was this large. The application failed with an out of memory error although it had only allocated 800 Mb or so of memory and was running on a machine with 4 Gb of physical memory. This was on Windows and I failed (then) to find a standard tool that helped analyse this problem. The debugger Windbg from Microsoft Debugging Tools for Windows came close with its "!vadump" command but this simply prints the details of each memory region allocation by the operating system to the process and I wanted to find the largest contiguous free region. Eventually I wrote a quick tool that scanned the address range and reported the size of the largest free memory region; implementation of a derivative of this tool is described below.

One solution to this problem is to replace the vector (that requires a single memory range) with a container that allocates in chunks, such as the deque. Another solution is to preset the capacity of the vector to the final allocation size, but this is hard to do in general! In our case we changed the resize algorithm for large vectors to avoid the doubling and hence reduce the need for such large allocations.

In a different case we had a message switching application written in Java running on a 32bit JVM on Solaris. The application would generate out of memory errors even though tools such as 'top' showed our application was using less than 2 Gb of memory (out of a possible limit over well over 3Gb) and we had many gigabytes of free physical memory on the machine.

The fundamental problem here also turned out to be running out of address space - our application was creating a pair of threads for each connection it was managing and each thread was reserving a stack of 1 MB. The threads all had a shallow call depth, so in fact only the first 8 Kb of each stack was actually being committed, the rest of each stack was just left as reserved address space. By the time you have a thousand threads in the program that means nearly 1 Gb of address space reserved and hence not available for other allocations.

There were three possible solutions we explored here. The first solution was to reduce the number of threads, but this proved hard in our case because the threads were being created by a third party library that we were not able to change. We explored reducing the size of the thread stack, but failed to find a mechanism that allowed us to do so (in some cases operating system APIs provide the feature, but higher level abstractions may not expose it to application code). The eventual solution we went for in this case was to run in a 64 bit virtual machine. This slightly increased the actual amount of allocated memory used but enormously increased the available address range. The 1 Gb of reserved space drops from one quarter of the whole range in a 32bit program to a tiny fraction of the available 64 bit address range.

However, we found in this case too a lack of standard tools that provided diagnostics for the 'out of addressability' problem. In this case we eventually looked at the data from the /proc pseudo-filesystem and used some scripting to identify the reserved memory ranges.

A Useful (Windows) Tool

Under the covers

The program expects a list of process IDs on the command line and simply prints the virtual address map, and a summary line, for each one.

The algorithm obtains the user-mode address range from GetSystemInfo and iterates through the range using VirtualQueryEx() to get the memory information for each address block. Once the complete range has been read the details for each block and the summary is produced (Note that the MEMORY_BASIC_INFORMATION structure holds additional information that this simple program does not display).

Here is some sample output from this program in action:

C:>virtmap 1812 Processing: 1812 8K at 00010000 committed 56K at 00012000 free 4K at 00020000 committed 60K at 00021000 free 240K at 00030000 reserved ... 4K at 7FFDF000 committed 4K at 7FFE0000 committed 60K at 7FFE1000 reserved Committed: 10Mb, reserved: 6Mb, free: 2031Mb (biggest: 1607Mb)

Here is the sample code itself (virtMap.cpp):

#include <windows.h>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <string>
#include <vector>

// This class holds the virtual memory map for a process
class VirtMap
{
public:
  VirtMap();
  int VirtMap::process( HANDLE hProcess );
  void printOn( std::ostream& os ) const;

private:
  void add( MEMORY_BASIC_INFORMATION const & mb );

  std::vector<MEMORY_BASIC_INFORMATION> m_info;
  ULONG m_commit;
  ULONG m_reserve;
  ULONG m_free;
  ULONG m_biggest;
};

// Stream a memory map
std::ostream & operator<<( std::ostream & os, VirtMap const & virtMap )
{
  virtMap.printOn( os );
  return os;
}

// Stream a memory block
std::ostream & operator<<( std::ostream &os, MEMORY_BASIC_INFORMATION const & mb)
{
  os << std::setw(8) << mb.RegionSize / 1024 << "K at " << mb.BaseAddress;
  switch( mb.State )
  {
    case MEM_COMMIT: os << " committed"; break;
    case MEM_FREE: os << " free"; break;
    case MEM_RESERVE: os << " reserved"; break;
  }
  return os;
}

// Class VirtMap implementation
VirtMap::VirtMap()
: m_commit( 0 )
, m_reserve( 0 )
, m_free( 0 )
, m_biggest( 0 )
{
}

// Handle a single process
int VirtMap::process( HANDLE hProcess )
{
  int ret(0);
  SYSTEM_INFO SystemInfo;
  GetSystemInfo( &SystemInfo );

  PVOID baseAddress( SystemInfo.lpMinimumApplicationAddress );

  while ( baseAddress < SystemInfo.lpMaximumApplicationAddress )
  {
    MEMORY_BASIC_INFORMATION mb = { 0 };
    if ( ! VirtualQueryEx( hProcess, baseAddress, &mb, sizeof( mb ) ) )
    {
      int ret = ::GetLastError();
      std::cerr << "Cannot query memory at: " << baseAddress << ": " << ret << std::endl;
      break;
    }
    add( mb );

    baseAddress = (PCHAR)mb.BaseAddress + mb.RegionSize;
  }
  return ret;
}

// Add an item to the memory map
void VirtMap::add( MEMORY_BASIC_INFORMATION const & mb )
{
  m_info.push_back( mb );

  if ( mb.State & MEM_FREE )
  {
    m_free += mb.RegionSize;
    if ( m_biggest < mb.RegionSize )
      m_biggest = mb.RegionSize;
  }
  else if ( mb.State & MEM_RESERVE )
  {
    m_reserve += mb.RegionSize;
  }
  else if ( mb.State & MEM_COMMIT )
  {
    m_commit += mb.RegionSize;
  }
}

// Print the memory map
void VirtMap::printOn( std::ostream& os ) const
{
static const ULONG megabyte = 1024L * 1024L;

  std::copy( m_info.begin(), m_info.end(), 
    std::ostream_iterator<MEMORY_BASIC_INFORMATION>(os, "\n" ) );

  os << "Committed: " << m_commit / megabyte << "Mb"
    ", reserved: " << m_reserve / megabyte << "Mb"
    ", free: " << m_free / megabyte << "Mb"
    " (biggest: " << m_biggest / megabyte << "Mb)";
}

int main( int argc, char **argv )
{
  int ret = 0;

  for ( int idx = 1; idx != argc; ++idx )
  {
    int const pid = atoi( argv[idx] );
    HANDLE const hProcess = OpenProcess( PROCESS_QUERY_INFORMATION, FALSE, pid );

    if ( hProcess == 0 )
    {
      ret = ::GetLastError();
      std::cerr << "Unable to open process " << pid << ", error: " << ret << std::endl;
      break;
    }
    else
    {
      std::cout << "Processing: " << pid << std::endl;
      VirtMap virtMap;
      ret = virtMap.process( hProcess );
      CloseHandle( hProcess );
      if ( ret != 0 )
        break;
      std::cout << virtMap << std::endl;
    }
  }

  return ret;
}

Conclusion

Notes and Resources

1. Newer Windows versions support the /3GB switch which potentially adds an extra gigabyte of addressability to a process
   See http://www.microsoft.com/whdc/system/platform/server/PAE/PAEmem.mspx for more details.
   
2. SysInternals is at http://technet.microsoft.com/en-us/sysinternals/.