Java API ドキュメントでは、Iterator.remove() メソッドについて以下のように説明している[API 2006]。
繰り返し処理が実行されているときに、このメソッドの呼び出し以外の方法で基になるコレクションが変更された場合、反復子の動作は保証されない。
シングルスレッドプログラムでこのような変更を行うのは、通常、反復処理中に要素を追加したり削除したりといった操作を行う場合である。さらに、マルチスレッドプログラムでは、ひとつのスレッドでコレクションに対する反復処理を行っている間に、別のスレッドがそのコレクションに変更を行う、という可能性もある。どちらの場合も未定義の動作となる。多くの実装では、反復処理中の変更操作を検出すると、ConcurrentModificationException をスローする。
Java API ドキュメントでは、ConcurrentModificationException について以下のように説明している[API 2006]。
たとえば、あるスレッドが Collection で繰り返し処理を行っている間に、別のスレッドがその Collection を変更することは一般に許可されない。通常、そのような環境では、繰り返し処理の結果は保証されない。いくつかの反復子(Iterator)の実装(JREが提供するすべての一般的な目的のコレクションの実装の、反復子の実装を含む)は、その動作が検出された場合にこの例外をスローすることを選択できる。この例外をスローする反復子は「フェイルファスト」反復子と呼ばれる。「フェイルファスト」反復子は、将来の予測できない時点において予測できない動作が発生する危険を回避するために、ただちにかつ手際よく例外をスローする。
通常、非同期の並行変更がある場合、確かな保証を行うことは不可能なので、フェイルファストの動作を保証することはできない。フェイルファストオペレーションは最善努力原則に基づき、ConcurrentModificationException をスローする。したがって、 反復処理を正確に行うために、この例外に依存するプログラムを書くことは誤りである。ConcurrentModificationException は、バグを検出するためにのみ使用すること。
コレクションに対する反復処理中に基のコレクションを変更することで発生する未定義の動作を防ぐために、ConcurrentModificationException に依存するのは不適切である。フェイルファスト動作が要素をいくつ処理してから発生するかは決まっていない。 『Java 並行処理プログラミング』(原著 Java Concurrency in Practice)には以下のような記述がある[Goetz 2006a]。
[フェイルファスト反復子は] コレクションに変更カウントを設ける方式で実装されている。イテレーションの間に変更カウントの値が変わると、hasNext や next が ConcurrentModificationException をスローする。しかしこのチェックは同期されていないので、変更カウントの値は最新のものではないかもしれず、そうするとイテレータは変更が行われたことが分からないかもしれない。これは並行変更を検出するコードが実行性能に与える影響を抑えるための、意図的な設計トレードオフである。
拡張 for ループ(for-each イディオム)は内部でイテレータを使っていることに注意。したがって、コード上にイテレータが出現しなくても、拡張 for ループも並行変更の問題の影響を受ける可能性がある。
違反コード (シングルスレッド)
Sun Developer Network SDN 2011 バグレポート 6687277 に基づく以下の違反コード例では、ArrayList に対して反復処理をしながら、ArrayList の remove() メソッドを使って ArrayList から要素を削除している。そのため、未定義の動作となる。
class BadIterate {
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list.add("one");
list.add("two");
Iterator iter = list.iterator();
while (iter.hasNext()) {
String s = (String)iter.next();
if (s.equals("one")) {
list.remove(s);
}
}
}
}
適合コード (iterator.remove())
Iterator.remove() メソッドは、基となる Collection から、イテレータが最後に返した要素を削除する。その動作は完全に規定されており、コレクションに対する反復処理中に使っても安全である。
// ...
if (s.equals("one")) {
iter.remove();
}
// ...
違反コード (マルチスレッド)
以下の違反コード例は、シングルスレッドの場合には問題ないが、マルチスレッドの場合にはセキュアではない。あるスレッドが widgetList に対して反復処理を行っている間に、別のスレッドがその widgetList を変更できるからである。さらに、反復処理中に doSomething() メソッドがコレクションに変更を加える可能性もある。
List<Widget> widgetList = new ArrayList<Widget>();
public void widgetOperation() {
// ConcurrentModificationException をスローするかもしれない
for (Widget w : widgetList) {
doSomething(w);
}
}
適合コード (スレッドセーフなコレクション)
以下の適合コードでは、ArrayList を同期コレクションでラップし、すべての変更操作を同一のロックの管理下に置いている。
List<Widget> widgetList =
Collections.synchronizedList(new ArrayList<Widget>());
public void widgetOperation() {
for (Widget w : widgetList) {
doSomething(w);
}
}
このアプローチを使う場合は、リソース枯渇、デッドロック、スケーラビリティといった問題が発生しないよう、正しく実装しなければならない[Goetz 2006a]。
適合コード (深いコピー)
以下の適合コードでは、widgetList に対して反復処理を行う前に深いコピーを作成している。
List<Widget> widgetList = new ArrayList<Widget>();
public void widgetOperation() {
List<Widget> deepCopy = new ArrayList<Widget>();
synchronized (widgetList) { // クライアント側でロック
for (Object obj : widgetList) {
deepCopy.add(obj.clone());
}
}
for (Widget w : deepCopy) {
doSomething(w);
}
}
リストの深いコピーを作成すれば、コピー元のリストに変更操作が行われても反復処理は影響を受けない。「そのクローンはスレッド拘束されるので、ほかのスレッドがイテレーションの間に変更することはできず、ConcurrentModificationException は起きない(クローンを作る操作の間はコレクションをロックすることが必要である)」[Goetz 2006a]。しかし、このアプローチは他のテクニックよりも高くつくことが多い。また、古くなったデータを処理している危険もあるため、コードが正しい動作をしなくなるかもしれない。
適合コード (CopyOnWriteArrayList)
データ構造 copyOnWriteArrayList では、その変更操作を、基となる配列の新しいコピーをつくる形で実装している。このデータ構造は完全にスレッドセーフであり、変更操作よりもデータ構造を辿る操作のほうが多い状況に最適化されている。このデータ構造を辿る場合、イテレータが作成された(あるいは拡張 for ループが開始された)時点の状態のデータ構造を辿ることになる。それ以降に行われた変更は、データ構造を辿っているときには見えない。そのため、変更操作が頻繁に行わる場合や、変更操作の結果が、辿っている最中のデータ構造に反映されるべき場合には、この手法は不適切である。
List<Widget> widgetList = new CopyOnWriteArrayList<Widget>();
public void widgetOperation() {
for (Widget w : widgetList) {
doSomething(w);
}
}
リスク評価
コレクションに対する反復処理中に変更を行うと、未定義の動作となる。
| ルール | 深刻度 | 可能性 | 修正コスト | 優先度 | レベル |
|---|---|---|---|---|---|
| MSC06-J | 低 | 中 | 中 | P4 | L3 |
自動検出
静的解析ツールのなかには、基になるコンテナが変更された後にイテレータが使われるケースを検出できるものもある。
関連する脆弱性
Apache Harmony のバグ HARMONY-6236 は、並行コレクションが入力として渡されると、ArrayList が破壊される問題である。
参考文献
| [API 2006] | Class ConcurrentModificationException |
| [SDN 2008] | Sun Bug database, Bug ID 6687277 |
| [Goetz 2006a] | 5.1.2. Iterators and ConcurrentModificationException |
翻訳元
これは以下のページを翻訳したものです。
MSC06-J. Do not modify the underlying collection when an iteration is in progress (revision 61)
コメント
共 有
