シンボリックリンクのループの検知方法について教えてください。

とあるディレクトリ以下のファイルの情報を再帰的に収集するとして、シンボリックリンクがループしていた場合は
ループを検知して、処理をスキップしたいのですが、以下の方法で良いのでしょうか?

1. シンボリックリンクかつリンク先がディレクトリの場合、該当のシンボリックリンクのiノード番号を記録しておく
2. ファイル走査している過程で、再度同じiノード番号のシンボリックリンクを辿ろうとしたら、処理をスキップする

man symlinkには、ループの検知は「リンクを辿ってみて、リンクの最大数を超えたらループとみなす」というやり方が
書いてありました。上記方法でケアできないパターンが存在するのでしょうか?
http://www.google.co.jp/search?hl=ja&client=firefox-a&rls=org.mozilla%3Aja%3Aofficial&hs=8FP&q=symbolic+link+loop+detection&btnG=%E6%A4%9C%E7%B4%A2&lr=

回答の条件
  • 1人2回まで
  • 登録:2009/05/01 12:47:56
  • 終了:2009/05/02 15:10:55

ベストアンサー

id:noocyte No.2

noocyte回答回数21ベストアンサー獲得回数32009/05/02 13:21:34

ポイント50pt

> 上記方法でケアできないパターンが存在するのでしょうか?


いやむしろ,上記方法の方が,有向グラフのサイクル (向きのついたループ)

検出アルゴリズムとしては真当です.2つの方法を比較すると,

(1) 上記方法 (探索中の経路上の節点をすべて記録する方法)
    (a) サイクルを検出する正しい方法である.
        (ただし今回の場合は zzz_1980 さんの指摘を考慮する必要がある.)
    (b) 探索する経路の長さが事前にわからないので,動的メモリ管理が必要.

(2) リンクをたどる回数を数え,上限値と比較する方法
    (c) 上限値より長い,サイクルでない経路をサイクルと誤判定してしまう.
    (d) 短いサイクル (例えば自分自身へのリンク) であっても,必ず上限回数
        だけリンクをたどらないと検出できない.誤判定を少なくしようとして
        必要以上に上限を大きくすると時間がかかる.
    (e) 動的メモリ管理不要で,実装が超簡単.

symlink で (2) の方法を採用したのは,たぶん次のような理由でしょう.


  • symlink(2) はライブラリ関数ではなくシステムコールなので,動的メモリ管理はなるべく避けたい.
    (malloc(3) はライブラリ関数なのでシステムコール内では使えない.
    カーネルモード内で使えるメモリ管理関数もなくはないが,制限がある(らしい).)

  • (c),(d) については,シンボリックリンクで無闇に長い経路を作るのは非実用的なので,小さい上限値で十分実用になるだろう.
    (手元の Ubuntu 8.04 で調べてみると,bits/posix1_lim.h で _POSIX_SYMLOOP_MAX=8 と定義されていました.)
id:mitani1207

なるほど。納得できました。

今回のケースではメモリについてはシビアではないので、(1)の方法を実施したいと思います。

ありがとうございます。

2009/05/02 15:10:16

その他の回答(1件)

id:zzz_1980 No.1

zzz_1980回答回数492ベストアンサー獲得回数642009/05/01 13:10:37

ポイント20pt

inode だけを保持する方法では、

ファイルシステムをまたがってシンボリックリンクをはられたとき

期待する動作になりません。

(inodeはファイルシステム毎に振られるから)

inode とせっとでフルパスを控えておかないと、

同じシンボリックリンクかどうかわかりません。

find / -inum 2 -print とかやってみるとわかりますよ。

id:mitani1207

なるほど。たしかにファイルシステムにまたがるケースも考慮しておく必要がありそうです。

ありがとうございます。

2009/05/01 18:31:50
id:noocyte No.2

noocyte回答回数21ベストアンサー獲得回数32009/05/02 13:21:34ここでベストアンサー

ポイント50pt

> 上記方法でケアできないパターンが存在するのでしょうか?


いやむしろ,上記方法の方が,有向グラフのサイクル (向きのついたループ)

検出アルゴリズムとしては真当です.2つの方法を比較すると,

(1) 上記方法 (探索中の経路上の節点をすべて記録する方法)
    (a) サイクルを検出する正しい方法である.
        (ただし今回の場合は zzz_1980 さんの指摘を考慮する必要がある.)
    (b) 探索する経路の長さが事前にわからないので,動的メモリ管理が必要.

(2) リンクをたどる回数を数え,上限値と比較する方法
    (c) 上限値より長い,サイクルでない経路をサイクルと誤判定してしまう.
    (d) 短いサイクル (例えば自分自身へのリンク) であっても,必ず上限回数
        だけリンクをたどらないと検出できない.誤判定を少なくしようとして
        必要以上に上限を大きくすると時間がかかる.
    (e) 動的メモリ管理不要で,実装が超簡単.

symlink で (2) の方法を採用したのは,たぶん次のような理由でしょう.


  • symlink(2) はライブラリ関数ではなくシステムコールなので,動的メモリ管理はなるべく避けたい.
    (malloc(3) はライブラリ関数なのでシステムコール内では使えない.
    カーネルモード内で使えるメモリ管理関数もなくはないが,制限がある(らしい).)

  • (c),(d) については,シンボリックリンクで無闇に長い経路を作るのは非実用的なので,小さい上限値で十分実用になるだろう.
    (手元の Ubuntu 8.04 で調べてみると,bits/posix1_lim.h で _POSIX_SYMLOOP_MAX=8 と定義されていました.)
id:mitani1207

なるほど。納得できました。

今回のケースではメモリについてはシビアではないので、(1)の方法を実施したいと思います。

ありがとうございます。

2009/05/02 15:10:16

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません