Closed31

ゼロからOS自作入門 8章

ackyacky

メモリ管理

PCに搭載されたメモリの管理を行う

  • メモリの空き容量の管理
  • アプリケーションの要求に応じてメモリの割り当て

ここでは「物理メモリの中の空き領域を探す方法」と「空き領域と割り当て済みの領域を管理する方法」を学ぶ

ackyacky

メモリ管理

現在のオペレーティングシステム(OS)においては、メモリ管理の1つとして仮想記憶が代表的である。
仮想記憶システムはプロセスが使用するメモリ空間 (アドレス空間) を物理アドレスから分離し、プロセス単位の分離を実現すると共に、実質的に使用可能なメモリ量を増大させる。仮想記憶管理の品質はオペレーティングシステム全体の性能に大きな影響がある。また、プロセス間通信の一種である共有メモリは多重仮想空間でのプロセス間のメモリ共有を実現する機能である。
メモリ確保

メモリ管理の代表的な機能は、メモリの確保と解放である。つまり、mallocとfreeである。

  • メモリが必要な人に必要な文を割り当てる
  • 不要になったメモリを回収する
ackyacky

UEFIメモリマップ

  • CPUのメモリコントローラのおかげで、ソフトウェアの観点では多数のバイトが直線的に並んでいるように見える
    • よく見るメモリの絵
  • メインメモリのどこからどこまでが何に使われているかを表すメモリマップというのがある
  • メモリ領域の大きさをページで表す。UEFIでは1ページ=4 KiB
  • メモリマップには歯抜けの部分(空き地みたいなやつ)があることにも注意。
  • メモリを使うならこの空き地を探す必要がある
メモリマップの例

メモリマップにこのあたりの情報が記載されいた

Index, Type, Type(name), PhysicalStart, NumberOfPages, Attribute
0, 3, EfiBootServicesCode, 00000000, 1, F
1, 7, EfiConventionalMemory, 00001000, 9F, F
2, 7, EfiConventionalMemory, 00100000, 700, F
3, A, EfiACPIMemoryNVS, 00800000, 8, F
4, 7, EfiConventionalMemory, 00808000, 8, F
5, A, EfiACPIMemoryNVS, 00810000, F0, F
6, 4, EfiBootServicesData, 00900000, B00, F
7, 7, EfiConventionalMemory, 01400000, 3AB36, F
8, 4, EfiBootServicesData, 3BF36000, 20, F
9, 7, EfiConventionalMemory, 3BF56000, 270F, F
10, 1, EfiLoaderCode, 3E665000, 2, F
11, 4, EfiBootServicesData, 3E667000, 217, F
12, 3, EfiBootServicesCode, 3E87E000, B6, F
ackyacky

このあたりの情報をBootLoderからKernelに受け渡す。

BootLoderを更新するので儀式

$ unlink MikanLoaderPkg # 前に残っていたシンボリックリンクを削除
$ ln -s /mnt/30DayOS/workspace/ch08/MikanLoaderPkg/ ./
$ source edksetup.sh
$ build
  • MikanLoaderPkg/Main.c

メモリマップ構造体のポインタを渡すように修正

  typedef void EntryPointType(const struct FrameBufferConfig*,
                              const struct MemoryMap*);
  EntryPointType* entry_point = (EntryPointType*)entry_addr;
  entry_point(&frame_buffer_config, &memmap);

元々は FrameBufferConfig しか渡していなかったところを修正

ackyacky

次はこのフォーマットに合わせるようにKernel側を修正

メモリマップの構造体

struct MemoryMap {
  unsigned long long buffer_size;
  void* buffer;
  unsigned long long map_size;
  unsigned long long map_key;
  unsigned long long descriptor_size; // 要素の大きさ(バイト数)
  uint32_t descriptor_version;
};
  printk("memory_map: %p\n", &memory_map);
  for (uintptr_t iter = reinterpret_cast<uintptr_t>(memory_map.buffer);
       iter < reinterpret_cast<uintptr_t>(memory_map.buffer) + memory_map.map_size;
       iter += memory_map.descriptor_size) {
    auto desc = reinterpret_cast<MemoryDescriptor*>(iter);
    for (int i = 0; i < available_memory_types.size(); ++i) {
      if (desc->type == available_memory_types[i]) {
        printk("type = %u, phys = %08lx - %08lx, pages = %lu, attr = %08lx\n",
            desc->type,
            desc->physical_start,
            desc->physical_start + desc->number_of_pages * 4096 - 1,
            desc->number_of_pages,
            desc->attribute);
      }
    }
  }
  • メモリマップはメモリディスクリプタの配列である
  • UEFIのBIOSのバージョンによっては、MemoryDescriptorの定義と実際に取得できるメモリディスクリプタの構造が異なる
  • descriptor_sizeを使ってメモリマップを一巡する
ackyacky

データ構造の移動

UEFIから渡られたメモリマップを参照して空いているメモリ領域を探し、メモリ割り当てに応じて必要なメモリ領域を払い出す

ackyacky

上のメモリマップの部分で、領域手として使える部分か判定するロジックか

inline bool IsAvailable(MemoryType memory_type) {
  return
    memory_type == MemoryType::kEfiBootServicesCode ||
    memory_type == MemoryType::kEfiBootServicesData ||
    memory_type == MemoryType::kEfiConventionalMemory;
}
ackyacky

メモリマップを参照して管理する前の準備

いくつかのデータ構造をOSが所有するメモリ領域に移動する

  • ブートローダー専用データ領域(kEfiBootServicesData)にあるデータを別の場所に移動させる
    • スタック領域
      • UEFIからOSが処理に移ってきた直後はUEFIが準備したスタック領域を使っている
      • これを移動しないとプログラムが実行できなくなる
    • Global Descriptor Table (GDT)
      • セグメンテーションの設定を集めたもの
      • セグメンテーションとは、メモリを区画に分ける
      • x86-64の64ビットモードでは区画に分ける機能はなくなり、事実上無効化された
    • ページテーブル
      • ページング機能ための設定情報を集めたもの
      • メモリを固定長区間に分割して管理する機能
      • セグメンテーションに変わってメモリ管理の主役になっている
ackyacky

スタック領域の移動

ここでのスタックはCPUがプログラムを実行する際に使用するメモリ領域である

  • CPUはcall命令で関数を呼び出す際に暗黙的にスタックに戻り先のアドレスを保存する
  • C++コンパイラは一時変数をスタックに確保する

スタックの挙動は以下の通り

役割
RSP:Stack Pointer サブルーチンコールの戻りアドレスをメモリに自動的に格納したり、PUSH、POP命令でレジスタを一時的に退避、復帰する場合に使
RIP:Instruction Pointer 次に実行すべき命令が格納されているメモリ上のアドレスを保存している
プログラムカウンタ
  • Push/Popの挙動

スタックポインタ(RSP)は最新のデータのレジスタを指す

  • プログラムカウンタ(RIP)の挙動

機械語はただ1つだけプログラム中に置き、必要なときにその処理部分を実行し、処理が終われば元に戻る処理を行う。

  • サブルーチン:プログラム中の複数の場所から飛んで来て実行し、実行が終われば元の位置へ戻る処理部分
  • サブルーチン呼び出し:サブルーチンへ実行を移すこと
  • サブルーチンからの復帰:サブルーチンを終了して元の処理へ実行を戻すこと

サブルーチン呼び出し命令は、以下の順序で処理を行う

  1. この命令の次の命令のアドレスをスタックにプッシュしてからサブルーチンの先頭アドレスへジャンプする
  2. サブルーチンからの復帰命令では、スタックからアドレスをポップして、そのアドレスにジャンプする
  3. サブルーチンからの復帰命令を実行することで、サブルーチン呼び出し命令の次の命令から処理を再開することができる
  4. 復帰アドレスをスタックに保存することで、サブルーチンの中から自分自身あるいは他のサブルーチンを呼び出すといったサブルーチンの多重呼び出しを行った場合でも、正しく復帰ができる

プログラミングの基本テクニックから引用

ackyacky

スタック領域を移し替えるとは、「RSPの値を書き換えること」である。つまり、ジャンプ先が変わることとで読み替えることになる。


alignas(16) uint8_t kernel_main_stack[1024 * 1024];

extern "C" void KernelMainNewStack(
    const FrameBufferConfig& frame_buffer_config_ref,
    const MemoryMap& memory_map_ref) {
  FrameBufferConfig frame_buffer_config{frame_buffer_config_ref};
  MemoryMap memory_map{memory_map_ref};
  • kernel_main_stackでスタック領域を確保する
  • Kernelのエントリポイントの名前を変更
  • 引数で渡された2つのデータ構造をスタック領域にコピーする
extern kernel_main_stack
extern KernelMainNewStack

global KernelMain
KernelMain:
    mov rsp, kernel_main_stack + 1024 * 1024
    call KernelMainNewStack
.fin:
    hlt
    jmp .fin

ここでKernelMainNewStackを呼び出す後に更新している

  • global KernelMain でUEFIはC++の関数ではなくアセンブリから呼び出すようになる
  • mov rsp, kernel_main_stack + 1024 * 1024 新たにRSPを設定している
  • 最後にKernelMainNewStackを呼び出す
ackyacky

セグメンテーションの設定

x86-64の64ビットモードでは、セグメンテーションはCPUの動作権限を決めるための機能である。

  • CPUは0~3までの動作権限を持っている
  • 上記の動作権限に適した操作を実行する
    • 内側にあるものほど広いアクセス権を持つ
    • リング0:特権モード
    • リング3:ユーザーモード
    • リング1/2:通常は使わない
  • セグメンテーションの設定で必要なデータ構造は GDT(Global Descriptor Table) である
    • ディスクリプタと呼ばれる8バイトのデータ

ここで上図のビット配列をビットフィールドで定義する

union SegmentDescriptor {
  uint64_t data;
  struct {
    uint64_t limit_low : 16;
    uint64_t base_low : 16;
    uint64_t base_middle : 8;
    DescriptorType type : 4;
    uint64_t system_segment : 1;
    uint64_t descriptor_privilege_level : 2;
    uint64_t present : 1;
    uint64_t limit_high : 4;
    uint64_t available : 1;
    uint64_t long_mode : 1;
    uint64_t default_operation_size : 1;
    uint64_t granularity : 1;
    uint64_t base_high : 8;
  } __attribute__((packed)) bits;
} __attribute__((packed));

GDTは今回は3つ持つことにする

無名名前空間を使っている
ファイルスコープのグローバル変数

namespace {
  std::array<SegmentDescriptor, 3> gdt;
}
ackyacky

再構築したGDTの内容をCPUに反映させる

  • セグメンテーションの設定
  SetupSegments();

  const uint16_t kernel_cs = 1 << 3;
  const uint16_t kernel_ss = 2 << 3;
  SetDSAll(0);
  SetCSSS(kernel_cs, kernel_ss);

  SetupIdentityPageTable();
  • SetupSegments():GDTを再構築する
  • SetDSAll(0)/SetCSSS(kernel_cs, kernel_ss):再構築したGDTをCPUに反映する
    • kernel_cs:gdt[1]に格納される
    • kernel_ss:gdt[2]に格納される
ackyacky
  • SetupSegments():GDTを再構築する
    • GDTの3つのディスクリプタに値を設定する
      • 0:0埋め。このディスクリプタは使わない
      • 1:SetCodeSegment()
      • 2:SetDataSegment()
    • 最後に LoadGDT を呼び出すことでGDTをCPUに登録する
  • SetCodeSegment():コードセグメントディスクリプタ
  • SetDataSegment():データセグメントディスクリプタ
ackyacky

セグメントディスクリプタ

セグメントは、セグメントディスクリプタテーブルに定義される。
セグメントディスクリプタテーブルには以下の2種類がある。

セグメントディスクリプタテーブル種別 対応するレジスタ 説明
GDT GDTR システム全体で唯一のセグメントディスクリプタテーブル
LDT - プロセスごとなどに持てるセグメントディスクリプタテーブル

セグメントディスクリプタは複数の属性を持つ。

構造体メンバー名 フィールド名 説明
base0(0 ~ 15)
base1(16 ~ 23)
base2(24 ~ 31)
ベース セグメントの先頭アドレスを示す
limit0(0 ~ 15)
limit1(16 ~ 19)
リミット セグメント長を表す
Gフラグが0なら1Byte ~ 1KBの範囲、1なら4KB ~ 4GBの範囲となる
type タイプ セグメントのタイプとアクセス権を表す
読み書きや割り込みなどの表現できる
DescriptorTypeで使用可能な値を定義する
S
system segments
システムフラグ 0ならLDTなどの重要なデータ構造を保持するシステムセグメント
1ならコードセグメント若しくはデータセグメント
dpl
Descriptor Privilege Level
DPL ディスクリプタ特権レベルを示す
DPLはCPLとなる。0ならカーネル、3ならユーザレベルとなる
present 有効なディスクリプタでは1を設定する
available AVLフラグ OSが自由に使って良いフラグ
long mode 1ならば64ビットモード用のコードセグメント
データセグメントでは予約フィールドのため0を設定する
default opration size long_modeが1ならば0になる
データセグメントの場合は1を設定する
granularity 1ならばリミットを4KiB単位として解釈する

セグメンテーションはメモリを区画に分けて管理する機能ため、メモリ区画の開始アドレス(base)と区画の大きさ(limit)を管理している

Typeに関してはEnum値で値が設定できるようにしている

enum class DescriptorType {
  // system segment & gate descriptor types
  kUpper8Bytes   = 0,
  kLDT           = 2,
  kTSSAvailable  = 9,
  kTSSBusy       = 11,
  kCallGate      = 12,
  kInterruptGate = 14,
  kTrapGate      = 15,

  // code & data segment types
  kReadWrite     = 2,
  kExecuteRead   = 10,
};

セグメントは大きく分けて以下の3種類がある。

セグメント種別 対応するレジスタ 説明
コードセグメント cs 機械語プログラムが格納されたセグメント
データセグメント ds プログラムが必要とするデータが格納されたセグメント
スタックセグメント ss プログラムのローカル変数や、関数呼び出しの戻り先を格納するセグメント

CPU は上記レジスタ cs、ds、ss の3つ(そのほか汎用セグメントレジスタ3つを合わせて計6つ)にセグメントを設定することで、プログラムを実行する。
CPU のレジスタ cs、ds、ss などは、セグメントディスクリプタテーブル内のセグメントディスクリプタを指し示すインデックスを保持する。(メモリのアドレスを保持するわけではない)

ackyacky

CPUにGDTを登録するアセンブリ

global LoadGDT  ; void LoadGDT(uint16_t limit, uint64_t offset);
LoadGDT:
    push rbp
    mov rbp, rsp
    sub rsp, 10
    mov [rsp], di  ; limit
    mov [rsp + 2], rsi  ; offset
    lgdt [rsp]
    mov rsp, rbp
    pop rbp
    ret
  • 引数にlimitとoffsetを持つ
  • lgdt命令引数をGDTR(Global Descriptor Table Register)に設定する
ackyacky

DS(データセグメント)やSS(スタックセグメント)を設定する

global SetDSAll  ; void SetDSAll(uint16_t value);
SetDSAll:
    mov ds, di
    mov es, di
    mov fs, di
    mov gs, di
    ret

ここでは、4つのセグメントに引数をコピーする

ackyacky

CSにはUEFIの値が入ったままなので、GDTRの再設定からCSを更新するまでの間はCSが意図しないディスクリプタを指すか、GDTの範囲外を指している可能性がある

ただし、セグメントディスクリプタにはプログラマがアクセスできない隠し領域があり、この問題を解決している

  • この隠し領域はセグメントディスクリプタと同等の内容を先に保持できるようになっている
  • mov命令などによってセグメントレジスタが更新されると、GDTから対応するディスクリプタが読み取られて隠し領域に設定する
    • 次にセグメントレジスタが更新されるまでの間、この隠し領域の値が使われるので、影響が直ちに現れることがない
global SetCSSS  ; void SetCSSS(uint16_t cs, uint16_t ss);
SetCSSS:
    push rbp
    mov rbp, rsp
    mov ss, si
    mov rax, .next
    push rdi    ; CS
    push rax    ; RIP
    o64 retf
.next:
    mov rsp, rbp
    pop rbp
    ret
ackyacky
  • アセンブラルーチンからC関数を呼び出す場合、RETN(near リターン)命令で帰還する関数はnear CALLで、RETF(far リターン)命令で帰還する関数はfar CALLで呼び出す必要がある
    • 他のコードセグメント(far return)アドレス
  • RETF命令は、small/compactモデルでfarを指定した関数と、medium/largeモデルでnearを指定しなかった関数で使用する
ackyacky

ページングの設定

ページングとは、仮想記憶(仮想メモリ)の方式の一つで、メモリ領域をページと呼ばれる一定の大きさの領域に分割し、物理的なアドレス(番地)とは別に仮想的なアドレスを割り当てて管理する方式

x86-64ではページサイズが4KiB/2MiB/1GiBが用意されている。


プログラムが使うメモリアドレスから物理メモリまでは次のように変換される。

論理アドレス --[セグメンテーション機構]--> リニアアドレス --[ページング機構]--> 物理アドレス

用語 意味 別名
Logical address 論理アドレス セグメントセレクタ:オフセットで表される far pointer
Effective address 論理アドレスのオフセットのこと near pointer
Liner address リニアアドレス(仮想アドレス) セグメントのベースアドレス + Effective address virtual address
Physical address 物理アドレス 物理的なメモリにアクセスするときのアドレス、Linerアドレスから変換する

論理アドレスとリニアアドレスは同じ意味で使われていることが多い

ページングとはリニアアドレスから物理アドレスに変換する処理である。これによって、ページ単位でアドレス変換が行える。ページングによって複雑なアドレス変換を一つに収めることが出来る

今回はリニアアドレスと物理アドレスを一致させるアイデンティティマッピングを採用する

Linux x86_64のメモリアドレッシング

ackyacky
namespace {
  const uint64_t kPageSize4K = 4096;
  const uint64_t kPageSize2M = 512 * kPageSize4K;
  const uint64_t kPageSize1G = 512 * kPageSize2M;

  alignas(kPageSize4K) std::array<uint64_t, 512> pml4_table;
  alignas(kPageSize4K) std::array<uint64_t, 512> pdp_table;
  alignas(kPageSize4K)
    std::array<std::array<uint64_t, 512>, kPageDirectoryCount> page_directory;
}

void SetupIdentityPageTable() {
  pml4_table[0] = reinterpret_cast<uint64_t>(&pdp_table[0]) | 0x003;
  for (int i_pdpt = 0; i_pdpt < page_directory.size(); ++i_pdpt) {
    pdp_table[i_pdpt] = reinterpret_cast<uint64_t>(&page_directory[i_pdpt]) | 0x003;
    for (int i_pd = 0; i_pd < 512; ++i_pd) {
      page_directory[i_pdpt][i_pd] = i_pdpt * kPageSize1G + i_pd * kPageSize2M | 0x083;
    }
  }

  SetCR3(reinterpret_cast<uint64_t>(&pml4_table[0]));
}
ackyacky

64ビットモードでのページングの設定は4つの階層になっている

  1. PML4(Page Map Level4) table
  2. PDP(Page Directory Pointer) table
  3. Page directory
    • ページテーブルへのポインタの配列
    • ファイルシステムのファイルとディレクトリの関係と同じ
  4. Page table

32ビットモードではページディレクトリとページテーブルの2階層だけであった

  • 1つのページサイズは2MiB
  • 1つのページディレクトリのサイズは512
  • kPageDirectoryCountは64

つまり、2(MiB) \times 512 \ timis 64 = 64(GiB) までアイデンティティマップすることが出来る

ackyacky

メモリ管理に挑戦

3つのデータ構造をOSの管理下に移動させたのでメモリ管理を行う。

  • メモリ領域を4KiBページフレーム単位で管理する
    • ページはリニアアドレス上の区間を表現している
    • ページフレームは物理アドレス上の区間を表現している
  • ページフレームの使用中・未使用が判定できるようにする
ackyacky

ページフレーム単位で1ビットを使い、対象のビットが立っていた時には使用中とする。

このようなビットで状態を管理することを ビットマップ と呼ぶ

ビットマップはビット位置とメモリが1対1対応し、そのビットの値で状態が管理できる。つまり、最小のデータ量で状態が管理できる

ackyacky
// frame_id
namespace {
  constexpr unsigned long long operator""_KiB(unsigned long long kib) {
    return kib * 1024;
  }

  constexpr unsigned long long operator""_MiB(unsigned long long mib) {
    return mib * 1024_KiB;
  }

  constexpr unsigned long long operator""_GiB(unsigned long long gib) {
    return gib * 1024_MiB;
  }
}

/** @brief 物理メモリフレーム 1 つの大きさ(バイト) */
static const auto kBytesPerFrame{4_KiB};

class FrameID {
 public:
  explicit FrameID(size_t id) : id_{id} {}
  size_t ID() const { return id_; }
  void* Frame() const { return reinterpret_cast<void*>(id_ * kBytesPerFrame); }

 private:
  size_t id_;
};

static const FrameID kNullFrame{std::numeric_limits<size_t>::max()};

FrameIDでIDをラップすることでページフレームIDであることを明示的に表現している。ID番号順にページフレームを確保することを前提にしている。

ここではユーザー定義リテラルを使って

  • static const auto kBytesPerFrame{4_KiB}; でページフレームのサイズは4KiBとしている
  • KiB をつけることで constexpr unsigned long long operator""_KiB(unsigned long long kib) とマッチしていることを表現している

これで unsigned long long 型の4096の値を返すようになる

ackyacky

ユーザー定義リテラル

ユーザー定義リテラル(User-defined literals)は、123、3.14、"hello"といったリテラルに対して付けられるサフィックスをオーバーロードできるようにすることで、ユーザーがリテラルに意味を持たせられるようにする機能である。

namespace unit_literals {
  // intの大きさを持ち、km (kiro-meter, キロメートル)単位を表すリテラル演算子
  // 上記 1 のバージョン
  int operator"" _kmi(unsigned long long x) {
    return x * 1000;
  }

  // 上記 2 のバージョン
  int operator"" _kmj(const char* s) {
    return std::strtoull(s, nullptr, 10) * 1000;
  }

  // 上記 3 のバージョン
  template<char... S>
  int operator"" _kmk() {
    using CSTR = const char[];
    return operator"" _kmj(CSTR{ S..., '\0' });
  }
}

using namespace unit_literals;

// 123km (123,000m)
int distance1 = 123_kmi;
// 456km (456,000m)
int distance2 = 456_kmj;
// 789km (789,000m)
int distance3 = 789_kmk;
ackyacky

メモリマネージャの使い方

  ::memory_manager = new(memory_manager_buf) BitmapMemoryManager;

  const auto memory_map_base = reinterpret_cast<uintptr_t>(memory_map.buffer);
  uintptr_t available_end = 0;
  for (uintptr_t iter = memory_map_base;
       iter < memory_map_base + memory_map.map_size;
       iter += memory_map.descriptor_size) {
    auto desc = reinterpret_cast<const MemoryDescriptor*>(iter);
    if (available_end < desc->physical_start) {
      memory_manager->MarkAllocated(
          FrameID{available_end / kBytesPerFrame},
          (desc->physical_start - available_end) / kBytesPerFrame);
    }

    const auto physical_end =
      desc->physical_start + desc->number_of_pages * kUEFIPageSize;
    if (IsAvailable(static_cast<MemoryType>(desc->type))) {
      available_end = physical_end;
    } else {
      // 使用中の領域
      memory_manager->MarkAllocated(
          FrameID{desc->physical_start / kBytesPerFrame},
          desc->number_of_pages * kUEFIPageSize / kBytesPerFrame);
    }
  }
  memory_manager->SetMemoryRange(FrameID{1}, FrameID{available_end / kBytesPerFrame});

今回はリニアアドレスを使わないので、物理アドレスが一対一対応する

  • ページフレーム番号:\frac{物理アドレス}{ページフレームの大きさ}
  • フレーム番号:\frac{ページフレーム番号}{4096}

UEFIの仕様と今から使用するメモリ領域のサイズが一致するとは限らないため、領域の大きさの計算は工夫が必要

  • desc->number_of_pages : UEFIを基準としたページ数
    • kUEFIPageSize:UEFIを基準としたページサイズ
    • kBytesPerFrame:今回使用するページサイズ
ackyacky

std::array<MapLineType, kFrameCount / kBitsPerMapLine> alloc_map_;

kernel\memory_manager.hppにて定義

  • MapLineType : 1ページフレームの使用・未使用を1ビットで表現したもの
  • kFrameCount:使用できるフレーム数
  • kBitsPerMapLine8 * sizeof(MapLineType) つまり、MapLineTypeのビット数

ここではフレーム数以上のビットマップが作れるようにしている

ackyacky
// 対象のページフレームのビットを下ろす
Error BitmapMemoryManager::Free(FrameID start_frame, size_t num_frames) {
  for (size_t i = 0; i < num_frames; ++i) {
    SetBit(FrameID{start_frame.ID() + i}, false);
  }
  return MAKE_ERROR(Error::kSuccess);
}

// 対象のページフレームのビットを立てる
void BitmapMemoryManager::MarkAllocated(FrameID start_frame, size_t num_frames) {
  for (size_t i = 0; i < num_frames; ++i) {
    SetBit(FrameID{start_frame.ID() + i}, true);
  }
}

ここでは一度に複数のページフレームの操作をすることを想定している

ackyacky
// 対象のフレームが使用中か確認する
bool BitmapMemoryManager::GetBit(FrameID frame) const {
  auto line_index = frame.ID() / kBitsPerMapLine;
  auto bit_index = frame.ID() % kBitsPerMapLine;

  return (alloc_map_[line_index] & (static_cast<MapLineType>(1) << bit_index)) != 0;
}

// ビットの設定
void BitmapMemoryManager::SetBit(FrameID frame, bool allocated) {
  auto line_index = frame.ID() / kBitsPerMapLine;
  auto bit_index = frame.ID() % kBitsPerMapLine;

  if (allocated) {
    alloc_map_[line_index] |= (static_cast<MapLineType>(1) << bit_index);
  } else {
    alloc_map_[line_index] &= ~(static_cast<MapLineType>(1) << bit_index);
  }
}
ackyacky

メモリ領域の確保

WithError<FrameID> BitmapMemoryManager::Allocate(size_t num_frames) {
  size_t start_frame_id = range_begin_.ID();
  while (true) {
    size_t i = 0;
    for (; i < num_frames; ++i) {
      if (start_frame_id + i >= range_end_.ID()) {
        return {kNullFrame, MAKE_ERROR(Error::kNoEnoughMemory)};
      }
      if (GetBit(FrameID{start_frame_id + i})) {
        // "start_frame_id + i" にあるフレームは割り当て済み
        break;
      }
    }
    if (i == num_frames) {
      // num_frames 分の空きが見つかった
      MarkAllocated(FrameID{start_frame_id}, num_frames);
      return {
        FrameID{start_frame_id},
        MAKE_ERROR(Error::kSuccess),
      };
    }
    // 次のフレームから再検索
    start_frame_id += i + 1;
  }
}

連続で指定のフレーム数だけ確保できる領域を探す。見つかった場合には確保する。

このスクラップは2021/08/25にクローズされました