c - mremap() よりもメモリページを移動する高速な方法は?

Question

私は mremap() を試してきました。仮想メモリページを高速で移動できるようにしたいと考えています。少なくともそれらをコピーするよりも高速です。メモリページを非常に高速に移動できることを利用できるアルゴリズムのアイデアがいくつかあります。問題は、以下のプログラムが mremap() が非常に遅いことを示していることです (少なくとも私の i7 ラップトップでは)。実際に同じメモリページをバイト単位でコピーする場合と比較して。

テストソースコードはどのように機能しますか? mmap() オン CPU キャッシュよりも大きい 256 MB の RAM。200,000 回繰り返します。各反復で、特定のスワップメソッドを使用して 2 つのランダムなメモリページをスワップします。mremap() ベースのページスワップメソッドを使用して 1 回だけ実行します。再度実行し、バイトごとのコピースワップメソッドを使用して時間を計ります。mremap() は 1 秒あたり 71,577 ページスワップしか管理しないのに対し、バイトごとのコピーは 1 秒あたりなんと 287,879 ページスワップを管理することがわかります。したがって、mremap() は、バイトごとのコピーよりも 4 倍遅くなります。

質問:

なぜ mremap() はとても遅いのですか?

より高速なユーザーランドまたはカーネルランドの呼び出し可能なページマッピング操作 API は他にありますか?

複数の連続していないページを 1 回の呼び出しで再マップできるようにする、別のユーザーランドまたはカーネルランドの呼び出し可能なページマッピング操作 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 回続けて、1 秒間に 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: 私が発見した modify_ldt() という関数を呼び出す WIP コードを追加しました。man ページは、ページ操作が可能である可能性があることを示唆しています。ただし、何を試しても、読み取ったバイト数を返すことを期待している場合、関数は常にゼロを返します。'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() が非常に遅い理由を説明するのに役立ちます。

「Intel メモリ管理の紹介」は、メモリページマッピングの理論を紹介する優れた入門書です。

「Intel 仮想メモリの主要な概念」では、独自の OS を作成する予定がある場合に備えて、すべてがどのように機能するかをより詳細に示しています :-)

「Linux カーネルでのページテーブルの共有」では、複雑な Linux メモリページマッピングのアーキテクチャ上の決定と、それらがパフォーマンスに与える影響について説明しています。

3 つの参考資料をすべてまとめて見ると、これまでカーネルアーキテクトがメモリページマッピングをユーザーランドに効率的に公開する努力がほとんど行われてこなかったことがわかります。カーネル内でも、ページテーブルの操作は最大 3 つのロックを使用して行う必要があり、これは遅くなります。

今後は、ページテーブル自体が 4k ページで構成されているため、カーネルを変更して、特定のページテーブルページが特定のスレッドに固有であり、スレッドが実行されている間はロックなしでアクセスできると想定できるようにすることができます。処理する。これにより、ユーザーランドを介した特定のページテーブルページの非常に効率的な操作が容易になります。しかし、これは元の質問の範囲外になります。

score 11 · Accepted Answer

mremap単一の4kページを交換するのに効率的だと思う理由は何ですか？少なくとも、単一の値（pidなど）を読み取ってそれを返すだけでもカーネルスペースへのラウンドトリップは、4kのデータを移動するよりもコストがかかります。そして、それは、メモリを再マッピングするためのキャッシュ無効化/ TLBコストに到達する前です。これについては、この回答で対処するのに十分な理解はありませんが、かなりのコストがかかるはずです。

mremap基本的に1つのことに役立ちます。それは、によって処理された大規模な割り当ての実装reallocです。そして大まかに言って、私はおそらく少なくとも100kを意味します。mmap

c - mremap() よりもメモリ ページを移動する高速な方法は?

2 に答える 2

Related

Reference

c - mremap() よりもメモリページを移動する高速な方法は?