Loading...
Searching...
No Matches
MemoryMap Class Reference

There are a pair of related data structures in the operating system, and also a few simple algorithms that explain why your processes are waiting forever. More...

`#include <MemoryMap.h>`

Inheritance diagram for MemoryMap:
[legend]

## Public Member Functions

void | debug_print ()
void | constructor_clear ()
void | destructor_clear ()
virtual bool | allocate ()
virtual bool | open (const char *file, int flags=O_RDONLY)
| open a previously created mapped vector
virtual bool | create (const char *file, size_t size)
| create the memory mapped file on disk
virtual bool | create (size_t size)
| store in allocated memory (malloc), not mmap:
bool | close ()
void | test ()
size_t | length ()
char | operator[] (unsigned int index)
int | prefetch ()
void | useMemoryMap (bool flag=true)

## Public Attributes

void * | data

## Detailed Description

There are a pair of related data structures in the operating system, and also a few simple algorithms that explain why your processes are waiting forever.

The symptom you have is that they are getting little or no CPU time, as shown in the command 'top'. The machine will appear to have available CPU time (look at the Cpu(s): parameter - if less than 100%, you have available CPU). The real key, however, is to look at the 'top' column with the label 'S' - that is the status of the process, and crucial to understanding what is going on.

In your instance, the 'S' column for your karma jobs is 'D', which means it is waiting for data. This is because the process is doing something that is waiting for the filesystem to return data to it. Usually, this is because of a C call like read() or write(), but it also happens in large processes where memory was copied to disk and re-used for other purposes (this is called paging).

So, a bit of background on the operating system... there is a CPU secheduler that takes a list of waiting processes, and picks one to run - if the job is waiting for the disk, there is no point in picking it to run, since it is blocked, waiting for the disk to return data. The scheduler marks the process with 'D' and moves on to the next process to schedule.

In terms of data structures that we care about for this example, there are two that we care about. First is a linear list of disk buffers that are stored in RAM and controlled by the operating system. This is usually called the disk buffer pool. Usually, when a program asks for data from the disk, this list can be scanned quickly to see if the data is already in RAM - if so, no disk operation needs to take place.

Now in the case of the normal Unix read() and write() calls, when the operating system is done finding the page, it copies the data into a buffer to be used by the process that requested it (in the case of a read() - a write() is the opposite). This copy operation is slow and inefficient, but gets the job done.

So overall, you gain some efficiency in a large memory system by having this disk buffer pool data structure, since you aren't re-reading the disk over and over to get the same data that you already have in RAM. However, it is less efficient than it might be because of the extra buffer copying.

Now we come to memory mapped files, and karma. The underlying system call of interest to us is mmap(), and is in MemoryMap.cpp. What it does and how it works are important to understanding the benefits of it, and frankly, most people don't care about it because it is seemingly complex.

Two things are important to know: firstly, there is a data structure in the CPU called the page table, which is mostly contained in the CPU hardware itself. All memory accesses for normal user processes like karma go through this hardware page table. Secondly, it is very fast for the operating system to put together a page table that 'connects' a bunch of memory locations in your user programs address space to the disk buffer pool pages.

The combination of those two facts mean that you can implement a 'zero copy' approach to reading data, which means that the data that is in the disk buffer pool is directly readable by the program without the operating system ever having to actually copy the data, like it does for read() or write().

So the benefit of mmap() is that when the underlying disk pages are already in the disk buffer pool, a hardware data structure gets built, then the program returns, and the data is available at full processor speed with no intervening copy of the data, or waiting for disk or anything else. It is as near to instantaneous as you can possibly get. This works whether it is 100 bytes or 100 gigabytes.

So, the last part of the puzzle is why your program winds up in 'D' (data wait), and what to do about it.

The disk buffer pool is a linear list of blocks ordered by the time and date of access. A process runs every once in awhile to take the oldest of those pages, and free them, during which it also has to update the hardware page tables of any processes referencing them.

So on wonderland, most file access (wget, copy, md5sum, anything else) is constantly putting new fresh pages at the front of the list, and karma index files, having been opened awhile ago, are prime candidates for being paged out. The reason they get paged out as far as I know is that in any given second of execution, nowhere near the entire index is getting accessed... so at some point, at least one page gets sent back to disk (well, flushed from RAM). Once that happens, a cascading effect happens, where the longer it waits, the older the other pages get, then the more that get reclaimed, and the slower it gets, until karma is at a standstill, waiting for pages to be brought back into RAM.

Now in an ideal world, karma would rapidly recover, and it can... sometimes. The problem is that your karma job is accessing data all over that index, and it is essentially looking like a pure random I/O to the underlying filesystem. There is about a 10 to 1 performance difference between accessing the disk sequentially as compared to randomly.

So to make karma work better, the first thing I do when starting karma is force it to read all of the disk pages in order. This causes the entire index to be forced into memory in order, so it is forcing sequential reads, which is the best case possible. There are problems, for example if three karma jobs start at once, the disk I/O is no longer as purely sequential as we would like. Also, if the filesystem is busy taking care of other programs, even if karma thinks it is forcing sequential I/O, the net result looks more random. This happens when the system is starting to break down (thrashing) and it will certainly stall, or look very very slow, or crash.

The upshot of all of this is that when a single reference is shared, it is more likely that all the pages will be in the disk buffer pool to begin with, and thereby reduce startup time to nearly zero. It is also the ideal situation in terms of sharing the same reference among say 24 copies of karma on wonderland - the only cost is the hardware page table that gets set up to point to all of the disk buffers.

As I mentioned a paragraph back, the pages can still get swapped out, even with dozens of karma jobs running. A workaround I created is a program in utilities called mapfile - it simply repeatedly accesses the data in sequential order to help ensure that all of the pages are at the head of the disk buffer pool, and therefore less likely to get swapped out.

The benefit of such a program (mapfile) is greater on wonderland, where a lot of processes are competing for memory and disk buffers.

Definition at line 155 of file MemoryMap.h.

## Constructor & Destructor Documentation

## MemoryMap()

MemoryMap::MemoryMap | ( |  | ) |

Definition at line 43 of file MemoryMap.cpp.

{
constructor_clear();
#if defined(_WIN32)
SYSTEM_INFO sysinfo = {0};
::GetSystemInfo(&sysinfo);
DWORD cbView = sysinfo.dwAllocationGranularity;
#else
page_size = sysconf(_SC_PAGE_SIZE);
#endif
}

## ~MemoryMap()

MemoryMap::~MemoryMap | ( |  | ) |

virtual

Definition at line 55 of file MemoryMap.cpp.

{
destructor_clear();
};

## Member Function Documentation

## allocate()

bool MemoryMap::allocate | ( |  | ) |

virtual

Definition at line 118 of file MemoryMap.cpp.

{
data = (void *) malloc(mapped_length);
if (data == NULL)
{
#ifdef __WIN32__
::CloseHandle(file_handle);
#else
::close(fd);
#endif
perror("MemoryMap::open");
constructor_clear();
return true;
}
#ifdef __WIN32__
DWORD resultSize = 0;
ReadFile(file_handle, data, mapped_length, &resultSize, NULL);
#else
size_t resultSize = read(fd, data, mapped_length);
#endif
if ( resultSize != mapped_length)
{
#ifdef __WIN32__
::CloseHandle(file_handle);
#else
::close(fd);
#endif
perror("MemoryMap::open");
constructor_clear();
return true;
}
return false;
}

## close()

bool MemoryMap::close | ( |  | ) |

Definition at line 324 of file MemoryMap.cpp.

{
destructor_clear();
return false;
}

## constructor_clear()

void MemoryMap::constructor_clear | ( |  | ) |

Definition at line 74 of file MemoryMap.cpp.

{
#if defined(_WIN32)
file_handle = NULL;
map_handle = NULL;
#else
fd = -1;
#endif
data = (void *) NULL;
offset = 0;
mapped_length = 0;
total_length = 0;
useMemoryMapFlag = true;
};

## create() [1/2]

bool MemoryMap::create | ( | const char * | file,
|  | size_t | size
| ) |  |

virtual

create the memory mapped file on disk

a file will be created on disk with the header filled in. The caller must now populate elements using (*this).set(index, value).

Definition at line 243 of file MemoryMap.cpp.

{
if (file==NULL)
{
data = calloc(size, 1);
return(data==NULL);
}
const char * message = "MemoryMap::create - problem creating file %s";
#ifdef __WIN32__
file_handle = CreateFile(file,
GENERIC_READ | GENERIC_WRITE,
FILE_SHARE_READ | FILE_SHARE_WRITE,
NULL,
CREATE_ALWAYS,
FILE_ATTRIBUTE_NORMAL,
NULL);
if (file_handle == INVALID_HANDLE_VALUE)
{
fprintf(stderr, message, file);
constructor_clear();
return true;
}
SetFilePointer(file_handle, size - 1, NULL, FILE_BEGIN);
char dummy = 0;
DWORD check = 0;
WriteFile(file_handle, &dummy, 1, &check, NULL);
if (check != 0)
{
CloseHandle(file_handle);
DeleteFile(file);
fprintf(stderr, message, file);
constructor_clear();
return true;
}
CloseHandle(file_handle);
open(file, O_RDWR);
#else
fd = ::open(file, O_RDWR|O_CREAT|O_TRUNC, 0666);
if(fd == -1)
{
fprintf(stderr, message, file);
constructor_clear();
return true;
}
lseek(fd, (off_t) size - 1, SEEK_SET);
char dummy = 0;
if(write(fd, &dummy, 1)!=1)
{
fprintf(stderr, message, file);
constructor_clear();
return true;
}
data = ::mmap(NULL, size, PROT_READ|PROT_WRITE,
MAP_SHARED, fd, offset);
if (data == MAP_FAILED)
{
::close(fd);
unlink(file);
fprintf(stderr, message, file);
constructor_clear();
return true;
}
mapped_length = total_length = size;
#endif
return false;
}
MemoryMap::open
virtual bool open(const char *file, int flags=O_RDONLY)
open a previously created mapped vector
Definition MemoryMap.cpp:156

References open().

Referenced by MemoryMapArray< elementT, indexT, cookieVal, versionVal, accessorFunc, setterFunc, elementCount2BytesFunc, arrayHeaderClass >::create(), and create().

## create() [2/2]

bool MemoryMap::create | ( | size_t | size | ) |

virtual

store in allocated memory (malloc), not mmap:

This is for code that needs to more flexibly the case when an mmap() file might be available, but if it is not, we want to load it as a convenience to the user. GenomeSequence::populateDBSNP does exactly this.

Definition at line 319 of file MemoryMap.cpp.

{
return create(NULL, size);
}
MemoryMap::create
virtual bool create(const char *file, size_t size)
create the memory mapped file on disk
Definition MemoryMap.cpp:243

References create().

## debug_print()

void MemoryMap::debug_print | ( |  | ) |

Definition at line 60 of file MemoryMap.cpp.

{
#if defined(_WIN32)
std::cout << "fd = " << file_handle << std::endl;
#else
std::cout << "fd = " << fd << std::endl;
#endif
std::cout << "data = 0x" << std::hex << data << std::endl;
std::cout << "offset = 0x" << std::hex << offset << std::endl;
std::cout << "mapped_length = 0x" << std::hex << mapped_length << std::endl;
std::cout << "total_length = 0x" << std::hex << total_length << std::endl;
std::cout << "page_size = 0x" << std::hex << page_size << std::endl;
};

## destructor_clear()

void MemoryMap::destructor_clear | ( |  | ) |

Definition at line 89 of file MemoryMap.cpp.

{
#if defined(_WIN32)
if (data!=NULL)
{
// free windows mapped object
::UnmapViewOfFile((LPVOID) data);
}
if (map_handle != NULL)
::CloseHandle(map_handle);
if (file_handle != NULL)
::CloseHandle(file_handle);
#else
if (data!=NULL)
{
// free unix mapped object
munmap(data, mapped_length);
}
// free unix resources
if (fd!=-1)
{
::close(fd);
}
#endif
constructor_clear();
}

## length()

size_t MemoryMap::length | ( |  | ) |

inline

Definition at line 211 of file MemoryMap.h.

{
return mapped_length;
}

## open()

bool MemoryMap::open | ( | const char * | file,
|  | int | flags = `O_RDONLY`
| ) |  |

virtual

open a previously created mapped vector

useMemoryMapFlag will determine whether it uses mmap() or malloc()/read() to populate the memory

Reimplemented in MemoryMapArray< elementT, indexT, cookieVal, versionVal, accessorFunc, setterFunc, elementCount2BytesFunc, arrayHeaderClass >, and GenomeSequence.

Definition at line 156 of file MemoryMap.cpp.

{
const char * message = "MemoryMap::open - problem opening file %s";
#if defined(_WIN32)
file_handle = CreateFile(file,
(flags==O_RDONLY) ? GENERIC_READ : (GENERIC_READ | GENERIC_WRITE),
FILE_SHARE_READ | FILE_SHARE_WRITE, // subsequent opens may either read or write
NULL,
OPEN_EXISTING,
FILE_ATTRIBUTE_NORMAL,
NULL);
if(file_handle == INVALID_HANDLE_VALUE)
{
fprintf(stderr, message, file);
constructor_clear();
return true;
}
LARGE_INTEGER file_size = {0};
::GetFileSizeEx(file_handle, &file_size);
mapped_length = total_length = file_size.QuadPart;
#else
struct stat buf;
fd = ::open(file, flags);
if ((fd==-1) || (fstat(fd, &buf) != 0))
{
fprintf(stderr, message, file);
constructor_clear();
return true;
}
mapped_length = total_length = buf.st_size;
#endif
if(!useMemoryMapFlag)
{
return allocate();
}
#if defined(_WIN32)
assert(offset == 0);
map_handle = CreateFileMapping(file_handle, NULL,
(flags==O_RDONLY) ? PAGE_READONLY : PAGE_READWRITE,
file_size.HighPart, // upper 32 bits of map size
file_size.LowPart, // lower 32 bits of map size
NULL);
if(map_handle == NULL)
{
::CloseHandle(file_handle);
fprintf(stderr, message, file);
constructor_clear();
return true;
}
data = MapViewOfFile(map_handle,
(flags == O_RDONLY) ? FILE_MAP_READ : FILE_MAP_ALL_ACCESS,
0, 0, mapped_length);
if (data == NULL)
{
CloseHandle(map_handle);
CloseHandle(file_handle);
fprintf(stderr, message, file);
constructor_clear();
return true;
}
#else
data = ::mmap(NULL, mapped_length,
(flags == O_RDONLY) ? PROT_READ : PROT_READ | PROT_WRITE,
MAP_SHARED, fd, offset);
if (data == MAP_FAILED)
{
::close(fd);
fprintf(stderr, message, file);
constructor_clear();
return true;
}
#endif
return false;
}

References open().

Referenced by create(), open(), and MemoryMapArray< elementT, indexT, cookieVal, versionVal, accessorFunc, setterFunc, elementCount2BytesFunc, arrayHeaderClass >::open().

## operator[]()

char MemoryMap::operator[] | ( | unsigned int | index | ) |

inline

Definition at line 216 of file MemoryMap.h.

{
return ((char *)data)[index];
};

## prefetch()

int MemoryMap::prefetch | ( |  | ) |

Definition at line 349 of file MemoryMap.cpp.

{
int sum = 0;
size_t i;
for (i=0; i<mapped_length; i += page_size) sum += *(i + (char *) data);
return sum;
}

## test()

void MemoryMap::test | ( |  | ) |

Definition at line 330 of file MemoryMap.cpp.

{
int result;
result = this->open("test/test_memmap_data.txt");
assert(result == 0);
assert(data!=NULL);
assert(mapped_length == 183); // length of the above file
close();
// now try non memory mapped (direct slow file I/O)
useMemoryMap(false);
result = this->open("test/test_memmap_data.txt");
assert(result == 0);
assert(data!=NULL);
assert(mapped_length == 183); // length of the above file
close();
}

## useMemoryMap()

void MemoryMap::useMemoryMap | ( | bool | flag = `true` | ) |

inline

Definition at line 227 of file MemoryMap.h.

{
useMemoryMapFlag = flag;
}

## Member Data Documentation

## data

void* MemoryMap::data

Definition at line 171 of file MemoryMap.h.

The documentation for this class was generated from the following files:

- general/MemoryMap.h
- general/MemoryMap.cpp