Valhalla Scanner

Hello,

Un petit nouveau a fait son entrée dans les dépôts de GeeXboX. C’est un projet qui est né suite à quelques expériences négatives avec une autre bibliothèque. Elle m’avait alors motivé à en écrire une afin d’y apporter une vision un peu différente. Le but de Valhalla (ou libvalhalla), est très simple, elle va scanner des emplacements sur votre disque dur (par exemple) afin d’y trouver des fichiers audio/video pour les référencer dans une base de données. Il est alors facile ensuite d’y effectuer des requêtes permettant de générer des listes d’artistes, d’albums, etc,…

Mais tout d’abord.. pourquoi Valhalla?

Dans la mythologie nordique, la Valhöll (ou Walhalla, Valhalla, Valhalle), demeure-des-occis, est le lieu où les guerriers valeureux sont amenés. C’est sur les champs de bataille que des vierges guerrières (pour les celts) ou des Valkyries (pour les germains), cherchent et récupèrent les hommes les plus braves et les plus valeureux afin de les ramener dans Ásgard, où Odin les attend pour les préparer à la bataille finale, le Ragnarök.
Dans la Valhöll(palais de Thor), les guerriers alors nommés Einherjar sont heureux : ils combattent, se tuent, renaissent pour encore se pourfendre dans un champ clos.

Valhöll. (2009, mars 10). Wikipédia, l’encyclopédie libre. Page consultée le 17:42, mars 12, 2009 à partir de http://fr.wikipedia.org/w/index.php?title=Valh%C3%B6ll&oldid=38802776.

Je cherchais un nom qui sort de l’ordinaire tout en gardant un sens par rapport à la fonctionnalité de cette bibliothèque. Si la définition de La Valhalla ci-dessus ne vous a pas convaincu, imaginez que les scanners sont les Valkyries, que les braves sont les fichiers audio/video, et qu’elles les emmènent à la Valhalla (dans la base de donnée). Ceux-ci mourant et renaissant sans cesse dans un champ clos (les fichiers pouvant être rescannés en boucle afin d’y repérer les modifications).

(A noter que Valgrind est la porte qui mène à La Valhalla)

Fonctionnement

Small. Fast. Reliable.

Valhalla se base sur deux bibliothèques principales. Tout d’abord il y a la libavformat (de FFmpeg) qui permet de récupérer les méta-données, puis SQLite qui s’occupe de gérer la base de donnée. Si ces libs ont été choisies c’est pour de bonnes raisons. Comme je l’ai dis plus haut, libvalhalla est née suit à des expériences avec une autre lib. En premier lieu, cela concerne le moyen pour récupérer les méta-données. Sans rentrer dans des détails inutiles, pour se faire il est nécessaire de passer par des démuxeurs et en créer peut avoir un avantage certain sur la rapidité. Néanmoins beaucoup de travail serait nécessaire pour gérer la plupart des formats de fichier, et c’est ici qu’intervient FFmpeg. Cette bibliothèque étant la plus aboutie, elle supporte énormément de formats. Il est donc facile de récupérer les méta-données sans se soucier du “comment”. La deuxième raison est purement technique. Certains aspects dans la construction de l’autre lib ne me plaisaient pas (à tord ou à raison).
Concernant SQLite, c’est un excellent outil (et très léger et rapide) de gestion de base de données.

Architecture

Avant d’aborder l’architecture en elle-même j’aimerais expliquer mes choix. Tout d’abord Valhalla repose sur les threads. Parce que j’aime travailler avec les threads même si de nombreuses personnes estiment que les “threads are evil”. Ensuite il y a une raison liée à l’aspect pratique et à l’aspect vitesse. D’un point de vue pratique, les threads sont un moyen facile de créer des tâches parallèles et aussi de créer des tâches de fond. Il est intéressant dans le cas d’Enna, de pouvoir l’utiliser sans être bloqué par Valhalla.

J’entends certaines personnes me parler des fork(), alors oui c’est également un moyen.. mais franchement, communiquer entre des sous-processus c’est pénible et nettement moins efficace que de le faire directement entre deux threads qui partagent le même espace mémoire. Les fork() doivent être utilisés si le contexte le demande. Tel que c’est le cas dans libplayer pour travailler avec MPlayer.

L’aspect vitesse est également intéressant car aujourd’hui il est courant de trouver des ordinateurs avec au moins 2 cores. Alors quitte à faire travailler les démuxeurs sur les deux (ou plus), je vous montrerais des petites statistiques plus loin.

La figure ci-dessous présente une vision simplifiée de l’architecture.

Il y a trois parties principales. En vert, le scanner s’occupe de chercher tous les fichiers qui respectent certains critères relatifs à leur nom. Puis chaque référence aux fichiers est envoyée à la partie jaune (Database) qui va vérifier si le fichier existe déjà dans la base de donnée ou s’il est nouveau. Si des modifications sont nécessaires, alors il est envoyé à la partie orange (Parser) afin que les méta-données soient récupérées. Le parser renvoit les données à la Database qui va alors insérer les modifications adéquates dans la base de données à travers SQLite. Chaque bloc représenté dans la figure est un thread. La partie orange peut contenir plusieurs parsers et donc plusieurs threads.

FFmpeg

A complete, cross-platform solution for audio and video.

Les parsers utilisent la bibliothèque libavformat d’FFmpeg pour réaliser l’extraction des méta-données. Il y a cependant un problème de vitesse. libavformat fait appel à des fonctions de “probe” afin d’identifier le format du fichier pour lui assigner le bon démuxeur. Et dans certains cas (fichiers altérés?), le “probe” prend beaucoup de temps car il y a beaucoup de démuxeurs et qu’il est parfois nécessaire de tester plusieurs fois un même fichier (en avançant dans les données) avant que la lib puisse deviner lequel est le bon.

L’idée est donc de proposer un format directement à libavformat au lieu de le laisser procéder tout seul à la détection. Le moyen utilisé est très simple et efficace. Il est rare que le suffixe d’un fichier ne correspond pas au bon format. La première étape est donc de récupérer le nom du format qui est lié au suffixe (à l’extension). Typiquement, si les fichiers sont des .mp3, le nom est tout simplement “mp3″. Voir les détails dans les sources.

name = suffix_fmt_guess (file);
if (name)
  fmt = av_find_input_format (name);

La deuxième étape est un petit peu plus compliquée. Bien que l’on a désormais une idée sur le démuxeur, il est exclus de l’utiliser tel quel. Si un format est forcé à l’ouverture du fichier, aucun test n’est réalisé par libavformat. Ainsi, une fonction de probe() a été écrite pour tester le démuxeur. L’avantage cette fois vient du fait qu’un seul démuxeur est testé, et non plus tous les démuxeurs de libavformat. Le gain en vitesse est impressionnant (j’ai constaté un gain de plus d’un facteur dix avec cette technique et un peu plus de 1000 MP3/OGG).

if (fmt)
{
  int score = parser_probe (fmt, file);
  if (!score) /* Bad score? */
    fmt = NULL;
}

Si vous êtes intéressé par la fonction parser_probe(), je vous invite à directement la consulter dans les sources. En résumé, la fonction est inspirée de libavformat/utils.c::av_open_input_file(), et dépend fortement de l’implémentation interne de libavformat en ce qui concerne les scores retournés par les fonctions de probe().

Les priorités

Si vous désirez définir des priorités non temps réelles à des threads, voici l’astuce:

#include <unistd.h>
#include <sys/resource.h>
#include <sys/syscall.h>

static inline void
my_setpriority (int prio)
{
  pid_t pid = syscall (__NR_gettid);
  setpriority (PRIO_PROCESS, pid, prio);
}

La fonction gettid() n’existe pas dans la glibc, il est donc obligatoire de passer par un appel système. Et sans utiliser setpriority(), il n’est pas possible à ma connaissance de baisser la priorité en étant un simple utilisateur.

Défaut de jeunesse

Malheureusement un défaut relativement important a été soulevé par Aurélien (un des leader du projet GeeXboX et développeur de FFmpeg). Les méta-données disponibles dans les fichiers audio/video peuvent être très différentes d’un format à l’autre. Valhalla est limité dans le nombre de meta-données supportées. Une future mise à jour majeure devrait apporter beaucoup plus de souplesse pour la gestion des méta-données. A priori cela ne semble pas si compliqué, mais si l’on considère le fait que la base de données suit un modèle relationnel, il est difficile d’être complètement générique.

Je n’ai pas encore pris le temps d’étudier toutes les possibilités pour y remédier. Mais ça fait partie de mes priorités pour Valhalla.

Enna

Mon but principal est d’utiliser Valhalla dans Enna. Ainsi un nouveau module à fait son apparition et permet de retrouver de manière thématique les albums, les artistes, les genres ainsi que les fichiers non-classés. Le module est également paramétrable depuis le fichier ~/.enna/enna.cfg pour surtout y indiquer les répertoires à scanner.

[valhalla]
path=file:///home/foo/music
path=file:///home/bar/music
verbosity=info
parser_number=2
commit_interval=128
# <=0 for infinite
scan_loop=-1
# time [sec] for sleeping between loops
scan_sleep=900
# 0: normal, -20: higher, 19 lower
scan_priority=19

Quelques paramètres méritent certaines explications. Tout d’abord vous pouvez indiquer autant de “path” que vous le désirez. Les paths ne sont pas scannés en parallèle, mais séquentiellement. Il n’y a pas beaucoup d’avantage de scanner  plusieurs répertoires en parallèle car les accès au disque ne seront pas plus rapide.
Vous pouvez bien sûr changer la verbosité de la bibliothèque. L’intérêt est limité pour de simples utilisateurs, mais ça peut être utile dans des cas de debuggage.

Nombre de parsers

L’option “parser_number” indique le nombre de parsers à créer. Par défaut, le nombre maximum est de 8. Ce chiffre peut être changé à la compilation de Valhalla en passant le define PARSER_NB_MAX=# dans le CFLAGS. Mais il faut garder à l’esprit qu’il est inutile de définir beaucoup de parsers car ça n’augmentera en rien la vitesse.

Intervalle entre les commits

L’option “commit_interval” permet de dire chaque combien de fichiers, les données sont réellement inscrites dans la base de données. Moins cette valeur est grande, et moins le scan sera rapide car SQLite augmentera le nombre d’écritures sur le disque dur. J’ai constaté un gain de ~20 en passant d’une valeur de 1 à une valeur de 128. Si vous définissez une valeur plus grande, le gain ne sera plus tellement visible et les données s’accumuleront dans la RAM. Le fait de mettre une petite valeur est également plus sûr, car en cas de plantage, plus de données seront écrites. C’est donc aussi une question de bon sens.

Bouclage du scan et temps entre les scans

L’option “scan_loop” indique le nombre de bouclage qui doivent être effectués pendant qu’Enna est exécuté. L’intérêt est de détecter les modifications et les nouveaux fichiers. En mettant une valeur de 1, le scan se fera uniquement au démarrage d’Enna. Par contre avec une valeur plus petite ou égale à 0, le scan se fera chaque “scan_sleep” secondes. Vous pouvez bien sûr donner une valeur supérieure tel que 2, 3, etc,.. pour définir exactement le nombre de bouclages désiré.

Priorité du scan

L’option “scan_priority” permet de garantir que le scanner, le gestionnaire de la base de données ainsi que les parsers, ne puissent pas monopoliser les ressources de votre système. Le fait de donner une valeur de 19, garanti que Valhalla aura la priorité la plus basse et son comportement sera bien une tâche de fond. Par défaut un utilisateur à une priorité de 0, et tous les programmes exécutés ont une priorité de 0 (vous ne pouvez donc donner que des priorités inférieures (valeurs positives ou égales)). Si vous n’avez pas les droits appropriés et que vous donnez une priorité de -1 à -20, Valhalla gardera une priorité de 0. Par contre, si vous êtes root, alors vous pouvez mettre n’importe quel priorité. (Il n’est pas recommandé de mettre une priorité supérieure ou égale à Enna à moins d’affecter directement la lecture des fichiers et l’interface.)

La suite

Comme je l’ai expliqué plus haut, il reste beaucoup de travail pour rendre la bibliothèque plus générique envers les méta-données. Mais il reste également du travail au niveau de l’API, en ce qui concerne les fonctions pour sélectionner les données dans la base de données, et ces fonctions dépendent directement des méta-données.

Bien sûr, il est possible d’effectuer des requêtes sur la base de données sans passer par Valhalla. Mais dans ce cas il faut être conscient qu’il peut y avoir des problèmes de parallélisme. SQLite utilise fcntl() pour bloquer l’accès au fichier le temps des modifications. Mais sur certains systèmes de fichier, cela est buggé (voir les explications  ici).

Quelques modifications mineures sont également prévues, comme l’ajout de filtres sur les paths, pour par exemple ignorer les fichiers et dossiers cachés. Et également un moyen de récupérer l’information si un fichier contient des flux audio, video ou audio+video.

Une mise à jour concernera également l’ajout d’informations sur la version du fichier de base de données et la version de Valhalla. Car actuellement, si des modifications structurelles sont effectuées sur la base de données, Valhalla ne fait aucun contrôle sur le fichier qui a été créé par une ancienne version. Ce qui peut provoquer des erreurs plus ou moins imprévisibles lors de l’exécution d’un scan. Le temps que j’implémente cette partie, il est judicieux d’effacer le fichier ~/.enna/valhalla_music.db lors d’une mise à jour de Valhalla.

Télécharger

Pour télécharger Valhalla, rien de plus simple:

hg clone http://hg.geexbox.org/libvalhalla

La compilation et l’installation se fait comme pour n’importe quel logiciel.

./configure && make && sudo make install

Pensez aussi à faire un `sudo ldconfig` pour être sûr que la lib soit référencée pour le chargeur de programme.

Il est également important (indispensable) d’utiliser une version récente d’FFmpeg!

Quelques statistiques

Comme promis, voici quelques statistiques liées à la vitesse du scan. Le premier scan est toujours le plus long. La vitesse dépend principalement de la vitesse d’accès du média sur lequel se trouve les fichiers. Puis en second lieu, elle dépend également du cache effectué par le système de fichier. Mes quelques tests ont été fait sur une partitions EXT3 avec principalement des fichiers MP3 (dont des corrompus), des fichiers OGG, WMA et M4A. (le fichier de base de données est bien sûr effacé entre chaque essai). Il y a 1090 fichiers et mon système est dual-core.

Premier scan (sans cache)

Run: parser=2 loop=1 wait=0 priority=19 commit-int=128
Time elapsing: 24675.591000 msec, 24.675591 sec

Quelques scans (même config + cache)

Time elapsing: 1049.802000 msec, 1.049802 sec
Time elapsing: 1183.110000 msec, 1.183110 sec
Time elapsing: 1066.583000 msec, 1.066583 sec

La vitesse a énormément changée et pourtant la bibliothèque à fait exactement le même job. Le cache du système de fichier a un effet très important.

Avec un seul parser (1 parser + cache)

Run: parser=1 loop=1 wait=0 priority=19 commit-int=128
Time elapsing: 1500.876000 msec, 1.500876 sec
Time elapsing: 1436.085000 msec, 1.436085 sec
Time elapsing: 1637.296000 msec, 1.637296 sec

On note en moyenne 1.10 sec pour 2 parsers et 1.53 sec pour 1 parser. Vous me direz que ça n’a rien d’exceptionnel et vous avez tout a fait raison. La différence est de 430 ms entre les deux moyennes. Mais en réfléchissant un peu, cela représente qu’en même un gain de ~40%.
Ces statistiques ne sont pas très exhaustives car 1090 fichiers ce n’est pas grand chose. Il faudrait également effectuer beaucoup plus de tests pour avoir une statistique relevante. Mon but était juste de vous montrer que le nombre de parsers ne fait pas de miracle. Et qu’avoir plus d’un parser lors du premier scan ne changera quasiment rien. Mais si vous avez beaucoup plus de fichiers que moi, (des dizaines de milliers) l’impacte sera bien plus grand.

Avec un commit-int à 1 (+ cache)

Run: parser=2 loop=1 wait=0 priority=19 commit-int=1
Time elapsing: 20299.520000 msec, 20.299520 sec
Time elapsing: 18831.318000 msec, 18.831318 sec
Time elapsing: 19063.652000 msec, 19.063652 sec

Voyez comme l’intervalle entre les commits effectués par SQLite sont très important. Passer de 1.5 sec à 20 sec n’est pas du tout négligeable.

Avec un commit-int à 1024 (+ cache)

Run: parser=2 loop=1 wait=0 priority=19 commit-int=1024
Time elapsing: 935.655000 msec, 0.935655 sec
Time elapsing: 1018.052000 msec, 1.018052 sec
Time elapsing: 953.042000 msec, 0.953042 sec

Il est intéressant de noter qu’avec un intervalle de 1024, Valhalla arrive à descendre en dessous de la seconde. Maintenant vous comprendrez qu’il est difficile de trouver une configuration parfaite pour tout le monde. Mais le gain entre un intervalle de 128 ou de 1024 n’a plus beaucoup d’impact. Sans compter que 128 est plus sûr dans le cas d’un crash.

(Tous les tests ont été effectué avec l’outil test-valhalla directement disponible depuis les sources.)

Conclusion

Il reste beaucoup de travail à faire, mais vous pouvez utiliser cette bibliothèque correctement dans l’état actuel. Les performances sont à mon avis très bonnes et le nombre de parsers sera sûrement plus significatif dans le futur, car certaines améliorations auront forcément un impact sur la vitesse de récupération des méta-données. Même sur un système mono-processeur (mono-core), il est judicieux de garder 2 parsers. Parfois certains fichiers sont relativement altérés et difficiles à parser. Le fait de garder un deuxième parser assure un bon enchaînement si l’un d’eux perd du temps.

A bientôt,

Mathieu SCHROETER