Loading...
Searching...
No Matches
MemoryMap.h
/*
* Copyright (C) 2010 Regents of the University of Michigan
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
#ifndef __MEMORYMAP_H
#define __MEMORYMAP_H
#include <sys/types.h>
#include <fcntl.h>
#if defined(_WIN32)
#include <windows.h>
#endif
///
/// 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.
///
///
class MemoryMap
{
#if defined(_WIN32)
HANDLE file_handle;
HANDLE map_handle;
DWORD page_size;
#else
int fd;
size_t page_size;
#endif
off_t offset;
size_t mapped_length;
size_t total_length;
bool useMemoryMapFlag;
public:
void *data;
MemoryMap();
virtual ~MemoryMap();
void debug_print();
void constructor_clear();
void destructor_clear();
virtual bool allocate();
/// open a previously created mapped vector
///
/// useMemoryMapFlag will determine whether it
/// uses mmap() or malloc()/read() to populate
/// the memory
virtual bool open(const char * file, int flags = O_RDONLY);
/// 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).
//
virtual bool create(const char * file, size_t size);
/// 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.
//
virtual bool create(size_t size);
bool close();
void test();
size_t length()
{
return mapped_length;
}
char operator[](unsigned int index)
{
return ((char *)data)[index];
};
int prefetch(); // force pages into RAM
//
// set or unset use of mmap() call in ::open().
// This flag must be set before ::open() is called,
// if it is called afterwards, it has no effect.
//
void useMemoryMap(bool flag=true)
{
useMemoryMapFlag = flag;
}
};
#endif
MemoryMap::open
virtual bool open(const char *file, int flags=O_RDONLY)
open a previously created mapped vector
Definition MemoryMap.cpp:156
MemoryMap::create
virtual bool create(const char *file, size_t size)
create the memory mapped file on disk
Definition MemoryMap.cpp:243