# 缺页优化

On operating systems like Linux with demand-paging support, an mmap call only modifies the page tables.

It makes sure that, for file-backed pages, the underlying data can be found and, for anonymous memory, that, on access, pages initialized with zeros are provided.

No actual memory is allocated at the time of the mmap call.

## 开辟内存

The allocation part happens when a memory page is first accessed, either by reading or writing data, or by executing code.

In response to the ensuing page fault, the kernel takes control and determines, using the page table tree, the data which has to be present on the page.

This resolution of the page fault is not cheap, but it happens for every single page which is used by a process.

## 降低缺页的开销

To minimize the cost of page faults, the total number of used pages has to be reduced.

Optimizing the code for size will help with this.

To reduce the cost of a specific code path (for instance, the start-up code), it is also possible to rearrange code so that, in that code path, the number of touched pages is minimized.

It is not easy to determine the right order, though.

# 作者编写的工具

The author wrote a tool, based on the valgrind toolset, to measure page faults as they happen.

Not the number of page faults, but the reason why they happen.

The pagein tool emits information about the order and timing of page faults.

## 输出例子

The output, written to a file named pagein.<PID>, looks as in Figure 7.8.

0 0x3000000000 C    0 0x3000000B50: (within /lib64/ld-2.5.so)
1 0x 7FF000000 D    3320 0x3000000B53: (within /lib64/ld-2.5.so)
2 0x3000001000 C    58270 0x3000001080: _dl_start (in /lib64/ld-2.5.so)
3 0x3000219000 D    128020 0x30000010AE: _dl_start (in /lib64/ld-2.5.so)
4 0x300021A000 D    132170 0x30000010B5: _dl_start (in /lib64/ld-2.5.so)
5 0x3000008000 C    10489930 0x3000008B20: _dl_setup_hash (in /lib64/ld-2.5.so)
6 0x3000012000 C    13880830 0x3000012CC0: _dl_sysdep_start (in /lib64/ld-2.5.so)
7 0x3000013000 C    18091130 0x3000013440: brk (in /lib64/ld-2.5.so)
8 0x3000014000 C    19123850 0x3000014020: strlen (in /lib64/ld-2.5.so)
9 0x3000002000 C    23772480 0x3000002450: dl_main (in /lib64/ld-2.5.so)


The second column specifies the address of the page which is pagedin.

Whether it is a code or data page is indicated in the third column, which contains ‘C’ or ‘D’ respectively.

The fourth column specifies the number of cycles which passed since the first page fault.

The rest of the line is valgrind’s attempt to find a name for the address which caused the page fault.

The address value itself is correct but the name is not always accurate（准确） if no debug information is available.

## 例子解释

In the example in Figure 7.8, execution starts at address 3000000B5016, which forces the system to page in the page at address 300000000016.

Shortly after that, the page after this is also brought in; the function called on that page is _dl_start.

The initial code accesses a variable on page 7FF0000001.

This happens just 3,320 cycles after the first page fault and is most likely the second instruction of the program (just three bytes after the first instruction).

If one looks at the program, one will notice that there is something peculiar about this memory access.

The instruction in question is a call instruction, which does not explicitly load or store data.

It does store the return address on the stack, though, and this is exactly what happens here.

This is not the official stack of the process, though, it is valgrind’s internal stack of the application.

This means when interpreting the results of pagein it is important to keep in mind that valgrind introduces some artifacts.

### 输出信息

The output of pagein can be used to determine which code sequences should ideally be adjacent in the program code.

A quick look at the /lib64/ld-2.5.so code shows that the first instructions immediately call the function _dl_start, and that these two places are on different pages.

Rearranging the code to move the code sequences onto the same page can avoid–or at least delay–a page fault.

It is, so far, a cumbersome process to determine what the optimal code layout should be.

Since the second use of a page is, by design, not recorded, one needs to use trial and error to see the effects of a change.

Using call graph analysis, it is possible to guess about possible call sequences;

this might help speed up the process of sorting the functions and variables.

# 调用序列的查看

At a very coarse（粗） level, the call sequences can be seen by looking a the object files making up the executable or DSO.

Starting with one or more entry points (i.e., function names), the chain of dependencies can be computed.

Without much effort this works well at the object file level.

In each round, determine which object files contain needed functions and variables.

The seed set has to be specified explicitly.

Then determine all undefined references in those object files and add them to the set of needed symbols.

Repeat until the set is stable.

## 确定执行顺序

The second step in the process is to determine an order.

The various object files have to be grouped together to fill as few pages as possible.

As an added bonus, no function should cross over a page boundary.

A complication in all this is that, to best arrange the object files, it has to be known what the linker will do later.

The important fact here is that the linker will put the object files into the executable or DSO in the same order in which they appear in the input files (e.g., archives), and on the command line.

This gives the programmer sufficient control.

## 重排序

For those who are willing to invest a bit more time, there have been successful attempts at reordering made using automatic call tracing via the __cyg_profile_func_enter and __cyg_profile_func_exit hooks gcc inserts when called with the -finstrument-functions option.

See the gcc manual for more information on these __cyg_* interfaces.

By creating a trace of the program execution, the programmer can more accurately determine the call chains（程序员可以更准确地确定调用链）.

The results in are a 5% decrease in start-up costs, just through reordering of the functions.

The main benefit is the reduced number of page faults, but the TLB cache also plays a role–an increasingly important role given that, in virtualized environments, TLB misses become significantly more expensive.

By combining the analysis of the pagein tool with the call sequence information, it should be possible to optimize certain phases of the program (such as start-up) to minimize the number of page faults.

# Linux

The Linux kernel provides two additional mechanisms to avoid page faults.

## mmap 标志

The first one is a flag for mmap which instructs the kernel to not only modify the page table but, in fact, to pre-fault all the pages in the mapped area.

This is achieved by simply adding the MAP_POPULATE flag to the fourth parameter of the mmap call.

This will cause the mmap call to be significantly more expensive, but, if all pages which are mapped by the call are being used right away, the benefits can be large.

Instead of having a number of page faults, which each are pretty expensive due to the overhead incurred by synchronization requirements etc., the program would have one, more expensive, mmap call.

The use of this flag has disadvantages, though, in cases where a large portion of the mapped pages are not used soon (or ever) after the call.

Mapped, unused pages are obviously a waste of time and memory.

Pages which are immediately pre-faulted and only much later used also can clog up the system.

The memory is allocated before it is used and this might lead to shortages of memory in the meantime.

On the other hand, in the worst case, the page is simply reused for a new purpose (since it has not been modified yet), which is not that expensive but still, together with the allocation, adds some cost.

The granularity of MAP_POPULATE is simply too coarse.

MAP_POPULATE的粒度太粗糙了。

And there is a second possible problem: this is an optimization;

it is not critical that all pages are, indeed, mapped in.

If the system is too busy to perform the operation the pre-faulting can be dropped.

Once the page is really used the program takes the page fault, but this is not worse than artificially creating resource scarcity.

## 另一种选择

This is a hint to of huge pages which should be reserved to the operating system that, in the near future, the program will need the page described in the call.

The kernel is free to ignore the advice, but it also can pre-fault pages.

### 优点

The advantage here is that the granularity is finer.

Individual pages or page ranges in any mapped address space area can be pre-faulted.

For memory-mapped files which contain a lot of data which is not used at runtime, this can have huge advantages over using MAP_POPULATE.

Beside these active approaches to minimizing the number of page faults, it is also possible to take a more passive approach which is popular with the hardware designers.

A DSO occupies neighboring pages in the address space, one range of pages each for the code and the data.

The smaller the page size, the more pages are needed to hold the DSO.

This, in turn, means more page faults, too.

Important here is that the opposite is also true.

For larger page sizes, the number of necessary pages for the mapping (or anonymous memory) is reduced; with it falls the number of page faults.

DSO占用地址空间中的相邻页面，每个页面范围用于代码和数据。

## 大部分页的设计

Most architectures support page sizes of 4k.

On IA-64 and PPC64, page sizes of 64k are also popular.

That means the smallest unit in which memory is given out is 64k.

The value has to be specified when compiling the kernel and cannot be changed dynamically (at least not at the moment).

The ABIs of the multiple-page-size architectures are designed to allow running an application with either page size.

The runtime will make the necessary adjustments, and a correctly-written program will not notice a thing.

Larger page sizes mean more waste through partially-used pages, but, in some situations, this is OK.

# 非常大的 page size 设计

Most architectures also support very large page sizes of 1MB or more.

Such pages are useful in some situations, too, but it makes no sense to have all memory given out in units that large.

The waste of physical RAM would simply be too large.

## 大页的优点

But very large pages have their advantages:

if huge data sets are used, storing them in 2MB pages on x86-64 would require 511 fewer page faults (per large page) than using the same amount of memory with 4k pages.

This can make a big difference.

The solution is to selectively request memory allocation which, just for the requested address range, uses huge memory pages and, for all the other mappings in the same process, uses the normal page size.

• 个人收获

## 价格方面

Huge page sizes come with a price, though.

Since the physical memory used for large pages must be continuous, it might, after a while, not be possible to allocate such pages due to memory fragmentation.

People are working on memory defragmentation and fragmentation avoidance, but it is very complicated.

## 系统启动的场景

For large pages of, say, 2MB the necessary 512 consecutive pages are always hard to come by, except at one time: when the system boots up.

This is why the current solution for large pages requires the use of a special filesystem, hugetlbfs.

This pseudo filesystem is allocated on request by the system administrator by writing the number of huge pages which should be reserved to

/proc/sys/vm/nr_hugepages


ps: 因为在系统启动初期，很多信息都是空的。所以会有很多连续的内存供使用。

# 操作失败的场景

This operation might fail if not enough continuous memory can be located.

The situation gets especially interesting if virtualization is used.

A virtualized system using the VMM model does not directly administrate physical memory and, therefore, cannot by itself allocate the hugetlbfs.

It has to rely on the VMM, and this feature is not guaranteed to be supported.

For the KVM model, the Linux kernel running the KVM module can perform the hugetlbfs allocation and possibly pass a subset of the pages thus allocated on to one of the guest domains.

## 程序需要大页

Later, when a program needs a large page, there are multiple possibilities:

• the program can use the System V shared memory interfaces with the SHM_HUGETLB flag.

• a filesystem of type hugetlbfs can actually be mounted and the program can then create a file under the mount point and use mmap to map one or more pages as anonymous memory.

## 场景1

In the first case, the hugetlbfs need not be mounted.

Code requesting one or more large pages could look like this:

key_t k = ftok("/some/key/file", 42);
int id = shmget(k, LENGTH,
SHM_HUGETLB|IPC_CREAT
|SHM_R|SHM_W);
void *a = shmat(id, NULL, 0);


The critical parts of this code sequence are the use of the SHM_HUGETLB flag and the choice of the right value for LENGTH, which must be a multiple of the huge page size for the system.

Different architectures have different values.

The use of the System V shared memory interface has the nasty problem of depending on the key argument to differentiate (or share) mappings.

The ftok interface can easily produce conflicts which is why, if possible, it is better to use other mechanisms.

## 最佳实践

If the requirement to mount the hugetlbfs filesystem is not a problem, it is better to use it instead of System V shared memory.

The only real problems with using the special filesystem are that the kernel must support it, and that there is no standardized mount point yet.

Once the filesystem is mounted, for instance at /dev/hugetlb, a program can make easy use of it:

int fd = open("/dev/hugetlb/file1",O_RDWR|O_CREAT, 0700);
void *a = mmap(NULL, LENGTH,PROT_READ|PROT_WRITE,fd, 0);


By using the same file name in the open call, multiple processes can share the same huge pages and collaborate.

It is also possible to make the pages executable, in which case the PROT_EXEC flag must also be set in the mmap call.

As in the System V shared memory example, the value of LENGTH must be a multiple of the system’s huge page size.

## 防御性写

A defensively-written program (as all programs should be) can determine the mount point at runtime using a function like this:

char *hugetlbfs_mntpoint(void) {
char *result = NULL;
FILE *fp = setmntent(_PATH_MOUNTED, "r");
if (fp != NULL) {
struct mntent *m;
while ((m = getmntent(fp)) != NULL)
if (strcmp(m->mnt_fsname,
"hugetlbfs") == 0) {
result = strdup(m->mnt_dir);
break; }
endmntent(fp);
}
return result;
}


More information for both these cases can be found in the hugetlbpage.txt file which comes as part of the kernel source tree.

The file also describes the special handling needed for IA-64.

## 大页的优点图示

To illustrate the advantages of huge pages, Figure 7.9 shows the results of running the random Follow test for NPAD=0.

This is the same data shown in Figure 3.15, but, this time, we measure the data also with memory allocated in huge pages.

As can be seen the performance advantage can be huge.

For 220 bytes the test using huge pages is 57% faster.

This is due to the fact that this size still fits completely into one single 2MB page and, therefore, no DTLB misses occur.

### 效益说明

After this point, the winnings are initially smaller but grow again with increasing working set size.

The huge pages test is 38% faster for the 512MB working set size.

The curve for the huge page test has a plateau at around 250 cycles.

Beyond working sets of 227 bytes, the numbers rise significantly again.

The reason for the plateau is that 64 TLB entries for 2MB pages cover 227 bytes.

## 大页的主要成本 TLB 未命中

As these numbers show, a large part of the costs of using large working set sizes comes from TLB misses.

Using the interfaces described in this section can pay off bigtime.

The numbers in the graph are, most likely, upper limits, but even real-world programs show a significant speed-up.

Databases, since they use large amounts of data, are among the programs which use huge pages to- day.

# 大页的局限性

There is currently no way to use large pages to map filebacked data.

There is interest in implementing this capability, but the proposals made so far all involve explicitly using large pages, and they rely on the hugetlbfs filesystem.

This is not acceptable: large page use in this case must be transparent.

The kernel can easily determine which mappings are large and automatically use large pages.

A big problem is that the kernel does not always know about the use pattern.

If the memory, which could be mapped as a large page, later requires 4k-page granularity (for instance, because the protection of parts of the memory range is changed using mprotect) a lot of precious resources, in particular the linear physical memory, will have been wasted.

So it will certainly be some more time before such an approach is successfully implemented.

P89