Not only is the Internet dead, it's starting to smell really bad.:2021年05月24日分

2021/05/24(Mon)

[オレオレN6] 続・bm(3)のバグのお話

Sunday法についてもうちょっと理解を深めていくことにしたいと思う、何の意味があるかは知らんが。

@Sunday法の高速化の隠し味である4.1.5 ufast loopを読み解く

前提条件として

  • 検索対象文字列のケツに
  • 検索パターン文字列と同じ長さのガード領域(いわゆる番兵)を用意する
  • そこを検索パターン文字列の末尾1文字で埋める*1

ことが可能であることが必須、よってstrstr(3)やregex(3)的なconst char *を引数に取るI/F設計ではこの番兵領域を用意することができないという問題がある。

この4.1.5 ufast loopで行っているのは「不一致文字だったらその文字からテーブルを引いて移動量を求め現在位置を進める」という処理。

通常なら

1	while (s < e) {
2		while ((k = d0[*s]) != 0) {
3			if (s >= e - k)
4				return NULL;
5			s += k;
6		}
7		...
8	}

ちゅー感じで

  • 2行目 … 移動距離 k が0ではないこと、すなわち検索パターン文字列の末尾と不一致のチェック
  • 3行目 … s が k 移動した場合に e を超えないこと、すなわちOOB(Out Of Bounds)してないことのチェック

というコードを書くところだ。

ところがufast loopの実装ではループをアンロールして高速化を図っている。

1	while (s < e) {
2		k = d0[*s];             /* ufast skip loop */
3		while (k) {
4			k = d0[*(s += k)];
5			k = d0[*(s += k)];
6			k = d0[*(s += k)];
7		}
8		if (s >= e)
9			break;
10		...
11	}

4~6行目で都合3回OOBチェック無しにsを移動させてますな、この僅かな差が性能向上に繋がってるってことね。 なぜ3回なのか、それはペーパーでは1~6回アンロールした結果を比較してバランス的に3回を選んだとあるので、別に増やしても減らしてもよいそうだ。

なおワイは頭が悪いので最初は

  • 4~5行目でk == 0でループ脱出条件を満たしても
  • 6行目がk != 0だったらループ脱出できない

よって場合によっては無限ループにならねえか?と思ってしまったのだけど、ちょっと考えると問題ないことが判る。

たとえば4行目で0が返されたら5行目でのsの移動距離はゼロなので4行目と同じ結果が返る、よって6行目も以下同文、つまり3回のうち1回でも条件満たせば安全にループ抜けられることが保証されているのだ。

だからこそ3回ループ展開してもガード領域の長さは3回分でなく1回分で十分なわけ、1回でもガード領域を踏んだらk == 0が保証されるからそれ以上後ろにはアクセスしないのでな。

ここまで理解すればこのテクニックはガード領域がないと成立しないということがわかるよね…

しかしKeith BosticちゅーGuruレベルの人でも、メインループの終了条件であるeすなわちbase(検索対象文字列)のケツ

	s = base+pat.patlen-1;
	e = base+n;
	memset(e, pat[patlen–1], patlen);
	while (s < e) {
		while (k) {
 			k = d0[*(s += k)];
			...
 		}
	}

↑を↓に変更すれば動くだろくらいのノリで論文斜め読みで実装するんだなぁと思いましたまる。

	s = base + (pat->patlen - 1);
	e = base + n - 3 * pat->patlen;
	while (s < e) {
		while (k) {
 			k = d0[*(s += k)];
			...
 		}
	}

でも問題はメインループじゃなくてufast loopの方なんだからいくらケツ動かしたって駄目だよね…

なもんで PR/42032として報告されるバグが発生し、N7に以下のような修正が入ったというわけ。

diff --git a/lib/libc/string/bm.c b/lib/libc/string/bm.c
index e38fe7db6c5..5dc211f8c64 100644
--- a/lib/libc/string/bm.c
+++ b/lib/libc/string/bm.c
@@ -201,7 +201,7 @@ bm_exec(pat, base, n)
 	e = base + n - 3 * pat->patlen;
 	while (s < e) {
 		k = d0[*s];		/* ufast skip loop */
-		while (k) {
+		while (k && s < e) {
 			k = d0[*(s += k)];
 			k = d0[*(s += k)];
 		}

おケツを超えてないことのチェックが追加されている。 でもこの修正って不十分だよね、まだufast loopに未練が残っててループのアンロールが残ってしまっている。

1回のsの移動でもおケツを超えてしまったならばそこはOOBなので、参照しようとしたら場合によってはSIGSEGVやSIGBUSでお亡くなりになるはずなんよね…

じゃあ正しい修正はどうすべきかというと、これはどうあがいても実装不可能なんだからまずufast loopを諦めるのが正しい。

diff --git a/lib/libc/string/bm.c b/lib/libc/string/bm.c
index a961cbb0ce6..d67f6c58965 100644
--- a/lib/libc/string/bm.c
+++ b/lib/libc/string/bm.c
@@ -163,60 +163,30 @@ bm_free(bm_pat *pat)
 u_char *
 bm_exec(bm_pat *pat, u_char *base, size_t n)
 {
-	u_char *e, *ep, *p, *q, *s;
-	size_t *d0, k, md2, n1, ro;
-	int rc;
+	u_char *e, *s;
+	size_t k, n1;
 
 	_DIAGASSERT(pat != NULL);
 	_DIAGASSERT(base != NULL);
 
-	if (n == 0)
-		return NULL;
-
-	d0 = pat->delta;
 	n1 = pat->patlen - 1;
-	md2 = pat->md2;
-	ro = pat->rareoff;
-	rc = pat->rarec;
-	ep = pat->pat + pat->patlen - 1;
-	s = base + (pat->patlen - 1);
-
-	/* fast loop up to n - 3 * patlen */
-	e = base + n - 3 * pat->patlen;
-	while (s < e) {
-		k = d0[*s];		/* ufast skip loop */
-		while (k && s < e) {
-			k = d0[*(s += k)];
-			k = d0[*(s += k)];
-		}
-		if (s >= e)
-			break;
-		if (s[ro] != rc)	/* guard test */
-			goto mismatch1;
-					/* fwd match */
-		for (p = pat->pat, q = s - n1; p < ep;)
-			if (*q++ != *p++)
-				goto mismatch1;
-		return s - n1;
-
-mismatch1:	s += md2;		/* md2 shift */
-	}
-
-	/* slow loop up to end */
+	s = base + n1;
 	e = base + n;
+
 	while (s < e) {
-		s += d0[*s];		/* step */
-		if (s >= e)
-			break;
-		if (s[ro] != rc)	/* guard test */
-			goto mismatch2;
-					/* fwd match */
-		for (p = pat->pat, q = s - n1; p <= ep;)
-			if (*q++ != *p++)
-				goto mismatch2;
-		return s - n1;
-
-mismatch2:	s += md2;		/* md2 shift */
+		/* fast skip loop */
+		while ((k = pat->delta[*s]) != 0) {
+			if (s >= e - k)
+				return NULL;
+			s += k;
+		}
+		/* guard test */
+		if (s[pat->rareoff] == pat->rarec &&
+		/* fwd match */
+		    !memcmp(pat->pat, s - n1, n1))
+			return s - n1;
+		/* md2 shift */
+		s += pat->md2;
 	}
 
 	return NULL;

はいコードもすっきりしたよね、ufast loopとslow loopのふたつのメインループがあったけど、fast loopのひとつに一本化できたし、goto も廃止することができた。

やたらと無駄な変数が多いのも古いコードなのでregister修飾子つけることで高速化を期待してたことの名残だから消しまくり、もはや今の時代無意味だし。

あと素のBM法やBMH法だとマッチしなかった場合の移動距離の算出に何文字目までマッチしたかが必要になるのだけど、Sunday法ではもはや必要ない情報なので、手書きループでマッチかけずともmemcmp(3)を使えばよろしい。 コンパイラくんが__builtin_memcmp()的なもので高速化してくれるのも期待できる、逆に遅くなってたら戻せばいいだけだ:-P

@bm(3)についてはデザインも微妙なんだよな…

プロトタイプu_char *(=unsigned char *)なのconst char *に変えたいよね、いちいち呼出し側でキャストするのめんどくせえ。 だってunsigned char *である必要性って、d0[*s]の一か所だけだもん。

あとわざわざ検索パターン文字列をコピーしてること、ポインタだけ持ってればいい話でね。 さらに移動距離のテーブルであるdeltaも固定長で宣言できるのにいちいちmalloc(3)してるし。

そもそもbm_pat型がbm.hで臓物見えてるのも気に入らないのだよな、こういうのは

typedef struct bmpat *bmpat_t;

みたいに不完全型にして実装見せるもんじゃないよねぇ、まぁ古いコードだからしゃーないけど。

これらの問題を修正しようとするとギリギリバイナリ互換は達成できそうでも、ソース互換無くなるからやっぱ変えられないので困る。 やっぱりオレオレN6では新しい実装入れて、bm(3)はobsoleteにしようかなという感じ。

*1:前回先頭一文字だけ検索パターン文字列のケツ1文字で後はゼロフィルと正しくない事を書いてしまったが、これはワイがなぜかmemset(3)とmemcpy(3)を見間違えたせい、斜めに読み過ぎて首が75°くらい曲がってない?大丈夫?

[宗教] ThinkPad X220 3号機逝く

今日になって電源すら入らなくなった、お前ら煽ったからって藁人形に五寸釘打つのを止めろ!(被害妄想)

ACアダプターを刺すとバッテリーランプは点滅するので、キーボードの問題が電源ボタンにまで進んだ感じやな。 なのでキーボードの疑いが高まったけど依然システムボード側かもしれない、犯人は20代から30代、もしくは40代から50代の可能性もある。

システムボードなら臓器移植の時間だね(ニッコリ)なんだが、問題はもはやX220のシステムボードってあまり売ってないんだよな、あってもX220iのi3とか。 やっぱりX230化しか無いのかね、7段キーボードは物理的にはつくけど認識しないキーがいくつかあって改造BIOSも無いのがネック。まぁ一番のネックはお金なんですけどねー。