センニジュウヨン

意味なんてない

C++においてメモリブロックのオーバーラップ判定は不可能なのか

先日 std::memcpy を使うコードを書いた。

void* memcpy( void* dest, const void* src, std::size_t count );

memcpy は src から dest へ count バイトだけコピーする簡単な関数だが、いくつか注意点があり、 その一つが、メモリの範囲がオーバーラップしていると動作が未定義という点である。

この点が気になったので assert でも書いておこうと思ったのだが*1、 ポインタ演算について調べてみると、どうもこれは(C++の規格の範囲内では)書けないんじゃないかと思い始めたりして、 色々迷走したのでそれについて調査過程を含めてここに記録しておく。

(規格文書を直接あたったわけでもない調査なので間違ったことを書いているかもしれません。ツッコミ歓迎。)

そのオーバーラップ判定大丈夫?

オーバーラップ判定コードは以下のようなものである。

// オーバーラップしていないかどうかチェック
assert(((src+count) <= dest) || (src >= dest+count));

自分で考えて判定を書くと、もっとグチャッとした処理を書きそうだったので、ググってどう書くべきか調べた。 その結果、 Linus のメールに書いてあるものがシンプルで良さそうだったのでこれを参考にした。 件のメールでは unsigned long にキャストしていて、念の為 unsigned long のオーバーフローにも配慮する場合も示してあるが、 オーバーフローのチェックとかほんとに要るのか疑問だったので、ポインタ同士の演算について調べてみることにした。

ポインタへの加算は大丈夫そう

ポインタへの加算については、cppreference の算術演算子のページ*2に記載があり、 配列の最後の要素+1までは保証されるけど、それを超えると未定義動作になると書いてある*3。 今回の事例は配列の末尾を超えることは無いものだったので、とりあえずこれは大丈夫だと分かった。

問題はポインタ同士の比較

ポインタ同士の比較については、cppreference の比較演算子のページに記載があり、 内容が多いのだが、関係しそうな部分だけ抜粋する。

2つのオブジェクトへのポインタ (の変換後) の比較の結果は、以下のように定義されます。

  1. 2つのポインタが同じ配列の異なる要素を指している場合、または同じ配列の異なる要素内の部分オブジェクトを指している場合、大きい添字を持つ要素を指しているポインタの方が他方より大きいとみなされます。 別の言い方をすると、ポインタの比較の結果は、それらが指している要素のインデックスを比較した結果と同じになります。
  2. 片方のポインタが配列の要素を指すか配列の要素の部分オブジェクトを指し、他方のポインタがその配列の最後の要素の次の要素を指す場合、後者のポインタの方が前者より大きいとみなされます。 単一のオブジェクトを指しているポインタは、サイズ1の配列を指しているとみなされます。 つまり &obj+1 は &obj より大きいとみなされます。 (C++17およびそれ以降)
  3. union でないクラス型のオブジェクト内で、2つのポインタが同じメンバアクセスを持つ異なる非静的データメンバを指している場合、またはそのようなメンバの部分オブジェクトまたは配列要素を指している場合、後に宣言されたメンバを指しているポインタの方が他方より大きいとみなされます。 別の言い方をすると、同じメンバアクセスモードを持つクラスメンバは、宣言された順番でメモリ内に配置されます。

(途中省略)

2つのポインタが、より大きいとも等しいとも規定されていない場合、比較の結果は未規定です。結果は非決定的であってもよく、プログラムの同じ実行における同じ被演算子を持つ同じ式の複数回の評価に対してであっても、一貫している必要はありません。

ここで、1 は同一配列内の要素での前後関係について、2 は配列内のものとその配列の最後の次の要素との前後関係について、3 はクラス内での前後関係について言及している。 重要なのは、同一ではない配列の比較について一切言及していないことである。 そして引用の最後の方にあるように、言及がないということは比較結果は未規定であることを意味する。

前述のオーバーラップチェックコードでは、同一配列内のポインタ同士(オーバーラップの可能性がある)では正しく動くだろうが、 別の配列同士(これは普通オーバーラップしない)では正しく動く保証がない。\(^o^)/オワタ

(非決定的でもよいという文言も気になる。はじめは、これがポインタ比較全般についての言及かと思ったが、引用先のページの作りからして未規定動作時のみへの言及だと思われる*4。 未規定動作時には既に正しく動く保証がないのでここは突っ込んで考える意味は余りなさそう。)

解決策?

なんとかならないか模索していたら、Stack Overflow のある回答が目についた。 要は、ポインタ比較がだめなら intptr_t で比較すればいいじゃない、という内容。 たしかに intptr_t 同士の比較では未規定とか未定義動作ということはありえないように思える。

前述のオーバーラップチェックコードの場合は特に signed である必要もないので、やるとしたら uintptr_t を使うだろうか。 ただ気になるのは、reinterpret_cast<uintptr_t>(...) という形でキャストが必要になるのが何となく不安になる*5のと、 uintptr_t での比較がポインタでの比較で意図していたものと同じ意味になるという保証があるのかという点。

詳しくは規格を見るのが正しいんだろうけど、そんな気力もないのでまたもやググって cpprefjp の uintptr_t のページに以下のような記述を見つけた。

この型を実装するかどうかは処理系定義。

この型は、以下の動作が保証される:

  1. 有効なvoidへのポインタからuintptr_t型への変換
  2. uintptr_t型のポインタ値からvoidへのポインタへの逆変換
  3. 変換前と逆変換のポインタ値が等値となる

実装するかどうかは処理系定義とあるが、今回は定義してある環境しか相手にしないのでとりあえず置いておく。

そして気になるのが、保証される動作が極端に少ないこと。変換と逆変換が正しくできてポインタ値が同じになるとしか書いていない。これを見る限り、規格内で意味のある比較は無理筋に思える。

真の解決策

というわけで、「無理っぽいです」という記事を書こうとしたわけだが、改めてググってみたら正解らしきものを見つけた。(なぜあのとき見つからなかったのか…)

Stack Overflow のある回答に以下のように書いてある。

int overlap_p(void *a, void *b, size_t n)
{
    char *x = a, *y =  b;
    for (i=0; i<n; i++) if (a+i==b || b+i==a) return 1;
    return 0;
}

要は比較は比較でも等値比較を使えってことである。

上の方でポインタの比較について引用したが、省略した部分に等値比較についての以下のような記述がある。

2つのポインタ (の変換後) の等値比較の結果は、以下のように定義されます。

  1. ポインタがどちらも NULL ポインタの場合、それらは等しいとみなされます。
  2. ポインタが関数ポインタで、同じ関数を指している場合、それらは等しいみなされます。
  3. ポインタがオブジェクトポインタで、同じアドレスを表している場合、それらは等しいとみなされます (これには、同じ共用体の非静的メンバを指している2つのポインタや、標準レイアウト構造体を指しているポインタとその最初のメンバを指しているポインタや、 reinterpret_cast によって関連付けられているポインタなどが含まれます)。
  4. それ以外のすべてのポインタは等しくないとみなされます。

今回の場合は 3 に当てはまりそうなので未規定ではなくなる。 これにて解決!

(でもなんか冗長っぽく見えて釈然としない。標準ライブラリとかコンパイラの組み込み関数とかでサクッと判定できないものか)

*1:結局、当該コードはオーバーラップして使われることがないと判断し、実際には assert は書かなかった

*2:日本語版はアレな機械翻訳なので英語版へリンク

*3:配列有効範囲外を指すポインタ値は存在が許されない - yohhoyの日記も参照されたし

*4:ほんとのところは規格を見てみないとわからないけど

*5:reinterpret_cast ってなんとなく不安になりますよね?