xv6OSを真面目に読みこんでカーネルを完全に理解する -マルチプロセッサ編-

はじめてのOSコードリーディング ~UNIX V6で学ぶカーネルのしくみにインスパイアされてxv6 OSを読んでます。

UNIX V6自体はx86CPUでは動作しないため、基本的には、UNIXv6をX86アーキテクチャで動くようにしたxv6 OSのリポジトリをForkしたkash1064/xv6-public: xv6 OSのソースコードを読んでいくことにしました。

前回はmain関数で実行されるkvmalloc関数によるページテーブル割り当ての挙動を確認しました。

今回はmpinit関数の挙動を追っていきます。

mpinit関数

mpinit関数はmp.cで定義されている以下の関数です。

「mp」はたぶんマルチプロセッサの意ですが、他のプロセッサを検出する役割を持つ関数がmpinit関数です。

void mpinit(void)
{
  uchar *p, *e;
  int ismp;
  struct mp *mp;
  struct mpconf *conf;
  struct mpproc *proc;
  struct mpioapic *ioapic;

  if((conf = mpconfig(&mp)) == 0) panic("Expect to run on an SMP");
  ismp = 1;
  lapic = (uint*)conf->lapicaddr;
  for(p=(uchar*)(conf+1), e=(uchar*)conf+conf->length; p<e; ){
    switch(*p){
    case MPPROC:
      proc = (struct mpproc*)p;
      if(ncpu < NCPU) {
        cpus[ncpu].apicid = proc->apicid;  // apicid may differ from ncpu
        ncpu++;
      }
      p += sizeof(struct mpproc);
      continue;
    case MPIOAPIC:
      ioapic = (struct mpioapic*)p;
      ioapicid = ioapic->apicno;
      p += sizeof(struct mpioapic);
      continue;
    case MPBUS:
    case MPIOINTR:
    case MPLINTR:
      p += 8;
      continue;
    default:
      ismp = 0;
      break;
    }
  }
  if(!ismp)
    panic("Didn't find a suitable machine");

  if(mp->imcrp){
    // Bochs doesn't support IMCR, so this doesn't run on Bochs.
    // But it would on real hardware.
    outb(0x22, 0x70);   // Select IMCR
    outb(0x23, inb(0x23) | 1);  // Mask external interrupts.
  }
}

それではソースコードを順に読んでいきます。

各種構造体変数の宣言

関数呼び出し後、複数の構造体変数を宣言しています。

uchar *p, *e;
int ismp;

struct mp *mp;
struct mpconf *conf;
struct mpproc *proc;
struct mpioapic *ioapic;

これらはいずれもmp.hで定義されています。

構造体の定義は以下です。

詳細は実際に使用するソースコードを読む際に見ていくため、一旦割愛します。

// See MultiProcessor Specification Version 1.[14]

struct mp {             // floating pointer
  uchar signature[4];           // "_MP_"
  void *physaddr;               // phys addr of MP config table
  uchar length;                 // 1
  uchar specrev;                // [14]
  uchar checksum;               // all bytes must add up to 0
  uchar type;                   // MP system config type
  uchar imcrp;
  uchar reserved[3];
};

struct mpconf {         // configuration table header
  uchar signature[4];           // "PCMP"
  ushort length;                // total table length
  uchar version;                // [14]
  uchar checksum;               // all bytes must add up to 0
  uchar product[20];            // product id
  uint *oemtable;               // OEM table pointer
  ushort oemlength;             // OEM table length
  ushort entry;                 // entry count
  uint *lapicaddr;              // address of local APIC
  ushort xlength;               // extended table length
  uchar xchecksum;              // extended table checksum
  uchar reserved;
};

struct mpproc {         // processor table entry
  uchar type;                   // entry type (0)
  uchar apicid;                 // local APIC id
  uchar version;                // local APIC verison
  uchar flags;                  // CPU flags
    #define MPBOOT 0x02           // This proc is the bootstrap processor.
  uchar signature[4];           // CPU signature
  uint feature;                 // feature flags from CPUID instruction
  uchar reserved[8];
};

struct mpioapic {       // I/O APIC table entry
  uchar type;                   // entry type (2)
  uchar apicno;                 // I/O APIC id
  uchar version;                // I/O APIC version
  uchar flags;                  // I/O APIC flags
  uint *addr;                  // I/O APIC address
};

MP仕様について

ソースコードを読む前に、MP仕様についてまとめておきます。

MPテーブルとは、x86CPUの持っているOSにマルチプロセッサの情報を取得させるための仕組みです。

MPテーブルにはx86CPUのMP仕様に関連した情報が格納されています。

以下は、Interlのドキュメントに記載されていたMP仕様のデータ構造の図です。

FLOATING POINTER STRUCTUREからFIXED-LENGTH HEADERを参照しています。

参考画像：Intel MultiProcessor Specification | ManualsLib

このFLOATING POINTER STRUCTUREは、MPフローティングポインタ構造体であり、xv6OSではmp構造体として定義されていました。

システムにMPフローティングポインタ構造体が存在する場合、そのシステムはMP仕様に準拠していることを意味します。

MPフローティングポインタ構造体には以下の情報が含まれます。

MPコンフィグレーションテーブルへのポインタ
その他のMP情報へのポインタ

MPコンフィグレーションテーブルは、xv6OSでmpconf構造体として定義されています。

後述するmpconfig関数では、MPフローティングポインタ構造体を取得した後に、その情報からMPコンフィグレーションテーブルを取得する処理が定義されています。

では、OSはどうやってMPフローティングポインタ構造体を見つけるのかという点ですが、Interlの仕様書によると、MPフローティングポインタ構造体は以下のいずれかに存在するよう定義されているため、OSはこれらを検索してMPフローティングポインタ構造体の有無を確認することになります。

拡張BIOSデータ領域（EBDA）の最初の1KiB以内の領域
システムベースメモリ領域の最後の1KiB以内の範囲
0x0F0000から0x0FFFFFFの間のBIOS ROMアドレス空間

xv6OSでも、mpsearch関数とmpsearch1関数によって、上記の領域の探索が行われます。

これらの関数については後述します。

次にMPコンフィグレーションテーブルですが、これは通常オプションの設定のようです。

システムがデフォルトの場合はMPコンフィグレーションテーブルの定義は不要ですが、CPUの数が変動する可能性のある場合などは必須になります。(実質的に汎用OSでは必須ってことでしょうか)

MPコンフィグレーションテーブルにはAPICやプロセッサ、バス、割込みに関する設定情報が含まれます。

また新しくAPICという単語がでてきましたが、これはIntelのマルチプロセッサCPUで使用される割込み制御の機構です。

APICについてはxv6OSで割込みコントローラを設定するときに詳しく見ていこうと思います。

参考：APIC - OSDev Wiki

MP仕様についてはWEBページや書籍からはあまり有益な情報が得られなかったので、詳しく知るにはIntelの仕様書を読むのが一番早いと思います。

参考：Chapter 4 Mp Configuration Table; Mp Configuration Data Structures - Intel MultiProcessor Specification [Page 37] | ManualsLib

MPフローティングポインタ構造体の取得

というわけでさっそく以下のコードを見ます。

if((conf = mpconfig(&mp)) == 0) panic("Expect to run on an SMP");

mpconfig関数の引数としてmp構造体を与え、戻り値をmpconf構造体の変数であるconfに格納しています。

ここでは、mpconf構造体の変数confを初期化するとともに、システムがSMPで動作しているかをチェックします。

SMPとは、Symmetric multiprocessingあるいはshared-memory multiprocessingの略称で、要するに複数のCPUがメモリリソースを共有するマルチプロセッサシステムを意味しています。

参考：Symmetric multiprocessing - Wikipedia

参考：Symmetric Multiprocessing - OSDev Wiki

一旦mpconfig関数のソースコードを見てみましょう。

mpconfig関数は、mpinit関数で宣言したmp構造体オブジェクトのアドレスを引数として、mpconf構造体を戻り値とする関数です。

この関数によってMPテーブルが検索され、引数として受け取ったmp構造体オブジェクトと戻り値のmpconf構造体の初期化が行われます。

// Search for an MP configuration table.  For now,
// don't accept the default configurations (physaddr == 0).
// Check for correct signature, calculate the checksum and,
// if correct, check the version.
// To do: check extended table checksum.
static struct mpconf* mpconfig(struct mp **pmp)
{
  struct mpconf *conf;
  struct mp *mp;

  if((mp = mpsearch()) == 0 || mp->physaddr == 0) return 0;
  conf = (struct mpconf*) P2V((uint) mp->physaddr);
  if(memcmp(conf, "PCMP", 4) != 0) return 0;
  if(conf->version != 1 && conf->version != 4) return 0;
  if(sum((uchar*)conf, conf->length) != 0) return 0;
  *pmp = mp;
  return conf;
}

mp構造体は前述したMPフローティングポインタ構造体を指します。

mpconfig関数が呼び出された時点ではまだシステムのMPフローティングポインタ構造体は取得できていないので、まずMPフローティングポインタ構造体を探索する必要があります。

このために呼び出されるのがmpsearch関数とmpsearch1関数です。

// Look for an MP structure in the len bytes at addr.
static struct mp* mpsearch1(uint a, int len)
{
  uchar *e, *p, *addr;
  addr = P2V(a);
  e = addr+len;
  for(p = addr; p < e; p += sizeof(struct mp))
  {
    if(memcmp(p, "_MP_", 4) == 0 && sum(p, sizeof(struct mp)) == 0) return (struct mp*)p;
  }
  return 0;
}

// Search for the MP Floating Pointer Structure, which according to the
// spec is in one of the following three locations:
// 1) in the first KB of the EBDA;
// 2) in the last KB of system base memory;
// 3) in the BIOS ROM between 0xE0000 and 0xFFFFF.
static struct mp* mpsearch(void)
{
  uchar *bda;
  uint p;
  struct mp *mp;

  bda = (uchar *) P2V(0x400);
  if((p = ((bda[0x0F]<<8)| bda[0x0E]) << 4)){
    if((mp = mpsearch1(p, 1024))) return mp;
  } else {
    p = ((bda[0x14]<<8)|bda[0x13])*1024;
    if((mp = mpsearch1(p-1024, 1024))) return mp;
  }
  return mpsearch1(0xF0000, 0x10000);
}

前述した通り、MPフローティングポインタ構造体が存在する場合は、以下のいずれかに配置されています。

拡張BIOSデータ領域（EBDA）の最初の1KiB以内の領域
システムベースメモリ領域の最後の1KiB以内の範囲
0x0F0000から0x0FFFFFFの間のBIOS ROMアドレス空間

これらの領域を検索してMPフローティングポインタ構造体が見つかった場合はmpに格納されます。

このとき、MPフローティングポインタ構造体が見つからない場合、もしくはMPフローティングポインタ構造体が持つMPコンフィグレーションテーブルのアドレスが空の場合はカーネルを終了します。

if((mp = mpsearch()) == 0 || mp->physaddr == 0) return 0;

MPフローティングポインタ構造体は以下の構造になっています。

struct mp {             // floating pointer
  uchar signature[4];           // "_MP_"
  void *physaddr;               // phys addr of MP config table
  uchar length;                 // 1
  uchar specrev;                // [14]
  uchar checksum;               // all bytes must add up to 0
  uchar type;                   // MP system config type
  uchar imcrp;
  uchar reserved[3];
};

mp構造体の定義は上記ですが、Intel仕様書の図の方がイメージしやすいので一緒に貼っておきます。

参考画像：Intel MultiProcessor Specification | ManualsLib

最初の4バイトのSIGNATUREには_MP_が格納されていることが期待されます。

mpsearch関数とmpsearch1関数で探索を行う場合には、このSIGNATUREを探索しています。

physaddrにはMPコンフィグレーションテーブルのアドレスが格納されており、ここからはこの情報を元にMPコンフィグレーションテーブルを取得していきます。

MPコンフィグレーションテーブルの取得

MPフローティングポインタ構造体を取得したら、MPコンフィグレーションテーブルの仮想アドレスを取得し、mpconf構造のポインタ変数confとして格納します。

struct mpconf *conf;
conf = (struct mpconf*) P2V((uint) mp->physaddr);

if(memcmp(conf, "PCMP", 4) != 0) return 0;
if(conf->version != 1 && conf->version != 4) return 0;
if(sum((uchar*)conf, conf->length) != 0) return 0;

MPコンフィグレーションテーブルは以下の構造になっています。

struct mpconf {         // configuration table header
  uchar signature[4];           // "PCMP"
  ushort length;                // total table length
  uchar version;                // [14]
  uchar checksum;               // all bytes must add up to 0
  uchar product[20];            // product id
  uint *oemtable;               // OEM table pointer
  ushort oemlength;             // OEM table length
  ushort entry;                 // entry count
  uint *lapicaddr;              // address of local APIC
  ushort xlength;               // extended table length
  uchar xchecksum;              // extended table checksum
  uchar reserved;
};

以下はIntel仕様書から引用した構造図です。

参考画像：Intel MultiProcessor Specification | ManualsLib

最初の4バイト分の領域にSIGNATUREが格納されていますが、これはPCMPになることが期待されます。

xv6OSでは、取得したMPコンフィグレーションテーブルの確認のため、memcmp関数にて先頭4バイトがPCMPに一致するかをチェックしています。

if(memcmp(conf, "PCMP", 4) != 0) return 0;
if(conf->version != 1 && conf->version != 4) return 0;
if(sum((uchar*)conf, conf->length) != 0) return 0;

また、バージョン情報が適切であるか、データサイズが実際のサイズと一致するかについてもチェックを行っています。

これでmpinit関数の以下の処理が終わり、MPフローティングポインタとMPコンフィグレーションテーブルを取得することができました。

if((conf = mpconfig(&mp)) == 0) panic("Expect to run on an SMP");

MPコンフィグレーションテーブルからIOAPICを取得する

つづいて、mpioapic構造体のioapicにMPコンフィグレーションテーブルのlapicaddrから取得したアドレスを格納します。

int ismp;
struct mpioapic *ioapic;

ismp = 1;
lapic = (uint*)conf->lapicaddr;

mpioapic構造体は以下の構造体です。

struct mpioapic {       // I/O APIC table entry
  uchar type;                   // entry type (2)
  uchar apicno;                 // I/O APIC id
  uchar version;                // I/O APIC version
  uchar flags;                  // I/O APIC flags
  uint *addr;                  // I/O APIC address
};

Intel仕様書の図は以下です。

参考画像：Intel MultiProcessor Specification | ManualsLib

IOAPICは外部割込みを複数のCPUで分散するための機構です。

APICが外部割込みの機構であることは前述しましたが、APICにはローカルAPICとIOAPICの2種類があるようです。

xv6OSではローカルAPICについてはlapic.cで、IOAPICについてはioapic.cで実装されています。

ローカルAPICはCPUに内臓された割込みで、IOAPICはI/Oデバイスから受けとった割込みを、リダイレクションテーブルの情報を元にCPUに通知します。

IOAPICはIOAPICテーブルを持っており、x86CPUはmemory-mapped I/Oを通してこのテーブルのエントリを定義できます。

memory-mapped I/Oは簡単に言うとCPUとI/Oデバイス間で入出力を行う方法の一つで、物理アドレス空間にI/Oデバイスの入出力のための空間を用意し、CPUのメモリの読み書きの機能を利用して入出力を行う方法です。

参考：I/O APICについて - 睡分不足

参考：メモリマップドI/O - Wikipedia

PCIをI/Oデバイスに持つ一般的なシステムの場合、IOAPICはPCIの割込み信号の変化を検知し、リダイレクションテーブルの情報を元にCPUに割込みメッセージを発行します。

この情報はCPU内部のローカルAPICが受け取り、割込みハンドラを呼び出して割込み処理を行った後、EOI(End of Interrupt)コマンドをIOAPICに返すことで、IOAPICに対して割込みの完了を通知します。

詳しくは実際に割込み処理を実装するところまで進んだらやります。たぶん。

参考：APIC - Wikipedia

参考：APIC - OSDev Wiki

参考：IOAPIC - OSDev Wiki

参考：82093AA I/O ADVANCED PROGRAMMABLE INTERRUPT CONTROLLER (IOAPIC)

APICの仕組みは、x86CPUとそのマザーボードのようなマルチプロセッサ環境での割込みを制御するための割込みコントローラが必要になったことで生まれました。

もともと実装されていたPICと呼ばれるシンプルな割込み機構では、マルチプロセッサ構成での割込み処理に対応できなかったようです。

xv6OSもマルチプロセッサ構成を前提としているので、PICからの割込みを無視してローカルAPICとIOAPICを使用した割込み処理を実装します。

参考：P45

xv6OSのコードではmpioapic構造体のioapicにMPコンフィグレーションテーブルのlapicaddrから取得したアドレスを格納しています。

lapicaddrに格納されているのはメモリマップドされたローカルAPICのアドレスです。

lapicaddrを格納する変数lapicはdefs.hでグローバル変数として定義されています。

この関数の中では以降使用することはなく、lapic.cで使用することになります。

extern volatile uint*    lapic;

プロセッサの情報を取得する

lapicaddrの取得が完了した後のループを見てみます。

confには、先ほど取得したMPコンフィグレーションテーブルが格納されています。

Intelの仕様書より、MPコンフィグレーションテーブルエントリは、MPコンフィグレーションテーブルヘッダ(MPコンフィグレーションテーブルの先頭アドレス)から、可変数で続いていくことがわかります。

MPコンフィグレーションテーブルエントリは、先ほど例示したProcessor Entriesの他に、Bus Entry、I/O APIC Entry、I/O Interrupt Entry、Local Interrupt Entryなどがあります。(他にも拡張エントリが存在します)

これらはいずれも先頭1バイトにユニークなEntry Pointが定義されています。

Processor Entry

Bus Entry

I/O APIC Entry

I/O Interrupt Entry

Local Interrupt Entry

参考画像：Intel MultiProcessor Specification | ManualsLib

xv6OSの以下のコードでも、MPコンフィグレーションヘッダの先頭から各エントリをチェックしていき、先頭のEntry Typeの値に応じて処理を分岐させています。

for(p=(uchar*)(conf+1), e=(uchar*)conf+conf->length; p<e; ){
  switch(*p){
          
  case MPPROC:
    proc = (struct mpproc*)p;
    if(ncpu < NCPU) {
      cpus[ncpu].apicid = proc->apicid;  // apicid may differ from ncpu
      ncpu++;
    }
    p += sizeof(struct mpproc);
    continue;
          
  case MPIOAPIC:
    ioapic = (struct mpioapic*)p;
    ioapicid = ioapic->apicno;
    p += sizeof(struct mpioapic);
    continue;
          
  case MPBUS:
  case MPIOINTR:
  case MPLINTR:
    p += 8;
    continue;
          
  default:
    ismp = 0;
    break;
  }
}

チェックしているエントリは以下のように定義されています。

// Table entry types
#define MPPROC    0x00  // One per processor
#define MPBUS     0x01  // One per bus
#define MPIOAPIC  0x02  // One per I/O APIC
#define MPIOINTR  0x03  // One per bus interrupt source
#define MPLINTR   0x04  // One per system interrupt source

Processor Entryの情報取得

まずはProcessor Entryの場合です。

ここではmpproc構造体のオブジェクトとしてProcessor Entriyを取得し、Local APIC IDの値をすべてのcpus配列に順に格納しています。

case MPPROC:
  proc = (struct mpproc*)p;
  if(ncpu < NCPU) {
    cpus[ncpu].apicid = proc->apicid;  // apicid may differ from ncpu
    ncpu++;
  }
  p += sizeof(struct mpproc);
  continue;

ちなみにここで使用されているNCPUはparam.hで以下のように定数として定義されています。

xv6OSは最大で8CPUまでサポートしているようです。

#define NCPU      8  // maximum number of CPUs

IOAPICの情報取得

続いてはIOAPICの情報を取得します。

case MPIOAPIC:
  ioapic = (struct mpioapic*)p;
  ioapicid = ioapic->apicno;
  p += sizeof(struct mpioapic);
  continue;

各構造体などについては前述したので割愛します。

IMCRの変更

これでmp.cの処理はほぼ完了しました。

最後にIMCRを無効化します。

IMCRは割り込みモード構成レジスタと呼ばれ、PICモードから変更するためにはIMCRの変更が必要になるようです。

参考：x86 - Where is the IMCR defined in the docs? - Reverse Engineering Stack Exchange

参考：OSDev.org • View topic - Set IMCR to 0x1 to mask external interrupts?

参考：Default Configurations; Symmetric I/O Mode - Intel MultiProcessor Specification [Page 31] | ManualsLib

まとめ

次回はlapicinit関数から始めます。

今回取得した情報を利用して割込みコントローラを実装するようです。

だんだん頭がついてこなくなってきたのでちょっと気合入れて頑張ろうと思います。

参考書籍

Published Jan 31, 2022

リバースエンジニアになりたいCTF Player(Team: 0nePadding)。WinDbgとYARAが好き。OSCP / CISSP / AtCoder 緑 Microsoft Japanに所属してます。発言はすべて個人の見解。かしわば on Twitter

xv6OSを真面目に読みこんでカーネルを完全に理解する -マルチプロセッサ 編-

もくじ

mpinit関数

各種構造体変数の宣言

MP仕様について

MPフローティングポインタ構造体の取得

MPコンフィグレーションテーブルの取得

MPコンフィグレーションテーブルからIOAPICを取得する

プロセッサの情報を取得する

Processor Entryの情報取得

IOAPICの情報取得

IMCRの変更

まとめ

参考書籍

xv6OSを真面目に読みこんでカーネルを完全に理解する -マルチプロセッサ編-