ビットマップの実装

MemBitmap構造体は、任意の長さの汎用一次元ビットマップのヘッダーとして使用されます。カーネルはビットマップを再利用可能な項目のセットを追跡するための効率的な方法として使用します。

struct MemBitmap {
    uint32_t length;
    PRIVATE_DATA_MEMBER uint8_t *buffer;
};

void MemBitmapInit(struct MemBitmap *btmp, uint8_t *bitsBuffer, uint32_t len);

bool MemBitmapTestBit(const struct MemBitmap *btmp, uint32_t idx);

int MemBitmapFindFreeBits(struct MemBitmap *btmp, uint32_t cnt);

void MemBitmapSetBit(struct MemBitmap *btmp, uint32_t idx, uint8_t val);

#define TEST_BIT(flag, idx) ((uint8_t)(1 << idx) & (flag))
#define SET_BIT(flag, idx)   ((flag) |= (1 << idx))
#define CLEAR_BIT(flag, idx) ((flag) &= ~(1 << idx))

MemBitmap構造体を使用する側は、MemBitmapInitを使用して初期化する必要があります。構造体自体はメモリの割り当てと解放を担当しません。

PRIVATE_DATA_MEMBERでマークされたメンバーは、アンダースコアと小文字のキャメルケースで始まる必要があり、呼び出し側がコード内で直接アクセスすべきではないことを示します。

使用例

    uint8_t buffer[4] = {0x00, 0x00, 0x00, 0x00}; // 32ビット
    struct MemBitmap bitmap;

    // ビットマップの初期化
    MemBitmapInit(&bitmap, buffer, sizeof(buffer));
    ASSERT(MemBitmapFindFreeBits(&bitmap, 1) == 0); // 0番目のビットが未設定
    MemBitmapSetBit(&bitmap, 0, 1);
    MemBitmapSetBit(&bitmap, 1, 1);

    ASSERT(MemBitmapFindFreeBits(&bitmap, 1) == 2);
    ASSERT(MemBitmapFindFreeBits(&bitmap, 2) == 2);
    MemBitmapSetBit(&bitmap, 2, 1);
    ASSERT(MemBitmapFindFreeBits(&bitmap, 1) == 3); // 3番目のビットが未設定
    MemBitmapSetBit(&bitmap, 3, 0);
    MemBitmapSetBit(&bitmap, 2, 0);
    ASSERT(MemBitmapFindFreeBits(&bitmap, 2) == 2); // 連続した2つの未設定ビットが見つからない
    MemBitmapSetBit(&bitmap, 3, 1);                      // 3番目のビットを設定
    ASSERT(MemBitmapFindFreeBits(&bitmap, 2) == 4); // 未設定ビットが見つからない

メモリプール（非ページプール）

オペレーティングシステムは物理メモリをカーネルメモリプールとユーザーメモリプールに分割します。

ビットマップリソース

オペレーティングシステムは物理アドレス0x3DF000から0x3FF000までを、メモリプールの維持に必要なビットマップ領域として予約します。ビットマップ内の1ビットは1つの自然ページ（4KB）を表します。したがって、この領域のビットマップは最大4,294,967,296バイト（4GiB）をマッピングできます。

オペレーティングシステムの最大サポートメモリ
オペレーティングシステムは、仮想アドレスマッピングを維持するために、カーネルとユーザーメモリプールに同じ長さのビットマップを追加で予約する必要があるため、最大サポートメモリは2GiBです。そのうち、ユーザープロセスが最大約1GiBのメモリ空間を要求できます。

メモリプールの初期化

初期化時に、カーネルおよびユーザーメモリプールの開始物理アドレスとサイズを指定し、物理ページの使用状況を管理するビットマップマッピングを確立します。

注意：図に示されているように、オペレーティングシステムはカーネルスタックのトップ（0x400000）からPDEとPTE領域まで0x100000のスペースを予約するため、カーネルメモリプールは0x600000から割り当てを開始します。

メモリプールサイズの割り当て戦略は、カーネル用に予約された低い0x500000スペース、PDE、カーネルPTEテーブルスペースを除いた残りのメモリをカーネルとユーザーメモリプールで均等に分割することです。

すべての物理メモリのサイズは、LOADERによってメモリアドレス0xB10にロードされています。

static void MemoryPoolInit(uint32_t totalMem) {
    /* 1 PDE + 1 PTE (0 PTE) + 254 PTE (769 - 1022) = 256 PAGE */
    uint32_t pageTableSize = PAGE_SIZE * 256;
    /* NOTE: OS reserves space of 0x100000 from the top of the kernel stack to the PDE and PTE regions*/
    uint32_t usedMem         = pageTableSize + KERNEL_PHY_STACK_TOP + 0x100000;
    uint32_t freeMem         = totalMem - usedMem;
    uint16_t allFreePages    = freeMem / PAGE_SIZE;
    uint16_t kernelFreePages   = allFreePages / 2;
    uint16_t userFreePages   = allFreePages - kernelFreePages;
    uint32_t kernelPoolBmpLen = kernelFreePages / 8;
    uint32_t userPoolBmpLen = userFreePages / 8;

    /* kernel pool */
    gKernelPool.phyAddrStart = usedMem;
    gKernelPool.poolSize     = kernelFreePages * PAGE_SIZE;
    MemBitmapInit(&gKernelPool.poolBitmap, (uint8_t *)MEM_BITMAP_BASE, kernelPoolBmpLen);

    /* user pool */
    gUserPool.phyAddrStart = gKernelPool.phyAddrStart + kernelFreePages * PAGE_SIZE;
    gUserPool.poolSize     = userFreePages * PAGE_SIZE;
    MemBitmapInit(&gUserPool.poolBitmap, (uint8_t *)MEM_BITMAP_BASE + kernelPoolBmpLen, userPoolBmpLen);

    /* kernel heap virtual address */
    gKernelVirtAddr.virtAddrStart = MEM_KERNEL_HEAP_START;
    MemBitmapInit(&gKernelVirtAddr.virtAddrBitmap, (uint8_t *)MEM_BITMAP_BASE + kernelPoolBmpLen + userPoolBmpLen,
                 kernelPoolBmpLen);
    // clang-format off
#ifdef _KDEBUG
    PrintString("Memory Summary\n");
    PrintString("  Available/Total: "); PrintInt(freeMem); PrintChar('/'); PrintInt(totalMem); PrintString(" BYTES\n");
    PrintString("  Kernel Pool: 0x"); PrintHex(gKernelPool.phyAddrStart); PrintString(" -> 0x"); 
    PrintHex(gKernelPool.phyAddrStart + gKernelPool.poolSize);
    PrintString(" ("); PrintInt(gKernelPool.poolSize); PrintString(" bytes)\n");
    PrintString("  User Pool: 0x"); PrintHex(gUserPool.phyAddrStart); PrintString(" -> 0x"); 
    PrintHex(gUserPool.phyAddrStart + gUserPool.poolSize);
    PrintString(" ("); PrintInt(gUserPool.poolSize); PrintString(" bytes)\n");
#endif
    // clang-format on
}

仮想アドレス

各メモリプールはメモリページの割り当てのみを担当し、対応する仮想アドレスマッピングはVirtualAddress構造体によって維持されます。

struct VirtualAddress {
    struct MemBitmap virtAddrBitmap;
    uint32_t         virtAddrStart;
};

以下のコードは、仮想アドレスプール内でサイズ条件に合致する開始アドレスを取得します。

static void *GetFreeVirtualAddress(enum MemoryPoolType type, uint32_t pageCount) {
    int32_t virtAddrStart = 0, bitIndex = -1;
    if (type == MEMORY_POOL_KERNEL) {
        bitIndex = MemBitmapFindFreeBits(&gKernelVirtAddr.virtAddrBitmap, pageCount);
        if (bitIndex == -1)
            return NULL;
        MemBitmapSetBits(&gKernelVirtAddr.virtAddrBitmap, bitIndex, pageCount, 1);
        virtAddrStart = gKernelVirtAddr.virtAddrStart + bitIndex * PAGE_SIZE;
    }
    return (void *)virtAddrStart;
}

PTE & PDE 操作

PDEおよびPTEの動的操作は、以下の事実に基づいています：

1. 保護モードでは仮想アドレスに対して操作する必要がある
2. x86の仮想アドレス構造：
   • 上位10ビット：ページディレクトリテーブル内のページディレクトリエントリ（PDE）を特定するために使用（ページディレクトリエントリにはページテーブルの**物理アドレス**が含まれる）
   • 中間10ビット：特定のページテーブル内でページテーブルエントリ（PTE）を特定するために使用
   • 下位12ビット：ページ内オフセット
3. LOADER段階で、最後のPDEの物理アドレスを最初のPDEに向けるように設定済み

したがって、任意の仮想アドレスVAddrが与えられた場合、以下の方法でそのアドレスに対応するPTE仮想アドレスを取得できます：

CPUは3回の位置指定によって実際の物理アドレスを見つけます。
上位10ビットを最後のPDEに向け、仮想アドレスのPDEをPTEとして扱い、仮想アドレスのPTEアドレス（中10ビットであるため、12ビット物理ページオフセットに合わせるために4を乗算）に4を乗算して物理ページオフセット量とします。
上位10ビットが最後のPDEを指し、最後のPDEの物理アドレスがPDEテーブルの先頭を指しているため、これは「先頭にその場でジャンプ」することと同等です。これにより、CPUは効果的に「2回」のアドレス指定のみを行います。つまり、最終的にPTEの実際の物理アドレスに留まります。

uint32_t *GetVirtualAddressPte(uint32_t virtAddr) {
    return (uint32_t *)(0xFFC00000 + ((virtAddr & 0xFFC00000) >> 10) + (VIRT_ADDR_MID_PART(virtAddr) << 2));
}

同様に、PDEを取得するには、2回の「先頭にその場でジャンプ」操作を行い、PDE部分（上位10ビット）を物理ページオフセットとして使用します。

uint32_t *GetVirtualAddressPde(uint32_t virtAddr) { 
    return (uint32_t *)(0xFFFFF000 + (VIRT_ADDR_HIGH_PART(virtAddr) << 2)); 
}

仮想アドレスと物理アドレスの関連付け

メモリを割り当てる際、まずメモリプールに新しい物理ページ（物理アドレスを返す）を要求します：

static void *AllocatePhysicalPage(struct MemoryPool *pool) {
    int index = MemBitmapFindFreeBits(&pool->poolBitmap, 1);
    if (index == -1)
        return NULL;
    MemBitmapSetBit(&pool->poolBitmap, index, 1);
    return (void *)(index * PAGE_SIZE + pool->phyAddrStart);
}

その後、割り当てられた物理ページを仮想アドレスに関連付けます：

/* PDEとPTEを介して仮想アドレスと物理アドレス間のマッピングを確立 */
static void EstablishPageMapping(void *virtAddrPtr, void *physPageAddrPtr) {
    uint32_t  virtAddr = (uint32_t)virtAddrPtr, physPageAddr = (uint32_t)physPageAddrPtr;
    uint32_t *pde = GetVirtualAddressPde(virtAddrPtr);
    uint32_t *pte = GetVirtualAddressPte(virtAddrPtr);

    if (*pde & PAGE_PRESENT) { /* PDEが存在する */
        if (*pte & PAGE_PRESENT)
            KernelPanic("既に割り当てられているPTEアドレスの二重割り当て");
        *pte = (physPageAddr | PAGE_USER | PAGE_WRITE | PAGE_PRESENT);
    } else { /* PDEが存在しない */
        uint32_t pdePhysAddr = (uint32_t)AllocatePhysicalPage(&gKernelPool);
        *pde                = (pdePhysAddr | PAGE_USER | PAGE_WRITE | PAGE_PRESENT);
        memset((void *)((int)pte & 0xFFFFF000), 0, PAGE_SIZE);
        ASSERT(!(*pte & PAGE_PRESENT));
        *pte = (physPageAddr | PAGE_USER | PAGE_WRITE | PAGE_PRESENT);
    }
}

メモリを割り当てる際、仮想アドレスはGetFreeVirtualAddressから取得する必要があるため、理論的にはPTEとのマッピングが存在することはありえません。存在する場合は、直接パニックを引き起こします。

PDEのPビットが存在しないとマークされている場合、そのPDEには対応するページテーブルがないことを意味します。したがって、カーネルメモリプールから直接物理ページを取得し、PDEに対応するPTEページテーブルとして使用します。pteが対応するのは仮想アドレスに対応するpteの仮想アドレスです。上位20ビットのみを取得する場合、そのアドレスはpteが存在するテーブルの先頭を表し、そのページテーブルエントリが存在するページをクリアします（ゴミデータがないようにするため）。

メモリプールからのページ単位割り当て

以上をまとめると、物理ページを割り当てて仮想アドレスに関連付けるには、おおよそ以下の手順が必要です：

1. カーネルの初期化時に、メモリプールを初期化する
2. GetFreeVirtualAddressを使用して、まだ物理ページが割り当てられていない仮想アドレスページを取得する
3. AllocatePhysicalPageを使用して空き物理ページを取得する
4. 仮想アドレスページから物理ページへのマッピングを追加し、仮想アドレスに対応するPTEを変更して、そのPTE項目が物理ページアドレスを記録するようにする

API AllocateMemoryPagesを使用して、メモリプールからpageCount自然ページを割り当てます：

void *AllocateMemoryPages(enum MemoryPoolType type, uint32_t pageCount) {
    ASSERT(pageCount > 0);
    struct MemoryPool *pool;
    void                  *pagePhysAddr, *virtAddrStart;
    uint32_t               virtAddr;

    virtAddrStart = GetFreeVirtualAddress(type, pageCount);
    if (virtAddrStart == 0)
        return NULL;
    virtAddr = (uint32_t)virtAddrStart;
    pool   = (type & MEMORY_POOL_KERNEL) ? &gKernelPool : &gUserPool;
    while (pageCount-- > 0) {
        pagePhysAddr = AllocatePhysicalPage(pool);
        if (pagePhysAddr == NULL)
            return NULL;
        EstablishPageMapping((void *)virtAddr, pagePhysAddr);
        virtAddr += PAGE_SIZE;
    }
    return virtAddrStart;
}

void *AllocateKernelMemoryPages(uint32_t pageCount) {
    void *kernelPage = AllocateMemoryPages(MEMORY_POOL_KERNEL, pageCount);
    if (kernelPage != NULL)
        memset(kernelPage, 0, pageCount * PAGE_SIZE);
    return kernelPage;
}