yohhoyの日記

2017-03-17

危険な型変換:&T→&mut T

プログラミング言語Rustにおける、&T から &mut T への型変換*1と同オブジェクトに対する変更操作は、未定義動作(undefined behavior)とされている。これはRustコンパイラのBorrow Checkerを騙すだけでなく、該当プログラムの動作が不定となり深刻な障害要因になり得る。*2

下記プログラムをrustc 1.15.1でコンパイル&実行すると、Debugビルドではおそらく期待通り動作するが、Releaseビルドでは★のassert!マクロより実行時エラーが報告される*3。なお明示的な#[allow(mutable_transmutes)]属性を削除すれば、コンパイル時lint検査エラー*4として危険なコードを検出できる。

// &i32 → &mut i32型変換と代入
#[allow(mutable_transmutes)]
#[inline(never)]
fn danger(p: &i32) {
  unsafe {
    *std::mem::transmute::<&_, &mut _>(p) = 0  // NG: 未定義動作
  }
}

#[allow(unused_mut)]
fn main() {
  let mut x = 1;
  danger(&x);
  assert!(x == 0);  // ★
}

イミュータブル参照型(&T)からミュータブル生ポインタ型(*mut T)への型キャスト*5はlint検査を通ってしまうが、同様に未定義動作を引き起こす。

// &i32 → *mut i32型変換と代入
#[inline(never)]
fn danger(p: &i32) {
  unsafe {
    *(p as *const _ as *mut _) = 0  // NG: 未定義動作
  }
}

イミュータビリティとUnsafeCell

Rust言語におけるイミュータビリティ(immutability; 不変性)のセマンティクスは、変数束縛に対して“値の変更を行えない”という制約に加え、変数束縛の“値が変更されることは無い”という保証の2つの側面を持つ。前掲コードでは関数dangerにイミュータブル参照(&i32)しか渡しておらず、セマンティクス上はassert!マクロ到達までに変数xの値が変わることが無いと判断できる。Rustコンパイラにはこの判断に基づいた最適化を行う自由度があるため、特にReleaseビルドで問題が顕在化しやすい。

"Interior Mutability"を安全に実現するために、通常のイミュータビリティ・セマンティクスを無視するような特別扱いが必要となる。この目的のために std::cell::UnsafeCell が提供されており、Rustコンパイラでは同構造体を特別扱いする。標準ライブラリstd::cell::RefCellstd::sync::Mutexでは、その内部実装としてUnsafeCellを利用している。同APIリファレンスより引用(下線部は強調)。

The core primitive for interior mutability in Rust.

UnsafeCell<T> is a type that wraps some T and indicates unsafe interior operations on the wrapped type. Types with an UnsafeCell<T> field are considered to have an 'unsafe interior'. The UnsafeCell<T> type is the only legal way to obtain aliasable data that is considered mutable. In general, transmuting an &T type into an &mut T is considered undefined behavior.

The compiler makes optimizations based on the knowledge that &T is not mutably aliased or mutated, and that &mut T is unique. When building abstractions like Cell, RefCell, Mutex, etc, you need to turn these optimizations off. UnsafeCell is the only legal way to do this. When UnsafeCell<T> is immutably aliased, it is still safe to obtain a mutable reference to its interior and/or to mutate it. However, it is up to the abstraction designer to ensure that no two mutable references obtained this way are active at the same time, and that there are no active mutable references or mutations when an immutable reference is obtained from the cell. This is often done via runtime checks.

Note that while mutating or mutably aliasing the contents of an & UnsafeCell<T> is okay (provided you enforce the invariants some other way); it is still undefined behavior to have multiple &mut UnsafeCell<T> aliases.

Types like Cell<T> and RefCell<T> use this type to wrap their internal data.

The Rustonomicon, The Rust Referenceより該当箇所を一部引用。("UB"=Undefined Behavior)

mem::transmute<T, U> takes a value of type T and reinterprets it to have type U. The only restriction is that the T and U are verified to have the same size. The ways to cause Undefined Behavior with this are mind boggling.

  • (snip)
  • Transmuting an & to &mut is UB
    • Transmuting an & to &mut is always UB
    • No you can't do it
    • No you're not special
  • (snip)
https://doc.rust-lang.org/nomicon/transmutes.html

The following is a list of behavior which is forbidden in all Rust code, including within unsafe blocks and unsafe functions. Type checking provides the guarantee that these issues are never caused by safe code.

  • (snip)
  • &mut T and &T follow LLVM's scoped noalias model, except if the &T contains an UnsafeCell<T>. Unsafe code must not violate these aliasing guarantees.
  • Mutating non-mutable data (that is, data reached through a shared reference or data owned by a let binding), unless that data is contained within an UnsafeCell<T>.
  • (snip)
https://doc.rust-lang.org/reference.html#behavior-considered-undefined

LLVM Language Reference Manual, Parameter Attributesよりnoaliasに関する説明を引用。

This indicates that objects accessed via pointer values based on the argument or return value are not also accessed, during the execution of the function, via pointer values not based on the argument or return value. The attribute on a return value also has additional semantics described below. The caller shares the responsibility with the callee for ensuring that these requirements are met. For further details, please see the discussion of the NoAlias response in alias analysis.

Note that this definition of noalias is intentionally similar to the definition of restrict in C99 for function arguments.

For function return values, C99's restrict is not meaningful, while LLVM's noalias is. Furthermore, the semantics of the noalias attribute on return values are stronger than the semantics of the attribute when used on function arguments. On function return values, the noalias attribute indicates that the function acts like a system memory allocation function, returning a pointer to allocated storage disjoint from the storage for any other object accessible to the caller.

http://llvm.org/docs/LangRef.html#noalias

関連URL:

*1:Rust型システムにおいて同型変換は安全でない(unsafe)ため、明示的にunsafeキーワードを指定する必要がある。

*2:Rustにおける未定義動作は、プログラミング言語C/C++における同用語と同じ意味を持つ。つまり未定義動作のプログラムに対してはいかなる保障も存在せず、何が起きても不思議ではない。

*3#[inline(never)]属性を削除すればReleaseビルドでも期待通り動作するようになるが、本質的に未定義動作のため何ら解決していないことに注意。より複雑な関数呼び出し構造において不具合が再発するだけである。

*4:"error: mutating transmuted &mut T from &T may cause undefined behavior, consider instead using an UnsafeCell, #[deny(mutable_transmutes)] on by default"

*5:型キャスト操作ではイュータブル生ポインタ(*const T)を経由する必要がある。イミュータブル参照型からの直接キャスト (p as *mut _) を試みると、"error: casting `&i32` as `*mut i32` is invalid"と怒られる。

2017-03-06

IntelliSenseコンテキスト判別マクロ

Visual Studio 2010以降では、IntelliSenseコンテキスト判別用マクロ __INTELLISENSE__ が定義される。

#ifdef __INTELLISENSE__
...
#endif

MSDN公式ドキュメントにはVisual Studio 2015以降から記載されている。

関連URL

2017-03-04

Objective-C atomic属性プロパティとスレッド間同期

LLVM/Objective-Cのatomic属性プロパティが保証する性質、C言語(C11)のAtomic変数アクセスとの比較、およびマルチスレッド処理での利用についてメモ。

超要約:Objective-C @property宣言には常にnonatomic属性を指定せよ。atomic属性プロパティは人類には早すぎる。決して使うな。この門をくぐる者は一切の希望を捨てよ。

@interface SomeClass {
  _Atomic(BOOL) atomicFlag;  // C11 Atomicインスタンス変数
}

@property (atomic) BOOL atomicProp;  // スカラ型atomic属性プロパティ
// または
@property BOOL atomicProp;

@property (atomic) id atomicObject;  // 参照型atomic属性プロパティ
@end

注意:本記事の内容はLLVM/Clangコンパイラ出力から演繹的に導いた解析内容に基づく。Objective-Cの厳格な言語仕様は存在しない(?)。

まとめ:

  • Objective-C/スカラ型のatomic属性プロパティは、最も弱いアトミック性(Atomicity)しか保証しない。これはC11/Atomic変数 relaxedアクセスよりも弱い保証レベルである。*1
    • スカラ型atomic属性プロパティの読込(Read)/書出(Write)操作は、文字通り不可分(Atomic)なメモリロード/ストア命令に変換されることのみ(→id:yohhoy:20121016)保証される。RMW(Read-Modify-Write)操作のアトミック性は保証されない。*2
  • スカラ型atomic属性プロパティへのアクセスでは順序性(Ordering)が保証されず、スレッド間同期機構として用いることができない(→id:yohhoy:20140808)。
    • 例1:スレッドA“変数Xへデータ書出→BOOL型atomic属性プロパティへ値YESを書出”、スレッドB“同atomic属性プロパティから値YESを読込→変数Xからデータ読込”というスレッド間同期処理が、プログラマの期待通り動作する保証がない。コンパイラやプロセッサは、スレッドA/B上で行われる書出/読込アクセスの順序を入れ替える可能性がある。
    • 例2:ロック状態をatomic属性プロパティで表現したSpinlock同期機構は、順序性保証の欠如により排他制御として機能しない。コンパイラやプロセッサは、ロック範囲(クリティカルリージョン内)のメモリアクセス命令をその領域外へと移動する可能性がある。
  • Objective-Cプログラム中でいわゆる「アトミック変数」が必要な場合、C11 Atomic変数型 _Atomic(T) を利用すること。Objective-C++プログラムならばC++11 Atomic変数型 std::atomic<T> が利用可能。
    • ソースコード上で通常変数のように透過的に扱え、かつAtomic変数アクセスが逐次一貫性(Sequential Consistency)をもつため、プログラマの期待通りに振る舞う(→id:yohhoy:20141221)ことが保証される。
    • 複数変数に対する並行操作を行う場合は、@synchronized構文やNSLock, NSCondition等によるロック操作が必要。
  • ノート:Objective-C/atomic属性プロパティは何の役にも立たないばかりかむしろ有害と考える。若干のメモリアクセス・オーバーヘッドに加え、マルチスレッド処理バグの潜在要因となり得るリスク因子である。Objective-C言語仕様によりプロパティの既定属性は atomic と定義されている。すでに広く指摘される通り、@property 宣言では常に nonatomic 属性を明示すべき。*3

LLVM/Clangにより変換されたLLVM IR命令は下記の通り。Objective-C/atomic属性プロパティでは"unordered"が、C11 Atomic変数の既定アクセスでは"seq_cst"が、memory_order_release+memory_order_acquire指定には直接対応、memory_order_relaxed指定には"monotonic"なload atomic/store atomic命令が出力されている。

$ clang --version
Apple LLVM version 8.0.0 (clang-800.0.42.1)
Target: x86_64-apple-darwin16.4.0
Thread model: posix
$ clang -c -S -emit-llvm input.m 
@interface SomeClass
@property (atomic) int atomicInt;  // atomic属性プロパティ
@end

@implementation SomeClass
- (int)atomicInt;
  // load atomic i32, i32* %N unordered, align 4
- (void)setAtomicInt:(int);
  // store atomic i32 %M, i32* %N unordered, align 4
@end
#include <stdatomic.h>

_Atomic(int) atomicInt;  // C11 Atomic変数

int val = atomicInt;
  // load atomic i32, i32* %N seq_cst, align 4
atomicInt = 42;
  // store atomic i32 42, i32* %N seq_cst, align 4

int val = atomic_load_explicit(&atomicInt, memory_order_acquire);
  // load atomic i32, i32* %N acquire, align 4
atomic_store_explicit(&atomicInt, 42, memory_order_release);
  // store atomic i32 %M, i32* %N release, align 4

int val = atomic_load_explicit(&atomicInt, memory_order_relaxed);
  // load atomic i32, i32* %N monotonic, align 4
atomic_store_explicit(&atomicInt, 42, memory_order_relaxed);
  // store atomic i32 %M, i32* %N monotonic, align 4

LLVM Language Reference Manual, Atomic Memory Ordering Constraintsより"unordered","monotonic"の説明を引用(下線部は強調)。

unordered
The set of values that can be read is governed by the happens-before partial order. A value cannot be read unless some operation wrote it. This is intended to provide a guarantee strong enough to model Java's non-volatile shared variables. This ordering cannot be specified for read-modify-write operations; it is not strong enough to make them atomic in any interesting way.
monotonic
In addition to the guarantees of unordered, there is a single total order for modifications by monotonic operations on each address. All modification orders must be compatible with the happens-before order. There is no guarantee that the modification orders can be combined to a global total order for the whole program (and this often will not be possible). The read in an atomic read-modify-write operation (cmpxchg and atomicrmw) reads the value in the modification order immediately before the value it writes. If one atomic read happens before another atomic read of the same address, the later read must see the same value or a later value in the address's modification order. This disallows reordering of monotonic (or stronger) operations on the same address. If an address is written monotonic-ally by one thread, and other threads monotonic-ally read that address repeatedly, the other threads must eventually see the write. This corresponds to the C++0x/C1x memory_order_relaxed.

LLVM Atomic Instructions and Concurrency Guideより"Unordered", "Monotonic"の説明を引用。

Unordered
Unordered is the lowest level of atomicity. It essentially guarantees that races produce somewhat sane results instead of having undefined behavior. It also guarantees the operation to be lock-free, so it does not depend on the data being part of a special atomic structure or depend on a separate per-process global lock. Note that code generation will fail for unsupported atomic operations; if you need such an operation, use explicit locking.

Relevant standard
This is intended to match the Java memory model for shared variables.
Notes for frontends
This cannot be used for synchronization, but is useful for Java and other "safe" languages which need to guarantee that the generated code never exhibits undefined behavior. Note that this guarantee is cheap on common platforms for loads of a native width, but can be expensive or unavailable for wider loads, like a 64-bit store on ARM. (A frontend for Java or other "safe" languages would normally split a 64-bit store on ARM into two 32-bit unordered stores.)
Notes for optimizers
In terms of the optimizer, this prohibits any transformation that transforms a single load into multiple loads, transforms a store into multiple stores, narrows a store, or stores a value which would not be stored otherwise. Some examples of unsafe optimizations are narrowing an assignment into a bitfield, rematerializing a load, and turning loads and stores into a memcpy call. Reordering unordered operations is safe, though, and optimizers should take advantage of that because unordered operations are common in languages that need them.
Notes for code generation
These operations are required to be atomic in the sense that if you use unordered loads and unordered stores, a load cannot see a value which was never stored. A normal load or store instruction is usually sufficient, but note that an unordered load or store cannot be split into multiple instructions (or an instruction which does multiple memory operations, like LDRD on ARM without LPAE, or not naturally-aligned LDRD on LPAE ARM).

Monotonic
Monotonic is the weakest level of atomicity that can be used in synchronization primitives, although it does not provide any general synchronization. It essentially guarantees that if you take all the operations affecting a specific address, a consistent ordering exists.

Relevant standard
This corresponds to the C++11/C11 memory_order_relaxed; see those standards for the exact definition.
Notes for frontends
If you are writing a frontend which uses this directly, use with caution. The guarantees in terms of synchronization are very weak, so make sure these are only used in a pattern which you know is correct. Generally, these would either be used for atomic operations which do not protect other memory (like an atomic counter), or along with a fence.
Notes for optimizers
In terms of the optimizer, this can be treated as a read+write on the relevant memory location (and alias analysis will take advantage of that). In addition, it is legal to reorder non-atomic and Unordered loads around Monotonic loads. CSE/DSE and a few other optimizations are allowed, but Monotonic operations are unlikely to be used in ways which would make those optimizations useful.
Notes for code generation
Code generation is essentially the same as that for unordered for loads and stores. No fences are required. cmpxchg and atomicrmw are required to appear as a single operation.

訳注:LPAE=Large Physical Address Extension。CSE=Common Subexpression Elimination, DSE=Dead Store Elimination。

関連URL

*1:Objective-C/atomic属性プロパティは、Java言語/(非volatile修飾)通常メンバ変数と同レベルのアトミック性となっている。スマートフォン向けアプリ開発の具体例をあげると、Android@Javaのvolatileメンバ変数 から iOS@Objective-Cのatomic属性プロパティ への対応付けは不適切といえる。

*2:C11 Atomic変数では、インクリメント/デクリメント演算といったRMW操作のアトミック性も保証される。

*3:Objective-C/atomic属性プロパティは、C11 Atomic変数のrelaxedアクセスよりもさらに正しく取り扱うのが困難である。特に弱いハードウェア・メモリモデルを採用するARMアーキテクチャ上では、LLVM IRが提供するメモリモデルについて正確に理解できるまでは、atomic属性プロパティの利用は避けるべきだろう...仮に理解したとしても使いたいとは思わないが。

2017-02-16

順序維持してJSONデータを読み込む

Python標準モジュール json ではJSONデコード結果を辞書型(dict)にて表現するため、入力JSON文字列中でのオブジェクトname/value出現順序が維持されない。

json.loadメソッドまたはJSONDecoderクラスの名前付き引数object_pairs_hookにcollections.OrderedDictを指定すると、デコード結果がOrderedDict型にて表現されることで出現順序が維持される。

import collections
import json

json_data = '{"C": 1, "B": 2, "A": 3}'

decoder = json.JSONDecoder()
print(decoder.decode(json_data))
# {'B': 2, 'C': 1, 'A': 3} など

decoder = json.JSONDecoder(object_pairs_hook=collections.OrderedDict)
print(decoder.decode(json_data))
# OrderedDict([('C', 1), ('B', 2), ('A', 3)])

Python言語のdict型は順序性について強い保証を持たないため、どのような順序となるかは各処理系に依存する。CPython 3.6ではdict型の順序が維持されるよう実装変更が行われたが、言語仕様上は依然としてdict型に対する順序規定は存在しない。*1

関連URL

*14.10.1. Dictionary view objects: "Keys and values are iterated over in an arbitrary order which is non-random, varies across Python implementations, and depends on the dictionary's history of insertions and deletions."

2017-02-14

recursive_(timed_)mutexの再帰ロック数上限

C++11標準ライブラリの recursive_mutex, recursive_timed_mutex クラスでは、同一スレッドからの再帰ロック獲得回数の上限は未規定(unspecified)となっている。ただし上限回数を超えるtry_lock操作は失敗し、lock操作は例外送出する振る舞いが保証される。

C++11 30.4.1.2.2/p3より引用(下線部は強調)。recursive_timed_mutexについても同様の定義(30.4.1.3.2/p3)。

A thread that owns a recursive_mutex object may acquire additional levels of ownership by calling lock() or try_lock() on that object. It is unspecified how many levels of ownership may be acquired by a single thread. If a thread has already acquired the maximum level of ownership for a recursive_mutex object, additional calls to try_lock() shall fail, and additional calls to lock() shall throw an exception of type system_error. A thread shall call unlock() once for each level of ownership acquired by calls to lock() and try_lock(). Only when all levels of ownership have been released may ownership be acquired by another thread.

関連URL