あかりラボ

七森中赤座あかり研究室の活動日記

C++ LLVM passでループを扱いたい人に送る記事

タイトルのとおりです．もう誰もLLVM IRで泣かないような世界を作るのが夢です．

LLVM IRには古いやつ(Legacy Pass Manager)と新しいやつ(New Pass Manager)がありますが，本記事は新しいやつ向けです．

関数内のループを抽出する

まずLoopInfoを取ってからイテレータを使ってループ(Loopクラス)を取り出します．一番外側のループのみ抽出できます．

ModulePass::run(Module& M, ModuleAnalysisManager& MAM)  {
  FunctionAnalysisManager &FAM = MAM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();

  for (auto &F : M) {
    if (!F.isDeclaration()) {
      LoopInfo &li = FAM.getResult<LoopAnalysis>(F);
      for (LoopInfo::iterator i = li.begin(), e = li.end(); i != e; i++) {
        // *i で Loop* が取れる
      }
    }
  }
}

ループ内ループを取る

  // Loop *loop;
  const std::vector<Loop*> &subloops = loop->getSubLoops();

ループの親ループを取る

一番外のループだった場合nullptrが返ります．

// Loop *loop;
Loop *parent = loop->getParentLoop();

ループ内の命令列を取る

// Loop *loop;
for (Loop::block_iterator bb = loop->block_begin(); bb != loop->block_end(); bb++) {
  BasicBlock *BB = *bb;
  for (auto &I: *BB) {
    // I は Instruction&
  }
}

そのループ内に属する全てのBasicBlockを取る

// Loop *loop;
for (Loop::block_iterator bb = loop->block_begin(); bb != loop->block_end(); bb++) {
  BasicBlock *BB = *bb;
  if (loop->contains(BB)) {
    // BB は loop に属する 
  }
}

ループにプリヘッダを付ける

hoistingなどに有用です．

// Loop *loop;
BasicBlock *newBB = InsertPreheaderForLoop(loop, nullptr, nullptr, nullptr, false);

付けたプリヘッダに命令を挿入する際は，IRBuilderを利用します

IRBuilder<> IRB(&newBB->back());

Linuxのmemmap_allocについて

LinuxにはFLATMEMやSPARSEMEMなど，物理メモリを管理するための仕組み（物理メモリモデル）が複数用意されていますが， それらは全てpage構造体(struct page)の配列を利用しています．

各物理メモリモデルの解説については以下を参照してください．

qiita.com

さて，通常のLinuxの物理メモリ割り当て関数(alloc_pagesなど)はこの物理メモリモデルに依存しているわけですが， 物理メモリモデルの実装に利用されるpage構造体の配列を格納するための物理メモリ領域はどのように割り当てられているのでしょうか？

当然alloc_pagesなどは利用できないので，それ専用の物理メモリ割り当て関数が用意されています．それがmemmap_allocです．

memmap_allocは以下のように実装されています．

void __init *memmap_alloc(phys_addr_t size, phys_addr_t align,
              phys_addr_t min_addr, int nid, bool exact_nid)
{
    void *ptr;

    if (exact_nid)
        ptr = memblock_alloc_exact_nid_raw(size, align, min_addr,
                           MEMBLOCK_ALLOC_ACCESSIBLE,
                           nid);
    else
        ptr = memblock_alloc_try_nid_raw(size, align, min_addr,
                         MEMBLOCK_ALLOC_ACCESSIBLE,
                         nid);

    if (ptr && size > 0)
        page_init_poison(ptr, size);

    return ptr;
}

nidとexact_nidはNUMAノード関係なので，一旦無視してmemblock_alloc_try_nid_rawを見ます．

void * __init memblock_alloc_try_nid_raw(
            phys_addr_t size, phys_addr_t align,
            phys_addr_t min_addr, phys_addr_t max_addr,
            int nid)
{
    memblock_dbg("%s: %llu bytes align=0x%llx nid=%d from=%pa max_addr=%pa %pS\n",
             __func__, (u64)size, (u64)align, nid, &min_addr,
             &max_addr, (void *)_RET_IP_);

    return memblock_alloc_internal(size, align, min_addr, max_addr, nid,
                       false);
}

memblock_alloc_internalを呼び出しているだけのようです．

static void * __init memblock_alloc_internal(
                phys_addr_t size, phys_addr_t align,
                phys_addr_t min_addr, phys_addr_t max_addr,
                int nid, bool exact_nid)
{
    phys_addr_t alloc;

    /*
    * Detect any accidental use of these APIs after slab is ready, as at
    * this moment memblock may be deinitialized already and its
    * internal data may be destroyed (after execution of memblock_free_all)
    */
    if (WARN_ON_ONCE(slab_is_available()))
        return kzalloc_node(size, GFP_NOWAIT, nid);

    if (max_addr > memblock.current_limit)
        max_addr = memblock.current_limit;

    alloc = memblock_alloc_range_nid(size, align, min_addr, max_addr, nid,
                    exact_nid);

    /* retry allocation without lower limit */
    if (!alloc && min_addr)
        alloc = memblock_alloc_range_nid(size, align, 0, max_addr, nid,
                        exact_nid);

    if (!alloc)
        return NULL;

    return phys_to_virt(alloc);
}

memblock_alloc_range_nidで割り当てられたメモリ領域の先頭物理アドレスを仮想アドレスに変換して返していることが分かります．

memblock_alloc_range_nidの中では，ここが実際の割り当て処理となります．

 found = memblock_find_in_range_node(size, align, start, end, nid,
                        flags);
    if (found && !memblock_reserve(found, size))
        goto done;

memblock_find_in_range_nodeで使用可能なメモリブロックの中から[start, end]の範囲でalignバイトにアラインメントされたsizeバイトのメモリ領域を探します．見つかったらmemblock_reserveでその領域を予約済みにマークします．

ここで，Linuxのメモリブロックについて少し説明します． struct memblockは以下のように定義され，Linuxが使用可能なメモリ領域を表すmemory，予約済みメモリ領域を表すreservedを持っています． これらはx86ならe820，aarch64ならdevicetreeなどで取得したメモリマップから構築されます．

struct memblock {
         bool bottom_up;
         phys_addr_t current_limit;
         struct memblock_type memory;
         struct memblock_type reserved;
#ifdef CONFIG_HAVE_MEMBLOCK_PHYS_MAP
         struct memblock_type physmem;
#endif
};

struct memblock_typeはメモリ範囲を表すstruct memblock_regionの配列で定義されています．以上を踏まえ，memblockのイメージ図を描いてみます．

memblockのイメージ

memblock_find_in_range_nodeは，memblockの中で使用可能なメモリ領域の中から，予約済み領域を除いた部分からsizeバイトのメモリ領域を探します．

濃い青色の範囲からsizeバイトのメモリ領域を探す

memblock_find_in_range_nodeが呼んでいるfor_each_mem_rangeは，使用可能かつ予約済みでない領域（図では濃い青色の範囲）をイテレートします．

あかり的気になる論文集【随時更新】

タイトルの通りです．

気になった/読んだ論文のタイトルと大まかな概要をまとめたメモとして活用していくつもりです．

詳しく読んだら別に1本の記事を書こうかなと思います．

TwinVisor: Hardware-isolated Confidential Virtual Machines for ARM

https://dl.acm.org/doi/10.1145/3477132.3483554

ELI: bare-metal performance for I/O virtualization

Efficient and Scalable Paravirtual I/O System

Efficient and Scalable Paravirtual I/O System | USENIX

通称ELVIS．Efficient and ScaLable ParaVirtual I/O System で ELVIS らしい．無理があるでしょ

(No)Compromis: paging virtualization is not a fatality

Rethinking the Library OS from the Top Down

https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/asplos2011-drawbridge.pdf

WSL1のpicoprocessの元になったDrawbridgeの論文

Process Implanting: A New Active Introspection Framework for Virtualization 読んだ

お久しぶりです、あかりです。

さらっと読んだ論文を雑に内容をまとめてメモとして残していきたいと思います。習慣化できたらいいね。

今回は、Process Implanting: A New Active Introspection Framework for Virtualization (2011) *1を読みました。

Process Implanting という不穏な名前から分かるように、VMM からゲスト OS にプロセスを「埋め込み」ます。埋め込むと言っても、ゲスト OS のプロセスをただ生やすのではなく、プロセスの中にプロセスを埋め込みます。変態的でいいですね。

論文から引用

プロセスを埋め込まれたプロセス (victim process) は、外っ面(プロセス名, pid など)はそのまま、中のプロセスの処理をします。中のプロセスは、VMM の連携と保護によって、他プロセスから終了されることはありません。中のプロセスは VMM によって中断可能で、すると victim process の元のコンテキストは復元され、何食わぬ顔で victim process の処理をします。中のプロセスが終了すると、これもまた victim process の元のコンテキストは復元され victim process の処理を始めます。

このプロセスは、以下の4つの要件を守るように設計されています。

  • ステルス性 (Stealthiness)

ゲストOS上の他プロセスから見つからない。

  • 分離性 (Isolation)

なるべくゲストOSの資源に頼らず実行する。例えば、動的リンクされる共有Cライブラリが汚染されている可能性を考慮し、埋め込まれたプロセスには全てのライブラリを静的リンクする。

  • 堅牢性 (Robustness)

他プロセスやゲストOSによってプロセスが終了されない。

  • 完全性 (Completeness)

埋め込まれたプロセスが終了する際、victim process やゲストOSに証拠を残さないようにする。

背景

ユーザプロセスとして動くマルウェア検知ツールや解析エンジンは、同じユーザプロセスとして動くマルウェアに脆弱です。マルウェアにとって、マルウェア対策ツールのプロセスを検知し対策を取ることは簡単なためです。

そこで考えられたのが VMM や外の VM からマルウェア検知や解析を行う VMI (Virtual Machine Introspection) という手法です。これによりマルウェアによって対策ツールの存在を認知されることはなくなりましたが*2、マルウェアのコンテキスト取得が難しいという問題があります (semantic gap, 例: VMM からプロセスの backtrace は取れない)。

この論文では、Process Implating という手法を使って対策ツールをマルウェアにとって人畜無害そうなプロセスにカモフラージュすることで、マルウェアからの検知、終了を逃れつつコンテキストを得るということをします。

方法(ざっくりと)

Process Implanting の流れ (論文から引用)

initialization

埋め込みたいプロセスのイメージを VM に割り当てられている物理メモリの領域外にマップします。

camouflage

victim process へのコンテキストスイッチ時に process を埋め込むという手法を採用しています。ゲスト Linux の __switch_to に trap をしかけることで、コンテキストスイッチ発生時に毎回 VMM への遷移が発生するため、victim process へのコンテキストスイッチを検知することができます。

implanting

ざっくりと次のような手順で victim process に プロセスを埋め込みます。

  1. victim プロセスのコンテキストを保存する
  2. 物理ページテーブル (おそらく VMM が内部で持っている ゲスト物理アドレス→ホスト物理アドレスのページテーブル) を initialization フェーズでマップしたメモリ領域を指すように書き換える
  3. 2と辻褄が合うようにシャドウページテーブルと Memory Descriptor を書き換える
  4. カーネルスタック上のユーザレジスタを埋め込むプロセスのレジスタの値に設定する
  5. コンテキストスイッチが発生、埋め込まれたプロセスの処理を開始する

プロセスのアドレス空間が埋め込まれたプロセスに切り替わる様子 (論文から引用)

checkpointing

埋め込まれたプロセスを中断し、コンテキストを保存し victim process に処理を戻します。埋め込まれたプロセスはいつでも再開できます。

exit

埋め込まれたプロセスが終了するとき、そのまま exit システムコールを発行してしまうと victim process も一緒に逝くことになるので、ここでも VMM の介入が必要になります。

ゲスト Linux の sys_exit と sys_exit_group に trap をしかけることで、exit システムコール時に VMM に処理が遷移するので、ここで victim process の復元を行います。

victim process の復元後は、自身がいままで他のプロセスを埋め込まれていたことなど知らずに、処理を再開します。

*1:https://www.cs.purdue.edu/homes/dxu/pubs/SRDS11.pdf

*2:VMM の存在を認知されることはある

aarch64 HCR_EL2.{CD, ID}

When the value of HCR_EL2.CD is 1:
— All stage 2 translations for data accesses to Normal memory are Non-cacheable.
— All accesses to the EL1&0 stage 2 translation tables are Non-cacheable.
• When the value of HCR_EL2.ID is 1:
— All stage 2 translations for instruction accesses to Normal memory are Non-cacheable.

CDを1にすると，

  • Stage 2変換を介してアクセスされる Normal Memory は全て Non-cacheable になる．

  • Stage 2変換テーブルへのアクセスは Non-cacheable になる．

IDを1にすると，

  • Stage 2変換を介した命令アクセスは全て Non-cacheable になる．

使い所がマジで分からん

aarch64 デバイスメモリ属性 GREについて

aarch64では、ページテーブルエントリによってページ単位でメモリ領域に属性をつけることができます。普通のメモリ領域とデバイスメモリ領域(MMIO領域など)にそれぞれNormalとDeviceという属性を付けるのが一般的です。

Deviceとマークされたメモリ領域はキャッシュされず、投機的なアクセスも禁止されます。そして、この領域はXN bitで実行不可能とマークすることが推奨されています*1。

さらに、Deviceではもっと詳細に属性を以下の4種類のうちから指定する必要があります。

  • GRE
  • nGRE
  • nGnRE
  • nGnRnE

GREは、それぞれ以下の意味を持ちます。

  • G(Gathering)

write combiningを許可する。つまり、複数の同一領域への読み込み/書き込みを内部で単一の読み込み/書き込みにまとめて一回で処理する。詳細は以下を参照。

Understanding Write Combining on Arm - Resources - Research Collaboration and Enablement - Arm Community

  • R(Re-ordering)

メモリアクセスの順序変更を許可する。Normalメモリへのアクセス時と同じRe-orderingが発生し得る。

  • E(Early Write Acknowledgement)

posted writeを許可する。つまり、CPUがデバイスメモリ領域にwriteをしたときにデバイスからの到達応答を待たずにwriteアクセスを完了させる。

全てを許可したい場合はGREを指定し、Eだけを許可したい場合はnGnREを指定する必要があります。

使用方法

結局どのデバイス領域にどの属性を付ければええねん、というのはLinuxのioremapを基準に考えると分かりやすいです。

https://dri.freedesktop.org/docs/drm/driver-api/device-io.html#architecture-exampleから引用、一部改変:

API Memory region type and cacheability
ioremap_np() Device-nGnRnE
ioremap() Device-nGnRE
ioremap_wc() Normal-Non Cacheable
ioremap_cache() Normal-Write-Back Cacheable

ioremap_wc()はDevice-GREと同義な気がしますが(実際にそういうパッチも出ている)、Normal Non Cacheableとして実装されています。

GREはメモリアクセスの順序があまり気にならないFrameBuffer領域によく使用されているみたいです。

結論

何も考えずにnGnRnEを指定するのはあまりよろしくない

*1:DDI0487H B2.1.2 Memory type overview 参照