Подтвердить что ты не робот

Более быстрый способ перемещения страницы памяти, чем mremap()?

Я экспериментировал с mremap(). Я хотел бы иметь возможность перемещать страницы виртуальной памяти на высоких скоростях. По крайней мере, более высокие скорости, чем их копирование. У меня есть некоторые идеи для алгоритмов, которые могли бы использовать возможность быстрого перемещения страниц памяти. Проблема в том, что в приведенной ниже программе показано, что mremap() работает очень медленно - по крайней мере, на моем ноутбуке i7 - по сравнению с фактическим копированием одного и того же байта страниц памяти байтом.

Как работает исходный код теста? mmap() 256 МБ ОЗУ, которая больше, чем кэширование на процессорах. Итерируйте в 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;
}

Обновление. Поэтому нам не нужно задавать вопрос о том, насколько быстрым является "round-trip to kernelspace", вот еще одна программа тестирования производительности, которая показывает, что мы можем вызвать 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 для указания ошибки". Любые идеи (а) будет ли modify_ldt() альтернативой mremap()? и (b) как заставить modify_ldt() работать?

4b9b3361

ОТВЕТЫ

Ответ 1

Похоже, что нет более быстрого механизма пользовательского пространства для переупорядочивания страниц памяти, чем memcpy(). mremap() намного медленнее и поэтому полезен только для изменения размера области памяти, ранее назначенной с помощью mmap().

Но таблицы страниц должны быть очень быстрыми, я слышу, как вы говорите! И пользовательская земля может вызывать функции ядра миллионы раз в секунду! Следующие ссылки помогают объяснить, почему mremap() такой медленный:

"Введение в Intel Memory Management" - хорошее введение в теорию отображения страниц памяти.

"Ключевые концепции виртуальной памяти Intel" более подробно показывают, как все это работает, если вы планируете писать свою собственную ОС :-)

"Совместное использование таблиц страниц в ядре Linux" показывает некоторые сложные архитектурные решения по отображению страниц памяти в Linux и их влияние на производительность.

Рассматривая все три ссылки вместе, мы можем видеть, что архитекторам ядра пока не требуется больших усилий для эффективного отображения сопоставления страниц памяти для пользовательского пространства. Даже в ядре манипулирование таблицей страниц должно выполняться с использованием до трех блокировок, которые будут медленными.

В дальнейшем, поскольку сама таблица страниц состоит из 4 тыс. Страниц, возможно, можно изменить ядро, чтобы конкретные страницы таблицы страниц были уникальными для конкретного потока и можно было предположить, что они будут иметь доступ без блокировки в течение всего периода времени. процесс. Это будет способствовать очень эффективному манипулированию этой конкретной страницей таблицы страниц с помощью пользовательского пространства. Но это выходит за рамки первоначального вопроса.

Ответ 2

Почему вы думаете, что mremap может быть эффективным для обмена одиночными 4k страницами? По крайней мере, круговое путешествие в ядерное пространство даже для чтения одного значения (например, pid) и возврата его будет стоить больше, чем перемещение 4k данных. И это до того, как мы перейдем к кэшированию недействительности /TLB из-за переназначения памяти, что я недостаточно хорошо понимаю для ответа в этом ответе, но которое должно иметь серьезные затраты.

mremap полезен, в основном, для одного: реализация realloc для больших распределений, обслуживаемых mmap. И по большому счету, я имею в виду, вероятно, не менее 100 тыс.