1. Le problème du charpentier
1.1 Contexte
Mon ami charpentier achète souvent du bois pour ses charpentes. Un jour, il lui manquait des renforts que l'on dispose en diagonale, comme indiqué sur la figure.
Fig. 1 : Schéma de pose d'un renfort
La pente est très variable suivant l'endroit où on doit poser un renfort : les dimensions x et y varient entre 0 et 10 cm, suivant les cas.
Ce jour-là, son fournisseur lui propose un lot de 40000 pièces en promo. Par contre, ces pièces font une longueur de 10 cm. C'est un peu court... En effet, comme on les pose en diagonale, il faut une longueur d'au moins racine_carrée(x^2+y^2). Si le renfort est plus long, on le coupe. S'il est trop court par contre, c'est un souci. Au final, pour savoir si cette offre vaut le coup, mon ami devait donc savoir combien de pièces allaient faire l'affaire directement, plutôt que d'encombrer son entrepôt.
En fait, pour qu'un renfort soit de longueur suffisante, on doit donc avoir :
longueur_renfort >= racine_carrée(x^2+y^2)
Pour simplifier les calculs, on peut compter en unités de 10 cm. Cela donne :
longueur_renfort = 1
0 <= x <= 1
0 <= y <= 1
Et on simplifie donc la formule en :
racine_carrée(x^2+y^2) <= 1
Quand je suis arrivé chez lui, mon ami venait de terminer l'implémentation de sa solution. Et j'ai été plutôt surpris de constater que ce qu'il avait implémenté, c'était un système de fichiers !
1.2 Premier contact avec charpentefs
Ce filesystem est basé sur FUSE et plus précisément sur le binding fuse-python. Il est donc implémenté en espace utilisateur, via un fichier Python, charpentefs.py. On le monte de la façon suivante :
$ mkdir /tmp/mountpoint
$ ./charpentefs.py /tmp/mountpoint
La commande mount permet de s'assurer que le montage est bien effectif :
$ mount | grep charpente
charpentefs.py on /tmp/mountpoint type fuse.charpentefs.py ([...options...])
$
On découvre alors que ce filesystem expose 3 fichiers « virtuels ». Deux d'entre eux, stock et pieces_ok, ne sont accessibles qu'en lecture et le troisième, pose_renfort, n'est accessible qu'en écriture :
$ ls -l /tmp/mountpoint/
total 8
-r-------- 1 etienne etienne 10 oct. 26 20:32 pieces_ok
--w------- 1 etienne etienne 0 oct. 26 20:32 pose_renfort
-r-------- 1 etienne etienne 10 oct. 26 20:32 stock
$
Et voici comment on les manipule :
$ cd /tmp/mountpoint/
$ cat stock
40000
$ cat pieces_ok
0
$ echo "0.5 0.5" > pose_renfort
$ cat stock
39999
$ cat pieces_ok
1
$ echo "0.9 0.9" > pose_renfort
$ cat stock
39998
$ cat pieces_ok
1
$
On simule donc l'utilisation d'une pièce en écrivant '<x> <y>' dans le fichier pose_renfort. À chaque fois, stock est décrémenté. En revanche, pieces_ok est incrémenté uniquement si la pièce de 10 cm est assez grande pour les valeurs x et y données.
Pour démonter le filesystem, on pourra utiliser sudo umount <mount_point> ou fusermount -u <mount_point>.
J'ai trouvé ça assez facile à utiliser, mais je lui ai quand même demandé pourquoi il était parti sur une implémentation de système de fichiers. Si j'ai bonne mémoire, ses explications tournaient autour des arguments suivants :
- Quand on implémente une fonctionnalité sous la forme d'un système de fichiers, alors n'importe quel programme pourra en profiter. En effet, lire et écrire dans des fichiers, c'est le B.A.-BA de n'importe quel langage de programmation. A partir de ce constat, tout est possible ; on peut par exemple interroger des services web avec un script bash... Et ce genre d'idée plaisait visiblement beaucoup à mon ami.
- Et par ailleurs, d'après lui, l'implémentation d'un filesystem n'est pas quelque chose de compliqué.
J'ai trouvé le premier argument assez convaincant. Effectivement, une fois la solution implémentée sous la forme d'un système de fichiers, on bénéficie d'une compatibilité inégalée avec tous les langages existants... (Et même, pour quelques décennies au moins, tous les langages futurs !) Par contre, pour vérifier son 2ème argument, je lui ai demandé de me montrer son code...
1.3 Le code de charpentefs
Voici en gros les explications qu'il m'a données sur son code1.
1.3.1 Généralités : FUSE et code métier
Ce filesystem est principalement basé sur un composant appelé FUSE (Filesystem in USErspace). Si vous avez lu le 1er article de cette série, vous savez que FUSE permet d'implémenter un système de fichiers en espace utilisateur. Cela permet principalement de rendre plus accessible une telle implémentation, par rapport à une implémentation directe dans le noyau Linux...
FUSE est utilisable avec un certain nombre de langages de programmation. Comme on l'a vu, mon ami a choisi d'utiliser le « binding » Python, que l'on trouve dans toute distribution digne de ce nom (apt-get install python-fuse pour une Debian).
Son filesystem est donc implémenté dans le fichier Python charpentefs.py.
Ce fichier débute par des imports assez classiques, puis par la déclaration de quelques constantes :
FILES = [ "pose_renfort", "stock", "pieces_ok" ]
STOCK_INIT = 40000
READ_SIZE = 10
READ_STRING_FORMAT = '%' + str(READ_SIZE) + 's'
Les 2 premières se passent d'explications. Les 2 dernières permettront de simplifier l'implémentation, en fixant la taille des fichiers en lecture (/stock et /pieces_ok) à une valeur constante. En effet, ce qu'on doit lire dans ces fichiers est un entier compris entre 0 et 40000, donc comportant entre 1 et 5 chiffres. Mettre à jour la taille de ces fichiers en fonction de l'entier qu'ils contiennent est une complication dont on peut se passer : on formatera ces entiers avec des espaces de « padding » de façon à avoir toujours la même longueur.
Ensuite, on trouve une classe StockEngine très simple qui implémente la partie « métier » de l'algorithme.
class StockEngine(object):
def __init__(self):
self.stock = STOCK_INIT
self.pieces_ok = 0
def pose_renfort(self, x, y):
if self.stock == 0:
return False
self.stock -= 1
if math.sqrt(x*x+y*y) <= 1:
self.pieces_ok += 1
return True
On a donc juste une initialisation dans le constructeur et une méthode pose_renfort(). Si l'opération de pose du renfort est valide (stock > 0), cette méthode décrémente le compteur self.stock, incrémente self.pieces_ok uniquement si la pièce convient (en fonction des paramètres x et y) et renvoie True. Si l'opération est invalide (stock déjà à 0) elle renvoie False.
Ensuite, l'implémentation de la classe de gestion du filesystem, CharpenteFS, est décrite. Voici comment elle débute :
class CharpenteFS(Fuse):
def __init__(self, *args, **kw):
"""Constructor."""
Fuse.__init__(self, *args, **kw)
self.initSampleStatStructures()
self.stock_engine = StockEngine()
Cette classe dérive de fuse.Fuse, comme pour toute implémentation utilisant python-fuse. Le constructeur crée une instance de la classe StockEngine et appelle la méthode initSampleStatStructures(), que nous allons décrire juste après.
1.3.2 Requête getattr()
La première requête à laquelle doit savoir répondre un système de fichiers est la requête getattr(). En effet, cette requête est utilisée pour deux choses très importantes :
- tester l'existence d'un fichier,
- récupérer les attributs de ce fichier.
Les attributs renseignent par exemple sur le propriétaire du fichier, son type (répertoire, lien symbolique, fichier régulier, etc.), les autorisations associées, les dates de dernier accès et de dernière modification.
Le résultat de cette requête getattr() (les attributs du fichier donc) est empaqueté. En C, il s'agit ainsi d'une structure struct stat. Dans notre cas, Python utilise un objet qui dépend du système d'exploitation (posix.stat_result dans mon cas), car la liste des attributs renvoyés varie légèrement en fonction du système d'exploitation.
La fonction lstat (voir man lstat) de la libc (ou os.lstat en Python) permet de déclencher ce genre de requête sur un système de fichiers. Un exemple évident d'utilisation de cette requête getattr() est la commande ls -l.
Cette requête getattr() est considérée comme la plus importante, car elle a de nombreuses implications. Par exemple, si on veux créer un répertoire dans l'arborescence de notre filesystem, une requête getattr() sera déclenchée pour tester s'il n'existe pas déjà un fichier (ou répertoire) portant ce nom et renvoyer une erreur le cas échéant. Une autre implication importante concerne les permissions de fichiers renvoyées par getattr(), qui doivent correspondre aux modes d'ouverture de fichier que l'on autorise ou pas.
Charpentefs étant un système de fichiers très simple, on a uniquement trois cas à gérer ;
- requête getattr() sur un fichier en lecture seule (/stock ou /pieces_ok),
- requête getattr() sur un fichier en écriture (/pose_renfort),
- requête getattr() sur un répertoire (répertoire racine du filesystem).
De ce fait, il est rentable de préparer ces trois cas à l'avance. C'est le rôle de la méthode initSampleStatStructures() appelée dans le constructeur et décrite ci-après :
def initSampleStatStructures(self):
self.sample_dir_stat = filestat.generateSampleDirStat()
self.sample_wr_only_stat = filestat.generateSampleFileStat(
stat.S_IWUSR, # write-only
0
)
self.sample_rd_only_stat = filestat.generateSampleFileStat(
stat.S_IRUSR, # read-only
READ_SIZE
)
On voit que c'est le module filestat qui fait à peu près tout le travail. Ce module a été implémenté par un autre ami, qui est D.J., et mon ami charpentier l'a réutilisé.
La méthode filestat.generateSampleFileStat() prend 2 arguments, le 1er correspondant au mode et le 2ème à la taille de fichier. On utilise donc ici notre constante READ_SIZE correspondant à la taille (fixe, voir plus haut) des fichiers en lecture.
Le code de gestion de la requête getattr() découle assez clairement de ces préparatifs :
def getattr(self, path):
if path == '/':
return self.sample_dir_stat
if path.lstrip('/') not in FILES:
return -ENOENT # no such file or dir
if path == '/pose_renfort':
return self.sample_wr_only_stat
else: # the 2 other files are read-only
return self.sample_rd_only_stat
Dans le code d'un filesystem, les chemins sont indiqués relativement au point de montage. Par exemple, si une requête getattr() est déclenchée sur un fichier /chemin/du/point_de_montage/repertoire/fichier, alors notre méthode getattr() sera appelée avec le paramètre path = /repertoire/fichier. Et une requête sur le point de montage sera reçue avec path = /.
Par ailleurs, la gestion des erreurs dans FUSE est un peu particulière : on doit retourner -1*<numero_d_erreur>. Par exemple, ici on retourne -ENOENT (« no such file or directory » voir le module python errno2) en cas de requête sur un fichier inexistant. Cette particularité n'est d'ailleurs pas spécifique au binding Python.
Pour le reste, on retourne bien évidemment, en fonction du fichier ou répertoire ciblé par la requête, un des 3 « paquets d'attributs » préparés dans la méthode initSampleStatStructures() décrite plus haut.
1.3.3 Requête readdir()
Une autre requête à gérer est la requête readdir(), qui permet de lister les entrées d'un répertoire.
def readdir(self, path, offset):
for e in FILES:
yield fuse.Direntry(e)
Je crois que celle-ci se passe quasiment de commentaires.
On pourra juste remarquer que l'argument offset n'est pas traité. Il s'agit d'une approximation, que l'on peut se permettre, dans la mesure où il est hautement improbable qu'on nous demande les 3 entrées de répertoire en plusieurs fois (si on en avait 300, ce serait autre chose).
L'argument path n'est pas non plus pris en compte parce qu'on a un seul répertoire (le répertoire racine) dans ce filesystem, donc c'est forcément de lui qu'il s'agit.
1.3.4 Requêtes d'ouverture et fermeture de fichier
Encore plus simple. Dans le cas de ce filesystem, on n'a rien besoin de faire au moment de l'ouverture ou de la fermeture d'un fichier. Donc :
def open(self, path, flags):
return 0
def release(self, path, flags):
return 0
1.3.5 Requête read()
Voilà qui est plus intéressant. Pour la gestion de la requête read() (il s'agit forcément d'un des 2 fichiers en lecture seule, pieces_ok ou stock), le code utilise une sous-méthode read_from_int(), qui permet de retourner une chaîne de caractères formatée à partir d'un entier, en l'occurrence self.stock_engine.pieces_ok ou self.stock_engine.stock suivant le cas :
def read(self, path, size, offset):
if path == '/pieces_ok':
return self.read_from_int(
self.stock_engine.pieces_ok, size, offset)
else: # /stock
return self.read_from_int(
self.stock_engine.stock, size, offset)
def read_from_int(self, int_value, size, offset):
s = READ_STRING_FORMAT % (str(int_value) + '\n')
if offset < len(s):
if (offset + size) > len(s):
size = len(s) - offset
return s[offset:(offset + size)]
else:
return ''
On utilise ici notre constante READ_STRING_FORMAT pour assurer le padding et obtenir une chaîne de longueur fixe. Cette chaîne de longueur fixe est vue comme le contenu du fichier lu. La méthode read_from_int() gère également le fait qu'on puisse lire une partie seulement de ce fichier (ou, du point de vue du filesystem, une partie de notre chaîne formatée), via les arguments size et offset.
En réalité, étant donné la petite taille de ce fichier (READ_SIZE = 10), on aurait presque pu simplifier la chose, un peu comme pour readdir(), et considérer offset toujours à zéro et size suffisamment grand... Mais cette fois-ci mon ami a semblé un peu plus courageux.
1.3.6 Requêtes d'écriture de fichier
Quand on écrit un fichier via, par exemple, une redirection de la sortie de commande cat, on fait en réalité 3 opérations :
- Si le fichier existe, on envoie une requête truncate() pour supprimer son contenu existant et passer sa taille à 0 ;
- On envoie la requête d'écriture : write() ;
- On envoie une requête pour mettre à jour la date de dernière modification du fichier : utime().
Ce filesystem doit donc savoir gérer ces trois requêtes :
def truncate(self, path, length):
return 0
def write(self, path, buf, offset):
return self.pose_renfort_input(buf)
def utime(self, path, times):
return 0
Dans notre cas, on sait de quel fichier il s'agit, pose_renfort, car c'est le seul qui autorise une écriture. Par ailleurs, on n'a pas besoin de traiter les requêtes truncate() et utime() dans ce cas de filesystem.
La requête write() fait appel à une méthode pose_renfort_input() et, là aussi, l'offset est ignoré par simplification.
def pose_renfort_input(self, buf):
try:
t = tuple(float(f) for f in buf.split())
except:
return -EINVAL
if len(t) != 2:
return -EINVAL
for x_or_y in t:
if x_or_y > 1 or x_or_y < 0:
return -EINVAL
if self.stock_engine.pose_renfort(*t):
return len(buf) # ok
else:
return -EINVAL
Cette méthode pose_renfort_input() est assez triviale. Elle commence par vérifier la validité de ce qui est écrit : on attend une chaîne de la forme '<x> <y>' avec 0<=x<=1 et 0<=y<=1. En cas de chaîne invalide, on retourne -EINVAL (« Invalid argument »). Si la chaîne est valide, on appelle self.stock_engine.pose_renfort(x, y). Si cette méthode échoue (le stock était déjà à 0), cette méthode renvoie False, ce qu'on traduit à nouveau en -EINVAL. Sinon, tout est OK, donc on retourne len(buf) pour signifier à l'auteur de la requête d'écriture que tous les caractères ont été pris en compte.
1.3.7 Section « main »
Le module charpentefs.py se termine par une section « main » assez triviale.
if __name__ == '__main__':
usage = "CharpenteFS: le filesystem du charpentier.\n" + \
argv[0] + " <mount_point>"
if len(argv) < 2:
print usage
exit()
mount_point = argv[1]
server = CharpenteFS(usage=usage)
server.fuse_args.mountpoint = mount_point
server.fuse_args.add('debug')
server.multithreaded = False
server.fuse_args.setmod('foreground')
server.fuse_args.add('default_permissions')
server.main()
Elle débute par une vérification sommaire des arguments de la ligne de commandes, puis crée un objet de type CharpenteFS, lui attribue quelques paramètres et appelle sa méthode main(), ce qui a pour effet de créer le montage.
Apparemment, la gestion des paramètres dans FUSE n'est pas la chose la plus jolie qu'il m'ait été donné de voir. Et malheureusement, contrairement à ce qu'on aurait pu espérer, le framework python-fuse ne rectifie pas le tir.
Deux des paramètres utilisés ici sont orientés « debugging » :
- debug permet de générer des traces pour chaque requête traitée,
- foreground évite que ce programme de gestion du filesystem se détache de notre terminal.
Deux autres paramètres permettent de largement simplifier l'implémentation :
- multithreaded = False permet d'éviter de se soucier des éventuelles requêtes concurrentes et des problèmes de réentrance de code. En effet, souvent on lance plusieurs programmes sur un même filesystem...
- default_permissions (paramètre très mal nommé à mon avis !) demande au noyau Linux de vérifier les permissions avant d'appeler nos gestionnaires de requêtes. Ainsi, si on tente de lire pose_renfort (qui n'est accessible qu'en écriture), le noyau va, au préalable, déclencher une requête getattr() pour obtenir les autorisations associées à ce fichier et finalement renvoyer une erreur d'autorisation ; notre gestionnaire read() ne sera donc jamais appelé. Comme on peut le voir dans cet exemple, ce paramètre est très important. Si on ne l'indique pas, alors il faut vérifier au début de chaque gestionnaire (readdir, open, read, write...) que le fichier existe et que l'opération est autorisée. A l'inverse, plusieurs hypothèses que j'ai formulées plus haut découlent directement de l'utilisation de ce paramètre. Par exemple : « on sait de quel fichier il s'agit, pose_renfort, car c'est le seul qui autorise une écriture ». Sans ce paramètre, le code serait donc clairement plus long.
1.4 Le script test_charpente.sh
Comme le filesystem paraissait fonctionnel, il ne restait plus qu'à l'utiliser pour faire un test statistique et avoir une idée du nombre de pièces utilisables directement dans un stock de 40000 pièces.
J'ai proposé à mon ami d'écrire le script bash avec lui, parce que j'ai l'habitude. Voilà ce qu'on a écrit :
$ cat test_charpente.sh
#!/bin/bash
PRECISION=5
MOUNTPOINT=$1
generate_float()
{
echo -n "0."
for i in $(seq $PRECISION)
do
echo -n $(($RANDOM % 10))
done
echo
}
while [ $(cat $MOUNTPOINT/stock) -gt 0 ]
do
x=$(generate_float)
y=$(generate_float)
echo "$x $y" > $MOUNTPOINT/pose_renfort
done
$
En paramètre on attend le point de montage. C'est du code vite fait, on ne vérifie pas...
Ensuite, on a une fonction qui génère un nombre flottant du type 0.xxxxx (donc entre 0 et 1, avec 5 décimales), en utilisant la fonction RANDOM de bash.
Et enfin, on boucle jusqu'à ce que le stock soit vide, en générant des valeurs x et y aléatoires à chaque itération pour poser un renfort.
Voilà ce que ça donne à l'utilisation :
$ ./test_charpente.sh /tmp/mountpoint
[...2 minutes plus tard...]
$ cat /tmp/mountpoint/pieces_ok
31410
$
Bon, ça fait donc 31410 pièces OK sur les 40000 du lot, un peu plus des trois quarts...
Tiens, c'est marrant, on dirait presque les décimales du nombre Pi !
C'est sans doute le hasard, la méthode étant basée sur des nombres aléatoires... Refaisons le test pour voir...
$ ./test_charpente.sh /tmp/mountpoint
[...]
$ cat /tmp/mountpoint/pieces_ok
31423
$ ./test_charpente.sh /tmp/mountpoint
[...]
$ cat /tmp/mountpoint/pieces_ok
31418
$
Bizarre ce truc ! On dirait bien qu'on reste proche des décimales de Pi !
Attendez, c'est pas possible... On tire des valeurs aléatoires et moyennant une petite formule toute bête, on obtient les décimales de Pi !! C'est quoi cette histoire ??
Bon... Tout cela est bien étrange. Et je dois avouer que je suis bien incapable d'expliquer ce phénomène...
Cela restera donc la « conjecture du charpentier »...
En attendant, l'histoire n'est pas finie. Parce que, pour avoir plus d'informations sur le module filestat utilisé par charpentefs, je suis allé voir son auteur original, mon ami D.J. Et celui-ci a commencé à m'expliquer le petit projet pour lequel il avait écrit ce module...
2. Le problème du D.J.
2.1 Contexte
Mon ami D.J. a accumulé au cours de sa carrière toute une collection de fichiers audio au format MP3. Ce qui l'ennuie, c'est que tous les logiciels actuels de gestion de collection multimédia se basent sur le tag ID3 pour afficher l'auteur ou l'album correspondant à un titre, alors que, pour toute une partie de sa collection, ces informations ne sont pas renseignées.
Les mettre à jour est une opération fastidieuse. Un jour, il décida donc de coder un petit filesystem pour faciliter cette opération.
Le but est le suivant : représenter la collection de fichiers MP3 sous la forme d'une arborescence de répertoires /<artiste>/<album>/<fichier>. Les noms de répertoires <artiste> et <album> refléteront les informations correspondantes du tag ID3 du fichier, s'il est renseigné. Dans le cas contraire, le chemin sera /UnknownArtist/UnknownAlbum/<fichier>. Pour simplifier l'implémentation, <fichier> sera simplement un lien symbolique vers l'emplacement original du fichier MP3 dans la collection.
Certaines opérations de modification, autorisées sur ce filesystem, permettront alors de mettre à jour les informations ID3 correspondantes. En particulier, déplacer un fichier /UnknownArtist/UnknownAlbum/<fichier> vers /<artiste>/<album>/<fichier> provoquera la mise à jour des informations <artiste> et <album> dans le tag ID3 du fichier. On autorisera également la création préalable de nouveaux artistes ou albums via la création du répertoire correspondant.
2.2 Premier contact avec taggerfs
Pour monter TaggerFS, il faut lui indiquer le chemin de notre collection de fichiers MP3, ainsi que le point de montage :
$ mkdir /tmp/mountpoint
$ ./taggerfs.py /mp3_collection /tmp/mountpoint
Ensuite, on peut explorer la collection via l'information contenue dans les tags ID3 :
$ cd /tmp/mountpoint/
Ra UnknownArtist Whitesnake
Pour que l'explication soit plus claire, je n'ai copié dans /mp3_collection qu'un petit fragment de la collection de mon ami. Il n'est pas très éclectique (surtout pour un D.J. !) mais quand même un peu plus que ça. ;)
Ce résultat indique qu'il y a des MP3 où le tag artiste indique « Ra », d'autres indiquant « Whitesnake » et d'autres où le tag n'est pas renseigné.
Explorons plus précisément cette dernière catégorie.
$ ls UnknownArtist/
UnknownAlbum
$
Bon, dans ces fichiers, le tag album manque également, comme on pouvait s'y attendre.
$ ls -l UnknownArtist/UnknownAlbum/
[…]
lrwxrwxrwx [...] Sky.mp3 -> /mp3_collection/HardRock/Ra/From One/Sky.mp3
lrwxrwxrwx [...] Rectifier.mp3 -> /mp3_collection/HardRock/Ra/From One/Rectifier.mp3
$
Ah, voilà qui est plus intéressant. Car, même si ces fichiers n'avaient pas un tag ID3 renseigné, ils étaient par contre correctement classés dans la collection de mon ami. Et, comme taggerfs représente ces fichiers via un lien symbolique, qui pointe vers le fichier MP3 dans la collection, il est facile de deviner que ces fichiers sont du groupe de hard rock « Ra » et de l'album « From One ».
Nous allons donc maintenant mettre à jour le tag ID3 de ces fichiers.
Comme vu plus haut, « Ra » est déjà connu dans notre filesystem. En effet, il y a dans la collection d'autres fichiers MP3 de ce même artiste, mais d'un album différent (« Duality ») :
$ cd Ra
$ ls
Duality
$
Il faut donc « déclarer » cet album « From One », en créant le répertoire correspondant.
$ mkdir 'From One'
$ ls
Duality From One
$
On peut alors déplacer dans ce répertoire nos fichiers (en fait, pour être plus précis, on déplace des liens symboliques) :
$ cd 'From One'
$ mv ../../UnknownArtist/UnknownAlbum/* .
$
Ceci a pour effet de mettre à jour les tags artiste et album de chacun des fichiers concernés.
Pour s'en assurer, on peut par exemple utiliser le programme en ligne de commandes eyeD3 :
$ eyeD3 /mp3_collection/HardRock/Ra/From\ One/Sky.mp3
Sky.mp3 [ 4.52 MB ]
-------------------------------------------------------------------------------
Time: 04:56 MPEG1, Layer III [ 128 kb/s @ 44100 Hz - Joint stereo ]
-------------------------------------------------------------------------------
ID3 v2.4:
title: artist: Ra
album: From One year: None
track:
$
Le tag ID3 a donc bien été mis à jour. On remarque que les autres infos du tag ID3 sont bien évidemment restées vierges. On pourrait imaginer une version plus avancée de taggerfs pour gérer ces autres données...3
2.3 Le code de taggerfs
Le code de taggerfs est basé sur 3 modules codés par mon ami D.J. :
- id3library.py
- taggerfs.py
- filestat.py
2.3.1 id3library.py
Ce module permet de gérer les tags ID3 d'une collection de fichiers MP3. Il utilise en interne la librairie python-mutagen pour l'édition des tags.
Comme ce code est relativement éloigné de notre propos, je ne vais pas le détailler ici. Pour plus d'informations, vous pourrez consulter le fichier source id3library.py4.
2.3.2 taggerfs.py
Le code de taggerfs.py présente des similitudes importantes avec charpentefs.py, du fait que tous deux décrivent un filesystem basé sur FUSE. Nous allons donc nous limiter à décrire les éléments qui diffèrent le plus.
En premier lieu, l'arborescence de charpentefs était plus simple, car on n'avait pas de sous-répertoires. Dans le code de taggerfs, il faut par contre analyser des chemins plus complexes. Ceux-ci doivent être de la forme /[<artist>[/<album>[/<basename>]]], suivant qu'on s'intéresse aux artistes, aux albums d'un artiste ou aux fichiers d'un album.
La méthode TaggerFS.analysePath() permet de factoriser cette analyse :
class TaggerFS(Fuse):
[...]
def analysePath(self, path):
if path == '/':
return None, None, None
tokens = path.split("/")[1:]
while len(tokens) < 3:
tokens.append(None)
return tuple(tokens) # (artist, album, mp3_basename)
[...]
Cette méthode analyse donc path pour déduire chaque composante (optionnelle) <artist>, <album> et <basename> et les retourne sous la forme d'un tuple.
Ainsi :
retournera (None, None, None)
retournera (<artist>, None, None)
retournera (<artist>, <album>, None)
- '/<artist>/<album>/<basename>' retournera (<artist>, <album>, <basename>)
Une fois cette analyse faite via un appel à analysePath(), l'implémentation des gestionnaires de requêtes FUSE est relativement triviale.
Les filesystems charpentefs et taggerfs présentent une autre différence notable : la liste des opérations autorisées par chacun d'entre eux est différente. Dans le cas de taggerfs.py, on trouve ainsi de nouveaux gestionnaires de requêtes FUSE :
- readlink(self, path) doit retourner la cible du lien symbolique indiqué par path. Dans notre cas, on retourne donc le chemin du fichier MP3.
- rename(self, old_path, new_path) permet de gérer le renommage ou le déplacement d'un fichier. Dans notre cas on autorise uniquement le déplacement d'un lien symbolique /<old_artist>/<old_album>/link_name vers /<new_artist>/<new_album>/link_name.
- mkdir(self, path, mode) permet de gérer la création d'un répertoire. Dans notre cas, cette opération permet de « déclarer » un nouvel artiste ou un nouvel album via la création du répertoire correspondant.
2.3.3 filestat.py
Ce module est utilisé à la fois par taggerfs et charpentefs. Il permet de créer des « paquets d'attributs de fichier » utiles pour répondre aux requêtes FUSE getattr().
Il y a deux façons pour fabriquer ces « paquets d'attributs de fichier » :
- manipuler un objet de type posix.stat_result et spécifier chacun des attributs (type de fichier, taille du fichier, autorisations, propriétaire, etc.),
- créer un fichier temporaire adéquat et lire le paquet d'attributs via os.lstat().
La deuxième méthode est sans doute bien plus portable. En effet, la première ne fonctionnera que sur les systèmes de type POSIX. D'autre part, avec la deuxième méthode, on n'a pas besoin de spécifier tous les attributs, car les valeurs par défaut utilisées pour la création du fichier temporaire conviennent souvent.
Mon ami D.J. a ainsi utilisé cette approche pour créer le module filestat.py.
Voici son code, qui est assez trivial :
import os, tempfile
def generateSampleDirStat():
tmpdir = tempfile.mkdtemp()
stat_info = os.stat(tmpdir)
os.rmdir(tmpdir)
return stat_info
def generateSampleFileStat(mode, size):
fd, tmpfile = tempfile.mkstemp()
if size > 0:
os.write(fd, '-' * size);
os.close(fd)
os.chmod(tmpfile, mode)
stat_info = os.stat(tmpfile)
os.remove(tmpfile)
return stat_info
def generateSampleSymlinkStat():
tmpdir = tempfile.mkdtemp()
tmplink = tmpdir + '/link'
os.symlink(tmpdir, tmplink)
stat_info = os.lstat(tmplink)
os.remove(tmplink)
os.rmdir(tmpdir)
return stat_info
2.4 taggerfs : conclusion
Concernant taggerfs, je me suis vite rendu à l'évidence : l'approche filesystem est diablement efficace pour ce genre de problèmes !
Je ne sais pas si vous avez remarqué, mais tout à l'heure, on a mis à jour deux tags différents (artiste et album), sur tous les fichiers d'un album. Et tout cela en une seule commande mv triviale !!
Et ce n'est pas tout : on pourra utiliser un gestionnaire de fichiers graphique pour sélectionner et déplacer les fichiers de manière ergonomique... Il ne faudra pas longtemps pour réorganiser la hiérarchie correctement et le filesystem va mettre à jour les tags ID3 en conséquence, de manière totalement transparente.
Le déplacement de fichiers est d'ailleurs la base de l'informatique, tout le monde sait faire ça (en tout cas de manière graphique). Donc, ce n'est pas forcément l'informaticien (que dis-je, le D.J.) qui a codé le filesystem qui s'en chargera...
3. Et toi, tu codes quoi comme filesystem ?
Moi ? Eh bien, en fait, je code un filesystem qui utilise des algorithmes de gestion de données avancés. Ce sont des algorithmes développés dans l'équipe de recherche où je travaille. Et j'espère donc obtenir des performances supérieures aux filesystems classiques (ce n'est pas gagné).
J'ai commencé par un prototype en C++ avec FUSE, et, suivant les résultats que j'obtiendrai, j'envisagerai ou non un codage noyau.
C'est un projet qui me plaît beaucoup, parce que c'est bien bas niveau. Même mon environnement de test était « amusant » à développer...
Je vous invite donc à vous essayer au codage de filesystem, c'est assez passionnant !
PS : Merci à Pierre-Henry pour la relecture.
La conjecture du charpentier : le mystère dévoilé !
Le problème du charpentier repose bien évidemment sur des hypothèses montées de toutes pièces ; et ceci dans le but d'obtenir le résultat « inattendu ». Et comme je suis un peu joueur, il fallait bien que je vous fasse mariner un peu avant de vous donner ces explications...
La figure suivante représente le placement aléatoire d'un point P, avec x et y choisis aléatoirement entre 0 et 1. Suivant les cas, P peut se trouver dans la zone rouge clair ou dans la zone vert clair.
Fig. 2 : Explication sur l'obtention des décimales du nombre Pi
La distance d est égale à racine_carree(x^2+y^2). La probabilité que P soit dans la zone rouge clair correspond donc à la probabilité que l'expression suivante soit vraie :
racine_carree(x^2+y^2) <= 1
Par ailleurs, comme P est placé de manière aléatoire dans le carré, la probabilité que P soit dans la zone rouge clair correspond aussi au rapport entre l'aire de la zone rouge clair sur l'aire du carré. La zone rouge clair étant un quart de disque de rayon 1, son aire est de Pi/4. Et l'aire du carré est bien évidemment 1. Donc le rapport donne Pi/4.
Avec ces deux façons de calculer la même probabilité, on en déduit que la probabilité que l'expression racine_carree(x^2+y^2) <= 1 soit vérifiée est de Pi/4.
Notre ami charpentier ayant testé 40000 fois cette expression, il est normal qu'il obtienne un nombre proche de 40000 * Pi/4 = 10000 * Pi, d'où l'apparition des décimales...
Même si ces explications rendent évident le résultat obtenu, j'avoue avoir été surpris moi-même quand on me l'a montré : comment imaginer qu'on peut approcher la valeur de pi avec uniquement un grand nombre de valeurs aléatoires et une formule aussi simple ?
1 Vous pouvez trouver ce code à l'adresse : https://github.com/eduble/SimpleFilesystems
2 http://docs.python.org/2/library/errno.html
3 Mon ami D.J. ne compte pas poursuivre ce projet, car la fonctionnalité est suffisante pour son besoin. D'autre part, il s'est aperçu qu'il existait un autre projet, pytagfs, dont l'approche semble similaire et dont les fonctionnalités semblent plus complètes : http://www.pytagsfs.org/
4 Voir : https://github.com/eduble/SimpleFilesystems
