Brevet FR2796178A1 — publié le 20010112

Procédé de réalisation de liens dynamiques dans une machine virtuelle La présente invention concerne un procédé de réalisation de liens dynamiques au sein d'un système embarqué dans une machine virtuelle. L'invention trouve une application particulièrement avantageuse dans le domaine des machines virtuelles orientées objet lorsqu'on veut obtenir des liens dynamiques très rapides, notamment au sein d'un petit système embarqué qui ne dispose pas de ressources matérielles très élevées et qui malgré tout devra présenter des performances de temps réels honorables (supérieures à 4 ms) . La problématique des liens dynamiques apparaît quand deux classes d'objets représentés par leurs instances doivent se lier via l'appel d'une méthode ou d'un attribut. Imaginons l'invocation d'une méthode virtuelle d'un objet, la machine virtuelle devra naviguer dans cet objet et son héritage (sous objets) afin de trouver une méthode qui a le même nom et le même descripteur (type des arguments). La comparaison de chaînes ASCII de longueurs variables représentant les noms (en anglais fully qualified norme ) et les descripteurs de fonctions peut être très longue et non déterministe. Pour comprendre la problématique, imaginons l'appel de la méthode statique FunctionExt de l'objet Other qui est une instance de la classe Java OtherClass . La machine virtuelle devra (voir figure 1): 1. trouver la classe OtherClass , 2. trouver la méthode FunctionExtN(), Une fois les deux directions trouvées, la machine pourra invoquer la méthode. L'édition de liens dynamiques permet la technique du téléchargement partiel. Lors de la mise à jour d'un programme d'application, seule la partie modifiée est téléchargée (parfois moins d'un kB), contre la totalité de l'application dans le cas de l'édition de liens statiques. Cette technique permet de réduire considérablement le temps et les coûts de téléchargement. Dans les machines virtuelles actuellement connues, le chargeur de classes réalise une édition de liens lors du chargement. Les nouvelles classes chargées sont marquées afin de ne pas répéter cette opération. Cette étape passe par un recensement de tous les liens dans une table de correspondance avec les adresses des classes correspondantes. Puis les images binaires des classes sont construites à partir de ces tables. En d'autres termes, l'édition de liens consiste à remplacer des noms par des adresses physiques de stockage de classes, de méthodes ou d'attributs. Cependant, ce procédé connu de réalisation de liens présente les inconvénients suivants 1. Le stockage des noms exacts des liens peut représenter un important pourcentage de la taille d'une classe. 2. Le temps nécessaire pour réaliser cette édition de liens. 3. Les noms des liens doivent être transportés jusqu'à la cible d'exécution ce qui représente une perte de rendement de transmission. Les conséquences sont 1. Si l'édition de liens est réalisée au chargement, cette opération est coûteuse en temps. 2. Si l'édition de liens est réalisée à l'exécution (à la volée), cette opération est non déterministe. Dans les deux cas, la manipulation de longues chaînes ASCII est contraignante pour des traitements en temps réel. Aussi, le problème technique à résoudre par l'objet de la présente invention est de proposer un procédé de réalisation de liens dynamiques au sein d'un système embarqué dans une machine virtuelle, qui permettrait de remédier aux inconvénients présentés par les procédés connus. La solution au problème technique posé consiste en ce que les noms de liens liés à une règle de codage sont remplacés par un code de hachage résultant du hachage de ces noms par une fonction de hachage. Le principe de l'invention repose donc sur les fonctions de hachage. Les fonctions de hachage ont les propriétés suivantes 1. La taille de leurs résultats est fixe. 2. Elles sont relativement simples à calculer. 3. Elles sont irréversibles (On ne peut pas à partir d'un résultat revenir à l'image de départ). 4. Elles sont exemptes de collision (bijection). La fonction de hachage MD5 est un des algorithmes éligibles pour réaliser cette opération de hachage. Cependant la théorie montre que les propriétés de base des fonctions de hachage ne sont pas formellement réalisées mais suffisamment proches pour les considérer réalisées. Le problème se pose pour deux des qualités de base des fonctions de hachage 1. L'aspect non réversible des fonctions de hachage. 2. La présence des collisions (surjection). Cependant les ressources nécessaires pour inverser une fonction de hachage ou le nombre d'images de départ pour craindre une collision sont sans communes mesures avec le domaine d'utilisation de ces fonctions. La théorie montre que la probabilité d'avoir deux anniversaires le même jour dans une même classe d'école est supérieure â 1/2 avec seulement 23 élèves. La formule est 1.2 k '/Z où k est le nombre de jours dans une année. Dans le cas du MD5, la signature digest code est de 128 bits, ce qui représente plus de 264 essais possibles avant d'obtenir une collision. La probabilité de collision est donnée par la formule (adaptée) de Poisson P= 1_e-n(n-1)/2N où ri est l'ensemble des noms de liens mis en présence dans un système. N est le nombre possible de codes de la fonction de hachage. Si le ratio n2/2N est très petit alors la probabilité de collision est approximativement P= n2/2N Dans le cas du MD5 avec 1000 liens en présence, la probabilité est environ 10-32 , soit quasiment nulle. D'autres fonctions de hachage peuvent être utilisées, telles que les fonctions MD4, SHA-1, CRC32, CRC64, CRC 128. Cependant dans le cas d'un système fermé, la présence de collisions est testable avant le chargement. Dans le cas très peu probable d'un conflit, le nom du lien est modifié afin de résoudre le conflit. Le principe de la fonction de hachage est la propriété de transformer une image binaire quelconque en un nombre aléatoire calculé. Si l'espace des nombres aléatoires est très grand par rapport au nombre de tirages, la probabilité de tirer deux fois le même nombre est quasiment nulle. Ce rapport d'espace peut être ajusté pour obtenir le meilleur rapport probabilité/taille des codes en fonction du système hôte (le système embarqué). Cet ajustement permet de replier le code de hachage sur lui-même afin d'obtenir un code plus court et sauver ainsi de l'espace de stockage. Il est également possible de tronquer le code de hachage. Ainsi, dans le cadre d'un système Java pour terminaux embarqués, l'édition de liens se produit lors de la recherche d'une classe, la probabilité de collision s'applique sur l'ensemble des classes en présence dans le système uniquement. Dans ce cadre, un code de hachage convenable doit être requis (≥64 bits). Par contre, lors de la recherche d'une méthode ou d'un attribut dans un objet, l'ensemble des liens possibles est celui de l'ensemble des noms de méthodes et attributs de l'objet et des objets dont il hérite. L'espace de collision est considérablement réduit et un code de hachage plus petit peut-être choisi (≥ 32 bits). Les avantages du procédé de l'invention sont multiples 1. Le nom du lien est dans le cas de la fonction de hachage MD5 est de 128 bits (16 octets), dans le cadre de Java, la plupart des liens (les noms de classe) ont plus de 16 octets. Le code représentant le nom qualifié a donc une longueur constante. La conséquence est un effet de compression, â savoir qu'une classe reconstruite en substituant les chaînes ASCII des liens par MD5 sera plus petite. 2. Lors de l'établissement des liens dynamiques, la différence des codes a lieu dès les premiers bits et la taille du code a une très faible conséquence sur les performances. En fait, le test du code complet (128 bits) n'a généralement lieu qu'une fois. Les codes de hachage présentent une distribution uniforme des différences sur l'ensemble des bits les constituant. 3. Le temps de recherche d'un lien est constant et déterministe. 4. Le moteur de recherche est réalisable par une fonction matérielle qui pourra permettre d'atteindre des vitesses de réalisation de liens très rapides (par rapport â une technique logiciel). 5. Le code de hachage est calculé et non extrait d'une base de référence commune et permet la communication entre systèmes disjoints sans utilisation des noms qualifiés (exemple : RMI de JAVA)- REVENDICATIONS 1. Procédé de réalisation de liens dynamiques au sein d'un système embarqué dans une machine virtuelle, caractérisé en ce que les noms de liens liés à une règle de codage sont remplacés par un code de hachage résultant du hachage de ces noms par une fonction de hachage, ladite fonction de hachage permettant d'associer sans collision, un nom qualifié et un code unique sans le truchement d'une base de référence commune à plusieurs systèmes disjoints. 2. Procédé selon la revendication 1, caractérisé en ce que la fonction de hachage est une des fonctions MD4, MDS, SHA-1, CRC32, CRC64, CRC 128. 3. Procédé selon l'une quelconque des revendications 1 à 2, caractérisé en ce que le code de hachage est issu d'un code de hachage standard plus long replié sur lui-même ou tronqué.