FFS - F* File System

Questo è uno strumento CLI per cercare file (come grep) che non usa il kernel del sistema operativo per leggere i file, ma legge direttamente i tuoi dischi. È praticamente inutile, ma incredibilmente figo.

sono solo circa 1.5k righe di codice C che:

• richiede sudo solo quando si legge un nodo dispositivo raw (es. /dev/rdisk*); la ricerca in un file immagine non richiede permessi elevati
• richiede la disattivazione della protezione SIP per girare sul disco principale di macOS
• può perdere alcune scritture recenti di file (richiederà una chiamata manuale a sync)
• potrebbe non riuscire a cercare alberi su un file system altamente volatile mentre altri componenti di sistema scrivono file nel sistema operativo
• funziona solo per file system implementati manualmente in questo progetto

ma allo stesso tempo

• legge direttamente i blocchi dai tuoi dischi
• bypassa il percorso VFS / read() bufferizzato, e invece fa pread direttamente sul dispositivo a blocchi
• progressivamente più veloce di ripgrep (più file devi cercare - più è veloce di ripgrep)
• può cercare volumi non montati - analizza semplicemente blob binari
• rileva e salta i file binari
• distribuisce il carico su tutti i core tramite openmp

Per la ricerca di file veloce realmente funzionante dai un'occhiata al mio progetto fff - supera significativamente ripgrep senza bisogno di sudo.

File system supportati

su linux quasi ogni file system è facile da implementare

Ext4

./fs/ext4.c

Questo è il file system più facile da supportare: è un file system journaling che scrive in place (niente copy-on-write), quindi la maggior parte delle volte è il miglior file system per ffs. A volte potresti notare che ffs non vede alcuni aggiornamenti recenti ai file; questo può accadere se il kernel tiene gli aggiornamenti recenti nella cache e rimanda le scritture su disco. Puoi forzare la sincronizzazione usando

sync

Btrfs

./fs/btrfs.c

Il file system B-tree è significativamente più complicato, è uno storage di file più efficiente e ha una limitazione aggiuntiva:

Quando un qualsiasi file sul tuo file system viene aggiornato, anche l'intero superblocco richiede un aggiornamento, il che significa che se ffs legge il superblocco (la b-tree di alto livello) e successivamente il kernel aggiorna l'albero - l'intera lettura diventa non valida.

Questo può essere bypassato usando fsfreeze o creando un volume separato non montato.

Apfs (MacOS)

./fs/apfs.c

APFS è un file system proprietario implementato da Apple che è stato sottoposto a reverse-engineering ed è supportato anche qui, ma Apple ha aumentato significativamente le sue politiche di sicurezza.

Non sarai in grado di eseguire ffs sul tuo disco principale senza disabilitare SIP

SIP - protezione dell'integrità di sistema è una speciale funzionalità di sicurezza che proibisce qualsiasi accesso al superblocco del disco principale anche come utente root. Non puoi bypassarla nemmeno con sudo; devi disabilitare questa funzionalità (potresti già averla disabilitata se usi progetti come yabai).

C'è un modo per testare ffs sul file system Apple senza toccare il disco principale - puoi cercare file .dmg raw senza alcun permesso elevato (sì, gli installer delle app sono solo volumi non montati). Con ffs non devi montare nulla, puoi semplicemente dargli un percorso ai byte raw di un volume insieme al tipo di file system:

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

Ricerca in volumi non montati

Poiché ffs legge direttamente i byte, puoi usarlo per cercare qualsiasi volume non montato senza montarli nel file system. Ad esempio leggendo file .iso o .dmg.

Velocità

Questa è la parte più divertente - ffs non ha accesso alla cache VFS / file system del kernel. Ecco perché sarà più lento su directory più piccole (o già in cache), ma progressivamente più veloce una volta che la cache è esaurita e il kernel deve andare a leggere lo stato effettivo del disco.

Perché? Esattamente per dimostrare che a un certo punto la VFS del kernel diventa un overhead.

Questo è il risultato di ricerca che confronta ffs con ripgrep su un'unità montata btrfs. Nota che ripgrep usa un matcher e un file walker basati su SIMD molto più avanzati, mentre ffs è solo ~1.8k righe di codice 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

I flag usati per ripgrep sono -F --no-heading -H -n --no-ignore --hidden --one-file-system --no-messages - il che lo porta a emettere gli stessi risultati di ffs.

Compilare il progetto

Tutto ciò che ti serve per compilare il progetto è libzstd per btrfs, openmp nel tuo pkg-config, poi semplicemente

make ffs
ffs --help