panda's tech note

Advent Calendar 2018: advos

Day 18: メモリ管理(NUMA-aware領域の管理)

11日目・12日目では,コアゾーンである少量の物理メモリ領域を管理するバディシステムを実装しました。今日はNUMA-aware領域もバディシステムで管理しようと思います。

メモリのNUMAドメイン

メモリ領域のNUMAドメインは14日目に実装したACPIのパーサにより取得できます。これまでsrc/arch/x86_64/arch.cに書いた以下のプログラムは,NUMAドメインを表示するものです。

    /* Print memory information */
    print_str(base, "Base             Length           Domain");
    base += 80;
    for ( i = 0; i < acpi->num_memory_region; i++ ) {
        print_hex(base, (uintptr_t)acpi->memory_domain[i].base, 8);
        print_hex(base + 17, (uintptr_t)acpi->memory_domain[i].length, 8);
        print_hex(base + 34, (uintptr_t)acpi->memory_domain[i].domain, 8);
        base += 80;
    }

この情報を使ってNUMAドメインごとにバディシステムを構築していきます。

仮想ページへのリニアマッピング

バディシステムでは,管理対象のページを使って連結リストを実現するため,すべての領域を仮想ページに割り当てています。この仮想ページの管理を簡略化するために物理ページを仮想ページにリニアマッピングします。この処理はsrc/kernel/arch/x86_64/arch.c_init_linear_pgt()関数で実装します。

まず,リニアマッピングするために必要なページテーブルのサイズを計算するために,以下のコードでシステムメモリマップからメモリの最大領域を取得します。

    /* Get the maximum address of the system memory */
    maxaddr = 0;
    for ( i = 0; i < nr; i++ ) {
        addr = map[i].base + map[i].len;
        if ( addr > maxaddr ) {
            maxaddr = addr;
        }
    }

これを2 MiBページングした場合に必要なPML4,PDPT,PDエントリ数を計算します。

    /* # of 2 MiB pages, PDPT entries */
    maxaddr += mem->p2v;
    npg = ((maxaddr + 0x1fffff) >> 21);
    npdpt = ((npg + 511) / 512);
    npml = ((npdpt + 511) / 512);
    n = (npdpt - 5) + (npml - 1) - 1;
    order = 0;
    while ( n ) {
        n >>= 1;
        order++;
    }

これから,必要な4 KiBページ数を計算します。ただし,カーネルページテーブルで既に使用している領域は再利用します。必要な4 KiBページはPML4エントリ数およびPDPTのエントリ数なので,PML4エントリ1つ,PDPTエントリ5つは再利用すると,(npdpt - 5) + (npml - 1)となります。

ここから,コアゾーンから2の累乗の4 KiBページを割り当てます。以下のようにn-1のMost Significant Bit (MSB)の場所を求めることで,割り当てるオーダーを計算できます。n-1=0のときは,MSBが計算できないですが,オーダー0(つまり1ページ)とします。

    n = (npdpt - 5) + (npml - 1) - 1;
    order = 0;
    while ( n ) {
        n >>= 1;
        order++;
    }

この割り当てたメモリを用い,以下のようにカーネルページテーブルを再構築します。この可変サイズのページ割り当てにはphys_mem_buddy_alloc()が必要なので,コアゾーンとNUMA-awareゾーンを分けて2段階で実装しています。

    /* Allocate memory for the page table from the kernel zone */
    arr = phys_mem_buddy_alloc(mem->czones[MEMORY_ZONE_KERNEL].heads, order);
    if ( NULL == arr ) {
        return -1;
    }

    /* Modify the kernel base page table */
    base = 0x00069000ULL;
    e = (uint64_t *)base;
    /* PML4 */
    for ( i = 1; i < npml; i++ ) {
        addr = (uintptr_t)arr[i - 1] - mem->p2v;
        *(e + i) = addr | 0x007;
    }
    /* PDPT */
    e = (uint64_t *)(base + 0x1000);
    for ( i = 5; i < 512 && i < npdpt; i++ ) {
        addr = (uintptr_t)arr[npml - 1 + i - 5] - mem->p2v;
        *(e + i) = addr | 0x007;
    }
    for ( i = 512; i < npdpt; i++ ) {
        e = (uint64_t *)arr[i / 512 - 1];
        addr = (uintptr_t)arr[npml - 1 + i - 5] - mem->p2v;
        *(e + i % 512) = addr | 0x007;
    }
    /* PD */
    e = (uint64_t *)(base + 0x4000);
    for ( i = 32; i < 512 && i < npg; i++ ) {
        addr = (uintptr_t)arr[npml - 1 + i - 5] - mem->p2v;
        *(e + i) = (0x00200000ULL * i) | 0x083;
        invlpg((0x00200000ULL * i + mem->p2v));
    }
    for ( i = 512; i < npg; i++ ) {
        e = (uint64_t *)arr[npml - 1 + i / 512];
        *(e + i % 512) = (0x00200000ULL * i) | 0x083;
        invlpg((0x00200000ULL * i + mem->p2v));
    }

かなりコードが汚くなってしまいました。ページテーブル周りはどうしてもこのようなコードになりがちなので,後日綺麗にリファクタリングしたいと思っています。

NUMA-awareゾーンの初期化

物理メモリにリニアマッピングされた仮想メモリが設定ができたので,NUMA-awareゾーンのバディシステムを初期化します。11日目・12日目では,物理メモリ管理構造体phys_memory_tにコアゾーンのみを定義しました。今回は,ここにNUMA-awareなゾーンを追加します。ただし,NUMAドメインの数はシステムによって異なるため,最大ドメイン番号とphys_memory_zone_t配列へのポインタをphys_memory_tのメンバに追加します。

    int max_domain;
    phys_memory_zone_t *numazones;

以下のコードで最大のドメイン番号を取得します。

    max_domain = 0;
    for ( i = 0; i < acpi->num_memory_region; i++ ) {
        if ( acpi->memory_domain[i].domain > max_domain ) {
            max_domain = acpi->memory_domain[i].domain;
        }
    }

以下のコードで,このドメイン数分(max_domain + 1),phys_memory_zone_tを配列として確保します。

    /* Allocate for the NUMA-aware zones */
    sz = sizeof(phys_memory_zone_t) * (max_domain + 1);
    sz = (sz - 1) >> MEMORY_PAGESIZE_SHIFT;
    order = 0;
    while ( sz ) {
        sz >>= 1;
        order++;
    }
    zones = phys_mem_buddy_alloc(mem->czones[MEMORY_ZONE_KERNEL].heads, order);
    if ( NULL == zones ) {
        return -1;
    }
    kmemset(zones, 0, sizeof(1 << (order + MEMORY_PAGESIZE_SHIFT)));

ここから,システムメモリマップとNUMAドメインの情報を参照して,各ゾーンのバディシステムにメモリ領域を追加します。以下のようにシステムメモリマップのうち,DMAゾーン,Kernelゾーンを除いた領域(4 KiBアライメントを取ります)を_add_region_to_numa_zones()関数を呼び出して追加します。

    for ( i = 0; i < nr; i++ ) {
        /* Base address and the address of the next block (base + length) */
        base = map[i].base;
        next = base + map[i].len;

        /* Ignore Kernel zone */
        if ( base < MEMORY_ZONE_NUMA_AWARE_LB ) {
            base = MEMORY_ZONE_NUMA_AWARE_LB;
        }
        if ( next < MEMORY_ZONE_NUMA_AWARE_LB ) {
            next = MEMORY_ZONE_NUMA_AWARE_LB;
        }

        /* Round up for 4 KiB page alignment */
        base = (base + (MEMORY_PAGESIZE - 1)) & ~(MEMORY_PAGESIZE - 1);
        next = next & ~(MEMORY_PAGESIZE - 1);

        if ( base != next ) {
            /* Add this region to the buddy system */
            _add_region_to_numa_zones(mem, acpi, base, next);
        }
    }

_add_region_to_numa_zones()関数では,以下のようにbaseからnextまでのNUMAドメインをACPIの情報から取得し,対応するNUMAドメイン(ゾーン)にメモリ領域を追加します。

static void
_add_region_to_numa_zones(phys_memory_t *mem, acpi_t *acpi, uintptr_t base,
                          uintptr_t next)
{
    int i;
    uintptr_t s;
    uintptr_t t;
    int dom;

    for ( i = 0; i < acpi->num_memory_region; i++ ) {
        s = acpi->memory_domain[i].base;
        t = s + acpi->memory_domain[i].length;
        dom = acpi->memory_domain[i].domain;
        if ( base >= s && next <= t ) {
            /* Within the domain, then add this region to the buddy system */
            phys_mem_buddy_add_region(mem->numazones[dom].heads,
                                      base + mem->p2v, next + mem->p2v);
        } else if ( base >= s ) {
            /* s <= base <= t < next */
            phys_mem_buddy_add_region(mem->numazones[dom].heads,
                                      base + mem->p2v, t + mem->p2v);
        } else if ( next <= t ) {
            /* base < s < next <= t */
            phys_mem_buddy_add_region(mem->numazones[dom].heads,
                                      s + mem->p2v, next + mem->p2v);
        }

    }
}

まとめと明日の予定

今日は,NUMA-aware領域をリニアマッピングしてカーネルの仮想メモリから扱えるようにしました。また,この領域についてバディシステムの初期化をしました。明日は2^nにアライメントされていないページアロケータを作ります。