------------------------------------------------------------------------------------
Décryptage de développeur sur la v0.42b de eMule par MiRVRe,
la dernière version v0.42b de la mule a tout remis à plat. Excellent !
D'autant excellent qu'une bonne partie de mes posts précédents sur ce sujet ainsi que tous mes scripts et la doc qui allait avec (que j'allais publier) sont à présent (presque) caduques, en particulier la partie où je critiquais l'obsolescence des algorithmes employés et leur inefficacité du point de vue de la complexité.
QUOTE(eMule changelog)
----------------------
- Feb 1st, 2004 -
----------------------
bluecow: Reworked IP filter
- Optimized IP filter lookup for less CPU load.
- Optimized loading of IP filter files.
- Added merge of overlapping and adjacent filter ranges.
- More safety in determining format of IP filter files (support for eMule IP filter and PeerGuardian file formats).
- More tolerance in eMule IP filter format files (level and description is now optional).
- Added IP filter dialog for basic editing and viewing IP filters (accessible via Tool menu).
- Added IP filter rule hit statistics.
...
J'ai regardé les sources et les commentaires pour vérifier de quoi il s'agissait.
Voici ce que je constate:
bluecow: Reworked IP filterEffectivement, visible ne serait-ce qu'au niveau de la taille du fichier source IPFilter.cpp qui passe de grosso-modo 4 ko à 10 ko.
- Optimized IP filter lookup for less CPU load.D'après les commentaires et les noms de fonctions employés, on passe d'un parcours linéaire de la liste à un parcours dichotomique sur une liste triée. La complexité passe de O(n) à O(log2(n)). (log2(n): logarithme en base 2 de n=log(n)/log(2))
L'amélioration est considérable.
En effet, distinguons 2 cas:
1. l'IP vérifiée est dans la liste de taille n (n plages dans la liste)
avant, en moyenne, la moitié de la liste était parcourue, soit n/2 tests
maintenant, au pire, le nombre de tests vaut log2(n)
Exemple:
avec une liste de 1000 éléments, c'est 500 tests (avant) contre 10 (maintenant)
avec une liste d'un million (hypothétique), c'est 500000 tests contre 20.
2. l'IP vérifiée n'est pas dans la liste
avant, toute la liste était parcourue, soit n tests pour ne rien trouver
maintenant, le nombre de tests vaut log2(n)
Autrement dit, si avant tout doublement de la taille de la liste entrainait un doublement moyen du nombre de tests, à présent, le doublement de la taille n'entraine qu'un test supplémentaire. C'est l'une des améliorations que je suggérais dans mes docs. On pourrait faire encore mieux (temps constant, complexité en O(1) (4 tests tout le temps quelque soit la taille de la liste) mais au prix d'une occupation mémoire plus importante en raison de la structure de données employée: B*Tree).
- Optimized loading of IP filter files.Sans que ce soit une optimisation (c'est même l'inverse, vu l'opération supplémentaire de tri, mais uniquement au moment du chargement), la liste est triée suivant les IP et c'est une nécessité pour que l'algorithme de recherche par dichotomie (bsearch) puisse fonctionner.
- Added merge of overlapping and adjacent filter ranges.La liste IPFilter est retravaillée pour fusionner les lignes présentant entre-elles des chevauchements et des adjacences. On peut le voir dans l'onglet
Verbose, une ligne indiquant le nombre de lignes lues à partir du fichier IPFilter.dat, le nombre de lignes utiles, le nombre de chevauchements et le nombre de lignes fusionnées.
- More safety in determining format of IP filter files (support for eMule IP filter and PeerGuardian file formats).Il est possible d'importer les 2 formats. Ceci est visible dans le bouton Tools (Outils?) -> IP Filter -> Append...
- More tolerance in eMule IP filter format files (level and description is now optional).Le format IPFilter.dat est devenu moins strict, on peut se passer de spécifier le niveau, cela permet la prise en compte de fichiers présentants des coquilles comme pour l'IPFilter.dat v1.42 version "suche":
195.241.164.000 - 195.241.165.255 , 240 Tiscali (dialin), il manque une virgule entre le niveau et le commentaire, ce qui entrainant la non-prise en compte avant, maintenant cette ligne est prise en compte avec un niveau par défaut qui est fixé dans les sources à 100.
- Added IP filter dialog for basic editing and viewing IP filters (accessible via Tool menu).Accessible à partir du bouton Tools (Outils?) (ou ALT-X) -> IP Filter.
Il est même possible de sauver le fichier IPFilter "optimisé".
- Added IP filter rule hit statistics.Intéressant, si j'avais eu Visual Studio, ça fait belle lurette que je l'aurais codé pour établir des statistiques des hits des règles qui auraient pu servir pour optimiser les règles (caduque à présent).
Toutefois, un commentaire (
//TODO: not yet handled, overlapping entries with different 'level') indique que la prise en compte des chevauchements pour des niveaux différents n'est pas encore d'actualité. Génant dans le cas suivant par exemple:
QUOTE(IPFilter.dat)
0.0.0.0 - 3.255.255.255 , 200 , non filtré
3.0.0.0 - 4.255.255.255 , 100 , filtré
qui est fusionné comme suit:
QUOTE(IPFilter.dat fusionné)
0.0.0.0 - 4.255.255.255 , 200, non filtré
Aïe (dans ce cas: 200 est un niveau inutile, on suppose 127 par défaut), en cas de fusion, c'est la première ligne dans l'ordre des IP qui détermine le niveau. La fusion n'est pas donc pas encore optimale et peut même créer des situations dangereuses ce qui n'était pas le cas avant (les 2 plages étaient prises en compte) !
Dommage. Il est encore et malgré tout nécessaire de faire attention à la cohérence de ses listes. (Mes scripts ne sont pas encore si obsolètes que ça). Ceci étant, ce "TODO" (à faire) sera (on l'espère) rapidement "DONE" (fait).
D'autre part, mais c'est presque accessoire, cette ligne (qui est commentée donc non prise en compte)
//pPrv->desc += _T("; ") + pCur->desc; // this may create a very very long description string... et son commentaire indique clairement que les commentaires seraient fusionnées sans limite de taille, ce qui est à la fois bien et pas bien: la fusion améliore la vitesse de traitement à charge constante, mais en cas de sauvegarde de la liste, amoindrit la lisibilité du fichier IPFilter.dat car on ne sait plus à quelle plage correspond quel commentaire (c'est trivial d'ajouter en commentaire la plage concernée mais en augmentant encore sa taille), commentaire qui pourrait, comme l'indique le commentaire du source, devenir gigantesque. En l'état (ligne commentée), seul le premier commentaire est conservé ce qui annihile le rôle du commentaire pour les lignes IPFilter fusionnées.
Il manque aussi la non-prise en compte au chargement des lignes dont le niveau est supérieur au seuil paramétré. Un commentaire dans le source indique ce "TODO", donc il est possible qu'une prochaine version de la mule en tienne compte, d'autant qu'effectuée (l'élimination des lignes non pertinentes) en amont du tri puis des fusions, permettrait d'éviter le genre de fusions ratées évoqué plus haut à condition de forcer en cas de changement de seuil dans la config de la mule, (éventuellement) le re-chargement du fichier, le "re-tri", la "re-fusion". Wait & See.
Je vais continuer à inspecter les sources, mais sans la suite Visual Studio, c'est des plus pénible pour vérifier le rôles des fonctions employées, d'autant que les sources relatives à l'IPFilter se sont complexifiées un brin.
De mon côté, je vais terminer puis remanier ma doc avant de mettre à disposition mes scripts qui restent valides (tels que pour les mules v0.41b.29 et inférieures, et à peu de choses près pour les v0.42b et supérieures: une clé de tri à ajouter pour me calquer sur la fonction de comparaison employée par le tri sous la mule v0.42b).
Ceci dit, joli boulot de ce côté pour cette nouvelle version de la mule, qui permettra une meilleure prise en compte (en attendant les "TODO") de listes de plus en plus délirantes, issues elles-mêmes de fusion plus ou moins heureuses.
Par MiRV.EDIT: petites corrections
------------------------------------------------------------------------------------