FFS - F* ファイルシステム

これは、OSカーネルを介してファイルを読み取るのではなく、ディスクを直接読み取ってファイルを検索するCLIツール（grepのようなもの）です。実用性はほぼありませんが、ものすごくクールです。

これはわずか約1.5k行のCコードであり、以下の特徴があります：

rawデバイスノード（例: /dev/rdisk*）を読み取るときだけsudoが必要。イメージファイルの検索には昇格権限は不要
macOSのメインディスク上で実行するにはSIP保護を無効化する必要がある
最近のファイル書き込みの一部を見逃す可能性がある（手動でsyncを呼ぶ必要がある）
OS内の他のシステムコンポーネントがファイルを書き込んでいる間、変動の激しいファイルシステム上のツリーを検索できない可能性がある
このプロジェクトで手動実装されたファイルシステムのみで動作する

しかし同時に

ディスクからブロックを直接読み取る
VFS / バッファリングされたread()パスをバイパスし、代わりにブロックデバイスを直接preadする
検索するファイルが多ければ多いほど、ripgrepよりも速くなる
マウントされていないボリュームを検索できる - バイナリブロブを解析するだけ
バイナリファイルを検出してスキップする
openmpを使用して全コアに負荷を分散する

実際に高速なファイル検索が必要な場合は、私のプロジェクト fff をチェックしてください - sudoを必要とせずにripgrepを大幅に上回る性能です。

対応ファイルシステム

Linuxでは、ほとんどどのファイルシステムも簡単に実装できます。

Ext4

./fs/ext4.c

これはサポートするのが最も簡単なファイルシステムです。インプレース書き込みを行うジャーナリングファイルシステム（コピーオンライトなし）なので、ほとんどの場合、ffsにとって最適なファイルシステムです。ffsがファイルへの最近の更新の一部を認識できないことがありますが、これはカーネルが最近の更新をキャッシュに保持し、ディスクへの書き込みを延期している場合に発生します。次のようにして同期を強制できます。

sync

Btrfs

./fs/btrfs.c

Bツリーファイルシステムははるかに複雑で、より効率的なファイルストレージですが、追加の制限があります：

ファイルシステム上のいずれかのファイルが更新されると、スーパーブロック全体も更新する必要があります。つまり、ffsがスーパーブロック（高レベルのBツリー）を読み取った後にカーネルがツリーを更新すると、読み取り全体が無効になります。

これは fsfreeze を使用するか、別のデタッチされたボリュームを作成することで回避できます。

Apfs (MacOS)

./fs/apfs.c

APFSはAppleが実装したプロプライエタリなファイルシステムで、リバースエンジニアリングされており、ここでもサポートされていますが、Appleはセキュリティポリシーを大幅に強化しています。

SIPを無効にしない限り、メインディスク上でffsを実行することはできません

SIP - システム整合性保護は、rootユーザーであってもメインディスクのスーパーブロックへのアクセスを禁止する特別なセキュリティ機能です。sudoを使用してもバイパスできません。この機能を無効にする必要があります（yabaiのようなプロジェクトを使用している場合は、すでに無効になっているかもしれません）。

メインディスクに触れずにAppleファイルシステム上でffsをテストする方法があります - 生の.dmgファイルを昇格権限なしで検索できます（そうです、アプリインストーラは単なるデタッチされたボリュームです）。ffsでは何もマウントする必要はなく、ファイルシステムタイプとともにボリュームの生バイトへのパスを渡すだけです：

ffs "<QUERY>" /path/to/volume.dmg apfs

デタッチされたボリュームの検索

ffsはバイトを直接読み取るため、デタッチされたボリュームをファイルシステムにマウントせずに検索できます。例: .iso や .dmg ファイルの読み取り。

速度

これが最も面白い部分です - ffsはVFS / カーネルファイルシステムキャッシュにアクセスできません。そのため、小さい（またはキャッシュ済みの）ディレクトリでは遅くなりますが、キャッシュが尽きてカーネルが実際のディスク状態を読み取りに行くと、次第に速くなります。

なぜか？ある時点でカーネルVFSがオーバーヘッドになるという点を証明するためです。

これはbtrfsマウントドライブ上でffsとripgrepを比較した検索結果です。ripgrepははるかに高度なSIMDベースのマッチャーとファイルウォーカーを使用していますが、ffsはわずか約1.8k行のCコードです。

[repos — 631k files]
  ffs |####                                              | 5.505s
  rg  |###                                               | 4.813s

[dev — 1.50M files]
  ffs |############                                      | 18.413s
  rg  |#################                                 | 25.673s

[home — 3.25M files]
  ffs |########################                          | 36.205s
  rg  |##################################################| 74.690s

ripgrepに使用されたフラグは -F --no-heading -H -n --no-ignore --hidden --one-file-system --no-messages です。これにより、ffsと同じ結果が出力されます。

プロジェクトのビルド

プロジェクトをコンパイルするために必要なのは、btrfs用のlibzstdとpkg-config内のopenmpだけです。あとは以下のとおりです。

make ffs
ffs --help

ffs

人気