c - 移动内存页面的方法比 mremap() 更快？

Question

我一直在尝试使用 mremap()。我希望能够高速移动虚拟内存页面。至少比复制它们的速度更高。我对算法有一些想法，可以利用能够非常快速地移动内存页面。问题是下面的程序显示 mremap() 非常慢 - 至少在我的 i7 笔记本电脑上 - 与实际逐字节复制相同的内存页面相比。

测试源代码是如何工作的？mmap() 256 MB RAM，比 CPU 上的缓存大。迭代 200,000 次。在每次迭代中，使用特定的交换方法交换两个随机内存页。使用基于 mremap() 的页面交换方法运行一次。使用逐字节复制交换方法再次运行并计时。事实证明，mremap() 每秒只管理 71,577 次页面交换，而逐字节复制每秒管理高达 287,879 次页面交换。所以 mremap() 比逐字节复制慢 4 倍！

问题：

为什么 mremap() 这么慢？

是否有另一个可能更快的用户级或内核级可调用页面映射操作 API？

是否有另一个用户级或内核级可调用页面映射操作 API 允许在一次调用中重新映射多个非连续页面？

有没有支持这种事情的内核扩展？

#include <stdio.h>
#include <string.h>
#define __USE_GNU
#include <unistd.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/errno.h>
#include <asm/ldt.h>
#include <asm/unistd.h>    

// gcc mremap.c && perl -MTime::HiRes -e '$t1=Time::HiRes::time;system(q[TEST_MREMAP=1 ./a.out]);$t2=Time::HiRes::time;printf qq[%u per second\n],(1/($t2-$t1))*200_000;'
// page size = 4096
// allocating 256 MB
// before 0x7f8e060bd000=0
// before 0x7f8e060be000=1
// before 0x7f8e160bd000
// after  0x7f8e060bd000=41
// after  0x7f8e060be000=228
// 71577 per second

// gcc mremap.c && perl -MTime::HiRes -e '$t1=Time::HiRes::time;system(q[TEST_COPY=1 ./a.out]);$t2=Time::HiRes::time;printf qq[%u per second\n],(1/($t2-$t1))*200_000;'
// page size = 4096
// allocating 256 MB
// before 0x7f1a9efa5000=0
// before 0x7f1a9efa6000=1
// before 0x7f1aaefa5000
// sizeof(i)=8
// after  0x7f1a9efa5000=41
// after  0x7f1a9efa6000=228
// 287879 per second

// gcc mremap.c && perl -MTime::HiRes -e '$t1=Time::HiRes::time;system(q[TEST_MEMCPY=1 ./a.out]);$t2=Time::HiRes::time;printf qq[%u per second\n],(1/($t2-$t1))*200_000;'
// page size = 4096
// allocating 256 MB
// before 0x7faf7c979000=0
// before 0x7faf7c97a000=1
// before 0x7faf8c979000
// sizeof(i)=8
// after  0x7faf7c979000=41
// after  0x7faf7c97a000=228
// 441911 per second

/*
 * Algorithm:
 * - Allocate 256 MB of memory
 * - loop 200,000 times
 *   - swap a random 4k block for a random 4k block
 * Run the test twice; once for swapping using page table, once for swapping using CPU copying!
 */

#define PAGES (1024*64)

int main() {
    int PAGE_SIZE = getpagesize();
    char* m = NULL;
    unsigned char* p[PAGES];
    void* t;

    printf("page size = %d\n", PAGE_SIZE);

    printf("allocating %u MB\n", PAGE_SIZE*PAGES / 1024 / 1024);
    m = (char*)mmap(0, PAGE_SIZE*(1+PAGES), PROT_READ | PROT_WRITE, MAP_SHARED  | MAP_ANONYMOUS, -1, 0);
    t = &m[PAGES*PAGE_SIZE];
    {
        unsigned long i;
        for (i=0; i<PAGES; i++) {
            p[i] = &m[i*PAGE_SIZE];
            memset(p[i], i & 255, PAGE_SIZE);
        }
    }

    printf("before %p=%u\n", p[0], p[0][0]);
    printf("before %p=%u\n", p[1], p[1][0]);
    printf("before %p\n", t);

    if (getenv("TEST_MREMAP")) {
        unsigned i;
        for (i=0; i<200001; i++) {
            unsigned p1 = random() % PAGES;
            unsigned p2 = random() % PAGES;
    //      mremap(void *old_address, size_t old_size, size_t new_size,int flags, /* void *new_address */);
            mremap(p[p2], PAGE_SIZE, PAGE_SIZE, MREMAP_FIXED | MREMAP_MAYMOVE, t    );
            mremap(p[p1], PAGE_SIZE, PAGE_SIZE, MREMAP_FIXED | MREMAP_MAYMOVE, p[p2]);
            mremap(t    , PAGE_SIZE, PAGE_SIZE, MREMAP_FIXED | MREMAP_MAYMOVE, p[p1]); // p3 no longer exists after this!
        } /* for() */
    }
    else if (getenv("TEST_MEMCPY")) {
        unsigned long * pu[PAGES];
        unsigned long   i;
        for (i=0; i<PAGES; i++) {
            pu[i] = (unsigned long *)p[i];
        }
        printf("sizeof(i)=%lu\n", sizeof(i));
        for (i=0; i<200001; i++) {
            unsigned p1 = random() % PAGES;
            unsigned p2 = random() % PAGES;
            unsigned long * pa = pu[p1];
            unsigned long * pb = pu[p2];
            unsigned char t[PAGE_SIZE];
            //memcpy(void *dest, const void *src, size_t n);
            memcpy(t , pb, PAGE_SIZE);
            memcpy(pb, pa, PAGE_SIZE);
            memcpy(pa, t , PAGE_SIZE);
        } /* for() */
    }
    else if (getenv("TEST_MODIFY_LDT")) {
        unsigned long * pu[PAGES];
        unsigned long   i;
        for (i=0; i<PAGES; i++) {
            pu[i] = (unsigned long *)p[i];
        }
        printf("sizeof(i)=%lu\n", sizeof(i));
        // int modify_ldt(int func, void *ptr, unsigned long bytecount);
        // 
        // modify_ldt(int func, void *ptr, unsigned long bytecount);
        // modify_ldt() reads or writes the local descriptor table (ldt) for a process. The ldt is a per-process memory management table used by the i386 processor. For more information on this table, see an Intel 386 processor handbook.
        // 
        // When func is 0, modify_ldt() reads the ldt into the memory pointed to by ptr. The number of bytes read is the smaller of bytecount and the actual size of the ldt.
        // 
        // When func is 1, modify_ldt() modifies one ldt entry. ptr points to a user_desc structure and bytecount must equal the size of this structure.
        // 
        // The user_desc structure is defined in <asm/ldt.h> as:
        // 
        // struct user_desc {
        //     unsigned int  entry_number;
        //     unsigned long base_addr;
        //     unsigned int  limit;
        //     unsigned int  seg_32bit:1;
        //     unsigned int  contents:2;
        //     unsigned int  read_exec_only:1;
        //     unsigned int  limit_in_pages:1;
        //     unsigned int  seg_not_present:1;
        //     unsigned int  useable:1;
        // };
        //
        // On success, modify_ldt() returns either the actual number of bytes read (for reading) or 0 (for writing). On failure, modify_ldt() returns -1 and sets errno to indicate the error.
        unsigned char ptr[20000];
        int result;
        result = modify_ldt(0, &ptr[0], sizeof(ptr)); printf("result=%d, errno=%u\n", result, errno);
        result = syscall(__NR_modify_ldt, 0, &ptr[0], sizeof(ptr)); printf("result=%d, errno=%u\n", result, errno);
        // todo: how to get these calls returning a non-zero value?
    }
    else {
        unsigned long * pu[PAGES];
        unsigned long   i;
        for (i=0; i<PAGES; i++) {
            pu[i] = (unsigned long *)p[i];
        }
        printf("sizeof(i)=%lu\n", sizeof(i));
        for (i=0; i<200001; i++) {
            unsigned long j;
            unsigned p1 = random() % PAGES;
            unsigned p2 = random() % PAGES;
            unsigned long * pa = pu[p1];
            unsigned long * pb = pu[p2];
            unsigned long t;
            for (j=0; j<(4096/8/8); j++) {
                t = *pa; *pa ++ = *pb; *pb ++ = t;
                t = *pa; *pa ++ = *pb; *pb ++ = t;
                t = *pa; *pa ++ = *pb; *pb ++ = t;
                t = *pa; *pa ++ = *pb; *pb ++ = t;
                t = *pa; *pa ++ = *pb; *pb ++ = t;
                t = *pa; *pa ++ = *pb; *pb ++ = t;
                t = *pa; *pa ++ = *pb; *pb ++ = t;
                t = *pa; *pa ++ = *pb; *pb ++ = t;
            }
        } /* for() */
    }

    printf("after  %p=%u\n", p[0], p[0][0]);
    printf("after  %p=%u\n", p[1], p[1][0]);
    return 0;
}

更新：所以我们不需要质疑“往返内核空间”有多快，这是一个进一步的性能测试程序，它表明我们可以连续调用 getpid() 3 次，每秒 81,916,192 次i7 笔记本电脑：

#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>

// gcc getpid.c && perl -MTime::HiRes -e '$t1=Time::HiRes::time;system(q[TEST_COPY=1 ./a.out]);$t2=Time::HiRes::time;printf qq[%u per second\n],(1/($t2-$t1))*100_000_000;'
// running_total=8545800085458
// 81916192 per second

/*
 * Algorithm:
 * - Call getpid() 100 million times.
 */

int main() {
    unsigned i;
    unsigned long running_total = 0;
    for (i=0; i<100000001; i++) {
        /*      123123123 */
        running_total += getpid();
        running_total += getpid();
        running_total += getpid();
    } /* for() */
    printf("running_total=%lu\n", running_total);
}

更新 2：我添加了 WIP 代码来调用我发现的名为 modify_ldt() 的函数。手册页暗示页面操作可能是可能的。但是，无论我尝试什么，当我期望它返回读取的字节数时，该函数总是返回零。'man modify_ldt' 表示“成功时，modify_ldt() 返回读取的实际字节数（用于读取）或 0（用于写入）。失败时，modify_ldt() 返回 -1 并设置 errno 以指示错误。” 任何想法（a） modify_ldt() 是否可以替代 mremap() ？(b) 如何让 modify_ldt() 工作？

score 19 · Accepted Answer

似乎没有比 memcpy() 更快的用户级机制来重新排序内存页面。mremap() 慢得多，因此仅对重新调整先前使用 mmap() 分配的内存区域的大小有用。

但是我听到你说页表必须非常快！并且用户级每秒可以调用数百万次内核函数！以下参考资料有助于解释为什么 mremap() 如此缓慢：

“An Introduction to Intel Memory Management”很好地介绍了内存页映射理论。

“英特尔虚拟内存的关键概念”更详细地展示了它是如何工作的，以防您打算编写自己的操作系统 :-)

“在 Linux 内核中共享页表”展示了一些困难的 Linux 内存页映射架构决策及其对性能的影响。

一起查看所有三个引用，我们可以看到，到目前为止，内核架构师几乎没有努力以有效的方式将内存页面映射公开给用户空间。即使在内核中，页表的操作也必须使用最多三个锁来完成，这会很慢。

展望未来，由于页表本身由 4k 页组成，因此可以更改内核，以便特定页表页对于特定线程是唯一的，并且可以假定在运行期间具有无锁访问过程。这将有助于通过用户空间对特定页表页面进行非常有效的操作。但这超出了原始问题的范围。

score 11 · Accepted Answer

是什么让您认为mremap交换单个 4k 页面可能是有效的？至少，即使只是读取单个值（如 pid）并返回它，往返内核空间也会比移动 4k 数据成本更高。那是在我们到达重新映射内存的缓存失效/TLB 成本之前，我不太了解这个答案，但应该有一些严重的成本。

mremap基本上对一件事很有用realloc：实现由mmap. 总的来说，我的意思是可能至少 100k。

c - 移动内存页面的方法比 mremap() 更快？

2 回答 2

Related

Reference