私は mremap() を試しています。仮想メモリ ページを高速で移動できるようにしたいです。少なくともコピーするよりも高速に。メモリ ページを非常に高速に移動できることを利用できるアルゴリズムのアイデアがいくつかあります。問題は、以下のプログラムを見ると、mremap() は、少なくとも私の i7 ラップトップでは、同じメモリ ページをバイトごとに実際にコピーする場合に比べて非常に遅いことがわかります。
テスト ソース コードはどのように動作するのでしょうか。CPU 上のキャッシュよりも大きい 256 MB の RAM を mmap() します。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;
}
更新: 「カーネル空間への往復」がどれだけ速いのか疑問に思わなくて済むように、同じ i7 ラップトップで getpid() を 3 回連続して呼び出すことができ、1 秒あたり 81,916,192 回呼び出せることを示すパフォーマンス テスト プログラムをさらに示します。
#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 ページには、ページ操作が可能である可能性が示されています。ただし、読み取ったバイト数を返すことを期待しているときに、何を試しても関数は常に 0 を返します。'man modify_ldt' には、「成功した場合、modify_ldt() は実際に読み取ったバイト数 (読み取りの場合) または 0 (書き込みの場合) を返します。失敗した場合、modify_ldt() は -1 を返し、エラーを示す errno を設定します。」とあります。(a) modify_ldt() が mremap() の代替になるかどうか、(b) modify_ldt() を動作させる方法について、何かアイデアはありますか?
ベストアンサー1
メモリ ページを並べ替えるには、memcpy() よりも高速なユーザー ランド メカニズムは存在しないようです。mremap() ははるかに低速であるため、mmap() を使用して以前に割り当てられたメモリ領域のサイズを変更する場合にのみ役立ちます。
しかし、ページ テーブルは非常に高速であるはずだという声が聞こえてきそうです。また、ユーザー ランドがカーネル関数を 1 秒間に何百万回も呼び出すことも可能です。次の参考資料は、mremap() がなぜそれほど遅いのかを説明するのに役立ちます。
「Intel メモリ管理入門」メモリ ページ マッピングの理論の優れた入門書です。
「Intel 仮想メモリの主要概念」独自の OS を作成する予定がある場合に備えて、すべての動作をより詳細に示します :-)
「Linux カーネルでのページ テーブルの共有」Linux のメモリ ページ マッピングに関する難しいアーキテクチャ上の決定と、それがパフォーマンスに与える影響の一部を示します。
これら 3 つの参考文献を一緒に見ると、カーネル設計者によるメモリ ページ マッピングをユーザー ランドに効率的に公開するための取り組みがこれまでほとんど行われていないことがわかります。カーネル内でも、ページ テーブルの操作は最大 3 つのロックを使用して行う必要があり、時間がかかります。
今後、ページ テーブル自体は 4k ページで構成されているため、特定のページ テーブル ページが特定のスレッドに固有であり、プロセスの実行中はロックなしでアクセスできると想定できるようにカーネルを変更することが可能になるかもしれません。これにより、ユーザー ランドを介して特定のページ テーブル ページを非常に効率的に操作できるようになります。ただし、これは元の質問の範囲外になります。