c++ queueのpop()時にsegmentation faultする

Question

実現したいこと

c++ queueのpop()時に発生するsegmentation faultの原因を知りたい

発生している問題・分からないこと

c++でAtCoderの問題( https://atcoder.jp/contests/abc339/tasks/abc339_d )を解いている最中にstd::queue::pop()にてsegmantation faultが発生した。

エラーメッセージ

...(省略)
671
6
3 5 4 6
670
6
2 6 3 7
671
6
0 6 1 7
Segmentation fault (core dumped)

該当のソースコード

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

// #include <atcoder/all>
// using namespace atcoder;

// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>
// namespace mp = boost::multiprecision;
// // 任意長整数型
// using Bint = mp::cpp_int;

using ll = long long int;

#define FOR(i, a, b) for (ll i = (a); i < (ll)(b); ++i)
#define RFOR(i, a, b) for (ll i = (a); i > (ll)(b); --i)
#define REP(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define INF numeric_limits<int>::max()
#define MINF numeric_limits<int>::min()
#define LLINF numeric_limits<long long int>::max()
#define LLMINF numeric_limits<long long int>::min()

using Pair = pair<ll, char>;
using Map = map<ll, ll>;
using Set = set<ll>;
using Hash = unordered_map<int, int>;
using Tuple = tuple<double, int, int>;

// using mint = modint998244353;
// using mint = modint1000000007;
// using mint = modint;

void print1d(vector<ll>& v) {
	REP(i, v.size()) {
		cout << v[i] << " ";
	}
	cout << endl;
}

void print2d(vector<vector<ll>> &v) {
	// cout << hex;
	REP(i, v.size()) {
		REP(j, v[i].size()) {
			cout << v[i][j] << " ";
		}
		cout << endl;
	}
	// cout << dec;
}

void printfield(vector<string> &S) {
	REP(i, S.size()) {
		cout << S[i] << endl;
	}
}

vector<vector<ll>> dxy = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

// const int MAX = 510000;
// mint fac[MAX], finv[MAX], inv[MAX];

// // テーブルを作る前処理
// void COMinit() {
//     const int MOD = mint::mod();
//     fac[0] = fac[1] = 1;
//     finv[0] = finv[1] = 1;
//     inv[1] = 1;
//     for (int i = 2; i < MAX; i++){
//         fac[i] = fac[i - 1] * i;
//         inv[i] = MOD - inv[MOD%i] * (MOD / i);
//         finv[i] = finv[i - 1] * inv[i];
//     }
// }

// // 二項係数計算
// mint COM(int n, int k){
//     if (n < k) return 0;
//     if (n < 0 || k < 0) return 0;
//     return fac[n] * finv[k] * finv[n - k];
// }

// ---

class Status {
public:
	ll i1, j1;
	ll i2, j2;

	bool completed() {
		return (i1 == i2) && (j1 == j2);
	}

	bool operator<(const Status& s2) const {
		return i1 < s2.i1 || j1 < s2.j1 || i2 < s2.i2 || j2 < s2.j2;
	}
};

int main() {
	ll N = 10;
	vector<string> S(N);
	S[0] = "..........";
	S[1] = "..........";
	S[2] = "..........";
	S[3] = "..........";
	S[4] = "....P.....";
	S[5] = ".....P....";
	S[6] = "..........";
	S[7] = "..........";
	S[8] = "..........";
	S[9] = "..........";

	Status s;
	s.i1 = -1;
	REP(i, N) {
		REP(j, N) {
			if (S[i][j] == 'P') {
				if (s.i1 == -1) {
					s.i1 = i;
					s.j1 = j;
				} else {
					s.i2 = i;
					s.j2 = j;
				}
			}
		}
	}

	map<Status, ll> m;
	queue<pair<ll, Status>> q;
	m[s] = 0;
	q.push(pair<ll, Status>(0, s));


	while (!q.empty()) {

		auto [d, s] = q.front();
		cout << q.size() << endl;
		cout << d << endl;
		cout << s.i1 << " " << s.j1 << " " << s.i2 << " " << s.j2 << endl;
		q.pop(); // <======= segmentation fault

		if (s.completed()) {
			cout << d << endl;
			return 0;
		}

		REP(k, 4) {
			ll ni1 = s.i1 + dxy[k][0];
			ll nj1 = s.j1 + dxy[k][1];
			ll ni2 = s.i2 + dxy[k][0];
			ll nj2 = s.j2 + dxy[k][1];
			Status ns = s;

			if (0 <= ni1 && ni1 < N && 0 <= nj1 && nj1 < N && S[ni1][nj1] != '#') {
				ns.i1 = ni1;
				ns.j1 = nj1;
			}
			if (0 <= ni2 && ni2 < N && 0 <= nj2 && nj2 < N && S[ni2][nj2] != '#') {
				ns.i2 = ni2;
				ns.j2 = nj2;
			}

			if (m.count(ns) == 0) {
				m[ns] = d + 1;
				q.push(pair<ll, Status>(d + 1, ns));
			}
		}
	}

	cout << -1 << endl;

	return 0;
}

試したこと・調べたこと

• teratailやGoogle等で検索した
• ソースコードを自分なりに変更した
• 知人に聞いた
• その他

上記の詳細・結果

• エラーメッセージの下から4行目の出力（671）がqueue.size()であり、空のqueueをpopしたのが原因ではないことを確認した。

• このコードは113行目のStatusの比較演算子の実装に問題があり、そこを直すとsegmentation faultも出なくなる。ただ、これはqueueへpushされる値が変わってsegmentation faultが発生しなくなっただけなので、なぜこの条件下でpop()でsegmentation faultが発生するかの回答にはなっていない。

• gdbでstack traceを追ってみると次のようになっていた。

(gdb) bt
#0  __GI___libc_free (mem=0x7) at malloc.c:3102
#1  0x0000563d22dd0490 in __gnu_cxx::new_allocator<std::pair<long long, Status> >::deallocate (
    this=0x7ffcaeee7950, __p=0x7) at /usr/include/c++/9/ext/new_allocator.h:128
#2  0x0000563d22dcf88d in std::allocator_traits<std::allocator<std::pair<long long, Status> > >::deallocate (__a=..., __p=0x7, __n=12) at /usr/include/c++/9/bits/alloc_traits.h:469
#3  0x0000563d22dcde0e in std::_Deque_base<std::pair<long long, Status>, std::allocator<std::pair<long long, Status> > >::_M_deallocate_node (this=0x7ffcaeee7950, __p=0x7)
    at /usr/include/c++/9/bits/stl_deque.h:627
#4  0x0000563d22dcbec5 in std::deque<std::pair<long long, Status>, std::allocator<std::pair<long long, Status> > >::_M_pop_front_aux (this=0x7ffcaeee7950) at /usr/include/c++/9/bits/deque.tcc:576
#5  0x0000563d22dc7576 in std::deque<std::pair<long long, Status>, std::allocator<std::pair<long long, Status> > >::pop_front (this=0x7ffcaeee7950) at /usr/include/c++/9/bits/stl_deque.h:1616
#6  0x0000563d22dc4766 in std::queue<std::pair<long long, Status>, std::deque<std::pair<long long, Status>, std::allocator<std::pair<long long, Status> > > >::pop (this=0x7ffcaeee7950)
--Type <RET> for more, q to quit, c to continue without paging--
    at /usr/include/c++/9/bits/stl_queue.h:295
#7  0x0000563d22dbd3f9 in main () at a.cc:160

#0のmem=0x7が明らかに怪しいが、なぜこうなるかがわからなかった。

補足

特になし

Comments

[jimbe]

paiza.io にコピペして 158-159 を(表示しきれないので) コメントにして実行したら、q.size が 2467 で 10 が表示されました。

[melian]

paize.io では C コンパイラとして clang が使われているそうです。以下の様に AddressSanitizer を利用すると stack overflow が発生している事が判ります。AddressSanitizer は gcc でも利用可能で(-fsanitize=address を指定)、実行結果は clang の場合と同じです。

$ clang++ --version
Ubuntu clang version 16.0.6 (15)
$ clang++ -g -fsanitize=address a.cc -o a
$ ./a
　　:
==465390==ERROR: AddressSanitizer: stack-buffer-overflow on address ...
#0 0x5c1548396ccd in Status::operator<(Status const&) const a.cc:114:24
　　　　:
#5 0x5c154838e32d in main a.cc:184:5

This frame has 11 object(s):
　　　　　:
[176, 224) 'm' (line 148) <== Memory access at offset 224 overflows this variable
　　　　　:
SUMMARY: AddressSanitizer: stack-buffer-overflow a.cc:114:24 in Status::operator<(Status const&) const

[tmp]

q.front()でとってきたStatusクラスのsは q.popで解放されてしまわないのですか？

[iwannatto]

@jimbe
別環境で試すのをサボっていたのですがpaiza.ioという手があったのですね……
ありがとうございます。

@melian
sanitizerは存在は知っていたのですが結構簡単に利用できるんですね……
関係ないと思っていたmが悪さをしているというのも貴重な結果です。ありがとうございます。

@tmp
コメントありがとうございます。
参照で取っているわけではないのでsはコピーコンストラクタで初期化されると考えています。

Answer 1

あくまで状況証拠からの推測にすぎませんが、直接の原因はStatus::operator<ではないでしょうか。

該当コードをg++ -fsanitize=addressでコンパイルして実行すると、Status::operator<にて stack-buffer-overflow が検出されます。

map - cpprefjp C++日本語リファレンスによると、std::mapの要素の比較演算子は、狭義の弱順序でなければならないそうです。Status::operator<がその条件を満たしていないために、std::mapにてメモリ範囲外アクセスが発生していると推察されます。(どういう理屈でそうなるのかについては、実装を追うのが大変なので追及していません)

std::mapにてメモリ範囲外アクセスが発生した結果、たまたまメモリ上隣り合っているstd::queueの管理領域が破壊されて、その破壊されたメモリをもとにstd::queue::pop()した結果、segmentation fault が発生したのではないでしょうか。

私もほとんど知識がないので、これ以上の調査が必要なら、自力でお願いします。

Comments

[iwannatto]

回答ありがとうございます。
mapが悪さをしているというのは頭から抜けていたのですが、確かにここの要件を満たしていないと何が起きても文句が言えないですね。
納得したのでベストアンサーとさせていただきます。ありがとうございました。