Project

General

Profile

Actions

Bug #18578

closed

Hash#shift を繰り返していると ruby が無応答になる。

Added by Anonymous 3 months ago. Updated about 2 months ago.

Status:
Closed
Priority:
Normal
Assignee:
-
Target version:
-
[ruby-dev:51159]

Description

はじめまして ds14050 といいます。最近スクリプトではなくインタープリタが原因で ruby の応答がなくなるケースに遭遇したと思いました。確認をお願いできますか。

<<<以下再現スクリプト

# ウチではだいたい 20 から 30 回で "empty?: true" を最後にして止まる。
# ウチの Ruby-2.5: ruby 2.5.5p157 (2019-03-15 revision 67260) [x64-mingw32]
# ウチの Ruby-2.7: ruby 2.7.1p83 (2020-03-31 revision a0c7c23c9c) [x64-mingw32]
# ウチの Ruby-3.1: ruby 3.1.0p0 (2021-12-25 revision fb4df44d16) [x64-mingw-ucrt]

H = {}
100.times{|n|
    while H.size < n
        k = Random.rand 0..1<<30
        H[k] = 1 # たぶんここで止まる。
    end
    warn "size: #{H.size} before shifting."
    0 while H.shift
    warn "empty?: #{H.empty?}"
}
warn :exit

Hash に要素を詰めて空にしてを 100 回繰り返すスクリプトです。3.1 を含む3つのバージョンでほぼ確実に止まる(ruby.exe がビジー状態で終了しない)ことを確認しています。2.5 より古い Ruby-1.9 では止まらずに最後まで実行が完了しました。

Hash を空にする方法として 0 while H.shift の代わりに H.shift until H.empty? を選ぶと最後まで実行が完了するようになったことから呼び出すメソッドを揃えて比較したところ、Hash が空になったあとの余分な Hash#shift が何か悪さをしているように思えます。

また、デバッグプリントを増やして確認したところ実際に停止しているのは Hash#shift の行ではなく H[k] = 1 の行であるようでした。

よろしくお願いします。

Updated by mame (Yusuke Endoh) 3 months ago

すばらしい再現例をありがとうございます!
次のパッチで直るとおもいます。

diff --git a/st.c b/st.c
index 53e9dc8320..07a083abb0 100644
--- a/st.c
+++ b/st.c
@@ -1363,7 +1363,6 @@ st_shift(st_table *tab, st_data_t *key, st_data_t *value)
            return 1;
        }
     }
-    tab->entries_start = tab->entries_bound = 0;
     if (value != 0) *value = 0;
     return 0;
 }

記録のためにチケットがほしいのですが、作っていただけますか?

https://bugs.ruby-lang.org/projects/ruby-master/issues/new

もしご面倒でしたら、代行して作成しますので言ってください。

Updated by mame (Yusuke Endoh) 3 months ago

すみません、メールからチケットを作る仕組みがあるのを忘れてました。
それで作っておきました。

https://bugs.ruby-lang.org/issues/18578

続きはチケットの方に書こうと思います。

Updated by mame (Yusuke Endoh) 3 months ago

メモ:entries_bound は使用中のビン(DELETEDになったビンを含む)の数に(ほぼ)対応していて、これをみてテーブルをリビルドしている(rebuild_table_if_necessary)。空のハッシュに対する Hash#shift はなぜか entries_bound を 0 にしているので、リビルドすべきタイミングを逃し、ビンがすべて使用中になった状態で空きビンを探そうとするので無限ループに陥っていた(find_table_bin_ind)。

Actions #4

Updated by naruse (Yui NARUSE) 3 months ago

  • Backport changed from 2.6: UNKNOWN, 2.7: UNKNOWN, 3.0: UNKNOWN, 3.1: UNKNOWN to 2.6: REQUIRED, 2.7: REQUIRED, 3.0: REQUIRED, 3.1: REQUIRED
Actions #5

Updated by nobu (Nobuyoshi Nakada) 3 months ago

  • Description updated (diff)
Actions #7

Updated by mame (Yusuke Endoh) 3 months ago

  • Status changed from Open to Closed

Applied in changeset git|496591de96b261b8789332c7f8b2bfbd17658955.


st.c: Do not clear entries_bound when calling Hash#shift for empty hash

tab->entries_bound is used to check if the bins are full in
rebuild_table_if_necessary.

Hash#shift against an empty hash assigned 0 to tab->entries_bound, but
didn't clear the bins. Thus, the table is not rebuilt even when the bins
are full. Attempting to add a new element into full-bin hash gets stuck.

This change stops clearing tab->entries_bound in Hash#shift.
[Bug #18578]

Updated by naruse (Yui NARUSE) 3 months ago

  • Backport changed from 2.6: REQUIRED, 2.7: REQUIRED, 3.0: REQUIRED, 3.1: REQUIRED to 2.6: REQUIRED, 2.7: REQUIRED, 3.0: REQUIRED, 3.1: DONE

ruby_3_1 7fe0ebc4e7abd78501094cbb2d47918c8ff29f60 merged revision(s) 496591de96b261b8789332c7f8b2bfbd17658955.

Updated by nagachika (Tomoyuki Chikanaga) 2 months ago

  • Backport changed from 2.6: REQUIRED, 2.7: REQUIRED, 3.0: REQUIRED, 3.1: DONE to 2.6: REQUIRED, 2.7: REQUIRED, 3.0: DONE, 3.1: DONE

ruby_3_0 f404b21f849af06fb8bbd4b87fdfb585e904d6c3 merged revision(s) 496591de96b261b8789332c7f8b2bfbd17658955.

Actions #10

Updated by usa (Usaku NAKAMURA) about 2 months ago

  • Backport changed from 2.6: REQUIRED, 2.7: REQUIRED, 3.0: DONE, 3.1: DONE to 2.6: WONTFIX, 2.7: DONE, 3.0: DONE, 3.1: DONE
Actions

Also available in: Atom PDF