readdirの取得順について
Takayuki Hirota
廣田と申します。
HP-UX 10.20 にて開発を行っています。
この度、ある特定のディレクトリに存在するファイルを
順次処理していくプログラムの改造を行うことになりました。
このプログラムでは、ディレクトリ走査に
opendir(), readdir() を使用しているのですが、
このreaddir() で取得できるファイルの順番には
何か規則性があるのでしょうか？
初歩的な質問で恐縮ですが、よろしくお願い致します。
Shinji KONO
In article <90023a$jj5$1...@ns.dmz.cjs.co.jp> ,
"Takayuki Hirota" <hir...@cjs.co.jp> writes
>このreaddir() で取得できるファイルの順番には
>何か規則性があるのでしょうか？
ありません。(あったら、何に使うのかな?)
---
Shinji KONO @ Information Engineering, University of the Ryukyus,
PRESTO, Japan Science and Technology Corporation
河野真治 @ 琉球大学工学部情報工学科,
科学技術振興事業団さきがけ研究21(機能と構成)
Takahiiko Makino
Takayuki Hirotaさんの<90023a$jj5$1...@ns.dmz.cjs.co.jp>から
>このプログラムでは、ディレクトリ走査に
>opendir(), readdir() を使用しているのですが、
>このreaddir() で取得できるファイルの順番には
>何か規則性があるのでしょうか？
ディレクトリエントリに記録されてる順番ではないでしょうか?
--
Takahiko Makino - mailto:pma...@sfc.ne.jp
Junn Ohta
fj.comp.lang.cの記事<900inf$n6r$1...@nsv3001.zaq.ne.jp>で
shi...@nintendo.co.jpさんは書きました。
> 「ありません」ってのには語弊があって、同じ directory 構成
> なら何度 readdir() したって同じ順序で取得出来る訳ですから、
> 何らかの「規則性」は否めないでしょう。
これを「規則性」と呼びたいかどうかにはそれなりに異
論があるかも。
同じタネを与えたら毎回同じ乱数列を生成する疑似乱数
発生器の生成する乱数列には「規則性がある」といって
よいですか? まあそういっても間違いではないのだろう
けど、規則そのものがブラックボックスである以上、万
人に受け入れられるのは「再現性がある」程度ではない
ですかね。
> 「規則性」はあるけど「決まり」はないので、具体的な規則詳細
> については case by case といった辺りが無難な解でしょうか。
(以下略)
用語についてはともかく、このあたりはおっしゃるとお
りで、たいへん参考になります。
--
太田純(Junn Ohta) (株)リコー/新横浜事業所
oh...@sdg.mdd.ricoh.co.jp
ku...@gssm.otsuka.tsukuba.ac.jp
oh...@src.ricoh.co.jpさん:
> 単なるタッパーウエアの隅なんですが...。
というのは重箱の隅ほど細かくないという意味? (全般的に言って
隅の曲率はタッパーウェアの方が小さい --- 曲がりがゆるやか、
ですよね。ああまたfj.sci.lang.japaneseネタになってるがご勘弁)
> 同じタネを与えたら毎回同じ乱数列を生成する疑似乱数発生器の生成
> する乱数列には「規則性がある」といってよいですか? まあそういっ
> ても間違いではないのだろうけど、規則そのものがブラックボックス
> である以上、万人に受け入れられるのは「再現性がある」程度ではな
> いですかね。
その再現性は保証されているのでしょうか? 時々中身を再構成したり
して順番が変わってしまう実装は排除されていないと考えていたのです
が。
ただし再構成したときに読みつつあったreaddir()がヌケを起こさな
いような工夫が必要ですけど。
その辺の仕様はPOSIXではどうなってるのかな? 久野
Takashi SHIRAI
In article <29799.9...@rananim.ie.u-ryukyu.ac.jp>,
Shinji KONO <ko...@ie.u-ryukyu.ac.jp> wrote:
>河野 真治@琉球大情報工学です。
>>このreaddir() で取得できるファイルの順番には
>>何か規則性があるのでしょうか？
>
>ありません。(あったら、何に使うのかな?)
「ありません」ってのには語弊があって、同じ directory 構成
なら何度 readdir() したって同じ順序で取得出来る訳ですから、
何らかの「規則性」は否めないでしょう。
ただ、その「規則性」は何かの共通規格や仕様書で定められてい
るものではなくて、readdir() や filesystem の実装をする人が勝
手に定めたものである訳ですね。
「規則性」はあるけど「決まり」はないので、具体的な規則詳細
については case by case といった辺りが無難な解でしょうか。
実際のところ、directory の中身の構造は大抵の場合は「作った
順」に並んでます。けど、filename 長等の要素により可変長構造
をしていて更に padding もあるんで、その規則性を調べるのは割
と難しいかも知れません。
また、べたーっと並べておくだけだと 10,000 番目の filename
を探し出すのに 10,000 回の比較をしないといけなくて効率が悪い
ので、最近の新しい filesystem ではそれを避けるために「作った
順」には並んでいないこともあり、そうなるともっと複雑な規則に
なりますね。
readdir() はこういった directory の中身を順に取り出してく
る仕様になっていることが多いので、そういう仕様では directory
内の構造的な順序自体が readdir() の順序になります。でも、そ
うでないといけないという決まりもないので、そうでない場合は更
に複雑な規則となるでしょう。
結論としては、「気にするな」ってところでしょうかね。
--
白井 隆 (as Ｎｅｃｏ)
Junn Ohta
ku...@gssm.otsuka.tsukuba.ac.jpさんは書きました。
> というのは重箱の隅ほど細かくないという意味?
# いやあそれほどでも(って意味不明? ^^;)。まあ重箱
# の隅ほど見つけにくくはない、という程度の気持ち。
> その再現性は保証されているのでしょうか? 時々中身を再構成したり
> して順番が変わってしまう実装は排除されていないと考えていたのです
> が。
たしかにそうですね。「再現性がある」を持ち出したの
は「規則性があるとはいえないかも」を補強するためだ
ったので、「あってもせいぜい再現性くらい」と言いか
えておきます。それでじゅうぶんですよね。
> その辺の仕様はPOSIXではどうなってるのかな?
POSIX準拠のSunOS 5.7のreaddir_r()のmanを見てもその
あたりは書かれていませんね。opendir()やrewinddir()
してからファイルが追加あるいは削除された場合、その
ファイルがreaddir()で見えるかどうかはunspecifiedで
ある、とは書かれていますが...。
ku...@gssm.otsuka.tsukuba.ac.jp
> # いやあそれほどでも(って意味不明? ^^;)。まあ重箱
> # の隅ほど見つけにくくはない、という程度の気持ち。
なるほど。では見つけ易さの程度を表すにはカーブの曲線半径を明示
するということでよろしくお願いします :-P
見つけやすい場合は「ボウルの隅」かな。:-)
> たしかにそうですね。「再現性がある」を持ち出したのは「規則性が
> あるとはいえないかも」を補強するためだったので、「あってもせい
> ぜい再現性くらい」と言いかえておきます。それでじゅうぶんですよ
> ね。
と思います。
> POSIX準拠のSunOS 5.7のreaddir_r()のmanを見てもそのあたりは書か
> れていませんね。opendir()やrewinddir() してからファイルが追加
> あるいは削除された場合、そのファイルがreaddir()で見えるかどう
> かはunspecifiedである、とは書かれていますが...。
なるほど、そのファイル自体はそうだとして、他のファイルについて
は順番はともかくちゃんと見えなければいけないですから、再構成する
ような実装だったら、たとえばバージョンを付与して管理するとか、
opendir()で実は全部メモリに取っちゃうとか、そういう工夫が必要に
なりますね。
でもlookupが速くなるとメリットがありますよね 久野
Junn Ohta
ku...@gssm.otsuka.tsukuba.ac.jpさんは書きました。
> なるほど。では見つけ易さの程度を表すにはカーブの曲線半径を明示
> するということでよろしくお願いします :-P
材質の透明性というのも影響しますが...。:-)
> 再構成する
> ような実装だったら、たとえばバージョンを付与して管理するとか、
> opendir()で実は全部メモリに取っちゃうとか、そういう工夫が必要に
> なりますね。
そうなるとopendir()で「メモリーが足りない」という
errnoを追加する必要があったりしますし、現在の仕様
のままでは無理でしょう。
ku...@gssm.otsuka.tsukuba.ac.jp
oh...@src.ricoh.co.jpさん:
> 材質の透明性というのも影響しますが...。:-)
おおっと! これはしたり。:-)
そうなると屈折率とかも問題になりますね。
反射率も問題になるか…内側が鏡張りとか。
また、内容探索機能などが装備されているか否かも(もうやめよう)。
> そうなるとopendir()で「メモリーが足りない」というerrnoを追加す
> る必要があったりしますし、現在の仕様のままでは無理でしょう。
なるほどー。やっぱりファイルシステム側でディレクトリをバージョ
ン管理方式にするとかかな。
log-based filesystemとか使われてるんだろうか? 久野
Takashi SHIRAI
In article <900n8g$5k$1...@ns.src.ricoh.co.jp>,
Junn Ohta <oh...@src.ricoh.co.jp> wrote:
>単なるタッパーウエアの隅なんですが...。
メーカは当然「UNIX」ですね :-)
>> 「ありません」ってのには語弊があって、同じ directory 構成
>> なら何度 readdir() したって同じ順序で取得出来る訳ですから、
>> 何らかの「規則性」は否めないでしょう。
>
>これを「規則性」と呼びたいかどうかにはそれなりに異
>論があるかも。
そうですね。この場合は一般的な用法としての規則性という意味
からはちょっと遠いと思います。なんで括弧付きで書いたんですけ
どね。
飽くまでも「何らかの規則性」であって、それが何であるかにつ
いては言及してないのもまぁ逃げな訳でして。
>同じタネを与えたら毎回同じ乱数列を生成する疑似乱数
>発生器の生成する乱数列には「規則性がある」といって
>よいですか? まあそういっても間違いではないのだろう
>けど、規則そのものがブラックボックスである以上、万
>人に受け入れられるのは「再現性がある」程度ではない
>ですかね。
それは受け止め方に寄ると思うんです。元の質問者の方がもし各
種 filesystem の仕組みに精通されていたとしたらこんな質問はし
ない訳で、仕組みが判っていない立場から見ると疑似乱数とて「規
則性」と感じてしまうんじゃないでしょうか。
それに対して「規則性はない」だけの回答で果して納得して貰え
るかどうか。ここは「あるけどない」といったちょっと遠回しな回
答の方が納得させ易いんじゃないかと思いました。
そんな辺りを丁寧に対応してあげることで、一人でも多く hacker
が生まれてきてくれるといいな、なんて考えてたりもして。
＃ 知的好奇心をくすぐった回答にしたつもりなんですが、んーそ
＃うは読めないですねー。
>> 「規則性」はあるけど「決まり」はないので、具体的な規則詳細
>> については case by case といった辺りが無難な解でしょうか。
>(以下略)
>
>用語についてはともかく、このあたりはおっしゃるとお
>りで、たいへん参考になります。
昔、何種類かの filesystem についてこの手の規則性を解析した
ことがあって、実際多くの実装ではちゃんと挙動を予想出来る程度
の規則性はあるんですよね。
こういった割としっかりした規則性が崩壊したのって割と最近の
ことなので、まだまだ規則性を持つ実装の方が多いと思います。探
求心煽られる人がいてもおかしくないかも。
勿論、multitask 環境上で常に生まれたり消えたりし続ける可能
性のある代物なんで、一アプリの視点からは完全には予測不可能で
すが、「ない」って言われてそれで終っちゃうよりは、「ある」っ
て言われて「どんなんだろ？」って突きとめ始める方が前向きなん
じゃないかなーなどと考えてたりもします。
Junn Ohta
shi...@nintendo.co.jpさんは書きました。
> >単なるタッパーウエアの隅なんですが...。
> メーカは当然「UNIX」ですね :-)
うまいっ。:-)
> 昔、何種類かの filesystem についてこの手の規則性を解析した
> ことがあって、実際多くの実装ではちゃんと挙動を予想出来る程度
> の規則性はあるんですよね。
その規則性って、単純化すれば
(1) たくさんのスロットが並んでいる
(2) ファイル名が生成されるとfirst fitで空きスロッ
トを探してそこに書き込む
(3) ファイル名を削除するとそこが空きスロットになる
(4) 空きスロットができてもつめて空きをなくしたりは
しない
といったところですよね? (知識が古いか? ^^;)
「どんな順にファイル名の生成と削除が行われたかの履
歴があれば現在のスロットの状況が予測できる」という
意味での規則性はありますが、元記事で期待されている
規則性とは違いそうです。
> こういった割としっかりした規則性が崩壊したのって割と最近の
> ことなので、まだまだ規則性を持つ実装の方が多いと思います。探
> 求心煽られる人がいてもおかしくないかも。
なるほど。やはり「自分でfilesystemを設計してみる」
のがいちばんなのでしょう。そういう方向であおられて
くれる人が多いとうれしいなあ。
Kusakabe Youichi
> > メーカは当然「UNIX」ですね :-)
> うまいっ。:-)
ヘ_ヘ ____________________________
ミ・・ ミ vo...@merope.pleiades.or.jp
( ° )～ 日下部陽一
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Junn Ohta
vo...@merope.pleiades.or.jpさんは書きました。
> でもあのブランド名は最近は使われていないみたいですよ。
# いつのまにか「Linux」になってる? (^^;
Takashi SHIRAI
In article <9038qm$q02$1...@ns.src.ricoh.co.jp>,
Junn Ohta <oh...@src.ricoh.co.jp> wrote:
>その規則性って、単純化すれば
>(1) たくさんのスロットが並んでいる
>(2) ファイル名が生成されるとfirst fitで空きスロッ
> トを探してそこに書き込む
>(3) ファイル名を削除するとそこが空きスロットになる
>(4) 空きスロットができてもつめて空きをなくしたりは
> しない
>といったところですよね? (知識が古いか? ^^;)
filename が固定長だった時代だと正にそのとおりだったと思い
ますが、可変長になってからはここで言う各「スロット」がそれぞ
れ異なるサイズなんで、padding を考慮しながら「空きスロット」
を求めるのがちょっと厄介ですね。
最近の PC-UNIX だと kernel source を直接解析してその辺の仕
組みを知ることも可能ですけど、商用 UNIX だと全くの black box
なんで内部構造を想像しながらあーでもないこーでもないと、結構
楽しい解析作業かも知れません。
>「どんな順にファイル名の生成と削除が行われたかの履
>歴があれば現在のスロットの状況が予測できる」という
>意味での規則性はありますが、元記事で期待されている
>規則性とは違いそうです。
そうですね。探求心が無ければ単なる「謎の順序」で終ってしま
っても仕方ないでしょう。しょっちゅう作成・削除が繰り返される
directory となると、「現在の状態」だけを考察する場合は既に何
の規則性も無いに等しいと思います。
ただ、「何の理由もない」訳ではないということを、後継のため
にも主張しておきたいですね。その一見規則性なく見える並びも偶
然ではなく必然であった訳ですから。
>なるほど。やはり「自分でfilesystemを設計してみる」
>のがいちばんなのでしょう。そういう方向であおられて
>くれる人が多いとうれしいなあ。
Linux 方面で「次世代 filesystem」が色々開発されてるんで、
そこここに煽られた人がいたってことかも知れませんね。
Nakayama Ryu~ji
oh...@src.ricoh.co.jp (Junn Ohta) さん、
> fj.comp.lang.cの記事<9033t8$fra$1...@nsv3001.zaq.ne.jp>で
> shi...@nintendo.co.jpさんは書きました。
> > 昔、何種類かの filesystem についてこの手の規則性を解析した
> > ことがあって、実際多くの実装ではちゃんと挙動を予想出来る程度
> > の規則性はあるんですよね。
>
> その規則性って、単純化すれば
> (1) たくさんのスロットが並んでいる
> (2) ファイル名が生成されるとfirst fitで空きスロッ
> トを探してそこに書き込む
> (3) ファイル名を削除するとそこが空きスロットになる
> (4) 空きスロットができてもつめて空きをなくしたりは
> しない
> といったところですよね? (知識が古いか? ^^;)
私の経験はSolarisしかないのですが、
・エントリ(上記で言うところのスロット?)はディスクブロックを跨がない
という性質があります。
具体的には、例えばエントリをたくさん作ってブロック(大抵512byte)境界に
あと16byteというところまで来たときに、8byte以上の長さを持つi-nodeをエ
ントリに登録しようとすると、残っている16byte分は飛ばして、513byte目か
ら4+2+2+ファイル名の長さ+1(+padding)分のエントリを確保してしまいます。
そのあとで、8byte未満の長さのエントリを登録しようとすると、先ほど飛ば
したエントリが最初にあたりますので、そこに登録されます。
> 「どんな順にファイル名の生成と削除が行われたかの履
> 歴があれば現在のスロットの状況が予測できる」という
> 意味での規則性はありますが、元記事で期待されている
> 規則性とは違いそうです。
ですから、ここのところはもう少しだけ複雑になるかと。:-)
--
中山隆二
nakayam...@lab.ntt.co.jp
ARIMA Yasuhiro
ku...@gssm.otsuka.tsukuba.ac.jp wrote:
> なるほどー。やっぱりファイルシステム側でディレクトリをバージョ
> ン管理方式にするとかかな。
>
> log-based filesystemとか使われてるんだろうか? 久野
読んだ話によると、Plan9 の filesystem ではそれをやってるような。
--
有馬 康弘 <fit...@fitec.co.jp>
Takashi SHIRAI
In article <01n1egj...@rina.pflab.ecl.ntt.co.jp>,
Nakayama Ryu~ji <nakayam...@lab.ntt.co.jp> wrote:
>私の経験はSolarisしかないのですが、
>
>・エントリ(上記で言うところのスロット?)はディスクブロックを跨がない
>
>という性質があります。
raw device が blocksize 単位でしか access 出来ないため、こ
れを跨いだ directory entry は access 効率が悪くなるので作ら
ないようになっていますね。
と書くと raw device を持たない Linux では関係ない話のよう
にも思えますが、ext2fs でもこの性質は守られています。
私の知る限りは、Solaris 以外の UNIX でも block size を跨い
だ directory entry を作るような file system の実装は無さそう
です。
padding の boundary や directory entry size はそれぞれ異な
りますけどね。filename 部分を除いた directory entry size は
大抵 sizeof(struct dirent) - sizeof(d_name) に一致します。