Le problème à résoudre

Vous est-il déjà arrivé de réaliser que votre disque dur (ou celui d’un de vos proches) était un vaste bazar, avec des fichiers/dossiers en double à la pelle (mais pas forcément totalement identiques), par exemples issus de backups passés (sans outil de backup permettant de faire les choses proprement et incrémentalement, ou backupés de manière fragmentée sur différents supports à la va-vite suite aux signes avant-coureurs de panne imminente de votre disque, puis regroupés, puis re-fragmentés, etc) ? Puis peut-être vous-êtes vous décidé un jour à tout ranger, mais avez abandonné ou procrastiné devant l’ampleur de la tâche et le volume de données (“ça sent le vécu” vous direz-vous: effectivement je n’ai pendant longtemps jamais géré de manière très organisée mes données et leurs backups (du moins, pas avec la rigueur que j’appliquais en entreprise) et entre backups d’urgence pré-crash et procrastination c’est comme ça qu’on se retrouve au bout de 10 ans avec 6 To à trier, répartis sur plusieurs disques et quelques CD-R ! J’ai aussi observé chez plusieurs proches que je n’étais clairement pas seul, et rares sont les personnes qui utilisent un outil adapté pour backuper leur machine ou leur smartphone de manière méthodique et incrémentale).

Il y a quelques années, j’ai décidé d’y mettre de l’ordre et trier le tout et d’avoir enfin une vraie politique de backups de mes machines… J’aurais sûrement pu me dire qu’une grande partie de ces vieilles données n’avait probablement plus tellement d’importance vu que je n’y avais pas accédé depuis de nombreuses années (plus de 10 ans pour les CDs…), mais je suis conservateur :). J’ai donc commencé par commander trois disques durs suffisamment gros pour que la totalité des données tienne sur un seul disque (l’idée étant de faire un rsync hebdomadaire sur le second disque, et un rsync tous les 3-6 mois sur le 3ème disque qui serait en temps normal stocké ailleurs pour se prémunir de risques tels que cambriolage/incendie/…). Mais une fois la totalité des données regroupées sur un même support, comment s’y prendre pour nettoyer les doublons sur une telle quantité ? La masse de fichiers en double/triple était énorme, parfois avec de petites variations entre les sous-dossiers. Parfois, la totalité des fichiers de certains dossiers était en double à un autre endroit, mais avec une autre structure de dossiers. Parfois, il y avait une quantité considérable de petits fichiers (e.g. résidus de compilation de firmares). Bref un simple rangement “manuel” était malcommode compte tenu de la masse de données, et j’ai bien sûr regardé quels outils pouvaient m’aider, cependant

• les outils de backup font ce pour quoi ils sont conçus: sauvegarder (éventuellement en détectant et exploitant les blocs/secteurs de disque identiques), mais n’aident pas à remettre de l’ordre dans une arborescence en désordre.
• il existe de nombreux outils de détection/suppresion de doublons : par exemple fslint/findup, fclones, ddh, fdupes, gdupes, etc. Certains peuvent par exemple remplacer les doublons par des hard links, d’autres listent les fichiers en double sans changer le filesystem. Même si ma priorité était de classer les données et non de “seulement” gagner de la place, la première approche pouvait se justifier malgré tout (e.g. faire une passe avec fdupes, puis faire une analyse postérieure sur les fichiers qui pointaient vers le même inode). Mais je n’étais pas très à l’aise avec un outil qui modifiait automatiquement filesystem sans nuances (par exemple, dans certains cas je peux souhaiter garder des doublons, ou permettre à deux arborescences partiellement identiques de diverger ensuite ce qui aurait été rendu impossible si les doublons pointaient vers le même inode. De plus l’approche “hard-links” n’est pas portable en dehors d’un système UNIX et je souhaitais un outil qui puisse aussi aider des proches sous d’autres systèmes). Bref, je préfèrais un outil qui se contente de me lister les doublons tout en me laissant le contrôle sur ce que j’en faisais ensuite. Cependant il me manquait toujours quelque chose dans les outils existants : par exemple au moment où j’ai fait mes recherches je n’ai trouvé aucun outil libre capable de lister les dossiers en double sans lister toute la sous-arborescence.

Naissance d’un outil

C’est ainsi qu’est né un premier projet appelé Duplicide (désormais obsolète), dont le but était de lister les dossiers en double sans renvoyer toutes les sous-arborescences. Plus récemment à la faveur des confinements, j’ai entièrement réécrit le soft avec une approche différente, et cela a donné kindfs. Il permet entre autres les choses suivantes

• scanner une arborescence pour l’indexer dans une base de données sqlite3 (d’où “kindfs” pour “indexeur de fs de Karteum” :). Par rapport aux purs outils de détection de doublons évoqués plus haut, il est un peu plus lent car il scanne tout (e.g. il calcule un hash sur l’ensemble des fichiers et non uniquement sur les candidats de taille identique), mais cela permet d’en faire un outil plus large que la simple détection de doublons et de faire des analyses postérieures sans tout re-scanner à chaque fois
• lister (par ordre de taille décroissante) les plus gros dossiers/fichiers en double (N.B. d’ailleurs à partir de ce résultat et en remontant d’un ou deux cran dans l’arborescence, on s’aperçoit souvent que dossier_parent1 et dossier_parent2 sont similaires mais pas identiques, d’où l’item suivant)
• lister les fichiers d’un dossier A qui sont absent d’une sous-arborescence B (indépendamment de la structure de sous-dossiers) : cela permet notamment de progressivement ranger les données dans une arborescence clean/ et de vérifier qu’on n’a rien oublié avant d’effacer les dossiers doublons/superflus
• monter la BD d’index comme système de fichier FUSE afin de pouvoir utiliser des outils comme du, find ou qdirstat (avec un calcul beaucoup plus rapide que sur les données d’origine. J’utilise parfois diff -r également pour avoir un résultat rapide, en gardant en tête les limitations ci-dessous sur la fiabilité du hash)

Comment ça marche (sous le capot) ?

Pour les non-geeks qui liraient ce billet : un “hash” est une sorte de “signature” de taille fixe que l’on calcule sur la base des données d’entrées (un peu comme une somme de contrôle). Il existe plein d’algorithmes pour ça, que je distinguerai essentiellement en deux catégories : ceux “optimisés pour la vitesse” (CRC, xxhash, etc.) et ceux de “qualité cryptographique” (MD5, SHA-1, etc.). Sauf exception rare, deux fichiers différents auront une signature différente. Cependant comme on part d’un ensemble de données arbitrairement large pour en calculer une petite signature de taille fixe (e.g. entre 32 et 512 bits suivant l’algorithme), il est évident qu’il peut exister des “collisions” i.e. deux fichiers différents peuvent avoir la même signature avec le même algorithme de hash. Un algo de qualité cryptographique a pour but de rendre ces “collisions” difficiles à forger délibérément (e.g. pour éviter qu’un attaquant vienne falsifier des données de manière indétectable par le hash) alors qu’un algorithme prévu pour la vitesse ne s’embarrasse pas avec ces considérations et se satisfera si le risque de collision est “improbable” (sur un hash de 64 bits, le risque est très faible). Dans mon cas je n’ai pas besoin de qualité cryptographique et je souhaite que le scan soit rapide : j’ai ainsi choisi l’algo XXH2/64 car au moment où j’ai commencé à écrire le soft c’était l’algo le plus rapide que je connaissais et il était très facile d’emploi depuis Python (XXH3 est apparu depuis, mais 1°/ je souhaite garder XXH2/64 bits car je souhaite garder une compatibilité avec mes anciennes signatures pour comparer les index dans le temps, 2°/ je n’ai pas besoin de la vitesse de XXH3 car de toute façon avec XXH2 c’est déjà la vitesse de lecture des données sur le disque qui est limitante loin devant le temps de calcul du hash). J’ai récemment découvert BLAKE3 qui se prétend à la fois rapide et supposément de qualité cryptographique, mais je n’ai pas essayé à ce stade et j’ignore si sa vitesse est comparable à XXH2.

Le principe est simple : deux fichiers/dossiers seront considérés comme “vraisemblablement identiques” s’ils ont la même taille et le même hash (je ne me base pas sur le nom de fichier car à travers les âges les backups peuvent avoir connu différents encodages, e.g. iso8859-1, big5 (e.g. anciens fichiers récupérés chez des amis chinois), puis utf8, Il peut aussi y avoir de vieux backups avec les noms MS-DOS courts xxxx~1, etc. On peut donc se retrouver avec des fichiers identiques mais aux noms de fichiers différents). Avoir des noms identiques ou proches me permet en revanche de conforter les résultats lors d’une vérification lorsque l’outil renvoie des candidat “vraisemblablement identiques”.

Détail très important : afin d’accélérer le scan, je ne calcule un hash que sur des portions de fichiers sur les fichiers de plus de 3 Mo (les 1 Mo du début, du milieu et de la fin du fichier, même si cela est configurable). Cela fait évidemment courir un risque accru que deux fichier différents aient malgré tout le même hash (s’ils sont identiques sur les 3 Mo du début/milieu/fin et différents ailleurs), et c’est pourquoi je mets en garde tout utilisateur : toujours savoir ce que l’on fait, vérifier les résultats derrière et ne pas effacer “aveuglément” les candidats doublons qu’il renvoie ! Dans la pratique, ce pseudo-hash s’est avéré amplement suffisant et sûr pour l’usage que j’en fais (les fichiers doivent de toute façon avoir la même taille, et je vérifie derrière avec la similarité sur les noms de fichiers, la date, et en cas de doute je fais un md5sum ou diff -r ciblé pour être sûr. En revanche, il existe certain types de fichiers pour lesquels ce hash partiel est risqué : je pense notamment aux images de VM, qui peuvent très fréquemment présenter des sections identiques au début/milieu/fin de fichier tout en étant différents ailleurs). N.B. Cette approche est également utilisée par imohash.

Une fois les hash sur les fichiers calculés, je calcule également un pseudo-hash sur les dossiers : je prends pour cela la liste des hash des fichiers/sous-dossiers qu’il contient et je recalcule un hash sur la concaténation (triée) de ces éléments. Comme le scan du filesystem se fait de manière récursive, cela revient à faire un parcours “bottom-up” donc je sais que les fichiers/sous-dossiers sont traités (et leur hash calculés) avant de traiter le dossier courant.

Et comment on s’en sert ?

Il faut avoir préalablement installé les packages Python suivants : pip install xxhash numpy fusepy python-magic

Ensuite la CLI s’utilise ainsi : kindfs <dbfile> <command> [args]

• kindfs <dbfile> scan <path> [-R] [-z] : crée le fichier sqlite dbfile et scanne le système de fichiers derrière path/. Pour des raisons de performances, il est conseillé de loger la base de données sur un SSD ou en RAM. Bien sûr, le process kindfs a les mêmes droits d’accès que l’utilisateur qui l’a lancé (ce qui peut entraîner un scan incomplet pour les parties de l’arborescence sur lesquelles il manquerait les droits d’accès). L’option -R effectue un reset de la base de données (si elle existait déjà. Le comportement par défaut étant une reprise sur erreur). L’option -C num permet de spécifier que le hash soit calculé sur des blocs de num ko en début/milieu/fin du fichier (par défaut il s’agit de 1 MB. Plus la taille de bloc est faible et plus le scan est rapide mais moins le hash est fiable). Si num vaut 0, le hash est calculé sur la totalité du fichier ce qui rend le scan beaucoup plus lent (en particulier s’il existe beaucoup de très gros fichiers) mais fiabilise la recherche ultérieure de doublons
• kindfs <dbfile> showdups [-l num] [-m <mountpoint>] [-k] : montre tous les fichiers/dossiers en double et le nombre d’occurences, par ordre de taille descendante. Si -n est spécifié, les résultats sont triés par ordre décroissant de nombre de sous-fichiers (pour les dossiers) plutôt que par taille (ce qui permet d’éliminer très rapidement un grand nombre de petits fichiers en double dans certaines situations). Si -l num est spécifié, seules les num premiers résultats sont renvoyés. Ajouter -m <mountpoint> permet de faire une vérification supplémentaire sur le filesystem (afin d’afficher dans une couleur différente les entrées qui ont été supprimées depuis le dernier scan).
• kindfs <dbfile> isincluded <dir1> <dir2> [-m <mountpoint>] [-i] [-n] [-g <glob_ignore_file>] : vérifie quels fichiers de dir1 sont presents dans dir2 (indépendamment de la structure de la sous-arborescence de dir1/dir2). -i renvoie les fichiers de dir1 qui sont inclus dans dir2, et -n (mutuellement exclusive avec -i) renvoie les fichiers de dir1 qui ne sont pas inclus dans dir2. Ajouter -m <mountpoint> a la même fonction que pour l’option précédente. Si -g glob_ignore_file est spécifié, le fichier glob_ignore_file passé en paramètre permet de décrire une liste d’entrées à ignorer/filtrer dans les résultats de sortie, de manière analogue à kindfs ... | grep -v -f <regexfile> (mais plus rapide et avec support des métacaractères * et ? à la place des regex).
• kindfs <dbfile> diff <dir1> <dir2> : equivalent à kindfs <dbfile> isincluded <dir1> <dir2> -n + kindfs <dbfile> isincluded <dir2> <dir1> -n i.e. affiche tous les fichiers présent d’un côté et absents de l’autre (indépendamment de la structure de dossiers)
• kindfs <dbfile1> comparedb <dbfile2> : affiche toutes les entrées de dbfile1 absentes de dbfile2 (i.e. compare deux versions de DB, à nouveau indépendamment de la structure de dossiers). Commode pour s’assurer qu’une réorganisation de ses données n’entraine pas de suppression intempestive de fichiers qui ne seraient pas en doubles…).
• kindfs <dbfile> dump <dir> : effectue un dump d’un dossier indexé, incluant les hash et la taille des entrées
• kindfs <dbfile> mount <mountpoint> : monte la DB sous forme de système de fichiers FUSE (read-only pour l’instant). Cela permet en particulier d’utiliser des outils tels que diff -r et find.
  • Notez que st_size correspond à la taille du contenu fictif généré par FUSE (dans lequel where les fichiers sont en réalité tous des fichiers texte contenant le hash+taille des données réelles, ce qui permet à des outils comme mc ou vim de fonctionner correctement), ce qui est différent de la taille renvoyée par st_blocks (qui est mappée sur la taille réelle du fichier correspondant dans la DB, ce qui permet à des outils comme du de fonctionner correctement)..
  • L’existence de st_blocks en plus de st_size m’a au passage fait découvrir que dans le cas de systèmes de fichiers tels que ext4, deux fichiers identiques sur le plan du contenu/taille/nom de fichier peuvent renvoyer des tailles différentes avec du -s (mais néanmoins toujours identiques avec du -sb) en fonction de leur fragmentation. Une autre amnière de l’observer est de taper find -type f -printf "%8b %10s\t%p\n" et observer le nombre de blocs variables pour des fichiers de taille identiques).
• kindfs <dbfile> inodes [-l num] [-m <mountpoint>] : identique à showdups mais renvoie uniquement les entrées avec des inodes identiques (i.e. qui ne consomment pas de place supplémentaire, néanmoins cette information peut être utile pour réorganiser ses données e.g. après avoir utilisé un outil comme rdfind qui remplace les doublons par des hard links. De plus, il peut être souhaitable de trier ses données pour éviter la profusion de hard links afin d’éviter de d’altérer ses données par erreur en pensant travailler sur une copie…)
• kindfs <filename> computehash : calcule et renvoie le hash d’un fichier avec le même algorithme que celui utilisé lors du scan du filesystem (pratique pour certaines vérifications)
• kindfs <filename> check_zerofile : vérifie si un fichier est uniquement constitué de zéros (pratique pour certaines vérifications)