FFS - F* File System

Это cli-инструмент для поиска файлов (как grep), который не использует ядро ОС для чтения файлов, а читает ваши диски напрямую. Он практически бесполезен, но безумно крутой.

это всего лишь ~1.5 тысяч строк кода на C, который:

• требует sudo только при чтении сырого узла устройства (например, /dev/rdisk*); поиск в образе файла не требует повышенных привилегий
• требует отключения защиты SIP для запуска на основном диске macOS
• может пропустить некоторые недавние записи файлов (потребуется ручной вызов sync)
• может не иметь возможности искать деревья в сильно изменчивой файловой системе, пока другие компоненты системы записывают файлы в ОС
• работает только для файловых систем, реализованных вручную в этом проекте

но в то же время

• напрямую читает блоки с ваших дисков
• обходит путь VFS/буферизированного read(), вместо этого он напрямую pread блочное устройство
• прогрессивно быстрее ripgrep (чем больше файлов нужно найти — тем он быстрее ripgrep)
• может искать в не смонтированных томах — он просто разбирает бинарные blobs
• обнаруживает и пропускает бинарные файлы
• распределяет нагрузку по всем ядрам через openmp

Для реально работающего быстрого поиска файлов загляните в мой проект fff — он значительно превосходит ripgrep без необходимости в sudo.

Поддерживаемые файловые системы

на linux в основном любую файловую систему легко реализовать

Ext4

./fs/ext4.c

Это самая простая файловая система для поддержки: это журналируемая файловая система, которая записывает на месте (без копирования при записи), так что в большинстве случаев это лучшая файловая система для ffs. Иногда вы можете заметить, что ffs не видит некоторые недавние обновления файлов, это может произойти, если ядро хранит последние обновления в кеше и откладывает запись на диск. Вы можете принудительно выполнить синхронизацию с помощью

sync

Btrfs

./fs/btrfs.c

Файловая система B-tree значительно сложнее, является более эффективным хранилищем файлов и имеет дополнительное ограничение:

Когда любой файл в вашей файловой системе обновляется, весь суперблок также требует обновления, что означает, что если ffs читает суперблок (высокоуровневое b-дерево), а после этого ядро обновляет дерево — всё чтение становится недействительным.

Это можно обойти с помощью fsfreeze или создав отдельный отключенный том

Apfs (MacOS)

./fs/apfs.c

APFS — это проприетарная файловая система, реализованная Apple, которая была реверсирована и также поддерживается здесь, но Apple значительно ужесточила свои политики безопасности.

Вы не сможете запустить ffs на вашем основном диске без отключения SIP

SIP — защита целостности системы, это особая функция безопасности, которая запрещает любой доступ к суперблоку основного диска даже пользователю root. Вы не можете обойти её даже с sudo; вам нужно отключить эту функцию (возможно, она уже отключена, если вы используете проекты типа yabai).

Существует способ протестировать ffs на файловой системе Apple, не затрагивая основной диск — вы можете искать в сырых файлах .dmg без каких-либо повышенных привилегий (да, установщики приложений — это просто отключенные тома). С помощью ffs вам не нужно ничего монтировать, вы можете просто указать путь к сырым байтам тома вместе с типом файловой системы:

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

Поиск в отключенных томах

Поскольку ffs читает байты напрямую, вы можете использовать его для поиска в любых отключенных томах без их монтирования в файловую систему. Например, чтение файлов .iso или .dmg.

Скорость

Это самая забавная часть — у ffs нет доступа к кешу VFS/файловой системы ядра. Вот почему он будет медленнее на маленьких (или уже закэшированных) каталогах, но прогрессивно быстрее, когда кеш исчерпан и вашему ядру приходится читать реальное состояние диска.

Зачем? Именно чтобы доказать, что в какой-то момент VFS ядра становится накладными расходами.

Это результаты поиска, сравнивающие ffs и ripgrep на смонтированном диске btrfs. Обратите внимание, что ripgrep использует гораздо более продвинутый сопоставитель на основе SIMD и обходчик файлов, в то время как ffs — это всего лишь ~1.8 тысяч строк кода на 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.

Сборка проекта

Всё, что вам нужно для компиляции проекта — это libzstd для btrfs, openmp в вашем pkg-config, затем просто

make ffs
ffs --help