FFS - F* 파일 시스템

이것은 파일을 검색하기 위한 CLI 도구로(grep처럼), OS 커널을 사용해 파일을 읽지 않고 디스크를 직접 읽습니다. 실질적으로는 쓸모없지만 미친 듯이 멋집니다.

이것은 단지 약 1.5k줄의 C 코드로 구성되어 있으며:

raw 디바이스 노드(예: /dev/rdisk*)를 읽을 때만 sudo가 필요합니다. 이미지 파일을 검색할 때는 높은 권한이 필요 없습니다.
macOS 기본 디스크에서 실행하려면 SIP 보호를 비활성화해야 합니다.
최근에 쓴 일부 파일을 놓칠 수 있습니다(수동으로 sync 호출이 필요할 수 있음).
OS의 다른 시스템 구성 요소가 파일을 쓰는 동안 변동이 심한 파일 시스템에서 트리를 검색하지 못할 수 있습니다.
이 프로젝트에서 수동으로 구현된 파일 시스템에서만 작동합니다.

하지만 동시에

디스크에서 블록을 직접 읽습니다.
VFS/버퍼링된 read() 경로를 우회하고, 대신 블록 디바이스를 직접 pread합니다.
ripgrep보다 점점 더 빨라집니다(검색해야 할 파일이 많을수록 ripgrep보다 더 빠릅니다).
마운트되지 않은 볼륨도 검색할 수 있습니다. 바이너리 blob을 그냥 파싱하기 때문입니다.
바이너리 파일을 감지하고 건너뜁니다.
openmp를 통해 모든 코어에 부하를 분산합니다.

실제로 작동하는 빠른 파일 검색을 원한다면 제 프로젝트 fff를 확인해 보세요. sudo 없이도 ripgrep을 크게 능가합니다.

지원되는 파일 시스템

리눅스에서는 대부분의 파일 시스템을 쉽게 구현할 수 있습니다.

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(시스템 무결성 보호)는 루트 사용자라도 기본 디스크 슈퍼블록에 대한 모든 접근을 금지하는 특별한 보안 기능입니다. 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

인기