raw_ptr in Chromium

メモリ保全は難しく、Google Secutiry Blogによると2022のQ1に発見されたChromiumのバグのうち50%以上のバグがUse-after-free起因だったらしい。
以前のノートで言及したMiracle Ptrはuse-after-freeを防ぐためいに導入されたChromium内でraw_ptrを乗っ取っているsmart pointerで、中身はBackupRefPtrという賢いポインタ。

BackupRefPtrについてはドキュメントがあり、これはMiracle PtrのReadmeのリンクから探せるpublicドキュメントです。

概要

raw_ptrはメモリの先頭にデータを書き込んでおくことでそのメモリの状態を他のところから参照したときでも取得でき、メモリの状態に応じた処理ができるという仕組み。

raw_ptrはallocateされているメモリの先頭にreference countなどのデータを持つヘッダーを書き込んでいる。以下のようにAllocateされているエリアのうちヘッダーのあとの部分が実際のメモリの保存したデータになっている。

(Google Security Blogより引用)

この仕組みをraw_ptrというクラスでラップしている。

もしreference countが0より大きいときにpointerがfree/deleteされたらメモリを即解放するのではなくヘッダーに情報を上書きして他のraw_ptrが参照できるようにしている。これによってuse-after-freeによる危険を取り除いている。
メモリはreference countが0になったらようやく解放される。

ちなみに実装は[base/allocator/partition_allocator/pointers/raw_ptr.h]((https://source.chromium.org/chromium/chromium/src/+/main:base/allocator/partition_allocator/pointers/raw_ptr.h)にあるが長いのでbase/memory/raw_ptr.hをincludeしよう。

BackupRefPtrの実装

wrapped_ptr_に実際のアドレスが保存されている。
raw_ptrクラスは先頭のデータを追加したり処理したりしてくれている。

大まかな流れは、allocate時にallocateしたというフラグをtrueにし、破壊されたときにfalseにする。ポインタが生きているかはこのフラグを確認すればわかる。
raw_ptrの作成時にref countをインクリメントし、破壊時にデクリメントする。
もしref countが0より大きいなら参照しているやつがいるので残しておいて、0になったらフリー。
なのでallocateフラグがfalseになっていてもref countが正の数になっているケースがあり、このときはまだフリーせず、次に参照されたときにもuse-after-freeにならないようにする・あるいは違うメモリによって上書きされていないようにする。

タグの実装

Allocatedされているエリアの先頭にタグを書くのがraw_ptrだが、そのタグはPrtitionRefCount型として処理している。
partition_ref_count.hのドキュメントを見ると、タグの中身はこんな感じ

• 0ビット目：is_allocatedのフラグ。construct時に1になり、ReleaseFromAllocatorで0にんる
• 1-31ビット目：ptr_count。raw_ptrのreferenceが何個あるかを保存。Aquireで++、Releaseで–。
• 32ビット目：dangling_detected。Dangling Ptrを検知するためのフラグ。
• 33ビット目：needs_mac11_malloc_size_hack。なんですか？
• 34-63ビット目：unprotected_ptr_count。DisableDanglingPtrDetectioのraw_ptrのカウント。AcquireFromUnprotectedPtrで++、ReleaseFromUnprotectedPtrで–。

is_allocated、ptr_count、unprotected_ptr_countがすべて0のときallocationは開放されている。

raw_ptrの値を変える時

以下Dangling Ptrについては無視する。

まずはraw_ptrをリセットする方を見ていく。以下のようなケース。

// dtor
~raw_ptr();

// `window` を null　でリセット
raw_ptr<aura::Window> window = nullptr;

// 自分が所有していない`new_window_owned_by_other`の生ポインタで上書き
window = new_window_owned_by_other.get();

constexpr ~raw_ptr() noexceptはdesturct時に明らかにリセットしてる。
constexpr raw_ptr& operator=(std::nullptr_t) noexceptはraw_ptrにnullptrが代入されるときに呼ばれる関数で、すなわちリセット時の操作が実装されている。
constexpr raw_ptr& operator=(T* p) noexceptでは新しいポインタが代入されるときに呼ばれる関数で、これもリセットである。
両者の関数でImpl::ReleaseWrappedPtr()が呼ばれている。
BackupRefPtrの場合の実装はraw_ptr+backup_ref_impl.hにあり、やっていることは大きく2つ。

// 簡略ver
template <typename T>
static constexpr void ReleaseWrappedPtr(T* wrapped_ptr) {
  uintptr_t address = partition_alloc::UntagPtr(UnpoisonPtr(wrapped_ptr));
  if (IsSupportedAndNotNull(address))
    ReleaseInternal(address);
}

UntagPtrの中身はaddress & internal::kPtrUntagMaskで、以下のように定義されているkPtrUntagMaskをmaskしている

constexpr uint64_t kPtrTagMask = 0xff00000000000000uLL;
constexpr uint64_t kPtrUntagMask = ~kPtrTagMask;

ちなみに"~"という演算子はビットごとの補数。つまりaddress & internal::kPtrUntagMaskはタグを取り除くという操作をしていることになる。

そののちにaddressがIsSupportedAndNotNullならばReleaseInternalを呼ぶ。つまり上書きしたいポインタであるwrapper_ptrがnullptrならUntagしたままで終わり。raw_ptrがnullptr状態ならタグは空っぽらしい。

一方ReleaseInternalが呼ばれるケース、すなわち新しいポインタを上書きしたい場合について。
PartitionAllocGetSlotStrtInBRPPoolでaddressに対応するallocated slotの先頭を獲得してるが、これはadressはslot内ならどこでもよいかららしい。マジで？
そのアドレスを用いてPositionRefCountPointerからslotの先頭に保存されているreference countを獲得する。
簡略版は以下。

PrtitionRefCount* PartitionRefCountPointer(uintptr_t slot_start) {
  uintptr_t refcount_address = slot_start - sizeof(PartitionRefCount);
  return reinterpret_cast<PartitionRefCount*>(refcount_address);
}

このPartitionRefCountに対してReleaseを呼んでおり、つまりptr_countがデクリメントされた。Releaseの中ではReleaseCommonを呼んでおり、もしcountがkPtrCountMaskとのorでtrueならつまりまだそのアドレスを参照しているポインタがあるということなので保持したい。そうでない場合はfreeしたい。ここでcountの値が活用されいてた。概要で書いたとおり、ptr_countが0に到達するまではフリーしていない。
freeしたい場合はRelease()がtrueを返すので、PartitionAlocFreeForRefCountingが呼ばれてFreeされる。

逆にセットする側。
window = new_window_owned_by_other.get();はポインタのセットもしている。
constexpr raw_ptr& operator=(T* p) noexceptでは上述のImpl::ReleaseWrappedPtr()のあとにImpl::WrapRawPtrも呼んでいる。

PA_ALWAYS_INLINE constexpr raw_ptr& operator=(T* p) noexcept {
  Impl::ReleaseWrappedPtr(wrapped_ptr_);
  wrapped_ptr_ = Impl::WrapRawPtr(p);
  return *this;
}

Impl::WrapRawPtrではImpl::ReleaseWrappedPtr()とは逆にAcquireInternalを呼んでいて、Acquireからptr_countをインクリメントしている。

以上がおおまかな流れ。

raw_ptrを参照する時

constexpr T* operator->() constが参照する関数。
中身はGetForDeferenceを呼んでいるだけでその中身はSafelyUnwrapPtrForDereference。

以下簡略版

static constexpr T* SafelyUnwrapPtrForDereference(T* wrapped_ptr) {
  uintptr_t address = partition_alloc::UntagPtr(wrapped_ptr);
  if (IsSupportedAndNotNull(address)) {
    PA_BASE_CHECK(wrapped_ptr != nullptr);
    PA_BASE_CHECK(IsPointeeAlive(address));
  }
  return wrapped_ptr;
}

IsPointeeAlive() → IsAliveでタグとkMemoryHeldByAllocatorBitとのビット&からis_allocatedを確認して、ポインタがまだ生きているかCheck。
この確認をパスしたならまだ生きているということなので安全にアクセスできる。

is_allocatedはいつ0になる？

ところでcountが0になるまでまつことでuse-after-freeを防ぐのはわかったが、ここまでではis_allocatedが0にならないのでずっとIsPointeeAlive() = trueのままである。
ownershipを持つやつが破壊された時に0にセットされるはず。
追っていくとallocator_shim::internal::PartitionBatchFreeがそんな感じのことをやっていそう。
PartitionAllocのDispatcherのInitialize時にその関数が挿入されているっぽいが長くなるのでこのノートではここまで。

unique_ptrは？

ここまでraw_ptrの中だけで話してきたが、Chromiumのポインタはraw_ptrだけではない。
例えばunique_ptrがdestructしたときにraw_ptrが保持しっぱなしみたいなケースがuse-after-freeの典型例だが、unique_ptrのref countも一緒に行っていないとこのシステムは成り立っていないはず。

std::unique_ptr<A> a = std::make_unique<A>();
// BはAのraw_ptrを持つ
std::unique_ptr<B> b = std::make_unique<B>(a.get());

// a を破壊
a = nullptr;
// a を参照するような関数
b->ReferToA();

例えばこのケースではReferToA()という関数でdestructされたはずのaにアクセスしないように、is_allocatedがa=nullptrによって0になっていてほしい。しかしaはunique_ptrなので？
unique_ptrのref countはどうやっている？内部実装にraw_ptrを使用していたりしますか…？
これもPartitionAllocのDispatcherとかを読まないとわからなさそう。

Partition Alloc

ところで上記の説明ではis_allocatedの値が〜とか言っているが、そもそもメモリをフリーして他の何かが上書きしたらallocationもなにもなくis_allocatedの位置のビットが書き換えられている可能性もあるのでは？
という疑問もあるが、それはChromiumがPartitionAllocというデザインを採用していることで守られている。
かんたんに言うと、メモリ領域をオブジェクトの種類と確保するサイズによってわかることにして、allocationの区切り位置を毎回同じにしている。このデザインであれば、毎回is_allocatedなどタグの各値の位置は不変なので正しく処理できる。

Chromiumのコード内でもBUILDFLAG(USE_PARTITION_ALLOC*)でガードされているところが散見される。

各Partitionのサイズは1024byteに抑えれているっぽい？(kMaxMemoryTaggingSize = 1024)

Note

std::memory_order_relaxed というやつを見かけた。
memory_orderの説明によると、マルチスレッドでの最適化で置きがちなメモリアクセスの順序が起きると困る際に順番を入れ替えないように強制するためのフラグらしい。今日CPU入門で読んだやつだ。