Path: katsu From: katsu@sra.co.jp (WATANABE Katsuhiro) Message-ID: Date: 08 Aug 1994 02:41:36 GMT Organization: Software Research Associates, Inc.,Japan In-reply-to: s-fujii@sra.co.jp's message of Tue, 22 Feb 1994 09:30:18 GMT Newsgroups: sra.os.unix Subject: Re: ndbm Distribution: sra References: あまりのフォローの遅さが議論の妨げになっていたらごめんなさい。 記事 で s-fujii@sra.co.jp (Seigo Fujii) さんいはく > :> キーと内容の組みの合計サイズは、内部ブロックサイズ (現在 > :> 4096 バイト) を超えてはいけません。さらに、ハッシュ結果が同 > :> じであるキーと内容の組みはすべて、1 つのブロックに対応させな > :> ければなりません。分けることのできないデータで、ディスクブロ > :> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ > :> ックがいっぱいになった場合、dbm_store はエラーを返します。 > :> ^^^^^^^^^^^^^^^^^^^^^^^^^^^ > :> > :> ^^^ の部分のような状況はどのようなときに起きるのでしょうか？ > :> 回避する ( 発生させない / 発生時の対応 ) 方法はあるのでしょうか？ > :> 「分けることのできないデータ」とは？ > :その前の二つの文で言ってる状況を指すと思います. > :すなわち「分けることのできないデータ」とは, > :・一つのキー/内容の組 > :・ ハッシュ結果が同じになる複数のキー/内容の組 > :のことで、エラーが起きる状況とは, > :(1) 一つのキー/内容の組の合計サイズが 4096 byte を越えているとき, > これがエラーになるのはわかるけど。 > > :(2) ハッシュ結果が同じになる複数の キー/内容の組の合計サイズ(単純な合計で > : いいかどうかは分からない)が 4096 byte を越えたとき. > げげげ、エラーするかしないかは運しだいってこと？ > こんなものを /etc/passwd に使ってるとは、、信じ難いなあ。 　こうした、key の hash 値の衝突かもしれない(わからない)現象に 遭遇したので報告します。 　付録のプログラムは、標準入力から数を読み込んでそれを int(4bytes) に 直したものを key とし、1000 バイトほどの contents をもつデータを DBM ファイルに書き込むものです。たまたま hashlist というファイルの 中身を key として選んでみると、13 個ほどのデータを書いたところで それ以上 store できなくなる場合(OS)があります。 　CISC-NEWS か RISC-NEWS で make test を試してみてください。しばらく すると store_dbm(3)が -1 を返すのが観察できます。 　Sun だと動いてしまうようですが、キーの選び方のせいなのか、それとも こういった問題が本質的に Sun には存在しないのかは不明です。 　データの長さを短くすると、それに応じて store に失敗するまでの回数が 延びるので、key の hash 値の衝突に関係あるんじゃないかと想像しています。 　よくわからないのは、一旦 store_dbm(3) が一旦 1 を返すような ことがあると、それ以降どんな key を指定しようとも store_dbm(3) が 失敗し続けることです。以前成功した(つまり現在 DBM ファイルに 存在している) key で再びデータを store しようとした時でさえも。 　それにしても、pag ファイルのでかくて隙間だらけなこと。十数個しか エントリがないのに 1.8G ですって。 -- 渡邊克宏＠システム技術グループ（四谷） #!/bin/sh # This is a shell archive (produced by shar 3.49) # To extract the files from this archive, save it to a file, remove # everything above the "!/bin/sh" line above, and type "sh file_name". # # made 08/08/1994 02:36 UTC by katsu@sran14 # Source directory /var/home/mmb/katsu/dbm # # existing files will NOT be overwritten unless -c is specified # # This shar contains: # length mode name # ------ ---------- ------------------------------------------ # 287 -rw-r--r-- Makefile # 1520 -rw-r--r-- enter.c # 737 -rw-r--r-- hashlist # # ============= Makefile ============== if test -f 'Makefile' -a X"$1" != X"-c"; then echo 'x - skipping Makefile (File already exists)' else echo 'x - extracting Makefile (Text)' sed 's/^X//' << 'SHAR_EOF' > 'Makefile' && hash: hash.c X $(CC) -o hash hash.c X enum: enum.c X $(CC) -o enum enum.c X enter: enter.c X $(CC) -o enter enter.c X test: enter hashlist X head -20 hashlist | enter X clean: X -cp /dev/null /var/tmp/ndbmtest X -rm /var/tmp/ndbmhash.dir /var/tmp/ndbmhash.pag X -rm /var/tmp/fr.dir /var/tmp/fr.pag SHAR_EOF chmod 0644 Makefile || echo 'restore of Makefile failed' Wc_c="`wc -c < 'Makefile'`" test 287 -eq "$Wc_c" || echo 'Makefile: original size 287, current size' "$Wc_c" fi # ============= enter.c ============== if test -f 'enter.c' -a X"$1" != X"-c"; then echo 'x - skipping enter.c (File already exists)' else echo 'x - extracting enter.c (Text)' sed 's/^X//' << 'SHAR_EOF' > 'enter.c' && /* X $Id:$ X X Usage: $0 filename datasize */ X #include #include #include #include #include X #define DATASIZE (PBLKSIZ - 16) X char *malloc(); X main(argc, argv) int argc; char **argv; { X X DBM *hashfile; X datum hashvalue; X datum contents; X char *rawdata; X int keyvalue; X int datasize; X char *filename; X int i, e; X X X if (argc > 2) { X datasize = atoi(argv[2]); X } else { X datasize = DATASIZE; X } X if (argc > 1) { X filename = argv[1]; X } else { X filename = "/usr/tmp/fr"; X } X X contents.dsize = datasize; X rawdata = malloc(datasize); X if (rawdata == NULL) { X fprintf(stderr, "Cannot allocate memory.¥n"); X exit(1); X } X contents.dptr = rawdata; X for (i = 0; i < datasize; i++) { X contents.dptr[i] = 0; X } X hashvalue.dsize = sizeof(int); X hashvalue.dptr = (char *)&keyvalue; X X hashfile = dbm_open(filename, O_CREAT | O_RDWR, 0777); X if (hashfile == NULL) { X fprintf(stderr, "cannot open hashfile.¥n"); X exit(1); X } X while (1) { X e = scanf("%d", &keyvalue); X if (e == EOF) { X break; X } else if (e != 1) { X fprintf(stderr, "Illegal input¥n"); X break; X } X fprintf(stderr, "store %d¥n", keyvalue); X e = dbm_store(hashfile, hashvalue, contents, DBM_REPLACE); X if (e == 1) { X fprintf(stderr, "dbm_store returns %d at key %d.¥n", e, keyvalue); X } else if (e < 0) { X fprintf(stderr, "dbm_store returns %d at key %d.¥n", e, keyvalue); X } X } X dbm_close(hashfile); X exit(0); } SHAR_EOF chmod 0644 enter.c || echo 'restore of enter.c failed' Wc_c="`wc -c < 'enter.c'`" test 1520 -eq "$Wc_c" || echo 'enter.c: original size 1520, current size' "$Wc_c" fi # ============= hashlist ============== if test -f 'hashlist' -a X"$1" != X"-c"; then echo 'x - skipping hashlist (File already exists)' else echo 'x - extracting hashlist (Text)' sed 's/^X//' << 'SHAR_EOF' > 'hashlist' && 1252 2202 32461 64319 68877 72466 92790 117615 122150 135857 156361 160846 165404 170446 188254 197072 208441 208742 264362 292447 309003 318288 323011 326709 342609 348715 353436 360326 391547 430800 457328 462404 470121 499040 518779 577325 598896 612304 613264 680968 691122 693584 693898 702589 706139 711582 763761 777460 837983 838721 877129 917504 954231 958317 1011459 1012642 1024720 1057331 1063220 1064478 1065821 1080765 1095381 1101401 1107882 1171689 1173020 1181209 1183270 1186049 1200447 1207850 1238269 1240315 1245376 1254620 1260315 1262458 1275456 1302170 1343351 1369807 1377046 1392747 1409465 1412567 1424246 1430818 1434136 1438301 1446876 1481116 1489889 1494138 1513042 1540904 1546734 1552339 1563514 1564551 SHAR_EOF chmod 0644 hashlist || echo 'restore of hashlist failed' Wc_c="`wc -c < 'hashlist'`" test 737 -eq "$Wc_c" || echo 'hashlist: original size 737, current size' "$Wc_c" fi exit 0